Currently, the automaton construction is not fully optimized. Even in the most complex examples, however, the construction never required more than a couple of minutes 7 .

## 7.2.1  Bomb In The Toilet

Bomb in the Toilet. The first domain we tackled is the classical bomb in the toilet, where there is no notion of clogging. We call the problem BT( p ), where the parameter p is the number of packages. The only uncertainty is in the initial condition, where it is not known which package contains the bomb. The goal is to defuse the bomb. The results for the BT problem are shown in Table 1. The columns relative to CMBP are the length of the plan (|P|), the number of cached belief states and the number of hits in the cache (\#BS and
\#NBS respectively), the time (expressed in seconds) needed for searching the automaton under Pentium/Linux (Time(L)) and under Sparc/Solaris (Time(S)). In the following, when clear from the context, the execution platform is omitted. The columns relative to CGP are the number of levels in the planning graphs ( | L |) and the sear time. The column relative to GPT is the search time.

| #BS/#BSH   | Time(L)   | Time[S]    | ll     | Time   | Time   |        |        |
|------------|-----------|------------|--------|--------|--------|--------|--------|
| BT(2)      | 2         | / 2        | 0.000  | 0.000  | 0.000  | 0.0 74 |        |
| BT(3)      | 0.000     | 0.000      | 0.000  | 0.0 77 |        |        |        |
| BT(4)      | 36        | 0.000      | 0.000  | 0.000  | 0.080  |        |        |
| BT(5       | 0.000     | 0.000      | 0.000  | 0.087  |        |        |        |
| BT(6       | 62        | 266        | 0.010  | 0.010  | 0.010  | 0.102  |        |
| BT[7       | 26        | 0.0 10     | 0000   |        |        |        |        |
| 0.030      |           |            |        |        |        |        |        |
| BT(8)      | 1496      | 0.030      | 0.030  | 0.020  | 0.230  |        |        |
| BT(9)      | 9         | 510 / 3463 | 0.0 70 | 0.070  | 0.020  |        |        |
| l          | 0.481     |            |        |        |        |        |        |
| BT(10)     | 10        | 1022       | 7862   | 0.150  | 0.140  | 0.020  | 1.0 18 |

The BT problem is intrinsically parallel, i.e. the depth of the planning graph is always one, because all the packages can be dunked at the same time. CGP inherits from GRAPH- PLAN the ability to deal with parallel actions efficiently, and therefore it is almost insensitive to the problem size. For this problem CGP outperforms both CMBP and GPT. Notice that the number of levels explored by CGP is always 1, while the length of the plan produced by CMBP and CGP grows linearly. CMBP performs slightly better than GPT.

Bomb in the Toilet with Clogging.  We call BTC( p ) the extension of the BT( p ) where dunking a package (always) clogs the toilet, flushing can remove the clogging, and no clogging is a precondition for dunking a package. Again, p is the number of packages.  The toilet is initially not clogged. With this modification, the problem no longer allows for a parallel solution. The results for this problem are listed in Table 2. The impact of the depth of the plan length becomes significant for all systems. Both CMBP and GPT outperform CGP.

In this case CMBP performs better than GPT, especially on large instances (see BTC(16)).