Efficient solutions for Stochastic Shortest Path Problems with Dead Ends

Felipe Trevizan, Florent Teichteil-Königsbuch, Sylvie Thiebaux
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:321-330, 2017.

Abstract

Many planning problems require maximizing the probability of goal satisfaction as well as min- imizing the expected cost to reach the goal. To model and solve such problems, there have been several attempts at extending Stochastic Shortest Path problems (SSPs) to deal with dead ends and optimize a dual optimization criterion. Unfortu- nately these extensions lack either theoretical ro- bustness or practical efficiency. We study a new, perhaps more natural optimization criterion cap- turing these problems, the Min-Cost given Max- Prob (MCMP) criterion. This criterion leads to the minimum expected cost policy among those with maximum success probability, and accu- rately accounts for the cost and risk of reaching dead ends. Moreover, it lends itself to efficient solution methods that build on recent heuristic search algorithms for the dual representation of stochastic shortest paths problems. Our experi- ments show up to one order of magnitude speed- up over the state of the art.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-trevizan17a, title = {Efficient solutions for Stochastic Shortest Path Problems with Dead Ends}, author = {Trevizan, Felipe and Teichteil-K{\"o}nigsbuch, Florent and Thiebaux, Sylvie}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {321--330}, 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/trevizan17a/trevizan17a.pdf}, url = {https://proceedings.mlr.press/r15/trevizan17a.html}, abstract = {Many planning problems require maximizing the probability of goal satisfaction as well as min- imizing the expected cost to reach the goal. To model and solve such problems, there have been several attempts at extending Stochastic Shortest Path problems (SSPs) to deal with dead ends and optimize a dual optimization criterion. Unfortu- nately these extensions lack either theoretical ro- bustness or practical efficiency. We study a new, perhaps more natural optimization criterion cap- turing these problems, the Min-Cost given Max- Prob (MCMP) criterion. This criterion leads to the minimum expected cost policy among those with maximum success probability, and accu- rately accounts for the cost and risk of reaching dead ends. Moreover, it lends itself to efficient solution methods that build on recent heuristic search algorithms for the dual representation of stochastic shortest paths problems. Our experi- ments show up to one order of magnitude speed- up over the state of the art.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Efficient solutions for Stochastic Shortest Path Problems with Dead Ends %A Felipe Trevizan %A Florent Teichteil-Königsbuch %A Sylvie Thiebaux %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-trevizan17a %I PMLR %P 321--330 %U https://proceedings.mlr.press/r15/trevizan17a.html %V R15 %X Many planning problems require maximizing the probability of goal satisfaction as well as min- imizing the expected cost to reach the goal. To model and solve such problems, there have been several attempts at extending Stochastic Shortest Path problems (SSPs) to deal with dead ends and optimize a dual optimization criterion. Unfortu- nately these extensions lack either theoretical ro- bustness or practical efficiency. We study a new, perhaps more natural optimization criterion cap- turing these problems, the Min-Cost given Max- Prob (MCMP) criterion. This criterion leads to the minimum expected cost policy among those with maximum success probability, and accu- rately accounts for the cost and risk of reaching dead ends. Moreover, it lends itself to efficient solution methods that build on recent heuristic search algorithms for the dual representation of stochastic shortest paths problems. Our experi- ments show up to one order of magnitude speed- up over the state of the art. %Z Reissued by PMLR on 04 October 2026.
APA
Trevizan, F., Teichteil-Königsbuch, F. & Thiebaux, S.. (2017). Efficient solutions for Stochastic Shortest Path Problems with Dead Ends. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:321-330 Available from https://proceedings.mlr.press/r15/trevizan17a.html. Reissued by PMLR on 04 October 2026.

Related Material