The blocks world is chosen to illustrate these techniques as it is sufficiently simple and well behaved to be easily understood yet it provides the environment to illustrate the way problems are broken into nearly distinct subproblems; thus showing how thepartial solutions need to be combined to form a realistic complete solution to the set problem. The world consists of a flat surface such as a tabletop and an adequate set of identical blocks which are identified by letters. The blocks can be stacked one on one to form towers of apparently unlimited height. The stacking is achieved using a robot arm which has fundamental operations and states which can be assessed using logic and combined using logical operations. The robot can hold one block at a time and only one block can be moved at a time. Using the four actions:
UNSTACK(A,B) pick up clear block A from block B;
STACK(A,B) place block A using the arm onto clear block B;
PICKUP(A) lift clear block A with the empty arm;
PUTDOWN(A) place the hled block A onto a free space on the table.
and the five predicates:
ON(A,B) block A is on block B
ONTABLE(A) block A is on the table
CLEAR(A) block A has nothing on it
HOLDING(A) the arm holds block A
ARMEMPTY the arm holds nothing
Using logic but not logical notation we can say that
If the arm is holding a block it is not empty
If block A is on the table it is not on any other block
If block A is on block B,block B is not clear.
Stack requires the arm to be holding a block A and the other block B to be clear.
Afterwards the block A is on block B and the arm is empty and these are true--- add;
The arm is not holding a block and block B is not clear; predicates that are false delete;
Unstack requires that the block A is on block B; that the arm is empty and that block A is clear.
Afterwards block B is clear and the arm is holding block A true---add;
The arm is not empty and the block A is not on block B; predicates that are false delete;
Pickup needs a block to be clear and on the table and the arm to be empty.
Afterwards the arm is holding the block which is true--add;
The block is not on the table and the arm is not empty; predicates that are false delete;
Putdown means that the arm is holding a block.
Afterwards the block is on the table and the arm is empty which is true--add;
The arm is not holding the block; predicates that are false delete;
GOAL STACK PLANNING
SUSSMAN ANOMALY
Consider the problem shown in fig 13.5 which is harder and is known as the Sussman anomaly because it was studied by Sussman in 1975.
This immediately leads to two approaches as given below
ON(A,B) ON(B,C)
ON(B,C) ON(A,B)
ON(A,B) H ON(B,C) ON(A,B) H ON(B,C)
choosing path 1 and trying to get block A on block B leads to the goal stack given in fig13.6
This achieves block A on block B which was produced by puttting block C on the table giving the diagram of fig 13.6a and the goal stack shown. The sequence of operators is
1 UNSTACK(C,A)
2 PUTDOWN(C)
3 PICKUP(A)
4 STACK (A,B)
Working on the next goal of ON(B,C) requires block B to be cleared so that it can be stacked on block C. Unfortunately we need to unstack block A which we just did. Thus the list of operators become
1 UNSTACK(C,A)
2 PUTDOWN(C)
3 PICKUP(A)
4 STACK (A,B)
5 UNSTACK(A,B)
6 PUTDOWN(A)
7 PICKUP(B)
8 STACK (B,C)
Arriving at fig13.6b we can see that block A is not on block B so that two extra operations are needed giving the final scheme
1 UNSTACK(C,A)
2 PUTDOWN(C)
3 PICKUP(A)
4 STACK (A,B)
5 UNSTACK(A,B)
6 PUTDOWN(A)
7 PICKUP(B)
8 STACK (B,C)
9 PICKUP(A)
10 STACK(A,B)
Analysing this sequence we observe that steps 4 and 5 are opposites and therefore cancel each other out, also steps 3 and 6 are opposites and therefore cancel each other out as well leaving the more efficient scheme
1 UNSTACK(C,A)
2 PUTDOWN(C)
7 PICKUP(B)
8 STACK (B,C)
9 PICKUP(A)
10 STACK(A,B)
NON-LINEAR PLANNING USING CONSTRAINT POSTING
SUSSMAN ANOMALY
Most problems such as this one require subproblems to be worked on simultaneously.
This means a nonlinear plan such as
1 Try to achieve ON(A,B) clearing block A putting block C on the table.
2 Achieve ON(B,C) by stacking block B on block C.
3 Complete ON(A,B) by stacking block A on block B.
This type of work was carried out in 1975 ish in HACKER NOAH NONLIN and TWEAK.
Constrain posting builds up a plan by suggesting operators, trying to order them and produce bindings between variables in the operators and actual blocks. The inital plan consists of no steps and by studying the goal state ideas for the possible steps are generated. There is no order or detail at this stage. Gradually more detail is introduced and constraints about the order of subsets of the steps are introduced until a completely ordered sequence is created.
In this problem means-end analysis suggests two steps with end conditions
ON(A,B) and ON(B,C) which indicates the operator STACK giving the layout shown below where the operator is preceded by its preconditions and followed by its post conditions
CLEAR(A) CLEAR(C)
*HOLDING(A) *HOLDING(B)
STACK(A,B) STACK(B,C)
ARMEMPTY ARMEMPTY
ON(A,B) ON(B,C)
not CLEAR(B) not CLEAR(C)
not HOLDING(A) not HOLDING(B)
There is no order at this stage and unachieved conditions are starred.
The TWEAK planning method is now used and this involves heuristics.1 STEP ADDITION creating new steps
2 PROMOTION constraining a step to go before another step
3 DECLOBBERING placing a new step between two steps to revert a precondition
4 SIMPLE ESTABLISHMENT assigning a value to a variable to ensure a precondition
5 SEPARATION preventing variables being assigned certain values.
TWEAK HEURISTICS USING CONSTRAINT POSTING
The STACK operator fulfills the HOLDING condition and this is inserted as indicated in 1 above giving the following potential situation
*CLEAR(A) *CLEAR(B)
ONTABLE(A) ONTABLE(B) preconditions
*ARMEMPTY *ARMEMPTY
PICKUP(A) PICKUP(B) operators
ONTABLE(A) ONTABLE(B) postconditions
*ARMEMPTY *ARMEMPTY
HOLDING(A) HOLDING(B)
CLEAR(A) CLEAR(C) preconditions
*HOLDING(A) *HOLDING(B)
STACK(A,B) STACK(B,C) operators
ARMEMPTY ARMEMPTY
ON(A,B) ON(B,C) postconditions
not CLEAR(B) not CLEAR(C)
not HOLDING(A) not HOLDING(B)
At the moment there is no plan as the postconditions of the second set could negate the preconditions of the first plan so we must introduce order
PICKUP(A) <- STACK(A,B) final steps 5 and 6
PICKUP(B) <- STACK(B,C)
This gives four steps partially ordered and four unachieved conditions
*CLEAR(A) *CLEAR(B)
*ARMEMPTY *ARMEMPTY
The first is not clear in the initial state and STACK(A,B) makes the second not clear; thus we use heuristic 2 called promotion to force one opertor to precede another so that the postcondition
of one operator STACK(A,B) does not negate the precondition CLEAR(B) of another operator PICKUP(B). This ordering is represented
PICKUP(B) <- STACK(A,B)
Making PICKUP(B) precede PICKUP(A) ensures that the arm is empty and all the conditions for PICKUP(B) are met. This is written
PICKUP(B) <- PICKUP(A)
Unfortunately a postcondition of the first operator is that the arm becomes not empty, so we need to use heuristic 3 declobbering to achieve the preconditions of the second operator
PICKUP(A).
Looking at the conditions of the four basic operators suggests STACK . The parameters also suggest block B as the arm is HOLDING(B) and block C as CLEAR(C) giving STACK(B,C)
PICKUP(B) <- STACK(B,C) <- PICKUP(A) final steps 3,4 and 5
clobber declobber
At this point we still need to achieve CLEAR(A) ; the appropriate operator is UNSTACK(x,A)
This leads to the following set of conditions
*CLEAR(x)
*ON(x,A) preconditions
*ARMEMPTY
UNSTACK(x,A) operators
not ON(x,A) postconditions
not ARMEMPTY
HOLDING(x)
CLEAR(A)
The variable x can be bound to the block C by simple establishment heuristic 4 to achieve a precondition; the precondition CLEAR(C) and ARMEMPTY are negated by STACK(B,C) and by PICKUP(B) or PICKUP(A)
Hence we introduce three orderings or promotion to ensure the operator UNSTACK(C,A)
UNSTACK(C,A) <- STACK(B,C)
UNSTACK(C,A) <- PICKUP(A)
UNSTACK(C,A) <- PICKUP(B)
Promotion involves adding a step and this clobbers one of the preconditions of PICKUP(B)
viz ARMEMPTY, always a potential problem with this heuristic. However all is not lost as there is an operator, PUTDOWN that has the required postcondition and given that the operator
UNSTACK(C,A) had generated the precondition for it of HOLDING(C) we can produce an extra operator successfully
HOLDING(C)
PUTDOWN(C)
not HOLDING(C)
ONTABLE(C)
ARMEMPTY
This operator declobbers the operator PICKUP(B) yielding the sequence
UNSTACK(C,A) <- PUTDOWN(C) <-PICKUP(B) final steps 1,2 and 3
This yields the final sequence showing the old order as well
1 1 UNSTACK(C,A)
2 2 PUTDOWN(C)
3 7 PICKUP(B)
4 8 STACK (B,C)
5 9 PICKUP(A)
6 10 STACK(A,B)
The formal form of the TWEAK algorithm
1 initialise S to be the set of propositions in the goal state;
2 repeat
3 remove some unachieved prposition P from S;
4 achieve P by using one of the heuristics;
5 review all the steps, including additional steps to find all unachieved preconditions; add these to S the set of unachieved preconditions;
6 until the set S is empty;
7 complete the plan by converting partial orders into a total order performing all necessary instantiations, binding of the variables.