in the T
     Consider the three disk Tower of Hanoi problem that was discussed earlier in this course. Recall that a disk, d1, may be moved from one peg, p1, to another peg, p2, if disk d1 is clear (that is, no other disk is on top of it) and if peg p2 is either empty or the top disk on p2 is larger than d1. Create a solution for the three disk problem and then represent this solution in the form of a triangle table.

     The basic action in this domain is to move a disk from one peg to another. There are, however, several different conditions for this type of move that must be distinguished in order to accurately model the move.

  • the disk to be moved is the sole disk on the current peg and is to be moved to an empty peg
  • the disk to be moved is the sole disk on the current peg and is to be moved to a peg already containing at least one other disk
  • the disk to be moved is above at least one other disk on the current peg and is clear and is to be moved to an empty peg
  • the disk to be moved is above at least one other disk on the current peg and is clear and is to be moved to a peg already containing at least one other disk

 In the answer below, the disks are named:

  • L (the largest),
  • M (the next largest), and
  • S (the smallest).

The pegs are named:

  • P1 (the left peg which is also the starting peg in this problem),
  • P2 (the middle peg), and
  • P3 (the right peg which is the goal peg in this problem).

The predicates are:

  • at(disk, peg) - the disk is on peg
  • >(disk1,disk2) - disk1 is larger than disk2
  • on(disk1, disk2) - disk1 is on disk2
  • empty(peg) - the peg has no disk on it
  • top(disk,peg) - disk is the top disk on peg
  • clear(disk) - the disk has no disk above it

The various move functions written in the STRIPs format are:

  • MoveEE(d,f,t) - The action that moves a disk from its current peg to a new peg when d is the only disk on the current peg and the new peg is empty is defined as:
    • preconditions: at(d,f) AND clear(d) AND empty(t)
    • add list: at(d,t), empty(f)
    • delete list: at(d,f), empty(t)
  • MoveOE(d,f,t) - The action that moves a disk from its current peg to a new peg when d is the top disk on the current peg and the new peg is empty is defined as:
    • preconditions: at(d,f) AND clear(d) AND on(d,d1) AND empty(t)
    • add list: at(d,t), top(d1,f), clear(d1)
    • delete list: at(d,f), empty(t), top(d,f), on(d,d1),
  • MoveEO(d,f,t) - The action that moves a disk from its current peg to a new peg when d is the only disk on the current peg and the new peg holds one or more disks is defined as:
    • preconditions: at(d,f) AND clear(d) AND top(d2,t) AND >(d2,d)
    • add list: at(d,t), empty(f, ), top(d1,t) on(d,d2)
    • delete list: at(d,f), empty(t), top(d,f), on(d,d1), clear(d2)
  • MoveOO(d,f,t) - The action that moves a disk from its current peg to a new peg when d is the top disk on the current peg and the new peg holds one or more disks is defined as:
    • preconditions: at(d,f) AND clear(d) AND on(d,d1) AND top(d2,t) AND >(d2,d)
    • add list: at(d,t), top(d1,f), clear(d1), on(d,d2)
    • delete list: at(d,f), top(d,f), on(d,d1), top(d2,t), clear(d2)

Triangle Table For the Three Disk Tower of Hanoi Problem
Depiction of the current state
Start State
Changes after Move 1
Changes after Move 2
Changes after Move 3
Changes after Move 4
Changes after Move 5
Changes after Move 6
Changes
after Move 7
at(S, P1)
clear(S)
on(S,M)
empty(P3)
MoveOE
(S,P1,P3)
 
 
 
 
 
 
at(M,P1)
on(M,L)
empty(P2)
clear(M)
MoveOE
(M,P1,P2)
 
 
 
 
 
 
 at(S, P3)
MoveEO
(S,P3,P2)
 
 
 
 
at(L,P1)
 
 clear(L)
Empty(P3)
MoveEE
(L,P1,P3)
 
 
 
 
 
 
  at(S, P2)
MoveOE
(S,P2,P1)
 
 
 
 
 at(M,P2)
 
 
 clear(M)
MoveEO
(M,P2,P3)
 
 
 
 
 
 
  at(S, P1)
 
MoveEO
(S,P1,P3)
 
 
 
 
 at(L,P3)
 
 at(M,P3)
 at(S,P3)

The predicates that are true in the start state and upon which the plan depends are:

at(S, P1), at(M,P1), at(L,P1), clear(S), on(S,M), on(M,L),empty(P2), empty(P3),

which are simply the predicates listed in column 0 above.

An example of a Kernel

Now, consider the problem of determining of a tail of the plan is usable in some new situation - say one where:

at(S, P3), at(M,P2), at(L,P1), clear(S), clear(M), clear(L).

This is the third state listed above,  Now recall the definition of a Kernel of the triangle table.

A Kernel at i is the rectangular sub array of the table defined as:
[(row i, column 0), ( row i, column i-1 ), (row n, column 0 ), (row n, column i-1 ) ]
where n is the last row of the table.

In this case i is equal to 3 and the plan tail that begins with the 3rd move constitutes a solution to the new problem. The kernel indicated above by the cells that are a lighter gray.

A Problem for Reuse

Consider next the case where the starting state is one where L and M are on P1 but S is on P2. The goal is again the same - all disks should be stacked on P3. Should we try to use our previous plan to solve this new problem? Or, should a new plan be created? If we choose to use the existing plan then we need to change the starting situation into one which occurs in our existing plan. Note that this can be done in two ways. S can be moved to L1 which then reproduces the starting state of our existing plan. Or S can be moved to L3 which then reproduces the second state of our existing plan.

Planning - Table of Contents
 © Charles F. Schmidt