Department of Computer Science
National University of Singapore
Title: Large-Scale Online Planning under Uncertainty
Abstract: How can a robot act robustly with imperfect control and noisy sensing? Unfortunately, choosing optimal actions under control and sensing uncertainty is computationally intractable, because the robot must reason about myriad future scenarios over many time steps. We introduce the Determinized Sparse Partially Observable Tree (DESPOT) for online planning under uncertainty. A DESPOT focuses online planning on a set of randomly sampled scenarios and compactly captures the “execution” of all policies under these scenarios. We show that the best policy obtained from a DESPOT is near-optimal, with a regret bound that depends on the representation size of an optimal policy. The algorithm demonstrates strong empirical performance, compared with the state of the art. It has also been incorporated into an autonomous driving system for real-time vehicle control. The source code for the algorithm is available online at http://bigbird.comp.nus.edu.sg/pmwiki/farm/appl/.
Short Bio: David Hsu is a professor of computer science at the National University of Singapore, a member of NUS Graduate School for Integrative Sciences & Engineering (NGS), and deputy director of the Advanced Robotics Center. His current research focuses on robotics and AI, in particular, robot planning and learning under uncertainty. More information about his research is available here (http://www.comp.nus.edu.sg/~dyhsu/).