**
Probabilistic Planning with Clear Preferences on Missing Information
**

**
Maxim Likhachev* and Anthony Stentz**
**

***University
of Pennsylvania, **Carnegie Mellon University**

**Abstract**

For many real-world problems, environments at the time of planning
are only partially-known. For example, robots often have to
navigate partially-known terrains, planes often have to be scheduled
under changing weather conditions, and car route-finders often have
to figure out paths with only partial knowledge of traffic
congestions. While the general decision-theoretic planning that
takes into account the uncertainty about the environment
is hard to scale to large problems, many such problems
exhibit a special property: one can clearly identify beforehand the
best (called clearly preferred) values for the variables that
represent the unknowns in the environment. For example, in the robot
navigation problem, it is always preferred to find out that an
initially unknown location is traversable rather than not, in the
plane scheduling problem, it is always preferred for the weather to
remain a good flying weather, and in route-finding problem, it is
always preferred for the road of interest to be clear of traffic. It
turns out that the existence of the clear preferences can be used to
construct an efficient planner, called PPCP (Probabilistic Planning
with Clear Preferences), that solves these planning problems by
running a series of deterministic low-dimensional A*-like searches.

In this paper, we formally define the notion of clear preferences on
missing information, present the PPCP algorithm together with its
extensive theoretical analysis, describe several useful extensions
and optimizations of the algorithm and demonstrate the usefulness of
PPCP on several applications in robotics. The theoretical analysis
shows that once converged, the plan returned by PPCP is guaranteed
to be optimal under certain conditions. The experimental analysis
shows that running a series of fast low-dimensional searches turns
out to be much faster than solving the full problem at once since
memory requirements are much lower and deterministic searches are
orders of magnitude faster than probabilistic planning.

*
*