A complete parameterized complexity analysis of bounded planning

DOI10.1016/J.JCSS.2015.04.002MaRDI QIDQ2353405zbMATH OpenOpenAlexFDO

Authors Peter Jonsson, Sebastian Ordyniak, Stefan Szeider, Christer Bäckström

Publication date 13 July 2015

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.7828

zbMATH Keywords

complexity of automated planningkernelizationparameterized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Abstract: The propositional planning problem is a notoriously difficult computational problem, which remains hard even under strong syntactical and structural restrictions. Given its difficulty it becomes natural to study planning in the context of parameterized complexity. In this paper we continue the work initiated by Downey, Fellows and Stege on the parameterized complexity of planning with respect to the parameter "length of the solution plan." We provide a complete classification of the parameterized complexity of the planning problem under two of the most prominent syntactical restrictions, i.e., the so called PUBS restrictions introduced by Baeckstroem and Nebel and restrictions on the number of preconditions and effects as introduced by Bylander. We also determine which of the considered fixed-parameter tractable problems admit a polynomial kernel and which don't.

Recommendations

• Parameterized complexity and kernel bounds for hard planning problems
• Parameterising the complexity of planning by the number of paths in the domain-transition graphs
• scientific article; zbMATH DE number 67474
• Time and Space Bounds for Planning
• The computational complexity of propositional STRIPS planning

Cites work

• A probabilistic analysis of propositional STRIPS planning
• Algorithms and limits for compact plan representations
• Causal graphs and structurally restricted planning
• Complexity results for standard benchmark domains in planning
• FPT algorithms for connected feedback vertex set
• From macro plans to automata plans
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 1341905 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1946870 (Why is no real title available?)
• scientific article; zbMATH DE number 2038900 (Why is no real title available?)
• scientific article; zbMATH DE number 2201583 (Why is no real title available?)
• Kernelization Lower Bounds by Cross-Composition
• Kernelization: new upper and lower bound techniques
• Macros, reactive plans and compact representations
• On problems without polynomial kernels
• On the complexity of blocks-world planning
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Parameterized complexity and kernel bounds for hard planning problems
• Parametrized complexity theory.
• Solving MAX-\(r\)-SAT above a tight lower bound
• State-variable planning under structural restrictions: algorithms and complexity
• Strong bounds on the approximability of two Pspace-hard problems in propositional planning
• The Causal Graph Revisited for Directed Model Checking
• The complexity of planning problems with simple causal graphs
• The computational complexity of propositional STRIPS planning
• The fast downward planning system
• The Lost Continent of Polynomial Time: Preprocessing and Kernelization
• The parameterized complexity of domination-type problems and application to linear codes
• The Turing way to parameterized complexity
• Tractable plan existence does not imply tractable plan generation

Cited in

(12)

• A framework for analysing state-abstraction methods
• Decidability and complexity of action-based temporal planning over dense time
• On structural parameterizations of the bounded-degree vertex deletion problem
• Backdoors to planning
• Sufficient Conditions for the Existence of Resolution Complete Planning Algorithms
• On structural parameterizations of the bounded-degree vertex deletion problem
• scientific article; zbMATH DE number 6519681 (Why is no real title available?)
• Parameterized complexity and kernel bounds for hard planning problems
• Refining complexity analyses in planning by exploiting the exponential time hypothesis
• Cost-optimal planning, delete relaxation, approximability, and heuristics
• Parameterising the complexity of planning by the number of paths in the domain-transition graphs
• Structural analysis of optimization problems formulated in planning languages

This page was built for publication: A complete parameterized complexity analysis of bounded planning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2353405)