1Constraint Satisfaction ProblemsProblemsArtificial IntelligenceAIMA 2ndedition, chapter 5Section 1 – 3Hadi Moradi1Outline Constraint Satisfaction Problems (CSP)Bkt ki hf CSPBacktracking search for CSPs Local search for CSPs22Constraint satisfaction problems (CSPs) CSP: Stategoal test3Example: Map-Coloring Variables4 Domains Constraints:3Example: Map-Coloring5 Solutions are complete and consistent assignments, Constraint graph Binary CSP: each constraint relates two variables Constraint graph: nodes are variables, arcs are constraints64Varieties of CSPs Discrete variables finite domains: infinite domains:7 Continuous variablesVarieties of constraints Unary constraints involve a single variable, Binary constraints involve pairs of variables,8 Higher-order constraints involve 3 or more variables,5Real-world CSPs Assignment problems Timetabling problemsTransportation scheduling9pg Factory schedulingStandard search formulation (incremental)Let's start with the straightforward approach, then fix itInitialstate:Initial state: Successor function Goal test:B anching facto101.Branching factor:6Backtracking search Variable assignments are commutative}, i.e.,[ WA = red then NT = green ] same as [ NT = green then WA = red ] Depth-first search for CSPs with single-variable assignments is called backtracking search11 Can solve n-queens for n≈ 25Backtracking search127Backtracking example13Backtracking example148Backtracking example15Backtracking example169Improving backtracking efficiency General-purpose methods can give huge gains in speed:gains in speed: Which variable should be assigned next? In what order should its values be tried?17 Can we detect inevitable failure early?Minimum Remaining Variable1810Degree Heuristic Choose the Most constraining variable:19Least constraining value Given a variable, choose the least constraining value:constraining value:2011Forward checking Idea: Keep track of remaining legal values for unassigned variablespgg g Terminate search when any variable has no legal values21Forward checking2212Forward checking23Forward checking2413Constraint propagation Forward checking doesn't provide early detection for all failures:failures: 25Arc consistency Simplest form of propagation makes each arc consistentXÆYiittiffX ÆYis consistent ifffor every value x of X there is some allowed y2614Arc consistency Simplest form of propagation makes each arc consistentXÆYiittiffX ÆYis consistent ifffor every value x of X there is some allowed y27Arc consistency If Xloses a value, neighbors of Xneed to be rechecked2815Arc consistency29Arc consistency algorithm AC-33016Local search for CSPs Hill-climbing, simulated annealing typically work with "complete" states, i.e., all variables assigned To apply to CSPs:31Example: 4-Queens States: 4 queens in 4 columns (44= 256 states) Actions: move queen in column Goal test: no attacks Evaluation: h(n) = number of attacks3217Summary CSPs are a special kind of problem: states defined by values of a fixed set of variablesgoal test defined by constraints on variable valuesgoal test defined by constraints on variable values Backtracking = depth-first search with one variable assigned per node Variable ordering and value selection heuristics help significantly Forward checking prevents assignments that guarantee later failure Constraint propagation (e.g., arc consistency) does additional work to constrain values and detect inconsistencies33constrain values and detect inconsistencies Iterative min-conflicts is usually effective in
View Full Document
Unlocking...