April 01, 2024

The ability to generate multiple plans is central to using planning in real-life applications. Top-quality planners generate sets of such top-cost plans, allowing flexibility in determining equivalent ones. In terms of the order between actions in a plan, the literature only considers two extremes – either all orders are important, making each plan unique, or all orders are unimportant, treating two plans differing only in the order of actions as equivalent. To allow flexibility in selecting important orders, we propose specifying a subset of actions the orders between which are important, interpolating between the top-quality and unordered top-quality planning problems. We explore the ways of adapting partial order reduction search pruning techniques to address this new computational problem and present experimental evaluations demonstrating the benefits of exploiting such techniques in this setting.

Motivated by the different settings and application domains, the problem of finding multiple plans – diverse planning [1], [2], top-k planning [3], [4], or top-quality planning [5], [6] – specify valid solutions by limiting either the number of plans or their costs, requiring to find all plans under that criterion. Some flexibility in that limitation is possible, allowing to specify an equivalence between plans as in quotient top-quality planning. In practice, however, only two extremes are considered in the literature – consider some plans as equivalent, e.g., plans that differ only in the order of the actions used, as in the case of unordered top-quality planning, or consider all plans as unique.

In this paper, we introduce a new class of problems called partially ordered top-quality planning, allowing us to interpolate between the two extremes by specifying a set of actions whose ordering in the plan is important. The motivation behind looking
for such a middle-ground is threefold: (1) under-specified action models (e.g., missing precondition or effect). If only one of the orders is produced, as in the unordered top-quality setting, that plan might not correspond to a desired solution; (2)
action ordering preferences: users may have soft constraints that they wish to impose on action orderings, not exposed in the planning model. For example, in the *rovers* domain, users may impose preferences over the order of actions such as
*sample_soil*, *sample_rock*, *take_image*, as seen in the International Planning Competition (IPC) [7],
or in the case of *openstacks*, certain products may have priority over others, and the user may want to impose a preference over the *make-product* action; (3) known unimportant orderings. For example, in transportation domains, one may not
care about the orders between the various *drive* actions. Planning domains may contain bookkeeping or auxiliary actions often resulting from transformations (e.g., [8], [8]) and it may be known that the order of such
auxiliary actions are not important. As the solutions for partially ordered top-quality planning are subsets of solutions for top-quality planning, one can solve the new problem by post-processing the plans obtained by a top-quality planner. These
planners, however, do not benefit from partial order reduction [9]. In this work, we explore the possibility of improving planner
performance by exploiting partial order reduction based pruning in the context of producing partially ordered top-quality solutions.

Our contributions are as follows: (1) we characterize the partial order planning problem; (2) we propose three computational approaches to solve the new planning problem. The first approach is a simple base case: post-process the results produced by a top-quality planner. The second and the third approaches leverage successor punning techniques (e.g., [10], [10]), achieved either through modification to the partial order reduction algorithm or by inspecting the reduced set of successor actions, respectively; (3) we prove the necessary theoretical guarantees for safe pruning and the use of partial order reduction in the proposed approaches, and (4) we evaluate the three approaches.

In this section, we introduce the necessary concepts in top-quality planning and partial order reduction.

We consider classical planning tasks in sas\({}^{+}\)formalism [11], extended with action costs. Such *planning tasks* \(\Pi^{} = \langle \mathcal{V}^{},\mathcal{O}^{},s_{0}^{},s_\star^{}\rangle\) consist of a finite set of finite-domain *state
variables* \(\mathcal{V}\), a finite set of *actions* \(\mathcal{O}\), an *initial state* \(s_{0}\), and the *goal* \(s_\star\). Each variable \(v\!\in\!\mathcal{V}\) is associated with a finite domain \(\mathit{dom}(v)\) of values. A *partial assignment* \(p\) maps a subset of variables \(\mathcal{V}(p)\!\subseteq\!\mathcal{V}\) to values in their domains. The value of \(v\) in \(p\) is denoted by \(p[v]\) if \(v\in \mathcal{V}(p)\) and *undefined* otherwise. A partial assignment \(s\) with \(\mathcal{V}(s) = \mathcal{V}\) is called a *state*. State \(s\) is *consistent* with partial assignment \(p\) if they agree on all variables in
\(\mathcal{V}(p)\), denoted by \(p \subseteq s\). \(s_{0}\) is a state and \(s_\star\) is a partial assignment. A state
\(s\) is a *goal state* if \(s_\star\subseteqs\) and \(\mathcal{S}_{s_\star}\) is the set of all goal states. Each action \(o\) in \(\mathcal{O}\) is a pair of partial assignments \(\langle \mathit{pre}(o),\mathit{eff}(o)\rangle\) called *precondition* and *effect*,
respectively. Further, \(o\) has an associated *cost* \(C(o)\in{\mathbb{R}}^{0+}\). An action \(o\) is applicable in \(s\) if \(\mathit{pre}(o) \subseteq s\). All such actions are denoted by \(\mathcal{O}(s)\). Applying \(o\) in \(s\) results in a state \(s\llbracket o \rrbracket\) where \(s\llbracket o \rrbracket[v] = \mathit{eff}(o)[v]\) for all \(v\in
\mathcal{V}(\mathit{eff})\) and \(= s\llbracket o \rrbracket[v] = s[v]\) for all other variables. An action sequence \(\pi= \langle o_1, \cdots, o_n \rangle\) is applicable in \(s\) if there are states \(s_1, \cdots ,s_{n+1}\) s.t. \(s=s_1\), \(o_i\) applicable in \(s_{i}\), and \(s_{i}\llbracket o_i \rrbracket\!=\!s_{i+1}\) for \(0\leq\!i\leq\!n\). We denote \(s_n\) by \(s\llbracket\pi \rrbracket\). An action sequence with \(s_{0}\llbracket\pi \rrbracket \in \mathcal{S}_{s_\star}\) is called a *plan*. The cost of a plan \(\pi\), denoted by \(C(\pi)\), is the summed cost of the actions in the plan. The set of all plans is denoted by \(\cP_{\Pi}\). A plan is *optimal* if its
cost is minimal among all plans in \(\cP_{\Pi}\). Cost-optimal planning deals with finding an optimal plan or proving that no plan exists.

Top-quality planning [5], [12] deals with
finding *all* plans of up to a specified cost. Formally, the **top-quality** planning problem is as follows. Given a planning task \(\Pi\) and a number \(q\in{\mathbb{R}}^{0+}\), find the set of plans \(P\!=\!\{ \pi\in\cP_{\Pi}\mid cost(\pi) \leq q\}\). In some cases, an equivalence between plans can be specified, allowing to possibly skip some
plans, if equivalent plans are found. The corresponding problem is called **quotient top-quality** planning and it is formally specified as follows. Given a planning task \(\Pi\), an equivalence relation \(N\) over its set of plans \(\cP_{\Pi}\), and a number \(q\in{\mathbb{R}}^{0+}\), find a set of plans \(P\subseteq\cP_{\Pi}\)
such that \(\bigcup_{\pi\in P} N[\pi]\) is the solution to the top-quality planning problem. The most common case of such an equivalence relation is when the order of actions in a valid plan is not significant from the
application perspective. The corresponding problem is called **unordered top-quality** planning and is formally specified as follows. Given a planning task \(\Pi\) and a number \(q\in{\mathbb{R}}^{0+}\), find a set of plans \(P\subseteq\cP_{\Pi}\) such that \(P\) is a solution to the quotient top-quality planning problem under the
equivalence relation \(\mathrm{\small U}_{\Pi} = \{ (\pi, \pi') \mid \pi,\pi'\in\cP_{\Pi}, \mathrm{\small MS}(\pi) = \mathrm{\small MS}(\pi')\}\), where \(\mathrm{\small
MS}(\pi)\) is the multi-set of the actions in \(\pi\).

A central to partial order reduction techniques is the notion of *safe* successor pruning [10].

**Definition 1** (safe). *Let \(succ\) be a successor pruning function for a planning task \(\Pi\). We say that \(succ\) is safe if for
every state \(s\), the cost of an optimal solution for \(s\) is the same when using the pruned state space induced by \(succ\) as when using the full state
space.*

When using safe successor pruning, it is possible to search the pruned state space instead when searching for cost-optimal plans. Stubborn sets [13], [14] induce safe successor pruning functions by helping identifying actions that can safely be ignored at node expansion. It is done by specifying a set, such that if an applicable action is not in the set, it can be safely ignored (e.g., [10], [10]).

At the core of these partial order reduction techniques is the idea that, for each non-goal state \(s\), if a goal is reachable from \(s\), then at least one *strongly optimal* (an
optimal plan with a minimal number of 0-cost actions among all optimal plans) is preserved in the pruned state space.

Two main notions in stubborn sets are *interference* and *necessary enabling sets* (NES). Interference dictates whether two actions disable each other or conflict. Necessary enabling set for an action \(o\)
and a set of paths from the initial state is a set of actions that appear on the paths that include \(o\) before its first appearance. There are various definitions of strong stubborn sets in the literature, we use
Generalized Strong Stubborn Set (GSSS) by [15] .

**Definition 2** (GSSS). * Let \(\Pi\) be a planning task and \(s\) be a solvable non-goal state. Let \(\overline{S}\) be the states along strongly optimal plans for \(s\). A set \(T\subseteq \mathcal{O}\) is a GSSS for \(s\)
if:*

(i) *\(\mathrm{\small T}\) contains actions from a strongly optimal plan for \(s\).*

(ii) *For every \(o\in \mathrm{\small T}\setminus \mathcal{O}(s)\), \(\mathrm{\small T}\) contains a NES for \(o\).*

(iii) *For every \(o\in \mathrm{\small T}\cap \mathcal{O}(s)\), \(\mathrm{\small T}\) contains all \(o'\in \mathcal{O}\) that interfere with \(o\) in any state \(s\in \overline{S}\).*

*The successor function \(\mathrm{\small T}(s)\) under \(\mathrm{\small T}\) therefore returns the applicable in \(s\) actions from \(\mathrm{\small T}\), \(\mathrm{\small T}(s):=\mathcal{O}(s)\cap\mathrm{\small T}\).*

For a sequence of actions \(\pi\) and a subset of task actions \(X\), we denote by \(\pi\!\mid_{X}\) the subsequence obtained from \(\pi\) by removing actions not in \(X\). With that, we can define a relation over the set of all plans \(\cP_{\Pi}\) as \[\mathrm{\small P}_{X}\!=\!\{ (\pi, \pi')\mid \pi,\pi'\in\cP_{\Pi}, \mathrm{\small MS}(\pi)\!=\!\mathrm{\small MS}(\pi'), \pi\!\mid_{X}\!=\!\pi'\!\mid_{X} \}.\] The relation \(\mathrm{\small P}_{X}\) is an equivalence relation: it is reflexive, transitive, and symmetric. With that relation, we can define the **partially ordered top-quality** planning as follows.

**Definition 3**. *Let \(\Pi\) be some planning task over the actions \(\mathcal{O}\) and \(\cP_{\Pi}\) be the set of its plans. The
partially ordered top-quality planning problem is defined as follows.
Given a set of actions \(X\) and a number \(q\!\in\!{\mathbb{R}}^{0+}\), find a set of plans \(P\!\subseteq\!\cP_{\Pi}\) that is a solution to the quotient
top-quality planning problem under the equivalence relation \(\mathrm{\small P}_{X}\).*

The notion of safe successor pruning in Definition 1 captures safety for cost-optimal planning, where any plan of minimal cost is a valid solution. However, when discussing top-quality planning in general and partially ordered top-quality planning in particular, the notion of safety changes.

**Definition 4** (top-quality safe). *Let \(succ\) be a successor pruning function for a planning task \(\Pi\) and let \(X\) be a subset
of actions of \(\Pi\). We say that \(succ\) is safe for partially ordered top-quality planning if for every state \(s\) and for every plan \(\pi_s\) for \(s\), there exists a path \(\pi'_s\) in the pruned state space induced by \(succ\), such that \((\pi_s,\pi'_s)\in\mathrm{\small P}_{X}\).*

In order to solve the defined computational problem, one can use an existing top-quality planner, post-processing the obtained plans. The currently best performing among these planners is \(K^{\ast}\) [16], which can exploit successor pruning techniques to improve its efficiency, as in unordered top-quality planning [6].

The most popular successor pruning techniques are based on partial order reduction methods exploiting stubborn sets [13], [14]. The idea behind these techniques is that a successor can be pruned as long as for every plan pruned there exists a reordering of that plan that is also a plan and it starts with an action that is not pruned. Although such pruning technique is deemed safe for unordered top-quality planning with \(K^{\ast}\) [6], it may prune some reorderings of the found plans. Consequently, it cannot be directly applied to top-quality planning or partially ordered top-quality planning.

In order to be able to use partial order reduction based pruning for partially ordered top-quality planning, we need to ensure that the successor function is safe for partially ordered top-quality planning. This can be done by either modifying the partial order reduction algorithm or externally, by inspecting the reduced set of successor actions. Let us start with the latter first.

Given the set of applicable actions \(\mathcal{O}(s)\) and a partial order reduction successor function \(\mathrm{\small T}(s)\), we can define an extended successor function as follows. \[{\mathrm{\small T}}_{X}(s) = \begin{cases} \mathrm{\small T}(s) & \mathrm{\small T}(s) \cap X=\emptyset, \\ \mathrm{\small T}(s) \cup X & \mathrm{\small T}(s) \cap X\neq\emptyset \wedge X \setminus \mathcal{O}(s) = \emptyset, \\ \mathcal{O}(s) & otherwise \end{cases}\]

We show that \({\mathrm{\small T}}_{X}(s)\) can be used for partial ordered top-quality planning.

**Theorem 1**. *The successor function \({\mathrm{\small T}}_{X}(s)\) is safe for partial ordered top-quality planning, when \(\mathrm{\small T}\) is a GSSS.*

Let \(\Pi\) be a planning task, \(s\) be some state, \(\mathrm{\small T}(s)\) be a strong stubborn set successor function, and \(\pi_s =o_1\ldots o_n\) be some plan for \(s\). If \(o_1\not\in{\mathrm{\small T}}_{X}(s)\), let \(k\) be the smallest index such that \(o_k\in{\mathrm{\small T}}_{X}(s)\). We start by noting that \(\pi'_s =o_ko_1\ldots o_{k-1}o_{k+1}\ldots o_n\) obtained from \(\pi_s\) by moving the action \(o_k\) to the front, is also a plan for \(s\). The claim stems from \({\mathrm{\small T}}_{X}(s)\) pruning at most as much as \(\mathrm{\small T}(s)\) and therefore the correctness was shown by [10] .

Now, we show that \((\pi_s,\pi'_s)\in\mathrm{\small P}_{X}\). If \(o_k\not\in X\), then \((\pi_s,\pi'_s)\in\mathrm{\small P}_{X}\) and we are done. Assume now that \(o_k\in X\). Since \(o_k\in X\) and \(o_k\in {\mathrm{\small T}}_{X}(s)\), we have \({\mathrm{\small T}}_{X}(s)\cap X \neq \emptyset\) and therefore \({\mathrm{\small T}}_{X}(s)\neq \mathrm{\small T}(s)\). Since we also have \(o_1\not\in {\mathrm{\small T}}_{X}(s)\), we have \({\mathrm{\small T}}_{X}(s)\neq \mathcal{O}(s)\) and thus \({\mathrm{\small T}}_{X}(s) = \mathrm{\small T}(s) \cup X\), the second case of the definition. Since \(k\) is the smallest index such that \(o_k \in \mathrm{\small T}(s)\), for all \(1\leq i <k\) we have \(o_i \not\in {\mathrm{\small T}}_{X}(s)\) and therefore \(o_i \not\in X\), giving us again \((\pi_s,\pi'_s)\in\mathrm{\small P}_{X}\). \(\square\)

A simple example shows that it is not sufficient to add the set \(X\) to the reduced successor function when not all actions in \(X\) are applicable. Let \(s = \{ v_0=0, v_1=0 \}\), \(s_\star= \{ v_0=2, v_1=1 \}\), and \(\mathcal{O}= \{ o_1\!=\!\langle \{ v_0=0 \}, \{ v_0=1 \} \rangle, o_2=\langle \{ v_0=1 \}, \{ v_0=2 \} \rangle, o_3=\langle \{ v_1=0 \}, \{ v_1=1 \} \rangle \}\). There are three plans for \(s\), namely \(\pi_1=o_1o_2o_3\), \(\pi_2=o_3o_1o_2\), and \(\pi_3=o_1o_3o_2\). If \(X = \{ o_2, o_3 \}\), then \(\mathrm{\small P}_{X} = \{ (\pi_2,\pi_3) \}\). Since \(\mathcal{O}(s) = \{o_1,o_3\}\) and \(o_1\) and \(o_3\) are completely independent, a partial order reduction may reduce either of these actions. If \(\mathrm{\small T}(s) = \{o_3\}\), the plans \(\pi_1\) and \(\pi_3\) are pruned, and \(\pi_2\) remains. While \(\pi_3\) is equivalent to \(\pi_2\), \(\pi_1\) is not. The plan \(\pi_2\), obtained from \(\pi_1\) by moving the action \(o_3\) to the front, changes the order between actions \(o_2\) and \(o_3\).

The benefit of the approach above is that it can work with any partial order reduction technique and does not require modifications to the technique. We now move to the other approach of modifying the partial order reduction technique.

Focusing on stubborn sets, we show that it is sufficient to extend condition 2 of Definition [def:gsss] by adding another condition on top of interference.

**Definition 5** (PO-GSSS). * Let \(\Pi\) be a planning task over the actions \(\mathcal{O}\) and \(X\subset\mathcal{O}\) be some set of its actions. Let \(s\) be a solvable non-goal state. Let \(\overline{S}\) be the states along strongly optimal plans for
\(s\). A set \(\mathrm{\small T}\subseteq \mathcal{O}\) is a PO-GSSS for \(s\) if:*

(i) *\(\mathrm{\small T}\) contains actions from a strongly optimal plan for \(s\).*

(ii) *For every \(o\in \mathrm{\small T}\setminus \mathcal{O}(s)\), \(\mathrm{\small T}\) contains a NES for \(o\).*

(iii) * For every \(o\in \mathrm{\small T}\cap \mathcal{O}(s)\), \(\mathrm{\small T}\) contains all \(o'\in \mathcal{O}\) that interfere with \(o\) in any state \(s\in \overline{S}\).*

(iv) *For every \(o\in \mathrm{\small T}\cap \mathcal{O}(s)\), if \(o\in X\), \(\mathrm{\small T}\) contains all actions in \(X\).*

**Theorem 2**. *PO-GSSS is safe for partial ordered top-quality planning.*

Let \(\Pi\) be a planning task, \(s\) be some state, \(\mathrm{\small T}\) be a PO-GSSS for \(s\), and \(\pi_s =o_1\ldots o_n\) be some plan for \(s\). Let \(k\) be the minimal index such that \(o_k\in\mathrm{\small T}\). Since \(\mathrm{\small T}\) is a super-set of a generalized strong stubborn set, using the same argument as [10] , we can show that \(o_k\) is applicable. Let \(\pi'_s =o_ko_1\ldots o_{k-1}o_{k+1}\ldots o_n\) If \(o_k\not\in X\), then \((\pi_s,\pi'_s)\in\mathrm{\small P}_{X}\) and we are done. If \(o_k\in X\), then for all \(1\leq i < k\), \(o_i\not\in X\), due to \(k\) being smallest such index and therefore, again, \((\pi_s,\pi'_s)\in\mathrm{\small P}_{X}\). \(\square\)

agricola | \((take\_food|plow\_field|build\_fences|improve\_home).*\) |

airport | \(takeoff\_seg.*\) |

barman | \((clean-shot|clean-shaker|empty-shake).*\) |

blocks | \(put-down.*\) |

depot | \((load|unload).*\) |

driverlog | \((load-truck|unload-truck|board-truck).*\) |

floortile | \(paint.*\) |

freecell | \(send.*\) |

ged | \(reset.*\) |

gripper | \(pick.*\) |

hiking | \(put.*\) |

logistics | \((load|unload).*\) |

miconic | \(board.*\) |

movie | \(re.*\) |

mprime | \(succumb.*\) |

mystery | \(succumb.*\) |

nomystery | \((load|unload).*\) |

openstacks | \(make-product.*\) |

organic-synthesis | \(sodium.*\) |

parcprinter | \((color|lc1).*\) |

parking | \(move-car-to-car.*\) |

pathways | \(initialize.*\) |

pipesworld | \(push-start.*\) |

psr-small | \(open.*\) |

rovers | \((sample|take\_image).*\) |

satellite | \(take\_image.*\) |

scanalyzer | \(rotate.*\) |

snake | \(move-and-eat-spawn.*\) |

spider | \(start-dealing.*\) |

storage | \(lift.*\) |

termes | \(.*-block.*\) |

tidybot | \(finish-object.*\) |

tpp | \(buy.*\) |

transport | \((pick-up|drop).*\) |

trucks | \((load|unload|deliver).*\) |

woodworking | \(load.*\) |

zenotravel | \(board.*\) |

Coverage | NoPOR | POR+ | POGSSS |
---|---|---|---|

airport (50) | 7 | 8 |
8 |

driverlog (20) | 10 | 11 |
11 |

movie (30) | 3 | 22 |
22 |

mystery (30) | 20 | 22 |
22 |

organic-synthesis-split18 (20) | 18 | 19 |
18 |

parcprinter-08 (30) | 6 | 10 | 11 |

parcprinter11 (20) | 3 | 6 | 7 |

parking14 (20) | 2 | 3 |
2 |

psr-small (50) | 46 | 48 |
48 |

satellite (36) | 5 | 6 | 7 |

snake18 (20) | 4 | 6 |
5 |

termes18 (20) | 4 | 5 |
5 |

tidybot14 (20) | 6 | 7 |
7 |

woodworking08 (30) | 7 | 21 |
21 |

woodworking11 (20) | 2 | 15 |
15 |

Sum other (1139) |
307 | 307 | 307 |

Sum (1555) |
450 | 516 |
516 |

To evaluate the performance of our suggested approaches we implemented these approaches on top of \(K^{\ast}\) algorithm implementation [16], which in turn is built on top of the Fast Downward planning system [17]. The code is available at https://github.com/ibm/kstar. All experiments were performed on Intel(R) Xeon(R) Gold 6248 CPU @ 2.50GHz machines, with the timeout of 30 minutes and memory limit of 3.5GB per run. The benchmark set consists of stripsbenchmarks from optimal tracks of International Planning Competitions 1998-2018. We have manually specified a subset of actions of which to preserve the orders per domain, for a total of 52 domains, with the total number of 1555 tasks. The regular expressions capturing the names of actions whose orders are important are provided in Table 1. We compared our two suggested approaches of extending the POR successor generator (denoted by POR+) and of modifying the definition of generalized strong stubborn sets (denoted by PO-GSSS) to a baseline, running a top-quality planner and post-processing the plans to filter out equivalent plans (denoted by NoPOR). We use \(K^{\ast}\) with symmetry based pruning [9] and lmcutheuristic [18]. We experiment with the atom-centric stubborn sets [15]. In our experiments, we measure the coverage of solving the partially ordered top-quality planning problem for \(q=1\), i.e., finding all non-equivalent cost-optimal plans.

First, to show that we capture a non-trivial subset of actions, Figure [fig:unified] (a) plots the number of order-important compared to the total number of actions. Out
of 1555 tasks, in 15 cases all actions are marked as order-important (nodes on the diagonal), and in 37 cases none were marked as order-important. Moving on to the coverage results, the overall any-time coverage is shown in Figure [fig:unified] (b). Note that both POR+ and PO-GSSS have a very similar performance, significantly outperforming the baseline approach that does not perform partial order reduction. The per-domain
coverage for the full 30 minutes time bound is shown in Table 2. There are 15 domains where the coverage is not the same for all three tested approaches. The most
significant increase in coverage from exploiting partial order reduction appears in the *movie* domain (from 3 to 22), following by *woodworking* domains (from 7 and 2 to 21 and 15). Finally, Figure [fig:unified] (c) depicts the solutions size (number of plans) of the partially ordered top-quality planning problem, comparing to unordered top-quality planning. Both are normalized by the full
top-quality planning solution size, fitting both values into a [0,1] range. Out of 325 tasks where all three of these values are available, 109 are on the diagonal. Out of the other 216 tasks, the largest relative decrease from top-quality solution size
was in *pathways*, from 4M to 8 plans.

We propose a new computational problem in top-quality planning, interpolating between the pure top-quality and the unordered top-quality. We adapt partial order reduction pruning technique to address this new computational problem, showing that such pruning is practically beneficial.

For future work, we would like to explore the possibility to prune all orders during search, while efficiently reconstructing the important orders from the unordered top-quality solution. Another important avenue for future research is how to
efficiently capture a more general class of problems in top-quality that deal with preserving *some* orders. For example, two plans that use different instances of essentially the same action might be considered equivalent from application
perspective. That can happen, for instance, as part of translation from PDDL to sas\({}^{+}\).

[1]

Nguyen, T. A.; Do, M. B.; Gerevini, A.; Serina, I.; Srivastava, B.; and Kambhampati, S. 2012. Generating diverse plans to handle unknown and partially known user preferences.
*Artificial Intelligence*, 190: 1–31.

[2]

Katz, M.; and Sohrabi, S. 2020. Reshaping Diverse Planning. In , 9892–9899.

[3]

Katz, M.; Sohrabi, S.; Udrea, O.; and Winterer, D. 2018. A Novel Iterative Approach to Top-k Planning. In de Weerdt, M.; Koenig, S.; Röger, G.; and Spaan, M., eds.,
*Proceedings of the Twenty-Eighth International Conference on Automated Planning and Scheduling (ICAPS 2018)*, 132–140. AAAI Press.

[4]

Speck, D.; Mattmüller, R.; and Nebel, B. 2020. Symbolic Top-k Planning. In , 9967–9974.

[5]

Katz, M.; Sohrabi, S.; and Udrea, O. 2020. Top-Quality Planning: Finding Practically Useful Sets of Best Plans. In , 9900–9907.

[6]

Katz, M.; and Lee, J. 2023. K* and Partial Order Reduction for Top-quality Planning. In .

[7]

Dimopoulos, Y.; Gerevini, A.; Haslum, P.; and Saetti, A. 2006. The benchmark domains of the deterministic part of IPC-5. In *Fifth International Planning
Competition (IPC-5): Planner Abstracts*, 14–19.

[8]

Keyder, E.; and Geffner, H. 2009. Soft Goals Can Be Compiled Away. *Journal of Artificial Intelligence Research*, 36: 547–556.

[9]

Katz, M.; and Lee, J. 2023. K* Search Over Orbit Space for Top-k Planning. In Elkind, E., ed., *Proceedings of the 32nd International Joint Conference on Artificial
Intelligence (IJCAI 2023)*. IJCAI.

[10]

Wehrle, M.; and Helmert, M. 2014. Efficient Stubborn Sets: Generalized Algorithms and Selection Strategies. In Chien, S.; Fern, A.; Ruml, W.; and Do, M., eds., *Proceedings of the
Twenty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2014)*, 323–331. AAAI Press.

[11]

Bäckström, C.; and Nebel, B. 1995. Complexity Results for SAS\(^{+}\) Planning. *Computational
Intelligence*, 11(4): 625–655.

[12]

Katz, M.; Lee, J.; and Sohrabi, S. 2024. Unifying and Certifying Top-Quality Planning. In Bernardini, S.; and Muise, C., eds., *Proceedings of the Thirty-Fourth International
Conference on Automated Planning and Scheduling (ICAPS 2024)*. AAAI Press.

[13]

Wehrle, M.; and Helmert, M. 2012. About Partial Order Reduction in Planning and Computer Aided Verification. In McCluskey, L.; Williams, B.; Silva, J. R.; and Bonet, B., eds.,
*Proceedings of the Twenty-Second International Conference on Automated Planning and Scheduling (ICAPS 2012)*, 297–305. AAAI Press.

[14]

Alkhazraji, Y.; Wehrle, M.; Mattmüller, R.; and Helmert, M. 2012. A Stubborn Set Algorithm for Optimal Planning. In De Raedt, L.; Bessiere, C.; Dubois, D.;
Doherty, P.; Frasconi, P.; Heintz, F.; and Lucas, P., eds., *Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012)*, 891–892. IOS Press.

[15]

Röger, G.; Helmert, M.; Seipp, J.; and Sievers, S. 2020. An Atom-Centric Perspective on Stubborn Sets. In Harabor, D.; and Vallati, M., eds., *Proceedings of the 13th
Annual Symposium on Combinatorial Search (SoCS 2020)*, 57–65. AAAI Press.

[16]

Lee, J.; Katz, M.; and Sohrabi, S. 2023. On K* Search for Top-k Planning. In .

[17]

Helmert, M. 2006. The FastDownward Planning System. *Journal of Artificial Intelligence Research*, 26: 191–246.

[18]

Helmert, M.; and Domshlak, C. 2009. Landmarks, Critical Paths and Abstractions: What’s the Difference Anyway? In Gerevini, A.; Howe, A.; Cesta, A.; and Refanidis, I., eds.,
*Proceedings of the Nineteenth International Conference on Automated Planning and Scheduling (ICAPS 2009)*, 162–169. AAAI Press.