Stochastic Shortest Path Problem with Failure Probability

📄 arXiv: 2409.16672v1 📥 PDF

作者: Ritsusamuel Otsubo

分类: math.OC, eess.SY

发布日期: 2024-09-25

备注: 22 pages, 5 figure

💡 一句话要点

提出基于失效概率的随机最短路径问题求解方法，应用于机器人运动规划。

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 随机最短路径 失效概率 贝叶斯马尔可夫决策过程 双人零和博弈 机器人运动规划

📋 核心要点

  1. 传统随机最短路径问题难以处理任务存在失败概率的序贯决策问题，导致策略过于保守。
  2. 通过引入死胡同概念，并将问题转化为贝叶斯马尔可夫决策过程和双人零和博弈求解。
  3. 实验表明，该方法在机器人运动规划中有效，能够找到满足失败概率阈值的更优策略。

📝 摘要（中文）

本文解决了一个考虑任务失败概率的不确定性序贯决策问题。标准的随机最短路径问题无法处理此类问题。本文通过引入死胡同来解决这个问题。传统方法通常只考虑最小化任务失败概率的策略，因此构建的最优策略可能过于保守。本文通过将搜索范围扩展到一类失败概率低于期望阈值的策略来解决这个问题。该问题可以通过将其视为贝叶斯马尔可夫决策过程和双人零和博弈的框架来解决。此外，最优策略可以表示为确定性策略集合上的概率分布。最后，通过将其应用于移动机器人避障运动规划问题，验证了所提出方法的有效性。

🔬 方法详解

问题定义：论文旨在解决在序贯决策过程中，任务存在失败概率的情况下，如何找到最优策略的问题。传统的随机最短路径问题（Stochastic Shortest Path, SSP）无法直接处理这种情况，因为它通常假设任务总是能够完成。现有方法为了避免失败，往往会采取过于保守的策略，导致整体性能下降。

核心思路：论文的核心思路是将任务失败视为一种状态转移到“死胡同”状态的过程。通过允许策略有一定的失败概率（但低于设定的阈值），从而扩展了策略搜索空间，避免了过于保守的策略。同时，将问题建模为贝叶斯马尔可夫决策过程（Bayesian Markov Decision Process, BMDP）和双人零和博弈，利用博弈论的方法来寻找最优策略。

技术框架：整体框架包含以下几个关键步骤：1) 将原始问题建模为带有死胡同的马尔可夫决策过程；2) 将该MDP转化为贝叶斯MDP，以处理不确定性；3) 将贝叶斯MDP转化为一个双人零和博弈，其中一个玩家试图最小化成本，另一个玩家试图最大化失败概率；4) 通过求解该博弈，得到最优策略，该策略表现为确定性策略集合上的概率分布。

关键创新：论文的关键创新在于：1) 显式地考虑了任务失败概率，并将其纳入到决策过程中；2) 将问题转化为贝叶斯MDP和双人零和博弈，从而可以使用博弈论的方法来求解；3) 允许策略有一定的失败概率，从而避免了过于保守的策略。与传统方法相比，该方法能够找到在满足失败概率约束下的更优策略。

关键设计：论文中，失败概率阈值的设定至关重要，它决定了策略搜索空间的范围。此外，在求解双人零和博弈时，需要选择合适的算法，例如线性规划或值迭代等。最优策略最终表示为一组确定性策略的概率分布，需要根据具体问题选择合适的策略表示方法和概率分布形式。

📊 实验亮点

论文通过在机器人运动规划问题上的实验，验证了所提出方法的有效性。实验结果表明，与传统的保守策略相比，该方法能够在满足失败概率约束的前提下，找到更短的路径和更快的速度。具体的性能提升数据在摘要和论文中未明确给出，属于未知信息。

🎯 应用场景

该研究成果可应用于机器人导航、自动驾驶、资源分配等领域。在这些领域中，任务的成功与否存在不确定性，且失败可能导致严重后果。通过允许一定程度的失败风险，可以提高任务的完成效率和整体性能。例如，在机器人导航中，可以允许机器人以较小的概率撞到障碍物，从而更快地到达目标地点。

📄 摘要（原文）

We solve a sequential decision-making problem under uncertainty that takes into account the failure probability of a task. This problem cannot be handled by the stochastic shortest path problem, which is the standard model for sequential decision-making. This problem is addressed by introducing dead-ends. Conventionally, we only consider policies that minimize the probability of task failure, so the optimal policy constructed could be overly conservative. In this paper, we address this issue by expanding the search range to a class of policies whose failure probability is less than a desired threshold. This problem can be solved by treating it as a framework of a Bayesian Markov decision process and a two-person zero-sum game. Also, it can be seen that the optimal policy is expressed in the form of a probability distribution on a set of deterministic policies. We also demonstrate the effectiveness of the proposed methods by applying them to a motion planning problem with obstacle avoidance for a moving robot.