Introduction to AI  Week 9
Planning
 The world is described in (a fragment of) logic
 Search in the universe of
states
Operators are represented by three lists:
 [Preconditions:] specify the applicability of the operator
 [delete list:] specifies what does not hold any longer
 [add list:] specifies what newly holds
The Planning System
Strips
Fikes and Nilsson 1971: STanford Research Institute
Problem Solver
 initial state Init (given by predicate logical formulae)
 goal state goal (given by predicate logical formulae)
 set of rules (given by name, preconditions, delete list, &
add list )
Remark: For firstorder logic it is not trivial
to see whether goal state is reached, however trivial for the fragment
normally taken
Example: Blocks World
Ontable(A)
Ontable(B)
On(D,A)
On(C,D)
Clear(C)
Clear(B)
Handempty
Ontable(B)
Ontable(C)
On(D,B)
On(A,D)
Clear(A)
Clear(C)
Handempty
InitGoal
The operators are as on the next slide.
Operators of the Blocks World
 
 
 
PICKUP(x)
preconditions 
Clear(x) 

Ontable(x) 

Handempty endtr
 delete list 
Clear(x) 

Ontable(x) 

Handempty 
add list 
Holds(x) 

PUTDOWN(x)
preconditions 
Holds(x) 
delete list 
Holds(x) 
add list 
Clear(x) 

Ontable(x) 

Handempty 

 
 
 
STACK(x,y)
preconditions 
Holds(x) 

Clear(y) 
delete list 
Holds(x) 

Clear(y) 
add list 
Clear(x) 

On(x,y) 

Handempty 

UNSTACK(x,y)
preconditions 
Clear(x) 

On(x,y) 

Handempty 
delete list 
Clear(x) 

On(x,y) 

Handempty 
add list 
Holds(x) 

Clear(y) 

 
 
 
Example Plan Execution
Ontable(A)
Ontable(B)
On(D,A)
On(C,D)
Clear(C)
Clear(B)
Handempty
UNSTACK(C,D)>
Ontable(A)
Ontable(B)
On(D,A)
On(C,D)
Clear(C)
Clear(B)
Handempty
Holds(C)
Clear(D)
PUTDOWN(C)>
Ontable(A)
Ontable(B)
On(D,A)
Clear(B)
Holds(C)
Clear(D)
Clear(C)
Ontable(C)
Handempty
UNSTACK(D,A)>
Ontable(A)
Ontable(B)
On(D,A)
Clear(B)
Clear(D)
Clear(C)
Ontable(C)
Handempty
Holds(D)
Clear(A)
STACK(D,B)>
Ontable(A)
Ontable(B)
Clear(B)
Clear(C)
Ontable(C)
Holds(D)
Clear(A)
Clear(D)
On(D,B)
Handempty
PICKUP(A)>
Ontable(A)
Ontable(B)
Clear(C)
Ontable(C)
Clear(A)
Clear(D)
On(D,B)
Handempty
Holds(A)
STACK(A,D)>
Ontable(B)
Clear(C)
Ontable(C)
Clear(D)
On(D,B)
Holds(A)
Clear(A)
On(A,D)
Handempty
Plan:
(UNSTACK(C,D),PUTDOWN(C),UNSTACK(D,A),STACK(D,B),PICKUP(A),STACK(A,D))
How to Search in
Strips
?
 Simple planning algorithm: breadth first search, i.e. apply all
applicable operators with all possible instantiations one after the
other and generate all possible states. But: intractable
 Heuristic procedure of Strips: means ends analysis (as in GPS):
Search in the search space from the goal, apply operators backward
 Advantages: Goal often relatively easy compared to initial state
 Examples: In order to come up with Holds(A) two possibilities:
PICKUP(A) or UNSTACK(A,x)
Algorithm MEA (meansendanalysis)
Input: a set Goal, an initial state Init, a set of rules RULES
Output: a plan P in form of a list of operators with instantiations
Auxiliary Variable: Actual for actual state
begin
0. P:=NIL;Actual:=Init
1. while goals in Goal open in Actual do
1.1. select goal Goal_{1} that is open in Actual
;;; arbitrary choice > backtrack point
1.2. select instance I of operator with Goal_{1}, in add list
;;; arbitrary choice > backtrack point
1.3 P:= append(P,MEA(preconditions(I),Actual),list(I))
1.4 Actual := P(Init)
end_do
2. return(P)
end
Example
Ontable(A)
Ontable(B)
On(D,A)
On(C,D)
Clear(C)
Clear(B)
Handempty
Actual = Init
Ontable(B)
Ontable(C)
On(D,B)
On(A,D)
Clear(A)
Clear(C)
Handempty
Goal
Open are: Ontable(C), On(D,B), On(A,D), and Clear(A)
Goal_1 := Ontable(C)
How to achieve this goal? Only by PUTDOWN(C), hence plan:
P=(MEA(preconditions(PUTDOWN(C))),PUTDOWN(C))
Hence we need a plan for the preconditions of PUTDOWN(C), i.e. Holds(C)
Example (Cont'd)
How to achieve Holds(C)? Two possibilities by PICKUP(C) or UNSTACK(C,x)
First: bad choice, since precondition is Ontable(C) (was initial goal)
Second: with x> D, hence plan:
P=(UNSTACK(C,D),PUTDOWN(C))
Now apply P to Init: Actual:= P(Init), i.e.,
Result after one loop ( Actual):
Ontable(A)
Ontable(B)
Ontable(C)
On(D,A)
Clear(B)
Clear(C)
Clear(D)
Handempty
Still open: On(D,B), On(A,D), and Clear(A)
Example (Cont'd)
For getting On(D,B) only possible operator STACK(D,B)
In order to get precondition UNSTACK(D,A)
Hence plan after second loop:
P=(UNSTACK(C,D),PUTDOWN(C),UNSTACK(D,A),STACK(D,B))
Result after two loops ( Actual):
Ontable(A)
Ontable(B)
On(D,B)
Clear(A)
Clear(C)
Clear(D)
Handempty
Still open: On(A,D)
Example (Cont'd)
Operator STACK(A,D)
For preconditions of this use PICKUP(A)
Hence plan after third loop:
P = (
UNSTACK(C,D),PUTDOWN(C),UNSTACK(D,A),
STACK(D,B),PICKUP(A),STACK(A,D))
No goal open ( Goal = Actual):
Ontable(B)
Ontable(C)
On(D,B)
On(A,D)
Clear(A)
Clear(C)
Handempty
Limitations of
Strips
Some general limitations of the representation, in particular:
 Expressive power of description language for the operators:
 Operator changes exactly, what is specified in its add list and delete list.
 Problems with the strategy:
Sussman anomaly
Sussman Anomaly (Cont'd)
Select first goal On(A,B) else selection optimal The following plan fulfils this goal
Ontable(A)
Ontable(B)
On(C,A)
Clear(B)
Clear(C)
Handempty
UNSTACK(C,A)>
Ontable(A)
Ontable(B)
Clear(B)
On(C,A)
Clear(C)
Handempty
Holds(C)
Clear(A)
PUTDOWN(C)>
Ontable(A)
Ontable(B)
Clear(A)
Clear(B)
Holds(C)
Ontable(C)
Clear(C)
Handempty
PICKUP(A)>
Ontable(B)
Ontable(C)
Clear(B)
Clear(C)
Ontable(A)
Clear(A)
Handempty
Holds(A)
STACK(A,B)>
Ontable(B)
Ontable(C)
Clear(C)
Clear(B)
Holds(A)
On(A,B)
Clear(A)
Handempty
Sussman Anomaly (Cont'd)
Now select the second goal On(B,C). Has plan:
Ontable(B)
Ontable(C)
Clear(C)
On(A,B)
Clear(A)
Handempty
UNSTACK(A,B)>
Ontable(B)
Ontable(C)
Clear(C)
Clear(A)
On(A,B)
Handempty
Holds(A)
Clear(B)
PUTDOWN(A)>
Ontable(B)
Ontable(C)
Clear(B)
Clear(C)
Holds(A)
Ontable(A)
Clear(A)
Handempty
PICKUP(B)>
Ontable(A)
Ontable(C)
Clear(A)
Clear(C)
Ontable(B)
Clear(B)
Handempty
Holds(B)
STACK(B,C)>
Ontable(A)
Ontable(C)
Clear(A)
Clear(C)
Holds(B)
On(B,C)
Clear(B)
Handempty
PICKUP(A)>
Ontable(C)
Clear(B)
On(B,C)
Ontable(A)
Clear(A)
Handempty
Holds(A)
STACK(A,B)>
Ontable(C)
On(B,C)
Holds(A)
Clear(B)
On(A,B)
Clear(A)
Handempty
First part undoes the plan for the goal On(A,B)
Sussman Anomaly (Cont'd)
Second trial: select the goal On(B,C) first. Now first, B is set on top of C, this must be undone again.
Hence, the decomposition into partial goals, necessarily results in
superfluous steps, i.e. bad plans. (disadvantage in particular, when
execution of plans is expensive)
That plans are found at all, is due to the fact that in the blocks
world for each operator there is an inverse operator
Heuristics in the Blocksworld
 Heuristic for selecting a goal:
Give order to goals such that:
 Prefer goals involving Ontable over all others
 When all Ontable predicates fulfilled, build towers:
Build up towers from the bottom up, i.e.,
when block A should be above block B, then On(A,x) has lower
priority than On(B,x)
 Handempty has always lowest priority
 Heuristic for selecting an operator:
 Never try an operator like UNSTACK(A,A)
 Whenever goal Holds(x) & Ontable(x) given,
choose PICKUP(x)
 Whenever goal Holds(x) and On(x,y) is
given, choose UNSTACK(x,y)
 Whenever goal Ontable(x), no choice
 Whenever goal On(x,y), no choice
 Whenever there is a further choice, take the first of the possible
operator instances
Assumptions of Planning in
Strips
 Linear planning, i.e., plan as sequence of operators
 Separation of planning in planning and execution phase
 Search in a particular model
 Assumption on complete knowledge of the initial state and the
operators
 Search Strategy select one subgoal after the
other. Narrow focus on a single subgoal at a time.
 Extended to deal with different subgoals
simultaneously, nonlinear planning.
Graphplan
Features:
 Fast graphbased partialorder planner
 Finds shortest possible plan (if exists)
 Does not search in the state space, but makes use of
compact structure, called Planning Graph
 Makes use of strong sufficient constraints
Planning Graphs
A planning graph is similar to a valid plan, but without the
requirement that the actions at a given time step not interfere (i.e.,
corresponds roughly to conflicts not resolved).
 Directed, levelled graph: that is, the nodes can be
partitioned into disjoint sets L_{1},L_{2},... ,L_{n} such that the
edges only connect nodes in adjacent levels.
 Two kinds of nodes: alternate between proposition nodes
(labelled by, e.g., On(A,B)) and action nodes (labelled
by, e.g., UNSTACK(A,B)):
1st level: propositions true at time 1 (initial state)
2nd level: possible actions at time 1
3rd level: propositions possibly true at time 2
4th level: possible actions at time 2
5th level: propositions possibly true at time 3 (and so forth)
Planning Graphs (Cont'd)
Three kinds of edges:
 preconditionedges connect actions in actionlevel i to
their preconditions in proposition level i.
 addedges connect action nodes in actionlevel i to their
addeffects in proposition level i+1.
 deleteedges connect action nodes in actionlevel i to their
deleteeffects in proposition level i+1.
Example  Rocket Domain
One rocket R, two pieces of cargo A and B, start location L,
destination P. Delete edges as dashed lines. Explicit noop
actions (with dot). Not all nodes at 2nd and 3rd action
levels displayed.
Valid Plans
A plan is called valid:
 Actions at time 1, at time 2, at time 3 etc
 Several actions may occur at the same time so long as they do
not interfere with each other, i.e., if one does not delete a
precondition or an addeffect of the other. (In a linear plan these
independent parallel actions could be arranged in any order
with exactly the same outcome.
 A valid plan may perform an action at time t=1 if all
its preconditions are true in the initial state.
 A valid plan may perform an action at time t>1 if the plan
makes all its preconditions true at time t.
 Because of noop actions we may define a proposition to be true
at time t>1 iff it is an addeffect of some action taken at time
t1.
 A valid plan must make all goals true at the final time step.
Mutual Exclusion
 Two actions at a given action level are mutual exclusive if
no valid plan could possibly contain both.
 Two propositions at a given proposition level are mutual
exclusive if no valid plan could possibly make both true.
Identify mutual exclusion relationships to reduce the search for a
subgraph of a Planning Graph that may correspond to a valid plan.
 Graphplan notices and records mutual exclusion relationships
by propagating them through the Planning Graph using a few simple
rules.
 The rules do not guarantee to find all mutual
exclusion relationships (just typically a large number of them).
Example
Rocket domain:
 Initial state: At(Rocket1,London), Fuel(Rocket1)
 The actions
MOVE(Rocket1,London,Paris) and
LOAD(Alex,Rocket1,London)
are exclusive at time 1 because the first
deletes the proposition At(Rocket1,London) which is a
precondition of the second
 The propositions
At(Rocket1,London) and
At(Rocket1,Paris) are
exclusive at time 2 because all ways of generating the first (only
noop does) are exclusive of all ways of
generating the second (only MOVE does).
Exclusion Relations
 The Competing needs relation and the exclusivity between
propositions are not just logical properties of the operators, they
also depend on the interplay between operators and the initial
state.
 Example: Initially one object is not at two different
places. The operators guarantee that this relation remains
invariant during the plan construction. [If, however, it were
not true initially, it wouldn't necessarily hold later on.]
Description of the Algorithm
Planning_Graph := Initial_state,
i := 1, No_Plan_found := TRUE,
Plan_exists := TRUE
WHILE No_Plan_found and Plan_exists DO
 i := i+1
 Take the Planning_Graph from stage i1, extend it
one time step, that is, add the next action level and the following
proposition level.
 Search for a valid plan of length i in
Planning_Graph.
If plan found No_Plan_found := FALSE,
store plan in Plan.
If
detected that no plan can exist Plan_exists := FALSE
END WHILE
IF No_Plan_found=FALSE RETURN Plan
ENDIF
IF Plan_exists=FALSE RETURN "No Plan Exists"
ENDIF
Properties
 Graphplan's algorithm is sound and complete: only
legal plans are generated. If there is a legal plan then
Graphplan finds one.
 In each loop i of the algorithm the algorithm either discovers a
plan or proves that no plan having i or fewer steps exists.
Extending planning graphs works as follows:
 For each operator and each way of instantiating its
preconditions to propositions in the previous level, insert an
action node if no two of its preconditions are labelled as
mutually exclusive.
 Insert all the noop actions & insert
the precondition edges.
 Check the action nodes for exclusivity and create an
"actionsthatIamexclusiveof" list for each action.
 Generate proposition level by inserting addeffects.
Searching for a Plan
Given a Planning Graph, search for a valid plan using a
backwardchaining strategy.
 Levelbylevel approach (to make best use of the mutual
exclusion constraints).
 Given a set of goals at time t, it attempts to find a set of
actions (noops included) at time t1 having these goals as add
effects.
 The preconditions of these actions form a set of subgoals at
time t1 (if these goals can be achieved in t1, then the
original goals can be achieved in t steps).
 If the goal set at time t1 turns out not to be solvable, try
to find a different set of actions (backtracking), continuing
until it either succeeds or proves that the original set of
goals is not solvable at time t.
Memoisation
 When a set of (sub)goals at some time t is determined to be not
solvable, then before backtracking Graphplan memoises this
fact (goal set and the time t) in a hash table.
 Before searching for plans of a set of subproblems look up hash
table whether it is proved to be unsolvable.
Two aspects:
 Speed up
 Termination check
Minimal Action sets  Goal Orderings
 Let G be a set of goals at time t. A nonexclusive set of
actions A at time t1 is a minimal set of actions achieving G
if:
 every goal in G is an addeffect of some action in A, and
 no action can be removed from A so that the add effects of the
actions remaining still contain G.
 It suffices to look at minimal action sets.
 Graphplan's strategy is breadthfirst like, hence fairly
insensitive to goal orderings, in particular when considering only
minimal action sets.
Termination on Unsolvable Problems
 If a proposition appears in some proposition level then (because
of noops) it also appears in all future proposition levels.
 Only a finite set of propositions can be created by Stripsstyle
operators. Hence there is a minimal n such that propositions
P_{n} are equal to P_{n+i} for all i>= 0. The graph is
levelled off.
 Let S^{t}_{i} the collection of all sets memoised as
unsolvable at level i at stage t:
 Any plan considered must make one of the goal
sets in S^{t}_{i} true at time i, and
 none of the goal sets in S^{t}_{i} is achievable in i steps.
 If a graph has levelled off at some level n and a stage t has
passed in which abs(S^{t1}_{n})=abs(S^{t}_{n}) then "No Plan
Exists."
 Graphplan outputs "No Plan Exists" if and only if the
problem is unsolvable.
Summary of Graphplan
 No search in the state space
 If a plan exists, finds shortest plan.
 If no plan exists, stops with "No Plan Exists"
 Experimental Results: In tests significantly more
efficient than traditional planners.
Literature
 Avrim L. Blum and Merrick L. Furst.
Fast Planning Through Planning Graph Analysis. Artificial
Intelligence, 90:281300, 1997.
© Manfred Kerber, 2004, Introduction to AI
24.4.2005
The URL of this page is http://www.cs.bham.ac.uk/~mmk/Teaching/AI/Teaching/AI/l9.html.
URL of module http://www.cs.bham.ac.uk/~mmk/Teaching/AI/