会 MERS Executing Model-based Programs sing Graph-based Temporal Planning Prof Brian C. williams February 23rd, 2004 16.412/6.834 Cognitive Robotics based on [Kim, williams Abramson, IJCAIO1I Outline MERS Model-based Programming Cooperative Vehicle missions The Reactive Model-based Programming Language (repl Temporal Plan Networks(TPN) Activity Planning(Kirk Unifying Activity and Path Planning
Executing Model-based Programs Using Graph-based Temporal Planning Prof. Brian C. Williams February 23rd, 2004 16.412/6.834 Cognitive Robotics based on [Kim,Williams & Abramson, IJCAI01] Outline • Model-based Programming • Cooperative Vehicle Missions • The Reactive Model-based Programming Language (RMPL) • Temporal Plan Networks (TPN) • Activity Planning (Kirk) • Unifying Activity and Path Planning
会 Why model-based programming Q MERS Leading Diagnosis .Legs deployed during descent Noise spike on leg sensors latched by monitors Laser altimeter registers 50ft Begins polling leg monitors to determine touch down Latched noise spike read as mage courtesy of JPL touchdown Engine shutdown at -50ft Mars Climate Orbiter · Mars polar lander Create Embedded Languages That Reason on the Fly from Commonsense models Model-based Programs MERS lai Interact Directly with State Embedded programs interact with Model-based programs plant sensors/actuators interact with plant state · Read sensors Read state Set actuators Write state ,,, Model-based Embedded Program Embedded Program obs Cntrl Plant Plant Programmer must map between Model-based executive maps state and sensors/actuators between sensors actuators to states
Why Model-based Programming? Create Embedded Languages That Reason on the Fly from Commonsense Models Leading Diagnosis: •Legs deployed during descent. • Noise spike on leg sensors latched by monitors. • Laser altimeter registers 50ft. • Begins polling leg monitors to determine touch down. • Latched noise spike read as touchdown. • Engine shutdown at ~50ft. Mars 98: • Climate Orbiter • Mars Polar Lander 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. Image courtesy of JPL
Example: The model-based program sets the state to thrusting, and the deductive controller Oxidizer tank Fuel tank →轻柱 Deduces that Plans actions thrust is off. and the engine is healthy six valves Deduces that a valve failed -stuck closed Determines that valves on the backup engine will achieve thrust. and plans needed actions RMPL Model-based Program Titan Model-based Executive Control Program Executes concurrent Pr Generates target goal states Queries(hidden) states conditioned on state estimates Asserts(hidden) state System Model State estimates State goals Tracks Tracks least e Valve plant states cost goal states Stuck Closed t。+4 closed/OE Stuck bservations Commands inflow outflow= Plant
Example: The model-based program sets the state to thrusting, and the deductive controller . . . . Determines that valves on the backup engine will achieve thrust, and plans needed actions. Deduces that a valve failed - stuck closed Plans actions to open six valves Oxidizer tank Oxidizer tank Fuel tank Fuel tank Deduces that thrust is off, and the engine is healthy Control Sequencer Deductive Controller System Model Observations Commands Control Program Plant RMPL Model-based Program Titan Model-based Executive State estimates State goals Generates target goal states conditioned on state estimates Mode Estimation Mode Reconfiguration 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
Modeling complex behaviors through Probabilistic concurrent constraint automata Valve Stuck Stuck Closed closed inflow outflow=0 Complex, discrete behaviors modeled through concurrency, hierarchy and non-determinism Anomalies and uncertainty modeled by probabilistic transitions Physical interactions modeled by discrete and continuous constraints Outline MERS Model-based Programming Cooperative Vehicle Missions The Reactive Model-based Programming Language (repl Temporal Plan Networks(TPN) Activity Planning(Kirk Unifying Activity and Path Planning
Closed Valve Open Stuck open Stuck closed Open Close 0. 01 0. 01 0.01 0.01 inflow = outflow = 0 Modeling Complex Behaviors through Probabilistic Concurrent Constraint Automata • Complex, discrete behaviors • modeled through concurrency, hierarchy and non-determinism. • Anomalies and uncertainty • modeled by probabilistic transitions • Physical interactions • modeled by discrete and continuous constraints Outline • Model-based Programming • Cooperative Vehicle Missions • The Reactive Model-based Programming Language (RMPL) • Temporal Plan Networks (TPN) • Activity Planning (Kirk) • Unifying Activity and Path Planning
Cooperative Search and Rescue MERS High-level vehicle coordination Fast Agile Maneuvering Cooperative Mars Exploration MERS How do we coordinate heterogeneous teams of orbiters rovers and air vehicles to perform globally optimal science exploration?
Cooperative Search and Rescue • High-level vehicle coordination • Fast Agile Maneuvering Cooperative Mars Exploration How do we coordinate heterogeneous teams of orbiters, rovers and air vehicles to perform globally optimal science exploration?
Example scenario MERS ⊥ ECTION POINT Enrout Landing Site: ABC DEZVOUS E AREA I SCIENCE AREA Properties SCIENCE AREA 3 Teams exploit a hierarchy of complex strategies maneuvers are temporally coordinated Novel events occur during critical phases Quick responses draw upon a library of contingencies Self-Adaptive Languages: RAPs [Firby PhD] RAPS programs monitor goals and plan activities ( define-rap (index(move-to? thing?place) (succeed (LoCatioN ?thing?place)) (method (context(and (location? thing?loc) (not(?loc UNKNOWN)) (task-net (to(goto?loc)((TRUCK-LOCATION ?loc)for tI)) (tl(pickup? thing(TRUCK -HOLDING? thing) for t2) (TRUCK-HOLDING ?thing) for t3)) (t2(goto?place)((TRUCK-LOCATION? place)for t3)) (t3(putdown?thing)) (method (context (LOCATiON? thing UNKNOWN)) (task-net (to(goto WAREHOUSE)
Properties: z Teams exploit a hierarchy of complex strategies. z Maneuvers are temporally coordinated. z Novel events occur during critical phases. z Quick responses draw upon a library of contingencies. Example Scenario HOME TWO COLLECTION POINTEnroute RENDEZVOUS Diverge SCIENCE AREA 1’ SCIENCE AREA 1’ SCIENCE AREA 3 Landing Site: ABC Landing Site: XYZ ONE SCIENCE AREA 1 Self-Adaptive Languages: RAPs [Firby PhD] • RAPS programs monitor goals and plan activities (define-rap (index (move-to ?thing ?place)) (succeed (LOCATION ?thing ?place)) (method (context (and (LOCATION ?thing ?loc) (not (= ?loc UNKNOWN)))) (task-net (t0 (goto ?loc) ((TRUCK-LOCATION ?loc) for t1)) (t1 (pickup ?thing)((TRUCK-HOLDING ?thing) for t2) ((TRUCK-HOLDING ?thing) for t3)) (t2 (goto ?place) ((TRUCK-LOCATION ?place) for t3)) (t3 (putdown ?thing)))) (method (context (LOCATION ?thing UNKNOWN)) (task-net (t0 (goto WAREHOUSE)))))
Self-Adaptive Languages: RAPs [Firby PhD RAPS Programs recover by selecting from functionally redundant methods (define-rap (index(move-to?thing? place)) (succeed (LoCation?thing?place)) (method (context( and (location? thing ?loc) (not(?loc UNKNOWN)) (task-net (to(goto ?loc)((TRUCK-LOCATION ? loc)for tD) (tl(pickup? thing)((tRUCK-HOLDING ?thing)for t2) (TRUCK-HOLDING? thing) for t3)) (t2(goto?place)((TRUCK-LOCATION ?place) for t3)) (t3(putdown? thing)) (method (context (LOCATION? thing UNKNOWN)) (task-net (to(goto WAREHOUSE)) Self-Adaptive languages: RAPS RAPS Exploits contingencies by performing functionally redundant method selection Methods are chosen based on the current situation If a method fails. another is tried instead Tasks do not complete until satisfied Methods can include monitoring subtasks that deal with contingencies and opportunities · Limitations Goals must be explicitly observable Methods selected reactively Method selection may dig itself into a hole Create Languages with planner-like capabilities
• RAPS Programs recover by selecting from functionally redundant methods (define-rap (index (move-to ?thing ?place)) (succeed (LOCATION ?thing ?place)) (method (context(and (LOCATION ?thing ?loc) (not (= ?loc UNKNOWN)))) (task-net (t0 (goto ?loc) ((TRUCK-LOCATION ?loc) for t1)) (t1 (pickup ?thing)((TRUCK-HOLDING ?thing) for t2) ((TRUCK-HOLDING ?thing) for t3)) (t2 (goto ?place) ((TRUCK-LOCATION ?place) for t3)) (t3 (putdown ?thing)))) (method (context (LOCATION ?thing UNKNOWN)) (task-net (t0 (goto WAREHOUSE))))) Self-Adaptive Languages: RAPs [Firby PhD] Self-Adaptive languages: RAPS • RAPS Exploits contingencies by performing functionally redundant method selection – Methods are chosen based on the current situation. – If a method fails, another is tried instead. – Tasks do not complete until satisfied. – Methods can include monitoring subtasks that deal with contingencies and opportunities. • Limitations • Goals must be explicitly observable • Methods selected reactively ¾Method selection may dig itself into a hole. Create Languages with planner-like capabilities
RMPL Model-based Program Kirk Model-based Executive Control Program Selects consistent Executes concurrently threads of activity Preempts non-deterministic choice from redundant methods L,u timing A at I location Schedules and Dispatches Activities dynamically Environment Mode location estimates location goals 命 Tracks Finds least location cost paths Executive pre-plans activities Observations Commands pre-plans paths Plant +i9 dynamically schedules [Tsmardinos et al. I Outline MERS Model-based Programming Cooperative Vehicle missions Reactive Model-based Programming Language (rMPl) Temporal Plan Networks(TPN) Activity Planning(Kirk Unifying Activity and Path Planning
Control Sequencer Deductive Controller Environment Model Observations Commands Control Program RMPL Model-based Program Kirk Model-based Executive location estimates location goals Selects consistent threads of activity from redundant methods Mode Estimation Mode Reconfiguration 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 SCIENCE AREA 3 Landing Site: ABC Landing Site: XYZ O N E SCIENCE AREA 1 SCIENCE AREA 1 Executive • pre-plans activities • pre-plans paths • dynamically schedules [Tsmardinos et al.] Plant Schedules and Dispatches Activities Dynamically Outline • Model-based Programming • Cooperative Vehicle Missions • Reactive Model-based Programming Language (RMPL) • Temporal Plan Networks (TPN) • Activity Planning (Kirk) • Unifying Activity and Path Planning
Reactive Model-based Programming mErS Idea: Describe team behaviors by starting with a rich concurrent embedded programming language(RMPL,TCC, Esterel) Sensing/actuation activities If c next A Conditional execution ● Unless c next A Preemption A B Full concurrency always A · Iteration Add temporal constraints A u · Timing Add choice(non-deterministic or decision-theoretic) Choose(A, B) · Contingency Example Enroute Activity: MERS Enroute Rendezvous escue a Corrid
Reactive Model-based Programming Idea: Describe team behaviors by starting with a rich concurrent, embedded programming language (RMPL,TCC, Esterel): z c z If c next A z Unless c next A z A, B z Always A • Sensing/actuation activities • Conditional execution • Preemption • Full concurrency • Iteration z A [l,u] • Timing z Add temporal constraints: z Choose {A, B} • Contingency z Add choice (non-deterministic or decision-theoretic): Example Enroute Activity: Rendezvous Rescue Area Corridor 2 Corridor 1 Enroute
RMPL for group-Enroute MERS Group-Enroute([l,u]=t choose i Group-Traverse- Path(PATH1 1, PATH1 2, PATH1 3, RE POS)[l*90g,u*9081 maintaining PATHI OK Group-Traverse- Path(PATH2 1, PATH2 2, PATH2 3, RE POS)[l*90,u*908] 1 maintaining PATH2 OK Group-Transmit(OPS, ARRIVED)[0, 21, Group-Wait(hOldI, HOLD2)[O,u*109] i watching PROCEED RMPL for Group-Enroute MERS Activities Group-Enroute()[l choose i Group-Traverse Path(PATH1 1, PATH1 2, PATH1 3, RE POS)[l*90,u*908]i maintaining PATH1 OK do Group-Traverse Path(PATH2 1, PATH2 2, PATH2 3, RE Pos)[l*909,u*909] 1 maintaining PATH2 OK Group-Transmit(OPS, ARRIVED)[0, 21, Group-Wait(HOLD1, HOLD2)[0, u*10% y watching PROCEED
RMPL for Group-Enroute Group-Enroute()[l,u] = { choose { do { Group-TraversePath(PATH1_1,PATH1_2,PATH1_3,RE_POS)[l*90%,u*90%]; } maintaining PATH1_OK, do { Group-TraversePath(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 } } RMPL for Group-Enroute Group-Enroute()[l,u] = { choose { do { Group-TraversePath(PATH1_1,PATH1_2,PATH1_3,RE_POS)[l*90%,u*90%]; } maintaining PATH1_OK, do { Group-TraversePath(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 } } Activities: