# Hierarchical Constrained Stochastic Shortest Path Planning via Cost Budget Allocation

arXiv: https://arxiv.org/abs/2205.05228 · HTML: https://mlsanity.com/paper/2205.05228/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 22 references that are in the map.
- First posted on arXiv 11 May 2022.

## Builds on (most cited first, 1 of 1)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)

## Abstract (arXiv)

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.