
| Low Unc   | High Unc   |         |         |           |
|-----------|------------|---------|---------|-----------|
| BM T C    | CM BP      | GP      | 'M BP   | GP        |
| (p t)     | Time       | Time    | Time    | Time      |
| [ 2 , 2 ] | 0.000      | 0.0 79  | 0.0 10  | 0.0 .0 .0 |
| (2,2)     | 0.010      | 0.087   | 0.0 10  | 0.091     |
| [ 2 , 2 ] | 0.000      | 0.105   | 0.020   | 0.121     |
| (5,2)     | 0.040      | 0.146   | 0.040   | 0.198     |
| ( 2 , 2 ) | 0.080      | 0 2 2 7 | 0.0 70  | 0.3 76    |
| (7,2)     | 0.190      | 0.441   | 0.200   | 0.850     |
| ( 8 , 2 )
(9 , 2 )           | 0.390      | 0.922   | 0.400   | 1.966     |
| 0.910     | 2.211      | 0.950   | 7.743   |           |
| (10,2)    | 1.850      | .169    | .900    | 10.620    |
| ( 2 , 4 ) | 0.000      | 0.109   | 0.0 10  | 0.121     |
| [ 3 , 4 ] | 0.010      | 0.156   | 0.040   | 0.284     |
| [4]       | 0.050      | 0.2 70  | 0.100   | 1.016     |
| (5 ,4 )   | 0.616      | 0.240   | 3.282   |           |
| 0.180     |            |         |         |           |
| (6 ,4 )   | 0.3 70     | 1.435   | 0.460   | 9.3 74    |
| ( 7 , 4 ) | 1.080      | 3.484   | 1.190   | 27.348    |
| 2.700     | 8.767      | 2.830   |         |           |
| [ 4 , 4 ] | 72 .344    |         |         |           |
| ( 9 , 4 ) | 8.9 70     | 23.858  | 6.920   | 180.039   |
| 4.210     | 59.966     | 14.690  | 40.308  |           |
|           |            |         |         |           |
| ( 2 , 6 ) | 0.0 1 0    | 0.303   | 0.060   | 0.482     |
| 0.050     | 0.562      | 0.260   | 17.406  |           |
| (3 , 6 )  |            |         |         |           |
| ( 6 )     | 0.310      | 1.354   | 0.620   |           |
| 1.110     | 3.25.7     | 2.060   | 74 .623 |           |
| (5,6)     |            |         |         |           |
| (6 , 6 )  | 3.400      | 8.691   | 4.660   | 243.113   |
| ( 7 , 6 ) | 8.910      | 25.677  | 10.430  | 701.431   |
| 21.240    |            |         |         |           |
| (8,6)     | 68.427     | 23.860  |         |           |
| ( 9 , 6 ) | 19.880     | 29.000  | 54.190  |           |
| [10,6]    | 13.680     | 486.969 | 18.590  |           |

uncertainty, CGP is almost unable to solve what were trivial problems.  GPT performs better than CGP, but it suffers from the explicit representation of the search space. Bomb in the Toilet with Uncertain Clogging.  The BTUC( p ) domain is the domain described in Section 2, where clogging is an uncertain outcome of dunking a package. This kind of problem cannot be expressed in CGP. The results for CMBP and GPT are reported in Table 5. Although CMBP performs better than GPT (by a factor of two to three), there is no significant difference in the behavior. It is interesting to compare the results of CMBP for the BTC and BTUC problems. For GPT a slight difference is noticeable, resulting from the increased branching factor in the search space due to the uncertainties in the effects of action executions. In the performance of CMBP, the number of uncertainties is not a direct factor - for example, in the BTC(16) and BTUC(16), the performance is almost the same.

## 7.2.2  Ring Of Rooms

Simple Ring of Room.  We considered another domain, where a robot can move in a ring of rooms. Each room has a window, which can be either open, closed or locked. The robot can move (either clockwise or counterclockwise), close the window of the room where it is, and lock it if closed. The goal is to have all windows locked.