Towards Partial (and Useful) Model Identification for Model-Based Diagnosis Academic Article uri icon

abstract

  • A fundamental requirement for model-based di-agnosis (MBD) is the existence of a model of the diagnosed system. Based on the model, MBD al-gorithms are able to diagnose the faulty compo-nents. Unfortunately, a model is not always avail-able. While it is possible in principle to infer a partial model by repeated trials, performing such trials is time and resource costly for any prac-tical system. Therefore minimizing the number of trials is important. In this paper, we propose three algorithms for learning the model: two al-gorithms are Depth-first search (DFS) based and one algorithm utilizes a binary search algorithm. We evaluate the algorithms theoretically and em-pirically 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 date

  • January 1, 2010