Title: Computational Complexity of Planning with Temporal Goals

Authors: Chitta Baral, Vladik Kreinovich, Sudeshna Sarkar and Raul Trejo.


In the last decade, there have been several studies on the computational complexity of planning. In these studies planning is about finding a plan that takes the world to one of several desired states. The set of desired states is often described by a goal formula. In some recent papers, the use of linear temporal logic to specify goals for planning has been studied. Such goals are able to specify conditions on the trajectory forced by the plan. In this paper we study the complexity of planning with such goals. In addition we also propose that for certain kind of goals we may need more than linear temporal logics to specify them. In particular we define what it means for a plan to satisfy a goal in branching time temporal logics such as CTL and CTL$^*$. We analyze the complexity of planning with such goals and identify a variant of CTL goals which leads to a lower complexity of planning. Our main results are: For goals expressible in Linear Temporal Logic, planning has the same complexity as for non-temporal goals: it is {\bf NP}-complete; and for goals expressible in a more general Branching Temporal Logic such as CTL and CTL$^*$ , planning is {\bf PSPACE}-complete.