An Adaptive Rapidly-Exploring Random Tree

Sampling-based planning algorithms play an important role in high degree-of-freedom motion planning(MP)problems,in which rapidly-exploring random tree(RRT)and the faster bidirectional RRT(named RRT-Connect)algorithms have achieved good results in many planning tasks.However,sampling-based methods have the inherent defect of having difficultly in solving planning problems with narrow passages.Therefore,several algorithms have been proposed to overcome these drawbacks.As one of the improved algorithms,Rapidlyexploring random vines(RRV)can achieve better results,but it may perform worse in cluttered environments and has a certain environmental selectivity.In this paper,we present a new improved planning method based on RRT-Connect and RRV,named adaptive RRT-Connect(ARRT-Connect),which deals well with the narrow passage environments while retaining the ability of RRT algorithms to plan paths in other environments.The proposed planner is shown to be adaptable to a variety of environments and can accomplish path planning in a short time.     

机器人路径规划的快速扩展随机树算法综述

路径规划是移动机器人的重要研究内容。快速扩展随机树（Rapidly-Exploring Random Tree，RRT）算法因在机器人路径规划中的成功应用，自提出以来就得到了极大的研究与发展。快速扩展随机树作为一种新颖的随机节点采样算法，相对传统路径规划算法，具有建模时间短、搜索能力强、方便添加非完整约束等优点。介绍了快速扩展随机树算法的基本原理与性质，并从单向随机树扩展、多向随机树扩展、其他改进等方面概括了算法的研究现状。最后，展望了算法未来的研究方向与挑战。     

低空复杂环境下基于采样空间约减的无人机在线航迹规划算法

针对低空复杂环境下障碍物密集且类型多样、带有多通道并存在不确定信息的无人机在线航迹规划问题,为了减少碰撞检测次数,提高航迹搜索速度,降低航迹代价,提出一种基于采样空间约减的无人机在线航迹规划算法. 算法通过引入代价模型,提出约减域逐步构造方法,引导规划树快速有效扩展,改善了基于动态域的快速拓展随机树（Dynamic domain rapidly-exploring random tree,DDRRT） 算法中存在的采样空间过度约减问题. 算法通过密度划分索引的方法逐步构建多棵Kd 树（K-dimensional tree）并采用多近邻节点搜索方法,加快了近邻树节点搜索速度. 仿真实验结果表明,与DDRRT方法相比,该方法在保证对采样空间约减合理性的同时,提高了航迹规划效率和通道内的寻路能力.     

基于多目标快速探索随机树的移动机器人巡检路径优化方法

针对移动机器人需要访问多目标的巡检路径规划问题,该文提出一种多目标快速探索随机树路径优化方法。首先,根据提供的环境地图与巡检目标点,该文采用一种 RRT-Connect-ACO 算法得到目标点的巡检顺序和可行路径;然后,通过引入信息子集,对路径进行优化,得到最终的最优路径。实验结果表明,与现有的多目标路径规划算法相比,该方法考虑了地形的影响,得到的最优路径更符合实际情况。     

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

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

复杂环境下基于RRT的智能车辆运动规划算法

在存在大量无规则障碍物且障碍物分布不均匀的复杂环境下,现有规划算法不能很好地解决智能车辆的运动规划问题.为此,本文提出了一种简单实用的基于RRT(快速搜索随机树)的运动规划算法——连续曲率RRT算法.该算法在RRT框架中结合了环境约束以及车辆自身的约束.它首先引入了目标偏向采样策略以及合理的度量函数,大大地提高了规划速度和质量;接着提出了一种基于最大曲率约束的后处理方法以生成平滑的且曲率连续的可执行轨迹.通过仿真实验和实车测试,证实了该算法的正确性、有效性和实用性.     

未知环境下改进的基于RRT算法的移动机器人路径规划

方法的有效性.     

基于RRT搜索算法的六自由度机械臂避障路径规划

针对三维空间下的机器人路径规划问题,提出了一种改进的快速随机树算法。该算法以机器人的出发点作为随机树的根节点,以基准向量为基准选择节点的扩展方向,逐渐增加叶子节点,降低了节点的随机性,提高了扩展速度。通过运动学反解快速规划出一条全局优化路径,对于反解失败的点,做了规划替代,保证了路径规划的平滑性,降低了机器人工作过程中的抖动,从而得到能够抵达目标位姿的安全路径。     

基于循环寻优RRT算法的无人机航迹规划

针对快速扩展随机树（RRT）算法在无人机在线自主航迹规划中的寻优性问题,提出基于循环寻优RRT算法。将航迹长度代价约束作为启发条件引入RRT算法,可以有效地剪除搜索空间的无用节点,获得较优航迹。通过引入已规划可行航迹的航迹长度代价约束作为下一次算法运行的启发条件,采用循环迭代策略有效地剪除搜索空间的无用节点,使得算法每次运行后的航迹长度代价减小,多次运行后最终得到的航迹接近最优航迹,充分利用航迹长度代价的启发性,克服了RRT算法的缺点,同时获得了一系列不同航迹代价的可行备选航迹,在协同任务中可以根据协同到达时间进行快速选择。仿真结果表明该算法能够快速生成安全并且满足无人机动力学约束的较优航迹。     

UAV Online Path Planning Algorithm in a Low Altitude Dangerous Environment

UAV online path-planning in a low altitude dangerous environment with dense obstacles, static threats (STs) and dynamic threats (DTs), is a complicated, dynamic, uncertain and real-time problem. We propose a novel method to solve the problem to get a feasible and safe path. Firstly STs are modeled based on intuitionistic fuzzy set (IFS) to express the uncertainties in STs. The methods for ST assessment and synthesizing are presented. A reachability set (RS) estimator of DT is developed based on rapidly-exploring random tree (RRT) to predict the threat of DT. Secondly a subgoal selector is proposed and integrated into the planning system to decrease the cost of planning, accelerate the path searching and reduce threats on a path. Receding horizon (RH) is introduced to solve the online path planning problem in a dynamic and partially unknown environment. A local path planner is constructed by improving dynamic domain rapidly-exploring random tree (DDRRT) to deal with complex obstacles. RRT* is embedded into the planner to optimize paths. The results of Monte Carlo simulation comparing the traditional methods prove that our algorithm behaves well on online path planning with high successful penetration probability.      

复杂城市环境下无人机三维路径规划

基于转移的快速扩展随机树(T-RRT)算法,能够较快寻找到机器人在二维复杂成本空间的低危险度路径,但面对无人机的三维飞行工况,其规划结果较差,针对此问题,提出了一种基于探索、启发和转移的EHT-RRT(exploring heuristic transition-based RRT)算法.首先,算法在T-RRT的基础上...     

基于引力自适应步长RRT的双臂机器人协同路径规划

快速扩展随机树(RRT)方法的步长确定过分依赖于程序调试,而且固定的步长会导致碰撞检测失效问题.针对此问题,本文提出一种适用于双臂机器人协同路径规划的引力自适应步长RRT.首先,通过建立构型空间与工作空间的步长范数不等式,对双臂机器人在工作空间中所产生的步长进行约束,进而确保实现有效的碰撞检测;然后,提出随机树被动生长方法,在保证双臂机器人协同运动的基础上,降低规划空间的维度.最后,在随机树的节点处引入引力函数,加快算法的融合速度.仿真结果表明,引力自适应步长RRT方法可对工作空间中的步长进行有效约束,确保算法碰撞检测的有效性.在无碰撞的前提下,引力自适应步长RRT方法相比于其他算法减少了迭代次数,降低了运行时间并缩短了路径长度.将所提算法应用于双臂机器人的样机实验,结果表明双臂机器人可在保持位置协同的前提下,完成避障运动,验证了算法的可行性.     

基于改进快速扩展随机树方法的隐身无人机突防航迹规划

针对隐身无人机在日趋严密的雷达防御系统下的生存问题,提出了基于改进快速扩展随机树的隐身突防航迹规划方法.本文首先对隐身突防航迹规划中无人机的动态雷达散射截面积和雷达的发现准则这两个关键问题进行了分析和建模,然后针对现有算法在解决隐身飞机航迹规划问题时的不足,设计了改进快速扩展随机树算法,将无人机的雷达散射截面积随姿态变化的情况考虑到新节点生成中,并且结合滚动时域策略计算时域范围内所有节点的瞬时发现概率均值,以判断新节点可行性.仿真结果和对比研究表明,算法的改进策略能够处理隐身突防航迹规划的两个特性,并且可在复杂环境下快速生成更优的突防路径.     

Generative Adversarial Network Based Heuristics for Sampling-Based Path Planning

Sampling-based path planning is a popular methodology for robot path planning.With a uniform sampling strategy to explore the state space,a feasible path can be found without the complex geometric modeling of the configuration space.However,the quality of the initial solution is not guaranteed,and the convergence speed to the optimal solution is slow.In this paper,we present a novel image-based path planning algorithm to overcome these limitations.Specifically,a generative adversarial network(GAN)is designed to take the environment map(denoted as RGB image)as the input without other preprocessing works.The output is also an RGB image where the promising region(where a feasible path probably exists)is segmented.This promising region is utilized as a heuristic to achieve non-uniform sampling for the path planner.We conduct a number of simulation experiments to validate the effectiveness of the proposed method,and the results demonstrate that our method performs much better in terms of the quality of the initial solution and the convergence speed to the optimal solution.Furthermore,apart from the environments similar to the training set,our method also works well on the environments which are very different from the training set.     

基于快速扩展随机树—贪婪边界搜索的多机器人协同空间探索方法

传统多机协同探索算法存在鲁棒性较差、探索效率较低、环境障碍感知不完全等问题,为此本文提出一种基于快速扩展随机树－贪婪边界搜索（ RRT-GFE）的多机器人协同空间探索方法。首先,采用 Thiessen 多边形对环境进行建模与划分,利用 RRT 边界探索算法依次对所有 Thiessen 多边形进行探索;其次,在 RRT 边界探索算法的基础上,引入 GFE 算法进行细化搜索,并提取连续边界域的形心作为探索目标点;再次,利用划分所形成的多边形区域以及所提取出的边界点,采用基于改进市场机制的多机器人任务分配方法对探索目标点进行动态分配,并在探索过程中采用地图融合算法进行局部地图的实时融合;最后,基于机器人操作系统（ ROS）搭建仿真／样机测试平台并进行了一系列实验验证。结果表明,无论在仿真还是样机实验中,基于 RRT-GFE 的多机器人协同探索算法均能取得更加省时高效的探索效果。     

动态环境下基于路径规划的机器人同步定位与地图构建

针对动态环境下随机目标同时为特征点和障碍物的情况,提出一种基于路径规划的同步定位与地图构 建（SLAM）算法．机器人在同步定位与地图构建的同时,基于势场原理来规划机器人下一步的运动控制规律．利用 混合当前统计模型的交互式多模型（IMM）方法预测随机目标的轨迹,采用最近邻数据关联方法将动态随机目标关 联到地图中．算法构建的地图由静态特征点和随机目标的轨迹组成．仿真结果表明,提出的算法解决了动态环境中 存在的随机目标同时为障碍物时机器人的同步定位与地图构建问题,相关性能指标验证了算法的一致性估计．     

非完整约束下的机器人运动规划算法

由非完整约束定义提出一种改进RRT(快速搜索随机树)算法,解决受动力学约束的移动机器人运动规划问题.该算法将移动机器人的非完整约束条件与RRT搜索算法相结合.针对RRT算法在全局状态空间均匀随机搜索导致算法无谓耗费代价大的缺陷,引入目标偏向思想,并选择计算复杂度低的距离参数提高求解速度.通过几类典型的非完整约束下的机器...     

Global Level Path Planning for Mobile Robots in Dynamic Environments

This paper presents a self-adapting approach to global level path planning in dynamic environments. The aim of this work is to minimize risk and delays in possible applications of mobile robots (e.g., in industrial processes). We introduce a hybrid system that uses case-based reasoning as well as grid-based maps for decision-making. Maps are used to suggest several alternative paths between specific start and goal point. The casebase stores these solutions and remembers their characteristics. Environment representation and casebase design are discussed. To solve the problem of exploration vs. exploitation, a decision-making strategy is proposed that is based on the irreversibility of decisions. Forgetting strategies are discussed and evaluated in the context of case-based maintenance. The adaptability of the system is evaluated in a domain based on real sensor data with simulated occupancy probabilities. Forgetting strategies and decision-making strategies are evaluated in simulated environments. Experiments show that a robot is able to adapt in dynamic environments and can learn to use paths that are less risky to follow.     

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

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

不确定动态环境下移动机器人的完全遍历路径规划

基于生物激励神经网络、滚动窗口和启发式搜索,提出了一种新的完全遍历路径规划方法．该方法用Grossberg的生物神经网络实现移动机器人的局部环境建模,将滚动窗口的概念引入到局部路径规划,由启发式算法决定滚动窗口内的局域路径规划目标．该方法能在不确定动态环境中有效地实现机器人自主避障的完全遍历路径规划．仿真研究证明了该方法的可用性和有效性．