May, 2022

通过成本预算分配的层次约束随机最短路径规划

PDF
TL;DR该论文提出了一种使用分层规划展开的基于成本约束的随机最短路径问题（HC-SSP）的框架，通过分支和剪枝算法来迭代地分配成本预算，从而在真实时间和风险敏感的应用中找到一个可行解。
stochastichierarchical planningconstrained shortest pathrisk-sensitive applicationsbranch-and-bound algorithm
发现论文，激发创造
  • 用于自主车辆行为规划的概率约束随机最短路径双重描述

    本文介绍了一个基于约束的随机规划问题，其中利用整数线性规划方法确保了确定性决策，同时为安全性关键的应用提供了约束违规概率的上界。同时还介绍了确定性策略和随机策略的随机舍入过程，并探讨了如何在考虑不同时间步的约束情况下进行 CC-SSP 的推广。

    Feb, 2023

  • 随机最短路径问题的高效约束生成

    利用规划和运筹学的新框架，解决了随机最短路径问题中冗余计算的问题，提出了一种有效的约束生成技术，应用到了新算法 CG-iLAO*，实验证明 CG-iLAO * 相较于 LRTDP 和 iLAO * 在解决问题时速度提高了 8 倍和 3 倍，并忽略了 iLAO * 的多达 57% 的动作。

    Jan, 2024

  • 固定时限约束随机最短路问题在局部转移下的全多项式时间逼近方案

    本文提出了一个在局部转换下的全多项式近似方案，可用于计算最优确定性策略，以解决 (C) C-SSP 问题，其中固定阈值限制随机最短路径问题是在一定操作限制下的规划形式，当限制违反时，这种 CC-SSP 变体允许边界概率，而 SSP 问题的状态可达性呈现出一定的局部性，并且在此情况下，只有一定数量的状态可以共享一些后续状态。

    Apr, 2022

  • 带有对手可变成本的随机最短路径

    本文提出了对抗性 SSP 模型，包含时间上对成本的不良变化和未知转移，其开发了第一个对抗性 SSP 算法，并证明了高概率的回报上限。

    Jun, 2020

  • 多目标概率规划的启发式搜索

    本篇论文旨在将启发式搜索算法应用于多目标随机最短路径 (MOSSPs) 问题，提出了基于相对快速的 MOLAO* 和 MOLRTDP 两种算法，以及一系列能够应对随机、多目标特点的启发式函数，通过实验证明了新算法及函数的有效性。

    Mar, 2023

  • 随机最短路径的隐式有限时间近似和有效最优算法

    该研究利用隐式有限时间近似技术，提出一种通用的模板，用于开发 Stochastic Shortest Path 模型中的情感极小化算法，并且开发了两个新算法，一个是无模型算法，一个是基于模型的算法。这两个算法具有高度稀疏更新，比所有现有算法的计算效率更高，并且都可以实现完全无参数。

    Jun, 2021

  • 随机最短路径的近最优遗憾边界

    本文介绍了一种解决随机最短路径问题的算法，其中代理必须通过在有限次数的游戏中获得最佳策略，从而在最短期望代价下达到目标状态。通过探究悔恨最小化和最小瞬时代价的根号反比关系，本文提出了一种不依赖于最小代价的算法，并展示了任何学习算法在最坏情况下都要有至少 Omega（Bstar 根号乘以 S、A、K 的数量）的悔恨。

    Feb, 2020

  • 随机最短路径问题的变体

    本文介绍了关于随机最短路径问题的算法和策略，提供多种保证路径长度分布，而不仅是期望值最小的解决方案，并对最近在马尔科夫决策过程的研究成果进行了应用。

    Nov, 2014

  • 基于风险的随机最短路径

    本研究针对马尔科夫决策过程中随机最短路径问题提出了一种基于条件风险价值优化的风险感知控制方法，并通过线性规划和价值迭代两种算法实现了精确而可靠的解决方案。实验结果表明该方法在多个中等规模的问题实例上是可行的。

    Mar, 2022

  • 权重受限最短路径问题增强方法：约束路径搜索与双目标搜索相遇

    本文研究基于 A * 算法和双目标搜索的两种解决方案，解决只有一个约束条件的成本最小路径规划问题，并研究在约束搜索中优先队列的重要性。实验证明，不带打结断的桶队列可以有效提高双目标搜索的算法性能。

    Jul, 2022