Deductive ControllerModeEstimationModeReconfigurationPDEBCFlightComputerReactivePlannerReactive Planning of Hidden States in Large State Spaces Through Decomposition and Serialization Brian C. Williams Joint with Seung H. Chung 16.412J/6.834J March 16 th, 2005 Control Sequencer Environment Model CommandsObservations Control Program Kirk Model-based ExecutiveRMPL Model-based Program location goalslocation estimates Selects consistent threads of activity from redundant methods Tracks location Finds least cost paths � Executes concurrently � Preempts � non -deterministic choice � A[l,u ] timing � A at l location HOMEHOMET W O Enroute COLLECTION POINTCOLLECTION POINTRENDEZVOUSRENDEZVOUSDiverge SCIENCE AREA 1’SCIENCE AREA 1’SCIENCE AREA 3SCIENCE AREA 3Landing Site: ABC Landing Site: XYZ O N E SCIENCE AREA 1SCIENCE AREA 1Executive • pre-plans activities • pre-plans paths • dynamically schedules [Tsmardinos et al.] Plant Schedules and Dispatches Activities Dynamically CSAIL Massachusetts Institute of Technology Outline • The need for model-based reactive planning • The Burton model-based reactive planner CSAIL Massachusetts Institute of Technology DS 1 Attitude Control System z facing thrusters x facing thrusters 1553 bus CommandsDataN2H4 HeSRU PDU GDE PASM DSEU PEPE Flight Computer BC PDE Livingstone reconfigured modes using one step commands. But how does the flight computer really open a valve? • Requires turning on device drivers • Requires repairing bus controllers • Sending commands • Powering down devices . . . CSAIL Massachusetts Institute of Technology Remote Terminal Remote Terminal Driver Bus ControlComputer Valve Driver Valve • Device modes are changed through indirect commanding . • Communication paths are established by reconfiguring other devices. • The task of reconfiguring devices in the proper order generalizes state-space planning to handle indirect effects. • To achieve reactivity all possible plans for all possible goal states should be pre -compiled (a generalization of universal plans). � To achieve compactness we decompose these universal plans according to a goal/sub-goal hierarchy. How do we reconfigure a valve? Massachusetts Institute of TechnologyMERS Model- based Embedded & Robotic Systems Group Mode Reconfiguration Model -based Programming of Intelligent Embedded Systems and Robotic Explorers [Williams et al., IEEE’03] Reactive Planner for a Model -based Executive [Williams & Nayak, IJCAI 97] Goal Interpreter Configuration Goal Command Goal State State Estimate (Current) Reactive Planner CommandGoal StateState Estimate(Current)1CSAIL Massachusetts Institute of Technology Example: Driver Valve Command Sequence Valve Driver dr Valve vlv vcmdindcmdin Commands Driver State Valve State ME: dr = off, vlv = open GI: dr = off, vlv = closed MRP dcmdin = on ME: dr = on, vlv = open MRP dcmdin = close ME: dr = reset failure, vlv = open MRP dcmdin = reset ME: dr = on, vlv = open MRP dcmdin = off ME: dr = off, vlv = open Goal: No thrust CSAIL Massachusetts Institute of Technology To achieve reactivity we eliminate all forms of search. CSAIL Massachusetts Institute of Technology Model-based Reactive Planning Achieved by: 1. Eliminate Indirect Control . . . through Compilation 2. Eliminate Search for Goal Ordering . . . through Reversibility and Serialization 3. Eliminate Search to find Suitable Transitions . . . by Constructing Hierarchical Polices CSAIL Massachusetts Institute of Technology Model-based Reactive Planning Achieved by: 1. Eliminate Indirect Control . . . through Compilation 2. Eliminate Search for Goal Ordering . . . through Reversibility and Serialization 3. Eliminate Search to find Suitable Transitions . . . by Constructing Hierarchical Polices CSAIL Massachusetts Institute of Technology To Handle Indirect Control . . . dcmdout = vcmdin off on failed resettable dcmdin = offdcmdin = on dcmdin = reset dcmdin = off dcmdin = dcmdout closed open stuck closed stuck open vcmdin = closevcmdin = open inflow = outflow vcmdindcmdin flowin flowout CSAIL Massachusetts Institute of Technology . . . Compile Out Constraints closed open stuck closed stuck open vcmdin = closevcmdin = open off on failed resettable dcmdin = offdcmdin = on dcmdin = reset dcmdin = off dcmdin = dcmdout inflow = outflowinflow = outflowdcmdout = vcmdin driver = ondriver = on dcmdin = closedcmdin = open vcmdindcmdin flowin flowout 2CSAIL Massachusetts Institute of Technology . . . Compile Out Constraints closed open stuck closed stuck open off on failed resettable dcmdin = offdcmdin = on dcmdin = reset dcmdin = off driver = ondriver = on dcmdin = closedcmdin = open dcmdin CSAIL Massachusetts Institute of Technology To Compile Out Constraints • Eliminate intermediate variables. � Transitions are conditioned on mode and control variables • Generate transitions as prime implicates: Fi � next(yi i) where Fi is a conjunction of mode and control variable assignments. �– = ePrime implicates for transitions enumerated using OpSAT 40 seconds on SPARC 20 for 12,000 clause spacecraft model. CSAIL Massachusetts Institute of Technology Achieved by: 1. Eliminate Indirect Effects . . . through Compilation 2. Eliminate Search for Goal Ordering . . . through Reversibility and Serialization 3. Eliminate Search to find Suitable Transitions . . . by Constructing Hierarchical Polices CSAIL Massachusetts Institute of Technology ValveDriver command • Example – Current State: driver = on, valve = closed – Goal State: driver = off, valve = open – Why Search is Needed 1) An achieved goal can be clobbered by a subsequent goal. � Achieve Valve goal before Driver goal Model-based Reactive Planning Achieving (driver = off) and then (valve = open) clobbers (driver = off) CSAIL Massachusetts Institute of Technology Observation: Engineered systems tend not to have loops Remote Terminal Remote Terminal Bus ControlComputer Valve Valve Driver Driver � Work conjunctive goals upstream from outputs to inputs – G of compiled transition system S • vertices are state variables. • edge from vi to vj if vjvi. dcmdin Driver Valve – CSAIL Massachusetts Institute of Technology • y7� y7 Solution 13 12 9 11 8 10 7 4 6 3 5 2 1 UnaffectedAffected �• Simple check: – Number causal graph depth first – achieve goals in order of increasing depth first number. Define: Causal Graph ’s transition
View Full Document
Unlocking...