Bottom-up construction of minimum-cost and/or trees for sequential fault diagnosis

Abstract

The problem of generating the sequence of tests required to reach a diagnostic conclusion with minimum average cost, which is also known as test sequencing problem, is considered. The traditional test sequencing problem is generalized here to include asymmetrical tests. In general, the next test to execute depends on the results of previous tests. Hence the test sequencing problem can naturally be 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 one-step look-ahead heuristic algorithms and basic ideas of Huffman coding to construct AND/OR decision tree bottom-up as opposed to heuristics proposed in the literature that construct the AND/OR trees top-down. The performance of the algorithm is demonstrated on numerous test cases, with various properties.