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

Sampling Space Reduction-based UAV Online Path Planning Algorithm in Complex Low Altitude Environments

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

The unmanned aerial vehicle （UAV） online path planning in low altitude complex environments is complicated due to the planning spaces of densely distributed obstacles with various shapes, narrow passages for the solution path to pass through, and uncertain information. For solving this problem, a sampling space reduction-based algorithm is proposed to reduce the number of collision detection calls, accelerate the path-search process and decrease the path cost. To deal with the over-reduction problem existing in the dynamic domain rapidly-exploring random tree （DDRRT） method, the algorithm makes the space reduction gradually by employing a cost model. Thus the planning tree can extend rapidly and efficiently under the guidance of the reduction. It also promotes the near neighbors searching speed by a new storage structure for tree nodes and a novel near neighbor searching approach. Indexes are built based on the density of tree nodes to construct the storage structure composed by multiple K-dimensional trees （Kd trees）. Simulation results certify that our algorithm can ensure the rationality of the sampling space reduction and improve the efficiency of path planning and the ability of path-searching in passages, as compared to the DDRRT.