Possibility and Infinitary Nondeterminism in the Situation Calculus 1997

Abstract:  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 ...