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 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, 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 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