**
PPCP: Efficient Probabilistic Planning with Clear Preferences in Partially-Known Environments
**

**Maxim Likhachev and Anthony Stentz**

**Carnegie Mellon University**

**Abstract**

For most real-world problems the agent operates in only
*partially*-known environments. Probabilistic planners can
reason over the missing information and produce plans that take
into account the uncertainty about the environment. Unfortunately though, they
can rarely scale up to the problems that are of interest in
real-world.
In this paper, however, we show that for a certain
subset of problems we can develop a very efficient probabilistic
planner.
The proposed planner, called PPCP, is applicable to the problems for which
it is clear what values of the missing information would result in the best plan.
In other words, there exists a clear preference for the actual values of the missing information.
For example, in the problem of robot navigation in partially-known
environments it is always preferred to find out that an initially
unknown location is traversable rather than not. The planner we propose
exploits this property by
using a series of deterministic A*-like searches to construct and
refine a policy in anytime fashion. On the theoretical side, we show
that once converged, the policy is guaranteed to be optimal under
certain conditions.
On the experimental side, we show the power of PPCP on the
problem of robot navigation in partially-known terrains. The planner can scale
up to very large environments with thousands of initially unknown
locations. We believe that this is several orders of magnitude more unknowns than
what the current probabilistic planners developed for the same problem can handle.
Also, despite the fact that the problem we experimented on in general does not satisfy the conditions for the solution optimality,
PPCP still produces the solutions that are nearly always optimal.

*
*