科学技术与工程

算法	平均采样次数/次	平均寻路时间/s	平均路径长度/cm	平均规划成功率/%
RRT	1 867.42	27.85	1 663.48	82.00
RRT^*	2 500.00	18.63	1 421.43	86.00
RRT-Connect	354.57	4.26	1 591.25	92.00
改进算法	238.08	2.72	1 185.14	98.00

算法

平均采样
次数/次

平均寻路
时间/s

平均路径
长度/cm

平均规划
成功率/%

RRT

1 867.42

27.85

1 663.48

82.00

RRT^*

2 500.00

18.63

1 421.43

86.00

RRT-Connect

354.57

4.26

1 591.25

92.00

改进算法

238.08

2.72

1 185.14

98.00

算法	平均采样次数/次	平均寻路时间/s	平均路径长度/cm	平均规划成功率/%
RRT	1 867.42	27.85	1 663.48	82.00
RRT^*	2 500.00	18.63	1 421.43	86.00
RRT-Connect	354.57	4.26	1 591.25	92.00
改进算法	238.08	2.72	1 185.14	98.00

算法

平均采样
次数/次

平均寻路
时间/s

平均路径
长度/cm

平均规划
成功率/%

RRT

1 867.42

27.85

1 663.48

82.00

RRT^*

2 500.00

18.63

1 421.43

86.00

RRT-Connect

354.57

4.26

1 591.25

92.00

改进算法

238.08

2.72

1 185.14

98.00

算法	平均采样次数/次	平均寻路时间/s	平均路径长度/cm	平均规划成功率/%
RRT	2 021.19	35.12	1 593.75	84.00
RRT^*	2 500.00	28.51	1 277.29	92.00
RRT-Connect	448.29	5.76	1 445.83	96.00
改进算法	228.41	2.58	1 157.60	100.00

算法

平均采样
次数/次

平均寻路
时间/s

平均路径
长度/cm

平均规划
成功率/%

RRT

2 021.19

35.12

1 593.75

84.00

RRT^*

2 500.00

28.51

1 277.29

92.00

RRT-Connect

448.29

5.76

1 445.83

96.00

改进算法

228.41

2.58

1 157.60

100.00

算法	平均采样次数/次	平均寻路时间/s	平均路径长度/cm	平均规划成功率/%
RRT	2 021.19	35.12	1 593.75	84.00
RRT^*	2 500.00	28.51	1 277.29	92.00
RRT-Connect	448.29	5.76	1 445.83	96.00
改进算法	228.41	2.58	1 157.60	100.00

算法

平均采样
次数/次

平均寻路
时间/s

平均路径
长度/cm

平均规划
成功率/%

RRT

2 021.19

35.12

1 593.75

84.00

RRT^*

2 500.00

28.51

1 277.29

92.00

RRT-Connect

448.29

5.76

1 445.83

96.00

改进算法

228.41

2.58

1 157.60

100.00

算法	平均采样次数/次	平均寻路时间/s	平均路径长度/cm	平均规划成功率/%
RRT	2 432.33	46.53	1 630.88	38.00
RRT^*	2 500.00	32.52	1 428.57	66.00
RRT-Connect	1 018.55	14.73	1 597.03	84.00
改进算法	669.73	6.07	1 369.81	92.00

算法

平均采样
次数/次

平均寻路
时间/s

平均路径
长度/cm

平均规划
成功率/%

RRT

2 432.33

46.53

1 630.88

38.00

RRT^*

2 500.00

32.52

1 428.57

66.00

RRT-Connect

1 018.55

14.73

1 597.03

84.00

改进算法

669.73

6.07

1 369.81

92.00

算法	平均采样次数/次	平均寻路时间/s	平均路径长度/cm	平均规划成功率/%
RRT	2 432.33	46.53	1 630.88	38.00
RRT^*	2 500.00	32.52	1 428.57	66.00
RRT-Connect	1 018.55	14.73	1 597.03	84.00
改进算法	669.73	6.07	1 369.81	92.00

算法

平均采样
次数/次

平均寻路
时间/s

平均路径
长度/cm

平均规划
成功率/%

RRT

2 432.33

46.53

1 630.88

38.00

RRT^*

2 500.00

32.52

1 428.57

66.00

RRT-Connect

1 018.55

14.73

1 597.03

84.00

改进算法

669.73

6.07

1 369.81

92.00

基于复杂环境的RRT-Connect路径规划算法改进

PDF下载

谭仲万 , 袁宇浩 ^*

科学技术与工程 | 论文∙自动化技术、计算机技术 2025,25(19): 8127-8134

收起

科学技术与工程 | 论文∙自动化技术、计算机技术 2025, 25(19): 8127-8134

基于复杂环境的RRT-Connect路径规划算法改进

全屏

谭仲万, 袁宇浩^*

作者信息

南京工业大学电气工程与控制科学学院, 南京 211816

谭仲万(1998—),男,汉族,贵州毕节人,硕士研究生。研究方向:机器人路径规划。E-mail:1592146461@qq.com。

通讯作者:

*袁宇浩(1979—),女,汉族,江苏南京人,博士,副教授。研究方向:智能控制理论与应用。E-mail:505416730@qq.com。

Improvement of RRT-Connect Path Planning Algorithm Based on Complex Environments

Zhong-wan TAN, Yu-hao YUAN^*

Affiliations

College of Electrical Engineering and Control Science, Nanjing Tech University, Nanjing 211816, China

出版时间: 2025-07-08 doi: 10.12404/j.issn.1671-1815.2405752

文章导航

摘要

收起

针对RRT-Connect算法在复杂环境下路径规划效率低、避障能力差以及生成路径质量差等问题,提出一种改进的RRT-Connect算法。首先,提出一种双向目标偏向策略,增加算法的目标导向性以及路径规划效率。其次,提出一种避障优化策略,增加算法在复杂环境下的主动避障能力以及通过能力。最后,加入路径重组策略和平滑策略对生成的初始路径进行优化处理,减少路径长度及拐点,提高路径质量。通过MATLAB将改进算法与其他算法在3种复杂环境下进行对比研究。仿真结果表明,改进算法相对规划时间更少、路径长度更短、采样次数更少、路径规划成功率更高,证明了改进算法在复杂环境下的有效性。

关键词

RRT-Connect算法 / 路径规划 / 双向目标偏向策略 / 避障优化策略 / 路径优化策略

Abstract

收起

To address the issues of low path planning efficiency, poor obstacle avoidance capability, and low path quality of the RRT-Connect algorithm in complex environments, an improved RRT-Connect algorithm was proposed. Firstly, a bidirectional goal bias strategy was introduced to enhance the goal-directedness and path planning efficiency of the algorithm. Secondly, an obstacle avoidance optimization strategy was proposed to increase the algorithm's active obstacle avoidance capability and passage ability in complex environments. Finally, a path recombination strategy and a smoothing strategy were added to optimize the generated initial path, reducing path length and the number of turns, and improving path quality. The improved algorithm was compared with other algorithms in three complex environments using MATLAB. Simulation results show that the improved algorithm has less planning time, shorter path length, fewer sampling times, and a higher success rate of path planning, demonstrating the effectiveness of the improved algorithm in complex environments.

Key words

RRT-connect algorithm / path planning / bidirectional goal-biased strategy / obstacle avoidance optimization strategy / path optimization strategy

引用本文

谭仲万, 袁宇浩. 基于复杂环境的RRT-Connect路径规划算法改进. 科学技术与工程, 2025 , 25 (19) : 8127 -8134 . DOI: 10.12404/j.issn.1671-1815.2405752

Zhong-wan TAN, Yu-hao YUAN. Improvement of RRT-Connect Path Planning Algorithm Based on Complex Environments[J]. Science Technology and Engineering, 2025 , 25 (19) : 8127 -8134 . DOI: 10.12404/j.issn.1671-1815.2405752

正文

收起

随着现代社会的快速发展和科技的不断进步,机器人在工业生产、医疗救援、家庭服务等领域的应用越来越广泛。路径规划作为机器人技术中的核心问题之一,直接关系到机器人的自主性和智能化水平。路径规划旨在为机器人从起始位置到目标位置找到一条最优或次优的无碰撞路径。当前,涉及路径规划的算法有多种,如智能算法,如蚁群算法^[1]、粒子群算法^[2]等;基于图搜索的算法,如A^*算法^[3]、Dijkstra算法^[4]等;基于采样的算法,如随机路图算法^[5]、快速扩展随机树算法(rapidly-exploring random tree,RRT)^[6]等。基于采样的算法在复杂多障碍物环境或高维状态空间中具备显著优势。RRT算法因其收敛速度快、探索能力强、无需环境预处理,适合复杂环境的路径规划。然而,其采样随机性导致生成路径往往不最优且曲折不平滑,需通过改进优化解决这些问题。

在RRT算法的基础上,Kuffner等^[7]在2000年提出RRT-Connect算法。该算法使用从起点和目标点同时开始的双向搜索树,增加了搜索空间覆盖率,加快了找到路径的速度。国外对RRT-Connect算法的研究主要集中于提高算法效率和适应性,广泛应用于机器人、无人机、自动驾驶和航天领域。研究者通过优化采样策略、动态环境处理和硬件加速等方式改进算法性能。例如,在动态环境中,结合预测模型和路径重规划增强适应性;在机械臂规划中,与机器人操作系统(robot operating system,ROS)的MoveIt!框架深度结合,解决高维自由度问题;在无人机导航和行星探测中,RRT-Connect展现出三维复杂环境中的高效路径规划能力^[8]。中国对RRT-Connect算法的研究重点在于提升其规划效率、路径质量和适应复杂环境的能力。研究者通过引入多随机树、优化采样策略、目标偏置和人工势场等方法改进算法性能。改进算法广泛应用于机器人、无人机、自动驾驶和航天领域^[9]。

但在各种复杂环境下,RRT-Connect算法仍具有搜索随机性大、避障能力差以及生成路径质量差等问题。王坤等^[10]提出了基于RRT-Connect的改进算法 DRRT-Connect,该算法加入中间采样点,可同时生成四棵随机树,提高了规划速度,但在面对密集障碍物环境时其效果较差;黄壹凡等^[11]提出一种改进的RRT-Connect 算法,引入考虑祖代点的重选父节点环节,优化部分路径长度,但并未提高算法的避障能力;胡晓阳等^[12]在RRT-Connect的基础上融入人工势场法和目标偏置法,改进了算法规划路径的平滑性和速度,但在面对存在多个凹陷阱的复杂环境时,算法容易陷入局部极值区域;朱建军等^[13]通过引入高质量随机点和动态步长的方法,提高了RRT-Connect算法生成随机树的质量,并减少了冗余节点数量,但当环境中存在狭窄通道时算法规划速度减慢。

针对上述问题,基于RRT-Connect算法进行改进,通过加入双向目标偏向策略、避障优化策略以及路径优化策略,增强算法在复杂环境下的路径规划能力。最后通过实验仿真,验证改进算法在复杂环境下的改进效果以及实用性。

1 RRT-Connect算法原理

收起

RRT-Connect算法相对于RRT算法进行了若干改进,除采用两棵随机树进行双向搜索外,其扩展方式也与RRT算法有所不同^[14]。 RRT-Connect算法两棵树同时以起始点

q i n i t

和目标点

Q g o a l

进行扩展,在扩展时Tree1以RRT算法扩展方式进行扩展,而Tree2的扩展方式则是以Tree1已生成的

q n e w

为目标点,并不断向

q n e w

进行步长扩展,直至遇到障碍物时停止^[15]。遇到障碍物后Tree1与Tree2交替扩展方式,直至两棵随机树相连。

如图1所示,有4个灰色椭圆形障碍物,起始点和目标点分别为

q i n i t

和

Q g o a l

。RRT-Connect算法扩展步骤如下。

(1)分别以

q i n i t

和

Q g o a l

作为树的根节点进行扩展,生成随机树Tree1和随机树Tree2。

(2)随机生成一个采样点

q r a n d

,遍历随机树Tree1上的点,并计算这些点与

q r a n d

的距离,找出离

q r a n d

距离最近的点

q n e a r

。

(3)由随机树Tree1上的点

q n e a r

沿着

q r a n d

的方向进行固定步长扩展,得到新的点

q n e w

,对

q n e w

以及

q n e a r

和

q n e w

的连线进行碰撞检测,若存在障碍物,则舍弃该采样点并进行重新采样,回到步骤(1);若不存在障碍物,则扩展成功,将新节点

q n e w

插入随机树Tree1中。

(4)遍历随机树Tree2上所有点,并计算这些点与

q n e w

的距离,找出离

q n e w

距离最近的点

Q n e a r

。

(5)由随机树Tree2上的点

Q n e a r

沿着

q n e w

的方向进行同一个固定步长的扩展,得到新的点

Q n e w

,对

Q n e w

以及

Q n e a r

和

Q n e w

的连线进行碰撞检测,若不存在障碍物,则扩展成功,将新节点

Q n e w

插入随机树Tree2中。

(6)采用贪婪搜索策略^[16],重复(4)和(5)两个步骤,直到检测到

Q n e w

或

Q n e a r

和

Q n e w

的连线处存在障碍物时,才停止随机树Tree2的扩展,此时不再重复Step4和Step5两个步骤。

(7)交换随机树Tree1和Tree2的扩展方式,再重复上述步骤(1)~步骤(6),将不断生成的新点

q n e w

和

Q n e w

分别插入Tree1和Tree2中,直至Tree1和Tree2的最前端相连,最终得到一条无碰撞的规划路径^[17]。

2 RRT-Connect算法改进

收起

针对传统RRT-Connect算法在复杂环境下路径规划目标导向性差、避障能力差以及生成路径质量差等问题,分别引入双向目标偏向策略、避障优化策略及路径优化策略对其进行改进。

2.1 双向目标偏向策略

传统RRT-Connect算法采样方式随机性较大,易导致采样点过多,生成路径较长,在复杂环境中易花费过多时间在无效区域上采样。针对上述问题,引入基于概率P的双向目标偏向策略,使两棵随机树在扩展时均不盲目随机采样,而是具有一定导向性,快速偏向双方目标点。该策略具体原理如下:

随机树开始扩展前,算法会生成两个0~1的值P与R,其中P固定,R则每次采样前随机生成。首先对于Tree1,当R≥P时,以目标点

Q g o a l

为采样点采样,当R<P时,采样点随机生成,即

(1)

q r a n d * = Q o a, R ≥ P q r a n d, R ＜ P

式(1)中:

q r a n d *

为Tree1的最后采样点;

Q g o a l

为目标点;

q r a n d

为Tree1的随机采样点。

同理,当随机树交替扩展后,对于Tree2,当R≥P时,以起始点

q i n i t

为采样点,当R<P时,采样点随机生成,即

(2)

Q r a n d * = q i n i t, R ≥ P Q r a n d, R ＜ P

式(2)中:

Q r a n d *

为Tree2最后采样点;

q i n i t

为起始点;

Q r a n d

为Tree2的随机采样点。

P越小,随机树扩展时的目标偏向性越强。在面对复杂环境时,对于单向扩展随机树的RRT算法,P过小易使算法陷入局部极值区域。但对于RRT-Connect算法,由于双树交替扩展,同时采用双向目标偏向策略,当P较小时,算法也不易陷入局部极值。因此,加入双向目标偏向策略后,RRT-Connect算法扩展目标偏向性得到增强,一定程度上解决了其采样方式随机性较大,采样点过多及效率低等问题。

2.2 避障优化策略

RRT-Connect算法由两棵随机树交替进行扩展,当一棵随机树遇到障碍物时,会切换到另一棵随机树,而不是避开障碍物继续进行扩展,这种方法虽能使算法继续运行,但同时意味着随机树在遇到障碍物时没有较好的避障能力,只能通过不断切换的方式来进行扩展。当面对复杂障碍物环境时,随机树与障碍物的碰撞次数增多,会使得两棵随机树进行频繁不断的交替扩展现象,从而大大增加路径规划时间。尤其当复杂环境中存在狭窄通道时,RRT-Connect算法可能会出现因为避障能力差而迟迟找不到通道入口或不能快速通过狭窄通道等情况。

针对上述问题,提出一种避障优化策略,当任意一棵随机树遇到障碍物时,并不立即切换到另外一棵随机树扩展,而是进行主动避障,通过使与障碍物发生碰撞的新节点偏移一定的量来达到绕开障碍物的目的。具体思路如下。

如图2所示,随机树生成的新节点

q n e w

与障碍物相撞,为使随机树能避开障碍物,以距

q n e w

最近的点

q n e a r

为轴心,以

q n e a r

与

q n e w

连线为轴线进行偏转。设定一个固定偏转角度

θ

和最大偏转角度阈值

φ

。首先,将

q n e w

绕

q n e a r

逆时针偏转一个固定角度

θ

,得到另外一个新节点

q 1

,对该新节点以及该新节点与

q n e a r

的连线进行碰撞检测。若无障碍物,则避障成功,随机树继续正常扩展;若存在障碍物,则将

q n e w

顺时针偏转角度

θ

,得到一个新节点

q 2

,然后进行碰撞检测。同理,在点

q 2

处进行同

q 1

处的操作步骤,若仍避障失败,则继续多偏转

θ

,不断重复检测,直到避障成功。若顺逆时针偏转角度之和超过阈值

φ

仍未能避障成功,此时再切换到另一棵随机树进行扩展。

通过引入上述的避障优化策略,算法避障寻路能力得到一定程度提升。在面对复杂环境时,算法不再通过频繁交替扩展来进行避障,提高了主动避障能力,增强了对复杂环境的适应性与通过性,有效提高了路径规划成功率。

2.3 路径优化策略

在复杂环境下,通过对算法的扩展性能进行优化后,算法生成的路径还面临长度大、冗余节点多、拐点多等问题。因此,本节引入路径重组策略改进算法生成的初始路径,减少冗余点和路径长度;再通过加入路径平滑函数对重组路径进行平滑处理,减少路径拐点,提高路径质量。

2.3.1 路径重组策略

路径重组策略的原理如图3所示,规划出一条初始路径,其中

q i n i t

为起始点,

Q g o a l

为目标点。获取初始路径后,进行路径节点重连。首先,连接起始点

q i n i t

和目标点

Q g o a l

,并对该连线进行碰撞检测。若无碰撞,则

q i n i t

与

Q g o a l

之间连线为最终输出路径;反之,则重新连接起始点

q i n i t

与目标点

Q g o a l

前的一个有效节点9,再对它们之间的连线进行碰撞检测。若检测无碰撞,则可获得

q i n i t

与节点9之间的最短路径,再以节点9为新的起始点,重复上述操作,直到所有节点重连完成;若检测有障碍物,则继续连接

q i n i t

与节点9前的另一个节点8,重复上述步骤。由图3可知,上述步骤进行到节点7时满足无碰撞的条件,此时再以节点7作为初始点进行重连,直到连接到目标点

Q g o a l

,图3中虚线为最终重连后得到的路径。

由图3中重连得到的虚线路径可知,在加入路径重组策略以后,得到的新路径比初始路径长度更短、冗余点更少,路径的质量明显提高。

2.3.2 路径平滑处理

得到节点重组路径后,需对路径进行平滑处理。三次样条插值生成的路径不仅在数据点处及其一阶和二阶导数上连续,还具备局部控制的特性,且能够精确通过给定路径点,鉴于这些优点,本文采用三次样条插值函数对最后重连得到的路径进行平滑处理。

三次样条插值是一种利用三次多项式对离散数据点进行插值的方法。其基本思想是为每两个相邻的数据点构造一个三次多项式,使得整个曲线在数据点处连续并具有二阶导数。取一段路径,将路径的区间

[a, b]

分成n个区间

[(x 0, x 1), (x 1, x 2), …, (x n - 1, x n)]

,三次样条插值函数满足在任意区间

[(x i - 1, x i)]

上都有一个三次方程,即

(3)

S i (x) = a i + b i (x - x i) + c i (x - x i) 2 + d i (x - x i) 3

为确保曲线在每个路径点处光滑且连续,需要满足以下条件,即

(1)插值条件,样条函数在每个数据点处通过该点,即

(4)

S i (x i) = y i S i (x i + 1) = y i + 1

(2)连续性条件,样条函数在每个分段的交点处具有连续的一阶和二阶导数,即

(5)

S' i (x i + 1) = S' i + 1 (x i + 1) S ″ i (x i + 1) = S ″ i + 1 (x i + 1)

(3)自然边界条件,假设样条曲线在边界处的二阶导数为零,即

(6)

S ″ 0 (x 0) = 0 S ″ n - 1 (x n) = 0

本文中,三次样条插值函数通过在路径点之间的插值,使路径更加光滑,减少了急转弯和突变。

2.4 改进RRT-Connect算法流程图

综上,依次将提出的改进策略融入RRT-Connect算法,并对算法整体步骤与流程进行整理,最后得到本文的改进RRT-Connect算法。改进RRT-Connect算法具体流程图如图4所示。

3 实验仿真与分析

收起

本文仿真实验基于MATLAB软件开展,电脑硬件配置为Intel(R) Core(TM) i5-7200U CPU @2.70 GHz,8.00 GB RAM。为充分验证改进算法有效性,共设置3种复杂环境地图,并将改进算法与RRT算法、RRT^*算法以及传统RRT-Connect算法分别在3种环境下进行仿真对比。地图大小均为800×800像素,起始点为(10,10),目标点为(790,790)。采样步长为20,最大采样次数为2 500 次,算法在3种地图中各运行50次,最后取各实验数据平均值进行比较分析。

3.1 第一种复杂环境地图下算法比较研究

该复杂环境主要特点为障碍物形状不规则、排列杂乱无章,且存在凹陷阱,一些传统算法容易陷入局部极值。如图5所示,为各算法在该环境地图下的规划路径,表1为4种算法在该环境下运行的仿真实验数据。

如图5所示为各算法规划生成的路径图,其中图5(d)中红色曲线是改进算法生成的初始路径,蓝色曲线是经过路径重组以及平滑处理后得到的最终路径。由表1数据知:

(1)平均采样次数方面,本文改进算法平均采样次数238.08次,分别比RRT、RRT^*及RRT-Connect算法少1 629.34次、2 261.92次及116.49次。

(2) 平均寻路时间方面,本文改进算法平均寻路时间2.72s,分别比RRT、RRT^*及RRT-Connect算法减少90.23%、85.40%及36.15%。

(3)平均路径长度方面,本文改进算法平均路径长度1 185.14 cm,分别比RRT、RRT^*及RRT-Connect算法减少28.76%、16.62%及25.52%。

(4)平均规划成功率方面,而本文改进算法为98%,成功率最高。由上述可知,在该环境下,本文改进算法规划效率最高,生成的路径质量最优。

3.2 第二种复杂环境地图下算法比较研究

该复杂环境主要特点为障碍物数量多、密集程度大,一些避障能力较弱算法在该环境下运行易丢失效率,且规划生成的路径曲折长度大。如图6所示,为各算法在该环境地图下的规划路径,表2为4种算法在该环境下运行的仿真实验数据。

由图6可知,第二种环境地图障碍物数量增加,密集程度增大,相对于第一种环境地图,前3种算法的采样次数与寻路时间都有所增加。而本文改进算法由于具有目标导向性强、避障能力优的特点,在该环境下的采样次数以及寻路时间的平均数据要更低。由表2数据显示,在该环境下,本文改进算法的规划时间更短、平均采样次数最少、平均路径长度最短、平均规划成功率更高。

3.3 第三种复杂环境地图下算法比较研究

该复杂环境主要特点为存在两条宽度为15的细长狭窄通道,普通算法在运行时存在识别狭窄通道入口难以及在狭窄通道中扩展困难的问题。该环境相较于前两个环境,更考验算法的扩展性能。如图7所示,为各算法在该环境地图下的规划路径,表3为4种算法在该环境下运行的仿真实验数据。

如图7所示,算法需通过两条细长狭窄通道才能连接起始点与目标点,这要求算法有较强的通过能力。由表3数据知:

(1)平均采样次数方面:本文改进算法平均采样次数669.73次,分别比RRT、RRT^*及RRT-Connect算法少1 762.6、1 830.27、348.82次。

(2)平均寻路时间方面:本文改进算法平均寻路时间6.07 s,分别比RRT、RRT^*及RRT-Connect算法减少86.95%、81.33%、58.79%。

(3) 平均路径长度方面:本文改进算法平均路径长度1 369.81 cm,分别比RRT、RRT^*及RRT-Connect算法减少16.01%、4.11%及13.25%。

(4)平均规划成功率方面:RRT、RRT^*及RRT-Connect算法平均规划成功率分别为38%、66%及84%,而本文改进算法为92%,成功率最高。

该环境下,基于完全随机采样的算法将大量采样点浪费在无效区域上,规划成功率以及效率会明显降低,尤其是RRT算法,成功率降到38%。而本文改进算法在复杂环境下导向性与通过性较强,能很好适应该复杂环境,整体表现最优。

综上所述,本文改进的RRT-Connect算法在3种不同的复杂环境下相比于其他算法,各方面性能均有所提升,主要表现在:同一复杂环境下平均采样次数比其他算法少、平均寻路时间比其他算法短、平均路径长度比其他算法短以及平均规划成功率比其他算法高。表明本文改进的RRT-Connect算法在二维静态复杂环境下具有较强的适应能力与通过能力。

4 结论

收起

针对RRT-Connect算法在复杂环境下路径规划存在的问题,本文提出了一种改进的RRT-Connect算法,具体工作和结论如下。

(1)通过引入双向目标偏向策略、避障优化策略及路径优化策略,增强了算法在复杂环境下的目标导向性以及避障能力,提高了算法生成的路径质量。

(2)在3种复杂环境下对改进算法进行仿真验证,实验结果表明,改进算法相比RRT算法、RRT^*算法以及传统RRT-Connect算法,路径规划时间更少、路径长度更短、采样次数更少、路径规划成功率更高。证明了改进算法在复杂环境下的有效性,具有一定的应用价值。

基金

收起

国家自然科学基金(61773200)

参考文献

收起

文献

收起

参考文献引证文献

排序方式：

[1]

周敬东, 高伟周, 杨文广. 基于改进蚁群算法的移动机器人路径规划[J]. 科学技术与工程, 2022, 22(28): 12484-12490.

Zhou

Jingdong

, Gao

Weizhou

, Yang

Wenguang

. Mobile robot path planning based on improved ant colony algorithm[J]. Science Technology and Engineering, 2022, 22(28): 12484-12490.

[2]

王飞, 杨清平. 基于改进粒子群算法的城市物流无人机路径规划[J]. 科学技术与工程, 2023, 23(30): 13187-13194.

Wang

Fei

, Yang

Qingping

. Urban logistics UAV path planning based on improved particle swarm optimization algorithm[J]. Science Technology and Engineering, 2023, 23(30): 13187-13194.

[3]

Yin

, Tan

, Wang

, et al. An improved a-star path planning algorithm based on mobile robots in medical testing laboratories[J]. Sensors, 2024, 24(6): 1784.

[4]

Sedeno

N A

, Colebrook

. A biobjective Dijkstra algorithm[J]. European Journal of Operational Research, 2019, 276(1): 106-118.

[5]

Huppi

, Bartolomei

, Mascaro

, et al. T-PRM:temporal probabilistic roadmap for path planning in dynamic environments[C]// 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Kyoto: IEEE, 2022: 10320-10327.

[6]

Nguyen

M K

, Léonard

, Stéphane

. ART-RRT: as-rigid-as-possible exploration of ligand unbinding pathways[J]. Journal of Computational Chemistry, 2018, 39(11): 665-678.

[7]

Kuffner

J J

, LaValle

S M

. RRT-connect: an efficient approach to single-query path planning[C]// IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2000: 995-1001.

[8]

刘青云. 基于改进RRT算法的移动机器人路径规划研究[D]. 大庆: 东北石油大学, 2023.

Liu

Qingyun

. Research on mobile robot path planning based on improved RRT algorithm[D]. Daqing: Northeast Petroleum University, 2023.

[9]

朱海云. 基于改进RRT-Connect算法的码垛机器人避障路径规划研究[D]. 兰州: 兰州理工大学, 2023.

Zhu

Haiyun

. Research on obstacle-avoidance path planning for palletizing robots based on improved RRT-Connect algorithm[D]. Lanzhou: Lanzhou University of Technology, 2023.

[10]

王坤, 曾国辉, 鲁敦科, 等. 基于改进渐进最优的双向快速扩展随机树的移动机器人路径规划算法[J]. 计算机应用, 2019, 39(5): 1312-1317.

Wang

Kun

, Zeng

Guohui

, Lu

Dunke

, et al. Path planning algorithm for mobile robots based on improved asymptotically optimal bidirectional rapidly-exploring random tree[J]. Computer Applications, 2019, 39(5): 1312-1317.

[11]

黄壹凡, 胡立坤, 薛文超. 基于改进RRT-Connect算法的移动机器人路径规划[J]. 计算机工程, 2021, 47(8): 22-28.

Huang

Yifan

, Hu

Likun

, Xue

Wenchao

. Path planning for mobile robots based on improved RRT-Connect algorithm[J]. Computer Engineering, 2021, 47(8): 22-28.

[12]

胡晓阳, 赵杰, 武炎明. 基于改进RRT-Connect算法的路径规划研究[J]. 沈阳理工大学学报, 2023, 42(4): 26-30, 39.

Xiaoyang

, Zhao

Jie

, Wu

Yanming

. Research on path planning based on improved RRT-Connect algorithm[J]. Journal of Shenyang Ligong University, 2023, 42(4): 26-30, 39.

[13]

朱建军, 王明森. 基于改进RRT-Connect算法的全局路径规划[J]. 组合机床与自动化加工技术, 2024(4): 52-55, 61.

Zhu

Jianjun

, Wang

Mingsen

. Global path planning based on improved RRT-connect algorithm[J]. Modular Machine Tools and Automated Manufacturing Technology, 2024(4): 52-55, 61.

[14]

Wang

G Q

, Zhang

C Z

, Chen

M S

, et al. Research on single-target point navigation task of indoor mobile robot integrating RRT-Connect and DWA algorithms[J]. Journal of Central South University (Science and Technology), 2023, 54(11): 4326-4337.

[15]

陈志澜, 唐昊阳. 改进RRT-Connect算法的机器人路径规划研究[J]. 计算机科学与探索, 2025, 19(2): 396-405.

Chen

Zhilan

, Tang

Haoyang

. Research on robot path planning based on improved RRT-Connect algorithm[J]. Computer Science and Exploration, 2025, 19(2): 396-405.

[16]

龚立雄, 陈佳霖, 黄霄. 基于改进Informed-RRT^*算法的舰载机甲板平面路径规划[J]. 科学技术与工程, 2024, 24(17): 7429-7437.

Gong

Lixiong

, Chen

Jialin

, Huang

Xiao

. Plane path planning for carrier-based aircraft deck based on improved informed-RRT^* algorithm[J]. Science Technology and Engineering, 2024, 24(17): 7429-7437.

[17]

徐启航. 基于改进型RRT-Connect算法的六自由度机械臂路径规划研究[D]. 青岛: 青岛理工大学, 2021.

Qihang

. Research on path planning for six-degree-of-freedom robotic arm based on improved RRT-Connect algorithm[D]. Qingdao: Qingdao University of Technology, 2021.

2025年第25卷第19期

PDF下载

261

117

引用本文

BibTeX

文章信息

doi: 10.12404/j.issn.1671-1815.2405752

接收时间：2024-07-31
首发时间：2025-12-22
出版时间：2025-07-08

补充材料

相关文章

文章信息

作者

出版历史

收稿日期：2024-07-31
修回日期：2024-12-23

基金

国家自然科学基金(61773200)

作者信息

南京工业大学电气工程与控制科学学院, 南京 211816

通讯作者:

*袁宇浩(1979—),女,汉族,江苏南京人,博士,副教授。研究方向:智能控制理论与应用。E-mail:505416730@qq.com。

参考文献

分享链接

https://castjournals.cast.org.cn/joweb/kxjsygc/CN/10.12404/j.issn.1671-1815.2405752

分享至

全文二维码

扫描看全文

引用本文

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