High Level Path Planning with Uncertainty
  For high level path planning, environments are usually modeled as distance
graphs, and path planning problems are reduced to computing the shortest path
in distance graphs. One major drawback of this modeling is the inability to
model uncertainties, which are often encountered in practice. In this paper, a
new tool, called U-yraph, is proposed for environment modeling. A U-graph is an
extension of distance graphs with the ability to handle a kind of uncertainty.
By modeling an uncertain environment as a U-graph, and a navigation problem as
a Markovian decision process, we can precisely define a new optimality
criterion for navigation plans, and more importantly, we can come up with a
general algorithm for computing optimal plans for navigation tasks.
