Download pdf
A fast convergence bidirectional a star path planning algorithm
- 1 Northwest Polytechnic University
* Author to whom correspondence should be addressed.
Abstract
A* and bidirectional A* have been classical pathfinding algorithms for long with many derivatives specially designed for their exclusive situations. To solve the problem of the bidirectional A* algorithm being inefficient in some situations, this paper gives a kind of optimized algorithm with a new dynamic parameter in the heuristic function and a 25% increase in efficiency. By modifying the weights, the proportion between distance and efficiency can be well balanced. This paper uses some typical problems for simulation and paints the scatter diagram of different weights to figure out the relationship between the weight and the balance. In the end, the author gives suggestions on optimizing the coefficient due to the rule, which stands for gradually promoting the weight of the dynamic parameter until the path doesn’t keep optimal, for various situations and how to further modify the heuristic function for better performance.
Keywords
Heuristic Algorithm, Path Planning; Bidirectional A* Algorithm, Efficiency Improvement
[1]. P. O. N. Saian, Suyoto and Pranowo. (2016). "Optimized A-Star algorithm in hexagon-based environment using parallel bidirectional search," 2016 8th International Conference on Information Technology and Electrical Engineering (ICITEE), Yogyakarta, Indonesia, pp. 1-5, doi: 10.1109/ICITEED.2016.7863246.
[2]. Barker, J., & Korf, R. (2015). Limitations of Front-To-End Bidirectional Heuristic Search. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1).
[3]. Barker, J. K. (2015). Front-To-End Bidirectional Heuristic Search. UCLA. ProQuest ID: Barker_ucla_0031D_13333. Merritt ID: ark:/13030/m5gq95nz. Retrieved from https://escholarship.org/uc/item/5j34j5bj
[4]. Fu L , Sun D , Rilett L R . (2005). Heuristic shortest path algorithms for transportation applications: State of the art [J]. Computers & Operations Research, 33(11):3324-3343.
[5]. Liu, Chenguang, Qingzhou Mao, Xiumin Chu, and Shuo Xie. 2019. "An Improved A-Star Algorithm Considering Water Current, Traffic Separation and Berthing for Vessel Path Planning" Applied Sciences 9, no. 6: 1057.
[6]. Erke S, Bin D, Yiming N, Qi Z, Liang X, Dawei Z. (2020). An improved A-Star based path planning algorithm for autonomous land vehicles. International Journal of Advanced Robotic Systems. 17(5). doi:10.1177/1729881420962263.
[7]. Dexin Yu, Luchen Wang, Xincheng Wu, Zhuorui Wang, Jianyu Mao, and Xiyang Zhou. (2023). "Implementation and visualization of weighted A-Star algorithm and bidirectional weighted A-Star algorithm under large-scale road network", Proc. SPIE 12604, International Conference on Computer Graphics, Artificial Intelligence, and Data Processing (ICCAID 2022), 126040F (23 May 2023)
[8]. P. E. Hart, N. J. Nilsson and B. Raphael. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," in IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100-107, July 1968, doi: 10.1109/TSSC.1968.300136.
[9]. Thi Thoa Mac, Cosmin Copot, Duc Trung Tran, Robin De Keyser. (2016). Heuristic approaches in robot path planning: A survey. Robotics and Autonomous Systems. Volume 86. 13-28. ISSN 0921-8890.
[10]. Rios, L. H. O., & Chaimowicz, L. (2011). Pnba*: A parallel bidirectional heuristic search algorithm. In ENIA VIII Encontro Nacional de Inteligê ncia Artificial.
Cite this article
Luo,Y. (2024). A fast convergence bidirectional a star path planning algorithm. Applied and Computational Engineering,54,241-247.
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 4th International Conference on Signal Processing and Machine Learning
© 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).