
| Tires   |
|---------|
| l       |
| 2       |
|         |
| 4       |
| 5       |
| 6       |
| 7       |
| 8       |
| g       |
| 10      |

| problem   | # actions   | GA M        | RIFO         |             |
|-----------|-------------|-------------|--------------|-------------|
| stack_20  | 800         | 0.31        | = 16 %       | 1.44 = 75 % |
| stack_40  | 3 200       | 1.57 = 7 %  | 18.77 = 90 % |             |
| stack_60  | 7 200       | 4.40 = 4 %  | 93.10 = 94 % |             |
| stack_80  | 1 2800      | 9.60 = 3 %  | 23.60 = 96 % |             |
| parcplan  | 1 960       | 0.86 = 12 % | 5.52 = 76 %  |             |

| search algorithm   |
|--------------------|
| 0.13 = 7 %         |
| 0.51 = 2 %         |
| 1.15 = 1 %         |
| 2.33 = 1 %         |
| 0.83 = 11 %        |

performance of GAM and RIFO. It also indicates that even the hardest planning problems can become easy if they are structured and decomposed in the right way.

Figure 11: Distribution of problem-solving time on blocks world examples between GAM,
RIFO, and the search algorithm, which comprises the time to build and search the planning graph.  The remaining fraction of total problem-solving time, which is not shown in the table, is spent on parsing and instantiating the operators.

## 5.2.2  The Tyreworld

The tyreworld problem, originally formulated by Stuart Russell, asks a planner to find out how to replace a flat tire. It is easily solved by IPP within a few milliseconds. The problem becomes much harder if the number of flat tires is increasing, cf. Figure 12. Figure 12:  IPP in the Tyreworld. The numbers in parentheses show the time steps, followed

by the number of actions in the generated plan. The last column compares the search spaces. The number before the slash shows the "number of actions tried" parameter for the plain IPP planning algorithm, while the number following the slash shows the "number of actions tried" for IPP using GAM, RIFO, and the linearization of entries in the agenda.  A dash means that the "number of actions tried" is unknown because IPP failed in solving the corresponding planning problem.

| # actions   | IPP             | +G+R         | +G+R+L       | Search Space   |
|-------------|-----------------|--------------|--------------|----------------|
| 26          | 0.10 (12/19)    | 0.15 (14/19) | 0.16 (17/19) | 1298/88        |
| 59          | 17.47 (18/30)   | 0.41 (24/32) | 0.32 (30/34) | 1290182/210    |
| 108         | 2.87 (32/44)    | 0.63 (41/46) | -/366        |                |
| 173         | 1.12 (52/60)    | -/565        |              |                |
| 254         | 1.93 (63/73)    | -/807        |              |                |
| 353         | 3.42 (73/85)    | -/1092       |              |                |
| 464         | 4.81 (84/98)    | -/14 20      |              |                |
| 593         | 8.07 ( 95/121 ) | -/1791       |              |                |
| 738         | 1.27 (106/124)  | -/ 2205      |              |                |
| 89          | 16.89 (118/136) | -/2662       |              |                |
