Domains

Experiments were performed on four hand-coded domains (propositions + dynamics) and on random domains. Each hand-coded domain has $n$ propositions $p_i$, 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 $p_i$, it has an action $a_i$ which sets $p_i$ to true and all propositions $p_j$, $1 \leq j < i$ to false. SPUDD-EXPON, was used by Hoey et al. [29] to demonstrate the worst case behaviour of SPUDD. For each proposition $p_i$, it has an action $a_i$ which sets $p_i$ to true only when all propositions $p_j$, $1 \leq j < i$ are true (and sets $p_i$ 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-$p_i$'' action only probabilistically succeeds in setting $p_i$ to true when $p_i$ was false. The turn-off action is similar. The fourth domain, called COMPLETE, is a fully connected reflexive domain. For each proposition $p_i$ there is an action $a_i$ which sets $p_i$ to true with probability $i/(n+1)$ (and to false otherwise) and $p_j$, $j\neq i$ to true or false with probability 0.5. Note that $a_i$ can cause a transition to any of the $2^n$ states. Random domains of size $n$ also involve $n$ 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.