Towards feasible approach to plan checking under probabilistic
uncertainty: Interval methods.
Raul Trejo, Vladik Kreinovich and Chitta Baral.
Abstract
The main problem of {\it 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
{\it 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, we only know the probabilities of
different fluents; in such situations, even plan checking becomes
computationally difficult. {\em In this paper, 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 proposed earlier to describe planning in the case
of partial knowledge.
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.