WIXLIB

Introduction toAutomated TaskPlanningJonas KvarnströmAutomated Planning and Diagnosis GroupArtificial Intelligence and Integrated Computer Systems (AIICS) / IDA

What is Planning?Planning is thinking aheadNot just reacting to what happens!34Thinking 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: ShakeyShakey Used the STRIPS planner Stanford Research InstituteProblem Solver One of the first planners (1969)jonkv@idajonkv@ida

Schindler Miconic 10 elevatorsMiconic 10 Elevators People enter their destinationbefore they board an elevator Many elevators, many floors The goal: For everyone to be at their destination The plan tells us:Which elevators should go to whichfloors, in which order? The gain: Less time to wait for an elevator!Robots bending sheet metalSheet Metal Bending Goal: Optimized operation saves a lot of time money! Constraints:65jonkv@idaBend a flat sheet to a specific shapeThe piece must not collide with anything when moved!(Geometric reasoning required)jonkv@ida

Earth Observing-1 MissionNASA Earth Observing-1 Mission Satellite in low earth orbit Can only communicate 8 x 10 minutes/day Operates for long periods without supervision78 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 vehiclesUnmanned Aerial Vehicles Multiple agents to coordinate Actions executed concurrentlyjonkv@idajonkv@ida

UAV 1: Photogrammetry Photograph buildings, to generate 3D modelsUAV 2: Traffic Monitoring Monitor traffic / find possible routes for emergency vehicles109jonkv@idajonkv@ida

UAV 3: Finding Forest Fires Patrol large areas searching for forest fires, day after day after day UAV 4: Emergency Services Logistics Assist in emergency situations Deliver packages of food, medicine, water1211jonkv@idajonkv@ida

Can’t we just solve these problems ourselves?Why Planning? Manual planning can be boring and inefficient Who wants to spend all day guiding elevators? Automated planning may create higher quality plans13 Software can systematically optimize, can investigate millions of alternatives 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 radioDomain-Specific vs.Domain-Independent Planningjonkv@ida

How do you create a photogrammetry plan? Goal: To take pictures of buildings Multiple UAVs available15Let’s say we are interested in the photogrammetry domainIntroduction 16Domain-specific planner: Created for a particular domainDomain-Specific Planning Input: A map containing buildings Everything else is implicit,since the planner already knowswhat actions are available, etc (hardcoded!) Implementation:PG Plan Calculate suitable UAV positions Call a Travelling Salesman Problem solver Generate flight commandsPG ProblemPG-specificPlannerSounds simple, and can be very efficient! But jonkv@idajonkv@ida

Specialization means less flexibility! What if Domain-Specific Planning you want to deliver a couple of crates at the same time? Generalize input you have to consider refueling? Different algorithm! you have two UAVs and a UGV (ground vehicle)? Differentalgorithm!PlanSatelliteproblem nnerw/ fuelPG DeliveryPlanner you want to survey an area (send a video feed of the ground)? you have dynamic no-fly-zones (”don’t fly there at 15:00-16:00”)?We want a generic planning system!Domain-Independent Planning Photogrammetryproblem instanceGeneralPlannerSatelliteDomain Capable of taking a high-level description of any problem domainand then solving problems within the domain!UAVDomain A single planner Improvements to the planner all domains benefit 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 prototypingjonkv@idajonkv@ida

What is Common?What is common to all of these problems?2019jonkv@ida takeoff(uav) photograph(uav, building) Can only be executed if we can see the building now the UAV is in the air now we have a picture of the buildingActions modify properties (simplified!) We should have a picture of each buildingGoals can be described as desired properties Location of a card, whether we have a picture of a building or not, We are generally interested in properties of these objects Buildings, cards, aircraft, switches, people, The world contains various types of objectsThis is Common! jonkv@ida

In the Emergency Services Logistics domain:Example 1 1. What objects exist? Helicopters!heli { surv1, surv2, ,cargo1, cargo2, } Boxes!box { box1, box2, } Locations!loc { basestation,person1, person2, ,depot1, depot2, } Let’s generalize:Both helicopters and boxesare objects as well.Example 2 2. What properties can different types of objects have?(Defined using state variables) 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)2221jonkv@idajonkv@ida

Example 323L224Situationwe want toachieveSituationright now 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), Every helicopter is at a certain location:at(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), 4. What can we do about it? Actions!Example 4 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 winchjonkv@idajonkv@ida

Domain-Independent PlanningInput 1: Planning domainEvery UAV has a maxSpeed, There are UAVs, boxes Properties:Definition of fly, pickup, Object Types:Actions:Box b1 at location l1, Box locations, Current UAVs are {UAV1,UAV2}Input 2: Problem instanceObjects:Initial State:Goal:But what language should we use?25jonkv@ida

Desirable properties of a domain-independent planner:Desirable Properties 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 specify2728Many of these properties are in direct conflict!Classical planning uses a common set of constraints This implies constraining the expressivity of the plannerand its input language!For efficiency, planners generally exploit domain structureClassical Planning 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@idajonkv@ida

What you can do:YouBlocks World Pick up a blockBWhat you knowAC 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 it Which actions will achieve your goals?2930Your greatest desireABCPDDL: Lisp-like language, expressions in parenthesesPDDL: Domain and Problem Definition Every domain is named,associated with explicit list of expressivity requirements (define (domain blocksworld)(:requirements:adl;; Conditional effects, quantification, :equality;; Use of “ ” );; Remaining domain information goes here!) Problem instance has a name, belongs to a domain (define (problem MyThreeBlockProblem)(:domain blocksworld) )Colon before many keywords,in order to avoid collisionswhen new keywords are addedjonkv@idajonkv@ida

In classical planning, there is a finite set of objects1: Objects A 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) )CClassical planning: World modeled using finite states2: Finite States B 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:)CA3231 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)) jonkv@idaBjonkv@ida

2b: State Example Three different statesin the Blocks World Can be described graphically Can be described in text(the following 3 slides!)ACCABCBABWe assume complete information about the initial state3: Complete Initial Information All state variables are given values in the problem instance BW: on(A,B), on(B,Table), on(C,Table) etc.C3433jonkv@idaBAjonkv@ida

How do we completely specify the initial BW state?3b: Initial State in PDDL (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!B 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)AC3c: 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.B PDDL is for planners that cannot handle unknown initial information,so for convenience,an atom that is not mentioned is by definition falseAC3635jonkv@idajonkv@ida

A set of single-step operators defines what you can do4: Operators and Actions Part of the domain description Many ways of modeling any domain! One example:37BAB38BBA put(A,B) CAC put(A,B) CA “put” should take a block from where it is, and put it on another block Each operator has parameters: put(x,y) Instantiated into actions: put(A,B), put(A,C), Each operator has a precondition “There must be no other block on top of x”, Each operator has effects Afterwards, x will be on top of yEach action is executed as a single step4b: Operators and Actions If the precondition holds in the current state: The action can be executed A single new state results, where the effects hold. UAV domain: Flying from (100,100) to (300,300)is basically modeled as “teleporting”in a single step We don’t model the factthat the UAV moves throughintervening locations Sufficient for sequential plansCjonkv@idajonkv@ida