Complexity Results for SAS+ Planning
Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Planning. Pages 1430-1434.
Abstract
We have previously reported a number of tractable planning problems defined in the SAS+ formalism. This paper complements these results by providing a complete map over the complexity of SAS+ planning under all combinations of the previously considered restrictions. We analyse the complexity both of finding a minimal plan and of finding any plan. In contrast to other complexity surveys of planning we study not only the complexity of the existence problems but also of the search problems. We prove that the SAS+ -PUS problem is the maximal tractable problem under the restrictions we have considered if we want to find a minimal plan. If we are satisfied with finding any plan, then we can generalize further to the SAS+-US problem, which we prove to be the maximal tractable problem in this case.
@inproceedings{ijcai1993p198,
title = {Complexity Results for SAS+ Planning},
author = {Bäckström, Christer and Nebel, Bernhard},
booktitle = {Proceedings of the Thirteenth International Joint Conference on
Artificial Intelligence, {IJCAI-93}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ruzena Bajcsy},
pages = {1430--1434},
year = {1993},
note = {Planning},
url = {https://ijcai.org/proceedings/1993/198},
}
TY - CPAPER TI - Complexity Results for SAS+ Planning AU - Bäckström, Christer AU - Nebel, Bernhard T2 - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93 PB - International Joint Conferences on Artificial Intelligence PY - 1993 SP - 1430 EP - 1434 UR - https://ijcai.org/proceedings/1993/198 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
