Global path planning with integration of B-spline technique and genetic algorithm

doi:10.3785/j.issn.1008-973X.2024.12.011

Journal of ZheJiang University (Engineering Science)

2024, Vol. 58

Issue (12): 2520-2530 DOI: 10.3785/j.issn.1008-973X.2024.12.011

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

Download:

HTML

PDF(910KB) HTML
Export: BibTeX | EndNote (RIS)

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., C² 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

Received: 29 July 2023 Published: 25 November 2024

CLC:

TP 242.6

Fund: 国家自然科学基金资助项目（12161043）；江西省研究生创新专项资金项目(YC2022-S648).

Corresponding Authors: Huogen YANG E-mail: 378201848@qq.com;yanghuogen@126.com

	Service
	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	Lifang CHEN
	Huogen YANG
	Zhichao CHEN
	Jie YANG

Cite this article:

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.

URL:

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

B样条技术与遗传算法融合的全局路径规划

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

关键词： B样条技术, 移动机器人, A^*算法, 遗传算法, 路径规划

Fig.1 Flowchart of traditional genetic algorithm

Fig.2 Two dimensional continuous map

Fig.3 Schematic diagram of path-type value points generation based on multi-objective A^* algorithm

Fig.4 Correspondence between k-times B-spline segment connectors and control polygons

Fig.5 Schematic diagram of crossover process based on single-point crossover approach

Fig.6 Schematic diagram of mutation operation based on single-point mutation approach

Fig.7 Flowchart of methodological path planning

Fig.8 Continuous map of simulation experiments

Tab.1 Parameter setting for each algorithm

Tab.2 Performance comparison of different initial population generation methods

Fig.9 Comparison of path planning results of different algorithms in scenario 1

Tab.3 Comparison of experimental results of each algorithm on 18×18 map

Fig.10 Comparison of path length variation curves with iteration number for different algorithms in scenario 1

Fig.11 Comparison of path planning results of different algorithms in scenario 2

Fig.12 Comparison of path length variation curves with iteration number for different algorithms in scenario 2

Tab.4 Comparison of experimental results of each algorithm on 35×35 map

Fig.13 Mecanum wheel robot constructed in early stage of laboratory

Fig.14 Visualization results of four algorithms on ROS robot for path planning


[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]	Yunchen ZHU,Mingjun CHENG,Xinwen ZHENG,Peili CEN,Xiangshuo XI,Shan HUANG,Chen HUA,Hai HUANG. Fuzzy location selection of urban emergency facilities based on optimized non-dominated sorting genetic algorithm III[J]. Journal of ZheJiang University (Engineering Science), 2024, 58(9): 1832-1843.

[2]	Yali XUE,Hanyan LI,Quan OUYANG,Shan CUI,Jun HONG. Multi-UAVs collaborative task allocation based on genetic slime mould algorithm in battlefield environment[J]. Journal of ZheJiang University (Engineering Science), 2024, 58(8): 1748-1756.

[3]	Zhiwei FAN,Kai JIA,Lei ZHANG,Fengshan ZOU,Zhenjun DU,Mingmin LIU. Optimal velocity planning for mobile robot based on simultaneous dynamic optimization[J]. Journal of ZheJiang University (Engineering Science), 2024, 58(8): 1556-1564.

[4]	Jie ZHAO,Feng LIU,Ling XIA,Yifeng FAN. Passive shimming optimization method of MRI based on genetic algorithm-sequential quadratic programming[J]. Journal of ZheJiang University (Engineering Science), 2024, 58(6): 1305-1314.

[5]	Lifeng LI,Kun HOU,Deqiang ZOU,Hao PENG,Lingxiao LI. Optimization of section layout of steel plate composite beam with medium span[J]. Journal of ZheJiang University (Engineering Science), 2024, 58(3): 510-517.

[6]	Yuting LIU,Shijie GUO,Shufeng TANG,Xuewei ZHANG,Tiantian LI. *Path planning based on fusion of improved A and ROA-DWA for robot**[J]. Journal of ZheJiang University (Engineering Science), 2024, 58(2): 360-369.

[7]	Yan ZHAN,Jieya CHEN,Weiguang JIANG,Jiansha LU,Hongtao TANG,Xinyu SONG,Lili XU,Saimiao LIU. Multi-objective workshop material distribution method based on improved NSGA-Ⅱ[J]. Journal of ZheJiang University (Engineering Science), 2024, 58(12): 2510-2519.

[8]	Yue’an WU,Changping DU,Rui YANG,Jiahao YU,Tianrui FANG,Yao ZHENG. Area coverage path planning for tilt-rotor unmanned aerial vehicle based on enhanced genetic algorithm[J]. Journal of ZheJiang University (Engineering Science), 2024, 58(10): 2031-2039.

[9]	Hao ZHENG,Yi CAO,Shan WANG. Feeder bus route optimization of multiple subway stations considering station transfer[J]. Journal of ZheJiang University (Engineering Science), 2024, 58(10): 2162-2170.

[10]	Peng LIU,Qingchang LU,Han QIN,Xin CUI. Road network multi-stage disaster resistance optimization model and its application[J]. Journal of ZheJiang University (Engineering Science), 2024, 58(1): 96-108.

[11]	Huang LI,Hong-juan GE,Ying MA,Yong-shuai WANG. Parameters optimization design of dual-input dual-buck inverter system based on hyperplane NSGA-II[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(3): 606-615.

[12]	Li-li XU,Yan ZHAN,Jian-sha LU,Yi-ding LANG. Compound operation scheduling optimization in four-way shuttle warehouse system[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(11): 2188-2199.

[13]	Hao ZHA,Shao-hua FEI,Yun FU,Zhen LV,Wei-dong ZHU. Online decoupling technology of six-dimensional force sensor based on EtherCAT bus[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(10): 2042-2050.

[14]	Jia-ao JIN,Hong-yao SHEN,Yang-fan SUN,Jia-hao LIN,Jing-ni CHEN. Single-line laser scanning path planning for wire arc and additive manufacturing[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(1): 21-31.

[15]	Wei-xiang XU,Nan KANG,Ting XU. Optimal path planning method based on travel plan data[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(8): 1542-1552.

Viewed

Full text

Abstract

Cited

Shared

Discussed