Download pdf
Modified A* algorithm for path smoothing and obstacle avoidance
- 1 School of Mechanical Engineering and Automation, Dalian Polytechnic University, Dalian, Liaoning, 116034, China
* Author to whom correspondence should be addressed.
Abstract
With the rapid development of robotics technology, path planning is a crucial aspect of autonomous robot systems. Among them, planning paths involves using the A* algorithm, which is a common method. However, traditional A* algorithm has several limitations in path planning, such as poor real-time performance, large amount of computation per node, long computation time, low algorithmic search efficiency. Based on this, two improved approaches for the A* algorithm are proposed. The first is expanding the obstacles in the map by increasing their expansion radius. The second is the Hybrid A* algorithm, which optimizes the A* algorithm by modifying its heuristic function. Specifically, the Hybrid A* algorithm combines two heuristic functions: one based on non-holonomic constraints and the other based on dynamic programming. Experimental tests are conducted under various map expansions and branching parameters to compare the performance of these two algorithms in terms of path length, execution time, and path smoothness at corners. The results demonstrate that, with smaller branching parameters, the Hybrid A* algorithm generates shorter paths. However, in highly complex mazes, the path length of the Hybrid A* algorithm may be longer, but it exhibits smoother movements at corners.
Keywords
path-planning, A* algorithm, Hybrid A* algorithm, optimization methods
[1]. S. a. J. J. a. S. H. a. Y. Y. Chen, 2023, Improved A-star Method for Collision Avoidance and Path Smoothing, in 2023 IEEE International Conference on Control, Electronics and Computer Technology (ICCECT), pp. 32-35.
[2]. H. a. Z. L. a. L. H. a. W. C. a. Q. Z. a. Q. Y. Zou, 2010, Optimized Application and Practice of A* Algorithm in Game Map Path-Finding, in 2010 10th IEEE International Conference on Computer and Information Technology, pp. 2138-2142.
[3]. Z. a. W. S. a. Z. J. Zhang, 2021, A-star algorithm for expanding the number of search directions in path planning, in 2021 2nd International Seminar on Artificial Intelligence, Networking and Information Technology (AINIT), pp. 208-211.
[4]. F. D. a. A. B. a. M. K. a. P. B. a. M. F. a. T. F. a. L. Jurišica, 2014, Path Planning with Modified a Star Algorithm for a Mobile Robot, Procedia Engineering, vol. 96, pp. 59-69.
[5]. J. Y. J. L. H. T. X. &. G. M. Liu, 2017, An improved ant colony algorithm for robot path planning, Soft computing, vol. 21, pp. 5829-5839.
[6]. D. a. Z. Y. a. L. Q. a. W. T. Huang, 2022, Research on Path Planning of Mobile Robot Based on Improved A-Star Algorithm, in 2022 International Conference on Informatics, Networking and Computing (ICINC), pp. 251-255.
[7]. J. W. Z. a. H. X. Huiqun, 2018, Path planning based on improved particle swarm optimization algorithm, Journal of agricultural machinery, vol. 49, no. 12, pp. 371-377.
[8]. Chang C, 2020, Research and Application on Path Planning Based on Improved A-Star Algorithm, Nanjing University.
[9]. L. S. J. J. W. Y. L. W. L. T. Wang H, 2022 , The EBS-A* algorithm: An improved A* algorithm for path planning, PLoS ONE, vol. 17, no. 2.
[10]. D. A. Dolgov, 2008, Practical Search Techniques in Path Planning for Autonomous Driving.
[11]. D. a. T. S. a. M. M. a. D. J. Dolgov, 2010, Path Planning for Autonomous Vehicles in Unknown Semi-structured Environments, I. J. Robotic Res., vol. 29, pp. 485-501.
[12]. Y. a. W. Z. a. Z. S. Li, 2022, Path Planning of Robots Based on an Improved A-star Algorithm, in 2022 IEEE 5th Advanced Information Management, Communicates, Electronic and Automation Control Conference (IMCEC), vol. 5, pp. 826-831.
Cite this article
Geng,H. (2024). Modified A* algorithm for path smoothing and obstacle avoidance. Applied and Computational Engineering,33,167-175.
Data availability
The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.
Disclaimer/Publisher's Note
The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.
About volume
Volume title: Proceedings of the 2023 International Conference on Machine Learning and Automation
© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and
conditions of the Creative Commons Attribution (CC BY) license. Authors who
publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons
Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this
series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published
version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial
publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and
during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See
Open access policy for details).