Trevizan, FelipeThiébaux, SylvieSantana, PedroWilliams, Brian2025-12-172025-12-172334-0835https://hdl.handle.net/1885/733795920We consider the problem of generating optimal stochastic policies for Constrained Stochastic Shortest Path problems, which are a natural model for planning under uncertainty for resourcebounded 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 enable i-dual to achieve up to two orders of magnitude improvement in run-time and memory over linear programming algorithms.This research was partially funded by AFOSR grant FA2386-15-1-4015 and NICTA. NICTA is funded by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Centre of Excellence Program. We would also like to thank Patrik Haslum for fruitful discussions which helped to improve this paper, and the anonymous reviewers for their constructive and helpful comments.9enPublisher Copyright: Copyright © 2016, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.201684989811775