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

Vladimir Sadov, Eliahu Khalastchi, Meir Kalech, and Gal A. Kaminka
Submission Type: 
Full Paper
phmc_10_123.pdf216.42 KBSeptember 22, 2010 - 5:28am

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 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.

Publication Control Number: 
Submission Keywords: 
Model Identification
Submitted by: 

follow us

PHM Society on Facebook Follow PHM Society on Twitter PHM Society on LinkedIn PHM Society RSS News Feed