The need to solve large problems within an acceptable amount of time is primary boon of parallel computing. Substantial resources in time and hardware are required to solve complex applications, therfore, it is neceesary to explore efficient methods for parallel processing. In this project, we worked on methods for parallelizing representatives of the two major classes of sampling-based motion planning algorithms that are based on uniform workspace subdivision. By subdividing the space and restricting the locality of connection attempts, we reduce the work and interprocessor communication associated with nearest neighbor search computations - a well known bottleneck in parallelizing sampling-based motion planning algorithms.
We proposed two techniques to address the problems of load imbalance. The first is a bulk-synchronous redistribution technique that redistributes regions among processors so that they have a more balanced distribution of data. The method approximates the amount of work a region will requre that is based on the complexity of a region and use it to attempt to balance work across processors, while also preserving the spatial geometry of the subdivision. The second approach is an adaptive work-stealing approach that permantently migrates both the region and the work related to it to improve the load balance.
Figure 1: When uniformly subdividing an environment as shown in our 2D example in (a), we divide along the environment's workspace degrees of freedom, with some overlap. Each region is then mapped by the Region Graph as seen in (b).
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.
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)
Supported by King Abdullah University of Science and Technology (KAUST), NSF, Dept. of Education, Texas Higher Education Coordinating Board
Project Alumni:Sam Ade Jacobs,Shishir Sharma
Parasol Home | Research | People | General info | Seminars | Resources
Parasol Laboratory, 425 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112
firstname.lastname@example.org Phone 979.458.0722 Fax 979.458.0718
Department of Computer Science and Engineering | Dwight Look College of Engineering | Texas A&M University
Privacy statement: Computer Science and Engineering Engineering TAMU
Web Accessibility Policy and Law - Web Accessibility and Usability Standards - Contact Webmaster