## Domains

Experiments were performed on four hand-coded domains (propositions + dynamics) and on random domains. Each hand-coded domain has propositions , and a dynamics which makes every state possible and eventually reachable from the initial state in which all propositions are false. The first two such domains, SPUDD-LINEAR and SPUDD-EXPON were discussed by Hoey et al. [29]; the two others are our own. The intention of SPUDD-LINEAR was to take advantage of the best case behaviour of SPUDD. For each proposition , it has an action which sets to true and all propositions , to false. SPUDD-EXPON, was used by Hoey et al. [29] to demonstrate the worst case behaviour of SPUDD. For each proposition , it has an action which sets to true only when all propositions , are true (and sets to false otherwise), and sets the latter propositions to false. The third domain, called ON/OFF, has one turn-on'' and one turn-off'' action per proposition. The turn-on-'' action only probabilistically succeeds in setting to true when was false. The turn-off action is similar. The fourth domain, called COMPLETE, is a fully connected reflexive domain. For each proposition there is an action which sets to true with probability (and to false otherwise) and , to true or false with probability 0.5. Note that can cause a transition to any of the states. Random domains of size also involve propositions. The method for generating their dynamics is detailed in appendix C. Let us just summarise by saying that we are able to generate random dynamics exhibiting a given degree of structure'' and a given degree of uncertainty. Lack of structure essentially measures the bushiness of the internal part of the ADDs representing the actions, and uncertainty measures the bushiness of their leaves.
Sylvie Thiebaux 2006-01-20