Peer-Reviewed Journal Details
Mandatory Fields
Feldman, A,Provan, G,van Gemund, A;
2010
January
Journal of Artificial Intelligence Research
A Model-Based Active Testing Approach to Sequential Diagnosis
Validated
()
Optional Fields
FAULT-DIAGNOSIS ALGORITHMS
39
301
334
Model-based diagnostic reasoning often leads to a large number of diagnostic hypotheses. The set of diagnoses can be reduced by taking into account extra observations (passive monitoring), measuring additional variables (probing) or executing additional tests (sequential diagnosis/test sequencing). In this paper we combine the above approaches with techniques from Automated Test Pattern Generation (ATPG) and Model-Based Diagnosis (MBD) into a framework called Fractal (FRamework for ACtive Testing ALgorithms). Apart from the inputs and outputs that connect a system to its environment, in active testing we consider additional input variables to which a sequence of test vectors can be supplied. We address the computationally hard problem of computing optimal control assignments (as defined in Fractal) in terms of a greedy approximation algorithm called Fractal(G). We compare the decrease in the number of remaining minimal cardinality diagnoses of Fractal(G) to that of two more Fractal algorithms: Fractal(ATPG) and Fractal(P). Fractal(ATPG) is based on ATPG and sequential diagnosis while Fractal(P) is based on probing and, although not an active testing algorithm, provides a baseline for comparing the lower bound on the number of reachable diagnoses for the Fractal algorithms. We empirically evaluate the trade-offs of the three Fractal algorithms by performing extensive experimentation on the ISCAS85/74XXX benchmark of combinational circuits.
Grant Details