Temporal Planning in Space Brian C. William 16412J6834J based on "Handling Time February 23rd, 2004 Constraint-based Interval Planning, by David E Smith 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
Temporal Planning in Space 1 Brian C. Williams 16.412J/6.834J February 23rd, 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 Mini-TES Pancam Navcam Mossbauer spectrometer APXS Rock Abrasion Tool Microscopic Mission Objective EPL 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 Slide courtesy of Kanna rajan Mars Exploration Rover Surface Operations Scenario Day 2 Traverse Estimated During the Day Day 1 (20-50 meters) e Activities
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 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 OnBoard 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
Slide courtesy of Kanna Rajan One day in the life of a Mars rover 10111213141516181920212223012345678 Plannig t teeing p Downlink Assessment; Science Planning Sequence Build/Validati 「118202122;230 Courtesv. Jimm Erickson Slide courtesy of Kanna rajan 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 DSN/Telcon 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) Slide courtesy of Kanna Rajan. Slide courtesy of Kanna Rajan
Next Challenge: Mars Smart Lander (2009) 9 Mission Duration: 1000 days Total Traverse: 3000-69000 meters Meters/Day: 230-450 Technology Demonstration Science mission: 7 instruments, sub-surface science (2005) package(drill, radar), in-situ sample "lab Images courtesy of JPL 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
Next Challenge: Mars Smart Lander (2009) 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 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. • 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
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 Plannin Find: program of actions that achieves the objective
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 ractical"planning MDP POMDP planning planning under uncertainty
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 Inits Operators Goals Simple Spacecraft Problem Observation-1 pointing target instruments observation -2 calibrated bservation -3 Observation-4 Image courtesy of JPL
The Classical Representation Operators: Goals: Goal1 Goal2 Goal3 Op pre1 pre2 pre3 eff1 eff2 Inits: P1 P2 P3 P4 Simple Spacecraft Problem Observation-1 target instruments Observation-2 Observation-3 Observation-4 … calibrated pointing Image courtesy of JPL
Example Actions Goal c POCL Planning (SNLP, UCPOP Select an open condition °xmF 2. Choose an op that can achieve it Link to an existing instance Add a new instance pc-c卜c 3. Resolve threats dIm HaF c
Example I Im x c px pC Init Actions C c Ty ¬px py px IA Goal pC 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 IA F Im c pA IA F pC C Im IA F c pA pC C Im IA F c pA S TA ¬pC pC C Im IA F c pA S pC TA ¬pC pC C Im IA F c pA S pC
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 priorit time window target instruments duratio observation -2 Observation -3 Image courtesy of JPL Observation -4 Objective: maximize science return Based on slides by Dave Smith, NASA Ames
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
Complications Observation-1 angle between targets priority → turn duration time window instruments callbration targ Observation -2 target2 Image courtesy of JPL Observation-3 Observation -4 consumables fuel obj power maximize science return data storage cryogen 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 Based on slides by Dave Smith, NASA Ames
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