摘 要：路径规划算法广泛应用于机器人、无人驾驶设备、自动导航等领域，是推动自动化和智能化发展的技术支撑。文章对几何搜索算法、智能搜索算法、人工智能算法、混合算法和局部规划算法等路径规划算法进行了简要介绍，内容包括若干典型算法以及由不同算法相互模仿混合而成的混合算法的特点、优缺点和重要改进。对路径规划算法的发展趋势进行总结，对路径规划算法的发展前景进行展望，以期为相关的研究提供参考。
关键词：路径规划；算法综述；自动导航
DOI:10.19850/j.cnki.2096-4706.2023.04.020
中图分类号：TP242 文献标识码：A 文章编号：2096-4706（2023）04-0075-06
Research Review of the Path Planning Algorithms
LIN Zijian, LIU Kai, LIN Qunxu
(School of Rail Transportation, Wuyi University, Jiangmen 529020, China)
Abstract: The path planning algorithms are widely used in robots, driverless equipments, automatic navigation and other fields, and they are the technical support for promoting the development of automation and intelligence. This paper briefly introduces path planning algorithms such as geometric search algorithm, intelligent search algorithm, artificial intelligence algorithm, hybrid algorithm and local planning algorithm, including the characteristics, advantages and disadvantages and important improvements of several typical algorithms as well as hybrid algorithms formed by mutual imitation and mixing of different algorithms. Summarize the development trend of path planning algorithms, and prospect the development prospect of path planning algorithms, in order to provide reference for relevant research.
Keywords: path planning; algorithm review; automatic navigation
参考文献：
[1] ZHANG J，WU J，SHEN X，et al. Autonomous land vehicle path planning algorithm based on improved heuristic function of A-Star [J/OL].International Journal of Advanced Robotic Systems，2021，18（5）： [2022-08-20].https://doi.org/10.1177/17298814211042730.
[2] TANG G，TANG C，CLARAMUNT C，et al. Geometric A-Star Algorithm：An Improved A-Star Algorithm for AGV Path Planning in a Port Environment [J].IEEE Access，2021，9：59196-59210.
[3] HONG Z H，SUN P F，TONG X H，et al. Improved A-Star Algorithm for Long-Distance Off-Road Path Planning Using Terrain Data Map [J/OL].ISPRS International Journal of Geo-Information， 2021，10（11）：[2022-08-20].https://doi.org/10.3390/ijgi10110785.
[4] SUN Y H，FANG M，SU Y X. AGV Path Planning based on Improved Dijkstra Algorithm [C]//Journal of Physics：Conference Series.Bijing：IOP，2021，1746（1）：1-7.
[5] ZHAO H L，NIE Z，ZHOU F B，et al. A Compound Path Planning Algorithm for Mobile Robots [C]//2021 IEEE International Conference on Power Electronics，Computer Applications（ICPECA）. Shenyang：IEEE，2021：1-5.
[6] HUANG S K，WANG W J，SUN C H. A Path Planning Strategy for Multi-Robot Moving with Path-Priority Order Based on a Generalized Voronoi Diagram [J/OL].Applied Sciences，2021，11（20）： [2022-08-20].https://doi.org/10.3390/app11209650.
[7] AL-DAHHAN M R H，SCHMIDT K W. Voronoi Boundary Visibility for Efficient Path Planning [J].IEEE Access，2020，8： 134764-134781.
[8] CHI W Z，DING Z Y，WANG J K，et al. A Generalized Voronoi Diagram-Based Efficient Heuristic Path Planning Method for RRTs in Mobile Robots [J].IEEE Transactions on Industrial Electronics，2022，69（5）：4926-4937.
[9] DORIGO M，GAMBARDELLA L M. Ant colony system：a cooperative learning approach to the traveling salesman problem [J].IEEE Transactions on evolutionary computation，1997，1（1）：53-66.
[10] KASHEF S，ELSHAER R. A Review of Implementing Ant System Algorithms on Scheduling Problems [J].The Egyptian Journal for Engineering Sciences and Technology，2021，36（2）：43-52.
[11] ABOLHOSEINI S，ALESHEIKH A A. Dynamic routing with ant system and memory-based decision-making process [J].Environment Systems and Decisions，2021，41（2）：198-211.
[12] POHAN M A R，TRILAKSONO B R，SANTOSA S P， et al. Path Planning Algorithm Using the Hybridization of the RapidlyExploring Random Tree and Ant Colony Systems [J].IEEE Access， 2021，9：153599-153615.
[13] ZHANG S C，PU J X，SI Y N. An adaptive improved ant colony system based on population information entropy for path planning of mobile robot [J].IEEE Access，2021，9：24933-24945.
[14] LI C Q，XIAO J，LIU Y，et al. An Adaptive Immune Ant Colony Optimization for Reducing Energy Consumption of Automatic Inspection Path Planning in Industrial Wireless Sensor Networks [J/ OL].Journal of Sensors，2021，2021：1-11[2022-08-16].https://doi. org/10.1155/2021/9960043.
[15] SONG Q，ZHAO Q L，Dynamic Path Planning for Unmanned Vehicles Based on Fuzzy Logic and Improved Ant Colony Optimization [J].IEEE Access，2020，8：62107-62115.
[16] 约翰 •H• 霍兰 . 隐秩序：适应性造就复杂性 [M]. 周晓牧，译 . 上海：上海科技教育出版社，2019.
[17] WANG H J，FU Z J，ZHOU J J，et al. Cooperative collision avoidance for unmanned surface vehicles based on improved genetic algorithm [J/OL].Ocean Engineering，2021，222：[2022-08-16].108612.https://doi.org/10.1016/j.oceaneng.2021.108612.
[18] XING X G，LIU Y，GARG A，et al. An improved genetic algorithm for determining modified water-retention model for biocharamended soil [J].CATENA，2021，200：[2022-08-16].https://doi. org/10.1016/j.catena.2021.105143.
[19] LI J L，LIU Z B，WANG X F. Public charging station location determination for electric ride-hailing vehicles based on an improved genetic algorithm [J/OL].Sustainable Cities and Society， 2021，74：[2022-08-16].https://doi.org/10.1016/j.scs.2021.103181.[20] LI R H，CHANG Y L，WANG Z C. Study of optimal
allocation of water resources in Dujiangyan irrigation district of China based on an improved genetic algorithm [J].Water Supply，2021，21（6）：2989-2999.
[21] 袁梦飞，阚秀，曹乐，等 . 自适应精英遗传算法的快递车路径规划 [J]. 导航定位学报，2021，9（6）：104-111.
[22] 王吉岱，王新栋，田群宏，等．基于改进模糊自适应遗传算法的移动机器人路径规划 [J]．机床与液压，2021，49（23）：18-23．
[23] YUAN Q N，YI J H，SUN R T，et al. Path Planning of a Mechanical Arm Based on an Improved Artificial Potential Field and a Rapid Expansion Random Tree Hybrid Algorithm [J/OL].Algorithms， 2021，14（11）：[2022-08-16].https://doi.org/10.3390/a14110321.
[24] YANG W L，WU P，ZHOU X Q，et al. Improved Artificial Potential Field and Dynamic Window Method for Amphibious Robot Fish Path Planning [J/OL].Applied Sciences，2021，11（5）：[2022-08-16].https://doi.org/10.3390/app11052114.
[25] WANG Z，LI G F，REN J. Dynamic path planning for unmanned surface vehicle in complex offshore areas based on hybrid algorithm [J].Computer Communications，2021，166：49-56.
[26] YAO Q F，ZHENG Z Y，QI L，et al. Path planning method with improved artificial potential field—A reinforcement learning perspective [J].IEEE Access，2020，8：135513-135523.
[27] HE N F，SU Y F，GUO J L，et al. Dynamic path planning of mobile robot based on artificial potential field [C]//2020 International Conference on Intelligent Computing and Human-Computer Interaction （ICHCI）.Sanya：IEEE，2020：259-264.
[28] WANG M，ZENG B，WANG Q. Research on Motion Planning Based on Flocking Control and Reinforcement Learning for Multi-Robot Systems [J/OL].Machines，2021，9（4）：[2022-08-12].https://doi.org/10.3390/machines9040077.
[29] ZHOU Y，ZHANG E D，GUO H L，et al. Lifting path planning of mobile cranes based on an improved RRT algorithm [J/OL]. Advanced Engineering Informatics，2021，50：[2022-08-12].https:// doi.org/10.1016/j.aei.2021.101376.
[30] KANG J G，LIM D W，CHOI Y S，et al. Improved RRTConnect Algorithm Based on Triangular Inequality for Robot Path Planning [J/OL].Sensors，2021，21（2）：[2022-08-12].https://doi. org/10.3390/s21020333.
[31] CHEN J G，ZHAO Y，XU X. Improved RRT-Connect Based Path Planning Algorithm for Mobile Robots [J].IEEE Access，2021，9：145988-145999.
[32] CHEN G，LUO N，LIU D，et al. Path planning for manipulators based on an improved probabilistic roadmap method [J/ OL].Robotics and Computer-Integrated Manufacturing，2021，72：[2022-08-12].https://doi.org/10.1016/j.rcim.2021.102196.
[33] XU Z F，DENG D，SHIMADA K. Autonomous UAV Exploration of Dynamic Environments Via Incremental Sampling and Probabilistic Roadmap [J].IEEE Robotics and Automation Letters， 2021，6（2）：2729-2736.
[34] RAVANKAR A A，RAVANKAR A，EMARU T，et al. HPPRM：Hybrid Potential Based Probabilistic Roadmap Algorithm for Improved Dynamic Path Planning of Mobile Robots [J].IEEE Access， 2020，8：221743-221766.
[35] LOW E S，ONG P，CHEAH K C. Solving the optimal path planning of a mobile robot using improved Q-learning [J].Robotics and Autonomous Systems，2019，115：143-161.
[36] SUN F J，WANG X C，ZHANG R. Improved Q-Learning Algorithm Based on Approximate State Matching in Agricultural Plant Protection Environment [J/OL].Entropy，2021，23（6）：[2022-08-12].https://doi.org/10.3390/e23060737.
[37] LI B，LIANG H B. Multi-Robot Path Planning Method Based on Prior Knowledge and Q-learning Algorithms [C]//Proceedings of 20202nd International Conference on Computer Modeling，Simulation and Algorithm（CMSA2020）.Beijing：IOP，2020，1624（4）:1-9.
[38] HAMDIA K M，ZHUANG X Y，RABCZUK T. An efficient optimization approach for designing machine learning models based on genetic algorithm [J].Neural Computing and Applications，2021，33（6）：1923-1933.
[39] ABDI A，ADHIKARI D，PARK J H. A Novel Hybrid Path Planning Method Based on Q-Learning and Neural Network for Robot Arm [J/OL].Applied Sciences，2021，11（15）：[2022-08-12].https://doi.org/10.3390/app11156770.
[40] XIANG L D，LI X M，LIU H，et al. Parameter Fuzzy Self-Adaptive Dynamic Window Approach for Local Path Planning of Wheeled Robot [J].IEEE Open Journal of Intelligent Transportation Systems，2021，3：1-6.
[41] CHANG L，SHAN L，JIANG C，et al. Reinforcement based mobile robot path planning with improved dynamic window approach in unknown environment [J].Autonomous Robots，2021，45（1）：51-76.
[42] BALLESTEROS J，URDIALES C，VELASCO A B M， et al. A Biomimetical Dynamic Window Approach to Navigation for Collaborative Control [J].IEEE Transactions on Human-Machine Systems，2017，47（6）：1123-1133.
[43] WANG X Y，WANG A，WANG D Z，et al. Repetitive Control Scheme of Robotic Manipulators Based on Improved B-Spline Function [J/OL].Complexity，2021，2021：[2022-08-12].https://doi. org/10.1155/2021/6651105.
[44] 古劲，吴泰羽，李传军，等 . 基于改进三次 B 样条的灌木修剪运动轨迹光顺算法研究 [J]. 农业机械学报，2021，52（S1）：89-97.
[45] LUAN P G，THINH N T. C 2 Piecewise Cubic Bezier Curve Based Smoothing Path for Mobile Robot [J/OL].International Journal of Mechanical Engineering and Robotics Research， 2021，10（9）：1-7[2022-08-12].http://www.ijmerr.com/uploadfi le/2021/0727/20210727113132943.pdf.
[46] ZENG X Y，LU H C，LYU H F，et al. Robot Path Planning Based on Improved RRT Algorithm [C]//LSMS 2021，ICSEE 2021： Intelligent Equipment，Robots，and Vehicles.Hangzhou：Springer， 2021：361-369.
[47] CHEN J B，ZHOU Y L，GONG J，et al. An improved probabilistic roadmap algorithm with potential field function for path planning of quadrotor [C]//2019 Chinese Control Conference（CCC）. Guangzhou：IEEE，2019：3248-3253.
[48] LI Y B，DONG D G，GUO X N. Mobile Robot Path Planning based on Improved Genetic Algorithm With A-star Heuristic Method [C]//2020 IEEE 9th Joint International Information Technology and Artificial Intelligence Conference（ITAIC）.Chongqing：IEEE， 2020：1306-1311.
[49] CHEN Y L，BAI GQ，ZHAN Y，et al. Path Planning and Obstacle Avoiding of the USV Based on Improved ACO-APF Hybrid Algorithm With Adaptive Early-Warning [J].IEEE Access，2021，9：40728- 40742.
作者简介：林梓健（1997—），男，汉族，广东江门人，硕士研究生在读，主要研究方向：智能装备；通信作者：林群煦（1983—），男，汉族，广东江门人，副教授，博士，主要研究方向：智能化物流和移动机器人；刘凯（1999—），男，汉族，广东广州人，硕士研究生在读，主要研究方向：机器视觉、机器人导航。