Current methods for solving Stochastic Shortest Path Problems (SSPs) find
states' costs-to-go by applying Bellman backups, where state-of-the-art methods
employ heuristics to select states to back up and prune. A fundamental
limitation of these algorithms is their need to compute the cost-to-go for
every applicable action during each state backup, leading to unnecessary
computation for actions identified as sub-optimal. We present new connections
between planning and operations research and, using this framework, we address
this issue of unnecessary computation by introducing an efficient version of
constraint generation for SSPs. This technique allows algorithms to ignore
sub-optimal actions and avoid computing their costs-to-go. We also apply our
novel technique to iLAO* resulting in a new algorithm, CG-iLAO*. Our
experiments show that CG-iLAO* ignores up to 57% of iLAO*'s actions and it
solves problems up to 8x and 3x faster than LRTDP and iLAO*.

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