Temporal Plan Execution: Dynamic Scheduling and Simple Temporal Networks Brian C. Williams 16412J6834J May10t,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
Temporal Plan Execution: Dynamic Scheduling and Simple Temporal Networks 1 Brian C. Williams 16.412J/6.834J May 10th, 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 Mini-TES Navcam Mossbauer spectromete APXS Rock Abrasion Tool Micro Mission Objectives Learn about ancient water and climate on For each rover, analyze a total of 6-12 targets Targets=natural rocks, abraded rocks, and soil Drive 200-1000 meters per rover
Mars Exploration Rovers – Jan. 2004 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 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
One day in the life of a Mars rover 10111213141516181920212223012345678 Plannig t teeing p Downlink Assessment; Science Planning Sequence Build/Validati 「11820212230 Courtesv. Jimm Erickson MAPGEN: Automated PL Science Planning for MER Planning Lead: Kanna Rajan(ARC) EUROPA Automated Planning System Flight rules ngineering Res Sequence Constraints Build Science Navigation DSNTelc Science team
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 Sleep Night Time Rover Operations 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 Calibration Target(T17) Constraint-based operators Takelmage(?target, ?instr) ntained-by Status(?instr, Calibr contained-by Pointing(?target meets mage(?target) Pointing(?target) contains meets Takelmage(?target, ?instr) Image(?target) Status(?instr, Calibrated)
A Temporal Planning Problem Past meets Image(?target) 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 AAAl83] a before B B verlaps B A contains B B A=B B A starts B Expansion 1 Pointing(Earth before Status(Cam1, Off) contains Takelmage(A 7. instr) me Image(A7 FUture Status(Cam2, Or contains Calibration Target(T17) Status(?instr, Calibrated)
Representing Timing: Qualitative Temporal Relations [Allen AAAI83] A before B A B A meets B A 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 Tum(A7) Status(Cam2, On) contain 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
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 meets meets 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<Y x meets X+=Y aps y (Y<X)&(x<Y) x during y (Y<X)&(x+<Y) X starts y (X=Y)&(x+<Y) (X<Y)&(x+=Y+) x equals y (X=Y)&(x+=Y+) Inequalities may be expressed as binary interval relations Y∈[-inf 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 bakin 0≤[Tr( baking)- T(eating)]≤lday Inequalities, X*<Y, may be expressed as binary interval relations inf<[X+-Y]<0
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) Bread should be eaten within a day of baking 0≤[T( baking)-T( eating)]≤lday TCSP A set of time points X, at which events occur Unary constraints (a0≤X≤b)o(a1≤X≤b1) Binary constraints X≤bo)or(a1≤XX≤b1)0 In General Solving TCSPs is nP hard Forward(……,l 1. ifi=m then 2.M← Munion solve-STP(l,…,lm,and 3.Go-Back/l1…,ln 4.C r eve li In D 6. if Consistent-STP(p.,Ii, p
Metric Time: Temporal CSPS (Dechter, Meiri, Pearl 91) TCSP: • A set of time points Xi at which events occur. • Unary constraints (a0 < Xi < b0 ) or (a1 < Xi < b1 ) or . . . • Binary constraints (a0 < Xj - Xi < b0 ) or (a1 < Xj - Xi < b1 ) 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(I1, . . ., Ii ) 1. if i = m then 2. M M union Solve-STP(I1, . . ., Im), and 3. Go-Back(I1, . . ., Im); 4. Ci+1 empty; 5. for every Ij in Di+1 do 6. if Consistent-STP (I1, . . . , Ii , Ij ), then 7. . .
TCSPs Are visualized using Directed Constraint Graphs [10,20] 160, inf [10,2 20,30 [40,50] Simple Temporal Networks(STNs) (Dechter, Meiri, Pearl 91) At most one interval per constraint T=(a1≤X-X≤b) [30,40] [10,2 Too,m [10,20] Can't represent Disjoint activities 0,30 Sufficient to represent most allen relations 4050 simple metric constraints
TCSPs Are Visualized Using Directed Constraint Graphs 1 3 2 4 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 • Tij = (aijd Xi - Xj d bij) 1 3 2 4 0 [10,20] [30,40] [60,inf] [10,20] [20,30] [40,50] [60,70] Sufficient to represent: • most Allen relations • simple metric constraints Sufficient to represent: • most Allen relations • simple metric constraints Can’t represent: • Disjoint activities Can’t represent: • Disjoint activities
A Temporal Plan Forms an Stn Thrust Delta v(direction=b, magnitude=200) Power Attitude Point(a)Turn(a, b Point(b) Turn(b, a Engine off Warm Up Thrust(, 200) Off A Temporal Plan Forms an Stn [1035,1035] [0300 [0,+o] [0,0] [13017
Thrust Goals Attitude Point(a) Turn(a,b) Point(b) Turn(b,a) Engine Off Thrust (b, 200) Off Delta_V(direction=b, magnitude=200) Power Warm Up A Temporal Plan Forms an STN A Temporal Plan Forms an STN >@ >@ ! >@ >f@ >f@ >@ A Temporal Plan Forms an STN A Temporal Plan Forms an STN