An Analysis of the Decidability and Complexity of Numeric Additive Planning

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 17:12:23

Abstract: In this paper, we first define numeric additive planning ($\mathrm{NAP}$), a planning formulation equivalent to Hoffmann's Restricted Tasks over Integers. Then, we analyze the minimal number of action repetitions required for a solution, since planning turns out to be decidable as long as such numbers can be calculated for all actions. We differentiate between two kinds of repetitions and solve for one by integer linear programming and the other by search. Additionally, we characterize the differences between propositional planning and $\mathrm{NAP}$ regarding these two kinds. To achieve this, we define so-called multi-valued partial order plans, a novel compact plan representation. Finally, we consider decidable fragments of $\mathrm{NAP}$ and their complexity.

Main paper: 
 introduction: 
 In classical propositional planning scenarios, effects are activations/deactivations of certain propositions, i.e., assignments of truth values ⊤, ⊥. Notice that activating p twice instead of once results in the same state, and, ignoring preconditions, any two (propositional) plans of the form [a, b, c], [a, b, b, c] are equivalent, but [b, a, c] is not equivalent to [a, b, c] in general, i.e., repeating an action without changing the order does not change a propositional plan.Conversely, order could be irrelevant in some numeric planning scenarios. For example, if actions have no preconditions and can only increase or decrease variables by a constant, then it is only relevant to know how often each action should be performed in the plan irrespective of order. Effects in this setting are additive. Since addition is associative, we can assume that all additions occur in parallel. This problem is an essential part of numeric planning, where additive effects are allowed, but actions could also have preconditions, i.e., where both order and the number of parallel additive effects are relevant.To illustrate the difference, consider the effects of actions like pay ten euros and open the door. One can immediately see the difference when one imagines a plan containing two successive repetitions of each action. If a minimal plan begins with the action open the door, there is no need to repeat this action later on in that plan, as long as none of its effects is deactivated by a following action, like close the door.Figure 1 : Demonstration of the expressive power of additive (below) compared to de-/activation effects (above). Compare p, q, r with x, y, z, respectively, in all actions (rectangles) and the resulting states (ellipses) for all three plans. However, one can easily imagine two successive repetitions of pay ten euros, without any of its effects getting "deactivated" or "reversed". One could perform these two actions 45 in parallel via pay twenty euros. This looks intuitive here, but it becomes hard to know which actions can be done in parallel when the problem is more complicated, e.g., if pay ten euros has preconditions that make it not always repeatable twice in a row.To finalize our observations, we show in Fig. 1 six plans, three propositional (above), and three numeric (below). All actions are described by their preconditions above and effects below the action name. By x+=1 we mean that the action increments x by 1 after applying it, and x-=1 means 55 that the value is decremented by 1. Initially, p, q, r are deactivated (false), and x = y = z = 0. Compare the plans from left to right, where (1) on the left, we begin with a simple plan; (2) in the middle, we repeat the action b; and (3) on the right, we add a negative effect to a. Notice that all precon-60 ditions and effects have the same overall structure w.r.t. the variables p with x, q with y, and r with z. We can see that all three propositional plans result in the same state, while the numeric plans result in three different states. These examples illustrate the additional expressive power of numeric additive over activation/deactivation effects.In a nutshell, we say that in the plan [a, b, b, c], there are two parallel repetitions of b, and in the plan [a, b, d, b, c] , there are two sequential repetitions of b, because they are separated by an occurrence of d. As discussed before, no parallel repetitions of propositional actions like open the door are relevant. However, numeric planning is a superset of propositional planning, i.e., parallel and sequential repetitions of actions could be needed for the solution. This paper aims to study the differences between these two kinds and find a compact and least committing representation for both. This will help structure the search for solutions to the planning problem and lead to novel decidable fragments.Paper outline: We define the planning problem and study its expressivity in Section 3. Then, in Section 4, we define a new way of representing plans. In Section 5, we introduce the solving algorithm. Finally, we define three decidable fragments in Section 6.Introducing unbounded numeric variables makes planning problems undecidable in general (Helmert 2002) . In recent years, many results have been published to tackle this issue by introducing restrictions on the planning problem: (Shin and Davis 2005; Gerevini, Saetti, and Serina 2008; Eye-90 rich, Mattmuller, and Roger 2009; Coles, Fox, and Long 2013; Scala et al. 2017; Aldinger and Nebel 2017; Li et al. 2018; Piacentini et al. 2018; Kuroiwa et al. 2021; Shleyfman, Kuroiwa, and Beck 2023; Gnad et al. 2023) . Specifically, Helmert (2002) presents decidable cases based on restricting the allowed mathematical functions and relations. We continue his work and identify decidable fragments based on their structural properties, similar to the causal graphs approach (CG) (Jonsson and Bäckström 1998; Brafman and Domshlak 2003; Helmert 2004; Giménez and Jons-100 son 2008) . We consider a variant of simple numeric planning (SNP) (Scala et al. 2016) , which is equivalent to restricted tasks (RT) (Hoffmann 2003) . Shleyfman et al. (2022; 2023) show how RT/SNP with restrictions on the causal structure of variables is in PSPACE. We extend this idea by focus-105 ing on the causal structure of actions. Additionally, many complexity results are considered w.r.t. total or partial order plans, while we use the ability for some exponential length plans to be described with a polynomial-size representation.Furthermore, many results on the advancements of plan-110 ning solvers show how numeric planning could benefit from heuristic search, e.g., by using abstraction methods: (Seipp and Helmert 2014; Illanes and McIlraith 2017, and others) . We follow the line of Hoffmann, who (2003) proposed an extension of delete lists, a relaxation of propositional planning, to numeric planning. We will extend his ideas about relaxed planning graphs (RPG) by ignoring "violations". Last but not least, we base our approach on some of the insights from LP-RPG (Coles et al. 2008 ) about the number of occurrences of an action in a plan, but we will use more general terms like sequential and parallel repetitions.The following definition will allow for a straightforward translation of the planning problem into an ILP system, as we will see in Section 4. Although, at first glance, the formulation lacks propositional preconditions and effects, we will include these later. We use the Greek letter π for preconditions and σ for the additive (sum) effects.Definition 1. A numeric additive planning domain (denoted NAD) is a tuple A = (A, V, σ, π), where A, V are finite nonempty sets of actions and variables, respectively. Additionally, σ : A×V → Z defines the additive effect of each action on each variable, and π : A × V → Z ∪ {-∞} defines the numeric precondition of each action for each variable.For each action b ∈ A and each variable x ∈ V , it is meant for the current value of x to be greater than or equal to π(b, x) for b to be applicable. If π(b, x) = -∞, then the preconditions of b are not dependent on the value of x. After applying b, the current value of x is incremented/decremented by the (constant) integer value σ(b, x) ∈ Z. If σ(b, x) = 0, the action b has no effect on variable x. We say[x ≥ v] is a precondition of b if π(b, x) = v, and [x+=v] is an effect of b if σ(b, x) = v as well as [x-=v] if σ(b, x) = -v, for v ∈ Z.Definition 2. For a NAD A = (A, V, σ, π), we define a state S : V → Z as a function assigning an integer value to each variable. Additionally:• For an action a ∈ A, a state satisfies the preconditions of a iff S(x) ≥ π(a, x) for all x ∈ V (denoted S ⊨ a). • An action a ∈ A can be added to a state by adding its effects, i.e., (S + a)(x) := S(x) + σ(a, x) for x ∈ V .With states defined, we are ready to define the validity of any sequence of actions. Definition 3. For n ∈ N ≥1 , and actions a 1 , ..., a n ∈ A, we call the sequence of actions l := [a 1 , a 2 , ..., a n ] a plan. We denote the length of the plan with |l| = n, and say that l is valid from an initial state S 0 :V → Z if S i ⊨ a i , with S i := S i-1 + a i-1 if i ≥ 1, for all i ∈ {0, .., n}.In this paper, unlike many other planning formulations, we will encode the set of goal states as a precondition of one of the actions (usually named g). In other words, we ask the following question: Given an initial state S 0 and an action g, does a valid plan that ends with g exist? I.e., is it possible to reach a state S s.t. g is applicable (S ⊨ g)? Therefore, we will denote the planning problem as {S 0 → g} A . Definition 4. For a NAD A = (A, V, σ, π), an initial state S 0 : V → Z, and an action g ∈ A, a numeric additive planning problem (denoted NAP) {S 0 → g} A is defined as the set of plans l = [a 0 , ..., a n ], s.t. a n = g and l is valid from S 0 .If the context is clear, we will use A, V, σ, π without explicitly referring to that A = (A, V, σ, π), when speaking of NAP {S 0 → g} A .Preconditions: In NAP, we only allow preconditions of the form [x ≥ v] for a variable x ∈ V and an integer v ∈ Z. However, for any precondition of the form [x ≤ v], we can define a new variable x s.t. for all a ∈ A, σ(a, x) = -σ(a, x). This implies that if the initial state S 0 : V → Z, respects S 0 (x) = -S 0 (x), then, any reachable state S : V → Z from S 0 , we get S(x) = -S(x). I.e.,[x ≤ v] is equivalent to [x ≥ -v],which is representable in NAP. We can, therefore, represent preconditions of the form[x = v] as [x ≥ v]∧[x ≥ -v].Additionally, preconditions of the form [x > v] can be represented by [x ≥ v +1], since we only deal with integers. Finally, if an action a has a disjunction in its preconditions, e.g.,[x ̸ = v] ≡ [x > v] ∨ [x < v],we can create two actions a 1 , a 2 with the same effects but a 1 has [x > v] as its precondition and a 2 has [x < v]. Finally, for an action a with the conditional effect[x ≥ v] → [y+=w 1 ] ∧ [x < v] → [y+=w 2 ], for x, y ∈ V, v, w 1 , w 2 ∈ Z,we can define two actions a 1 , a 2 s.t. a 1 is applied in the first situation (precondition [x ≥ v] and effect [x+=w 1 ]), and a 2 is applied in the second situation. It is also important to mention that preconditions with a linear combination of variables, e.g., [x + 2y -z ≥ v], can be represented in NAP by defining a new variable t := x + 2y -z and ensuring that all the effects on x, y, z are combined with effects on t with a factor 1, 2, -1 respectively. All these transformations can be easily implemented and reversed. For this reason, in NAP, we can focus only on conjunctions of preconditions of the form [x ≥ v] and unconditional additive effects.Effects: NAP lacks the de-/activating effects used in propositional planning (PP). However, this does not necessarily mean that PP cannot be reduced to NAP in polynomial time. Given a PP domain A := (A, P, eff, pre) with sets of actions and propositions A, P , respectively. We define Lit := {p, ¬p : p ∈ P } as the set of literals. Finally, pre, eff : A → 2 Lit are functions defining the preconditions and effects of each action. A state in PP is a function S : P → {⊤, ⊥}. A PP problem is given as a tuple (A, I, G), where I is the initial state and G ⊆ Lit describes a set of goal states S s.t.S(p) = ⊤ iff p ∈ G, and S(p) = ⊥ iff ¬p ∈ G.For each proposition p, we create a numeric variable x p . For an initial state I, we create an initial state S I , s.t.S I (x p ) = 1 iff I(p) = ⊤, and S I (x p ) = 0 iff I(p) = ⊥.For each propositional precondition p, we add a numeric precondition [x p = 1], and for ¬p, we add [x p = 0]. And finally, for each propositional effect p, we add a numeric effect [x p +=1] and for ¬p, we add [x p -=1]. Notice that in PP, as discussed in the introduction, an action a with a precondition p can be applied even if p was activated twice before, but this does not work for our current translation. E.g., for a proposition r, propositional actions a, b, g, and initial state [a, b, b, g] is not valid from S I in NAP with the translation above because the state S before applying g has S(x r ) = 2, but g has the precondition [x r = 1], compare the middle plans in Fig. 1 . Therefore, for each proposition r, we need two new actions c r , c ¬r that cor-rect the numeric value representing a proposition r from any value greater than 1 to 1 and from any value less than 0 to 0, i.e., c r has the precondition [x r > 1] and effect [x r -=1], and c ¬r has the precondition [x r < 0] and effect I, if I(r) = ⊥, r ∈ eff(b) ∩ pre(g), and ¬r ̸ ∈ eff(a), then, if [a, b, b, g] is valid from I in PP,[x r +=1]. Now, if [a, b, b, g] is valid from I in PP, then, [a, b, b, c r , g] 235 is valid from S I in NAP,We study the complexity of NAP w.r.t. ∥A∥, the minimal number of bits required to encode a NAD A.Theorem 1. Hoffmann's Restricted Tasks (RT) can be reduced to NAP in polynomial time.Proof. NAP is similar to RT, except that it does not allow 245 for propositional preconditions, which were shown to be included in NAP without exponential blowup. Additionally, we can transform any NAP over rationals into a NAP over integers by scaling all variables with suitable factors. Parts of this proof are discussed by Hoffman (2003) .Therefore, NAP is undecidable as it can model Abacus programs, as Helmert (2002) shows. In that paper, a NAP problem is equivalent to PLANEX-(C c , C c , E ±c ). Gnad et al. (2023) show that multiplication and division by constant and general assignment effects are included in RT/-255 NAP, proving the undecidability by reducing Collatz problems to it.An investment company starts with an initial capital c 0 ∈ N and can perform buying and selling actions to reach a goal 260 profit of p ∈ N. Let us model a small example of this problem as NAP: We define the variables c for the current capital and q for the number of products in stock. Additionally, two actions: b for buying one instance of a product for 4 units of money, σ(b, c) = -4, preconditioned by having this amount 265 of money, π(b, c) = 4, and s for selling it with 25% profit, σ(s, c) = 5. In a simpler notation:• The action b, to buy, with preconditions {[c ≥ 4]}, and effects{[c-=4], [q+=1]}. • The action s, to sell, with preconditions {[q ≥ 1]}, and 270 effects {[c+=5], [q-=1]}. • The goal action g, with preconditions {[c ≥ c 0 + p]}.Finally, the initial state is defined by S 0 (c) := c 0 and S 0 (q) := 0. E.g., if p = 2 and c 0 = 8, then l 1 = [b, b, s, s, g] and l 2 = [b, s, b, s, g] are both valid plans. However, if the 275 initial capital c 0 = 7, then only l 2 is valid because there is not enough capital to buy twice in a row before selling once. This example will be used (always in italic) to demonstrate the algorithms discussed in this paper because of its simplicity. Of course, any sophisticated investment process in-280 volves more actions than buying and selling the same product. However, the results of this paper generalize to many other planning domains with complicated dependencies.Let us first discuss the idea of a multi-valued relation. For example, a classical binary relation r over a set K is a subset of K 2 . We can represent this relation by f r : K 2 → {0, 1}, s.t. f r (b, s) = 1 iff (b, s) ∈ r. We extend the concept by allowing values other than 0 and 1, e.g., f r : K 2 → N. We usually represent solutions in planning as a partial order re- For the plan l 2 = [b, s, b, s, g]. Given the (unordered) multi-set A 2 = {g, s, b, s, b}, the MvPOP P 2 over A 2 with max. g described by the following matrix, is an equivalent representation to l 2 (Fig. 2 ): On a side note, for any MvPOP P over A, an ordering of A must exist, s.t., the matrix of P is triangular because otherwise, the represented relation contains a cycle. Definition 5. An MvPOP P over a multi-set A = (A, µ) is a matrix in N |A|×|A| s.t. for all a, b, c ∈ A:• Irreflexive: P[a, a] = 0. • Asymmetric: P[b, a] > 0 implies P[a, b] = 0. • Transitive: P[c, b] > 0 implies P[c, a] ≥ P[b, a].We say that g ∈ A is a maximum (denoted max.) of P iff P[a, g] = 0 for all a ∈ A.Classically, partial order plans are a compact representation of a set of plans, known as linearizations, linear extensions, or total ordering of the partial order. For example, if We call a multi-valued partial order with exactly one linearization a multi-valued total order plan (MvTOP). Lemma 1. For any plan l = [a 0 , ..., a n ] there exists a multiset A = (A, µ) and an MvTOP P l over A with max. a n s.t. lin(P l ) = {l}.Proof. Let µ(a) := # a (l), P l [a j , a i ] = 1 if i < j, and P l [a j , a i ] = 0 else, for a i , a j ∈ A. Then, lin(P l ) = {l}.Next, we will show, through an example, an illustration of the translation of the NAP validity checking of an MvPOP 365 into an ILP satisfiability problem by constraining the states that are produced through the plan.Given l 1 = [b, b, s, s, g]. Let P 1 be an MvPOP over {g, s, b} with max. g, s.t. lin(P 1 ) = {l 1 } (Fig. 2 ):P1 g s b g 0 2 2 s 0 0 2 b 0 0 0For a multi-set A = (A, µ) and a NAD A = (A, V, σ, π), we define the matrices that represent the effects and preconditions, respectively, Σ, Π ∈ (Z ∪ {-∞}) |A|×|V | , with Σ[a, x] := σ(a, x), Π[a, x] := π(a, x), for all actions a ∈ A over all variables x ∈ V . Finally, the matrix S 0 ∈ Z |A|×|V | represents an initial state S 0 , by S 0 [a, x] := S 0 (x) for all a ∈ A, x ∈ V .In our example, Σ and Π over A = {g, s, b} is:Σ c q g 0 0 s +5 -1 b -4 +1 Π c q g 10 -∞ s -∞ 1 b 4 -∞Now, for an initial capital c 0 = 8, if S := S 0 + P 1 Σ, then:380 S[s, q] = 0 + 0 • σ(s, q) + 2 • σ(b, q) = 0 + 0(-1) + 2(+1) = 2 ≥ 1 = Π[s, q] S[g, c] = 8 + 2 • σ(s, c) + 2 • σ(b, c) = 8 + 2(5) + 2(-4) = 10 ≥ 10 = Π[g, c]These are the values of the variables q, c before applying the actions s, g, in any linearization of P 1 , respectively, which satisfy the precondition of both action on the respective variable, ensuring the plan's validity (compare Fig. 2 ). We generalize this result.Lemma 2. If l ∈ {S 0 → g} A , then:S 0 + P l Σ ≥ Πwhere ≥ applies to each element of the matrices.Proof. Let S := S 0 + P l Σ, i. The result of Lemma 2 is not reversible, i.e., if S 0 +PΣ ≥ Π, this does not ensure that P has only valid linearizations. This happens because some actions could be incomparable, similar to partial order plans, where two incomparable actions w.r.t. the partial order relation can cause a threat or a violation. This is solved classically by demotion or promotion.A similar phenomenon arises in MvPOPs, but the number of these incomparable occurrences here matters. In the MvTOP case, the set lin(P) was a singleton, i.e., no incomparability was allowed and thus no threats. However, if lin(P) contains at least two different plans, then at least two occurrences of two actions a, b ∈ A are ordered differently in these lists.We call such occurrences incomparable.In our investment example, in case the initial capital is c 0 = 7, l 1 = [b, b, s, s, g], is not valid because, after one occurrence of b, the remaining capital is 3 < 4 = π(b, c), i.e., the two incomparable occurrences of b cause a threat. In P 1 , I P1 [b, b] = P 1 [g, b] -1 = 2 -1 = 1,which is the number of incomparable occurrences of the action b to itself. Remember that the pair (b, b) causes a threat. Intuitively, there is not enough capital to buy twice in a row. We formalize that in the two following definitions. Definition 8. For actions a, b ∈ A, we say a violates b in A (w.r.t. x ∈ V ) iff π(b, x) > -∞ and σ(a, x) < 0, and write a ∼ x b, as well as a ∼ b if such a variable exists. Definition 9. For a NAD A, the violation multi-valued relation of an MvPOP P over A with max. g w.r.t. variable x ∈ V (denoted V Px ∈ N |A|×|A| ) is defined for a, b ∈ A as:• V P x [b, a] := I P [b, a] if a ∼ x b and b ̸ = g. • V Px [b, a] := 0 else. Back to our example, there is exactly one incomparable repetition of b to itself, i.e.,I P1 [b, b] = 1. Since b ∼ c b, we get V P1 c [b, b] = 1.Therefore, if the initial capital is c 0 = 7, in P 1 (see Fig. 2 ), accounting for an additional b parallel repetition w.r.t. the variable c results in the state S before applying the second b in l 1 = [b, b, s, s, g] ∈ lin(P 1 ), where: , s, s, g] . This corresponds to the fact that we cannot buy twice in a row with such initial capital, i.e., that the second occurrence of b is invalid. We can generalize this result.S(c) = S 0 (x) + a∈{g,s,b} (P 1 [b, a] + V P1 c [b, a])σ(a, c) = 7 + (0 + 1)σ(b, c) = 7 -4 = 3 < π(b, c) Which indicates that P 1 contains a non-valid linearization l 1 = [b, bIn the following theorem, we define sufficient conditions for MvPOP validity by ensuring it contains only valid linearizations. We can use the violation multi-valued relation defined above to account for all violating occurrences of actions to each other and consider the worst-case linearization w.r.t. each variable. Check the supplementary material for the complete proof of this and other theorems.Theorem 2. For an NAP {S 0 → g} A , a multi-set (A, µ), and an MvPOP P over (A, µ) with max. g:If for all x ∈ V : S 0 + (P + V P x )Σ ≥ Π then, lin(P) ⊆ {S 0 → g} AIn this section, we use Th. 2 to reformulate the planning problem as a combination of ILP and search. We have already shown that for a fixed number of sequential repetitions, the problem can be solved by ILP. Let us formalize this in a definition. Definition 10. For a NAP {S 0 → g} A , an numeric additiveplanning fixed problem [S 0 → g] AA is defined as the set of linearizations of the MvPOPs P over a fixed multi-set A with max. g s.t. S 0 + (P + V Px )Σ ≥ Π for all x ∈ V . Notice that a fixed NAP over a multi-set A is empty if no MvPOPs over A with max. g possessing only valid linearizations exist. In the next corollary, we show that solving the NAP by solving fixed NAPs over all possible combinations of sequential repetitions covers all solutions to establish the completeness and soundness of the search. Corollary 1 (NAP as Search). For any NAP {S 0 → g} A :{S 0 → g} A = A=(A,µ) µ:A→N [S 0 → g] A A Proof. From Lemmata 1, 2: {S 0 → g} A ⊆ A=(A,µ) µ:A→N [S 0 → g] A AAnd from Theorem 2:A=(A,µ) µ:A→N [S 0 → g] A A ⊆ {S 0 → g} ACorollary 1 can be used to formulate any NAP as a search problem that aims to find the (minimal) number of needed sequential repetitions of each action, i.e., a minimal multiset A, s.t. an MvPOP P over A containing only valid linearizations exists. We can always find the number of parallel repetitions needed for each action a ∈ A because we can calculate that using ILP, as shown in Th. 2. Therefore, the undecidability of NAP comes from the hardness of finding the needed number of sequential repetitions in the plan (i.e., µ(a) for each action a), specifically, knowing whether such a number exists or not. To demonstrate the importance of this result, notice that, in general, any planning problem is presented as a path search problem in the states graph from the initial state to one of the goal states. Numeric planning is generally undecidable because the number of states is infinite. Finding an upper bound for the number of needed repetitions of each action makes the graph finite, and thus, the problem becomes decidable in that case. However, in our representation, we only need to find an upper bound for the number of sequential repetitions of each action to guarantee decidability. This will be our approach to finding decidable fragments of numeric planning.Input: A NAD A, a g ∈ A, and S 0 :V → Z. Output: A plan l ∈ {S 0 → g} A . µ : A → N : a → 1; while True do A ← (A, µ);Minimize f (P) s.t. for all x ∈ V :S 0 + (P + λV P x )Σ ≥ Π if There exists MvPOP solution P over A with max. g for λ = 1 then return l ∈ lin(P); else if There exists MvPOP solution P r over A with max. g for λ = 0 then Analyse P r and update µ; else return "No solution found";Soundness and Termination of Alg. 1: Th. 2 proves the soundness of Alg. 1, and Corollary 1 and Lemma 1 show that Alg. 1 terminates for any solvable instance of NAP af-505 ter less than |A||l| while-loops, where l is the minimal length solution. We solve an ILP with O(|A| 2 ) integer variables and O(|A||V |) constraints in each while loop. However, if {S 0 → g} A = ∅, the algorithm may never terminate. The minimization objective f (P) is irrelevant for the next sec-510 tions, but we can use it to search for minimal length or cost plans. Furthermore, updating µ relates to adding sequential repetitions. We will discuss that in the next section.We use a parameter λ to differentiate between the standard and relaxed case. If λ = 0, then the term V Px is re-515 moved, and violations are ignored, which makes one sequential repetition of all a ∈ A enough for a (relaxed) solution to exist. The algorithm keeps delivering relaxed solutions P r (with λ = 0) until it finds a valid solution P (with λ = 1). Notice that any valid solution is also a relaxed one. Thus, 520 this relaxation forms an admissible heuristic, extending the relaxed planning graph heuristic (Hoffmann 2003) .Definition 11. For a NAP {S 0 → g} A , a relaxed MvPOP solution P over A of {S 0 → g} A , is an MvPOP over A with max. g s.t. S 0 + PΣ ≥ Π.In a relaxed solution, the preconditions of the first repetition of any a ∈ A are satisfied in at least one linearization. After analyzing the violations in a relaxed solution, we only need to update the number of sequential repetitions (update µ) when required. Therefore, this heuristic can also help by 530 finding an upper bound for the number of sequential repetitions needed for each action.In our investment example with initial capital c 0 = 7, Alg. 1 would first find the relaxed solution l 1 = [b, b, s, s, g], and then notice that no two parallel buying actions can be 535 performed and thus add sequential repetitions of b and s to reach the valid solution l 2 = [b, s, b, s, g] which requires indeed two sequential repetitions of b and s. We will show later that this works for any goal profit p ∈ N.It is easy to see that any NAP without violations (denoted nvNAP) can be solved directly by ILP since any relaxed solution is valid in that case, i.e., one sequential repetition of each action suffices. Let us first enlarge that NP fragment.A threat could emerge whenever two actions a, b ∈ A, with a ∼ b, are considered incomparable in a relaxed solution. The threat can be solved by promoting a over b. However, a could be needed before b as well. Therefore, we might need two sequential repetitions of a to distinguish between occurrences of a before and after b. For this reason, we will rely on the relaxed solution to discover action pairs a ∼ b, where an additional sequential repetition of a is needed. Definition 12. For a relaxed MvPOP solution P over A, we define a binary relation ≾ P over A, s.t., for all a, b ∈ A,a ≾ P b iff a ∼ b, P[b, a] > 0, and I P [b, a] > 0 .Notice that ≾ P is a partial order over A because an MvPOP P respects irreflexivity, asymmetry, and transitivity. Therefore, ≾ P has a maximum for any relaxed solution P. Only one sequential repetition is required of such a maximum because it does not cause any violation to any action occurring after it. However, this only holds for actions not violating themselves; thus, a distinction is needed. Definition 13. For an action a ∈ A in a NAD A, if a does not violate itself (i.e., a ̸ ∼ a , or more precisely, a ̸ ∼ x a for all x ∈ V ), we say that a is a maintainable action.If there exists a state S : V → Z s.t. S ⊨ a and a is maintainable, then a can be repeated arbitrarily often from S using one sequential repetition, i.e., any plan [a, ..., a] is valid from S. Therefore, in this case, we call a maintainable.In our investment example, buying, b, is not-maintainable. For an initial c 0 = 7, b can be applied once but not arbitrarily often. Any repetition after that must be preceded by a sell action, s, to collect capital and be able to buy again.Now that we know how to repeat a maintainable action a ∈ A, we can prove that for a relaxed solution P over A, if we have upper bounds for all the actions that a can cause a threat to, denoted T P (a) := {b ∈ A : a ≾ P b}, then, we can also find an upper bound for a. or I P [b, a] = 0. In the first case, all occurrences of a are incomparable to b in P. Therefore, all a occurrences can be promoted over all b occurrences to solve a threat (a, b). Finally, for I P [b, a] = 0, no ocurrences of a are incomparable to b in P. Therefore, since a is maintainable, i.e., whenever a is applicable once, it can be repeated arbitrarily often with one sequential repetition, we conclude that sequential repetitions of a are required only to differentiate between a oc-590 currences after and before each sequential repetition of an action b only if a ≾ P b.Definition 14. If all actions in a NAP {S 0 → g} A are maintainable, we call it a maintainable NAP problem (denoted mNAP).We can characterize mNAP as the fragment of NAP, where a polynomial number of sequential repetitions is sufficient to find solutions for any solvable instance. Corollary 2. Maintainable NAP is NP-complete.Proof. First, notice that ILP can be reduced polynomially 600 to a NAP without any preconditions, proving the NPhardness. Second, if no relaxed solution exists, the problem is unsolvable. Otherwise, given that all actions are maintainable, the upper bounds µ * can be calculated iteratively for all actions starting from the maxima in A w.r.t. ≾ P . The 605 upper bound for the number of sequential repetitions of any action is at most |A| i=1 i = |A|(|A| + 1), i.e., the size of the MvPOP solution is polynomial w.r.t. ∥A∥.Notice that the plan length could be exponential w.r.t. ∥A∥, if, e.g., the goal g has the precondition [x ≥ 2 n ], then 610 n ≤ ∥A∥. If additionally, σ(a, x) = 1, then, the minimal valid plan [a, ..., a, g] has exponential length w.r.t. n. However, we need only O(n) ⊆ O(∥A∥) bits to encode this plan in an MvPOP, since 2 n is an entry in the matrix, that is, an MvPOP can be exponentially more compact than its 615 linearizations.We can repeat any maintainable action without needing additional sequential copies. This allows us to easily calculate upper bounds for the number of sequential repetitions once a relaxed solution is found. However, this does not apply to non-maintainable actions. In this subsection, we will study how such actions are repeated to avoid irrelevant sequential repetitions during the search. For a ∈ A, let aA * a denote the set of plans that start and end with a. We call a plan l an a-repetition if l ∈ aA * a. E.g., [a, b, c, d, a ] is an a-repetition. We denote withσ(l, x) := c∈A # c (l)σ(c, x)the total effect of a plan l. We will define two types of repetitions that ensure termination for Alg. 1. Definition 15. An a-repetition l ∈ aA * a is called beneficial 620 iff for all x ∈ V , if σ(a, x) > 0, then σ(l, x) > σ(a, x), and l is called de-violating iff for all y ∈ V , if a ∼ y a, then σ(l, y) > σ(a, y).While searching for the number of sequential repetitions needed of an action a ∈ A, beneficial repetitions ensure that 625 the a effects remain after repeating a, i.e., repeating a does not introduce new actions that reverse the effects of a. Furthermore, de-violating repetitions ensure that the need for additional sequential repetitions terminates eventually, i.e., there exists a future point in that search where only parallel repetitions will suffice for the existence of a solution. Let R(a) := {S : V → Z, ∃l ∈ aA * a s.t. l is valid from S} be the set of states from which a can be validly repeated. Definition 16. For an action a ∈ A, we call the function ρ a : R(a) → aA * a an a-repetition policy iff for all states S ∈ R(a), ρ a (S) is valid from S.In our example, the s-repetition Consider that from the initial capital c 0 = 7 we cannot buy twice in a row, but after buying and selling once, the capital increases by 1 and two parallel repetitions of b are possible, i.e. [b, s, b, b, s, s] is valid from that initial state. Definition 17. For an action a ∈ A, an a-repetition policy ρ is called beneficial / de-violating iff for all S ∈ R(a), ρ a (S) is beneficial / de-violating, respectively.In this characterization, any maintainable action a ∈ A has the simplest form of a constant, beneficial and deviolating repetition policy ρ a : R(a) → aA * a : S → [a, a], which is why one sequential repetition of a maintainable action suffices for arbitrarily many parallel repetitions. Definition 18. A NAP is called beneficially maintainable (denoted bmNAP) iff all actions have beneficial repetition policies, and finitely maintainable (denoted fmNAP) iff all actions have beneficial or de-violating repetition policies.We can use these terms to characterize PP within NAP.Lemma 4. There exists a polynomial time reduction of PP to bmNAP.Proof. Remember that we can translate any PP domain to a NAD in polynomial time. Additionally, notice that, in propositional planning, any repetition is beneficial. We can intuitively validate that from our understanding of PP because an activation effect p of a cannot be reversed by an effect ¬p even if it occurs many times before that a. In other words, all actions in PP have beneficial repetition policies. This is the second characterization for the difference between PP and NAP we deliver after stating that only sequential repetitions are needed in PP.Next, we can use induction over the number of nonmaintainable actions to prove that the fragment of NAP with the same restriction (bmNAP) is in PSPACE. For that, we show that a bmNAP problem can be decomposed into mNAP problems, which can be solved with polynomial space. Furthermore, by focusing the search on the number of sequential repetitions needed of exactly one action a ∈ A, we get a trace of successive applications of a repetition policy. We can define the sufficient conditions for how such traces can be pruned in fmNAP to prove the following result.Theorem 5. fmNAP is decidable.Check the supplementary material for full proofs of the last two theorems.We conclude with Fig. 3 : Numeric additive planning (NAP) 695 is a superset of propositional planning (PP) where additive effects are allowed; therefore, in NAP, we distinguish between two types of action repetition: (1) Sequential as in PP, and (2) Parallel as in NAP without violations (nvNAP), a superset of ILP. We use search methods for the first and 700 ILP for the latter. Additionally, solving NAP becomes easier when using a compact and least committing plan representation, multi-valued partial order plans, that differentiates structurally between the parallel and sequential repetitions. In general, finding an upper bound for the number of se-705 quential repetitions needed for each action is sufficient for an NAP to be decidable. We can use this observation to study repetition and define mNAP, an NP-complete fragment of NAP, bmNAP, a PSPACE-complete fragment of NAP and a superset of PP, and fmNAP, a decidable super-710 set of both. Finally, we draw a clearer picture of the factors that make NAP undecidable; we characterize these factors as differences to its subsets PP/nvNAP, since only sequential/parallel repetitions are needed for each subset, respectively. Finally, we deliver an algorithm for NAP that always 715 returns a valid solution if it exists and develop heuristics and pruning rules that help decide in many cases if action repetition is irrelevant based on the type of that repetition.Concerning future work, currently, knowing if an action has a any special kind of repetition policies, e.g. beneficial, 720 is proven to be in PSPACE; we are searching for a tractable characterization of that. Furthermore, we suspect fmNAP to be EXPTime-complete. In general, we believe that developing suitable repetition policies for non-maintainable actions can help discover many more decidable fragments of NAP. 725 
 
 Appendix:  


Decision: After the discussion, all reviewers agreed to accept the paper. The one reviewer that was initially more critical of the contribution raised their evaluation after seeing the rebuttal. Because the discussion quickly converged on acceptance, there wasn't much further discussion.

In the discussion we had, one of the reviewers emphasized again that they would like to see the connections to related work made clearer, with more detail provided. With an increasing number of nontrivial complexity results in the literature, for future readers it is critical that the (at times quite nuanced) similarities and differences are very explicitly delineated. There was agreement on this point.

There was also some discussion regarding the redefinition of the numeric planning formalism compared to earlier work. One reviewer disliked that a new avenue was taken here; another reviewer particularly liked the redefinition and considered it an important contribution, as new formalizations provide new perspectives. (I agree with this point.) In any case even the reviewer that didn't like this aspect didn't see it as a blocker.

Reviews: review: strength_weakness: strength_weakness: As I denoted in the Weaknesses question there are not major weaknesses, thus I live here a set of comments on the minor things in the paper. 

Minor comments:
The sentence below is too cumbersome, and can be divided into two. 
Notice that activating p twice instead of once results in the same state, and, ignoring preconditions, any two (propositional) plans of the form [a, b, c], [a, b, b, c] are equivalent, but [b, a, c] is not equivalent to [a, b, c] in general, i.e., repeating an action without
changing the order does not change a propositional plan.
Specifically, I don’t get why do we need this part “but [b, a, c] is not equivalent
to [a, b, c] in general” it does not illustrate what comes after the i.e.

I don’t get why the next paragraph starts with the word “Conversely”.

I think that for parallel execution you need both associativity and commutativity.


The related work effectively introduces the reader to the work that has been done so far. However, the paper fails to explicitly reference these relationships (some of wich are indicated below) within its main content.

NAD seems to be equivalent to the RT Hoffmann (2003) defined for the interval relaxation, with only difference that the propositional variables were removed, and the goal action introduced. 

In definition 3 something went wrong with the indices “if i ≥ 1, for all i ∈ {0, .., n}.”

You should probably either bold or italicize the definition of the planning problem. Moreover, it feels like a planning problem should be defined prior to a plan. 

In the Expressiveness subsection, the trick on <, \leq precondition is exactly what is done for RT in Hoffmann (2003). You should cite the paper.

Note in this subsection you use interchangeably >, < and \geq, \leq signs. Obviously, >,< can be translated to  \geq, \leq  over integers, but you should probably mention this. 

I like the trick in the Effects. Note that it can make the plans longer by a factor of |P|, if I’m not mistaken. 

After definition 5, the plan linearizations may be exponential in size, if I’m not mistaken. This probably should be mentioned.

In defintions 8 and 9, shouldn't you mentione Coles et al. (2008)?

It seems that NAP without violations is equivalent to interval relaxation as it was defined by Hoffman (2003).

Corollary 2. can bee seen as an extension of the proof the numeric h^{+} is npc (see Kuroiwa et al. 2021)

In the proof of Lemma 4 you use \textit{pre} and \textit{eff} that were not previously defined. 


The definition of the multi-sets of actions \textbf{A} = (A, \mu) is confusing. 

Here are commands for += and -=:
\newcommand{\pleq}{\mathrel{{+}{=}}}
\newcommand{\mineq}{\mathrel{{-}{=}}}
You can also use \models instead of \vDash. 
This is obviously a matter of taste. 

Now, correctly me if I’m wrong, but if I know the bound on the number each action can be applied, denote it #a and I know the effect of this action on the variable x, denote it \sigma(a,x). Then the domain of x is bounded by |x| \leq \sum_{a \in A} #a |\sigma(a,x)|. Thus, the domains of all numeric variables are bounded, and the problem is decidable.


*POST-REBUTTAL*
===============
Thank you for your response. I believe adding the clarifications you pointed out should improve the paper.
questions: questions: 1. You have a section NAP as Search. Do you intened to implement the proposed methods? It looks like using relaxations on the proposed techniques may lead to powerful heuristics.
2. In Related Work you write "We extend this idea by focusing on the causal structure of actions." And this is the only section where the word  "causal" apears. Can you elaborate on the relation of your methods to causal structures?
strength_weakness: strength_weakness: I have two main criticisms:
- Although the paper addresses a known fragment of numeric planning, it does not use established formalisms, but re-defines it in its own terms.
I see that this is beneficial later on to make a better connection to ILP, but it also uses up a lot of space.
The new complexity results only appear on pages 7 and 8, the rest is used to introduce the new formalism (including showing that it's equivalent to established ones) and the matrix-based plan representation.
With that, proofs for two of the main results had to be moved to the appendix.

- The related work section only compares to existing complexity results on a quite high level.
Helmert (2002) already used some ILP to count the number of action occurrences and the corresponding cumulative effects on variables. How does it differ from the proposed approach?
Shleyfman et al (2023) introduces complexity results based on restricting the causal graph. This is very similar to the shown approach (as acknowledged by the authors).
Therefore, some closer comparison would be good to have. It seems like the presented results are more fine-grained, in that they allow cycles in the causal graph, but only if the involved actions are maintainable in some way, i.e. the variables are affected only "positively".


Minor:
- Line 81-84: number references to sections that are not numbered
- line 114: maybe ".. the line of Hoffmann (2003), who proposed.." instead?
- line 115: not sure if ignoring deletes can be considered an "extension of delete lists"
- line 423: there seems to be something wrong here, isn't B(g,b) > 0 a prerequisite?
- Shleyfman,Gnad,Jonsson 2022 vs. 2023: does the workshop version contain separate results; the venue is missing for the 2023 paper
- Venue missing for Scala et al 2016, and "et al" in author list
questions: questions: 1) How hard is it to check if an beneficial / de-violating repetition policy for an action exists.
2) Is relaxed MvPOP a strict generalization of numeric delete relaxation?
Are there action sets/sequences that are relaxed plans under one, but not the other relaxation?
3) What role does the plan representation play for the complexity results?
4) How does your ILP encoding differ from the one in Helmert (2002)?
5) How does maintainability relate to the causal-graph restrictions of Shleyfman et al (2023)?
strength_weakness: strength_weakness: The introduction provides an extensive discusssion of the different kinds of repetitions of actions in plans, but it lacks a clear remark of what the paper is going to present, until the very end where a single short paragraph is devoted to it. After reading the introduction I had precisely in mind what the paper was *about*, but not what were the original contributions. I suggest the authors to give a bit more space to that paragraph, maybe shortening the (well written) related-work section a bit.
questions: questions: N/A