Interval computation methods and probabilistic methods for planning and plan checking under uncertainty and incomplete information

The main problem of planning is to find a sequence of actions that an agent must perform to achieve a given objective. An important part of planning is checking whether a given plan achieves the desired objective. Historically, in AI, the planning and plan checking problems were mainly formulated and solved in a deterministic environment, when the initial state is known precisely and when the results of each action in each state is known (and uniquely determined). In this deterministic case, planning is difficult, but plan checking is straightforward. In many real-life situations, however, the agent does not have complete information about the initial state of the system. In the best case, the agent may know the probabilities of the different fluents that describe the state of the system; sometimes even such probabilities are unknown and the agent has no information whatsoever about the initial state of some fluents. Recently, there has been proposal to use ‘sensing’ actions to plan in presence of incompleteness. In this work we use the action description language [special characters omitted] proposed in 1993 by M. Gelfond and V. Lifschitz, and its extensions, that allow for sensing actions. In real-life planning, we often also use the knowledge about the system\u27s past behavior. To describe such more realistic planning situations, a special language [special characters omitted] was developed in 1997 by C. Baral, M. Gelfond and A. Provetti. In this work we expand the known results about computational complexity of planning to this more general class of planning problems. The language [special characters omitted] allows planning in the situations with complete information. It is known that, 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 given initial state is NP-complete. In this work, we show that the planning problem in presence of incompleteness is indeed harder: it belongs to the next level of complexity hierarchy (in precise terms, it is Σ2P-complete). To overcome the complexity of this problem, C. Baral and T. Son have proposed several approximations. We show that under certain conditions, one of these approximations—0-approximation—makes the problem NP-complete (thus indeed reducing its complexity). We also show results about the complexity of planning when the past states are considered. Then we address the planning problem when initial probabilities of fluents are known. We describe how methods of interval computations can be used to get a feasible approximation to plan checking under probabilistic uncertainty. The resulting method is a natural generalization of 0-approximation. It turns out that some of the resulting probabilistic techniques coincides with heuristically proposed “fuzzy” methods. Thus, we justify these fuzzy heuristics as a reasonable feasible approximation to the (NP-hard) probabilistic problem. In view of the usefulness of interval computation techniques in planning, we overview these techniques and propose improvements which lead to optimal and sub-optimal interval methods