Utilizing Device Behavior in Structure-Based Diagnosis

Abstract

Structure-based approaches to diagnosis provide useful computational guarantees based on a device structure. In particular, these approaches can identify device structures for which the complexity of model-based diagnosis is guaranteed to be linear. Structure-based approaches, however, can fail to answer even the simplest diagnostic queries if the device structure is not well behaved (strongly connected) . We show in this pap er that this deficiency can be addressed to a reasonable extent by utilizing device behavioral properties (its component models in particular) which are typically ignored by structure-based approaches. Specifically, we prese nt a structure-based algorithm for diagnosis which takes advantage of a device behavior and then present experimental results indicating th at our algorithm can lead to significant (orders-of-magnitude) savings over pure structural approaches when applied to strongly connected dev ic es.