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.

In Model-Based Diagnosis (MBD), the problem of computing a diagnosis in a strong-fault model (SFM) is computationally much harder than in a weak-fault model (WFM). For example, in propositional Horn models, computing the first minimal diagnosis in a weak-fault model (WFM) is in P but is NP-hard for strong-fault models. As a result, SFM problems of practical significance have not been studied in great depth within the MBD community. In this paper we describe an algorithm that renders the problem of computing a diagnosis in several important SFM subclasses no harder than a similar computation in a WFM. We propose an approach for efficiently computing minimal diagnoses for these subclasses of SFM that extends existing conflict-based algorithms like GDE (Sherlock) and CDA*. Experiments on ISCAS85 combinational circuits show (1) inference speedups with CDA* of up to a factor of 8, and (2) an average of 28% reduction in the average conflict size, at the price of an extra low-polynomial-time consistency check for a candidate diagnosis.

Model-Based Diagnosis (MBD) approaches often yield a large number of diagnoses, severely limiting their practical utility. This paper presents a novel active testing approach based on MBD techniques, called FRACTAL (FRamework for ACtive Testing ALgorithms), which, given a system description, computes a sequence of control settings for reducing the number of diagnoses. The approach complements probing, sequential diagnosis, and ATPG, and applies to systems where additional tests are restricted to setting a subset of the existing system inputs while observing the existing outputs. This paper evaluates the optimality of FRACTAL, both theoretically and empirically. FRACTAL generates test vectors using a greedy, next-best strategy and a low-cost approximation of diagnostic information entropy. Further, the approximate sequence computed by FRACTAL's greedy approach is optimal over all poly-time approximation algorithms, a fact which we confirm empirically. Extensive experimentation with ISCAS85 combinational circuits shows that FRACTAL reduces the number of remaining diagnoses according to a steep geometric decay function, even when only a fraction of inputs are available for active testing.