考虑误差校正点的无人机航迹规划模型与算法  

Model and algorithm of unmanned aerial vehicle path planning considering error correction points

作　　者：李珍萍[1] 刘嵘 陈星艺 徐冉 邢立宁 LI Zhenping;LIU Rong;CHEN Xingyi;XU Ran;XING Lining(School of Information,Beijing Wuzi University,Beijing 101149,China;School of Logistics and Transportation,Central South University of Forestry and Technology,Changsha 410018,China)

机构地区：[1]北京物资学院信息学院,北京101149 [2]中南林业科技大学物流与交通学院,湖南长沙410018

出　　处：《计算机集成制造系统》2022年第4期990-1000,共11页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(71771028);北京市自然科学基金资助项目(9212004,Z180005);北京市属高校高水平科研创新团队建设资助项目(IDHT20180510);北京市智能物流协同创新中心开放资助项目(BILSCIC-2019KF-25);北京市科技创新服务能力建设—高精尖学科建设资助项目。

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

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

分 类 号：TP39[自动化与计算机技术—计算机应用技术]