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=<X, DX,C> 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 = <X, DX,C> 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=<Y, g, CSP> Decision variables y with domain d Utility function g(Y:Dy→>界 CSP is over variables <XY> 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= <Y, g, CSP> Decision variables Y with domain DY Utility function g(Y): DY → ℜ CSP is over variables <X,Y> 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