Utilizing Device Behavior in Structure-Based Diagnosis

Abstract

Structure-based approaches to diagnosis pro-vide 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 ap-proaches, however, can fail to answer even the simplest diagnostic queries if the device struc-ture is not well behaved (strongly connected). We show in this paper that this deficiency can be addressed to a reasonable extent by utiliz-ing device behavioral properties (its component models in particular) which are typically ig-nored by structure-based approaches. Specif-ically, we present a structure-based algorithm for diagnosis which takes advantage of a device behavior and then present experimental results indicating that our algorithm can lead to signif-icant (orders-of-magnitude) savings over pure structural approaches when applied to strongly connected devices. 1