Reconciling Situation Calculus and Fluent Calculus

Stephan Schiffel, Michael ThielscherAAAI 2006

Abstract

This paper establishes a formal bridge between Situation Calculus and Fluent Calculus, two prominent frameworks for reasoning about action in artificial intelligence. By introducing a translation between their respective axioms and a new semantics for the Golog programming language based on Fluent Calculus, the authors enable efficient "progression" of states. This approach overcomes the computational bottlenecks of traditional regression-based reasoning in long-running AI agent tasks.

Introduction

Reasoning about dynamic environments is a cornerstone of artificial intelligence. Agents must maintain an internal model of the world that updates as actions are performed. Historically, two primary formalisms have dominated this field: Situation Calculus (SC) and Fluent Calculus (FC). While SC defines the world through a history of actions, FC utilizes an explicit state representation. This paper addresses the computational limitations of Golog—a high-level agent programming language originally rooted in SC—by reconciling it with the state-update efficiencies of FC.

The Challenge: Regression vs. Progression

In Situation Calculus, determining the truth of a property (a "fluent") typically involves "regression," which requires looking back through the entire history of actions to the initial state. As an agent's history grows, this process becomes increasingly inefficient. Conversely, Fluent Calculus supports "progression," where the state is updated forward in time. By moving Golog from an SC-based foundation to an FC-based one, the authors aim to decouple reasoning complexity from the length of the action history.

Methods: Bridging the Calculi

The authors provide two primary technical contributions:

  1. Domain Translation: A mathematical mapping converts Successor State Axioms (SC) into State Update Axioms (FC) and vice versa. This ensures logical equivalence between domain descriptions in both frameworks.
  2. New Golog Semantics: The execution of Golog programs is redefined. Instead of tracking a program and a situation (history), the new semantics track the program, the current state, and a sequence of actions.
Table 1: Core constructs of the Golog programming language.

The Golog language includes several constructs for defining complex agent behaviors, as shown in Table 1. The new semantics allow these constructs to be evaluated against an explicit state rather than a historical situation. The translation assumes the domains are deterministic and have finite effects, meaning an action doesn't change an infinite number of properties at once.

Implementation and Results

The proposed framework was implemented as FluxGolog, a Prolog-based interpreter leveraging FLUX. FLUX is a logic programming language specifically designed for efficient state updates and handling incomplete information via constraint solving.

Key findings include:

  • Computational Efficiency: FluxGolog avoids the overhead of re-processing long action histories, making it significantly faster than traditional SC-based interpreters like LeGolog for long-running tasks. In the new FC-based Golog, checking a condition like "is the battery low?" only requires looking at the current state.
  • Formal Soundness: The authors proved that their translation is sound; a program running under the new FC-based semantics reaches the same logical conclusions as it would under the original SC-based system.
  • State as a First-Class Citizen: By introducing an explicit State term into Golog's transition semantics, the authors decouple the reasoning about the current world from the history of how the agent got there.

Limitations and Future Directions

The current translation is limited to deterministic domains. Real-world environments often involve non-deterministic actions (e.g., a robot attempting to pick up an object and failing). Future work aims to extend this to non-deterministic environments and "knowledge-based" reasoning, where agents must account for uncertainty and incomplete information. The authors intend to leverage FLUX’s existing constraint solvers to handle these "incomplete states" where the agent doesn't know everything about the world.

Summary updated

BibTeX
@inproceedings{schiffel2006reconciling,
  author = {Stephan Schiffel and Michael Thielscher},
  title = {{Reconciling Situation Calculus and Fluent Calculus}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure