Introduction to AI - Week 9

Planning

The Planning System Strips

Fikes and Nilsson 1971: STanford Research Institute Problem Solver

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

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 ?


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 Goal1 that is open in Actual
        ;;; arbitrary choice -> backtrack point
 1.2.   select instance I of operator with Goal1, 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:

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


Assumptions of Planning in Strips


Graphplan
Features:

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).


Planning Graphs (Cont'd)

Three kinds of edges:

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.


Valid Plans

A plan is called valid:

Mutual Exclusion

Identify mutual exclusion relationships to reduce the search for a subgraph of a Planning Graph that may correspond to a valid plan.


Example

Rocket domain:

Exclusion Relations


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

Extending planning graphs works as follows:

Searching for a Plan

Given a Planning Graph, search for a valid plan using a backward-chaining strategy.

Memoisation

Two aspects:


Minimal Action sets - Goal Orderings


Termination on Unsolvable Problems


Summary of Graphplan

Literature    



© 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/