Introduction

Views:
 
Category: Education
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

Automated Planning: 

Automated Planning Introduction and Overview

Literature: 

Literature Malik Ghallab, Dana Nau, and Paolo Traverso. Automated Planning – Theory and Practice, chapter 1. Elsevier/Morgan Kaufmann, 2004. Qiang Yang. Intelligent Planning – A Decomposition and Abstraction Based Approach. Springer, 1997. James Allen, James Hendler, Austin Tate (eds). Readings in Planning. Morgan Kaufmann, 1990.

Overview: 

Overview What is AI Planning? A Conceptual Model for Planning Restricting Assumptions A Running Example: Dock-Worker Robots

Human Planning and Acting: 

Human Planning and Acting acting without (explicit) planning: when purpose is immediate when performing well-trained behaviours when course of action can be freely adapted acting after planning: when addressing a new situation when tasks are complex when the environment imposes high risk/cost when collaborating with others humans plan only when strictly necessary

Defining AI Planning: 

Defining AI Planning planning: explicit deliberation process that chooses and organizes actions by anticipating their outcomes aims at achieving some pre-stated objectives AI planning: computational study of this deliberation process

Why Study Planning Computationally?: 

Why Study Planning Computationally? for designing information processing tools that give access to affordable and efficient planning resources planning is an important component of rational behaviour as part of the study and engineering of autonomous intelligent machines

Domain-Specific Planning: 

Domain-Specific Planning domain-specific planning: use specific representations and techniques adapted to each problem important domains that justify specific algorithms: path and motion planning perception planning manipulation planning communication planning problems with domain-specific planning: commonalities to all forms of planning are not addressed more costly to address each domain anew no good for study and design of autonomous intelligent machines

Domain-Independent Planning: 

Domain-Independent Planning generic action models used: with time constraints only: project planning with time and resource constraints (and optimization criteria): scheduling with time and resource constraints, applicability conditions, and effects on world state: plan synthesis domain-independent planning complements domain-specific planning

Overview: 

Overview What is AI Planning? A Conceptual Model for Planning Restricting Assumptions A Running Example: Dock-Worker Robots

Why a Conceptual Model?: 

Why a Conceptual Model? conceptual model: theoretical device for describing the elements of a problem good for: explaining basic concepts clarifying assumptions analyzing requirements proving semantic properties not good for: efficient algorithms and computational concerns

Conceptual Model for Planning: State-Transition Systems: 

Conceptual Model for Planning: State-Transition Systems A state-transition system is a 4-tuple Σ = (S,A,E,γ), where: S={s1,s2,…} is a finite or recursively enumerable set of states; A={a1,a2,…} is a finite or recursively enumerable set of actions; E={e1,e2,…} is a finite or recursively enumerable set of events; and γ: S×A×E→2S is a state transition function.    

State-Transition Systems as Graphs: 

State-Transition Systems as Graphs A state-transition system Σ = (S,A,E,γ) can be represented by a directed labelled graph G = (NG,EG) where: the nodes correspond to the states in S, i.e. NG=S; and there is an arc from s to s for s, sNG with label (a,e) for aA, eE, i.e. (s,(a,e),s’)EG, if and only if sγ(s,a,e).

State-Transition Systems: Graph Example: 

State-Transition Systems: Graph Example pallet cont. pallet cont. pallet cont. pallet cont. pallet cont. pallet cont. take put move1 move2 move2 move1 take put load unload move2 move1

State-Transition Systems: Abbreviations: 

State-Transition Systems: Abbreviations the neutral event (written ε) for transitions that are due only to actions the neutral action (written no-op) for transitions that are due only to events for a state-transition system Σ = (S,A,E,γ) we write: γ(s,a) for sS, aA, as shorthand for γ(s,a,ε) γ(s,e) for sS, eE, as shorthand for γ(s,no-op,e) in the graph the arc labels can be abbreviated to a for (a,ε) and e for (no-op,e)

Actions vs. Events: 

Actions vs. Events actions: transitions that are controlled by the plan executor if aA and γ(s,a,ε)   then a is applicable to state s applying a in s will take the system to some state sγ(s,a) events: transitions that are contingent (correspond to the internal dynamics of the system) if eE and γ(s,no-op,e)   then e may possibly occur in state s the occurrence of e in s will take the system to some state sγ(s,e)

Objectives and Plans: 

Objectives and Plans plan: a structure that gives appropriate actions to apply in order to achieve some objective when starting from a given state types of objective: goal state sg or set of goal states Sg satisfy some conditions over the sequence of states followed optimize utility function attached to states task to be performed

Planning and Plan Execution: 

Planning and Plan Execution planner: given: description of Σ, initial state, objective generate: plan that achieves objective controller: given: plan, current state (observation function: η:S→O) generate: action state-transition system: evolves as actions are executed and events occur Planner Controller System Σ Initial State Objectives Description of Σ Events Plan Actions Observations

Dynamic Planning: 

Dynamic Planning problem: real world differs from model described by Σ more realistic model: interleaved planning and execution plan supervision plan revision re-planning dynamic planning: closed loop between planner and controller execution status Planner Controller System Σ Initial State Objectives Description of Σ Events Plans Actions Observations Execution Status

Overview: 

Overview What is AI Planning? A Conceptual Model for Planning Restricting Assumptions A Running Example: Dock-Worker Robots

A0: Finite Σ: 

A0: Finite Σ Assumption A0 system Σ has a finite set of states Relaxing A0 why? to describe actions that construct or bring new objects into the world to handle numerical state variables issues: decidability and termination of planners

A1: Fully Observable Σ: 

A1: Fully Observable Σ Assumption A1 system Σ is fully observable, i.e. η is the identity function Relaxing A1 why? to handle states in which not every aspect is or can be known issues: if η(s)=o, η-1(o) usually more than one state (ambiguity) determining the successor state

A2: Deterministic Σ: 

A2: Deterministic Σ Assumption A2 system Σ is deterministic, i.e. for all sS, uAE: |γ(s,u)|1 short form: s= γ(s,u) means γ(s,u)={s} Relaxing A2 why? to plan with actions that may have multiple alternative outcomes issues: controller has to observe actual outcomes of actions solution plan may include conditional and iterative constructs

A3: Static Σ: 

A3: Static Σ Assumption A3 system Σ is static, i.e. E= short form: Σ = (S,A,γ) for Σ = (S,A,,γ) Relaxing A3 why? to model a world in which events can occur issues: world becomes nondeterministic from the point of view of the planner (same issues)

A4: Restricted Goals: 

A4: Restricted Goals Assumption A4 the planner handles only restricted goals that are given as an explicit goal state sg or set of goal states Sg Relaxing A4 why? to handle constraints on states and plans, utility functions, or tasks issues: representation and reasoning over constraints, utility, and tasks

A5: Sequential Plans: 

A5: Sequential Plans Assumption A5 a solution plan is a linearly ordered finite sequence of actions Relaxing A5 why? to handle dynamic systems (see A3: static Σ) to create different types of plans issues: must not shift problem to the controller reasoning about (more complex) data structures

A6: Implicit Time: 

A6: Implicit Time Assumption A6 actions and events have no duration in state transition systems Relaxing A6 why? to handle action duration, concurrency, and deadlines issues: representation of and reasoning about time controller must wait for effects of actions to occur

A7: Offline Planning: 

A7: Offline Planning Assumption A7 planner is not concerned with changes of Σ while it is planning Relaxing A7 why? to drive a system towards some objectives issues: check whether the current plan remains valid if needed, revise current plan or re-plan

The Restricted Model: 

The Restricted Model restricted model: make assumptions A0-A7 Given a planning problem P=(Σ,si,Sg) where Σ = (S,A,γ) is a state transition system, siS is the initial state, and Sg  S is a set of goal states, find a sequence of actions 〈a1,a2,…,ak〉 corresponding to a sequence of state transitions 〈si,s1,…,sk〉 such that s1= γ(si,a1), s2= γ(s1,a2),…, sk= γ(sk-1,ak), and skSg.

Overview: 

Overview What is AI Planning? A Conceptual Model for Planning Restricting Assumptions A Running Example: Dock-Worker Robots

The Dock-Worker Robots (DWR) Domain: 

The Dock-Worker Robots (DWR) Domain aim: have one example to illustrate planning procedures and techniques informal description: generalization of earlier example (state transition graph) harbour with several locations (docks), docked ships, storage areas for containers, and parking areas for trucks and trains cranes to load and unload ships etc., and robot carts to move containers around

Objects in the DWR Domain: 

Objects in the DWR Domain locations {loc1, loc2, …}: storage area, dock, docked ship, or parking or passing area robots {robot1, robot2, …}: container carrier carts for one container can move between adjacent locations cranes {crane1, crane2, …}: belongs to a single location can move containers between robots and piles at same location piles {pile1, pile2, …}: attached to a single location pallet at the bottom, possibly with containers stacked on top of it containers {cont1, cont2, …}: stacked in some pile on some pallet, loaded onto robot, or held by crane pallet: at the bottom of a pile

Topology in the DWR Domain: 

Topology in the DWR Domain adjacent(l,l): location l is adjacent to location l attached(p,l): pile p is attached to location l belong(k,l): crane k belongs to location l topology does not change over time!

Relations in the DWR Domain (1): 

Relations in the DWR Domain (1) occupied(l): location l is currently occupied by a robot at(r,l): robot r is currently at location l loaded(r,c): robot r is currently loaded with container c unloaded(r): robot r is currently not loaded with a container

Relations in the DWR Domain (2): 

Relations in the DWR Domain (2) holding(k,c): crane k is currently holding container c empty(k): crane k is currently not holding a container in(c,p): container c is currently in pile p on(c,c): container c is currently on container/pallet c top(c,p): container/pallet c is currently at the top of pile p

Actions in the DWR Domain: 

Actions in the DWR Domain move robot r from location l to some adjacent and unoccupied location l’ take container c with empty crane k from the top of pile p, all located at the same location l put down container c held by crane k on top of pile p, all located at location l load container c held by crane k onto unloaded robot r, all located at location l unload container c with empty crane k from loaded robot r, all located at location l

Overview: 

Overview What is AI Planning? A Conceptual Model for Planning Restricting Assumptions A Running Example: Dock-Worker Robots

authorStream Live Help