Carnegie Mellon University
Applying Metric-Trees to Belief-Point POMDPs

Joelle Pineau, Geoffrey Gordon, and Sebastian Thrun
Neural Information Processing Systems (NIPS), 2003.

  • Adobe portable document format (pdf) (130KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Recent developments in grid-based and point-based approximation algorithms for POMDPs have greatly improved the tractability of POMDP planning. These approaches operate on sets of belief points by individually learning a value function for each point. In reality, belief points exist in a highly-structured metric simplex, but current POMDP algorithms do not exploit this property. This paper presents a new metric-tree algorithm which can be used in the context of POMDP planning to sort belief points spatially, and then perform fast value function updates over groups of points. We present results showing that this approach can reduce computation in point-based POMDP algorithms for a wide range of problems.

Associated Lab(s) / Group(s): Robot Learning Lab
Number of pages: 8

Text Reference
Joelle Pineau, Geoffrey Gordon, and Sebastian Thrun, "Applying Metric-Trees to Belief-Point POMDPs," Neural Information Processing Systems (NIPS), 2003.

BibTeX Reference
   author = "Joelle Pineau and Geoffrey Gordon and Sebastian Thrun",
   title = "Applying Metric-Trees to Belief-Point POMDPs",
   booktitle = "Neural Information Processing Systems (NIPS)",
   year = "2003",