Planning Approaches in Artificial Intelligence

planning in artificial intelligence example and planning in artificial intelligence tutorial and basic representations for planning in artificial intelligence
JaydenGibbs Profile Pic
JaydenGibbs,United States,Teacher
Published Date:19-07-2017
Your Website URL(Optional)
Comment
Automated Planning Introduction to Planning Jonas Kvarnström Automated Planning Group Department of Computer and Information Science Linköping University jonas.kvarnstromliu.se – 2017One way of defining planning: Using knowledge about the world, including possible actions and their results, to decide what to do and when in order to achieve an objective, before you actually start doing it4 4 Towers of Hanoi Some applications are simple, well-structured, almost toy problems Simple structure Single agent acting Possible actions Objective  Move topmost disk from x to y,  All disks on the third peg, without placing larger disks in order of increasing size on smaller disks jonkvi jonkvida da5 5 Shakey  Classical robot example: Shakey (1969)  Available actions: ▪ Moving to another location ▪ Turning light switches on and off ▪ Opening and closing doors ▪ Pushing movable objects around ▪ …  Goals: ▪ Be in room 4 with objects A,B,C ▪ jonkvi jonkvida da6 6 Miconic 10 Elevators  Schindler system  Tall buildings, multiple elevators  Enter destination before you board  System creates a plan: ▪ Which elevator goes to which floor ▪ In which order  Saves time ▪ 3 elevators could serve as much traffic as 5 elevators with earlier algorithms jonkvi jonkvida da7 7 Earth and Space On-board planning to view interesting natural events: http://ase.jpl.nasa.gov/ SIADEX – plan for firefighting Limited resources Plan execution is dangerous NASA Mapgen / Mars Rovers Primary platform for creating daily activity plans for Spirit, Opportunity Mixed-initiative tool: Human in the loop jonkvi jonkvida da8 8 Why should Computers Plan?  And why should computers create plans?  Manual planning can be boring and inefficient  Automated planning may create higher quality plans ▪ Software can systematically optimize  Automated planning can be applied where the agent is ▪ Satellites cannot always communicate with ground operators ▪ Spacecraft or robots on other planets may be hours away by radio jonkvi jonkvida da10 10 Context: Unmanned Aerial Vehicles  A modern context for planning:  Autonomous Unmanned Aerial Vehicles (UAVs) jonkvi jonkvida daUsing knowledge about the world, including possible actions and their results, to decide what to do and when in order to achieve an objective, before you actually start doing it12 12 Actions for UAVs  General knowledge about the world  of UAVs and objects  levels, …  Available actions:  ▪ Before: The UAV must be on the ground Informal ▪ Result: The UAV is flying  Incomplete ▪ Before: Must have sufficient fuel ▪ Result: Will end up at the indicated point More later…       jonkvi jonkvida daUsing knowledge about the world, including possible actions and their results, to decide what to do and when in order to achieve an objective, before you actually start doing it14 14 UAV Objective 1: Emergency Services Logistics  Assist in emergency situations ▪ Deliver packages of food, medicine, water jonkvi jonkvida da15 15 UAV Objective 2: Photogrammetry  A specific photogrammetry problem with a single UAV:  Photograph buildings – generate realistic 3D models  Problem: Find best way of taking pictures ▪ From specificed locations ▪ In the specified directions jonkvi jonkvida daUsing knowledge about the world, including possible actions and their results, to decide what to do and when in order to achieve an objective, before you actually start doing it17 17 Method 0: Reactive + Stupid  Method 0: Let’s be reactive and stupid  Reactive: No planning, don’t explicitly consider the future  Very fast decision + execution algorithm: ←  Somewhat suboptimal for flight… jonkvi jonkvida da18 18 Method 1: Reactive + Greedy  Method 1: Let’s be reactive and greedy  Greedy heuristic chooses next location ▪ ”Least expensive extension to the plan” Start here;  generate actions ← incrementally  Seems good for this task; not optimal ▪ Least expensive right now, more expensive in the long run  For many other tasks: Still really bad Often, not thinking ahead means you can’t even solve the problem (Fly too far  run out of fuel; crack an egg  can’t uncrack it; …) Run out of fuel here? jonkvi jonkvida daUsing knowledge about the world, including possible actions and their results, to decide what to do and when in order to achieve an objective, before you actually start doing it20 20 Method 2: Think ahead  Method 2: Let’s think ahead  First create a complete plan, considering multiple choices  Keeping track of jonkvi jonkvida da