Route Planning under Uncertainty: The Canadian Traveller Problem

Evdokia Nikolova, David R. KargerAAAI 2008

Abstract

The Canadian Traveller Problem (CTP) is a fundamental challenge in stochastic pathfinding where edge costs are revealed only upon arrival at an adjacent node. This paper investigates the computational complexity of CTP, identifying specific graph topologies—such as Directed Acyclic Graphs (DAGs) and disjoint paths—where exact polynomial-time solutions exist. Furthermore, the study evaluates common heuristics, demonstrating that while the Minimum Expected Distance (MED) can be exponentially suboptimal, the Expected Minimum Distance (EMD) provides a near-optimal approximation in practice.

Introduction

In traditional shortest-path algorithms like Dijkstra’s, the cost of every edge is known a priori. However, real-world navigation often involves uncertainty, such as road closures due to weather. The Canadian Traveller Problem (CTP) models this by treating edge costs as random variables that are only realized when a traveller reaches an endpoint. This setup introduces a classic exploration-exploitation trade-off: should one continue on a known path or deviate to explore potentially better routes?

Finding an optimal strategy for CTP is #P-hard due to the exponential growth of the state space. This research seeks to delineate the boundaries of tractability and provide robust approximation methods for general graphs.

Methodology and Graph Structures

The authors employ Markov Decision Processes (MDPs) to model the traveller's state, which comprises their current location and the set of observed edge realizations. To manage the state space explosion, they focus on specific graph classes:

  1. Directed Acyclic Graphs (DAGs): The absence of cycles simplifies the problem to $O(|E|)$ time, as backtracking—the primary source of complexity—is impossible.
  2. Disjoint-Path Graphs: These consist of multiple independent paths from source to destination. The authors develop a "parsimonious MDP" for cases where edges have binary costs (e.g., "clear" vs. "blocked"), enabling polynomial-time exact solutions.
Structure of a disjoint-path graph

The study utilizes synthetic datasets, including $n \times n$ directed grid graphs and custom disjoint-path configurations, primarily using independent and identically distributed (iid) binary edge costs.

Heuristic Strategies

Two primary heuristics are analyzed:

  • Minimum Expected Distance (MED): This "average-case" approach replaces all unknown costs with their expectations and solves for the shortest path.
  • Expected Minimum Distance (EMD): This strategy calculates the expected value of the shortest path given future realizations and moves toward the node minimizing this value.

Key Results and Performance Analysis

A significant theoretical contribution is the proof of an exponential gap between the MED heuristic and the optimal policy. MED often fails because it ignores the "option value" of uncertain paths that might turn out to be very cheap.

In contrast, experimental simulations on $50 \times 50$ grid graphs show that EMD performs remarkably well. Even when EMD is approximated via sampling, its performance remains nearly indistinguishable from the optimal policy, whereas MED's performance degrades significantly as the grid size increases.

Performance comparison of pathfinding heuristics

Conclusion

While CTP remains computationally difficult in the general case, this work provides efficient exact algorithms for DAGs and disjoint paths. The findings highlight the risks of naive "average-cost" heuristics like MED and demonstrate the practical efficacy of EMD-based strategies. Future research may extend these results to more complex topologies like Series-Parallel graphs or continuous cost distributions.

Summary updated

BibTeX
@inproceedings{nikolova2008route,
  author = {Evdokia Nikolova and David R. Karger},
  title = {{Route Planning under Uncertainty: The Canadian Traveller Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure