摘要：针对快速扩展随机树（RRT）算法在智能轮椅路径规划中存在搜索目的性差、随机性大、搜索时间长、节点数过多、改进算法迭代次数多的问题进行研究，提出了限制RRT采样区域的路径规划算法，无需多次迭代，减少计算量。在采样的范围上，设置椭圆区域采样，对采样的范围加以限制，减少无用的采样点；在采样策略上，使用了目标偏置采样，提高采样的目的性；在步长扩展上，使用了自适应步长扩展策略，使得可以朝着目标点所在的方向更加快速地扩展；加入贪心算法的思想对路径长度和过多的路径节点进行优化，同时减少迭代次数，从而减少计算量。用MATLAB进行仿真，结果证明，相比RRT、RRT*、IRRT*算法，所提的限制RRT采样区域的智能轮椅路径规划算法在时间上分别减少了82%、92.25%、94.69%，在路径长度上分别减少了23.12%、10.01%、5.21%。

　　关键词：快速扩展随机树；路径规划；智能轮椅；椭圆区域采样

　　0引言

　　我国人口基数大，残疾人和行动不便的老人数量众多。因此，智能轮椅的发展十分必要。本文作者实验室研制的智能轮椅如图1所示。对于轮椅的使用者来说，主要的需求是辅助出行，自主驾驶和导航自然成为研究的重点；路径规划又是上述问题的核心问题之一，因此，对路径规划进行研究十分有必要。对路径规划进行研究的目的不仅仅是要提高路径规划的效率，减少路径的节点来改善用户使用体验也相当重要。

　　路径规划指的是在工作空间中规划出一条无碰撞的路径。传统的路径规划主要有以A*和Dijstra为代表的栅格图路径规划算法，以快速扩展随机树（Rapidly-exploring Random Tree，RRT）和概率图（PRM）为代表的基于采样的路径规划方法，因为RRT算法在高维路径规划中表现良好，且无需对障碍物做出准确的描述而受到广泛关注。Karaman等在RRT算法的基础上进行了改进，提出了RRT*算法，增加了重选父节点和重布线的操作，以渐近最优性受到了该领域专家、学者的广泛关注。LAVALLE和KUFFNER提出了双向扩展的RRT-connect算法，从起点和终点同时初始化两棵随机树交替扩展生长，该算法提高了运行的效率、节约了运算时间，但是在一定程度上增加了路径的代价，且仍然存在随机性过大、无用节点过多等问题；Gammell等一改盲目的随机采样方式，通过路径的长度和起始点的距离构建椭球来进行采样点选择，从而缩小采样范围，进而缩短时间。但是在生成第一条路径之前，其仍然会存在目的性差，路径规划效率低的问题。

　　在国内的研究中，刘文倩等在使用IRRT*算法对无人机路径规划时，加入了人工势场法来增加路径探索的目的性；胡兵等在对AGV（Automated Guided Vehi⁃cle）路径规划进行研究时，使用了双向扩展随机树算法与自适应目标引力思想来提高效率，但节点数仍较多；程满等在进行AGV路径规划时，在采样阶段没用正态分布代替随机取样；王稷尧等提出了一种结合人工势场法思想的改进RRT算法，提出了改进后的增益复合选点函数来生成新的节点，减少了无用节点的生成，节约了时间；卢宝勇等[17]提出了一种BOIT-RRT*算法，引入了目标偏置和直连检测的双向生长策略加快收敛策略。上述算法为了使路径的长度更短，需要进行多次迭代使得路径规划时间更长，效率较低。

　　基于以上问题，本文提出改进RRT算法，在采样时将采样的范围限制在椭圆之内，减少无用节点的生成，减少计算量；同时使用目标偏置法在采样时将目标点加入采样点，使得可以朝着目标点所在的方向生成部分新节点，提高采样的目的性；在扩展新节点时，使用自适应步长扩展来向目标点所在的方向更加快速地扩展，减少路径规划的时间；最后在计算出初始路径之后加入贪心算法的思想来进行优化，减少迭代的次数，缩短路径的距离的同时减少路径的节点。

　　1问题描述和传统RRT算法

　　1.1路径规划问题描述

　　设X为路径规划问题的工作空间，其中，xobs为障碍物空间，xfree为无障碍空间，且满足xfree=X/xobs，起点xinit∈xfree，目标点xgoal∈xfree；路径规划是求在满足约束条件的情况下路径代价函数c(σ)为最小值的路径。其中约束条件是路径的起点c(0)为x start，终点c(1)为xgoal，路径上的任意位置s，其对应的状态σ(s)需满足在自由空间xfree中。径为如式（1）所示。

　　1.2 RRT算法

　　RRT算法作为一种基于全局随机采样的路径规划算法。如果在自由空间内存在可行路径，则RRT算法的概率完备性可以保证找到可行路径。但是因为随机树生长的随机性，规划出的路径可能不是最优路径。RRT算法的流程为，以初始节点为根节点xinit，每次随机采样生成x rand，选择树上最近的节点生成x nearest，在无障碍物的情况下，在这个方向上扩展固定步长θ,生成x new，完成节点扩展；当有障碍物的时候放弃此次扩展。重复上面的步骤，直到x new和终点的距离小于设置的阈值，完成路径规划。

　　如图2所示，传统的RRT算法中是全局随机采样，会探索到整个空间，毫无目的性，同时也会在很多无用的空间和节点上浪费计算量，使其效率低下。同时每进行完一次固定步长的扩展都会进行重新采样，增加计算量，从而导致规划时间过长，效率低下。而且规划出的路径会出现冗余节点过多，导致路径更长等问题。

　　2改进RRT算法

　　针对以上关于RRT算法的不足，从采样区域、采样策略、扩展步长和路径优化4个方面进行改进，改进的RRT算法流程如图3所示。首先，通过节点拒绝策略将采样点控制在椭圆内，同时为了提高路径探索的目的性，利用目标偏置采样策略来控制采样点向目标点靠近；为了减少计算量，提高效率，使用自适应步长策略进行了改进；最后，在得到初始路径之后，使用贪心算法思想来删除冗余节点，减少路径长度，提高路径质量。

　　2.1限制区域采样

　　传统的RRT算法在采样范围的选择上采用全局采样的方式，这样容易使得采样点向目标点之外的方向偏移，从而使得规划的路径长度更长。根据椭圆的性质可知，椭圆外的点与两个焦点距离之和一定大于椭圆内点与两个焦点的距离之和。据此，本文提出了一种椭圆区域采样的方式，将采样的范围限制在椭圆内，如图4所示。若在这此椭圆内找不到路径，则扩大椭圆的范围，具体的操作步骤如下。

　　首先构造出一个椭圆，xinit和xgoal分别为路径的起始点，在椭圆内，其欧几里得距离为椭圆初始的长轴Cbest，短轴为Cmin，ka为条件系数，其公式如式（4）~（7）所示。其中，(x,y)为采样点的坐标，(x1,y1)为xinit和xgoal的中点坐标，若ffeasible大于1，则证明采样点在椭圆之外，拒绝加入x rand；反之，在椭圆内，加入x rand。最后，若在迭代一定的次数之后未找到初始路径，则增加ka的值；若增大到一定的值仍未找到，则路径规划失败；反之，路径规划完成。

　　2.2目标偏置采样

　　限制随机树的采样节点提高了效率，但是目的性仍然较弱，步长扩展时会向各个方向扩展从而导致更多无用的x new加入，使得随机树过于枝繁叶茂，主干难以生长，路径规划的效率较差。

　　因此，针对上面的问题，在采样的过程中将部分采样点设置为目标点，这样可以使得在扩展步长的过程中可以有目标性地扩展，提高效率。具体的操作：在算法开始时，设置一个阈值p，阈值的范围在（0，1）之间，当随机数小于设置的阈值时，在父节点和目标点的连线上随机取一点，若该值大于选取的阈值，则在自由空间内随机选取一点；当环境越复杂的时候，阈值越小，当环境障碍物越少时，阈值越大，即：

　　这种方式不仅可以增加算法的目标导向性，使得x new有方向性的扩展，同时保留了算法的随机性，使得随机树不是一味在这个方向上扩展，在遇到障碍物的时候，在无障碍空间内探索，绕过障碍，以免陷入局部最小值。

　　2.3自适应步长扩展

　　当x rand和x nearest之间没有障碍物的情况下，随机树会在这个方向上按照固定步长的方式进行扩展生成，每一次扩展步长后都重新采样，并计算与父节点的距离，进行重选父节点的操作，增加了算法的计算量和计算的时间。在本文的算法中，为了加快扩展速度，节约运算时间，采用了自适应步长的方式进行扩展。

　　在扩展步长时，若父节点和x rand之间的连线与父节点没有障碍物，且和xgoal之间的连线的夹角大于90°,则继续进行扩展并进行碰撞检测；若小于90°,则重新采样并进行碰撞检测。知道将xgoal加入路径完成路径规划。

　　2.4贪心算法优化路径

　　以上对RRT算法的改进，提高了路径规划的效率和目的性，可以更快地找到初始路径。但是路径的长度和节点的数量并没有改善，因此，引入贪心算法的思想对此进行优化。贪心算法会在求解时，将目前的结果视为之前状况的最优解，并以此为基础，进行最优化求解。贪心算法优化路径如图5所示。

　　在本算法中，当已经找到初始路径之后，获得了从初始点到最终点的一系列无碰撞路径点合集path.pos，在此基础上寻找可行更短的可行路径。具体步骤如下：

　　（1）首先将上述路径的终点加入最优路径path.new中；

　　（2）判断初始点和最终点之间是否有碰撞，若无碰撞，则将此点加入最优路径节点path.new中；若有碰撞，则判断下一个路径节点和最终点有无碰撞，继续循环，直到找到下一个与终点无碰撞的节点，将其加入最优路径path.new中；

　　（3）将最新与终点无碰撞的节点设为新的终点，初始节点为1，继续循环，直到终点与初始节点重合，结束循环，找到最优路径合集path.new，即为最终路径，完成路径规划。

　　伪代码如表1所示。

　　3结果与讨论

　　3.1算法仿真

　　本文实验仿真环境为AMD R7-5800H Windows 11，使用MATLAB 2021（b）分别对RRT算法、RRT*算法、IRRT*算法和本文改进的RRT算法进行仿真。图6所示为800 pixel×800 pixel的二维空间，仿真设置的起点为（200，200），终点为（550，650），固定步长step为100，阈值为100。在改进的RRT算法中，目标偏置概率P设置为0.5，ka设置为0.5。在RRT、RRT*算法和IRRT*算法中，最大节点数设置为2 000。

　　图中白色为无障碍自由空间，黑色为障碍物空间。算法需要在白色的无障碍空间内构造出一棵随机树，且不能与黑色障碍物有交点。基于采样的路径规划算法具有很强的随机性，因此，为了提高数据的准确性，每个算法都运行了50次。仿真过程中，“*”表示的是随机在扩展过程中的采样点x rand，蓝色表示规划出的路径。为了便于表示贪心算法对于路径优化的重要性，在图6（a）~（c）中蓝色表示最终路径，图6（d）中蓝色为初始路径，红色为贪心算法优化后的路径。

　　由图6可以看出，由于RRT*算法本身对全局的探索性，会在全局内进行探索，以至于会产生很多无用的x rand节点，这些节点的产生会导致计算量增大；同时，对于IRRT*算法来说，前期的采样方式接近于全局的采样，仍旧会产生很多无用的x rand来增加计算量。而改进的RRT算法在开始的时候就限制了x rand的生成，会减少一部分x rand的生成。

　　3.2结果

　　表2所示为二维路径规划中RRT、RRT*、IRRT*和改进RRT算法在同一地图中实验了50次的平均值，包括路径规划消耗时间、路径长度和节点数。可以见得，由于改进RRT算法在探索过程中增加了目的性并且在初始路径上直接优化不用重复探索路径，提出的限制RRT采样区域的路径规划算法相对于RRT、RRT*、IRRT*算法来说时间分别减少了82%、92.25%、94.69%，在路径长度上分别减少了23.12%、10.01%、5.21%。

　　4结束语

　　本文提出了一种限制RRT采样区域的路径规划算法，基于RRT算法做出了4点改进：首先通过将采样点限制在椭圆区域内减少无用采样点的生成；然后通过目标偏置策略将可以加入路径的节点向目标点偏移，提高路径探索的目的性；通过自适应步长策略减少计算量、加快初始路径生成的速度；在初始路径生成之后，加入贪心算法的思想来减少路径节点和路径长度，无需多次迭代，优化路径的同时提高效率。

　　改进算法在MATLAB进行了仿真，仿真结果表明，本文提出的算法相对于传统的RRT算法、RRT*算法和IRRT*算法可以有效地提高路径规划的速度、缩短路径的长度和节点数，提高路径规划的质量。

       参考文献：

　　[1]欧阳崛,陈刚,盛鑫军,等.基于梯度采样的轮椅机械臂局部路径规划算法[J].机电一体化,2022,28(Z1):3-12.

　　[2]黄辉,孙梦雪,舒展,等.智能轮椅、控制方法、电子设备及存储介质:CN115778695A[P].2023-03-14.

　　[3]喻九阳,张德安,戴耀南,等.基于改进B-GRRT~*算法的移动机器人路径规划[J].计算机科学,2023,50(S1):105-111.

　　[4]杨金铎,王林波,曾惜,等.自动化机器人轨迹跟踪与路径规划技术研究[J].自动化仪表,2022,43(7):40-45.

　　[5]潘世瑛.基于改进A*算法的AUV路径规划研究[J].装备制造技术,2022,(11):49-52.

　　[6]江韩,晁永生,周江林,等.改进RRT算法的机械臂路径规划[J].机械设计与制造,2023(12):288-292.

　　[7]赵盼,xxx,刘江,等.基于改进RRT~*算法的超冗余度机器人末端避障路径规划[J].航空制造技术,2023,66(4):90-95,110.

　　[8]KARAMAN S.Sampling-based algorithms for optimal motion planning[J].The International Journal of Robotics Research,2011,30(7):846-894.

　　[9]LAVALLE S M.Rapidly-Exploring Random Trees:A New Tool for Path Planning[J].Research Report,1999.

　　[10]杜传胜,高焕兵,侯宇翔,等.同根双向扩展的贪心RRT路径规划算法[J].计算机工程与应用,2023,59(21):312-318.

　　[11]GAMMELL J D,SRINIVASA S S,BAR-FOOT T D.Informed RRT*:optimal sampling-based path planning focused via di⁃rect sampling of an admissible ellipsoidal heuristic[C]//2014 IEEE/RSJ International Conference on Intelligent Robots and Systems,September 14-18,2014,Chicago,IL,USA.New York:IEEE,2997-3004.

　　[12]代军,xx明,李艳琴,等.基于改进Informed-RRT~*算法的机器人路径规划[J].河南理工大学学报(自然科学版),2022,41(4):95-100.

　　[13]刘文倩,单梁,张伟龙,等.复杂环境下基于改进Informed RRT的无人机路径规划算法[J].上海交通大学学报,2024,58(4):511-524.

　　[14]胡兵,向凤红,毛剑琳.基于改进RRT算法的AGV路径规划研究[J].软件导刊,2018,17(3):28-31.

　　[15]程满,杨光永,徐天奇,等.基于RRT改进算法的AGV路径规划[J].计算机与数字工程,2023,51(3):606-611.

　　[16]王稷尧,袁锋伟.一种改进的RRT路径规划算法[J].机电工程技术,2022,51(3):161-164+298.

　　[17]卢宝勇,顾寄南,王文波,等.BITO-RRT*全局路径规划算法研究[J/OL].机械科学与技术,1-9[2024-09-29].

　　[18]王怀震,高明,王建华,等.基于改进RRT~*-Connect算法的机械臂多场景运动规划[J].农业机械学报,2022,53(4):432-440.

　　[19]靳午煊,马向华,赵金良.改进Informed-RRT*的移动机器人路径规划算法研究[J].计算机工程与应用,2023,59(19):75-81.

　　[20]谭力珲.基于改进RRT算法的移动机器人路径规划及应用研究[D].重庆:重庆大学,2022.

　　[21]蔡立彪.空间椭球最短距离计算方法研究[D].广州:华南理工大学,2014.

　　[22]商德勇,汪俊杰,樊虎,等.基于RRT~*-DR算法的机械臂避障路径规划[J].计算机集成制造系统,2024,30(3):1149-1160.