用启发式方法高效剪枝，让最短路径搜索快3倍以上
Efficient Constraint Generation for Stochastic Shortest Path Problems
- 将启发式搜索转为线性规划，动态生成约束避开高成本动作
- 相比iLAO*减少40%动作计算，部分问题仅需1%动作评估
- 适合需要快速求解的强化学习与路径规划场景
随机最短路径问题（SSPs）传统上通过贝尔曼备份计算每个状态的代价至终值。标准算法使用启发式函数对代价进行预估，并仅对估计代价较低的状态执行贝尔曼备份，从而提升效率。然而，每次备份仍需遍历所有可行动作，即使某些动作已被启发式判断为过贵，导致计算浪费。为此，本文提出一种基于线性规划的约束生成技术，利用启发式信息主动排除高成本动作。我们设计了新算法CG-iLAO*，在多个问题上仅需iLAO* 40%的动作评估，部分问题低至1%。平均而言，该算法比iLAO*和LRTDP少计算3.5倍动作代价，使求解速度分别提升2.8倍和3.7倍。
原文摘要 · Abstract (English)
Stochastic Shortest Path problems (SSPs) are traditionally solved by computing each state's cost-to-go by applying Bellman backups. A Bellman backup updates a state's cost-to-go by iterating through every applicable action, computing the cost-to-go after applying each one, and selecting a minimal action's cost-to-go. State-of-the-art algorithms use heuristic functions; these give an initial estimate of costs-to-go, and lets the algorithm apply Bellman backups only to promising states, determined by low estimated costs-to-go. However, each Bellman backup still considers all applicable actions, even if the heuristic tells us that some of these actions are too expensive, with the effect that such algorithms waste time on unhelpful actions. To address this gap we present a technique that uses the heuristic to avoid expensive actions, by reframing heuristic search in terms of linear programming and introducing an efficient implementation of constraint generation for SSPs. We present CG-iLAO*, a new algorithm that adapts iLAO* with our novel technique, and considers only 40% of iLAO*'s actions on many problems, and as few as 1% on some. Consequently, CG-iLAO* computes on average 3.5x fewer costs-to-go for actions than the state-of-the-art iLAO* and LRTDP, enabling it to solve problems faster an average of 2.8x and 3.7x faster, respectively.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。