WIXLIB

Introduction toAutomated TaskPlanningJonas KvarnströmAutomated Planning and Diagnosis Group3Shakey Planning is thinking aheadNot just reacting to what happens!Thinking about possible actions and their effects,formulating a complete plan that describes what to do and when,in order to achieve a goal so when do we want computers to do that?Classical example: Shakey Used the STRIPS planner Stanford Research InstituteProblem Solver One of the first planners (1969)4jonkv@idaWhat is Planning?jonkv@idaArtificial Intelligence and Integrated Computer Systems (AIICS) / IDA

Schindler Miconic 10 elevatorsSheet Metal Bending 6jonkv@ida5jonkv@idaMiconic 10 ElevatorsRobots bending sheet metal People enter their destination Goal:before they board an elevator Many elevators, many floorsBend a flat sheet to a specific shapeThe piece must not collide with anything when moved!(Geometric reasoning required) Constraints: The goal: For everyone to be at their destination Optimized operation saves a lot of time money! The plan tells us:Which elevators should go to whichfloors, in which order? 7Earth Observing-1 Mission Satellite in low earth orbit Can only communicate 8 x 10 minutes/day Operates for long periods without supervision CASPER software:Continuous Activity Scheduling, Planning, Execution and Replanning Dramatically increases science returns Interesting events are analyzed(volcanic eruptions, ) Targets to view are planneddepending on previous observations Plans downlink activities:Limited bandwidth http://ase.jpl.nasa.gov/Unmanned Aerial Vehicles Unmanned aerial vehicles Multiple agents to coordinate Actions executed concurrently8jonkv@idaNASA Earth Observing-1 Missionjonkv@ida The gain: Less time to wait for an elevator!

Patrol large areas searching for forest fires, day after day after day jonkv@idaUAV 3: Finding Forest Fires1012 Monitor traffic / find possible routes for emergency vehicles11jonkv@ida Photograph buildings, to generate 3D modelsUAV 2: Traffic Monitoringjonkv@ida9jonkv@idaUAV 1: PhotogrammetryUAV 4: Emergency Services Logistics Assist in emergency situations Deliver packages of food, medicine, water

13jonkv@idaWhy Planning?Can’t we just solve these problems ourselves? Manual planning can be boring and inefficient Who wants to spend all day guiding elevators?Domain-Specific vs.Domain-Independent Planning Automated planning may create higher quality plans Software can systematically optimize, can investigate millions of alternatives 15Let’s say we are interested in the photogrammetry domain Multiple UAVs available Goal: To take pictures of buildingsDomain-Specific Planning Domain-specific planner: Created for a particular domain Input: A map containing buildings Everything else is implicit,since the planner already knowswhat actions are available, etc (hardcoded!) Implementation: Calculate suitable UAV positions Call a Travelling Salesman Problem solver Generate flight commandsPG Problem 16PG-specificPlannerPG PlanHow do you create a photogrammetry plan?Sounds simple, and can be very efficient! But jonkv@idaIntroductionjonkv@ida 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

Specialization means less flexibility! What if you want to deliver a couple of crates at the same time? Generalize input Domain-Independent Planning 18jonkv@ida17jonkv@idaDomain-Specific PlanningWe want a generic planning system! Capable of taking a high-level description of any problem domainand then solving problems within the domain!PG DeliveryPlanner you have to consider refueling? Different algorithm! you have two UAVs and a UGV (ground vehicle)? Differentalgorithm!Photogrammetryproblem instancePGPlannerw/ fuelUAVDomainGeneralPlannerSatelliteproblem instancePlanSatelliteDomainGeneralPlannerPlan A single planner Improvements to the planner all domains benefitMultiTSPplanner High-level domain and problem definitions Easier to specify these than to write specialized algorithms Easier to change than a hard-coded optimized implementation Also useful for rapid prototyping you want to survey an area (send a video feed of the ground)?What is common to all of these problems?19This is Common! 20The world contains various types of objects Buildings, cards, aircraft, switches, people, We are generally interested in properties of these objects Location of a card, whether we have a picture of a building or not, Goals can be described as desired properties We should have a picture of each building Actions modify properties (simplified!) takeoff(uav) now the UAV is in the air photograph(uav, building) now we have a picture of the building Can only be executed if we can see the buildingjonkv@idaWhat is Common?jonkv@ida you have dynamic no-fly-zones (”don’t fly there at 15:00-16:00”)?

22jonkv@idaExample 224jonkv@ida 21jonkv@idaExample 1 2. What properties can different types of objects have?In the Emergency Services Logistics domain:(Defined using state variables) 1. What objects exist? Helicopters!heli { surv1, surv2, ,cargo1, cargo2, } An object is or isn’t at a certain location:at(object, loc)A helicopter is or isn’t at a certain location: at(heli, loc)A helicopter is or isn’t carrying a certain box: carrying(heli, box) Boxes!box { box1, box2, } Locations!loc { basestation,person1, person2, ,depot1, depot2, }Example 323 3. What properties do the objects of the current problem have now? Every box is at a certain location:at(box1, depot1),at(box2, depot1), Situation Every helicopter is at a certain location:rightnowat(surv1, basestation),at(surv2, person1), Some helicopters are carrying boxes:carrying(cargo1, box4) 4. What properties should they have?This is our goal! at(box1, person1),at(box2, person2), Situationwe want toachievejonkv@ida Let’s generalize:Both helicopters and boxesare objects as well.Example 4 4. What can we do about it? Actions! Example: fly(heli, loc1, loc2) Preconditions:at(heli, loc1)loc2 is free – no other helicopter thereL1fuel(heli) dist(loc1, loc2) * fuelUsage(heli) Effects:at(heli, loc1) is no longer trueat(heli, loc2) is true insteadfuel(heli) decreases by dist(loc1, loc2) * fuelUsage(heli) Time requirements:distance(loc1, loc2) / speed(heli) Take off / land Hover at the current location Position the camera at angle θ Take a visual picture / Take an infrared picture Lift a package using a winch / Deliver a package using winchL2

25jonkv@ida27jonkv@idaDomain-Independent PlanningInput 1: Planning domainObject Types:There are UAVs, boxes Properties:Every UAV has a maxSpeed, Actions:Definition of fly, pickup, Input 2: Problem instanceObjects:Current UAVs are {UAV1,UAV2}Initial State:Goal:Box locations, Box b1 at location l1, Desirable Properties Desirable properties of a domain-independent planner:Classical Planning Should be as general as possible Handle a wide variety of domains Should be as efficient as possible Generate plans quickly Should generate plans of the highest quality Fewer actions, lower cost, faster to execute, Should support the user as much as possible Provide useful high-level structures such as actionsthat a user can easily specifyMany of these properties are in direct conflict!For efficiency, planners generally exploit domain structure This implies constraining the expressivity of the plannerand its input language! 28Classical planning uses a common set of constraints Sometimes called "STRIPS planning" Demonstrated using a simple domain: The Blocks World Also introduces PDDL, the Planning Domain Definition Language General language Subsets are supported by most modern plannersjonkv@idaBut what language should we use?

What you know Your greatest desireC associated with explicit list of expressivity requirements (define (domain blocksworld)(:requirements:adl;; Conditional effects, quantification, :equality;; Use of “ ” );; Remaining domain information goes here!)BBPDDL: Lisp-like language, expressions in parentheses Every domain is named,AACWhat you can do: Problem instance has a name, belongs to a domain (define (problem MyThreeBlockProblem)(:domain blocksworld) ) Pick up a block unless something is on top of it Put a block that you’re holding on the table (space for all blocks) on another block,unless something is on top of itColon before many keywords,in order to avoid collisionswhen new keywords are added1: Objects31In classical planning, there is a finite set of objects32Classical planning: World modeled using finite states A finite set of state variables (predicates or non-boolean fluents),with values from a finite domain A finite (but gigantic!) set of possible states of the world Each state gives every state variable a specific value Many ways to model any domain! One example for blocks world: We must know if a block is on something else, or not We must know whether an object is the table,which we modeled as a ”special” block (define (domain blocksworld)Variables are(:requirements :adl )prefixed with “?”(:predicates (on ?X ?Y) (istable ?X)) )AC2: Finite States Objects are generally declared in the problem instance Different objects in different instances! (define (problem MyThreeBlockProblem)(:domain blocksworld)(:objects A B C) ) We can choose to model the table as a special block Always present in all instances defined in the domain (define (domain blocksworld)(:requirements :adl )(:constants Table) )jonkv@ida Which actions will achieve your goals? 30jonkv@idaPDDL: Domain and Problem DefinitionABCBjonkv@idaYou29jonkv@idaBlocks World

Three different statesin the Blocks WorldA Can be described graphicallyC3: Complete Initial Information 34jonkv@ida33jonkv@ida2b: State ExampleWe assume complete information about the initial state All state variables are given values in the problem instance BW: on(A,B), on(B,Table), on(C,Table) etc.BA Can be described in text(the following 3 slides!)CBACBAB How do we completely specify the initial BW state? (and(not (on A A)) (not (on A B)) (on A C) (not (on A Table)(not (on B A)) (not (on B B)) (not (on B C)) (on B Table)(not (on C A)) (not (on C B)) (not (on C C)) (on C Table)(not (on Table A)) (not (on Table B))(not (on Table C)) (not (on Table Table))(not (istable A)) (not (istable B)) (not (istable C))(istable Table)) Observation: Given complete info, most facts are false! A block can only be on one other block:Given any ?x, at most one instance of (on ?x ?y) is true(Given 1000 blocks, ?x is on 1, not on 999)AC353c: Conventions for Initial States Convention: Only specify what is true in the initial state (define (problem MyThreeBlockProblem)(:domain blocksworld)(:objects A B C)(:init (on A C) (on C Table) (on B Table) (istable Table)) ) This is a shorthand notation, and is only used in :init. PDDL is for planners that cannot handle unknown initial information,so for convenience,an atom that is not mentioned is by definition falseABCB36jonkv@ida3b: Initial State in PDDLjonkv@idaC