Non-determinism and uncertainty in the situation calculus

The purpose of this article is to extend the situation calculus, a logical framework for the specification of theories of action and change, with acti ons that have a non-deterministic or uncertain nature. Our approach is base d upon the idea that actions may have a deterministic component, and a prob abilistic component. For example, the act of flipping a coin has a determin istic component (the actual coin toss) and an uncertain component (the outc ome). We extend the language of the situation calculus in order to make exp licit this distinction between these two action components. Furthermore, we provide means to reason about the outcomes of processes specified only in terms of deterministic action components (which we call behaviors). In part icular, we show how one can compute the probability that some fluent will h old after specific behavior is realized. An important feature of our approa ch is that the syntactic and semantic structure of actions and situations i s independent of the decomposition of actions into deterministic and uncert ain components. Thus, we inherit solutions to the frame problem, ramificati on problem, etc.