Artificial intelligence has traditionally used constraint satisfaction and logic to frame a wide range of problems, including planning, diagnosis, cognitive robotics and embedded systems control. However, many decision making problems are now being re-framed as optimization problems, involving a search over a discrete space for the best solution that satisfies a set of constraints. The best methods for finding optimal solutions, such as A*, explore the space of solutions one state at a time. This paper introduces conflict-directed A*, a method for solving optimal constraint satisfaction problems. Conflict-directed A* searches the state space in best first order, but accelerates the search process by eliminating subspaces around each state that are inconsistent. This elimination process builds upon the concepts of conflict and kernel diagnosis used in model-based diagnosis [1,2] and in dependency-directed search [3-6]. Conflict-directed A* is a fundamental tool for building model-based embedded systems, and has been used to solve a range or problems, including fault isolation [1], diagnosis [7], mode estimation and repair [8], model-compilation [9] and model-based programming [10].
[Postscript (1,055k)] [PDF (278k)]
Preprint submitted to Journal of Discrete Applied Math, 9 January 2003.
Last updated March 12th, 2003. Direct feedback to Brian C. Williams (williams@mit.edu)