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.

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

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

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.

HQD-RRT^(*):a high-quality path planner for mobile robot in dynamic environment

Mobile robots have been used for many industrial scenarios which can realize automated manufacturing process instead of human workers. To improve the quality of the optimal rapidly-exploring random tree(RRT^(*)) for planning path in dynamic environment, a high-quality dynamic rapidly-exploring random tree(HQD-RRT^(*)) algorithm is proposed in this paper, which generates a high-quality solution with optimal path length in dynamic environment. This method proceeds in two stages: initial path generation and path re-planning. Firstly, the initial path is generated by an improved smart rapidly-exploring random tree(RRT^(*)-SMART) algorithm, and the state tree information is stored as prior knowledge. During the process of path execution, a strategy of obstacle avoidance is proposed to avoid moving obstacles. The cost and smoothness of path are considered to re-plan the initial path to improve the path quality in this strategy. Compared with related work, a higher-quality path in dynamic environment can be achieved in this paper. HQD-RRT^(*) algorithm can obtain an optimal path with better stability. Simulations on the static and dynamic environment are conducted to clarify the efficiency of HQD-RRT^(*) in avoiding unknown obstacles.

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.

近海复杂环境下UUV动态路径规划方法研究

为解决近海环境下水下无人航行器(unmanned underwater vehicle,UUV)的动态路径规划问题,本文提出一种结合全局和局部动态路径规划的算法。首先,本文提出一种基于自适应目标引导的快速拓展随机树算法,以增加随机树生长的方向性,并通过转向和重选策略减少无效拓展加快算法的收敛速度。接着,获得全局路径之后使用自适应子节点选取策略获取动态窗口法的子目标点,将复杂的全局动态任务规划分解为多个简单的动态路劲规划,从而防止动态窗口法陷入局部极小值。最后,通过UUV出港任务仿真实验验证了算法的有效性和实用性。

基于对比优化的RRT路径规划改进算法

针对动态环境下机器人RRT路径规划算法缺乏稳定性和偏离最优解的问题,提出一种基于对比优化的RRT路径规划改进算法。算法在新一周期的环境下,通过对上一周期路径树进行剪枝和重新规划得到一条稳定的路径,同时利用基本RRT算法规划出一条新路径,通过对比两条路径得到较优解。仿真和真实机器人实验结果均表明,改进的算法提高了动态复杂环境下RRT路径规划的稳定性,并保证了规划的路径逼近最优解。

一种基于动态步长的AAPF-RRT*移动机器人路径规划新算法

针对改进快速搜索随机树(rapidly-exploring random tree,RRT*)算法中节点盲目扩展和收敛速率慢的问题,提出了一种基于RRT*的路径规划新算法。首先,通过改进相对距离势场法,提出了自适应人工势场(adaptive artificial potential field,AAPF)法,既克服了相对距离势场法中引力与斥力过大的问题,又解决了目标点不可达的问题。然后,将RRT*算法与AAPF法相结合,并将固定步长改为动态步长,从而既克服了RRT*算法中节点盲目扩展的问题,又显著提高了移动机器人路径规划效率和避障灵活性,同时兼顾路径平滑性。最后,基于MATLAB进行仿真,验证了所提算法的有效性和实用性。

融合动态窗与改进RRT的全位置机器人路径规划算法研究

针对传统RRT算法在无人车、无人船等自适应路径规划中的随机性导致树枝生长缺乏目标方向性问题,提出一种改进RRT算法与动态窗口相结合的混合算法,考虑其随机树生长过程中存在大量的冗余点,使得路径曲折、不平滑,基于子目标点选取策略研究一种过滤多余节点的算法;为了满足无人车、无人船行驶的安全性,建立安全阈值距离模型,避免与障碍物发生碰撞。对所提出的方法进行仿真实验,结果表明:改进的RRT算法能够在复杂的动态环境下生成有效的可行路径,与传统RRT算法相比较,它使搜索效率提高了43%,规划路径平滑度明显提升,能够实现动态环境中无人车、无人船在线实时路径规划。

基于改进RRT^(*)算法的动态路径规划策略

为了进一步解决移动机器人在动态环境下的路径规划问题,提出了一种改进的快速扩展随机树^(*)(RRT^(*))算法。首先,引入目标偏置采样以降低RRT^(*)算法的随机性,在静态环境下进行路径初规划。其次,在动态环境下应用该路径,并将初规划的路径作为路径缓存,当路径中出现新障碍物时,将无效路径进行裁剪并进行路径重规划,此时在进行节点采样时,有一定概率选择路径缓存中的点作为新节点,使得新路径更大程度上保持原有路径的趋势。最后,使用MATLAB分别进行初规划、重规划的仿真实验。与传统RRT^(*)算法进行了对比,新的改进算法使用的节点数量平均减少了43.19%。

基于综合改进RRT算法的无人机三维航路规划

针对复杂飞行环境下的无人机三维航路规划问题,提出了一种基于快速扩展随机树(RRT)的综合改进航路规划算法。根据实际复杂任务环境,建立三维任务空间模型,并考虑无人机性能约束;通过引入基于概率的启发式策略引导节点扩展方向,加入贪婪策略提高终点扩展方向节点生长速度;提出动态引力步长策略在保证节点搜索概率完备性的同时,降低节点扩展方向的随机性;设计平滑度优化方法改善规划航路曲折问题。仿真结果表明,综合改进RRT算法整体性能较好,具有良好的避障特性。

基于改进RRT算法的无人机航路规划与跟踪方法研究

为了使航路规划算法在三维动态环境下能够快速规划出较优可行航路,基于快速扩展随机树算法(RRT),对规划航路点进行了无人机飞行动力学约束,并且设计了局部航路动态优化策略。针对传统的航路跟踪控制律跟踪较为曲折的航线时跟踪误差较大的问题,通过将规划算法得出的姿态指令引入姿态控制回路的方式,提高了航路跟踪控制算法的快速性与准确性。在此基础上,搭建了无人机验证平台,利用该验证平台完成了无人机自主避障飞行试验,对算法的有效性进行了验证,并对算法性能进行了评估。

无人驾驶路径规划算法研究

快速扩展随机树(Rapidly-exploring Random Trees,RRT)是路径规划中常用到的算法之一,具有结构简单、搜索能力强、搜索效率高的优点,但也具有随机性强、算法路径不平滑的缺点。文章通过引入动态步长和增加平滑算法改进RRT算法。首先,改进动态步长,通过设置固定最大步长和最小步长,计算目标节点与障碍物的距离;其次,计算具体每一步的步长;最后,比较最小二乘法、二次指数平滑法、三次B样条曲线3种平滑算法的平滑性能,采用三次B样条曲线改进原RRT算法。通过MATLAB仿真软件对传统RRT算法和改进RRT算法进行仿真测试,得出改进后的RRT在路径搜索和路径平滑方面都有一定的提升。

基于强化学习的快速探索随机树特殊环境中路径重规划算法

针对移动机器人在未知的特殊环境(如U型、狭窄且不规则通道等)下路径规划效率低问题,本文提出一种强化学习(RL)驱动快速探索随机树(RRT)的局部路径重规划方法(RL-RRT).该方法利用Sarsa(λ)优化RRT的随机树扩展过程,既保持未知环境中RRT的随机探索性,又利用Sarsa(λ)缩减无效区域的探索代价.具体来说,在满足移动机器人运动学模型约束的同时,通过设定扩展节点的回报函数、目标距离函数和平滑度目标函数,缩减无效节点,加速探索过程,从而达到路径规划多目标决策优化的目标.仿真实验中,将本方法用于多种未知的特殊环境,实验结果显示出RL-RRT算法的可行性、有效性及其性能优势.

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

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

移动机器人实时采样路径重规划

针对传统采样规划算法因随机性强,在动态环境中重规划时路径质量差,抖动严重,实时优化效果不明显等问题,提出了一种利用反向生长最优快速搜索随机树的实时采样重规划算法DRT-RRT^(*)(Dynamic Real-Time RRT^(*))。引入基于三角不等式的剪枝策略对路径进行平滑处理以减少路径拐点;提出了组合采样策略和局部终点跳动策略,将优化目标由全局路径聚焦于机器人当前位置至最近路径拐点的局部路径段,实时对执行路径段进行修正,进而提高路径质量的稳定性;在路径重规划时仅对受影响的随机树枝进行修剪,并在随机树重新生长时引入了目标偏置采样策略,与组合采样策略共同作用,提高路径搜索速率和稳定程度;将DRT-RRT^(*)与RRT^(*)和增加了三角不等式剪枝策略的RRT^(*)-Pruning进行仿真对比分析,实验结果验证了DRT-RRT^(*)重规划的高效性和稳定性。

未知环境下移动机器人实时路径规划

针对在未知环境下实现移动机器人实时的路径规划问题,提出了一种将快速扩展随机树(RRT)算法与视野域自适应的滚动窗口相结合的路径规划算法。该方法实时获取滚动窗口内的局部环境信息,根据环境的变化,滚动窗口视野域进行自适应调整,通过分析滚动窗口内传感器获取的信息,结合改进后的RRT算法筛选出可行的路径,控制移动机器人到达子目标点,在此过程中动态监测规划好的路径,确保路径合理,并重复上述过程,直至到达目标区域。实验对比分析表明,该方法能实时并有效实现未知环境下移动机器人的路径规划。

基于狭窄通道路径树的快速航路规划算法

针对无人机在障碍间存在狭窄通道的城市环境中进行低空航路规划的问题,根据障碍之间的空间几何关系确定障碍之间的狭窄通道,再综合所有狭窄通道生成复杂环境中的狭窄通道路径树。设计了结合狭窄通道路径树的双向快速扩展随机树(Rapidly-exploring Random Tree,RRT)算法,在两棵搜索树的扩展过程中,通过判断搜索树与狭窄通道路径树的位置关系,将狭窄通道路径树添加到搜索树上,实现搜索树在狭窄通道中的快速扩展,减少两棵搜索树的无用扩展,提升航路树生成的速度。仿真结果表明,该方法能够解决无人机在存在狭窄通道的复杂环境中进行快速有效航路规划的问题。