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.
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.
Path quality in both SE(2) and SE(3), along with number of answered queries (in SE(2)).
Memory requirements of the approaches (offline and online) as well as termination condition tracking.
- Dobson, A., Bekris K E., Finite-Time Near-Optimality Properties of Sampling-Based Motion Planners. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2013, Tokyo Big Site, Japan.
- Dobson, A., Bekris K E., Improving Sparse Roadmap Spanners. International Conference on Robotics and Automation (ICRA) 2013, Karslruhe, Germany.
- Dobson, A., Krontiris, A., Bekris K E., Sparse Roadmap Spanners. Workshop on the Algorithmic Foundations of Robotics (WAFR) 2012, MIT, Cambridge, Massachusetts, USA.
- Marble, J., Bekris K E., Asymptotically Near-Optimal Planning with Probabilistic Roadmap Spanners. IEEE Transactions on Robotics (TRO) 2013.
- Marble, J., Bekris K E., Asymptotically Near-Optimal is Good Enough for Motion Planning. International Symposium on Robotics Research (ISRR) 2011, Flagstaff, Arizona, USA.
- Marble, J., Bekris K E., Computing Spanners of Asymptotically Optimal Probabilistic Roadmaps. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2011, San Francisco, California, USA.
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.