Efficient Constraint Generation for Stochastic Shortest Path Problems
This work addresses computational bottlenecks in planning algorithms for SSPs, offering significant speed-ups for researchers and practitioners in AI and operations research.
The paper tackles the inefficiency in solving Stochastic Shortest Path Problems (SSPs) by introducing an efficient constraint generation technique that avoids computing costs for sub-optimal actions, resulting in CG-iLAO* ignoring up to 57% of actions and solving problems up to 8x and 3x faster than existing methods.
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*.