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 first-order logic it is not trivial to see whether goal state is reached, however trivial for the
fragment normally taken
_________________________________________________________________________________________________________
Example: Blocks World
[planning6.jpg]
Ontable(A)
Ontable(B)
On(D,A)
On(C,D)
Clear(C)
Clear(B)
Handempty
[planning7.jpg]
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)
[DEL: On(C,D) :DEL]
[DEL: Clear(C) :DEL]
Clear(B)
[DEL: Handempty :DEL]
Holds(C)
Clear(D)
PUTDOWN(C)--->
Ontable(A)
Ontable(B)
On(D,A)
Clear(B)
[DEL: Holds(C) :DEL]
Clear(D)
Clear(C)
Ontable(C)
Handempty
UNSTACK(D,A)--->
Ontable(A)
Ontable(B)
[DEL: On(D,A) :DEL]
Clear(B)
[DEL: Clear(D) :DEL]
Clear(C)
Ontable(C)
[DEL: Handempty :DEL]
Holds(D)
Clear(A)
STACK(D,B)--->
Ontable(A)
Ontable(B)
[DEL: Clear(B) :DEL]
Clear(C)
Ontable(C)
[DEL: Holds(D) :DEL]
Clear(A)
Clear(D)
On(D,B)
Handempty
PICKUP(A)--->
[DEL: Ontable(A) :DEL]
Ontable(B)
Clear(C)
Ontable(C)
[DEL: Clear(A) :DEL]
Clear(D)
On(D,B)
[DEL: Handempty :DEL]
Holds(A)
STACK(A,D)--->
Ontable(B)
Clear(C)
Ontable(C)
[DEL: Clear(D) :DEL]
On(D,B)
[DEL: Holds(A) :DEL]
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 (means-end-analysis)
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):
[planning5.jpg]
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):
[planning4.jpg]
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):
[planning2.jpg]
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
[planning1.jpg]
_________________________________________________________________________________________________________
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)
[DEL: On(C,A) :DEL]
[DEL: Clear(C) :DEL]
[DEL: Handempty :DEL]
Holds(C)
Clear(A)
PUTDOWN(C)--->
Ontable(A)
Ontable(B)
Clear(A)
Clear(B)
[DEL: Holds(C) :DEL]
Ontable(C)
Clear(C)
Handempty
PICKUP(A)--->
Ontable(B)
Ontable(C)
Clear(B)
Clear(C)
[DEL: Ontable(A) :DEL]
[DEL: Clear(A) :DEL]
[DEL: Handempty :DEL]
Holds(A)
STACK(A,B)--->
Ontable(B)
Ontable(C)
Clear(C)
[DEL: Clear(B) :DEL]
[DEL: Holds(A) :DEL]
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)
[DEL: Clear(A) :DEL]
[DEL: On(A,B) :DEL]
[DEL: Handempty :DEL]
Holds(A)
Clear(B)
PUTDOWN(A)--->
Ontable(B)
Ontable(C)
Clear(B)
Clear(C)
[DEL: Holds(A) :DEL]
Ontable(A)
Clear(A)
Handempty
PICKUP(B)--->
Ontable(A)
Ontable(C)
Clear(A)
Clear(C)
[DEL: Ontable(B) :DEL]
[DEL: Clear(B) :DEL]
[DEL: Handempty :DEL]
Holds(B)
STACK(B,C)--->
Ontable(A)
Ontable(C)
Clear(A)
[DEL: Clear(C) :DEL]
[DEL: Holds(B) :DEL]
On(B,C)
Clear(B)
Handempty
PICKUP(A)--->
Ontable(C)
Clear(B)
On(B,C)
[DEL: Ontable(A) :DEL]
[DEL: Clear(A) :DEL]
[DEL: Handempty :DEL]
Holds(A)
STACK(A,B)--->
Ontable(C)
On(B,C)
[DEL: Holds(A) :DEL]
[DEL: Clear(B) :DEL]
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:
1. Prefer goals involving Ontable over all others
2. 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)
3. Handempty has always lowest priority
* Heuristic for selecting an operator:
1. Never try an operator like UNSTACK(A,A)
2. Whenever goal Holds(x) & Ontable(x) given, choose PICKUP(x)
3. Whenever goal Holds(x) and On(x,y) is given, choose UNSTACK(x,y)
4. Whenever goal Ontable(x), no choice
5. Whenever goal On(x,y), no choice
6. 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, non-linear planning.
_________________________________________________________________________________________________________
Graphplan
Features:
* Fast graph-based partial-order 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:
* precondition-edges connect actions in action-level i to their preconditions in proposition level i.
* add-edges connect action nodes in action-level i to their add-effects in proposition level i+1.
* delete-edges connect action nodes in action-level i to their delete-effects 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 no-op actions (with dot). Not all nodes at 2nd and 3rd action levels displayed.
[graphplan.jpg]
_________________________________________________________________________________________________________
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 add-effect 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 no-op actions we may define a proposition to be true at time t>1 iff it is an add-effect of
some action taken at time t-1.
* 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 no-op 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
1. i := i+1
2. Take the Planning_Graph from stage i-1, extend it one time step, that is, add the next action level and
the following proposition level.
3. 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 no-op actions & insert the precondition edges.
* Check the action nodes for exclusivity and create an "actions-that-I-am-exclusive-of" list for each
action.
* Generate proposition level by inserting add-effects.
_________________________________________________________________________________________________________
Searching for a Plan
Given a Planning Graph, search for a valid plan using a backward-chaining strategy.
* Level-by-level 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 (no-ops included) at time t-1 having
these goals as add effects.
* The preconditions of these actions form a set of subgoals at time t-1 (if these goals can be achieved in
t-1, then the original goals can be achieved in t steps).
* If the goal set at time t-1 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 non-exclusive set of actions A at time t-1 is a minimal set of
actions achieving G if:
1. every goal in G is an add-effect of some action in A, and
2. 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 breadth-first 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 no-ops) it also appears in all future
proposition levels.
* Only a finite set of propositions can be created by Strips-style 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 St[i] the collection of all sets memoised as unsolvable at level i at stage t:
1. Any plan considered must make one of the goal sets in St[i] true at time i, and
2. none of the goal sets in St[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(St-1[n])=abs(St[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 [books-shelf1.jpg]
* Avrim L. Blum and Merrick L. Furst. Fast Planning Through Planning Graph Analysis. Artificial
Intelligence, 90:281-300, 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 [1]http://www.cs.bham.ac.uk/~mmk/Teaching/AI/
References
1. http://www.cs.bham.ac.uk/~mmk/Teaching/AI/