麻雀搜索算法-粒子群算法与快速扩展随机树算法协同优化的智能车辆路径规划

doi:10.3969/j.issn.1004-132X.2024.06.005

摘要/Abstract

摘要： 针对智能汽车在面对多样化工作场景时其路径规划算法存在响应时间长、规划效率低的问题，提出了多元协同优化策略。首先，融合麻雀搜索算法(SSA)的警惕机制与粒子群算法(PSO)的种群寻优特性，对PSO算法中的惯性权重因子和学习因子进行优化；其次，提出“三角布线”搜索规则，对快速扩展随机树算法（RRT）进行双向优化（RRT-Connect）；然后，基于MATLAB软件建立了复杂环境道路仿真模型，对上述优化方案进行了仿真验证。结果表明，相较于单一的优化方案，协同优化算法在路径长度与规划时间上均具有显著的优势。对两种协同优化方案的应用场景进行了实车试验，结果显示：在局部路径规划中，SSA-PSO算法响应时间更短，规划效率更高，而在全局路径规划中，“三角布线”RRT-Connect算法更具优势。

关键词: 路径规划, 麻雀搜索算法, 粒子群算法, 三角布线, 快速扩展随机树算法

Abstract: Regarding the issues of long response time and low planning efficiency in the path planning algorithms for smart vehicles facing diverse working scenarios, a multi-element collaborative optimization strategy was proposed. Firstly, the vigilance mechanism of SSA was integrated with the population optimization characteristics of PSO, optimizing the inertia weight factor and learning factor in the PSO algorithm. Secondly, a “triangular wiring” search rule was introduced to perform bidirectional optimization(RRT-Connect) on the RRT algorithm. Subsequently, a complex environmental road simulation model was established using MATLAB software, and simulation tests were conducted on the proposed optimization solutions. The results demonstrate that, compared to single optimization approaches, the collaborative optimization algorithm exhibits significant advantages in terms of path length and planning time. Finally, real-vehicle tests are conducted on the application scenarios of the two collaborative optimization solutions, showing that in local path planning, the SSA-PSO algorithm has a shorter response time and higher planning efficiency, while in global path planning, the “triangular wiring” RRT-Connect algorithm exhibits greater advantages.

Key words: path planning, sparrow search algorithm（SSA）, particle swarm optimization（PSO） algorithm, triangular wiring, rapidly-exploring random tree（RRT） algorithm

中图分类号:

U461

张志文1, 2, 刘伯威3, 张继园1, 唐杰1, 张天赐1, 2. 麻雀搜索算法-粒子群算法与快速扩展随机树算法协同优化的智能车辆路径规划[J]. 中国机械工程, 2024, 35(06): 993-999，1009.

ZHANG Zhiwen1, 2, LIU Bowei3, ZHANG Jiyuan1, TANG Jie1, ZHANG Tianci1, 2. Cooperative Optimization of Intelligent Vehicle Path Planning Based on PSO-SSA and RRT[J]. China Mechanical Engineering, 2024, 35(06): 993-999，1009.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.cmemo.org.cn/CN/10.3969/j.issn.1004-132X.2024.06.005

http://www.cmemo.org.cn/CN/Y2024/V35/I06/993

参考文献

［1］SCHWAB K. The Fourth Industrial Revolution［M］. New York:Crown Business, 2017.
［2］张鹏. 基于改进A*算法的全局动态路径规划研究［D］.太原：中北大学,2021.
ZHANG Peng. Research on Global Dynamic Path Planning Based on Improved A* Algorithm［D］. Taiyuan：North University of China, 2021.
［3］GILBERT E G, JOHNSON D W. Distance Functions and Their Application to Robot Path Planning in the Presence of Obstacles［J］. IEEE Journal on Robotics and Automation ，1985, 1(1):21-30.
［4］MADANI T, DAACHI B, BENALLEGUE A. Adaptive Variable Structure Controller of Redundant Robots with Mobile/Fixed Obstacles Avoidance［J］. Robotics and Autonomous Systems， 2013,61(6):555-564.
［5］LI G, TONG S, CONG F, et al. Improved Artificial Potential Field-based Simultaneous Forward Search Method for Robot Path Planning in Complex Environment［C］∥2015 IEEE/SICE International Symposium on System Integration. Nagoya ：IEEE，2015:760-765.
［6］夏军勇, 刘科进, 钟飞, 等. 运用改进的教学模拟退火算法辨识关节臂式三坐标测量机的结构参数［J］. 中国机械工程, 2023, 34(3):314-323.
XIA Junyong, LIU Kejin, ZHONG Fei,et al. Structural Parameter Identification for Articulated Arm Coordinate Measuring Machines Using Modified Teaching-learning-based Optimization Optimized by Simulated Annealing Algorithm［J］. China Mechanical Engineering, 2023, 34(3):314-323.
［7］刘加奇,王泰华,董征. 基于改进蚁群算法的移动机器人路径规划［J］.传感器与微系统，2022,41(5)：140-143.
LIU Jiaqi, WANG Taihua, DONG Zheng. Path Planning of Mobile Robot Based on Improved Ant Colony Algorithm［J］. Sensors and Microsystems，2022,41(5) ：140-143.
［8］师颖慧,张冰,赵强. 改进型RRT*算法的水下机器人三维全局路径规划［J］.软件导刊, 2022,21(2):48-52.
SHI Yinghui,ZHANG Bing, ZHAO Qiang. 3D Global Path Planning of Underwater Vehicle Based on Improved RRT* Algorithm［J］. Journal of Software Guide, 202,21(2):48-52.
［9］CHENG K P， RAJESH E M， NGUYEN H K N，et al. Multi-objective Genetic Algorithm Based Autonomous Path Planning for Hinged Tetro Reconfigurable Tiling Robot［J］. IEEE Access，2020,8:121267-121284.
［10］HAO K, ZHAO J L, YU K C, et al. Path Planning of Mobile Robots Based on a Multi-population Migration Genetic Algorithm［J］. Sensors， 2020,20(20):5873-5873.
［11］LAMINI C, BENHLIMA S, ELBEKRI A. Genetic Algorithm Based Approach for Autonomous Mobile Robot Path Planning［J］. Procedia Computer Science，2018,127:180-189.
［12］吕刚,吕金壮,邓军,等. 部分环境信息未知下的机器人动态路径规划算法［J］.自动化与仪器仪表, 2022(3):186-190.
LYU Gang, LYU Jinzhuang, DENG Jun, et al. Robot Dynamic Path Planning Algorithm with Unknown Environmental Information［J］. Automation & Instrumentation, 2022(3):186-190.
［13］彭晓燕,谢浩,黄晶. 无人驾驶汽车局部路径规划算法研究［J］.汽车工程, 2020,42(1):1-10.
PENG Xiaoyan, XIE Hao, HUANG Jing. Research on Local Path Planning Algorithm for Driverless Vehicles［J］. Automotive Engineering, 2019,42(1):1-10.
［14］徐钊,胡劲文,马云红,等. 无人机碰撞规避路径规划算法研究［J］.西北工业大学学报, 2019,37(1):100-106.
XU Zhao, HU Jinwen, MA Yunhong, et al. Research on Collision Avoidance Path Planning Algorithm for UAV［J］. Journal of Northwestern Polytechnical University, 2019,37(1):100-106.
［15］AGARWAL D, BHARTI P S. Implementing Modified Swarm Intelligence Algorithm Based on Slime Moulds for Path Planning and Obstacle Avoidance Problem in Mobile Robots［J］. Applied Soft Computing Journal, 2021,107：233613844.
［16］ZAFAR M N, MOHANTA J C. Methodology for Path Planning and Optimization of Mobile Robots:a Review［J］. Procedia Computer Science，2018,133:141-152.
［17］刘伯威. 基于改进PSO与RRT的智能车辆路径规划研究［D］.太原：中北大学,2023.
LIU Bowei. Research on Intelligent Vehicle Path Planning Based on Improved PSO and RRT［D］. Taiyuan：North University of China,2023.
［18］杜婉茹,王潇茵,田涛,等. 面向未知环境及动态障碍的人工势场路径规划算法［J］.计算机科学, 2021,48(2):250-256.
DU Wanru, WANG Xiaoyin, TIAN Tao, et al. Artificial Potential Field Path Planning Algorithm for Unknown Environment and Dynamic Obstacles［J］. Computer Science, 2021,48(2):250-256.
［19］李兆强,张时雨. 基于快速RRT算法的三维路径规划算法研究［J］.系统仿真学报, 2022,34(3):503-511.
LI Zhaoqiang, ZHANG Shiyu. Research on 3D Path Planning Algorithm Based on Fast RRT Algorithm［J］. Journal of System Simulation, 2022,34(3):503-511.
［20］WANG Z F, WANG Q, BILL M, et al. Optimal Submarine Cable Path Planning and Trunk-and-Branch Tree Network Topology Design［J］. IEEE/ACM Transactions on Networking， 2020,28(4):1562-1572.
［21］JEONG I B, LEES J, KIM J H. Quick-RRT*:Triangular Inequality Based Implementation of RRT* with Improved Initial Solution and Convergence Rate［J］. Expert Systems with Applications， 2019,123（1）:82-90.

[1]	王秋莲1, 欧桂雄1, 徐雪娇1, 刘锦荣1, 马国红2, 邓红标2. 基于VDM-SSA-LSTM考虑刀具磨损的数控铣床切削功率预测模型研究[J]. 中国机械工程, 2024, 35(06): 1052-1063.
[2]	荣誉, 陈刚, 豆天赐, . 一种多指标综合最优的抗冲击轨迹规划方法[J]. 中国机械工程, 2024, 35(02): 305-316.
[3]	陈俊翔, 孔祥东, 许克龙, 艾超, . 高压螺纹插装式溢流阀综合性能优化[J]. 中国机械工程, 2023, 34(24): 2909-2919,2926.
[4]	蒲志新, 郭建伟, 潘玉奇, 白杨溪. 2PPaPaR并联机构性能分析及优化设计[J]. 中国机械工程, 2023, 34(19): 2304-2312.
[5]	王伏林, 肖强, 来书宁, 唐能艺. 基于不等分剪切模型的ZM5镁合金本构参数的逆向辨识[J]. 中国机械工程, 2023, 34(19): 2362-2369.
[6]	段林超, 张旭刚, 张华, 宋华伟, 敖秀奕. 基于二阶近似扩展卡尔曼滤波的锂离子电池SOC估计[J]. 中国机械工程, 2023, 34(15): 1797-1804.
[7]	张馨予, 刘勤明, 叶春明, 谢世锐. 外包合同视角下的多设备分阶段成组维护策略[J]. 中国机械工程, 2023, 34(14): 1683-1692.
[8]	唐炜, 孙宇, 顾金凤, 陈远. 连续切换轮系下变尺寸物料的传输模型与路径规划[J]. 中国机械工程, 2023, 34(11): 1372-1385.
[9]	田宗睿, 智鹏鹏, 云国丽, 郭新凯, 官毅. 基于自适应增量Kriging模型的多目标稳健优化设计方法[J]. 中国机械工程, 2023, 34(08): 931-940.
[10]	武星, 杨俊杰, 汤凯, 翟晶晶, 楼佩煌. 面向复合地图的移动机器人分层路径规划[J]. 中国机械工程, 2023, 34(05): 563-575.
[11]	陈帅, 郭飞燕, 孟月梅, 王明阳, 侯志霞. 融合实测数据的航空结构件修配量迭代寻优及评价方法[J]. 中国机械工程, 2022, 33(17): 2061-2070，2078.
[12]	张家旭, 周时莹, 李长龙, 郭崇, 赵健. 线控四轮转向汽车自主代客泊车路径规划[J]. 中国机械工程, 2022, 33(08): 993-1000.
[13]	邹裕吉, 宋豫川, 王馨坤, 王毅. 自动导向小车与加工设备多目标集成调度的聚类遗传算法[J]. 中国机械工程, 2022, 33(01): 97-108.
[14]	张家骅, 李爱平, 刘雪梅. 行驶时间区间不确定的装配线物料配送路径规划[J]. 中国机械工程, 2021, 32(18): 2239-2246.
[15]	路浩, 陈洋, 吴怀宇, 程磊, . 受路网和测量约束的变电站巡检机器人路径规划[J]. 中国机械工程, 2021, 32(16): 1972-1982.