A Novel Encoding for Model-Based Diagnosis

Model-based diagnosis (MBD), a well-known approach in the AI field, aims at identifying the root cause of a diagnosis problem. Since computing diagnosis is computationally challenging, some MBD algorithms by modifying the model encode are presented successively, such as Dominator-Oriented Encoding (DOE) approach. In this study, we propose a new encoding process, Observation-Oriented Encoding (OOE), which uses two ideas to simplify MBD model. Firstly, we consider more filtered edges based on observation of system and output of dominated components. This idea can reduce the number of encoded clauses for diagnosis system and observations. Secondly, more components are filtered by finding out observation-based filtered nodes. This approach reduces the number of encoded clauses for components. All of them can reduce the number of encoded clauses efficiently. Furthermore, experiment evaluations on ISCAS85 and ITC99 benchmarks, which contain well-known combinational circuits used for MBD algorithms, show that OOE approach generates less weighted conjunctive normal forms (WCNF) and makes diagnosis easier with maximum satisfiability (MaxSAT) solver, compared with DOE, the latest encoding algorithms for MBD, and Basic Encoding (BE), which is the traditional encoding approach for MBD. In addition, OOE approach returns a solution in a shorter time than DOE and BE approaches.