Sorting Sequential Portfolios in Automated Planning

Sergio Núñez, Daniel Borrajo, Carlos Linares López

TL;DR

In automated planning, "portfolios" combine multiple solvers to tackle complex problems, but the order in which these solvers run is often overlooked. This research demonstrates that execution sequence significantly impacts "anytime" performance. It introduces SLOPE, a greedy algorithm that finds near-optimal orderings while avoiding the overfitting traps of complex optimization methods.

The Importance of Solver Ordering

Automated planning involves finding a sequence of actions to achieve a goal. Since no single algorithm performs best across all domains, researchers use sequential portfolios: a collection of solvers executed one after another for fixed time limits.

While much research focuses on solver selection and time allocation, the order of execution is often an afterthought. However, for "anytime" performance—finding a solution as quickly as possible or improving solution quality over time—the sequence is critical. Running a slow, high-coverage solver before a fast, low-coverage one might solve more problems eventually, but it wastes precious time in the early stages of execution.

Impact of solver ordering on coverage over time

As illustrated in Figure 1, different orderings result in different performance profiles. The goal is to maximize the "area under the curve" of a portfolio’s performance (coverage or quality) over time. A poorly ordered portfolio might have the same final coverage as a well-ordered one but will be significantly less useful in time-sensitive real-world applications, such as power restoration.

Methodology: Optimal Search vs. Greedy Heuristics

The authors define the optimization goal as maximizing the cumulative performance of a portfolio. They propose two primary methods for finding the best sequence:

  1. Optimal Approach (DFBnB): A Depth-First Branch and Bound search using the SQUARE admissible heuristic. This method explores permutations to find the mathematically perfect sequence for a specific training set. However, with $n!$ possible orderings, it is computationally expensive and can take days to compute for large solver sets.
  2. Greedy Approach (SLOPE): The core contribution of this work. SLOPE uses a hill-climbing search that selects solvers based on their "bang for the buck"—specifically, the ratio of expected performance increase to allotted time. This algorithm typically finishes in less than one second.

These are compared against several baselines, including STS (sorting by increasing time), DC (sorting by decreasing coverage), and Random orderings.

Key Results and Generalization

The study utilized data from the International Planning Competitions (IPC) 2008, 2011, and 2014 to evaluate how well these orderings generalize to new domains.

Comparison of training and test scores across different ordering algorithms

As shown in Figure 3, the results highlight several key insights:

  • The Overfitting Trap: While DFBnB is optimal for training data, it often overfits. For example, an ordering optimized for IPC 2008 saw its performance drop to 0.9421 on IPC 2011 test data because it tuned itself too closely to the specific quirks of the training set.
  • SLOPE's Robustness: The greedy SLOPE algorithm consistently achieves ~99% of the optimal training score but generalizes much better. In the IPC 2011 test, SLOPE achieved a perfect score of 1.0000, outperforming the "optimal" DFBnB model trained on 2008 data.
  • Satisficing Planning: The differences were even more pronounced in satisficing planning (where solution quality matters). SLOPE consistently outperformed random and simple sorting strategies across almost all benchmarks.

Conclusion and Future Work

A portfolio's value lies not just in its solvers, but in its sequence. SLOPE provides a fast, robust way to optimize this sequence, ensuring high anytime efficiency across diverse planning problems.

Future research may address current limitations, such as the assumption that solvers do not share information (like cost upper bounds). The authors also suggest applying these sorting algorithms to dynamic portfolios that are customized for specific input instances, further refining the efficiency of automated planners.

Summary updated

Abstract

Recent work in portfolios of problem solvers has shown their ability to outperform single-algorithm approaches in some tasks (e. g. SAT or Automated Planning). However, not much work has been devoted to a better understanding of the relationship between the order of the component solvers and the performance of the resulting portfolio over time. We propose to sort the component solvers in a sequential portfolio, such that the resulting ordered portfolio maximizes the probability of providing the largest performance at any point in time. We empirically show that our greedy approach efficiently obtains near-optimal performance over time. Also, it generalizes much better than an optimal approach which has been observed to suffer from overfitting.
BibTeX
@inproceedings{nunez2015sorting,
  author = {Sergio Núñez and Daniel Borrajo and Carlos Linares López},
  title = {{Sorting Sequential Portfolios in Automated Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}

Loading related content...

Figure