Home research People General Info Seminars Resources Intranet

Sam Ade Jacobs, Nancy M. Amato, "From Days to Seconds: Scalable Parallel Algorithms for Motion Planning," In ACM Student Research Compet, Conf. on High Performance Computing Networking, Storage and Analysis Companion Proceedings, Seattle, Washington, USA, Nov 2011.
Proceedings(pdf, abstract)

This work presents a scalable framework for parallelizing sampling based motion planning algorithms. The framework subdivides the con figuration space (C-space) into regions and uses (sequential) sampling-based planners to build roadmaps in each region. The regional roadmaps are later connected to form a roadmap of the entire free space. By subdividing the space, we reduce the work and inter-processor communication associated with nearest neighbor calculation, 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 Prob- abilistic Roadmap (PRM) and Rapidly-exploring Random Trees (RRT) algorithms. We compare our approach to two other existing parallel algorithms and demonstrate that our approach achieves better and more scalable performance. Our approach achieves almost linear scalability to hundreds of processors on a 2400-core Linux cluster and over a thousand core on a Cray XE6 petascale machine.