{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T09:25:23Z","timestamp":1770283523592,"version":"3.49.0"},"reference-count":26,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2023,3,27]],"date-time":"2023-03-27T00:00:00Z","timestamp":1679875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Henan science and technology research plan project","award":["222102220079"],"award-info":[{"award-number":["222102220079"]}]},{"name":"Henan science and technology research plan project","award":["2019GGJS082"],"award-info":[{"award-number":["2019GGJS082"]}]},{"name":"Henan science and technology research plan project","award":["17A460003"],"award-info":[{"award-number":["17A460003"]}]},{"name":"Training plan for young backbone teachers in universities of Henan Province","award":["222102220079"],"award-info":[{"award-number":["222102220079"]}]},{"name":"Training plan for young backbone teachers in universities of Henan Province","award":["2019GGJS082"],"award-info":[{"award-number":["2019GGJS082"]}]},{"name":"Training plan for young backbone teachers in universities of Henan Province","award":["17A460003"],"award-info":[{"award-number":["17A460003"]}]},{"name":"Basic research plan project of key scientific research projects of universities in Henan Province","award":["222102220079"],"award-info":[{"award-number":["222102220079"]}]},{"name":"Basic research plan project of key scientific research projects of universities in Henan Province","award":["2019GGJS082"],"award-info":[{"award-number":["2019GGJS082"]}]},{"name":"Basic research plan project of key scientific research projects of universities in Henan Province","award":["17A460003"],"award-info":[{"award-number":["17A460003"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Various navigation tasks involving dynamic scenarios require mobile robots to meet the requirements of a high planning success rate, fast planning, dynamic obstacle avoidance, and shortest path. PRM (probabilistic roadmap method), as one of the classical path planning methods, is characterized by simple principles, probabilistic completeness, fast planning speed, and the formation of asymptotically optimal paths, but has poor performance in dynamic obstacle avoidance. In this study, we use the idea of hierarchical planning to improve the dynamic obstacle avoidance performance of PRM by introducing D* into the network construction and planning process of PRM. To demonstrate the feasibility of the proposed method, we conducted simulation experiments using the proposed PRM-D* (probabilistic roadmap method and D*) method for maps of different complexity and compared the results with those obtained by classical methods such as SPARS2 (improving sparse roadmap spanners). The experiments demonstrate that our method is non-optimal in terms of path length but second only to graph search methods; it outperforms other methods in static planning, with an average planning time of less than 1 s, and in terms of the dynamic planning speed, our method is two orders of magnitude faster than the SPARS2 method, with a single dynamic planning time of less than 0.02 s. Finally, we deployed the proposed PRM-D* algorithm on a real vehicle for experimental validation. The experimental results show that the proposed method was able to perform the navigation task in a real-world scenario.<\/jats:p>","DOI":"10.3390\/s23073512","type":"journal-article","created":{"date-parts":[[2023,3,28]],"date-time":"2023-03-28T01:41:34Z","timestamp":1679967694000},"page":"3512","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":33,"title":["PRM-D* Method for Mobile Robot Path Planning"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1090-9667","authenticated-orcid":false,"given":"Chunyang","family":"Liu","sequence":"first","affiliation":[{"name":"School of Mechatronics Engineering, Henan University of Science and Technology, Luoyang 471003, China"},{"name":"Longmen Laboratory, Luoyang 471000, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6561-0094","authenticated-orcid":false,"given":"Saibao","family":"Xie","sequence":"additional","affiliation":[{"name":"School of Mechatronics Engineering, Henan University of Science and Technology, Luoyang 471003, China"}]},{"given":"Xin","family":"Sui","sequence":"additional","affiliation":[{"name":"School of Mechatronics Engineering, Henan University of Science and Technology, Luoyang 471003, China"},{"name":"Key Laboratory of Mechanical Design and Transmission System of Henan Province, Henan University of Science and Technology, Luoyang 471003, China"}]},{"given":"Yan","family":"Huang","sequence":"additional","affiliation":[{"name":"School of Mechatronics Engineering, Henan University of Science and Technology, Luoyang 471003, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8933-4557","authenticated-orcid":false,"given":"Xiqiang","family":"Ma","sequence":"additional","affiliation":[{"name":"School of Mechatronics Engineering, Henan University of Science and Technology, Luoyang 471003, China"},{"name":"Longmen Laboratory, Luoyang 471000, China"}]},{"given":"Nan","family":"Guo","sequence":"additional","affiliation":[{"name":"School of Mechatronics Engineering, Henan University of Science and Technology, Luoyang 471003, China"}]},{"given":"Fang","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Mechatronics Engineering, Henan University of Science and Technology, Luoyang 471003, China"},{"name":"Longmen Laboratory, Luoyang 471000, China"}]}],"member":"1968","published-online":{"date-parts":[[2023,3,27]]},"reference":[{"key":"ref_1","unstructured":"Stentz, A. (1997). Intelligent Unmanned Ground Vehicles, Springer."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1109\/70.508439","article-title":"Probabilistic roadmaps for path planning in high-dimensional configuration spaces","volume":"12","author":"Kavraki","year":"1996","journal-title":"IEEE Trans. Robot. Autom."},{"key":"ref_3","unstructured":"Qin, Y.Q., Sun, D.B., Li, N., and Cen, Y.G. (2004, January 26\u201329). Path planning for mobile robot using the particle swarm optimization with mutation operator. Proceedings of the 2004 International Conference on Machine Learning and Cybernetics (IEEE Cat. No. 04EX826), Shanghai, China."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1016\/j.procs.2018.01.113","article-title":"Genetic Algorithm Based Approach for Autonomous Mobile Robot Path Planning","volume":"127","author":"Lamini","year":"2018","journal-title":"Procedia Comput. Sci."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"106960","DOI":"10.1016\/j.asoc.2020.106960","article-title":"An improved PSO algorithm for smooth path planning of mobile robots using continuous high-degree Bezier curve","volume":"100","author":"Song","year":"2020","journal-title":"Appl. Soft Comput."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"62107","DOI":"10.1109\/ACCESS.2020.2984695","article-title":"Dynamic Path Planning for Unmanned Vehicles Based on Fuzzy Logic and Improved Ant Colony Optimization","volume":"8","author":"Song","year":"2020","journal-title":"IEEE Access"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Chen, J., Zhou, Y., Gong, J., and Deng, Y. (2019, January 27\u201330). An improved probabilistic roadmap algorithm with potential field function for path planning of quadrotor. Proceedings of the 2019 Chinese Control Conference (CCC), Guangzhou, China.","DOI":"10.23919\/ChiCC.2019.8865585"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"221743","DOI":"10.1109\/ACCESS.2020.3043333","article-title":"HPPRM: Hybrid Potential Based Probabilistic Roadmap Algorithm for Improved Dynamic Path Planning of Mobile Robots","volume":"8","author":"Ravankar","year":"2020","journal-title":"IEEE Access"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/j.jtbi.2013.11.022","article-title":"COStar: A D-star Lite-based dynamic search algorithm for codon optimization","volume":"344","author":"Liu","year":"2014","journal-title":"J. Theor. Biol."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/s11370-022-00416-8","article-title":"Auto-splitting D* lite path planning for large disaster area","volume":"15","author":"Heo","year":"2022","journal-title":"Intell. Serv. Robot."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"115706","DOI":"10.1016\/j.eswa.2021.115706","article-title":"Optimal path finding in stochastic quasi-dynamic environments using particle swarm optimization","volume":"186","author":"Alfadhel","year":"2021","journal-title":"Expert Syst. Appl."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1394","DOI":"10.1109\/ACCESS.2019.2962074","article-title":"A Novel Step Optimal Path Planning Algorithm for the Spherical Mobile Robot Based on Fuzzy Control","volume":"8","author":"Guo","year":"2019","journal-title":"IEEE Access"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/s10846-019-01112-z","article-title":"Hybrid Path Planning Based on Safe A* Algorithm and Adaptive Window Approach for Mobile Robot in Large-Scale Dynamic Environment","volume":"99","author":"Zhong","year":"2020","journal-title":"J. Intell. Robot. Syst."},{"key":"ref_14","unstructured":"Wilt, C., and Ruml, W. (2012, January 19\u201321). When does weighted A* fail?. Proceedings of the International Symposium on Combinatorial Search, Niagara Falls, ON, Canada."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Bohlin, R., and Kavraki, L.E. (2000, January 24\u201328). Path Planning Using Lazy PRM. Proceedings of the IEEE International Conference on Robotics and Automation, San Francisco, CA, USA.","DOI":"10.1109\/ROBOT.2000.844107"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1177\/0278364911406761","article-title":"Sampling-based Algorithms for Optimal Motion Planning","volume":"30","author":"Karaman","year":"2011","journal-title":"Int. J. Robot. Res."},{"key":"ref_17","unstructured":"Krontiis, A., Dobson, A., and Bekris, K. (2012, January 13\u201315). Sparse Roadmap Spanners. Proceedings of the Workshop on the Algorithmic Foundations of Robotics (WAFR), Cambridge, MA, USA."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Dobson, A., and Bekris, K. (2013, January 6\u201310). Improving Sparse Roadmap Spanners. Proceedings of the 2013 IEEE International Conference on Robotics and Automation (ICRA), Karlsruhe, Germany.","DOI":"10.1109\/ICRA.2013.6631156"},{"key":"ref_19","unstructured":"Chowdhury, M.I., and Schwartz, D.G. (2020, January 5\u201330). The PRM-A* path planning algorithm for UUVs: An application to Navy mission planning. Proceedings of the Global Oceans 2020: Singapore\u2013US Gulf Coast, Biloxi, MS, USA."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1186\/s10033-021-00544-9","article-title":"Multi-branch cable harness layout design based on genetic algorithm with probabilistic roadmap method","volume":"34","author":"Zhao","year":"2021","journal-title":"Chin. J. Mech. Eng."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"4298","DOI":"10.1109\/LRA.2019.2931199","article-title":"RL-RRT: Kinodynamic Motion Planning via Learning Reachability Estimators From RL Policies","volume":"4","author":"Chiang","year":"2019","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1109\/TRO.2020.2975428","article-title":"Long-range indoor navigation with prm-rl","volume":"36","author":"Francis","year":"2020","journal-title":"IEEE Trans. Robot."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Gao, J., Ye, W., Guo, J., and Li, Z. (2020). Deep Reinforcement Learning for Indoor Mobile Robot Path Planning. Sensors, 20.","DOI":"10.3390\/s20195493"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/j.future.2020.09.032","article-title":"Incremental multi-agent path finding","volume":"116","author":"Semiz","year":"2020","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Sadiq, A.T., and Hasan, A.H. (2017, January 26\u201327). Robot path planning based on PSO and D* algorithmsin dynamic environment. Proceedings of the 2017 International Conference on Current Research in Computer Science and Information Technology (ICCIT), Sulaymaniyah, Iraq.","DOI":"10.1109\/CRCSIT.2017.7965550"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Huang, H., Huang, P., Zhong, S., Long, T., Wang, S., Qiang, E., Zhong, Y., and He, L. (2019, January 15\u201317). Dynamic Path Planning Based on Improved D* Algorithms of Gaode Map. Proceedings of the 2019 IEEE 3rd Information Technology, Networking, Electronic and Automation Control Conference (ITNEC), Chengdu, China.","DOI":"10.1109\/ITNEC.2019.8729438"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/23\/7\/3512\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T19:04:21Z","timestamp":1760123061000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/23\/7\/3512"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,27]]},"references-count":26,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2023,4]]}},"alternative-id":["s23073512"],"URL":"https:\/\/doi.org\/10.3390\/s23073512","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,27]]}}}