A Levy Flight based Narrow Passage Sampling Method for Probabilistic Roadmap Planners
This addresses motion planning for robots with high degrees of freedom, offering a robust solution for scenarios with critical narrow passages, though it is incremental as it builds on existing PRM techniques.
The paper tackles the problem of probabilistic roadmap planners failing in narrow passages by introducing a Levy Flight-based sampling method, which improves completeness and outperforms state-of-the-art methods in collision calls, computational overhead, and sample quality.
Sampling based probabilistic roadmap planners (PRM) have been successful in motion planning of robots with higher degrees of freedom, but may fail to capture the connectivity of the configuration space in scenarios with a critical narrow passage. In this paper, we show a novel technique based on Levy Flights to generate key samples in the narrow regions of configuration space, which, when combined with a PRM, improves the completeness of the planner. The technique substantially improves sample quality at the expense of a minimal additional computation, when compared with pure random walk based methods, however, still outperforms state of the art random bridge building method, in terms of number of collision calls, computational overhead and sample quality. The method is robust to the changes in the parameters related to the structure of the narrow passage, thus giving an additional generality. A number of 2D & 3D motion planning simulations are presented which shows the effectiveness of the method.