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.

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.

A path planning algorithm for autonomous flying vehicles in cross-countryenvironments with a novel TF-RRT^(*) method

Autonomous flying vehicles(AFVs)are promising future vehicles,which have high obstacle avoidance ability.To plan a feasible path in a wide range of cross-country environments for the AFV,a triggered forward optimal rapidly-exploring random tree(TF-RRT^(*))method is proposed.Firstly,an improved sampling and tree growth mechanism is built.Sampling and tree growth are allowed only in the forward region close to the target point,which significantly improves the planning speed;Secondly,the driving modes(ground-driving mode or air-driving mode)of the AFV are added to the sampling process as a planned state for uniform planning the driving path and driving mode;Thirdly,according to the dynamics and energy consumption models of the AFV,comprehensive indicators with energy consumption and efficiency are established for path optimal procedures,so as to select driving mode and plan driving path reasonably according to the demand.The proposed method is verified by simulations with an actual cross-country environment.Results show that the computation time is decreased by 71.08%compared with Informed-RRT^(*)algorithm,and the path length of the proposed method decreased by 13.01%compared with RRT^(*)-Connect algorithm.

Path-planning algorithms for self-driving vehicles basedon improved RRT-Connect

This study aims to solve path planning of ntelligent vehicles in self driving In this study,an improved path planning method com-bining constraints of the environment and vehicle is proposed.The algorithm designs a reasonable path cost function,then uses a heuristic guided search strategy to improve the speed and quality of path planning,and finally generates smooth and continuous cur-vature paths based on the path post-processing method focusing on the requirements of path smoothness.A simulation test shows that compared with the basic rapidly-exploring random tree(RRT),RRT-Connect and RRT*algorithms,the path length of the proposed algorithm can be reduced by 19.7%,29.3%and 1%respectively,and the maximum planned path curvature of the proposed algorithm is 0.0796 mr1 and 0.1512 mi respectively.under the condition of a small amount of planning time.The algorithm can plan the more suitable driving path for intelligent vehicles in a complex environment.

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

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

Path Planning and Optimization of Humanoid Manipulator in Cartesian Space

To solve the problems of low efficiency and multi-solvability of humanoid manipulator Cartesian space path planning in physical human-robot interaction,an improved bi-directional rapidly-exploring random tree algorithm based on greedy growth strategy in 3D space is proposed.The workspace of manipulator established based on Monte Carlo method is used as the sampling space of the rapidly-exploring random tree,and the opposite expanding greedy growth strategy is added in the random tree expansion process to improve the path planning efficiency.Then the generated path is reversely optimized to shorten the length of the planned path,and the optimized path is interpolated and pose searched in Cartesian space to form a collision-free optimized path suitable for humanoid manipulator motion.Finally,the validity and reliability of the algorithm are verified in an intelligent elderly care service scenario based on Walker2,a large humanoid service robot.

Motion Planning of Concrete Pump Truck with End-Effector's Specified Path

For motion planning of concrete pump truck( CPT) with end-effector's hosepipe path, this paper sets up the mathematic model,including definition of its motion planning,description of its state in C space( configuration space) and its path length. An advanced rapidly-exploring random trees( RRT) algorithm is proposed, in which each tracing point dispersed from the end hosepipe path can map multi-states of CPT so as to make variety of motion path of CPT. For increasing search efficiency and motion path quality,this algorithm generates any random states of CPT in certain probability to trend to the initial state or target state mapped with the end hosepipe path,and to have the least cost between this random state and its parent state. A typical case and two special cases are analyzed in which the end hosepipe paths are reciprocating linear trajectory and planar or spatial sine curves respectively. Their results verify the feasibility and validity of the proposed algorithm.

基于均匀概率的目标启发式RRT机械臂路径规划方法

针对多自由度机械臂在三维空间中轨迹规划的高复杂性、安全性和可靠性等问题,基于快速扩展随机树(rapidly-exploring random trees,RRT)算法在高维空间中的概率完备性和计算轻量性等优势,提出了一种基于均匀概率的目标启发式RRT(target heuristic RRT based on uniform probability,PH-RRT)方法.首先,该方法基于均匀概率的分配机制选取概率采样阈值作为节点标准,并与随机采样值进行比较.当随机采样值在设定的阈值范围内时,确定目标点为随机点进行节点扩展.当随机采样值在设定的阈值范围外时,随机生成随机点,在目标重力和随机点重力的目标启发式作用下进行节点扩展.然后,在已规划出的路径的基础上,进一步引入广度优先搜索思想,针对规划出的路径进行优化处理,提高了路径平滑度并减少了路径长度.实验结果表明,该方法能较好地解决传统RRT方法固有的盲目搜索问题,减少路径规划时间和路径长度,提高机械臂的路径规划效率.

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

针对快速探索随机树(RRT)路径规划算法缺乏导向性和规划空间增大时算法时间复杂度高的问题,提出一种目标概率偏置与步长控制的改进RRT算法(I-RRT)。I-RRT结合目标概率偏置,以一定概率使采样点偏置为目标点,提高路径规划的导向性,并引入步长控制优化算法,提高运算效率,优化路径。在MATLAB平台建立了算法的仿真实验,结果表明:I-RRT的导向性与算法时间复杂度均优于经典的RRT算法;并在ROS平台上搭建了六自由度机械臂的避障规划与控制实验,实验验证了该算法的有效性。

基于改进双向RRT^(*)算法的机械臂路径规划

针对传统双向改进快速扩展随机树(RRT^(*))算法采样速度较慢以及产生路径较粗糙的问题,对6轴机械臂的运动规划进行分析,提出了一种基于目标采样和局部路径优化改进的双向RRT^(*)算法。首先,应用目标采样思想,在对扩展点进行筛选时,考虑随机扩展点与目标点的距离,保留距离目标点最近的随机搜索点;然后,对该搜索点进行扩展,减少不必要区域的搜索,使采样更加高效,搜索路径更优;最后,在此基础上,结合局部路径优化算法,对RRT^(*)算法中重布线随机树过程引入优化函数概念,计算两个节点之间最小距离所需节点,并连接该节点以降低路径曲折程度。将所提改进算法与原始双向RRT^(*)算法在不同测试环境下用机器人操作系统(ROS)进行仿真实验,实验结果表明,所提算法能有效优化算法规划路径,并提高规划效率。

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

为解决渐进最优快速扩展随机树(RRT^(*))算法在特殊环境下(如狭窄通道)路径规划存在的内存占用多、规划效率低等问题,提出了一种基于目标约束采样和目标偏置扩展的改进RRT^(*)算法.首先,在采样上引入目标偏置策略,并对每次采样进行位置约束,使采样的目标导向性更强.然后,在新点扩展上摒弃了已有算法单纯朝着采样点扩展的思路,通过给采样点和目标点分配不同权重,使得每一次扩展同时由采样点和目标点共同决定,进而加快搜索速度.接着,采用三次B样条曲线对搜索到的路径进行平滑处理,以保证路径的可行性.最后,分别基于Matlab和V-REP平台对RRT^(*)算法和改进RRT^(*)算法进行了2D和3D的对比实验,实验结果验证了改进RRT^(*)算法的优越性和有效性.

基于改进快速扩展随机树的机械臂路径规划

针对机械臂路径规划问题,提出一种基于改进RRT算法的路径规划方法。改进RRT结合了目标偏置策略和贪婪生长策略的优点,在随机采样时,以一定概率使采样点偏置为目标节点,降低随机采样的盲目性,在目标节点方向上采用贪婪式扩展策略,增加随机树局部方向上的生长速度。RRT法规划路径结果并非最优,提出改进GPP法删除多余路径节点,优化机械臂运动路径。通过与Biased-RRT和Greedy-RRT数值仿真结果对比,证明了改进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的偏向性路径搜索算法(m-RRT)。m-RRT采用生成随机点向量组的形式对随机点选取策略进行了优化,改善快速扩展随机树的不确定性,减少不必要的扩展,而加快向目标位置搜索的速度,且得到的路径优于RRT算法的结果。通过其在二维平面路径规划和三维机械臂路径规划的测试,表明其具有一定的应用价值。

复杂环境下基于采样空间自调整的航迹规划算法

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

基于自适应目标偏置系数的机械臂路径规划算法

针对快速搜索随机树(RRT)算法因其随机特性导致的运行时间过长和计算结果往往不是最优解的问题,在RRT算法及其改进算法的基础上,课题组提出了一种基于自适应目标偏置系数的机械臂路径规划算法,并将该算法应用到医疗设备无影灯的使用中。首先,用D-H参数法对6自由度机械臂进行运动学描述和正运动学求解,得到末端的运动状态和位姿;然后,综合RRT算法及其改进算法的优点拓展新节点和重置父节点,并引入自适应目标偏置系数,再对路径作剪枝后处理。对比实验结果显示:该方法在保证算法搜索效率的基础上,有效地提高了路径质量。基于ROS的仿真平台验证了该方法具有实用性和可行性。

一种基于改进的快速扩展随机树的工业机器人路径避障规划算法

针对传统快速扩展随机树(RRT)算法在机械臂的运动规划上缺乏导向性,收敛速度慢等问题,文中在传统RRT的基础上,提出了一种扩展点选择策略和自适应步长策略,并且在算法陷入局部极小值时,采用避免回归机制,快速脱离极小值.然后结合Dijkstra算法对改进算法产生的路径进行优化,得到一条优化后的路径.最后,得到的机械臂末端有效路径再通过本文的机械臂规划模块,转化为一条机械臂最优位姿路径.将该改进算法与其他算法在Matlab和ROS中进行仿真实验,实验结果表明,该算法能有效指导RRT树的生长方向,避免陷入极小值,并且提高算法的收敛速度,并且提高了机械臂在仿真中运动规划效率.