Divide-and-Evolve: a New Memetic Scheme for Domain-Independent Temporal Planning

Marc Schoenauer, Pierre Savéant, Vincent Vidal

Introduction

Temporal Planning Problems (TPPs) represent a significant challenge in artificial intelligence, requiring the coordination of actions with specific durations and potential concurrency to reach a goal state. These problems are classified as PSPACE-hard; as the number of objects and potential interactions increases, the search space expands exponentially. While classical Operational Research (OR) solvers are highly effective at finding optimal solutions for small-scale instances, they frequently fail to scale to the complex, large-scale problems encountered in real-world logistics and scheduling.

This paper introduces the Divide-and-Evolve (D&E) framework, a memetic approach that hybridizes Evolutionary Algorithms (EA) with classical OR solvers. By decomposing intractable global problems into a sequence of smaller, manageable sub-goals, D&E extends the reach of existing planning technology and enables multi-objective optimization without requiring modifications to the underlying solver.

The Divide-and-Evolve Paradigm

The core philosophy of D&E is inspired by the "TGV metaphor": planning a high-speed train route is simplified by identifying a sequence of intermediate stops (stations) rather than attempting to map the entire trajectory in a single calculation.

Framework Components

  1. Representation: Within the evolutionary population, an individual is represented as a variable-length list of intermediate states, termed "stations."
  2. The Oracle (Evolutionary Algorithm): The EA serves as the explorer of the state space. Through mutation and crossover operators, it suggests various sequences of stations that might connect the initial state to the final goal.
  3. The Worker (OR Solver): For every pair of consecutive stations $(s_i, s_{i+1})$, a deterministic temporal planner—specifically the CPT solver—is tasked with finding a valid sub-plan.
  4. The Glue: If the solver successfully identifies plans for all segments, the sub-plans are concatenated. A final "compression" step shifts actions as early as possible to minimize the total makespan, resulting in a globally valid plan.

Multi-objective Extension

A significant advantage of the D&E framework is its ability to handle multi-objective optimization. By utilizing the NSGA-II algorithm at the evolutionary level, the framework can simultaneously optimize for conflicting criteria, such as total time (makespan) and operational risk. Crucially, this is achieved even when the underlying "Worker" solver (CPT) is strictly single-objective. The EA manages the trade-offs at the global level, while the local solver remains focused on solving specific sub-tasks.

Experimental Evaluation

The researchers evaluated the D&E approach using the Zeno transportation benchmark from the International Planning Competition (IPC-3). The study focused on three instances of increasing difficulty: zeno10, zeno12, and zeno14.

Key Results

  • Scaling and Feasibility: On the zeno10 and zeno12 benchmarks, D&E consistently produced optimal or near-optimal solutions. The most notable result occurred with zeno14. While the standalone CPT solver was entirely unable to solve this instance, the D&E framework found a feasible plan with a makespan of 772 in approximately 254 seconds. This demonstrates that problem decomposition is a viable strategy for solving problems previously considered unreachable by classical planners.
  • Pareto Optimization: In original multi-objective versions of the Zeno framework—where cities were assigned specific "risks"—D&E successfully mapped the Pareto front. It identified a range of solutions, allowing users to choose between "fast but high-risk" and "slow but safe" trajectories.

Discussion and Future Work

The D&E framework effectively transforms a planning problem into a state-space navigation problem, where the "distance" between points is defined by the difficulty for the local solver. However, several areas for improvement remain:

  • Computational Efficiency: The current implementation suffers from overhead due to launching the CPT solver as an external process for each sub-problem. Integrating the solver as a library would significantly reduce runtime.
  • State Representation: Currently, "stations" are limited to predicates found in the final goal. This can occasionally hide optimal paths if the necessary intermediate states (e.g., a person being inside a plane) are not represented in the goal predicates.
  • Domain Knowledge: Future iterations aim to incorporate "state invariants"—logical rules that prevent the EA from exploring impossible states, such as an object existing in two locations simultaneously.

Conclusion

Divide-and-Evolve offers a robust path forward for temporal planning by leveraging the global search capabilities of Evolutionary Algorithms to assist the local precision of OR solvers. By "slicing" through complexity, the framework not only solves larger problems but also provides a flexible architecture for multi-objective decision-making in complex domains.

Summary updated

Abstract

An original approach, termed Divide-and-Evolve is proposed to hybridize Evolutionary Algorithms (EAs) with Operational Research (OR) methods in the domain of Temporal Planning Problems (TPPs). Whereas standard Memetic Algorithms use local search methods to improve the evolutionary solutions, and thus fail when the local method stops working on the complete problem, the Divide-and-Evolve approach splits the problem at hand into several, hopefully easier, sub-problems, and can thus solve globally problems that are intractable when directly fed into deterministic OR algorithms. But the most prominent advantage of the Divide-and-Evolve approach is that it immediately opens up an avenue for multi-objective optimization, even though the OR method that is used is single-objective. Proof of concept approach on the standard (single-objective) Zeno transportation benchmark is given, and a small original multi-objective benchmark is proposed in the same Zeno framework to assess the multi-objective capabilities of the proposed methodology, a breakthrough in Temporal Planning.
BibTeX
@inproceedings{schoenauer2006divide,
  author = {Marc Schoenauer and Pierre Savéant and Vincent Vidal},
  title = {{Divide-and-Evolve: a New Memetic Scheme for Domain-Independent Temporal Planning}},
  booktitle = {EvoCOP},
  year = {2006},
  doi = {10.1007/11730095\_21},
}
Figure