APPLICATION OF HEURISTIC-SEARCH AND INFORMATION-THEORY TO SEQUENTIAL FAULT-DIAGNOSIS

The problem of constructing optimal and near-optimal test sequences to diagnose permanent faults in electronic and electromechanical systems is considered. The test sequencing problem is formulated as an optimal binary and/or decision tree construction problem, whose solution is known to be NP-complete. Our approach is based on integrating concepts from information theory and heuristic and/or graph search methods to subdue the computational explosion of the optimal test sequencing problem. Lower bounds on the optimal cost-to-go from the information-theoretic concepts of Huffman coding and entropy are derived. These information-theoretic lower bounds ensure that an optimal solution is found using the heuristic and/or graph search algorithms, and have enabled us to obtain optimal test sequences to problems that are intractable with the traditional dynamic programming techniques. In addition, a class of test sequencing algorithms that provide a trade-off between solution quality and complexity have been derived using the ∈ -optimal and limited search strategies. The effectiveness of the algorithms is demonstrated on several test cases. As a byproduct, our approach to test sequencing can be adapted to solve a wide variety of binary identification problems arising in decision table programming, medical diagnosis, data base query processing, quality assurance, and pattern recognition. © 1990 IEEE