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

By Hanna Kurniawati, David Hsu, Wee Sun Lee. Robotics: Science and Systems Conference, 2008

1,050 citations recorded by the source corpus.

IN Proc. Robotics: Science & Systems, 2008 Abstract—Motion planning in uncertain and dynamic environ- ments 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 com- putational 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. In most of the 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 http://motion.comp.nus.edu.sg/ projects/pomdp/pomdp.html.

Subfields: Artificial Intelligence, Computer Networks and Communications, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/6c485f3d910d46c88f00cdaa9883cc7c43805fb5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

Citations in the corpus

Reinforcement learning with limited reinforcement: using Bayes risk for active learning in POMDPs (2008, neutral): “Recent advances in POMDP approximation algorithms allow agents to plan in POMDPs with tens of thousands of states [8, 9].”
Shared autonomy via hindsight optimization for teleoperation and teaming (2017, methodology): “Bandyopadhyay et al. (2012) use ﬁxed models for pedestrian motions, and focus on utilizing a POMDP framework with SARSOP (Kurniawati et al., 2008) for selecting good actions.”
POMDP-Based Statistical Spoken Dialog Systems: A Review (2013, methodology): “[52] H. Kurniawati, D. Hsu, and W. Lee, ‘‘SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces,’’ in Proc.”
Integrated task and motion planning in belief space (2013, background): “Recent pointbased POMDP solvers (Kurniawati et al., 2008) can be leveraged to solve a variety of robotics problems (Hsiao et al., 2007; Ong et al., 2010; Kurniawati et al., 2011), but mobile manipulation problems involving many movable objects are beyond the scope of these methods.”
Rational quantitative attribution of beliefs, desires and percepts in human mentalizing (2017, methodology): “In the domains we study here, near-optimal solutions can be computed efficiently using approximate solvers: for Experiment 1 we used a grid-based approximation 42 , and for Experiment 2 we used a point-based algorithm 43 .”
Shared Autonomy via Hindsight Optimization (2015, methodology): “Bandy et al. [4] use ﬁxed models for pedestrian motions, and focus on utilizing a POMDP framework with SARSOP [17] for selecting good actions.”
Learning to plan with uncertain topological maps (2020, neutral): “Approaches for ﬁnding optimal solutions have been intensively investigated in the 2000s, ranging from dynamic programming [26] to heuristic search methods [51,30].”
Monte-Carlo Planning in Large POMDPs (2010, methodology): “The full-width, offline planner SARSOP was given approximately 1000 seconds of offline computation; results are from [9].”
Offline policy evaluation across representations with applications to educational games (2014, methodology): “Many widely-used offline POMDP planning techniques such as SARSOP [11] are not applicable due to the fact that our observations are continuous.”
Nonmyopic View Planning for Active Object Classification and Pose Estimation (2014, methodology): “We represent the active object classification and pose estimation problem as a partially observable Markov decision process (POMDP) and use a pointbased approximate algorithm [25], [26] to solve it.”
Deep Reinforcement Learning amidst Lifelong Non-Stationarity (2020, methodology): “While exact solution methods are tractable only for tiny state and actions spaces [27], methods based (primarily) on approximate Bayesian inference have enabled scaling to larger problems over the course of the past two decades [31, 44].”
Sidekick agents for sequential planning problems (2013, methodology): “One popular set of more general-purpose approaches to POMDP solving use pointbased methods which sample points in belief space, compute the value function at those points via value iteration, and use them to form a value function estimate, such as PBVI [50] and SARSOP [37].”
DESPOT: Online POMDP Planning with Regularization (2013, methodology): “Although offline planning algorithms have made major progress in recent years (Pineau et al., 2003; Spaan & Vlassis, 2005; Smith & Simmons, 2005; Kurniawati et al., 2008), they still face significant difficulty in scaling up to very large POMDPs, as they must plan for all beliefs and future…”
LQG-MP: Optimized path planning for robots with motion uncertainty and imperfect state information (2010, background): “The MD P concept can be extended to POMDPs to also include sensing uncertainty [12], [16], [26], but these suffer from issues o f scalability [24].”
Deep Reinforcement Learning amidst Continual Structured Non-Stationarity (2021, methodology): “, 1998), methods based (primarily) on approximate Bayesian inference have enabled scaling to larger problems over the course of the past two decades (Kurniawati et al., 2008; Roy et al., 2005).”