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

Many robotic systems deal with uncertainty by performing a sequence of information gathering actions. In this work, we focus on the problem of efficiently constructing such a sequence by drawing an explicit connection to submodularity. Ideally, we would like a method that finds the optimal sequence, taking the minimum amount of time while providing sufficient information. Finding this sequence, however, is generally intractable. As a result, many well-established methods select actions greedily. Surprisingly, this often performs well. Our work first explains this high performance -- we note a commonly used metric, reduction of Shannon entropy, is submodular under certain assumptions, rendering the greedy solution comparable to the optimal plan in the offline setting. However, reacting online to observations can increase performance. Recently developed notions of adaptive submodularity provide guarantees for a greedy algorithm in this online setting. In this work, we develop new methods based on adaptive submodularity for selecting a sequence of information gathering actions online. In addition to providing guarantees, we can capitalize on submodularity to attain additional computational speedups. We demonstrate the effectiveness of these methods in simulation and on a robot.

Notes

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: 14

Note: Extended version of paper with identical title presented at the IEEE International Conference on Robotics and Automation (ICRA) 2013. Please cite the ICRA version instead.

Text Reference

Shervin Javdani, Matthew Klingensmith, J. Andrew (Drew) Bagnell, Nancy Pollard, and Siddhartha Srinivasa, "Efficient Touch Based Localization through Submodularity," tech. report CMU-RI-TR-12-25, Robotics Institute, Carnegie Mellon University, August, 2012

BibTeX Reference

@techreport{Javdani_2012_7264,
   author = "Shervin Javdani and Matthew Klingensmith and J. Andrew (Drew) Bagnell and Nancy Pollard and Siddhartha Srinivasa",
   title = "Efficient Touch Based Localization through Submodularity",
   booktitle = "",
   institution = "Robotics Institute",
   month = "August",
   year = "2012",
   number= "CMU-RI-TR-12-25",
   address= "Pittsburgh, PA",
   Notes = "Extended version of paper with identical title presented at the IEEE International Conference on Robotics and Automation (ICRA) 2013. Please cite the ICRA version instead."
}

The Robotics Institute

Menu