Carnegie Mellon University
Browse
file.pdf (2.64 MB)

Efficient Touch Based Localization through Submodularity

Download (2.64 MB)
journal contribution
posted on 2013-05-01, 00:00 authored by Shervin Javdani, Matthew Klingensmith, J. Andrew Bagnell, Nancy Pollard, Siddhartha SrinivasaSiddhartha Srinivasa

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 of actions, 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 even with only one step lookahead. Our work first explains this high performance -- we note that 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. Recently developed notions of adaptive submodularity enable guarantees for a greedy algorithm in the online setting. We develop new methods within this framework, enabling us to provide guarantees compared to the optimal online policy, as well as exploit additional computational speedups. We demonstrate the effectiveness of these methods in simulation and on a robot.

History

Date

2013-05-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC