Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2024, Vol. 58 Issue (12): 2520-2530    DOI: 10.3785/j.issn.1008-973X.2024.12.011
计算机技术     
B样条技术与遗传算法融合的全局路径规划
陈丽芳1(),杨火根1,*(),陈智超2,杨杰2
1. 江西理工大学 理学院，江西 赣州 341000
2. 江西理工大学 电气工程与自动化学院，江西 赣州 341000
Global path planning with integration of B-spline technique and genetic algorithm
Lifang CHEN1(),Huogen YANG1,*(),Zhichao CHEN2,Jie YANG2
1. College of Science, Jiangxi University of Science and Technology, Ganzhou 341000, China
2. College of Electrical Engineering and Automation, Jiangxi University of Science and Technology, Ganzhou 341000, China
 全文: PDF(910 KB)   HTML
摘要：

针对机器人在复杂障碍物环境下的路径规划问题，提出B样条技术与遗传算法融合的路径规划方法. 设计基于多目标A* 算法生成路径型值点以及反求控制点的策略，产生优质初始种群以增加种群多样性，提高算法早期的收敛速度；融合路径的连续性、安全性和最短性等因素设计新型适应度函数，计算每条路径的适应度；引入自适应策略调整交叉、变异算子以增加个体的多样性，避免早熟收敛至局部最优解. 基于MATLAB对所提算法进行仿真实验. 在复杂静态环境下的实验结果表明，与GABE算法、IPSO-SP算法生成的路径比较，所提算法生成的机器人行驶路径在长度上平均减少8.22%和2.15%，在早熟率上平均减少88.31%和77.08%，且路径具有二阶连续可导（即C2连续），提升了机器人的行驶稳定性. 结合机器人操作平台，通过导航实验验证了所提算法能在实际环境中完成路径规划.
关键词： B样条技术;  移动机器人;  A*算法;  遗传算法;  路径规划    
Abstract:

A path planning method integrating B-spline technique and genetic algorithm was proposed, aiming at the path planning problem of robots in complex obstacle environments. Firstly, a strategy based on the multi-objective A* algorithm for generating path-type value points as well as inversing the control points was designed to generate a high-quality initial population, so as to increase the population diversity and improve the early convergence speed of the algorithm. Secondly, a novel fitness function was designed by integrating the continuity, safety and shortest of path, and the fitness value of each path was calculated. Then, the adaptive strategy was introduced to adjust the crossover and mutation operators to increase the diversity of individuals and avoid premature convergence to local optimal solutions. Finally, simulation experiments of the proposed algorithm were conducted based on MATLAB. The experimental results in complex static environment showed that the length of the robot traveling path generated by the proposed algorithm was reduced by an average of 8.22% and 2.15%, and the prematurity was reduced by an average of 88.31% and 77.08%, compared with the paths generated by GABE and IPSO-SP methods. And the paths had a second-order continuum derivability (i.e., C2 continuum), which improved the robot’s traveling stability. Simultaneously, the proposed algorithm was verified to be able to complete the path planning efficiently in real environments through navigation experiments by combining with the robot operation platform.
Key words: B-spline technique    mobile robot    A* algorithm    genetic algorithm    path planning
收稿日期: 2023-07-29 出版日期: 2024-11-25
CLC:  TP 242.6  
基金资助: 国家自然科学基金资助项目（12161043）；江西省研究生创新专项资金项目(YC2022-S648).
通讯作者: 杨火根     E-mail: 378201848@qq.com;yanghuogen@126.com
作者简介: 陈丽芳（1996—），女，硕士生，从事计算机辅助设计. orcid.org/0000-0002-8636-0335. E-mail：378201848@qq.com
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
陈丽芳
杨火根
陈智超
杨杰

引用本文:

陈丽芳,杨火根,陈智超,杨杰. B样条技术与遗传算法融合的全局路径规划[J]. 浙江大学学报(工学版), 2024, 58(12): 2520-2530.

Lifang CHEN,Huogen YANG,Zhichao CHEN,Jie YANG. Global path planning with integration of B-spline technique and genetic algorithm. Journal of ZheJiang University (Engineering Science), 2024, 58(12): 2520-2530.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2024.12.011    或    https://www.zjujournals.com/eng/CN/Y2024/V58/I12/2520

图 1  传统遗传算法流程图
图 2  二维连续地图
图 3  基于多目标A*算法生成路径型值点的示意图
图 4  k次B样条曲线分段连接点与控制多边形的对应关系
图 5  基于单点交叉方式的交叉过程示意图
图 6  基于单点变异方式的变异操作示意图
图 7  本研究算法路径规划流程图
图 8  仿真实验连续地图
方法参数数值
GABE算法/本研究方法种群大小100
交叉概率0.9
变异概率0.1
迭代次数200
IPSO-SP算法种群大小150
惯性权重0.8
个体学习因子c1
全局学习因子c2		0.5
迭代次数200
表 1  各算法参数设置
地图NUM随机法随机法+筛选步骤本研究方法
Favgt/sFavgt/sFavgt/s
10×10800.0960450.10211250.356070
20×20800.04592190.06352970.0942225
30×30800.01084280.01135100.0281389
40×40800.00326200.00417130.0070519
表 2  不同初始种群生成方法的性能对比
图 9  不同算法在场景1的路径规划结果对比
方法Lavg/mNavgPavg连续性
GABE算法21.39460.07G1
IPSO-SP算法19.98290.03C2
A*-DWA算法20.73——C0
本研究方法19.59310.01C2
表 3  各算法在18×18地图上的实验结果对比
图 10  场景1下不同算法的路径长度随迭代次数变化曲线对比
图 11  不同算法在场景2的路径规划结果对比
图 12  场景2下不同算法的路径长度随迭代次数变化曲线对比
方法Lavg/mNavgPavg连续性
GABE算法36.7696610.22G1
IPSO-SP算法33.9548390.16C2
A*-DWA算法34.4733——C0
本研究方法33.8208440.02C2
表 4  各算法在35×35地图上的实验结果对比
图 13  实验室前期搭建的麦克纳姆轮小车
图 14  4种算法在ROS机器人上的路径可视化结果
1 江明, 王飞, 葛愿, 等 基于改进蚁群算法的移动机器人路径规划[J]. 仪器仪表学报, 2019, 40 (2): 113- 121
JIANG Ming, WANG Fei, GE Yuan, et al Mobile robot path planning based on improved ant colony algorithm[J]. Chinese Journal of Scientific Instrument, 2019, 40 (2): 113- 121
2 ZHANG X, GUO Y, YANG J, et al Many-objective evolutionary algorithm based agricultural mobile robot route planning[J]. Computers and Electronics in Agriculture, 2022, 200: 107274- 107286
doi: 10.1016/j.compag.2022.107274
3 YAN R T, WANG J J, ZHU S T, et al Novel planning methodology for energy stations and networks in regional integrated energy systems[J]. Energy Conversion and Management, 2020, 205: 112441- 112453
doi: 10.1016/j.enconman.2019.112441
4 CHEN L, YANG H, CHEN Z, et al Research on intelligent disinfection-vehicle system design and its global path planning[J]. Electronics, 2023, 12 (7): 1514
doi: 10.3390/electronics12071514
5 徐兴, 俞旭阳, 赵芸, 等 基于改进遗传算法的移动机器人全局路径规划[J]. 计算机集成制造系统, 2022, 28 (6): 1659- 1672
XU Xing, YU Xuyang, ZHAO Yun, et al Global path planning for mobile robots based on improved genetic algorithm[J]. Computer Integrated Manufacturing Systems, 2022, 28 (6): 1659- 1672
6 TSAI C C, HUANG H C, CHAN C K Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation[J]. IEEE Transactions on Industrial Electronics, 2011, 58 (10): 4813- 4821
doi: 10.1109/TIE.2011.2109332
7 ZHOU F, SONG B, TIAN G Bezier curve based smooth path planning for mobile robot[J]. Journal of Information and Computational Science, 2011, 8 (12): 2441- 2450
8 李艳生, 万勇, 张毅, 等 基于人工蜂群-自适应遗传算法的仓储机器人路径规划[J]. 仪器仪表学报, 2022, 43 (4): 282- 290
LI Yansheng, WANG Yong, ZHANG Yi, et al Path planning for warehouse robot based on the artificial bee colony-adaptive genetic algorithm[J]. Chinese Journal of Scientific Instrument, 2022, 43 (4): 282- 290
9 ZULKIFLY M I E, WAHAB A F A new fuzzy Bezier curve modeling by using fuzzy control point relation[J]. Applied Mathematical Sciences, 2017, 11 (1): 39- 57
10 GUO J, LIANG C, WANG K, et al Three-dimensional autonomous obstacle avoidance algorithm for UAV based on circular arc trajectory[J]. International Journal of Aerospace Engineering, 2021, 2021: 1- 13
11 RAVANKAR A, RAVANKAR A A, KOBAYASHI Y, et al Path smoothing techniques in robot navigation: state-of-the-art, current and future challenges[J]. Sensors, 2018, 18 (9): 3170
doi: 10.3390/s18093170
12 张跃明, 薛奇, 纪姝婷 满足曲率约束的B样条曲线连续路径平滑方法[J]. 华中科技大学学报: 自然科学版, 2022, 50 (5): 59- 65
ZHANG Yueming, XUE Qi, JI Shuting Continuous path smoothing method of B-spline curve satisfying curvature constraint[J]. Huazhong University of Science and Technology: Natural Science Edition, 2022, 50 (5): 59- 65
13 ESHTEHARDIAN S A, KHODAYGAN S A continuous RRT*-based path planning method for non-holonomic mobile robots using B-spline curves[J]. Journal of Ambient Intelligence and Humanized Computing, 2023, 14 (7): 8693- 8702
doi: 10.1007/s12652-021-03625-8
14 张伟民, 付仕雄 基于改进RRT~*算法的移动机器人路径规划[J]. 华中科技大学学报: 自然科学版, 2021, 49 (1): 31- 36
ZHANG Weimin, FU Shixiong Mobile robot path planning based on improved RRT* algorithm[J]. Huazhong University of Science and Technology: Natural Science Edition, 2021, 49 (1): 31- 36
15 刘景森, 吉宏远, 李煜 基于改进蝙蝠算法和三次样条插值的机器人路径规划[J]. 自动化学报, 2021, 47 (7): 1710- 1719
LIU Jingsen, JI Hongyuan, LI Yu Robot path planning based on improved bat algorithm and cubic spline interpolation[J]. Acta Automatica Sinica, 2021, 47 (7): 1710- 1719
16 LI Y, HUANG T, CHETWYND D G An approach for smooth trajectory planning of high-speed pick-and-place parallel robots using quintic B-splines[J]. Mechanism and Machine Theory, 2018, 126: 479- 490
doi: 10.1016/j.mechmachtheory.2018.04.026
17 SONG B, WANG Z, SHENG L A new genetic algorithm approach to smooth path planning for mobile robots[J]. Assembly Automation, 2016, 36 (2): 138- 145
doi: 10.1108/AA-11-2015-094
18 PAN J, ZHANG L, MANOCHA D Collision-free and smooth trajectory computation in cluttered environments[J]. The International Journal of Robotics Research, 2012, 31 (10): 1155- 1175
doi: 10.1177/0278364912453186
19 LI W, TAN M, WANG L, et al. A cubic spline method combing improved particle swarm optimization for robot path planning in dynamic uncertain environment [J]. International Journal of Advanced Robotic Systems , 2020, 17(1): 1729881419891661.
20 施法中. 计算机辅助几何设计与非均匀有理B样条[M]. 北京: 高等教育出版社, 2013: 217–229.
21 HOLLAND J H Genetic algorithms[J]. Scientific American, 1992, 267 (1): 66- 73
doi: 10.1038/scientificamerican0792-66
22 唐俊林, 张栋, 王孟阳, 等 改进链式多种群遗传算法的防空火力任务分配[J]. 哈尔滨工业大学学报, 2022, 54 (6): 19- 27
TANG Junlin, ZHANG Dong, WANG Mengyang, et al Air defense firepower task assignment based on improved chainlike multi-population genetic algorithm[J]. Journal of Harbin Institute of Technology, 2022, 54 (6): 19- 27
23 张铮, 柯子鹏, 周嘉政, 等 基于改进多目标自适应遗传算法的机器人路径规划[J]. 西安理工大学学报, 2023, 39 (1): 69- 78
ZHANG Zheng, KE Zipeng, ZHOU Jiazheng, et al Robot path planning based on improved multi-objective adaptive genetic algorithm[J]. Journal of Xi’an University of Technology, 2023, 39 (1): 69- 78
24 ZHANG L, ZHANG K, YAN Y Local corner smoothing transition algorithm based on double cubic nurbs for five-axis linear tool path[J]. Strojniski Vestnik-Journal of Mechanical Engineering, 2016, 62 (11): 647- 656
doi: 10.5545/sv-jme.2016.3525
25 WU Q H, CAO Y J, WEN J Y Optimal reactive power dispatch using an adaptive genetic algorithm[J]. International Journal of Electrical Power and Energy Systems, 1998, 20 (8): 563- 569
doi: 10.1016/S0142-0615(98)00016-7
26 陈娇, 徐菱, 陈佳, 等 改进A*和动态窗口法的移动机器人路径规划[J]. 计算机集成制造系统, 2022, 28 (6): 1650- 1658
CHEN Jiao, XU Ling, CHEN Jia, et al Path planning based on improved A* and dynamic window approach for mobile robot[J]. Computer Integrated Manufacturing Systems, 2022, 28 (6): 1650- 1658
[1] 朱云辰,程明骏,郑昕文,岑沛立,郗祥硕,黄杉,华晨,黄海. 基于优化第三代非支配排序遗传算法的城市应急设施模糊选址[J]. 浙江大学学报(工学版), 2024, 58(9): 1832-1843.
[2] 薛雅丽,李寒雁,欧阳权,崔闪,洪君. 战场环境下遗传黏菌算法的多机协同任务分配[J]. 浙江大学学报(工学版), 2024, 58(8): 1748-1756.
[3] 樊志伟,贾凯,张雷,邹风山,杜振军,刘明敏. 基于同步动态优化的移动机器人最优速度规划[J]. 浙江大学学报(工学版), 2024, 58(8): 1556-1564.
[4] 赵杰,刘锋,夏灵,范一峰. 基于遗传算法-序列二次规划的磁共振被动匀场优化方法[J]. 浙江大学学报(工学版), 2024, 58(6): 1305-1314.
[5] 李立峰,侯坤,邹德强,彭浩,李凌霄. 中等跨径钢板组合梁截面布置优化[J]. 浙江大学学报(工学版), 2024, 58(3): 510-517.
[6] 刘宇庭,郭世杰,唐术锋,张学炜,李田田. 改进A*与ROA-DWA融合的机器人路径规划[J]. 浙江大学学报(工学版), 2024, 58(2): 360-369.
[7] 吴越安,杜昌平,杨睿,俞佳浩,方天睿,郑耀. 基于改进遗传算法的倾转旋翼无人机区域覆盖路径规划[J]. 浙江大学学报(工学版), 2024, 58(10): 2031-2039.
[8] 郑好,曹弋,王珊. 考虑站点换乘的地铁多车站接运公交线路优化[J]. 浙江大学学报(工学版), 2024, 58(10): 2162-2170.
[9] 刘鹏,路庆昌,秦汉,崔欣. 道路网络多阶段抗灾能力优化模型构建与应用[J]. 浙江大学学报(工学版), 2024, 58(1): 96-108.
[10] 李煌,葛红娟,马莹,王永帅. 基于超平面NSGA-II的双输入双降压逆变器系统参数优化设计[J]. 浙江大学学报(工学版), 2023, 57(3): 606-615.
[11] 许丽丽,詹燕,鲁建厦,郎一丁. 四向穿梭车仓储系统复合作业调度优化[J]. 浙江大学学报(工学版), 2023, 57(11): 2188-2199.
[12] 查浩,费少华,傅云,吕震,朱伟东. 基于EtherCAT总线的六维力传感器在线解耦技术[J]. 浙江大学学报(工学版), 2023, 57(10): 2042-2050.
[13] 靳佳澳,沈洪垚,孙扬帆,林嘉浩,陈静霓. 面向电弧增材的单线激光扫描路径规划[J]. 浙江大学学报(工学版), 2023, 57(1): 21-31.
[14] 徐维祥,康楠,徐婷. 基于出行计划数据的最优路径规划方法[J]. 浙江大学学报(工学版), 2022, 56(8): 1542-1552.
[15] 赵永胜,李瑞祥,牛娜娜,赵志勇. 数字孪生驱动的机身形状控制方法[J]. 浙江大学学报(工学版), 2022, 56(7): 1457-1463.