Compiling Control Knowledge into Preconditions for Planning in the Situation Calculus

Alfredo Gabaldon

Introduction

In the field of automated planning, the "state space explosion" remains a primary obstacle. As the number of possible actions and states grows, searching for a valid sequence of actions becomes computationally prohibitive. To mitigate this, researchers employ search control knowledge—domain-specific rules that guide a planner by pruning suboptimal or illogical paths. For example, a rule might specify that a transport truck should not move if it still contains a package destined for its current location.

While systems like TLPlan have demonstrated the efficacy of using temporal logic for search control, integrating these rules into formal logic frameworks like the Situation Calculus presents a significant challenge. The Situation Calculus traditionally operates under the Markov assumption, where an action's preconditions and effects depend solely on the current state. However, effective search control is often non-Markovian, requiring knowledge of the history of actions leading to the current state. This paper presents a formal methodology for "compiling" these history-dependent constraints directly into the action definitions of a Markovian theory.

The Problem: Bridging History and the Markov Assumption

In standard Situation Calculus, an action is executable if its preconditions are met in the current situation. Non-Markovian constraints break this model because they require the planner to look back at previous situations. Traditionally, this necessitated a separate, complex reasoning engine to evaluate temporal constraints alongside the primary planning logic.

The author addresses this by proposing a method to transform non-Markovian theories into standard Markovian ones. By doing so, the search control knowledge is "baked" into the action preconditions, allowing any standard planner to benefit from the control rules without needing specialized temporal reasoning capabilities.

Methodology: The Markovian Transformation

The paper introduces a two-step logical compilation process to bridge the gap between history-dependent rules and state-dependent actions.

1. Control as Qualification

The first step involves treating search control formulas as "qualification constraints." In this view, if a sequence of actions violates a control rule, the subsequent action is rendered logically "unexecutable." This is achieved by adding the control formula as a new conjunct to the action’s existing precondition axioms. Essentially, the search strategy becomes a fundamental requirement for the action to occur within the model.

2. The Transformation Operator (M)

The core technical contribution is the definition of a transformation operator, $\mathcal{M}$, which converts the non-Markovian theory into a classical Markovian one through two primary mechanisms:

  • Synthetic Fluents: The transformation introduces new state variables, or "synthetic fluents," which act as a memory of the history. These fluents store the necessary information from past states required to evaluate the control rules.
  • Automated Successor State Axioms: Using a technique called regression—reasoning backward from effects to causes—the system automatically generates axioms that define how these synthetic fluents update. Instead of a human programmer manually determining what to remember, the logic of the constraints themselves dictates the memory structure.

Key Insights: Past-Looking Logic and Memory

A pivotal insight of this work is the preference for past-looking logic (bounded formulas) over future-looking temporal logic. While many planners use future-looking constraints (e.g., "Eventually, goal X must be reached"), the author argues that past-looking logic is more natural for planning. As a planner constructs a "plan prefix" (the history generated so far), it is more efficient to check if that specific history satisfies the rules rather than making assumptions about an infinite or unknown future.

Furthermore, the framework extends to handle explicit time. This allows for the compilation of constraints involving durations and deadlines, such as "Action B must occur within 10 minutes of Action A."

Results and Formal Correctness

The paper provides rigorous proofs demonstrating that the transformed Markovian theory is logically equivalent to the original non-Markovian theory regarding action executability. Key results include:

  • Unified Framework: The approach successfully represents complex temporal connectives—such as always, sometime, since, and until—within the standard Situation Calculus.
  • Closed-Form Solutions: The transformation can facilitate the derivation of "closed-form" solutions for fluents, potentially simplifying how planners reason about state changes over time.

Limitations and Future Research

Despite its formal strengths, the approach has certain limitations:

  • Syntactic Restrictions: The transformation requires formulas to adhere to a specific "bounded" syntactic form, which, while expressive, does not encompass every possible logical construction.
  • Computational Overhead: The introduction of numerous synthetic fluents could potentially slow down state updates in a practical planner. The empirical cost of this overhead remains a subject for future study.
  • Mapping Future Logic: Since many existing benchmarks use future-looking temporal logic (TLPlan-style), future work is needed to develop robust procedures for translating those constraints into the bounded, past-looking formulas utilized in this framework.

Conclusion

By providing a formal method to compile non-Markovian search control into Markovian preconditions, this research simplifies the integration of domain-specific knowledge into automated planning. It moves search control from an external layer of the planning process into the very heart of the action definitions, ensuring that efficiency is a built-in property of the logical model.

Summary updated

BibTeX
@inproceedings{gabaldon2003compiling,
  author = {Alfredo Gabaldon},
  title = {{Compiling Control Knowledge into Preconditions for Planning in the Situation Calculus}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2003},
}
Figure