next up previous
Next: Further Reading Up: Nonlinear Planning Using Constraint Previous: Nonlinear Planning Using Constraint

Tweak Heuristics Using Constraint Posting

The Tweak planning method involves the following heuristics.

Step Addition
-- creating new steps (GPS).
Promotion
-- constraining a step to go before another step (Sussman's HACKER).
Declobbering
-- placing a new step between two steps to revert a precondition (NOAH, NONLIN).
Simple Establishment
-- assigning a value to a variable to ensure a precondition (TWEAK).
Separation
-- preventing variables being assigned certain values (TWEAK).

Now lets look at the effect of each heuristic.

We must try and achieve the preconditions of the STACK operation above.

We could try picking up the respective blocks:

 
		 CLEAR(A)				CLEAR(C)

ONTABLE(A) ONTABLE(B)

*ARMEMPTY *ARMEMPTY

__________________ __________________

PICKUP(A) PICKUP(B)

__________________ __________________

tex2html_wrap_inline7182ONTABLE(A) tex2html_wrap_inline7182ONTABLE(B)

tex2html_wrap_inline7182ARMEMPTY tex2html_wrap_inline7182ARMEMPTY

HOLDING(A) HOLDING(B)

At the moment there is no plan as the postconditions of the this set could negate the preconditions of the first (STACK) plan so we must introduce order:

This gives four steps partially ordered and four unachieved conditions

We can use the promotion heuristic to force one operator 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 by

PICKUP(B) tex2html_wrap_inline8336 STACK(A,B)

We can use promotion to achieve one of the ARMEMPTY preconditions:

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) tex2html_wrap_inline8336 PICKUP(A).

Unfortunately a postcondition of the first operator is that the arm becomes not empty, so we need to use the declobbering heuristic to achieve the preconditions of the second operator PICKUP(A).

Declobbering

We still need to achieve CLEAR(A):

The appropriate operator is UNSTACK(x,A) by step addition. This leads to the following set of conditions

   *CLEAR(x)

*ON(x,A)

*ARMEMPTY

__________________

UNSTACK(x,A)

__________________

tex2html_wrap_inline7182 ON(x,A)

tex2html_wrap_inline7182 ARMEMPTY

HOLDING(x)

CLEAR(A)

The variable x can be bound to the block C by the simple establishment heuristic since C is on A in the initial state.

The preconditions CLEAR(C) and ARMEMPTY are negated by STACK(B,C) and by PICKUP(B) or PICKUP(A) however.

So we must introduce three orderings by promotion to ensure the operator UNSTACK(C,A).

   UNSTACK(C,A)  leftarrow  STACK(B,C)

UNSTACK(C,A) leftarrow PICKUP(A)

UNSTACK(C,A) leftarrow 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)

__________________

tex2html_wrap_inline7182 HOLDING(C)

ONTABLE(C)

ARMEMPTY

This operator declobbers the operator PICKUP(B) yielding the sequence

UNSTACK(C,A) tex2html_wrap_inline8336 PUTDOWN(C) tex2html_wrap_inline8336 PICKUP(B)

This yields the final sequence:

  1. UNSTACK(C,A)
  2. PUTDOWN(C)
  3. PICKUP(B)
  4. STACK (B,C)
  5. PICKUP(A)
  6. STACK(A,B)

Let us finish this section by looking at the formal form of the TWEAK algorithm:

  1. Initialise S to be the set of propositions in the goal state.
  2. Repeat
    1. Remove some unachieved proposition P from S.
    2. Achieve P by using one of the heuristics.
    3. Review all the steps, including additional steps to find all unachieved preconditions, add these to S the set of unachieved preconditions.

    until the set S is empty.

  3. Complete the plan by converting partial orders into a total order performing all necessary instantiations, binding of the variables.

next up previous
Next: Further Reading Up: Nonlinear Planning Using Constraint Previous: Nonlinear Planning Using Constraint

dave@cs.cf.ac.uk