Computational complexity of planning
based on partial information about the system's present
and past states
Chitta Baral, Le-Chi Tuan, Raul Trejo and Vladik Kreinovich.
Abstract.
Planning is a very important AI problem, and it is also a very
time-consuming AI problem. To get an idea of how complex different
planning problems are, it is useful to
describe the computational complexity of different general planning
problems. This complexity has been described for problems in which
planning is based on the (complete or partial) information about
the {\it current} state of the system.
In real-life planning problems,
we can often complement the incompleteness of
our {\it explicit} knowledge about the current state
by using the {\it implicit} knowledge about this state which is contained
in the description of the system's {\it past behavior}. For
example, the information about the system's past failures is very important
in planning diagnostic and repair.
To describe planning which can
use the information about the past,
a special language $\cal L$ was developed in 1997 by
C.~Baral, M.~Gelfond and A.~Provetti. In this paper, we
expand the known results about computational complexity of planning
(including our own previous results)
to this more general class of planning problems.