Parameterized Complexity of Optimal Planning: A Detailed Map
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 954-960.
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).
@inproceedings{ijcai2013p146,
title = {Parameterized Complexity of Optimal Planning: A Detailed Map},
author = {Kronegger, Martin and Pfandler, Andreas and Pichler, Reinhard},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {954--960},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/146},
}
TY - CPAPER TI - Parameterized Complexity of Optimal Planning: A Detailed Map AU - Kronegger, Martin AU - Pfandler, Andreas AU - Pichler, Reinhard T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 954 EP - 960 UR - https://ijcai.org/proceedings/2013/146 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
