Binary CSPs and Heuristics for Modeling and Diagnosing Dynamic Systems

摘要

In this paper we concentrate on practicalaspects of qualitative modeling and reasoning about physical systems, reporting our experience within the VMBD project1 in applying Constraint Programming techniques to the task of diagnosing a real-life automotive subsystem. We propose a layered modeling approach: qualitative deviations equations as a high level model description language, and Constraint Satisfaction Problems (CSPs)with non binary constraints as underlying implementation formalism. An implementation of qualitative equations systems based on non binary constraints is presented, discussing the applicability o various heuristics. In particular, a greedy heuristic algorithm for cycle cutset decomposition and variable ordering is proposed for efficient reasoning on CSPs derived from qualitative equations. A prototype implementation of a constraint-based diagnostic engine has been developed using CLP(FD) and C++, and some preliminary results on the proposed modeling approach and heuristics are reported.