A Formal Account of Nondeterministic and Failed Actions James P. Delgrande Hector J. Levesque
Abstract
Nondeterminism is pervasive in all but the simplest action domains: an agent may ?ip a coin or pick up a different object than intended, or an action may fail and may fail in different ways. In this paper we provide a qualitative theory of nondeterminism. The account is based on an epistemic extension to the situation calculus that accommodates sensing actions. Our position is that nondeterminism is an epistemic phenomenon, and that the world is most usefully regarded as deterministic. Nondeterminism arises from an agent’s limited awareness and perception. The account offers several advantages: an agent has a set of categorical (as opposed to probabilistic) beliefs, yet can deal with equallylikely outcomes (such as in ?ipping a fair coin) or with outcomes of differing plausibility (such as an action that may on rare occasion fail).