Temporal Planning in Space 1 Brian C. Williams 16.412J/6.834J February 23 rd , 2004 based on “Handling Time: Constraint-based Interval Planning,” by David E. Smith Based on slides by Dave Smith, NASA Ames Outline ? Operational Planning for the Mars Exploration Rovers ? Review of Least Commitment Planning ? Constraint-based Interval Planning ? Temporal Constraint Networks ? Model-based Program Execution as Graph-based Temporal Planning 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 Mars Exploration Rover Surface Operations Scenario Target Day 4 During the Day Science Activities Day 1 Long-Distance Traverse (<20-50 meters) Day 2 Initial Position; Followed by “Close Approach” During the Day Autonomous On- Board Navigation Changes, as needed Day 2 Traverse Estimated Error Circle Day 3 Science Prep (if Required) Day 2 Traverse Estimated Error Circle Image courtesy of JPL. Slide courtesy of Kanna Rajan. 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) Slide courtesy of Kanna Rajan. Slide courtesy of Kanna Rajan. Next Challenge: Mars Smart Lander (2009) Mission Duration: 1000 days Total Traverse: 3000-69000 meters Meters/Day: 230-450 Science Mission: 7 instruments, sub-surface science package (drill, radar), in-situ sample “lab” Technology Demonstration: (2005). Course Challenge ? What would it be like to operate MER if it was fully autonomous? Potential inspiration for course projects: ? Demonstrate an autonomous MER mission in simulation, and in the MIT rover testbed. Images courtesy of JPL. Based on slides by Dave Smith, NASA Ames Outline ? Operational Planning for the Mars Exploration Rovers ? Review of Least Commitment Planning ? Constraint-based Interval Planning ? Temporal Constraint Networks ? Model-based Program Execution as Graph-based Temporal Planning Planning Find: program of actions that achieves the objective Planning Find: program of actions that achieves the objective partially-ordered set goals Paradigms Classical planning (STRIPS, operator-based, first-principles) “generative” HTN planning “practical” planning MDP & POMDP planning planning under uncertainty The Classical Representation Operators: Goals: Goal 1 Goal 2 Goal 3 Op pre 1 pre 2 pre 3 eff 1 eff 2 Inits: P 1 P 2 P 3 P 4 Simple Spacecraft Problem Observation-1 target instruments Observation-2 Observation-3 Observation-4 … calibrated pointing Image courtesy of JPL. Example I x Im c p x p C Init Actions C c T y ?p x p y p x I A Goal p C POCL 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 I A F Im c p A I A F p C C Im I A F c p A C p C Im I A F c p A S T A ?p C C p C Im I A F c p A S p C T A ?p C Cp C Im I A F c p A S p C Based on slides by Dave Smith, NASA Ames Outline ? Operational Planning for the Mars Exploration Rovers ? Review of Least Commitment Planning ? Constraint-based Interval Planning ? Temporal Constraint Networks ? Model-based Program Execution as Graph-based Temporal Planning Based on slides by Dave Smith, NASA Ames An Autonomous Science Explorer Observation-1 priority time window target instruments duration Observation-2 Observation-3 Observation-4 … Objective: maximize science return Image courtesy of JPL. Based on slides by Dave Smith, NASA Ames Complications Observation-1 priority time window target instruments duration Observation-2 Observation-3 Observation-4 … calibration target1 target2 … consumables: fuel power data storage cryogen angle between targets ? turn duration Objective: maximize science return linked Based on slides by Dave Smith, NASA Ames Limitations of Classical Planning with Atomic Actions (aka STRIPS) Instantaneous actions No temporal constraints No concurrent actions No continuous quantities Image courtesy of JPL. Based on slides by Dave Smith, NASA Ames Some STRIPS Operators TakeImage (?target, ?instr): Pre: Status(?instr, Calibrated), Pointing(?target) Eff: Image(?target) Calibrate (?instrument): Pre: Status(?instr, On), Calibration-Target(?target), Pointing(?target) Eff: ?Status(?inst, On), Status(?instr, Calibrated) Turn (?target): Pre: Pointing(?direction), ?direction ? ?target Eff: ?Pointing(?direction), Pointing(?target) no time, no resources Based on slides by Dave Smith, NASA Ames Needed Extensions Time Resources Uncertainty Based on slides by Dave Smith, NASA Ames World Description State-centric: for each time describe propositions that are true Proposition-centric: for each proposition describe times it is true Pointing(A7) Status(Cam2, Calibrated) Turn(A7) Pointing(Earth) Status(Cam2, Calibrated) ? Image(A7) Turn(A7) Pointing(A7) Status(Cam2, Calibrated) ? Image(A7) Pointing(Earth) Based on slides by Dave Smith, NASA Ames Representing Timing: Qualitative Temporal Relations [Allen AAAI83] A B A before B A B A 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 Based on slides by Dave Smith, NASA Ames Representing Temporal Operators: TakeImage Schema TakeImage (?target, ?instr): Pre: Status(?instr, Calibrated), Pointing(?target) Eff: Image(?target) TakeImage (?target, ?instr) contained-by Status(?instr, Calibrated) contained-by Pointing(?target) meets Image(?target) Based on slides by Dave Smith, NASA Ames Pictorially 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) Based on slides by Dave Smith, NASA Ames TakeImage Schema Semantics TakeImage(?target, ?instr) A ?P {Status(?instr, Calibrated) P ? Contains(P, A)} ?Q {Pointing(?target) Q ? Contains(Q, A)} ?R {Image(?target) R ? Meets(A, R)} TakeImage (?target, ?instr) contained-by Status(?instr, Calibrated) contained-by Pointing(?target) meets Image(?target) Based on slides by Dave Smith, NASA Ames Turn Turn (?target) met-by Pointing(?direction) meets Pointing(?target) Pointing(?target) Pointing(?direction) Turn(?target) meets meets Based on slides by Dave Smith, NASA Ames Calibrate Status(?instr, Calibrated) Pointing(?target) CalibrationTarget(?target) Calibrate(?instr) meetsmeets contains contains Status(?instr, On) Calibrate (?instr) met-by Status(?instr, On) contained-by CalibrationTarget(?target) contained-by Pointing(?target) meets Status(?instr, Calibrated) 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) Future meets -? ? 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 ? Past meets -? Based on slides by Dave Smith, NASA Ames CBI Planning Algorithm Choose: introduce an action & instantiate constraints coalesce propositions Propagate constraints Based on slides by Dave Smith, NASA Ames Initial Plan Past Image(?target)meets Pointing(Earth) Status(Cam1, Off) Status(Cam2, On) CalibrationTarget(T17) Future meets -? ? Based on slides by Dave Smith, NASA Ames 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 Based on slides by Dave Smith, NASA Ames Expansion 2 ting(Earth) atus(Cam1, Off) atus(Cam2, On) brationTarget(T17) Image Pointing(A7) Status(?instr, Calibrated) TakeImage(A7, ?instr) meets contains contains Pointing(?direction) Turn(A7) Pointing(?caltarget) CalibrationTarget(?caltarget ) Calibrate(?instr) meetsmeets meetsmeets contains contains Status(?instr, On) before Based on slides by Dave Smith, NASA Ames Coalescing ng(Earth) tus(Cam1, Off) Status(Cam2, On) CalibrationTarget(T17) Image( Pointing(A7) Status(Cam2, Calibrated) TakeImage(A7, Cam2) meets contains contains Pointing(?direction) Turn(A7) Pointing(T17) Calibrate(Cam2) meetsmeets meetsmeets contains contains before before Based on slides by Dave Smith, NASA Ames Coalescing nting(Earth) tatus(Cam1, Off) Status(Cam2, On) CalibrationTarget(T17) Image Pointing(A7) Status(Cam2, Calibrated) TakeImage(A7, Cam2) meets contains contains Turn(A7) Pointing(T17) Calibrate(Cam2) meets meets meetsmeets contains contains before Based on slides by Dave Smith, NASA Ames Expansion 3 ting(Earth) atus(Cam1, Off) Status(Cam2, On) CalibrationTarget(T17) Image 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 Pointing(?direction) Based on slides by Dave Smith, NASA Ames Coalescing inting(Earth) Status(Cam1, Off) Status(Cam2, On) CalibrationTarget(T17) Imag 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 Based 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 Zeno (Penberthy) intervals, no CSP Trains (Allen) Descartes (Joslin) extreme least commitment IxTeT (Ghallab) functional rep. HSTS (Muscettola) functional rep., activities EUROPA (Jonsson) functional rep., activities Based on slides by Dave Smith, NASA Ames Outline ? Operational Planning for the Mars Exploration Rovers ? Review of Least Commitment Planning ? Constraint-based Interval Planning ? Temporal Constraint Networks ? Model-based Program Execution as Graph-based Temporal Planning Based on slides by Dave Smith, NASA Ames Y Qualitative Temporal Constraints (Allen 83) ? x before y ? x meets y ? x overlaps y ? x during y ? x starts y ? x finishes y ? x equals y X Y X Y X Y YX YX Y X X ?y after x ? y met-by x ? y overlapped-by x ? y contains x ? y started-by x ? y finished-by x ? y equals x Based on slides by Dave Smith, NASA Ames Example: Deep Space One Remote Agent Experiment Max_ThrustIdle Idle Poke Timer Attitude Accum SEP Action SEP_Segment Th_Seg contained_by equals equals meets meets contained_by Start_Up Start_Up Shut_Down Shut_Down Thr_Boundary Thrust ThrustThrustThrustStandby Standby Standby Th_Sega Th_Seg Th_SegIdle_Seg Idle_Seg Accum_NO_Thr Accum_Thr Accum_Thr Accum_Thr Thr_Boundary contained_by CP(Ips_Tvc) CP(Ips_Tvc) CP(Ips_Tvc) contained_by Th_Seg Based on slides by Dave Smith, NASA Ames 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] Based on slides by Dave Smith, NASA Ames 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 Based on slides by Dave Smith, NASA Ames Metric Time: Quantitative Temporal Constraint Networks (Dechter, Meiri, Pearl 91) ? 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 . . . Based on slides by Dave Smith, NASA Ames Temporal Constraint Satisfaction Problem (TCSP) < X i , T i ,T ij > ?X i continuous variables ?T i ,T ij interval constraints {I 1 , . . . ,I n } where I i = [a i ,b i ] –T i = (a i d X i d b i ) or . . . or (a i d X i d b i ) –T ij = (a 1 d X i -X j d b 1 ) or ... or (a n d X i -X j d b n ) [Dechter, Meiri, Pearl, aij89] 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] Based on slides by Dave Smith, NASA Ames Simple Temporal Networks (Dechter, Meiri, Pearl 91) Simple Temporal Networks: ? 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 . . . Sufficient to represent: ? most Allen relations ? simple metric constraints most Allen relations Can’t represent: ? Disjoint tokens Based on slides by Dave Smith, NASA Ames Simple Temporal Network ?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] Based on slides by Dave Smith, NASA Ames 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 Completed Plan Forms an STN Slide courtesy of Nicola Muscettola. Based on slides by Dave Smith, NASA Ames >@ >@ ! >@ >f@ >f@ >@ A Completed Plan Forms an STN Based on slides by Dave Smith, NASA Ames Outline ? Operational Planning for the Mars Exploration Rovers ? Review of Least Commitment Planning ? Constraint-based Interval Planning ? Temporal Constraint Networks ? Model-based Program Execution as Graph-based Temporal Planning Slide courtesy of Nicola Muscettola.