Proceedings

Utilizing Device Behavior in Structure-Based Diagnosis

Download BibTeX Cite

Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Qualitative Reasoning and Diagnosis. Pages 1096-1100.

© 1999 International Joint Conferences on Artificial Intelligence

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.

  1. Darwiche, 1998) Adnan Darwiche. Model-based diag- nosis using structured system descriptions. Journal of Artificial Intelligence Research, 8:165-222, 1998.
  2. Darwiche, 1999) Adnan Darwiche. Compiling knowl- edge into decomposable negation normal form . Tech- nical Report R-262, Cognitive Systems Laboratory, UCLA, 1999. IJCAI
  3. Dechter and Dechter, 1996) Rina Dechter and Avi Dechter. Structure-driven algorithms for truth main- tenance. Artificial Intelligence, 82:1-20, 1996.
  4. Geffner and Pearl, 1987) Hector Geffner and Judea Pearl. An improved constraint-propagation algorithm for diagnosis. In Proceedings of IJCAI, pages 1105- 1111, Milan, Italy, 1987.
  5. Hamscher et al., 1992) Walter Hamscher, Luca Con- sole, and Johan de Kleer. Readings in Model-Based Diagnosis. Morgan Kaufmann Publishers, Inc., San Mateo, California, 1992.
  6. Jensen et al., 1990) F. V. Jensen, S.L. Lauritzen, and K.G. Olesen. Bayesian updating in recursive graphical models by local computation. Computational Statis- tics Quarterly, 4:269-282, 1990.
  7. Pearl, 1988) Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards