Research map / Learning theory and algorithms / Combinatorial and search optimization
A Syntactic Approach to Computing Complete and Sound Abstraction in the Situation Calculus
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a syntactic method to compute complete and sound abstractions in the situation calculus, via a linear integer situation calculus high-level theory and restricted refinement mappings over guarded-action low-level Golog programs.
Problem
No syntactic method exists to compute a sound and complete abstraction of a low-level basic action theory under a refinement mapping; prior work characterized it only via forgetting, which is computationally hard.
Approach
Introduces linear integer situation calculus as the high-level formalism, identifies guarded-action Golog programs and restrictions on refinement mappings (flat, complete, simply forgettable, consistent, syntax-irrelevant, propositional ∃-definable), and constructs the high-level initial KB, action precondition axioms and successor state axioms syntactically via a translation m^{-1}.
Key results
- Blocks world case study: the proposed syntactic procedure yields a high-level BAT (Holding, Num fluents) shown to be a complete and sound abstraction of the low-level blocks world BAT.
- Theorems establish that under flat, complete, executability-preserving refinement mappings, SSAs of a sound abstraction can be read off syntactically.
Limitations
- Requires restricted refinement mappings (six conditions), some of which are not syntactic and must be checked manually.
- Only illustrated on a single blocks world example; no implementation.
- Assumes the restricted refinement mapping is given rather than generated.
Experimental setup
Builds on: Banihashemi et al. abstraction framework for situation calculus and ConGolog Cialdea Mayer forgetting-based characterization Zhu et al. finitely many objects axiom
Closest papers by meaning
- Abstraction in Situation Calculus Action Theories (AAAI 2017 · similarity 0.94)
- Abstraction of Situation Calculus Concurrent Game Structures (AAAI 2024 · similarity 0.89)
- Situation Calculus Temporally Lifted Abstractions for Generalized Planning (AAAI 2025 · similarity 0.89)
- On Action Theories with Iterable First-Order Progression (AAAI 2025 · similarity 0.87)
- Learning Planning Abstractions from Language (ICLR 2024 · similarity 0.85)
- LTLf Synthesis on First-Order Agent Programs in Nondeterministic Environments (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.