@inproceedings {icaps16-71,
    track    = {​Main Track},
    title    = {Heuristic Search in Dual Space for Constrained Stochastic Shortest Path Problems},
    url      = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13179},
    author   = {Felipe Trevizan and  Sylvie Thiebaux and  Pedro Santana and  Brian Williams},
    abstract = {We consider the problem of generating optimal stochastic policies for Constrained Stochastic Shortest Path problems, which are a natural model for planning under uncertainty for resource-bounded agents with multiple competing objectives. While unconstrained SSPs enjoy a multitude of efficient heuristic search solution methods with the ability to focus on promising areas reachable from the initial state, the state of the art for constrained SSPs revolves around linear and dynamic programming algorithms which explore the entire state space. In this paper, we present i-dual, which, to the best of our knowledge, is the first heuristic search algorithm for constrained SSPs. To concisely represent constraints and efficiently decide their violation, i-dual operates in the space of dual variables describing the policy occupation measures. It does so while retaining the ability to use standard value function heuristics computed by well-known methods. Our experiments on a suite of PPDDL problems augmented with constraints show that these features enables i-dual to achieve significant run-time improvements over linear programming algorithms.},
    keywords = {Probabilistic planning; MDPs and POMDPs}
}

{"_id":"ENs9oharuYyuZwyh7","bibbaseid":"trevizan-thiebaux-santana-williams-heuristicsearchindualspaceforconstrainedstochasticshortestpathproblems","downloads":0,"creationDate":"2016-03-09T03:04:32.960Z","title":"Heuristic Search in Dual Space for Constrained Stochastic Shortest Path Problems","author_short":["Trevizan, F.","Thiebaux, S.","Santana, P.","Williams, B."],"year":null,"bibtype":"inproceedings","biburl":"icaps16.icaps-conference.org/papers.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","track":"​Main Track","title":"Heuristic Search in Dual Space for Constrained Stochastic Shortest Path Problems","url":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13179","author":[{"firstnames":["Felipe"],"propositions":[],"lastnames":["Trevizan"],"suffixes":[]},{"firstnames":["Sylvie"],"propositions":[],"lastnames":["Thiebaux"],"suffixes":[]},{"firstnames":["Pedro"],"propositions":[],"lastnames":["Santana"],"suffixes":[]},{"firstnames":["Brian"],"propositions":[],"lastnames":["Williams"],"suffixes":[]}],"abstract":"We consider the problem of generating optimal stochastic policies for Constrained Stochastic Shortest Path problems, which are a natural model for planning under uncertainty for resource-bounded agents with multiple competing objectives. While unconstrained SSPs enjoy a multitude of efficient heuristic search solution methods with the ability to focus on promising areas reachable from the initial state, the state of the art for constrained SSPs revolves around linear and dynamic programming algorithms which explore the entire state space. In this paper, we present i-dual, which, to the best of our knowledge, is the first heuristic search algorithm for constrained SSPs. To concisely represent constraints and efficiently decide their violation, i-dual operates in the space of dual variables describing the policy occupation measures. It does so while retaining the ability to use standard value function heuristics computed by well-known methods. Our experiments on a suite of PPDDL problems augmented with constraints show that these features enables i-dual to achieve significant run-time improvements over linear programming algorithms.","keywords":"Probabilistic planning; MDPs and POMDPs","bibtex":"@inproceedings {icaps16-71,\r\n track = {​Main Track},\r\n title = {Heuristic Search in Dual Space for Constrained Stochastic Shortest Path Problems},\r\n url = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13179},\r\n author = {Felipe Trevizan and Sylvie Thiebaux and Pedro Santana and Brian Williams},\r\n abstract = {We consider the problem of generating optimal stochastic policies for Constrained Stochastic Shortest Path problems, which are a natural model for planning under uncertainty for resource-bounded agents with multiple competing objectives. While unconstrained SSPs enjoy a multitude of efficient heuristic search solution methods with the ability to focus on promising areas reachable from the initial state, the state of the art for constrained SSPs revolves around linear and dynamic programming algorithms which explore the entire state space. In this paper, we present i-dual, which, to the best of our knowledge, is the first heuristic search algorithm for constrained SSPs. To concisely represent constraints and efficiently decide their violation, i-dual operates in the space of dual variables describing the policy occupation measures. It does so while retaining the ability to use standard value function heuristics computed by well-known methods. Our experiments on a suite of PPDDL problems augmented with constraints show that these features enables i-dual to achieve significant run-time improvements over linear programming algorithms.},\r\n keywords = {Probabilistic planning; MDPs and POMDPs}\r\n}\r\n\r\n","author_short":["Trevizan, F.","Thiebaux, S.","Santana, P.","Williams, B."],"key":"icaps16-71","id":"icaps16-71","bibbaseid":"trevizan-thiebaux-santana-williams-heuristicsearchindualspaceforconstrainedstochasticshortestpathproblems","role":"author","urls":{"Paper":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13179"},"keyword":["Probabilistic planning; MDPs and POMDPs"],"metadata":{"authorlinks":{}}},"search_terms":["heuristic","search","dual","space","constrained","stochastic","shortest","path","problems","trevizan","thiebaux","santana","williams"],"keywords":["probabilistic planning; mdps and pomdps"],"authorIDs":[],"dataSources":["iMkx859KiXcegwsin","EZtZjCTnxcdTTyeij"]}