Computational Complexity of Planning and Approximate Planning in Presence of Incompleteness

Abstract

In t he last several yea rs th e co mputational complexity of classical planning and HTN planning have b ee n s tudi ed . But in both cases it is assumed that the planner has complete knowledge about th e initial state. Recently, th ere has b ee n 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 A proposed in 1993 by M. Gelfond and V. Lifschitz and its extensions. The language A allows planning in the situations with complete information. It is known t h at, if we consider only plans of feasible (polynomial) length , the planning problem for such situations is NP-complete : even checking whether a given objective is attainable from a g iv en initi al state is NP- complete. In this paper, we show that th e planning problem in presen ce of incompleteness is indeed hard er : it belongs to the next level of complexity hierarchy (in precise terms, it is I:2P-complete) . To overcome th e complexity of this problem, C. Baral and T . Son have proposed several approximations. We show that under certain conditions, one of th ese approximations - 0-approximation - mak es the problem NP- complete (thus indeed redu cing its complexity).