Comparative Analysis of Path Planning Algorithms and Prospects for Practical Application
DOI:
https://doi.org/10.54097/hset.v52i.8889Keywords:
Route planning, artificial intelligence, transportation, traditional methods, new methods.Abstract
Path planning, as an important applications of artificial intelligence technology in the field of intelligent transportation, has a wide range of application prospects in achieving efficient, intelligent, and safe travel. This paper first introduces the importance of path planning technology in the field of transportation, and then discusses the development of path planning from two aspects: traditional methods and new methods based on artificial intelligence. In terms of traditional methods, the principles and advantages and disadvantages of methods such as Dijkstra's algorithm, A* algorithm, and Floyd's algorithm are included. In terms of new methods based on artificial intelligence, the principles and application examples of methods such as genetic algorithms, simulated annealing algorithms, and deep reinforcement learning are included. Finally, the problems existing in path planning field are analyzed, and the future research directions are prospected in order to provide useful references for the development of intelligent transportation.
Downloads
References
Chen, T., & Shen, G. (2019). Review of intelligent transportation systems for urban network traffic signal control. IET Intelligent Transport Systems, 13(1), 1-11.
Fiorini, P., & Shiller, Z. (1998). Motion planning in dynamic environments using velocity obstacles. The International Journal of Robotics Research, 17(7), 760-772.
LaValle, S. M. (2006). Planning algorithms. Cambridge University Press.
Choset, H., Lynch, K. M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L. E., & Thrun, S. (2005). Principles of robot motion: Theory, algorithms, and implementation. MIT Press.
Ge, S. S., & Yang, Y. (2010). Autonomous mobile robots: Sensing, control, decision-making, and applications. CRC Press.
Kumar, S., & Cohen, I. (2000). Global path planning for autonomous robot navigation. In Proceedings of the IEEE-INNS-ENNS International Joint Conference on Neural Networks (Vol. 3, pp. 165-170). IEEE.
Fiorini, P., & Shiller, Z. (1998). Motion planning in dynamic environments using velocity obstacles. The International Journal of Robotics Research, 17(7), 760-772.
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
Zhan, F. B., & Noon, C. E. (1998). Shortest path algorithms: An evaluation using real road networks. Transportation Science, 32(1), 65-73.
Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2), 163-177.
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107.
Yang, S. X., & Meng, M. (2000). Path Planning with Modified a Star Algorithm for a Mobile Robot. Proceedings of the 2000 IEEE International Conference on Robotics and Automation, 2000, 2, 1177-1182. doi: 10.1109/ROBOT.2000.844739
LaValle, S. M. (1998). Rapidly-exploring random trees: A new tool for path planning. Technical Report TR 98-11, Computer Science Department, Iowa State University.
LaValle, S. M., & Kuffner, J. J. (2001). Randomized Kinodynamic Planning. The International Journal of Robotics Research, 20(5), 378-400.
Kuwata, Y., Fiore, G. A., Teo, J., Frazzoli, E., & How, J. P. (2008). Motion planning for urban driving using RRT. 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 1681-1686.
Kim, S., Lee, S., Lee, M., & Myung, H. (2018). Autonomous drone navigation system for indoor environments using RRT-based path planner and artificial potential field. 2018 15th International Conference on Ubiquitous Robots (UR), 887-891.
Stentz, A. (1994). Optimal and Efficient Path Planning for Partially-Known Environments. Proceedings of the IEEE International Conference on Robotics and Automation, 1994, 3310-3317.
Stentz, A. (1995). The Focussed D* Algorithm for Real-Time Replanning. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 1995, 1652-1659.
Manandhar, S., Song, J. B., & Yim, S. (2017). A modified D* lite algorithm for unmanned ground vehicle navigation in a dynamic urban environment. 2017 14th International Conference on Ubiquitous Robots and Ambient Intelligence (URAI), 519-524.
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., ... & Hassabis, D. (2015). Human-level control through deep reinforcement learning. Nature, 518(7540), 529-533.
Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., ... & Wierstra, D. (2015). Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.02971.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., & Klimov, O. (2017). Proximal Policy Optimization Algorithms. arXiv preprint arXiv:1707.06347.
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
