论文标题
通过成本预算分配的分层约束随机路径计划
Hierarchical Constrained Stochastic Shortest Path Planning via Cost Budget Allocation
论文作者
论文摘要
随机的顺序决策通常需要在每个高级行动的问题中都需要通过原始状态和行动进一步计划的问题。此外，许多现实世界中的应用程序都需要一项计划，以满足二级成本（例如风险措施或燃料消耗）的限制。在本文中，我们提出了一个分层约束的随机最短路径问题（HC-SSP），该问题符合单个框架中这两个关键要求。尽管HC-SSP提供了一个有用的框架，可以在许多现实世界应用程序中建模此类计划要求，但最终的问题具有很高的复杂性，并且很难快速找到最佳解决方案，从而阻止用户将其应用于实时和风险敏感的应用程序。为了解决这个问题，我们提出了一种算法，该算法将基于分支机构和结合方案的较低级别的计划问题分配给较低级别的计划问题，以快速找到可行的解决方案，并逐步更新现有的解决方案。我们在疏散方案中演示了提出的算法，并证明了比基于数学编程的方法的优势。
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.
