Loading presentation...

Present Remotely

Send the link below via email or IM


Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.


Efficient Touch Based Localization through Submodularity

Presentation from ICRA 2013. For more details, see: http://www.ri.cmu.edu/publication_view.html?pub_id=7264

Shervin Javdani

on 14 October 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Efficient Touch Based Localization through Submodularity

Efficient Touch Based Localization through Submodularity
Information Gain (Reduction of Shannon Entropy)
[Hebert et al. '12]
[Bourgault et al. '02]
[Fox et al. '98]
[Mutlu et al. '07]
[Krause and Guestrin '05]
[Erickson et al. '08]
[Fu et al. '07]
[Hsiao et al. '08]
Many More!
Plan vs. Policy
Cannot React to Observations
[Nemhauser et al. '78]
Ex: Chair sensors [Mutlu et al. '07]
Adaptive Submodular
React Online to Observations
offline plan
online policy
Adaptive Submodularity Implications

More is better

Early is better
Mild Implication:
Actions cannot increase uncertainty
Strong Implication:
Actions cannot setup future actions
Shervin Javdani, Matt Klingensmith, J. Andrew Bagnell, Nancy Pollard, Siddhartha S. Srinivasa
Robotics Institute, Carnegie Mellon University

Automation of Touch Localization
Select a Sequence of Information Gathering Actions
Need to account for uncertainty
Find minimum-time sequence which achieves sufficient localization
Intractable! Limit actions and depth
Unclear how this affects performance
Recent Advance: If the problem is
adaptive submodular

greedy is near-optimal!
Touch Localization is Adaptive Submodular
Efficient lazy-greedy algorithm comparable to optimal solution
Guarded moves can be effective
Touch Localization as Set Cover
Objective: Maximize Coverage
(Maximally Disprove Hypotheses)
Problem Formulation
[1] Golovin and Krause '11
Computing Action Utilities
Related Work:
Generalized Binary Search [Nowak '08]
Multiple Outcomes [Guillory and Bilmes '09]
Computing Action Utilities After Update
Adaptive Submodularity Requirements
Strong Adaptive Monotonicity
Adaptive Submodularity
More is Better
Any action, observation pair can only remove hypotheses
Early is Better
Easy to see:
Utility does not increase for
fixed observation
Less obvious:

utility does not increase. Proof in paper!
Observation Probabilities and Utilities change with updates
Hypotheses: Object Pose
Actions: Guarded Moves
(Straight motion until contact)
Observations: Distance until contact
Properties imply greedy is near-optimal policy [Golovin and Krause '11]
Use Adaptive Submodularity to skip re-evaluations
Efficiency Boost: Lazy-Greedy
Results and Discussion
submodular, stills work well with greedy
[Golovin and Krause '11]
Ex: Touch based Localization
Take Away: Touch Localization is Adaptive Submodular
Efficient lazy-greedy algorithm comparable to optimal solution
theoretical bound
Partially Observable Markov Decision Process (POMDP) [Kaelbling '98]
POMDP for Touch Localization [Hsiao '09]
Full transcript