# Canadian Traveller Problem with Predictions

arXiv: https://arxiv.org/abs/2209.11100 · HTML: https://mlsanity.com/paper/2209.11100/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Sep 2022.

## Built on by (most cited first, 3 of 3)

- [Learning-augmented smooth integer programs with PAC-learnable oracles](https://mlsanity.com/paper/2602.02505/) (2026)
- [Dynamic UGV-UAV Cooperative Path Planning in Uncertain Environments](https://mlsanity.com/paper/2604.25267/) (2026)
- [Scout-Assisted Planning for Heterogeneous Robot Teams under Partially Known Environments](https://mlsanity.com/paper/2605.22693/) (2026)

## Abstract (arXiv)

In this work, we consider the k-Canadian Traveller Problem (k-CTP) under the learning-augmented framework proposed by Lykouris & Vassilvitskii. k-CTP is a generalization of the shortest path problem, and involves a traveller who knows the entire graph in advance and wishes to find the shortest route from a source vertex s to a destination vertex t, but discovers online that some edges (up to k) are blocked once reaching them. A potentially imperfect predictor gives us the number and the locations of the blocked edges. We present a deterministic and a randomized online algorithm for the learning-augmented k-CTP that achieve a tradeoff between consistency (quality of the solution when the prediction is correct) and robustness (quality of the solution when there are errors in the prediction). Moreover, we prove a matching lower bound for the deterministic case establishing that the tradeoff between consistency and robustness is optimal, and show a lower bound for the randomized algorithm. Finally, we prove several deterministic and randomized lower bounds on the competitive ratio of k-CTP depending on the prediction error, and complement them, in most cases, with matching upper bounds.