Canadian traveller problem

In computer science and graph theory, the Canadian traveller problem is a generalization of the shortest path problem to graphs where the cost of traversing an edge isn't completely known until reaching it. The problem was introduced by Papadimitriou and Yannakakis in 1989 and many variants of the problem has been studied since. The name supposedly originates from conversations of the authors who learned of the difficulty Canadian drivers had with certain roads randomly being closed due snowfall. Variants of the problem is studied in various fields but the original problem hasn't been the topic of many papers since its publication.

Definition

As mentioned above, many variants have been considered. We here define the original problem, as was studied in the paper from 1989. It is necessary that we begin by introducing certain terms.

Consider a family of undirected graphs that can construct by adding a set of given edges to a given graph. Formally, let $mathcal\{G\}(V,E,F)\; =\; \{(V,E+F\text{'})\; |\; F\text{'}\; subseteq\; F\},\; E\; cap\; F\; =\; emptyset$. We say that $G\; in\; mathcal\{G\}(V,E,F)$ is a "realization" of the graph family. Furthermore, let W be an associated cost matrix where $w\_\{ij\}$ is the cost of going from vertex "i" to vertex "j", assuming that this edge is in the realization.

For any vertex "v" in "V", we call $E\_B(v,V)$ its adjacent edges with respect to the edge set "B" on "V". Let furthermore, for a realization "G", $d\_B(s,t)$ be the cost of the shortest path in the graph from "s" to "t". This is called the off-line problem because an algorithm for such a problem would have complete information of the graph.

We say that a strategy $pi$ to navigate such a graph is a mapping from $(mathcal\{P\}(E),mathcal\{P\}(F),V)$ to "E", where $mathcal\{P\}(X)$ denotes the powerset of "X". We define the cost $c(pi,\; B)$ of a strategy $pi$ with respect to a particular realization $G\; =\; (V,B)$ as follows.
* Let $v\_0\; =\; s,\; E\_0\; =\; E$ and $F\_0\; =\; F$.
* For $i\; =\; 0,\; 1,\; 2,\; ...$, define
** $E\_\{i+1\}\; =\; E\_i\; cup\; E\_B(v\_i,V)$,
** $F\_\{i+1\}\; =\; F\_i\; -\; E\_F(v\_i,V)$, and
** $v\_\{i+1\}\; =\; pi(E\_\{i+1\},\; F\_\{i+1\},\; v\_i)$.
* If there exists a "T" such that $v\_T\; =\; t$, then $c(pi,\; B)\; =\; sum\_\{i=0\}^\{T-1\}\; w\_\{v\_i,v\_\{i+1$, otherwise let $c(pi,\; B)\; =\; infty$.

In other words, we evaluate the policy based on the edges we currently know are in the graph ($E\_i$) and the edges we known might be in the graph ($F\_i$). When we take a step in the graph, the edges adjacent to our new location become known to us. Those edges that are in the graph are added to $E\_i$, and regardless of whether the edges are in or not, they are removed from the set of unknown edges $F\_i$. If the goal is never reached, we say that we have an infinite cost. If the goal is reached, we define the cost of the walk as the sum of the costs of all of the edges traversed, some possibly more than once.

Finally, we define the problem as: Given an instance $(V,E,F,s,t,r)$, decide whether there exists a policy $pi$ such that for every realization $(V,B)\; in\; mathcal\{G\}(V,E,F)$, the cost $c(pi,\; B)$ of the policy is no more than "r" times the off-line optimal, $d\_B(s,\; t)$. In the case $c(pi,\; B)\; =\; d\_b(s,t)\; =\; infty$, we let the answer be "yes" iff $r\; geq\; 1$.

Papadimitriou and Yannakakis noted that this defines a two-player game, where the players compete over the cost of their respective paths and the edge set is chosen by the second player (nature).

Complexity

The original paper analysed the complexity of the problem and reported it to be PSPACE-complete. It was also shown that computing the minimum ratio is #P-hard. [Papadimitriou and Yannakakis, 1982, p. 148]

Applications

The problem is said to have applications in operations research, transportation planning, artificial intelligence, and machine learning. A variant of the problem has been studied for robot navigation with probabilistic landmark recognition.cite journal | author = Amy J. Briggs | coauthors="Carrick Detweiler, Daniel Scharstein | title="Expected shortest paths for landmark-based robot navigation" | journal = "International Journal of Robotics Research" | year=2004 | volume=23 | pages=717-718 ]

Open Problems

Despite the age of the problem and its many potential applications, many natural questions still remain open. Is there a constant-factor approximation or is the problem APX-hard? An even more fundamental question has been left unanswered - is there a polynomial-size "description" of an optimal policy, setting aside for a moment the time to compute? [Karger and Nikolova, 2008, p. 1]

ee Also

*Shortest path problem

Notes

References

*
*