Optimal csPs and Conflict-directed A* Brian c. williams 16412J/6834J March 17th 2004 courtesy of JPL Brian C Williams, copyright 2000 Mode estimation Mode reconfiguration Select a most likely set of Select a least cost set of component modes that are commandable component consistent with the model and modes that entail the current observations nq goal, and are consistent System Model State estimates e goals Track likely Tracks least plant state cost goal states arg min P(Y Obs arg max R(Y) s.t.P(X,Y)AO(m) is consistent s.t.Y(X, Y)entails G(X,Y) ons pi s.t. Y(X, Y) is consistent
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 17th, 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 Observations Commands Plant Titan Model-based Executive State estimates State goals 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 Pt (Y| Obs) s.t. Ψ(X,Y) ∧ O(m’) is consistent arg max Rt (Y) s.t. Ψ(X,Y) entails G(X,Y) s.t. Ψ(X,Y) is consistent
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 Constraint Satisfaction Problem CSP= variables X with domain Dx Constraint C(X) Dx >True, False] Find X in Dxst C(X)is True RG.B Dififerent-color constrain copyright Brian Williams, 2002
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 = variables X with domain DX Constraint C(X): DX → {True,False} Find X in DX s.t. C(X) is True R,G,B R, G G Different-color constraint V1 V2 V3
Optimal CSP OCSP= Decision variables y with domain d Utility function g(Y:Dy→>界 CSP is over variables Find Leading arg max g(Y) Y∈by st.3XE Dyst C(X,Y)is True Frequently we encode C in propositional logic e g0 is a multi-attribute utility function that is preferentially independent 3/17/2004 copyright Brian Williams, 2002 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) V1 V2 E1 copyright Brian Williams, 2002
3/17/2004 copyright Brian Williams, 2002 5 Optimal CSP OCSP= Decision variables Y with domain DY Utility function g(Y): DY → ℜ CSP is over variables Find Leading arg max g(Y) Y ∈ Dy s.t. ∃ X ∈ DY 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
Multi Attribute Utility Functions g(Y)=G(91y,g2(y2),) where G{u1u2….U=G(u1,G(u2…un) G(u1)=G(u1,1 Example: Diagnosis gi(mode j =P(y;=modei) G(u,, uxu 3/17/2004 copyright Brian Williams, 2002 Mutual Preferential Independence For any subset WcY our preference between two assignments to w is independent of the assignment to the remaining variables W-Y Assignment 0, is preferred over 02 if g(01)<g(02) Example: Diagnosis If M1=G is more likely than M1=U, a Then {M1=G,M2=G,M3=U,A1=G,A2=G} Is preferred to {M1=U,M2=G,M3=U,A1=G,A2=G} copyright Brian Williams, 2002
3/17/2004 copyright Brian Williams, 2002 7 Multi Attribute Utility Functions g(Y) = G(g1(y1), g2(y2), . . .) where G(u1, u2 … un) = G(u1,G(u2 … un)) G(u1) = G(u1, IG) Example: Diagnosis gi (modeij) = P(yi = modeij) G(u1,u2) = u1 x u2 IG = 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}
Solving Optimal CSPs Through Generate and Test Leading Candidates Generate Conflict-directed A* Based on Cost Candidate Test Incremental Sat Candidate Yes Keep Consistent Extract Conflic (Optional) Update Cost Donekres No Threshold 3/17/2004 copyright Brian Williams, 2002 Outline Optimal csps Review of a Conflict-directed A Generating the Best Kernel Intelligent Tree Expansion EXtending to Multiple Solutions Performance Comparison copyright Brian Williams, 2002
3/17/2004 copyright Brian Williams, 2002 9 Solving Optimal CSPs Through Generate and Test Generate Candidate Test Candidate Keep Consistent? (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
A Increasing Cost Infeasible Feasible 3/17/2004 opyright Brian Williams, 2002 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-stat Admissible Heuristic-Optimistic cost to go Search node: Node in the search tree State State the search is at Parent Parent in search tree copyright Brian Williams, 2002
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
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 e, with no expanded nodes 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 A米 Search Function A*(problem, h) returns the best solution or failure Problem pre-initialized f(×)←- pRoblem](x)+h(x) loop do xpand if Nodes[ problem] is empty then return failure best first node <Remove-Best(Nodes[problem], f) state← State(node) remove any n from Nodes[problem] such that State(n)=state Expanded[problem]<Expanded [problem]u(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[], new-node, if Goal-Test[problem] applied to State(node) succeeds then return node end 3/17/2004 copyright Brian Williams, 2002
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
A Search Function A*(problem, h) returns the best solution or failure Problem pre-initialized f(×)←- problem](x)+h(x) op Terminates if Nodes[problem] is empty then return failure when node < Remove-Best(Nodes[problem], f) state←- State(noe) remove any n from Nodes[problem] such that State(n )= state Expanded[problem]<Expanded[problem]u(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, if Goal-Testiproblem] applied to state(node) succeeds then return node end 3/17/2004 copyright Brian Williams, 2002 A米 Search Function A*(problem, h) returns the best solution or failure Problem pre-initialized f(×)←- pRoblem](x)+h(x) Dynamic loop do if Nodes[ problem] is empty then return failure Programming node +Remove-Best(Nodes[problem f) Principle state← State( node) remove any n from Nodes[problem] such that State(n)= state Expanded[problem]<Expanded[problem]u(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, if Goal-Test[problem] applied to State(node) succeeds then return node end 3/17/2004 copyright Brian Williams, 2002
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 . .
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 Conflict-directed A* Increasing Cost Infeasible Feasible copyright Brian Williams, 2002
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*
Conflict-directed A* Increasing Cost Conflict 1 Infeasible Feasible 3/17/2004 opyright Brian Williams, 2002 Conflict-directed A* Increasing Cost ○○O Conflict 1 Infeasible Feasible copyright Brian Williams, 2002
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*
