3/17/2004 copyright Brian Williams, 2002 1 courtesy of JPL Optimal CSPs and Conflict-directed A* Brian C. Williams 16.412J/6.834J March 17 th , 2004 Brian C. Williams, copyright 2000 3/17/2004 copyright Brian Williams, 2002 2 System Model Control Program RMPL Model-based Program Control Sequencer Deductive Controller CommandsObservations Plant Titan Model-based Executive State goalsState estimates Mode Estimation Mode Reconfiguration Tracks likely plant states Tracks least cost goal states z Executes concurrently z Preempts z Queries (hidden) states z Asserts (hidden) state Closed Valve Open Stuck open Stuck closed Open Close 0. 01 0. 01 0.01 0.01 inflow = outflow = 0 Generates target goal states conditioned on state estimates Mode Reconfiguration: Select a least cost set of commandable component modes that entail the current goal, and are consistent Mode Estimation: Select a most likely set of component modes that are consistent with the model and observations arg min P t (Y| Obs) s.t. Ψ(X,Y) ∧ O(m’) is consistent arg max R t (Y) s.t. Ψ(X,Y) entails G(X,Y) s.t. Ψ(X,Y) is consistent 3/17/2004 copyright Brian Williams, 2002 3 Outline ? Optimal CSPs ? Review of A* ? Conflict-directed A* ? Generating the Best Kernel ? Intelligent Tree Expansion ? Extending to Multiple Solutions ? Performance Comparison 3/17/2004 copyright Brian Williams, 2002 4 Constraint Satisfaction Problem CSP = <X, D X ,C> ? variables X with domain D X ? Constraint C(X): D X → {True,False} Find X in D X s.t. C(X) is True R,G,B GR, G Different-color constraint V 1 V 2 V 3 3/17/2004 copyright Brian Williams, 2002 5 Optimal CSP OCSP= <Y, g, CSP> ? Decision variables Y with domain D Y ? Utility function g(Y): D Y →? ? CSP is over variables <X,Y> Find Leading arg max g(Y) Y ∈ D y s.t. ? X ∈ D Y s.t. C(X,Y) is True ? Frequently we encode C in propositional logic ? g() is a multi-attribute utility function that is preferentially independent. 3/17/2004 copyright Brian Williams, 2002 6 CSP Frequently in Propositional Logic (mode(E1) = ok implies (thrust(E1) = on if and only if flow(V1) = on and flow(V2) = on)) and (mode(E1) = ok or mode(E1) = unknown) and not (mode(E1) = ok and mode(E1) = unknown) E1 V1 V2 3/17/2004 copyright Brian Williams, 2002 7 Multi Attribute Utility Functions g(Y) = G(g 1 (y 1 ), g 2 (y 2 ), . . .) where G(u 1 , u 2 … u n ) = G(u 1 ,G(u 2 … u n )) G(u 1 ) = G(u 1 , I G ) Example: Diagnosis g i (mode ij ) = P(y i = mode ij ) G(u 1 ,u 2 ) = u 1 x u 2 I G = 1 3/17/2004 copyright Brian Williams, 2002 8 Mutual Preferential Independence For any subset W ? Y our preference between two assignments to W is independent of the assignment to the remaining variables W – Y. Assignment δ 1 is preferred over δ2 if g(δ 1 ) < g(δ 2 ) Example: Diagnosis ? If M1 = G is more likely than M1 = U, ? Then, {M1 = G, M2 = G, M3 = U, A1 = G, A2 = G} ?Is preferred to {M1 = U, M2 = G, M3 = U, A1 = G, A2 = G} 3/17/2004 copyright Brian Williams, 2002 9 Solving Optimal CSPs Through Generate and Test Generate Candidate Test Candidate Consistent?Keep (Optional) Update Cost Below Threshold? Extract Conflict Done Yes No Yes No Leading Candidates Based on Cost Conflict-directed A* Incremental Sat 3/17/2004 copyright Brian Williams, 2002 10 Outline ? Optimal CSPs ? Review of A* ? Conflict-directed A* ? Generating the Best Kernel ? Intelligent Tree Expansion ? Extending to Multiple Solutions ? Performance Comparison 3/17/2004 copyright Brian Williams, 2002 11 Increasing Cost Feasible Infeasible A* 3/17/2004 copyright Brian Williams, 2002 12 A* Search: Search Tree Problem: State Space Search Problem ? Θ Initial State ? Expand(node) Children of Search Node = next states ? Goal-Test(node) True if search node at a goal-state h Admissible Heuristic -Optimistic cost to go Search Node: Node in the search tree ? State State the search is at ? Parent Parent in search tree ds search node to those to be expanded 3/17/2004 copyright Brian Williams, 2002 13 A* Search: State of Search Problem: State Space Search Problem ? Θ Initial State ? Expand(node) Children of Search Node = adjacent states ? Goal-Test(node) True if search node at a goal-state ? Nodes Search Nodes to be expanded ? Expanded Search Nodes already expanded ? Initialize Search starts at Θ, with no expanded nodes h Admissible Heuristic -Optimistic cost to go Search Node: Node in the search tree ? State State the search is at ? Parent Parent in search tree Nodes[Problem]: ? Remove-Best(f) Removes best cost node according to f ? Enqueue(new-node, f ) Adds search node to those to be expanded 3/17/2004 copyright Brian Williams, 2002 14 A* Search Function A*(problem, h) returns the best solution or failure. Problem pre-initialized. f(x) ← g[problem](x) + h(x) loop do if Nodes[problem] is empty then return failure node ← Remove-Best(Nodes[problem], f) state ← State(node) remove any n from Nodes[problem] such that State(n) = state Expanded[problem] ← Expanded[problem] ∪ {state} new-nodes ← Expand(node, problem) for each new-node in new-nodes unless State(new-node) is in Expanded[problem] then Nodes[problem] ← Enqueue(Nodes[problem], new-node, f ) if Goal-Test[problem] applied to State(node) succeeds then return node end Expand best first 3/17/2004 copyright Brian Williams, 2002 15 A* Search Function A*(problem, h) returns the best solution or failure. Problem pre-initialized. f(x) ← g[problem](x) + h(x) loop do if Nodes[problem] is empty then return failure node ← Remove-Best(Nodes[problem], f) state ← State(node) remove any n from Nodes[problem] such that State(n) = state Expanded[problem] ← Expanded[problem] ∪ {state} new-nodes ← Expand(node, problem) for each new-node in new-nodes unless State(new-node) is in Expanded[problem] then Nodes[problem] ← Enqueue(Nodes[problem], new-node, f ) if Goal-Test[problem] applied to State(node) succeeds then return node end Terminates when . . . 3/17/2004 copyright Brian Williams, 2002 16 A* Search Function A*(problem, h) returns the best solution or failure. Problem pre-initialized. f(x) ← g[problem](x) + h(x) loop do if Nodes[problem] is empty then return failure node ← Remove-Best(Nodes[problem], f) state ← State(node) remove any n from Nodes[problem] such that State(n) = state Expanded[problem] ← Expanded[problem] ∪ {state} new-nodes ← Expand(node, problem) for each new-node in new-nodes unless State(new-node) is in Expanded[problem] then Nodes[problem] ← Enqueue(Nodes[problem], new-node, f ) if Goal-Test[problem] applied to State(node) succeeds then return node end Dynamic Programming Principle . . . 3/17/2004 copyright Brian Williams, 2002 17 Outline ? Optimal CSPs ? Review of A* ? Conflict-directed A* ? Generating the Best Kernel ? Intelligent Tree Expansion ? Extending to Multiple Solutions ? Performance Comparison 3/17/2004 copyright Brian Williams, 2002 18 Increasing Cost Feasible Infeasible Conflict-directed A* 3/17/2004 copyright Brian Williams, 2002 19 Increasing Cost Feasible Infeasible Conflict 1 Conflict-directed A* 3/17/2004 copyright Brian Williams, 2002 20 Increasing Cost Feasible Infeasible Conflict 1 Conflict-directed A* 3/17/2004 copyright Brian Williams, 2002 21 Increasing Cost Feasible Infeasible Conflict 2 Conflict 1 Conflict-directed A* 3/17/2004 copyright Brian Williams, 2002 22 Increasing Cost Feasible Infeasible Conflict 2 Conflict 1 Conflict-directed A* 3/17/2004 copyright Brian Williams, 2002 23 Increasing Cost Feasible Infeasible Conflict 3 Conflict 2 Conflict 1 Conflict-directed A* 3/17/2004 copyright Brian Williams, 2002 24 Increasing Cost Infeasible Conflict 3 Conflict 2 Conflict 1 Conflict-directed A* Feasible 3/17/2004 copyright Brian Williams, 2002 25 Conflict-directed A* Function Conflict-directed-A*(OCSP) returns the leading minimal cost solutions. Conflicts[OCSP] ← {} OCSP ← Initialize-Best-Kernels(OCSP) Solutions[OCSP] ← {} loop do decision-state ← Next-Best-State-Resolving-Conflicts(OCSP) if no decision-state returned or Terminate?(OCSP) then return Solutions[OCSP] if Consistent?(CSP[OCSP ], decision-state) then add decision-state to Solutions[OCSP] new-conflicts ← Extract-Conflicts(CSP[OCSP], decision-state) Conflicts[OCSP] ← Eliminate-Redundant-Conflicts(Conflicts[OCSP] ∪ new-conflicts) end 3/17/2004 copyright Brian Williams, 2002 26 Conflict-directed A* Function Conflict-directed-A*(OCSP) returns the leading minimal cost solutions. Conflicts[OCSP] ← {} OCSP ← Initialize-Best-Kernels(OCSP) Solutions[OCSP] ← {} loop do decision-state ← Next-Best-State-Resolving-Conflicts(OCSP) if no decision-state returned or Terminate?(OCSP) then return Solutions[OCSP] if Consistent?(CSP[OCSP ], decision-state) then add decision-state to Solutions[OCSP] new-conflicts ← Extract-Conflicts(CSP[OCSP], decision-state) Conflicts[OCSP] ← Eliminate-Redundant-Conflicts(Conflicts[OCSP] ∪ new-conflicts) end 3/17/2004 copyright Brian Williams, 2002 27 Increasing Cost Infeasible Conflict 3 Conflict 2 Conflict 1 Conflict-directed A* ? Feasible subregions described by kernel assignments. ? Approach: Use conflicts to search for kernel assignment containing the best cost candidate. Kernel 1 Kernel 2 Kernel 3 Feasible 3/17/2004 copyright Brian Williams, 2002 28 Conflicts & Kernels for Optimal CSPs Conflict: A set of decision variable assignments that are inconsistent with the constraints. Constituent Kernel: An assignment A that resolves a conflict C. A entails null? C Kernel: A minimal set of decision variable assignments that resolves all known conflicts. M1 M2 A1 A B C D E 3 2 2 3 F G X Y Z 10 6 6 12 M3 A2 ? ? 3 2 2 3 3 M1 M3 A1 A B C D E F G X Y Z 10 12 ? 3/17/2004 copyright Brian Williams, 2002 29 Conflict: {M1=G, M2=G, A1=G} M1=U ∨ M2=U ∨ M3=U Constituent Kernels: {M1=U, M2=U, A1=U} ? Select best utility value for unassigned variables Conflict to its constituent kernels ?(M1=G ∧ M2=G ∧ A1=G) 3/17/2004 copyright Brian Williams, 2002 30 Conflicts & Kernels for Optimal CSPs Conflict: A set of decision variable assignments that are inconsistent with the constraints. Constituent Kernel: An assignment A that resolves a conflict C. A entails null? C Kernel: A minimal set of decision variable assignments that resolves all known conflicts. ? Constituent kernels map to kernels by minimal set covering M1 M2 A1 A B C D E 3 2 2 3 F G X Y Z 10 6 6 12 M3 A2 ? ? 3 2 2 3 3 M1 M3 A1 A B C D E F G X Y Z 10 12 ? 3/17/2004 copyright Brian Williams, 2002 31 {M2=U } M1=? ∧ M2=U ∧ M3=? ∧ A1=? ∧ A2=? M1=G ∧ M2=U ∧ M3=G ∧ A1=G ∧ A2=G ? Select best utility value for unassigned variables Extracting a kernel’s best state 3/17/2004 copyright Brian Williams, 2002 32 Next Best State Resolving Conflicts function Next-Best-State-Resolving-Conflicts(OCSP) best-kernel ← Next-Best-Kernel(OCSP) if best-kernel = failure then return failure else return kernel-Best-State[problem](best-kernel) end function Kernel-Best-State(kernel) unassigned ← all variables not assigned in kernel return kernel ∪ {Best-Assignment(v) | v ∈ unassigned} End function Terminate?(OCSP) return True iff Solutions[OCSP] is non-empty Algorithm for only finding the first solution, multiple later. 3/17/2004 copyright Brian Williams, 2002 33 3 2 2 3 3 10 M1 M2 M3 A1 A2 A B C D E F G X Y Z 12 Assume Independent Failures: ? P G(mi) >> P U(mi) ? P single >> P double ? P U(M2) > P U(M1) > P U(M3) > P U(A1) > P U(A2) Example: Diagnosis 3/17/2004 copyright Brian Williams, 2002 34 3 2 2 3 3 10 M1 M2 M3 A1 A2 A B C D E F G X Y Z 12 ? Conflicts / Constituent Kernels ? none ? Best Kernel: ? {} ? Best Candidate: ? ? First Iteration 3/17/2004 copyright Brian Williams, 2002 35 { } M1=? ∧ M2=? ∧ M3=? ∧ A1=? ∧ A2=? M1=G ∧ M2=G ∧ M3=G ∧ A1=G ∧ A2=G ? Select best value for unassigned variables Extracting the kernel’s best state 3/17/2004 copyright Brian Williams, 2002 36 ? Test: M1=G ∧ M2=G ∧ M3=G ∧ A1=G ∧ A2=G 3 2 2 3 3 10 M1 M2 M3 A1 A2 A B C D E F G X Y Z 12 3/17/2004 copyright Brian Williams, 2002 37 ? Test: M1=G ∧ M2=G ∧ M3=G ∧ A1=G ∧ A2=G 3 2 2 3 3 10 M1 M2 M3 A1 A2 A B C D E F G X Y Z 12 6 3/17/2004 copyright Brian Williams, 2002 38 ? Test: M1=G ∧ M2=G ∧ M3=G ∧ A1=G ∧ A2=G 3 2 2 3 3 10 M1 M2 M3 A1 A2 A B C D E F G X Y Z 12 6 6 3/17/2004 copyright Brian Williams, 2002 39 ? Test: M1=G ∧ M2=G ∧ M3=G ∧ A1=G ∧ A2=G 3 2 2 3 3 10 M1 M2 M3 A1 A2 A B C D E F G X Y Z 12 6 6 6 3/17/2004 copyright Brian Williams, 2002 40 ? Test: M1=G ∧ M2=G ∧ M3=G ∧ A1=G ∧ A2=G 3 2 2 3 3 10 M1 M2 M3 A1 A2 A B C D E F G X Y Z 12 6 6 6 12 3/17/2004 copyright Brian Williams, 2002 41 ? Test: M1=G ∧ M2=G ∧ M3=G ∧ A1=G ∧ A2=G 3 2 2 3 3 10 M1 M2 M3 A1 A2 A B C D E F G X Y Z 12 6 6 6 12 ? Extract Conflict and Constituent Kernels: 3/17/2004 copyright Brian Williams, 2002 42 ? Test: M1=G ∧ M2=G ∧ M3=G ∧ A1=G ∧ A2=G 3 2 2 3 3 10 M1 M2 M3 A1 A2 A B C D E F G X Y Z 12 6 6 6 12 ? Extract Conflict and Constituent Kernels: 3/17/2004 copyright Brian Williams, 2002 43 ? Test: M1=G ∧ M2=G ∧ M3=G ∧ A1=G ∧ A2=G 3 2 2 3 3 10 M1 M2 M3 A1 A2 A B C D E F G X Y Z 12 6 6 6 12 ? Extract Conflict and Constituent Kernels: ?[M1=G ∧ M2=G ∧ A1=G] 3/17/2004 copyright Brian Williams, 2002 44 ? Test: M1=G ∧ M2=G ∧ M3=G ∧ A1=G ∧ A2=G ? Extract Conflict and Constituent Kernels: ?[M1=G ∧ M2=G ∧ A1=G] M1=U ∨ M2=U ∨ A1=U 3 2 2 3 3 10 M1 M2 M3 A1 A2 A B C D E F G X Y Z 12 6 6 6 12 3/17/2004 copyright Brian Williams, 2002 45 ? Conflicts / Constituent Kernels ? M1=U ∨ M2=U ∨ A1=U ? Best Kernel: ? M2=U ? Best Candidate: ? M1=G ∧ M2=U ∧ M3=G ∧ A1=G ∧ A2=G Second Iteration 3 2 2 3 3 10 M1 M2 M3 A1 A2 A B C D E F G X Y Z 12 6 6 6 12 ? P G(mi) >> P U(mi) ? P single >> P double ? P U(M2) > P U(M1) > P U(M3) > P U(A1) > P U(A2) 3/17/2004 copyright Brian Williams, 2002 46 ? Test: M1=G ∧ M2=U ∧ M3=G ∧ A1=G ∧ A2=G 3 2 2 3 3 10 M1 M3 A2 A B C D E F G X Y Z 12 A1 3/17/2004 copyright Brian Williams, 2002 47 3 2 2 3 3 10 M1 M3 A2 A B C D E F G X Y Z 12 6 ? Test: M1=G ∧ M2=U ∧ M3=G ∧ A1=G ∧ A2=G A1 3/17/2004 copyright Brian Williams, 2002 48 3 2 2 3 3 10 M1 M3 A2 A B C D E F G X Y Z 12 6 6 ? Test: M1=G ∧ M2=U ∧ M3=G ∧ A1=G ∧ A2=G A1 3/17/2004 copyright Brian Williams, 2002 49 3 2 2 3 3 10 M1 M3 A2 A B C D E F G X Y Z 12 6 4 6 ? Test: M1=G ∧ M2=U ∧ M3=G ∧ A1=G ∧ A2=G A1 3/17/2004 copyright Brian Williams, 2002 50 3 2 2 3 3 10 M1 M3 A2 A B C D E F G X Y Z 12 6 4 6 10 ? Test: M1=G ∧ M2=U ∧ M3=G ∧ A1=G ∧ A2=G A1 3/17/2004 copyright Brian Williams, 2002 51 3 2 2 3 3 10 M1 M3 A2 A B C D E F G X Y Z 12 6 4 6 10 ? Test: M1=G ∧ M2=U ∧ M3=G ∧ A1=G ∧ A2=G A1 ? Extract Conflict: 3/17/2004 copyright Brian Williams, 2002 52 3 2 2 3 3 10 M1 M3 A2 A B C D E F G X Y Z 12 6 4 6 10 ? Test: M1=G ∧ M2=U ∧ M3=G ∧ A1=G ∧ A2=G A1 ? Extract Conflict: ? [M1=G ∧ M3=G ∧ A1=G ∧ A2=G] 3/17/2004 copyright Brian Williams, 2002 53 3 2 2 3 3 10 M1 M3 A2 A B C D E F G X Y Z 12 6 4 6 10 ? Test: M1=G ∧ M2=U ∧ M3=G ∧ A1=G ∧ A2=G A1 ? Extract Conflict: ? [M1=G ∧ M3=G ∧ A1=G ∧ A2=G] M1=U ∨ M3=U ∨ A1=U ∨ A2=U 3/17/2004 copyright Brian Williams, 2002 54 ? Conflicts / Constituent Kernels ? M1=U ∨ M2=U ∨ A1=U ? M1=U ∨ M3=U ∨ A1=U ∨ A2=U ? Best Kernel: ? M1=U ? Best Candidate: ? M1=U ∧ M2=G ∧ M3=G ∧ A1=G ∧ A2=G Second Iteration 3 2 2 3 3 10 M1 M3 A2 A B C D E F G X Y Z 12 6 4 6 10 A1 ? P G(mi) >> P U(mi) ? P single >> P double ? P U(M2) > P U(M1) > P U(M3) > P U(A1) > P U(A2) 3/17/2004 copyright Brian Williams, 2002 55 ? Test: M1=U ∧ M2=G ∧ M3=G ∧ A1=G ∧ A2=G 3 2 2 3 3 10 M2 M3 A1 A2 A B C D E F G X Y Z 12 3/17/2004 copyright Brian Williams, 2002 56 3 2 2 3 3 10 M2 M3 A1 A2 A B C D E F G X Y Z 12 ? Test: M1=U ∧ M2=G ∧ M3=G ∧ A1=G ∧ A2=G 3/17/2004 copyright Brian Williams, 2002 57 3 2 2 3 3 10 M2 M3 A1 A2 A B C D E F G X Y Z 12 6 ? Test: M1=U ∧ M2=G ∧ M3=G ∧ A1=G ∧ A2=G 3/17/2004 copyright Brian Williams, 2002 58 3 2 2 3 3 10 M2 M3 A1 A2 A B C D E F G X Y Z 12 6 6 ? Test: M1=U ∧ M2=G ∧ M3=G ∧ A1=G ∧ A2=G 3/17/2004 copyright Brian Williams, 2002 59 ? Test: M1=U ∧ M2=G ∧ M3=G ∧ A1=G ∧ A2=G 3 2 2 3 3 10 M2 M3 A1 A2 A B C D E F G X Y Z 12 6 6 4 3/17/2004 copyright Brian Williams, 2002 60 ? Test: M1=U ∧ M2=G ∧ M3=G ∧ A1=G ∧ A2=G 3 2 2 3 3 10 M2 M3 A1 A2 A B C D E F G X Y Z 12 6 6 4 12 Consistent! 3/17/2004 copyright Brian Williams, 2002 61 Outline ? Optimal CSPs ? Review of A* ? Conflict-directed A* ? Generating the Best Kernel ? Intelligent Tree Expansion ? Extending to Multiple Solutions ? Performance Comparison 3/17/2004 copyright Brian Williams, 2002 62 A2=U M1=U M3=UA1=U A1=U, A2=U, M1=U, M3=U A1=U M1=U M2=U A1=U M1=U M1=U ∧ A2=U M2=U ∧ M3=U Generating The Best Kernel of The Known Conflicts A1=U, M1=U , M2=U Constituent Kernels ? Minimal set covering is an instance of breadth first search. Insight: ? Kernels found by minimal set covering 3/17/2004 copyright Brian Williams, 2002 63 A1=U, A2=U, M1=U, M3=U A1=U M1=U M2=U M1=U Generating The Best Kernel of the Known Conflicts A1=U, M1=U , M2=U Constituent Kernels ? Minimal set covering is an instance of breadth first search. ? To find the best kernel, expand tree in best first order. Insight: ? Kernels found by minimal set covering 3/17/2004 copyright Brian Williams, 2002 64 Next Best Kernel of Known Conflicts Function Next-Best-Kernel (OCSP) returns the best cost kernel of Conflicts[OCSP]. f(x) ← G[OCSP] (g[OCSP](x), h[OCSP](x)) loop do if Nodes[OCSP] is empty then return failure node ← Remove-Best(Nodes[OCSP], f) add State[node] to Visited[OCSP] new-nodes ← Expand-Conflict(node, OCSP) for each new-node ∈ new-nodes unless ? n ∈ Nodes[OCSP] such that State[new-node] = State[n] OR State[new-node] ∈ Visited[problem] then Nodes[OCSP] ← Enqueue(Nodes[OCSP], new-node, f ) if Goal-Test-Kernel[OCSP] applied to State[node] succeeds Best-Kernels[OCSP] ← Add-To-Minimal-Sets(Best-Kernels[OCSP], best-kernel) if best-kernels ∈ Best-Kernels[OCSP] then return State[node] end An instance of A* 3/17/2004 copyright Brian Williams, 2002 65 M2=U A1=UM1=U M2=U ∨ M1=U ∨ A1=U { } To Expand a Node: ? Select an unresolved Conflict. ? Each child adds a constituent kernel. Expanding a Node to Resolve a Conflict Constituent kernels 3/17/2004 copyright Brian Williams, 2002 66 Terminate when all conflicts resolved Function Goal-Test-Kernel (node, problem) returns True IFF node is a complete decision state. if forall K in Constituent-Kernels(Conflicts[problem]), State[node] contains a kernel in K then return True else return False 3/17/2004 copyright Brian Williams, 2002 67 Admissible h(α): Cost of best state extending partial assignment α ∧ M1=? ∧ M3=? ∧ A1=? ∧ A2=? x P M1=G x P M3=G x P A1=G x P A2=G ? Select best value of unassigned variables f = g + h P M2=u M2=U 3/17/2004 copyright Brian Williams, 2002 68 Admissible Heuristic h ? Let g = <G,g i ,Y> describe a multi-attribute utility fn ? Assume the preference for one attribute x i is independent of another x k ? Called Mutual Preferential Independence: For all u, v ∈Y If g i (u) ≥ g i (v) then for all w G(g i (u),g k (w)) ≥ G(g i (v),g k (w)) An Admissible h: ? Given a partial assignment, to X ? Y ? h selects the best value of each unassigned variable Z = X – Y h(Y) = G({g zi_max | z i ∈Z, max g zi (v ij ))}) v ij ∈D zi ? A candidate always exists satisfying h(Y). 3/17/2004 copyright Brian Williams, 2002 69 Outline ? Optimal CSPs ? Review of A* ? Conflict-directed A* ? Generating the Best Kernel ? Intelligent Tree Expansion ? Extending to Multiple Solutions ? Performance Comparison 3/17/2004 copyright Brian Williams, 2002 70 M2=U A1=UM1=U Order constituents by decreasing likelihood { } >> Expand Only Best Child & Sibling ? Traditionally all children expanded. ? But only need to expand the child with the best candidate, if it can be identified apriori. ? This child is the one with the best estimated cost f = g+h. M2=U ∨ M1=U ∨ A1=U Constituent kernels 3/17/2004 copyright Brian Williams, 2002 71 M2=U Order constituents by decreasing utility { } Expand Only Best Child & Sibling M2=U ∨ M1=U ∨ A1=U Constituent kernels ? Traditionally all children expanded. ? But only need to expand the child with the best candidate, if it can be identified apriori. ? This child is the one with the best estimated cost f = g+h. 3/17/2004 copyright Brian Williams, 2002 72 M1=U ∨ M3=U ∨ A1=U ∨ A2=U M1=U M2=U M1=U When Do We Expand The Childs Next Best Sibling? M2=U ∨ M1=U ∨ A1=U Constituent kernels ? When a best child has a subtree or leaf pruned, it may have lost its best candidate. ? One of the child’s siblings might now have the best candidate. ? Expand child’s next best sibling: ? when child expanded to resolve another conflict. { } 3/17/2004 copyright Brian Williams, 2002 73 Expand Node to Resolve Conflict function Expand-Conflict(node, OCSP) return Expand-Conflict-Best-Child(node, OCSP) ∪ Expand-Next-Best-Sibling (node, OCSP) function Expand-Conflict-Best-Child(node, OCSP) if for all K γ in Constituent-Kernels(Γ[OCSP]) State[node] contains a kernel ∈ K γ then return {} else return Expand-Constituent-Kernel(node,OCSP) function Expand-Constituent-Kernel(node, OCSP) K γ ← = smallest uncovered set ∈ Constituent-Kernels(Γ[OCSP]) C ← {y i = v ij | {y i = v ij } in K γ , y i = v ij is consistent with State[node]} Sort C such that for all i from 1 to |C| - 1, Better-Kernel?(C[i],C[i+1], OCSP) is True Child-Assignments[node] ← C y i = v ij ← C[1], which is the best kernel in K γ consistent with State[node] return {Make-Node({y i = v ij }, node)} 3/17/2004 copyright Brian Williams, 2002 74 Expand Node to Resolve Conflict function Expand-Next-Best-Sibling(node, OCSP) if Root?[node] then return {} else {y i = v ij } ← Assignment[node] {y k = v kl } ← next best assignment in consistent child-assignments[Parent[node]] after {y i = v ij } if no next assignment {y k = v kl } or Parent[node] already has a child with {y k = v kl } then return {} else return {Make-Node({y k = v kl }, Parent[node])} 3/17/2004 copyright Brian Williams, 2002 75 Outline ? Optimal CSPs ? Review of A* ? Conflict-directed A* ? Generating the Best Kernel ? Intelligent Tree Expansion ? Extending to Multiple Solutions ? Performance Comparison 3/17/2004 copyright Brian Williams, 2002 76 A2=U M3=U A1=U, A2=U, M1=U, M3=U A1=U M1=U M2=U A1=U M1=U M1=U ∧ A2=U M2=U ∧ M3=U Multiple Solutions: Systematically Exploring Kernels A1=U, M1=U , M2=U Constituent Kernels 3/17/2004 copyright Brian Williams, 2002 77 Child Expansion For Finding Multiple Solutions If Unresolved Conflicts: If All Conflicts Resolved: M2=U M1=U A1=U A2=G A2=U ? (M2=G ∧ M1=G ∧ A1=G) Conflict { } ? Select unresolved conflict. ? Each child adds a constituent kernel. ? Select unassigned variable y i . ? Each child adds an assignment from D i . 3/17/2004 copyright Brian Williams, 2002 78 {M1=U } Intelligent Expansion Below a Kernel Order assignments by decreasing utility M2=G ∨ M2=U Select Unassigned Variable Expand best child Continue expanding best descendents When leaf visited, expand all next best ancestors. M2=G M3=G A1=G A2=G M2=U M3=U A1=U A2=U {} 3/17/2004 copyright Brian Williams, 2002 79 M1=U ∨ M3=U ∨ A1=U ∨ A2=U M1=U M2=U M1=U Putting It Together: Expansion Of Any Search Node M2=U ∨ M1=U ∨ A1=U Constituent kernels ? When a best child loses any candidate, expand child’s next best sibling: ? If child has unresolved conflicts, expand sibling when child expands next conflict. ? If child resolves all conflicts: expand sibling when child expands leaf. { } M2=G M3=G A1=G A2=G M2=U M3=U A1=U A2=U 3/17/2004 copyright Brian Williams, 2002 80 Outline ? Optimal CSPs ? Review of A* ? Conflict-directed A* ? Generating the Best Kernel ? Intelligent Tree Expansion ? Extending to Multiple Solutions ? Performance Comparison 3/17/2004 copyright Brian Williams, 2002 81 5 6 6 6 5 5 5 5 520 20 20 10 10 10 10 10 10 Clau -se lngth Dec Vars 2.0 2.2 1.6 2.3 4.2 1.6 2.6 7.2 9.2 7.2 27.3 94.4 16.0 41.3 3.217.9 1.26.3 11.0% 5.4% 13.0% 3.9% 5.8% 1.0% 1.1% 3.5% 5.6% 197 434 149 4,060 5,130 13,400 6,260 3,490 50 30 10 50 30 10 50 30 10 Clau -ses Queue Size Conflicts used Queue Size 1,230 Queue Size 12.0%5.41495 6.0%6.43335 13.0%4.21095 3.5%6.092910 4.6%9.71,43010 2.0%5.73,79010 0.83%12.04,2705 2.4%8.12,3605 4.5%3.36835 Nodes Expanded Nodes Expand Nodes Expande d Dom Size Mean CD-CB RatioConflict-directed A*Constraint-based A* (no conflicts) Problem Parameters Performance: With and Without Conflicts 3/17/2004 copyright Brian Williams, 2002 82 When you have eliminated the impossible, whatever remains, however improbable, must be the truth. - Sherlock Holmes. The Sign of the Four. Conflict-directed A* 1. Test Hypothesis 2. If inconsistent, learn reason for inconsistency (a Conflict). 3. Use conflicts to leap over similarly infeasible options to next best hypothesis.