Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a constraint generation technique for Stochastic Shortest Path Problems (SSPs) that avoids computing costs-to-go for provably sub-optimal actions during Bellman backups. By establishing connections between planning and operations research, the authors formulate SSP solving as an iterative constraint satisfaction problem. The resulting CG-iLAO* algorithm achieves speedups of up to 8x and 3x compared to LRTDP and iLAO*, respectively, by ignoring up to 57% of actions considered by iLAO*.
Stop wasting compute on provably bad actions: constraint generation slashes computation in stochastic shortest path problems by up to 57%.
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*.