Abstract
Background: Path-planning algorithms are widely used in robotics, vehicles, UAVs, carrier- based aircraft towing vehicles, etc. Using these algorithms, an optimal path with safe obstacle avoidance and high efficiency can be planned. In recent years, path-planning algorithms have received more and more attention from scholars at home and abroad.
Objective: In order to promote the application and development of path-planning algorithms, an indepth analysis of the current development status of path-planning algorithms was presented. In patents and literature, The most widely used and representative algorithms in several representative results were extracted, and the characteristics and advantages and disadvantages of each algorithm were analyzed and elaborated in detail for the readers' reference.
Methods: The existing path-planning algorithms were classified, and a brief overview of each traditional algorithm was given, followed by an in-depth study of the improved algorithms to summarize the advantages and disadvantages of each type of algorithm. Finally, based on these research results, the future development trend of path-planning algorithms was projected.
Results: Through the research and analysis of the path-planning algorithm, it was found that the path- planning algorithm before the improvement had the problems of an unsmooth path, low computational efficiency, a slow response time, the inability to safely avoid obstacles, etc. After the improvement and optimization of the path-planning algorithm, the performance was greatly improved.
Conclusion: After research and analysis, it was found that multi-algorithm fusion had great potential for development in path-planning compared to the application and optimization of a single algorithm. In addition, further research is needed in the areas of algorithm adaptability, fusion, intelligent algorithms, and extending the range of algorithmic applications.
Graphical Abstract
[1]
J.C. Yang, S.H. Li, and Z.Y. Cai, "Research and development of path planning algorithm", Control Eng., vol. 24, no. 07, pp. 1473-1480, 2017.
[2]
H. Chen, G.L. Wang, and X. Hao, "Review and development trend of path planning for mobile robots", Log. Tech. Appl., vol. 25, no. 10, pp. 158-160, 2020.
[3]
S.B. Li, Q.S. Song, Z.A. Li, X.X. Zhang, and L.X. Zhe, "A review of research on genetic algorithms in robot path planning", Sci. Technol. Eng., vol. 20, no. 02, pp. 423-431, 2020.
[4]
H.G. Qi, "Research on deep reinforcement learning-based path planning for mobile robots", M.S. thesis, Jilin University, China, vol. 42, no. 42, pp. 15-222021.
[5]
T. Wang, Y.K. Lai, and W.X. Liu, "Current status of unmanned vehicle path planning algorithm development", Ship Electronics Engineering, vol. 42, no. 05, pp. 15-22, 2022.
[6]
Y.D. Li, T.L. Ma, C.B. Chen, H.L. Wei, and Q.N. Yang, "A review of path planning algorithms for driverless vehicles", In: Foreign Electronic Measurement Technol., vol. 36. 2019, no. 6, pp. 72-79.
[7]
J. Zhang, Y. Wu, and X.J. Qu, "Path planning method for shipboard aircraft traction system", J. Beijing Univer. Aeronaut., vol. 44, no. 10, pp. 2125-2133, 2018.
[8]
Y.M. Gong, Y.L. Luo, S. Han, X.D. Zhao, and H.X. Li, "Deck mobile equipment transfer path planning and simulation verification", In: Ship Engineering, vol. 43, no. 2, pp. 64-69+81, 2021.
[9]
M. Yu, X. Gong, G. Fan, and Y. Zhang, "Trajectory planning and tracking for carrier aircraft-tractor system based on autonomous and cooperative movement", Math. Probl. Eng., vol. 2020, pp. 1-24, 2020.
[http://dx.doi.org/10.1155/2020/6531984]
[http://dx.doi.org/10.1155/2020/6531984]
[10]
J.J. Tang, Z.Q. Zhu, Y.Y. Wang, Y. Liu, and Y.H. Fang, "Modeling analysis of carrier-based aircraft’s scheduling on flight deck", J. Phys., vol. 1746, 2021.
[http://dx.doi.org/10.1088/1742-6596/1746/1/012002]
[http://dx.doi.org/10.1088/1742-6596/1746/1/012002]
[11]
H.X. Lin, and D. Xiang, "A review of research on path planning algorithms for mobile robots", Comput. Eng. Appl., vol. 57, no. 18, pp. 38-48, 2021.http://cea.ceaj.org/CN/article/advancedSearchResult.do
[12]
Y. Xue, "Research on multi-objective path planning for mobile robots", M.S. thesis, Tianjin University, China, 2019.
[14]
X.Y. Xu, "Research on outdoor mobile robot localization and path planning algorithm", M.S. thesis, Beijing University, China., 2021.
[15]
Z.Q. Wang, X.G. Hu, X.X. Li, and Z.Q. Du, "A review of global path planning algorithms for mobile robots", Comput. Sci., vol. 48, no. 10, pp. 19-29, 2021.
[16]
J. Zhu, "Research on path planning of unmanned vehicles based on deep reinforcement learning", M.S. thesis, Xi'an University, China., 2021.
[17]
S.Y. Ma, D.C. Huang, H.L. Xu, and H.Y. Fu, "A review of path planning algorithms for surface unmanned boats", Automation Expo, vol. 38, no. 11, pp. 68-71, 2021.
[18]
P. Udhan, A. Ganeshkar, P. Murugesan, R.P. Abhishek, S. Sameep, and D. Parth, "Vehicle route planning using dynamically weighted dijkstra’s algorithm with traffic prediction", Arxiv, 2022. https://arxiv.org/abs/2205.15190
[19]
J.L. Liu, W.B. Zhang, H.B. Ji, and M.Z. Zhu, "A review of UAV cluster path planning algorithm research", Aero. Elec. Count., vol. 38, no. 1, pp. 9-12, 2022. https://kns.cnki.net/kns8/defaultresult/index
[20]
S.F. Pan, "A review of research on path planning algorithms for driverless cars", Automotive Practical Technol., vol. 47, no. 04, pp. 162-165, 2022.
[21]
B.J. Ni, "A roadless network path planning method based on a raster network", Jiangsu Sci. Technol. Informat., vol. 39, no. 07, pp. 49-52, 2022.
[22]
L. Jiang, W.Y. Jia, L. Liu, L.D. Liang, and W.T. Wei, "Optimal node A-star algorithm for operational path planning of wheeled mobile robots under energy consumption optimization", In: Mech. Sci.Tech., pp. 1-7, 2022.
[23]
S. Schoenberg, and F. Dressler, "Reducing waiting times at charging stations with adaptive electric vehicle route planning", IEEE Trans. Intell. Veh., vol. 8, no. 1, pp. 95-107, 2023.
[http://dx.doi.org/10.1109/TIV.2022.3140894]
[http://dx.doi.org/10.1109/TIV.2022.3140894]
[24]
J.D. Zhou, L. Yang, and C. Zhang, "Improved a~* algorithm for indoor robot path planning", Mod. Elect. Tech., vol. 45, no. 08, pp. 181-186, 2022.
[25]
K. Feng, X. Ji, and X. Yang, "Application of a* algorithm in self-driving vehicle path planning", Aut. Prac. Tech., vol. 45, no. 22, pp. 25-28, 2020.
[26]
W.N. Shu, J.S. Zhao, Z.X. Xie, X.S. Zhang, and X. Ma, "Surface unmanned boat path planning based on improved a~* algorithm", J. Shang. Mari. Uni., vol. 43, no. 02, pp. 1-6, 2022.
[27]
C. Liu, Q. Mao, X. Chu, and S. Xie, "An improved a-star algorithm considering water current, traffic separation and berthing for vessel path planning", Appl. Sci., vol. 9, no. 6, p. 1057, 2019.
[http://dx.doi.org/10.3390/app9061057]
[http://dx.doi.org/10.3390/app9061057]
[28]
F. Duchoň, A. Babinec, M. Kajan, P. Beňo, M. Florek, T. Fico, and L. Jurišica, "Path planning with modified a star algorithm for a mobile robot", Procedia Eng., vol. 96, pp. 59-69, 2014.
[http://dx.doi.org/10.1016/j.proeng.2014.12.098]
[http://dx.doi.org/10.1016/j.proeng.2014.12.098]
[29]
Y.W. Kang, "Research on obstacle avoidance path planning algorithm for mobile robot", M.S. thesis, Hubei University, China., 2021.
[30]
J.W. Shen, "Research on automatic driving path trajectory planning based on improved rrt algorithm", M.S. thesis, Zhejiang Normal University, China, 2021.
[31]
Q.L. Chen, H.Y. Jiang, and Y.J. Zheng, "A review of fast extended random tree algorithms for robot path planning", Comput. Eng. Appl., vol. 55, no. 16, pp. 10-17, 2019.
[32]
S. Wang, R.K. Duan, and Y.H. Liao, "Improvement of fast extended random tree algorithm in robot path planning", J. Xi’an Jiao Tong Uni., vol. 56, no. 07, pp. 1-8, 2022.
[33]
W.L. Hu, "Improved rrt-based vehicle path planning", Prac. Aut. Tech., vol. 46, no. 06, pp. 45-47, 2021.
[34]
R. Zhang, L. Zhou, and Z.K. Liu, "Mobile robot path planning based on MOBDB-RRT~* algorithm", In: Electro-Optics Control, vol. 29, no. 7, pp. 12-16+36, 2022.
[35]
X.G. Ruan, S.D. Liu, and X.Q. Zhu, "AHMRRT-based path planning algorithm for mobile robots", J. Beijing Uni. Tech., vol. 48, no. 02, pp. 121-128, 2022.
[36]
H.X. Xia, "Research on unmanned vehicle path planning method based on improved rrt algorithm", M.S. thesis, Jilin University, China., 2019.
[37]
G. Zhao, "Improved RRT* algorithm for intelligent vehicle path planning", Aut. Prac. Tech., vol. 46, no. 22, pp. 41-43, 2021.
[38]
R.Y. Song, H.X. Que, Z.Y. Ma, and H.C. Lan, "Research on self-driving vehicle path planning based on improved RRT~* algorithm", Aut. Prac. Tech., vol. 46, no. 01, pp. 20-22, 2021.
[39]
Z. P. Wang, Y. S. Li, H. Zhang, and Q. J. Chen, "An improved fast search random tree path planning method for unmanned vehicles", C.N patent.108196536B, 2021.
[40]
P. C. Shi, G. Z. Liu, J. F. Yang, P. Wan, H. Qi, X. H. Chen, L. X. Gao, Z. J. Pan, S. B. Yang, and Y. F. Ma, "An improved two-way fast search random tree algorithm for intelligent vehicle path planning method", C.N patent.113064426B, 2022.
[41]
Y. Tao, H. Gao, F. Ren, C. Chen, T. Wang, H. Xiong, and S. Jiang, "A mobile service robot global path planning method based on ant colony optimization and fuzzy control", Appl. Sci., vol. 11, no. 8, p. 3605, 2021.
[http://dx.doi.org/10.3390/app11083605]
[http://dx.doi.org/10.3390/app11083605]
[42]
Y.Y. Chen, and X.M. Zhou, "Path planning of robot based on improved ant colony algorithm in computer technology", Journal of Physics: Conference Series, 2020 International Conference on Mechanical Automation and Computer Engineering, Shanxi, China vol. 1744,, 2020 .https://iopscience.iop.org/article/10.1088/1742-6596/1744/4/042092/meta
[43]
M. Pluciński, "Application of the ant colony algorithm for the path planning", In: Enhanced Methods in Computer Security, Biometric and Artificial Intelligence Systems., Springer: Boston, MA, 2005, pp. 345-352.
[http://dx.doi.org/10.1007/0-387-23484-5_34]
[http://dx.doi.org/10.1007/0-387-23484-5_34]
[44]
C. He, "Research on the path of same-city fresh food pickup and delivery vehicles based on ant colony algorithm", M.S. thesis, North Central University ,China., 2021.
[45]
Y.H. Wang, D.M. Gao, and X.D. Wang, "Shortest path planning based on improved ant colony algorithm", ASP Transactions on Computers, vol. 1, no. 3, pp. 6-11, 2021.
[http://dx.doi.org/10.52810/TC.2021.100077]
[http://dx.doi.org/10.52810/TC.2021.100077]
[46]
Y. Pu, J. Gong, D.C. Li, and Z.X. Sun, "An introduction to the application of ant colony algorithm in path planning problem", In: Log. Eng. Manag., vol. 43. 2021, no. 7, pp. 43-45+26.
[47]
S.S. Li, G.H. Zhao, and W.X. Yue, Research on path planning for mobile robot based on improved ant colony algorithm 2nd International Conference on Computer Science and Communication Technology (ICCSCT), vol. 2026. .Beijing, China,
2021 [http://dx.doi.org/10.1088/1742-6596/2026/1/012049]
2021 [http://dx.doi.org/10.1088/1742-6596/2026/1/012049]
[48]
H. G. Wu, and Y. L. Gao, "Application of improved ant colony algorithm in static vehicle path planning", J. Baoji College Arts Sci., vol. 40, no. 4, pp. 25-30+38, 2020.
[49]
L.L. Fu, H. Chen, and W.J. Gong, "Path planning for underwater robots based on improved ant colony algorithm", Aut. Inst., vol. 37, no. 04, pp. 46-50, 2022.
[50]
D. Lan, D.H. Fan, Q. Chen, and W. Wei, "The use of improved ant colony algorithm in intelligent vehicle path planning", In: Combined machine tools and automated machining technology, vol. 4. 2021, pp. 130-133+138.
[51]
S.B. Li, and J.K. Peng, "Optimal path planning method for traffic networks based on improved ant colony algorithm", J. Guizhou Univ., vol. 39, no. 05, pp. 88-93, 2022.
[52]
X.X. Li, X.L. Ma, and X.P. Wang, "A review of path planning algorithms for mobile robots", Jisuanji Celiang Yu Kongzhi, vol. 30, no. 07, pp. 9-19, 2022.
[53]
M.A. Damos, J. Zhu, W. Li, A. Hassan, and E. Khalifa, "A novel urban tourism path planning approach based on a multiobjective genetic algorithm", ISPRS Int. J. Geoinf., vol. 10, no. 8, p. 530, 2021.
[http://dx.doi.org/10.3390/ijgi10080530]
[http://dx.doi.org/10.3390/ijgi10080530]
[54]
M. Li, M. Huang, Z.F. Cheng, and J. Zhou, "Application of the genetic algorithm on path planning", Comp. Syst. Appl., vol. 29, no. 08, pp. 255-260, 2020.
[55]
Y.V. Pehlivanoglu, and P. Pehlivanoglu, "An enhanced genetic algorithm for path planning of autonomous UAV in target coverage problems", Appl. Soft Comput., vol. 112, no. 112, p. 107796, 2021.
[http://dx.doi.org/10.1016/j.asoc.2021.107796]
[http://dx.doi.org/10.1016/j.asoc.2021.107796]
[56]
Y. Tao, Y. Wen, H. Gao, T. Wang, J. Wan, and J. Lan, "A Path-Planning Method for Wall Surface Inspection Robot Based on Improved Genetic Algorithm", Electronics, vol. 11, no. 8, p. 1192, 2022.
[http://dx.doi.org/10.3390/electronics11081192]
[http://dx.doi.org/10.3390/electronics11081192]
[57]
J. Shao, "Robot path planning method based on genetic algorithm", Journal of Physics: Conference Series, The 2nd International Conference on Computing and Data Science (CONF-CDS), January 2021 Stanford, United..
[http://dx.doi.org/10.1088/1742-6596/1881/2/022046]
[http://dx.doi.org/10.1088/1742-6596/1881/2/022046]
[58]
J.R. Liu, "An improved genetic algorithm for rapid uav path planning", Journal of Physics: Conference Series, 3rd International Conference on Robotics, Intelligent Control and Artificial Intelligence, vol. 2216, no. 1, 2022.
[http://dx.doi.org/10.1088/1742-6596/2216/1/012035]
[http://dx.doi.org/10.1088/1742-6596/2216/1/012035]
[59]
X. Xu, X.Y. Yu, Y. Zhao, C.X. Liu, and X. Wu, "Global path planning for mobile robots based on improved genetic algorithm", Jisuanji Jicheng Zhizao Xitong, vol. 28, no. 06, pp. 1659-1672, 2022.
[60]
B. Yang, S.D. Liu, W.J. Lu, and Y.H. Pan, "Application of improved genetic algorithm in robot path planning", Modern Manufacturing Engineering, no. 06, pp. 9-16, 2022.
[61]
L. Yang, "Path planning and trajectory tracking control of cushion robot", M.S. thesis, Shenyang University, China., 2021.
[62]
Q.Y. Tao, H.Y. Sang, H.W. Guo, and P. Wang, "Improved particle swarm optimization algorithm for agv path planning", IEEE Access, vol. 9, no. 09, pp. 33522-33531, 2021. https://ieeexplore.ieee.org/document/9361079
[63]
E.N. Mobarez, A. Sarhan, and M.M. Ashry, "Obstacle avoidance for multi-uav path planning based on particle swarm optimization", Conference Series: Materials Science and Engineering, The 19th International Conference on Aerospace Sciences & Aviation Technology, vol. 1172, Cairo, Egypt, no. 1, 2021.
[http://dx.doi.org/10.1088/1757-899X/1172/1/012039]
[http://dx.doi.org/10.1088/1757-899X/1172/1/012039]
[64]
X.L. Wang, C. Huang, and F.H. Chen, "An improved particle swarm optimization algorithm for unmanned aerial vehicle route planning", Journal of Physics: Conference Series 2022 International Conference on Electronics and Integrated Circuit Technology Shenzhen, China..
[http://dx.doi.org/10.1088/1742-6596/2245/1/012013]
[http://dx.doi.org/10.1088/1742-6596/2245/1/012013]
[65]
R. Mesquita, and P.D. Gaspar, "A novel path planning optimization algorithm based on particle swarm optimization for UAVS for bird monitoring and repelling", Processes, vol. 10, no. 1, p. 62, 2021.
[http://dx.doi.org/10.3390/pr10010062]
[http://dx.doi.org/10.3390/pr10010062]
[66]
J. Chen, H. Zhao, and L. Wang, Three-dimensional path planning of uav based on adaptive particle swarm optimization algorithm Journal of Physics: Conference Series, 2021 7th International Symposium on Sensors, Mechatronics and Automation System , vol. 1846. no. 1, Xiamen, China, 2021.
[http://dx.doi.org/10.1088/1742-6596/1846/1/012007]
[http://dx.doi.org/10.1088/1742-6596/1846/1/012007]
[67]
J.H. Feng, T.Y. Zhang, S. Feng, and B.J. Zheng, "An improved particle swarm algorithm for robot path planning", In: Machine Design and Manufacture., 2021, no. 9, pp. 291-294+298.
[68]
X.H. Liu, D.G. Zhang, J. Zhang, T. Zhang, and H.L.A. Zhu, "Path planning method for intelligent driving vehicles based on particle swarm optimization improvement strategy", J. Beijing Jiaotong Univ., vol. 44, no. 05, pp. 87-97, 2020.
[69]
Z. Ming, "Research on local path planning for intelligent vehicle driving based on the improved artificial potential field", M.S. thesis, Zhengzhou University, China., 2021.
[70]
W.H. Ma, "Research on vehicle obstacle avoidance path planning based on artificial potential field algorithm", M.S. thesis, Chongqing Jiaotong University, China., 2021.
[71]
B.Y. Liu, X.B. Ye, X.B. Wang, J. Jia, and T. Wang, "An unmanned ground vehicle path avoidance algorithm based on the improved artificial potential field", Chi. J. Iner. Tech., vol. 28, no. 06, pp. 769-777, 2020.
[72]
X.C. Wang, X.C. Wu, W.W. Zhang, and H.C. Wang, "Research on local path planning method for autonomous vehicles based on improved artificial potential field algorithm", In: Computer and Digital Engineering, vol. 50. 2022, no. 3, pp. 554-558+630.
[73]
J. Chen, "Research on path planning of agricultural robots based on artificial fish swarm and dynamic window method", M.S. thesis, Anhui Agricultural University, China., 2020.
[74]
C.G. Li, "Research on improving A~* algorithm and dynamic window method for mobile robot path planning", M.S. thesis, Chongqing University, China., 2022.
[75]
H.B. Wang, P.H. Yin, W. Zheng, H. Wang, and J.X. Zuo, "Path planning for mobile robots based on improved A~* algorithm and dynamic window method", Robotics, vol. 42, no. 03, pp. 346-353, 2022.
[76]
J.S. Ma, L.J. Liu, J.C. Cai, and M.Z. Chen, "An unmanned ship target tracking motion planning method based on an improved dynamic window method", J.Mar. Tech., vol. 41, no. 03, pp. 1-9, 2022.
[77]
C.W. Yin, "Hybrid path planning for mobile robots based on the firefly algorithm and dynamic window method", M.S. thesis, Chongqing University, China., 2018.
[78]
M.L. Yang, and N. Li, "Improved A~* algorithm for mobile robot path planning", Mach. Sci. Technol., vol. 41, no. 05, pp. 795-800, 2022.
Related Books
Mechanical Engineering Technologies and Applications
Mechanical Engineering Technologies and Applications
Facets of a Smart City: Computational and Experimental Techniques for Sustainable Urban Development
Soft Robotics
Voltammetry for Sensing Applications
Advances in Manufacturing Technologies and Production Engineering
Advances in Additive Manufacturing Processes
Lean Management Solutions for Contemporary Manufacturing Operations
Mechanical Engineering Technologies and Applications
Global Emerging Innovation Summit (GEIS-2021)
