# Intellectics Group: Technical Report 97-06

## Possibility and Infinitary Nondeterminism in the Situation Calculus

### Hesham Khalil

This paper presents a version of the Situation Calculus
with improved capabilities in formalizing and reasoning about
nondeterministic actions. Instead of describing the effects of such
actions by posting constraints on their possible outcomes, as is
typically done in the common Situation Calculus, we provide means of
describing actions by the set of their possible total effects. An
important advantage of this approach is its allowing for reasoning
about the possible (as opposed to the necessary) postconditions of
actions. Furthermore, our method does not require enumerating the
possible outcomes of an action, so that actions with infinitary
effects, like randomly picking an object from a bag containing unknown
objects, can be modeled without difficulty. Based on our version of
the Situation Calculus, we present a high-level first-order language
for specifying queries about the possible courses of given action
sequences and a simple regression procedure for evaluating such
queries.