Automated Planning

Planning Definition

[a representation] of future behavior … usually a set of actions, with temporal and other constraints on them, for execution by some agent or agents.

– Austin Tate, MIT Encyclopedia of the Cognitive Sciences, 1999

Planning is the task of finding a procedural course of action for a declaratively described system to reach its goals while optimizing overall performance measures.

– IBM Research

Automated planners find the transformations to apply in each given state out of the possible transformations for that state.

– IBM Research

Abstraction of Planning

• Abstraction to remove irrelevant information
• Minimal knowledge representation that the planner needs to reason about

Abstraction of Planning

loc1

loc2

State Transition System

Dock Worker Robots (DWR) example

load

unload

put

take

take

put

move2

move1

move2

move1

move1

move2

State Transition System

Conceptual Model of Planning

State Transition System

Dock Worker Robots (DWR) example

load

unload

put

take

take

put

move2

move1

move2

move1

move1

move2

Planning Problem

State Transition System

Dock Worker Robots (DWR) example

load

unload

put

take

take

put

move2

move1

move2

move1

move1

move2

A Plan

Types of Planners

• Domain Specific
• Tuned to solve planning problem for a particular domain
• Does not work for other domains
• Domain Independent
• Works for any planning domain
• May not be that efficient than domain specific planners
• Configurable
• Domain independent planning engine
• Input: Knowledge about how to solve problems in a domain

Domain Specific Planner

Domain Independent Planners

Restrictive Assumptions

Restrictive Assumptions

Classical Planning

Classical Planning

Plan-space Planning

• Decompose the planning goals into individual goals
• Plan the subgoals separately
• Interaction to remove conflict
• Produce a flexible partially ordered plan
• Has been used Mars rovers

Planning Graph-based Formulation

All appli-cable actions

All effects of those actions

All actions applicable to subsets of Level 1

All effects of those actions

Initial state

Level 0

        Level 1       

         Level 2          

Problem Conversion

• Translate the planning problem or the planning graph�into another kind of problem for which there are efficient solvers
• Find a solution to that problem
• Translate the solution back into a plan
• Satisfiability solvers (SAT Solvers)
• Satplan
• Integer programming solvers such as Cplex
• Convert the planning problem into a Constraint Satisfaction Problem
• Solve the CSP

​

​

Configurable Planners

• Domain-independent planners are less efficient than the domain dependent planners
• Domain dependent planner can steer directly to the solution
• Domain independent planner will explore different alternative paths
• Writing domain dependent planners is costly
• Configurable planners
• Domain independent planning engine
• Input encode how to solve a problem (may be at macro level)
• Hierarchical Task Network (HTN Planners)

Planning in Non-deterministic Environments

• Actions may have multiple (uncertain) outcomes
• Some actions are inherently random (e.g., rolling of a dice)
• Actions sometimes may fail to have desired effects
• Hitting a golf ball may not land up in hole
• How to models possible uncertain outcomes?
• Markov Decision Processes (MDP)
• Outcomes have probabilities

Dock Worker Robots

• Used as example in major part in the lecture
• A harbour has several locations
• e.g., docks, docked ships, storage areas, parking areas
• Containers
• going to/from ships
• Robot vehicles
• can move containers
• Cranes
• can load and�unload containers

Objects

• Locations: l1, l2, …, or loc1, loc2, …
• Containers: c1, c2, …
• can be stacked in piles, loaded onto robots, or held by cranes
• Piles: p1, p2, …
• places to stack containers
• pallet at the bottom of each pile
• Robot vehicles: r1, r2, …
• carry at most one container
• can move to adjacent locations
• limit on how many can be at a location
• Cranes: k1, k2, …
• each belongs to a single location or a single robot
• move containers between piles and robots

​

Properties of the Objects

• Rigid properties: same in all states
• which locations are adjacent
• which cranes and piles are at which locations
• Variable properties: differ from one state to another
• location of each robot
• for each container
• which location, which pile/crane/robot, at top of pile?
• Actions:
• A crane make take a container from a stack, put it onto a stack, load it onto a robot, or unload it from a robot
• A robot may move from a location to another adjacent location

​

​

​

​