KR2021Proceedings of the 18th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning

Online event. November 3-12, 2021.

Edited by

ISSN: 2334-1033
ISBN: 978-1-956792-99-7

Sponsored by
Published by

Copyright © 2021 International Joint Conferences on Artificial Intelligence Organization

The Nondeterministic Situation Calculus

  1. Giuseppe De Giacomo(DIAG, Università degli Studi di Roma "La Sapienza", Rome, Italy)
  2. Yves Lespérance(EECS, York University, Toronto, Canada)


  1. Reasoning about actions and change, action languages
  2. KR and autonomous agents and multi-agent systems


The standard situation calculus assumes that atomic actions are deterministic. But many domains involve nondeterministic actions, with problems such as fully observable nondeterministic (FOND) planning and high-level program execution requiring solutions. Various approaches have been proposed to accommodate nondeterminism on top of the standard situation calculus language, for instance by introducing nondeterministic programs as in Golog and ConGolog. But a key problem in these approaches is that they don’t clearly distinguish between choices that can be made by the agent and choices that are made by the environment, i.e., angelic vs. devilish nondeterminism. In this paper, we propose a simple extension to the standard situation calculus that accommodates nondeterministic actions and preserves Reiter’s solution to the frame problem and answering projection queries through regression. We also provide a formalization of FOND planning and show how ConGolog high-level program execution in nondeterministic domains can be defined.