Category Archives: Research

Stronger Formal Guarantees for Practical Motion Planners

Overview of Project

Probabilistic roadmap planners utilize an offline phase to build up information about the configuration space (C-space) and solve many practical motion planning problems. Traditionally, many of these planners focus on feasibility and may return paths of low quality; considerably different from the optimal ones, where path quality can be measured in terms of length, clearance, or smoothness. Smoothing can be used to improve some of these measures and algorithms exist that produce roadmaps with paths that are deformable to optimal ones. Hybridization graphs combine multiple solutions into a higher quality one that uses the best portions of each input path. These techniques, however, can be expensive for the online resolution of a query, especially when multiple queries must be answered.

Alternatively, it is possible to construct larger, denser roadmaps that better sample the C-space by investing more preprocessing time. For instance, a planner that attempts to connect a new sample to every existing node in the roadmap will eventually provide optimal solutions, a property known as asymptotic optimality. Asymptotically optimal planners tend to work well in practice; however, current analysis only allows optimality guarantees in an asymptotic fashion. Since algorithms are terminated in finite time in practice, bounds on path quality after finite execution time is desirable. By leveraging probability theory, asymptotically optimal algorithms can be shown to be probably near-optimal in finite time. This guarantees that returned paths will be within a bound of optimal with a certain probability. In addition, path length can be estimated given the number of iterations an algorithm has been run. The following figure illustrates the predicted path length in orange, and 1000 paths extracted from a sampling-based planner.

While roadmaps with this property are desirable for their high path quality, their large size can be problematic. Large roadmaps impose significant costs during construction, storage, transmission and online query resolution, so they may not be feasible for some applications. The recently proposed k-PRM* algorithm minimizes the number of neighbors each new sample has to be connected to while still providing asymptotic optimality. Even so, the density of roadmaps produced by k-PRM* can be very high, resulting in slow online query resolution times, as shown in the following figure.

This project shows that a viable alternative is to compute roadmaps with asymptotically near-optimal guarantees. By relaxing the optimality guarantees, it is possible to construct roadmaps that are sparser, faster to build, and can answer queries more quickly while providing solution paths with near-optimal guarantees. Additionally, these roadmaps tend to return a solution in the same homotopic class as the optimum one, so smoothing brings path quality even closer to optimal in practice. These techniques are general enough to use on roadmaps in any configuration space such as the various robots and environments in SE(3) shown in the following image.

Algorithmic Techniques

Sequential Roadmap Spanner

The Sequential Roadmap Spanner (SRS) technique uses the concept of graph spanners to provide smaller roadmaps with asymptotically near optimal solutions. Graph spanners are subgraphs which uphold the property that all paths through the spanner between two nodes of the graph are no longer than t times the length in the original graph, where t is called the ‘stretch factor’ of the spanner. The algorithm first runs an asymptotically optimal planner such as k-PRM* and then applies the spanner property to the resulting graph.

Incremental Roadmap Spanner

Computing the entire roadmap from k-PRM* can be very expensive in terms of memory, so this technique attempts to apply the spanner property during the construction of the roadmap. The Incremental Roadmap Spanner (IRS) technique applies a filter to the edges which would normally be added by k-PRM* by checking if the edge is required to uphold the spanner property for traveling from newly sampled configurations to the local neighborhood of the sample. The following image shows a result from this technique. A roadmap with 150 vertices and 2406 edges is reduced to 465 edges while preserving homotopy and adding only 7.3% to the mean path length over all shortest paths.

Sparse Roadmap Spanner

The SRS and IRS techniques use the results of graph spanners directly, and as such, they share a property with graph spanners, that is, that each node which would be added by k-PRM* is also added to the resulting roadmap. The SPArse Roadmap Spanner (SPARS) technique focuses on providing asymptotic near optimality while reducing the number of nodes added to the roadmap. The results are very sparse structures which not only maintain asymptotic near optimality as a property, but in practice return paths with very small amounts of degradation when compared to k-PRM*.


A Roadmap Spanner in an SE(3) environment constructed from the SPARS2 algorithm.

The method provides upper bounds on the length of paths through the resulting structure compared to the solutions returned by k-PRM*: returned_path_length = t*optimum_path_length + 3*D, where t and D are parameters of the algorithm. Furthermore, our analysis shows that the probability of adding nodes to the resulting data structure goes to zero as the iterations of the algorithms increase. This suggests that these structures may asymptotically converge to a finite-size while still providing solutions within a hard bound of optimal.


Path quality in both SE(2) and SE(3), along with number of answered queries (in SE(2)).

Experimental results show that the actual cost of paths returned by the resulting roadmap spanner is much smaller than the theoretical bounds drawn. Furthermore, choosing large values of t does not degrade paths returned by the framework dramatically. An interesting result indicates that at least in certain environments, the roadmap spanner framework is able to answer more queries than k-PRM* early in the execution of the algorithms.


Memory requirements of the approaches (offline and online) as well as termination condition tracking.

The memory usage for the roadmap spanner techniques during the preprocessing step is orders of magnitude smaller than k-PRM*. The resulting roadmap spanners vary on size depending on the specific algorithm used. The SPARS algorithm has a path quality/memory tradeoff compared to the SPARS2 variant. As shown, the SPARS2 algorithm uses less memory during offline pre-processing; however, the resulting roadmap which is used for online query resolution is generally much larger. Furthermore, the framework provides an automated stopping criterion, which checks the maximum number of consecutive failures. As the algorithms run, the maximum number of consecutive failures increases over time. This suggests that setting a threshold for maximum failures is a sufficient stopping criterion.

Related Publications

Acknowledgements

This work has been supported by NSF CNS 0932423. Any opinions and findings expressed in this paper are those of the authors and do not necessarily reflect the views of the sponsor.

People Involved