# backdoors_to_planning__b6f77dd1.pdf Backdoors to Planning Martin Kronegger Vienna University of Technology, Vienna, Austria kronegger@dbai.tuwien.ac.at Sebastian Ordyniak Masaryk University, Brno, Czech Republic sordyniak@gmail.com Andreas Pfandler Vienna University of Technology, Vienna, Austria pfandler@dbai.tuwien.ac.at Backdoors measure the distance to tractable fragments and have become an important tool to find fixed-parameter tractable (fpt) algorithms. Despite their success, backdoors have not been used for planning, a central problem in AI that has a high computational complexity. In this work, we introduce two notions of backdoors building upon the causal graph. We analyze the complexity of finding a small backdoor (detection) and using the backdoor to solve the problem (evaluation) in the light of planning with (un)bounded plan length/domain of the variables. For each setting we present either an fpt-result or rule out the existence thereof by showing parameterized intractability. In three cases we achieve the most desirable outcome: detection and evaluation are fpt. 1 Introduction Planning is one of the central formalisms in AI. Unfortunately, the expressive power of planning comes at the cost of high computational complexity. In general, already propositional STRIPS planning is PSPACE-complete for unbounded plan length. In order to cope with this high complexity, several fragments of planning have been considered where planning becomes tractable. For propositional STRIPS a comprehensive complexity analysis was performed by Bylander (1994). Later, B ackstr om and Nebel (1995) presented a similar analysis for the SAS+ formalism, where the state variables range over multi-valued domains. A more fine-grained understanding of the hardness of a problem can be obtained from the viewpoint of parameterized complexity theory (Downey and Fellows 1999). Here one is interested in identifying one or multiple features of the instance the so-called parameters which capture the combinatorial explosion. More formally, the time needed to solve the problem is not only measured in terms of the input size n, but also depends on the parameter (or combination of parameters) k. The class of efficiently solvable problems is FPT (fixed-parameter tractable), i.e., the problem can be solved by an fpt-algorithm in time f(k) n O(1), where n denotes the size of the problem instance and f(k) is a computable function depending on parameter k only (and not on n). The exponential time complexity is thus confined to the Copyright c 2014, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. parameter, i.e., the function f(k). Therefore, an fpt-algorithm can be considered efficient as long as the parameter values of an instance are sufficiently low. Furthermore notice that an fpt-result immediately yields tractability of the problem if parameter k is bounded by a constant. Techniques from parameterized complexity have been successfully used to tackle hard problems, e.g., in Knowledge Representation & Reasoning (Gottlob and Szeider 2008). For planning a parameterized complexity analysis was initiated by Downey, Fellows, and Stege (1999). In recent works by B ackstr om et al. (2012) and Kronegger, Pfandler, and Pichler (2013), several fpt-results have been obtained for SAS+ and propositional STRIPS. Despite this success the desire for additional fpt-algorithms remains. A powerful tool to obtain fpt-algorithms are so-called backdoors (for a survey see Gaspers and Szeider (2012b)). Backdoors were originally introduced by Williams, Gomes, and Selman (2003) to explain the behavior of SAT and CSP solvers on practical instances. The basic idea is that the size of a backdoor set measures the distance to a tractable fragment of the problem. In the past, the backdoor approach has been used to obtain fpt-results for SAT (Nishimura, Ragde, and Szeider 2004; Gaspers and Szeider 2012a), QBFs (Samer and Szeider 2009), ASP (Fichte and Szeider 2011a), and Argumentation (Dvor ak, Ordyniak, and Szeider 2012). Furthermore, several experiments regarding the size of the backdoors of SAT and ASP instances were performed (Kilby et al. 2005; Gregory, Fox, and Long 2008; Fichte and Szeider 2011b). Interestingly, some of the instances were obtained through SATand ASP-encodings of planning instances. Recently, backdoors have also been used to construct parameterized reductions to SAT for problems harder than NP such as ASP (Fichte and Szeider 2013) and Abduction (Pfandler, R ummele, and Szeider 2013). However, backdoors for planning have not been considered yet. In contrast to other problems such as SAT, where backdoors can be defined in a direct way, the situation is different for planning. Here, an additional layer is needed. The challenge is to find a suitable notion capturing the underlying structure of the planning instance, which in the next step can be used to define the desired notion of backdoors. Main contributions In this work, we introduce two natural notions of backdoors for planning, which are based on the underlying causal graph Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence of the planning instance. For both of the new notions of backdoors, we perform a comprehensive parameterized complexity analysis (see Table 1 for an overview). In more detail, we analyze the complexity of the two phases of the backdoor approach: (i) finding a small backdoor (detection phase), and (ii) using the additional information given in the backdoor to solve the planning instance (evaluation phase). In the evaluation phase, we additionally consider a bound on the plan length and/or on the domain of the variables as additional restrictions. For each of the above settings we present either an fpt-result, or show parameterized intractability. This gives us a complete picture of the parameterized complexity of the backdoor approach w.r.t. the considered notions of backdoors. Among our fpt-results is the first fpt-algorithm for planning with unbounded plan length that does neither limit the number of variables nor actions in the planning instance. 2 Preliminaries We assume the reader to be familiar with the basics of complexity theory and planning. For an introduction to complexity theory we refer, e.g., to the book of Papadimitriou (1994). For n N, we use [n] to denote the set {1, . . . , n}. Parameterized Complexity. Parameterized algorithmics (cf. Downey and Fellows (1999), Flum and Grohe (2006), Niedermeier (2006)) is a promising approach to obtain efficient algorithms for fragments of intractable problems. In a parameterized complexity analysis the runtime of an algorithm is studied with respect to a parameter k N and input size n. The basic idea is to find a parameter that describes the structure of the instance such that the combinatorial explosion can be confined to this parameter. The most favorable class is FPT (fixed-parameter 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 fixed-parameter tractable (fpt). Formally, a parameterized problem is a subset of Σ N, where Σ is the input alphabet. Problem reductions now also have to take the parameter into account. Let L1 and L2 be parameterized problems, with L1 Σ 1 N and L2 Σ 2 N. 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 fpt-algorithm w.r.t. parameter k; (iii) there is a computable function g such that k g(k), where (x , k ) = P(x, k). Next, we will define the classes capturing fixed-parameter intractability needed in this work. For further details we have to refer to the literature on parameterized complexity theory. The class W[1] contains all problems that are fpt-reducible to INDEPENDENT SET when parameterized by the size of the solution, i.e., the independent set (Downey and Fellows 1999; Flum and Grohe 2006). 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 NP-hardness 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] para NP. Showing W[1]-hardness for a problem rules out the existence of a fixed-parameter algorithm under the usual complexity theoretic assumption FPT = W[1]. Planning. Let V = {v1, . . . , vn} be a finite set of variables over a finite domain D. Implicitly define 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]. 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 let 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. 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: SAS+ PLANNING Instance: A SAS+ instance P. Question: Does P have a plan? BOUNDED SAS+ PLANNING Instance: A SAS+ instance P and a positive integer k. Parameter: k. Question: Does P have a plan of length at most k? Notice that the propositional version of the well-known STRIPS planning language is a special case of SAS+. Let P = V, D, A, I, G be an SAS+ instance, V V , and A A. 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 write P \ V for the instance P[V \ V ]. Similarly, we denote by P[A ] the SAS+ instance V, D, A , I, G and by P \ A the SAS+ instance P[A \ A ]. 3 Using the Causal Graph for Backdoors In this work we will introduce two new types of backdoors. Before we start with the presentation of the details, we give a high-level introduction to the backdoor approach. The backdoor approach can be separated into two phases. In the first phase (detection) one searches for a set, i.e., the backdoor, whose size measures the distance of the given instance to a tractable base class. In the second phase (evaluation) one makes use of the information of the backdoor to Detection Evaluation Setting (un)bounded plan length bounded plan length unbounded plan length variable-deletion (un)bounded domain in FPT (Thm. 3) W[1]-hard (Thm. 4) W[1]-hard (Thm. 4) action-deletion bounded domain in FPT (Thm. 7) in FPT (Thm. 10) in FPT (Thm. 9) unbounded domain in FPT (Thm. 7) in FPT (Thm. 10) para NP-hard (Thm. 8) Table 1: Complexity map of backdoors to planning. solve the problem. Usually, the size of the backdoor is considered as parameter in the detection and evaluation problem. Hence, if both problems are fpt, they can be solved efficiently as long as the backdoor is of moderate size. For instance, for the SAT problem, one searches for a small set of variables of size k such that the given formula can be reduced to 2k easy formulas that belong to the desired tractable base class (e.g., Horn or Krom). For planning, however, it is not immediately clear how to break a hard instance into multiple easy instances by using a backdoor set. The basic idea of this work is to use some underlying structure of the planning instance, namely the causal graph, instead of the planning instance itself to define the backdoor. Therefore, we first need to recapitulate the concept of the causal graph (Knoblock 1994; Brafman and Domshlak 2006; Chen and Gim enez 2010; B ackstr om and Jonsson 2013). The causal graph GCAUSAL(P) of a SAS+ instance P = V, D, A, I, G is the directed graph with vertices V that contains an arc (v, v ), for distinct v, v V , if either there is an action a A with pre(a)[v] = u and eff(a)[v ] = u or there is an action a A with eff(a)[v] = u and eff(a)[v ] = u. If C is a set of vertices of a subgraph of GCAUSAL(P) we denote by P[C] the SAS+ instance P[V ] where V V are all variables that correspond to vertices of C. We denote by cc-size(H) the cardinality of the largest weakly connected component of the directed graph H. If it is clear from the context, we will write components instead of weakly connected components of the causal graph GCAUSAL(P) . In order to be able to define the backdoors, we need to find a suitable, tractable base class. From the literature it is known that SAS+ PLANNING is solvable in polynomial time if the maximum component size of the underlying graph can be bounded by a constant c, i.e., cc-size(GCAUSAL(P)) c. Theorem (Chen and Gim enez (2010)). Let c be a constant. Then SAS+ PLANNING can be solved in polynomial time for instances where cc-size(GCAUSAL(P)) c. For the setting with bounded plan length it is easy to obtain a similar result. It suffices to construct the state transition graph (of size O(|D|c)) for each component and compute the shortest path to the partial goal. An arbitrary combination of the shortest plans for each component gives a solution. Proposition 1. Let c be a constant. Then c-BOUNDED SAS+ PLANNING can be solved in polynomial time for instances where cc-size(GCAUSAL(P)) c. The backdoors introduced in this work measure the distance of the planning instance P to a tractable planning instance P that has bounded component size. We will consider two natural ways to decompose the components of the causal graph. The backdoor set S either contains the variables or the actions that are removed from the instance to reduce the size of the weakly connected components. Notice that from the viewpoint of classical complexity theory the evaluation problem remains as hard as the original planning problem, because one is free to add all variables or all actions to the backdoor set. In this work, each backdoor type is considered in the light of four different settings of planning. We consider the SAS+ PLANNING and the BOUNDED SAS+ PLANNING problem in case of an bounded or unbounded domain of the variables. For each case we will present either an fpt-algorithm or hardness for the classes W[1] or para NP. The results of this work are summarized in Table 1. Due to space limitations several proof details had to be omitted. 3.1 Variable-Deletion-Backdoors In this section we consider planning instances that have a small number of variables whose removal results in a causal graph with components of bounded size. We show that even though the detection of these planning instances is fixedparameter tractable (Theorem 3) this does not hold for the evaluation problem even for planning instances with bounded domain (Theorem 4). We start by defining the detection problem for the setting where variables are allowed to be removed (variable-deletionbackdoors). c-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(GCAUSAL(P \ S)) c? Intuitively, a variable-deletion-backdoor captures the distance (in terms of variables that need to be removed) to an instance where all variables can be partitioned into small sets that are relevant for independent subtasks. Observe that the property of having small components in the causal graph is very fragile: Even if the variables form small independent components, adding a single variable that occurs in all actions in the precondition creates a single, big component in the causal graph. Variable-deletion-backdoors can be seen as a more robust notion. In the example above a backdoor of size one (containing the newly introduced variable) is sufficient. Next, we build upon this backdoor and extend the problems SAS+ PLANNING and BOUNDED SAS+ PLANNING to make use of a previously computed backdoor S. c-CAUSAL EVALUATION[VARIABLES] Instance: A SAS+ instance P and a set S of variables of P such that cc-size(GCAUSAL(P \ S)) c. Parameter: |S|. Question: Does P have a plan? c-BOUNDED CAUSAL EVALUATION[VARIABLES] Instance: A SAS+ instance P and a set S of variables of P such that cc-size(GCAUSAL(P \ S)) c. Parameter: |S| + k. Question: Does P have a plan of length at most k? We start the analysis by a discussion of the complexity of the detection problem. To justify a parameterized complexity analysis, we first show NP-hardness. Theorem 2. 1-CAUSAL DETECTION[VARIABLES] is NPhard even for planning instances with bounded domain. Proof. Let G = (V, E), k , with |V | = n, be an instance of the well-known VERTEX COVER problem. We construct an instance P, k of 1-CAUSAL DETECTION[VARIABLES] in the following way: Let D = {0, 1}, I = 0n and G = 1n. The planning instance P contains one variable for each vertex in V . Furthermore, let A be the union of all actions of the form ax,y with eff(ax,y)[x] = eff(ax,y)[y] = 1 where {x, y} E. Then, P := V, D, A, I, G . From the construction it is easy to see that every set S with |S| = k that is a vertex cover of G is a set of k vertices such that cc-size(GCAUSAL(P \ S)) = 1 and vice versa. In the next theorem we will show that the detection problem is fixed-parameter tractable when parameterized by the size of the backdoor set S. To establish this result we will make use of Courcelle s theorem and present an encoding in Monadic Second-Order logic (MSO). For the proof of the theorem, we need further definitions. Let G = (VG, EG) be a graph. A tree-decomposition of G is a pair T, χ where T = (VT , ET ) is a tree and χ is a labeling function that maps every vertex x VT to a set of vertices χ(x) VG with the following properties: (i) for every vertex y VG there is a node x VT such that y χ(x), (ii) for every edge {y1, y2} EG there is a node x VT such that y1, y2 χ(x), and (iii) for all y1, y2, y3 VT , if y2 lies on the unique path from y1 to y3 in T, then χ(y1) χ(y3) χ(y2). The width of a treedecomposition T, χ is defined as maxx VT {|χ(x)|} 1. The treewidth tw(G) of a graph G is the minimum width over all its tree-decompositions. Bodlaender (1996) showed that for any fixed c, one can check in linear time (and hence in fpt-time when parameterized by c) whether tw(G) c. Monadic Second-Order (MSO) logic is first-order logic extended by set variables. Courcelle (1990) showed that checking whether a graph G satisfies an MSO formula ϕ is fixedparameter tractable when parameterized by the treewidth tw(G) and the length of ϕ. Theorem 3. c-CAUSAL DETECTION[VARIABLES] is fpt. Proof. Let P, k be an instance of c-CAUSAL DETECTION[VARIABLES] over variables V . We can construct GCAUSAL(P) in polynomial time. For every YES-instance the following holds: GCAUSAL(P) can be partitioned into S and P1, . . . , Pm such that |S| k, |Pi| c for i [m], and for every edge {x, y} between two different components either x S or y S. Hence, the Pi are the remaining weakly connected components if the vertices in S are removed from GCAUSAL(P). Therefore, a valid tree-decomposition T, χ of GCAUSAL(P) can be constructed in the following way: T is a complete bipartite graph with vertices b S and b1, . . . , bm such that b S is adjacent to all bi. The labeling χ is defined by χ(b S) = S and χ(bi) = Pi S. Hence, the treewidth tw(GCAUSAL(P)) for every YES-instance is bounded above by k + c 1. We now use Bodlaender s theorem to check in fpt-time whether tw(GCAUSAL(P)) k + c 1. If the answer is NO, there cannot be a backdoor set of size k. Otherwise, we construct an MSO formula ϕ (whose size depends only on c and k) which checks whether there is a set of vertices S V such that there is no weakly connected component of size larger than c after deleting the vertices in S. Then we can check in fpt-time whether GCAUSAL(P) satisfies ϕ by using Courcelle s theorem. It remains to present the MSO formula ϕ. For this, let adj(x, y) be the symmetric adjacency relation stating that vertex x is adjacent to/from vertex y. Then, ϕ is defined as follows: ϕ := S V |S| k x1, . . . , xc+1 V \ S 1 i 3. We claim that (X, Y, Z), T, k is a YES-instance of 3-DIMENSIONAL MATCHING if and only if the instance P, t k with P = V, D, A, I, G is a YES-instance of c-CAUSAL DETECTION[ACTIONS]. Suppose that (X, Y, Z), T, k is a YES-instance of 3DIMENSIONAL MATCHING and let T be a set of at least k triples witnessing this. It is straightforward to check that the set A = { at | t T \ T } satisfies cc-size(GCAUSAL(P \ A )) c and hence A is a solution of P, t k . For the reverse direction suppose that P, t k is a YESinstance of c-CAUSAL DETECTION[ACTIONS] and let A be a set of at most t k actions witnessing this. We claim that the set T = { t | at / A } satisfies t t = for every t and t in T . Suppose for a contradiction that there are t and t in T with t t = . It follows that the graph GCAUSAL(G \ A ) contains a component that contains all vertices in t t and additionally the vertices { vi t | t {t, t } and 3 < i c }. Since we can assume w.l.o.g. that t = t and thus |t t | 4 this contradicts our assumption that all components of the graph GCAUSAL(P \ A ) have cardinality at most c. The following technical lemma is very useful to simplify the proof of the next theorem, an fpt-result for the detection problem. c-BALANCED LABEL SEPARATOR Instance: An undirected edge-labeled multigraph G (without self-loops), a labeling function λ : E(G) N, and an integer k. Parameter: k. Question: Is there a set L of at most k labels such that cc-size(G \ λ 1(L)) c? Lemma 6. c-BALANCED LABEL SEPARATOR is fpt. With help of this lemma, we now show the desired result. Theorem 7. c-CAUSAL DETECTION[ACTIONS] is fpt. Proof. We reduce c-CAUSAL DETECTION[ACTIONS] to c BALANCED LABEL SEPARATOR. Let P, k be an instance of CAUSAL DETECTION[ACTIONS]. We construct an equivalent instance G, λ, k of c-BALANCED LABEL SEPARATOR as follows. Let G be the undirected edge-labeled multigraph with vertex set V and an edge e labeled with a between two variables v and v for every action a A with pre(a)[v] = u and eff(a)[v ] = u and for every action a A with eff(a)[v] = u and eff(a)[v ] = u. It is straightforward to check that P, k is a YES-instance of c-CAUSAL DETECTION[ACTIONS] if and only if G, λ, k is a YES-instance of c-BALANCED LABEL SEPARATOR. After this promising result for the detection problem, we turn to the evaluation problem. In case neither the plan length nor the size of the domain of the variables is bounded, evaluation remains hard even for action-deletion-backdoors. However, if either the domain or the plan length is bounded we can show two fpt-results for the evaluation problem. Theorem 8. 9-CAUSAL EVALUATION[ACTIONS] is para NP-hard even if the global actions (the actions in the backdoor S) have no preconditions. Proof (sketch). The proof is via a reduction from 3-SAT. Let Φ be a 3-CNF formula with variables x1, . . . , xn. We construct an instance P, S of 9-CAUSAL EVALUATION[ACTIONS] where S contains 5 global actions s1, . . . , s5 and GCAUSAL(P) \ S contains one component for each clause of Φ and one global component (each component contains at most 9 variables). The main idea is that the global component guesses an assignment α for the variables of Φ and forces a sequence of global actions that represents the guessed assignment. In particular, for every variable xi, if α(xi) = 0, then the following sequence of global actions is forced by the global component: s1, s3, . . . , s1, s3 | {z } (i 1)-times s1,s3 , s4, s3, s1, s3, . . . , s1, s3 | {z } (n i)-times s1,s3 If α(xi) = 1, then the following sequence of global actions is forced by the global component: s2, s3, . . . , s2, s3 | {z } (i 1)-times s2,s3 , s4, s3, s2, s3, . . . , s2, s3 | {z } (n i)-times s2,s3 Observe that the above sequences uniquely identify the variable xi and its assignment α(xi) for every variable xi. The total sequence of global actions forced by the global component is then the concatenation of the above sequences for every variable xi. The components of the clauses now ensure that every clause is satisfied by the assignment chosen by the global component. They do so by allowing only sequences of global actions that correspond to a satisfied literal of the respective clause to lead to their (local) goal state. Due to space limitations we had to omit the details of the construction and a rigorous proof. Theorem 9. c-CAUSAL EVALUATION[ACTIONS] is fpt for planning instances with bounded domain. Proof. Let P, S with P = V, D, A, I, G be an instance of c-CAUSAL EVALUATION[ACTIONS] such that |D| d for some constant d. 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 f from V1 D1 A1 to V2 D2 A2 such that: (i) f(v) V2 for every v V1, f(d) D2 for every d D1, and f(a) A2 for every a A1, (ii) for every a A1 and v V1 it holds that f(pre(a)[v]) = pre(f(a))[f(v)] and f(eff(a)[v]) = eff(f(a))[f(v)], and (iii) for every v V1 it holds that f(I1[v]) = I2[f(v)] and f(G1[v]) = G2[f(v)]. Let C1 and C2 be two weakly connected components of the graph GCAUSAL(P\S). We say that C1 and C2 are globally equivalent, denoted by C1 C2, if there is an isomorphism f between P[C1] and P[C2] such that f(s) = s for every s S. Claim 1. The number of equivalence classes of the components of GCAUSAL(P \ S), with respect to , is at most c G = c ((d + 1)2c)|S|+2 2(d+1)2c. The claim follows from the following observations for every component C of GCAUSAL(P \ S): (i) C has at most c variables, (ii) there are at most dc (d + 1)c (d + 1)2c possible configurations for the initial state and for the goal state on the variables of C, (iii) there are at most (d + 1)2c possible combinations of preconditions and effects for any action in S on the variables of C, (iv) there are at most (d + 1)2c possible distinct actions defined only on the variables of C, and (v) there are at most 2(d+1)2c distinct sets of actions defined only on the variables of C. Claim 2. Let C1 and C2 be two globally equivalent components of GCAUSAL(P\S), let V1 be the variables corresponding to the vertices of C1, and let P = P \ V1. Then, P is a YESinstance if and only if so is P . Suppose that there is a plan ω for P. Then it is straightforward to verify that the plan ω obtained from ω after deleting all occurrences of actions that have at least one precondition or one effect in C1 and are not in S, is a plan for P . For the reverse direction, let ω be a plan for P and let f be an isomorphism from P[C2] to P[C1] such that f(s) = s for every s S. Furthermore, let ω be obtained from ω after replacing every occurrence of an action a in P that has at least one precondition or one effect in C2 and is not in S, with the sequence (a, f(a)). Again it is straightforward to check that ω is a plan for P. The following algorithm solves the SAS+ PLANNING problem for P in 3 steps. 1) Compute the global type, i.e., the equivalence class with respect to , of each component C in GCAUSAL(P \ S). 2) Compute the reduced instance P of SAS+ PLANNING from P by deleting all but one component for each global component type from P. 3) Compute the state-transition graph of the reduced instance P and solve P . Return YES, if P is a YES-instance and otherwise NO. The correctness of the algorithm follows immediately from Claim 2. The running time of the algorithm is obtained as follows. Because of Claim 1, Step 1 needs time O(|V | c G) (recall that c G is the number of equivalence classes with respect to ), Step 2 can be executed in time O(|V |) (by using clever data structures), and Step 3 needs time at most O(dc c G), because there are at most c c G variables left in the reduced instance. Hence the total running time of the algorithm is O(dc c G + |V | c G), which shows that c-CAUSAL EVALUATION[ACTIONS] is fixed-parameter tractable for planning instances with a bounded domain of the variables. Theorem 10. c-BOUNDED CAUSAL EVALUATION[ACTIONS] is fpt. Proof. Let P, S, k be an instance of c-BOUNDED CAUSAL EVALUATION[ACTIONS]. The main idea is to iterate over all k l |S|l sequences of actions from S that can appear in a plan of length l k for P. For each of those sequences ω and for every component C of GCAUSAL(P \ S) one can then compute the minimal plan (if one exists) for P[C] in polynomial time with the help of the state-transition graph of P[C] (whose size is at most |D|c). Then P has a plan of length at most k if and only if there is a sequence of actions of S whose length l is between 0 and k such that l + s k, where s is the sum of the lengths of the minimal plans for each component of GCAUSAL(P \ S). Theorems 9 and 10 show in combination with Theorem 7 that the backdoor approach can be used to obtain new fptalgorithms for planning problems. This is because, under action-deletion-backdoors the detection problem as well as three important evaluation problems are efficiently solvable as long as the size of the backdoor is moderate. The fptalgorithm for planning works as follows. First we search for a small backdoor (detection phase), which is then used in a subsequent step to solve the given planning instance (evaluation phase). Observe that this is the first fpt-algorithm for planning with unbounded plan length, which does not depend on the parameters |V | or |A|. 4 Discussion In this section we comment briefly on the potential impact to practical applications and the choice of the tractable base class. There has recently been a growing interest in finding tractable fragments of planning using the causal graph (Brafman and Domshlak 2003; Chen and Gim enez 2010; Katz and Domshlak 2008; 2010; Gim enez and Jonsson 2008; Katz and Keyder 2012)). As pointed out in (Katz and Keyder 2012): Such results are not purely of theoretical interest, as the causal graph is used in a variety of practical applications from problem decomposition (Brafman and Domshlak 2006) to the derivation of non-admissible domain-independent heuristics for planning (Helmert 2004). We believe that this applies even more to (fixed-parameter) tractable extensions of these fragments obtained by the backdoor approach. In particular, the backdoor approach adds a novel dimension of flexibility to the definition of these tractable classes that allows one to trade efficiency for generality to best suit the particular application. This also allows to use the insights obtained for those tractable classes to solve arbitrary planning instances. Regarding the choice of the tractable base class, we want to point out that even though the class of instances with bounded component size of the causal graph itself can be seen as rather trivial, the backdoor approach extends its applicability to arbitrary planning instances. Moreover, as shown by (Chen and Gim enez 2010) this class is as general as possible for unbounded planning, in the sense that it cannot be properly contained in any other polynomial-time tractable fragment of planning. Nevertheless, considering further fragments remains an interesting direction for future work. 5 Conclusion In this work we have introduced the first two types of backdoor sets for planning. The distance to the tractable fragment was expressed by the number of variables or actions that need to be removed in order to obtain a causal graph of bounded maximum component size. For each backdoor type and each setting of considered SAS+ planning formalisms (with bounded/unbounded plan length and bounded/unbounded domain of the variables) we have analyzed the (parameterized) complexity of the detection and evaluation problem. In three cases (all settings under action-deletion-backdoors with the exception of unbounded planning with unbounded domain of the variables) we have obtained the most desirable result where detection as well as evaluation are fixedparameter-tractable. In the remaining cases, we have ruled out the existence of an fpt-algorithm by showing hardness for W[1] or para NP. We envisage the study of other underlying graph structures (such as the planning graph) to obtain further useful notions of backdoor sets. By employing techniques such as dynamic programming we plan to improve the running time of the fpt-result obtained via Courcelle s theorem. Furthermore, we want to explore additional supporting parameters that help to make the evaluation problem in the variable-deletion setting fixed-parameter tractable. Acknowledgments We want to thank the anonymous reviewers for their constructive comments. Sebastian Ordyniak acknowledges support from the Employment of Newly Graduated Doctors of Science for Scientific Excellence (CZ.1.07/2.3.00/30.0009). Martin Kronegger and Andreas Pfandler were supported by the Austrian Science Fund (FWF): P25518-N23. B ackstr om, C., and Jonsson, P. 2013. A refined view of causal graphs and component sizes: SP-closed graph classes and beyond. J. Artif. Intell. Res. 47:575 611. B ackstr om, C., and Nebel, B. 1995. Complexity results for SAS+ planning. Comput. Intell. 11:625 656. B ackstr om, C.; Chen, Y.; Jonsson, P.; Ordyniak, S.; and Szeider, S. 2012. The complexity of planning revisited a parameterized analysis. In Proc. AAAI 2012, 1735 1741. AAAI Press. Bodlaender, H. L. 1996. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6):1305 1317. Brafman, R. I., and Domshlak, C. 2003. Structure and complexity in planning with unary operators. J. Artif. Intell. Res. 18:315 349. Brafman, R. I., and Domshlak, C. 2006. Factored planning: How, when, and when not. In Proc. AAAI 2006, 809 814. AAAI Press. Bylander, T. 1994. The computational complexity of propositional STRIPS planning. Artif. Intell. 69(1 2):165 204. Chen, H., and Gim enez, O. 2010. Causal graphs and structurally restricted planning. J. Comput. Syst. Sci. 76(7):579 592. Courcelle, B. 1990. Graph rewriting: An algebraic and logic approach. In van Leeuwen, J., ed., Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B). Elsevier. 193 242. Downey, R. G., and Fellows, M. R. 1999. Parameterized Complexity. Springer. Downey, R. G.; Fellows, M. R.; and Stege, U. 1999. Parameterized complexity: A framework for systematically confronting computational intractability. In Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, volume 49 of DIMACS Series in Disc. Math. Theor. Comput. Sci. DIMACS. 49 99. Dvor ak, W.; Ordyniak, S.; and Szeider, S. 2012. Augmenting tractable fragments of abstract argumentation. Artif. Intell. 186:157 173. Fichte, J. K., and Szeider, S. 2011a. Backdoors to tractable answer-set programming. In Proc. IJCAI 2011, 863 868. Fichte, J. K., and Szeider, S. 2011b. Backdoors to tractable answer-set programming. Co RR abs/1104.2788. Fichte, J. K., and Szeider, S. 2013. Backdoors to normality for disjunctive logic programs. In Proc. AAAI 2013, 320 327. AAAI Press. Flum, J., and Grohe, M. 2003. Describing parameterized complexity classes. Inf. Comput. 187(2):291 319. Flum, J., and Grohe, M. 2006. Parameterized Complexity Theory. Springer. Garey, M. R., and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. Gaspers, S., and Szeider, S. 2012a. Backdoors to acyclic SAT. In Proc. ICALP 2012, volume 7391 of LNCS, 363 374. Springer. Gaspers, S., and Szeider, S. 2012b. Backdoors to satisfaction. In Bodlaender, H. L.; Downey, R.; Fomin, F. V.; and Marx, D., eds., The Multivariate Algorithmic Revolution and Beyond, volume 7370 of LNCS, 287 317. Springer. Gim enez, O., and Jonsson, A. 2008. The complexity of planning problems with simple causal graphs. J. Artif. Intell. Res. 31:319 351. Gottlob, G., and Szeider, S. 2008. Fixed-parameter algorithms for artificial intelligence, constraint satisfaction and database problems. Comput. J. 51(3):303 325. Gregory, P.; Fox, M.; and Long, D. 2008. A new empirical study of weak backdoors. In Proc. CP 2008, volume 5202 of LNCS, 618 623. Springer. Helmert, M. 2004. A planning heuristic based on causal graph analysis. In Proc. ICAPS 2004, 161 170. AAAI. Katz, M., and Domshlak, C. 2008. New islands of tractability of cost-optimal planning. J. Artif. Intell. Res. 32:203 288. Katz, M., and Domshlak, C. 2010. Optimal admissible composition of abstraction heuristics. Artif. Intell. 174(12 13):767 798. Katz, M., and Keyder, E. 2012. Structural patterns beyond forks: Extending the complexity boundaries of classical planning. In Proc. AAAI 2012. AAAI Press. Kilby, P.; Slaney, J. K.; Thi ebaux, S.; and Walsh, T. 2005. Backbones and backdoors in satisfiability. In Proc. AAAI 2005, 1368 1373. AAAI Press / The MIT Press. Knoblock, C. A. 1994. Automatically generating abstractions for planning. Artif. Intell. 68(2):243 302. Kronegger, M.; Pfandler, A.; and Pichler, R. 2013. Parameterized complexity of optimal planning: A detailed map. In Proc. IJCAI 2013, 954 961. AAAI Press. Niedermeier, R. 2006. Invitation to Fixed-Parameter Algorithms. Oxford University Press. Nishimura, N.; Ragde, P.; and Szeider, S. 2004. Detecting backdoor sets with respect to Horn and binary clauses. In Proc. SAT 2004, 96 103. Papadimitriou, C. H. 1994. Computational complexity. Addison-Wesley. Pfandler, A.; R ummele, S.; and Szeider, S. 2013. Backdoors to abduction. In Proc. IJCAI 2013, 1046 1052. AAAI Press. Pietrzak, K. 2003. On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci. 67(4):757 771. Samer, M., and Szeider, S. 2009. Backdoor sets of quantified Boolean formulas. J. Autom. Reasoning 42(1):77 97. Williams, R.; Gomes, C.; and Selman, B. 2003. Backdoors to typical case complexity. In Proc. IJCAI 2003, 1173 1178. Morgan Kaufmann.