Brian C. Williams 16.410/16.413 September 3 rd , 2003 Introduction to Principles of Autonomy and Decision Making 1 Brian C. Williams 16.410/16.413 September 3 rd , 2003 Today’s Assignment ? ? Read Chapters 1 and 2 of AIMA – – “Artificial Intelligence: A Modern Approach” by Stuart Russell and Peter Norvig –2 nd Edition (not 1 st Edition!!) nd st – – AIMA is available at the Coop AIMA is available at the Coop 1 Outline ? ? The promise of autonomous explorers ? ? The challenge of autonomous explorers ? ? Agents great and small ? ? Course objective 1 (16.410/13): – – Principles for Building Agents ? ?C C ourse objective 2 (16.413): – B uilding an Agent: Agent: –B The Mars exploration rover (MER) project. 2 . Courtesy NASA/JPL-Caltech. http://www.jpl.nasa.gov A Image taken from NASA's website: http://www.nasa.gov Courtesy of Kanna Rajan. Frontier . . . spacecraft.’’ establish a virtual presence, in space, on planets, in aircraft and ``Our vision in NASA is to open the Space We must - Daniel S. Goldin, NASA Administrator, May 29, 1996 3 Motive: Follow the water …. ? to find evidence of past life on Mars. ? to study the forces that shaped Mars. ? to develop future life on Mars. Courtesy NASA/JPL-Caltech. http://www.jpl.nasa.gov Courtesy of Kanna Rajan. Mars Motive: Follow the water …. ? to find evidence of past life on Mars. ? to study the forces that shaped Mars. ? to develop future life on Mars. Courtesy U.S. Geological Survey. 4 Inner and Outer Planets Missions MESSENGER mission to Mercury MESSENGER ury Venus Sample Return Venus rn Comet Nucleus Sample Return Primitive Bodies Missions Pluto/Kuiper Express Europa Orbiter Europa Lander Neptune Orbiter Titan Explorer Cryobot & Hydrobot Motive: life underMotive: life under Europa? Courtesy NASA/JPL-Caltech. http://www.jpl.nasa.gov Courtesy of Kanna Rajan. 5 MIT SPHERES Image taken from NASA's website. http://www.nasa.gov. Adapted. Courtesy of Kanna Rajan. 6 Cooperative Exploration Distributed Planning Group, JPL Model-based Embedded and Robotic Systems Group, MIT Courtesy NASA/JPL-Caltech. http://www.jpl.nasa.gov Courtesy of Kanna Rajan. Outline ? ? The promise of autonomous explorers ? ? The challenge of autonomous explorers The challenge of autonomous explorers ? ? Agents great and small Agents great and small ? ? Course objective 1 (16.410/13): – – Principles for Building Agents ? ? Course objective 2 (16.413): Course objective 2 (16.413): – Building n Agent: Building an Agent: The Mars exploration rover (MER) project. 7 A Capable Robotic Explorer: Cassini ? 7 year cruise Faster, Better, Cheaper ? ~ 150 - 300 ground operators ?~ 1 billion $ ?150 million $ ? 7 years to ?2 year build build ? 0 ground ops Four launches in 7 months Mars Climate Orbiter: 12/11/98 /99 Stardust: 2/7/99 QuickSCAT: 6/19/98 Mars Polar Lander: 1/3 courtesy of JPL 8 Mars Polar Lander L Spacecraft require a good physical commonsense… Launch: 1/3/99 Traditional spacecraft commanding 2; 6; , Whats a better paradigm? GS,SITURN,490UA,BOTH,96-355/03:42:00.000; CMD,7GYON, 490UA412A4A,BOTH, 96-355/03:47:00:000, ON; CMD,7MODE, 490UA412A4B,BOTH, 96-355/03:47:02:000, INT; CMD,6SVPM, 490UA412A6A,BOTH, 96-355/03:48:30:000, CMD,7ALRT, 490UA412A4C,BOTH, 96-355/03:50:32:000, CMD,7SAFE, 490UA412A4D,BOTH, 96-355/03:52:00:000, UNSTOW; CMD,6ASSAN, 490UA412A6B,BOTH, 96-355/03:56:08:000, GV,153,IMM,231, GV,153; CMD,7VECT, 490UA412A4E,BOTH, 96-355/03:56:10.000, 0,191.5,6.5, 0.0,0.0,0.0, 96-350/ 00:00:00.000,MVR; SEB,SCTEST, 490UA412A23A,BOTH, 96-355/03:56:12.000 SYS1,NPERR; CMD,7TURN, 490UA412A4F,BOTH, 96-355/03:56:14.000, 1,MVR; MISC,NOTE, 490UA412A99A,, 96-355/04:00:00.000, ,START OF TURN;, CMD,7STAR, 490UA412A406A4A,BOTH 96-355/04:00:02.000, 7,1701, 278.813999,38.74; CMD,7STAR, 490UA412A406A4B,BOTH, 96-355/04:00:04.000, 8,350,120.455999, -39.8612; CMD,7STAR, 490UA412A406A4C,BOTH, 96-355/04:00:06.000, 9,875,114.162, 5.341; CMD,7STAR, 490UA412A406A4D,BOTH, 96-355/04:00:08.000, 10,159,27.239, 89.028999; CMD,7STAR, 490UA412A406A4E,BOTH, 96-355/04:00:10.000, 11,0,0.0,0.0; CMD,7STAR, 490UA412A406A4F,BOTH, 96-355/04:00:12.000, 21,0,0.0,0.0; 9 Outline ? ? The promise of autonomous explorers ? ? The challenge of autonomous explorers ? ? Agents great and small ? ? Course objective 1 (16.410/13): – – Principles for Building Agents ? ? Course objective 2 (16.413): – – Building an Agent: Agent: The Mars exploration rover (MER) project. Agents and Intelligence Adaoted from J. Malik, U.C. Berkeley 10 Reflex agents Adaoted from J. Malik, U.C. Berkeley Goal-oriented agent Adaoted from J. Malik, U.C. Berkeley 11 Utility-based agent Adaoted from J. Malik, U.C. Berkeley Outline ? ? The promise of autonomous explorers ? ? The challenge of autonomous explorers ? ? Agents great and small ? ? Course objective 1 (16.410/13): – – Principles for Building Agents ? ? Course objective 2 (16.413): – – Building an Agent: Agent: The Mars exploration rover (MER) project. 12 Course Objective 1: Course Objective 1: Principles of Agents 16.410/13: To learn the modeling and 16.410/13: To learn the modeling and algorithmic building blocks for creating algorithmic building blocks for creating reasoning, learning agents: ? ? To formulate reasoning problems. ? ? To describe, analyze and demonstrate o describe, analyze and demonstrate reasoning algorithms. ? ? To model and encode o model and encode knowledge used by knowledge used by reasoning algorithms. Agent Paradigms ? Extensive Reasoning ? Extensive Learning ? Extensive Optimization 13 Extensive Reasoning: Houston, we have a problem ... courtesy of NASA ? Quintuple fault occurs (three shorts, tank-line and pressure jacket burst, panel flies off). ? Mattingly works in ground simulator to identify new sequence handling severe power limitations. ? Mattingly identifies novel reconfiguration, exploiting LEM batteries for power. ? Swaggert & Lovell work on Apollo 13 emergency rig lithium hydroxide unit. Image taken from NASA's website: http://www.nasa.gov. Courtesy of Kanna Rajan. Example of a Model-based Agent: ? Goal-directed ? First time correct ? projective ? reactive ? Commonsense models ? Heavily deductive Scripts component models Goals Diagnosis & Repair Mission Manager Executive Planner/ Scheduler Remote Agent Mission-level actions & resources 14 Reasoning methods that Reasoning methods that support the creation of agents ? ? Rule-b ased systems – – Forwa rd chaining – – Goal -directed directed- ? ? Search and roadm ap path planning – – Blind Search Blind Search – – Inform ed Search – – Adversa rial (Game) Search ? ? Planning and Acting in the W orld ? ? Constraints and Scheduling ? ? Model-based Diagnosis ? ? Logic and Deduction Extensive Learning: TD-Gammon [Tesauro, 1995] TD-Gammon [Tesauro, 1995] Learns to play Backgammon Situations: ? Board configurations (10 20 ) Actions: ? Moves Rewards: – +100 if win – - 100 if lose – 0 for all other states ? Trained by playing 1.5 million games against self. ? Currently, roughly equal to best human player. t n s: ard s ) Actions: s Rewards: – +100 if win lose – all other states ? ned by f. 15 Learning methods that support Learning methods that support the creation of agents ? ? Learning through reinforcement earning through reinforcement ? ? Learning decision trees ? ? Neural net learning Extensive Optimization 16 Cooperative Path Planning: MILP Encoding: Fuel Equation Cooperative Path Planning: MILP Encoding: Fuel Equation min = J T = min 6 q’w i + 6 r’v i + p’w N min = J T i + i w i , v i w i , v i i=1 N-1 i=1 N-1 slack control vector weighting vectors slack state vector past-horizon terminal cost term total fuel calculated over all time instants i Cooperative Path Planning: MILP Encoding: Constraints ?s ij ij <= w ij , etc. ij State Space Constraints ? ? s i i +1 = As i i + Bu + i i State Evolution Equation -x ?x i i <= x min + Mt i1 n i i <= -x + Mt i2max -y y i i <= y min + Mt i3 n Obstacle Avoidance i i <= -y max + Mt i4 (for all time i) 6 t ik <= 3 (t introduce IP element) ? Sim ilar equation for Collision Avoidance (for all pairs of voidance (for all pairs of vehicles) 17 Outline ? ?T T he promise of autonomous explorers ? ?T T he challenge of autonomous explorers ? ?A A gents great and small ? ?C C ourse objective 1 (16.410/13): – – Principles for Building Agents ? ?C C ourse objective 2 (16.413): – –B B uilding an Agent: Agent: The Mars exploration rover (MER) project. Optimization methods that Optimization methods that support the creation of agents Modeling Frameworks: – Markov Decision Processes Markov Decision Processes Mixed Integer Linear Programming – – Mixed Integer Linear Programm Solution Methods: – Dyna Dynamic Programming –Simplex – Simplex – Branch and Bound Branch and Bound 18 Course Objective 2: Course Objective 2: Building Agents 16.413: To appreciate the challenges of building a 16.413: To appreciate the challenges of building a state of the art autonomous explorer: ? ? To model and encode knowledge needed to solve To m a state of the art challenge. ? ? To work through the To work through the process of autonomy systems process of autonomy system integration. ? ? To assess the promise, frustrations and challenges To assess the prom of using (b)leading art technologies. 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 ? Take 1-3 panoramas both with Pancam and mini-TES ? Take 5-15 daytime and 1-3 nightime sky observations with mini-TES Mission Objectives: ate on Mars. alyze a total of 6-12 targets ts il ters per rover as both with Pancam ni-TES ni-TES Mini-TES Pancam Navcam Rock Abrasion Tool Microscopic Imager Mossbauer spectrometer APXS Courtesy NASA/JPL-Caltech. http://www.jpl.nasa.gov. Courtesy of Kanna Rajan. 19 Surface Operations Scenario Day 4 Day 1 Day 2 Board Navigation Changes, as needed Day 3 Mars Exploration Rover Target During the Day Science Activities Long-Distance Traverse (<20-50 meters) Initial Position; Followed by “Close Approach” During the Day Autonomous On- Day 2 Traverse Estimated Error Circle Science Prep (if Required) Day 2 Traverse Estimated Error Circle Courtesy of Kanna Rajan, NASA Ames. Used with permission. 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 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 Science Planning Sequence Build/Validation Uplink Downlink Product Generation... Courtesy: Jim Erickson Downlink Assessment Courtesy of Kanna Rajan, NASA Ames. Used with permission. 20 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) Courtesy of Kanna Rajan, NASA Ames. Used with permission. Course Challenge ? What would it be like to operate MER if it was fully autonomous? Course project: ? Demonstrate an autonomous MER mission in simulation, and in the MIT rover testbed. was fully autonomous? in simulation, and in the MIT rover testbed. 21 Next Challenge: Mars Smart Lander (2009) (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). Courtesy NASA/JPL-Caltech. http://www.jpl.nasa.gov. Courtesy of Kanna Rajan. 22