Title: Computational Complexity of Planning with Temporal Goals
Authors: Chitta Baral, Vladik Kreinovich, Sudeshna Sarkar and Raul Trejo.
Abstract
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.