Prezi

Present Remotely

Send the link below via email or IM

Copy

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 the manual

Do you really want to delete this prezi?

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

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

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
by Shervin Javdani on 14 May 2013

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 Submodular Cannot React to Observations [Nemhauser et al. '78]
Ex: Chair sensors [Mutlu et al. '07] Adaptive Submodular React Online to Observations Near-optimal offline plan Near-optimal online policy Adaptive Submodularity Implications Monotonicty: More is better Submodularity: 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 Goal: Efficient Automation of Touch Localization Select a Sequence of Information Gathering Actions Motivation 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 [1] greedy is near-optimal! Touch Localization is Adaptive Submodular Efficient lazy-greedy algorithm comparable to optimal solution { seconds days { Method 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: Expected 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 Results and Discussion Not adaptive 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 speedup theoretical bound Overview Partially Observable Markov Decision Process (POMDP) [Kaelbling '98]
POMDP for Touch Localization [Hsiao '09]
See the full transcript