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. The 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 are derived from the information-theoretic concepts of Huffman coding and entropy, which ensure that an optimal solution is found using the heuristic AND/OR graph search algorithms. This makes it possible 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 tradeoff between optimality 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 by-product, this approach to test sequencing can be adapted to solve a wide variety of binary identification problems arising in other fields