# Abstraction of Nondeterministic Situation Calculus Action Theories -- Extended Version

arXiv: https://arxiv.org/abs/2305.14222 · HTML: https://mlsanity.com/paper/2305.14222/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 58 references that are in the map.
- First posted on arXiv 20 May 2023.

## Builds on (most cited first, 4 of 4)

- [Bounded Situation Calculus Action Theories](https://mlsanity.com/paper/1509.02012/) (2015)
- [Generalized Planning: Non-Deterministic Abstractions and Trajectory Constraints](https://mlsanity.com/paper/1909.12135/) (2019)
- [Stochastic Fairness and Language-Theoretic Fairness in Planning on Nondeterministic Domains](https://mlsanity.com/paper/1912.11203/) (2019)
- [Multi-tier Automated Planning for Adaptive Behavior (Extended Version)](https://mlsanity.com/paper/2002.12445/) (2020)

## Built on by (most cited first, 2 of 2)

- [Abstracting Situation Calculus Action Theories](https://mlsanity.com/paper/2410.14712/) (2024)
- [Spatio-temporal Value Semantics-based Abstraction for Dense Deep Reinforcement Learning](https://mlsanity.com/paper/2405.15829/) (2024)

## Abstract (arXiv)

We develop a general framework for abstracting the behavior of an agent that operates in a nondeterministic domain, i.e., where the agent does not control the outcome of the nondeterministic actions, based on the nondeterministic situation calculus and the ConGolog programming language. We assume that we have both an abstract and a concrete nondeterministic basic action theory, and a refinement mapping which specifies how abstract actions, decomposed into agent actions and environment reactions, are implemented by concrete ConGolog programs. This new setting supports strategic reasoning and strategy synthesis, by allowing us to quantify separately on agent actions and environment reactions. We show that if the agent has a (strong FOND) plan/strategy to achieve a goal/complete a task at the abstract level, and it can always execute the nondeterministic abstract actions to completion at the concrete level, then there exists a refinement of it that is a (strong FOND) plan/strategy to achieve the refinement of the goal/task at the concrete level.