{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T01:53:43Z","timestamp":1783043623476,"version":"3.54.6"},"reference-count":31,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2021,11,19]],"date-time":"2021-11-19T00:00:00Z","timestamp":1637280000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Path planning plays an essential role in mobile robot navigation, and the A* algorithm is one of the best-known path planning algorithms. However, the conventional A* algorithm and the subsequent improved algorithms still have some limitations in terms of robustness and efficiency. These limitations include slow algorithm efficiency, weak robustness, and collisions when robots are traversing. In this paper, we propose an improved A*-based algorithm called EBHSA* algorithm. The EBHSA* algorithm introduces the expansion distance, bidirectional search, heuristic function optimization and smoothing into path planning. The expansion distance extends a certain distance from obstacles to improve path robustness by avoiding collisions. Bidirectional search is a strategy that searches for a path from the start node and from the goal node at the same time. Heuristic function optimization designs a new heuristic function to replace the traditional heuristic function. Smoothing improves path robustness by reducing the number of right-angle turns. Moreover, we carry out simulation tests with the EBHSA* algorithm, and the test results show that the EBHSA* algorithm has excellent performance in terms of robustness and efficiency. In addition, we transplant the EBHSA* algorithm to a robot to verify its effectiveness in the real world.<\/jats:p>","DOI":"10.3390\/sym13112213","type":"journal-article","created":{"date-parts":[[2021,11,19]],"date-time":"2021-11-19T08:29:17Z","timestamp":1637310557000},"page":"2213","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":75,"title":["An Efficient and Robust Improved A* Algorithm for Path Planning"],"prefix":"10.3390","volume":"13","author":[{"given":"Huanwei","family":"Wang","sequence":"first","affiliation":[{"name":"State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xuyan","family":"Qi","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shangjie","family":"Lou","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jing","family":"Jing","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hongqi","family":"He","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wei","family":"Liu","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2021,11,19]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/j.procs.2018.07.018","article-title":"Methodology for path planning and optimization of mobile robots: A review","volume":"133","author":"Zafar","year":"2018","journal-title":"Procedia Comput. Sci."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Injarapu, A.S.H.H.V., and Gawre, S.K. (2017, January 27\u201329). A survey of autonomous mobile robot path planning approaches. Proceedings of the 2017 International Conference on Recent Innovations in Signal Processing and Embedded Systems (RISE), Bhopal, India.","DOI":"10.1109\/RISE.2017.8378228"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Costa, M.M., and Silva, M.F. (2019, January 24\u201326). A survey on path planning algorithms for mobile robots. Proceedings of the 2019 IEEE International Conference on Autonomous Robot Systems and Competitions (ICARSC), Porto, Portugal.","DOI":"10.1109\/ICARSC.2019.8733623"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.robot.2016.08.001","article-title":"Heuristic approaches in robot path planning: A survey","volume":"86","author":"Mac","year":"2016","journal-title":"Robot. Auton. Syst."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.proeng.2014.12.098","article-title":"Path planning with modified a star algorithm for a mobile robot","volume":"96","author":"Babinec","year":"2014","journal-title":"Procedia Eng."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1109\/MITS.2019.2903536","article-title":"Trajectory planning and tracking for autonomous vehicle based on state lattice and model predictive control","volume":"11","author":"Zhang","year":"2019","journal-title":"IEEE Intell. Transp. Syst. Mag."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"103565","DOI":"10.1016\/j.robot.2020.103565","article-title":"Rapidly-exploring Random Trees multi-robot map exploration under optimization framework","volume":"131","author":"Zhang","year":"2020","journal-title":"Robot. Auton. Syst."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1564","DOI":"10.1016\/j.compeleceng.2012.06.016","article-title":"Dynamic path planning of mobile robots with improved genetic algorithm","volume":"38","author":"Tuncer","year":"2012","journal-title":"Comput. Electr. Eng."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"448","DOI":"10.3390\/vehicles3030027","article-title":"A Survey of Path Planning Algorithms for Mobile Robots","volume":"3","author":"Karur","year":"2021","journal-title":"Vehicles"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Dudi, T., Singhal, R., and Kumar, R. (2020, January 23\u201326). Shortest Path Evaluation with Enhanced Linear Graph and Dijkstra Algorithm. Proceedings of the 2020 59th Annual Conference of the Society of Instrument and Control Engineers of Japan (SICE), Chiang Mai, Thailand.","DOI":"10.23919\/SICE48898.2020.9240227"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1504\/IJVAS.2017.087148","article-title":"Global path planning for autonomous vehicles in off-road environment via an A-star algorithm","volume":"13","author":"Liu","year":"2017","journal-title":"Int. J. Veh. Auton. Syst."},{"key":"ref_13","first-page":"1","article-title":"Overview of Global Path Planning Algorithms for Mobile Robots","volume":"48","author":"Ziqiang","year":"2021","journal-title":"Comput. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Sedighi, S., Nguyen, D.V., and Kuhnert, K.D. (2019, January 19\u201322). Guided hybrid A-star path planning algorithm for valet parking applications. Proceedings of the 2019 5th International Conference on Control, Automation and Robotics (ICCAR), Beijing, China.","DOI":"10.1109\/ICCAR.2019.8813752"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Liu, C., Mao, Q., Chu, X., and Xie, S. (2019). An improved A-star algorithm considering water current, traffic separation and berthing for vessel path planning. Appl. Sci., 9.","DOI":"10.3390\/app9061057"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"172988142096226","DOI":"10.1177\/1729881420962263","article-title":"An improved A-Star based path planning algorithm for autonomous land vehicles","volume":"17","author":"Erke","year":"2020","journal-title":"Int. J. Adv. Robot. Syst."},{"key":"ref_17","first-page":"217","article-title":"Improvement and verification of A-star algorithm for AGV path planning","volume":"54","author":"Zhao","year":"2018","journal-title":"Comput. Eng. Appl."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Kim, H., Park, B., and Myung, H. (2013). Curvature path planning with high resolution graph for unmanned surface vehicle. Robot Intelligence Technology and Applications (RiTA), Springer.","DOI":"10.1007\/978-3-642-37374-9_15"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/j.apor.2018.12.001","article-title":"Smoothed A* algorithm for practical unmanned surface vehicle path planning","volume":"83","author":"Song","year":"2019","journal-title":"Appl. Ocean Res."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Gunawan, S.A., Pratama, G.N., Cahyadi, A.I., Winduratna, B., Yuwono, Y.C., and Wahyunggoro, O. (2019, January 24\u201325). Smoothed A-star Algorithm for Nonholonomic Mobile Robot Path Planning. Proceedings of the 2019 International Conference on Information and Communications Technology (ICOIACT), Yogyakarta, Indonesia.","DOI":"10.1109\/ICOIACT46704.2019.8938467"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Sheikh, T.S., and Afanasyev, I.M. (2018). Stereo vision-based optimal path planning with stochastic maps for mobile robot navigation. International Conference on Intelligent Autonomous Systems, Springer.","DOI":"10.1007\/978-3-030-01370-7_4"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/j.oceaneng.2018.09.016","article-title":"A constrained A* approach towards optimal path planning for an unmanned surface vehicle in a maritime environment containing dynamic obstacles and ocean currents","volume":"169","author":"Singh","year":"2018","journal-title":"Ocean. Eng."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Cheng, L., Liu, C., and Yan, B. (2014, January 28\u201330). Improved hierarchical A-star algorithm for optimal parking path planning of the large parking lot. Proceedings of the 2014 IEEE International Conference on Information and Automation (ICIA), Hailar, China.","DOI":"10.1109\/ICInfA.2014.6932742"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1515\/ijnaoe-2015-0007","article-title":"Path planning on satellite images for unmanned surface vehicles","volume":"7","author":"Yang","year":"2015","journal-title":"Int. J. Nav. Archit. Ocean Eng."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Yao, J., Lin, C., Xie, X., Wang, A., and Hung, C.C. (2010, January 12\u201314). Path Planning for Virtual Human Motion Using Improved A* Star Algorithm. Proceedings of the 2010 Seventh International Conference on Information Technology, New Generations, Las Vegas, NV, USA.","DOI":"10.1109\/ITNG.2010.53"},{"key":"ref_26","first-page":"42","article-title":"Feasible Path Search and Optimization Based on Improved A* Algorithm","volume":"23","author":"Gao","year":"2005","journal-title":"J. Civ. Aviat. Univ. China"},{"key":"ref_27","first-page":"171","article-title":"Robot Path Planning Based on Improved A* Algorithm","volume":"15","author":"Peng","year":"2015","journal-title":"Cybern. Inf. Technol."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1016\/j.protcy.2016.03.010","article-title":"Time-Efficient A* Algorithm for Robot Path Planning","volume":"23","author":"Guruji","year":"2016","journal-title":"Procedia Technol."},{"key":"ref_29","first-page":"315","article-title":"A dynamic path planning algorithm for robots with both global and local characteristics","volume":"35","author":"Zhang","year":"2018","journal-title":"J. Surv. Mapp. Sci. Technol."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"59196","DOI":"10.1109\/ACCESS.2021.3070054","article-title":"Geometric A-Star Algorithm: An Improved A-Star Algorithm for AGV Path Planning in a Port Environment","volume":"9","author":"Tang","year":"2021","journal-title":"IEEE Access"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1016\/j.robot.2018.04.007","article-title":"An improved A* algorithm for the industrial robot path planning with high success rate and short length","volume":"106","author":"Fu","year":"2018","journal-title":"Robot. Auto. Syst."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/11\/2213\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:32:53Z","timestamp":1760167973000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/11\/2213"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,19]]},"references-count":31,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2021,11]]}},"alternative-id":["sym13112213"],"URL":"https:\/\/doi.org\/10.3390\/sym13112213","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,19]]}}}