
## 5.2.3  The Tower Of Hanoi

A surprising result is obtained in the tower of hanoi domain.  In this domain, a stack of discs has to be moved from one peg to a third peg with an auxiliary second peg between them, but never a larger disc can be put onto a smaller disc. In the case of three discs d 1, d 2, d 3 of increasing size, the goals are stated as on(d3,peg3), on(d2,d3), on(d1,d2). GAM returns the following agenda, which correctly reflects the ordering that the largest disc needs to be put in its goal position first.

1: on(d3,peg3) 2: on(d2,d3) 3: on(d1,d2)
The goal agenda leads to a partition into subproblems that corresponds to the recursive formulation of the problem solving algorithm, i.e., to solve the problem for n discs, the planner first has to solve the problem for n - 1 discs, etc. For the first entry, a plan of 4 actions (time steps 0 to 3 below) is generated, which achieves the goal on(d3,peg3),8  Then a plan of 2 actions (time steps 4 and 5) achieves the goals on(d3,peg3) and on(d2,d3) with on(d3,peg3) holding already in the initial state.  Finally, a one-step plan (time step 6) is generated that moves the third disc with the other two discs being already in the goal position.

| time step 0:   | move(d1,d2,peg3)   | time step 4:     | move(d1 ,d2 ,peg1)   |
|----------------|--------------------|------------------|----------------------|
| time step 1:   | move(d2,d3,peg2)   | move(d2,peg2,d3) |                      |
| time step 5:   |                    |                  |                      |
| time step 2:   | move(d1,peg3,d2)   | time step 6:     | move(d1 ,peg1,d2)    |
| time step 3:   | move(d3,peg1,peg3) |                  |                      |

Surprisingly, IPP is not able to benefit from this information, but runtime of IPP using GA M is exploding dramatically for increasing numbers of discs, see Figure 13.

| discs    | IPP   | IPP +G                           | U CP OP   | UCP On subproblems   |                    |
|----------|-------|----------------------------------|-----------|----------------------|--------------------|
| #actions |       |                                  |           |                      |                    |
| 2        | 21    | 0.02                             | 0.02      | 0.12 (27)            | 06 (17) + 0.02 (6) |
| 0.08     | 0.07  | 0.18 (48) + 0.06 (13) + 0.01 (6) |           |                      |                    |
| 3        | 48    | 8.00 ( 2291 )                    |           |                      |                    |
| 4        | 90    | 0.33                             | 0.25      |                      |                    |
| 5        | 150   | 1.57                             | 3.10      |                      |                    |
| 6        | 231   | 9.71                             | 88.45     |                      |                    |
| 2339.94  |       |                                  |           |                      |                    |
| 36       | 69.44 |                                  |           |                      |                    |

Figure 13: Runtimes of IPP with and without the goal agenda on hanoi problems compared to UCPOP without agenda and UCPOP on the agenda subproblems using ZLIFO and the ibf control strategy.