Towards Partial (and Useful) Model Identification for Model-Based Diagnosis

##plugins.themes.bootstrap3.article.main##

##plugins.themes.bootstrap3.article.sidebar##

PDF
Published Oct 11, 2010
DOI https://doi.org/10.36001/phmconf.2010.v2i1.1932
Vladimir Sadov
Department of Computer Science, Bar-Ilan University
Eliahu Khalastchi
Department of Computer Science, Bar-Ilan University
Meir Kalech
Department of Information Systems Engineering, Ben-Gurion University
Gal A. Kaminka
Department of Computer Science, Bar-Ilan University

Abstract

A fundamental requirement for model-based diagnosis (MBD) is the existence of a model of the diagnosed system. Based on the model, MBD algorithms are able to diagnose the faulty components. Unfortunately, a model is not always available. While it is possible in principle to infer a partial model by repeated trials, performing such trials is time and resource costly for any practical system. Therefore minimizing the number of trials is important. In this paper, we propose three algorithms for learning the model: two algorithms are Depth-first search (DFS) based and one algorithm utilizes a binary search algorithm. We evaluate the algorithms theoretically and empirically through thousands of tests and show that one of the DFS-based algorithm scales well and the binary search algorithm is efficient for small systems. Finally, we successfully demonstrate the algorithms on a model of the NAO robot (20 components) to show its capability in real-world domain.

How to Cite

Sadov, V., Khalastchi, E., Kalech, M., & A. Kaminka, G. (2010). Towards Partial (and Useful) Model Identification for Model-Based Diagnosis. Annual Conference of the PHM Society, 2(2). https://doi.org/10.36001/phmconf.2010.v2i1.1932
Abstract 119 | PDF Downloads 140

##plugins.themes.bootstrap3.article.details##

Keywords

Model Identification

References
(Black et al., 2004 ) Richard Black, Austin Donnelly, and Cedric Fournet. Ethernet topology discovery without network assistance. In In ICNP, 2004.

(Daigle et al., 2006 ) Matthew Daigle, Xenofon Koutsoukos, and Gautam Biswas. Multiple fault diagnosis in complex physical systems. In DX-06, pages 69–76, 2006.

(de Kleer and Williams, 1987 ) J. de Kleer and B. C.Williams. Diagnosing multiple faults. Artificial Intelligence, 32(1):97–130, 1987.

(Farkas et al., 2008 ) Janos Farkas, Vinicius G. de Oliveira, Marcos R. Salvador, and Giovanni C. dos Santos. Automatic discovery of physical topology in ethernet networks. In 22nd International Conference on Advanced Information Networking and Applications. IEEE, 2008.

( Han and Kamber, 2001 ) Jiawei Han and Micheline Kamber. Data mining : Concepts and techniques. Morgan Kaufmann, 2001.

(O’Hallaron et al., 2001 ) David R. O’Hallaron, Bruce Lowekamp, and Thomas R. Gross. Topology discovery for large ethernet networks. In ACM Sigcomm 2001, 2001.

(Papadimitriou and Steiglitz, 1982 ) Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: algorithms and complexity. PrenticeHall, Inc., Upper Saddle River, NJ, USA, 1982.

(Steinbauer et al., 2009 ) Gerald Steinbauer, Alexander Kleiner, and Franz Wotawa. Using qualitative and model-based reasoning for sensor validation of autonomous mobile robots. In DX-09, pages 219226, 2009.

(Williams and Ragno, 2007 ) Brian C. Williams and Robert J. Ragno. Conflict-directed a* and its role in model-based embedded systems. Discrete Appl. Math., 155(12):1562–1595, 2007.
Issue
Vol. 2 No. 2 (2010): Proceedings of the 21st International Workshop on the Principles of Diagnosis, held jointly with the Annual Conference of the PHM Society 2010
Section
Poster Presentations

The Prognostic and Health Management Society advocates open-access to scientific data and uses a Creative Commons license for publishing and distributing any papers. A Creative Commons license does not relinquish the author’s copyright; rather it allows them to share some of their rights with any member of the public under certain conditions whilst enjoying full legal protection. By submitting an article to the International Conference of the Prognostics and Health Management Society, the authors agree to be bound by the associated terms and conditions including the following:

As the author, you retain the copyright to your Work. By submitting your Work, you are granting anybody the right to copy, distribute and transmit your Work and to adapt your Work with proper attribution under the terms of the Creative Commons Attribution 3.0 United States license. You assign rights to the Prognostics and Health Management Society to publish and disseminate your Work through electronic and print media if it is accepted for publication. A license note citing the Creative Commons Attribution 3.0 United States License as shown below needs to be placed in the footnote on the first page of the article.

First Author et al. This is an open-access article distributed under the terms of the Creative Commons Attribution 3.0 United States License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.