Concurrent Actions in the Situation Calculus

Fangzhen Lin, Yoav Shoham

Abstract

This paper addresses the limitations of the classical Situation Calculus in modeling concurrent actions. By introducing a "global action" sort and establishing a formal symmetry between situations and actions, the authors resolve the "action-oriented frame problem." This allows for the correct inheritance or cancellation of individual action effects when performed simultaneously. The framework is evaluated using commonsense reasoning benchmarks and demonstrates how nonmonotonic logic can simplify the representation of complex, concurrent domains.

Introduction

In the early 1990s, the Situation Calculus, pioneered by John McCarthy, served as the primary framework for representing change in artificial intelligence. However, its design was fundamentally sequential, making it difficult to formalize scenarios where multiple actions occur simultaneously—such as moving a block while painting it. This paper proposes an extension to the calculus that treats concurrency as a first-class citizen by introducing structural symmetry into the logic.

The Dual Frame Problem

The authors identify a fundamental asymmetry in the traditional framework: situations are "rich" objects defined by many fluents (properties), while actions are "poor," primitive objects. This imbalance gives rise to two distinct versions of the infamous Frame Problem.

Visual representation of the fluent-oriented, action-oriented, and generalized frame problems.
  1. The Fluent-Oriented Frame Problem: This concerns how we determine which properties persist when an action occurs (e.g., if a block is painted, the status of a nearby door should remain unchanged).
  2. The Action-Oriented Frame Problem: This concerns how we determine which action effects are inherited when multiple actions happen at once (e.g., if one paints a block and closes a door simultaneously, the block should still end up painted).

By addressing these together, the authors propose a solution to the Generalized Frame Problem, ensuring that both properties and action effects are correctly propagated through time.

Methodology: Symmetry and Global Actions

The core innovation is the introduction of a "global action" sort ($g$), which is essentially a set of primitive actions ($a$). The authors introduce a binary predicate $In(a, g)$, which mirrors the traditional $H(p, s)$ predicate (which asserts that fluent $p$ holds in situation $s$).

This creates a powerful structural analogy: Situations : Fluents :: Global Actions : Primitive Actions. By treating actions with the same complexity as situations, the mathematics for concurrency becomes more natural and symmetric.

Achieving Epistemological Completeness

To ensure the theory can uniquely predict the resulting state after a concurrent action, the authors explore two completion methods:

  • Monotonic Completion: This involves manually adding "inheritance axioms" that explicitly define which actions can occur together without interference.
  • Nonmonotonic Completion: Utilizing Circumscription, the authors introduce a Canceled(g1, g2, s) predicate. This allows the logic to assume that action effects are inherited by default unless a specific conflict is identified, significantly reducing the manual overhead of writing axioms.

Benchmarks and Results

As a theoretical contribution, the work is validated against classic commonsense reasoning benchmarks rather than empirical datasets:

  • The Stolen Car Problem: The framework correctly infers that a theft must have occurred during one of the concurrent "wait" periods in a scenario where a car disappears.
  • Conflict Detection: The system can formally identify "unresolved conflicting subactions." If a global action leads to a logical contradiction (e.g., a door being both open and closed), the theory flags the action set as inconsistent for that specific situation.

Conclusion and Future Work

The authors demonstrate that their nonmonotonic approach is provably equivalent to more cumbersome monotonic theories while being far easier for humans to author. While the current focus is on deterministic actions, future work may extend this to non-deterministic settings. Additionally, the authors suggest that Default Logic might provide an even cleaner implementation for the Canceled predicate than the prioritized circumscription used here.

Summary updated

Abstract

We propose a representation of Concurrent actions; rather than invent a new formalism, we model them within the standard situation calculus by introducing the notions of global actions and primitive actions, whose relationship is analogous to' that between situations and fluents. The result is a framework in which situations and actions play quite symmetric roles. The rich structure of actions gives rise to' a new problem, which, due to' this symmetry between actions and situations, is analogous to' the traditional frame problem. In [Lin and Shoham 1991] we provided a solution to' the frame problem based on a formal adequacy criterion called "epistemological completeness." Here we show how to' solve the new problem based on the same adequacy criterion.
BibTeX
@inproceedings{lin1992concurrent,
  author = {Fangzhen Lin and Yoav Shoham},
  title = {{Concurrent Actions in the Situation Calculus}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure