DOC PREVIEW
MIT 16 412J - Optimal CSPs and Conflict-directed A

This preview shows page 1-2-3-4-5-6-40-41-42-43-44-82-83-84-85-86-87 out of 87 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

MIT 16 412J - Optimal CSPs and Conflict-directed A

Documents in this Course
Load more
Download Optimal CSPs and Conflict-directed A
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Optimal CSPs and Conflict-directed A and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Optimal CSPs and Conflict-directed A 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?