Pareto-Based Multiobjective AI Planning

Mostepha Khouadjia, Marc Schoenauer, Vincent Vidal, Johann Dréo, Pierre Savéant2014

TL;DR

This paper introduces MO-DAE, a novel Pareto-based multiobjective AI planning system that can leverage any planner, even non-metric-sensitive ones, to find optimal trade-offs between conflicting objectives. MO-DAE demonstrates superior performance compared to existing metric-based approaches, particularly on complex planning problems.

What Problem Does This Paper Address?

Many real-world problems, including AI planning, involve multiple, often conflicting, objectives. For instance, a plan might need to minimize its execution time (makespan) while also minimizing resource costs. Finding the "best" plan in such scenarios means identifying the set of optimal trade-offs, known as the Pareto front. Traditional AI planning approaches often rely on aggregating these objectives into a single metric (e.g., a weighted sum), which can be suboptimal, require prior knowledge of trade-offs, and may fail to find the complete Pareto front. Existing multiobjective planners are often "metric-sensitive," meaning they are specifically designed to handle these trade-offs, limiting their applicability. This paper addresses the need for a more general and robust approach to multiobjective AI planning that can work with a wider range of planners and effectively approximate the Pareto front.

Methods

The core of the proposed solution is MO-DAE (Multiobjective Divide-and-Evolve), an extension of the Divide-and-Evolve (DAE) planner. DAE works by decomposing a planning problem into a sequence of subproblems, each solved by an embedded planner. MO-DAE enhances DAE by:

  • Multiobjective Selection: Incorporating Pareto-based selection mechanisms (specifically, Indicator-Based Evolutionary Algorithms like IBEAH) into the evolutionary search process. This allows the system to favor solutions that are not dominated by others.
  • Leveraging Non-Metric-Sensitive Planners: Crucially, MO-DAE can use embedded planners that are not metric-sensitive. While such planners might not inherently understand trade-offs, MO-DAE uses them to compute the values of individual objectives (e.g., makespan and cost) for each subproblem. The overall MO-DAE system then handles the multiobjective optimization by managing the population of solutions and their Pareto dominance relationships.
  • Embedded Planner Flexibility: The system is designed to embed any classical planner. In their experiments, they use YAHSP, a satisficing temporal planner, which can be configured to optimize either makespan or cost, while computing the other objective as a side effect.

Datasets

The authors introduce two main types of benchmarks:

  • MULTIZENO: A tunable, artificial benchmark designed to create multiobjective planning problems with varying difficulty and Pareto front shapes (linear, convex, concave). It involves managing cities, passengers, and planes, with objectives being flight duration (makespan) and landing costs.
  • Modified IPC-2011 Problems: They adapt existing single-objective planning domains from the International Planning Competition (IPC) 2011 (e.g., ELEVATORS, OPENSTACKS, FLOORTILE) into multiobjective versions. This is done by either merging temporal and cost-based versions of domains or by creating antagonistic objectives where they don't naturally exist.

Key Insights and Ideas

  • Democratizing Multiobjective Planning: The most significant insight is that a Pareto-based approach can effectively turn any planner into a multiobjective planner, removing the need for specialized "metric-sensitive" planners. This greatly expands the applicability of multiobjective AI planning.
  • Decomposition is Key: The Divide-and-Evolve strategy, which breaks down complex problems into manageable subproblems, proves to be a robust framework for multiobjective optimization.
  • Surprising Performance of Non-Metric-Sensitive Planners: Even when the embedded planner (YAHSP) doesn't explicitly optimize for both objectives simultaneously, MO-DAE can still achieve excellent Pareto front approximations. This highlights the power of the evolutionary search guided by Pareto dominance.
  • Local Search Can Be Detrimental Early On: Preliminary experiments showed that aggressively improving solutions too early (akin to local search) could negatively impact the overall Pareto approximation quality. This suggests a need for a broader exploration phase before fine-tuning.
  • Equal Weights are Often Optimal: For their experiments, tuning the strategy weights for the embedded planner (YAHSP) often resulted in equal weights, reinforcing the idea that no single objective should be artificially prioritized.

Key Results

  • MO-DAEYAHSP (MO-DAE with YAHSP) significantly outperforms the metric-based MO-LPG approach on most tested instances, especially on more complex problems like MULTIZENO9.
  • For MULTIZENO6 and MULTIZENO9, MO-DAEYAHSP was able to identify the complete Pareto front or a robust approximation, while MO-LPG struggled or failed to find feasible solutions.
  • On modified IPC-2011 domains, MO-DAEYAHSP generally found better Pareto fronts than MO-LPG, particularly on larger instances of OPENSTACKS.
  • MO-DAEYAHSP demonstrated the ability to solve larger instances than MO-LPG in several cases.

Limitations and Future Work

  • Parameter Tuning: MO-DAE, like many evolutionary algorithms, has parameters that require tuning. While they used a framework (PARAMILS) to tune these, finding universal parameters for all domains remains a challenge.
  • Embedded Planner Limitations: The current implementation relies on YAHSP, which has limitations in handling numerical state variables beyond action costs. This restricts the direct application of MO-DAE to certain types of multiobjective problems.
  • Benchmark Design: While MULTIZENO is a good start, more sophisticated and diverse multiobjective benchmarks are needed to thoroughly test and compare planners.
  • Future Work: The authors suggest extending MO-DAE to handle more complex objective types, exploring other embedded planners, and further developing multiobjective benchmark suites. They believe their decomposition-based approach has the potential to push the boundaries of solvable problem complexity in multiobjective AI planning.

Summary updated

Abstract

Real-world problems generally involve several an-tagonistic objectives, like quality and cost for de-sign problems, or makespan and cost for plan-ning problems. The only approaches to multiob-jective AI Planning rely on metrics, that can incor-porate several objectives in some linear combina-tions, and metric sensitive planners, that are able to give different plans for different metrics, and hence to eventually approximate the Pareto front of the multiobjective problem, i.e. the set of opti-mal trade-offs between the antagonistic objectives. Divide-and-Evolve (DAE) is an evolutionary plan-ner that embeds a classical planner and feeds it with a sequence of subproblems of the problem at hand. Like all Evolutionary Algorithms, DAE can be turned into a Pareto-based multiobjective solver, even though using an embedded planner that is not metric sensitive. The Pareto-based multiobjective planner MO-DAE thus avoids the drawbacks of the aggregation method. Furthermore, using YAHSP as the embedded planner, it outperforms in many cases the metric-based approach using LPG met-ric sensitive planner, as witnessed by experimental results on original multiobjective benchmarks built upon IPC-2011 domains. 1
BibTeX
@misc{khouadjia2014pareto,
  author = {Mostepha Khouadjia and Marc Schoenauer and Vincent Vidal and Johann Dréo and Pierre Savéant},
  title = {{Pareto-Based Multiobjective AI Planning}},
  year = {2014},
}
Figure