Home/Planning under Uncertainty with Multiple Heuristics

Planning under Uncertainty with Multiple Heuristics

Sung Kyun Kim
PhD Thesis, Tech. Report, CMU-RI-TR-19-26, May, 2019

Download Publication

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

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.


@phdthesis{Kim-2019-112862,
author = {Sung Kyun Kim},
title = {Planning under Uncertainty with Multiple Heuristics},
year = {2019},
month = {May},
school = {},
address = {Pittsburgh, PA},
number = {CMU-RI-TR-19-26},
keywords = {planning under uncertainty; robust motion planning; search-based motion planning; robotic manipulation},
} 2019-05-13T14:32:16-04:00