We develop parallel algorithms for motion planning applications. In particular, we use the Standard Template Adaptive Parallel Library (STAPL) to build platform independent code that can handle both shared memory and distributed memory models, without requiring user code modification. STAPL handles the underlying communications through parallel, distributed data structures, similar to structures provided by the ANSI C++ Standard Template Library (STL). We have successfully applied this to both motion planning and protein folding applications.
We design a general framework for these sampling based motion planning algorithms that subdivides the motion space into (possibly overlapping) regions and independently, in parallel, uses standard sampling based motion planners to construct solutions in each subdivision. It then merges these solutions together to form a large roadmap, or graph, of the motion space which describes motion pathways between various points in the space.
Some motion planning algorithms build a tree, instead of a graph, which can be challenging in a parallel system. We develop parallel algorithms that can handle the issues that come with a tree structure containing a single root.