Model-based Programming of Cooperating Explorers Brian C. Williams CSAIL Dept. Aeronautics and Astronautics Massachusetts Institute of Technology With Complex Autonomic Processes Programming Long-lived Embedded Systems Large collections of devices must work in concert to achieve goals ? Devices indirectly observed and controlled ? Need quick, robust response to anomalies throughout life ? Must manage large levels of redundancy Coordination Recapitulated At The Level of Cooperating Explorers (Courtesy of Jonathan How. Used with permission.) Coordination Issues Increase For Dexterous Explorers (Courtesy of Frank Kirchner. Used with permission.) Outline ? Model-based Programming ? Autonomous Engineering Operations – An Example – Model based Execution – Fast Reasoning using Conflicts ? Cooperating Mobile Vehicles – Predictive Strategy Selection – Planning Out The Strategy Approach Elevate programming and operation to system-level coaching. ? Model-based Programming – State Aware: Coordinates behavior at the level of intended state. ? Model-based Execution – Fault Aware: Uses models to achieve intended behavior under normal and faulty conditions. Why Model-based Programming? Polar Lander Leading Diagnosis: ? Legs deployed during descent. ? Noise spike on leg sensors latched by software monitors. ? Laser altimeter registers 40m. ? Begins polling leg monitors to determine touch down. ? Read latched noise spike as touchdown. ? Engine shutdown at ~40m. Programmers often make commonsense mistakes when reasoning about hidden state. Objective: Support programmers with embedded languages that avoid these mistakes, by reasoning about hidden state automatically. Reactive Model-based Programming Language (RMPL) Interact Directly with State Model-based Programs Embedded programs interact with Model-based programs plant sensors and actuators: interact with plant state: ? Read sensors ? Read state ? Set actuators ?Write state Embedded Program S Plant Obs Cntrl Model-based Embedded Program S Plant S’ Model-based Executive Obs Cntrl Programmer must map between Model-based executive maps state and sensors/actuators. between state and sensors/actuators. Control Sequencer Deductive Controller Mode Estimation Mode Reconfiguration RMPL Model-based Program Titan Model-based Executive System Model CommandsObservations Control Program Plant State goalsState estimates Generates target goal states conditioned on state estimates Tracks likely plant states Tracks least cost goal states z Executes concurrently z Preempts z Queries (hidden) states z Asserts (hidden) state Closed Valve Open Stuck open Stuck closed Open Close 0. 01 0. 01 0.01 0.01 inflow = outflow = 0 Outline ? Model-based Programming ? Autonomous Engineering Operations – An Example – Model based Execution – Fast Reasoning using Conflicts ? Cooperating Mobile Vehicles – Predictive Strategy Selection – Planning Out The Strategy Mission-critical sequences: Motivation images courtesy of NASA ? Launch & deployment ? Planetary fly-by ? Orbital insertion ? Entry, descent & landing (Courtesy of Mitch Ingham. Used with permission.) Mars Entry Example engine to standby planetary approach switch to inertial nav rotate to entry-orient & hold attitude separate lander (Courtesy of Mitch Ingham. Used with permission.) Mars Entry Example engine to standby planetary approach switch to Descent engine to “standby”: off heating 30-60 sec standby separate lander inertial nav rotate to entry-orient & hold attitude (Courtesy of Mitch Ingham. Used with permission.) Mars Entry Example engine to standby Spacecraft approach: ? ? observable ? of cruise trajectory planetary approach separate lander switch to inertial nav rotate to entry-orient & hold attitude 270 mins delay relative position wrt Mars not based on ground computations (Courtesy of Mitch Ingham. Used with permission.) Mars Entry Example engine to standby planetary approach switch to separate lander inertial nav rotate to entry-orient & hold attitude Switch navigation mode: “Earth-relative” = Star Tracker + IMU Switch navigation mode: “Inertial” = IMU only (Courtesy of Mitch Ingham. Used with permission.) Mars Entry Example engine to standby Rotate spacecraft: ? planetary approach separate lander switch to inertial nav rotate to entry-orient & hold attitude command ACS to entry orientation (Courtesy of Mitch Ingham. Used with permission.) Mars Entry Example engine to standby Rotate spacecraft: ? once entry orientation achieved, ACS holds attitude planetary approach separate lander switch to inertial nav rotate to entry-orient & hold attitude (Courtesy of Mitch Ingham. Used with permission.) Mars Entry Example engine to standby planetary approach switch to separate lander inertial nav rotate to entry-orient & hold attitude cruise stage lander stage pyro latches Separate lander from cruise stage: (Courtesy of Mitch Ingham. Used with permission.) Mars Entry Example engine to standby planetary approach separate lander switch to inertial nav rotate to entry-orient & hold attitude ? cruise stage lander stage pyro latches Separate lander from cruise stage: when entry orientation achieved, fire primary pyro latch (Courtesy of Mitch Ingham. Used with permission.) Mars Entry Example engine to standby planetary approach separate lander switch to inertial nav rotate to entry-orient & hold attitude ? cruise stage lander stage Separate lander from cruise stage: when entry orientation achieved, fire primary pyro latch (Courtesy of Mitch Ingham. Used with permission.) Mars Entry Example engine to standby planetary approach separate lander switch to inertial nav rotate to entry-orient & hold attitude ? cruise stage lander stage Separate lander from cruise stage: in case of failure of primary latch, fire backup pyro latch (Courtesy of Mitch Ingham. Used with permission.) Mars Entry Example engine to standby planetary approach separate lander switch to inertial nav rotate to entry-orient & hold attitude ? cruise stage lander stage Separate lander from cruise stage: in case of failure of primary latch, fire backup pyro latch (Courtesy of Mitch Ingham. Used with permission.) What is Required to Program at This Level? engine to standby planetary approach switch to inertial nav rotate to entry-orient & hold attitude separate lander ? simple state-based control specifications ? systems engineers ? handle timed plant & control behavior ? automated reasoning through low- level plant interactions ? fault-aware (in-the-loop recoveries) models are writable/inspectable by (Courtesy of Mitch Ingham. Used with permission.) Descent Example Turn camera off and engine on EngineA EngineB EngineA EngineB Science Camera Science Camera Model-based Program Control program specifies state trajectories: ? fires one of two engines ? sets both engines to ‘standby’ ? prior to firing engine, camera must be turned off to avoid plume contamination ? in case of primary engine failure, fire backup engine instead Plant Model describes behavior of each component: – Nominal and Off nominal – qualitative constraints – likelihoods and costs OrbitInsert():: (do-watching ((EngineA = Thrusting) OR (EngineB = Thrusting)) (parallel (EngineA = Standby) (EngineB = Standby) (Camera = Off) (do-watching (EngineA = Failed) (when-donext ( (EngineA = Standby) AND (Camera = Off) ) (EngineA = Thrusting))) (when-donext ( (EngineA = Failed) AND (EngineB = Standby) AND (Camera = Off) ) (EngineB = Thrusting)))) Plant Model component modes… described by finite domain constraints on variables… deterministic and probabilistic transitions cost/reward Standby Engine Model Off Failed Firing (thrust = full) AND (power_in = nominal) (thrust = zero) AND (power_in = zero) (thrust = zero) AND (power_in = nominal) off - cmd standby - cmd 0.01 0.01 standby - cmd fire - cmd 0 v 0 v 2 kv 2 kv On Camera Model Off turnoff - cmd turnon - cmd (power_in = zero) AND (shutter = closed) (power_in = nominal) AND (shutter = open) 0 v 20 v 0.01 0.01 0 v one per component … operating concurrently Example: The model-based program sets engine = thrusting, and the deductive controller . . . . Mode Estimation Mode Reconfiguration Oxidizer tank Fuel tank Selects valve Deduces that configuration; thrust is off, and plans actions Deduces that a valve the engine is healthy to open failed - stuck closed six valves Determines valves on backup engine that will achieve thrust, and plans needed actions. Mode Reconfiguration Mode Estimation Outline ? Model-based Programming ? Autonomous Engineering Operations – An Example – Model based Execution – Fast Reasoning using Conflicts ? Cooperating Mobile Vehicles – Predictive Strategy Selection – Planning Out The Strategy Modeling Plant Dynamics using Probabilistic Concurrent, Constraint Automata (PCCA) Compact Encoding: – Concurrent probabilistic transitions – State constraints between variables Standby Engine Model Off Failed off - cmd standby - cmd 0.01 (thrust = full) AND (power_in = nominal) Firing 0.01 standby - cmd fire - cmd (thrust = zero) AND (power_in = zero) (thrust = zero) AND (power_in = nominal) On Camera Model Off turnoff - cmd turnon - cmd (power_in = zero) AND (shutter = closed) (power_in = nominal) AND (shutter = open) 0 v 2 kv 2 kv 0 v 0 v 20 v 0.01 0.01 0 v Typical Example (DS1 spacecraft): – 80 Automata, 5 modes on average – 3000 propositional variables, 12,000 propositional clauses Possible Behaviors Visualized by a Trellis Diagram S T X 0 X 1 X N-1 X N ?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 transitions The Plant’s Behavior Control Sequencer Deductive Controller Commands Tracks least-cost state goals RMPL Model-based Program Titan Model-based Executive System Model Observations Control Program Plant State goalsState estimates Control Sequencer: Generates goal states Mode Estimation: Tracks likely States Mode Reconfiguration: z z Preempts z z OrbitInsert():: ( i iring)) (parallel ) ) ( ( (Camera = Off) ) iring))) ( ) AND (Camera = Off) ) iring)))) CO EAS ) EAF ( ) EAR i i ) EBS ) EBF ( ) EBR i i ) ( ) EAR ( ) hierarchical constraint automata on state s conditioned on state estimates Executes concurrently Asserts and queries states Chooses based on reward do-watching ((EngineA = F ring) OR (EngineB = F (EngineA = Standby (EngineB = Standby (Camera = Off) do-watching (EngineA = Failed) when-donext ( (EngineA = Standby) AND (EngineA = F when-donext ( (EngineA = Failed) AND (EngineB = Standby (EngineB = F MAINTAIN (EAR OR EBR) EBS LEGEND: (EngineA = Standby EngineA = Failed (Eng neA = F ring (EngineB = Standby EngineB = Failed (Eng neB = F ring CO Camera = Off) MAINTAIN (EAF EAS (EAS AND CO) EAS AND CO EAF AND EBS AND CO EBR EAF AND EBS AND CO Control Sequencer Deductive Controller RMPL Model-based Program Titan Model-based Executive System Model Observations Control Program Plant State goalsState estimates Control Sequencer: Generates goal states Mode Estimation: Tracks likely States Mode Reconfiguration: Tracks least-cost state goals z z Preempts z z engine stuck closed S T X 0 X 1 X X N S T X 0 X 1 X X N least cost reachable goal state First ActionCurrent Belief State Commands conditioned on state estimates Executes concurrently Asserts and queries states Chooses based on reward Fire backup Valve fails N-1 N-1 Deductive Controller Observations Plant State goalsState estimates Mode Estimation: Tracks likely States Mode Reconfiguration: Tracks least-cost state goals engine stuck closed S T X 0 X 1 X X N S T X 0 X 1 X X N least cost reachable goal state First ActionCurrent Belief State s.t. C(x) is satisfiable D(x) is unsatisfiable T (m’) s.t. M(m’) ^ O(m’) is satisfiable T* s.t. M(m’) entails G(m’) s.t. M(m’) is satisfiable Commands Fire backup Valve fails N-1 N-1 OpSat: arg min f(x) arg max P arg min R (m’) Outline ? Model-based Programming ? Autonomous Engineering Operations – An Example – Model based Execution – Fast Reasoning using Conflicts ? Cooperating Mobile Vehicles – Predictive Strategy Selection – Planning Out The Strategy Diagnosis Formulation Consistency-based Diagnosis: Given symptoms, find diagnoses that are consistent with symptoms. Handle Novel Failures by Suspending Constraints: Make no presumptions about faulty component behavior. 1 1 1 Symptom Or1 Or2 Or3 And1 And2 A B C D E 1 1 1 1 0 F G X Y Z 0 1 Diagnosis Formulation Consistency-based Diagnosis: Given symptoms, find diagnoses that are consistent with symptoms. Handle Novel Failures by Suspending Constraints: Make no presumptions about faulty component behavior. 1 1 1 Symptom Or2 Or3 And1 And2 A B C D E 1 1 1 1 0 F G X Y Z 0 1 Fast Reasoning Through Conflict When you have eliminated the impossible, whatever remains, however improbable, must be the truth. - Sherlock Holmes. The Sign of the Four. 1. Test Hypothesis 2. If inconsistent, learn reason for inconsistency (a Conflict). 3. Use conflicts to leap over similarly infeasible options to next best hypothesis. Compare Most Likely Hypothesis to Observations Helium tank Fuel tankOxidizer tank Main Engines Pressure 1 = nominal Pressure 2 = nominal Acceleration = zero Flow 1 = zero It is most likely that all components are okay. Isolate Conflicting Information Helium tank Fuel tankOxidizer tank Main Engines Flow 1 = zero The red component modes conflict with the model and observations. Leap to the Next Most Likely Hypothesis that Resolves the Conflict Helium tank Fuel tankOxidizer tank Main Engines Flow 1 = zero The next hypothesis must remove the conflict New Hypothesis Exposes Additional Conflicts Pressure 1 = nominal Pressure 2 = nominal Acceleration = zero Helium tank Fuel tankOxidizer tank Main Engines Another conflict, try removing both Final Hypothesis Resolves all Conflicts Helium tank Fuel tankOxidizer tank Main Engines Pressure 1 = nominal Flow 1 = zero Pressure 2 = nominal Flow 2 = positive Acceleration = zero Implementation: Conflict-directed A* search. A* Increasing Cost Feasible Infeasible Conflict-directed A* Increasing Cost Feasible Infeasible Conflict-directed A* Increasing Cost Feasible Infeasible Conflict 1 Conflict-directed A* Increasing Cost Feasible Infeasible Conflict 3 Conflict 2 Conflict 1 feasible regions as implicants (Kernel Assignments) ?Want kernel assignment ? Conflicts are mapped to containing the best cost state. Outline ? Model-based Programming ? Autonomous Engineering Operations – An Example – Model based Execution – Fast Reasoning using Conflicts ? Cooperating Mobile Vehicles – Predictive Strategy Selection – Planning Out The Strategy Coordination is Recapitulated at the Level of Cooperating Explorers (Courtesy of Jonathan How. Used with permission.) ? Explicit human guidance is at the lowest levels Traditional Robot Architectures Planning and Scheduling Goal-directed Execution Goal-directed Programs Goals Action descriptions Reactive Behaviors RMPL for Robotics Reactive Model-based Model-based Programming Executive Goal-directed Execution Control Programs Plant Models Deductive Controllers Language (RMPL) What types of reasoning should the programmer/operator guide? ? State/mode inference ? Method selection ? Machine control ? Roadmap path planning ? Scheduling ? Optimal trajectory planning ? Generative temporal planning RMPL Model-based Program Kirk Model-based Executive Control Sequencer Predictive Strategy Selection Dynamic Scheduling Ensures Safe Execution Deductive Controller Achieves State via Path Planning Estimates using Localization Environment Model Control Program location goalslocation estimates z Executes concurrently z Preempts z non-deterministic choice z A[l,u] timing z A at l location HOME T W O Enroute COLLECTION POINT RENDEZVOUS Diverge SCIENCE AREA 1’ SCIENCE AREA 3 Landing Site: ABC Landing Site: XYZ O N E SCIENCE AREA 1 Observations Commands Plant Properties: Example Scenario HOME TWO Enroute COLLECTION POINT RENDEZVOUS Diverge SCIENCE AREA 1’ SCIENCE AREA 3 Landing Site: ABC Landing Site: XYZ ONE SCIENCE AREA 1 z Mars rover operators have been leery of generative planners. z Are more comfortable with specifying contingencies. z Want strong guarantees of safety and robust to uncertainty. z Global path planning is on the edge Extend RMPL with planner-like capabilities ..except planning Reactive Model-based Programming Idea: To describe group behaviors, start with concurrent language: z p z If c next A z Unless c next A z A, B z Always A z Add temporal constraints: z A [l,u] ? Primitive activities ? Conditional execution ? Preemption ? Full concurrency ? Iteration ? Timing z Add choice (non-deterministic or decision-theoretic): z Choose {A, B} ? Contingency z Parameterize by location: z A at [l] Example Enroute Activity: Enroute Rendezvous Rescue Area Corridor 2 Corridor 1 RMPL for Group-Enroute Group-Enroute()[l,u] = { Temporal Constraints: choose { do { Group-Fly- Path(PATH1_1,PATH1_2,PATH1_3,RE_POS)[l*90%,u*90%]; } maintaining PATH1_OK, do { Group-Fly- Path(PATH2_1,PATH2_2,PATH2_3,RE_POS)[l*90%,u*90%]; } maintaining PATH2_OK }; { Group-Transmit(OPS,ARRIVED)[0,2], do { Group-Wait(HOLD1,HOLD2)[0,u*10%] } watching PROCEED } at RE_POS } RMPL for Group-Enroute Location Constraints: Group-Enroute()[l,u] = { choose { do { Group-Fly- Path(PATH1_1,PATH1_2,PATH1_3,RE_POS)[l*90%,u*90%]; } maintaining PATH1_OK, do { Group-Fly- Path(PATH2_1,PATH2_2,PATH2_3,RE_POS)[l*90%,u*90%]; } maintaining PATH2_OK }; { Group-Transmit(OPS,ARRIVED)[0,2], do { Group-Wait(HOLD1,HOLD2)[0,u*10%] } watching PROCEED } at RE_POS } RMPL for Group-Enroute Non-deterministic Group-Enroute()[l,u] = { choose { choice: do { Group-Traverse- Path(PATH1_1,PATH1_2,PATH1_3,RE_POS)[l*90%,u*90%]; } maintaining PATH1_OK, do { Group-Traverse- Path(PATH2_1,PATH2_2,PATH2_3,RE_POS)[l*90%,u*90%]; } maintaining PATH2_OK }; { Group-Transmit(OPS,ARRIVED)[0,2], do { Group-Wait(HOLD1,HOLD2)[0,u*10%] } watching PROCEED } at RE_POS } Outline ? Model-based Programming ? Autonomous Engineering Operations – An Example – Model based Execution – Fast Reasoning using Conflicts ? Cooperating Mobile Vehicles – Predictive Strategy Selection – Planning Out The Strategy Control Sequencer Deductive Controller Mode Estimation Mode Reconfiguration RMPL Model-based Program Titan Model-based Executive Environment Model CommandsObservations Control Program location goalslocation estimates Selects consistent threads of activity from redundant methods Tracks location Finds least cost paths z Executes concurrently z Preempts z non-deterministic choice z A[l,u] timing z A at l location HOME T W O Enroute COLLECTION POINT RENDEZVOUS Diverge SCIENCE AREA 1’ SCIENCE AREA 3 Landing Site: ABC Landing Site: XYZ O N E SCIENCE AREA 1 Executive ? pre-plans activities ? pre-plans paths ? dynamically schedules [Tsmardinos et al.] Plant Enroute Activity Encoded as a Temporal Plan Network ? Start with flexible plan representation Enroute [450,540] 1 2 [0, 0] Group Traverse Group Wait [0, 0] 4 [405, 486] 5 [0, 0] [0, 0] [0, 54] [0, 0] Science Target 8 [0, 0] [0, ] Group Transmit [0, 2] Activity (or sub-activity) Duration (temporal constraint) Enroute Activity Encoded as a Temporal Plan Network ? Add conditional nodes Enroute [450,540] 1 2 [0, 0] Group Traverse Group Wait [0, 0] [0, 0] 4 [405, 486] 5 [0, 0] [0, 0] [0, 54] [0, 0] Science Target 3 8 [0, ][0, 0] Group Traverse [0, 0] [0, 0] Group Transmit [405, 486] [0, 2] Activity (or sub-activity) Duration (temporal constraint) Conditional node Enroute Activity Encoded as a Temporal Plan Network ?Add temporally extended, symbolic constraints Enroute [450,540] 1 2 [0, 0] Group Traverse Group Wait [0, 0] [0, 0] 4 [405, 486] 5 [0, 0] [0, 0] 9 [0, 54] 10 [0, 0] Ask( PATH1 = OK) Science Target Ask( EXPLORE = OK) 3 8 13 [0, ][0, 0] Group Traverse [0, 0] [0, 0] Group Transmit 6 [405, 486] 7 11 [0, 2] 12 Ask( PATH2 = OK) Activity (or sub-activity) Duration (temporal constraint) Conditional node Symbolic constraint (Ask,Tell) Instantiated Enroute Activity ?Add environmental constraints Group-Enroute [500,800] s e [0,∞] [0,∞] [450,540] 1 Group Traverse Group Wait 2 Ask(PROCEED) 4 9 10 5 Ask(PATH1=OK) [405,486] [0,54] Science Target 3 8 1 Group Traverse Group Transmit 3 Ask(PATH2=OK) [0,∞] 6 7 11 12 [405,486] [0,2] [10,10] Tell(PATH1=OK) Tell(PROCEED) [0,∞] 14 15 16 17 [450,450] [200,200] Activity (or sub-activity) Duration (temporal constraint) Conditional node Symbolic constraint (Ask,Tell) External constraints Generates Schedulable Plan Group-Enroute [500,800] s e [0,∞] [0,∞] [450,540] 1 Group Traverse Group Wait 2 Ask(PROCEED) 4 9 105 Ask(PATH1=OK) [405,486] [0,54] Science Target 133 Group Traverse 8 Group Transmit Ask(PATH2=OK) [0,∞] 6 7 11 12 [405,486] [0,2] [10,10] Tell(PATH1=OK) Tell(PROCEED) [0,∞] 14 15 16 17 [450,450] [200,200] To Plan, . . . perform the following hierarchically: ? Trace trajectories ? Check schedulability ? Supporting and protecting goals (Asks) Supporting and Protecting Goals Unsupported Subgoal Threatened Activities 1 2 3 43 4 Goal: any UCAV at Target 1 2 Activity: UAV1 at Base Activity: UAV1 at Target Activity: UCAV1 at Target Close open goals Activities can’t co-occur Resolving Unsupported Subgoals: ? Scan plan graph,identifying activities that support open sub-goals; force to co-occur. Resolving Threatened Subgoals: ? Search for inconsistent activities that co-occur, and impose ordering. Key computation is bound time of occurrence: ? Used Floyd-Warshall APSP algorithm O(V 3 ). Randomized Experiments for Assessing Scaling and Robustness Randomized Experiments: ? Randomly generated range of scenarios with 1-50 vehicles. ? Each vehicle has two scenario options, each with five actions and 2 waypoints: 1. Go to waypoint 1 2. Observe science 3. Go to waypoint 2 4. Observe science 5. Return to collection point ? Waypoints generated randomly from environment with uniform distribution. Strategy Selection: ? TPN planner chooses one option per vehicle. ? Combined choices must be consistent with timing constraints and vehicle paths. Kirk Strategy Selection: Scaling and Robustness Each vehicle visits 2 science sites and returns to collection point Kirk Oct. ’02 Kirk April ’03 Performance Improvement Through ? Incremental temporal consistency ? Conflict-directed Search (in progress) Control Sequencer Deductive Controller Mode Estimation Mode Reconfiguration RMPL Model-based Program Titan Model-based Executive Environment Model CommandsObservations Control Program location goalslocation estimates Selects consistent threads of activity from redundant methods Tracks location Finds least cost paths z Executes concurrently z Preempts z non-deterministic choice z A[l,u] timing z A at l location HOME T W O Enroute COLLECTION POINT RENDEZVOUS Diverge SCIENCE AREA 1’ SCIENCE AREA 3 Landing Site: ABC Landing Site: XYZ O N E SCIENCE AREA 1 Executive ? pre-plans activities ? pre-plans paths ? dynamically schedules [Tsmardinos et al.] Plant Achieving Program States Combines Logical Decisions and Trajectory Planning Vehicle Obstacle Waypoint Explorers Will Need to Be Dexterous (Courtesy of Frank Kirchner. Used with permission.) Outline ? Model-based Programming ? Autonomous Engineering Operations – An Example – Model based Execution – Fast Reasoning using Conflicts ? Cooperating Mobile Vehicles – Predictive Strategy Selection – Planning Out The Strategy OEP Example: Coaching Heterogeneous Teams ?Search and Rescue ?Ocean Exploration A dozen vehicles is too many to micro manage → Act as a coach: ? Specify evolution of state and location. (Courtesy of Jonathan How. Used with permission.) Forest Fire Rescue ? Goal: retrieve family from fire. ? Rescue cannot take place until the local fire is suppressed. ? Retrofit one rescue vehicle for fire suppression Ambulance Rescue Point Fire Fire Line Forest Kirk Model-based Execution System Overview Strategy Selection TPN Planner Activity Planning Generative Activity Planner Visibility Graph Mission Developer RMPL Strategy macro control decomposition program Mission Controller ? Strategy Selection ? Activity Planning figures out within strategic framework using determines the optimal rules / strategies to accomplish mission goals. how to achieve mission goals available low-level actions. Strategy Macro Library Operators, Scenario Model Tactics, state configuration goals environment and action data schedulable plan with rationale Human / Computer Interface MILP Path-Planning RMPL Control Program ? (defclass rescue-team (execute () (sequence (parallel [l1,u1] (tell-start(at family RescuePoint)) (tell-start(at uav1 Ambulance)) (tell-start(at uav2 Ambulance)) Initial State ) (parallel [l2,u2] (ask-end(suppressed Fire)) Phase 1 Intermediate State (ask-end(rescued family)) (ask-end(at uav1 Ambulance)) ) ) ) ) (ask-end(at uav2 Ambulance)) Phase 2 Goal State Environment Model ? Terrain Map ? Object instantiations: – UAV uav1 – UAV uav2 – RESCU-READY uav1 – RESCUE-READY uav2 – IN-DISTRESS family – LOCATION Ambulance – LOCATION Fire – LOCATION RescuePoint Vehicle Specifications ? Vehicle linearized dynamics ? Vehicle primitive operators: – Fly(V,A,B) ? move UAV “V” from location “A” to location “B” – Refit(V) ? Prepare UAV “V” to drop fire retardant – Drop(V,A) ? Drop fire retardant at location “A” with UAV “V” – Rescue(V,P,A) ? Rescue people “P” in distress with UAV “V” at location “A” Kirk Model-based Execution System Overview Strategy Selection TPN Planner Activity Planning Generative Activity Planner Visibility Graph Mission Developer RMPL Strategy macro control decomposition program Mission Controller ? Strategy Selection ? Activity Planning figures out within strategic framework using determines the optimal rules / strategies to accomplish mission goals. how to achieve mission goals available low-level actions. Strategy Macro Library Operators, Scenario Model Tactics, state configuration goals environment and action data schedulable plan with rationale Human / Computer Interface MILP Path-Planning Kirk Constructs Vehicle Activity Plan Using a Generative Temporal Planner Approach: ? Encode Goal Plan using an LPGP-style encoding ? Prototype using LPGP [Fox/Long, CP03] Mission Goal State Plan Generative Temporal Planner Use Atomic Generative Planner To Generate Operators and Precedence Extract Temporal Plan and Check Schedulability Translate to Planning Problem with Atomic Operators Vehicle Operator Definitions (GraphPlan – Blum & Furst) Vehicle Activity Plan Generated Activity Plan Refit-Inv Fly-Inv Fly-Inv Refit-End Refit-Start Fly-Start [10,+INF] [20,+INF] [20,+INF] [10,20] Fly-Start [20,+INF] Fly-Inv Suppress-Start Suppress-Inv Fly-End Fire [20,+INF] [10,20] Suppress-End CP-Inv-1 CP-Inv-1 CP-Inv-1 CP-Inv-1 CP-Inv-1 CP-Inv-1 CP-Inv-1 CP-Start CP-Midpoint [0,100] [0,100] [0,100] [0,100] [0,100] [0,100] [0,100] Kirk extracts a least commitment plan and generates a rationale [0,100] Fly-Start Fire Fly-Inv [20,+INF] ress-Start -Inv [10,20] Refit-Start Refit-Inv [10,+INF] d Fly-Start Fly-Inv [20,+INF] Fly-Inv [20,+INF] Kirk Model-based Execution System Overview Strategy Selection TPN Planner Activity Planning Generative Activity Planner Visibility Graph Mission Developer RMPL Strategy macro control decomposition program Mission Controller Human / Computer Interface MILP Path-Planning ? Strategy Selection ? Activity Planning figures out within strategic framework using determines the optimal rules / strategies to accomplish mission goals. how to achieve mission goals available low-level actions. Strategy Macro Library Operators, Scenario Model Tactics, state configuration goals environment and action data schedulable plan with rationale Output: Least Commitment Plan with Rationale Plan layered with rationale Rescue(UAV1,Troops,RSQ) Refit(UAV1) Fly(UAV1,Base,RSQ) Fly(UAV1,RSQ,Base) [20,+INF] [10,+INF] [20,+INF] [30,60] [20,+INF] [10,20] [20,+INF] [0,100] [0,100] Control Program Phase II Control Program Phase I Fly(UAV2,Radar,Base) Fly(UAV2,Base,Radar) Attack(UAV2,Radar) Kirk Ensures Plan Completeness, Consistency and Minimality Activity-A fact-L Activity-C fact-J [l 3 ,u 3 ] fact-O [l 1 ,u 1 ] fact-M Start End Activity-B Activity-D fact-P fact-K fact-N[l 2 ,u 2 ] [l 4 ,u 4 ] ? Complete Plan ? A plan is complete IFF every precondition of every activity is achieved. ? An activity’s precondition is achieved IFF: ? The precondition is the effect of a preceding activity (support), and ? No intervening step conflicts with the precondition (mutex). ? Consistent Plan ? The plan is consistent IFF the temporal constraints of its activities are consistent (the associated distance graph has no negative cycles), and ? no conflicting (mutex) activities can co-occur. ? Minimal Plan ? The plan is minimal IFF every constraint serves a purpose, i.e., ? If we remove any temporal or symbolic constraint from a minimal plan, the new plan is not equivalent to the original plan Plan-based HCI Proof of Concept: Coaching through Coordinated Views (Courtesy of Howard Shrobe, Principal Research Scientist, MIT CSAIL. Used with permission.) Plan & Geography View Sequencing: (Courtesy of Howard Shrobe, Principal Research Scientist, MIT CSAIL. Used with permission.) Causal View Causality Explanation (Courtesy of Howard Shrobe, Principal Research Scientist, MIT CSAIL. Used with permission.) Model-based Programming of Robust Robotic Networks ? Long-lived systems achieve robustness by coordinating a complex network of internal devices. ? Programmers make a myriad of mistakes when programming these autonomic processes. ? Model-based programming simplifies this task by elevating the programmer to the level of a coach: – Makes hidden states directly accessible to the programmer. – Automatically mapping between states, observables and control variables. ? Model-based executives reasoning quickly and extensively by exploiting conflicts. ? Mission-level executives combine activity planning, logical decision making and control into a single hybrid decision problem.