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



Vladimir Sadov Eliahu Khalastchi Meir Kalech Gal A. Kaminka


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).
Abstract 1 | PDF Downloads 1



Model Identification

(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.
Poster Presentations