Reactive Planning in Large State Spaces Through Decomposition and Serialization Brian C. Williams Joint with Seung H. Chung 16.412J/6.834J April 26 th , 2004 Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Outline ? Model-based programming The need for model-based reactive planning The Burton model-based reactive planner Model-based Programs Interact Directly with State Embedded programs interact with plant sensors/actuators: Read sensors Set actuators Model-based programs interact with plant state: Read state Write state Embedded Program S Plant Obs Cntrl Model-based Embedded Program S Plant Programmer must map between state and sensors/actuators. Model-based executive maps between sensors, actuators to states. Orbital Insertion Example EngineA EngineB Science Camera Turn camera off and engine on EngineA EngineB Science Camera Control Sequencer Deductive Controller System Model Commands Observations Control Program Plant Titan Model-based ExecutiveRMPL Model-based Program State goalsState estimates Control Sequencer: Generates goal states conditioned on state estimates Mode Estimation: Tracks likely States Mode Reconfiguration: Tracks least-cost state goals z Executes concurrently z Preempts z Asserts and queries states z Chooses based on reward OrbitInsert():: (do-watching ((EngineA = Firing) OR (EngineB = Firing)) (parallel (EngineA = Standby) (EngineB = Standby) (Camera = Off) (do-watching (EngineA = Failed) (when-donext ( (EngineA = Standby) AND (Camera = Off) ) (EngineA = Firing))) (when-donext ( (EngineA = Failed) AND (EngineB = Standby) AND (Camera = Off) ) (EngineB = Firing)))) MAINTAIN (EAR OR EBR) EBS CO LEGEND: EAS (EngineA = Standby) EAF (EngineA = Failed) EAR (EngineA = Firing) EBS (EngineB = Standby) EBF (EngineB = Failed) EBR (EngineB = Firing) CO (Camera = Off) MAINTAIN (EAF) EAS (EAS AND CO) EAR EAS AND CO (EAF AND EBS AND CO) EBR EAF AND EBS AND CO hierarchical constraint automata on state s Control Sequencer Deductive Controller System Model Commands Observations Control Program Plant Titan Model-based ExecutiveRMPL Model-based Program State goalsState estimates Control Sequencer: Generates goal states conditioned on state estimates Mode Estimation: Tracks likely States Mode Reconfiguration: Tracks least-cost state goals z Executes concurrently z Preempts z Asserts and queries states z Chooses based on reward Closed Valve Open Stuck open Stuck closed Open Close 0. 01 0. 01 0.01 0.01 inflow = outflow = 0 Fire backup engine Valve fails stuck closed S T X 0 X 1 X N-1 X N S T X 0 X 1 X N-1 X N least cost reachable goal state First ActionCurrent Belief State Deductive Controller Commands Observations Plant State goalsState estimates Mode Estimation: Tracks likely States Mode Reconfiguration: Tracks least-cost state goals Fire backup engine Valve fails stuck closed S T X 0 X 1 X N-1 X N S T X 0 X 1 X N-1 X N least cost reachable goal state First ActionCurrent Belief State Optimal CSP: arg min f(x) s.t. C(x) is satisfiable D(x) is unsatisfiable arg max P T (m’) s.t. M(m’) ^ O(m’) is satisfiable arg min R T* (m’) s.t. M(m’) entails G(m’) s.t. M(m’) is satisfiable Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology A simple model-based executive (Livingstone) commanded NASA’s Deep Space One probe courtesy NASA JPL Started: January 1996 Launch: October 15th, 1998 Remote Agent Experiment: May, 1999 Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Remote Agent Experiment May 17-18th experiment Generate plan for course correction and thrust Diagnose camera as stuck on – Power constraints violated, abort current plan and replan Perform optical navigation Perform ion propulsion thrust May 21th experiment. Diagnose faulty device and – Repair by issuing reset. Diagnose switch sensor failure. – Determine harmless, and continue plan. Diagnose thruster stuck closed and – Repair by switching to alternate method of thrusting. Back to back planning See rax.arc.nasa.gov Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Outline Model-based programming The need for model-based reactive planning The Burton model-based reactive planner Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology DS 1 Attitude Control System z facing thrusters x facing thrusters 1553 bus Commands Data N 2 H 4 He PDE SRU PDU GDE PASM DSEU PEPE BC Flight Computer 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 . . . Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Remote Terminal Remote Terminal Driver Bus Control Computer 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 Technology MERS 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 Reactive Planner Configuration Goal Command Goal State State Estimate (Current) Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Example: Driver Valve Command Sequence Valve Driver dr Valve vlv vcmdin dcmdin Commands Driver State Valve State ME: dr = off, vlv = open MS: 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 Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology To achieve reactivity we eliminate all forms of search. Artificial Intelligence & Space Systems Laboratories 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 Artificial Intelligence & Space Systems Laboratories 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 Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology To Handle Indirect Control . . . dcmd out = vcmd in off on failed resettable dcmd in = offdcmd in = on dcmd in = reset dcmd in = off dcmd in = dcmd out closed open stuck closed stuck open vcmd in = closevcmd in = open inflow = outflow vcmdindcmdin flowin flowout Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology . . . Compile Out Constraints closed open stuck closed stuck open vcmd in = closevcmd in = open off on failed resettable dcmd in = offdcmd in = on dcmd in = reset dcmd in = off dcmd in = dcmd out inflow = outflow dcmd out = vcmd in driver = ondriver = on dcmd in = closedcmd in = open vcmdindcmdin flowin flowout Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology . . . Compile Out Constraints closed open stuck closed stuck open off on failed resettable dcmd in = offdcmd in = on dcmd in = reset dcmd in = off driver = ondriver = on dcmd in = closedcmd in = open dcmdin Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology To Compile Out Constraints Eliminate intermediate variables. ?Transitions are conditioned on mode and control variables Generate transitions as prime implicates: ) i ? next(y i = e i ) 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 Laboratories Massachusetts Institute of Technology Model-based Reactive Planning 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 Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology ValveDriver command Example – Current State: driver = on, valve = closed – Goal State: driver = off, valve = open – Achieving (driver = off) and then (valve = open) clobbers (driver = off) Why Search is Needed 1) An achieved goal can be clobbered by a subsequent goal. ? Achieve Valve goal before Driver goal Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Note: Component schematics tend not to have loops Remote Terminal Remote Terminal Bus Control Computer Valve Valve Driver Driver ? Work conjunctive goals upstream from outputs to inputs – Define: Causal Graph G of compiled transition system S vertices are state variables. edge from v i to v j if v j ’s transition is conditioned on v i . dcmd in Driver Valve – Requirement: The causal graph is acyclic. Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology The only variables used to set some variable (y 7 ) is its ancestors, ? y 7 can be changed without affecting its descendants. Solution 13 12 9 11 8 10 7 4 6 3 5 2 1 Unaffected Affected Safe to achieve goals in an upstream order. Simple check: – Number causal graph depth first – achieve goals in order of increasing depth first number. Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Latch1 Switch data Example – Latch1 and Latch2 compete for the position of Switch if achieved concurrently. Why Search is Needed 2) Two goals can compete for the same variable in their subgoals. Latch2 1 2 Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Sibling goals (7,4) may both need shared ancestors. 13 12 9 11 8 10 7 4 6 3 5 2 1 UnaffectedNot Shared Shared 13 12 9 11 8 10 7 4 6 3 5 2 1 Unaffected Not Shared But ancestors no longer needed once goal (7) is satisfied. Solution: Solve one goal before starting next sibling (Serialization). Feature: Generates first control action of plan first! Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Latch1 Switch data Example – Assume Switch can be used once, – Then Latch1 must be latched before Latch2. Why Search is Needed 3) A state transition of a subgoal variable has irreversible effect. Latch2 But irreversible effects aren’t desirable for reactive planners ? Don’t allow irreversible actions ?. . . Except to repair failure modes 1 2 Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Solution: Mark Allowed Transitions/Assignments off on failed resettable dcmd in = offdcmd in = on dcmd in = reset dcmd in = off closed open stuck closed stuck open driver = ondriver = on dcmd in = closedcmd in = open dcmd in Driver Valve Mark all control variable assignments allowed: 1 23 Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Solution: Mark Allowed Transitions/Assignments off on failed resettable dcmd in = offdcmd in = on dcmd in = reset dcmd in = off closed open stuck closed stuck open driver = ondriver = on dcmd in = closedcmd in = open dcmd in Driver Valve Mark all control variable assignments allowed: 1 23 For each mode variable v, in decreasing order of DF number: Select each transition of v, whose guard has only allowed assignments. Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Solution: Mark Allowed Transitions/Assignments off on failed resettable dcmd in = offdcmd in = on dcmd in = reset dcmd in = off closed open stuck closed stuck open driver = ondriver = on dcmd in = closedcmd in = open dcmd in Driver Valve Mark all control variable assignments allowed: 1 23 For each mode variable v, in decreasing order of DF number: Select each transition of v, whose guard has only allowed assignments. Given current assignment v = I for v: Mark assignments and transitions in SCC allowed. Find strongly connected component of selected transitions that contains I. Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Solution: Mark Allowed Transitions/Assignments off on dcmd in = offdcmd in = on closed open stuck closed stuck open driver = ondriver = on dcmd in = closedcmd in = open dcmd in Driver Valve Mark all control variable assignments allowed: 1 23 For each mode variable v, in decreasing order of DF number: Select each transition of v, whose guard has only allowed assignments. Given current assignment v = I for v: Mark assignments and transitions in SCC allowed. Find strongly connected component of selected transitions that contains I. Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Solution: Mark Allowed Transitions/Assignments off on dcmd in = offdcmd in = on closed open stuck closed stuck open driver = ondriver = on dcmd in = closedcmd in = open dcmd in Driver Valve Mark all control variable assignments allowed: 1 23 For each mode variable v, in decreasing order of DF number: Select each transition of v, whose guard has only allowed assignments. Given current assignment v = I for v: Mark assignments and transitions in SCC allowed. Find strongly connected component of selected transitions that contains I. Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Solution: Mark Allowed Transitions/Assignments off on dcmd in = offdcmd in = on closed open driver = ondriver = on dcmd in = closedcmd in = open dcmd in Driver Valve Mark all control variable assignments allowed: 1 23 For each mode variable v, in decreasing order of DF number: Select each transition of v, whose guard has only allowed assignments. Given current assignment v = I for v: Mark assignments and transitions in SCC allowed. Find strongly connected component of selected transitions that contains I. Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Model-based Reactive Planning 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 Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Solution Convert automata into hierarchical policies, one per automaton closed open cmd = closecmd = open fail Goal fail driver = on cmd = open idle idle driver = on cmd = close Current Open Closed Stuck Open Closed driver = ondriver = on – Policy selects first transition towards achieving each automata goal state, given current state. – Policy maps goals to subgoals and commands, in proper order – Ensures only reversible transitions are taken, by only using transitions marked allowed. Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Plan by passing sub-goals up causal graph ValveDriver fail Goal fail driver = on cmd = open idle idle driver = on cmd = close Current Open Closed Stuck Open Closed Goal cmd = on idle idle cmd = off Current On Off Resettable On Off Goal: Driver = off, Valve = closed cmd = reset cmd = off Current: Driver = off, Valve = open 1 2 Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Plan by passing sub-goals up causal graph ValveDriver fail Goal fail driver = on cmd = open idle idle driver = on cmd = close Current Open Closed Stuck Open Closed Goal cmd = on idle idle cmd = off Current On Off Resettable On Off Goal: Driver = off, Valve = closed cmd = reset cmd = off Current: Driver = off, Valve = open 1 2 Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Plan by passing sub-goals up causal graph ValveDriver Send: cmd = on fail Goal fail driver = on cmd = open idle idle driver = on cmd = close Current Open Closed Stuck Open Closed Goal cmd = on idle idle cmd = off Current On Off Resettable On Off Goal: Driver = off, Valve = closed cmd = reset cmd = off Current: Driver = off, Valve = open 1 2 Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology 1 2 Current: Driver = resettable, Valve = open Plan by passing sub-goals up causal graph ValveDriver fail Goal fail driver = on cmd = open idle idle Current Open Closed Stuck Open Closed Goal idle idle cmd = off Current On Off Resettable On Off Goal: Driver = off, Valve = closed cmd = reset cmd = off driver = on cmd = close Failed Resettable cmd = on Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Plan by passing sub-goals up causal graph ValveDriver fail Goal fail driver = on cmd = open idle idle Current Open Closed Stuck Open Closed Goal cmd = on idle idle cmd = off Current On Off Resettable On Off Goal: Driver = off, Valve = closed cmd = reset cmd = off driver = on cmd = close Current: Driver = resettable, Valve = open 1 2 Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Plan by passing sub-goals up causal graph ValveDriver fail Goal fail driver = on cmd = open idle idle Current Open Closed Stuck Open Closed Goal cmd = on idle idle cmd = off Current On Off Resettable On Off Goal: Driver = off, Valve = closed Send cmd = reset cmd = reset cmd = off driver = on cmd = close Current: Driver = resettable, Valve = open 1 2 Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Plan by passing sub-goals up causal graph ValveDriver fail Goal fail driver = on cmd = open idle idle driver = on cmd = close Current Open Closed Stuck Open Closed Goal cmd = on idle idle cmd = off Current On Off Resettable On Off Goal: Driver = off, Valve = closed Send cmd = close cmd = reset cmd = off Current: Driver = on, Valve = open 1 2 Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Plan by passing sub-goals up causal graph ValveDriver fail Goal fail driver = on cmd = open idle idle driver = on cmd = close Current Open Closed Stuck Open Closed cmd = reset Goal cmd = off cmd = on idle idle cmd = off Current On Off Resettable On Off Goal: Driver = off, Valve = closed Send cmd = off Current: Driver = on, Valve = closed 1 2 Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Plan by passing sub-goals up causal graph ValveDriver fail Goal fail driver = on cmd = open idle idle driver = on cmd = close Current Open Closed Stuck Open Closed cmd = reset Goal cmd = off cmd = on idle idle Current On Off Resettable On Off cmd = off Goal: Driver = off, Valve = closed Success Current: Driver = off, Valve = closed 1 2 Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Hierarchical, Model-based Reactive Planning Compile-time Analysis: – Compile-out interactions – Confirm schematics are loop free. – Depth first number variables. Periodic, Run-time Analysis: – Given initial state Identify allowed transitions and assignments – Given autonomous jump to failure state Identify allowed transitions and assignments Run-time Plan Execution: – Work conjunctive goals from outputs to inputs. – Achieve goals serially. – Only perform reversible transitions. – Lookup control actions and sub-goals in policies Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Complexity of Reactive Planning Worst Case per action: Depth * Sub-goal branch factor Average Cost per action: Sub-goal branch factor Valve 1 = open Valve 2 = open Driver 1 = off Driver 2 = off Driver 1 = on CU = on CU = on Driver 2 = on CU = on CU = on CU = on CU = on Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology What If Plan is Not Serializable? – compose each cycle into a single component. Bus Control Computer Antenna Antenna AmplifierK-band Transmitter AmplifierK-band Transmitter What if causal graph G contains cycles? Solution: – Isolate the cyclic components (compute SCCs) New causal graph G’ is acyclic, Goals of G’ are serializable Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Composing Cyclic Components off on cmd T = off Transmitter Amplifier cmd T = on A = offA = off off on cmd A = off cmd A = on T = on on T on A on T off A off T off A off T on A cmd T = offcmd T = on cmd A = off cmd A = on ? cmd A = off Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Policy for Composed Components on T on A on T off A off T off A off T on A cmd T = offcmd T = on cmd A = off cmd A = on cmd A = off ? cmd T = on Goal cmd T = on cmd A = on idle idle cmd A = off Current On T , On A On T , Off A Off T , Off A On T , On A On T , Off A idle cmd T = off cmd A = off Off T , Off A fail fail fail Off T , On A fail fail cmd A = off idleOff T , On A Problem: Composition grows exponential in space usage. Solution: Use BDD encoding (in progress). Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Model-based Reactive Planning 1. Compile away constraints from the model 2. Compile away cyclic components 3. Plan serially pursuing causal graph upstream 4. Generate actions using hierarchical policies Only performs reversible actions Responds to failure at each step Average cost per step = subgoal branching factor Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Next Challenge: Mars Smart Lander (2009) Mission Duration: 1000 days Total Traverse: 3000-69000 meters Meters/Day: 230-450 Science Mission: 7 instruments, sub-surface science package (drill, radar), in-situ sample “lab” Technology Demonstration: (2005). Images courtesy of JPL. Model-based Programming of Embedded Systems To survive decades embedded systems orchestrate complex regulatory and immune systems. Future systems will be programmed with models, describing themselves and their environments. Runtime kernels will be agile, deducing and planning by solving optimization problems with propositional constraints. Model-based reactive planners respond quickly to failure, while using compile-time analysis of structure to respond quickly and concisely to indirect effects. Appendix 1 Handling Cycles In The Causal Graph Slides by Seung Chung Massachusetts Institute of Technology MERS Model-based Embedded & Robotic Systems Group Telecommunication Subsystem Example Computer – Controls the devices and sends data to the devices. Bus Controller – Routes the commands and the data to the appropriate devices. Transmitter – Generates a signal that corresponds to the data to be transmitted. Amplifier – Amplifies the signal and transmits it to an antenna. Bus Controller Computer Antenna Antenna AmplifierTransmitter AmplifierTransmitter Massachusetts Institute of Technology MERS Model-based Embedded & Robotic Systems Group Interdependent Components Turning the transmitter on or off can generate a noise (i.e. transient signal). The transient signal may damage the amplifier. The amplified transient signal may damage other devices down stream of the amplifier. Constraint on the system: – The amplifier must be turned off before the transmitter can be turned on or off. – The transmitter must be turned on before the amplifier can be turned on. off on Transmitter Amplifier B = on A = off cmd T = off B = on A = off cmd T = on off on B = on cmd A = off B = on T = on cmd A = on Massachusetts Institute of Technology MERS Model-based Embedded & Robotic Systems Group Composing Strongly Connected CA Compose all automata into a single automaton R SCC =?R i Transmitter Amplifier off on B = on A = off cmd T = off B = on A = off cmd T = on off on B = on cmd A = off B = on T = on cmd A = on B = on cmd A = off on T on A on T off A off T off A off T on A B = on cmd T = off B = on cmd T = on B = on cmd A = off B = on cmd A = on Massachusetts Institute of Technology MERS Model-based Embedded & Robotic Systems Group Interdependent Concurrent Transitions One Transition Missing! ? on T on A on T off A off T off A off T on A B = on cmd T = off B = on cmd T = on B = on cmd A = off B = on cmd A = on B = on cmd A = off off on B = on A = off cmd T = off B = on A = off cmd T = on off on B = on cmd A = off B = on T = on cmd A = on A = off A = on B = on T = on cmd A = on T = offT = on B = on A = off cmd T = off T = off A = on T = on A = off B = on cmd T = off cmd A = on Massachusetts Institute of Technology MERS Model-based Embedded & Robotic Systems Group A = off A = on B = on T = on cmd A = on T = offT = on B = on A = off cmd T = off T = off A = on T = on A = off B = on cmd T = off cmd A = on H a z a rd ! Simultaneous Commanding Both the transmitter and the amplifier depend on one another for the transition. The transmitter must be commanded “off” and the amplifier must be commanded “on” precisely at the same time. Unless system is perfectly synchronous, simultaneous commanding cannot be guaranteed. If the amplifier were commanded on first, and then the transmitter is commanded off, the amplifier can be damaged. Massachusetts Institute of Technology MERS Model-based Embedded & Robotic Systems Group Concurrent Automata (CA) Synchronous – Assume that each automaton performs a single state transition at each time step. Interleaved execution within a time step – A single main processor executes synchronous activities by interleaving. – Devices are not synchronized. off on Transmitter Amplifier B = on A = off cmd T = off B = on A = off cmd T = on off on B = on cmd A = off B = on T = on cmd A = on off on Bus Controller cmd B = off cmd B = on Massachusetts Institute of Technology MERS Model-based Embedded & Robotic Systems Group Assuring Proper Execution of Interdependent Transitions Enforce concurrency as interleaving: – For a given transition, the interdependent state constraints become the pre- and post-conditions. – No change to all other automata that are not independent. Amplifier Transmitter A = off A = on B = on T = on T = offT = on B = on A = off cmd A = on cmd T = off T = on A = off T = on A = on B = on T = off A = off T = on A = off B = on cmd A = on cmd T = off Massachusetts Institute of Technology MERS Model-based Embedded & Robotic Systems Group Assuring Proper Execution of Interdependent Transitions Inconsistencies are automatically detected when conjoining the transition relations in OBDDs. R SCC =?R i Similar to the Graphplan mutual exclusion rule. – Interference: One transition deletes the precondition and/or effect of another. – Competing Needs: Inconsistent preconditions T = on A = off T = on A = on B = on T = off A = off T = on A = off B = on cmd A = on cmd T = off T = off A = on T = on A = off B = on cmd T = off cmd A = on Massachusetts Institute of Technology MERS Model-based Embedded & Robotic Systems Group Goal-directed Plan Goal-directed Plan ￠s,a,s’2 : ￠s, s’2:a – s : current state – s’ : goal state – a : first action/intermediate subgoals in a trajectory that eventually leads to s’ B = on cmd T = on Goal B = on cmd T = on B = on cmd A = on idle idle B = on cmd A = off Current On T , On A On T , Off A Off T , Off A On T , On A On T , Off A idle B = on cmd T = off B = on cmd A = off Off T , Off A fail fail fail Off T , On A B = on cmd A = off B = on cmd A = off B = on cmd A = off idleOff T , On A on T on A on T off A off T off A off T on A B = on cmd T = off B = on cmd T = on B = on cmd A = off B = on cmd A = on B = on cmd A = off Executing a goal-directed plan guarantees: – Progress toward the goal. – Finite number of actions to achieve the goal. – Optimal (shortest) trajectory under nominal conditions. Massachusetts Institute of Technology MERS Model-based Embedded & Robotic Systems Group n steps Computing Goal-Directed Plan: COMPUTEGDP(T) Iteratively search backward breadth-first for the goal-directed rules. – Find ￠s,a,s’2 that can reach s’ within 1 step – Find ￠s,a,s’2 that can reach s’ within 2 steps –… – Find ￠s,a,s’2 that can reach s’ within n steps 1 step 2 steps3 steps …n-1 steps Massachusetts Institute of Technology MERS Model-based Embedded & Robotic Systems Group Generating Goal-Directed Plan ￠s,a,s’2 that can reach s’ within 1 step Transition Relation B = on cmd T = on Goal B = on cmd T = on B = on cmd A = on idle idle B = on cmd A = off Current On T , On A On T , Off A Off T , Off A On T , On A On T , Off A idle B = on cmd T = off B = on cmd A = off Off T , Off A fail fail fail Off T , On A B = on cmd A = off B = on cmd A = off B = on cmd A = off idle Off T , On A on T on A on T off A off T off A off T on A B = on cmd T = off B = on cmd T = on B = on cmd A = off B = on cmd A = on B = on cmd A = off Massachusetts Institute of Technology MERS Model-based Embedded & Robotic Systems Group Generating Goal-Directed Plan ￠s,a,s’2 that can reach s’ within 2 steps – To the previous GDP add ￠s,a,s’2 that can reach s’ in 2 steps: s: current state s’: goal state that can be reached in 2 steps a: first control action that must be commanded to eventually reach s’ on T on A on T off A off T off A off T on A B = on cmd T = off B = on cmd T = on B = on cmd A = off B = on cmd A = on B = on cmd A = off B = on cmd T = on Goal Current On T , On A On T , Off A Off T , Off A On T , On A On T , Off A B = on cmd A = off Off T , Off A fail fail fail Off T , On A B = on cmd A = off B = on cmd A = off Off T , On A B = on cmd T = on B = on cmd A = on idle idle B = on cmd A = off idle B = on cmd T = off B = on cmd A = off idle Massachusetts Institute of Technology MERS Model-based Embedded & Robotic Systems Group Generating Goal-Directed Plan ￠s,a,s’2 that can reach s’ within 3 steps – To the previous GDP add ￠s,a,s’2 that can reach s’ in 3 steps: s: current state s’: goal state that can be reached in 3 steps a: first control action that must be commanded to eventually reach s’ on T on A on T off A off T off A off T on A B = on cmd T = off B = on cmd T = on B = on cmd A = off B = on cmd A = on B = on cmd A = off Goal Current On T , On A On T , Off A Off T , Off A On T , On A On T , Off A Off T , Off A fail fail fail Off T , On A B = on cmd A = off Off T , On A B = on cmd T = on B = on cmd A = on idle idle B = on cmd A = off idle B = on cmd T = off B = on cmd A = off idle B = on cmd T = on B = on cmd A = off B = on cmd A = off Massachusetts Institute of Technology MERS Model-based Embedded & Robotic Systems Group Generating Goal-Directed Plan ￠s,a,s’2 that can reach s’ within 3 steps: – What about ￠{on T ,off A },{cmd T =off},{on T ,on A }2? The goal can be achieved in 1 step using the existing goal-directed rule: ￠{on T ,off A },{cmd A =on},{on T ,on A }2. Do not overwrite the existing goal-directed rule. This guarantees the optimality of the plan. on T on A on T off A off T off A off T on A B = on cmd T = off B = on cmd T = on B = on cmd A = off B = on cmd A = on B = on cmd A = off Goal Current On T , On A On T , Off A Off T , Off A On T , On A On T , Off A Off T , Off A fail fail fail Off T , On A B = on cmd A = off Off T , On A B = on cmd T = on B = on cmd A = on idle idle B = on cmd A = off idle B = on cmd T = off B = on cmd A = off idle B = on cmd T = on B = on cmd A = off B = on cmd A = off Massachusetts Institute of Technology MERS Model-based Embedded & Robotic Systems Group Generating Goal-Directed Plan ￠s,a,s’2 that can reach s’ within 4 steps – No new ￠s,a,s’2 exists that can reach s’ in 4 steps. – When the fixed-point is reached, generating the plan is complete. on T on A on T off A off T off A off T on A B = on cmd T = off B = on cmd T = on B = on cmd A = off B = on cmd A = on B = on cmd A = off Goal Current On T , On A On T , Off A Off T , Off A On T , On A On T , Off A Off T , Off A fail fail fail Off T , On A B = on cmd A = off Off T , On A B = on cmd T = on B = on cmd A = on idle idle B = on cmd A = off idle B = on cmd T = off B = on cmd A = off idle B = on cmd T = on B = on cmd A = off B = on cmd A = off Appendix 2 Symbolic Encoding and Construction of Reactive Plans Slides by Seung Chung Massachusetts Institute of Technology MERS Model-based Embedded & Robotic Systems Group Achieve Compactness Using BDD Encoding A = on A' = on cmd A = on 1 0 B = on off on B = on cmd A = off B = on T = on cmd A = on T = on A = on A' = on cmd A = on cmd A = on A' = on 1 B = on A = on A' = on Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Ordered BDD (OBDD) Boolean Operators –{?, ?, ?, ?, ?, o} Compose BDD by recursively calling the Shannon Expansion function. ( ) ( ) 01 ii ix ix fxf xf == =? ù ú ù x 1 y 1 y 1 x 2 y 2 y 2 1 0 1 00 1 0 10 0 x 2 y 2 y 2 low high ordering: x 1 % y 1 % x 2 % y 2 (x 1 ? y 1 ) ? (x 2 ? y 2 ) Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Reduced Ordered BDD (ROBDD) x 1 y 1 y 1 x 2 y 2 y 2 1 0 1 00 1 0 10 0 x 2 y 2 y 2 y 2 y 2 1 0 10 y 2 y 2 0 1 y 2 y 2 y 2 Remove Duplicate Terminals Remove Duplicate Nonterminals Remove Redundant Tests y 2 x 1 y 1 y 1 0 1 x 2 y 2 y 2 low high ordering: x 1 % y 1 % x 2 % y 2 (x 1 ? y 1 ) ? (x 2 ? y 2 ) Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Reducing OBDD Duplicate Terminals x 1 y 1 y 1 x 2 y 2 y 2 1 0 1 00 1 0 10 0 x 2 y 2 y 2 Duplicate Nonterminals y 2 x 1 y 1 y 1 x 2 y 2 y 2 0 1 x 2 y 2 y 2 Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Reducing OBDD Cont’ Duplicate Nonterminals x 2 Duplicate Nonterminals y 2 x 1 y 1 y 1 x 2 y 2 y 2 0 1 x 2 y 2 y 2 x 1 y 1 y 1 x 2 y 2 0 1 x 2 y 2 x 1 y 1 y 1 y 2 0 1 x 2 y 2 Reduced OBDD (OBDD) Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Variable Ordering in ROBDD ordering: x 1 % x 2 % y 1 % y 2 x 1 x 2 x 2 y 1 y 2 y 1 0 1 y 1 y 1 y 2 ordering: x 1 % y 1 % x 2 % y 2 (x 1 ? y 1 ) ? (x 2 ? y 2 ) low high x 1 y 1 y 1 y 2 0 1 x 2 y 2 Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology APPLY Operation ? APPLY Operation computes two Boolean functions operated by a binary operator. Compute APPLY operation with Shannon Expansion: Example of Boolean binary operators are {?,?,?,?} Time complexity is reduced from to by using hash tables. ()() 12 1020 1121 ii ii ix x ix x fopf x f opf x f opf == == éùéù =? ù ú ù êúêú ???? () 12 On n× () 12 2 nn O × 12 f op f Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology APPLY Operation Example ()() [] () 11 11 11 12 1 1020 1 1121 111121 1 xx xx xx ff x f f x f f xxff == == == éùéù ? ú = ? ù? ú ú ù? ú êúêú ???? éù =? ù ú ù? ú êú ?? ()() [][] 12 12 123 123 123 123 2 1,1 2 1,1 3 2 1,1,0 2 1,1,0 2 2 1,1,1 2 1,1,1 32 11 xx xx xxx xxx xxx xxx ff xf f xf f xx == == === === === === éùéù ? ú = ? ù? ú ú ù? ú êúêú ???? =? ù ú ù () ()() 1 1 12 12 12 12 12 12 12 11 21 2 11,0 21,0 2 11,1 11,1 2 1 1,0 2 1 1,1 1 1,1 0 x x xx xx xx xx xx xx xx ff xf f xf f xf xf f = = == == == == == == == éù ? ú = ? ù? ú ú ù? ú êú ?? éùé ù = ? ù? ú ú ù? ú êúê ú ??? ? x 1 0 1 x 3 f 1 = x 1 ? x 3 x 2 0 1 x 3 f 2 = x 2 ? x 3 ?f 1 ? f 2 x 1 10 x 2 x 3 ()() [][] 12 12 3 12 3 2 1,0 3 2 1,0,0 3 2 1,0,1 33 000 10 xx xxx xxx fxf xf xx == === === ù ? ú = ? ù? ú ú ù? ú ú ? =? ù ú ù Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology RESTRICT Operation RESTRICT Operation restricts a variable in Boolean function to a value. – RESTRICT by finding all vertices that point the vertex – Redirect them to the vertex Time complexity is i x a f = i x i xa= () On f| x2=0x 1 10 x 2 x 3 2 0x f = x 1 10 x 3 Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology COMPOSE Operation COMPOSE Operation restricts a variable to a Boolean function. – COMPOSE Operation uses the Shannon Expansion in which both APPLY and RESTRICT operations. Time complexity is 2 1 i x f f = ()() 2 1210211 iii xf x x fffff === =? ù ú ù () 2 12 On n× Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology ROBDD Summary Advantages – Efficient representation of Boolean function – Low complexity for the operations on OBDD’s with the use of Dynamic Programming Reduce Reducing G to canonical form O(|G|) Apply f 1 <op> f 2 O(|G 1 |?|G 2 |) Restrict f| x i =b O(|G|) Compose f 1 | x i =f 2 O(|G 1 | 2 ?|G 2 |) Satisfy-one Find a satisfying truth assignment O(|n|) Disadvantage – Efficiency of Boolean function representation is highly dependent on the ordering of the variables – Efficient ordering of BDD is NP-complete problem, HOWEVER good heuristics is to order dependent variables near each other. Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Driver 1 Transition System ￠3,6,72 3 - set of variables 3 s : dr 1 3 c : cmdin 1 3 d : cmdout 1 6 - set of assignments dr 1 : {on,off,resettable,failed} cmdin 1 : {on,off,reset,open,close,none} cmdout 1 : {open,close,none} 7 - transition relations dr 1 =on ? cmdin 1 =off o dr 1 =off dr 1 =resettable ? cmdin 1 =reset o dr 1 =on dr 1 =off ? cmdin 1 =on o dr 1 =on dr 1 =on dr 1 =off cmdin 1 =on cmdin 1 =off cmdin 1 =reset dr 1 =failed dr 1 =resettable Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology BDD Encoding of Constraints Encoding constraints in the form of the Propositional Formula is straight forward since all propositional formulas are boolean functions. a 0 1 a 0 1 b ?a a ? b a ? b a 0 1 b Use Apply Operator to construct the BDD of the constraint – f 1 <op> f 2 – <op> ? {?,?} Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology BDD Encoding of Transitions 7 - transition relations (a) dr 1 =on ? cmdin 1 =off o dr 1 =off (b) dr 1 =resettable ? cmdin 1 =reset o dr 1 =on (c) dr 1 =off ? cmdin 1 =on o dr 1 =on dr 1 =resettable dr 1 =on’ cmdin 1 =reset 0 1 dr 1 =off cmdin 1 =on dr 1 =on’ 0 1 dr 1 =on cmdin 1 =off dr 1 =off’ 0 1 (a) (b) (c) Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Strong Plan Universal Non-Deterministic Domain Optimal – Backward breadth first search BDD-based – Encode automata and transitions as OBDD – Encode the universal plan as OBDD Goal State Initial State Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Strong Plan with BDD Use BDD Encoding in Strong Plan – Constraints – Transition Relations <state, action, state’> – <state, action> Tables (I.e. plan or policy) Use BDD Operations in Strong Plan – Strong Plan uses many set operators: z, ?, ?, ?, ?, ?, ? – Basic set operations as well as logical operations are straight forward for BDD. – With these basic operations on BDD’s and their closure properties more complex operations on BDD’s can be derived. Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology BDD Encoding of Plans <s,a> Goal : dr 1 =on <dr 1 =on,?> <dr 1 =off,cmdin 1 =on> <dr 1 =resettable,cmdin 1 =reset> Goal : dr 1 =off <dr 1 =on,cmdin 1 =off> <dr 1 =off,? > <dr 1 =resettable,cmdin 1 =reset> <dr 1 =resettable,cmdin 1 =reset>kk dr 1 =resettable cmdin 1 =reset dr 1 =on dr 1 =off cmdin 1 =on 0 1 cmdin 1 =off dr 1 =resettable cmdin 1 =reset dr 1 =off dr 1 =on 0 1 Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology BDD Operations in Strong Plan PreImage := {￠s,W2|s?6,W?7,?zW(s)?ACC}; PrunedPreImage := {￠s,W2|￠s,W2?PreImage,s?ACC} SA := SA ? PrunedPreImage; OldAcc := Acc; Acc := Acc ? {s|￠s,W2?PrunedPreImage}; Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Strong Cyclic Plan Algorithm PROCEDURE StrongCyclicPlan(Init, Goal) OldAcc := ?; Acc := Goal; SA := ?; While (Acc z OldAcc) If Init ? Acc then return SA; PreImage := {￠s,W2|s?6,W?7,?zW(s)?ACC}; PrunedPreImage := {￠s,W2|￠s,W2?PreImage,s?ACC} If PrunedPreImage z ? then SA := SA ? PrunedPreImage; OldAcc := Acc; Acc := Acc ? {s|￠s,W2?PrunedPreImage}; else StrongCycles(OldAcc,Acc,SA); return Fail; Artificial Intelligence & Space Systems Laboratories Massachusetts Institute of Technology Strong Cycles Algorithm PROCEDURE StrongCycles(OldAcc,Acc,SA) OldWpiAcc := T; WpiAcc := ?; CSA := ?; While (CSA = ? and WpiAcc z OldWpiAcc) S := {s|￠s,W2?WpiACC} ? ACC; WeakPreImage := {￠s,W2|s?6,W?7,W(s)?Sz?}; CSA := Outgoing := {￠s,W2|￠s,W2?WeakPreImage,s?ACC}; While (CSA z ? and Outgoing z ?) S := {s|￠s,W2?CSA} ? ACC; Outgoing := {￠s,W2|￠s,W2?CSA,s?S}; CSA := CSA \ Outgoing; If (CSA z ?) then SA := SA ? CSA; OldAcc := Acc; Acc := Acc ? {s|￠s,W2?CSA}; else OldWpiAcc := WpiAcc; WpiAcc := WpiAcc ? WeakPreImage;