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

The problem of planning under uncertainty has received significant attention in the scientific community over the past few years. It is now well-recognized that considering uncertainty during planning and decision-making is imperative to the design of robust computer systems. This is particularly crucial in robotics, where the ability to interact effectively with real-world environments is a prerequisite for success.

The Partially Observable Markov Decision Process (POMDP) provides a rich framework for planning under uncertainty. The POMDP model can optimize sequences of actions which are robust to sensor noise, missing information, occlusion, as well as imprecise actuators. While the model is sufficiently rich to address most robotic planning problems, exact solutions are generally intractable for all but the smallest problems.

This thesis argues that large POMDP problems can be solved by exploiting natural structural constraints. In support of this, we propose two distinct but complementary algorithms which overcome tractability issues in POMDP planning. PBVI is a sample-based approach which approximates a value function solution by planning over a small number of salient information states. PolCA+ is a hierarchical approach which leverages structural properties of a problem to decompose it into a set of smaller, easy-to-solve, problems. These techniques improve the tractability of POMDP planning to the point where POMDP-based robot controllers are a reality. This is demonstrated through the successful deployment of a nursing assistant robot.

Keywords

decision-making, planning, Markov decision process, POMDP, robotics, dialogue management

Notes

Associated Lab(s) / Group(s): Robot Learning Lab

Text Reference

Joelle Pineau, "Tractable Planning Under Uncertainty: Exploiting Structure," doctoral dissertation, tech. report CMU-RI-TR-04-32, Robotics Institute, Carnegie Mellon University, August, 2004

BibTeX Reference

@phdthesis{Pineau_2004_4767,
   author = "Joelle Pineau",
   title = "Tractable Planning Under Uncertainty: Exploiting Structure",
   booktitle = "",
   school = "Robotics Institute, Carnegie Mellon University",
   month = "August",
   year = "2004",
   number= "CMU-RI-TR-04-32",
   address= "Pittsburgh, PA",
}

The Robotics Institute

Menu