GapMin is a flat POMDP solver that provides lower and upper bounds on the optimal value. In many cases, the bounds are fairly tight in the sense that they match for the first three significant digits.
Closing the Gap: Improved Bounds on Optimal POMDP Solutions Pascal Poupart, Kee-Eung Kim and Dongho Kim
International Conference on Automated Planning and Scheduling (ICAPS), Freiburg, Germany, 2011.
[paper.pdf]
Symbolic Perseus
Author: Pascal Poupart
Symbolic Perseus is a point-based value iteration algorithm that uses Algebraic
Decision Diagrams (ADDs) as the underlying data structure to tackle large factored POMDPs. The original Perseus
algorithm is a point-based value iteration algorithm developed by Matthijs Spaan and Nikos Vlassis for flat POMDPs.
To be notified about releases, send me an email (ppoupart [at] cs [dot] uwaterloo [dot] ca). If you find a bug or have comments/suggestions to improve the code, please do not hesitate to contact me.
The best reference for symbolic Perseus is Chapter 5 of my PhD thesis:
Exploiting Structure to Efficiently Solve Large Scale Partially Observable Markov Decision Processes Pascal Poupart
Ph.D. thesis, Department of Computer Science, University of Toronto,
Toronto, 2005.
[thesis pdf]
Symbolic Perseus has been used to solve factored POMDPs with up to 50 million states in the following papers:
Automated Handwashing Assistance for Persons with Dementia Using Video and a Partially Observable Markov Decision Process Jesse Hoey, Pascal Poupart, Axel von Bertoldi, Tamy Craig, Craig Boutilier and Alex Mihailidis
Computer Vision and Image Understanding (CVIU), Volume 114, Issue 5, pages 503-519, May 2010.
[paper.pdf]
Assisting Persons with Dementia during Handwashing Using a Partially Observable Markov Decision Process Jesse Hoey, Axel von Bertoldi, Pascal Poupart, and Alex Mihailidis
In Proceedings of the International Conference on Vision Systems (ICVS), Biefeld, Germany, 2007.
[paper.pdf] winner of the best paper award
A Decision-Theoretic Approach to Task Assistance for Persons with Dementia Jennifer Boger, Pascal Poupart, Jesse Hoey, Craig Boutilier, Geoff Fernie,
and Alex Mihailidis
In Proceedings of the International Joint Conference on Artificial
Intelligence (IJCAI), pages 1293-1299, Edinburgh, Scotland, 2005.
[paper.pdf]