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)

		 __________________ __________________

		 ONTABLE(A)			 	ONTABLE(B)

		 ARMEMPTY 		 		ARMEMPTY

		 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:

• If the eventual plan contains a PICKUP then STACK step then
• HOLDING preconditions would need to be satisfied by some other steps.
• Solve this by enforcing ordering by introducing constraints whenever step addition is employed.
• In this case we need to state that a PICKUP step should precede a corresponding STACK step. That is to say

  PICKUP(A) STACK(A,B)

  PICKUP(B) STACK(B,C)

This gives four steps partially ordered and four unachieved conditions

• *CLEAR(A) -- block A is not clear in initial state.
• *CLEAR(B) -- although block B is clear in initial state STACK(A,B) with postcondition CLEAR(B) might precede the step with *CLEAR(B) precondition.
• Two *ARMEMPTY -- initial state makes ARMEMPTY but PICKUP step has ARMEMPTY and could again precede this step.

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

• PICKUP(B) asserts ARMEMPTY.
• But if we insert a step between PICKUP(B) and PICKUP(A) to reassert ARMEMPTY then we can achieve the precondition.
• STACK(B,C) can do this so we post another constraint:

  PICKUP(B) STACK(B,C) PICKUP(A)

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)

		 __________________

			 ON(x,A)

			 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)

		 __________________

		  HOLDING(C)

			ONTABLE(C)

			ARMEMPTY

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

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