Synthesizing Customized Planners from Specifications

Biplav Srivastava, Subbarao Kambhampati

Abstract

Existing plan synthesis approaches in artificial intelligence generally fall into two categories: domain-independent and domain-dependent. While domain-independent planners are versatile across various domains, they often lack efficiency. Conversely, domain-dependent planners are highly efficient but require manual redesign for every new domain. This paper investigates an alternative: the automatic synthesis of domain-customized planners using automated software synthesis tools. We introduce the CLAY architecture, which leverages the Kestrel Interactive Development System (KIDS) to derive customized planners. By combining a declarative theory of planning with domain-specific control knowledge, CLAY generates high-performance planners through semi-automatic program transformation. Our experiments demonstrate that these synthesized planners significantly outperform classical refinement planners, even when those planners utilize the same control knowledge.

Introduction

In the field of AI planning, researchers have long grappled with the "generality vs. efficiency" bottleneck. Domain-independent planners offer the promise of universal applicability but often struggle with computational overhead because they cannot exploit the specific structure of a problem domain. In contrast, domain-specific planners are optimized for speed but are expensive and time-consuming to develop.

The CLAY (Customized pLAnner sYnthesis) architecture proposes a middle ground. Rather than manually coding a new planner for every task, CLAY allows developers to provide high-level specifications of planning logic and domain physics. The system then automatically "folds" this knowledge into a specialized algorithm, resulting in a planner that is both theoretically sound and computationally efficient.

The CLAY Architecture and KIDS

CLAY is built upon the Kestrel Interactive Development System (KIDS), a program transformation environment. The synthesis process involves three distinct layers of specification:

  1. Planning Theory: This is a high-level, declarative description of the planning process itself (e.g., Forward State Space or Backward State Space refinement). It defines what constitutes a valid plan and how the search space is structured.
  2. Domain Theory: This describes the "physics" of the specific world, including available actions, operators, and their preconditions. It also includes "control knowledge"—heuristics or pruning rules that guide the search toward a solution.
  3. Synthesis and Optimization: KIDS takes these specifications and applies algorithm design tactics, such as global search.

Program Transformation Techniques

A key advantage of the CLAY architecture is its use of formal program transformations to optimize the resulting code. Rather than interpreting rules at runtime, CLAY utilizes several sophisticated techniques:

  • Finite Differencing: Instead of re-calculating the entire state of the world after every action, the synthesized planner incrementally updates only the variables that have changed. This significantly reduces the computational cost per node in the search tree.
  • Context-Dependent Simplification: The system analyzes the logic of the domain to identify and remove redundant checks. If a certain condition is logically guaranteed to be true based on the domain's rules, the planner does not waste cycles verifying it during execution.
  • Folding-in Knowledge: This is perhaps the most critical feature. Domain-specific pruning rules are compiled directly into the search algorithm's structure. This eliminates the overhead associated with external heuristic evaluators used in traditional planners.

Experimental Evaluation

To validate the approach, the authors evaluated synthesized planners against UCP (Universal Classical Planning), a framework capable of emulating various classical planners like SNLP or STRIPS. The tests were conducted across three standard benchmarks:

  • Blocks World: Tasks included complex operations like "Stack Inversion." A synthesized planner (BW-P-H1) solved a 14-block inversion in under a minute, whereas the domain-independent version (INDEP-P) failed to solve even a 5-block problem in the same timeframe.
  • Logistics Domain: This involved moving packages and vehicles between locations. The customized planner successfully handled 6-plane problems in 30 minutes, while the general-purpose version could not scale beyond 2-plane problems.
  • Tyre World: A complex domain involving causal dependencies (e.g., jacking up a car before removing a wheel). The synthesized planners maintained high performance even as the complexity of the causal chain increased.

Key Insights

The primary finding of this research is that the method of incorporating knowledge matters as much as the knowledge itself. When the synthesized planners were compared to UCP instantiations using the exact same heuristic information, the synthesized versions were consistently faster. This confirms that the speedup is a direct result of the synthesis process—specifically the "folding" of heuristics into the code—rather than just the quality of the domain rules.

Furthermore, the architecture is highly modular. Because the theory of planning is separated from the domain dynamics, a developer can synthesize different types of planners (e.g., forward-searching vs. backward-searching) for the same domain without rewriting the domain rules.

Limitations and Future Directions

While CLAY demonstrates the power of automated synthesis, it is not yet a "plug and play" solution. Using the KIDS system requires significant expertise in formal methods, particularly in writing the monotonic and distributive laws required for optimization. Additionally, the current focus on state-space planning suggests a need for future expansion into partial-order planning and Hierarchical Task Network (HTN) planning.

Conclusion

Synthesizing customized planners from specifications offers a viable path toward high-performance AI planning without the prohibitive cost of manual development. By treating planning as a software synthesis problem, the CLAY architecture allows for the creation of planners that are both general in their theoretical foundation and specialized in their execution, effectively providing the best of both worlds.

Summary updated

Abstract

Existing plan synthesis approaches in artificial intelligence fall into two categories -- domain independent and domain dependent. The domain independent approaches are applicable across a variety of domains, but may not be very efficient in any one given domain. The domain dependent approaches need to be (re)designed for each domain separately, but can be very efficient in the domain for which they are designed. One enticing alternative to these approaches is to automatically synthesize domain independent planners given the knowledge about the domain and the theory of planning. In this paper, we investigate the feasibility of using existing automated software synthesis tools to support such synthesis. Specifically, we describe an architecture called CLAY in which the Kestrel Interactive Development System (KIDS) is used to derive a domain-customized planner through a semi-automatic combination of a declarative theory of planning, and the declarative control knowledge specific to a given domain, to semi-automatically combine them to derive domain-customized planners. We discuss what it means to write a declarative theory of planning and control knowledge for KIDS, and illustrate our approach by generating a class of domain-specific planners using state space refinements. Our experiments show that the synthesized planners can outperform classical refinement planners (implemented as instantiations of UCP, Kambhampati & Srivastava, 1995), using the same control knowledge. We will contrast the costs and benefits of the synthesis approach with conventional methods for customizing domain independent planners.
BibTeX
@article{srivastava1998synthesizing,
  author = {Biplav Srivastava and Subbarao Kambhampati},
  title = {{Synthesizing Customized Planners from Specifications}},
  journal = {J. Artif. Intell. Res.},
  year = {1998},
  url = {https://openreview.net/forum?id=goLRr2kByC},
}
Figure