ACM SRC poster: from days to seconds: scalable parallel algorithm for motion planning
Conference Paper
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
Tliis work presents a scalable framework for parallelizing sampling ha,sed motion planning algorithms. The frame work subdivides the configuration, space (C-space) into re gions and uses (sequential) sampling-based planners to build roadmaps in each region. The regional roadraaps are later connected lo form a roadmap of the entire free space. By subdividing the space, we reduce ike work and inter-processor conumnheation associated with nearest neighbor ealeula-tion, a critical drawback and bottleneck to scalability in existing parallel motion planning methods. We show that our method is general enough to handle a ?variety of planning schemes, including the popular Probabilistic Roadmap (PRM) and Rapidly-exploring Random Trees (RRT) algoritluns. We compare our approach to two other existing parallel algorithms and demonstrate thai our approach achieves better and more scalable performance. Our approach achieves almost linear scalability to hundreds of processors on a 2400-eore Linux cluster and over a thousand core on a. Cray XE6 petaseale machine.
name of conference
Proceedings of the 2011 companion on High Performance Computing Networking, Storage and Analysis Companion
