TL;DR
This paper introduces an adaptive planning system that learns to predict the performance of a default planner on new problems. By learning to estimate planning effort, the system can efficiently select relevant past solutions from a library, significantly improving planning performance without complex plan modification.
What Problem Does This Paper Address?
Traditional AI planning systems often struggle with the computational complexity of finding solutions, especially in large or novel domains. While reusing previously solved problems (case-based planning) is a promising approach, directly matching new problems to existing cases can be computationally expensive (NP-hard). Furthermore, modifying existing plans to fit new scenarios can be even more challenging than generating a plan from scratch. This paper tackles the problem of efficiently leveraging past planning experience by developing a system that learns to predict the "effort" required by a default planner for different planning tasks, thereby enabling faster and more effective case retrieval.
Methods
The core of the proposed system is a case-based planner that utilizes a default planner and a library of previously solved problems. Instead of directly modifying retrieved plans, the system learns to predict the cost of two sub-plans: one to transform the new problem's initial state to the retrieved case's initial state, and another to transform the retrieved case's goal state to the new problem's goal state. A neural network is employed to learn these predictions, using features extracted from the problems. The "Gain" metric, calculated as the ratio of the predicted cost of planning from scratch to the sum of the predicted costs of the two sub-plans, is used to select the most appropriate case. A higher Gain indicates a more beneficial case for reuse.
Datasets
The system was implemented and tested in the blocks-world domain. The paper does not specify the exact number or nature of the training examples or benchmark problems used, beyond stating that the system was tested on problems with 3-7 blocks.
Key Insights and Ideas
- Learning to Predict, Not Just Match: The key innovation is shifting from direct, potentially expensive, case matching to learning to predict the utility of a case. This allows for a more efficient selection process.
- Decomposition for Efficiency: By breaking down the problem into transforming initial states and goal states separately, the system leverages the default planner's capabilities on potentially simpler sub-problems.
- The "Gain" Metric: This metric elegantly captures the trade-off between planning from scratch and reusing a case, providing a clear objective for case selection.
- Feature Engineering is Crucial: The effectiveness of the learned predictions heavily relies on the quality and relevance of the extracted problem features, highlighting the importance of domain knowledge or sophisticated feature learning.
Key Results
The prototype system, tested in the blocks-world domain, demonstrated an average improvement in planning performance of 25-35% for problems involving 3-7 blocks. This improvement is attributed to the system's ability to efficiently select relevant past solutions.
Limitations and Future Work
The authors acknowledge that the effectiveness of their system is highly dependent on the success of learning, which in turn relies on the extraction of relevant problem features. They also point out the "utility problem" – the overhead of searching a large library might negate the gains from reuse. Future work could explore more sophisticated feature extraction methods and strategies to manage large case libraries. The authors hypothesize that this approach could be generalized to improve the performance of other planners as well.
Summary updated