Hierarchical Constrained Stochastic Shortest Path Planning via Cost Budget Allocation
This addresses planning in real-time, risk-sensitive applications like evacuation, but appears incremental as it builds on existing hierarchical and constrained frameworks.
The paper tackles the problem of hierarchical constrained stochastic shortest path planning, which is complex and slow for real-time use, by proposing an algorithm that iteratively allocates cost budgets to find feasible solutions quickly. It demonstrates advantages over a state-of-the-art approach in an evacuation scenario, though no specific numerical results are provided.
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.