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.

Navigation Method Based on Improved Rapid Exploration Random Tree Star-Smart(RRT^(*)-Smart) and Deep Reinforcement Learning

A large number of logistics operations are needed to transport fabric rolls and dye barrels to different positions in printing and dyeing plants, and increasing labor cost is making it difficult for plants to recruit workers to complete manual operations. Artificial intelligence and robotics, which are rapidly evolving, offer potential solutions to this problem. In this paper, a navigation method dedicated to solving the issues of the inability to pass smoothly at corners in practice and local obstacle avoidance is presented. In the system, a Gaussian fitting smoothing rapid exploration random tree star-smart(GFS RRT^(*)-Smart) algorithm is proposed for global path planning and enhances the performance when the robot makes a sharp turn around corners. In local obstacle avoidance, a deep reinforcement learning determiner mixed actor critic(MAC) algorithm is used for obstacle avoidance decisions. The navigation system is implemented in a scaled-down simulation factory.

复杂环境下DWA与RRT算法融合的AUV局部路径规划

针对复杂水下环境下的自主水下航行器(autonomous underwater vehicle,AUV)局部路径规划问题,传统动态窗口法(dynamic window approach,DWA)存在复杂障碍物中陷入局部停滞,动态避障性能不佳等问题,本文提出了一种基于DWA与快速随机搜索树(rapid-exploration random tree,RRT)算法融合的路径规划算法。改进的DWA算法速度空间根据整个动态窗口的周期生成,重设了评价函数并结合AUV任务环境引入洋流能耗评价函数;改进的RRT算法在局部已知空间内规划导引点,帮助DWA脱离局部停滞状态并实现更安全的动态避障。将2种算法融合,实现了AUV在复杂水下环境中的局部路径规划。仿真表明,该融合算法能够降低AUV在洋流中的能耗代价,解决了DWA在复杂障碍物中陷入局部停滞的问题,能够安全有效地躲避动态避障物。

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

针对RRT^(*)算法在复杂环境路径规划中存在的盲目搜索、冗余节点及路径较长等问题,提出一种融合树扩展策略和采样策略的改进RRT^(*)算法(AF-RRT^(*))。通过创造父节点改进RRT^(*)扩展树的结构,缩小路径长度;引入自适应探索,增加采样导向的选择性,减少路径搜索时间,同时不会陷入局部最优陷阱;通过动态步长,减少冗余节点。仿真结果表明,AF-RRT^(*)算法在多种环境下,路径获取效率和路径质量均优于RRT^(*)和F-RRT^(*)。消融实验验证了AF-RRT^(*)算法和算法各功能模块的有效性。

基于CL-RRT与MPC的舰载机牵引系统路径规划

针对舰载机在甲板狭小、复杂环境下的调运过程,结合闭环快速随机搜索树(close loop rapidly exploring random trees,CL-RRT)和模型预测控制(model predictive control,MPC)提出一种舰载机牵引系统的路径规划算法。首先,在CL-RRT中采用纯追踪器与线性二次型(linear quadratic,LQ)控制器得到系统的控制输入并向前仿真得到规划路径。其次,将已得路径进行等比缩放与插值作为MPC的初始解。最后,设置MPC的目标函数等并解得最终路径。展开自定义三个场景下的仿真实验,通过与CL-RRT算法的实验结果进行比较,验证本文算法的优越性。实验结果表明,所提算法可有效解决因采样随机性带来解质量不佳的问题,提升舰载机在甲板上的调运效率与安全性。

Intermediary RRT*-PSO:A Multi-Directional Hybrid Fast Convergence Sampling-Based Path Planning Algorithm

Path planning is a prevalent process that helps mobile robots find the most efficient pathway from the starting position to the goal position to avoid collisions with obstacles.In this paper,we propose a novel path planning algorithm-Intermediary RRT*-PSO-by utilizing the exploring speed advantages of Rapidly exploring Random Trees and using its solution to feed to a metaheuristic-based optimizer,Particle swarm optimization(PSO),for fine-tuning and enhancement.In Phase 1,the start and goal trees are initialized at the starting and goal positions,respectively,and the intermediary tree is initialized at a random unexplored region of the search space.The trees were grown until one met the other and then merged and re-initialized in other unexplored regions.If the start and goal trees merge,the first solution is found and passed through a minimization process to reduce unnecessary nodes.Phase 2 begins by feeding the minimized solution from Phase 1 as the global best particle of PSO to optimize the path.After simulating two special benchmark configurations and six practice configurations with special cases,the results of the study concluded that the proposed method is capable of handling small to large,simple to complex continuous environments,whereas it was very tedious for the previous method to achieve.

考虑无人艇运动学约束的IRRT^(*)-APF路径规划算法

针对未知环境下无人艇(USV)的路径规划问题,提出了一种考虑无人艇运动学约束的改进RRT^(*)-APF路径规划算法(IRRT^(*)-APF)。通过引入改进的人工势场法(APF)提高了快速搜索随机树(RRT^(*))的避障性能,在人工势场中考虑无人艇与障碍物和目标点间的角度大小,加速了无人艇远离障碍物并接近目标点;使用曼哈顿距离法提高了RRT^(*)算法的效率。所提出的IRRT^(*)-APF方法,与滚动RRT^(*)算法和PSOFS算法进行了仿真对比实验。结果表明,提出的方法所规划的路径转折的次数和转角均显著减小,有利于实现无人艇的平稳控制,同时缩短了路径长度和规划路径的时间。在风浪环境下的进一步仿真实验结果表明,所提出的算法在有风浪干扰时依然能规划出符合无人艇运动学的轨迹,具有较强的抗风浪鲁棒性。

基于改进RRT的带电作业机器人机械臂的避障路径规划研究

针对带电作业机器人机械臂在复杂配电网环境的路径规划问题,该文提出了一种改良的快速随机扩展树(RRT)避障算法。该算法通过引入基于障碍物分布的动态采样函数,实现了采样点的动态调整,以提高路径规划的效率和准确性。结合A*算法的代价函数,进一步简化和平滑路径,减少拐点,优化了机器人机械臂的运动轨迹。仿真结果表明,该算法在缩短路径规划时间和路径长度上的高效性,其中在三维仿真中采样点个数减少70.3%,规划时间缩短68.3%,证明了其在带电作业机器人领域的有效性。

基于RRT的无人机航迹规划算法

针对传统快速搜索随机树无人机航迹规划算法中采样点生成随机性过高,规划路径平滑度差的问题,提出一种基于改进快速搜索随机树的无人机航迹规划算法。在搜索树拓展过程中,引入限定采样点生成范围的探测场,改变采样点的生成策略,使算法具备迅速向目标收敛的能力和绕开障碍物威胁的能力。此外,改进算法还对初始航迹的冗余点进行裁剪,并采用B样条曲线法改善航迹平滑度。仿真结果表明,基于改进快速搜索随机树的无人机航迹规划算法比传统快速搜索随机树无人机航迹规划算法平均航迹长度减少21.75%,平均搜索树节点数减少75.78%,平均计算时间减少48.04%。

融合RRT^(*)与APF算法的机器人路径规划研究

针对传统快速扩展随机树(rapidly-exploring random tree star,RRT^(*))算法在全局路径规划过程中存在收敛速度慢、搜索路径不平滑、内存占用多等问题,提出了一种RRT^(*)与人工势场法(artificial potential field,APF)的融合搜索算法。为了加快RRT^(*)算法在搜索过程中的收敛速度,在算法中利用人工势场法的思想引导扩展随机树快速向目标点生长;对融合算法在空间中的采样范围做出改进,使算法在APF产生的合力特定范围内进行采样,提高算法在空间中的搜索效率,减少无用节点的扩展。仿真结果表明:相比传统的RRT和RRT^(*)算法以及APF-RRT融合算法,APF-RRT^(*)融合算法能够规划出更短、更平滑的路径,路径距离缩短了1.5%~10.83%;算法的搜索时间也显著缩短了1.97%~49.78%;与其他算法相比,APF-RRT^(*)融合算法的路径节点数量减少了4.66%~41.95%,路径平滑性也得到了提高。

基于RRT-Dubins的无人机航迹优化方法

针对多障碍物环境下考虑无人机(Unmanned Aerial Vehicle,UAV)始末位姿、转弯半径和航迹长度的1阶光滑约束的UAV航迹规划问题,提出一种基于快速搜索随机树(Rapidly-exploring Random Trees,RRT)算法和Dubins曲线以局部最优逼近全局最优的UAV航迹优化方法。利用RRT算法和基于贪心算法的剪枝优化方法,在二维任务空间中规划出满足避障要求的可行离散航路点。采用多条Dubins曲线平滑连接航路点,根据UAV始末位姿确定首尾曲线端点,基于UAV性能、障碍物和飞行参数的约束关系,建立多约束的航迹优化数学模型。通过粒子群优化算法确定曲线类型,同时优化曲线连接处位姿和曲线半径,获得最短航迹。仿真结果表明:所提方法得到的航迹与其他方法相比,在不同障碍物数量和始末位姿的多种场景中,平均长度缩短了11.48%,在避开障碍物的同时,满足UAV动力学约束。

基于改进RRT的直捻机上纱机械臂路径规划

为了提高直捻机上纱机械臂的避障路径规划效率,提出一种动态目标圆采样结合回归机制的改进型双向快速扩展随机树算法(Dynamic-target-circle Sampling and Regression mechanism Bidirectional Rapidly-exploring Random Trees,DSRB-RRT)。为解决随机树盲目采样问题,提出了一种动态目标圆采样法,引导随机树在以目标为圆心的动态圆区域内进行采样;为解决随机树拓展速度慢,提出了一种变步长变概率法,根据障碍物信息自行改变拓展步长和偏置概率,加快随机树收敛;引入了回归机制防止随机树在区域内过度采样;算法生成路径后,裁剪路径中冗余节点来缩短路径长度,并用三次B样条曲线平滑优化路径。仿真结果表明,DSRB-RRT算法相比于加入目标偏置的RRT、BI-RRT和GS-RRT在不同障碍场景下的收敛效率更高,平均路径更短。在ROS系统中对上纱机械臂进行仿真,验证了DSRB-RRT算法的有效性,可以提高机械臂路径规划效率。

基于改进RRT算法的电缆敷设算法设计

为提高发电工程电缆敷设效率与准确性,采用快速扩展随机树(RRT)算法来设计电缆敷设算法,设计了电缆通道、敷设搜索树、敷设路径等计算要素的数据结构,结合渐进最优的RRT*算法的“重连”操作来优化电缆路径长度,设定了电缆属性、容积率、电缆弯曲限制等敷设条件。通过通道修剪、迭代约束、终点导向、多点扩展、路径复用等多种方式优化了敷设算法。

基于MI-RRT^(*)算法的路径规划研究

针对Informed-RRT(rapidly-exploring random tree)^(*)算法收敛速度慢、优化效率低和生成路径无法满足实际需求等问题,开展了基于MI-RRT^(*)(Modified Informed-RRT^(*))算法的路径规划研究,通过引入贪心采样和自适应步长的方法提高算法的收敛率,减少路径生成时间、降低内存占用;利用最小化Snap曲线优化的方法使路径平滑的同时动力也变化平缓,达到节省能量的效果,并提供实际可执行的路径。最后通过多组不同复杂度的实验环境表明,较Informed-RRT^(*)算法MI-RRT^(*)算法稳定性更高、所得规划路径平滑可执行,并且能够减少20%的迭代次数和25%的搜索时间,得出在开阔以及密集环境中MI-RRT^(*)算法较Informed-RRT^(*)和RRT^(*)算法有明显的优势。

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

针对无人车在复杂环境中进行全局路径规划时存在的盲目搜索、节点冗余、路径不光滑及不安全等问题,提出一种基于快速扩展随机树(RRT,rapidly-exploring random tree)的综合改进路径规划算法;首先引入目标动态概率采样策略和人工势场引导随机树扩展机制;其次根据汽车运动学模型,对规划的路径进行转角约束和碰撞检测,保证路径的安全性;然后引入Reeds-Sheep曲线用于直接与目标位姿进行连接,避免多余的位姿调整;最后对路径进行剪枝和平滑处理,得到一条更短更光滑的路径;在实验部分,针对不同仿真环境,以规划时间、路径长度和节点数目作为评价指标,对比了RRT算法、RRT*算法和文章算法的路径规划效果;实验结果显示,文章算法相比于RRT算法和RRT*算法,节点数目分别减少了58.94%和85.22%,规划时间分别缩短了61.20%和79.23%,且路径长度相比于RRT算法缩短了17.26%,并和RRT*算法规划的最优路径长度相近。

基于改进RRT结合B样条的机械臂运动规划方法

为解决传统快速拓展随机树(RRT)算法的随机性强,导向性差,规划时间长及寻迹平滑度差等问题,提出一种基于目标偏置策略结合自适应可变步长的改进型RRT算法(PAVS-RRT)。首先,在传统RRT算法基础上设置一个目标偏置阈值,同时引入局部扩展机制避免因改变采样结构而造成的局部最优问题;其次,结合自适应步长策略优化其搜索时间;最后,采用三次B样条函数对所规划路径进行拟合优化。仿真实验中所提算法在保证机械臂成功避障且顺利抵达目标位置的同时,其各关节参数均波动较小且未发生突变,有效降低了机械臂在运动规划过程中的抖振情况。实验结果表明,所提算法较基本算法其平均路径搜索时间提高了73.49%,算法搜索效率及平滑性得到显著改善。

基于CRS-RRT算法的无人机航迹规划

针对快速搜索随机树(RRT)算法在航迹规划过程中存在采样点扩展随机性强、航迹曲折不平滑等问题,提出了一种基于约束随机采样点的RRT(Constrained Random Sampling-based RRT,CRS-RRT)算法。该算法引入人工势场法中的引力场势能函数约束随机采样点在目标点附近采样,引导随机树朝着目标点生长,提高算法的规划速度,并结合去除冗余节点策略和Minimum Snap航迹平滑方法,在复杂三维环境中可快速生成一条安全、平滑且满足无人机动力学约束的航迹。仿真结果表明,该算法有效提高航迹规划速度并缩短航迹长度。

Two-Layer Path Planner for AUVs Based on the Improved AAF-RRT Algorithm

As autonomous underwater vehicles(AUVs)merely adopt the inductive obstacle avoidance mechanism to avoid collisions with underwater obstacles,path planners for underwater robots should consider the poor search efficiency and inadequate collision-avoidance ability.To overcome these problems,a specific two-player path planner based on an improved algorithm is designed.First,by combing the artificial attractive field(AAF)of artificial potential field(APF)approach with the random rapidly exploring tree(RRT)algorithm,an improved AAF-RRT algorithm with a changing attractive force proportional to the Euler distance between the point to be extended and the goal point is proposed.Second,a twolayer path planner is designed with path smoothing,which combines global planning and local planning.Finally,as verified by the simulations,the improved AAF-RRT algorithm has the strongest searching ability and the ability to cross the narrow passage among the studied three algorithms,which are the basic RRT algorithm,the common AAF-RRT algorithm,and the improved AAF-RRT algorithm.Moreover,the two-layer path planner can plan a global and optimal path for AUVs if a sudden obstacle is added to the simulation environment.

基于改进RRT算法的狭长空间无人车辆路径规划

针对狭长空间无人车辆路径规划系统,提出一种基于改进的快速搜索随机树(rapidly-exploring random trees,RRT)路径规划算法,以解决传统RRT算法随机性较大、路径缺乏安全性的问题.该算法通过加入自适应目标概率采样策略、动态步长策略对传统的RRT算法进行改进,同时考虑到实际情况中无人驾驶车辆的动力学约束,该算法加入车辆碰撞约束和路径转角约束,并针对转角约束会导致迭代次数激增的问题提出了一种限制区域内随机转向的策略,最终得到一条安全性较高的路径.采用计算机仿真对所提算法和现有算法的性能进行对比验证.所提算法在狭长空间相较于传统人工势场引导下的RRT算法迭代次数降低了33.09%,规划时间减少了6.44%,路径长度减少了0.06%,并且在简单环境和复杂障碍物环境下规划能力均有提升.所提算法规划效率更高、迭代次数更少.

基于采样空间约束的改进RRT算法

由于水下环境比陆地环境复杂,在进行机器人水下路径规划时,利用传统算法规划的路径质量较差。为此,提出一种基于采样空间约束的改进快速扩展随机树(RRT)算法。首先,提取边界点,通过凸包算法划定障碍范围;其次,利用膨胀算法对划定的范围做区域膨胀,对采样空间进行约束;最后,通过对随机节点的四个特征进行计算,确定采样点的概率,为采用点的选择提供导向性,缩短因采样空间过大而导致过长寻路时间,提高路径质量。通过在PyCharm环境下的仿真实验对比RRT算法、RRT*算法和改进后的RRT算法,实验结果表明改进的RRT算法各项性能均优于RRT算法和RRT*算法。