# Efficient Constraint Generation for Stochastic Shortest Path Problems

arXiv: https://arxiv.org/abs/2401.14636 · HTML: https://mlsanity.com/paper/2401.14636/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 54 references that are in the map.
- First posted on arXiv 26 Jan 2024.

## Builds on (most cited first, 4 of 4)

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Verification of Markov Decision Processes using Learning Algorithms](https://mlsanity.com/paper/1402.2967/) (2014)
- [Topological Value Iteration Algorithms](https://mlsanity.com/paper/1401.3910/) (2014)
- [On the Computational Complexity of Multi-Agent Pathfinding on Directed Graphs](https://mlsanity.com/paper/1911.04871/) (2019)

## Abstract (arXiv)

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*.