Shortest Path under Uncertainty: Exploration versus Exploitation

Zhan Wei Lim, David Hsu, Wee Sun Lee
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:701-710, 2017.

Abstract

In the Canadian Traveler Problem (CTP), a traveler seeks a shortest path to a destination through a road network, but unknown to the traveler, some roads may be blocked. This paper studies the Bayesian CTP (BCTP), in which road states are correlated with known prior probabilities and the traveler can in- fer the states of an unseen road from past observations of other correlated roads. As generalized shortest-path problems, CTP and BCTP have important practical applications. We show that BCTP is NP-complete and give a polynomial-time approximation algorithm, Hedged Shortest Path under Determinization (HSPD), which approximates an optimal solu- tion with a polylogarithmic factor. Preliminary experiments show promising results. HSPD outperforms a widely used greedy algorithm and a state-of-the-art UCT-based search algo- rithm for CTP, especially when significant ex- ploration is required.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-lim17a, title = {Shortest Path under Uncertainty: Exploration versus Exploitation}, author = {Lim, Zhan Wei and Hsu, David and Lee, Wee Sun}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {701--710}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/lim17a/lim17a.pdf}, url = {https://proceedings.mlr.press/r15/lim17a.html}, abstract = {In the Canadian Traveler Problem (CTP), a traveler seeks a shortest path to a destination through a road network, but unknown to the traveler, some roads may be blocked. This paper studies the Bayesian CTP (BCTP), in which road states are correlated with known prior probabilities and the traveler can in- fer the states of an unseen road from past observations of other correlated roads. As generalized shortest-path problems, CTP and BCTP have important practical applications. We show that BCTP is NP-complete and give a polynomial-time approximation algorithm, Hedged Shortest Path under Determinization (HSPD), which approximates an optimal solu- tion with a polylogarithmic factor. Preliminary experiments show promising results. HSPD outperforms a widely used greedy algorithm and a state-of-the-art UCT-based search algo- rithm for CTP, especially when significant ex- ploration is required.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Shortest Path under Uncertainty: Exploration versus Exploitation %A Zhan Wei Lim %A David Hsu %A Wee Sun Lee %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-lim17a %I PMLR %P 701--710 %U https://proceedings.mlr.press/r15/lim17a.html %V R15 %X In the Canadian Traveler Problem (CTP), a traveler seeks a shortest path to a destination through a road network, but unknown to the traveler, some roads may be blocked. This paper studies the Bayesian CTP (BCTP), in which road states are correlated with known prior probabilities and the traveler can in- fer the states of an unseen road from past observations of other correlated roads. As generalized shortest-path problems, CTP and BCTP have important practical applications. We show that BCTP is NP-complete and give a polynomial-time approximation algorithm, Hedged Shortest Path under Determinization (HSPD), which approximates an optimal solu- tion with a polylogarithmic factor. Preliminary experiments show promising results. HSPD outperforms a widely used greedy algorithm and a state-of-the-art UCT-based search algo- rithm for CTP, especially when significant ex- ploration is required. %Z Reissued by PMLR on 04 October 2026.
APA
Lim, Z.W., Hsu, D. & Lee, W.S.. (2017). Shortest Path under Uncertainty: Exploration versus Exploitation. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:701-710 Available from https://proceedings.mlr.press/r15/lim17a.html. Reissued by PMLR on 04 October 2026.

Related Material