Theoretical and Natural Science
- The Open Access Proceedings Series for Conferences
Theoretical and Natural Science
Vol. 19, 08 December 2023
Open
Access | Article
Optimization methods for A* and D* algorithms
* Author to whom correspondence should be addressed.
Abstract
With the Internet industry's development and the economy's rapid growth, the logistics industry has been overgrowing in recent years. It plays an irreplaceable role in the institutions of economic systems worldwide. However, the A* algorithm and the D* algorithm, which currently dominate the logistics industry's path planning algorithms, still have problems, such as long planning times and long planning paths, and there is much room for optimization. Starting with the conventional A* and D* algorithms, this study improves the planning times of the former by enhancing the heuristic function and the latter by increasing the judgment condition. After verification, the average optimization rate of both improved methods reaches more than 5%, improving the transport efficiency of the logistics industry.
Keywords
A* algorithms, D* algorithms, route planning.
References
1. L. Wang, S.-j. Lee, X.-f. Wu, B.-l. Liu, and J.-h. Xiao, "Contemporary Logistics in China," Springer Science and Business Media LLC, 2020.
2. A. Amling and P. J. Daugherty, "Logistics and distribution innovation in China," International Journal of Physical Distribution & Logistics Management, vol. 50, no. 3, pp. 323-332, 2020.
3. M. Giuffrida, R. Mangiaracina, A. Perego, and A. Tumino, "Cross-border B2C e-commerce to Greater China and the role of logistics: a literature review," International Journal of Physical Distribution & Logistics Management, 2017.
4. D. O. Pugas, M. Somantri, and K. I. Satoto, "Pencarian Rute Terpendek Menggunakan Algoritma Dijkstra dan Astar (A*) pada SIG Berbasis Web untuk Pemetaan Pariwisata Kota Sawahlunto," Transmisi, vol. 13, no. 1, pp. 27-32, 2011.
5. W. E. Wong, V. Debroy, R. Gao, and Y. Li, "The DStar method for effective software fault localization," IEEE Transactions on Reliability, vol. 63, no. 1, pp. 290-308, 2013.
6. L. Qin, J. X. Yu, and L. Chang, "Diversifying top-k results," arXiv preprint arXiv:1208.0076, 2012.
7. C. Hocaoglu and A. C. Sanderson, "Planning multiple paths with evolutionary speciation," IEEE transactions on evolutionary computation, vol. 5, no. 3, pp. 169-191, 2001.
8. Z. Wang, X. Xiang, J. Yang, and S. Yang, "Composite Astar and B-spline algorithm for path planning of autonomous underwater vehicle," in 2017 IEEE 7th International Conference on Underwater System Technology: Theory and Applications (USYS), 2017: IEEE, pp. 1-6.
9. C. Thorpe and L. Matthies, "Path relaxation: Path planning for a mobile robot," in OCEANS 1984, 1984: IEEE, pp. 576-581.
10. Y. Fan, F. Deng, and X. Shi, "Multi-robot task allocation and path planning system design," in 2020 39th Chinese Control Conference (CCC), 2020: IEEE, pp. 4759-4764.
11. L. Chang, X. Feng, X. Lin, L. Qin, and W. Zhang, "Efficient graph edit distance computation and verification via anchor-aware lower bound estimation," arXiv preprint arXiv:1709.06810, 2017.
12. H. Li, N. Xu, G. Liu, and J. Zhang, "An optimized 3D Astar algorithm for multi-layer PCB automatic routing," in 2021 IEEE International Conference on Consumer Electronics-Taiwan (ICCE-TW), 2021: IEEE, pp. 1-2.
13. S. Kambhampati and L. Davis, "Multiresolution path planning for mobile robots," IEEE Journal on Robotics and Automation, vol. 2, no. 3, pp. 135-145, 1986.
14. K. Sugihara and J. Smith, "Genetic algorithms for adaptive motion planning of an autonomous mobile robot," in Proceedings 1997 IEEE International Symposium on Computational Intelligence in Robotics and Automation CIRA'97.'Towards New Computational Principles for Robotics and Automation', 1997: IEEE, pp. 138-143.
15. Z. Xu, X. Liu, and Q. Chen, "Application of improved Astar algorithm in global path planning of unmanned vehicles," in 2019 Chinese Automation Congress (CAC), 2019: IEEE, pp. 2075-2080.
16. S. Shekhar, A. Kohli, and M. Coyle, "Path computation algorithms for advanced traveller information system (ATIS)," in Proceedings of IEEE 9th International Conference on Data Engineering, 1993: IEEE, pp. 31-39.
17. Z. Wang and X. Xiang, "Improved astar algorithm for path planning of marine robot," in 2018 37th Chinese Control Conference (CCC), 2018: IEEE, pp. 5410-5414.
Data Availability
The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International 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 Instruction).
- Volume Title
- Proceedings of the 2nd International Conference on Computing Innovation and Applied Physics
- ISBN (Print)
- 978-1-83558-203-9
- ISBN (Online)
- 978-1-83558-204-6
- Published Date
- 08 December 2023
- Series
- Theoretical and Natural Science
- ISSN (Print)
- 2753-8818
- ISSN (Online)
- 2753-8826
- DOI
- 10.54254/2753-8818/19/20230493
- Copyright
- 08 December 2023
- Open Access
- This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited