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