The situation calculus is a popular technique for
reasoning about action and change. However, its restriction to a
first-order syntax and pure deductive reasoning makes it unsuitable in
many contexts.  In particular, we often face uncertainty, due either
to lack of knowledge or to some probabilistic aspects of the world.
While attempts have been made to address aspects of this problem, most
notably using nonmonotonic reasoning formalisms, the general problem
of uncertainty in reasoning about action has not been fully dealt with
in a logical framework.  In this paper we present a theory of action
that extends the situation calculus to deal with uncertainty.  Our
framework is based on applying the <I>random-worlds</I> approach of
<A HREF="bghk.html">[BGHK]</A> to a situation calculus ontology,
enriched to allow the expression of probabilistic action effects.  Our
approach is able to solve many of the problems imposed by incomplete
and probabilistic knowledge within a unified framework. In particular,
we obtain a <I>default</I> Markov property for chains of actions, a
derivation of conditional independence from irrelevance, and a simple
solution to the frame problem.<p>