Author name cluster

Martin Kronegger

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

1 author row

AIJ Journal 2019 Journal Article

Backdoors to planning

Martin Kronegger
Sebastian Ordyniak
Andreas Pfandler

Backdoors measure the distance to tractable fragments and have become an important tool to find fixed-parameter tractable (fpt) algorithms for hard problems in AI and beyond. 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. For several interesting cases we achieve the most desirable outcome: detection and evaluation are fpt. In addition, we explore the power of polynomial preprocessing for all fpt-results, i. e. , we investigate whether polynomial kernels exist. We show that for the detection problems, polynomial kernels exist whereas we rule out the existence of polynomial kernels for the evaluation problems.

Details DOI

IJCAI Conference 2015 Conference Paper

Fixed-Parameter Tractable Reductions to SAT for Planning

Ronald de Haan
Martin Kronegger
Andreas Pfandler

Planning is an important AI task that gives rise to many hard problems. In order to come up with efficient algorithms for this setting, it is important to understand the sources of complexity. For planning problems that are beyond NP, identifying fragments that allow an efficient reduction to SAT can be a feasible approach due to the great performance of modern SAT solvers. In this paper, we use the framework of parameterized complexity theory to obtain a more fine-grained complexity analysis of natural planning problems beyond NP. With this analysis we are able to point out several variants of planning where the structure in the input makes encodings into SAT feasible. We complement these positive results with some hardness results and a new machine characterization for the intractability class ∃∗ ∀k -W[P].

PDF Details

AAAI Conference 2015 Conference Paper

Variable-Deletion Backdoors to Planning

Martin Kronegger
Sebastian Ordyniak
Andreas Pfandler

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).

PDF Details

AAAI Conference 2014 Conference Paper

A Parameterized Complexity Analysis of Generalized CP-Nets

Martin Kronegger
Martin Lackner
Andreas Pfandler
Reinhard Pichler

Generalized CP-nets (GCP-nets) allow a succinct representation of preferences over multi-attribute domains. As a consequence of their succinct representation, many GCP-net related tasks are computationally hard. Even finding the more preferable of two outcomes is PSPACE-complete. In this work, we employ the framework of parameterized complexity to achieve two goals: First, we want to gain a deeper understanding of the complexity of GCP-nets. Second, we search for efficient fixed-parameter tractable algorithms.

PDF Details

AAAI Conference 2014 Conference Paper

Backdoors to Planning

Martin Kronegger
Sebastian Ordyniak
Andreas Pfandler

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.

PDF Details

IJCAI Conference 2013 Conference Paper

Parameterized Complexity of Optimal Planning: A Detailed Map

Martin Kronegger
Andreas Pfandler
Reinhard Pichler

The goal of this paper is a systematic parameterized complexity analysis of different variants of propositional STRIPS planning. We identify several natural problem parameters and study all possible combinations of 9 parameters in 6 different settings. These settings arise, for instance, from the distinction if negative effects of actions are allowed or not. We provide a complete picture by establishing for each case either paraNPhardness (i. e. , the parameter combination does not help) or W[t]-completeness with t ∈ {1, 2} (i. e. , fixed-parameter intractability), or FPT (i. e. , fixedparameter tractability).

PDF Details DOI