Abstract
This paper presents CLAY (Customized pLAnners from theorY), an architecture that utilizes automated software synthesis to bridge the gap between domain-independent and domain-dependent AI planners. By leveraging the Kestrel Interactive Development System (KIDS), CLAY transforms high-level declarative specifications—including domain rules and control knowledge—into highly efficient, domain-specific executable code. Experimental results across standard benchmarks like Blocks World and Logistics demonstrate that synthesized planners can achieve massive speedups over traditional generic planners by mathematically "folding" heuristics into the search algorithm.
Introduction
The field of AI planning has long grappled with a trade-off between flexibility and performance. Domain-independent planners offer broad applicability but often suffer from slow execution due to their inability to exploit domain-specific structures. Conversely, hand-coded domain-dependent planners are highly efficient but require significant manual effort to develop for each new task. This research explores whether fast, domain-specific planners can be automatically generated from the same high-level inputs used by general planners.
The CLAY Architecture
The proposed CLAY architecture centers on the KIDS synthesis tool. Instead of manual coding, a user provides formal definitions of the planning task (e.g., state-space progression) and the specific "physics" of the domain.
As shown in Figure 1, the system integrates domain knowledge (dynamical models and control rules) with refinement planning theories to produce a customized planner tailored to a specific problem. This approach allows for a clean separation of concerns: developers specify the logic of the domain, while the synthesis tool handles the complexities of efficient search control.
The Synthesis Pipeline
The transformation from specification to code involves several distinct stages. Initially, a "global search" tactic is used to construct a basic, un-optimized algorithm from the software specification.
The core strength of this approach lies in the optimization phase depicted in Figure 2. Techniques such as context-dependent simplification and finite differencing are applied. Finite differencing is particularly impactful; it allows the planner to evaluate complex heuristic rules incrementally. Rather than re-calculating a rule for the entire state at every node, the synthesized code only updates values based on the specific changes made in the previous step. Finally, the optimized algorithm is compiled into executable Lisp or C code.
Key Insights and Results
A fundamental innovation of CLAY is the "folding in" of control knowledge. In generic planners, heuristics typically act as external filters. In CLAY, software synthesis embeds these rules directly into the algorithm's structure, preventing the search from ever exploring invalid paths at a fundamental code level.
Experimental Evaluation
The synthesized planners were evaluated on standard benchmarks, including Blocks World, the Logistics domain, and the Tyre World "fixit" problem.
- Massive Speedups: Synthesized planners solved complex problems (e.g., 14-block stack inversion or 31-step Tyre World problems) in under a minute, whereas generic planners often timed out.
- Efficiency over Generic Engines: When compared against the Universal Classical Planner (UCP) using identical heuristics, the synthesized planners consistently outperformed the baseline. This advantage stems from the low-level code optimizations performed by KIDS, which execute heuristics much faster than a generic evaluation engine.
Conclusion and Future Work
While CLAY demonstrates the power of automated synthesis, it currently faces limitations, including a steep learning curve for the KIDS system and the manual effort required to define mathematical laws for optimization. Future work aims to extend this framework to support partial-order (plan-space) planning, Hierarchical Task Network (HTN) planning, and deeper integration with Constraint Satisfaction Problem (CSP) techniques directly within the generated code.
Summary updated