icra02

60 %
40 %
Information about icra02
Product-Training-Manuals

Published on June 19, 2007

Author: Mahugani

Source: authorstream.com

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

Add a comment

Related presentations

Related pages

gki.informatik.uni-freiburg.de

gki.informatik.uni-freiburg.de
Read more

Dynamic Decentralized Area Partitioning for Cooperating ...

Dynamic Decentralized Area Partitioning for Cooperating Cleaning Robots Markus J¨ager Bernhard Nebel Corporate Technology Institut fur¨ Informatik
Read more

Robotics 8 DC Experiments in Visual Feedback Control of ...

Procaedings of the 2002 IEEE lntemational Conference on Robotics 8 Automation Washington, DC May 2002 Experiments in Visual Feedback Control
Read more

Learning Motion Patterns - uni-freiburg.de

Learning Motion Patterns of Persons for Mobile Service Robots Maren Bennewitz yWolfram Burgard Sebastian Thrunz yDepartment of Computer Science, University ...
Read more

Real Time Visualization of Robot State with Mobile Virtual ...

Amstutz & Fagg; Proceedings of the IEEE International Conference on Robotics and Automation (ICRA’02) 1 Real Time Visualization of Robot State with ...
Read more

Mobile Robot Self-Localization in Large-Scale Environments

Mobile Robot Self-Localization in Large-Scale Environments Axel Lankenau, Thomas Rofer¨ Bremer Institut fur Sichere Systeme, TZI, FB3, Universit¨ at ...
Read more

Robust Vision-based Localization for Mobile Robots Using ...

Robust Vision-based Localization for Mobile Robots Using an Image Retrieval System Based on Invariant Features Jurgen Wolf¨ y Wolfram Burgard zHans Burkhardt
Read more

A Versatile Depalletizer of Boxes Based on Range Imagery

A Versatile Depalletizer of Boxes Based on Range Imagery Dimitrios Katsoulasy Lothar Bergeny Lambis Tassakosz yComputer Science Department, University of ...
Read more

Collaborative Online Teleoperation with Spatial Dynamic ...

Collaborative Online Teleoperation with Spatial Dynamic Voting and a Human “Tele-Actor” ∗ K. Goldberg, D. Song, Y. Khor, D. Pescovitz, A. Levandowski,
Read more

In Proceedings of the IEEE International Conference on ...

In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA02) (2002)
Read more