next up previous
Next: Detecting Progress Up: Planning System Components Previous: Choice of best rule

Rule application

Green's Approach (1969)

Basically this states that we note the changes to a state produced by the application of a rule.

Consider the problem of having two blocks A and B stacked on each other (A on top).

Then we may have an initial state tex2html_wrap_inline7770 which could be described as:

    ON(tex2html_wrap_inline7772

ONTABLE(tex2html_wrap_inline7774

CLEAR(tex2html_wrap_inline7776

If we now wish to UNSTACK(A, B). We express the operation as follows:

 [CLEAR(x,s) tex2html_wrap_inline7782 ON(x, y, s)] tex2html_wrap_inline7156

[HOLDING(x, DO(UNSTACK(x,y),s)) tex2html_wrap_inline7782

CLEAR(y,DO(UNSTACK(x,y),s))]

where x,y are any blocks, s is any state and DO() specifies that an new state results from the given action.

The result of applying this to state tex2html_wrap_inline7770 to give state tex2html_wrap_inline7808 then we get:

HOLDING(tex2html_wrap_inline7810) tex2html_wrap_inline7782 CLEAR(tex2html_wrap_inline7814).

There are a few problems with this approach:

The frame problem
-- In the above we know that B is still on the table. This needs to be encoded into frame axioms that describe components of the state not affected by the operator.

The qualification problem
-- If we resolve the frame problem the resulting description may still be inadequate. Do we need to encode that a block cannot be places on top of itself? If so should this attempt fail?

If we allow failure things can get complex -- do we allow for a lot of unlikely events?

The ramification problem
-- After unstacking block A, previously, how do we know that A is no longer at its initial location?

Not only is it hard to specify exactly what does not happen ( frame problem) it is hard to specify exactly what does happen.

STRIPS (1971 ff.)

STIPS proposed another approach:

Consider the following example in the Blocks World and the fundamental operations:

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 - ADD; The arm is not empty and the block A is not on block B -- DELETE;

See Exercises for more examples.

We have now greatly reduced the information that needs to be held. If a new attribute is introduced we do not need to add new axioms for existing operators. Unlike in Green's method we remove the state indicator and use a database of predicates to indicate the current state

Thus if the last state was:

ONTABLE(B) tex2html_wrap_inline7782 ON(A,B) tex2html_wrap_inline7782 CLEAR(A)

after the unstack operation the new state is

ONTABLE(B) tex2html_wrap_inline7782 CLEAR(B) tex2html_wrap_inline7782 HOLDING(A) tex2html_wrap_inline7782 CLEAR(A)


next up previous
Next: Detecting Progress Up: Planning System Components Previous: Choice of best rule

dave@cs.cf.ac.uk