An Evolutionary Metaheuristic for Domain-Independent Satisficing Planning

Jacques Bibaï, Pierre Savéant, Marc Schoenauer, Vincent VidalHAL 2010

TL;DR

This paper introduces DAEx, an evolutionary metaheuristic that improves both the quality and scalability of AI planning systems. By decomposing complex planning problems into a sequence of simpler subproblems and using an evolutionary algorithm to discover the best decomposition, DAEx significantly enhances the performance of existing planners, particularly in achieving high-quality solutions.

What Problem Does This Paper Address?

Traditional AI planning systems often prioritize finding any solution quickly, leading to plans of poor quality. While optimal planners exist, they struggle with the scale of real-world problems. The 6th International Planning Competition highlighted a shift towards valuing plan quality. This paper addresses the challenge of developing planning systems that can produce high-quality plans for complex, real-world problems, bridging the gap between fast but suboptimal satisficing planners and slow but optimal planners. They aim to improve both the quality of solutions and the scalability of satisficing planners when faced with difficult planning tasks.

Methods

The core of DAEx is a metaheuristic approach that wraps around an existing planning system. It consists of three main components:

  1. State Decomposition: The planning problem is broken down into a sequence of intermediate states (subgoals) that must be reached. This decomposition is guided by an evolutionary algorithm. The intermediate states are partial states, and their construction leverages classical planning heuristics (specifically, the h¹ heuristic) to estimate the earliest time atoms can appear and to avoid mutually exclusive atoms.
  2. Encapsulated Satisficing Planner: A fast, but often suboptimal, satisficing planner (YAHSP in this case) is used to solve each of the decomposed subproblems. The metaheuristic aims to guide this planner towards better overall solutions.
  3. Evolutionary Algorithm: An evolutionary algorithm (EA) drives the search for the optimal state decomposition. The EA maintains a population of candidate decompositions (individuals), evaluates their fitness (based on the quality of the plan produced by the encapsulated planner), and uses variation operators (crossover and mutation) to evolve better decompositions over generations.

The novelty lies in using an EA to optimize the decomposition strategy itself, rather than directly optimizing the plan. This allows DAEx to explore a wider range of potential solutions and guide the encapsulated planner more effectively.

Datasets

The experiments were conducted on a collection of 736 problems from various International Planning Competition (IPC) benchmarks. These include:

  • Cost-based planning domains: Woodworking, Pegsolitaire, Parcprinter, Openstacks, Transport, Scanalyser, Elevator, Sokoban.
  • Temporal planning domains: Crewplanning, Elevator, Openstacks, Pegsolitaire, Parcprinter, Sokoban, Rovers, Satellite, Zeno.
  • STRIPS domains: Airport, Psr small, Satellite, Openstacks, Rovers, Zeno, Freecell, Pathways.

The paper notes that these domains were chosen to represent different types of complexity and were selected from previous IPC competitions. No new benchmarks were introduced.

Key Insights and Ideas

  • Decomposition as an Optimization Problem: The paper frames the search for an effective state decomposition as an optimization problem, solvable by an evolutionary algorithm. This is a key departure from previous methods that might use more rigid decomposition strategies.
  • Leveraging Heuristics for Decomposition: Using reachability heuristics (like h¹) to guide the construction of intermediate states is crucial. It helps ensure that the decomposed states are "time-coherent" and avoid impossible combinations of actions.
  • Metaheuristic for Quality Improvement: DAEx demonstrates that a metaheuristic can significantly boost the performance of existing planners, particularly in terms of plan quality, without needing to redesign the core planner itself.
  • Scalability through Decomposition: By breaking down large problems, DAEx makes them tractable for planners that would otherwise struggle, thus improving scalability.
  • Evolutionary Algorithms for Search Space Exploration: EAs are well-suited for exploring complex, potentially unstructured search spaces, which is exactly what the space of possible state decompositions represents.

Key Results

  • Improved Coverage and Quality: DAEx significantly outperforms the base YAHSP planner in both coverage (problems solved) and plan quality across various domain types.
  • Competitive with State-of-the-Art: DAEx is shown to be competitive with, and often superior to, other state-of-the-art planners like LAMA, LPG, and TFD, especially in terms of plan quality.
  • Specific Performance Gains:
    • On simple temporal planning, DAEx achieves a coverage of 89.01% and a quality score of 195.97, outperforming LPG (93.84% coverage, 186.46 quality) and TFD (80.32% coverage, 148.44 quality).
  • On STRIPS planning, DAEx achieves 95.01% coverage and a quality score of 230.70, outperforming LPG (96.81% coverage, 196.55 quality) and LAMA (96.09% coverage, 229.26 quality).
  • Robustness: The experiments show that DAEx is robust, with high average coverage across multiple runs.
  • Adaptation to Instance Difficulty: The paper notes that DAEx seems to adapt the complexity of its decompositions (number of states and atoms per state) based on the difficulty of individual planning instances.

Limitations and Future Work

  • Parameter Tuning: The authors acknowledge that tuning the numerous parameters of evolutionary algorithms is a known challenge. While they used a "Racing" procedure to find a common parameter configuration, they suggest that instance-specific parameter tuning could further improve performance.
  • Single Planner Used: The experiments primarily used YAHSP as the encapsulated planner. Future work could explore using different planners or even a portfolio of planners within DAEx to solve subtasks.
  • Heuristic Choice: The current implementation relies on the simple h¹ heuristic for decomposition. Investigating the impact of more elaborate heuristics is suggested.
  • Potential for Further Improvement: The paper hints that using more sophisticated heuristics or exploring different evolutionary strategies could lead to even better results.

Summary updated

Abstract

International audience
BibTeX
@inproceedings{bibai2010evolutionary,
  author = {Jacques Bibaï and Pierre Savéant and Marc Schoenauer and Vincent Vidal},
  title = {{An Evolutionary Metaheuristic for Domain-Independent Satisficing Planning}},
  booktitle = {HAL},
  year = {2010},
}
Figure