Computational Complexity of Planning, Diagnosis, and Diagnostic Planning in the Presence of Static Causal Laws
Chitta R. Baral, Le-Chi Tuan, Владик Крейнович · scholarworks - UTEP (The University of Texas at El Paso) · 2000
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 the result res(a,s) of applying an action a to a system in a state s is uniquely determined by the action a and by the state s. In real-life planning, some consequences of certain actions are non-deterministic. In this paper, we expand the known results about computational complexity of planning (with and without sensing) to this more general class of planning problems. In addition to analyzing computational complexity of regular planning - in which the goal is to achieve a certain property of the system - we also analyze the computational complexity of a simpler problem - of diagnosing the system.