Improved PRM algorithm based on dynamic partitioning and adaptive sampling

Abstract

The Probabilistic Roadmap (PRM) algorithm has been widely employed in robotic manipulator path planning tasks due to its rapid exploration capabilities, particularly in high-dimensional configuration spaces with complex kinematic and environmental constraints. However, the efficiency of PRM is inherently constrained by the distribution of sampling points. In scenarios involving narrow passages, the sparsity of samples within such regions may significantly increase the likelihood of planning failure. In view of this, this paper proposes an improved PRM algorithm that is suitable for narrow channels with obstacles and can significantly improve the efficiency of path planning. First, a non-uniform partitioning strategy based on obstacle density is proposed to dynamically divide the sampling area to reduce the connection of redundant edges. Second, to address the sampling failure often encountered in narrow passages due to insufficient sample points, a weighted sampling adjustment strategy is proposed, which adaptively modifies the sampling density between narrow and open regions based on a comprehensive distance metric. Third, an adaptive variable step-size strategy is developed to dynamically adjust the connection steps between obstacle boundaries and open areas, further enhancing roadmap connectivity. By integrating the aforementioned strategies, the improved PRM algorithm proposed was applied in both two-dimensional and three-dimensional environments. The simulation results demonstrate that the method is capable of finding feasible paths in complex scenarios. Compared to the Lazy PRM and the OBPRM algorithms, the proposed approach achieves reductions of approximately 8.77% and 7.44% in path length and 9.00% and 5.74% in planning time, respectively. Finally, its effectiveness and superiority in robotic manipulator path planning were further validated through application to a 7-DOF manipulator.

Keywords

Path planning / Probabilistic roadmap / Partitioning strategy / Adaptive sampling

CRediT authorship contribution statement

Yifan Wang: Writing – review & editing, Funding acquisition, Conceptualization. Xiangrong Zhao: Writing – original draft, Visualization, Validation, Supervision, Methodology, Investigation, Conceptualization. Gang Chen: Writing – review & editing, Supervision, Funding acquisition. Xianyuan Gao: Methodology, Data curation. Kaichao Chen: Writing – review & editing, Investigation.

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (62173044 and 62103058).

Appendix A. Supplementary data

Supplementary material related to this article can be found online at https://doi.org/10.1016/j.birob.2026.100283.

References

[1] B. Singh, R. Kumar, V.P. Singh, Reinforcement learning in robotic applications: a comprehensive survey, Artif. Intell. Rev. 55 (2) (2022) 945-990.

[2] P. Dario, E. Guglielmelli, B. Allotta, M.C. Carrozza, Robotics for medical applications, IEEE Robot. Autom. Mag. 3 (3) (2002) 44-56.

[3] R. Firoozi, J. Tucker, S. Tian, A. Majumdar, J. Sun, W. Liu, Y. Zhu, S. Song, A. Kapoor, K. Hausman, et al., Foundation models in robotics: Applications, challenges, and the future, Int. J. Robot. Res., (2023), 02783649241281508.

[4] A. Gasparetto, P. Boscariol, A. Lanzutti, R. Vidoni, Path planning and trajectory planning algorithms: A general overview, Motion Oper. Plan. Robot. Syst.: Backgr. Pr. Approaches, 2015, pp. 3-27.

[5] L. Zhang, K. Cai, Z. Sun, Z. Bing, C. Wang, L. Figueredo, S. Haddadin, A. Knoll, Motion planning for robotics: A review for sampling-based planners, Biomim. Intell. Robot., (2025), 100207.

[6] L. Yang, J. Qi, D. Song, J. Xiao, J. Han, Y. Xia, Survey of robot 3D path planning algorithms, J. Control Sci. Eng. 2016 (1) (2016) 7426913.

[7] J. Tisdale, Z. Kim, J.K. Hedrick, Autonomous UAV path planning and estimation, IEEE Robot. Autom. Mag. 16 (2) (2009) 35-42.

[8] M. Soulignac, Feasible and optimal path planning in strong current fields, IEEE Trans. Robot. 27 (1) (2010) 89-98.

[9] C.W. Warren, Global path planning using artificial potential fields, 1989 IEEE International Conference on Robotics and Automation, IEEE Computer Society, 1989, pp. 316-317.

[10] P.B. Kumar, H. Rawat, D.R. Parhi, Path planning of humanoids based on artificial potential field method in unknown environments, Expert Syst. 36 (2) (2019) e12360.

[11] Z. Pan, C. Zhang, Y. Xia, H. Xiong, X. Shao, An improved artificial potential field method for path planning and formation control of the multi-UAV systems, IEEE Trans. Circuits Syst. II: Express Briefs 69 (3) (2021) 1129-1133.

[12] J. Luo, Z.-X. Wang, K.-L. Pan, Reliable path planning algorithm based on improved artificial potential field method, IEEE Access 10 (2022) 108276-108284.

[13] C.W. Warren, Fast path planning using modified A* method, [1993] Proceedings IEEE International Conference on Robotics and Automation, IEEE, 1993, pp. 662-667.

[14] T. Lei, T. Sellers, C. Luo, D.W. Carruth, Z. Bi, Graph-based robot optimal path planning with bio-inspired algorithms, Biomim. Intell. Robot. 3 (3) (2023) 100119.

[15] L. Jaillet, J. Cortés, T. Siméon, Sampling-based path planning on configuration-space costmaps, IEEE Trans. Robot. 26 (4) (2010) 635-646.

[16] R. Yang, J. Li, Z. Jia, S. Wang, H. Yao, E. Dong, EPL-PRM: Equipotential line sampling strategy for probabilistic roadmap planners in narrow passages, Biomim. Intell. Robot. 3 (3) (2023) 100112.

[17] O. Khatib, The potential field approach and operational space formulation in robot control, Adaptive and Learning Systems: Theory and Applications, Springer, 1986, pp. 367-377.

[18] K.P. Carroll, S.R. McClaran, E.L. Nelson, D.M. Barnett, D.K. Friesen, G.N. William, AUV path planning: an A* approach to path planning with consideration of variable vehicle speeds and multiple, overlapping, time-dependent exclusion zones, Proceedings of the 1992 Symposium on Autonomous Underwater Vehicle Technology, IEEE, 1992, pp. 79-84.

[19] S. Erke, D. Bin, N. Yiming, Z. Qi, X. Liang, Z. Dawei, An improved A-star based path planning algorithm for autonomous land vehicles, Int. J. Adv. Robot. Syst. 17 (5) (2020) 1729881420962263.

[20] O.O. Martins, A.A. Adekunle, O.M. Olaniyan, B.O. Bolaji, An improved multi-objective a-star algorithm for path planning in a large workspace: Design, implementation, and evaluation, Sci. Afr. 15 (2022) e01068.

[21] X. Li, X. Hu, Z. Wang, Z. Du, Path planning based on combinaion of improved A-STAR algorithm and dwa algorithm, 2020 2nd International Conference on Artificial Intelligence and Advanced Manufacture, AIAM, IEEE, 2020, pp. 99-103.

[22] A. Stentz, Optimal and efficient path planning for partially-known environments, Proceedings of the 1994 IEEE International Conference on Robotics and Automation, IEEE, 1994, pp. 3310-3317.

[23] S. Kadry, G. Alferov, V. Fedorov, A. Khokhriakova, Path optimization for D-star algorithm modification, AIP Conference Proceedings, vol. 2425, AIP Publishing, (2022).

[24] V. Yevsieiev, A. Abu-Jassar, S. Maksymova, A. Alkhalaileh, Route Constructing for a Mobile Robot Based on the D-Star Algorithm, Technical science research in Uzbekistan, (2024).

[25] H. Wang, Y. Yu, Q. Yuan, Application of dijkstra algorithm in robot path-planning, 2011 Second International Conference on Mechanic Automation and Control Engineering, IEEE, 2011, pp. 1067-1069.

[26] S. LaValle, Rapidly-exploring Random Trees: A New Tool for Path Planning: Research Report 9811, Department of Computer Science, Iowa State University, (1998).

[27] I. Noreen, A. Khan, Z. Habib, Optimal path planning using RRT* based approaches: a survey and future directions, Int. J. Adv. Comput. Sci. Appl., 7 (11), (2016).

[28] H. Zhang, Y. Wang, J. Zheng, J. Yu, Path planning of industrial robot based on improved RRT algorithm in complex environments, IEEE Access 6 (2018) 53296-53306.

[29] J. Wang, W. Chi, C. Li, C. Wang, M.Q.-H. Meng, Neural RRT*: Learning-based optimal path planning, IEEE Trans. Autom. Sci. Eng. 17 (4) (2020) 1748-1758.

[30] L.E. Kavraki, P. Svestka, J.-C. Latombe, M.H. Overmars, Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE Trans. Robot. Autom. 12 (4) (1996) 566-580.

[31] L.-C. Latombe, Probabilistic roadmaps for robot path planning, Prat. Motion Plan. Robot.: Curr. Aproaches Futur. Challenges, 1998, pp. 33-53.

[32] G. Song, S. Thomas, N.M. Amato, A general framework for PRM motion planning, 2003 IEEE International Conference on Robotics and Automation (Cat. No. 03CH37422), vol. 3, IEEE, 2003, pp. 4445-4450.

[33] S. Karaman, E. Frazzoli, Sampling-based algorithms for optimal motion planning, Int. J. Robot. Res. 30 (7) (2011) 846-894.

[34] J.D. Gammell, S.S. Srinivasa, T.D. Barfoot, Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic, 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE, 2014, pp. 2997-3004.

[35] J.D. Gammell, S.S. Srinivasa, T.D. Barfoot, Batch informed trees (BIT*): Sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs, 2015 IEEE International Conference on Robotics and Automation, ICRA, IEEE, 2015, pp. 3067-3074.

[36] M.P. Strub, J.D. Gammell, Adaptively informed trees (AIT*) and effort informed trees (EIT*): Asymmetric bidirectional sampling-based path planning, Int. J. Robot. Res. 41 (4) (2022) 390-417.

[37] K. Cai, L. Zhang, X. Su, K. Chen, C. Wang, S. Haddadin, A. Knoll, A. Ajoudani, L. Figueredo, Just-in-time informed trees: Manipulability-aware asymptotically optimized motion planning, IEEE/ASME Trans. Mechatronics, (2025).

[38] Q. Li, Y. Xu, S. Bu, J. Yang, Smart vehicle path planning based on modified PRM algorithm, Sensors 22 (17) (2022) 6581.

[39] M. Novosad, R. Penicka, V. Vonasek, CTopPRM: Clustering topological PRM for planning multiple distinct paths in 3D environments, IEEE Robot. Autom. Lett. 8 (11) (2023) 7336-7343.

[40] R. Bohlin, L.E. Kavraki, Path planning using lazy PRM, Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No. 00CH37065), vol. 1, IEEE, 2000, pp. 521-528.

[41] V. Boor, M.H. Overmars, A.F. Van Der Stappen, The Gaussian sampling strategy for probabilistic roadmap planners, Proceedings 1999 IEEE International Conference on Robotics and Automation (Cat. No. 99CH36288C), vol. 2, IEEE, 1999, pp. 1018-1023.

[42] J. Denny, N.M. Amatoo, Toggle PRM: A coordinated mapping of C-free and C-obstacle in arbitrary dimension, Algorithmic Foundations of Robotics X: Proceedings of the Tenth Workshop on the Algorithmic Foundations of Robotics, Springer, 2013, pp. 297-312.

[43] N.M. Amato, O.B. Bayazit, L.K. Dale, C. Jones, D. Vallejo, OBPRM: An obstacle-based PRM for 3D workspaces, Proceedings of the Third Workshop on the Algorithmic Foundations of Robotics on Robotics: The Algorithmic Perspective: The Algorithmic Perspective, 1998, pp. 155-168.

[44] A.A. Ravankar, A. Ravankar, T. Emaru, Y. Kobayashi, HPPRM: hybrid potential based probabilistic roadmap algorithm for improved dynamic path planning of mobile robots, IEEE Access 8 (2020) 221743-221766.