A Syntactic Approach to Computing Complete and Sound Abstraction in the Situation Calculus

Liangda Fang, Xiaoman Wang, Zhang Chen, Kailun Luo, Zhenhe Cui, Quanlong Guan

TL;DR

This paper introduces a first-of-its-kind syntactic method to automatically compute sound and complete abstractions within the Situation Calculus. By restricting low-level actions to a specific "guarded" format and utilizing linear integer arithmetic, the authors provide a set of logical rules to transform complex, low-level action theories into simplified, high-level versions suitable for efficient planning and verification.

What Problem Does This Paper Address?

In Artificial Intelligence, abstraction is the process of simplifying a complex "low-level" world (like a robot's joint torques and sensor readings) into a "high-level" model (like "pick up the block"). This reduction is essential for solving problems in massive or infinite state spaces, such as generalized planning or multi-agent system verification.

The Situation Calculus is a powerful logical framework used to represent these dynamic worlds. While researchers have previously defined what makes an abstraction "sound" (the high-level model doesn't lie about what's possible) and "complete" (the high-level model captures everything relevant), actually building these models has remained a manual, error-prone task. Existing theoretical methods rely on "forgetting"—a computationally expensive logical operation—making them impractical for automated use. This paper seeks a syntactic approach: a way to calculate high-level axioms directly from low-level ones using a set of transformation rules.

Methods

The authors bridge the gap between levels using several novel components:

  1. Linear Integer Situation Calculus ($L^{LIA}_{sc}$): They propose a variant of the Situation Calculus that uses Linear Integer Arithmetic (LIA) as its backbone. This allows the high-level theory to handle numerical values (functional fluents) and counting naturally.
  2. Guarded Actions: They identify a specific class of Golog programs (agent programming languages) called "guarded actions." These actions are restricted to the form: check a condition $\psi$, then perform action $A$. This restriction is the "secret sauce" that makes the syntactic translation mathematically tractable.
  3. Refinement Mappings: They define a mapping that tells the system how high-level fluents (properties) and actions relate to low-level formulas and programs.
  4. Syntactic Transformation Rules: The core contribution is a set of formulas (Theorem 3) that take low-level Successor State Axioms (which describe how the world changes) and Action Precondition Axioms and "re-write" them into high-level versions.

Datasets

As a theoretical paper in formal logic and knowledge representation, this work does not use traditional training datasets. Instead, it uses the Blocks World domain—a classic AI benchmark involving stacking blocks on a table—as a running example to demonstrate how a complex low-level theory (tracking every block's position) can be syntactically abstracted into a high-level theory (tracking only the number of blocks in a specific tower).

Key Insights and Ideas

  • From Semantics to Syntax: The major "aha moment" is realizing that if you restrict the refinement mapping to be "flat" and "complete" (meaning every high-level action is clearly an enabling, disabling, or invariant force for a fluent), you can bypass the need for general logical "forgetting."
  • Handling Numbers: Unlike previous abstraction frameworks that focused mostly on Boolean (true/false) properties, this method explicitly handles functional fluents (like "the number of blocks"). This is crucial for real-world applications where resources or counts matter.
  • Executability Preservation: The authors identify that for an abstraction to be truly useful, the mapping must preserve "executability"—if a sequence of high-level actions is possible in the abstract model, there must be a corresponding valid sequence in the concrete world.

Key Results

  • Theorem 3 (The Main Result): The authors prove that if a refinement mapping meets certain criteria (flat, complete, and executability-preserving), the high-level initial knowledge base, preconditions, and successor state axioms can be directly constructed from the low-level theory.
  • Soundness and Completeness: They formally prove that their syntactic construction results in a high-level theory that is both a sound and complete abstraction of the low-level theory relative to the mapping.
  • Practical Example: They successfully demonstrate the approach by deriving a high-level "counting" version of the Blocks World from a standard first-order logic version.

Limitations and Future Work

  • Mapping Requirement: The method assumes the "refinement mapping" is already provided by a human expert. A major next step is developing algorithms to automatically discover these mappings.
  • Restricted Logic: The current approach is tied to Linear Integer Arithmetic. While powerful, it may not cover domains requiring non-linear math or continuous physics.
  • Non-Syntactic Checks: Some of the requirements for the mapping (like "completeness") are currently verified semantically. The authors suggest that future work should focus on making these checks purely tactical or automated.
  • Complexity: While more efficient than general "forgetting," the syntactic transformation still involves logical operations that could become complex for very large theories. Implementing this in a practical tool is a suggested future direction.

Summary updated

Abstract

Abstraction is an important and useful concept in the field of artificial intelligence. To the best of our knowledge, there is no syntactic method to compute a sound and complete abstraction from a given low-level basic action theory and a refinement mapping. This paper aims to address this issue. To this end, we first present a variant of situation calculus, namely linear integer situation calculus, which serves as the formalization of high-level basic action theory. We then migrate Banihashemi, De Giacomo, and Lesperance’s abstraction framework to one from linear integer situation calculus to extended situation calculus. Furthermore, we identify a class of Golog programs, namely guarded actions, so as to restrict low-level Golog programs, and impose some restrictions on refinement mappings. Finally, we design a syntactic approach to computing a sound and complete abstraction from a low-level basic action theory and a restricted refinement mapping.
BibTeX
@inproceedings{fang2025syntactic,
  author = {Liangda Fang and Xiaoman Wang and Zhang Chen and Kailun Luo and Zhenhe Cui and Quanlong Guan},
  title = {{A Syntactic Approach to Computing Complete and Sound Abstraction in the Situation Calculus}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i14.33635},
}
Figure