Carnegie Mellon University
The
Robust Trajectory Selection for Rearrangement Planning as a Multi-Armed Bandit Problem

Michael Koval, Jennifer King, Nancy Pollard , and Siddhartha Srinivasa
IEEE/RSJ International Conference on Intelligent Robots and Systems, September, 2015.


Download
  • Adobe portable document format (pdf) (1MB)
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
We present an algorithm for generating open- loop trajectories that solve the problem of rearrangement planning under uncertainty. We frame this as a selection problem where the goal is to choose the most robust trajectory from a finite set of candidates. We generate each candidate using a kinodynamic state space planner and evaluate it using noisy rollouts.

Our key insight is we can formalize the selection problem as the “best arm” variant of the multi-armed bandit problem. We use the successive rejects algorithm to efficiently allocate rollouts between candidate trajectories given a rollout budget. We show that the successive rejects algorithm identifies the best candidate using fewer rollouts than a baseline algorithm in simulation. We also show that selecting a good candidate increases the likelihood of successful execution on a real robot.

Keywords
manipulation planning, manipulation under uncertainty, non-prehensile manipulation

Notes
Sponsor: NASA Space Technology Research Fellowship program, National Science Foundation, and the Toyota Motor Corporation
Associated Center(s) / Consortia: Quality of Life Technology Center, National Robotics Engineering Center, and Center for the Foundations of Robotics
Associated Lab(s) / Group(s): Personal Robotics
Number of pages: 8

Text Reference
Michael Koval, Jennifer King, Nancy Pollard , and Siddhartha Srinivasa, "Robust Trajectory Selection for Rearrangement Planning as a Multi-Armed Bandit Problem," IEEE/RSJ International Conference on Intelligent Robots and Systems, September, 2015.

BibTeX Reference
@inproceedings{Koval_2015_7999,
   author = "Michael Koval and Jennifer King and Nancy {Pollard } and Siddhartha Srinivasa",
   title = "Robust Trajectory Selection for Rearrangement Planning as a Multi-Armed Bandit Problem",
   booktitle = "IEEE/RSJ International Conference on Intelligent Robots and Systems",
   month = "September",
   year = "2015",
}