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:
- 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.
- 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.
- 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