fchitta asuedu lctuan asuedug

vladik csutepedu Planning is a very important AI problem and it is also a very timeconsuming AI problem To get an idea of how complex dierent planning problems are it is useful to describe the computational complexity of dierent general planning problems This complex ity has been described for problems in which the result resa 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 reallife planning some consequences of certain actions are nondeterministic In this paper we expand the known results about computational complexity of planning with and without sensing to this more gen eral 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 syste