Abstract
Traditional AI planning research predominantly focuses on "speed-up learning"—the ability to find any valid solution as quickly as possible. However, real-world applications often require high-quality solutions that optimize specific criteria, such as cost or time. This paper introduces a method for learning quality-enhancing control knowledge. By comparing standard search traces with superior ones, the system automatically derives search-control rules that guide planners toward higher-quality solutions. Preliminary results in process planning domains demonstrate that this approach effectively translates global objective functions into actionable local search guidance.
Introduction
In automated planning, a significant gap exists between finding a valid solution and finding a high-quality one. While classical planners are designed for soundness and completeness, they often prioritize search efficiency over the optimality of the resulting plan. For AI planners to be viable in industrial settings, they must generate "production-quality" plans.
Previous research in "speed-up learning" has successfully reduced planning time but often at the expense of plan quality. The core challenge lies in the nature of quality metrics: while "quality" is typically defined by a global objective function, a planner must make local, incremental decisions during its search. Bridging this gap requires a mechanism to translate high-level quality metrics into local search-control rules. This paper proposes a learning framework that utilizes trace comparison and explanation-based learning to achieve this translation.
System Architecture and Methodology
The proposed system is built upon PRODIGY, a nonlinear planner designed to incorporate various forms of knowledge. The architecture integrates domain-specific information with learning mechanisms to refine search behavior over time.
The learning process involves five key stages:
- Input Specification: The system is provided with a domain theory (operators and inference rules), a domain-dependent objective function (e.g., minimizing total execution cost), and a set of target problems.
- Trace Comparison: The algorithm compares two distinct search traces for the same problem: a "current trace" generated by the planner's existing knowledge and a "better trace" representing a higher-quality solution. The better trace can be obtained through extended search or by observing expert demonstrations.
- Identifying Learning Opportunities: By analyzing where the current trace diverges from the better trace, the system identifies critical decision points where existing control knowledge failed to prioritize the superior path.
- Explanation-Based Learning (EBL): The system uses the objective function to "explain" why the alternative path is superior. This step is crucial for understanding the causal link between local choices and global outcomes.
- Knowledge Acquisition: These explanations are compiled into search-control rules. This process effectively performs a "change of representation," converting a global, static objective function into dynamic, local rules that guide the planner's real-time decision-making.
Evaluation
The approach was evaluated using the Process Planning Domain, a standard benchmark for AI planning. The authors utilized a set of randomly generated synthetic problems to test the incremental performance improvements of the planner.
The preliminary results indicate that the system successfully acquired control knowledge that improved the quality of generated plans over time. As the planner encountered more problems, its ability to generate plans with lower costs (as defined by the objective function) increased, demonstrating the effectiveness of the learning mechanism in bridging the gap between search and quality.
Discussion and Limitations
While the results are promising, several limitations remain. Currently, the system relies on linear, additive evaluation functions where total cost is the sum of individual operator costs. Such models may struggle to capture complex tradeoffs between competing quality factors. Additionally, while the system improves quality incrementally, it does not provide a theoretical guarantee of reaching the absolute mathematical optimum.
Future work will focus on scaling the approach to more diverse domains and exploring non-linear evaluation functions. The ultimate goal is to move beyond simple cost-minimization toward more sophisticated notions of plan quality that reflect the complexities of real-world environments.
Summary updated