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

Introduction

In the field of Artificial Intelligence, abstraction is a fundamental technique used to manage complexity. It involves simplifying a detailed "low-level" environment—such as a robot's specific joint angles and sensor data—into a "high-level" model consisting of discrete actions like "pick up the block." This reduction is critical for solving problems in massive or infinite state spaces, particularly in generalized planning and the verification of multi-agent systems.

While the Situation Calculus provides a robust logical framework for representing dynamic worlds, creating these abstractions has historically been a manual and error-prone process. Previous theoretical approaches relied on a logical operation known as "forgetting," which is computationally expensive and often impractical for automated systems. This paper introduces a novel syntactic method to automatically compute sound and complete abstractions, bypassing the need for general logical forgetting.

The Problem: The Bottleneck of Manual Abstraction

An abstraction is considered sound if the high-level model accurately reflects the possibilities of the low-level world, and complete if it captures all relevant information for the task at hand. In the Situation Calculus, defining these properties is one thing; constructing a model that satisfies them is another. Existing methods require human experts to manually derive high-level axioms or use heavy-duty semantic operations. The authors address this by seeking a syntactic approach: a set of transformation rules that can rewrite low-level axioms into high-level ones directly.

Methodology

To achieve a tractable syntactic translation, the authors introduce several key components:

1. Linear Integer Situation Calculus ($L^{LIA}_{sc}$)

The researchers propose a variant of the Situation Calculus that incorporates Linear Integer Arithmetic (LIA). This allows the high-level theory to naturally handle numerical values—referred to as functional fluents—and counting, which are essential for real-world applications where resources or quantities are tracked.

2. Guarded Actions

The "secret sauce" of this approach is the restriction of low-level actions to a specific format called "guarded actions." These are Golog programs (agent programming languages) structured as: check a condition $\psi$, then perform action $A$. This specific structure makes the mathematical transformation into high-level logic manageable.

3. Refinement Mappings

A refinement mapping acts as the bridge between levels, defining how high-level properties (fluents) and actions relate to low-level formulas and programs. The authors focus on mappings that are "flat" and "complete," meaning every high-level action has a clearly defined effect (enabling, disabling, or invariant) on a fluent.

4. Syntactic Transformation Rules

The core contribution is a set of formulas (detailed in Theorem 3) that take low-level Successor State Axioms (describing world changes) and Action Precondition Axioms and transform them into their high-level counterparts.

Key Insights and Results

The major breakthrough of this work is the realization that by restricting the refinement mapping and action types, one can avoid the computational cost of logical forgetting.

Theorem 3: Direct Construction

The authors prove that if a refinement mapping is flat, complete, and preserves executability (meaning high-level plans have valid low-level counterparts), the high-level knowledge base can be directly constructed from the low-level theory. This ensures that the resulting abstraction is both sound and complete relative to the mapping.

Practical Demonstration: Blocks World

To validate their theory, the authors applied the method to the Blocks World domain, a classic AI benchmark. They demonstrated how a complex theory tracking the exact coordinates and identities of every block could be syntactically transformed into a high-level "counting" version that only tracks the number of blocks in specific configurations. This transition from first-order logic to a numerical abstraction highlights the power of the $L^{LIA}_{sc}$ framework.

Limitations and Future Work

While this research marks a significant step toward automated abstraction, several challenges remain:

  • Mapping Discovery: The current method requires a human to provide the refinement mapping. Future research will focus on algorithms that can automatically discover these mappings.
  • Logical Constraints: The reliance on Linear Integer Arithmetic, while powerful, may not suffice for domains involving non-linear physics or continuous variables.
  • Automation of Checks: Some requirements for the mapping currently require semantic verification. The authors suggest moving toward purely tactical or automated syntactic checks to further streamline the process.

Conclusion

By shifting the focus from semantic forgetting to syntactic transformation, this paper provides a practical pathway for generating high-level models in the Situation Calculus. This work lays the groundwork for more efficient planning and verification in complex, numerically-driven environments.

Summary updated

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