High Level Path Planning with Uncertainty

Runping Qi, David L. PooleUAI 1991

TL;DR

This paper introduces "U-graphs" to model environments with uncertain connections, moving beyond traditional distance graphs. They formalize path planning in these uncertain environments as a Markovian Decision Process, proposing a novel optimality criterion based on minimizing expected cost and deriving an algorithm to compute optimal navigation plans.

What Problem Does This Paper Address?

Traditional path planning in robotics and AI often relies on distance graphs, where edges represent guaranteed traversable routes between locations. This model breaks down in real-world scenarios where connections are uncertain – for example, a door might be locked, or a bridge might be out. The paper addresses the challenge of planning efficient navigation strategies in such environments where uncertainty is a key factor, and the agent needs to make decisions based on incomplete information.

Methods

The core contribution is the introduction of U-graphs, an extension of standard directed graphs. U-graphs augment traditional edges with switches, which represent uncertain connections. Each switch has an associated probability of being traversable and a cost if it is traversable.

To handle path planning in these U-graphs, the authors formulate the problem as a Markovian Decision Process (MDP). A navigation plan is then treated as a policy for this MDP. The key innovation here is the proposed optimality criterion: minimizing the expected cost to reach a goal, rather than just the worst-case cost. This is a more practical approach for navigation. They derive an algorithm, Algorithm A1, to compute the optimal policy by iteratively calculating the expected cost for each state (configuration) in the MDP, leveraging the fact that the representing graph of the MDP is a Directed Acyclic Graph (DAG).

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • U-graphs are a more expressive model: They capture real-world uncertainty in connectivity, which is crucial for robust navigation.
  • MDPs are a natural fit for uncertain navigation: The sequential decision-making under uncertainty inherent in navigation maps well onto the MDP framework.
  • Expected cost is a practical optimality criterion: Minimizing expected cost is often more desirable than worst-case cost in navigation, as it balances risk and reward.
  • The DAG structure of the MDP is key: This property allows for an efficient, iterative algorithm to compute optimal policies, avoiding the complexity of general MDP solvers.

Key Results

The paper presents a formal framework for path planning in uncertain environments using U-graphs and MDPs. They derive Algorithm A1, which computes an optimal navigation plan (policy) that minimizes the expected cost. The algorithm's complexity is linear in the size of the reachable state space of the MDP, though the state space itself can be exponential in the number of uncertain switches.

Limitations and Future Work

The authors acknowledge that the size of the state space in their MDP formulation can be exponential in the number of uncertain switches. Future work includes exploring other optimality criteria (e.g., cost limits), leveraging hierarchical properties of U-graphs for complexity reduction, and developing approximation algorithms for faster, sub-optimal plans. They also suggest integrating their U-graph model into existing frameworks like Kuipers' TOUR model.

Summary updated

BibTeX
@inproceedings{qi1991high,
  author = {Runping Qi and David L. Poole},
  title = {{High Level Path Planning with Uncertainty}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1991},
}
Figure