Citation
Abstract
Over the past decade, the number of Earth orbiters and deep-space probes has grown dramatically and is expected to continue to do so in the future as miniaturization technologies drive spacecraft to become more numerous and more complex. This rate of growth has brought a new focus on autonomous and self-preserving systems that depend on fault diagnosis. Although diagnosis is needed for any autonomous system, current approaches are almost uniformly ad hoc, inefficient, and incomplete. Systematic methods of general diagnosis exist in literature, but they all suffer from two major drawbacks that severely limit their practical applications. First, they tend to be large and complex and hence difficult to apply. Second and more importantly, in order to find the minimal diagnosis set, i.e., the minimal set of faulty components, they rely on algorithms with exponential computational cost and hence are highly impractical for application to many systems of interest. In this article, we propose a two-fold approach to overcoming these two limitations and to developing a new and powerful diagnosis engine. First, we propose a novel and compact reconstruction of the general diagnosis engine (GDE) as one of the most fundamental approaches to model-based diagnosis. We then present a novel algorithmic approach for calculation of the minimal diagnosis set. Using a powerful yet simple representation of the calculation of the minimal diagnosis set, we map the problem onto two well-known problems—that is, the Boolean satisfiability and 0/1 integer programming problems. The mapping onto the Boolean satisfiability problem enables the use of very efficient algorithms with a superpolynomial rather than an exponential complexity for the problem. The mapping onto the 0/1 integer programming problem enables the use of a variety of algorithms that can efficiently solve the problem for up to several thousand components. These new algorithms are a significant improvement over the existing ones, enabling efficient diagnosis of large, complex systems. In addition, the latter mapping allows one, for the first time, to determine the bound on the solution, i.e., the minimum number of faulty components, before solving the problem. This is a powerful insight that can be exploited to develop yet more efficient algorithms for the problem.
Keywords
Details
- Volume
- 42-149
- Published
- May 15, 2002
- Pages
- 1–10
- File Size
- 125.5 KB