Computational Complexity of Planning with Temporal Goals
Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Pages 509-513.
Abstract
In the last decade, there has been several studies on the computational complexity of planning. These studies normally assume that the goal of planning is to make a certain fluent true after the sequence of actions. In many real-life planning problems, the goal is represented in a much more complicated temporal form: e.g., in addition to having a desired fluent true at the end, we may want to keep certain fluents true at all times. In this paper, we study the complexity of planning for such temporal goals. We show that for goals expressible in Linear Temporal Logic, planning has the same complexity as for non-temporal goals: it is NP-complete; and for goals expressible in a more general Branching Temporal Logic, planning is PSPACE-complete.
@inproceedings{ijcai2001p71,
title = {Computational Complexity of Planning with Temporal Goals},
author = {Baral, Chitta and Kreinovich, Vladik and Trejo, Raul},
booktitle = {Proceedings of the Seventeenth International Joint Conference on
Artificial Intelligence, {IJCAI-01}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {509--513},
year = {2001},
url = {https://ijcai.org/proceedings/2001/71},
}
TY - CPAPER TI - Computational Complexity of Planning with Temporal Goals AU - Baral, Chitta AU - Kreinovich, Vladik AU - Trejo, Raul T2 - Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01 PB - International Joint Conferences on Artificial Intelligence PY - 2001 SP - 509 EP - 513 UR - https://ijcai.org/proceedings/2001/71 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
