A framework and algorithm for model-based active testing

Due to model uncertainty and/or limited observability, the multiple candidate diagnoses (or the associated probability mass distribution) computed by a Model-Based Diagnosis (MBD) engine may be unacceptable as the basis for important decision-making. In this paper we present a new algorithmic approach, called FRACTAL (FRamework for ACtive Testing ALgorithms), which, given an initial diagnosis, computes the shortest sequence of additional test vectors that minimizes diagnostic entropy. The approach complements probing and sequential diagnosis (ATPG), applying to systems where only additional tests can be performed by using a subset of the existing system inputs while observing the existing outputs (called "Active Testing"). Our algorithm generates test vectors using a myopic, next-best test vector strategy, using a low-cost approximation of diagnostic information entropy to guide the search. Results on a number of 74XXX/ISCAS85 combinational circuits show that diagnostic certainty can be significantly increased, even when only a fraction of inputs are available for active testing.