C-FOREST: Parallel Shortest Path Planning With Superlinear Speedup

C-FOREST is a parallelization framework for single-query sampling-based shortest path-planning algorithms. Multiple search trees are grown in parallel (e.g., 1 per CPU). Each time a better path is found, it is exchanged between trees so that all trees can benefit from its data. Specifically, the path´s nodes increase the other trees´ configuration space visibility, while the length of the path is used to prune irrelevant nodes and to avoid sampling from irrelevant portions of the configuration space. Experiments with a robotic team, a manipulator arm, and the alpha benchmark demonstrate that C-FOREST achieves significant superlinear speedup in practice for shortest path-planning problems (team and arm), but not for feasible path panning (alpha).