[Back]

M. Kronegger:
"On the Parameterized Complexity of Planning";
Supervisor, Reviewer: R. Pichler, C. Bäckström; Institut für Informationsysteme, 2016.

One of the fundamental goals in computer science is to understand the computational complexity of important problems. Many of these important problems have been proven to be computationally hard. Thus, for the design of efficient algorithms it is indispensable to search for tractable fragments. Structure in the input has turned out to be one of the key ingredients that needs to be exploited for such a design. The relatively new field of parameterized complexity theory has emerged as a powerful tool to obtain efficient algorithms by taking structure in the input into account. Here, the computational complexity is measured not only in terms of the input size but also in terms of a parameter describing structure in the input. Planning is one of the central problems in artificial intelligence. Due to its general definition, planning has many applications. Thus, there is a great need for efficient algorithms. For decades, researchers have analyzed the computational complexity of planning. Most variants of planning turned out to be at least \NP-hard while only some restricted variants yield tractability. A deeper understanding of the sources of the complexity of planning is crucial for the development of efficient algorithms. A systematic parameterized complexity analysis considerably contributes to such a deeper understanding. In this work we use the modern framework of parameterized complexity to perform a fine-grained complexity analysis of planning. In particular, the main results are the following: (i) we systematically analyze the complexity of different variants of planning with respect to several natural parameters. For each of the variants we provide a complete picture by establishing for each parameter combination either a fixed-parameter tractable algorithm (fpt-algorithm) or rule out the existence thereof by showing hardness for parameterized intractability classes; (ii) we introduce the concept of backdoors, a modern tool to obtain fpt-algorithms, to planning. For two of three types of backdoors we show several novel fpt-algorithms. Among these results is the first fpt-result for planning with unbounded plan length that does neither limit the number of variables nor the number of actions. We also identify several cases that yield a polynomial kernel, i.e., cases where efficient preprocessing is possible. Furthermore, we show a close connection between planning and a verification problem which is called Vector Addition Systems with States; (iii) due to the great performance of state-of-the-art SAT solvers, encodings into the satisfiability problem of propositional formulas (SAT) often are a feasible approach for solving \NP-complete problems. However, in general, efficient encodings into SAT do not exist for problems beyond \NP. In this work we make use of so-called fpt-reductions to SAT to analyze whether for planning problems that are harder than \NP efficient encodings in terms of fpt-reductions into SAT exist. We show that some natural but hard variants of planning can be encoded into SAT efficiently. For other natural variants of planning we show that fpt-reductions into SAT are unlikely to exist.