Access Restriction

Author Kleinbort, M. ♦ Salzman, O. ♦ Halperin, D.
Source IEEE Xplore Digital Library
Content type Text
Publisher Institute of Electrical and Electronics Engineers, Inc. (IEEE)
File Format PDF
Copyright Year ©2015
Language English
Subject Domain (in DDC) Technology ♦ Engineering & allied operations ♦ Other branches of engineering
Subject Keyword Robots ♦ Motion-planning ♦ Approximation algorithms ♦ Collision avoidance ♦ Arrays
Abstract Sampling-based motion-planning algorithms typically rely on nearest-neighbor (NN) queries when constructing a roadmap. Recent results suggest that in various settings NN queries may be the computational bottleneck of such algorithms. Moreover, in several asymptotically-optimal algorithms these NN queries are of a specific form: Given a set of points and a radius r report all pairs of points whose distance is at most r. This calls for an application-specific NN data structure tailored to efficiently answering this type of queries. Randomly transformed grids (RTG) were recently proposed by Aiger et al. [1] as a tool to answer such queries in Euclidean spaces and have been shown to outperform common implementations of NN data structures for this type of queries. In this work we employ RTG for sampling-based motion-planning algorithms and describe an efficient implementation of the approach. We show that for motion planning, RTG allow for faster convergence to high-quality solutions when compared to existing NN data structures. Additionally, RTG enable significantly shorter construction times for batched-PRM variants; specifically, we demonstrate a speedup by a factor of two to three for some scenarios.
Description Author affiliation: Blavatnik Sch. of Comput. Sci., Tel-Aviv Univ., Tel-Aviv, Israel (Kleinbort, M.; Salzman, O.; Halperin, D.)
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research ♦ Reading
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2015-05-26
Publisher Place USA
Rights Holder Institute of Electrical and Electronics Engineers, Inc. (IEEE)
e-ISBN 9781479969234
Size (in Bytes) 425.56 kB
Page Count 6
Starting Page 2985
Ending Page 2990

Source: IEEE Xplore Digital Library