On the Progression of Situation Calculus Basic Action Theories: Resolving a 10-year-old Conjecture

Stavros Vassos, Hector J. LevesqueAAAI 2008

Introduction

In the field of Artificial Intelligence, the Situation Calculus serves as a foundational formal language for representing and reasoning about dynamical systems. Within this framework, a Basic Action Theory (BAT) defines the initial state of the world and the logic governing how actions transform that state. As an autonomous agent interacts with its environment, its history of actions grows, making reasoning increasingly complex. To maintain efficiency, researchers utilize "progression"—a process that updates the agent's knowledge base to reflect the current state, effectively discarding the explicit history of past actions.

The Lin and Reiter Conjecture

In 1997, Lin and Reiter introduced two primary methods for progression:

  1. LR-progression: A theoretically complete method that often necessitates second-order logic. While logically robust, second-order logic is computationally expensive and difficult to implement in standard reasoning engines.
  2. FO-progression: A method restricted to first-order logic. While more computationally tractable, Lin and Reiter conjectured that FO-progression was "too weak," potentially losing critical information about future possibilities that the original theory possessed.

For a decade, the relationship between these two methods remained a fundamental open question in the community. This paper provides the definitive resolution to this conjecture.

Proving the Theoretical Weakness

The authors first confirm the Lin and Reiter conjecture by demonstrating that FO-progression is indeed strictly weaker than LR-progression. To achieve this, they constructed a specific Basic Action Theory, denoted as $D_1$, which serves as a counter-example.

The failure of FO-progression stems from what the authors describe as the "unnamed object" problem. In first-order logic, it is difficult to constrain "extra" or "ghostly" objects that may exist in a mathematical model but are not explicitly named or reachable through standard counting. The authors showed that FO-progression "forgets" certain constraints on these unnamed objects. Consequently, while the original theory might know that a certain property must hold in the future, the FO-progressed version loses this foresight. This formally proves Theorem 2: FO-progression is technically incomplete.

The Silver Lining: Practical Correctness

Despite the theoretical incompleteness, the paper offers a significant "silver lining" for AI practitioners. The authors identify a massive class of sentences, $\mathcal{L}^Q_{S_\alpha}$, for which FO-progression is perfectly accurate.

Using advanced tools from model theory—specifically the Compactness Theorem and the Upward Löwenheim-Skolem Theorem—the authors prove Theorem 4. This theorem states that for any query within the $\mathcal{L}^Q_{S_\alpha}$ class, FO-progression yields the exact same results as the more complex LR-progression. Crucially, this class includes:

  • State Invariants: Questions regarding whether certain conditions will always hold (e.g., "Will the robot remain within the safety zone?").
  • Possibility Queries: Questions regarding reachability (e.g., "Is there a sequence of actions to achieve the goal?").

Since these represent the vast majority of queries used in automated planning and high-level program execution, the theoretical weakness of FO-progression is often irrelevant in practical applications.

Conclusion

This research reconciles a decade-long gap between theory and practice in the Situation Calculus. By proving the Lin and Reiter conjecture, the authors clarify the logical boundaries of first-order reasoning. Simultaneously, by establishing the correctness of FO-progression for the $\mathcal{L}^Q_{S_\alpha}$ class, they provide a rigorous justification for its continued use in real-world AI systems.

Future work remains in addressing the potential for FO-progression to result in infinite sets of sentences, which poses a challenge for finite implementation. Additionally, exploring even broader classes of sentences or specific types of action theories where this weakness never manifests remains a promising avenue for further investigation.

Summary updated

BibTeX
@inproceedings{vassos2008progression,
  author = {Stavros Vassos and Hector J. Levesque},
  title = {{On the Progression of Situation Calculus Basic Action Theories: Resolving a 10-year-old Conjecture}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure