Chinese Journal of Computers   Full Text
Title	Fast Diagnosing Through Diagnostic Graph Analysis
Authors	CHEN Ai-Xiang1) CHEN Qing-Liang2) PAN Jiu-Hui2) JIANG Yun-Fei3) YANG Jin-Ji4)
Address	1)(Department of Mathematics, Guangdong University of Business Studies, Guangzhou 510320) 2)(Department of Computer Science, Jinan University, Guangzhou 510632) 3)(Software Research Institute, Sun Yat-Sen University, Guangzhou 510275) 4)(School of Computer Science, South China Normal University, Guangzhou 510631)
Year	2009
Issue	No.8(1470—1485)
Abstract &   Background	Abstract Given the logical model of system and its input, when an observation of system’s behavior conflicts with the way the system meant to behave, we can determine those components of the system which, when assumed to be functioning abnormally, will explain the discrepancy between the observed and correct system behavior. That is the main idea of model-based diagnosis. The classic diagnosis method is very inefficient because its diagnosis procedure is based on logical reasoning. In this paper, the authors redefine the diagnosis, and introduce a new procedure-based rather than logic-based approach to compute diagnosis based on constructing and analyzing a compact structure which we call a diagnostic graph. It is shown that it is a better choice since the search made by this approach is fundamentally different from the search of classic model-based one. So the approach in this paper can provide a new perspective on the diagnosis problem. Finally, the effectiveness of this methodology is demonstrated by the experimental results. Keywords diagnosis; diagnostic graph; model-based diagnosis; abductive reasoning; automated planning Background Informally, diagnosis can be defined as the task of explaining why a given physical system does not exhibit its nominal behavior. Due to its generality, its dramatic importance in many application domains, and its intrinsic complexity, automated diagnosis has received constant and considerable attention in AI research. Formally speaking, given the logical model of system and its input, when an observation of system’s behavior conflicts with the way the system meant to behave, we can determine those components of the system which, when assumed to be functioning abnormally, will explain the discrepancy between the observed and correct system behavior. That is the main idea of model-based diagnosis. However the classic diagnostic method is very inefficient because its computing procedure is based on logical reasoning. We in this paper redefine the idea of diagnosis based on the original concept of Reiter’s model-based diagnosis. And then we introduce a fast diagnosis method by the data structure of diagnostic graph. In fact, our model is procedure-theoretic rather than logic-theoretic. In our diagnosis model, we have two phases in the processing, first we construct the diagnostic graph according to our system model, and then we implement computations on the graph conversely by the system observations. This is obvious a procedural approach that differs inherently from the traditional pure logical one. We have implemented our method based on Graphplan and LPG and have our tool GDT (Graph Diagnosis Tool). The preliminary experimental results justify the effectiveness of our method. This work are supported by the National Basic Research Program (973 Program) of China under grant No.2005CB321902; the National Natural Science Foundation of China under grant No.60773201; the International Joint Research Project of National Science Foundation under grant No.60911130005; the Start-up Research Fund for Introduced Talents in Jinan University; the Distinguished Young Researcher Nurturing Program in Universities of Guangdong No.LYM08017; the Research Foundation of Science and Technology Plan Project in Guangdong Province of China under grant No.2007B010400068 and the Industry, Education and Research Joint Research Fund of Guangdong Province under grant No.2007B090400095.