Scalable Parallelization of Sampling-Based Planning Algorithms
Related Projects:  Robot Task and Motion Planning    Parallel & Distributed Planning Methods    STAPL: Standard Template Adaptive Parallel Library    Parallel Hierarchical Planning Algorithms    Parallelizing Protein Folding       Robots on the (Mobile) Edge and in the Hybrid Cloud  

We have developed a scalable method for parallelizing sampling-based 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 previous parallel motion planning methods.

There are two main types of sampling-based planning methods, graph-based methods used when multiple queries will be performed in the same environment (e.g., Probabilistic Roadmap Methods, or PRMs) and tree-based approached most suitable for single query settings (e.g., Rapidly-explorign Random Trees, or RRTs). We show how both types of methods can be parallelized efficiently.



Parallelizing Graph-based Methods. The multi-query graph-based methods (e.g., PRMs) build a graph during preprocessing which is later used to answer many queries. The constuction of the graph consists of two main 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.

Parallelizing Tree-based Methods. The single-query tree-based methods (e.g., RRTs) have been more challenging to parallelize efficiently due to the sequential nature of the tree growth. In one approach, Radial RRT, we demonstrated a scalable algorithm that subdivides the space radially into regions to increase the computation locality. However, if an obstacle completely blocks RRT growth in a region, the planning space is not covered and the method is thus not probabilistically complete. We addressed this with another version, Blind RRT, which ignores obstacles during initial growth to efficiently explore the entire space. Because obstacles are ignored, free components of the tree become disconnected and fragmented. Blind RRT merges parts of the tree that have become disconnected from the root. We show how this algorithm can be applied to the Radial RRT framework allowing both scalability and effectiveness in motion planning. This method is a probabilistically complete approach to parallel RRTs. We show that our method not only scales but also overcomes the motion planning limitations that Radial RRT has in a series of difficult motion planning tasks.

Distributed RRT Illustration

Figure 1: Example of a radial subdivision for a 2D CSpace from a root node. Each process
concurrently builds a subtree from the root and attempts to connect to goal.

Results. We show that our method (pSBMP-X) is general enough to handle both graph-based (pSBMP-PRM) and tree-based (pSBMP-RRT) approaches. 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

Load Balancing Strategies. These strategies based on uniform spatial subdivision techniques for parallelizing sampling-based motion planning algorithms can scale well. However, such methods are prone to load imbalance, as planning time depends on region characteristics and, for most problems, the heterogeneity of the sub problems increases as the number of processors increases. We introduced two techniques to address load imbalance in the parallelization of sampling-based motion planning algorithms: an adaptive work stealing approach and bulk-synchronous redistribution. 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.

Our results show that applying these techniques to representatives of the two major classes of parallel sampling-based motion planning algorithms, probabilistic roadmaps and rapidly-exploring random trees, results in a more scalable and load-balanced computation on more than 3,000 cores.

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.
(a)
(b)
Figure 3: Experimental validation of (a) measure of load imbalance and (b) potential improvement in model environment.
(a)
(b)
(c)
Figure 4: Evaluation of (a) execution time and (b) coefficient of variation and (c) load distribution for PRM on HOPPER using med-cube.


Related Publications

Parallel Hierarchical Composition Conflict-Based Search, Hannah Lee, James Motes, Marco Morales, Nancy M. Amato, IEEE/RSJ International Conference on Intelligent Robots and Systems, Vol: 6, Issue: 4, pp. 7001-7008, Prague, Czech Republic, Jul 2021. DOI: 10.1109/LRA.2021.3096476.
Keywords: Multi-Agent, Parallel Planning, Path Planning
Links : [Published]

BibTex

@article{lee2021parallel,
title={Parallel Hierarchical Composition Conflict-Based Search for Optimal Multi-Agent Pathfinding},
author={Lee, Hannah and Motes, James and Morales, Marco and Amato, Nancy M},
journal={IEEE Robotics and Automation Letters},
volume={6},
number={4},
pages={7001--7008},
year={2021},
publisher={IEEE}
}


Abstract

In this letter, we present the following optimal multi-agent pathfinding (MAPF) algorithms: Hierarchical Composition Conflict-Based Search, Parallel Hierarchical Composition Conflict-Based Search, and Dynamic Parallel Hierarchical Composition Conflict-Based Search. MAPF is the task of finding an optimal set of valid path plans for a set of agents such that no agents collide with present obstacles or each other. The presented algorithms are an extension of Conflict-Based Search (CBS), where the MAPF problem is solved by composing and merging smaller, more easily manageable subproblems. Using the information from these subproblems, the presented algorithms can more efficiently find an optimal solution. Our three presented algorithms demonstrate improved performance for optimally solving MAPF problems consisting of many agents in crowded areas while examining fewer states when compared with CBS and its variant Improved Conflict-Based Search.


The anatomy of a distributed motion planning roadmap, Sam Ade Jacobs, Nancy M. Amato, 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3019-3026, Chicago, Illinois, USA, Sep 2014. DOI: 10.1109/IROS.2014.6942979
Keywords: Motion Planning, Parallel Planning, Parallel Processing
Links : [Manuscript]

BibTex

@INPROCEEDINGS{6942979, author={S. A. {Jacobs} and N. M. {Amato}}, booktitle={2014 IEEE/RSJ International Conference on Intelligent Robots and Systems}, title={The anatomy of a distributed motion planning roadmap}, year={2014}, volume={}, number={}, pages={3019-3026}, doi={10.1109/IROS.2014.6942979}}


Abstract

In this paper, we evaluate and compare the quality and structure of roadmaps constructed from parallelizing sampling-based motion planning algorithms against that of roadmaps constructed using sequential planner. Also, we make an argument and provide experimental results that show that motion planning problems involving heterogenous environments (common in most realistic and large-scale motion planning) is a natural fit for spatial subdivision-based parallel processing. Spatial subdivision-based parallel processing approach is suited for heterogeneous environments because it allows for local adaption in solving a global problem while taking advantage of scalability that is possible with parallel processing.


Using Load Balancing to Scalably Parallelize Sampling-Based Motion Planning Algorithms, Adam Fidel, Sam Ade Jacobs, Shishir Sharma, Nancy M. Amato, Lawrence Rauchwerger, 2014 IEEE 28th International Parallel and Distributed Processing Symposium, pp. 573-582, Phoenix, AZ, USA, May 2014. DOI: 10.1109/IPDPS.2014.66
Keywords: Parallel Algorithms, Parallel Planning, Sampling-Based Motion Planning
Links : [Published]

BibTex

@INPROCEEDINGS{6877290, author={A. {Fidel} and S. A. {Jacobs} and S. {Sharma} and N. M. {Amato} and L. {Rauchwerger}}, booktitle={2014 IEEE 28th International Parallel and Distributed Processing Symposium}, title={Using Load Balancing to Scalably Parallelize Sampling-Based Motion Planning Algorithms}, year={2014}, volume={}, number={}, pages={573-582}, doi={10.1109/IPDPS.2014.66}}


Abstract

Motion planning, which is the problem of computing feasible paths in an environment for a movable object, has applications in many domains ranging from robotics, to intelligent CAD, to protein folding. The best methods for solving this PSPACE-hard problem are so-called sampling-based planners. Recent work introduced uniform spatial subdivision techniques for parallelizing sampling-based motion planning algorithms that scaled well. However, such methods are prone to load imbalance, as planning time depends on region characteristics and, for most problems, the heterogeneity of the sub problems increases as the number of processors increases. In this work, we introduce two techniques to address load imbalance in the parallelization of sampling-based motion planning algorithms: an adaptive work stealing approach and bulk-synchronous redistribution. We show that applying these techniques to representatives of the two major classes of parallel sampling-based motion planning algorithms, probabilistic roadmaps and rapidly-exploring random trees, results in a more scalable and load-balanced computation on more than 3,000 cores.


A Scalable Framework for Parallelizing Sampling-Based Motion Planning Algorithms, Samson Ade Jacobs, Doctoral Dissertation, Texas A&M University, College Station, Texas, USA, May 2014.
Keywords: Parallel Algorithms, Parallel Planning, Sampling-Based Motion Planning
Links : [Published]

BibTex

@phdthesis{jacobs2014scalable,
title={A Scalable Framework for Parallelizing Sampling-Based Motion Planning Algorithms},
author={Jacobs, Samson Ade},
year={2014}
}


Abstract

Motion planning is defined as the problem of finding a valid path taking a robot (or any movable object) from a given start configuration to a goal configuration in an environment. While motion planning has its roots in robotics, it now finds application in many other areas of scientific computing such as protein folding, drug design, virtual prototyping, computer-aided design (CAD), and computer animation. These new areas test the limits of the best sequential planners available, motivating the need for methods that can exploit parallel processing. This dissertation focuses on the design and implementation of a generic and scalable framework for parallelizing motion planning algorithms. In particular, we focus on sampling-based motion planning algorithms which are considered to be the state-of-the-art. Our work covers the two broad classes of sampling-based motion planning algorithms--the graph-based and the tree-based methods. Central to our approach is the subdivision of the planning space into regions. These regions represent sub- problems that can be processed in parallel. Solutions to the sub-problems are later combined to form a solution to the entire problem. By subdividing the planning space and restricting the locality of connection attempts to adjacent regions, we reduce the work and inter-processor communication associated with nearest neighbor calculation, a critical bottleneck for scalability in existing parallel motion planning methods. We also describe how load balancing strategies can be applied in complex environments. We present experimental results that scale to thousands of processors on different massively parallel machines for a range of motion planning problems.


Adaptive Neighbor Connection for PRMs: A Natural Fit for Heterogeneous Environments and Parallelism, Chinwe Ekenna, Sam Ade Jacobs, Shawna Thomas, Nancy M. Amato, In. Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Tokyo, Japan, Nov 2013. DOI: 10.1109/IROS.2013.6696510
Keywords: Parallel Algorithms, Parallel Planning, Sampling-Based Motion Planning
Links : [Published]

BibTex

@INPROCEEDINGS{6696510, author={C. {Ekenna} and S. A. {Jacobs} and S. {Thomas} and N. M. {Amato}}, booktitle={2013 IEEE/RSJ International Conference on Intelligent Robots and Systems}, title={Adaptive neighbor connection for PRMs: A natural fit for heterogeneous environments and parallelism}, year={2013}, volume={}, number={}, pages={1249-1256}, doi={10.1109/IROS.2013.6696510}}


Abstract

Probabilistic Roadmap Methods (PRMs) are widely used motion planning methods that sample robot configurations (nodes) and connect them to form a graph (roadmap) containing feasible trajectories. Many PRM variants propose different strategies for each of the steps and choosing among them is problem dependent. Planning in heterogeneous environments and/or on parallel machines necessitates dividing the problem into regions where these choices have to be made for each one. Hand-selecting the best method for each region becomes infeasible. In particular, there are many ways to select connection candidates, and choosing the appropriate strategy is input dependent. In this paper, we present a general connection framework that adaptively selects a neighbor finding strategy from a candidate set of options. Our framework learns which strategy to use by examining their success rates and costs. It frees the user of the burden of selecting the best strategy and allows the selection to change over time. We perform experiments on rigid bodies of varying geometry and articulated linkages up to 37 degrees of freedom. Our results show that strategy performance is indeed problem/region dependent, and our adaptive method harnesses their strengths. Over all problems studied, our method differs the least from manual selection of the best method, and if one were to manually select a single method across all problems, the performance can be quite poor. Our method is able to adapt to changing sampling density and learns different strategies for each region when the problem is partitioned for parallelism.


Blind RRT: A Probabilistically Complete Distributed RRT, Cesar Rodriguez, Jory Denny, Sam Ade Jacobs, Shawna Thomas, Nancy M. Amato, In. Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Tokyo, Japan, Nov 2013. DOI: 10.1109/IROS.2013.6696587
Keywords: Parallel Planning, Rapidly-exploring Random Tree (RRT), Sampling-Based Motion Planning
Links : [Published]

BibTex

@INPROCEEDINGS{6696587, author={C. {Rodriguez} and J. {Denny} and S. A. {Jacobs} and S. {Thomas} and N. M. {Amato}}, booktitle={2013 IEEE/RSJ International Conference on Intelligent Robots and Systems}, title={Blind RRT: A probabilistically complete distributed RRT}, year={2013}, volume={}, number={}, pages={1758-1765}, doi={10.1109/IROS.2013.6696587}}


Abstract

Rapidly-Exploring Random Trees (RRTs) have been successful at finding feasible solutions for many types of problems. With motion planning becoming more computationally demanding, we turn to parallel motion planning for efficient solutions. Existing work on distributed RRTs has been limited by the overhead that global communication requires. A recent approach, Radial RRT, demonstrated a scalable algorithm that subdivides the space into regions to increase the computation locality. However, if an obstacle completely blocks RRT growth in a region, the planning space is not covered and is thus not probabilistically complete. We present a new algorithm, Blind RRT, which ignores obstacles during initial growth to efficiently explore the entire space. Because obstacles are ignored, free components of the tree become disconnected and fragmented. Blind RRT merges parts of the tree that have become disconnected from the root. We show how this algorithm can be applied to the Radial RRT framework allowing both scalability and effectiveness in motion planning. This method is a probabilistically complete approach to parallel RRTs. We show that our method not only scales but also overcomes the motion planning limitations that Radial RRT has in a series of difficult motion planning tasks.


A scalable distributed RRT for motion planning, Sam Ade Jacobs, Nicholas Stradford, Cesar Rodriguez, Shawna Thomas, Nancy M. Amato, 2013 IEEE International Conference on Robotics and Automation, pp. 5088-5095, Karlsruhe, Germany, May 2013. DOI: 10.1109/ICRA.2013.6631304
Keywords: Parallel Planning, Rapidly-exploring Random Tree (RRT), Sampling-Based Motion Planning
Links : [Published]

BibTex

@INPROCEEDINGS{6631304,
author={S. A. {Jacobs} and N. {Stradford} and C. {Rodriguez} and S. {Thomas} and N. M. {Amato}},
booktitle={2013 IEEE International Conference on Robotics and Automation},
title={A scalable distributed RRT for motion planning},
year={2013},
volume={},
number={},
pages={5088-5095},
doi={10.1109/ICRA.2013.6631304}}


Abstract

Rapidly-exploring Random Tree (RRT), like other sampling-based motion planning methods, has been very successful in solving motion planning problems. Even so, sampling-based planners cannot solve all problems of interest efficiently, so attention is increasingly turning to parallelizing them. However, one challenge in parallelizing RRT is the global computation and communication overhead of nearest neighbor search, a key operation in RRTs. This is a critical issue as it limits the scalability of previous algorithms. We present two parallel algorithms to address this problem. The first algorithm extends existing work by introducing a parameter that adjusts how much local computation is done before a global update. The second algorithm radially subdivides the configuration space into regions, constructs a portion of the tree in each region in parallel, and connects the subtrees,i removing cycles if they exist. By subdividing the space, we increase computation locality enabling a scalable result. We show that our approaches are scalable. We present results demonstrating almost linear scaling to hundreds of processors on a Linux cluster and a Cray XE6 machine.


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, College Station, TX, USA, Mar 2013.
Keywords: Parallel Planning, Sampling-Based Motion Planning, STAPL
Links : [Manuscript]

BibTex

@techreport{afidel-tr13-002-2013,
title = "Load Balancing Techniques for Scalable Parallelization of Sampling-Based Motion Planning Algorithms",
author = "Fidel, Adam and Jacobs, Sam Ade and Sharma, Shishir and Rauchwerger, Lawrence and Amato, Nancy M. ",
institution = "Texas A&M University",
address = "College Station, TX, USA",
number = "TR13-002",
year = 2013,
month = mar
}


Abstract

Motion planning, which is the problem of computing feasible paths through an environment for a movable object, has applications in many domains ranging from robotics, to intelligent CAD, to protein folding. The best methods for solving this PSPACE-hard problem are so-called sampling-based planners. Recent work introduced uniform spatial subdivision techniques for parallelizing sampling-based motion planning algorithms that scaled well. However, such methods are prone to load imbalance, particularly as the number of processors is increased, because planning time depends on region characteristics and, for most problems, the heterogeneity of the set of regions increases as the region size decreases. In this work, we introduce two techniques to address the problems of load imbalance in the parallelization of sampling-based motion planning algorithms: bulk-synchronous redistribution and an adaptive workstealing approach. We show that applying these techniques to representatives of the two major classes of parallel sampling-based motion planning algorithms, probabilistic roadmaps and rapidly-exploring random trees, results in a more scalable and load-balanced computation on 3,000+ cores.


A Scalable Method for Parallelizing Sampling-Based Motion Planning Algorithms, Sam Ade Jacobs, Kasra Manavi, Juan Burgos, Jory Denny, Shawna Thomas, Nancy M. Amato, 2012 IEEE International Conference on Robotics and Automation, pp. 2529-2536, Saint Paul, MN, USA, May 2012. DOI: 10.1109/ICRA.2012.6225334
Keywords: Parallel Algorithms, Parallel Planning, Sampling-Based Motion Planning
Links : [Published]

BibTex

@INPROCEEDINGS{6225334,
author={S. A. {Jacobs} and K. {Manavi} and J. {Burgos} and J. {Denny} and S. {Thomas} and N. M. {Amato}},
booktitle={2012 IEEE International Conference on Robotics and Automation},
title={A scalable method for parallelizing sampling-based motion planning algorithms},
year={2012},
volume={},
number={},
pages={2529-2536},
doi={10.1109/ICRA.2012.6225334}}


Abstract

This paper describes a scalable method for parallelizing sampling-based motion planning algorithms. It subdivides configuration space (C-space) into (possibly overlapping) regions and independently, in parallel, uses standard (sequential) sampling-based planners to construct roadmaps in each region. Next, in parallel, regional roadmaps in adjacent regions are connected to form a global roadmap. By subdividing the space and restricting the locality of connection attempts, we reduce the work and inter-processor communication associated with nearest neighbor calculation, a critical bottleneck for scalability in existing parallel motion planning methods. We show that our method is general enough to handle a variety of planning schemes, including the widely used Probabilistic 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 on a 2400 core LINUX cluster and on a 153,216 core Cray XE6 petascale machine.


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.
Keywords: Parallel Planning, Sampling-Based Motion Planning, STAPL
Links : [Published]

BibTex

N/A


Abstract

This work describes a scalable method for parallelizing sampling-based motion planning algorithms. It subdivides configuration space (C-space) into (possibly overlapping) regions and independently, in parallel, uses standard (sequential) sampling-based planners to construct roadmaps in each region. Next, in parallel, regional roadmaps in adjacent regions are connected to form a global roadmap. By subdividing the space and restricting the locality of connection attempts, we reduce the work and inter-processor communication associated with nearest neighbor calculation, a critical bottleneck for scalability in existing parallel motion planning methods. We show that our method is general enough to handle a variety of planning schemes, including the widely used Probabilistic 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 on a 2400 core LINUX cluster and on a 153,216 core Cray XE6 petascale machine.


Parallel Protein Folding with STAPL, Shawna Thomas, Gabriel Tanase, Lucia K. Dale, Jose E. Moreira, Lawrence Rauchwerger, Nancy M. Amato, Concurrency and Computation: Practice and Experience, Vol: 17, Issue: 14, pp. 1643-1656, Dec 2005. DOI: https://doi.org/10.1002/cpe.950
Keywords: Parallel Planning, Protein Folding, STAPL
Links : [Published]

BibTex

@article{https://doi.org/10.1002/cpe.950,
author = {Thomas, Shawna and Tanase, Gabriel and Dale, Lucia K. and Moreira, Jose M. and Rauchwerger, Lawrence and Amato, Nancy M.},
title = {Parallel protein folding with STAPL},
journal = {Concurrency and Computation: Practice and Experience},
volume = {17},
number = {14},
pages = {1643-1656},
keywords = {protein folding, motion planning, parallel libraries, C++},
doi = {https://doi.org/10.1002/cpe.950},
url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/cpe.950},
eprint = {https://onlinelibrary.wiley.com/doi/pdf/10.1002/cpe.950},
abstract = {Abstract The protein-folding problem is a study of how a protein dynamically folds to its so-called native state—an energetically stable, three-dimensional conformation. Understanding this process is of great practical importance since some devastating diseases such as Alzheimer's and bovine spongiform encephalopathy (Mad Cow) are associated with the misfolding of proteins. We have developed a new computational technique for studying protein folding that is based on probabilistic roadmap methods for motion planning. Our technique yields an approximate map of a protein's potential energy landscape that contains thousands of feasible folding pathways. We have validated our method against known experimental results. Other simulation techniques, such as molecular dynamics or Monte Carlo methods, require many orders of magnitude more time to produce a single, partial trajectory. In this paper we report on our experiences parallelizing our method using STAPL (Standard Template Adaptive Parallel Library) that is being developed in the Parasol Lab at Texas A\&M. An efficient parallel version will enable us to study larger proteins with increased accuracy. We demonstrate how STAPL enables portable efficiency across multiple platforms, ranging from small Linux clusters to massively parallel machines such as IBM's BlueGene/L, without user code modification. Copyright © 2005 John Wiley \& Sons, Ltd.},
year = {2005}
}


Abstract

The protein-folding problem is a study of how a protein dynamically folds to its so-called native state - an energetically stable, three-dimensional conformation. Understanding this process is of great practical importance since some devastating diseases such as Alzheimer's and bovine spongiform encephalopathy (Mad Cow) are associated with the misfolding of proteins. We have developed a new computational technique for studying protein folding that is based on probabilistic roadmap methods for motion planning. Our technique yields an approximate map of a protein's potential energy landscape that contains thousands of feasible folding pathways. We have validated our method against known experimental results. Other simulation techniques, such as molecular dynamics or Monte Carlo methods, require many orders of magnitude more time to produce a single, partial trajectory. In this paper we report on our experiences parallelizing our method using STAPL (Standard Template Adaptive Parallel Library) that is being developed in the Parasol Lab at Texas A&M. An efficient parallel version will enable us to study larger proteins with increased accuracy. We demonstrate how STAPL enables portable efficiency across multiple platforms, ranging from small Linux clusters to massively parallel machines such as IBM's BlueGene/L, without user code modification.


Parallel Protein Folding with STAPL, Shawna Thomas, Nancy M. Amato, 18th International Parallel and Distributed Processing Symposium (IPDPS), pp. 189-, Santa Fe, NM, USA, Apr 2004. DOI: 10.1109/IPDPS.2004.1303204
Keywords: Parallel Planning, Protein Folding, STAPL
Links : [Published]

BibTex

@INPROCEEDINGS{1303204,
author={S. {Thomas} and N. M. {Amato}},
booktitle={18th International Parallel and Distributed Processing Symposium, 2004. Proceedings.},
title={Parallel protein folding with STAPL},
year={2004},
volume={},
number={},
pages={189-},
doi={10.1109/IPDPS.2004.1303204}}


Abstract

Summary form only given. The protein folding problem is to study how a protein dynamically folds to its so-called native state - an energetically stable, three-dimensional configuration. Understanding this process is of great practical importance since some devastating diseases such as Alzheimer\'s and bovine spongiform encephalopathy (Mad Cow) are associated with the misfolding of proteins. In our group, we have developed a new computational technique for studying protein folding that is based on probabilistic roadmap methods for motion planning. Our technique yields an approximate map of a protein\'s potential energy landscape that contains thousands of feasible folding pathways. We have validated our method against known experimental results. Other simulation techniques, such as molecular dynamics or Monte Carlo methods, require many orders of magnitude more time to produce a single, partial, trajectory. We report on our experiences parallelizing our method using STAPL (the standard template adaptive parallel library), that is being developed in the Parasol Lab at Texas A&M. An efficient parallel version enables us to study larger proteins with increased accuracy. We demonstrate how STAPL enables portable efficiency across multiple platforms without user code modification. We show performance gains on two systems: a dedicated Linux cluster and an extremely heterogeneous multiuser Linux cluster.


Probabilistic Roadmap Methods are Embarrassingly Parallel, N.M. Amato, L.K. Dale, Proceedings of IEEE International Conference on Robotics and Automation, pp. 688-694, Detroit, MI, USA, May 1999. DOI: 10.1109/ROBOT.1999.770055
Keywords: Parallel Algorithms, Parallel Planning, Sampling-Based Motion Planning
Links : [Published]

BibTex

@INPROCEEDINGS{770055,
author={Amato, N.M. and Dale, L.K.},
booktitle={Proceedings 1999 IEEE International Conference on Robotics and Automation (Cat. No.99CH36288C)},
title={Probabilistic roadmap methods are embarrassingly parallel},
year={1999},
volume={1},
number={},
pages={688-694 vol.1},
doi={10.1109/ROBOT.1999.770055}}


Abstract

In this paper we report on our experience in parallelizing probabilistic roadmap motion planning methods (PRMs). We show that significant, scalable speed-ups can be obtained with relatively little effort on the part of the developer. Our experience is not limited to PRMs. In particular, we outline general techniques for parallelizing types of computations commonly performed in motion planning algorithms, and identify potential difficulties that might be faced in other efforts to parallelize sequential motion planning methods.