Application of Information Gain Based Heuristic Search in Optimal Test Strategy

摘要

The problem of constructing optimal test strategy to diagnose permanent faults in electronic and electromechanical systems is considered. The test strategy problem is formulated as an optimal binary decision construction problem, whose solution is known to be NP-complete. Our approach integrates information gain of test into heuristic search methods to subdue the computational explosion of the optimal test strategy problem. Lower bounds of the expected test cost to getting diagnosis information gain are derived. These information-theoretic lower bounds ensure that an optimal solution is found using the heuristic search algorithms, and have enabled us to obtain optimal test strategy. In addition, the algorithms can obtain all optimal test strategies. The effectiveness of the algorithms is demonstrated on several test cases. As a byproduct, our approach to test strategy can be adapted to solve a wide variety of binary decision problems such as medical diagnosis, data base query, quality assurance, and pattern recognition.