Conflict-directed A* and Its Role inModel-based Embedded Systems1Brian C. Williams and Robert J. RagnoSpace Systems and Artificial Intelligence LaboratoriesMassachusetts Institute of Technology, Rm 37-381Cambridge, Massachusetts 02139AbstractArtificial intelligence has traditionally used constraint satisfaction and logic to framea wide range of problems, including planning, diagnosis, cognitive robotics andembedded systems control. However, many decision making problems are now beingre-framed as optimization problems, involving a search over a discrete space forthe best solution that satisfies a set of constraints. The best methods for findingoptimal 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 constraintsatisfaction problems. Conflict-directed A* searches the state space in best firstorder, but accelerates the search process by eliminating subspaces around each statethat are inconsistent. This elimination process builds upon the concepts of conflictand kernel diagnosis used in model-based diagnosis[1,2] and in dependency-directedsearch[3–6]. Conflict-directed A* is a fundamental tool for building model-basedembedded systems, and has been used to solve a range of problems, including faultisolation[1], diagnosis[7], mode estimation and repair[8], model-compilation[9] andmodel-based programming[10].1 IntroductionThe approach of focusing search based on summaries of logical inconsistencyis a venerable problem solving method within AI. These descriptions havegone under various names, such as nogoods[3], conflicts [11,12,1], eliminationsets[6], or exclusion relations[13]; in this paper we use the term conflict. PastEmail addresses: [email protected] (Brian C. Williams), [email protected](Robert J. Ragno).1Supported by DARPA Mobies program under contract F33615-00-C-1702.Preprint submitted to Journal of Discrete Applied Math 6 December 2001work has concentrated extensively on using conflicts to find a solution that isconsistent with a set of constraints. Consistency, however, says nothing aboutthe quality of the solution. Hence, AI is shifting increasingly towards problemformulations that involve finding a set of best solutions, given a utility functionthat measures the quality of the solution. The task of generalizing conflict-directed search to handle constraint-based optimization problems is an openresearch frontier. In this paper we demonstrate how conflicts, when combinedwith A* search, provide a powerful method for finding optimal solutions todiscrete constraint satisfaction problems. We call this method conflict-directedA*.One of the earliest systems to exploit conflicts is Hacker [14], a repair-basedplanner that eliminates conflicts between a set of goals and a proposed plan.Subsequently, conflicts between current and intended states have been used tofocus problem solving in a broad range of applications, including circuit analy-sis[3], diagnosis[12,11,1,15–17], qualitative reasoning[18,19], planning, schedul-ing[20], constraint satisfaction[4,6] and propositional inference[21]. In theseapproaches a conflict takes on many forms, such as a discrepancy between asolution and a goal, a hypothesis and a set of observables, or a set of constraintsthat are logically inconsistent.Methods that use conflicts to focus search fall into three basic paradigms.Systematic, backtrack search methods use conflicts extensively to select back-track points. Examples include dependency-directed backtracking [3], intelli-gent backtracking, conflict-directed backjumping[22] and dynamic backtrack-ing[6].Conflicts have proven equally useful for guiding local search. Representativeexamples include Hacker[14] for planning, Min-Conflict for constraint satisfac-tion [20], and GSAT or WalkSat for propositional satisfiability[21,23,24]. Inthese approaches a local operator is selected based on the number of conflictsit eliminates.Conflict-directed A* builds upon a third approach, which uses conflicts to solveconstraint satisfaction problems using divide and conquer. We will refer to thisas conflict-directed divide and conquer (CDC). CDC plays an integral role inthe General Diagnostic Engine (GDE) [1], and has been incorporated withina range of diagnostic methods [17]. GDE frames diagnosis as a constraintsatisfaction problem that involves finding assignments of modes to componentsthat are consistent with a device model and a set of observations. CDC beginsby searching in parallel for all “smallest” partial assignments that producean inconsistency. These partial assignments are called conflicts.Thesetofconflicts are then combined to produce compact descriptions of all feasiblestates, called kernel diagnoses. The key feature of CDC is its ability to reasonintensionally about collections of states rather than states individually. This2reduces the effective size of the search space explored.A significant limitation of CDC is that many practical applications only requireone or a few best solutions, rather than all solutions. In this case CDC’sapproach of generating all solutions and all conflicts in parallel can wastesignificant effort. This limitation is exacerbated by the fact that the set ofabstract descriptions – conflicts and kernel diagnoses – grows exponentiallyin the worst case. Hence in the model-based diagnosis community, CDC fellincreasingly to the wayside during the 90’s, being replaced by methods thatenumerate the state space in best first order [7,25,8].Research on these best first enumeration methods have grappled with threekey questions:• Can we use conflicts to effectively reason about classes of states, when weare only interested in a few best solutions, not all solutions?• Can theories of diagnosis based on conflicts and kernel diagnoses be rigor-ously unified with theories of diagnosis as best-first search?• Can general purpose, conflict-directed methods for solving constraint sat-isfaction problems (CSPs) be unified with informed methods for best-firstsearch?We resolve these questions in this paper by first defining a family of problemscalled Optimal Constraint Satisfaction Problems (see Section 3). An optimalCSP is a multi-attribute decision problem whose decision variables are con-strained by a set of finite domain constraints. We focus on the solution to op-timal CSPs whose attributes are preferentially independent, a
View Full Document
Unlocking...