Proceedings

Topological Order Planner for POMDPs

Download BibTeX Cite

Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 1684-1688.

© 2009 International Joint Conferences on Artificial Intelligence

Abstract

Over the past few years, point-based POMDP solvers scaled up to produce approximate solutions to mid-sized domains. However, to solve real world problems, solvers must exploit the structure of the domain. In this paper we focus on the topological structure of the problem, where the state space contains layers of states. We present here the Topological Order Planner (TOP) that utilizes the topological structure of the domain to compute belief space trajectories. TOP rapidly produces trajectories focused on the solveable regions of the belief space, thus reducing the number of redundant backups considerably. We demonstrate TOP to produce good quality policies faster than any other point-based algorithm on domains with sufficient structure.Jilles Steeve Dibangoye, Guy Shani, Brahim Chaib-draa, Abdell-Illah Mouaddib

  1. [Abbad and Boustique, 2003] Mohammed Abbad and Hatim Bous- tique. A decomposition algorithm for limiting average markov decision problems. Oper. Res. Lett., 31(3):473-476, 2003.
  2. [Bonet and Geffner, 2003] Blai Bonet and Hector Geffner. Faster heuristic search algorithms for planning with uncertainty and full feedback. In Proceedings of IJCAI, pages 1233-1238, 2003. IJCAI
  3. [Cassandra et al., 1997] Anthony Cassandra, Michael L. Littman, and Nevin L. Zhang. Incremental Pruning: A simple, fast, exact method for partially observable Markov decision processes. In Proceedings of UAI, pages 54-61, 1997.
  4. [Dai and Goldsmith, 2007] Peng Dai and Judy Goldsmith. Topo- logical value iteration algorithm for Markov Decision Processes. In Proceedings of IJCAI, pages 1860-1865, 2007. IJCAI
  5. [Lovejoy, 1991] W. S. Lovejoy. Computationally feasible bounds for partially observable markov decison processes. Operations Research, 39:175-192, 1991.
  6. [Pineau et al., 2003a] Joelle Pineau, Geoffrey J. Gordon, and Se- bastian Thrun. Point-based value iteration: An anytime algorithm for pomdps. In Proceedings of IJCAI, pages 1025-1032, 2003. IJCAI
  7. [Pineau et al., 2003b] Joelle Pineau, Geoffrey J. Gordon, and Se- bastian Thrun. Policy-contingent abstraction for robust robot control. In Proceedings of UAI, pages 477-484, 2003.
  8. [Shani et al., 2006] Guy Shani, Ronen I. Brafman, and Solomon Eyal Shimony. Prioritizing point-based pomdp solvers. In Proceedings of ECML, pages 389-400, 2006.
  9. [Shani et al., 2007] Guy Shani, Ronen I. Brafman, and Solomon Eyal Shimony. Forward search value iteration for pomdps. In Proceedings of IJCAI, pages 2619-2624, 2007. IJCAI
  10. [Shani et al., 2008] Guy Shani, Pascal Poupart, Ronen I. Brafman, and Solomon Eyal Shimony. Efficient add operations for point- based algorithms. In Proceedings of ICAPS, pages 330-337, 2008.
  11. [Smith and Simmons, 2005] Trey Smith and Reid G. Simmons. Point-based POMDP algorithms: Improved analysis and imple- mentation. In Proceedings of UAI, pages 542-547, 2005.
  12. [Spaan and Vlassis, 2005] Matthijs T. J. Spaan and Nikos Vlassis. Perseus: Randomized point-based value iteration for POMDPs. Journal of Artificial Intelligence Research, 24:195-220, 2005.
  13. [Virin et al., 2007] Yan Virin, Guy Shani, Solomon Eyal Shimony, and Ronen I. Brafman. Scaling up: Solving pomdps through value based clustering. In Proceedings of AAAI, pages 1290- 1295, 2007.
  14. [Wingate and Seppi, 2005] David Wingate and Kevin D. Seppi. Pri- oritization methods for accelerating mdp solvers. J. Mach. Learn. Res., 6:851-881, 2005.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards