Introduction to AI - Week 9

The Planning System Strips

• 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

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

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

Ontable(A)
Ontable(B)
On(D,A)
On(C,D)
Clear(C)
Clear(B)
Handempty
Holds(C)
Clear(D)

Ontable(A)
Ontable(B)
On(D,A)
Clear(B)
Holds(C)
Clear(D)
Clear(C)
Ontable(C)
Handempty

Ontable(A)
Ontable(B)
On(D,A)
Clear(B)
Clear(D)
Clear(C)
Ontable(C)
Handempty
Holds(D)
Clear(A)

Ontable(A)
Ontable(B)
Clear(B)
Clear(C)
Ontable(C)
Holds(D)
Clear(A)
Clear(D)
On(D,B)
Handempty

Ontable(A)
Ontable(B)
Clear(C)
Ontable(C)
Clear(A)
Clear(D)
On(D,B)
Handempty
Holds(A)

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

Ontable(A)
Ontable(B)
Ontable(C)
On(D,A)

Clear(B)
Clear(C)
Clear(D)
Handempty

Example (Cont'd)

Ontable(A)
Ontable(B)
On(D,B)
Clear(A)
Clear(C)
Clear(D)
Handempty

Still open: On(A,D)

Example (Cont'd)

Ontable(B)
Ontable(C)
On(D,B)
On(A,D)

Clear(A)
Clear(C)
Handempty

Limitations of Strips

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

The following plan fulfils this goal

Ontable(A)
Ontable(B)
On(C,A)
Clear(B)
Clear(C)
Handempty

Ontable(A)
Ontable(B)
Clear(B)
On(C,A)
Clear(C)
Handempty
Holds(C)
Clear(A)

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)

Ontable(B)
Ontable(C)
Clear(C)
Clear(B)
Holds(A)
On(A,B)
Clear(A)
Handempty

Sussman Anomaly (Cont'd)

Ontable(B)
Ontable(C)
Clear(C)
On(A,B)
Clear(A)
Handempty

Ontable(B)
Ontable(C)
Clear(C)
Clear(A)
On(A,B)
Handempty
Holds(A)
Clear(B)

Ontable(B)
Ontable(C)
Clear(B)
Clear(C)
Holds(A)
Ontable(A)
Clear(A)
Handempty

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

Ontable(C)
Clear(B)
On(B,C)
Ontable(A)
Clear(A)
Handempty
Holds(A)

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)

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.

Planning Graphs

• Directed, levelled graph: that is, the nodes can be partitioned into disjoint sets L₁,L₂,... ,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)

• 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

Valid Plans

• 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

• 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

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

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.

• 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

• 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 S^t_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 S^t_i true at time i, and
  2. 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^t-1_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:281-300, 1997.