Nonlinear Planning Using Constraint Posting

Let us reconsider the SUSSMAN ANOMALY

• Problems such as this one require subproblems to be worked on simultaneously.
• Thus a nonlinear plan using heuristics 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.

Constraint posting has emerged as a central technique in recent planning systems (E.g. MOLGEN and TWEAK)

Constraint posting builds up a plan by:

• suggesting operators,
• trying to order them, and
• produce bindings between variables in the operators and actual blocks.

The initial 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(B)				CLEAR(C)

		 *HOLDING(A)				*HOLDING(B)

		 __________________ __________________

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

		 __________________ __________________

		 ARMEMPTY 				ARMEMPTY

		 ON(A,B)				ON(B,C)

		  CLEAR(B)				 CLEAR(C)

		  HOLDING(A)			 HOLDING(B)

NOTE:

• There is no order at this stage.
• Unachieved preconditions are starred (*).
• Both of the HOLDING preconditions are unachieved since the arm holds nothing in the initial state.
• Delete postconditions are marked by ().

Many planning methods have introduced heuristics to achieve goals or preconditions. The TWEAK planning method brought all these together under one formalism. Other methods that introduced/used the following heuristics are mentioned in brackets in the following section.

 
• Tweak Heuristics Using Constraint Posting