Introduction
In autonomous systems, identifying a failure is only the first step. For high-stakes applications such as spacecraft or aircraft, the ultimate goal is Fault Detection, Identification, and Reconfiguration (FDIR). While model-based diagnosis has historically excelled at identifying broken components, reconfiguration—the process of restoring system functionality—was often treated as an ad-hoc planning problem or a set of hard-coded recovery scripts.
This paper, originally presented at AAAI-91, establishes a foundational theoretical bridge between diagnosis and reconfiguration. The authors propose that reconfiguration can be framed as a logical consistency problem, mathematically analogous to diagnosis. By doing so, they enable the use of established diagnostic algorithms to automatically generate recovery plans based on a system's structural model.
Theoretical Framework: The Diagnosis-Reconfiguration Analogy
The core contribution of this work is the recognition of a formal symmetry between finding a fault and finding a fix. Building on Reiter’s Theory of Diagnosis (1987), which uses first-order logic to describe system behavior, the authors map the components of a diagnostic problem to a reconfiguration problem.
As shown in the mapping above, the components are directly analogous:
- Diagnosis seeks a set of components whose abnormality (
ab) explains the discrepancy between observed behavior (obs) and the system description (sd). - Reconfiguration seeks a set of components whose reconfiguration (
rcfg) allows the system to satisfy its requirements (reqs) given a modified system description (sd') that accounts for known faults.
By introducing the rcfg(c) predicate as a mirror to ab(c), the authors demonstrate that a reconfiguration engine is essentially a diagnosis engine with different inputs. This allows the application of powerful tools like conflict sets and hitting set algorithms to find minimal reconfigurations—the simplest possible changes needed to restore functionality.
Illustrative Example: Redundant Circuits
To demonstrate the theory in practice, the authors utilize examples such as the redundant electrical circuit shown below.
In this circuit, if a bulb (e.g., b1) fails, the system can reason about its structure to determine that closing a different switch (e.g., r2 or r3) can restore light to the system. The "requirements" define what must be operational, and the reconfiguration engine finds the simplest set of switch changes to meet those requirements despite the failed component. This move away from pre-planned scripts toward a system that reasons about its own structure allows for novel recovery strategies.
Key Insights and Ideas
- Unified Computational Engine: A single software architecture can handle both diagnosis and recovery, significantly reducing the complexity of autonomous controllers.
- Information Gain through Action: Reconfiguration can serve a dual purpose. If a diagnosis is ambiguous (e.g., Part A or Part B might be broken), switching to a backup for Part A acts as a "test" that can confirm the diagnosis while simultaneously attempting a fix.
- Abstraction of Mechanism: The theory decouples the logical state of reconfiguration from physical implementation. Whether the fix involves a software reroute or a mechanical switch, the underlying logic remains the same.
- The Superset Property Challenge: One critical difference identified is that while any superset of a valid diagnosis is also a diagnosis, the same does not hold for reconfiguration. One cannot indefinitely "fix" a system by adding more reconfigurations (e.g., using a single spare for multiple failures).
Key Results and Limitations
The paper successfully formalizes reconfiguration within the consistency-based diagnostic framework, ensuring that systems find the most resource-efficient recovery paths. It also allows for "graceful degradation" by permitting requirements to be downgraded to safe modes if full functionality cannot be restored.
However, several challenges remain for future work:
- The Entailment Problem: The current framework ensures a reconfiguration is consistent with goals but does not strictly entail success, necessitating verification filters.
- Computational Complexity: The cost of searching both diagnostic and reconfiguration spaces can be high, suggesting a need for interleaved processing.
- Physical Constraints: Physical constraints (e.g., mutually exclusive switch states) must be explicitly modeled as axioms to prevent the engine from proposing impossible actions.
Summary updated