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.
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:
- 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.
- 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.
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