eolson AUV2004

Information about eolson AUV2004

Published on June 18, 2007

Author: FunSchool

Source: authorstream.com

Content

Robust Range Only Beacon Localization:  Robust Range Only Beacon Localization Edwin Olson (eolson) John Leonard (jleonard) Seth Teller (teller) (@csail.mit.edu) MIT Computer Science and Artificial Intelligence Laboratory Outline:  Outline Our goal: Navigate with LBL beacons, without knowing the beacon locations Components Outlier rejection without a prior Initial solution estimation SLAM filter Optimal exploration Experimental Results:  Experimental Results Using real data from GOATS’02 Applications:  Applications Operation in unsurveyed beacon fields Covert deployment Aerial deployment Autonomous deployment Moving baseline navigation Vehicles serve as beacons Detection of beacon movement Basic Idea:  Basic Idea Record range measurements while traveling a relatively short distance. Initialize feature in Kalman filter based on trilateration. Continue updating both robot state and beacon position with EKF. but… Feature Initialization:  Feature Initialization Noise is a major issue Interference from sensors/other robots Outlier rejection Necessary due to non Gaussian error (if Gaussian noise, Kalman filter is optimal) No prior with which to do outlier detection How bad is the noise?:  How bad is the noise? Our data set has extensive interference from SAS payload But is the noise Gaussian?:  But is the noise Gaussian? Extensive outliers; result is not Gaussian (Multiplicative noise model is similarly poor) Noise Characterization:  Noise Characterization Noise is non-stationary Particular errors can occur consistently Examples: Multi-path, periodic interference Outlier RejectionPrevious Work:  Outlier Rejection Previous Work Prior-based outlier rejection ('gating') But we don’t have a prior… Newman’03 searches for 'low-noise' regions, uses them to extrapolate a constraint over higher noise regions Many parameters to tune, ad-hoc Outlier rejection:  Outlier rejection Goal Well-principled method (few tunable parameters) Good performance, even in extreme noise Other considerations CPU time isn’t really a factor Data arrives so slowly (~4Hz)… More important to make good use of data Try to make use of what we do know E.g., dead-reckoned vehicle position Measurements:  Measurements Use vehicle’s dead-reckoned position and measured range to construct a circle: Beacon lies on circle Measurement Consistency:  Measurement Consistency Consider pair-wise measurement consistency Limited dead-reckoning accuracy limits comparison of measurements to small window of time Spectral Clustering Formulation:  Spectral Clustering Formulation Consider many pair-wise compatibility tests Construct a graph: vertices are measurements, edges connect consistent measurements Inliers will tend to be more connected than outliers! Graph Outlier Rejection:  Outlier Rejection Find a cut that separates the inliers from outliers Cut A: Good! Cut B: Awful Cut C: Mediocre How do we formalize this? Adjacency Matrix:  Adjacency Matrix Create an Adjacency matrix where element {i,j}=consistency of measurements i and j Graph Partitioning:  Graph Partitioning Let u be an indicator vector If ui=1, then measurement i is an inlier If ui=0, then measurement i is an outlier What makes a value of u good? Highly consistent measurements are classified as inliers Less consistent measurements are classified as outliers Average Connectivity:  Average Connectivity Use average inlier connectivity as our metric: Intuition: Given a set of inliers, when should a measurement be added? Answer: when it’s at least as consistent with the inliers as the inliers are with themselves Number of edges connecting inliers (*2) Total number of inliers Spectral Clustering:  Spectral Clustering How does our metric perform? Cut A: 1.6 Cut B: 0.5 Cut C: 1.43 Finding the best u vector:  Finding the best u vector For discrete-valued u, this is hard! For continuous-valued u, exact solution is known Differentiating r(u) with respect to u, setting to zero: It’s an eigenvalue problem! Maximize r(u) by setting u to the maximum eigenvector Optimal eigenvector:  Optimal eigenvector First eigenvalue of adjacency matrix A Finding the u vector:  Finding the u vector We now have the optimal continuous-valued u vector. Larger values -andgt; inliers We need the discrete version Threshold u by scalar t Brute force search for t Only O(n); try each value of u as threshold Incorporate prior, if known, of % of outliers Computation in blocks:  Computation in blocks Measurements use dead-reckoned position Error in Adjacency matrix grows with dead-reckoning error Must limit this by performing outlier rejection in blocks Computation in blocks also bounds work needed to compute eigenvector Computational Optimization:  Computational Optimization Helpful observation: Our solution is the largest eigenvector, use the power method to find it! Power method Behavior of Anv is dominated by the largest eigenvector of A (call it u). For all1 v, Anv  u as n  infinity Anv is good enough in a few iterations (~3) 1Except vTu=0 Result on one block:  Result on one block Results from our algorithm: Black: outlier Blue: inlier Highly consistent set of measurements are classified as inliers Spectral clustering of 25 measurements (GOATS’02 data) Result on many blocks:  Result on many blocks Spectral Clustering, block size=20, prior=50% outliers After Before Multiple vehicles:  Multiple vehicles If vehicles positions are known in the same coordinate frame, just add the data and use the same algorithm. No need to do outlier rejection independently on each AUV. In fact, better not to! Initial Solution Estimation:  Initial Solution Estimation Given 'clean' data, estimate a beacon location Or determine that it’s still ambiguous! Compute intersections of consistent measurements Find an area with many votes Solution Estimation:  Solution Estimation Put each intersection into a 2-dimensional accumulator Extract peaks We get multiple solutions and the number of votes for each If #votes in 1st peak andgt;andgt; #votes in 2nd peak, then initialize feature Ratio ~=2 Initial Solution Estimation:  Initial Solution Estimation Vote ratio=4 to show algorithm working for longer. Ratio~=2 more realistic. Put it all together:  Put it all together We can now filter range measurements We can estimate where beacons are When we find a beacon, add feature to SLAM filter Beacons define coordinate system for robot Differ from global frame by rigid translation and rotation Difference is related to dead-reckoning error before acquiring beacons. SLAM:  SLAM GOATS’02 data Four beacons Dead-reckoned path in Red Uncalibrated compass+DVL EKF path with prior beacon locations in magenta SLAM Movie:  SLAM Movie Optimal Exploration:  Optimal Exploration Robot at x, beacon is at either A or B. Disambiguate by maximizing the difference in range depending on actual location i.e., maximize: What should robot do now? Path leads to two possible solutions Path leads to only one plausible solution Optimal Exploration: Solution:  Optimal Exploration: Solution Gradient is easily computed Absolute value handled by setting A to be the closest of A and B. Optimal robot motions given possible beacon locations at (-1,0) and (1,0). Arrow size indicates magnitude of ∆r per distance traveled. Future Work:  Future Work Guess beacon locations earlier and use particle filter to track the multiple hypotheses Incorporate optimal exploration algorithm into experiment. Questions/Comments:  Questions/Comments

#votes presentations

Nossi ch 3
29. 05. 2008
0 views

Nossi ch 3

Related presentations


Other presentations created by FunSchool

Got Discipline PowerPoint
18. 06. 2007
0 views

Got Discipline PowerPoint

InterAccess
30. 04. 2008
0 views

InterAccess

lockin1
28. 04. 2008
0 views

lockin1

IIEF MCX
22. 04. 2008
0 views

IIEF MCX

MapAccNov01
18. 04. 2008
0 views

MapAccNov01

ICW Presentation
17. 04. 2008
0 views

ICW Presentation

Lecture 9 Macro model
16. 04. 2008
0 views

Lecture 9 Macro model

ATE12
14. 04. 2008
0 views

ATE12

TeAM NEF ESF Report
13. 04. 2008
0 views

TeAM NEF ESF Report

SAEA06Robinson
10. 04. 2008
0 views

SAEA06Robinson

Larose
09. 04. 2008
0 views

Larose

dairybreeds
19. 10. 2007
0 views

dairybreeds

hex
18. 09. 2007
0 views

hex

infocom2001sfb
18. 09. 2007
0 views

infocom2001sfb

2003 Student Info System IBM
18. 09. 2007
0 views

2003 Student Info System IBM

vfpweb
18. 09. 2007
0 views

vfpweb

Fine Art and Literature
13. 10. 2007
0 views

Fine Art and Literature

cell3
15. 10. 2007
0 views

cell3

opel
19. 10. 2007
0 views

opel

horrocks
23. 10. 2007
0 views

horrocks

yang45
15. 10. 2007
0 views

yang45

GGFpart2
28. 11. 2007
0 views

GGFpart2

Sunken backbone game
10. 10. 2007
0 views

Sunken backbone game

BrandtPadua
16. 10. 2007
0 views

BrandtPadua

Lectures4 5 Ch2
07. 11. 2007
0 views

Lectures4 5 Ch2

vugia emerging
23. 10. 2007
0 views

vugia emerging

1a co clustering
19. 11. 2007
0 views

1a co clustering

mobopts 5
01. 12. 2007
0 views

mobopts 5

majoranastatus
10. 12. 2007
0 views

majoranastatus

Northern Renaissance Art
14. 12. 2007
0 views

Northern Renaissance Art

world Hunger
13. 08. 2007
0 views

world Hunger

unconscious Origins
13. 08. 2007
0 views

unconscious Origins

Vending Ala Carte
13. 08. 2007
0 views

Vending Ala Carte

weaning mice
13. 08. 2007
0 views

weaning mice

Xiushi Yang
13. 08. 2007
0 views

Xiushi Yang

LarsonWelcome
16. 10. 2007
0 views

LarsonWelcome

Ken stellar halo
15. 11. 2007
0 views

Ken stellar halo

African Union 2050
23. 12. 2007
0 views

African Union 2050

frfin
12. 10. 2007
0 views

frfin

Bhutan Hunger presentation RCC
04. 01. 2008
0 views

Bhutan Hunger presentation RCC

10 31 05 chaps 15 16
02. 11. 2007
0 views

10 31 05 chaps 15 16

HAtrash
15. 10. 2007
0 views

HAtrash

gti pmgti
24. 10. 2007
0 views

gti pmgti

Uniform Wear
18. 09. 2007
0 views

Uniform Wear

Lsn 6 Maya and Inca
20. 11. 2007
0 views

Lsn 6 Maya and Inca

monster
21. 11. 2007
0 views

monster

campusmap
28. 12. 2007
0 views

campusmap

wolson presentation
17. 10. 2007
0 views

wolson presentation

thurston
09. 10. 2007
0 views

thurston

compfpm flood plain functions
03. 01. 2008
0 views

compfpm flood plain functions

jeff kephart 11 03
18. 09. 2007
0 views

jeff kephart 11 03

LACEApresJZ1
26. 10. 2007
0 views

LACEApresJZ1

Wedding PP Presntation attach
27. 11. 2007
0 views

Wedding PP Presntation attach

RHCh1
20. 02. 2008
0 views

RHCh1

MATERIAL HANDLING PREVIEW
26. 02. 2008
0 views

MATERIAL HANDLING PREVIEW

unaids
13. 08. 2007
0 views

unaids

tgs04b
18. 09. 2007
0 views

tgs04b

about
28. 09. 2007
0 views

about

CPPStudyPhysicalProt ection
19. 11. 2007
0 views

CPPStudyPhysicalProt ection

nliwiSCS
12. 10. 2007
0 views

nliwiSCS

TurfBMP81704
14. 02. 2008
0 views

TurfBMP81704

CAlbala
22. 10. 2007
0 views

CAlbala

LT SLIDE show
11. 03. 2008
0 views

LT SLIDE show

marie curie jenam june 2005
13. 03. 2008
0 views

marie curie jenam june 2005

volcanoes group5
25. 03. 2008
0 views

volcanoes group5

gusev
15. 10. 2007
0 views

gusev

Parent Presentation predators
01. 01. 2008
0 views

Parent Presentation predators

Williams Tanzania
13. 08. 2007
0 views

Williams Tanzania

PrelimI
07. 10. 2007
0 views

PrelimI

personalities
12. 10. 2007
0 views

personalities

MeetingFreightDataCh allenges
28. 02. 2008
0 views

MeetingFreightDataCh allenges

04 19 SW
29. 10. 2007
0 views

04 19 SW

APP The American Experience WK3
17. 12. 2007
0 views

APP The American Experience WK3

062507
04. 03. 2008
0 views

062507

wedekind
08. 10. 2007
0 views

wedekind

IZMO CONCIERGE
30. 10. 2007
0 views

IZMO CONCIERGE

eh wellseptic
07. 11. 2007
0 views

eh wellseptic

20070114 sanog9 apnic update
27. 03. 2008
0 views

20070114 sanog9 apnic update

ATCNewswireCatalogue EN Q207
02. 10. 2007
0 views

ATCNewswireCatalogue EN Q207

db pres okutani whois
09. 10. 2007
0 views

db pres okutani whois

hotchips 2004 motes
18. 06. 2007
0 views

hotchips 2004 motes

gww sid july27
18. 06. 2007
0 views

gww sid july27

EMS Stake holders
18. 06. 2007
0 views

EMS Stake holders

edinburgh condor tutorial
18. 06. 2007
0 views

edinburgh condor tutorial

dztalk 3
18. 06. 2007
0 views

dztalk 3

dw olap
18. 06. 2007
0 views

dw olap

Digital Photos Hitchcock
18. 06. 2007
0 views

Digital Photos Hitchcock

DGov transform wo notes web
18. 06. 2007
0 views

DGov transform wo notes web

defense
18. 06. 2007
0 views

defense

palais 04
18. 09. 2007
0 views

palais 04

chop06
29. 10. 2007
0 views

chop06

MISR images Aug2001
21. 10. 2007
0 views

MISR images Aug2001

PresentacionGobCorp2 003
22. 10. 2007
0 views

PresentacionGobCorp2 003

cmc2q06
18. 09. 2007
0 views

cmc2q06

AfricanAmericans A Z
03. 10. 2007
0 views

AfricanAmericans A Z

Proper KeyBoarding Technique
15. 06. 2007
0 views

Proper KeyBoarding Technique

Dinosaurs
15. 06. 2007
0 views

Dinosaurs

Memories
15. 06. 2007
0 views

Memories

Like - Having Different Hobbies
15. 06. 2007
0 views

Like - Having Different Hobbies

humanity
15. 06. 2007
0 views

humanity

Volcanoes are Hot Stuff
15. 06. 2007
0 views

Volcanoes are Hot Stuff

China2005NoAnimation
23. 10. 2007
0 views

China2005NoAnimation

BTL Statistics2005
18. 09. 2007
0 views

BTL Statistics2005

Dillon
18. 06. 2007
0 views

Dillon

infovis03 talk slides
18. 09. 2007
0 views

infovis03 talk slides

Block 6 Basler Ausschuss
16. 10. 2007
0 views

Block 6 Basler Ausschuss

scarlett 28oct05
18. 09. 2007
0 views

scarlett 28oct05

barrier
18. 09. 2007
0 views

barrier

SNIMA BTP
24. 10. 2007
0 views

SNIMA BTP

familyweek3
24. 02. 2008
0 views

familyweek3

rutkowska bheurope2006
18. 09. 2007
0 views

rutkowska bheurope2006

ATA2007 US MA MReyna
23. 10. 2007
0 views

ATA2007 US MA MReyna

P Jonson AIC
18. 10. 2007
0 views

P Jonson AIC

Denver 05b
18. 06. 2007
0 views

Denver 05b

6 WP4 TRT
20. 03. 2008
0 views

6 WP4 TRT

Enigma1
31. 12. 2007
0 views

Enigma1

P416 Lec5 S07
27. 09. 2007
0 views

P416 Lec5 S07

mulligan
18. 09. 2007
0 views

mulligan