---
title: "FRACTAL: Efficient Fault Isolation Using Active Testing"
authors:
  - "Alexander Feldman"
  - "Gregory M. Provan"
  - "Arjan J. C. van Gemund"
doi: ""
url: "https://ijcai.org/proceedings/2009/134"
pdf: "https://ijcai.org/proceedings/2009/0134.pdf"
venue: "Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence"
year: 2009
pages: "778-783"
track: ""
keywords:
---

# FRACTAL: Efficient Fault Isolation Using Active Testing

Alexander Feldman, Gregory M. Provan, Arjan J. C. van Gemund

*Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence*, pages 778-783.

## Abstract

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.Alexander Feldman, Gregory Provan, Arjan van Gemund