Speeding Up Model-based Diagnosis by a Heuristic Approach to Solving SAT

B. Stein, O. Niggemann, and T. Lettmann (Germany)


diagnosis, machine learning, model-based reasoning, qual itative reasoning, SAT problem 1 Model-Based Diagnosis, Qualitative Modeling, and Satisfiability This section introduces the idea of model-based diagnosis and a special qualitative modeling approach for modular technical systems. So far, our modeling approach has only be used in the domain of fluidic engineering; however, it is not tailored to a particular plant structure but allows for the generation of behavior descriptions for a


Model-based diagnosis of technical systems requires both a simulation machinery and a logic calculus. The former is responsible for the system’s behavior analysis, the latter controls the actual diagnosis process. Especially when pur suing qualitative simulation, it makes sense to realize the simulation machinery with a logic calculus as well. Say, a qualitatively described hypothesis can directly be mapped onto an instance of the well-known SAT problem. Like wise, an entire diagnosis process, i. e., a sequence of hy pothesis refinements, represents a set of SAT problems. This paper reports on the operationalization of such a SAT-based diagnosis approach. A specific characteristic here is the idea to exploit an ordering of the logical formu las according to their likeliness of being satisfiable. This idea is new in the context of qualitative reasoning, and it leads to a considerable speed up of the diagnosis process. Its applicability has been evaluated in the domain of hy draulic circuit diagnosis.

Important Links:

Go Back