RECORD
Efficient Touch Based Localization through Submodularity
Robotics · Submitted 30 Aug 2012
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We demonstrate the effectiveness of these methods in simulation and on a robot.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Many robotic systems deal with uncertainty by performing a sequence of information gathering actions. | background 1.00 | 0.04 | 0.02 | asserted 0.99 |
| s1 | In this work, we focus on the problem of efficiently constructing such a sequence by drawing an explicit connection to submodularity. | contribution 0.89 | 0.72 | 0.07 | asserted 0.93 |
| s2 | Ideally, we would like a method that finds the optimal sequence, taking the minimum amount of time while providing sufficient information. | background 0.94 | 0.07 | 0.05 | asserted 0.54 |
| s3 | Finding this sequence, however, is generally intractable. | background 0.78 | 0.11 | 0.02 | asserted 0.98 |
| s4 | As a result, many well-established methods select actions greedily. | background 1.00 | 0.05 | 0.02 | asserted 0.99 |
| s5 | Surprisingly, this often performs well. | background 0.90 | 0.11 | 0.04 | asserted 0.87 |
| s6 | 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. | contribution 0.78 | 0.76 | 0.21 | asserted 1.00 |
| s7 | However, reacting online to observations can increase performance. | gap 0.52 | 0.09 | 0.04 | hedged possibility 0.51 |
| s8 | Recently developed notions of adaptive submodularity provide guarantees for a greedy algorithm in this online setting. | background 0.99 | 0.04 | 0.08 | asserted 1.00 |
| s9 | In this work, we develop new methods based on adaptive submodularity for selecting a sequence of information gathering actions online. | contribution 0.98 | 0.94 | 0.22 | asserted 1.00 |
| s10 | In addition to providing guarantees, we can capitalize on submodularity to attain additional computational speedups. | contribution 0.92 | 0.83 | 0.11 | asserted 0.75 |
| s11 | We demonstrate the effectiveness of these methods in simulation and on a robot. | result 0.70 | 0.94 | 0.25 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.