快速扩展随机树

摘要： 核退役机器人工作过程中,传统快速扩展随机树(Rapidly-exploring Random Tree,RRT)路径规划算法缺乏导向性,路径规划效率低,避障能力弱;为此,提出改进RRT路径规划算法,以提高作业效率和准确率。首先,引入目标偏置函数,并提出自适应步长,使RRT路径规划具有导向性,避免陷入局部最优;其次,采用启发式搜索思想,保留优于其父节点的随机搜索点为新节点;最后,修剪路径中的冗余节点,并采用贝塞尔曲线对路径进行平滑处理。在MATLAB平台上进行仿真,结果表明,改进RRT路径规划算法较传统RRT路径规划算法、RRT-connect路径规划算法效率更高,收敛性更强,可以很好地提高核退役机器人的避障能力。

摘要： 由于煤矸石分拣环境复杂,为了避免机器人与障碍物发生碰撞,提高分拣效率,对机器人进行路径规划十分必要。分析了煤矸石分拣系统原理,将煤矸石分拣机器人路径规划问题归结为在障碍物环境下规划出一条从给定起点到目标点的无碰撞路径,且需同时满足速度快、避免与障碍物碰撞2个约束条件。结合笛卡尔空间和关节空间的优点,提出一种在关节空间进行路径规划、在笛卡尔空间进行碰撞检测的煤矸石分拣机器人路径规划方案,该方案不需要对机器人进行运动学求逆,且可避免在关节空间中描述障碍物。针对RRT^(*)路径规划算法存在盲目性的问题,提出一种变概率的目标偏置策略,并将其引入RRT^(*)算法,得到G-RRT^(*)算法。变概率的目标偏置策略在无障碍物区域增大目标偏置概率值,以增强算法的目标导向性;而在障碍物区域减小目标偏置概率值,以保证算法的避障能力。G-RRT^(*)算法将变概率的目标偏置策略与RRT^(*)算法相结合,既保留了RRT^(*)算法路径长度渐进最优的特点,也提高了算法的目标导向性,可极大地提高路径规划效率。实验结果表明,与加入固定概率目标偏置策略的RRT-Connect算法和RRT算法相比,采用G-RRT^(*)算法得到的路径长度平均值最小,说明G-RRT^(*)算法更适用于煤矸石分拣机器人路径规划。

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

摘要： 由于快速扩展随机树(RRT)算法存在规划路径曲折、收敛较慢,且无法被智能车辆直接跟踪等问题。为克服此缺陷,本文在基本RRT算法基础上,加入目标偏向性策略和密集节点过滤,以此提高规划速度;在选择父节点时考虑车辆运动学约束并根据车辆位置动态确定扩展步长,最后对所得路径进行修剪,并使用三次B样条曲线进行平滑,生成一条平滑可被追踪的曲线。仿真实验表明,改进的RRT算法生成路径更加合理、平滑,且符合车辆运动学特性。

摘要： 针对未知水下环境下的自主水下航行器(autonomous underwater vehicle,AUV)目标搜索问题,传统方法搜索速度慢且以解决二维平面下搜索问题为主,本文提出了一种基于改进RRT(rapid-exploration random tree)的未知三维环境目标搜索算法。在搜索方面,分别建立了包括目标存在概率地图、不确定度地图、区域遍历度地图在内的实时地图并设定其更新规则,根据搜索目标建立决策函数;在局部规划方面,将滚动规划与改进RRT算法相结合,规划出到搜索决策点的路径。二者的结合,实现了AUV在三维空间下在线实时搜索。仿真表明,该算法具有较强的遍历能力,提高了三维空间下目标搜索的速度。

摘要： 针对传统人工势场法(Artificial potential field method,APF)在6自由度双机械臂系统避障路径规划中容易陷入局部极小值这一缺陷,提出了一种改进APF与改进快速扩展随机树算法(Rapidly-exploring random trees,RRT)相结合进行避障路径规划的方法。分析了双机械臂的工作空间,确认了双臂干涉的可能性。对于双机械臂的路径规划,利用改进后的APF对主机械臂进行路径规划,并将其作为从机械臂的动态障碍物,为从机械臂规划运动路径;利用改进后的RRT自适应地选择临时目标点,解决了从机械臂路径规划时陷入局部极小值的问题;利用改进的APF对从机械臂的剩余路径进行了规划。仿真分析表明,改进后的APF-RRT算法能比传统算法更加快速准确地解决双臂系统的避障路径规划问题。

摘要： 混合动力水下滑翔机相对于传统的滑翔机,有运动速度快、机动性好,运动模式多等优点。为了更好地利用混合动力水下滑翔机的优势,开展滑翔机的路径规划研究,通过引入RRT算法向终点采样概率Rsample并调整合适的生长步长α,可以更快地生成滑翔机的规划路径。并简化了滑翔机在水平面侧向的运动学方程,增加了滑翔机的转向半径约束。最后使用B样条曲线对生成路径进行光滑化处理,改善了生成路径的质量。

摘要： 针对机械臂在高维关节空间下路径规划效率低的问题,本文提出了一种基于低差异序列与快速扩展随机树融合的路径规划算法.该方法首次使用Sobol序列代替快速扩展随机树中的伪随机序列,从而生成均匀差异采样点,且在采样过程中通过建立采样池对采样点进行优选,提高了采样点质量和采样效率.在此基础上,为使规划的路径变得光滑,本文采用基于最小二乘法的多项式拟合方法对各关节角的离散点进行后处理.实验部分首先在二维空间中进行算法性能分析,证明了本文改进的算法能够快速稳定的避开障碍物到达目标点;最后以AUBO–i5机械臂为原型开展了实验研究,验证了所提算法在机械臂上应用的优势.

摘要： 在机器人路径规划实践中,运用快速扩展随机树法(RRT)法引进动力学约束,但是若行进路线上分布着很多障碍物,基于RRT算法下的路径检索效率将会明显下降,并且这种算法自身不具备最优性。鉴于以上状况,设计了一种混合式的路径规划策略,运用路径导引点拓展了RRT结构,基于所得结构探查到机器人可通行的区域范围,配合启发式搜索算法寻找到机器人运动轨迹。结合仿真实验所得结果,以上方法策略能快捷有效地处理复杂障碍物广泛分布工况下机器人运动路径规划相关问题。

摘要： 针对智能巡检机器人在狭窄通道上的路径规划问题,设计了一种多次根节点快速扩展随机树算法。首先通过多个次根节点扩展得到局部扩展树,实现对局部区域探索;其次,通过不断重启生成新的根采样节点,找到狭窄空间区域;最后,进行迭代搜索,得到一条从起点到目标点的代价最小且无碰撞的最优路径。通过与传统的RRT算法和Bi-RRT算法以及Informed-RRT算法进行对比实验,算法在在整个连通路径上采样节点的分布更加均衡、探索成功率更高、路径成本更小,出现过度采样和欠缺采样的概率大大降低,通过狭窄通道的性能明显提高。

摘要： 针对现有航迹规划算法缺乏同时具备快速性和最优性的问题,本文提出了了一种新型的无人机航迹规划算法,在快速扩展随机树算法基础上,引入了RRT-connect方法,充分发挥了RRT算法快速扩展的特性,并采用Dijkstra算法对改进算法产生的冗余节点进行处理,得到一条优化的航迹,最后采用K航迹法进行航迹平滑处理,使得航迹对于无人机可飞.仿真结果表明该算法能够在有效提高航迹产生速度的同时得到近似最优的航迹.

摘要： 近年来,国内大型公建项目发展迅速,建筑规模不断扩大,同时内部空间结构体系也日趋复杂.因此,探讨如何科学客观地评价一个建筑的空间复杂程度是十分必要的,现阶段空间复杂度评价方法多是基于空间句法原理,采用基于密度或网格的传统算法对区域内可达性空间的分布特点进行计算,计算耗时较大且结果过于理想化.如常见的可见度图分析方法(VGA),利用光线直线传播原理,以视野可见性表征空间可达性,缺少考虑实际场景中人眼可视域的范围、注意力机制等影响.本文提出一种基于快速扩展随机树(RRT)路径规划算法的新型空间复杂度计算方法对传统方法进行修正.本文通过对VGA算法与本文算法的案例结果分析对比,探讨该算法的实际可行性.结果表明,该方法可以简洁快速地实现对建筑空间结构复杂度的分析,量化空间可达性和可理解性,辅助设计师于空间结构效能角度快速分析建筑空间,理性的创作或评价建筑设计.

摘要： 突防反隐身雷达网是无人作战飞机(UCAV)完成纵深打击任务的关键环节,而进行有效的突防航迹规划是提高突防成功率的必要手段之一.考虑到雷达网反隐身原理,本文首先根据UCAV实际飞行过程中的动态RCS特性建立了一种动态随机RCS模型.进一步,通过引入快速扩展随机树(RRT)的思想,提出了一种反隐身雷达网威胁条件下的UCAV突防航迹规划方法.通过在典型威胁场景以及复杂场景下得到的突防航迹和统计实验结果表明,该方法能够在高密度的雷达威胁环境中保证UCAV突防低可探测性,而且规划结果具有随机性,能够满足突防线路不可预知性的要求.

摘要： 基于快速扩展随机树的运动规划算法通过随机采样的方式探索未知空间,具有概率完备性和较高的路径搜索效率. 当前该类算法在解决无人机路径规划问题时需要对飞行距离和平滑度进一步优化. 针对这一问题,对无人机机动性能和探测能力建模,设计随机采样、威胁规避及路径平滑性等启发式快速收敛策略,提出了面向已知和未知任务空间的无人机改进路径规划算法. 仿真结果表明该方法能有效缩短航路长度,改善路径的可跟踪性和平滑性.

摘要： 针对移动机器人未知环境探索有效性问题，对传统快速扩展随机树(RRT)算法进行改进，降低了探索盲目性。提出一种未知环境探索的路径规划方法，该方法借助环境局部知识，对目标进行包围式搜索，同时制定了环境动态因素分割策略，完成环境的全过程探索。仿真验证表明：该方法提高了环境探索的有效性和主动性。

摘要： 提出一种以动力学模型为基础的电力线路巡检飞行机器人运动规划方法,采用随机优化的思想解决有限时间内不完整系统的问题，本质上是一种在快速扩展随机树算法的基础上融入飞行机器人动力学模型的运动规划算法，初步解决了电力线巡检飞行机器人运动规划问题。运用Matlab工具进行仿真实验，验证了方法的可行性和有效性。

摘要： 本发明公开了一种高效的基于快速随机扩展树的路径规划方法，使用贪婪采样器在空间中采样样本点引导树的扩展，并且在遇到障碍物无法成功对树进行扩展时会判断局部环境的情况来引导树的扩展。规划器使用双树的方式搜索路径，在双树的交换方式上也采用更加灵活的方法。可以有效处理窄通道环境的规划问题。本发明使用贪婪采样器，加快了规划器探索空间的速度，从而减少了规划所需时间；环境判断过程使得树可以更容易的通过窄通道环境。环境判断过程会引导树向着计算出的可行方向扩展，树可以在障碍物附近有更好的扩展表现；两棵树的交换方式使得规划器可以更稳定的给出规划结果，不会长时间陷入一方无法扩展且无法交换的状态或是陷入频繁交换的状态。

摘要： 本发明涉及一种基于快速扩展随机树的无人机航路规划方法，属于无人机技术领域。相对于现有技术主要改进点：在使用随机点作为新增点替换传统方法的定步长生成新增点，通过为新增节点创建父节点的方式使得局部路径更加靠近障碍物。其中使用随机点作为新增点替换传统方法的定步长生成新增点的方案，极大程度上提高了随机树的扩展速度，减少了环境的维度和大小对规划算法的约束强度，能更好的适应于无人机工作的三维场景；通过为新增节点创建父节点的方式使得局部路径更加靠近障碍物，从而减少了新增节点添加到随机树后到根节点的代价，提高了生成符合无人机航迹的速度。

摘要： 本发明公开了一种快速扩展随机树路径光滑方法。本发明方法是基于Douglas‑Peucker算法及B样条函数的路径光滑方法。首先，利用Douglas‑Peucker算法从快速扩展随机树算法产生的路径节点中提取若干节点作为关键路标；然后，采用B样条函数拟合关键路标，得到一条曲率连续的光滑路径，从而实现规划路径的光滑化，解决了快速扩展随机树算法产生的路径存在过多的冗余点，路径转折点较多的问题。

摘要： 基于高斯采样和目标偏向引导的快速扩展随机树算法、电子设备及存储介质，包括结合高斯采样和目标偏向引导的改进型快速扩展随机树算法及其装备设置，用于生成和优化机器人运动轨迹。本发明提出使用动态高斯采样器取代原有的随机采样，减少节点生成的随机性；本发明结合使用了目标偏向引导的扩展方式，使得树的扩展更具方向性；本发明使用了延后的碰撞检查，避免重复的碰撞检查过程所造成的冗余计算量和时间代价。

摘要： 本发明属于自动控制的技术领域，公开了一种基于改进快速扩展随机树的冗余机械臂避障轨迹规划方法，包括步骤一、建立冗余机械臂的D‑H模型以及障碍物的简化包络模型；步骤二、根据冗余机械臂末端执行器的目标位姿，利用冗余机械臂逆运动学解析法求解满足需求的目标关节角，并设为qgoal；步骤三、将障碍物的简化包络模型向冗余机械臂的关节空间映射，进而得到冗余机械臂在关节空间内的无碰撞自由空间；步骤四、以目标关节角qgoal对应的节点为目标节点，在无碰撞自由空间内建立搜索树，根据选取规则有条件地选取随机采样节点，并引入搜索树节点筛选机制，最终在无碰撞自由空间内规划出一条无碰撞路径。

摘要： 本发明公开了一种基于快速扩展随机树的无人车避障方法，包括：步骤1、通过获取无人车数据以及障碍物位置数据，对障碍物轮廓尺寸进行膨胀处理，以得到障碍物膨胀后的区域；步骤2、通过快速遍历随机树法结合无人车行驶起点终点数据，生成所述无人车行驶的路径点，其中，随机树中新节点选用依据是，所述新节点是否在步骤1中所述障碍物膨胀后的区域内；步骤3、通过Dubins曲线对步骤2中生成的路径点进行检测，以生成最终所述无人车避障的路径；若检测中删除路径无效点后的路径点的密度低于阈值，则进入步骤2中重新生成所述无人车行驶的路径点。本发明可快速寻找满足车辆转弯半径的避障通路，提高了生成的无人车行驶的避障路径的安全性和可靠性。

摘要： 本发明公开了基于改进双向快速扩展随机树算法的无人机路径优化方法，该方法包括以下几个步骤：一、建立无人机运动学约束模型和确定二维空间内起始点和目标点；二、基于后向扇形区域采样方法扩展双向随机树的节点；三、基于动态自适应步长方法解决在障碍物附近生长局限性的问题；四、通过连接双向搜索树的节点，形成一条完整的飞行路径。本发明在经典B‑RRT*算法的基础上，基于后向扇形区域采样方法，当节点扩展时把随机树采样点限制在后向扇形区域，同时基于动态自适应步长方法解决了在障碍物附近生长局限性的问题，最后连接各节点，生成一条符合无人机真实可飞的飞行路径，为低空下无人机自主导航飞行提供了可行的方法。

摘要： 本发明公开了一种基于强化学习和快速扩展随机树的无人艇路径规划方法，首先基于马尔科夫决策过程构建用于无人艇路径规划的决策模型；然后对无人艇的航行环境进行建模，并确定初始位置和目标位置；再将初始位置作为根节点，构建初始随机树，基于构建的用于无人艇路径规划的决策模型，采用Q‑learning算法对初始随机树的拓展点进行选择，根据选择出的拓展点更新随机树，直到找到从初始位置到目标位置的路径，扩展点的选择过程中根据与环境模型交互的状态筛选随机采样点，并根据随机采样点的状态和奖励更新价值函数。本发明的方法可以提供对环境的适应性，并提高路径规划的准确性。

摘要： 本发明提出一种基于快速扩展随机树与动态窗口法的双层路径规划方法，先对地图内的障碍物进行处理，包括安全距离设定和障碍物填充，然后利用快速扩展随机树算法对已处理的地图进行初步规划，其中，提出模仿植物生长的趋光性的仿生设计。以无障碍物最远的规则取得局部目标点，进一步采用动态窗口法以局部目标点为指引向其运行，当智能车到达局部目标点一定范围内时，转而向下一个目标点运行，循环上述步骤，直到到达最终的全局目标点。应用本技术方案可实现将无人车的运动学约束融入到路径规划过程中，使算法规划出的路径符合无人车的行驶要求。

摘要： 基于高斯采样和目标偏向引导的快速扩展随机树算法、电子设备及存储介质，包括结合高斯采样和目标偏向引导的改进型快速扩展随机树算法及其装备设置，用于生成和优化机器人运动轨迹。本发明提出使用动态高斯采样器取代原有的随机采样，减少节点生成的随机性；本发明结合使用了目标偏向引导的扩展方式，使得树的扩展更具方向性；本发明使用了延后的碰撞检查，避免重复的碰撞检查过程所造成的冗余计算量和时间代价。