The Complexity of Optimal Monotonic Planning: The Bad, the Good, and the Causal Graph
Abstract
For almost two decades, monotonic, or ``delete free,'' relaxation has been one of the key auxiliary tools in the practice of domain-independent deterministic planning. In the particular contexts of both satisficing and optimal planning, it underlies most state-of-the-art heuristic functions. While satisficing planning for monotonic tasks is polynomial-time, optimal planning for monotonic tasks is NP-equivalent. We took a step towards a fine-grained classification of worst-case time complexity of optimal monotonic planning, with a focus on ``what gets harder" and ``what gets easier" when switching from optimal planning to optimal relaxed planning, in the context of finite-domain planning task representations.
Cite
Text
Domshlak and Nazarenko. "The Complexity of Optimal Monotonic Planning: The Bad, the Good, and the Causal Graph." Journal of Artificial Intelligence Research, 2013. doi:10.1613/JAIR.4145Markdown
[Domshlak and Nazarenko. "The Complexity of Optimal Monotonic Planning: The Bad, the Good, and the Causal Graph." Journal of Artificial Intelligence Research, 2013.](https://mlanthology.org/jair/2013/domshlak2013jair-complexity/) doi:10.1613/JAIR.4145BibTeX
@article{domshlak2013jair-complexity,
title = {{The Complexity of Optimal Monotonic Planning: The Bad, the Good, and the Causal Graph}},
author = {Domshlak, Carmel and Nazarenko, Anton},
journal = {Journal of Artificial Intelligence Research},
year = {2013},
pages = {783-812},
doi = {10.1613/JAIR.4145},
volume = {48},
url = {https://mlanthology.org/jair/2013/domshlak2013jair-complexity/}
}