ReadingStates are commanded through lengthy pathsHow do we command safely?Model-based Execution & Reactive Planning Burton [Williams & Nayak, IJCAI97]Models are Concurrent Probabilistic AutomataExample: Model-based Execution in ActionPowerPoint PresentationSlide 9To Handle Indirect Control . . .. . . Compile Out ConstraintsSlide 12To Compile Out ConstraintsSlide 14Why Search is NeededSlide 16Slide 17Eliminating Type 1 SearchSlide 19SolutionEliminating Type 3 SearchSlide 22Slide 23Slide 30Solution: Create Factored PoliciesPlan by passing sub-goals up causal graphSlide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Factored, Model-based Reactive PlanningComplexity of Reactive PlanningArtificial Intelligence & Space Systems LaboratoriesMassachusetts Institute of TechnologyReading•B. Williams and P. Nayak, “A Reactive Planner for a Model-based Executive,” International Joint Conference on Artificial Intelligence, 1997.Artificial Intelligence & Space Systems LaboratoriesMassachusetts Institute of TechnologyStates are commanded through lengthy pathsz facing thrusters x facing thrusters1553 busCommandsDataN2H4HePDESRUPDUGDEPASMDSEUPEPEBCFlightComputerFlightComputerBCPDEArtificial Intelligence & Space Systems LaboratoriesMassachusetts Institute of TechnologyHow do we command safely?RemoteTerminalRemoteTerminalDriverBusControlComputerHow do we open a valve?ValveDriverValveModel-based Execution & Reactive PlanningBurton [Williams & Nayak, IJCAI97]State estimatesGoalInterpretationModeEstimationCommandsObservationssˆgoalsReact ivePlanningModelFlight System ControlRT Control LayerGoal statespecificationssˆArtificial Intelligence & Space Systems LaboratoriesMassachusetts Institute of TechnologyModels are Concurrent Probabilistic Automatadcmdout= vcmdinoffonfailedresettabledcmdin = offdcmdin = ondcmdin = resetdcmdin = offdcmdin = dcmdoutclosedopenstuck closedstuck openvcmdin = closevcmdin = openinflow = outflowvcmdindcmdinflowinflowoutArtificial Intelligence & Space Systems LaboratoriesMassachusetts Institute of TechnologyExample: Model-based Execution in ActionValve Driver dr Valve vlvvcmdindcmdinCommands Driver State Valve StateME: dr = off, vlv = openGI: dr = off, vlv = closedRP dcmdin = onME: dr = on, vlv = openRP dcmdin = closeME: dr = reset failure, vlv = openRP dcmdin = resetME: dr = on, vlv = openRP dcmdin = offME: dr = off, vlv = openGoal: No thrustArtificial Intelligence & Space Systems LaboratoriesMassachusetts Institute of TechnologyTo achieve reactivity we eliminate all forms of search.1. Eliminate Indirect Control . . . through Compilation2. Eliminate Search for Goal Ordering . . . through Reversibility and Serialization3. Eliminate Search to find Suitable Transitions . . . by Constructing Factored PolicesArtificial Intelligence & Space Systems LaboratoriesMassachusetts Institute of TechnologyTo achieve reactivity we eliminate all forms of search.1. Eliminate Indirect Control . . . through Compilation2. Eliminate Search for Goal Ordering . . . through Reversibility and Serialization3. Eliminate Search to find Suitable Transitions . . . by Constructing Factored PolicesArtificial Intelligence & Space Systems LaboratoriesMassachusetts Institute of TechnologyTo Handle Indirect Control . . .dcmdout= vcmdinoffonfailedresettabledcmdin = offdcmdin = ondcmdin = resetdcmdin = offdcmdin = dcmdoutclosedopenstuck closedstuck openvcmdin = closevcmdin = openinflow = outflowvcmdindcmdinflowinflowoutArtificial Intelligence & Space Systems LaboratoriesMassachusetts Institute of Technology. . . Compile Out Constraintsclosedopenstuck closedstuck openvcmdin = closevcmdin = openoffonfailedresettabledcmdin = offdcmdin = ondcmdin = resetdcmdin = offdcmdin = dcmdoutinflow = outflowinflow = outflowdcmdout = vcmdindriver = ondriver = ondcmdin = closedcmdin = openvcmdindcmdinflowinflowoutArtificial Intelligence & Space Systems LaboratoriesMassachusetts Institute of Technology. . . Compile Out Constraintsclosedopenstuck closedstuck openoffonfailedresettabledcmdin = offdcmdin = ondcmdin = resetdcmdin = offdriver = ondriver = ondcmdin = closedcmdin = opendcmdinArtificial Intelligence & Space Systems LaboratoriesMassachusetts Institute of TechnologyTo Compile Out Constraints•Eliminate intermediate variables.Transitions are conditioned on mode and control variables•Generate transitions as prime implicates:i next(yi = ei)where i is a conjunction of mode and control variable assignments. •Prime implicates for transitions enumerated using OpSAT–40 seconds on SPARC 20 for 12,000 clause spacecraft model.Artificial Intelligence & Space Systems LaboratoriesMassachusetts Institute of TechnologyTo achieve reactivity we eliminate all forms of search.1. Eliminate Indirect Control . . . through Compilation2. Eliminate Search for Goal Ordering . . . through Reversibility and Serialization3. Eliminate Search to find Suitable Transitions . . . by Constructing Factored PolicesArtificial Intelligence & Space Systems LaboratoriesMassachusetts Institute of TechnologyValveDrivercommand•Example–Current State: driver = on, valve = closed–Goal State: driver = off, valve = open–Achieve: (driver = off) Then: (valve = open) –. . . clobbers (driver = off)Why Search is Needed1) An achieved goal can be clobbered by a subsequent goal. Must achieve Valve goal before Driver goalArtificial Intelligence & Space Systems LaboratoriesMassachusetts Institute of TechnologyLatch1Switchdata•Example–Goal: Latch1 Closed, Latch2 Open Latch1 and Latch2 compete for the position of Switch if goals achieved concurrently.Why Search is Needed2) Two goals can compete for the same variable in their subgoals.Latch212Artificial Intelligence & Space Systems LaboratoriesMassachusetts Institute of TechnologyLatch1Switchdata•Example–Assume Switch can only be used once, –Then Latch1 must be latched before Latch2.Why Search is Needed3) A state transition of a subgoal variable has irreversible effect.Latch212Artificial Intelligence & Space Systems LaboratoriesMassachusetts Institute of TechnologyValveDrivercommand•Example–Current State: driver = on, valve = closed–Goal State: driver = off, valve = open–Achieving (driver = off) and then (valve = open) clobbers (driver = off)Eliminating Type 1 Search1) An achieved goal can be clobbered by a subsequent goal. Achieve Valve goal before Driver goal Achieve downstream goal before upstream goalArtificial Intelligence
View Full Document
Unlocking...