Abstract
The need for finding a set of plans rather than one has been motivated by a variety of planning applications. The problem is studied in the context of both diverse and top-k planning: while diverse planning focuses on the difference between pairs of plans, the focus of top-k planning is on the quality of each individual plan. Recent work in diverse planning introduced additionally restrictions on solution quality. Naturally, there are application domains where diversity plays the major role and domains where quality is the predominant feature. In both cases, however, the amount of produced plans is often an artificial constraint, and therefore the actual number has little meaning. Inspired by the recent work in diverse planning, we propose a new family of computational problems called top-quality planning, where solution validity is defined through plan quality bound rather than an arbitrary number of plans. Switching to bounding plan quality allows us to implicitly represent sets of plans. In particular, it makes it possible to represent sets of plans that correspond to valid plan reorderings with a single plan. We formally define the unordered top-quality planning computational problem and present the first planner for that problem. We empirically demonstrate the superior performance of our approach compared to a top-k planner-based baseline, ranging from 41% increase in coverage for finding all optimal plans to 69% increase in coverage for finding all plans of quality up to 120% of optimal plan cost. Finally, complementing the new approach by a complete procedure for generating all valid reorderings of a given plan, we derive a top-quality planner. We show the planner to be competitive with a top-k planner based baseline.
Introduction
In the field of automated planning, the traditional objective is to find a single "best" path from an initial state to a goal. However, many real-world applications—such as malware detection, intent recognition, and explainable AI—require a set of high-quality alternative plans rather than a single solution. Existing approaches typically rely on diverse planning, which emphasizes differences between plans, or top-$k$ planning, which seeks the $k$ lowest-cost plans.
This paper identifies a fundamental limitation in top-$k$ planning: the parameter $k$ is often an arbitrary constraint that does not reflect the underlying needs of the application. More critically, top-$k$ planners are frequently overwhelmed by the "combinatorial explosion" of plan reorderings—different sequences of the same set of actions.
The Challenge of Plan Reorderings
In many domains, the specific order of independent actions is irrelevant to the high-level solution. For instance, in a logistics task, loading two packages onto a truck in different orders results in two distinct plans for a top-$k$ planner, even though they represent the same fundamental strategy.
As shown in the table above, a top-$k$ planner would be forced to enumerate every possible permutation of these actions before it could discover a plan with a different set of actions. This redundancy significantly hinders the discovery of truly distinct high-quality alternatives.
Unordered Top-Quality Planning
To address these issues, the authors propose Unordered Top-Quality Planning. Instead of finding $k$ plans, the goal is to find all plans within a specific cost bound $q$ (e.g., within 10% of the optimal cost). Crucially, this framework treats plans that are reorderings of each other as equivalent, focusing on the "multiset" of actions rather than their sequence.
The core of the proposed solution is the FMPMA (Forbidding Multiple Plans as a Multi-set of Actions) reformulation. This technique iteratively modifies the planning task:
- Find the best plan.
- Add the plan's action multiset to the results.
- Reformulate the task to "forbid" this specific combination of actions (and all its permutations).
- Repeat until the cost of the next best plan exceeds the bound $q$.
Empirical Evaluation and Results
The researchers evaluated the performance of their top-quality (tq) planner against a state-of-the-art top-$k$ baseline (K-tq) using 1797 tasks from the International Planning Competitions (IPC) 1998–2018. The baseline was configured with $k=10^6$ to approximate the search for all plans within a bound.
The results demonstrate a significant performance advantage for the top-quality approach. By implicitly handling reorderings, the tq planner avoids the exponential overhead faced by K-tq. The study found a 41% increase in coverage for finding all optimal plans and a 69% increase for plans within 120% of the optimal cost. Furthermore, the reformulated tasks produced by this method were much smaller and more efficient to solve than those produced by standard top-$k$ methods.
Conclusion
Top-quality planning offers a more robust and practically useful framework for finding sets of high-quality plans. By shifting the focus from an arbitrary count $k$ to a quality bound and utilizing implicit representations for action reorderings, this approach significantly improves both the efficiency of the search and the relevance of the results. Future work may extend these "unordered" principles to diverse planning and multi-agent coordination, where the focus is on what agents do rather than the exact sequence of actions.
Summary updated