Temporal Plan Execution: Dynamic Scheduling and Simple Temporal Networks Outline • Review: Constraint -based Interval Planning • Simple Temporal Networks • Temporal Consistency and Scheduling • Execution Under Uncertainty Brian C. Williams 16.412J/6.834J March 7th, 2005 1 Simple Spacecraft Problem 1 target instruments 2 3 4 … calibrated pointing Example IxIm c px pC Init Actions C c Ty ¬px py px IA Goal pC 16.410/13: Solved using Graph ) Observation-Observation-Observation-Observation--based Planners (Blum & FurstPartial Order Causal Link Planning (SNLP, UCPOP) 1. Select an open condition 2. Choose an op that can achieve it Link to an existing instance Add a new instance 3. Resolve threats IA F Im c pA IA F pC C Im IA F c pA CpC Im IA F c pA S TA ¬pC CpC Im IA F c pAS pC TA ¬pC CpC Im IA F c pA S pC Based on slides by Dave Smith, NASA Ames Needed Extensions Time Resources Utility UncertaintyBased on slides by Dave Smith, NASA Ames Representing Timing: Qualitative Temporal Relations [Allen AAAI83] A BA before B A BA meets B A BA overlaps B A contains B A B A = B A B A B A starts B A B A ends B Based on slides by Dave Smith, NASA Ames Pointing(?target) Image(?target) meets contains contains Pointing(?target) meets Image(?target) TakeImage Pictorially Status(?instr, Calibrated) TakeImage(?target, ?instr) TakeImage (?target, ?instr) contained-by Status(?instr, Calibrated) contained-by Based on slides by Dave Smith, NASA Ames A Temporal Planning Problem Past Image(?target)meets Pointing(Earth) Status(Cam1, Off) Status(Cam2, On) CalibrationTarget(T17) Futuremeets 8 Based on slides by Dave Smith, NASA Ames 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 8 Past meets -8 -8 Based on slides by Dave Smith, NASA Ames CBI Planning Algorithm Choose: introduce an action & instantiate constraints coalesce propositions Propagate temporal constraints 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 8 Past meets Planner Must: execute. -8 • Check schedulability of candidate plans for correctness. • Schedule the activities of a complete plan in order toBased on slides by Dave Smith, NASA Ames Relation to Causal Links & Threats propositionaction meets meets actionaction action proposition action action proposition action threatens proposition action action proposition mutex POCL CBI Causal links: Threats : Based on slides by Dave Smith, NASA Ames Examples of CBI Planners intervals, no CSP Trains (Allen) extreme least commitment functional rep. functional rep., activities functional rep., activities Kirk (Williams) HTN Based on slides by Dave Smith, NASA Ames Outline • • Simple Temporal Networks • Temporal Consistency and Scheduling • Execution Under Uncertainty Based on slides by Dave Smith, NASA Ames Qualitative Temporal Constraints Maybe Expressed as Inequalities • 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: Y-- X+ Generalize to include metric constraints: Y-- X+ Based on slides by Dave Smith, NASA Ames < Xi, Ti ij > • Xi continuous variables • Ti ij interval constraints {I1 n } where Ii i,bi] i i £ Xi £ bi i £ Xi £ bi) ij = (a1£ Xi j £ b1 n £ Xi j £ bn) ? [T +(baking) – T -1 day Metric Time: Temporal CSPS Based on slides by Dave Smith, NASA Ames TCSP Are Visualized Using Directed Constraint Graphs 1 3 42 0 [10,20] [30,40] [60,inf] [10,20] [20,30] [40,50] [60,70] Zeno (Penberthy) Descartes (Joslin) IxTeT (Ghallab) HSTS (Muscettola) EUROPA (Jonsson) Review: Constraint -based Interval Planning (Vilain , Kautz 86) < [0, +inf] < [lb, ub] , T,T, . . . ,I = [a– T = (a ) or . . . or (a– T - X ) or ... or (a - X“ Bread should be eaten within a day of baking.” 0 < (eating)] < (Dechter, Meiri, Pearl 91)Simple Temporal Networks (STNs) (Dechter, Meiri, Pearl 91) At most one interval per constraint • Tij = (aij £ Xi - Xj £ bij ) 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 STNA Temporal Plan Forms an STN[1035, 1035] [130,170] <0, 0> [0, 300] [0, + ¥ ] [0, + ¥] [0, 0] A Temporal Plan Forms an STNA Temporal Plan Forms an STNOutline • Review: Constraint -based Interval Planning • Simple Temporal Networks • Temporal Consistency and Scheduling • Execution Under Uncertainty TCSP Queries (Dechter , Meiri, Pearl, AIJ91) • Is the TCSP consistent? • What are the feasible times for each Xi? • What are the feasible durations between each Xi and Xj? • What is a consistent set of times? • What are the earliest possible times? • What are the latest possible times? Planning Planning Planning Scheduling Scheduling To Query an STN, Map to a Distance Graph Gd = < V,Ed > • Edge encodes an upper bound on distance to target from source. • Negative edges are lower bounds. XT ij = (aij£ Xj- Xi £ bij) Xj- Xi £ bij i - Xj £ - aij 20 401 3 42 0 50 -10 -30 20 -10 -40 -60 1 3 42 0 [10,20] [30,40] [10,20] [40,50] [60,70] 70Gd Induces Constraints • Path constraint: i0 =i, i1 = . . ., ik= j k Xj - Xi £� ai j -1,ij j = 1 ? Conjoined path constraints result in the shortest path as bound: Xj -Xi £ dij where dij is the shortest path from i to j Conjoined Paths Computed using All Pairs Shortest Path (e.g., Floyd -Warshall, Johnson) 1. for i := 1 to n do dii 0; Initialize distances2. for i, j := 1 to n do dij aij; 3. for k := 1 to n doTake minimum distance 4. for i, j := 1 to n do over all triangles 5. dij min{dij, dik+ dkj}; ki
View Full Document
Unlocking...