Parameterized Complexity of Optimal Planning: A Detailed mAP
Abstract
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 paraNP-hardness (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., fixed-parameter tractability).
Cite
Text
Kronegger et al. "Parameterized Complexity of Optimal Planning: A Detailed mAP." International Joint Conference on Artificial Intelligence, 2013.Markdown
[Kronegger et al. "Parameterized Complexity of Optimal Planning: A Detailed mAP." International Joint Conference on Artificial Intelligence, 2013.](https://mlanthology.org/ijcai/2013/kronegger2013ijcai-parameterized/)BibTeX
@inproceedings{kronegger2013ijcai-parameterized,
title = {{Parameterized Complexity of Optimal Planning: A Detailed mAP}},
author = {Kronegger, Martin and Pfandler, Andreas and Pichler, Reinhard},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2013},
pages = {954-961},
url = {https://mlanthology.org/ijcai/2013/kronegger2013ijcai-parameterized/}
}