# variabledeletion_backdoors_to_planning__0dd6d9c4.pdf Variable-Deletion Backdoors to Planning Martin Kronegger,1 Sebastian Ordyniak,2 Andreas Pfandler1,3 1Vienna University of Technology, Vienna, Austria 2Masaryk University, Brno, Czech Republic 3University of Siegen, Siegen, Germany kronegger@dbai.tuwien.ac.at sordyniak@gmail.com pfandler@dbai.tuwien.ac.at Backdoors are a powerful tool to obtain efficient algorithms for hard problems. Recently, two new notions of backdoors to planning were introduced. However, for one of the new notions (i.e., variable-deletion) only hardness results are known so far. In this work we improve the situation by defining a new type of variabledeletion backdoors based on the extended causal graph of a planning instance. For this notion of backdoors several fixed-parameter tractable algorithms are identified. Furthermore, we explore the capabilities of polynomial time preprocessing, i.e., we check whether there exists a polynomial kernel. Our results also show the close connection between planning and verification problems such as Vector Addition System with States (VASS). 1 Introduction Classical planning has been an intensively studied field of AI for decades. Until today, planning remains a challenging task due to its high computational complexity. Even propositional STRIPS planning with unbounded plan length is PSPACEcomplete. This hardness has led to an intensive study of tractable fragments such as in the work by Bylander (1994) and by B ackstr om and Nebel (1995). The framework of parameterized complexity (Downey and Fellows 1999) has been successfully used to find tractable fragments for problems in AI and beyond. For more details see, e.g., the survey of Gottlob and Szeider (2008). The basic idea of a parameterized complexity analysis is to find parameters capturing the computational hardness in a way such that the combinatorial explosion can be confined to these parameters. Thus, the runtime is measured not only in terms of the input size n but also with respect to one or several parameters k of the instance. The class FPT (fixed-parameter tractable) contains all problems that can be solved by an algorithm in time f(k) n O(1), where n denotes the size of the instance and f(k) is a computable function depending on parameter Supported by the Austrian Science Fund (FWF): P25518-N23, the German Research Foundation (DFG): ER 738/2-1, and by the Employment of Newly Graduated Doctors of Science for Scientific Excellence (CZ.1.07/2.3.00/30.0009). Copyright c 2015, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. k only. Such an fpt-algorithm can be considered efficient as long as the value of the parameter is sufficiently small. Using these techniques a variety of tractable fragments in form of fpt-algorithms has been revealed for planning (Downey, Fellows, and Stege 1999; B ackstr om et al. 2012; B ackstr om et al. 2013; Kronegger, Pfandler, and Pichler 2013; Kronegger, Ordyniak, and Pfandler 2014). In the last years the so-called backdoor approach has become a valuable tool to obtain fpt-algorithms, e.g., for SAT (Nishimura, Ragde, and Szeider 2004; Gaspers et al. 2013; Gaspers and Szeider 2013), QBFs (Samer and Szeider 2009), ASP (Fichte and Szeider 2011), Argumentation (Dvor ak, Ordyniak, and Szeider 2012), and also for SAS+ planning (Kronegger, Ordyniak, and Pfandler 2014). Recently, backdoors were used to construct parameterized reductions for problems that are harder than NP (Fichte and Szeider 2013; Pfandler, R ummele, and Szeider 2013). In the backdoor approach, the aim is to find a robust fptalgorithm that also performs well on instances that are not part of the considered tractable base class, but are sufficiently close to this class. This leads to an algorithm which is applicable to a larger set of instances (when compared to algorithms for the tractable base class). Usually, the performance of such an algorithm scales with the distance to the tractable base class. Solving a problem with the backdoor approach consists of two phases. First, we have to find a backdoor of small size (detection phase), which can afterwards, in the second phase, be used as additional information to guide the decision algorithm for the original problem (evaluation phase). A challenging task is to find suitable notions of backdoors and algorithms building upon these notions such that both phases can be solved efficiently, i.e., by an fpt-algorithm. For planning, it turned out that backdoors cannot be defined in such a direct way as it is possible for SAT and related problems. This is because a suitable notion is needed to describe the underlying structure of the planning instance. In the work of Kronegger, Ordyniak, and Pfandler (2014) the first two backdoors for planning were introduced. These backdoors measure the number of variables/actions that have to be deleted such that the underlying causal graph decomposes into weakly connected components of small size. Such instances of constant component size are known to be efficiently solvable (Chen and Gim enez 2010). For the notion of action-deletion backdoors several fpt-algorithms were ob- Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence tained. Among these results is also the first fpt-algorithm for planning with unbounded plan length that limits neither the number of variables or actions in the instance. Unfortunately, for variable-deletion backdoors only parameterized intractability results were shown (W[1]-hardness, to be more precise). Finding fpt-algorithms also for backdoors based on variable-deletion would, however, be very desirable since there are instances for which the notion of deleting variables is stronger than deleting actions. Main contributions We introduce a new type of a variable-deletion backdoors based on the underlying extended causal graph. This new type of backdoor leads to three fpt-algorithms for planning, i.e., fpt-algorithms both for the detection and evaluation problem. We complement these results by showing parameterized intractability for several evaluation problems. In our results we show the close connection between planning and verification problems, as we build upon Vector Addition Systems with States (VASS), a formalism strongly related to Petri-nets, to obtain fpt-results for planning. We present efficient preprocessing algorithms, polynomial kernels to be more precise, for the detection problems and rule out their existence for the evaluation problems. 2 Preliminaries We assume the reader to be familiar with the basics of complexity theory and planning. Parameterized Complexity. In parameterized algorithmics (Downey and Fellows 1999; Flum and Grohe 2006; Niedermeier 2006; Downey and Fellows 2013) the runtime of an algorithm is studied with respect to a parameter k N and input size n. The most favorable class is FPT (fixedparameter tractable) which contains all problems that can be decided by an algorithm running in time f(k) n O(1), where f is a computable function. We call such an algorithm fixedparameter tractable (fpt). Formally, a parameterized problem is a subset of Σ N, where Σ is the input alphabet. Let L1 Σ 1 N and L2 Σ 2 N be parameterized problems. A parameterized reduction (or fpt-reduction) from L1 to L2 is a mapping P : Σ 1 N Σ 2 N such that (i) (x, k) L1 iff P(x, k) L2, (ii) the mapping can be computed by an fptalgorithm w.r.t. parameter k, and (iii) there is a computable function g such that k g(k), where (x , k ) = P(x, k). The class W[1] captures parameterized intractability and contains all problems that are fpt-reducible to INDEPENDENT SET when parameterized by the size of the solution. The class para NP (Flum and Grohe 2003) is defined as the class of problems that are solvable by a non-deterministic Turing machine in fpt-time. In our para NP-hardness proofs, we will make use of the following characterization of para NPhardness given by Flum and Grohe (2006), Theorem 2.14: any parameterized problem that remains NP-hard when the parameter is set to some constant is para NP-hard. The following relations between the parameterized complexity classes hold: FPT W[1] XP, where the class XP contains all problems solvable in time O(nf(k)) for a computable function f. Showing W[1]-hardness for a problem rules out the existence of an fpt-algorithm under the usual complexity theoretic assumption FPT = W[1]. Closely related to the search for fpt-algorithms is the search for efficient preprocessing techniques. A kernelization algorithm transforms in polynomial time a problem instance (x, k) of a parameterized problem L into an instance (x , k ) of L such that (i) (x, k) L iff (x , k ) L, (ii) k f(k), and (iii) the size of x can be bounded above by g(k), for functions f and g depending only on k. It is easy to show that a parameterized problem is in FPT if and only if there is kernelization algorithm. A polynomial kernel is a kernel whose size can be bounded by a polynomial in the parameter. Planning. Let V = {v1, . . . , vn} be a finite set of variables over a finite domain D and let D+ = D {u}, where u is a special undefined value not present in D. Then Dn is the set of total states and (D+)n is the set of partial states over V and D. Clearly, Dn (D+)n. The value of a variable v in a state s (D+)n is denoted by s[v] and the projection of a state s to a set of variables V V is denoted by s[V ]. A SAS+ instance is a tuple P = V, D, A, I, G where V is a set of variables, D is a domain, A is a set of actions, I Dn is the initial state and G (D+)n is the (partial) goal state. Each action a A has a precondition pre(a) (D+)n and an effect eff(a) (D+)n. We will frequently use the convention that a variable has value u in a precondition/effect unless a value is explicitly specified. Let a A and s Dn. Then a is valid in s if for all v V , either pre(a)[v] = s[v] or pre(a)[v] = u. Furthermore, the result of a in s is a state t Dn defined such that for all v V , t[v] = eff(a)[v] if eff(a)[v] = u and t[v] = s[v] otherwise. We denote by V (P), A(P) the set V and A, respectively. Let s0, sℓ Dn and let ω = a1, . . . , aℓ be a sequence of actions (of length ℓ). Then ω is a plan from s0 to sℓif either (i) ω = and ℓ= 0, or (ii) there are states s1, . . . , sℓ 1 Dn such that for all 1 i ℓ, ai is valid in si 1 and si is the result of ai in si 1. A state s Dn is a goal state if for all v V , either G[v] = s[v] or G[v] = u. An action sequence ω is a plan for P if ω is a plan from I to some goal state. We will study backdoors for the following problems: Given a SAS+ instance P and a positive integer k the problem BOUNDED SAS+ PLANNING is parameterized by k and asks whether P has a plan of length at most k. The problem SAS+ PLANNING is defined analogously without a bound on the plan length k. Let P = V, D, A, I, G be a SAS+ instance, V V . Then we denote by P[V ] the SAS+ instance V , Dr, Ar, Ir, Gr , where Dr is the restriction of D to the domains of the variables in V , Ar are the actions in A whose preconditions and effects are restricted to the variables in V , and Ir and Gr are the restriction of I and G to the variables in V . We denote by P(V ) the SAS+ instance obtained from P[V ] after deleting all actions that correspond to actions in P with at least one precondition or effect on a variable in V \ V . We write P \ V for the instance P[V \ V ]. Vector Addition System with States. Let d N, u Zd, and i {1, . . . , d}. We denote by u[i] the value of the i-th entry (component) of u and by ||u|| the maximum absolute value of any entry of u, i.e., ||u|| = max1 j d |u[i]|. We also denote by u + v, u v, and u v the componentwise summation, subtraction, and comparison of u and v, respectively. A d-VASS V is a pair Q, , where Q is a non-empty finite set of control points and Q Zd Q is a finite set of transitions. A V-state s is a pair q, v , where q Q and v Nd. We denote by ||s|| the value ||v||. A run in V is a sequence q1, v1 , . . . , qn, vn of V-states such that for every i with 1 i < n, contains a transition qi, v, qi+1 with vi+1 = vi + v. We say that a V-state s G = q G, v G is coverable by a V-state s I = q I, v I in V if there is a covering of s G from s I in V, i.e., a run R = q0, v0 , . . . , qn, vn in V such that q0 = q I, v0 = v I, qn = q G, and vn v G. We denote by || || the maximum ||v|| over all v Zd such that q, v, q for some q, q Q. Theorem 1 (Bozzelli and Ganty (2011), Theorem 1). Let V = Q, be a d-VASS and s I and s G be two V-states. If s G is coverable from s I in V, then there is a covering of s G from s I in V of length at most (|Q| (|| || + ||s G|| + 2))(3d)!+1. 3 A New Type of Backdoors The backdoor approach is a powerful tool to obtain fptalgorithms for hard problems. This approach comprises two phases: In the first phase, the detection phase, one needs to find a certain set, the backdoor, whose size is used to measure the distance of a given instance to a tractable base class. After that, in the second phase, which is called the evaluation phase, the additional information stored in the backdoor set is used to solve the problem efficiently. The runtime of the evaluation phase usually depends exponentially on the size of the given backdoor. Still, we can consider the algorithm to be efficient as long as the backdoor is reasonably small. Therefore, the size of the backdoor set is usually considered as a parameter. In particular, if detection and evaluation are both fpt, this yields an fpt-algorithm for the whole problem. Recently, for SAS+ PLANNING the first two notions of backdoors were introduced (Kronegger, Ordyniak, and Pfandler 2014), where the so-called causal graph (Knoblock 1994; Brafman and Domshlak 2006; Chen and Gim enez 2010; B ackstr om and Jonsson 2013) is used to capture the structure of the instance. The considered base class contains all instances for which the size of the largest weakly-connected component of the underlying causal graph is bounded by a constant c. For this base class, SAS+ PLANNING is solvable in polynomial time (Chen and Gim enez 2010). Kronegger, Ordyniak, and Pfandler (2014) considered two types of backdoors: action-deletion and variable-deletion backdoors. While for both types detection is fpt, the complexity of evaluation varies among these two types. For the former type several fpt-algorithms were found. In contrast, for the latter type only W[1]-hardness results were shown that rule out the existence of an fpt-algorithm under the usual assumptions. Having fpt-algorithms for variable-deletion backdoors would, however, be beneficial as variable-deletion can be stronger than action-deletion. This is because, deleting a single, central variable can have the same effect as deleting a large set of actions, which can result in a notably smaller backdoor. The goal of this work is to find an improved type of variable-deletion backdoors, for which detection remains fpt and for which evaluation becomes fpt. To this end, we introduce the extended causal graph GE(P) of a SAS+ instance P = V, D, A, I, G . GE(P) is a directed graph with vertices V that contains an arc (v, v ), for distinct v, v V , if there is an action a A with (i) pre(a)[v] = u and pre(a)[v ] = u, or (ii) pre(a)[v] = u and eff(a)[v ] = u, or (iii) eff(a)[v] = u and eff(a)[v ] = u. With cc-size(G) we denote the largest weakly connected component of a digraph G. We remark that the notion of the causal graph of P, denoted by GC(P), is similar to the definition above, with the difference that it does not add an edge between variables appearing in the precondition of an action. Therefore, the extended causal graph is more restrictive and hence the tractable fragment mentioned above immediately carries over to the extended causal graph. Furthermore, as studied by Kronegger, Ordyniak, and Pfandler (2014), this base class can also be used for BOUNDED SAS+ PLANNING. In this work, we consider variable-deletion backdoors on the extended causal graph together with four different settings of planning. We study the SAS+ PLANNING and the BOUNDED SAS+ PLANNING problem in case of a bounded or unbounded domain of the variables, as well as, novel backdoor specific restrictions, such as, instances that do not contain mixed actions (i.e., actions having effects both on the backdoor set and at least one component). In our analysis, we present fpt-algorithms, and hardness results for the classes W[1] and para NP. If a problem is known to be fpt, the next challenge is to find (or rule out the existence of) a method for efficient preprocessing, i.e., a polynomial kernel. Of course this is the most desirable result, as this yields a versatile polynomial time algorithm that produces a small, equivalent instance, which can in turn be processed by any algorithm for the problem. The results obtained in this work are juxtaposed with known results from the literature (Kronegger, Ordyniak, and Pfandler 2014) in Table 1. Due to space limitations several proof details had to be omitted. The proofs for results marked with are provided in the supplementary material (Kronegger, Ordyniak, and Pfandler 2015). 3.1 Detection As a first step, we show that detection of our new type of backdoors remains fpt as it was for the version defined over the causal graph. Actually, we prove a stronger result, namely, that there exists a polynomial kernel for the detection problem. This is good news as this lets hope for very efficient detection algorithms. We consider the following problem: c-EXTENDED CAUSAL DETECTION[VARIABLES] Instance: A SAS+ instance P and a positive integer k. Parameter: k Question: Is there a set S of at most k variables of P such that cc-size(GE(P \ S)) c? Throughout the paper, we abbreviate c-EXTENDED CAUSAL DETECTION[VARIABLES] with c-DET. Detection Evaluation Setting Domain (un)bounded plan len. bounded plan len. unbounded plan length variable-del. in GC (un)bounded in FPT W[1]-hard W[1]-hard action-del. in GC bounded in FPT in FPT in FPT unbounded in FPT in FPT para NP-hard variable-deletion in GE in FPT and in FPT (Thm. 8) sog: in FPT (Cor. 13) and npk (Thm. 16) pk (Thm. 3) and nma: in FPT (Thm. 15) and npk (Thm. 16) npk (Thm. 16) in general: in XP (Thm. 10) and npk (Thm. 16) unbounded in FPT and W[1]-hard and para NP-hard (Thm. 4) pk (Thm. 3) in XP (Thm. 5) Table 1: Complexity map. Results marked with are shown in (Kronegger, Ordyniak, and Pfandler 2014). We use the abbreviation (n)pk for (no) polynomial kernel , sog for additionally parameterized by the size of the goal and nma for no mixed actions . Before we start with our parameterized analysis we need to show that the detection problem is NP-hard. Inspecting the NP-hardness proof for variable-deletion backdoors based on the causal graph (Kronegger, Ordyniak, and Pfandler 2014, Theorem 2), we observe that the construction does not use preconditions in the actions. Thus, the result carries over to backdoors based on the extended causal graph. Corollary 2. c-DET is NP-hard even for planning instances with bounded domain. In the next result we show that the detection problem is not only fpt when parameterized by the size of the backdoor but also admits a polynomial kernel. Theorem 3. c-DET admits a polynomial kernel of size at most O((k + k(k + c)c)2) and hence is fpt. Proof. Let P, k be an instance of c-DET over variables V = V (P). We can construct GE(P) in polynomial time. W.l.o.g. we can assume that GE(P) is weakly connected, otherwise a deletion set for GE(P) can be obtained as the union of deletion sets for every component of GE(P). Furthermore, we can assume that the degree of every vertex of GE(P) is at most k + c. Assume that this is not the case, i.e., there is a vertex v of GE(P) with more than k + c neighbors. Then v has to be contained in the deletion set, because otherwise the deletion set would have to contain more than k of its neighbors. Consequently, P \ {v}, k 1 is equivalent to P, k . We now show that if P, k is a YES-instance, then P can have at most k + k(k + c)c variables. So assume that P, k is a YES-instance and let S be a deletion set of size at most k witnessing this. Because every vertex in S has at most k + c neighbors and GE(P) is connected, we obtain that GE(P)\S has at most k(k +c) components and hence P, k has at most k + k(k + c)c variables. Thus, we can transform P, k in polynomial time into an equivalent instance P , k that contains at most k = k + k(k + c)c variables. The following claim shows that also the number of actions can be bounded and thus we obtain a polynomial kernel. Claim 1 (*). There is an equivalent instance P , k with at most k variables and at most (k )2 actions. 3.2 Evaluation After we have shown that detection is fpt, we turn to the evaluation problem. Finding an fpt-result for these problems would hence give an fpt-result for the whole backdoor approach. This is in particular interesting as no fpt-results for variable-deletion backdoors are known so far (cf. Table 1). The evaluation problems are defined as follows: c-BOUNDED EXTENDED CAUSAL EVALUATION[VARIABLES] Instance: A SAS+ instance P, a positive integer k, and a set S of variables of P such that cc-size(GE(P \ S)) c. Parameter: |S| + k Question: Does P have a plan of length at most k? The problem c-EXTENDED CAUSAL EVALUATION[VARIABLES] is defined analogously without a bound on the plan length k. We abbreviate c-EXTENDED CAUSAL EVALUATION[VARIABLES], resp. c-BOUNDED EXTENDED CAUSAL EVALUATION[VARIABLES], with c-EVAL, resp. c-BOUNDED EVAL. If neither the plan length nor the domain of the variables is bounded, evaluation is para NP-hard. However, if only the length is bounded we obtain W[1]-hardness and membership in XP. This yields a polynomial algorithm if the parameter values are fixed to a constant. Theorem 4 (*). 2-EVAL is para NP-hard. Theorem 5 (*). c-BOUNDED EVAL is W[1]-hard (even if additionally parameterized by the number of variables) and in XP. Proof (sketch). Hardness can be shown by a reduction from PARTITIONED CLIQUE parameterized by the number of partitions, which is known to be W[1]-complete (Pietrzak 2003). The reduction is similar to the one given in (Kronegger, Ordyniak, and Pfandler 2014, Theorem 4) and is therefore omitted. For XP-membership notice that all possible plans of length k can be trivially bounded by O(nk), where n is the number of actions in the SAS+ instance. The above Theorem shows that c-BOUNDED EVAL is contained in XP. In the following we will show that if we consider only c-BOUNDED EVAL instances of bounded domain then this can be improved to an fpt-result. Before showing this, we need additional definitions. We say that two instances P1 = V1, D1, A1, I1, G1 and P2 = V2, D2, A2, I2, G2 of SAS+ PLANNING are isomorphic if there is a bijection ϕ from V1 D1 A1 to V2 D2 A2 such that (i) ϕ(v) V2 for every v V1, ϕ(d) D2 for every d D1, and ϕ(a) A2 for every a A1, (ii) for every a A1 and v V1 it holds that ϕ(pre(a)[v]) = pre(ϕ(a))[ϕ(v)] and ϕ(eff(a)[v]) = eff(ϕ(a))[ϕ(v)], and (iii) for every v V1 it holds that ϕ(I1[v]) = I2[ϕ(v)] and ϕ(G1[v]) = G2[ϕ(v)]. In the following let P = V, D, A, I, G be a SAS+ PLANNING instance and S be a c-Extended Causal Backdoor of P. We denote by C(P, S) the set of components of GE(P \ S) . We say that two components C1 and C2 in C(P, S) are equivalent, denoted by C1 C2, if there is an isomorphism ϕ between P(V (C1) S) and P(V (C2) S) such that ϕ(s) = s for every s S. Let p N. We denote by E(P, S, p) the SAS+ PLANNING instance obtained from P by removing any component in excess of p from C(P, S) for every equivalence class with respect to . Furthermore, we write E(P, S) to denote E(P, S, 1). By removing a component C C(P, S) from P we mean that all variables in V (P) together with all actions that have at least one precondition or effect in C are removed from P. Observe that E(P, S, p) is unique up to isomorphism. We denote by ET(P, S) an arbitrary but fixed ordering of the components of C(E(P, S), S) and by EV(P, S) the vector v N|ET(P,S)| such that for every i with 1 i |ET(P, S)|, we have that v[i] is equal to the total number of components of C(P, S) that are equivalent to the component ET(P, S)[i]. Observe that a planning instance P with c-Extended Causal Backdoor S is equivalent to P if E(P, S) is isomorphic to E(P , S ) and EV(P, S) = EV(P , S ). The following lemma gives an upper bound on the number of equivalence classes of the components. Lemma 6 (*). |ET(P, S)| is at most c ((|D| + 1)2(c+|S|)) 2(|D|+1)2(c+|S|). Our fpt-algorithms use the following general approach: We first compute a reduced instance P of the form E(P, S, l) for some l N that is equivalent to P in fpt time. We then use the following lemma to show that P and hence also P can be solved in fpt-time. Observe that instead of solving P using brute-force (as it is done in the following lemma) one can use state-of-the-art planners or even heuristic approaches to solve P . This provides a high degree of freedom for the design of efficient algorithms that use our backdoor set approach. Lemma 7 (*). Given a SAS+ PLANNING instance P, a c-Extended Causal Backdoor S of P, and l N, we can solve c-EVAL and c-BOUNDED EVAL of E(P, S, l) in time O(|D|V (E(P,S,l)) + |V | |ET(P, S)|). With the help of the above two lemmas it is now relatively straightforward to prove the following theorem. Theorem 8 (*). c-BOUNDED EVAL is fpt for instances with bounded domain. Given that c-BOUNDED EVAL is fpt for instances with bounded domain, it becomes natural to ask whether the same holds for c-EVAL instances of bounded domain. Even though, we are not able to answer this question in its full generality, we obtain fpt-algorithms for two natural restrictions of this problem, i.e., (i) if we consider the size of the goal as an additional parameter, and (ii) for instances, which do not contain any mixed actions, i.e., actions that have effects both on S and on some component in C(P, S). Before showing these two results we need some preparation. In particular, we first show that c-EVAL is in XP for instances of bounded domain. We denote by ST(P) an arbitrary but fixed ordering of all possible (total) states of P. Let s be a (total) state of P and assume that ET(P, S) = C1, . . . , C|ET(P,S)| . Below we define the vector ESV(P, S, s), which will be important for the following constructions. The vector contains one entry for every type of a component and for every possible state of a component, whose value is equal to the number of components of the corresponding type being in that state (in the global state s). We denote by ESV-D(P, S) the number Pi |ET(P,S)| i=1 |ST(P(V (Ci)))|. Let i with 1 i |ET(P, S)| and z ST(P(V (Ci))). We denote by ESV-I(P, S, Ci, z) the number Pj