Summary
Imagine trying to find the shortest way on a map where some roads might unexpectedly be blocked, and you only find out the blockage once you reach that spot. The authors study this problem on grid-like maps where every road is the same length. They show that it's possible to plan a route that isn't too much longer than an ideal route that already knows which roads are blocked, achieving a travel distance that grows with the square root of the number of blockages. They also prove this is the best possible performance in this setting and that if the map or road lengths are different, planning becomes much harder.
What this means in practice
- •For robotics navigation teams: Design routing algorithms for robots moving on grid-like warehouses with unknown blocked paths improving navigation efficiency under uncertainty.
- •For urban traffic control teams: Develop traffic routing strategies on grid-patterned city maps to better handle unexpected road closures discovered during travel.
A theory result. No direct application yet.
Authors
Pierre Bergé, Vsevolod Chernyshev, Malory Marin, Alexey Pyrko, Lou Salaün
Abstract
We study the $k$-Canadian Traveller Problem (k-ctp), an online navigation problem introduced by Papadimitriou and Yannakakis in 1991. Given an undirected weighted graph $G=(V,E,ω)$ and two vertices $s,t\in V$, a traveller aims at navigating from $s$ to $t$ while minimizing the total distance travelled. However, up to $k$ edges of the graph may be blocked, and the traveller discovers that an edge is blocked only upon reaching one of its endpoints. The performance of an online algorithm for k-ctp is measured with the competitive ratio, which is the quotient between the distance actually traversed and the distance traversed by an omniscient traveller who knows all blockages in advance. A general lower bound $2k+1$ for the competitive ratio of deterministic algorithms remains valid even when the input graph is series-parallel, whereas constant competitive ratios can be achieved on restricted graph classes, such as cycles or unit-weighted outerplanar graphs. In this paper, we establish the first intermediate competitive ratio between constant and linear regimes. We prove that, on unit-weighted solid grid graphs, there exists an online algorithm with competitive ratio $O(\sqrt{k})$. This ratio is asymptotically tight and cannot be defeated, even on unit-weighted square grids. Finally, we show that both the unit-weighted and solidity assumptions are essential: going further with arbitrary edge weights (even on square grids) or non-solid unit-weighted grid structures yields a linear lower bound of $Ω(k)$.