icra02

Information about icra02

Published on June 19, 2007

Author: Mahugani

Source: authorstream.com

Content

Efficient Nearest Neighbor Searching for Motion Planning:  Efficient Nearest Neighbor Searching for Motion Planning Anna Atramentov Dept. of Computer Science Iowa State University Ames, IA, USA Steven M. LaValle Dept. of Computer Science University of Illinois Urbana, IL, USA Support provided in part by an NSF CAREER award. Motivation:  Motivation Statistics Pattern recognition Machine Learning Nearest neighbor searching is a fundamental problem in many applications: PRM-based methods RRT-based methods In motion planning the following algorithms rely heavily on nearest neighbor algorithms: Basic Motion Planning Problem:  Basic Motion Planning Problem Given: 2D or 3D world Geometric models of a robot and obstacles Configuration space Initial and goal configurations Task: Compute a collision free path that connects initial and goal configurations Slide4:  Probabilistic roadmap approaches (Kavraki, Svestka, Latombe, Overmars, 1994) The precomputation phase consists of the following steps: Generate vertices in configuration space at random Connect close vertices Return resulting graph Obstacle-Based PRM (Amato, Wu, 1996); Sensor-based PRM (Yu, Gupta, 1998); Gaussian PRM (Boor, Overmars, van der Stappen, 1999); Medial axis PRMs (Wilmarth, Amato, Stiller, 1999; Psiula, Hoff, Lin, Manocha, 2000; Kavraki, Guibas, 2000); Contact space PRM (Ji, Xiao, 2000); Closed-chain PRMs (LaValle, Yakey, Kavraki, 1999; Han, Amato 2000); Lazy PRM (Bohlin, Kavraki, 2000); PRM for changing environments (Leven, Hutchinson, 2000); Visibility PRM (Simeon, Laumond, Nissoux, 2000). The query phase: Connect initial and goal to graph Search the graph Rapidly-exploring random tree approaches:  Rapidly-exploring random tree approaches GENERATE_RRT(xinit, K, t) T.init(xinit); For k = 1 to K do xrand  RANDOM_STATE(); xnear  NEAREST_NEIGHBOR(xrand, T); u  SELECT_INTPUT(xrand, xnear); xnew  NEW_STATE(xnear, u, t); T.add_vertex(xnew); T.add_edge(xnear, xnew, u); Return T; xnear xrand xnew LaValle, 1998; LaValle, Kuffner, 1999, 2000; Frazzoli, Dahleh, Feron, 2000; Toussaint, Basar, Bullo, 2000; Vallejo, Jones, Amato, 2000; Strady, Laumond, 2000; Mayeux, Simeon, 2000; Karatas, Bullo, 2001; Li, Chang, 2001; Kuffner, Nishiwaki, Kagami, Inaba, Inoue, 2000, 2001; Williams, Kim, Hofbaur, How, Kennell, Loy, Ragno, Stedl, Walcott, 2001; Carpin, Pagello, 2002. The result is a tree rooted at xinit: Goals:  Goals Existing nearest neighbor packages: ANN (U. of Maryland) Ranger (SUNY Stony Brook) Problem: They only work for Rn. Configuration spaces that usually arise in motion planning are products of R, S1 and projective spaces. Theoretical results: Problem: Difficulty of implementation P. Indyk, R. Motwani, 1998; P. Indyk, 1998, 1999; Our goal: Design simple and efficient algorithm for finding nearest neighbor in these topological spaces Literature on NN searching:  Literature on NN searching It is very well studied problem Kd-tree approach is very simple and efficient T. Cover, P. Hart, 1967 D. Dobkin, R. Lipton, 1976 J. Bentley, M. Shamos, 1976 S. Arya, D. Mount,  1993, 1994 M. Bern, 1993 T. Chan,  1997 J. Kleinberg,  1997 K. Clarkson, 1988, 1994, 1997 P. Agarwal, J. Erickson, 1998 P. Indyk, R. Motwani, 1998 E. Kushilevitz, R. Ostrovsky, Y. Rabani, 1998 P. Indyk, 1998, 1999 A. Borodin, R. Ostrovsky, Y. Rabani,  1999 Problem Formulation:  Problem Formulation Given a d-dimensional manifold, T, represented as a polygonal schema, and a set of data points in T. Preprocess these points so that, for any query point q  T, the nearest data point to q can be found quickly. The manifolds of interest: Euclidean one-space, represented by (0,1)  R. Circle, represented by [0,1], in which 0  1 by identification. P3, represented by [0, 1]3 with antipodal points identified. Examples of 4-sided polygonal schemas: cylinder torus projective plane Example: a torus:  Example: a torus 4 7 6 5 1 3 2 9 8 10 11 q Algorithm presentation:  Algorithm presentation Overview of the kd-tree algorithm Modification of kd-tree algorithm to handle topology Analysis of the algorithm Experimental results Kd-trees:  Kd-trees The kd-tree is a powerful data structure that is based on recursively subdividing a set of points with alternating axis-aligned hyperplanes. The classical kd-tree uses O(dn lgn) precomputation time, O(dn) space and answers queries in time logarithmic in n, but exponential in d. l1 l8 l2 l3 l4 l5 l7 l6 l9 l10 Kd-trees. Construction:  Kd-trees. Construction l5 l9 l6 l3 l10 l7 l4 l8 l2 l1 l8 l2 l3 l4 l5 l7 l6 l9 l10 Kd-trees. Query:  Kd-trees. Query 4 7 6 5 1 3 2 9 8 10 11 l5 l9 l6 l3 l10 l7 l4 l8 l2 l1 l8 l2 l3 l4 l5 l7 l6 l9 l10 Algorithm Presentation:  Algorithm Presentation Analysis of the Algorithm:  Analysis of the Algorithm Proposition 1. The algorithm correctly returns the nearest neighbor. Proof idea: The points of kd-tree not visited by an algorithm will always be further from the query point then some point already visited. Proposition 2. For n points in dimension d, the construction time is O(dn lgn), the space is O(dn), and the query time is logarithmic in n, but exponential in d. Proof idea: This follows directly from the well-known complexity of the basic kd-tree. Experiments:  Experiments For 50,000 data points 100 queries were made: ExperimentsPRM method:  Experiments PRM method ExperimentsRRT method:  Experiments RRT method ExperimentsRRT method:  Experiments RRT method Conclusion:  Conclusion We extended kd-tree to handle topology of the configuration space We have presented simple and efficient algorithm We have developed software for this algorithm which will be included in Motion Strategy Library (http://msl.cs.uiuc.edu/msl/) Future Work Extension to more efficient kd-trees Extension to different topological spaces Extension to different metric spaces

Related presentations


Other presentations created by Mahugani

Exploring the Deep Web
12. 03. 2008
0 views

Exploring the Deep Web

Moving Mountains
02. 10. 2007
0 views

Moving Mountains

dustbowl
10. 10. 2007
0 views

dustbowl

The Internet China
12. 10. 2007
0 views

The Internet China

shen 1
12. 10. 2007
0 views

shen 1

Triumph of Bolshevism
12. 10. 2007
0 views

Triumph of Bolshevism

Kukovecz
15. 10. 2007
0 views

Kukovecz

09 Panama s ppt
22. 10. 2007
0 views

09 Panama s ppt

Common By Product Feeds
04. 10. 2007
0 views

Common By Product Feeds

Dissertation Writing comms ug
27. 11. 2007
0 views

Dissertation Writing comms ug

TT
27. 11. 2007
0 views

TT

black holes v2
28. 11. 2007
0 views

black holes v2

Production of Calla Lily
07. 12. 2007
0 views

Production of Calla Lily

Water Track 8 7 15 051
07. 11. 2007
0 views

Water Track 8 7 15 051

PVC Toronto talk
16. 11. 2007
0 views

PVC Toronto talk

2022lecture2
19. 11. 2007
0 views

2022lecture2

Robertson
03. 10. 2007
0 views

Robertson

20050922 Crafoord Symposium
29. 08. 2007
0 views

20050922 Crafoord Symposium

field mmr naga
31. 12. 2007
0 views

field mmr naga

Anthony Kelly International
02. 01. 2008
0 views

Anthony Kelly International

fy2004 mfc construction
04. 01. 2008
0 views

fy2004 mfc construction

NASC PresentHanson
08. 08. 2007
0 views

NASC PresentHanson

Nicosia Raymond Pawson
08. 08. 2007
0 views

Nicosia Raymond Pawson

Methamphetamine final10 05
08. 08. 2007
0 views

Methamphetamine final10 05

ppt43
16. 10. 2007
0 views

ppt43

McCarthy Mitchell
29. 08. 2007
0 views

McCarthy Mitchell

Update FutureDirection LRago
22. 10. 2007
0 views

Update FutureDirection LRago

gef 160306
23. 10. 2007
0 views

gef 160306

IT Trends 2005 2010
14. 11. 2007
0 views

IT Trends 2005 2010

rec pond mgnt compressed
07. 01. 2008
0 views

rec pond mgnt compressed

Sci Case II
29. 08. 2007
0 views

Sci Case II

markenklima index q1 2005
05. 01. 2008
0 views

markenklima index q1 2005

yalenov2006
29. 08. 2007
0 views

yalenov2006

media 4917
08. 08. 2007
0 views

media 4917

gatorsncrocs
12. 10. 2007
0 views

gatorsncrocs

Eradicating Systemic Poverty
29. 11. 2007
0 views

Eradicating Systemic Poverty

Kennedy obesity 0904
08. 08. 2007
0 views

Kennedy obesity 0904

jsimon santacruz
29. 08. 2007
0 views

jsimon santacruz

9 0568 rusack r
20. 11. 2007
0 views

9 0568 rusack r

soc100ch10Corepwrpt
19. 02. 2008
0 views

soc100ch10Corepwrpt

Edward Albee
24. 02. 2008
0 views

Edward Albee

AFCEA NOVA Breakfast7Sept07v1
06. 03. 2008
0 views

AFCEA NOVA Breakfast7Sept07v1

Lakeside2
26. 03. 2008
0 views

Lakeside2

sHansen
29. 08. 2007
0 views

sHansen

Tectonics Terrestrial Planets2
07. 04. 2008
0 views

Tectonics Terrestrial Planets2

Sept SECC
02. 11. 2007
0 views

Sept SECC

Hercules
28. 03. 2008
0 views

Hercules

deprez presentation 12 1 05
30. 03. 2008
0 views

deprez presentation 12 1 05

HARIPARSAD Ishwarie 2
09. 04. 2008
0 views

HARIPARSAD Ishwarie 2

Beaulieu
10. 04. 2008
0 views

Beaulieu

sings2mw
29. 08. 2007
0 views

sings2mw

molgas twong
29. 08. 2007
0 views

molgas twong

newman1
14. 04. 2008
0 views

newman1

session 25 V2
17. 04. 2008
0 views

session 25 V2

Citel
22. 04. 2008
0 views

Citel

ICHEP 04 Barr Higgs
19. 06. 2007
0 views

ICHEP 04 Barr Higgs

IBERs and e Theses
19. 06. 2007
0 views

IBERs and e Theses

HS P2P Liao
19. 06. 2007
0 views

HS P2P Liao

he b
19. 06. 2007
0 views

he b

HB2004
19. 06. 2007
0 views

HB2004

Hartenstein Oerebro03 pt1
19. 06. 2007
0 views

Hartenstein Oerebro03 pt1

Grid InteropSupport
19. 06. 2007
0 views

Grid InteropSupport

Grid Interop
19. 06. 2007
0 views

Grid Interop

grid 06talk
19. 06. 2007
0 views

grid 06talk

wednesday
29. 08. 2007
0 views

wednesday

comer5e ch08 HO
15. 11. 2007
0 views

comer5e ch08 HO

SAG YinG 9 Jan New
03. 01. 2008
0 views

SAG YinG 9 Jan New

02 Cattle2
26. 11. 2007
0 views

02 Cattle2

Grid Shib uk april05
19. 06. 2007
0 views

Grid Shib uk april05

J Acar
14. 03. 2008
0 views

J Acar

20061130 woodling
30. 12. 2007
0 views

20061130 woodling

ch02exoh
07. 01. 2008
0 views

ch02exoh

Choose your way carefully
03. 10. 2007
0 views

Choose your way carefully

4 vista
16. 06. 2007
0 views

4 vista

33233 11162218 S
16. 06. 2007
0 views

33233 11162218 S

23
16. 06. 2007
0 views

23

2007 tips tricks
16. 06. 2007
0 views

2007 tips tricks

19b
16. 06. 2007
0 views

19b

EPL Membership
16. 06. 2007
0 views

EPL Membership

Entire Gra duation Slideshow
16. 06. 2007
0 views

Entire Gra duation Slideshow

elley web graphics
16. 06. 2007
0 views

elley web graphics

A Loose Confederation
14. 12. 2007
0 views

A Loose Confederation

employee 2004
16. 06. 2007
0 views

employee 2004

Obesity 1
08. 08. 2007
0 views

Obesity 1

Active Kill Disk
19. 06. 2007
0 views

Active Kill Disk

teall cost 3 ch16
24. 02. 2008
0 views

teall cost 3 ch16

CFA05
29. 08. 2007
0 views

CFA05

gemini sab
29. 08. 2007
0 views

gemini sab

NINDS Audience Report
08. 08. 2007
0 views

NINDS Audience Report

mm1
29. 08. 2007
0 views

mm1

ENGD POWERPOINT
16. 06. 2007
0 views

ENGD POWERPOINT

I3C BSML July2002
19. 06. 2007
0 views

I3C BSML July2002

igt 3
04. 03. 2008
0 views

igt 3

MassesofGalaxies
29. 08. 2007
0 views

MassesofGalaxies