Computational complexity of planning and approximate planning in the presence of incompleteness

In the last several years, there have been several studies about the comput ational complexity of classical planning assuming that the planner has comp lete knowledge about the initial situation. Recently, there have been propo sals to use 'sensing' actions to plan in the presence of incompleteness. In this paper we study the complexity of planning in such cases. In our study we use the action description language A proposed in 1991 by Gelfond and L ifschitz, and its extensions. It is known that if we consider only plans of tractable (polynomial) durati on, planning in A-with complete information about the initial situation-is NP-complete: even checking whether a given objective is attainable from a g iven initial state is NP-complete. In this paper, we show that the planning problem in the presence of incompleteness is indeed harder: it belongs to the next level of the complexity hierarchy (in precise terms, it is Sigma P -2-complete). To overcome the complexity of this problem, Baral and Son hav e proposed several approximations. We show that under certain conditions, o ne of these approximations-0-approximation-makes the problem NP-complete (t hus indeed reducing its complexity). (C) 2000 Elsevier Science B.V. All rig hts reserved.