Robotics: Science and Systems IV

SARSOP: Efficient Point-Based POMDP Planning by Approximating Optimally Reachable Belief Spaces

Hanna Kurniawati, David Hsu, Wee Sun Lee

Abstract: Motion planning in uncertain and dynamic environments is an essential capability for autonomous robots. Partially observable Markov decision processes (POMDPs) provide a principled mathematical framework for solving such problems, but they are often avoided in robotics, due to high computational complexity. Our goal is to create practical POMDP algorithms and software for common robotic tasks. To this end, we have developed a new point-based POMDP algorithm that exploits the notion of optimally reachable belief spaces to improve computational efficiency. In simulation, we successfully applied the algorithm to a set of common robotic tasks---including instances of coastal navigation, grasping, mobile robot exploration, and target tracking---all modeled as POMDPs with a large number of states. Furthermore, in most of these instances studied, our algorithm substantially outperformed one of the fastest existing point-based algorithms. A software package implementing our algorithm will soon be released at



    AUTHOR    = {Hanna Kurniawati, David Hsu, Wee Sun Lee},
    TITLE     = {{SARSOP}: Efficient Point-Based {POMDP} Planning by Approximating Optimally Reachable Belief Spaces},
    BOOKTITLE = {Proceedings of Robotics: Science and Systems IV},
    YEAR      = {2008},
    ADDRESS   = {Zurich, Switzerland},
    MONTH     = {June},
    DOI       = {10.15607/RSS.2008.IV.009}