A Model-Based Active Testing Approach to Sequential Diagnosis
  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.
