Sampling-based motion planners are an effective means for generating collision-free motion paths. However, the quality of these motion paths (with respect to quality measures such as path length, clearance, smoothness or energy) is often notoriously low, especially in high-dimensional configuration spaces. We introduce a simple algorithm for merging an arbitrary number of input motion paths into a hybrid output path of superior quality, for a broad and general formulation of path quality. Our approach is based on the observation that the quality of certain sub-paths within each solution may be higher than the quality of the entire path. A dynamic-programming algorithm, which we recently developed for comparing and clustering multiple motion paths, reduces the running time of the merging algorithm significantly. We tested our algorithm in motion-planning problems with up to 12 degrees of freedom. We show that our algorithm is able to merge a handful of input paths produced by several different motion planners to produce output paths of much higher quality.
Wilmarth @cite_1 improved the local clearance of sampled configurations by sampling closer to the medial axis. Nieuwenhuisen @cite_0 improved the optimal path length in probabilistic roadmaps by closing cycles only when they significantly reduce the (graph) path length between configurations, and Geraerts @cite_36 combined both approaches. In contrast to the above techniques, the approach we present below is not tailored for any specific criterion of path quality, and is designed to allow general formulations of path quality.
@cite_0 @cite_1 @cite_36
2122724557 2606507580 2119159374 2158207287
Probabilistic roadmap (PRM) planners have been successful in path planning of robots with many degrees of freedom, but sampling narrow passages in a robot's configuration space remains a challenge for PRM planners. This paper presents a hybrid sampling strategy in the PRM framework for finding paths through narrow passages. A key ingredient of the new strategy is the bridge test, which reduces sample density in many unimportant parts of a configuration space, resulting in increased sample density in narrow passages. The bridge test can be implemented efficiently in high-dimensional configuration spaces using only simple tests of local geometry. The strengths of the bridge test and uniform sampling complement each other naturally. The two sampling strategies are combined to construct the hybrid sampling strategy for our planner. We implemented the planner and tested it on rigid and articulated robots in 2-D and 3-D environments. Experiments show that the hybrid sampling strategy enables relatively small roadmaps to reliably capture the connectivity of configuration spaces with difficult narrow passages. A landmark based heuristic is investigated for reducing query phase run-time of the probabilistic roadmap (PRM) motion planning method. The heuristic is generated by storing minimum spanning trees from a small number of vertices within the PRM graph and using these trees to approximate the cost of a shortest path between any two vertices of the graph. The intermediate step of preprocessing the graph increases the time and memory requirements of the classical motion planning technique in exchange for speeding up individual queries making the method advantageous in multi-query applications. This paper investigates these trade-offs on PRM graphs constructed in randomized environments as well as a practical manipulator simulation. We conclude that the method is preferable to Dijkstra's algorithm or the A∗ algorithm with conventional heuristics in multi-query applications. Many motion planning techniques, like the probabilistic roadmap method (PRM), generate low quality paths. In this paper, we study a number of different quality criteria on paths in particular length and clearance. We describe a number of techniques to improve the quality of paths. These are based on a new approach to increase the path clearance. Experiments showed that the heuristics were able to generate paths of a much higher quality than previous approaches. We present, implement, and analyze a spectrum of closely-related planners, designed to gain insight into the relationship between classical grid search and probabilistic roadmaps (PRMs). Building on quasi-Monte Carlo sampling literature, we have developed deterministic variants of the PRM that use low-discrepancy and low-dispersion samples, including lattices. Classical grid search is extended using subsampling for collision detection and also the optimal-dispersion Sukharev grid, which can be considered as a kind of lattice-based roadmap to complete the spectrum. Our experimental results show that the deterministic variants of the PRM offer performance advantages in comparison to the original PRM and the recent Lazy PRM. This even includes searching using a grid with subsampled collision checking. Our theoretical analysis shows that all of our deterministic PRM variants are resolution complete and achieve the best possible asymptotic convergence rate, which is shown superior to that obtained by random sampling. Thus, in surprising contrast to recent trends, there is both experimental and theoretical evidence that some forms of grid search are superior to the original PRM.