We present methods for offline generation of sparse roadmap spanners that result in graphs 79 smaller than existing approaches while returning solutions of equivalent path quality. Our method uses a hybrid approach to sampling that combines traditional graph discretization with random sampling. We present techniques that optimize the graph for the L1-norm metric function commonly used in joint-based robotic planning, purposefully choosing a @math -stretch factor based on the geometry of the space, and removing redundant edges that do not contribute to the graph quality. A high-quality pre-processed sparse roadmap is then available for re-use across many different planning scenarios using standard repair and re-plan methods. Pre-computing the roadmap offline results in more deterministic solutions, reduces the memory requirements by affording complex rejection criteria, and increases the speed of planning in high-dimensional spaces allowing more complex problems to be solved such as multi-modal task planning. Our method is validated through simulated benchmarks against the SPARS2 algorithm. The source code is freely available online as an open source extension to OMPL.
One of the most popular methods for solving the robotic motion planning problem has been the sampling-based probabilistic roadmap (PRM) @cite_8 . While in theory PRMs are pre-processed and reusable across all environments, in practice they are typically only re-usable for a given environment, though in some implementations more general re-use is actually achieved such as in Dynamic Roadmaps @cite_4 . Even for versions of PRMs that can re-use their roadmap in changing environments, there are open questions on how to generate efficient and high quality graphs. Traditional PRMs are probabilistically complete but do not provide any guarantees on the quality of the path returned. PRM* @cite_5 has been proven to be asymptotically optimal as samples are infinitely added to the roadmap.
@cite_5 @cite_4 @cite_8
1971086298 2022115960
During the last decade, sampling-based path planning algorithms, such as probabilistic roadmaps (PRM) and rapidly exploring random trees (RRT), have been shown to work well in practice and possess theoretical guarantees such as probabilistic completeness. However, little effort has been devoted to the formal analysis of the quality of the solution returned by such algorithms, e.g. as a function of the number of samples. The purpose of this paper is to fill this gap, by rigorously analyzing the asymptotic behavior of the cost of the solution returned by stochastic sampling-based algorithms as the number of samples increases. A number of negative results are provided, characterizing existing algorithms, e.g. showing that, under mild technical conditions, the cost of the solution returned by broadly used sampling-based algorithms converges almost surely to a non-optimal value. The main contribution of the paper is the introduction of new algorithms, namely, PRM* and RRT*, which are provably asymptotically optimal, i.e. such that the cost of the returned solution converges almost surely to the optimum. Moreover, it is shown that the computational complexity of the new algorithms is within a constant factor of that of their probabilistically complete (but not asymptotically optimal) counterparts. The analysis in this paper hinges on novel connections between stochastic sampling-based path planning algorithms and the theory of random geometric graphs. We present a practical strategy for real-time path planning for articulated robot arms in changing environments by integrating PRM for Changing Environments with 3D sensor data. Our implementation on Care-O-Bot 3 identifies bottlenecks in the algorithm and introduces new methods that solve the overall task of detecting obstacles and planning a path around them in under 100 ms. A fast planner is necessary to enable the robot to react to quickly changing human environments. We have tested our implementation in real-world experiments where a human subject enters the manipulation area, is detected and safely avoided by the robot. This capability is critical for future applications in automation and service robotics where humans will work closely with robots to jointly perform tasks.