Robust shortest path planning and semicontractive dynamic programming
Robust shortest path planning and semicontractive dynamic programming
复制标题
DOI：
10.1002/nav.21697
复制
发表时间：
2016-08
期刊：
影响因子：
--
通讯作者：
D. Bertsekas
中科院分区：
文献类型：
--
作者：
D. Bertsekas
在本文中，我们考虑有向图中的最短路径问题，其中节点之间的过渡受到不确定性的影响。我们使用极小极大公式，其目标是保证在最不确定性的最坏情况下，以最小代价路径到达特定的目标状态。这种类型的问题出现在规划和追逐-逃避环境中，以及模型预测控制中。我们的分析使用了最近发展起来的抽象半牵引动态规划模型理论。我们研究了最优性方程解的存在唯一性问题，最优路径的存在性问题，以及在经典的值迭代和策略迭代方法之后的各种算法的有效性问题，以及非负弧长问题的Dijkstra - like算法。©2016 Wiley期刊公司海军科研后勤，2019 (6):15 - 37
In this article, we consider shortest path problems in a directed graph where the transitions between nodes are subject to uncertainty. We use a minimax formulation, where the objective is to guarantee that a special destination state is reached with a minimum cost path under the worst possible instance of the uncertainty. Problems of this type arise, among others, in planning and pursuit‐evasion contexts, and in model predictive control. Our analysis makes use of the recently developed theory of abstract semicontractive dynamic programming models. We investigate questions of existence and uniqueness of solution of the optimality equation, existence of optimal paths, and the validity of various algorithms patterned after the classical methods of value and policy iteration, as well as a Dijkstra‐like algorithm for problems with nonnegative arc lengths.© 2016 Wiley Periodicals, Inc. Naval Research Logistics 66:15–37, 2019