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