Home research People General Info Seminars Resources Intranet
| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News
Algorithms & Applications Group
Scalable Framework for Parallelizing Sampling-Based Motion Planning Algorithms

Our recent work focuses on scalable method for parallelizing sampling based motion planning algorithms. The method subdivides the configuration 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 calculations, 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) algorithms. We compare our approach (pSBMP-PRM and pSBMP-RRT) to two other existing parallel algorithms (pPRM and pSRT) and demonstrate that our approach achieves better and more scalable performance (shown in Figure 1). Our approach achieves almost linear scalability to hundreds of cores (shown in Figure 2) on a 2400 cores Linux cluster of 13.8 tera-flop peak performance at Texas A&M University and over a thousand cores (shown in Figure 3) on a Cray XE6 petascale machine with peak performance of 1.288 peta-flops and 153,216 cores at Lawrence Berkeley National Laboratory.

Figure 1: Performance Comparison with Existing Approaches
Figure 2: Scalability on Linux Cluster
Figure 3: Scalability on Cray XE6 Machine

Using Load Balancing to Scalably Parallelize Sampling-Based Motion Planning Algorithms, Adam Fidel, Sam Ade Jacobs, Shishir Sharma, Nancy M. Amato, Lawrence Rauchwerger, In Proc. Int. Par. and Dist. Proc. Symp. (IPDPS), Phoenix, Arizona, USA, May 2014.
Proceedings(pdf, abstract)

A Scalable Framework for Parallelizing Sampling-Based Motion Planning Algorithms, Sam Ade Jacobs, Ph.D. Thesis, Department of Computer Science and Engineering, Texas A&M University, May 2014.
Ph.D. Thesis(pdf, abstract)

Load Balancing Techniques for Scalable Parallelization of Sampling-Based Motion Planning Algorithms, Adam Fidel, Sam Ade Jacobs, Shishir Sharma, Lawrence Rauchwerger, Nancy M. Amato, Technical Report, TR13-002 , Parasol Laboratory, Department of Computer Science, Texas A&M University, Mar 2013.
Technical Report(pdf, abstract)

A Scalable Method for Parallelizing Sampling-Based Motion Planning Algorithms, Sam Ade Jacobs, Kasra Manavi, Juan Burgos, Jory Denny, Shawna Thomas, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 2529-2536, St. Paul, Minnesota, USA, May 2012.
Proceedings(ps, pdf, abstract)

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

Supported by King Abdullah University of Science and Technology (KAUST), NSF, Dept. of Education, Texas Higher Education Coordinating Board

Project Alumni:Juan Burgos,Sam Ade Jacobs,Kasra Manavi,Shishir Sharma

Related Projects
STAPL
Protein Folding