基于GA优化与路径扩展启发式采样的BI-RRT*路径规划方法

doi:10.3969/j.issn.1674-8484.2025.06.012

摘要/Abstract

摘要： 针对传统BI-RRT*存在收敛缓慢和路径随机性过强的问题，提出改进的BI-RRT*算法与进化策略相结合的双阶段优化框架算法GEP_BIRRT。该方法首先对BI-RRT*算法引入柔性边界限制采样范围提高搜索效率，并设计度量函数获得高质量的可行路径；其次，基于遗传算法进行路径优化，以可行路径为中心构建优化区域，设计多目标优化的适应度函数以平衡路径平滑性和安全性得到最终规划路径；最后利用MATLAB软件进行仿真实验。结果表明：在3种不同环境下GEP_BIRRT都具有较好的鲁棒性，相对于Informed-RRT*和传统BI-RRT*，规划时长分别平均减少59.48%和20.08%，规划路径长度分别平均缩短1.26%和1.51%，累计转弯角度分别平均减少32.60%和40.84%，同时能较好地实现动态障碍物的规避，验证了GEP_BIRRT算法的优越性与可行性。

关键词: 路径规划, 路径扩展, 遗传算法, 快速随机搜索

Abstract:

To address the issues of slow convergence and excessive path randomness in traditional BI-RRT*, this paper proposed a two-stage optimization framework algorithm, GEP_BIRRT, which combined an improved BI-RRT* algorithm with evolutionary strategies. Firstly, flexible boundary constraints to the BI-RRT* algorithm were introduced to enhance search efficiency by limiting the sampling range, and a metric function to obtain high-quality feasible paths was designed. Second, a path optimization was performed based on a genetic algorithm, in which an optimization region centered on feasible paths was constructed and a multi-objective fitness function was designed to balance path smoothness and safety, ultimately yielding the planned path. Finally, simulation experiments were conducted using MATLAB software. The strong robustness of GEP_BIRRT across three distinct environments was demonstrated by the results. The results show that compared to Informed-RRT* and traditional BI-RRT*, the planning duration is reduced by 59.48% and 20.08% on average, respectively, with average path length reductions of 1.26% and 1.51%, and cumulative turning angle reductions of 32.60% and 40.84%, respectively. It also effectively avoids dynamic obstacles, validating the superiority and feasibility of the GEP_BIRRT algorithm.

Key words: path planning, path extension, genetic algorithm, fast random search

中图分类号:

U467.13

张炳力, 张智森, 张羊阳, 刘安, 许永华. 基于GA优化与路径扩展启发式采样的BI-RRT*路径规划方法[J]. 汽车安全与节能学报, 2025, 16(6): 923-933.

ZHANG Bingli, ZHANG Zhisen, ZHANG Yangyang, LIU An, XU Yonghua. BI-RRT* path planning method based on GA optimization and path extension heuristic sampling[J]. Journal of Automotive Safety and Energy, 2025, 16(6): 923-933.

图/表 18

参考文献 21

[1]	匡兴红, 沈佳成. 改进北方苍鹰算法及其在智能汽车路径规划中的应用[J]. 汽车安全与节能学报, 2025, 16(1): 148-158.
	KUANG Xinghong, SHEN Jiacheng. Improvement of the northern eagle algorithm and its application in intelligent vehicle path planning[J]. J Autom Safe Energ, 2025, 16(1): 148-158. (in Chinese)
[2]	郭丛帅, 刘辉, 聂士达, 等. 考虑复杂地形和障碍尺度的无人车轨迹规划[J]. 汽车工程, 2025, 47(4): 645-657, 668.
	GUO Congshuai, LIU Hui, NIE Shida, et al. Trajectory planning for autonomous vehicles considering complex terrain and obstacle scales[J]. Autom Engineering, 2025, 47(4): 645-657, 668. (in Chinese)
[3]	滕磊. 无人驾驶车辆路径规划与轨迹跟踪控制算法的研究[D]. 杭州: 浙江科技大学, 2024.
	TENG Lei. Research on the path planning and track tracking control algorithm of autonomous driving vehicles[D]. Hangzhou: Zhejiang University of Science and Technology, 2024. (in Chinese)
[4]	TANG Guang, TANG Congqiang, 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. doi: 10.1109/ACCESS.2021.3070054 URL
[5]	QING Guo, ZHENG Zhang, YUE Xu. Path-planning of automated guided vehicle based on improved Dijkstra algorithm [C]// 2017 29th Chinese Contr Deci Conf (CCDC). Chongqing, China. IEEE, 2017: 7138-7143.
[6]	赵晓鹏, 王国权. 基于改进人工势场法的车辆编队避障研究[J]. 电子测量技术, 2025, 48(18): 13-19.
	ZHAO Xiaopeng, WANG Guoquan. Research on vehicle formation obstacle avoidance based on improved artificial potential field method[J]. Elect Meas Tech, 2025, 48(18): 13-19. (in Chinese)
[7]	朱冰, 贾士政, 赵健, 等. 自动驾驶车辆决策与规划研究综述[J]. 中国公路学报, 2024, 37(1): 215-240. doi: 10.19721/j.cnki.1001-7372.2024.01.018
	ZHU Bing, JIA Shizheng, ZHAO Jian, et al. A review of decision-making and planning research on self-driving vehicles[J]. China J Highw Transport, 2024, 37(1): 215-240. (in Chinese)
[8]	Noreen I, Khan A, Habib Z. A comparison of RRT, RRT* and RRT-smart path planning algorithms[J]. Int’l J Comput Sci Netw Secu* (IJCSNS), 2016, 16(10): 20-27.
[9]	王蔡琪, 崔西宁, 熊毅, 等. 基于节点到障碍物距离的自适应扩展RRT*路径规划算法[J]. 计算机应用, 2025, 45(3): 920-927. doi: 10.11772/j.issn.1001-9081.2024030400
	WANG Caiqi, CUI Xining, XIONG Yi, et al. Adaptive extended RRT* path planning algorithm based on node-to-obstacle distance[J]. J Comput Appl, 2025, 45(3): 920-927. (in Chinese) doi: 10.11772/j.issn.1001-9081.2024030400
[10]	Karaman S, Frazzoli E. Sampling-based algorithms for optimal motion planning[J]. Int’l J Robot Res, 2011, 30(7): 846-894.
[11]	CHAI Qisen, WANG Yujun. RJ-RRT: improved RRT for path planning in narrow passages[J]. Appl Sci, 2022, 12(23): 12033-12050.
[12]	WANG Binpeng, JU Dianyuan, XU Fangzhou, et al. BI-RRT: an improved bidirectional RRT path planner for robot in two-dimensional space[J]. IEEJ Trans Electri Electro Engi, 2023, 18(10): 1639-1652.
[13]	采国顺, 刘昊吉, 冯吉伟, 等. 智能汽车的运动规划与控制研究综述[J]. 汽车安全与节能学报, 2021, 12(3): 279-297.
	CAI Guoshun, LIU Haoji, FENG Jiwei, et al. Research review on motion planning and control for intelligent vehicles[J]. J Autom Safe Energ, 2021, 12(3): 279-297. (in Chinese)
[14]	赵学健, 叶昊, 江宇航, 等. 融合改进D*与RRT算法的单AGV路径规划算法[J]. 小型微型计算机系统, 2025, 46(8): 1847-1860.
	ZHAO Xuejian, YE Hao, JIANG Yuhang, et al. A single AGV path planning algorithm incorporating improved D* and RRT algorithms[J]. J Chin Comput Syst, 2025, 46(8): 1847-1860. (in Chinese)
[15]	蒋启龙, 许健. 改进PSO-PH-RRT*算法在智能车路径规划中的应用[J]. 东北大学学报(自然科学版), 2025, 46(3): 12-19.
	JIANG Qilong, XU Jian. Improved PSO-PH-RRT* algorithm in intelligent vehicle path planning[J]. J Northeast Univ (Nat Sci), 2025, 46(3): 12-19. (in Chinese)
[16]	WANG Wenjuan, LI Jiaye, BAI Zongning, et al. Toward optimization of AGV path planning: an RRT-ACO algorithm[J]. IEEE Access*, 2024, 12: 18387-18399. doi: 10.1109/ACCESS.2024.3359748 URL
[17]	李忠林, 贾玉婷, 蒋晓丽. 改进遗传算法的移动机器人路径规划研究[J]. 现代信息科技, 2024, 8(23): 180-183, 188.
	LI Zhonglin, JIA Yuting, JIANG Xiaoli. Research on mobile robot path planning with improved genetic algorithm[J]. Mode Info Tech, 2024, 8(23): 180-183, 188. (in Chinese)
[18]	Lavalle S M, Kuffner J J J. Randomized kinodynamic planning[J]. Int’l J Robot Res, 1999, 15(5): 378-400.
[19]	Gammell J D, Srinivasa S S, Barfoot T D, et al. Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic [C]// 2014 IEEE /RSJ Int’l Conf Intel Robot Syst (IROS 2014Chicago, IL, USA. IEEE, 2014: 2997-3004.
[20]	Jordan M, Perez A. Optimal bidirectional rapidly-exploring andom trees[R]. Csail MIT, 2013, MIT-CSAIL-TR-2013-021.
[21]	CUI Bo, CUI Rongxin, YAN Weisheng, et al. RT-RRT:Reverse tree guided real-time path planning/replanning in unpredictable dynamic environments [C]// 2024 IEEE/RSJ Int’l Conf Intel Robot Syst (IROS). Abu Dhabi, United Arab Emirates. IEEE, 2024: 5380-5387.

扩展基本步长	20
种群数量，N_P	50
进化次数，G_max	100
锦标赛选择数量	3
交叉概率，p_c	0.8
最小变异概率，p_m.min	0.1
最大变异概率，p_m.max	0.3

扩展基本步长	20
种群数量，N_P	50
进化次数，G_max	100
锦标赛选择数量	3
交叉概率，p_c	0.8
最小变异概率，p_m.min	0.1
最大变异概率，p_m.max	0.3

实验环境	实验算法	平均路径长度	最优路径长度	平均规划时间/ s	最短用时/ s	平均总转角/ (°)
复杂障碍物	Informed-RRT*	708.460	701.500	2.278	2.065	228.592
	BI-RRT*	711.381	702.214	1.794	1.620	317.402
	GEP_BIRRT	701.074	696.673	1.857	1.573	154.147
迷宫	Informed-RRT*	815.490	805.272	3.215	2.907	384.057
	BI-RRT*	820.836	804.884	1.694	1.481	421.388
	GEP_BIRRT	806.318	799.392	1.806	1.442	273.355
狭窄通道	Informed-RRT*	973.051	960.308	5.492	5.087	375.659
	BI-RRT*	970.842	964.300	2.702	2.419	372.965
	GEP_BIRRT	958.113	953.146	1.614	1.061	238.905

实验环境	实验算法	平均路径长度	最优路径长度	平均规划时间/ s	最短用时/ s	平均总转角/ (°)
复杂障碍物	Informed-RRT*	708.460	701.500	2.278	2.065	228.592
	BI-RRT*	711.381	702.214	1.794	1.620	317.402
	GEP_BIRRT	701.074	696.673	1.857	1.573	154.147
迷宫	Informed-RRT*	815.490	805.272	3.215	2.907	384.057
	BI-RRT*	820.836	804.884	1.694	1.481	421.388
	GEP_BIRRT	806.318	799.392	1.806	1.442	273.355
狭窄通道	Informed-RRT*	973.051	960.308	5.492	5.087	375.659
	BI-RRT*	970.842	964.300	2.702	2.419	372.965
	GEP_BIRRT	958.113	953.146	1.614	1.061	238.905