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

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).

An imbalanced environment and roadmap graph node distribution.
(b) Before
(c) After
(b) before and (c) after rebalancing for parallel PRM.
Figure 3: Experimental validation of (a) measure of load imbalance and (b) potential improvement in model environment.
Figure 4: Evaluation of (a) execution time and (b) coefficient of variation and (c) load distribution for PRM on HOPPER using med-cube.

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)

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

Related Projects

Parasol Home | Research | People | General info | Seminars | Resources  

Parasol Laboratory, 425 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112 
parasol-admin@cse.tamu.edu      Phone 979.458.0722     Fax 979.458.0718 

Department of Computer Science and Engineering | Dwight Look College of 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