Efficient Solutions for Stochastic Shortest Path Problems with Dead Ends
Trevizan, F., Teichteil-Koenigsbuch, F., and Thiebaux, S.,
Proc. of 33rd Int. Conf. on Uncertainty in Artificial Intelligence (UAI)
We are working on the camera-ready of this paper and it will be available in my
website soon. Below is the abstract of this paper.
Many planning problems require maximizing the probability of goal satisfaction as well as minimizing the expected cost to reach the goal. To model and solve such problems, there has been several attempts at extending Stochastic Shortest Path problems (SSPs) to deal with dead ends and optimize a dual optimization criterion. Unfortunately these extensions lack either theoretical robustness or practical efficiency. We study a new, perhaps even more natural optimization criterion capturing 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 accurately 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 experiments show up to one order of magnitude speed-up over the state of the art.