TL;DR
This paper introduces "Learn-and-Optimize" (LaO), a novel framework that combines machine learning with optimization to automatically tune parameters for AI planning algorithms. LaO learns a mapping between instance features and optimal parameters, enabling it to generalize and improve planning performance even with limited training data.
What Problem Does This Paper Address?
AI planning algorithms, particularly Evolutionary Algorithms (EAs), often require computationally expensive parameter tuning to achieve optimal performance. A significant challenge in this tuning process is generalization: how to ensure that parameters optimized for one planning instance are effective for others, even within the same domain. Existing methods often struggle with this, leading to suboptimal performance on unseen instances. This paper addresses this gap by proposing a framework that learns a relationship between instance characteristics and optimal parameters, aiming to overcome the generalization issue.
Methods
The core of the LaO framework is the integration of learning and optimization. It proposes learning a mapping from instance features to optimal parameters. This mapping is then used to guide the optimization process.
- Learning Component: An Artificial Neural Network (ANN) is used to learn the mapping from instance features to optimal parameters. The paper specifically mentions using a simple multi-layer Feed-Forward ANN trained with standard backpropagation.
- Optimization Component: The Covariance Matrix Adaptation Evolution Strategy (CMA-ES), specifically a (1+1)-CMA-ES variant, is employed for parameter tuning. This choice is justified by its robustness and suitability for successive optimization across multiple instances.
- Gene-Transfer: A novel component called "gene-transfer" is introduced. This mechanism allows for the exchange of information (best parameters found so far) between the optimization processes of different instances, acting as a form of crossover or migration in evolutionary computation. This is intended to help instances learn from each other.
- Target Algorithm: The framework is applied to tune the parameters of Divide-and-Evolve (DaE), an Evolutionary Algorithm for AI Planning. DaE itself uses an external "embedded" planner (YAHSP) to solve sub-problems.
Datasets
The paper uses benchmark domains from the Planning and Learning Part of IPC2011 (IPC). Specifically, they generated instances from the Ferry, Freecell, Grid, Mprime, and Sokoban domains. However, Ferry and Sokoban were excluded due to insufficient instances. The remaining domains (Freecell, Grid, Mprime, and Parking) were used for training and testing. For the "Parking" domain, they used a lower range of generator parameters due to its difficulty.
Key Insights and Ideas
- Learning to Tune: The fundamental idea that parameters can be learned from instance features, rather than being tuned exhaustively for each instance, is a key insight. This shifts the paradigm from instance-specific tuning to a more generalized approach.
- Feature-Parameter Mapping: The hypothesis that a learnable, potentially non-linear, relationship exists between instance features and optimal parameters is central. This allows for extrapolation to unseen instances.
- Gene-Transfer for Collaboration: The gene-transfer mechanism is an interesting idea for enabling instances to "learn" from each other's optimization progress. This is particularly relevant when instances share similar features, suggesting that good parameter settings for one might be beneficial for another.
- ANN as a Surrogate: The ANN acts as a surrogate model, not for fitness evaluation (as in some other surrogate-based optimization), but for directly predicting optimal parameters based on instance features.
Key Results
- Improved Quality: LaO consistently improved the quality of the DaE algorithm's results compared to tuning with global racing, even with a limited number of LaO iterations.
- Generalization: The learned ANN model demonstrated good generalization to independent test sets for most domains, with quality-improvement ratios dropping only slightly compared to the training set.
- Efficiency: The framework showed promise in improving results with relatively few iterations, suggesting potential for significant speedups in the tuning process.
- Domain-Specific Models: The paper focused on training domain-specific ANN models. The results for the "Parking" domain showed a large gain in training but a significant drop on the test set, highlighting challenges in extrapolation for very difficult domains.
Limitations and Future Work
- Feature Set: The authors acknowledge that the current feature set might be too small and should be extended for better results.
- ANN Complexity: The ANN's complexity might need to be adjusted, or more sophisticated architectures (like Growing Neural Networks) could be explored.
- Extrapolation Issues: For hard domains, avoiding unfeasible parameters when extrapolating the ANN model remains a challenge.
- More Iterations and Domains: The most important future experiment is to run LaO for a significantly larger number of iterations and on more diverse domains.
- Inter-Domain Models: Training a single domain-independent ANN is a direction for future work.
- Gene-Transfer Improvement: Investigating more deterministic gene-transfer mechanisms based on feature similarity is suggested.
Summary updated