汽车技术

方法	平均曲率 /m^-1	平均时间/s	曲率均方差/m^-1	平均节点数量/个
RRT	0.015	0.63	0.013	350
RRT-Connect	0.014	0.34	0.013	300
RRT*	0.012	0.38	0.011	210
本文算法	0.009	0.19	0.008	180

方法	平均曲率 /m^-1	平均时间/s	曲率均方差/m^-1	平均节点数量/个
RRT	0.015	0.63	0.013	350
RRT-Connect	0.014	0.34	0.013	300
RRT*	0.012	0.38	0.011	210
本文算法	0.009	0.19	0.008	180

基于优化快速搜索随机树算法的全局路径规划^*

PDF下载

杨炜 ¹ , 谭亮 ¹ , 孙雪 ¹ , 杜亚峰 ¹ , 周晓冰 ¹^,²

汽车技术 | 2024,(3): 31-36

收起

汽车技术 | 2024, (3): 31-36

基于优化快速搜索随机树算法的全局路径规划^*

全屏

杨炜¹, 谭亮¹, 孙雪¹, 杜亚峰¹, 周晓冰¹^,²

作者信息

¹ 长安大学，西安 710064

² 一汽解放汽车有限公司商用车开发院，长春 130011

通讯作者:

杨炜（1985—），男，陕西蒲城人，讲师，工学博士，主要研究方向为汽车主动安全技术、智能网联汽车，yw@chd.edu.cn。

The Global Path Planning Algorithm Based on Optimization RRT Algorithm

Wei Yang¹, Liang Tan¹, Xue Sun¹, Yafeng Du¹, Xiaobing Zhou¹^,²

Affiliations

¹ Chang’an University, Xi’an 710064

² Commercial Vehicle Development Institute, FAW Jiefang Automobile Co., Ltd., Changchun 130011

出版时间: 2024-03-24 doi: 10.19620/j.cnki.1000-3703.20230346

文章导航

摘要

收起

为了改善传统快速搜索随机树（RRT）算法在全局路径规划中存在的平滑度差、具有潜在碰撞性等问题，提出了一种双重优化的RRT算法。在传统RRT算法基础上，引入自适应目标偏向策略以缩短采样时间，引入角度约束采样策略以适应车辆极限转角。得到初始路径后，建立二项优化函数（即降低路径曲率和远离障碍物），并将其作为基点进行梯度下降二次优化，生成可供车辆行驶、平滑性良好且碰撞概率低的路径，并进行仿真验证。结果表明：优化RRT算法相比于传统RRT算法、RRT-Connect算法和RRT*算法，平均曲率分别降低了38.1%、36.4%和24.7%，曲率均方差分别降低了38.4%、38.4%和27.2%。

关键词

快速搜索随机树 / 全局路径规划 / 避障 / 梯度下降法

Abstract

收起

In order to improve the shortcomings of poor smoothness and potential collision in traditional Rapidly-exploring Random Tree (RRT) algorithm for global path planning, the paper proposed a dual-optimization RRT algorithm. Based on the traditional RRT algorithm, an adaptive target bias strategy was introduced to shorten the sampling time, and an angle-constrained sampling strategy was introduced to adapt to the vehicle’s maximum steering angle. After the initial path was obtained, a binary optimization function (reducing path curvature and avoiding obstacles) was established and used as a basis for gradient descent secondary optimization, generating a path that can be driven by vehicles with good smoothness and low collision probability, which was then simulated and verified. The results show that compared with RRT algorithm, RRT-Connect algorithm and RRT* algorithm, the optimized RRT algorithm reduces average curvature by 38.1%, 36.4% and 24.7%, respectively; while reducing curvature variance by 38.4%, 38.4% and 27.2%, respectively.

Key words

Rapidly-exploring Random Tree (RRT) / Global path planning / Obstacle avoidance / Gradient descent method

引用本文

杨炜, 谭亮, 孙雪, 杜亚峰, 周晓冰. 基于优化快速搜索随机树算法的全局路径规划^*. 汽车技术, 2024 , (3) : 31 -36 . DOI: 10.19620/j.cnki.1000-3703.20230346

Wei Yang, Liang Tan, Xue Sun, Yafeng Du, Xiaobing Zhou. The Global Path Planning Algorithm Based on Optimization RRT Algorithm[J]. Automobile Technology, 2024 , (3) : 31 -36 . DOI: 10.19620/j.cnki.1000-3703.20230346

正文

收起

1 前言

收起

无人驾驶汽车的全局路径规划旨在利用路径搜索算法，在已知起点位置、终点位置和环境信息的情况下，搜寻可行驶路径并满足安全、无碰撞和平滑等条件^[1]。

目前，国内外常用的无人驾驶汽车全局路径生成方法有基于搜索的迪杰斯特拉（Dijkstra）^[2]和A*^[3]算法，生成的路径距离虽然较短，但没有使用运动学约束，实际规划效果并不理想。智能仿生类算法^[4]、蚁群算法^[5]由于计算量过大，无法满足无人车对实时性的要求。

快速搜索随机树^[7]（Rapidly-exploring Random Tree，RRT）算法是一种基于采样的算法，通过在状态空间进行随机采样到达目标点。但由于缺乏约束及采样的随机性，导致收敛速度慢，生成的路径光滑性不足。针对传统RRT算法的各类问题，国内外学者提出了不同的改进方法：Taheri等^[7]提出模糊贪婪RRT算法，通过模糊控制实现了节点数量的减少与路径曲率的减小；张卫波等^[8]利用同心圆采样策略和临近点选择方法改进RRT的采样策略生成路径，并利用三次B样条曲线对路径进行二次优化，试验结果表明，该算法在路径平滑性和长度上与其他改进算法相比显著改善；Zaid等^[9]通过将人工势场（Artificial Potential Field，APF）法纳入双向势场梯度启发式的方法对PIB-RRT*（Probabilistic Informed Biased-Rapidly Exploring Random Trees*）和PB-RRT*（Probabilistic Roadmap Rapidly-Exploring Random Trees*）算法进行改进，使算法的效率和路径的平滑性显著提高；Skačkauskas等^[10]首先人为规定路径规划的起始点、终点及转折点，连接后形成粗略路径，将其转换为杜宾斯（Dubins）路径，通过实车试验验证了算法的有效性；臧强等^[11]提出了一种基于RRT*的路径规划算法，并将RRT*算法与自适应人工势场（Adaptive Artificial Potential Field，AAPF）法相结合，提高了路径规划效率和路径的平滑度；胡小平等^[12]提出了3种改进势场方法，并通过试验与仿真验证了方法的有效性；Mohammed等^[13]通过限制算法节点生成的区域或体积缩短了路径生成的时间。

综上，多数文献只关注改善路径平滑度和路径生成时间，而未针对实际车辆的运动姿态进行优化。本文提出自适应偏向目标策略，以改善传统RRT算法在全局路径规划中存在的平滑度差和潜在碰撞危险等问题为目标，引入角约束策略以满足实际车辆的运动需求，并建立梯度优化函数进一步优化生成的路径。

2 车辆行驶场景下的传统RRT算法优化

收起

2.1 传统RRT算法

RRT算法首先以无人驾驶汽车初始状态q_init作为初始节点生成随机树T，在可行空间q_goal中随机采样，得到随机点q_rand，遍历随机树T，查找与随机点q_rand最近的节点q_near，由q_near向q_rand以随机步长D进行扩展得到节点q_new，判断q_near向q_new扩展过程中是否与障碍物节点发生碰撞，若发生碰撞，则重新采样，否则将节点q_new添加到随机树T中，并将q_near设为节点q_new的父节点，重复以上步骤，直到将目标点q_goal加入随机树时结束循环。由q_goal沿父节点回溯到q_init，即可得到可行路径，如图1所示。针对传统RRT算法存在的一些不足，本文在RRT的基础上加以改进。

2.2 基于车辆行驶场景的传统RRT算法改进

2.2.1 基于偏向目标扩展的采样策略

APF方法是一种局部优化算法，它以目标与障碍物的合力方向作为节点扩展的方向，从而加速了节点的扩张。然而，这也容易导致在扩展节点的力平衡处无法生成节点。传统的人工势场主要用于牵引小车的局部路径规划，本文利用该思想改进节点扩展策略，障碍物对扩展节点的斥力场U_r(p)为：

（1）

U_r(p)=k_r·[ρ(p, p_obs)]^-2/2

式中：k_r为斥力场增益系数，ρ(p, p_obs)为父节点与最近的障碍物的距离。

则最近障碍物对节点的斥力F_r(p)为：

（2）

F_r(p)=k_r·[ρ(p, p_obs)]^-2

为了降低RRT算法搜索过程的盲目性，引入目标动态概率采样。动态设置概率阈值o_bia∈(0,1)，每次采样前生成随机值p∈(0,1)，如果p<o_bia，以目标点为扩展方向，否则按原定的随机步长进行扩展，以跳出与目标的碰撞。

o_bia的计算公式为：

（3）

o_bia=1-F_r(p)/F_max

式中：F_max为最大斥力；当斥力占比大时，以小步长生成节点，斥力占比小时以大步长生成扩展节点。

本文采用如图2示的栅格地图生成路径。由图2可以看出，采取目标偏向策略后的RRT有目的性地向目标节点生长，随机树的采样节点也比未采取目标偏向策略的RRT少很多，但仍存在潜在的碰撞危险及路径曲率较大、不易于车辆行驶等弊端。

2.2.2 基于车辆转角约束的重采样策略

算法生成的路径要符合传统车辆模型的实际要求，规划的路径才会具有现实指导意义。车辆模型如图3所示，在车辆匀速运动的状态下，且侧向加速度限定在0.4 g以下、轮胎侧偏特性处于线性范围时，可以将汽车模型简化为二自由度模型^[14]。设(x,y)为车辆后轴中心点的位置坐标，R为车辆的转弯半径，l为轴距，δ_f为前轮转角，v_f、v_r分别为前、后轮的瞬时速度，基于车辆运动学模型可知，在已知轴距l与最小转弯半径R_min的情况下，可求得车辆的前轮最大转向角：

（4）

δ_fmax=arctan(l/R_min)

由于每一次采样均在可行域中随机采样，很可能会出现生成大转角节点的情况，如图4所示，其中q_near为父节点，q_rand为临时节点，q_new为新节点。可以看出，传统RRT算法采样的新节点超出了车辆的转向极限，理应被去除，因此，在RRT节点生成时应加入转向约束条件，限制新节点生成时的方向，使其满足车辆的最大转向极限。

对于每个扩展的节点q_new，边E(q_near,q_new)与边E(q_n,q_near)所形成的夹角δ都不应超过车辆前轮最大转角δ_fmax。

要想使生成的新节点q_new满足前轮最大转向角δ_fmax约束，应采用如下方式生成新节点：

（5）

θ=θ_near+rand(-1,1)δ_fmax

（6）

q_new=(x_near,y_near)+(cos(θ),sin(θ))D

式中：θ、θ_near分别为边E(q_near,q_new)、边E(q_n,q_near)与全局坐标系X轴的夹角，rand(-1,1)为[-1,1]范围内的随机数，D为随机树节点的扩展随机步长，(x_near,y_near)为q_near在全局坐标系下的坐标。

该方法可以使生成的节点满足车辆的最大转向角约束，同时保持RRT算法的随机性。

如图5所示为未采用运动学约束和采用运动学约束时产生的路径。由图5可知，采用运动学约束后部分节点的转角明显比未加约束时的转角小，且未采用运动学约束时部分路径存在尖锐转角，无法满足车辆的实际行驶需求。虽然经过转角优化后曲率略有减小，但路径仍不够理想。

通过对比可以发现，在本文提出的运动学约束下生成的路径相较于传统RRT算法更加平滑，但仍存在较高的碰撞概率。

3 梯度下降法的再次优化

收起

3.1 梯度下降法优化原理

梯度下降法是求解无约束优化问题最常采用的方法之一，通过迭代求解得到最小化优化函数，从而实现对于目标值的优化。

本文根据梯度下降法原理设计合理的优化函数对RRT算法求解得的初始路径进行优化，优化函数P由2个部分组成：

（7）

P=w_o·P_obs+w_c·P_cur

式中：P_obs为障碍物函数，用于惩罚车辆与障碍物的碰撞，从而引导车辆远离不可行驶区域来保证安全性；P_cur为曲率函数，用于约束每个路径点的最大曲率，避免路径曲率过大；w_o、w_c分别为障碍物函数、曲率函数的权重，用于限制各函数的影响。

3.2 优化函数设计

3.2.1 路径安全性优化函数设计

障碍物函数P_obs可表示为：

（8）

P o b s = ∑ i = 1 N x i - o i - d o b s 2 x i - o i - d o b s

式中：x_i=(x_i,y_i)为路径点的向量坐标，o_i为与路径点x_i最近的障碍物点的向量坐标，d_obs为最大距离的阈值。

其中，对于所有的顶点x_i，有|x_i-o_i|≤d_obs，即当路径点与最近障碍物的距离大于d_obs时，P_obs不起作用。为了在接近障碍物时加重惩罚，令σ_obs=(|x_i-o_i|-d_obs)²，采用二次惩罚函数。可求得σ_obs在点x_i处的梯度为：

（9）

∂ σ o b s ∂ x i = 2 x i - o i - d o b s x i - o i x i - o i

3.2.2 路径舒适性优化函数设计

路径点处的最大曲率主要由相邻的2个节点决定，分别用x_i_-1、x_i、x_i₊₁表示3个点的向量坐标，Δφ_i为路径在点x_i处的角度改变量。则曲率函数P_cur可表示为：

（10）

P c u r = ∑ i = 1 N - 1 σ c u r Δ φ i Δ x i - κ m a x

式中：σ_cur为惩罚函数，Δx_i=x_i-x_i_-1为x_i处的位移向量，κ_max为最大允许曲率。

路径点处切向角的变化表示为：

（11）

Δ φ i = a r c c o s Δ x i T Δ x i + 1 Δ x i Δ x i + 1

曲率κ_cur=Δφ_i/Δx_i，当κ_cur≥κ_max时，最大允许曲率的偏差用惩罚函数σ_cur进行惩罚。可求得κ_cur在3个点处的梯度分别为：

（12）

∂ κ c u r ∂ x i = - 1 Δ x i ∂ Δ φ i ∂ c o s (Δ φ i) ∂ c o s (Δ φ i) ∂ x i - ∂ Δ φ i Δ x i 2 ∂ Δ x i ∂ x i

（13）

∂ κ c u r ∂ x i - 1 = - 1 Δ x i ∂ Δ φ i ∂ c o s (Δ φ i) ∂ c o s (Δ φ i) ∂ x i - 1 - ∂ Δ φ i Δ x i 2 ∂ Δ x i ∂ x i - 1

（14）

∂ κ c u r ∂ x i + 1 = - 1 Δ x i ∂ Δ φ i ∂ c o s (Δ φ i) ∂ c o s (Δ φ i) ∂ x i + 1

通过这3项加权求和得到曲率惩罚梯度：

（15）

∂ Δ φ i ∂ c o s (Δ φ i) = ∂ a r c c o s c o s Δ φ i) ∂ c o s (Δ φ i) = - 1 1 - c o s 2 (Δ φ i) 1 / 2

对生成的路径采用本文所提出的梯度优化法进行二次优化，经过梯度下降优化前、后的路径如图6所示。由对比结果可知，经过梯度下降法优化后的路径曲率更加平滑且无突变产生。

4 验证与分析

收起

为了充分说明改进后的RRT算法的优化效果，将其与RRT算法、RRT*算法和RRT-Connect算法所规划的路径进行对比。在图7所示的场景下，每个算法各进行12次仿真，去掉最优和最差值后统计平均曲率、时间、曲率均方差以及节点数量，结果如图8和表1所示。相较于其他3种方法，本文提出的改进RRT算法在平均曲率和曲率均方差上存在明显优势：平均曲率为0.009 m^-1，曲率均方差为0.008 m^-1，并具有良好的稳定性。小的平均曲率和曲率均方差意味着路径点之间没有过大的转向突变，有利于提高车辆乘坐舒适度和跟踪效果；此外，改进RRT算法在4种方法中计算时间较短，能够提高规划效率。

5 结束语

收起

本文提出了一种双重优化RRT算法，采用角约束采样策略来改善路径生成，并使用梯度下降法对产生的路径进行二次优化，从而得到更加平滑、易于车辆行驶的路径，提高实际车辆行驶的安全性和舒适性，并通过仿真验证将本文算法与RRT及其衍生算法的路径规划结果进行了对比分析。仿真结果表明，相比于其他算法，本文算法在路径曲率方面更具优势，有效改善了车辆在实际行驶工况下的安全舒适性。

基金

收起

*国家重点研发计划项目(2021YFE0203600)
陕西省自然科学基金青年项目(2017JQ6045)

参考文献

收起

文献

收起

参考文献引证文献

排序方式：

[1]

朱冰, 韩嘉懿, 赵健, 等. 基于安全场改进RRT-*算法的智能汽车路径规划方法[J]. 汽车工程, 2020, 42(9): 1145-1150+1182.

ZHU

, HAN

J Y

, ZHAO

, et al. Intelligent Vehicle Path Planning Method Based on Improved RRT-* Algorithm Based on Safety Field[J]. Automotive Engineering, 2020, 42(9): 1145-1150+1182.

[2]

叶颖诗, 魏福义, 蔡贤资. 基于并行计算的快速Dijkstra算法研究[J]. 计算机工程与应用, 2020, 56(6): 58-65.

Y S

, WEI

F Y

, CAI

X Z

. Research on Fast Dijkstra’s Algorithm Based on Parallel Computing[J]. Computer Engineering and Applications, 2020, 56(6): 58-65.

[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]. ISPRS International Journal of Geo-Information, 2021, 10(11).

[4]

SANGEETHA

, RAVICHANDRAN

K S

, SHEKHAR

, et al. An Intelligent Gain-Based Ant Colony Optimisation Method for Path Planning of Unmanned Ground Vehicles[J]. Defence Science Journal, 2019, 69(2): 167-172.

[5]

李根, 李航, 张帅阳, 等. 基于蚁群算法的最优路径规划及参数研究[J]. 中国科技论文, 2018, 13(16): 1909-1914.

, LI

, ZHANG

S Y

, et al. Research on Optimal Path Planning and Parameters Based on ant Colony Algorithm[J]. China Science and Technology Papers, 2018, 13(16): 1909-1914.

[6]

LAVALLE

S M

. Rapidly-Exploring Random Trees: A New Tool for Path Planning[J]. Algorithmic and Computational Robotics New Directions, 1998: 293-308.

[7]

TAHERI

, FERDOWSI

M H

, DANESH

. Fuzzy Greedy RRT Path Planning Algorithm in a Complex Configuration Space[J]. International Journal of Control Automation and Systems, 2018, 16(6): 3026-3035.

[8]

张卫波, 肖继亮. 改进RRT算法在复杂环境下智能车路径规划中的应用[J]. 中国公路学报, 2021, 34(3): 225-234.

ZHANG

W B

, XIAO

J L

. Application of Improved RRT Algorithm in Intelligent Vehicle Path Planning Complex Environment[J]. Chinese Journal of Highways, 2021, 34(3): 225-234.

[9]

ZAID

, QURESHI

A H

, YASAR

, et al. Potentially Guided Bidirectionalized RRT* for Fast Optimal Path Planning in Cluttered Environments[J]. Robotics and Autonomous Systems, 2018, 108: 13-27.

[10]

SKAČKAUSKAS

, SOKOLOVSKIJ

. Analysis of the Hybrid Global Path Planning Algorithm for Different Environments[J]. Transport and Telecommunication, 2019, 20(1): 1-11.

[11]

臧强, 张国林, 靳雨桐, 等. 一种基于动态步长的AAPF-RRT*移动机器人路径规划新算法[J]. 中国科技论文, 2021, 16(11): 1227-1233+1270.

ZANG

, ZHANG

G L

, JIN

Y T

, et

. A New AAPF-RRT* Mobile Robot Path Planning Algorithm Based on Dynamic Step Size[J]. China Science and Technology Paper, 2021, 16(11): 1227-1233+1270.

[12]

胡小平, 曹敬. 一种多机器人的改进势场路径规划算法[J]. 机械科学与技术, 2018, 37(8): 1207-1216.

X P

, CAO

. An Improved Potential Field Path Planning Algorithm for Multiple Robots[J]. Mechanical Science and Technology, 2018, 37(8): 1207-1216.

[13]

MOHAMMED

, JARADAT

M A

, ROMDHANE

L B

. RRT*N:An Improved Rapidly-Exploring Random Tree Approach for Reduced Processing Times[C]// 2018 11th International Symposium on Mechatronics and Its Applications (ISMA). Sharjah, United Arab Emirates: IEEE, 2018.

[14]

陈特, 陈龙, 徐兴, 等. 基于Hamilton理论的无人车路径跟踪控制[J]. 北京理工大学学报, 2019, 39(7): 676-682.

CHEN

, CHEN

, XU

, et al. Unmanned Vehicle Path Tracking Control Based on Hamilton Theory[J]. Transactions of Beijing Institute of Technology, 2019, 39(7): 676-682.

2024年第卷第3期

PDF下载

197

引用本文

BibTeX

文章信息

doi: 10.19620/j.cnki.1000-3703.20230346

首发时间：2025-12-23
出版时间：2024-03-24

补充材料

相关文章

文章信息

作者

出版历史

基金

*国家重点研发计划项目(2021YFE0203600)

陕西省自然科学基金青年项目(2017JQ6045)

作者信息

¹ 长安大学，西安 710064

² 一汽解放汽车有限公司商用车开发院，长春 130011

通讯作者:

杨炜（1985—），男，陕西蒲城人，讲师，工学博士，主要研究方向为汽车主动安全技术、智能网联汽车，yw@chd.edu.cn。

参考文献

分享链接

https://castjournals.cast.org.cn/joweb/qcjs/CN/10.19620/j.cnki.1000-3703.20230346

分享至

全文二维码

扫描看全文

引用本文

BibTeX

本文的引用情况

2种不同金属材料的力学参数

科 Family	属数 Number of genus	种数 Number of species	占总种数比例 Percentage of total species (%)	属 Genus	种数 Number of species	占总种数比例 Percentage of total species (%)
鹅膏菌科Amanitaceae	2	11	5.26	鹅膏菌属 Amanita	10	4.78
小菇科 Mycenaceae	2	12	5.74	丝盖伞属 Inocybe	5	2.39
多孔菌科 Polyporaceae	8	14	6.70	蜡蘑属 Laccaria	5	2.39
红菇科 Russulaceae	3	23	11.00	小皮伞属 Marasmius	6	2.87
				小菇属 Mycena	11	5.26
				光柄菇属 Pluteus	5	2.39
				红菇属 Russula	17	8.13
				栓菌属 Trametes	5	2.39

关闭全屏

BibTeX
EndNote
RefWorks
TxT