CG-iLAO* – Efficient Constraint Generation for Stochastic Shortest Path Problems
CG-iLAO* is a modification of the iLAO* algorithm, which is capable of using heuristics to ignore unpromising actions until they are needed. In our experiments, CG-iLAO* outperforms iLAO* and LRTDP (the state-of-the-art). To derive CG-iLAO* we view iLAO* under the lens of linear programming in a novel way, and generalise it with constraint generation. Then, we bring this algorithm back into the world of dynamic programming.
AAAI 2024 Paper [link] [poster]
This paper was accepted at AAAI 2024!
Technical Report [arxiv]
Extended version of the paper with more experimental results in the appendix.
1h Talk [pdf]
I gave this talk in Toulouse and at Uni Basel. It steps through iLAO* and CG-iLAO* on a toy problem, which might be helpful to gain some intuition.
Source Code, Benchmarks, and Data [zenodo] [github]
The code, benchmarks, and experimental results are all here. Note: the zenodo link points to the github repo.
