Efficient solutions for stochastic shortest path problems with dead ends
Date
2017
Authors
W. Trevizan, Felipe
Teichteil-Konigsbuch, Florent
Thiebaux, Sylvie
Journal Title
Journal ISSN
Volume Title
Publisher
AUAI Press
Abstract
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 have 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 more natural optimization criterion capturing
these problems, the Min-Cost given MaxProb
(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
Description
Keywords
Citation
Collections
Source
Uncertainty in Artificial Intelligence - Proceedings of the 33rd Conference, UAI 2017
Type
Conference paper
Book Title
Entity type
Access Statement
License Rights
DOI
Restricted until
2099-12-31