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

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

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

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

基于改进蚁群算法的三维航迹规划

针对蚁群算法在无人机（UAV）三维航迹规划中存在的收敛速度慢、空间复杂度高的缺点,提出了一种基于改进蚁群算法的无人机（UAV）三维航迹规划方法。该方法改进了局部搜索策略、初始信息素调整因子并在启发函数中加入了路径偏移因子,从而降低了航迹搜索空间的复杂度,提高了算法的搜索效率和收敛速度。在利用DEM数字高程数据建立的搜索空间中,该算法与现有算法相比,规划航迹缩短约24.08%,运行时间减少约11.56%,表明改进蚁群算法在无人机（UAV）三维航迹规划中的可行性和有效性。     

基于局部规划的三维航迹规划方法

研究飞行器航迹是选择最优航线问题,针对三维航迹规划中搜索空间大、计算时间长的问题,为缩短搜索时间,获得最优航迹,提出了一种基于A<'*>算法并结合局部规划的三维航迹规划方法.方法首先对A<'*>算法中的当前待扩展节点在局部规划空间中确定几个最有希望的扩展节点,再将其与A<'*>算法相结合,最后对局部规划算法过程中的不足,通过地形标记和加入树搜索深度惩罚做出改进,有效地减小了搜索空间,缩短了搜索时间,并在搜索过程中充分利用地形信息,使算法生成的航迹能够避开大的地形障碍,而且能够充分利用有利的地形.在实际地形数据中进行的实验表明方法能快速、有效地规划出理想优化的航迹.     

基于改进粒子群算法的UAV航迹规划方法

结合当前无人机集群发展趋势,针对航迹规划算法和策略问题开展研究,在分析经典粒子群算法和传统航迹规划方法基础上,提出了一种基于改进粒子群算法的航迹规划方法,将无人机航迹规划分为整体航迹规划和节点间航迹规划两部分,针对两部分对于搜索速度和解的精度的不同需求,结合环境模型及约束条件,分别设计粒子群航迹规划算法的评价函数;对于节点间粒子群航迹规划,通过设计分段式惯性权重调整公式改进粒子群算法,在保证了算法的搜索速度的同时,提高了航迹规划解的精度。通过仿真验证了该方法的正确性和可行性,横向对比其他算法策略分析了该方法的优越性。最后在算法自主实时性方向上对于后续的工作开展提出了期望。     

无人机低空突防航迹规划算法研究

结合低空突防中的地形跟随/地形回避/威胁回避( TF/TA2)技术,在分析无人机各种机动性能以及A-Star算法的基础上,提出了一种基于局部空间搜索最优节点的方法,将A-Star算法进行稀疏化处理;设计了更贴近实际的航迹代价计算方法,将算法与数字地形相结合进行仿真计算.仿真结果表明,设计的航迹规划算法兼顾了算法效率、航...     

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

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

基于改进RRT算法的UAV航迹规划与优化研究

分析步长、搜索次数对UAV航迹生成的影响,给出一种改进RRT算法。结合目标信息给出启发因子、优话采样节点选择方法、选取合适的启发概率等方法,解决了扩展树生长过程中随机性较大的问题,提高了全局搜索能力和搜索速度,同时考虑局部搜索精度。针对航迹随机化造成的航迹不够优化的问题,提出一种航迹迭代优化方法。仿真结果表明:该算法和优化方法具有较快的收敛速度和更短的搜索时间;迭代优化方法减少了冗余规划点,缩短了规划航迹,提高了航迹规划效率。     

基于改进A*算法的无人机航迹规划

在无人机航迹规划问题的研究中,针对在执行飞行任务前,需要根据所经区域内已知的地形、地貌、障碍和威胁等信息以及飞机本身机动能力的限制计算出飞行航迹, 并根据规划出的航迹完成飞行任务.能准确识别起始点到目标航路,提出了一种基于改进A*算法的无人机航迹规划方法,将无人机自身的性能和飞行任务结合到A*算法中去,在节点的搜索过程中解决了A*算法大空间搜索耗时多的问题.通过简单的路径消减算法去除不必要的航迹点,使得规划出来的航迹能够最大程度上满足无人机的运动特性.仿真结果表明采用的方法计算速度快并且规划达到最优性能.     

面向UAV的三维空间快速路径规划算法

无人机、无人水下机器人等工作在三维空间中的无人飞行器在进行路径规划时采用的路径规划算法多数为RRT*算法，但RRT*算法存在收敛速度较慢、迭代次数多、采样点利用率低、需要频繁进行碰撞检测等问题，针对现有算法采样的不足，提出双向自由化生长树算法（B-SOGT*）。该算法采用双向搜索、双引力场、试探性弹性扩张的方法来实现无人机在三维空间中的路径规划。双向搜索分别以起始点和目标点为根节点，构造出2棵随机树同时进行空间搜索，这样的方式提高了搜索效率；双引力场是分别以2颗随机树的根节点为中心生成的引力场，在引力场的作用下采样效率得到提升；试探性弹性扩张方法在生成路径时，引入父节点重选机制，并且去掉碰撞检测过程，提高了算法计算速度。仿真验证表明，B-SOGT*算法在取消碰撞检测过程后，拥有收敛速度更快、路径质量更优、迭代次数更少的优势。     

基于改进RRT*FN算法的机器人路径规划

针对固定节点数的渐近最优快速扩展随机数算法(RRT*FN)精度低、收敛到最优值速度慢等问题,提出一种改进的RRT*FN路径规划算法,并用于解决二维静态环境下的移动机器人全局路径规划问题.首先,改进算法使用与RRT*FN算法相同的均匀采样方法进行路径搜索,当搜索到一条初始路径时,在之后的路径规划中使用启发式采样方法.在之后的每次迭代中,改进算法在椭圆子集采样方法与路径点邻近区域采样方法中随机选择一种作为当前采样方法.然后,当树中的总节点数达到预设值时,对树中的叶子结点采用加权方法进行删除.通过给予采样区域内的叶子结点更高的权重,从而将采样区域外的叶子结点以更高概率删除,得以保留树中的高性能节点,以便提高算法性能.最后,通过仿真实验验证改进算法的有效性.     

室内场景下应用拓扑结构的高效路径规划算法

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

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.      

基于B-RRT*FND算法的移动机器人路径规划

针对RRT*FN算法获取路径解的速度慢,且无法应用于动态环境等问题,提出固定节点数的动态双向渐近最优快速随机扩展树算法(bidrectional RRT* fix-node dynamic, B-RRT*FND),用于解决移动机器人在二维空间内快速实时获取无碰撞路径的问题.所提出算法基于RRT*FN算法,采用双向贪婪搜索方法加快路径搜索速度,解决单向RRT算法由于随机采样的盲目性造成的搜索速度慢、在狭窄环境下难以搜索到解的问题;利用固定节点算法在规划过程中不占用过多计算量的特点,在路径迭代优化过程中,实时更新地图信息,并对被破坏的原始路径进行修复重连,以完成算法的动态规划.将所提出算法与RRT、RRT*FN等算法在3种环境下进行对比仿真,验证结果表明,所提出算法在规划速度、路径解长度以及动态规划性能方面具有较好效果.     

一种Halton序列的HDRRT移动机器人融合规划算法

针对标准快速扩展随机树(RRT)算法采用伪随机序列导致采样点分布不均、不合理,且移动机器人从起始点到目标点路径有冗余路段及冗余节点的问题,提出HDRRT (halton & dijkstra & rapidly exploring random tree)算法,该算法采用采样点分布均匀性好的Halton序列进行采样,并利用候选点集策略对节点进行筛选,以剔除冗余节点;同时该算法采用改进的Dijkstra算法提取原始路径关键节点,以减少路径冗余路段;在此基础上采用3次B样条曲线对路径作平滑处理.经Matlab联合ROS系统仿真结果表明, HDRRT算法相对于Bias-RRT和标准RRT算法具有快速性,稳定规划出最短以及平滑路径等优点.     

A Learning-based Multi-RRT Approach for Robot Path Planning in Narrow Passages

As an important class of sampling-based path planning methods, the Rapidly-exploring Random Trees (RRT) algorithm has been widely studied and applied in the literature. In RRT, how to select a tree to extend or connect is a critical factor, which will greatly influence the efficiency of path planning. In this paper, a novel learning-based multi-RRTs (LM-RRT) approach is proposed for robot path planning in narrow passages. The LM-RRT approach models the tree selection process as a multi-armed bandit problem and uses a reinforcement learning algorithm that learns action values and selects actions with an improved ε-greedy strategy (ε _t -greedy). Compared with previous RRT algorithms, LM-RRT can not only enhance the local space exploration ability of each tree, but also guarantee the efficiency of global path planning. The probabilistic completeness and combinatory optimality of LM-RRT are proved based on the geometric characteristics of the configuration space. Simulation and experimental results show the effectiveness of the proposed LM-RRT approach in single-query path planning problems with narrow passages.     

改进RRT算法陷阱空间下的无人机航迹规划

针对大部分航迹规划算法在陷阱空间下,存在规划时间长、成功率低的问题,提出了一种改进RRT算法。通过将人与RRT算法相结合,由人设置虚拟目标点,引导航迹搜索走出陷阱空间;同时对节点扩展进行优化,保证航迹搜索在可行域内;并设置快速收敛策略,删除冗余节点,使航迹搜索速度加快。最后,通过仿真验证表明,该方法在陷阱空间规划中具有良好的效果,可快速规划可行航迹。     

目的驱动最短路径树的快速算法

通过分析目的驱动最短路径生成树算法DDSP(Destination-drivenShortestPath)的节点搜索过程,提出一种以较小的存储空间为代价,减少DDSP算法在搜索当前节点、父节点和待处理节点时搜索空间的快速算法FDDSP(Fastdestination-driv-enshortestpath)。随机网络模型的仿真结果表明,FDDSP算法生成的多播树与DDSP算法相同,但FDDSP算法的效率更高。     

目标偏置双向RRT*算法的机器人路径规划

针对RRT*和B-RRT*算法在较复杂环境下路径规划时,存在搜索时间长、采样效率低和规划路径曲折的问题,提出一种目标偏置双向快速扩展随机树算法——GBB-RRT*(goal biased bidirectional RRT*).该算法每次迭代中两棵随机树都进行扩展,一次迭代能生成两个新节点,加快扩展速度.然后引入目标偏...