目标偏置双向RRT*算法的机器人路径规划

针对RRT*和B-RRT*算法在较复杂环境下路径规划时,存在搜索时间长、采样效率低和规划路径曲折的问题,提出一种目标偏置双向快速扩展随机树算法——GBB-RRT*（goal biased bidirectional RRT*）。该算法每次迭代中两棵随机树都进行扩展,一次迭代能生成两个新节点,加快扩展速度。然后引入目标偏置策略来优化采样点的选取,使两棵随机树在一定概率下朝各自的目标点方向扩展。针对得到的规划路径,设计一种逆向寻优结合转角约束路径简化方法,结合B样条曲线生成光滑可执行路径。在仿真实验中将提出的算法与B-RRT*进行对比实验,结果表明所提算法搜索时间缩短40%左右、扩展节点减少10%左右,结合路径简化方法后路径长度缩短3%左右。     

基于B-RRT*FND算法的移动机器人路径规划

针对RRT*FN算法获取路径解的速度慢,且无法应用于动态环境等问题,提出固定节点数的动态双向渐近最优快速随机扩展树算法(bidrectional RRT* fix-node dynamic, B-RRT*FND),用于解决移动机器人在二维空间内快速实时获取无碰撞路径的问题.所提出算法基于RRT*FN算法,采用双向贪婪搜索方法加快路径搜索速度,解决单向RRT算法由于随机采样的盲目性造成的搜索速度慢、在狭窄环境下难以搜索到解的问题;利用固定节点算法在规划过程中不占用过多计算量的特点,在路径迭代优化过程中,实时更新地图信息,并对被破坏的原始路径进行修复重连,以完成算法的动态规划.将所提出算法与RRT、RRT*FN等算法在3种环境下进行对比仿真,验证结果表明,所提出算法在规划速度、路径解长度以及动态规划性能方面具有较好效果.     

涡流人工势场引导下的RRT*移动机器人路径规划

为了解决快速扩展随机树(RRT)在障碍物密集、通道狭窄的环境中收敛速度缓慢、采样节点密集、路径曲折复杂等问题,围绕RRT的一种常见的变体算法RRT*,设计了一种由人工势场(APF)引导RRT*进行路径规划的方法。首先,使用涡流约束向外发散的斥力场,沿着切向梯度方向形成涡流场,并利用涡流人工势场(VAPF)在RRT*偏向区域中引导采样节点进行偏向采样,以减少执行时间,加快收敛速度;同时,利用节点拒绝技术去除高成本节点和无效节点,生成节点更为集中的轨迹树,降低内存需求;最后,通过修剪路径中的多余节点,并利用涡流势场的特性对路径进行平滑处理,达到路径优化的效果。考虑到RRT类算法具有概率随机性,对RRT算法、改进RRT*算法和VAPF-RRT*算法分别进行了32次对比实验。仿真结果表明,提出的VAPFRRT*算法明显降低了迭代次数,以更少的采样节点和执行时间收敛到更短更平滑的路径,提高了内存利用率,加快了收敛速度。     

基于改进RRT*FN算法的机器人路径规划

针对固定节点数的渐近最优快速扩展随机数算法(RRT*FN)精度低、收敛到最优值速度慢等问题,提出一种改进的RRT*FN路径规划算法,并用于解决二维静态环境下的移动机器人全局路径规划问题.首先,改进算法使用与RRT*FN算法相同的均匀采样方法进行路径搜索,当搜索到一条初始路径时,在之后的路径规划中使用启发式采样方法.在之后的每次迭代中,改进算法在椭圆子集采样方法与路径点邻近区域采样方法中随机选择一种作为当前采样方法.然后,当树中的总节点数达到预设值时,对树中的叶子结点采用加权方法进行删除.通过给予采样区域内的叶子结点更高的权重,从而将采样区域外的叶子结点以更高概率删除,得以保留树中的高性能节点,以便提高算法性能.最后,通过仿真实验验证改进算法的有效性.     

一种基于改进RRT*的全局路径规划算法

针对传统RRT*全局路径规划算法在多障碍物复杂环境中搜索效率低、占用内存过大、搜索路径不平滑等问题,提出一种基于简化地图的区域采样RRT*算法(simplified map-based regional sampling RRT*, SMRS-RRT*).首先简化处理全局栅格地图,在此基础上寻找从起点到目标点的最优路径点集合,并将该路径作为引导路径通过智能采样因子进行扩大,得到智能采样区域;然后在智能采样区域中不断迭代搜索,得到一条从起点到目标点的代价小、无碰撞路径;最后结合最小转弯半径约束的路径修剪和基于B样条曲线的路径优化,生成一条路径平滑且曲率连续的优化路径,从而使移动机器人沿着该全局优化路径快速、平稳、安全地到达目标点.仿真实验表明,所提出算法能够有效提高传统RRT*搜索效率,加快收敛速度,降低内存消耗.     

基于改进渐进最优的双向快速扩展随机树的移动机器人路径规划算法

针对带启发式的快速扩展随机树（RRT-Connect）算法路径生成的随机性以及渐进最优的双向快速扩展随机树（B-RRT^*）算法收敛速度的缓慢性，提出了一种基于B-RRT^*改进的高效路径规划算法（EB-RRT^*）。首先引入一种智能采样函数，使随机树的扩展更具方向性，从而减少寻路时间，并提高路径的平滑性；其次在B-RRT^*算法的基础上，在EB-RRT^*算法中加入了一种快速扩展策略，使改进后的算法在自由空间中使用RRT-Connect算法的扩展方式进行快速扩展，而在障碍物空间则使用改进的渐进最优的快速扩展随机树（RRT^*）算法进行扩展，在提高扩展效率的同时避免算法陷入局部最优。将EB-RRT^*算法分别与快速扩展随机树（RRT）、RRT-Connect、RRT^*和B-RRT^*算法进行仿真对比，仿真结果表明，改进后的算法在路径规划效率及路径平滑性方面均明显优于其他算法；且相对于B-RRT^*算法，其在路径规划时间上降低了68.3%，在迭代次数上减少了48.6%。     

基于改进RRT算法的无人机三维避障规划

RRT算法由于其在复杂环境中有强大的随机搜索能力,在无人机避障规划中被广泛运用.为了提高无人机避障规划的效率,提出了一种基于预规划路径优化RRT算法的无人机三维避障规划算法.算法首先在障碍物膨胀规则和相交规则下生成预规划路径,然后将预规划路径看做成连续的质点组成,按一定的扩展树步长的比例从连续质点取点来确定搜索树的随机状态点,最后RRT算法在这些随机状态点的引导下进行搜索,生成避障规划路径.仿真结果表明,改进的RRT算法生成的预规划路径降低了障碍物搜索的时间和增强了搜索树扩展的方向性;预先确定的随机状态点使搜索树在扩展中具有方向性,可减少新生节点的个数和路径长度,进而提高了无人机避障路径规划的效率,使得最终生成避障路径的时间更优.     

基于改进RRT算法的UAV航迹规划与优化研究

分析步长、搜索次数对UAV航迹生成的影响,给出一种改进RRT算法。结合目标信息给出启发因子、优话采样节点选择方法、选取合适的启发概率等方法,解决了扩展树生长过程中随机性较大的问题,提高了全局搜索能力和搜索速度,同时考虑局部搜索精度。针对航迹随机化造成的航迹不够优化的问题,提出一种航迹迭代优化方法。仿真结果表明:该算法和优化方法具有较快的收敛速度和更短的搜索时间;迭代优化方法减少了冗余规划点,缩短了规划航迹,提高了航迹规划效率。     

基于A*引导域的RRT智能车辆路径规划算法

为了泛化RRT （快速搜索随机树）算法在智能车辆路径规划领域内的应用,解决该算法搜索效率低、最近邻搜索函数不合理等问题,本文提出了一种基于A*引导域的RRT路径规划算法.该算法将A*算法与RRT搜索算法进行有效地结合,利用由A*算法在低分辨率栅格图中生成的最短路径来构建引导域,以提升RRT算法的采样效率;同时在设计RRT算法的最近邻搜索函数时考虑车辆自身约束,以增强搜索树节点选择的合理性.通过仿真实验和实车测试,对该算法的优越性、有效性和实用性进行了验证.     

同根双向扩展的贪心RRT路径规划算法

针对传统RRT-Connect算法路径规划过程中随机性大、算法效率低、搜索时间长、搜索路径冗长等问题,提出一种同根双向扩展的贪心RRT路径规划算法。将由起点开始向终点进行扩展的方式改为由起点与终点连线的中间点同时向起点和终点进行双向扩展,同时在扩展节点时叠加引力场和极度贪心算法,使树快速向起点和终点的方向扩散,加速路径的生成。对生成的路径进行剪枝优化处理,删除路径中冗余的节点,缩短路径长度。在三种不同环境中对改进算法进行仿真对比实验,结果表明所提算法相关性能优于传统RRT-Connect算法及其相关衍生算法。将改进RRT-Connect算法应用在实际移动机器人中,进一步证明改进算法的实用性和有效性。     

基于动态变采样区域RRT的无人车路径规划

针对无人车传统RRT路径规划算法节点搜索盲目性、随机性以及路径曲折不连续等问题,提出一种动态变采样区域RRT路径规划算法(dynamic variable sampling area RRT, DVSA-RRT).首先,初始化地图信息,根据动态变采样区域公式划分采样空间,进而选择采样区域;在此基础上,利用基于安全距离的碰撞检测、概率目标偏置策略和多级步长扩展完成初始路径规划;最后,利用考虑最大转角约束的逆向寻优和3次B样条曲线对初始路径进行拟合优化.仿真结果表明,该算法相较于原始RRT算法在不同地图环境下的搜索时间和采样次数均降低50%以上,大大降低了节点搜索的盲目性和随机性,相较于其他算法搜索时间也减少30%以上,且优化后的路径平滑满足车辆运动动力学约束.     

基于改进RRT算法的智能车辆路径规划研究

针对快速搜索随机树(RRT)算法在路径规划中存在目标导向性差、收敛速度慢、路径拐点多的问题，提出了一种改进的RRT算法。改进算法采用渐近区域采样并融合偏向目标采样机制，有效防止随机采样点的反向搜索，提高对采样空间的利用率，保证了采样的方向性；用动态圆规则化处理车辆有效避免碰撞和通过狭窄区域，采用基于三角不等式的方法对路径冗余点进行修剪，在此基础上采用三次B样条线平滑的方法对路径优化。最后通过MATLAB仿真对比分析，证明了上述算法的有效性，并且搜索次数更少，用时更短，规划出的路径效果更优。     

针对包含狭窄通道复杂环境的高效RRT*△路径规划算法

针对RRT*算法在狭窄通道等复杂环境产生大量节点和收敛速度慢的问题,提出一种基于多种启发式策略和强化节点机制改进的高效RRT*路径规划算法(heuristic node enhancement informed RRT*,HNEI-RRT*).该算法首先采取组合启发式采样策略,快速找到初始路径之后在启发式子集内完成采样;同时提出启发式节点拒绝策略,拒绝不满足预设条件的节点参与后续扩展;其次,该算法提出强化节点机制,扩大节点蕴涵的信息,提高节点利用率.在各种障碍物分布和狭窄通道的复杂环境中的仿真结果表明,HNEI-RRT*算法的节点数量、收敛时间相比其他五类RRT*改进算法更少,验证了该算法能够节省内存花销的同时有效提高收敛速度.     

改进RRT*的室内机器人路径规划算法

路径规划在室内机器人的应用中有着无可比拟的作用。为了提高路径规划算法收敛的速度,综合时间消耗和路径质量方面考虑,针对RRT*（渐进最优快速扩展随机树）算法的局限性,提出一种改进的RRT*算法。该算法采用目的性的设置采样点代替原算法中的随机高斯采样和引进人工势场与避障策略结合的思想,设置目标偏向性,引导随机树生长方向,然后利用曼哈顿距离代替欧几里得距离作为代价估值函数,防止陷入极小值以及一定程度上减小算法时间损耗。实验表明,该方法可有效平衡算法收敛时间与最佳路径的可靠性。     

融合有向D*与RRT*的移动机器人路径规划算法

针对快速扩展随机树(RRT)算法在复杂障碍物和狭窄通道环境中收敛速度慢,冗余节点多的问题,提出了一种融合有向D*与RRT*的路径规划算法,用于改善移动机器人在二维环境下路径规划的性能.首先,算法根据初始路径确定关键点,以它为圆心形成采样子集,在之后的迭代中,按概率在圆形子集和全部状态中选择采样空间.然后,利用变距离重新布线,通过大半径重新布线减少冗余节点,再利用小半径重新布线对障碍物顶点和转弯处进行优化,达到缩短路径长度和平滑路径的目的 .仿真结果表明,融合改进算法比对照算法的路径长度缩短了4.30％,搜索时间减少了25.91％,路径总步数减少了50.26％,且可以适应存在连续小洞和狭窄通道的特殊环境.     

一种移动机器人路径规划新算法

快速搜索随机树（Rapidly-exploring random Tree Star,RRT*）算法在移动机器人实际应用中规划路径在转向部分存在较多的冗余转折点,导致移动机器人在移动转向过程中出现多次停顿与转向,为剔除规划路径中的冗余路径点,提高机器人移动流畅性,提出一种改进的 RRT*算法。算法将局部逆序试连法引入移动机器人路径规划,在确保RRT*算法概率完备性和渐进最优性的前提下,剔除规划路径中的冗余路径节点,使最终路径更加接近最短路径。通过MATLAB仿真实验证明,规划路径平均长度缩短4%,算法耗时缩短35%,改进后的RRT*算法能缩短规划路径且转向部分路径更加平滑。最后,使用改进后的RRT*算法在室内环境下进行移动机器人路径规划实验。实验结果表明：规划路径上无冗余路径点,且移动机器人沿路径移动流畅。     

基于改进RRT算法的无人车路径规划

针对无人车在复杂环境中进行全局路径规划时存在的盲目搜索、节点冗余、路径不光滑及不安全等问题,提出一种基于快速扩展随机树（Rapidly-Exploring Random Tree,RRT）的综合改进路径规划算法。首先引入目标动态概率采样策略和人工势场引导随机树扩展机制。其次根据汽车运动学模型,对规划的路径进行转角约束和碰撞检测,保证路径的安全性。然后引入Reeds-Sheep曲线用于直接与目标位姿进行连接,避免在终点处进行多余的位姿调整。最后对路径进行剪枝和平滑处理,得到一条更短更光滑的路径。在实验部分,针对不同仿真环境,以规划时间、路径长度和节点数目作为评价指标,对比了基本RRT算法、基本RRT*算法和本文算法的路径规划效果。实验结果显示本文算法在路径规划效率和路径质量上都具有一定优越性,规划的路径长度较优并且满足车辆运动学约束。     

移动机器人实时采样路径重规划

针对传统采样规划算法因随机性强,在动态环境中重规划时路径质量差,抖动严重,实时优化效果不明显等问题,提出了一种利用反向生长最优快速搜索随机树的实时采样重规划算法DRT-RRT*（Dynamic Real-Time RRT*）。引入基于三角不等式的剪枝策略对路径进行平滑处理以减少路径拐点;提出了组合采样策略和局部终点跳动策略,将优化目标由全局路径聚焦于机器人当前位置至最近路径拐点的局部路径段,实时对执行路径段进行修正,进而提高路径质量的稳定性;在路径重规划时仅对受影响的随机树枝进行修剪,并在随机树重新生长时引入了目标偏置采样策略,与组合采样策略共同作用,提高路径搜索速率和稳定程度;将DRT-RRT*与RRT*和增加了三角不等式剪枝策略的RRT*-Pruning进行仿真对比分析,实验结果验证了DRT-RRT*重规划的高效性和稳定性。     

基于改进的RRT*-connect算法机械臂路径规划

基于双向渐进最优的RRT*-connect算法,对高维的机械臂运动规划进行分析,从而使规划过程中的搜索路径更短,效率更高。将目标偏向策略引入采样过程,同时对采样点区域进行约束,保证每次采样都能朝着目标方向搜索,使得搜索路径更优。在此基础上,采用梯度下降法优化搜索出的路径,将整个路径做平滑处理,去除大角度转弯。利用Matlab对改进后的RRT*-connect算法进行仿真对比分析,从而证明该算法在各种复杂环境下都能保证搜索的概率完备性以及渐进最优性,并且搜索路径更短,用时更少。在ROS平台使用UR5机械臂进行仿真实验,验证该算法的实用性与有效性。     

动态环境下基于人工势场引导的RRT路径规划算法

现有的大多数动态RRT路径规划算法不能使规划的路径远离障碍物,这有可能导致机器人没有足够的避障时间。针对此问题,提出了一种利用人工势场引导快速扩展随机树向目标区域生长并远离障碍物的改进RRT算法APFG-RRT(artificial potential field guided RRT)。为了进一步加快算法的收敛速度、加速算法跳出局部极小值,引入了一种按自适应概率选择目标点作为采样点的策略;针对动态环境采用全局规划结合局部重新规划的方法以提高算法的实时性。仿真实验表明,相比于初始RRT和Goal-bias RRT,APFG-RRT的计算效率更高,内存需求更小,并且搜索到的路径能够有效地远离障碍物,提高了动态路径规划的成功率。