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.

翻译：此外,许多实际应用要求有一个能满足风险计量或燃料消耗等次级成本限制的计划。我们在本文件中提出一个等级限制和随机性最短路径问题(HC-SSP),在单一框架内满足这两个关键要求。虽然HC-SSP提供了一个有用的框架,用以在许多现实世界应用中模拟这种规划要求,但由此产生的问题非常复杂,难以找到最佳解决办法,使用户无法将它应用到实时和风险敏感应用中。为了解决这一问题,我们提出一种计算法,根据分支和边际计划,将成本预算反复分配给较低水平的规划问题,以便找到一个可行的解决办法,迅速和逐步更新现有解决办法。我们展示了在撤离情景中拟议的算法,并证明在基于国家数学规划方法的优势。