1 Introduction↩︎

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.

2 Background↩︎

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

2.1 Top-quality Planning↩︎

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\).

2.2 Partial Order Reduction↩︎

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

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

3 Partially Ordered Top-Quality Planning↩︎

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.

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.

4 Solve Partially Ordered Top-Quality Planning↩︎

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.

4.1 Extending The Reduced Successors↩︎

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.

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.

4.2 Modifying Partial Order Reduction↩︎

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.

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\)

5 Experimental Evaluation↩︎

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.

6 Discussion and Future Work↩︎

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\({}^{+}\).

References↩︎