Abstract
Diverse planning is an important problem in automated planning with many real world applications. Recently, diverse planning has seen renewed interest, with work that defines a taxonomy of computational problems with respect to both plan quality and solution diversity. However, despite the recent advances in diverse planning, the variety of approaches and the number of available planners are still quite limited, even nonexistent for several computational problems. In this work, we aim to extend the portfolio of planners for various computational problems in diverse planning. To that end, we introduce a novel approach to finding solutions for three computational problems within diverse planning and present planners for these three problems. For one of these problems, our approach is the first one that is able to provide solutions to the problem. For another, we show that top-k and top quality planners can provide, albeit naive, solutions to the problem and we extend these planners to improve the diversity of the solution. Finally, for the third problem, we show that some existing diverse planners already provide solutions to that problem. We suggest another approach and empirically show it to compare favorably with these existing planners.
Introduction: The Challenge of Diverse Planning
In traditional automated planning, the primary objective is typically to find a single optimal (least-cost) plan. However, real-world scenarios—such as malware detection, risk management, or automated machine learning—often require a set of diverse solutions. A single plan might not account for unmodeled constraints or user preferences.
While a taxonomy for diverse planning exists, practical tools for many of its categories have been lacking. Specifically, researchers have struggled to find efficient solutions for:
- bQ-k: Finding $k$ plans within a specific quality bound.
- bQbD-k: Finding $k$ plans that satisfy both quality and diversity thresholds.
- bQoptD-k: Finding the $k$ most diverse plans within a quality bound.
The fundamental difficulty lies in the inherent trade-off: as quality requirements become stricter, the available plans tend to look more alike, making diversity harder to achieve.
Methodology: A Two-Step Framework
The authors propose a modular, two-stage approach to decouple plan generation from subset selection:
- Candidate Generation: The system uses "unordered top-quality planners" to find all plans within a cost multiplier ($q_m$) of the optimal plan. By ignoring simple action reorderings (which contribute nothing to diversity), the search space is significantly pruned.
- Subset Selection: From the generated pool, the best $k$ plans are selected.
- For bQ-k, a fast greedy algorithm is employed.
- For bQbD-k and bQoptD-k, the selection is modeled as a Mixed Integer Linear Program (MILP) to ensure optimal diversity.
This decoupling allows for flexibility; different planners or diversity metrics can be swapped in without redesigning the entire pipeline.
Experimental Evaluation
The framework was tested on 1,797 tasks from the International Planning Competitions (IPC) benchmarks (1998–2018). To ensure rigorous quality bounds, the set was filtered to 1,192 tasks where optimal costs could be verified using the Delfi1 planner portfolio.
Key Results and Insights
The proposed planners, FI-bQbD and Sym-bQbD, demonstrate significant improvements over existing state-of-the-art methods like DFAM and A*AM.
Superior Coverage and Scalability
The new planners solved more problems across various quality bounds and handled much larger plan sets (up to $k=1000$), where previous methods often failed to find any solution.
Greedy vs. Optimal Selection
A key finding is the efficiency of the greedy approach for the bQ-k problem. While the MILP provides theoretical optimality for diversity, the greedy algorithm achieved nearly identical diversity scores in a fraction of the time (typically under 1.2 seconds vs. hundreds of seconds for the MILP).
Complexity and Efficiency
The authors formally proved that finding a subset with a specific diversity bound is NP-complete, justifying the use of MILP for the selection phase. Furthermore, the "unordered" generation strategy proved essential for efficiency, preventing the system from being overwhelmed by redundant plan permutations.
Conclusion and Future Work
This work fills critical gaps in the diverse planning landscape by providing the first practical tools for several bounded-quality problems. Future research will focus on overcoming the "generation bottleneck" and adapting the MILP formulation to more complex diversity metrics beyond pairwise stability.
Summary updated