Probabilistic RoadMaps (PRMs) have been successful for many high-dimensional motion planning problems. However, they encounter difficulties when mapping narrow passages. While many PRM sampling methods have been proposed to increase the proportion of samples within narrow passages, such difficult planning areas still pose many challenges. We introduce a novel algorithm, Spark PRM, that sparks the growth of Rapidly-expanding Random Trees (RRTs) from narrow passage samples generated by a PRM. The RRT rapidly generates further narrow passage samples, ideally until the passage is fully mapped. After reaching a terminating condition, the tree stops growing and is added to the roadmap.

Spark PRM is a general method that can be applied to all PRM variants. We study the benefits of Spark PRM with a variety of sampling strategies in a wide array of environments. We show significant speedups in computation time over RRT, Sampling-based Roadmap of Trees (SRT), and various PRM variants.

The motivation for Spark PRM lies heavily on the observation that RRTs growing inside narrow passages are forced to stay inside the narrow passage until they find an exit, regardless of how narrow or long the passage is. Spark PRM `sparks’ the construction of RRTs in narrow passages rooted at PRM samples that pass a narrow passage test. Ideally, these RRTs grow inside narrow passages until they find exits that allow them to connect to the roadmap built by the PRM. Thus, RRT growth will lead to a continual and rapid generation of narrow passage samples until the passage has been fully mapped. In practice, it is difficult to balance this ideal with robustness in different environments. However, Spark PRM still achieves significant efficiency boosts.

Algorithmically, Spark PRM is a simple extension of PRM. As in incremental PRM, Spark PRM alternates between sampling and connecting until the roadmap meets some terminating criteria (e.g., solving a query). However, after the connection step, Spark PRM performs a narrow passage test for each new configuration s, and if s is inside a narrow passage, an RRT is constructed with s as the root. Upon termination of RRT growth, the tree is added to the roadmap. Since the incremental growth of the roadmap can utilize any PRM technique, the Spark PRM methodology is quite general.

As an example, we will follow the execution of Spark PRM in a narrow passage environment shown below. The white areas represent free space and the gray areas represent obstacle space. Spark PRM begins by using an iterative PRM planner, which constructs a roadmap (blue) in (a). The red node passes the narrow passage test, and an RRT (magenta) is sparked (b). When the RRT expands and reaches an exit of the narrow passage, it connects to the roadmap (dotted magenta edge). In (c), the RRT continues expansion and again connects to the roadmap. The RRT grows toward the other exit of the narrow passage due to an optimization that prevents further expansion outside the narrow passage near the first connection. In (d), the RRT terminates expansion and is added to the roadmap. Finally, the iterative PRM resumes, possibly sparking other RRTs, until the map is satisfactory (e.g., can solve a query).

(a) Initial environment. Blue shows current roadmap and magenta shows a narrow passage sample.

(b) From the narrow passage sample, an RRT is grown. Connections are attempted back to the overall map.

(c) Finalized RRT growth and connections.

(d) The RRT is added into the full roadmap.

Publications

Updated: