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.

  • News and Highlights
    • h-pom, h-roc, and i2-dual won the best paper award at ICAPS'17!
    • New efficient approach to solve SSPs and C-SSPs with dead ends (UAI'17).
    • Solving SSPs and MDPs with PCTL* constraints to appear on TABLEAUX'17.
    • h-pom and h-roc: the first heuristics able to handle probabilities and costs for SSPs and C-SSPs (ICAPS'17).
    • i-dual won the best paper award at ICAPS'16!
    • QTM won the best paper award from the AI committee of TRB'16! (demo).
    • i-dual: combining AI and OR to efficiently solve constrained SSPs (ICAPS'16).
  • Word cloud of my papers:
  • wordcloud
    large wordcloud