Carnegie Mellon University
sungkyuk_phd_robotics_2019.pdf (7.55 MB)

Planning under Uncertainty with Multiple Heuristics

Download (7.55 MB)
posted on 2019-07-01, 20:15 authored by Sung Kyun KimSung Kyun Kim
Many robotic tasks, such as mobile manipulation, often require interaction with unstructured environments and are subject to imperfect sensing and actuation. This brings substantial uncertainty into the problems. Reasoning
under this uncertainty can provide higher level of robustness but is computationally significantly more challenging. More specifically, sequential decision making under motion and sensing uncertainty can be formulated in a principled form as a Partially Observable Markov Decision Process (POMDP). Solving POMDPs exactly is computationally intractable due to their exponential complexity with the number of states and the depth of the planning horizon, so called, the curse of dimensionality and the curse of
history, respectively. In this work, we propose a novel search-based robust planning framework that sample-efficiently finds a solution with theoretical suboptimality
bounds by leveraging multiple heuristics that are designed using domain knowledge. The main contributions of this work can be summarized as follows: 1) it works with generative models, in the absence of mathematical models, similarly to the reinforcement learning paradigm, but 2) it still exhibits high sample-efficiency by bootstrapping with the domain knowledge in the form of heuristics, and 3) it is empowered with effective guidance of the search toward the goal through the systematic employment of multiple
heuristics. Its solution can be returned in an anytime fashion, and converges to the bounded suboptimality with theoretical guarantees. We validate the proposed frameworks through simulation and robot experiments,
which includes 2D rover navigation, PR2 parts assembly, and full size mobile manipulator truck unloading tasks. The truck unloading task is especially interesting, where the custom-built robot is to unload up to several thousands of boxes from a truck. It is a challenging real-world manipulation problem in continuous space with excessively high uncertainty, and we demonstrate the efficacy of our approach in such a domain.




Degree Type

  • Dissertation


  • Robotics Institute

Degree Name

  • Doctor of Philosophy (PhD)


Maxim Likhachev

Usage metrics


    Ref. manager