---
title: "Computational Complexity of Planning and Approximate Planning in Presence of Incompleteness"
authors:
  - "Chitta Baral"
  - "Vladik Kreinovich"
  - "Raul Trejo"
doi: ""
url: "https://ijcai.org/proceedings/1999/135"
pdf: "https://ijcai.org/proceedings/1999/0135.pdf"
venue: "Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence"
year: 1999
pages: "948-954"
track: "Planning and Scheduling"
keywords:
---

# Computational Complexity of Planning and Approximate Planning in Presence of Incompleteness

Chitta Baral, Vladik Kreinovich, Raul Trejo

*Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence*, pages 948-954.

## 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).