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

摘要

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 have been proposals 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 Lifschitz, and its extensions.