
| GPT           |                  |             |         |       |
|---------------|------------------|-------------|---------|-------|
| P             | B S / # B SH     | Time        | ime     |       |
| BTUC[2]       | 0.000            | 0.0 76      |         |       |
| BTUC(3)       | 14 / 23          | 0.000       | 0.0 78  |       |
| BTUC(4)       | 7                | 30 / 6 1    | 0.010   | 0.085 |
| BTUC(5)       | 9                | 62 / 150    | 0.010   | 0.098 |
| BTUC(6)       | l l              | 126 / 347   | 0.030   | 0.128 |
| BTUC(8)       | 0.205            |             |         |       |
| 13            | 254 / 796        | 0.050       |         |       |
| 10            | 1844             | 0.170       | 0.380   |       |
| BTUC(9)       | 1022             | 4149        | 0.310   | 0.812 |
| BTUC(10)      | 19               | 2046 / 9190 | 0.720   | 1828  |
| BTUC(16)   31 | 1310 70 / 921355 | 98.270      | 486.252 |       |

Table 5: Results for the BTUC problems.

![0_image_0.png](0_image_0.png)

In the problem RING(r), where r is the number of rooms, the uncertainty is only in the initial condition: both the position of the robot and the status of the windows can be uncertain.  These problems do not have a parallel solution, and have a large number of initial states ( r * 3 r ), corresponding to full uncertainty on the position of the robot and on the status of each window. The results® are reported on the left in Table 6. CMBP outperforms

| GP T       |                |             |        |        |         |        |        |       |
|------------|----------------|-------------|--------|--------|---------|--------|--------|-------|
| H          |                |             |        |        |         |        |        |       |
| P          | #BS/#BSH       | Time        | Time   | Time   |         |        |        |       |
| RING(2)    | 0.000          | c           | 0.0 70 | 0.085  |         |        |        |       |
| 8 / 24     | CP on RING[5]  |             |        |        |         |        |        |       |
| RING(3)    | 78             | 0.020       | 0.087  | IS     | ][      |        | Time   |       |
| RING[1]    | l l            | 80 / 240    | 00000  | 0.392  | 5       | 0.0 10 | 9      | 0.020 |
| RING(5)    | 242 /          |             |        |        |         |        |        |       |
| 11         | 726            | 0.120       | 1.150  | 5      | 0.060   | 9      | 0.140  |       |
| RING[6]    | 17             | 728 / 2184  | 0.3 70 | 6.620  | 5       | 0.420  | 9      | 1.950 |
| RING(7)    | 20             | 2186 / 6558 | 1.420  | 23.636 | 6.150   | g      | 59.680 |       |
| R IN G(8)  | 23             | 6560        | 19680  | 4.950  | 105.158 | 16     |        |       |
| RING[9]    | 19682          | 59999999    | 27.330 |        |         |        |        |       |
| R IN G[10] | 59048 / 177144 | 106.8 70    |        |        |         |        |        |       |
| 29         |                |             |        |        |         |        |        |       |

both CGP and GPT, although GPT performs much better than CGP. Both CGP and GPT
suffer from the increasing complexity of the problem. On the right in Table 6, we plot (for the RING(5) problem) the dependency of CGP on the number of initial states combined with the number of levels to be explored (different goals were provided which require the exploration of different levels). It is clear that the number of initial states and the depth of the search are both critical factors for CGP.