Nondeterministic Actions and the Frame Problem

Craig Boutilier
Department of Computer Science
University of British Columbia
Vancouver, BC, CANADA, V6T 1Z4

Nir Friedman
Department of Computer Science
Stanford University
Stanford, CA 94305-2140, U.S.A.

We describe a logical system and methodology for the natural specification of nondeterministic actions. The logic combines elements of dynamic logic, process logic and the situation calculus and allows one to express alternative (actual and possible) paths or sequences of events. Our system permits a simple solution to the frame problem for nondeterministic actions that ``completes'' user-supplied theories of action. While drawing inspiration from Reiter's solution for the deterministic case, some of the main intuitions underlying this solution must be abandoned in the nondeterministic setting due to possible correlations among effects. We show our completion is unambiguous and faithful to our stated intuitions, and that in a deterministic setting our solution is equivalent to that of Reiter.

Appeared AAAI Spring Symposium on Extending Theories of Action, Stanford, March 1995

Return to List of Papers