Principles of Autonomy and Decision Making 1 Brian C. Williams 16.410/16.413 December 10 th , 2003 Outline ? Objectives ? Agents and Their Building Blocks ? Principles for Building Agents: – Modeling Formalisms – Algorithmic Principles ? Building an Agent: The Mars Exploration Rover Course Objective 1: Principles of Agents 16.410/13: To learn the modeling and algorithmic building blocks for creating reasoning and learning agents: ? To formulate reasoning problems. ? To describe, analyze and demonstrate reasoning algorithms. ? To model and encode knowledge used by reasoning algorithms. Course Objective 2: Building Agents 16.413: To appreciate the challenges of building a state of the art autonomous explorer: ? To model and encode knowledge needed to solve a state of the art challenge. ? To work through the process of autonomy systems integration. ? To assess the promise, frustrations and challenges of using (b)leading art technologies. Outline ? Objectives ? Agents and Their Building Blocks ? Principles for Building Agents: – Modeling Formalisms – Algorithmic Principles ? Building an Agent: The Mars Exploration Rover Courtesy NASA/JPL-Caltech. http://www.jpl.nasa.gov. ``Our vision in NASA is to open the Space Frontier . . . We must establish a virtual presence, in space, on planets, in aircraft and spacecraft.’’ - Daniel S. Goldin, NASA Administrator, May 29, 1996 Mission-Oriented Agents Agent Building Blocks ? Activity Planning ? Execution/Monitoring Cassini Maps Titan ? 7 year cruise ? ~ 150 - 300 ground operators ?~ 1 billion $ ? 7 years to build 1. Engineering Agents ?150 million $ ?2 year build ? 0 ground ops Affordable Missions Courtesy NASA/JPL-Caltech. http://www.jpl.nasa.gov. Houston, we have a problem ... Image taken from NASA’s web site: http://www.nasa.gov. ? Quintuple fault occurs (three shorts, tank-line and pressure jacket burst, panel flies off) – Diagnosis. ? Mattingly works in ground simulator to identify new sequence handling severe power limitations. – Planning & Resource Allocation ? Mattingly identifies novel reconfiguration, exploiting LEM batteries for power. – Reconfiguration and Repair ? Swaggert & Lovell work on Apollo 13 emergency rig lithium hydroxide unit. – Execution Agent Building Blocks ? Activity Planning ? Execution/Monitoring ? Diagnosis ? Repair ? Scheduling ? Resource Allocation 2. Mobile Agents 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 Courtesy Kanna Rajan, NASA Ames. Used with permission. Cooperative Vehicle Planning Courtesy NASA/JPL-Caltech. http://www.jpl.nasa.gov. Agent Building Blocks ? Activity Planning ? Execution/Monitoring ? Diagnosis ? Repair ? Scheduling ? Resource Allocation ? Global Path Planning ? Task Assignment 3. Agile Agents Courtesy of Eric Feron. Used with permission. Agent Building Blocks ? Activity Planning ? Execution/Monitoring ? Diagnosis ? Repair ? Scheduling ? Resource Allocation ? Global Path Planning ? Task Assignment ? Trajectory Design ? Policy Construction Agent Paradigms ? Agent Environment Sensors Actions Percepts Effectors Figure adapted from Russell and Norvig. Model-based Agents En vir onment A gent Sensors Effectors What the world is like now What action I should do now What my actions do How the world evolves State World Model Figure adapted from Russell and Norvig. Reflexive Agents En vir onment A gent Sensors Effectors What the world is like now What action I should do now Condition- action rules Figure adapted from Russell and Norvig. Goal-Oriented Agents En vir onment A gent Sensors Effectors What the world is like now What it will be like if I do action A What action I should do now What my actions do Goals How the world evolves State Figure adapted from Russell and Norvig. Utility-Based Agents En vir onment A gent Sensors Effectors What the world is like now What it will be like if I do action A What action I should do now How happy I will be in such a state What my actions do Utility How the world evolves State Figure adapted from Russell and Norvig. 16.413 Project: Example of a Model-based Agent: ? Goal-directed ? First time correct ? projective ? reactive ? Commonsense models ? Heavily deductive Scripts component models Goals Titan Diagnosis & Repair Mission Description Kirk Executive Europa Planner/ Scheduler Mission-level actions & resources Outline ? Objective ? Agents and Their Building Blocks ? Principles for Building Agents: – Modeling Formalisms – Algorithmic Principles ? Building an Agent: The Mars Exploration Rover Building Blocks to Models ? Activity Planning ? Execution/Monitoring ? Diagnosis ?Repair ? Scheduling ? Resource Allocation ? Global Path Planning ? Task Assignment ? Trajectory Design ? Policy Construction Goal and Feasibility-based: ? State Space Search ? Rules, First Order Logic ? Strips Operators ? Constraint Satisfaction Problems ? Propositional Logic Utility-based: ? Weighted Graphs ? Linear Programs ? Mixed Integer Programs ? Markov Decision Processes Building Blocks from Models ? Activity Planning – Graphplan, SatPlan, Partial Order Planning ? Execution/Monitoring ? Diagnosis – Constraint Suspension ?Repair – Rule-based ? Scheduling – CSP-based ? Resource Allocation –LP-based ? Global Path Planning – Roadmap ? Task Assignment ? Trajectory Design –MILP ? Policy Construction –MDP – Reinforcement Learning Models to Core Algorithms Uninformed Search: ? Depth First, Breadth First ? Iterative Deepening. ? Backtrack Search ? Backtrack w Forward checking ? Conflict-directed Search Informed Search: ? Single Source Shortest Bath ? Best First Search (A*, Hill Climbing, …) ?Simplex ? Branch and Bound Goal and Feasibility-based: ? State Space Search ? Rules, First Order Logic ? Strips Operators ? Constraint Satisfaction ? Propositional Logic Utility-based: ? Weighted Graphs ? Linear Programs ? Mixed Integer Programs ? Markov Decision Processes Algorithms to Principles Deduction: ? Unification ? Unit Clause Resolution ? Arc Consistency. ? Gaussian Elimination Relaxation ? Value Iteration ? Reinforcement Learning Divide and Conquer ? Branching ? Sub-goaling ? Variable Splitting ? Dynamic Programming ? Uninformed & Informed Abstraction: ? Conflicts ? Bounding Goal and Feasibility-based: ? State Space Search ? Rules, First Order Logic ? Strips Operators ? Constraint Satisfaction ? Propositional Logic Utility-based: ? Weighted Graphs ? Linear Programs ? Mixed Integer Programs ? Markov Decision Processes Outline ? Objectives ? Agents and Their Building Blocks ? Principles for Building Agents: – Modeling Formalisms – Algorithmic Principles ? Building an Agent: The Mars Exploration Rover 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 Mini-TES Pancam Navcam Rock Abrasion Tool Microscopic Imager Mossbauer spectrometer APXS Courtesy NASA/JPL-Caltech. http://www.jpl.nasa.gov.