  Stochastic sequential decision making often requires hierarchical structure
in the problem where each high-level action should be further planned with
primitive states and actions. In addition, many real-world applications require
a plan that satisfies constraints on the secondary costs such as risk measure
or fuel consumption. In this paper, we propose a hierarchical constrained
stochastic shortest path problem (HC-SSP) that meets those two crucial
requirements in a single framework. Although HC-SSP provides a useful framework
to model such planning requirements in many real-world applications, the
resulting problem has high complexity and makes it difficult to find an optimal
solution fast which prevents user from applying it to real-time and
risk-sensitive applications. To address this problem, we present an algorithm
that iteratively allocates cost budget to lower level planning problems based
on branch-and-bound scheme to find a feasible solution fast and incrementally
update the incumbent solution. We demonstrate the proposed algorithm in an
evacuation scenario and prove the advantage over a state-of-the-art
mathematical programming based approach.
