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

针对带启发式的快速扩展随机树（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^*的基础上,提出一种基于采样空间自调整的渐进最优快速扩展随机树（AS-RRT^*）无人机（UAV）航迹规划算法。该算法可以自适应调整采样空间,进而引导树更为高效地生长,而这些主要通过有偏采样、节点筛选和节点学习这三种策略来实现。首先,在采样空间中定义向光和背光区域来进行有偏采样,而向光和背光区域的概率权重由当前扩展失败率决定,从而保证算法在搜索初始航迹时同时具有探索性和方向性;然后,在完成初始航迹的搜索后,算法就开始周期性地筛选节点,高质量的节点作为学习样本来产生新的抽样分布,质量最低的节点在算法达到最大节点数量后被新节点替代。在多种不同类型的环境下进行了对比仿真实验,结果表明所提算法在一定程度上改善了采样算法固有的随机性,而且相较于传统的RRT^*算法,该算法在相同环境里使用了更少的寻路时间,在相同时间里生成了更低代价的航迹,且在三维空间里的改进更为明显。     

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

针对RRT^*算法速度较慢问题,提出一种快速收敛至最优路径的最优双向快速扩展随机树(Optimal Bidirectional Rapidly-exploring Random Trees,Obi-RRT)算法。Obi-RRT使用改进的RRT-Connect算法快速得到较低成本路径,通过路径修剪得到关键点,围绕关键点提出三种采样空间并进行采样,通过不断更新关键点从而得到最优或接近最优的路径。平面和机械臂关节空间下的仿真实验表明,Obi-RRT算法运行时间仅为RRT^*算法的十分之一,并且路径成本更低。     

基于改进蚁群算法的机器人路径规划研究

机器人自主移动导航是近年来研究的热点.针对蚁群优化(ACO)算法存在收敛速度慢以及易陷入局部最优的问题,提出了一种改进的ACO算法来解决机器人路径规划问题.上述算法将改进的人工势场(APF)算法和蚁群算法相结合,采用改进APF算法进行初始地图规划,减少了ACO算法初始规划的盲目性.算法利用A*算法的评估函数以及路径转折角度来改进启发函数,引入启发信息递增函数,免于局部最优的同时保证收敛速度.改进算法的信息素更新机制和路径评价函数,提高了算法的全局最优性,使得到的路径更符合实际需求.通过改进该算法的信息素更新机制和路径评价函数,提高了算法的全局最优性,得到的路径更符合实际需求.仿真结果表明,改进算法能提升收敛速度和最优解.     

基于随机游走的多目标A*算法的改进

针对基于降维技术改进的多目标A^*（NAMOA_dr^*）算法中存在的高原搜索现象,结合蒙特卡罗随机游走策略提出了一种基于随机游走的多目标A^*（RWNAMOA_dr^*）算法,其基本思想是当NAMOA_dr^*算法陷入高原搜索时,利用随机游走策略及时找到一个出口（具有被上次扩展标签的启发值非支配的启发值的标签）逃离该高原搜索。针对NAMOA_dr^*算法何时陷入高原搜索的问题,提出了一种检测高原搜索的方法,即当连续扩展m次标签的启发值都被上一次扩展的标签的启发值支配时则认为NAMOA_dr^*算法陷入了高原搜索。使用多目标搜索算法的标准测试平台——随机网格进行了实验。实验结果表明RWNAMOA_dr^*算法比NAMOA_dr^*算法的运行时间平均减少了50.69%,占用的空间平均减少了约10%,能够为现实生活中加速多目标路径搜索提供理论支撑。     

移动机器人RRT算法改进研究

目前,机器人路径规划常用算法有避障(Bug)算法、概率路线图(PRM)算法、快速搜索随机树(RRT)算法、蚁群算法、人工势场法等,其中RRT算法在路径规划中应用最广。针对RRT算法存在随机性强、偏差大、路径不一定最优、收敛速度慢等缺点,对RRT算法进行改进,引导随机树向目标点生长,借助人工势场的引力思想,并加入自适应策略,通过机器人与目标点位置、速度和加速度的不断变化来改变步长大小,使机器人快速到达目标点。实验结果表明,通过自适应RRT算法可以提高算法收敛性,缩短了算法时间,可以有效应用在移动机器人系统上,提高移动机器人的工作效率。     

室内场景下应用拓扑结构的高效路径规划算法

针对基于随机采样的路径规划算法效率低且采样具有随机性的问题,提出一种应用拓扑结构的高效路径规划算法ATIRRT^*。通过引入拓扑节点代替STIRRT*算法中Harris角点检测算法得到的特征点进行采样,给出基于阈值的自适应选择方法来消除路径骨架上提取的冗余特征点,利用该阈值得到的拓扑节点可以使随机树的扩展更具方向性,从而减少寻找初始路径的时间和代价。根据非单一父节点的连接方式加强交叉支路上的拓扑节点间的联系,通过节点扩充策略增加相邻拓扑节点间的节点数量以加快优化算法的收敛。在此基础上定义相关约束条件将初始路径分段并进行逐段优化,以提高优化算法的效率。在常规环境、狭长空间和仿真的室内环境3种类型地图上的仿真结果表明,相较于STIRRT^*算法,改进算法在规划路径长度上平均减少8%,在规划时间上平均降低10%,可快速地找到更优的初始路径,同时在优化过程中减少了无用的探索空间,提高了搜索效率。     

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

RRT~*算法在路径规划过程中确保了其概率完备性和渐进最优性,但仍存在收敛速度慢且产生大而密集的采样空间等问题。为此,在RRT~*的基础上提出一种新的离线路径规划算法。在开始采样前快速瞄准目标区域,生成包含起始点与目标点的有界连通性区域。采用人工势场法优化采样过程,减少计算量,在势场合力的作用下有界区域内执行目标偏差采样,调整采样区域,在较短时间内生成较优路径。实验结果表明,当生成的路径成本相同时,该算法所需的迭代次数和执行时间远小于RRT~*算法,算法效率更高。     

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

为了解决快速扩展随机树(R RT)在障碍物密集、通道狭窄的环境中收敛速度缓慢、采样节点密集、路径曲折复杂等问题,围绕RRT的一种常见的变体算法RRT*,设计了一种由人工势场(APF)引导RRT*进行路径规划的方法.首先,使用涡流约束向外发散的斥力场,沿着切向梯度方向形成涡流场,并利用涡流人工势场(VAPF)在RRT*偏...     

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

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

基于改进A*算法的移动机器人路径规划

为了解决较大场景下A^*寻路算法存在的内存开销大、计算时间长等问题,本文在A^*算法的基础上,结合跳点搜索算法,提出一种改进的A^*算法．该算法通过筛选跳点进行扩展,直到生成最终路径,扩展过程中使用跳点代替A^*算法中大量可能被添加到OpenList和ClosedList的不必要节点,从而减少计算量．为了验证改进A^*算法的有效性,分别在不同尺寸的2维栅格地图中进行仿真,仿真结果表明,相比A^*算法,改进A^*算法在寻路过程中扩展更少的节点,寻路速度更快,且加速效果随环境地图的增大更加明显．最后将改进A^*算法应用于移动机器人Turtlebot2进行对比实验．实验结果表明,在生成相同路径的基础上,改进A^*算法的寻路速度较A^*算法提高了约200%,能够满足移动机器人路径规划的要求．     

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

传统的A^*算法在无人车路径规划中存在规划时间较长和搜索范围较大的缺点。综合分析A^*算法的计算流程后,从四个方面对A^*算法进行改进：1）目标性拓展,即根据待扩展节点和目标节点的相对位置来有目标性地选择不同的象限进行节点拓展;2）目标可见性判断,即判断待扩展节点与目标点之间有无障碍物,若无障碍物则跳出A^*算法的探索过程,以此减少多余的搜索;3）改变A^*算法的启发函数,即增加待扩展节点的n辈父节点到目标点的代价估计,以此减少到目标点的代价估计的局部最优情况;4）改变扩展节点的选取方略,即改变传统的最小化启发函数来选择扩展节点的方式,通过引入模拟退火法来优化扩展节点的选择方式,使得搜索过程尽可能向靠近目标点的方向进行。最后通过Matlab仿真实验结果表明,在模拟的地图环境下,提出的改进A^*算法在运行时间上减少67.06%,经历的栅格数减少73.53%,优化路径长度浮动范围在±0.6%。     

多路口环境下RRT的最优路径规划

针对于多路口环境下RRT的搜索时间长,搜索范围广和路径不平整的问题。提出一种基于路标引导和增长采样区域的混合策略来引导RRT算法向目标搜索。将对地图做预处理,处理掉较小的障碍物,尽可能保存大障碍物,得到预处理地图;在新地图上路口区域设置路标点,路标点的可视区域的组合要覆盖整个地图,根据其在新地图上的连通区域,通过寻找出一组从起点到终点的最优路标点组合,以相邻两路标之间构建移动增长采样区域来引导RRT算法快速向目标搜索;用树枝修剪和二次贝塞尔曲线拟合生成光滑路径。通过仿真实验验证了算法的有效性、合理性和正确性。     

融合安全A*算法与动态窗口法的机器人路径规划

A^*算法通过启发信息指引搜索方向,被广泛应用于移动机器人的路径规划,但其规划出的搜索路径存在冗余节点且与障碍物相近,无法满足动态避障需求。对标准A^*算法进行改进,设计安全A^*算法并融合动态窗口法进行路径规划。定义安全距离因子引入A^*算法的启发函数中,提高算法规划路径的安全性,同时采用平面结构法对算法规划得到的路径进行优化,根据相邻节点与障碍物之间的位置关系判断该相邻节点间是否存在障碍物,由此减少路径拐点数,提高路径平滑度。由于当移动机器人处于未知环境时,仅靠A^*算法不能避开障碍物到达目标点,因此借助动态窗口法的局部避障功能。通过安全A^*算法规划全局最优路径节点坐标,设计融合子函数改进动态窗口法的评价函数,解决动态窗口法易陷入局部最优的问题。实验结果表明,在复杂环境中,该方法通过融合安全A^*算法和动态窗口法,能够确保在安全路径基础上实时随机避障,使机器人安全到达终点。     

多方向无人水面艇路径规划算法

针对海洋环境下无人水面艇路径（USV）规划安全性与平滑性问题,提出一种多方向A^*路径规划算法以获得全局最优路径。首先,结合电子海图生成栅格化环境信息,并根据安全航行距离约束建立USV安全区域模型,在传统A^*算法基础上设计一种带安全距离约束的A^*启发函数来保证生成的路径节点的安全;其次,改进传统A^*算法的八方向搜索模式,提出一种多方向搜索模式来调整生成路径中的冗余点与拐点;最后,采用路径平滑算法对路径拐点进行平滑处理以获得满足实际航行要求的连续平滑路径。在仿真实验中,改进A^*算法规划的路径距离为7 043 m,相较于Dijkstra算法、传统A^*四方向搜索算法和传统A^*八方向搜索算法分别降低了9.7%、26.6%和7.9%。仿真结果表明改进后的多方向A^*搜索算法能够有效减小路径距离,更适用于USV路径规划问题。     

多方向无人水面艇路径规划算法

针对海洋环境下无人水面艇路径（USV）规划安全性与平滑性问题，提出一种多方向A^*路径规划算法以获得全局最优路径。首先，结合电子海图生成栅格化环境信息，并根据安全航行距离约束建立USV安全区域模型，在传统A^*算法基础上设计一种带安全距离约束的A^*启发函数来保证生成的路径节点的安全；其次，改进传统A^*算法的八方向搜索模式，提出一种多方向搜索模式来调整生成路径中的冗余点与拐点；最后，采用路径平滑算法对路径拐点进行平滑处理以获得满足实际航行要求的连续平滑路径。在仿真实验中，改进A^*算法规划的路径距离为7 043 m，相较于Dijkstra算法、传统A^*四方向搜索算法和传统A^*八方向搜索算法分别降低了9.7%、26.6%和7.9%。仿真结果表明改进后的多方向A^*搜索算法能够有效减小路径距离，更适用于USV路径规划问题。