A new sample-based strategy for narrow passage detection

In this paper three different milestone generation methods are proposed to better overcome the narrow passage problem in Probabilistic Roadmaps (PRM). Unlike previous approaches the points generated on obstacles are preserved and their information is used to find the location of narrow passages. We have tested the proposed algorithms on several standard environments and compared its results with the results of two other well-known sample generation methods. The results show better performance in terms of runtime, uniform coverage of the configuration space, and success rate in narrow passage detection and final path generation.