.png){kind=icon}
返回
Efficient Constraint Generation for Stochastic Shortest Path Problems
.png){kind=icon}
PRE
AI
DOI：10.1016/j.artint.2026.104505.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
随机最短路径问题（SSPs）传统上通过应用贝尔曼备份来计算每个状态的成本至终值。贝尔曼备份通过遍历所有适用的动作，计算应用每个动作后的成本至终值，并选择最小动作的成本至终值来更新一个状态的成本至终值。最先进的算法使用启发式函数；这些函数提供成本至终值的初始估计，并让算法仅对具有低估计成本至终值的潜在状态应用贝尔曼备份。然而，每个贝尔曼备份仍然考虑所有适用的动作，即使启发式函数告诉我们其中一些动作成本过高，其效果是这些算法在无益动作上浪费时间。为解决这一差距，我们提出了一种技术，利用启发式函数避免昂贵动作，通过将启发式搜索重新表述为线性规划，并为SSPs引入了一种高效的约束生成实现。我们提出了CG-iLAO*，一种新的算法，它采用我们的新技术改进iLAO*，并在许多问题上仅考虑iLAO*动作的40%，在某些情况下甚至低至1%。因此，CG-iLAO*平均计算的动作成本至终值比最先进的iLAO*和LRTDP少3.5倍，使其能够分别平均快2.8倍和3.7倍地解决问题。
Keyword:
Stochastic Shortest Path
Heuristic Search
Linear Programming
Constraint Generation
Bellman Backup
