POMDP Workshop: Beyond Simple State Space Representation

It is often believed that the main barrier to the adoption of POMDPs in practice is the ability to solve them fast enough. The speed of POMDP solvers has improved dramatically in recent years. Yet the adoption of POMDPs in real applications is still scarce. What is needed to overcome this barrier? What are the suitable applications for POMDPs? What technical challenges are critical and must be addressed in order for POMDPs to be widely applied? It is clear that the simple discrete state space representation used in most of the fast POMDP solvers in recent years quickly becomes inadequate for most applications. More advanced representations have been proposed, but work on them is mostly at the initial stages.

This workshop aims to bring together researchers in the area to discuss the challenges, the approaches, and the various representations in order to scale up POMDP solvers for real applications. Desired outcomes include a better understanding of the research directions and insights into how to overcome some of the technical challenges. Areas of interest include:

• Continuous POMDPs
• Factored POMDPs
• Hierarchical POMDPs
• First Order POMDPs
• Applications

Date: 19-21 January 2009
Location: TR15, AS6 level 2, School of Computing, National University of Singapore (directions)

Participants

• Eric Hansen (Mississippi State University)
• Milos Hauskrecht (University of Pittsburgh)
• David Hsu (National University of Singapore)
• Kee-Eung Kim (Korea Advanced Institute of Science and Technology)
• Leslie Kaelbling (Massachusetts Institute of Technology)
• Wee Sun Lee (National University of Singapore)
• Tze Yun Leong (National University of Singapore)
• Tomas Lozano-Perez (Massachusetts Institute of Technology)
• Joelle Pineau (McGill University)
• Pascal Poupart (University of Waterloo)
• Nick Roy (Massachusetts Institute of Technology)
• Guy Shani (Microsoft Research)
• Nikos Vlassis (Technical University of Crete)
• Scott Sanner (NICTA and Australian National University)
• Jason Williams (AT&T Labs)
• Luke Zettlemoyer (Massachusetts Institute of Technology)

Programme

Monday 19 January 2009

Tuesday 20 January 2009

Wednesday 21 January 2009

Organizers

• David Hsu, National University of Singapore
• Wee Sun Lee, National University of Singapore
• Tze Yun Leong, National University of Singapore

Reading list

General POMDPs

1. LP Kaelbling, ML Littman, AR Cassandra, Planning and acting in partially observable stochastic domains. Artificial Intelligence, 1998
2. M. Hauskrecht. Value-function approximations for partially observable Markov decision processes. Journal of Artificial Intelligence Research, vol.13, pp. 33-94, 2000.
3. MTJ Spaan, N Vlassis, Perseus: Randomized point-based value iteration for POMDPs. Journal of Artificial Intelligence Research, 2005
4. J Pineau, G Gordon, S Thrun, Point-based value iteration: An anytime algorithm for POMDPs IJCAI 2003
5. T Smith, R Simmons, Heuristic search value iteration for POMDPs. UAI 2004
6. David Hsu, Wee Sun Lee and Nan Rong, What Makes Some POMDP Problems Easy to Approximate? NIPS 2007
7. Hanna Kurniawati, David Hsu, and Wee Sun Lee, SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces. RSS 2008

Applications

1. Cassandra, A.R., A survey of POMDP applications. Working Notes of AAAI 1998 Fall Symposium on Planning with Partially Observable Markov Decision Processes, 1998
2. Jason D. Williams and Steve Young, Scaling POMDPs for spoken dialog management. IEEE Trans. on Audio, Speech, and Language Processing 15(7): 2116-2129, 2007.
3. Jesse Hoey, Axel von Bertoldi, Pascal Poupart, and Alex Mihailidis, Assisting Persons with Dementia during Handwashing Using a Partially Observable Markov Decision Process. Proceedings of the International Conference on Vision Systems ICVS 2007, Bielefeld, Germany, March 2007.
4. J Pineau, G Gordon, POMDP planning for robust robot control. The Twelveth International Symposium on Robotics Research, 2005
5. M Hauskrecht, H Fraser, Planning treatment of ischemic heart disease with partially observable Markov decision processes. Artificial Intelligence In Medicine, 2000
6. MTJ Spaan, N Spaan, A point-based POMDP algorithm for robot planning. Robotics and Automation, 2004. Proceedings. ICRA'04. 2004
7. David Hsu, Wee Sun Lee, and Nan Rong, A point-based POMDP planner for target tracking. Proc. IEEE Int. Conf. on Robotics & Automation, pp. 2644–2650, 2008.

Continuous POMDPs

1. JM Porta, N Vlassis, MTJ Spaan, P Poupart, Point-Based Value Iteration for Continuous POMDPs. The Journal of Machine Learning Research, 2006
2. E Brunskill, L Kaelbling, T Lozano-Perez, N Roy, Continuous-State POMDPs with Hybrid Dynamics, ISIAM 2008
3. AY Ng, M Jordan, PEGASUS: A policy search method for large MDPs and POMDPs,UAI 2000

Factored POMDPs

1. C Boutilier, D Poole, Computing Optimal Policies for Partially Observable Decision Processes Using Compact Representations. AAAI 1996
2. D McAllester, S Singh, Approximate planning for factored POMDPs using belief state simplification. UAI 1999
3. Boutilier, C., Dean, T., and Hanks, S.,Decision-theoretic planning: Structural assumptions and computational leverage. Journal of Artificial Intelligence Research, 11:1--94, 1999.
4. C Guestrin, D Koller, R Parr, Solving factored POMDPs with linear value functions. IJCAI-01 workshop on Planning under Uncertainty
5. E Hansen, Z Feng, Dynamic programming for POMDPs using a factored state representation Proc. AIPS, 2000
6. G Shani, RI Brafman, SE Shimony, P Poupart, Efficient ADD Operations for Point-Based Algorithms. ICAPS 2008
7. HS Sim, KE Kim, JH Kim, DS Chang, MW Koo, Symbolic Heuristic Search Value Iteration for Factored POMDPs Proceedings of AAAI-2008, 2008.

Hierarchical POMDPs

1. E Hansen, R Zhou, Synthesis of hierarchical finite-state controllers for POMDPs. ICAPS-03
2. J Pineau, G Gordon, S Thrun, Policy-contingent abstraction for robust robot control. UAI 2003
3. G Theocharous, S Mahadevan, LP Kaelbling, Spatial and Temporal Abstractions in POMDPs Applied to Robot Navigation MIT Tech Report 2005
4. Marc Toussaint, Laurent Charlin and Pascal Poupart, Hierarchical POMDP Controller Optimization by Likelihood Maximization Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence (UAI), Helsinki, Finland, 2008.
5. Laurent Charlin, Pascal Poupart and Romy Shioda, Automated Hierarchy Discovery for Planning in Partially Observable Environments Advances in Neural Information Processing Systems 19 (NIPS), Vancouver, BC, 2006.

First Order POMDPs

1. C Boutilier, R Reiter, B Price, Symbolic Dynamic Programming for First-Order MDPs
2. C Wang, S Joshi, R Khardon, First Order Decision Diagrams for Relational MDPs. Journal of Artificial Intelligence Research, 2008
3. C Wang, J Schmolze, Planning with POMDPs Using a Compact, Logic-Based Representation ICTAI 05
4. Sungwook Yoon, Alan Fern, Subbarao Kambhampati and Robert Givan, Probabilistic Planning via Determinization in Hindsight AAAI '08
5. S Sanner, and C Boutilier, Practical linear value-approximation techniques for first-order MDPs UAI-06

Related Links

AAAI 2008 Workshop on Advancements in POMDP Solvers