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

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