On Action Theories with Iterable First-Order Progression

Daxin Liu, Jens ClaßenAAAI 2025 · DOI

Introduction

In the field of artificial intelligence, the Situation Calculus serves as a foundational formal framework for reasoning about dynamic environments. A critical operation within this framework is progression: the process of updating an agent's knowledge base (KB) to reflect the state of the world after an action is performed. However, a significant theoretical hurdle has persisted since 1997, when researchers Lin and Reiter demonstrated that progressing a First-Order (FO) knowledge base can result in a Second-Order (SO) theory. Because SO logic is computationally intractable for standard automated reasoners, maintaining an agent's world model over time becomes a major bottleneck.

This paper, presented at AAAI-25, addresses this challenge by identifying new classes of action theories that guarantee progression remains within the realm of First-Order Logic. Crucially, the authors solve the problem of iterability, ensuring that the logic remains simple enough for continuous, long-term operation.

The Challenge of Iterability

While previous research identified specific "local-effect" or "normal" action theories that allow for FO progression, these solutions often lacked iterability. In these cases, the result of a single progression step might no longer satisfy the strict syntactic requirements needed for the subsequent step to remain First-Order.

In a real-world scenario where an agent performs a sequence of hundreds or thousands of actions, a non-iterable system eventually "breaks," reverting to complex SO logic. This paper provides the theoretical groundwork to prevent this breakage, allowing for indefinite sequences of actions while maintaining FO-representable knowledge bases.

Proposed Action Theories

The authors introduce two primary classes of action theories that support iterable FO progression:

1. Disjunctive Normal Action Theories

Building upon the concept of "normal actions," the authors expand the framework to accommodate disjunctions (e.g., "Object A is in the box OR Object B is in the box"). By utilizing Disjunctive Semi-Definitional (DSDEF) theories, they structure how predicates relate to one another, ensuring that the uncertainty introduced by actions does not push the logic into Second-Order complexity.

2. PANACK (Pan-Ackermann) Action Theories

PANACK theories represent the paper's primary contribution. This class is significantly broader than previous models, allowing for complex dependencies between fluents (properties that change over time), including circular dependencies. The authors distinguish between context conditions (the state required to trigger an effect) and effect descriptors (the specific change). They demonstrate that context conditions can be highly complex without compromising iterability, provided the effects themselves follow a structured format.

Technical Foundations: The Ackermann Lemma

The core technical mechanism used to prove these results is the Ackermann Lemma. This mathematical tool provides a method for eliminating second-order quantifiers. The authors prove that if an action theory begins in a "Pan-semi-definitional" form, the progression operation yields a result that can be systematically rewritten back into that same safe form. This "closed-loop" property is what guarantees iterability.

Key Results and Significance

The paper establishes several landmark proofs for the Situation Calculus:

  • Theorem 14: Formally proves that Disjunctive Normal action theories are iteratively FO progressable.
  • Theorem 21: Establishes that PANACK action theories—which allow for global effects and more expressive dependencies—are also iteratively FO progressable.
  • Subsumption: The authors show that PANACK strictly subsumes previous classes, such as "local-effect" theories, providing a more general and powerful framework for AI reasoning.

To validate these theoretical findings, the authors apply their framework to classic AI logic domains, such as the Exploding Bomb Domain (representing non-local effects) and the Box Domain (representing complex object dependencies). These examples demonstrate that even when actions have wide-ranging consequences or involve significant uncertainty, the knowledge base remains manageable.

Conclusion and Future Directions

By solving the iterability problem for a broad class of action theories, this work moves the Situation Calculus closer to practical application in complex, long-term agent deployments. While the current framework requires human designers to follow specific syntactic constraints, it provides a guaranteed path to efficient reasoning.

Future research directions include identifying even broader classes of FO-progressable theories and integrating these results into high-level agent programming languages like GOLOG. Additionally, these findings have significant implications for automated planning and verification, where agents must project their knowledge many steps into the future without facing a computational explosion.

Summary updated

BibTeX
@inproceedings{liu2025action,
  author = {Daxin Liu and Jens Claßen},
  title = {{On Action Theories with Iterable First-Order Progression}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i14.33649},
}
Figure