Home research People General Info Seminars Resources Intranet
| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News
Algorithms & Applications Group
Parallel Motion Planning
Parallel Algorithms for Motion Planning
Distributed RRT
Load Balancing for Parallel Motion Planning
Parallelizing Protein Folding

Here are our projects. Click on the sliding image to learn more.

In this project, we are developing parallel algorithms for motion planning applications. We are particularly interested in parallelizing probabilistic roadmap motion planning methods (PRMs), and have shown that significant, scalable speedups can be obtained with relatively little effort on the part of the developer. In our initial work, we demonstrated that PRMs are "embarrassingly parallel". In later work, we used STAPL, the Standard Template Adaptive Parallel Library, to produce a platform independent parallel implementation. Our recent work focuses on scalable framework for parallelizing sampling-based motion planning algorithms. This work builds on the initial work and extend it such that any sampling-based motion planning algorithm is supported.

PRMs consist of two phases, node generation and node connection, both of which can be easily parallelized. To generate n random nodes in parallel, we simply ask each of the p processors to generate n/p of them. Effective parallelization of the connection phase is essential to obtain scalable speedups since this typically accounts for 98% of the sequential computation time. A simple sequential connection algorithm attempts to connect every node to its k nearest neighbors. Suppose we group the n nodes into p sets, one for each processor. Then, a simple parallel solution is for each processor to compute the k nearest neighbors for its set of nodes and attempt the connections.

Parallelization with STAPL

We use the Standard Template Adaptive Parallel Library (STAPL) to parallelize our existing motion planning and protein folding code. STAPL allows for easy transition from sequential code to parallel code by extending the ANSI C++ Standard Template Library, and it provides portable efficiency to different systems, both shared memory and distributed memory models, without requiring user code modification. We simply represent the roadmap in a pGraph, a parallel, distributed data structure provided by STAPL. The pGraph manages all communication for the user.

Papers

Parallel Algorithms for Motion Planning

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)

Distributed RRT

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)

Blind RRT: A Probabilistically Complete Distributed RRT, Cesar Rodriguez, Jory Denny, Sam Jacobs, Shawna L. Thomas, Nancy M. Amato, In Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS), pp. 1758 - 1765, Tokyo, Japan, Nov 2013.
Proceedings(ps, pdf, abstract)

A Scalable Distributed RRT for Motion Planning, Sam Ade Jacobs, Nicholas Stradford, Cesar Rodriguez, Shawna Thomas, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 5088-5095, Karlsruhe, Germany, May 2013.
Proceedings(ps, pdf, abstract)

Load Balancing for Parallel Motion Planning

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)

Parallelizing Protein Folding

Parallel Protein Folding with STAPL, Shawna Thomas, Nancy M. Amato, In Proc. IEEE Int. Wkshp. on High Performance Computational Biology, Santa Fe, NM, Apr 2004.
Proceedings(ps, pdf, abstract)

Probabilistic Roadmap Methods are Embarrassingly Parallel, Nancy M. Amato, Lucia K. Dale, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 688-694, Detroit, Michigan, USA, May 1999.
Proceedings(ps, pdf, abstract)