Unifying and Certifying Top-Quality Planning

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-06 05:29:18

Abstract: The growing utilization of planning tools in practical scenarios has sparked an interest in generating multiple high-quality plans. Consequently, a range of computational problems under the general umbrella of top-quality planning were introduced over a short time period, each with its own definition. 
In this work, we show that the existing definitions can be unified into one, based on a dominance relation. The different computational problems, therefore, simply correspond to different dominance relations. 
Given the unified definition, we can now certify the top-quality of the solutions, leveraging existing certification of unsolvability and optimality.  We show that task transformations found in the existing literature can be employed for the efficient certification of various top-quality planning problems and propose a novel transformation to efficiently certify loopless top-quality planning.

Main paper: 
 introduction: 
 A body of research on generating plans of top quality (Katz et al. 2018; Speck, Mattmüller, and Nebel 2020; Lee, Katz, and Sohrabi 2023) has recently yielded various computational problems, including unordered top-quality planning 20 (Katz, Sohrabi, and Udrea 2020) , subset top-quality planning (Katz and Sohrabi 2022) , and loopless top-k planning (von Tschammer, Mattmüller, and Speck 2022) . Each of these problems is defined in an ad-hoc manner, addressing specific issues, often identified by an application of interest. For instance, unordered top-quality planning addresses the equivalence of plans that perform the same actions in a different order, a property that holds in many applications. Subset top-quality planning handles unnecessary actions on plans, while the loopless setting specifically addresses unnecessary loops on plans. Clearly, these problems cover only a fraction of possible cases, and there may be various yet unspecified computational problems of practical use. As it is impractical to specify each such computational problem separately, we propose to unify the existing definitions under the framework we call dominance top-quality planning. Essentially, any relation over plans defines a computational problem in top-quality planning and the definition specifies whether a set of plans constitutes a solution to the problem. The natural next step is to check whether a set of 40 plans is a solution to the problem. We follow the existing work on certificates of unsolvability (Eriksson, Röger, and Helmert 2017) and of optimality (Mugdan, Christen, and Eriksson 2023) and propose certifying top-quality planning solutions. We show how to certify top-quality for the unified definition, exploiting existing tools that can certify optimality (Mugdan, Christen, and Eriksson 2023) . Further, for the computational problems of unordered top-quality planning and subset top-quality planning, the existing in the literature task transformations (Katz, Sohrabi, and Udrea 2020; Katz and Sohrabi 2022 ) can be used for efficient certification. For loopless top-quality planning no such transformation exists. We close the gap by introducing a new transformation that allows us to efficiently certify solutions for loopless top-quality planning.A planning task Π = V , O, s 0 , s , cost in SAS + formalism (Bäckström and Nebel 1995) consists of a finite set of finite-domain state variables V, a finite set of actions O, an initial state s 0 , and the goal s . Each variable v ∈ V is associated with a finite domain D(v) of values. An assignment of d ∈ D(v) to v ∈ V is denoted by v,d . A partial assignment p maps a subset of variables V(p) ⊆ V to values in their domains. For a variable v ∈ V and a partial assignment p, the value of v in p is denoted by p[v] if v ∈ V(p)and is undefined otherwise. A full assignment s is called a state, and the set of all states is denoted by S. State s is consistent with a partial assignment p if they agree on all variables in V(p), denoted by p ⊆ s. [v] = eff (o)[v] for all v ∈ V(eff ), and s o [v] = s[v]for all other variables. An action sequence π = o 1 . . . o n is applicable in state s if there are states s 1 , . . . , s n+1 such that s = s 1 , o i is applicable in s i and s i o i = s i+1 for 0 ≤ i ≤ n. We denote s n by s π . An action sequence with s ⊆ s 0 π is called a plan. The cost of a plan π, denoted by cost(π) is the sum of the costs of the actions in the plan. The set of all plans is denoted by P Π , and an optimal plan is a plan in P Π with the minimum cost. Next, we present the top-k planning problem, as de-fined by Sohrabi et al. (2016) and Katz et al. (2018) . Given a classical planning task Π and a natural number k, find a set of plans P ⊆ P Π that satisfy the following properties: (I) For all plans π ∈ P , if there exists a plan π ∈ P Π such that cost(π ) < cost(π), then π ∈ P , and (II) |P | ≤ k, and if |P | < k, then P = P Π . Note that cost-optimal planning is a special case of top-k planning for k = 1. Extending costoptimal planning, top-quality planning (Katz, Sohrabi, and Udrea 2020) deals with finding all plans of up to a specified cost. Given a planning task Π and a number q ∈ R 0+ , find the set of plans P = {π ∈ P Π | cost(π) ≤ 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 100 task Π, an equivalence relation N over its set of plans P Π , and a number q ∈ R 0+ , find a set of plans P ⊆ P Π such that π∈P N [π] 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 105 from the application perspective. In other words, when you can reorder some of the actions in a plan and still get a valid plan. The corresponding problem is called unordered topquality planning and is formally specified as follows. Given a planning task Π and a number q ∈ R 0+ , find a set of plans 110 P ⊆ P Π such that P is a solution to the quotient top-quality planning problem under the equivalence relationR U = {(π, π ) | π, π ∈ P Π , MS(π) = MS(π )}, where MS(π) is the multi-set of the actions in π. Going beyond equivalence relations, let R ⊂ = {(π, π ) | MS(π) ⊂ MS(π )} denotethe relation defined by the subset operation over plan action multi-sets. The subset top-quality planning problem (Katz and Sohrabi 2022 ) is defined as follows. Given a planning task Π and a natural number q, find a set of plans P ⊆ P Π s.t. (i) ∀π ∈ P , cost(π) ≤ q, and (ii) ∀π ∈ P Π \ P with 120 cost(π ) ≤ q, ∃π ∈ P s.t. (π, π ) ∈ R ⊂ . In words, a plan π with cost(π) ≤ q may be excluded from the solution to the subset top-quality planning problem only if its subset is part of the solution. Note, while a top-quality and unordered topquality solutions are also subset top-quality solutions, we are 125 interested in finding the smallest (in the number of plans) such solutions. While unordered top-quality solutions can be of infinite size, the smallest subset top-quality planning solutions are always finite. Yet another problem is the loopless top-k planning problem (von Tschammer, Mattmüller, and Speck 2022). It is defined in the literature similarly to the top-k planning problem, where the set of all plans P Π is replaced with the set of all loopless plans P Π . Here, we consider the corresponding loopless top-quality planning problem. We therefore define the top-quality variant as follows.Given a planning task Π and a number q ∈ R 0+ , find the set of plans P = {π ∈ P Π | cost(π) ≤ q}.We start by noticing that the definition for quotient topquality planning can be rewritten similarly to the one 140 for subset top-quality planning, by requiring the plans of bounded by q costs missing from the solution to be in relation to the ones that are in the solution. With that, given any relation R, we extend the Definition 1 of Katz and Sohrabi (2022) as follows.Definition 1 Let Π be some planning task, P Π be the set of its plans, and R be some relation over P Π . The dominance top-quality planning problem is defined as follows. Given a natural number q, find a set of plans P ⊆ P Π such that 1. ∀π ∈ P , cost(π) ≤ q, 2. ∀π ∈ P with cost(π ) ≤ q, ∃π ∈ P such that (π, π ) ∈ R, 3. P is minimal under ⊆ among all P ⊆ P Π for which conditions 1 and 2 hold.Observe that for an empty relation we get the top-quality planning problem, for R U we get the unordered top-quality planning (Katz, Sohrabi, and Udrea 2020), while for R ⊂ we get sub-multi-set top-quality planning (Katz and Sohrabi 2022) . It is worth noting that in these publications, the third condition was not part of the definition, but the aim was to find solutions of minimal size.Moving on to loopless top-quality planning, while the existing definition is not expressed via a relation over plans, there can be various such relations. While varying in detail, the idea is the same -a plan without loops dominates plans with loops. Concrete relations may require that the loopless plan could be obtained from the one with loops by removing these loops. A relation we adopt in this work, however, is somewhat more general: (π, π ) ∈ R if and only if (a) π is a loopless plan and (b) if S are the states traversed by π, then π traverses some s ∈ S more than once.Theorem 1 The dominance top-quality planning problem for R is the loopless top-quality planning problem.The proof is deferred to the supplementary material.While none of the common properties of relations (reflexivity, transitivity, and symmetry) are required to make Definition 1 well defined, it is worth discussing the relations we considered so far. The quotient top-quality planning problem in general and unordered top-quality in particular deal with equivalence relations. On the other hand, the relations R ⊂ and R are transitive and anti-symmetric, but they are not reflexive and therefore not a partial order. In principle extending these relations by adding the elements (π, π) for all π ∈ P Π would not affect what is considered to be a solution under the definition. In general, if (π, π ) ∈ R and (π , π ) ∈ R, if both π and π are not in P , while π is, transitivity would suffice to ensure condition 2. It is not strictly necessary though. An example isR = {(π a , π b ), (π c , π d ), (π b , π d ), (π d , π b )} over the set of plans P Π = {π a , π b , π c , π d },all of the same cost q. The set P = {π a , π c } is a solution to the R dominance top-quality problem according to Definition 1. Note that the example relation is neither symmetric nor anti-symmetric.Given a planning task Π and a set of plans P ⊆ P Π , note that it is possible to obtain another (transformed) planning task Π P with the set of plans being P Π \ P (Katz et al. 2018) . The family of such transformations is generally called plan forbidding, and several such transformations exist in the literature, forbidding plans and their reorderings (Katz and Sohrabi 2020; Katz, Sohrabi, and Udrea 2020) or plans and their super-multi-sets (Katz and Sohrabi 2022) .We start with certifying the top-quality planning problem. Theorem 2 A set of plans P can be checked for being a solution to the top-quality planning problem. Proof: P is a solution to the top-quality planning problem if and only if (a) ∀π ∈ P , cost(π) ≤ q, and (b) Π P has no plans of cost smaller or equal to q. That means that we can certify top-quality planning solutions for Π by certifying optimality for the transformed task Π P (Mugdan, Christen, and Eriksson 2023) .Moving now to dominance top-quality planning, for a set of plans P , we define an extended under R set of plansP := P ∪ π∈P {π ∈ P Π | cost(π ) ≤ q, (π, π ) ∈ R}.Theorem 3 If P is a solution to the dominance top-quality planning problem, then P is a solution to the top-quality planning problem.The proof is technical, deferred to the supplementary material. We can now certify solutions to the dominance topquality planning problem.Theorem 4 A set of plans P can be checked for being a solution to the dominance top-quality planning problem.Proof: We can certify P in two steps.• Certify P to be a solution to the top-quality planning problem, and • For every π ∈ P , show that P \ {π} is not a solution to the top-quality planning problem.The latter is needed for certifying the condition 3 of Definition 1. The first two conditions of Definition 1 imply that if P is a solution, then so is its superset. Therefore, it is sufficient to ensure that removing any single plan prevents the extended set from being a top-quality solution.Given P , it can be impossible to compute P explicitly. One example is the R relation, where while the set of all loopless plans P Π is finite and therefore all solutions to the loopless top-quality planning problem are finite, the extended under R set can be infinite. In what follows, we show how to efficiently certify dominance top-quality without explicitly computing P .In practice, when R is specified implicitly, like R U for unordered top-quality, R ⊂ for subset top-quality or R for loopless top-quality, it may be computationally intensive or even infeasible to explicitly generate the extended set P from a solution P . In such cases, instead of transforming Π into a planning task that forbids the set of plans P , we can transform into a planning task Π P that forbids the entire extended set P . Such transformations exist for the cases of R U (Katz and Sohrabi 2020) and R ⊂ (Katz and Sohrabi 2022) .Similarly to the case of top-quality planning, we can now certify P to be a solution to the unordered respectively subset top-quality planning by certifying optimality of the respective transformation. Such transformation however does not exist for loop-less top-quality planning. In what follows, 250 we present a novel transformation for the R relation, allowing us to certify P to be a solution to the loopless topquality planning.Forbidding Plans With Loops Here we present a novel transformation for forbidding plans with loops. Specifically, 255 for a plan π, it forbids π and all π such that (π, π ) ∈ R .The idea is based on the transformation that forbids a single plan (Definition 3 by (Katz et al. 2018 )), with an additional dimension added, ensuring that no action enters the already traversed states of π. Each original action is extended 260 with additional preconditions and effects, allowing to capture whether the execution (a) is following the prefix of the input plan π, (b) diverging from π, or, (c) has already diverged from π. Each of these is further split to sub-cases. Figure 1 visualizes the various sub-cases in different col-265 ors. It shows three different areas of the state space, with the bottom one including the initial state, the top one including only sink states, and the middle one, where all the goal states are. In what follows, we will refer to the colors of the edges to simplify the explanation. Further, in what follows, 270 for simplicity, we use disjunctive preconditions, which can be compiled away by introducing multiple action instances.Let Π = V , O, s 0 , s , cost be a planning task and π = o 1 •. . .•o n be some plan for Π traversing the states s 0 , . . . , s n . For every 0 ≤ i ≤ n, letO i := {o ∈ O | prv (o) ∪ eff (o) ⊆ s i }denote the actions that may lead to the state s i . For an action o ∈ O i , letcond i (o) := s i \ (prv (o) ∪ eff (o))denote the extra condition that would ensure the state achieved by applying o is exactly s i . We denote the negation of cond i (o) bycond i (o) := v∈V(condi(o)) D(v) \ {cond i (o)[v]}.The task Π π = V , O , s 0 , s , cost is defined as follows.• V = V ∪ {v d , v e } ∪ {v i | 0 ≤ i ≤ n}, with v d and v ebeing binary variables and v i being ternary variables,275 • s 0 [v] = s 0 [v] for all v ∈ V, s 0 [v d ] = F , s 0 [v e ] = F , s 0 [v 0 ] = C, and s 0 [v i ] = 0 for all i > 0, and • s [v] = s [v] for all v ∈ V s.t. s [v] defined, s [v d ] = T ,and s [v e ] = F . As mentioned before, the actions O extend the actions in 280 O by introducing additional preconditions and effects, with multiple copies covering the various cases. Specifically,o f i = pre(o i ) ∪ { v e ,F , v d ,F , v i-1 ,C }, eff (o i ) ∪ { v i-1 ,1 , v i ,C }are the copies of the actions on π (colored black in Figure 1 ) that follow the execution of the plan π, until a diverging from π is happening. When that happens, there are five options.First, the first action o = o k+1 diverging from π (after op 1 • . . . • o k were applied) is in O i for some i < k and it reaches an already traversed state s i , with an action copy (red)o e i = pre(o) ∪ { v e ,F , v d ,F , v i ,1 , v k ,C } ∪ cond i (o), eff (o) ∪ { v e ,T } .Second, it reaches a not yet traversed state s j for j > k + 1 with an action copy (magenta)o j = pre(o) ∪ { v e ,F , v d ,F , v j ,0 , v k ,C } ∪ cond j (o), eff (o) ∪ { v d ,T , v j ,1 , v k ,1 } .Third, it reaches the state s k+1 with an action copy (cyan)o k+1 = pre(o) ∪ { v e ,F , v d ,F , v k ,C } ∪ cond k+1 (o), eff (o) ∪ { v d ,T , v k ,1 , v k+1 ,1 } .Forth, it reaches a different state with an action copy (blue)o = pre(o) ∪ { v e ,F , v d ,F , v k ,C } ∪ k-1 i=0 cond i (o), eff (o) ∪ { v d ,T } ∪ { v k ,1 } .Fifth and last, if the action o is not in any O i , 0 ≤ i ≤ n, it reaches a different state with an action copy (violet)o = pre(o) ∪ { v e ,F , v d ,F , v k ,C }, eff (o) ∪ { v d ,T } ∪ { v k ,1 } .Once diverged from π, the action copies only need to record whether they reached one of the states s i more than once. This can be done with the following cases:o i = pre(o) ∪ { v e ,F , v d ,T , v i ,0 } ∪ cond i (o), eff (o) ∪ { v i ,1 } ,for reaching s i for the first time (green),o i e = pre(o) ∪ { v e ,F , v d ,T , v i ,1 } ∪ cond i (o), eff (o) ∪ { v e ,T } ,for reaching s i for the second time (red), or EQUATIONEQUATIONo) . The costs of these copies is the same as the cost of the original action. We say that Π π is the loopless transformation of Π under π. Theorem 5 Let Π be a planning task, π be its plan and Π π be the loopless transformation under π. Then Π π forbids exactly π and all plans dominated by π. The proof is deferred to the supplementary material.For top-k planning problem as well, we can certify P to be top-k solution. Theorem 6 A set of plans P can be checked for being a solution to the top-k planning problem.Proof: First, if |P | < k, we certify unsolvability of Π P . Otherwise, let m = max π∈P cost(π) and P 1 := {π ∈ P | cost(π) < m} and P 2 := {π ∈ P | cost(π) = m} be the partition of P into the set of plans of maximal cost and the set of plans of lower than maximal cost. If P 1 is empty, then all plans in P are of the same cost m, and we can certify top-k planning by certifying optimality of m. Now, assume that P 1 is not empty and let q = max π∈P1 cost(π) be the maximal cost in P 1 . Observing that P 1 must be a solution for the top-quality planning problem for q, we can certify top-k planning solution in two steps: (I) certify P 1 to be a solution to the top-quality planning problem, and (II) certify optimality of m for Π P1 .We present a definition that unifies existing computational problems under the umbrella of top-quality planning. Based on the definition, we show that certification of top-quality can be obtained with the help of task transformations and certification of optimality. We further show that existing task transformations can be used for efficient certification of unordered and subset top-quality planning problems. Finally, we present a novel transformation and use it for certifying loopless top-quality planning.In the future, we would like to certify planning algorithms for the various top-quality problems. While the ForbidIterative planners are relatively straightforward to certify, other methods, such as K * search or symbolic search are more challenging to certify. Same can be said for search pruning techniques used in top-quality planners, such as symmetry reduction or partial order reduction. Another interesting direction for future work is to use the suggested in this work transformation for loopless top-quality planning, e.g., as part of the ForbidIterative framework. While the transformation significantly increases the number of actions, it might still pay off in several domains. 
 
 Appendix:  


Decision: This paper is sort of borderline. There is nothing inherently wrong with it, but all reviewers agree that a longer paper, containing more background on the different variants of the top-quality problem, the compilations used (including their complexity, and an empirical evaluation of them in comparison with other methods) would be better. (If the aim is to unify a set of different problem formulations, then it makes sense to also present a thorough survey of work on those problems.) The question comes down to how valuable it will be to the planning community to have this short paper published first (hopefully to be followed by a longer one that includes all these things) vs having only a longer paper published in the (hopefully near) future. The majority (2 out of 3) arrived at the answer that this short paper would have some value, and hence the recommendation is to accept, but it is a weak recommendation.

Reviews: review: strength_weakness: strength_weakness: I'm not clear about the overall impact of the paper for future development in the "top-quality" planning theme. Researchers will come up with new variations and propose approaches specifically designed to solve such variations. While those variations will likely fall into this "dominate top-quality" umbrella, I'm not sure yet if ideas and techniques proposed here will influence or get used in such work.

While I understand that probably each domination relation will warrant different techniques best suited to solve them and it’s ok to not presenting empirical evaluation for dominance top-quality planning. However, some empirical evaluation for the transformation presented in the “Efficient Computation” would be good to show that it’s actually efficient and practical. Since the transformation introduce new preconditions and effects and copies of the existing tasks, it’s not clear if solving the transformed problem is more efficient than utilizing the existing approach so it would be nice to back it up empirically.
questions: questions: 1. Did you try to implement the algorithms presented in this paper: (1) to certify top-quality, dominate top-quality, top-k planning combining optimality certification + forbidding plan transformation; (2) transformation to forbid plans with loop and if so are they efficient to solve?
strength_weakness: strength_weakness: The paper is short and terse, which is unfortunate given that it also contains supplemental material.  Given that some of the material is complex, a longer paper with more explanations and more complete proofs would be more accessible.

There are no empirical results showing how long it takes to perform the certification operations.  While this is primarily a theory paper, results on complexity alone don't really give a sense of how 'hard' the certification problem is.
questions: questions: Specific comments:

p. 1: I see different notational conventions used for non-negative real costs: $\mathbb{R}_{geq 0}$ and $\mathbb{R}_+$ . I don’t think I’ve ever seen $\mathbb{R}^{0+}$.  (A nit)
p. 2: if plans can be partial order, we wouldn’t need unordered top quality, right?  (Top-K would be sufficient). (This is the only version of top-k I find trivially objectionable, all the others are very reasonable.)
p. 2: I don’t understand why unordered top quality plan solutions can be of infinite size. Is it because action costs can be zero?  If costs are strictly greater than zero then this would not happen?  (Well, even then, if you were really evil I suppose you could define an infinite number of actions with an infinite number of nonzero costs…)
p. 2-3: please say something about the complexity of the plan forbidding transformations.  Presumably they are polynomial time, but are they linear in the size of the set of plans?  Worse?
p. 3 proof of theorem 2: just to make sure I understand, it seems ‘certifying the transformed task $\Pi_P$’ means ‘find an optimal solution to $\Pi_P$ and make sure this solution has value > q’, which takes the usual amount of time for optimal planning, i.e. PSPACE or EXPTIME or what have you.  Right?
p.3: thm 3.  So you give me a propose solution to dominance planning.  But to check it I need to take this solution and extend it with all plans of top quality.  Do you give me \overline{P} and P?  Or do I have to compute \overline{P} by solving the top quality problem?   What is the complexity of this check?  (It’s dominated by the 2d bullet which requires me to solve a planning problem for every plan in P
p. 3: the forbidding plans with loops has to take a loop less plan to begin with for the forbidding translation, right?  This isn’t made explicit; suggest adding a sentence to this effect.
strength_weakness: strength_weakness: Readability could be improved by adding some more content to the background section (although I understand this is not easy for a short paper). E.g., describing the problem of certifying top-quality planning solutions, which is quite relevant for this paper, and indicating the complexity of the considered computational problems.
The paper uses the expression "efficient computation" in an inform way. I would have liked to see a more detailed/formal analysis about efficiency (either theoretical or experimental/practical) and/or a more elaborated explanation of what efficiency means in this context.
questions: questions: Can you clarify why "instead of transforming \Pi into a planning task that forbids the set of plans P, we can transform into a planning task \oveline{\Pi}_P that forbids the entire extended set \overline{P}" is more efficient?
What  does "efficient computation" mean?
What is the computational cost of the transformation proposed for forbidding plans with loops?