2/22/2005 copyright Brian Williams, 2002 1courtesy of JPLOptimal CSPs andConflict-directed A*Brian C. Williams16.412J/6.834JFebruary 22nd, 2005Brian C. Williams, copyright 20002/22/2005 copyright Brian Williams, 2002 2System ModelControl ProgramRMPL Model-based ProgramControl SequencerDeductive ControllerCommandsObservationsPlantTitan Model-based ExecutiveState goalsState estimatesModeEstimationModeReconfigurationTrackslikely plant statesTracks least cost goal statesz Executes concurrentlyz Preemptsz Queries (hidden) statesz Asserts (hidden) stateClosedClosedValveValveOpenOpenStuckStuckopenopenStuckStuckclosedclosedOpenOpenCloseClose0. 010. 010. 010. 010.010.010.010.01inflow = outflow = 0Generates target goal statesconditioned on state estimatesMode Reconfiguration:Select a least cost set of commandable component modes that entail the current goal, and are consistentMode Estimation:Select a most likely set of component modes that are consistent with the model and observationsarg min Pt(Y| Obs)s.t. Ψ(X,Y) ∧ O(m’) is consistentarg max Rt(Y)s.t. Ψ(X,Y) entails G(X,Y)s.t. Ψ(X,Y) is consistent2/22/2005 copyright Brian Williams, 2002 3Outline• Optimal CSPs• Application to Model-based Execution Review of A* Conflict-directed A* Generating the Best Kernel Intelligent Tree Expansion Extending to Multiple Solutions Performance Comparison2/22/2005 copyright Brian Williams, 2002 4Constraint Satisfaction ProblemCSP = <X, DX,C> variables X with domain DX Constraint C(X): DX → {True,False}Find X in DX s.t. C(X) is TrueR,G,BGR, GDifferent-color constraintV1V2V32/22/2005 copyright Brian Williams, 2002 5Optimal CSPOCSP= <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 ∈ Dys.t. ∃ X ∈ DXs.t. C(X,Y) is TrueÎ Frequently we encode C in propositional state logicÎ g() is a multi-attribute utility function that is preferentially independent.2/22/2005 copyright Brian Williams, 2002 6CSP 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) andnot (mode(E1) = ok and mode(E1) = unknown)V1 V2E12/22/2005 copyright Brian Williams, 2002 7Multi Attribute Utility Functionsg(Y) = G(g1(y1), g2(y2), . . .)whereG(u1, u2… un) = G(u1,G(u2… un))G(u1) = G(u1, IG)Example: Diagnosisgi(yi=modeij) = P(yi= modeij)G(u1,u2) = u1x u2IG= 12/22/2005 copyright Brian Williams, 2002 8Mutual Preferential IndependenceAssignment δ1is preferred over δ2if g(δ1) < g(δ2) For any set of decision variables W ⊆ Y, our preference between two assignments to W is independent of the assignment to the remaining variables W – Y.2/22/2005 copyright Brian Williams, 2002 9Mutual Preferential IndependenceExample: 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}2/22/2005 copyright Brian Williams, 2002 10Reconfiguration via Conflict Learningarg max Rt(Y)s.t. Ψ(X,Y) entails G(X,Y)s.t. Ψ(X,Y) is consistentGoal: Achieve ThrustA conflict is an assignment to a subset of the control variables that entails the negation of the goal.2/22/2005 copyright Brian Williams, 2002 11Approximate PCCA Belief State UpdateApproximate PCCA Belief State UpdateStandbyStandbyEngine ModelEngine ModelOffOffFailedFailedoffoff--cmdcmdstandbystandby--cmdcmd0.010.01(thrust = full) AND(power_in = nominal)FiringFiring0.010.01standbystandby--cmdcmdfirefire--cmdcmd(thrust = zero) AND(power_in = zero)(thrust = zero) AND(power_in = nominal)OnOnCamera ModelCamera ModelOffOffturnoffturnoff--cmdcmdturnonturnon--cmdcmd(power_in = zero) AND(shutter = closed)(power_in = nominal) AND(shutter = open)0 v2 kv2 kv0 v0 v20 v0.010.010.010.010 vSTX0X1XN-1XN•Assigns a value to each variable (e.g.,3,000 vars).•Consistent with all state constraints (e.g., 12,000).•A set of concurrent transitions, one per automata (e.g., 80).•Previous & Next states consistent with source & target of transitions2/22/2005 copyright Brian Williams, 2002 12Belief State Propagation Propagation Equation propagates the system dynamics Update Equation updates prior distribution with observations2/22/2005 copyright Brian Williams, 2002 13Best-First Belief State Enumeration• Enumerate next state priors in best first order• Evaluate likelihood of partial states using optimistic estimate of unassigned variables. HMM propagate equation Assuming independent transitionscost so far, g optimistic estimate of the cost to go, h2/22/2005 copyright Brian Williams, 2002 14Outline• Optimal CSPs Application to Model-based Execution Review of A* Conflict-directed A* Generating the Best Kernel Intelligent Tree Expansion Extending to Multiple Solutions Performance Comparison2/22/2005 copyright Brian Williams, 2002 15A* IncreasingCostInfeasibleFeasible2/22/2005 copyright Brian Williams, 2002 16A* Search: Search TreeProblem: State Space Search Problem Θ Initial State Expand(node) Children of Search Node = next states Goal-Test(node) True if search node at a goal-stateh Admissible Heuristic -Optimistic cost to goSearch Node: Node in the search tree State State the search is at Parent Parent in search treeds search node to those to be expanded2/22/2005 copyright Brian Williams, 2002 17A* Search: State of SearchProblem: 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 nodesg(state) Cost to stateh(state) Admissible Heuristic-Optimistic cost to goSearch Node: Node in the search tree State State the search is at Parent Parent in search treeNodes[Problem]: Enqueue(node, f ) Adds node to those to be expanded Remove-Best(f) Removes best cost queued node according to f2/22/2005 copyright Brian Williams, 2002 18A* SearchFunction A*(problem, h)returns the best solution or failure. Problem pre-initialized.f(x) ← g[problem](x) + h(x)loop donode ← Remove-Best(Nodes[problem], f)new-nodes ← Expand(node, problem)for each new-node in new-nodesthen Nodes[problem] ← Enqueue(Nodes[problem], new-node, f )endExpandbest first2/22/2005 copyright Brian Williams, 2002 19A* SearchFunction
View Full Document