基于改进RRT算法的狭长空间无人车辆路径规划.pdf

DOI：10.12265/j.gnss.2023090基于改进 RRT 算法的狭长空间无人车辆路径规划张俊豪，潘树国，高旺，郭芃，王萍，胡鹏(东南大学仪器科学与工程学院,南京 210096)摘要：针对狭长空间无人车辆路径规划系统，提出一种基于改进的快速搜索随机树(rapidly-exploringrandomtrees，RRT)路径规划算法，以解决传统 RRT 算法随机性较大、路径缺乏安全性的问题.该算法通过加入自适应目标概率采样策略、动态步长策略对传统的 RRT 算法进行改进，同时考虑到实际情况中无人驾驶车辆的动力学约束，该算法加入车辆碰撞约束和路径转角约束，并针对转角约束会导致迭代次数激增的问题提出了一种限制区域内随机转向的策略，最终得到一条安全性较高的路径.采用计算机仿真对所提算法和现有算法的性能进行对比验证.所提算法在狭长空间相较于传统人工势场引导下的 RRT 算法迭代次数降低了 33.09%，规划时间减少了 6.44%，路径长度减少了 0.06%，并且在简单环境和复杂障碍物环境下规划能力均有提升.所提算法规划效率更高、迭代次数更少.关键词：快速搜索随机树(RRT)；自适应目标概率采样；动态步长；路径约束；随机转向策略中图分类号：P228.4文献标志码：A文章编号：1008-9268（2023）04-0081-100引言近年来，得益于电子通信技术、智能控制技术和智能计算技术等先进科技领域研究的突飞猛进，无人驾驶技术在世界各国得到快速发展.其中，路径规划是实现无人驾驶的重要技术之一，也是无人驾驶车辆能否安全并有效地抵达目的地的关键.路径规划是指在规定区域内规划出一条从起点到目标点的最优解路径，且要保证与障碍物无碰撞，并尽可能保证路径短、平滑度高、规划时间短1.目前，路径规划算法可以分为传统路径规划算法和智能仿生路径规划算法两类，其中传统路径规划算法有 A*(Astar)算法、快速搜索随机树算法(rapidly-exploringrandomtrees，RRT)、人工势场算法、动态 A*算法(dynamicA*，D*)等；智能仿生路径规划算法有蚁群算法、粒子群算法、遗传算法等.在这些算法中，RRT算法是一种基于采样的算法，因其具有概率完备性的特点而被广泛应用于机器人路径规划中.近年来，针对 RRT 算法收敛速度慢、随机性较大的缺点，许多学者都提出了改进 RRT 算法的措施.Karaman 等2提出RRT*算法，该算法引入了重新布线的思想，通过重新选取路径的父节点，使得得到的路径最短；彭君3提出了基于变权重势场的改进RRT 算法和基于模糊逻辑的改进 RRT*算法，前者通过采用 KD-Tree 算法(k-dimensionaltree)和变权重的人工势场法的规划策略，解决了 RRT 算法在路径规划时收敛速度慢和避障效果较差的问题，后者在RRT*算法的基础上加入了模糊逻辑策略，提高了路径质量；Zucker 等4提出了 MP-RRT 算法，该算法通过偏置采样分布并重新使用先前规划迭代中的分支来实现动态环境中的实时规划；Otte 等5提出 RRTX算法，它在整个导航过程中对相同的搜索图进行了改进，以处理不可预测的移动障碍物.现有的算法大多聚焦于改进各个算法本身，专注于对算法进行优化和结合，但却忽略了实际情况中环境和无人车辆本身的约束.在狭长空间中，可行区域狭小，随机树很容易陷入局部困境，从而导致规划效率和成功率较低，影响无人车辆的正常运行.另外，在狭长空间中，无人车辆的尺寸不可忽视，这对于路径则有着更高的要求.在已有研究成果的基础上，结合 RRT 算法本身的缺陷以及无人车辆和环境的约束，本文提出了一种收稿日期：2023-04-17资助项目：国家重点研发计划(2021YFB3900804)通信作者：潘树国E-mail：第 48卷第4期全球定位系统Vol.48，No.42023年8月GNSS World of ChinaAugust，2023改进 RRT 算法.该算法首先通过目标动态概率采样策略，将终点信息加入了 RRT 算法随机采样的过程里，减少了 RRT 算法随机采样的盲目性；之后利用人工势场对 RRT 算法中的随机树进行引导，使其更容易接近终点；然后算法考虑了传统 RRT 算法中步长固定导致的规划效率低的问题，以一种动态步长代替原有的固定步长，提高了规划效率；最后，算法考虑了实际情况中路径的转角限制和车辆的碰撞限制，提高了路径的平滑度和安全性.1传统人工势场引导下的 RRT 算法传统的 RRT 算法是一种基于采样的路径规划算法，以一个初始的根节点为起点，通过随机采样的方法在空间搜索，然后添加子节点来不断扩展随机树.当目标点进入随机树后，随机树扩展立即停止，此时能找到一条从起始点到目标点的路径.人工势场法(artificialpotentialfield，APF)是一种人为的在地图中添加一个特殊的场来引导无人车辆从起点到终点的路径规划算法.RRT 算法最大的优点在于其搜索能力强，能够在时间充足的情况下搜索整个空间，从而得到一条可行路径，但其搜索的随机性也带来了搜索效率低的缺陷.而 APF 则拥有目标导向的作用，将两者结合，人工势场能够在一定程度上引导随机树向目标点扩展，同时 RRT 算法也能在一定程度上解决 APF 容易陷入局部最优解的情况.图 1 为人工势场引导下的 RRT 算法(APF-RRT算法).XnewXrandXnearF图 1 APF-RRT 算法示意图其算法流程图如图 2 所示.初始化随机采样获得Xrand确定与Xrand最近的节点Xnear根据RRT和APF算法扩展得到新节点XnewXnear与Xnew的连线与障碍物相交将Xnew加入随机树，更新随机树Xnear到Xgoal距离小于预设距离回溯节点得到规划路径，结束舍弃Xnew节点是否是否计算Xnear所受合力F图 2 APF-RRT 算法流程图2算法优化及改进2.1 改进 RRT 算法2.1.1自适应目标概率采样PgoalXgoalXrand在传统的 RRT 算法中，虽然随机树能够保证在时间充足的情况下搜索出一条可行路径，但这样的搜索具有盲目性，会使得随机树产生许多无用的节点，另外，当随机树扩展到目标点附近时，由于搜索的随机性，会出现多次扩展都无法扩展至目标点范围的情况，降低了规划效率.为解决这样的问题，本文采用自适应目标概率采样的方法为随机树增加目标导向性，使得其能够快速扩展到目标点附近.传统的目标概率采样策略的做法，在采样阶段，以一定的概率选用目标点作为随机采样点，即Xrand=Xgoal,P PgoalXrandom,P Pgoal(1)XrandomP式中：为原算法随机产生的采样点；为 01的一个随机值.PgoalPgoal传统的目标概率采样策略能够很好地对随机树产生一定的目标引导作用，但是，当地图中的障碍物较多且较为密集，尤其是狭长路段时，直接使用传统的目标概率采样策略不仅不会提高规划效率，反而会出现陷入局部困境的问题.为了解决这样的问题，本文采用目标动态概率采样的方法来应对障碍物密集的情况.具体的做法是将原有的固定的概率调整为自适应的值，即当随机树扩展到障碍物密集的区域时则降低，使得随机树能够更好地逃离狭长区域.即82全 球 定 位 系 统第48卷Pgoal=niternvoidniterPmax(2)niternvoidPmax式中：为迭代次数；为无效节点的个数(即与障碍物发生碰撞的节点个数)；为概率采样阈值的最大值(一般为 0.10.3).2.1.2动态步长在 RRT 算法中，由于步长的固定性，导致算法不能适应地图中的各种情况，从而使得生成路径的平滑度和效率较低.当步长较大时，生成路径的效率较高，当产生路径的平滑度较低，并且当遇到狭长区域时会陷入局部困境从而提高迭代次数；当步长较小时，在遇到狭长区域时能够快速逃离障碍物区域并且生成路径较为平滑，但规划效率较低.因此，为了解决这种矛盾，本文采用一种动态步长的方法，使得步长随着障碍物的密集程度进行变化，能够有效解决大步长和小步长之间的矛盾，提高 RRT 算法适应各种环境的能力，从而使得其能够更好地应用于狭长区域.具体的动态步长为=(1SobsStotal)ori(3)SobsStotalXrandXnearori式中：为所有障碍物与上述矩形相交部分的面积；为以和为对角线且长和宽平行于坐标轴的矩形面积；为设置的初始最大步长.示意图如图 3 所示.XnearXrand图 3 动态步长策略示意图XrandXnearStotalSobs其中，以和为对角线的矩形面积即为，红色区域的面积即为.通过这样的动态步长，能够让随机树在狭长空间减少步长，从而快速逃离该区域；在空旷的区域，步长会随之增大，从而提高规划效率.2.2 路径约束条件常见的路径规划算法大多关注于算法的优化和结合，而忽略了实际情况中的一些动力学约束条件，这些约束条件是让无人驾驶车辆能够正常运作的关键条件，因此并不能忽略.例如实际无人车辆不能作为质点进行处理，而必须考虑其本身大小，另外实际无人车辆的底盘有最大转角的限制，过大的路径转角会使得无人车辆花费更多的动力甚至出现无法转向的情况，因此本节将从碰撞约束和路径转角约束两个方面展开.2.2.1碰撞约束XrandXnear安全性是路径规划的基本要求之一，为了让生成的路径能够使得无人车辆安全地抵达终点，必须对路径点进行碰撞约束.常用的碰撞约束是判断以和为端点和线段与障碍物是否相交来完成的，但是这样方法的前提是将无人车辆看作质点，然而实际情况中如狭长空间中，无人车辆的大小无法忽略，常用的碰撞约束方法则不适用.XnewXnew本文考虑了无人车辆的大小，将其视为一个矩形，在每产生一个节点之后，对其进行碰撞检测，若以为中心的矩形与障碍物有相交的情况，则舍弃该节点.但是，当步长较大时，会出现图 4 所示的情况.XnearXnew图 4 步长较大时两节点连线与障碍物相交XnewXnearXnewXnearXmidXmidXnewXmidXnew这种情况的和节点均满足碰撞约束，但是，他们的连线与障碍物发生的相交.为了减少这种情况，取和的中点，对同样进行一次碰撞检测，即当和均通过碰撞检测时才认为是符合碰撞约束的，从而提高路径的安全性.2.2.2路径转角约束路径的转角约束对于无人车辆也是十分有必要的，这样不仅能够减少无人车辆转向所消耗的动力，也能提高路径的平滑度.路径的转角如图 5 所示.XnewXnearXparent图 5 路径转角XparentXrand其中，为的父节点，为转角，根据余弦定理，有=180arccosl2Xnear,Xparent+l2Xnear,Xnewl2Xnew,Xparent2lXnear,XparentlXnear,Xnew(4)第4期张俊豪，等：基于改进 RRT 算法的狭长空间无人车辆路径规划83lXnear,XparentlXnear,XnewlXnew,XparentXnewmax式中，、和分别表示三个节点之间的距离.当产生时，若的值大于所允许的最大转角限制，则舍弃该节点，从而保证转角约束.2.2.3限制区域随机转向上述的路径转角约束对于无人车辆的作用不可忽视，但是，这样的约束对于规划效率带来了很大的困难，由于 RRT 算法的随机性，满足转角约束的节点较少，这就导致每次规划都将花费较多的迭代次数，大大降低了规划效率，这在狭长的空间尤为明显.狭长空间由于可行区域较窄，转角的限制会使得随机树陷入局部困境.XnewXnear2maxXnewXnew为了解决这样的问题，本文提出了限制区域随机转向的策略.即当产生的不满足转角约束的时候，在以为顶点，为张角的范围内随机选择一个方向，在这个方向以步长产生新的，这样产生的满足转角限制，因此只需要进行碰撞检测即可.示意图如图 6 所示.XnearXnewXoldmaxrand图 6 限制区域随机转向策略示意图Xoldrandmax其中，为不符合转角约束的节点，为 0随机选取的角度.随机转向的策略为随机树在障碍物密集或狭长的空间提供了更多扩展到可行区域的机会.2.3 算法总流程图 7 为算法整体流程.算法的具体步骤如下：XstartXgoalOrectstepori1)设置起点，终点，可行区域，障碍物，初始最大步长等参数；OXrand2)在可行区域内采用自适应目标概率采样得到；XrandXnear3)遍历随机树上的所有节点，计算得出距离最近的节点；4)根据动态步长策略得到新的步长 step；XnearF5)计算所受的引力场和斥力场的合力；XnearXrandFFnew6)计算指向的单位向量并和的单位向量进行矢量叠加得到新的向量；FnewXnew7)以方向，step 为步长扩展生成新的节点；XnewXnewXnewXnewXnewXnewXnewXnewXnewXnew8)若不满足碰撞约束，则舍弃；若满足碰撞约束且满足转角限制，则将作为新的树节点加入到随机树中；若满足碰撞约束但不满足转角限制，采用限制区域随机转向策略产生新的，若新的不满足碰撞约束，则舍弃；若新的满足碰撞约束则将作为新的树节点加入到随机树中；9)重复步骤 2)8)直到新的树节点与终点的距离小于设定的阈值，之后回溯树节点得到路径.初始化自适应概率采样获得Xrand确定与Xrand最近的节点Xnear是否满足碰撞约束将Xnew加入随机树，更新随机树Xnew到Xgoal距离小于预设距离回溯节点得到规划路径，结束舍弃Xnew节点否是否计算Xnear所受合力F根据RRT和APF算法扩展得到新节点Xnew动态步长策略得到步长是否满足转角约束利用限制区域随机转向策略重新选择Xnew是否满足碰撞约束是是是否否图 7 改进 RRT 算法流程图3仿真实验结果及分析本文利用 Python 语言，基于 Windows10 下的PyCharmCommunity(Edition2023.1)编写程序.分别在简单环境、密集障碍物环境以及狭长空间三种情况下对现有算法和改进 RRT 算法进行仿真对比分析.为了减少结果的随机性，在三种不同环境下分别运行不同算法各 100 次，取平均迭代次数、平均路径长度、平均规划时间、成功率作为路径规划的评价指标.另外，选用 2020 的矩形作为仿真地图，并在仿真地图中根据不同环境设置不同障碍物进行测试.84全 球 定 位 系 统第48卷3.1 参数设置考虑初始设置参数对实验结果的影响，采用不同的初始最大步长(0.5、1 和 1.5)和不同的最大迭代次数(2000、5000 和 10000)对约束条件下的改进 RRT算法和 APF-RRT 算法在狭长空间进行测试从而选取适合的初始参数.首先固定最大迭代次数为 10000，测试不同的初始最大步长对结果的影响(为了减少随机性，对不同算法分别运行 100 次取平均值)，结果如图 8 所示.(a)平均迭代次数迭代次数(b)平均路径长度路径长度(c)平均规划时间规划时间/%(d)成功率成功率/%3 5003 0002 5002 0001 5000.51.01.533.032.532.031.531.030.530.03.01.101.051.000.950.952.52.01.5初始最大步长0.51.01.5初始最大步长0.51.01.5初始最大步长0.51.01.5初始最大步长APF-RRT算法改进RRT算法APF-RRT算法改进RRT算法APF-RRT算法改进RRT算法APF-RRT算法改进RRT算法图 8 不同初始最大步长下算法的实验结果折线图结果表明，随着步长的增大，两种算法平均迭代次数和规划时间呈下降趋势，并且在步长为 0.5 时成功率有所下降，而平均路径长度则变化较小.因此，选用 1.5 作为初始最大步长能同时保证算法的成功率和效率，减少其对算法性能的影响.其次，固定初始最大步长为 1.5，测试不同的最大迭代次数对结果的影响，结果如图 9 所示.2 0005 00010 000最大迭代次数最大迭代次数2 0005 00010 000最大迭代次数最大迭代次数1 8001 6001 4001 200(a)平均迭代次数迭代次数(b)平均路径长度路径长度平均规划时间规划时间成功率33.032.532.031.531.030.530.0成功率-算法改进算法-算法改进算法APF-RRT算法改进RRT算法APF-RRT算法改进RRT算法APF-RRT算法改进RRT算法-算法改进算法-算法改进算法第4期张俊豪，等：基于改进 RRT 算法的狭长空间无人车辆路径规划85最大迭代次数最大迭代次数5 000最大迭代次数2 0005 00010 0002 00010 000最大迭代次数平均迭代次数迭代次数平均路径长度路径长度(c)平均规划时间规划时间/%(d)成功率2.01.11.00.90.80.70.61.81.61.41.21.0成功率/%APF-RRT算法改进RRT算法APF-RRT算法改进RRT算法-算法改进算法-算法改进算法-算法改进算法APF-RRT算法改进RRT算法APF-RRT算法改进RRT算法图 9 不同最大迭代次数下算法的实验结果折线图结果表明，当最大迭代次数为 2000 和 5000 时，两种算法的成功率较低，因此选用 10000 作为最大迭代次数来减少其对其算法性能影响.3.2 简单环境由图 10 可知，在简单环境下，传统的 APF-RRT算法得到路径质量较差，会出现路径贴合障碍物的情况发生，这在实际中是不允许的，而在约束条件下的APF-RRT 算法和改进 RRT 算法均生成了合理、安全的路径.由表 1 可知，在没有约束条件时，改进 RRT算法相较于 APF-RRT 算法在平均迭代次数、平均路径长度和平均规划时间方面分别降低了 34.99%、4.89%、40.67%；在有约束条件时，改进 RRT 算法相较于 APF-RRT 算法在在上述指标里分别降低了44.51%、2.23%、14.49%.(a)APF-RRT算法(b)改进RRT算法(c)约束条件下的APF-RRT算法(d)约束条件下的改进RRT算法20.017.5yx15.012.510.07.55.02.500 1 2 3 4 5 6 7 8 9 101112131415161718192020.017.5yx15.012.510.07.55.02.500 1 2 3 4 5 6 7 8 9 101112131415161718192020.017.5yx15.012.510.07.55.02.500 1 2 3 4 5 6 7 8 9 101112131415161718192020.017.5yx15.012.510.07.55.02.500 1 2 3 4 5 6 7 8 9 1011121314151617181920图 10 简单环境下不同算法所得路径图86全 球 定 位 系 统第48卷表 1 简单环境下不同算法实验结果数据算法平均迭代次数平均路径长度平均规划时间/s成功率/%APF-RRT120.6429.28510.2063100改进RRT78.4227.85290.1224100约束条件下APF-RRT373.0529.14820.4305100约束条件下改进RRT207.0228.49960.36811003.3 复杂障碍物环境如图 11 所示，在复杂障碍物的情况下，传统的APF-RRT 算法依然产生了贴合障碍物的情况.由表 2可知，在没有约束条件时，改进 RRT 算法相较于APF-RRT 算法在平均迭代次数、平均路径长度和平均规划时间方面分别降低了 16.13%、4.05%、2.72%；在有约束条件时，改进 RRT 算法相较于 APF-RRT 算法在在上述指标里分别降低了 11.99%、5.09%、0.85%.20.017.5yx15.012.510.07.55.02.500 1 2 3 4 5 6 7 8 9 101112131415161718192020.017.5yx15.012.510.07.55.02.500 1 2 3 4 5 6 7 8 9 101112131415161718192020.017.5yx15.012.510.07.55.02.500 1 2 3 4 5 6 7 8 9 101112131415161718192020.017.5yx15.012.510.07.55.02.500 1 2 3 4 5 6 7 8 9 1011121314151617181920(a)APF-RRT算法(b)改进RRT算法(c)约束条件下的APF-RRT算法(d)约束条件下的改进RRT算法图 11 复杂障碍物环境下不同算法所得路径图表 2 复杂障碍物环境下不同算法实验结果数据算法平均迭代次数平均路径长度平均规划时间/s成功率/%APF-RRT145.6529.20500.2501100改进RRT122.1528.02200.2433100约束条件下APF-RRT542.8530.42561.5243100约束条件下改进RRT477.7828.87731.51131003.4 狭长空间在狭长空间中，改进 RRT 算法能够在自适应目标概率采样策略和动态步长策略下快速通过狭长区域，提高了规划效率.首先由图 12 可知，在增加了约束条件后，路径质量得到明显提升，并且减少了路径贴合障碍物的情况.由表 3 可知，在没有约束条件时，改进 RRT 算法相较于 APF-RRT 算法在平均迭代次数、平均路径长度方面分别降低了 35.73%、0.1%；在有约束条件时，改进 RRT 算法相较于 APF-RRT 算法在上述指标分别降低了 33.09%、0.06%，另外在平均规划时间方面也降低了 6.44%.第4期张俊豪，等：基于改进 RRT 算法的狭长空间无人车辆路径规划8720.017.5yx15.012.510.07.55.02.500 1 2 3 4 5 6 7 8 9 101112131415161718192020.017.5yx15.012.510.07.55.02.500 1 2 3 4 5 6 7 8 9 101112131415161718192020.017.5yx15.012.510.07.55.02.500 1 2 3 4 5 6 7 8 9 101112131415161718192020.017.5yx15.012.510.07.55.02.500 1 2 3 4 5 6 7 8 9 1011121314151617181920(a)APF-RRT算法(b)改进RRT算法(c)约束条件下的APF-RRT算法(d)约束条件下的改进RRT算法图 12 狭长空间下不同算法所得路径图表 3 狭长空间下不同算法实验结果数据算法平均迭代次数平均路径长度平均规划时间/s成功率/%APF-RRT981.3529.64270.1834100改进RRT630.7129.61320.2031100约束条件下APF-RRT1761.9531.75871.5571100约束条件下改进RRT1178.9331.73811.4569100当空间更加狭窄的时候，改进 RRT 算法更能体现其优势，如图 13 所示.20.017.5yx15.012.510.07.55.02.500 1 2 3 4 5 6 7 8 9 101112131415161718192020.017.5yx15.012.510.07.55.02.500 1 2 3 4 5 6 7 8 9 1011121314151617181920(a)约束条件下的APF-RRT算法(b)约束条件下的改进RRT算法图 13 狭长空间(极端狭窄)下不同算法所得路径图88全 球 定 位 系 统第48卷由表 4 可知，在约束条件下，RRT 和传统 APF-RRT 算法的规划成功率极低，其中 RRT 算法甚至在100 次规划无一次成功，而改进 RRT 算法则有着55%的成功率.这说明当随机树进入狭长空间时，自适应目标概率采样策略降低了采样概率，同时，动态步长策略降低采样步长，从而使得随机树能够更好地逃离狭长区域，完成路径规划.表 4 狭长空间(极端狭窄)下不同算法实验结果数据算法平均迭代次数平均路径长度平均规划时间/s成功率/%约束条件下RRT-0约束条件下APF-RRT5972.0033.04545.26002约束条件下改进RRT5708.8534.21229.8017554结束语为了解决 RRT 算法在狭长空间路径规划时可能出现的随机性过大、迭代次数较大的问题，本文提出了改进 RRT 算法，其中自适应目标概率采样策略和动态步长策略有效改善了在障碍物复杂或狭长空间中随机树容易陷入局部困境的问题，提高了规划效率.尤其在狭长空间的情况下，自适应目标概率采样策略和动态步长策略能够很好地引导随机树逃离障碍物区域，使得随机树快速到达终点附近.另外，本文还考虑了实际情况中的路径约束，对路径进行了碰撞约束和转角约束，并针对转角约束会导致迭代次数激增的问题提出了一种限制区域内随机转向的策略，这种策略能够有效降低迭代次数，提高规划速度.最后，通过仿真实验，验证了改进 RRT 算法在简单环境、复杂障碍物环境、狭长空间中应用的有效性.在狭长空间中，改进 RRT 算法在约束条件下相较于传统 APF-RRT 算法迭代次数降低了 33.09%，路径长度减少了 0.06%，规划时间减少了 6.44%，另外在极端狭窄的情况下，改进 RRT 算法相较于传统 APF-RRT 算法规划成功率从 2%提高到了 55%，提升效果十分明显.此外在简单环境和复杂障碍物环境下该算法均有提升.参考文献 王鹤静,王丽娜.机器人路径规划算法综述 J/OL.桂林理工大学学报,2023,43(1):137-147.1KARAMAN S,FRAZZOLI E.Sampling-based algorithms2foroptimalmotionplanningJ.Theinternationaljournalofroboticsresearch,2011,30(7):846-894.DOI:10.1109/ICRA.2014.6907642彭君.改进 RRT 算法在移动机器人路径规划中的应用研究 D.南京:南京邮电大学,2022.3ZUCKERM,KUFFNERJ,BRANICKYMS.MultipartiteRRTsforrapidreplanningindynamicenvironmentsC/IEEEInternationalConferenceonRoboticsandAutomation,2007:1603-1609.DOI:10.1109/ROBOT.2007.3635534OTTEMW,FRAZZOLIE.RRTX:Asymptoticallyoptimalsingle-querysampling-based motion planning with quickreplanningJ.Theinternationaljournalofroboticsresearch,2016,35(7):797-822.DOI:10.1177/02783649155946795YANG Y,ZHANG L,GUO R H,et al.Path planning ofmobilerobotbasedonimprovedRRTalgorithmC/ChineseAutomationCongress(CAC),2019:4741-4746.DOI:10.1109/CAC48633.2019.89964156QIJ,YANGH,SUNHX.MOD-RRT*:asampling-basedalgorithmforrobotpathplanningindynamicenvironmentJ.IEEE transactions on industrial electronics,2020,68(8):7244-7251.DOI:10.1109/TIE.2020.29987407WANGXY,LIXJ,GUANY,etal.BidirectionalpotentialguidedRRT*formotionplanningJ.IEEEaccess,2019(7):95046-95057.DOI:10.1109/ACCESS.2019.29288468WUZP,MENGZ,ZHAOWL,etal.Fast-RRT:aRRT-based optimal path finding methodJ.Applied sciences,2021,11(24):11777.DOI:10.3390/app1124117779WANGJK,LIBP,MENGMQH.KinematicconstrainedBi-directional RRT with efficient branch pruning for robotpathplanningJ.Expertsystemswithapplications,2021(170):114541.DOI:10.1016/j.eswa.2020.11454110LIYJ,WEIW,GAOY,etal.PQ-RRT*:animprovedpathplanningalgorithmformobilerobotsJ.Expertsystemswithapplications,2020(152):113425.DOI:10.1016/j.eswa.2020.11342511YUANCG,LIUGF,ZHANGWG,etal.AnefficientRRTcachemethodindynamicenvironmentsforpathplanningJ.Roboticsandautonomoussystems,2020(131):103595.DOI:10.1016/j.robot.2020.10359512田小壮,石辉,刘家辛,等.复杂环境下无人机智能巡检轨迹规划方法研究 J.电子设计工程,2021,29(20):77-81.13董敏,陈铁桩,杨浩.基于改进RRT算法的无人车路径规划仿真研究 J.计算机仿真,2019,36(11):96-100.14张兰勇,韩宇.基于改进的RRT*算法的AUV集群路径规划研究 J.中国舰船研究,2023,18(1):43-51.15李犇,褚伟.基于改进RRT与人工势场法的机器人路径规16第4期张俊豪，等：基于改进 RRT 算法的狭长空间无人车辆路径规划89划 C/中国生物医学工程学会血液疗法与工程分会第七届学术大会暨 UBIO 疗法专题研讨会,2021.王海群,王水满,张怡,等.未知环境的移动机器人路径规划研究 J.机械设计与制造,2021,368(10):233-235,240.17作者简介张俊豪(2001)，男，硕士研究生，研究方向为导航感知与路径规划.潘树国(1975)，男，博士，教授，研究方向为高精度GNSS卫星定位、智能体环境感知与自主导航、多源融合泛在智能导航定位、高精度动态定位检定与溯源.高旺(1989)，男，博士，副教授，研究方向为多源融合高精度导航定位.Path planning of unmanned vehicles in narrow and long space based onimproved RRT algorithmZHANGJunhao，PANShuguo，GAOWang，GUOPeng，WANGPing，HUPeng(Southeast University School of Instrument Science and Engineering,Nanjing 210096,China)Abstract：A path planning algorithm based on improved rapidly-exploring random trees(RRT)isproposedforthepathplanningsystemofunmannedvehiclesinnarrowandlongspace,whichsolvestheproblemsoflargerandomnessandlackofsafetyofthetraditionalRRTalgorithm.ThealgorithmimprovesthetraditionalRRTalgorithmbyaddingadaptivetargetprobabilitysamplingstrategyanddynamicstepsizestrategy.Atthesametime,consideringthedynamicsconstraintsofdriverlessvehiclesintheactualsituation,thealgorithmaddsvehiclecollisionconstraintsandpathangleconstraints,andproposesarandomturningstrategywithintherestrictedareatosolvetheproblemthattheangleconstraintswillleadtothemultiplicationofiterations,andapathwithhighersafetyisfinallyobtained.Theperformanceoftheproposedalgorithmiscomparedwithexistingalgorithmsbycomputersimulation.ComparedwiththetraditionalRRTalgorithmguidedbyartificialpotentialfieldinnarrowandlongspace,theiterationtimes,planningtimeandpathlengthoftheproposedalgorithmarereducedby33.09%,6.44%and0.06%,andtheplanningabilityoftheproposedalgorithmisimprovedinbothsimpleenvironmentanddenseobstacleenvironment.Theproposedalgorithmhashigherplanningefficiencyandfeweriteration.Keywords：rapidly-exploringrandomtrees(RRT);adaptivetargetprobabilitysampling;dynamicstep;pathconstraint;randomturnstrategy90全 球 定 位 系 统第48卷