Change the World - How Hard Can that Be? On the Computational Complexity of Fixing Planning Models

1 Intro

Involving humans in the planning process is an important area of interest within the field of automated planning - in particular when tackling real-world problems, since often not all constraints are known in advance and posed by a human expert during planning [Allen and Ferguson, 2002; Myers et al., 2003]. In particular, the planning model used by a system is usually distinct from what a user expects [Chakraborti et al., 2017; 2020], which may consequently lead to a system not finding any solution at all, or a solution that is rejected by the user. The former can be addressed, e.g., by changing the initial state appropriately [G¨obelbecker et al., 2010], whereas the latter, e.g., can be addressed by incorporating change requests on the solution produced [Behnke et al., 2016]. In general, dealing with change requests to plans or models by a human user is formally known as mixed-initiative planning (MIP) [Myers et al., 2003]. The scheme of MIP has been successfully applied, e.g., in activities like route planning [Ferguson et al., 1996], the Mars-rovers [Ai-Chang et al., 2004; Bresina et al., 2005], and the evacuation of inhabitants of a fictitious island [Ferguson and Allen, 1998]. Moreover, imposing changes to the model employed by a system is a way to provide modeling assistance which aims to help humans identify and fix potential problems in a model. A user could, for example, provide a plan claiming it must be a solution based on the current model. If this is not the case, a (MIP) system could suggest model changes to make it a solution thus finding potential modeling mistakes. Those changes can further be regarded as a reconciliation of the current model and the user-desired model, and thus serve as model-based explanations [Chakraborti et al., 2020].

We assume that we are given a sequence of actions that is supposed to be a solution, but it is actually not: either because it is not executable, or because it does not fulfill additional constraints posed on desired solutions. For the latter, we consider the framework of Hierarchical Task Network (HTN) planning (see the work by Bercher et al. [2019] for a recent survey), which is a hierarchical approach to planning where a set of initially given abstract activities need to be refined until a primitive (executable) action sequence was obtained. Relying on this approach allows more control on the produced plans than classical planning as only plans are allowed that follow the user-specified hierarchy [H¨oller et al., 2014; 2016], and was thus also studied and applied in MIP before [Myers et al., 2003; Bresina et al., 2005; Behnke et al., 2016]. To make the action sequence in question a solution to the problem, we consider changing the actions' preconditions or effects (the obtained results are thus relevant to both hierarchical and non-hierarchical planning), as well as changing the model's rules on how plans can be obtained (socalled decomposition methods) by either adding or removing actions to them.

The objective of this paper is to establish the computational complexity of checking the feasibility of such model changes. In HTN planning, checking for feasible changes to the current solution range between NP and undecidability [Behnke et al., 2016], similar to deciding HTN problems [Erol et al., 1996; Geier and Bercher, 2011; Alford et al., 2015]. It turns out that model changes are much easier, namely at most NP-complete.

For changing the task hierarchy, we will restrict ourselves to totally-ordered HTN planning, which is the simplest version of HTN planning and also plays a pivot role in practice as seen by a vast majority of totally ordered planning benchmarks at the International Planning Competition 2020 on HTN planning as well as by the increasing body of research dedicated to total-order HTN planning [Marthi et al., 2007; Alford et al., 2009; Behnke et al., 2018; Schreiber et al., 2019; Behnke and Speck, 2021; Olz et al., 2021]. Furthermore all complexity results obtained will directly serve as lower bounds for the partially ordered setting. Changing preconditions and effects is agnostic against the hierarchy. An overview of our complexity results is given in Tables 1 and 2.

2 HTN Planning

We first introduce the deployed HTN planning formalism, which is a combination of the one by Bercher et al. [2019] and Behnke et al. [2018], the latter introducing a simplification for the total order setting.

Definition 1 (Planning Problem). A (totally ordered) HTN planning problem P is a tuple (D, tnI , sI , g) where 1) D = (F,Np,Nc, δ,M) is called the domain of P, in which F is a finite set of facts, Np is a finite set of primitive task names, Nc is a finite set of compound task names with Nc ∩Np = ∅, δ : Np → 2F × 2F × 2F is a function that maps primitive task names to their actions, and M ⊆ Nc × (Np ∪ Nc)∗ is a set of (decomposition) methods. 2) tnI ⊆ (Np ∪Nc)∗ is the initial task network. 3) sI ∈ 2F is the initial state. 4) g ⊆ F is the goal description.

In the following we will skip the "totally ordered", since we will restrict to this setting throughout the paper. At the centre of the HTN planning formalism is the concept of the task network, which in the total order setting is simply a sequence of task names. Such names are either 1) A primitive task name p ∈ Np, which is mapped to its action through the function δ. The action of p, δ(p) = (prec, add, del) ∈

2F × 2F × 2F , consists of p's precondition, add, and delete list, respectively. If δ(p) = (prec, add, del), we also write (prec(p), add(p), del(p)) for short. 2) A compound task name c ∈ Nc, which can be refined (decomposed) into a task network tn = t1 . . . tn by applying a method m = (c, tn) ∈ M, where tn is a task network. We write tn(m) to refer to tn of m, and |tn| to refer to the length of tn.

Definition 2 (Decomposition). Let tn = tn1 c tn2 be a task network where tn1 and tn2 are two sequences of task names, and c ∈ Nc is a compound task name, and m = (c, tnm) ∈ M be a method. We say m decomposes tn into another task network tn′ , written tn →m tn′ , such that tn′ = tn1 tnm tn2.

Similarly, given a sequence of methods m = m1 · · · mn, a task network tn is decomposed into another task network tn′ by applying m, written tn →∗m tn′ , if and only if there exists a sequence of task networks tn0 · · · tnn such that tn0 = tn, tnn = tn′ , and for each 1 ≤ i ≤ n, tni-1 →mi tni.

A (primitive) task network tn = p1 · · · pn (also called an action sequence) is said to be executable in a state s ∈ 2F if and only if for each 1 ≤ i ≤ n, pi is a primitive task name, and there exists a sequence of states s0 · · · sn such that s0 = s and for each 1 ≤ j ≤ n, prec(pj) ⊆ sj-1 and sj = (sj-1\del(pj)) ∪ add(pj). The state sn is the state produced by tn.

Definition 3 (Solution). Let P = (D, tnI , sI , g) be an HTN planning problem. A task network tn is a solution (or plan) to P if and only if tn is executable in sI, it generates a state s′ ⊇ g, and there exists a sequence of methods m that refines tnI into tn, i.e., tnI →∗m tn.

We will now start our investigations where we have a primitive task network tn given (i.e., an action sequence), which is not a solution - but should be according to a user. According to the solution criteria there are just two possible reasons: Either tn is not executable/does not satisfy all goals 1 , or it does but can not be obtained from the available decomposition methods. To make tn a solution we first consider changing the available methods of the model in Section 3 and then consider changing the action definitions in Section 4.

3 Correcting the Model: ChangingMethods

Given an action sequence that cannot be obtained by a sequence of decomposition methods, we want to change the model so that it can. For this, we first need to consider the allowed changes, which will be adding and deleting actions from the decomposition methods - they will be formally defined next. We start with the ADD-TASK operation, which specifies at which position in a method's task sequence a given action may be added.

Definition 4 (ADD-TASK). Let p be a primitive task name, m = (c, tn) with tn = t1 · · · tn be a method, and 1 ≤ i ≤ n + 1 be an integer. The operation ADD-TASK is a function that takes as inputs m, p, and i and outputs a new method m′ = (c, tn′ ), written m′ = ADD-TASK(m, p, i), such that tn′ = tn1 p tn2 where tn1 = t1 · · · ti-1 and tn2 = ti · · · tn.

1 We do not differentiate between an action sequence that is not executable and a sequence that is executable but does not satisfy all goals, since the latter can be regarded a special case of the former.

The operation DEL-TASK, which allows the primitive task name in a specific position to be removed from a method, is the analogous operation to ADD-TASK for action deletion.

Definition 5 (DEL-TASK). Let m = (c, tn) be a method where tn = tn1 p tn2 with tn1 = t1 · · · ti-1 and tn2 = ti+1 · · · tn be two sequences of task names, and p be a primitive task name. The operation DEL-TASK is a function that takes as inputs m and i and outputs a new method m′ = (c, tn′ ), written m′ = DEL-TASK(m, i), such that tn′ = tn1 tn2.

Given two methods m and m′ and a sequence of methodchange operations X = x1(m1, ∗) · · · xn(mn, ∗) where for each 1 ≤ i ≤ n, xi is either ADD-TASK or DEL-TASK, mi is a method, and ∗ refers to the remaining parameters in the operation xi, we write m →∗X m′ if m1 = m, m′ = xn(mn, ∗), and mi+1 = xi(mi, ∗) for each 1 ≤ i ≤ n - 1. Informally, m→∗X m′ indicates that the methodm′ can be obtained from m by applying a sequence of method-change operations X. We use |X| to refer to the length of X.

Definition 6 (Model Change). Let P = (D, tnI , sI , g) with D = (F,Np,Nc, δ,M) and M = {m1, · · · ,mn} be a planning problem, and X be a sequence of method-changes. A problem P ′ = (D′ , tnI , sI , g) with D′ = (F, Np, Nc, δ, M ′ ) andM ′ = {m′1 , · · · ,m′n } is obtained fromP by applying X, written P →∗X P ′ , if and only if for each 1 ≤ i ≤ n, either m′i = mi or there exists a subsequence 2 Xi of X such that mi →∗Xi m′i .

The definition above highlights that after applying X , nothing changes except the methods in P , which maintain a oneto-one mapping to that in P ′ . For convenience, we use βX : M → M ′ to denote this mapping, where for each method mi with 1 ≤ i ≤ n, βX (mi) = m′i .

Now that we have defined all necessary changes, we can move on to investigate the computational complexity of checking whether such changes exist that turn the given plan into a solution. We will consider two cases, where either we are only given the action sequence, or we are also given a method sequence that is supposed to generate the task network in question - but didn't. We start by investigating the former case.

3.1 Complexity of Fixing the Methods - Given Just an Action Sequence

We first define the decision problem of fixing the method set by an arbitrary number of add or delete operations.

Definition 7 (FIX-METHSX). Let P be a planning problem, and tn be a task network. We define the decision problems FIX-METHSX with X ⊆ {ADD, DEL} and |X| ≥ 1 as: Is there a sequence of method-change operations X, such that P →∗X P ′ , tn is a solution to P ′ , and X consists of ADD-TASK and DEL-TASK operations, according to X?

2 We define a subsequence in a conventional way where a sequence a′ is said to be a subsequence of another sequence a if a′ can be obtained from a by removing some elements from it.

One immediate observation is that if there exists some change sequence that turns tn into a solution, there must be one of length bounded by a polynomial.

Lemma 1. Let P and tn be the planning problem and the task network given by an instance of FIX-METHSX with X ⊆ {ADD, DEL} and |X| ≥ 1. If there exists some sequence of method-change operations that turns tn into a solution, then there exists a sequence X such that P →∗X P ′ , tn is a solution to P ′ , and |X | ≤ |tn| + ∑m∈M |tn(m)|.

Proof. We only consider the case where X = {ADD, DEL} because the upper bound of the sequence X in question in this case is strictly larger than that in the remaining ones.

To prove the argument, we only need to show that the shortest change sequence that turns tn into a solution has the upper bound in question. Suppose X is the shortest change sequence that turns P into another planning problem P ′ such that tn is a solution to P ′ . X can contain at most ∑m∈M |tn(m)| deletions, which is obtained by removing all actions from all methods. Similarly, X contains at most |tn| additions because the number of additions cannot exceed the size of tn. Thus, |X| ≤ |tn| + ∑m∈M |tn(m)|.

Membership of the problem under investigation can thus be easily determined by this lemma.

Theorem 1. FIX-METHSX with X ⊆ {ADD, DEL} and |X| ≥ 1 is in NP.

Proof. For each variant, we can always guess a change sequence X whose length is bounded by a polynomial according to Lem. 1. Transforming P into P ′ thus takes polynomial time. Verifying whether tn is a solution to P ′ can also be done in polynomial time by regarding P ′ as a context-free grammar and tn as a string [Behnke et al., 2015].

We now investigate the hardness of these problems.

Theorem 2. FIX-METHSDEL is NP-hard.

Proof. We reduce from the independent set problem, which is known to be NP-complete [Korte and Vygen, 2008]. Let k, n, r ∈ N, and G = (V,E) with V = {v1, · · · vn} and E = {e1, · · · , er} where ei = (v, v′ ) with some v, v′ ∈ V for each 1 ≤ i ≤ r be a graph. A solution to an independent set problem instance is a subset S of V such that |S| = k, and no two vertices in S are adjacent, i.e., no two vertices are connected by an edge.

To construct an equivalent FIX-METHSDEL instance, we first construct a planning problem P = (D, tnI , sI , g) with D = (F,Nc,Np, δ,M) as follows. We let F = ∅, sI = ∅, g = ∅, and δ : Np → {(∅, ∅, ∅)}. For each vertex vi (with 1 ≤ i ≤ n) in V , we construct a compound task vc i . For each edge ei (1 ≤ i ≤ r) in E, we construct one primitive task epi and one compound task hci (hci is used as a placeholder, which will be explained shortly). Additionally, we construct one more primitive task s (which stands for 'selected'). Taken together, Nc = {vc1 , · · · , vcn , hc1 , · · · , hcr } and Np = {ep1 , · · · , epr , s}. Afterwards, for each compound task vc i (with 1 ≤ i ≤ n), we construct a method msi = (vc i , s) which stands for selecting vertex vi into S. For each hci (with

1 ≤ i ≤ r), we construct a method mhi = (hci , s). Thus, M = {ms1 , · · · ,msn ,mh1 , · · · ,mhr }. We then construct tnI to encode the structure of G, as shown in Figure 1.

The prefix sequence vc1 · · · vcn encodes all the vertices in G, and each subsequence epi hci vc ji vcki with 1 ≤ i ≤ r and 1 ≤ ji, ki ≤ n indicates that the two endpoints of the edge ei are vji and vki . Any method sequence which decomposes tnI into a solution tnP should be a permutation of the one shown in Figure 1, and it encodes how the vertices are selected into S. At the beginning, all vertices are selected. Thus, applying a DEL-TASK operation to a method msi (1 ≤ i ≤ n) is analogous to deselecting vertex vi from the set S.

Lastly, the solution to the independent set problem instance is encoded using the plan tn which is shown in Figure 1. The prefix sequence which repeats s k times indicates that there should be k selected vertices. The suffix sequence indicates that for each edge ei (with 1 ≤ i ≤ r), at most one of its endpoints can be selected. Moreover, a solution to the independent set instance may result in a situation where both endpoints of some edge are not selected. The placeholders hc1 , · · · , hcr in tnI are used to encounter this situation. For some edge ei (1 ≤ i ≤ r) 1) if a solution to the independent set instance asserts that only one endpoint of ei should be deselected, the respective DEL-TASK operation will be applied to mhi , which results in the subsequence epi s to match tn, otherwise 2) mhi will not be modified, which also results in the subsequence epi s.

It then follows that the given independent set instance has a yes answer if and only if the FIX-METHSDEL instance we constructed has one. Further, observe that the size of Np, Nc, and M are bounded by r + 1, n + r, and n + r, respectively, and |tnI| is bounded by n + 4r, the planning problem can be constructed in time O(n + r). Additionally, since |tn| = k + 2r ≤ n + 2r (because k cannot exceed the number of vertices in the graph), we can conclude that the reduction can be done in polynomial time.

We now consider the hardness when only additions are allowed. Since this is somehow analogous to the deletion case, we non-surprisingly obtain NP-hardness as well:

Theorem 3. FIX-METHSADD is NP-hard.

Proof. We again reduce from the independent set problem. We construct a plan tn and a planning problem P which are identical to those we constructed in the proof of Thm. 2 except that for each 1 ≤ i ≤ n, msi = (vc i , ε), and for each

1 ≤ j ≤ r, mhj = (hcj , ε), where ε denotes an empty task network. One can easily verify that there exists solely one primitive task network (solution) into which tnI can be refined, i.e., ep1 · · · epr . Applying ADD-TASK to a method msi is now analogous to selecting the vertex vi into the set S, and we can always apply ADD-TASK to some mhj with 1 ≤ j ≤ r in the case where none of the endpoints of ej are selected. It follows that the independent set problem has a yes answer if and only if the problem we constructed has one.

We now show the computational hardness of the general case, where all change operations can be used.

Theorem 4. FIX-METHSADD,DEL is NP-hard.

Proof. In the proof of Thm. 3 we let eachmsi with 1 ≤ i ≤ n and each mhj with 1 ≤ j ≤ r in the constructed planning problem contain an empty task network, thus making the DEL-TASK operation redundant (or pointless). Thus, by applying the same reduction, we directly obtain hardness.

So far, we only asked whether any number of changes exists that makes the given task network a solution. We now check whether the problem becomes harder when we are interested in the minimal number of required changes. We formalize this in terms of limiting the size k of the methodchange operation sequence.

Definition 8 (FIX-METHSkX ). Let k ∈ N. For X ⊆ {ADD, DEL} and |X| ≥ 1, the problems FIX-METHSkX are identical to FIX-METHSX, except that we demand that any sequence of model changes is limited in size by k, i.e., |X | ≤ k.

These problems, apparently, do not become harder than the original, unbounded ones.

Corollary 1. FIX-METHSkX with X ⊆ {ADD, DEL} and |X| ≥ 1 is NP-complete.

Proof. Membership: Let L = ∑m∈M |tn(m)|. For each FIX-METHSkX with X ⊆ {ADD, DEL} and |X| ≥ 1, we have already shown in Lem. 1 that each shortest change sequence that turns tn into a solution must be limited by a polynomial. Thereby, although the given k can be exponentially large via encoding it logarithmically, a change sequence does never have to be of length of that worst-case exponential value. More precisely, it should be of length smaller or equal to the minimum of the requested number of k changes and the polynomial bound L + |tn|. Guessing such a sequence X, it takes polynomial time to change P to P ′ [Behnke et al., 2015]. Further, since deciding whether tn is a solution to P ′ takes polynomial time, the total time required to verify whether X is a correct sequence is also a polynomial.

Hardness: For each FIX-METHSkX with X ⊆ {ADD, DEL} and |X| ≥ 1, we reduce from FIX-METHSX. Given an instance of FIX-METHSX, since a shortest change sequence for it cannot have length greater than L+|tn| (with L = ∑m∈M |tn(m)|), we can construct a FIX-METHSkX instance which is identical to the FIX-METHSX instance and has k = L + |tn|. Hardness then follows directly.

3.2 Complexity of Fixing the Methods - Given an Action and Method Sequence

We move on to consider the computational hardness of problems where we are given both an action sequence and a decomposition method sequence that is supposed to generate it. This eliminates one possible source of computational hardness, because there won't be a choice which method to choose per compound task. Though one practical motivation is again failed plan verification. Suppose a flawed HTN planning system that claims that a plan can be produced based on a sequence of used methods, whereas an independent plan verification system [Behnke et al., 2017; Bart´ak et al., 2018; 2020] tells that this is not the case. Checking which methods are flawed can then serve as counter-factual explanation [Ginsberg, 1986; Chakraborti et al., 2017; 2020] to point towards implementation errors (showing the user which methods were not correctly processed by the planning system).

We start with the decision problems which allow an arbitrary number of changes.

Definition 9 (FIX-SEQSX). Let P be a planning problem, m = m1 · · ·mn be a sequence of methods, and tn be a task network. We define the decision problems FIX-SEQSX with X ⊆ {ADD, DEL} and |X| ≥ 1 as: Is there a sequence of method-change operations X such that P →∗X P ′ , tnI →∗m′ tn with m′ = βX(m1) · · · βX(mn), and X consists of only DEL-TASK and ADD-TASK operations according to X?

As before all variants turn out to be equally hard:

Theorem5. FIX-SEQSX withX ⊆ {ADD, DEL} and |X| ≥ 1 is NP-complete.

Proof. Membership: Let L = ∑ni=1 |tn(mi)|. For each FIX-SEQSX with X ⊆ {ADD, DEL} and |X| ≥ 1, one immediate observation is that if there exists some change sequence that turns tn into a solution, there must be one (assuming all operations refer to methods in m) whose length is bounded by L + |tn|, which contains at most L deletions and |tn| additions. Guessing such a sequence, transforming P into P ′ thus takes time O(L + |tn|), and it follows that L′ = ∑ni=1 |tn(βX(mi))| ≤ L + |tn|. Thereby, checking whether m′ decomposes tnI to tn can be done in time O(L′ ) = O(L + |tn|). Taken together, verifying whether X is a correct operation sequence takes P-time.

Hardness: For each FIX-SEQSX with X ⊆ {ADD, DEL} and |X| ≥ 1, we again reduce from the independent set problem. We construct a plan tn and a planning problem P which are identical to those in the hardness proof of the corresponding FIX-METHSX problem. There, we have justified that any method sequence that refines tnI into a solution is a permutation of the one shown in Figure 1. Thus, by explicitly constructing such a method sequence, we complete the reduction. Hardness then follows directly.

We now formalize the problems which we use to formalize finding an optimal (i.e., shortest) sequence of changes.

Definition 10 (FIX-SEQSkX ). Let k ∈ N. For each X ⊆ {ADD, DEL} and |X| ≥ 1, the problem FIX-SEQSkX is identical to FIX-SEQSX except that we demand that any sequence of change operations is limited in size by k, i.e., |X| ≤ k.

Following the idea used in the proof of Cor. 1, we immediately obtain the following result.

Corollary 2. The problems FIX-SEQSkX with X ⊆ {ADD, DEL} and |X| ≥ 1 are NP-complete.

Under certain conditions the problem becomes tractable.

Theorem 6. FIX-SEQSkX and FIX-SEQSX with X ⊆ {ADD, DEL} and |X| ≥ 1 can be decided in polynomial time if tnI contains no primitive tasks, and each method in the method sequence refines a unique task, i.e., for each 1 ≤ i, j ≤ n with i ̸= j, if mi = (ci, tni) and mj = (cj, tnj), then ci ̸= cj.

Proof. We only show the proof for the case where both additions and deletions are allowed, but the same idea can be applied to the other cases. The idea is to compare k with the minimal number of changes required. To find that number, we first apply the method sequence m to tnI , which results in a solution tnP . We can regard tnP and tn as strings where each task is a symbol. Since each method refines a unique task, changes that are imposed to one method will not have an impact on another. In other words, we can directly apply additions and deletions to tnP without considering the method sequence. Thus, the problem of finding the minimal number of changes required to transform P into P ′ such that tnI →∗m′ tn can then be reduced to finding the minimal number of editions required to transform tnP into tn. That is equivalent to the string edit distance problem [Masek and Paterson, 1980], which takes as inputs two strings S and S′ , and outputs an edit sequence E that consists of two types of editions: adding a character and deleting a character, and changes S to S′ in the minimal number of steps. In our case, the two strings are tnP and tn, and the length of E is the minimal number of changes required. Since the string edit distance problem is solvable in polytime, and comparing the minimal number of changes with k takes polynomial time as well, the k-bounded problem can be solved in P. Clearly, the unbounded case can thus also be decided in P.

4 Correcting the Model: Changing Tasks

We now investigate the case where we are given an action sequence that is not executable, and we aim to make it executable by changing its actions' preconditions and effects. So here we ignore the hierarchy completely, either because a non-hierarchical problem was solved in the first place, or because the plan is already proved to be obtainable by the available methods. Note that actions may occur multiple times, so changing one action results in changing all the other identical actions in the same sequence as well. We begin our investigation by introducing the allowed changes. One can easily verify that a reasonable change made to an action p can be categorized as being: 1) Removing a fact from prec(p). 2) Removing a fact from del(p). 3) Adding a fact to add(p).

We formalize these changes as follows.

Definition 11 (FIX-PREC). Let p be an action and f ∈ prec(p) be a fact. The operation FIX-PREC is a function that takes as inputs p and f, and outputs new preconditions of p such that δ(p) = (prec(p)\{f}, add(p), del(p)).

Definition 12 (FIX-ADD). Let p be an action and f ∈ F be a fact. The operation FIX-ADD is a function that takes as inputs p and f , and outputs new effects of p such that δ(p) = (prec(p), add(p) ∪ {f }, del(p)).

Definition 13 (FIX-DEL). Let p be an action and f ∈ del(p) be a fact. The operation FIX-DEL is a function that takes as inputs p and f , and outputs new effects of a such that δ(p) = (prec(p), add(p), del(p)\{f }).

Having defined the allowed operations, we now proceed to examine the complexity of making an action sequence executable. Notice that in most cases, deciding whether any such modifications exist is rather trivial and can be done in polynomial time or even constant time. We will thus focus on checking whether k changes are sufficient.

Definition 14 (FIX-ACTIONSkX ). Let k be an integer, tn be an action sequence. We define the problems FIX-ACTIONSkX with X ⊆ {PREC, ADD, DEL} and |X| ≥ 1 as follows: Is it possible to make tn executable by applying the allowed FIX operation(s) (Defs. 11 to 13) according to X at most k times?

We start with the simplest questions where we are only allowed to use one of the three operations.

Theorem 7. FIX-ACTIONSkPREC is in P.

Proof. Given an action sequence tn = p1 · · · pn, we compare k with the minimal number of changes required to make tn executable, which can be found as follows. For any action pi with 1 ≤ i ≤ n, if there exists some fact f ∈ prec(pi) that cannot be satisfied, we apply FIX-PREC to remove it. One can easily verify that the total number of FIX-PREC applied is minimal. Thus, the answer can be obtained by comparing that number with k, and the total time required is O(|tn|).

Proof. Let tn = p1 · · · pn be the given action sequence. We again compare k with the minimal number of changes required to make tn executable. For each pi with 1 ≤ i ≤ n that contains some fact f ∈ prec(pi) which is not satisfied in the current state, we find all actions pj with j < i, f ∈ del(pj), and f /∈ add(pr) for each j < r < i, and apply FIX-DEL to remove f from del(pj). If no such action can be found, or f is not satisfied after all pjs have been processed, it is not possible to make tn executable. For every such pair of pj and pi, if f remains in del(pj), the precondition of pi cannot be satisfied. Thus, we can conclude that the number of FIX-DEL operations applied is minimal, and comparing it with k takes polynomial time. Thus, FIX-ACTIONSkDEL is in P.

Unlike the previous ones, the problem becomes harder when we are only allowed to use FIX-ADD.

Theorem 9. FIX-ACTIONSkADD is NP-complete.

Proof. Membership: Let tn = p1 · · · pn be the given action sequence, and L = ∑ni=1 |prec(pi)|. We can bound the number of changes that make tn executable by L|tn|, which we get by adding all facts to all actions in tn. Thus, even though the given k can be exponentially large via encoding it logarithmically, there always exists a way to change actions in polynomial many steps if one exists at all. Guessing at most min{k,L|tn|} changes, it takes time O(min{k,L|tn|}) to change the action sequence and O(|tn|) to verify whether the changed sequence is executable.

Hardness: We reduce from the set covering problem, which is known to be NP-complete [Karp, 1972]. Let τ and S = {S1, · · · , Sm} be the integer and the set of sets given by an instance of the set covering problem, respectively. The solution to this problem instance is a subset T ⊆ S such that |T | ≤ τ and ⋃T∈T T = ⋃mi=1 Si. We use the notation U = ⋃mi=1 Si to refer to the universal set. Without loss of generality, suppose U = {e1, · · · , en}. We construct an equivalent instance of FIX-ACTIONSkADD as follows. Let f be a dummy fact, for each ei ∈ U with 1 ≤ i ≤ n, we construct an action pi such that prec(pi) = {f}, add(pi) = ∅, and del(pi) = {f}, and we place these actions sequentially: tn = p1 · · · pn. Afterwards, for each Sj ∈ S with 1 ≤ j ≤ m, we construct an action aj with prec(aj) = ∅, add(aj) = ∅, and del(aj) = ∅. For each ei ∈ U with 1 ≤ i ≤ n, if ei ∈ Sj, we insert aj into a position between ti-1 and ti in tn. Particularly, if i - 1 = 0, aj is inserted before p1. For example, if a set Sj = {e1, e3, e4}, the action aj will be inserted to the positions shown: ajp1p2ajp3ajp4 · · · pn

Lastly, let k = τ. By construction, if we apply FIX-ADD to some action ar (1 ≤ r ≤ m), it will resolve the flaws between ar and the actions that occur after it and have fact f as a precondition. That is equivalent to select Sr into T , and vice versa. Additionally, although applying FIX-ADD to some pi (1 ≤ i ≤ n) is possible, it is useless because each pi is preceded by at least one aj (1 ≤ j ≤ m). Thus, the instance of the set covering problem has a yes answer if and only if the instance we constructed has one.

We now start to examine whether the problems become harder when multiple operations are involved.

Proof. The idea is again to compare k with the minimal number of changes required to make tn executable. Observe that all facts that occur in the action sequence and may result in flaws are independent of each other. We can consequently deal with them one after another. Let tn = p1 · · · pn be the action sequence, F = ⋃ni=1 Fi with Fi = prec(pi) ∪ add(pi) ∪ del(pi) be the set of all facts involved in tn. For each f ∈ F, we do the following:

1. For each action pi with 1 ≤ i ≤ n in tn, if f /∈ Fi, we remove pi from tn. Without loss of generality, we denote the new action sequence after this step as tn′ = p′1 · · · p′r (r ≤ n). If tn′ is executable, we move on to process the next fact in F, otherwise, we continue to the next step.
2. For each action p′i with 1 ≤ i ≤ r in tn′ , if f ∈ prec(p′i ) ∩ del(p′i ), we split p′i into two consecutive actions p′i,⊤ and p′i,⊥ such that prec(p′i,⊤) = prec(p′i ), add(p′i,⊤) = ∅, del(p′i,⊤) = ∅, prec(p′i,⊥) = ∅, add(p′i,⊥) = add(p′i ), and del(p′i,⊥) = del(p′i ). We denote the new action sequence after this step as tn∗ = p∗1 · · · p∗k (r ≤ k).
3. We construct an undirected graph G = (V,E) where V = {p∗1 , · · · , p∗k }, and for any two nodes v, v′ ∈ V ,

(v, v′ ) ∈ E if and only if there exist i, j with i < j such that v = p∗i , v′ = p∗j , f ∈ del(p∗i ), f ∈ prec(p∗j ), for each l with i ≤ l < j, f /∈ add(p∗l ), and there exist an integer q with 1 ≤ q < i and f ∈ add(p∗q ).

An edge (v, v′ ) ∈ E asserts that there exist actions v and v′ in tn∗ such that v deletes the fact f that is required by v′ , which consequently make tn∗ nonexecutable. Thus, for each such edge (v, v′ ) ∈ E, we should remove f from either 1) prec(v′ ), 2) del(v), 3) or both. For finding the minimal number of changes Nf required to fix the flaws associated with f, one can immediately note that this is equivalent to finding the minimum vertex cover of G, which can be solved in polynomial time when G is a bipartite graph [Korte and Vygen, 2008]. Thus, the minimal number of changes required to make tn executable can be obtained by summing up Nf for each f ∈ F. Since |F| is bounded by a polynomial, and calculating Nf for each f also takes polynomial time, the minimal number of changes required can be obtained in polynomial time. Further, comparing this number with k takes polynomial time. The problem is thus in P.

Proof. Membership: Let tn = p1 · · · pn be the given action sequence, and F = ⋃ni=1 prec(pi) ∪ add(pi) ∪ del(pi). At most 2|F||tn| changes are required if tn can be made executable, which is the number obtained by adding all facts to all actions and removing all facts from the preconditions of all actions in tn. After guessing a sequence of changes which is of length smaller or equal to the minimum of k and 2|F||tn| it takes O(min{k, 2|F||tn|}) time to change the action sequence and O(|tn|) to verify executability.

Hardness: We reduce from the FIX-ACTIONSkADD problem. Let k and tn = p1 · · · pn be the integer and the action sequence given by an instance of FIX-ACTIONSkADD , respectively. For simplicity, we only consider the case where tn contains only one fact f, and we have shown in the hardness proof of FIX-ACTIONSkADD that it is NP-complete even in such a case. To construct an equivalent instance of FIX-ACTIONSkPREC,ADD , we keep the k unchanged, and construct the action sequence as follows: For each pi with 1 ≤ i ≤ n and f ∈ prec(pi), we construct a sequence of dummy actions di,1 · · · di,r where r = min{k, 2|F||tn|}, and for each 1 ≤ j ≤ r, prec(di,j) = {f}, del(di,j) = ∅, and add(di,j) = ∅, and place this sequence right before pi in tn. After consulting the argument in the membership proof, one can immediately observe that r is a sufficient upper bound for the maximal number of changes required for both the FIX-ACTIONSkADD instance and the FIX-ACTIONSkPREC,ADD instance. By construction, we make FIX-PREC pointless, because if we apply FIX-PREC to some action pi with f ∈ prec(pi), it should also be applied to the sequence di,1 · · · di,r accordingly, thus the number of changes applied will exceed r. Thereby, the given FIX-ACTIONSkADD instance has a yes answer if and only if the instance we constructed has one.

Proof. Membership: Let tn = p1 · · · pn be the given action sequence, and F = ⋃ni=1 prec(pi) ∪ add(pi) ∪ del(pi).

2|F||tn| is a sufficient upper bound for the number of changes making tn executable, which shows membership.

Hardness: The argument is almost identical to that in the hardness proof of Thm. 11 except that each dummy action sequence di,1 · · · di,r is now placed right after an action pi in tn with f ∈ del(pi), and for each 1 ≤ j ≤ r, prec(di,j) = ∅, del(di,j) = {f}, and add(di,j) = ∅. By construction, we make FIX-DEL pointless. Thus, the given FIX-ACTIONSkADD instance has an yes answer if and only if the instance we constructed has one.

Proof. Membership: Let tn = p1 · · · pn be the given action sequence, and F = ⋃ni=1 prec(pi) ∪ add(pi) ∪ del(pi). The number of changes can be bounded by 3|F||tn|. Membership follows immediately.

Hardness: The argument is similar to that in the proofs of Thm. 11 and 12. We reduce from a FIX-ACTIONSkADD instance where only one fact f is involved. Let k and tn = p1 · · · pn be the integer and the action sequence given by the FIX-ACTIONSkADD instance, respectively. To construct an equivalent instance of FIX-ACTIONSkPREC,ADD,DEL , we keep k unchanged, and construct the action sequence as follows. For each pi with 1 ≤ i ≤ n and f ∈ prec(pi), we place a dummy action sequence di,1 · · · di,r with r = min{k, 3|F||tn|}, and prec(di,j) = {f}, del(di,j) = ∅, and add(di,j) = ∅ for each 1 ≤ j ≤ r right before pi. In the mean time, for each pi with 1 ≤ i ≤ n and f ∈ del(pi), we place a dummy action sequence d′i,1 · · · d′i,r with prec(d′i,j ) = ∅, del(d′i,j ) = {f}, and add(d′i,j ) = ∅ for each 1 ≤ j ≤ r right after pi. By construction, we make both FIX-PREC and FIX-DEL redundant. Thus, the given FIX-ACTIONSkADD instance has a yes answer if and only if the FIX-ACTIONSkPREC,ADD,DEL instance we constructed has one.

We can summarize our findings as follows:

Corollary 3. Let X ⊆ {PREC, ADD, DEL} and |X| ≥ 1. FIX-ACTIONSkX is NP-complete if ADD ∈ X, otherwise it is in P.

5 Conclusion

Motivated by MIP, modeling assistance, and providing counter-factual explanations for failed plan verification, we investigated the computational complexity of checking whether there exists a sequence of model changes (possibly of bounded length) to turn a given action sequence into a solution. These changes are either performed 1) on decomposition methods, or 2) on the actions' preconditions and effects. For the former, we show that deciding whether such a sequence exists is NP-complete no matter what or how many changes are allowed (unless we are given a sequence of methods where each method refines a unique task, which is in P). For the latter, the problem becomes NP-hard whenever it is allowed to change actions' add lists, otherwise the problem will be in P. A natural exploitation of our results is to implement the decision problems in suitable frameworks, e.g., by relying on SAT or ILPs, which are both efficient reasoning frameworks for NP-complete problems.