Abstract: Path planning problem of Unmanned Aerial Vehicle(UAV)with multiple horizontal and vertical error correction points in the navigation area was studied.Under the threshold constraint of cumulative error,a mixed integer programming model of UAV path planning problem was established to minimize the total path distance.Considering that each error correction point could only revise the accumulated error of one specific direction,and the accumulated error before and after correction did not meet the linear relationship,based on the multi-dimensional labeling algorithm and the pulse algorithm,a two-stage exact algorithm was designed to solve the model.An initial feasible solution was obtained by multi-dimensional labeling algorithm,and the objective function value was taken as the upper bound of the optimal value.Based on the constraints of the model and the upper bound,three judge rules for path extension were given,and the improved pulse algorithm was designed to obtain the global optimal solution.The efficiency of the algorithm was verified by simulation on some instances,which provided a theoretical basis for solving UAV path planning problem in reality.

Key words: unmanned aerial vehicle, path planning, error correction, mixed integer programming, multi-dimensional label algorithm, pulse algorithm

摘要： 针对飞行区域内有若干个水平和垂直误差校正点的无人机航迹规划问题,在满足累积误差阈值约束的前提下,以总航迹最短为目标,建立了混合整数规划模型。考虑到每个误差校正点只能校正一个方向的累积误差,且校正前后的累积误差不满足线性关系,为了快速求出问题的精确最优解,基于多维标号算法和脉冲算法设计了两阶段算法。首先利用多维标号算法求出初始可行解,并将其作为最优解的上界;然后利用模型的约束条件和目标函数值上界,构造3种子路径扩展判断准则,并基于3种准则设计了改进的脉冲算法,求出全局最优解。通过模拟计算,验证了两阶段算法求解无人机航迹规划问题的快速有效性,为解决无人机航迹规划问题提供了理论依据。

关键词: 无人机, 航迹规划, 误差校正, 混合整数规划, 多维标号法, 脉冲算法