-
摘要:
针对复杂低空物流无人机路径规划问题，考虑空域环境、运输任务等内外限制，以飞行时间、能耗及危险度最小为目标函数，建立多限制条件物流无人机路径规划模型，设计启发算法以快速解算路径。采用栅格法对规划环境表征，引入物流无人机性能约束确保路径可飞。针对A*算法存在的问题及物流无人机航空运输特色，引入栅格危险度因子、货物质量惩罚系数，增加飞行时间、能耗等代价以提升避障能力、降低成本。为匹配所提启发算法解算效率与精度，采用动态加权法对函数赋权。为筛除冗余路径点及保证平稳飞行，采用双向交叉判断法等对原路径优化平滑。为验证所提路径规划模型及启发算法的有效性，对比4种算法规划结果，分析栅格粒度大小与代价权重值对结果的影响。在既定的运输环境及物流无人机性能约束下，研究结果表明：所提算法与A*算法相比，保证了物流无人机飞行安全、能耗少，将飞行时间由406 s降至386 s，降低了5%；飞行路径点数为129个、栅格危险度因子为11.69，降低了姿态改变次数，保证了运输安全；当栅格粒度大小为5 m，代价权重值为0.4、0.1、0.5时，采用所提算法规划的路径最佳。
Abstract:To solve the problem of path planning for logistics UAV in the complex low-altitude airspace, internal and external restrictions such as airspace environment and transportation tasks were considered. Taking minimize flight time, energy consumption and path risk as the objective function, the multi-restricted transportation path planning model of logistics UAV was established. To plan the path quickly, an improved heuristic algorithm was designed. The grid method was used to model the environment. The performance constraints of UAV were introduced to ensure that UAV can follow the path. To solve the existing problems of the original algorithm and indicate the characteristics of logistics UAV air transportation, the concepts of grid risk and cargo weight penalty coefficient were introduced, and flight time and energy consumption were calculated to improve the obstacle avoidance ability and reduce the cost. The dynamic weighting method was used to assign the weight of the function to match the efficiency and accuracy of the algorithm. In order to delete redundant path points and ensure smooth flight, bidirectional cross judgment method was used to optimize and smooth the original path. In order to verify the effectiveness of the model and the algorithm, the results of four algorithms were compared. Meanwhile, the influence of grid length and cost weight on planning results was analyzed. With the constraints of the assumed environment and UAV performance, the study results indicate that, compared with the original algorithm, the proposed algorithm ensures the flight safety of logistics UAV with less energy consumption, and reduces the flight time from 406 s to 386 s, which is reduced by 5%. The number of flight path points is 129 and the grid risk is 11.69, which reduces the number of attitude changes and ensures the safety of transportation. When the grid length is 5 m and the cost weight is 0.4, 0.1 and 0.5, the path planned by the proposed algorithm is optimal.
-
表 1 环境数据
Table 1. Environmental data
高程数据/m 1 2 3 4 … 1 34.52 34.54 34.47 34.65 … 2 34.96 35.00 34.56 34.74 … 3 35.10 35.10 34.73 34.88 … 4 35.09 35.10 34.87 34.99 … ⋮ 
下载: 导出CSV
表 2 仿真参数
Table 2. Simulation parameters
参数 数值 最远航程[18]Lmax/m 2 865 最大转弯角[18]βmax/rad π/2 飞行高度最大值[18]Hmax/m 120 飞行时间权重系数α1 0.3 能耗权重系数α2 0.4 栅格危险度因子权重系数α3 0.3 单位距离垂直运动能耗r/(J·m-1) 340 单位距离水平运动能耗λ/(J·m-1) 106 惩罚系数最大值[7]τmax 3 起始派送点起飞时刻t1/h 0 起始点S坐标/m (150, 150, 50) 栅格粒度大小l/m 5 最小路径段长度[18]lmin/m 5 最大爬升角[18]μmax/rad π/2 总电能Etotal/kJ 307.2 实际货物载重Q/kg 3 货物质量惩罚系数τ(Q) 1.75 飞行速度v/(m·s-1) 5 gQ(n)权重系数最小值[22]wmin 0.5 gQ(n)权重系数最大值[22]wmax 0.8 最大货物载重[7]Qmax/kg 8 目的派送点最晚时刻t2/h 0.16 目的点G坐标/m (1 100, 1 100, 40) 注：参数右上角标注文献表明该参数值参考对应文献中参数值赋值方法进行设置，应按实际应用而定。
下载: 导出CSV
表 3 A*算法和本文算法路径规划结果对比
Table 3. Comparison of path planning results between A* algorithm and proposed algorithm
参数 A*算法 本文算法 路径点数 226 129 路径航程/m 2 030 1 930 能耗/kJ 236.2 204.5 飞行时间/s 406 386 规划时间/s 5.31 4.77
下载: 导出CSV
表 4 不同算法路径规划结果对比
Table 4. Comparison of path planning results among different algorithms
参数 人工势场法 未优化及平滑的改进算法 本文算法 规划时间/s 30.85 4.48 4.77 路径点数 202 258 129 路径航程/m 2 230 2 050 1 930 栅格危险度因子 23.73 17.15 11.69
下载: 导出CSV
表 5 栅格粒度大小对路径规划结果的影响
Table 5. Influence of grid length on path planning results
栅格粒度大小/m 路径点数 路径航程/m 能耗/kJ 栅格危险度因子 5 129 1 930 204.5 11.69 10 137 1 980 209.8 20.88 15 128 1 950 206.7 19.34 20 133 1 970 208.4 17.47
下载: 导出CSV
表 6 代价权重值对规划结果的影响
Table 6. Influence of cost weight on planning results
实验
组别代价权重值 路径
点数路径
航程/m能耗/kJ 栅格危险
度因子α1 α2 α3 1 0 0.5 0.5 141 2 010 220.1 21.58 2 0.1 0.4 0.5 128 1 950 206.7 19.34 3 0.2 0.3 0.5 135 1 990 210.3 10.50 4 0.3 0.2 0.5 124 1 930 209.5 9.53 5 0.4 0.1 0.5 114 1 930 211.6 6.31 6 0.5 0 0.5 109 2 010 227.1 5.47
下载: 导出CSV
-
[1] GOODCHILD A, TOY J.Delivery by drone:An evaluation of unmanned aerial vehicle technology in reducing CO2, emissions in the delivery service industry[J].Transportation Research Part D:Transport and Environment, 2017, 61:58-67. [2] ROBERGE V, TARBOUCHI M, LABONTE G.Fast genetic algorithm path planner for fixed-wing military UAV using GPU[J].IEEE Transactions on Aerospace and Electronic Systems, 2018, 54(5):2105-2117. doi: 10.1109/TAES.2018.2807558 [3] WU Z Y, LI J H, ZUO J M, et al.Path planning of UAVs based on collision probability and Kalman filter[J].IEEE Access, 2018, 6:34237-34245. doi: 10.1109/ACCESS.2018.2817648 [4] PAPACHRISTOS C, KAMEL M, POPOVIĆ M, et al.Autonomous exploration and inspection path planning for aerial robots using the robot operating system[M]//KOUBAA A.Robot operating system(ROS).Berlin:Springer, 2018, 778:67-111. [5] 王宇, 陈海涛, 李煜, 等.基于Grid-GSA算法的植保无人机路径规划方法[J].农业机械学报, 2017, 48(7):29-37.WANG Y, CHEN H T, LI Y, et al.Path planning method based on Grid-GSA for plant protection UAV[J].Transactions of the Chinese Society for Agricultural Machinery, 2017, 48(7):29-37(in Chinese). [6] 郑翔.无人机物流业发展的法律障碍和立法思考[J].北京交通大学学报(社会科学版), 2018, 17(1):136-142. doi: 10.3969/j.issn.1672-8106.2018.01.017ZHENG X.The legal obstacles and countermeasures for unmanned aircraft logistics development[J].Journal of Beijing Jiaotong University(Social Sciences Edition), 2018, 17(1):136-142(in Chinese). doi: 10.3969/j.issn.1672-8106.2018.01.017 [7] BYUNG D S, KYUNGSU P, JONGHOE K.Persistent UAV delivery logistics:MILP formulation and efficient heuristic[J].Computers & Industrial Engineering, 2018, 120:418-428. [8] BOUALEM R, CHRISTIAN W, GERALD R.A drone fleet model for last-mile distribution in disaster relief operations[J].International Journal of Disaster Risk Reduction, 2018, 28:107-112. doi: 10.1016/j.ijdrr.2018.02.020 [9] SCOTT J E, SCOTT C H.Drone delivery models for healthcare[J].International Journal of Healthcare Information Systems and Informatics, 2018, 13(3):20-34. doi: 10.4018/IJHISI.2018070102 [10] 周浪.农村电商物流配送"配送车+无人机"路径优化研究[D].武汉: 武汉理工大学, 2017.ZHOU L.Research on the route optimization of rural E-commercial distribution based on 'vehicle-unmanned aircraft'[D].Wuhan: Wuhan University of Technology, 2017(in Chinese). [11] 翁丹宁.无人机物流配送的主要影响因素分析[J].企业改革与管理, 2015(8):170.WENG D N.Analysis on the main influencing factors of UAV logistics distribution[J].Enterprise Reform and Management, 2015(8):170(in Chinese). [12] 吴永鑫.物流无人机在中国农村电商物流市场应用研究[D].深圳: 深圳大学, 2017.WU Y X.The research of the application of the logistics unmanned aerial vehicle in the China's rural electricity supplier logistics[D].Shenzhen: Shenzhen University, 2017(in Chinese). [13] JIANG X W, ZHOU Q, YE Y.Method of task assignment for UAV based on particle swarm optimization in logistics[C]//Proceedings of the 2017 International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence.New York: ACM, 2017: 113-117. [14] DORLING K, HEINRICHS J, MESSIER G G, et al.Vehicle routing problems for drone delivery[J].IEEE Transactions on Systems, Man, and Cybernetics:Systems, 2016, 47(1):70-85. [15] TORABBEIGI M, LIM G J, KIM S J.Drone delivery scheduling optimization considering payload-induced battery consumption rates[J].Journal of Intelligent & Robotic Systems, 2020, 97(3):471-487. doi: 10.1007/s10846-019-01034-w [16] GOSS K, MUSMECI R, SILVESTRI S.Realistic models for characterizing the performance of unmanned aerial vehicles[C]//201726th International Conference on Computer Communication and Networks(ICCCN).Piscataway: IEEE Press, 2017: 1-9. [17] ABEYWICKRAMA H V, JAYAWICKRAMA B A, HE Y, et al.Comprehensive energy consumption model for unmanned aerial vehicles, based on empirical studies of battery performance[J].IEEE Access, 2018, 6:58383-58394. doi: 10.1109/ACCESS.2018.2875040 [18] 李月茹.四旋翼无人机航迹规划算法研究[D].沈阳: 沈阳航空航天大学, 2018.LI Y R.The algorithm study of four-rotor UAV route planning[D].Shenyang: Shenyang Aerospace University, 2018(in Chinese). [19] 徐晨晨, 廖小罕, 岳焕印, 等.基于改进蚁群算法的无人机低空公共航路构建方法[J].地球信息科学学报, 2019, 21(4):570-579.XU C C, LIAO X H, YUE H Y, et al.Construction of a UAV low-altitude public air route based on an improved ant colony algorithm[J].Journal of Geo-Information Science, 2019, 21(4):570-579(in Chinese). [20] 任逸晖.一种新的4D航路规划算法及其仿真[D].西安: 西安电子科技大学, 2017.REN Y H.A new kind 4D route planning algorithm and simulation[D].Xi'an: Xidian University, 2017(in Chinese). [21] KELLER J, THAKUR D, LIKHACHEV M, et al.Coordinated path planning for fixed-wing UAS conducting persistent surveillance missions[J].IEEE Transactions on Automation Science and Engineering, 2017, 14(1):17-24. doi: 10.1109/TASE.2016.2623642 [22] 刘源, 王海泉.基于理论最短距离变权重A*算法的路径规划[J].计算机测量与控制, 2018, 26(4):175-178.LIU Y, WANG H Q.Path planning based on theoretical minimum distance of A* algorithm[J].Computer Measurement & Control, 2018, 26(4):175-178(in Chinese). -
下载:
点击查看大图
计量
- 文章访问数: 2548
- HTML全文浏览量: 595
- PDF下载量: 482
- 被引次数: 0
