<scp>PRM</scp> ‐Star: An Enhanced Probabilistic Roadmap Algorithm With Adaptive Sampling and Path Optimization

Abstract

ABSTRACT Probabilistic roadmaps (PRM) are a cornerstone of autonomous motion planning, yet they face a persistent trade‐off: efficient sampling often yields jagged, kinematically infeasible paths, while existing solutions, such as Gaussian biasing or post hoc spline smoothing, either compromise global connectivity or impose significant computational overhead. This study introduces PRM‐Star, a novel unified planning framework that overcomes these limitations by embedding adaptive obstacle‐aware sampling and curvature‐based optimization directly into the roadmap construction pipeline. Unlike traditional two‐stage approaches that treat smoothing as an afterthought, PRM‐Star dynamically adjusts sampling density in narrow passages and utilizes a curvature‐minimizing connection strategy to generate inherently smooth, production‐ready trajectories in real time. The algorithm leverages k‐d tree data structures and grid‐based operation tracking to maintain high computational efficiency without sacrificing path quality. The proposed method was rigorously benchmarked against Standard PRM, Gaussian‐PRM, PRM‐Lite, PRM‐RRT, PRM‐B‐Spline, and PRM‐Cubic‐Spline in complex simulated environments. Empirical results demonstrate that PRM‐Star significantly outperforms state‐of‐the‐art variants, reducing total path curvature by approximately 82% (from &gt; 1000° to ˜181°) and waypoint redundancy by 76% compared to standard approaches. Statistical validation using one‐way ANOVA, Tukey's HSD, and Cohen's d effect size analysis confirms that these improvements are statistically significant ( p &lt; 0.05) and yield large effect sizes. By harmonizing the conflicting goals of kinematic smoothness and computational scalability, PRM‐Star offers a robust, statistically validated advancement suitable for deployment in resource‐constrained autonomous systems.