Temporal Plan Execution: Dynamic Scheduling and Simple Temporal Networks 1 Brian C. Williams 16.412J/6.834J May 10 th , 2004 Outline ? Review: Constraint-based Interval Planning ? Simple Temporal Networks ? Schedulability and Scheduling ? Review: Temporal, Model-based Programming ? Managing Execution Uncertainty – Execution with Dynamic Scheduling – Execution with Explicit Models of Uncertainty Mars Exploration Rovers – Jan. 2004 Mission Objectives: ? Learn about ancient water and climate on Mars. ? For each rover, analyze a total of 6-12 targets – Targets = natural rocks, abraded rocks, and soil ? Drive 200-1000 meters per rover Mini-TES Pancam Navcam Rock Abrasion Tool Microscopic Imager Mossbauer spectrometer APXS Image courtesy of JPL. Activity Name Durati on 10 11 12 13 14 15 16 17 18 19 20 21 22 23 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 0 1 2 3 4 5 6 7 8 9 DTE 4.50 0.75 DTE period DFE Night Time Rover Operations 16.97 Night Time Rover OperationsSleep Wakeup Pre-Comm Session Sequence Plan Review Current Sol Sequence Plan Review 1.50 1.50 Current Sol Sequence Plan Review Prior Sol Sequence Plan Review 2.00 Prior Sol Sequence Plan Review Real-TIme Monitoring 4.50 0.75 Real-TIme Monitoring Real-TIme Monitoring Downlink Product Generation... 2.75 Downlink Product Generation Tactical Science Assessment/Observation Planning 5.00 Tactical Science Assessment/Observation Planning Science DL Assessment Meeting 1.00 Science DL Assessment Meeting Payload DL/UL Handoffs 0.50 Payload DL/UL Handoffs Tactical End-of-Sol Engr. Assessment & Planning 5.50 Tactical End-of-Sol Engr. Assessment & Planning DL/UL Handover Meeting 0.50 DL/UL Handover Meeting Skeleton Activity Plan Update 2.50 Skeleton Activity Plan Update SOWG Meeting 2.00 SOWG Meeting Uplink Kickoff Meeting 0.25 Uplink Kickoff Meeting Activity Plan Integration & Validation 1.75 Activity Plan Integration & Validation Activity Plan Approval Meeting 0.50 Activity Plan Approval Meeting Build & Validate Sequences 2.25 Build & Validate Sequences UL1/UL2 Handover 1.00 UL1/UL2 Handover Complete/Rework Sequences 2.50 Complete/Rework Sequences Margin 1 0.75 Margin 1 Command & Radiation Approval 0.50 Command & Radiation Ap Margin 2 1.25 Margin 2 Radiation 0.50 Radiation MCT Team 7.00 4.00 One day in the life of a Mars rover Courtesy: Jim Erickson Downlink Assessment Science Planning Sequence Build/Validation Uplink EUROPA Automated Planning System EUROPA Automated Planning System Science Navigation Engineering Resource Constraints DSN/Telcom Flight Rules Science Team Sequence Build MAPGEN: Automated Science Planning for MER Planning Lead: Kanna Rajan (ARC) A Temporal Planning Problem Past Image(?target)meets Pointing(Earth) Status(Cam1, Off) Status(Cam2, On) CalibrationTarget(T17) Future meets -? ? Constraint-based Operators Pointing(?target) Status(?instr, Calibrated) TakeImage(?target, ?instr) Image(?target) meets contains contains TakeImage (?target, ?instr) contained-by Status(?instr, Calibrated) contained-by Pointing(?target) meets Image(?target) Representing Timing: Qualitative Temporal Relations [Allen AAAI83] A B A before B A BA meets B A B A overlaps B A contains B A B A = B A B A B A starts B A B A ends B Expansion 1 Image(A7) Future meets st meets Pointing(Earth) Status(Cam1, Off) Status(Cam2, On) CalibrationTarget(T17) ? Pointing(A7) Status(?instr, Calibrated) TakeImage(A7, ?instr) meets contains contains before A Consistent Complete Temporal Plan Pointing(Earth) Status(Cam1, Off) Status(Cam2, On) CalibrationTarget(T17) Image(A7) Pointing(A7) Status(Cam2, Calibrated) TakeImage(A7, Cam2) meets contains contains Turn(A7) Pointing(T17) Calibrate(Cam2) meets meets meetsmeets contains contains Turn(T17) meets meets Future meets ? Past meets -? Planner Must: ? Check schedulability of candidate plans. ? Schedule the activities of a complete plan. Outline ? Review: Constraint-based Interval Planning ? Simple Temporal Networks ? Schedulability and Scheduling ? Review: Temporal, Model-based Programming ? Managing Execution Uncertainty – Execution with Dynamic Scheduling – Execution with Explicit Models of Uncertainty Qualitative Temporal Constraints Maybe Expressed as Inequalities (Vilain, Kautz 86) ?x before y X + < Y - ? x meets y X + = Y - ? x overlaps y (Y - < X + ) & (X - < Y + ) ? x during y (Y - < X - ) & (X + < Y + ) ?x starts y (X - = Y - ) & (X + < Y + ) ?x finishes y (X - < Y - ) & (X + = Y + ) ? x equals y (X - = Y - ) & (X + = Y + ) Inequalities may be expressed as binary interval relations: X + -Y - ? [-inf, 0] Metric Constraints ? Going to the store takes at least 10 minutes and at most 30 minutes. :10 < [T + (store) – T - (store)] < 30 ? Bread should be eaten within a day of baking. :0 < [T + (baking) – T - (eating)] < 1 day ? Inequalities, X + < Y - , may be expressed as binary interval relations: :-inf< [X + -Y - ] < 0 Metric Time: Temporal CSPS (Dechter, Meiri, Pearl 91) TCSP: ? A set of time points X i at which events occur. ? Unary constraints (a 0 < X i < b 0 ) or (a 1 < X i < b 1 ) or . . . ? Binary constraints (a 0 < X j -X i < b 0 ) or (a 1 < X j -X i < b 1 ) or . . . “ Bread should be eaten within a day of baking.” :0 < [T + (baking) – T - (eating)] < 1 day In General Solving TCSPs is NP Hard Forward(I 1 , . . ., I i ) 1. if i = m then 2. M M union Solve-STP(I 1 , . . ., I m ), and 3. Go-Back(I 1 , . . ., I m ); 4. C i+1 empty; 5. for every I j in D i+1 do 6. if Consistent-STP (I 1 , . . . , I i , I j ), then 7. . . . TCSPs Are Visualized Using Directed Constraint Graphs 1 3 42 0 [10,20] [30,40] [60,inf] [10,20] [20,30] [40,50] [60,70] Simple Temporal Networks (STNs) (Dechter, Meiri, Pearl 91) At most one interval per constraint ?T ij = (a ij d X i -X j d b ij ) 1 3 42 0 [10,20] [30,40] [60,inf] [10,20] [20,30] [40,50] [60,70] Sufficient to represent: ? most Allen relations ? simple metric constraints Can’t represent: ? Disjoint activities Thrust Goals Attitude Turn(a,b) Point(a) Point(b) Turn(b,a) Engine Thrust (b, 200) OffOff Delta_V(direction=b, magnitude=200) Power Warm Up A Temporal Plan Forms an STN >@ >@ ! >@ >f@ >f@ >@ A Temporal Plan Forms an STN Outline ? Review: Constraint-based Interval Planning ? Simple Temporal Networks ? Schedulability and Scheduling ? Review: Temporal, Model-based Programming ? Managing Execution Uncertainty – Execution with Dynamic Scheduling – Execution with Explicit Models of Uncertainty TCSP Queries (Dechter, Meiri, Pearl, AIJ91) ? Is the TCSP consistent? Planning ? What are the feasible times for each X i ? Planning ? What are the feasible durations between Planning each X i and X j ? ? What is a consistent set of times? Scheduling ? What are the earliest possible times? Scheduling ? What are the latest possible times? To Query an STN Map to a Distance Graph G d = < V,E d > 70 1 3 42 0 20 50 -10 40 -30 20 -10 -40 -60 1 3 42 0 [10,20] [30,40] [10,20] [40,50] [60,70] T ij = (a ij d X j -X i d b ij ) X j -X i db ij X i -X j d -a ij ? Edge encodes an upper bound on distance to target from source. ? Negative edges are lower bounds. G d Induces Constraints ? Path constraint: i 0 =i, i 1 = . . ., i k = j :Conjoined path constraints result in the shortest path as bound: where d ij is the shortest path from i to j X j  X i d a i j1 ,i j j 1 k | X j  X i d d ij Conjoined Paths Computed using All Pairs Shortest Path (e.g., Floyd-Warshall, Johnson) 1. for i := 1 to n do d ii 0; 2. for i, j := 1 to n do d ij a ij ; 3. for k := 1 to n do 4. for i, j := 1 to n do 5. d ij min{d ij , d ik + d kj }; i k j 0 1 2 3 4 0 0 20503070 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph Shortest Paths of G d 70 1 2 43 0 20 50 -10 40 -30 20 -10 -40 -60 STN Minimum Network 0 1 2 3 4 0 [0] [10,20] [40,50] [20,30] [60,70] 1 [-20,-10] [0] [30,40] [10,20] [50,60] 2 [-50,-40] [-40,-30] [0] [-20,-10] [20,30] 3 [-30,-20] [-20,-10] [10,20] [0] [40,50] 4 [-70,-60] [-60,-50] [-30,-20] [-50,-40] [0] 0 1 2 3 4 0 0 20503070 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph STN minimum network Schedulability: Plan Consistency 0 1 2 3 4 0 0 20503070 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph 70 1 2 43 0 20 50 -10 40 -30 20 -10 -40 -60 No negative cycles: -5 > T A –T A = 0 Scheduling: Latest Solution 0 1 2 3 4 0 0 20503070 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 70 1 2 43 0 20 50 -10 40 -30 20 -10 -40 -60 d-graph Node 0 is the reference. S 1 = (d 01 , . . . , d 0n ) Scheduling: Earliest Solution 0 1 2 3 4 0 0 20503070 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 70 1 2 43 0 20 50 -10 40 -30 20 -10 -40 -60 d-graph Node 0 is the reference. S 1 = (-d 10 , . . . , -d n0 ) Scheduling: Window of Feasible Values 0 1 2 3 4 0 0 20503070 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph ?X 1 in [10, 20] ?X 2 in [40, 50] ?X 3 in [20, 30] ?X 4 in [60, 70] Latest Times Earliest Times Scheduling without Search: Solution by Decomposition 0 1 2 3 4 0 0 20503070 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph ? Select value for 1 ? 15 [10,20] ? Can assign variables in any order, without backtracking. 0 1 2 3 4 0 0 20503070 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph ? Select value for 1 ? 15 [10,20] Solution by Decomposition ? Can assign variables in any order, without backtracking. Solution by Decomposition 0 1 2 3 4 0 0 20503070 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph ? Select value for 2, consistent with 1 ? 45 [40,50], 15+[30,40] ? Select value for 1 ? 15 ? Can assign variables in any order, without backtracking. ? Tighten bound of Y using all selected X: Y ? X + |XY| Solution by Decomposition 0 1 2 3 4 0 0 20503070 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph ? Select value for 2, consistent with 1 ? 45 [45,50] ? Select value for 1 ? 15 ? Can assign variables in any order, without backtracking. ? Tighten bound of Y using all selected X: Y ? X + |XY| Solution by Decomposition 0 1 2 3 4 0 0 20503070 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph ? Select value for 2, consistent with 1 ? 45 [45,50] ? Select value for 1 ? 15 ? Can assign variables in any order, without backtracking. ? Tighten bound of Y using all selected X: Y ? X + |XY| Solution by Decomposition 0 1 2 3 4 0 0 20503070 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph ? Select value for 2, consistent with 1 ? 45 ? Select value for 1 ? 15 ? Select value for 3, consistent with 1 & 2 ? 30 [20,30], 15+[10,20],45+[-20,-10] ? Can assign variables in any order, without backtracking. ? Tighten bound of Y using all selected X: Y ? X + |XY| Solution by Decomposition 0 1 2 3 4 0 0 20503070 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph ? Select value for 2, consistent with 1 ? 45 ? Select value for 1 ? 15 ? Select value for 3, consistent with 1 & 2 ? 30 [25,30] ? Can assign variables in any order, without backtracking. ? Tighten bound of Y using all selected X: Y ? X + |XY| Solution by Decomposition 0 1 2 3 4 0 0 20503070 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph ? Select value for 2, consistent with 1 ? 45 ? Select value for 1 ? 15 ? Select value for 3, consistent with 1 & 2 ? 30 [25,30] ? Can assign variables in any order, without backtracking. ? Tighten bound of Y using all selected X: Y ? X + |XY| Solution by Decomposition 0 1 2 3 4 0 0 20503070 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph ? Select value for 4, consistent with 1,2 & 3 O(N 2 ) ? Select value for 2, consistent with 1 ? 45 ? Select value for 1 ? 15 ? Select value for 3, consistent with 1 & 2 ? 30 ? Can assign variables in any order, without backtracking. ? Tighten bound of Y using all selected X: Y ? X + |XY| Outline ? Review: Constraint-based Interval Planning ? Simple Temporal Networks ? Schedulability and Scheduling ? Review: Temporal, Model-based Programming ? Managing Execution Uncertainty – Execution with Dynamic Scheduling – Execution with Explicit Models of Uncertainty 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 X0 X1 XN-1 XN S T X0 X1 XN-1 XN least cost reachable goal state First ActionCurrent Belief State Control Sequencer Deductive Controller Environment Model CommandsObservations Control Program Kirk Model-based ExecutiveRMPL Model-based Program location goalslocation estimates 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 POINTCOL RENDEZVOUS Diverge SCIENCE AREA 1’ SCIENCE AREA 3SCIENCE ARE Landing Site: ABC Landing Site: XYZ O N E SCIENCE AREA 1SCIENCE ARE Model-predictive dispatch ? pre-plans safe execution ? executes while adapting to execution uncertainties. Plant Schedules and Dispatches Activities Dynamically Example Enroute Activity: Rendezvous Rescue Area Corridor 2 Corridor 1 Enroute RMPL for Group-Enroute Group-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 } } Planning Group-Enroute 3 6 4 5 [405,486] Ask(PATH1=OK) 1 2 7 Ask(PATH2=OK) 8 [405,486] [450,540] Ask(PROCEED) 1 1 9 1 0 [0,54] 1 2 1 3 [0,2] [0,f] [0,f] [0,f] 14 15 Tell(PATH1=OK) [450,450] 16 17 Tell(PROCEED) [200,200] s e [500,800] [10,10] [0,f] To Plan: ? Instantiate Group-Enroute ? Select schedulable threads of execution that resolve Tell and Asks. Group-Enroute Group Traverse Group Traverse Group Wait Group Transmit Science Target Control Sequencer Deductive Controller Environment Model CommandsObservations Control Program Kirk Model-based ExecutiveRMPL Model-based Program location goalslocation estimates 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 POINTCOL RENDEZVOUS Diverge SCIENCE AREA 1’ SCIENCE AREA 3SCIENCE ARE Landing Site: ABC Landing Site: XYZ O N E SCIENCE AREA 1SCIENCE ARE Model-predictive dispatch ? pre-plans safe execution ? executes while adapting to execution uncertainties. Plant Schedules and Dispatches Activities Dynamically Outline ? Review: Constraint-based Interval Planning ? Simple Temporal Networks ? Schedulability and Scheduling ? Review: Temporal, Model-based Programming ? Managing Execution Uncertainty – Execution with Dynamic Scheduling – Execution with Explicit Models of Uncertainty Executing Flexible Temporal Plans [Muscettola, Morris, Pell et al.] EXECUTIVE CONTROLLED SYSTEM Handling delays and fluctuations in task duration: ? Least commitment temporal plans leave room to adapt. Flexible execution adapts through dynamic scheduling. ? Assigns time to event when executed. Issues in Flexible Execution 1. How do we minimize execution latency? 2. How do we schedule at execution time? Time Propagation Can Be Costly EXECUTIVE CONTROLLED SYSTEM EXECUTIVE CONTROLLED SYSTEM Time Propagation Can Be Costly EXECUTIVE CONTROLLED SYSTEM Time Propagation Can Be Costly EXECUTIVE CONTROLLED SYSTEM Time Propagation Can Be Costly EXECUTIVE CONTROLLED SYSTEM Time Propagation Can Be Costly EXECUTIVE CONTROLLED SYSTEM Time Propagation Can Be Costly Issues in Flexible Execution 1. How do we minimize execution latency? ? Propagate through a small set of neighboring constraints. 2. How do we schedule at execution time? EXECUTIVE CONTROLLED SYSTEM Compile to Efficient Network EXECUTIVE CONTROLLED SYSTEM Compile to Efficient Network EXECUTIVE CONTROLLED SYSTEM Compile to Efficient Network Issues in Flexible Execution 1. How do we minimize execution latency? ? Propagate through a small set of neighboring constraints. 2. How do we schedule at execution time? Issues in Flexible Execution 1. How do we minimize execution latency? ? Propagate through a small set of neighboring constraints. 2. How do we schedule at execution time? ? Through decomposition? Dynamic Scheduling by Decomposition A C B D [0,10] [2,2] [1,1][0,10] Simple Example A C B D 0 0 10 10 2 -2 -1 1 Equivalent Distance Graph Representation A C B D 0 0 10 10 2 -2 -1 1 Equivalent Distance Graph Representation A C B D 0 0 10 10 2 -2 -1 1 11 -2 1-1 Equivalent All Pairs Shortest Paths (APSP) Representation ? Compute APSP graph ? Decomposition enables assignment without search Dynamic Scheduling by Decomposition Assignment by Decomposition A C B D 0 0 10 10 2 -2 -1 1 11 -2 1-1t = 0 <0,10> <0,10> <2,11> ? Select executable timepoint and assign ? Propagate assignment to neighbors A C B D 0 0 10 10 2 -2 -1 1 11 -2 1-1 t = 3 <0,10> <0,0> <2,11> Assignment by Decomposition ? Select executable timepoint and assign ? Propagate assignment to neighbors ? Select executable timepoint and assign ? Propagate assignment to neighbors A C B D 0 0 10 10 2 -2 -1 1 11 -2 1-1 <2,2> <0,0> <4,4> But C now has to be executed at t =2, which is already in the past! Solution: ? Assignments must monotonically increase in value. ? First execute all APSP neighbors with negative delays. Assignment by Decomposition t = 3 Dispatching Execution Controller Execute an event when enabled and active ? Enabled - APSP Predecessors are completed – Predecessor – a destination of a negative edge that starts at event. ?Active - Current time within bound of task. Initially: ? E = Time points w/o predecessors ? S = {} Repeat: 1. Wait until current_time has advanced st a. Some TP in E is active b. All time points in E are still enabled. 2. Set TP’s execution time to current_time. 3. Add TP to S. 4. Propagate time of execution to TP’s APSP immediate neighbors. 5. Add to A, all immediate neighbors that became enabled. a. TPx enabled if all negative edges starting at TPx have their destination in S. Dispatching Execution Controller EXECUTIVE Propagation is Focused ? Propagate forward along positive edges to tighten upper bounds. – forward prop along negative edges is useless. ? Propagate backward along negative edges to tighten lower bounds. –Backward prop along positive edges useless. Propagation Example A C B D 0 -1 10 9 2 -2 -1 1 -2 -11 11 <0,0> S = {A} Propagation Example A C B D 0 -1 10 9 2 -2 -1 1 -2 -11 11 <0,0> <1,10> S = {A} Propagation Example A C B D 0 -1 10 9 2 -2 -1 1 -2 -11 11 <0,0> <1,10> <0,9> S = {A} Propagation Example A C B D 0 -1 10 9 2 -2 -1 1 -2 -11 11 <0,0> <1,10> <0,9> <2,11> S = {A} Propagation Example A C B D 0 -1 10 9 2 -2 -1 1 -2 -11 11 <0,0> <1,10> <0,9> <2,11> S = {A} E = { C } A C B D 0 0 10 10 2 -2 -1 1 11 -2 1-1 t = 3 <0,10> <0,0> <2,11> Execution time is: ? worst case O(n) ? best case O(n) Filtering: ? some edges are redundant ? remove redundant edges Reducing Execution Latency Edge Domination ? BC upper-dominates AC if in every consistent execution, T B + b(B,C) d T A + b(A,C) –The thread running through A-B-C is always just as fast or faster than the thread running through A-C A C B Edge Domination ? AB lower-dominates AC if in every consistent execution, T B - b(A,B) t T C -b(A,C) – Enablement of node A is always determined by thread running through A-B-C A C B The Triangle Rule ? A non-negative edge AC is upper-dominated by another non-negative edge BC if and only if |AB| + |BC| = |AC| ? A negative edge AC is lower-dominated by another negative edge BC if and only if |AB| + |BC| = |AC| A Proof of the Triangle Rule ? Let’s look at the proof for upper-bound domination –T B -T A d |AB| –?T B d T A + |AB| –|AB| + |BC| = |AC| –? T B d T A + |AC| -|BC| –? T B + |BC| d T A + |AC| ? Thus, the triangle rule guarantees that the A-B-C thread always gets to C before than the A-C thread. ? Similar proof applies for lower-bound domination Filtering Edges ? So, an edge that satisfies the triangle rule is unneeded because its thread of execution always lags behind the thread that runs through the dominant edge –This means that the execution of C through the A-B-C thread will always satisfy the AC constraint, regardless of its presence –Notice also that A is enabled by both threads, so removing AC won’t violate C’s enablement condition C A B 150 -100 10080 -50 -20 ? Edge Dominance – Eliminate edge that is redundant due to the triangle inequality AB + BC = AC C A B 150 -100 10080 -50 -20 ? Edge Dominance – Eliminate edge that is redundant due to the triangle inequality AB + BC = AC C A B 150 -100 80 -50 -20 ? Edge Dominance – Eliminate edge that is redundant due to the triangle inequality AB + BC = AC C A B 150 -100 80 -50 ? Edge Dominance – Eliminate edge that is redundant due to the triangle inequality AB + BC = AC An Example of Edge Filtering ? Start off with the APSP network A C B D 0 -1 10 9 2 -2 -1 1 -2 -11 11 An Example of Edge Filtering ? Start at A-B-C triangle A C B D 0 -1 10 9 2 -2 -1 1 -2 -11 11 An Example of Edge Filtering ? Look at B-D-C triangle A C B D 0 -1 2 -2 -1 1 -2 -1 11 9 1 An Example of Edge Filtering ? Look at B-D-C triangle A C B D 0 -1 2 -2 -1 1 -1 11 9 1 An Example of Edge Filtering ? Look at D-A-B triangle A C B D 0 -1 2 -1 1 -1 11 9 1 An Example of Edge Filtering ? Look at D-A-C triangle A C B D 0 2 -1 1 -1 11 9 1 An Example of Edge Filtering ? Look at B-C-D triangle A C B D 0 2 -1 1 -1 9 1 An Example of Edge Filtering ? Look at B-C-D triangle A C B D 0 -1 1 -1 9 1 An Example of Edge Filtering ? Resulting network has less edges than the original A C B D 0 -1 1 -1 9 1 A C B D 0 0 10 10 2 -2 -1 1 A |LA| |AL| L B |BL| |LB| ? Node Contraction – Collapse two events with fixed time between them Additional Filtering AL B |BL| |LB| ? Node Contraction – Collapse two events with fixed time between them Additional Filtering An Example of Node Contraction ? Resulting network has less edges than the original A C B D 0 -1 1 -1 9 1 A CBD 0 9 Avoiding Intermediate Graph Explosion Problem: ? APSP consumes O(n 2 ) space. Solution: ? Interleave process of APSP construction with edge elimination – Never have to build whole APSP graph Outline ? Review: Constraint-based Interval Planning ? Simple Temporal Networks ? Schedulability and Scheduling ? Review: Temporal, Model-based Programming ? Managing Execution Uncertainty – Execution with Dynamic Scheduling – Execution with Explicit Models of Uncertainty Uncertainty ? Uncertainty in a Temporal Network occurs whenever the occurrence time of some events may not be under the control of the execution agent ? For Example: Sequence Start Interrogate SensorTurn Sensor On Sensor Information Acquired -1 1 0 3 -2 10 1023 Uncertainty ? Uncertainty in a Temporal Network occurs whenever the occurrence time of some events may not be under the control of the execution agent ? For Example: Agent is in full control when turning a sensor on Sequence Start Interrogate SensorTurn Sensor On Sensor Information Acquired -1 1 0 3 -2 10 1023 t = 0 <1,1> Uncertainty ? Uncertainty in a Temporal Network occurs whenever the occurrence time of some events may not be under the control of the execution agent ? For Example: Agent is in full control when turning a sensor on Sequence Start Interrogate SensorTurn Sensor On Sensor Information Acquired -1 1 0 3 -2 10 1023 <0,0> t = 1 <1,4> Uncertainty ? Uncertainty in a Temporal Network occurs whenever the occurrence time of some events may not be under the control of the execution agent ? For Example: Agent is in full control when turning a sensor on Agent is not in control when interrogating the sensor Sequence Start Interrogate SensorTurn Sensor On Sensor Information Acquired -1 1 0 3 -2 10 1023 <0,0> <1,1> t = 3 <5,13> Uncertainty ? Uncertainty in a Temporal Network occurs whenever the occurrence time of some events may not be under the control of the execution agent ? For Example: Agent is in full control when turning a sensor on Agent is not in control when interrogating the sensor Sequence Start Interrogate SensorTurn Sensor On Sensor Information Acquired -1 1 0 3 -2 10 1023 <0,0> <1,1> t = 3 t = ? Formal Definition of STNU ?STN – 4-tuple < N, E, l, u >, where ? N is a set of nodes ? E is a set of edges ?l : E o??{-f} ?u : E o??{+f} ?STNU – 5-tuple < N, E, l, u, C >, where ? N, E, l, u are as defined in an STN ? C is a subset of E – The edges in C are called the contingent links ? 0 < l(e) < u(e) < f – All other edges are called requirement links C A B C A B Contingent Link Requirement Links Formal Definition of STNU Implied dependency on the contingent links: ? We can think of an STNU representing a family of STNs for every consistent execution of each contingent link C A B [l, u] [x, y] [w, z] C A B [l(e), l(e)] [x, y] [w, z] C A B [u(e), u(e)] [x, y] [w, z] C A B [b, b] [x, y] [w, z] Safe Networks ? An STNU is safe if and only if the forward and reverse edges from each contingent link are the tightest edges. ? In the APSP graph, the forward edge of each contingent link dominates all positive edges ending up at the contingent link finishing node. ? In the APSP graph, the reverse edge of each contingent link dominates all negative edges starting from the contingent link finishing node C A B 150 -100 10080 -60 -1 AB = 150 BA = -100 AB = 180 BA = -61 150 < 180 -100 < -61 ? Contingent link survives Preferences for times: Satellite Observation Scheduling Slew Take scene Take scene… time Antenna slewing on Landsat 7 may cause vibration, potentially affecting the quality of image taken. Therefore preferable for antenna slewing not to overlap with imaging, if possible. ok Better! Example [1 1] [10 20] B C D A [1 10] [1 10] = min soft constraint STP P Model-based Programming & Task Execution Reactive Task Expansion Projective Task Expansion Goals Dynamic Scheduling and Task Dispatch Task Dispatch Temporal Plan Commands Observations Modes Goals and Environment Constraints Temporal Network Solver Temporal Planner