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