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
- Representation: Within the evolutionary population, an individual is represented as a variable-length list of intermediate states, termed "stations."
- 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.
- 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.
- 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
zeno10andzeno12benchmarks, D&E consistently produced optimal or near-optimal solutions. The most notable result occurred withzeno14. 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