High-Quality Policies for the Canadian Traveler's Problem

Patrick Eyerich, Thomas Keller, Malte HelmertAAAI 2010 · DOI

Abstract

The Canadian Traveler’s Problem (CTP) is a fundamental path-planning challenge where road availability is uncertain until observed locally. While traditional approaches rely on "optimistic" shortest-path heuristics, they often fail to account for the true cost of uncertainty. This paper introduces Optimistic UCT (UCTO), a variant of Monte Carlo Tree Search, which theoretically converges to the global optimum. Empirical evaluations on Delaunay graphs demonstrate that UCTO outperforms standard methods by up to 19% while maintaining real-time decision-making efficiency.

Introduction

The Canadian Traveler’s Problem (CTP) models navigation in environments with stochastic edge blockages. An agent must travel from a source to a destination, discovering whether a road is passable only upon reaching an adjacent vertex. Once a road is confirmed blocked, it remains so for the duration of the trip. The objective is to find a policy that minimizes the expected total travel cost.

Historically, the Optimistic Policy (OMT) has been the standard baseline. OMT always follows the shortest path to the goal, assuming all unobserved edges are open. While computationally efficient, this "blind optimism" ignores the value of information and can lead to significant detours when critical paths are found to be blocked late in the journey.

Algorithmic Approaches

To address the limitations of OMT, several probabilistic strategies are evaluated:

  1. Hindsight Optimization (HOP): Samples multiple "weather" scenarios (edge configurations) and averages the costs of clairvoyant shortest paths for each.
  2. Optimistic Rollout (ORO): Simulates the performance of the OMT policy across sampled scenarios to estimate expected costs.
  3. Optimistic UCT (UCTO): Adapts the Upper Confidence bounds applied to Trees (UCT) algorithm. By initializing the search tree with optimistic cost estimates, UCTO focuses exploration on promising regions of the map, accelerating convergence toward the optimal policy.

Key Insights and Convergence

A core theoretical contribution of this work is the establishment of a cost hierarchy: $$Cost_{Optimistic} \le Cost_{Hindsight} \le Cost_{Optimal} \le Cost_{OptimisticRollout}$$ While OMT provides a lower bound, it is often far from the true optimal cost. Unlike heuristic methods like HOP or ORO, UCT is mathematically guaranteed to converge to the global optimum ($Cost_{Optimal}$) as the number of simulations increases.

Convergence of average path length for different algorithms as the number of rollouts increases.

As shown in the figure above, "blind" UCT (UCTB) initially performs poorly due to random exploration. However, by seeding the search with optimistic estimates, UCTO achieves superior performance much faster, eventually surpassing all other heuristics.

Experimental Results

The algorithms were tested on Delaunay graphs of varying scales: small (20 nodes), medium (50 nodes), and large (100 nodes).

Performance comparison of OMT, HOP, ORO, UCTB, and UCTO across small (20), medium (50), and large (100) Delaunay graphs.

The experimental data reveals that UCTO consistently achieves the lowest average travel costs ($\varnothing C$). On the largest benchmarks, UCTO reduced costs by approximately 17% to 19% compared to the OMT baseline. Furthermore, UCTO remains computationally viable for real-time applications; even on 100-node maps, the average decision time ($\varnothing T_{dec}$) was under 3 seconds.

In additional benchmarks involving "Remote Sensing"—where agents can pay to check road status from afar—UCTO's movement-only policy outperformed specialized sensing-aware algorithms. This suggests that superior path-planning logic can be more effective than acquiring additional environmental data at a cost.

Conclusion

This research demonstrates that explicitly reasoning about uncertainty through Monte Carlo Tree Search significantly improves outcomes in the Canadian Traveler’s Problem. UCTO provides a powerful balance between theoretical optimality and practical efficiency. Future work may explore scaling these methods to continental-sized road networks through hierarchical decomposition and investigating dynamic environments where road statuses change over time.

Summary updated

BibTeX
@inproceedings{eyerich2010high,
  author = {Patrick Eyerich and Thomas Keller and Malte Helmert},
  title = {{High-Quality Policies for the Canadian Traveler's Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7542},
}
Figure