Online POMDP Planning
The lack of general and systematic treatment of uncertainties and imperfect robot control, noisy sensors, and environmental changes—is a major barrier to robust robot operation and has thwarted the widespread use of robots in natural human environments until the recent decade. The partially observable Markov decision process (POMDP) provides a principled general framework for planning under uncertainty, using a probabilistic approach. Unfortunately solving POMDPs exactly is provably intractable. Early algorithms can handle only very small POMDPs with 10–20 states, which are woefully inadequate for modeling realistic robotic tasks. The challenge for POMDP planning is to scale up and handle POMDPs with very large state spaces and complex dynamics. Our research on POMDPs spans the entire spectrum of mathematical foundations, efficient algorithms, and application to critical real-world systems: The notion of covering numbers provides theoretical justification that explains why probabilistic approximation algorithms work well empirically on the computationally intractable problem of solving POMDPs. SARSOP and DESPOT are among the fastest POMDP algorithms available today for offline and online POMDP planning, respectively. Our algorithms have found a broad range of applications in robotics and beyond, including collision avoidance protocols for unmanned aircrafts, autonomous vehicles, penetration testing for computer security, and intelligent computer tutoring system.