Computational complexity of planning and approximate planning
in presence of incompleteness.
C. Baral,
V. Kreinovich, and R. Trejo.
Abstract
In the last several years, there have been several studies about
the computational complexity of classical planning assuming that
the planner has complete knowledge about the initial situation.
Recently, there has been proposal to use `sensing' actions to plan
in presence of incompleteness. In this paper we study the
complexity of planning in such cases. In our study we use the
action description language $\cal A$ proposed in 1991 by Gelfond
and Lifschitz, and its extensions.
It is known that if we consider only plans of feasible
(polynomial) length, planning -- with complete information about
the initial situation -- in $\cala$ is {\bf NP}-complete: even
checking whether a given objective is attainable from a given
initial state is {\bf NP}-complete. In this paper, we show that
the planning problem in presence of incompleteness is indeed
harder: it belongs to the next level of complexity hierarchy (in
precise terms, it is $\Sigma_2{\bf P}$-complete). To overcome the
complexity of this problem, Baral and Son have proposed several
approximations. We show that under certain conditions, one of
these approximations -- 0-approximation -- makes the problem {\bf
NP}-complete (thus indeed reducing its complexity).