1Robust Task Execution:Procedural and Model-based 1Brian C. Williams16.412J/6.834J March 14th, 2005Model-based ExecutiveRobust Task ExpansionProjectiveTask ExpansionGoalsDynamic Scheduling and Task DispatchTaskDispatchTemporal PlanCommandsObservationsModesMission Goals and Environment ConstraintsTemporalNetworkSolverTemporalPlannerInitial ConditionsDesiderata: Robust Task-level ExecutionSPlantObsCntrlModel-basedEmbedded ProgramsSContinuousReactiveCommandingContinuous Mode/StateEstimation ModelCreate Languages that are:• Suspicious•Monitor intentions and plans • Self-Adaptive• Exploits and generates contingencies• Anticipatory• Predicts, plans and verifies into future•State Aware• Commanded with desired state• Fault Aware•Reasons about and responds to failureOutline• Safe Procedural Execution• Model-Predictive Dispatch• Model-based Reactive PlanningRobust Task Execution: RAPS [Firby PhD]• RAPS Monitors Success Against Spec(define-rap (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)))))Robust Task Execution: RAPS [Firby PhD]• RAPS Exploits contingencies by performing functionally redundant method selection(define-rap (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)))))2• 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 to deal with contingencies and opportunities.ØMethods selected reactivelyðModel-predictive dispatch ØGoals explicitly observable and controllableðModel-based execution Robust Task Execution: RAPS [Firby PhD]Control SequencerDeductive ControllerEnvironment ModelCommandsObservationsControl ProgramKirk Model-based ExecutiveRMPL Model-based Programlocation goalslocation estimatesSelects consistent threads of activity from redundant methodsModeEstimationModeReconfigurationTrackslocationFinds least cost pathsl Executes concurrentlyl Preemptsl non-deterministic choicel A[l,u ] timingl A at l location HOMEHOMETWOEnrouteCOLLECTION POINTCOLLECTION POINTRENDEZVOUSRENDEZVOUSDivergeSCIENCE AREA 1’SCIENCE AREA 1’SCIENCE AREA 3SCIENCE AREA 3Landing Site: ABCLanding Site: XYZONESCIENCE AREA 1SCIENCE AREA 1Executive• pre-plans activities • pre-plans paths • dynamically schedules [Tsmardinos et al.]PlantSchedules and Dispatches Activities DynamicallyOutline• Safe Procedural Execution• Model-Predictive Dispatch– Model-based Programming– Temporal Plan Networks (TPN)– Activity Planning (Kirk)– Unifying Activity and Path Planning• Model-based Reactive PlanningExample: Cooperative Mars ExplorationHow do we coordinate heterogeneous teams of orbiters, rovers and air vehicles to perform globally optimal science exploration?Properties:l Teams exploit a hierarchy of complex strategies.l Maneuvers are temporally coordinated.l Novel events occur during critical phases.l Quick responses draw upon a library of contingencies.l Selected contingencies must respect timing constraints.HOMEHOMETWOEnrouteCOLLECTION POINTCOLLECTION POINTRENDEZVOUSRENDEZVOUSDivergeSCIENCE AREA 1’SCIENCE AREA 1’SCIENCE AREA 3SCIENCE AREA 3Landing Site: ABCLanding Site: XYZONESCIENCE AREA 1SCIENCE AREA 1Example: Cooperative Mars Exploration Reactive Model-based ProgrammingIdea: Describe team behaviors by starting with a rich concurrent, embedded programming language (RMPL,TCC, Esterel):l cl If c next Al Unless c next Al A, Bl Always A• Sensing/actuation activities• Conditional execution• Preemption• Full concurrency • Iterationl A [l,u] • TimingAdd temporal constraints:l Choose {A, B} • ContingencyAdd choice (non-deterministic or decision-theoretic):3Example EnrouteActivity:RendezvousRendezvous Rescue AreaRescue AreaCorridor 2Corridor 1EnrouteRMPL for Group-EnrouteGroup-Enroute()[l,u] = {choose {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}}RMPL for Group-EnrouteGroup-Enroute()[l,u] = {choose {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}}Activities:RMPL for Group-EnrouteGroup-Enroute()[l,u] = {choose {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}}Conditionalityand Preemption:RMPL for Group-EnrouteGroup-Enroute()[l,u] = {choose {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}}Sequentiality:Concurrency:RMPL for Group-EnrouteGroup-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}}Temporal Constraints:4RMPL for Group-EnrouteGroup-Enroute()[l,u] = {choose {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%];}
View Full Document