The Use of Condition Types to Restrict Search in an AI Planner

Austin Tate, Brian Drabble, Jeff DaltonAAAI 1994

Abstract

In the field of Artificial Intelligence planning, the "state-space explosion" problem historically limited the scalability of general-purpose planners. This paper presents a methodology for "condition typing," implemented in the O-Plan2 system, which allows domain experts to provide teleological context to a planner. By distinguishing between different types of preconditions—such as filters, queries, and goals—the search space can be significantly pruned. This approach bridges the gap between raw logical search and human-guided domain expertise, making AI planning more efficient and practical for large-scale, realistic domains.

Introduction

During the early 1990s, AI planners relied heavily on algorithms like the "Truth Criterion" to maintain logical consistency. While effective for small problems, these systems often became "blind" to the broader context, attempting to solve every precondition as a potential sub-goal. This lack of intent, or teleology, led to inefficient search behaviors where planners would waste computational resources on impossible or irrelevant tasks. The authors argue that for a planner to be effective, it must understand the purpose of a condition within the plan's hierarchy.

The Triangle Model of Activity

To address these challenges, the authors introduce the Triangle Model of Activity. This conceptual framework categorizes the inputs and outputs of any given action into four distinct pillars: Authority, Conditions/Effects, Resources, and Time.

Figure 1: The Triangle Model of Activity, illustrating the relationship between activity decomposition, authority, conditions, effects, resources, and time.

This model ensures that the planner considers not just logical preconditions, but also the temporal and resource-based constraints necessary for realistic execution. By decomposing activities within this structured environment, O-Plan2 can manage complex interactions and prevent infinite recursion using a Plan Level algorithm based on Strongly Connected Components (SCCs).

Condition Typing Taxonomy

The core contribution of this work is the implementation of a taxonomy of five distinct condition types. This taxonomy allows domain writers to explicitly state how a condition should be handled by the search engine, moving away from a monolithic "goal" type.

Table 1: Taxonomy of Condition Types in O-Plan2, detailing the levels considered (above, same, below) and the internal/external nature of each type.

The five types are:

  1. only-use-if (Filters): These check if a schema is applicable. If not met, the planner rejects the strategy immediately.
  2. only-use-for-query: Used to retrieve information (e.g., variable binding) without triggering a search to change the environment.
  3. unsupervised: Conditions expected to be satisfied by external processes or prior actions, serving as sequencing constraints.
  4. supervised: Internal requirements satisfied within a specific manager's scope to protect causal links.
  5. achieve: The only type that permits the planner to "sub-goal," or add new actions to the plan to make the condition true.

By restricting sub-goaling to the achieve type, the branching factor of the search tree is drastically reduced, preventing the planner from "over-indulging" in unnecessary search.

Comparative Analysis and Results

The paper situates O-Plan2 within the broader landscape of contemporary planning systems, comparing it to Nonlin, SIPE-2, and ACT. The authors demonstrate that O-Plan2’s condition types are more expressive; for instance, it splits the broad "usewhen" type found in Nonlin into more precise only-use-if and only-use-for-query categories. This granularity allows for more precise control over the search process. The authors conclude that condition typing is "essential" for reducing search spaces to a manageable level in real-world AI applications.

Conclusion

Condition typing represents a significant shift toward knowledge-based planning. While the approach improves efficiency, it requires domain writers to correctly categorize conditions—a task that can be difficult without proper tooling. Future research is needed to further formalize these interactions and develop software tools to assist in domain modeling. Ultimately, this work provides a foundational framework for making AI planners scalable and context-aware.

Summary updated

BibTeX
@inproceedings{tate1994use,
  author = {Austin Tate and Brian Drabble and Jeff Dalton},
  title = {{The Use of Condition Types to Restrict Search in an AI Planner}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure