The Robotics Institute

Carnegie Mellon Robotics Institute

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.

Abstract

Existing complexity bounds for point-based POMDP value iteration algorithms focus either on the curse of dimensionality or the curse of history. We derive a new bound that relies on both and uses the concept of discounted reachability; our conclusions may help guide future algorithm design. We also discuss recent improvements to our (point-based) heuristic search value iteration algorithm. Our new implementation calculates tighter initial bounds, avoids solving linear programs, and makes more effective use of sparsity. Empirical results show speedups of more than two orders of magnitude.

Keywords

probabilistic planning, POMDP

Notes

Text Reference

Trey Smith and Reid Simmons, "Point-based POMDP Algorithms: Improved Analysis and Implementation," Proc. of the Conference on Uncertainty in Artificial Intelligence, July, 2005.

BibTeX Reference

@inproceedings{Smith_2005_5310,
   author = "Trey Smith and Reid Simmons",
   title = "Point-based POMDP Algorithms: Improved Analysis and Implementation",
   booktitle = "Proc. of the Conference on Uncertainty in Artificial Intelligence",
   month = "July",
   year = "2005",
}

The Robotics Institute

Menu