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.
Sylvie Thiebaux 2006-01-20