Probabilistic roadmap (PRM) methods are widely used for robot navigation in both 2D and 3D environments; however, a major drawback is that the raw paths tend to be jagged. Executing a trajectory along such paths can lead to significant overshoots and tight turns, making it difficult to achieve a near-optimal solution under motion constraints. This paper presents an enhanced PRM-based path planning approach designed to improve path quality and computational efficiency. The method integrates advanced sampling strategies, adaptive neighbor selection with spatial data structures, and multi-stage path post-processing. In particular, shortcut smoothing and polynomial fitting are used to generate smoother trajectories suitable for motion-constrained robots. The proposed hybrid sampling scheme biases sample generation toward critical regions—near obstacles, in narrow passages, and between the start and goal—to improve graph connectivity in challenging areas. An adaptive k-d tree-based connection strategy then efficiently builds a roadmap using variable connection radii guided by PRM* theory. Once a path is found using an any-angle graph search, post-processing is applied to refine it. Unnecessary waypoints are removed via line-of-sight shortcuts, and the final trajectory is smoothed using a fitted polynomial curve. The resulting paths are shorter and exhibit gentler turns, making them more feasible for execution. In simulated complex scenarios, including narrow corridors and cluttered environments, the advanced PRM achieved a 100% success rate where standard PRM frequently failed. It also reduced calculation time to 30% and peak turning angle by up to 50% compared to conventional methods. The approach supports dynamic re-planning: when the environment changes, the roadmap is efficiently updated rather than rebuilt from scratch. Furthermore, the use of an adaptive k-d tree structure and incremental roadmap updates leads to an order-of-magnitude speedup in the connection phase. These improvements significantly increase the planner’s path quality, runtime performance, and reliability. Quantitative results are provided to substantiate the performance gains of the proposed method.
Ambrożkiewicz et al. (Thu,) studied this question.