Introduction
In complex systems, identifying the root cause of a failure—known as fault isolation—is a critical but challenging task. Model-Based Diagnosis (MBD) often generates a large set of potential diagnoses, creating ambiguity that hinders effective recovery. FRACTAL (FRamework for ACtive Testing ALgorithms) addresses this by intelligently selecting system inputs to rapidly narrow down the cause of failure through "active testing."
The Challenge of Diagnostic Ambiguity
Traditional MBD engines analyze failing systems to produce a list of candidate diagnoses. In systems with limited sensors, this list can contain thousands of possibilities, making it nearly impossible for technicians or automated systems to take action. While adding sensors is one solution, it is often physically or economically unfeasible. FRACTAL proposes a dynamic approach: choosing the next set of system inputs (controls) to reduce diagnostic uncertainty as quickly as possible.
Methodology: The FRACTAL Framework
FRACTAL employs a two-pronged approach to manage the computational complexity of active testing, which is generally NP-hard.
- Stochastic Expectation: Calculating the exact expected number of remaining diagnoses is computationally expensive. FRACTAL uses a randomized sampling approach to estimate this value efficiently, achieving high correlation with exact counts.
- Greedy Control Strategy: Instead of searching for a perfect sequence of tests, FRACTAL utilizes a "next-best" approach, flipping control bits one by one and retaining changes that reduce the estimated number of diagnoses.
The theoretical foundation of FRACTAL lies in submodularity. The researchers proved that the function used to count diagnoses exhibits diminishing returns—the more you know, the less a new test can tell you. This property guarantees that a simple greedy algorithm will achieve at least ~63% ($1 - 1/e$) of the performance of an ideal, exhaustive search, making it a highly efficient polynomial-time solution.
Evaluation and Key Results
The framework was evaluated using ISCAS85 benchmark circuits, simulating "double-fault" scenarios. The results demonstrate that control can be as effective as sensing; by manipulating inputs and observing existing outputs, internal failures can be deduced.
Key findings include:
- Rapid Convergence: In the
c7552circuit, FRACTAL reduced the number of potential double-fault diagnoses from 46,003 to just 4 in only 6 steps. - Near-Optimal Performance: As shown in the comparison of strategies, the greedy approach performs nearly as well as the exhaustive optimal search while being orders of magnitude faster. For instance, in one test case, FRACTAL took less than 3 seconds, compared to 43 minutes for the optimal search.
- Robustness: The system remains effective even when only a small fraction of the system's inputs are controllable.
Conclusion
FRACTAL demonstrates that active testing, powered by submodular optimization and stochastic estimation, provides a scalable and efficient solution for fault isolation in complex systems. Future work includes extending this framework to sequential circuits with memory states and exploring more complex physical fault models beyond the "stuck-at-opposite" abstraction.
Summary updated