复杂低空物流无人机路径规划

doi:10.13700/j.bh.1001-5965.2019.0455

北京航空航天大学学报 ›› 2020, Vol. 46 ›› Issue (7): 1275-1286.doi: 10.13700/j.bh.1001-5965.2019.0455

复杂低空物流无人机路径规划

张启钱, 许卫卫, 张洪海, 邹依原, 陈雨童

南京航空航天大学民航学院, 南京 211106

收稿日期:2019-08-26 发布日期:2020-07-18
通讯作者: 张洪海 E-mail:honghaizhang@nuaa.edu.cn
作者简介:张启钱男,博士,副研究员,硕士生导师。主要研究方向:交通运输规划与管理。
张洪海男,博士,教授,博士生导师。主要研究方向:交通运输规划与管理。
基金资助:
国家自然科学基金（61573181，71971114）；南京航空航天大学研究生创新基地（实验室）开放基金（kfjj20180726）

Path planning for logistics UAV in complex low-altitude airspace

ZHANG Qiqian, XU Weiwei, ZHANG Honghai, ZOU Yiyuan, CHEN Yutong

College of Civil Aviation, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China

Received:2019-08-26 Published:2020-07-18
Supported by:
National Natural Science Foundation of China (61573181,71971114); Nanjing University of Aeronautics and Astronautics Graduate Innovation Base (Lab) Open Fund (kfjj20180726)

摘要/Abstract

摘要： 针对复杂低空物流无人机路径规划问题，考虑空域环境、运输任务等内外限制，以飞行时间、能耗及危险度最小为目标函数，建立多限制条件物流无人机路径规划模型，设计启发算法以快速解算路径。采用栅格法对规划环境表征，引入物流无人机性能约束确保路径可飞。针对A^*算法存在的问题及物流无人机航空运输特色，引入栅格危险度因子、货物质量惩罚系数，增加飞行时间、能耗等代价以提升避障能力、降低成本。为匹配所提启发算法解算效率与精度，采用动态加权法对函数赋权。为筛除冗余路径点及保证平稳飞行，采用双向交叉判断法等对原路径优化平滑。为验证所提路径规划模型及启发算法的有效性，对比4种算法规划结果，分析栅格粒度大小与代价权重值对结果的影响。在既定的运输环境及物流无人机性能约束下，研究结果表明：所提算法与A^*算法相比，保证了物流无人机飞行安全、能耗少，将飞行时间由406 s降至386 s，降低了5%；飞行路径点数为129个、栅格危险度因子为11.69，降低了姿态改变次数，保证了运输安全；当栅格粒度大小为5 m，代价权重值为0.4、0.1、0.5时，采用所提算法规划的路径最佳。

关键词: 航空运输, 路径规划, A^*算法, 物流无人机, 复杂低空, 栅格危险度, 双向交叉判断法

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.

Key words: air transportation, path planning, A^* algorithm, logistics UAV, complex low-altitude airspace, grid risk, bidirectional cross judgment method

中图分类号:

V279.3

张启钱, 许卫卫, 张洪海, 邹依原, 陈雨童. 复杂低空物流无人机路径规划[J]. 北京航空航天大学学报, 2020, 46(7): 1275-1286.

ZHANG Qiqian, XU Weiwei, ZHANG Honghai, ZOU Yiyuan, CHEN Yutong. Path planning for logistics UAV in complex low-altitude airspace[J]. Journal of Beijing University of Aeronautics and Astronautics, 2020, 46(7): 1275-1286.

参考文献

[1] GOODCHILD A,TOY J.Delivery by drone:An evaluation of unmanned aerial vehicle technology in reducing CO₂,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.
[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.
[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.ZHENG 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).
[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.
[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.
[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.
[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.
[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.
[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).

复杂低空物流无人机路径规划

Path planning for logistics UAV in complex low-altitude airspace

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	崔恺, 曾国奇, 林伟, 全权. 一种基于图论的机场空域无人机流量控制方法[J]. 北京航空航天大学学报, 2020, 46(5): 978-987.
[2]	魏彤, 龙琛. 基于改进遗传算法的移动机器人路径规划[J]. 北京航空航天大学学报, 2020, 46(4): 703-711.
[3]	郑丽君, 胡荣, 张军峰, 朱佳琳. 高峰时段下离港航空器绿色滑行策略设计与评价[J]. 北京航空航天大学学报, 2019, 45(11): 2320-2326.
[4]	张立志, 陈殿生, 刘维惠. 基于混合地图的护理机器人室内导航方法[J]. 北京航空航天大学学报, 2018, 44(5): 991-1000.
[5]	张竞, 吴宇, 屈香菊. 舰载机牵引系统路径规划方法[J]. 北京航空航天大学学报, 2018, 44(10): 2125-2133.
[6]	张青松, 曹文杰, 罗星娜, 姜乃文. 基于多米诺效应的锂离子电池热释放速率分析方法[J]. 北京航空航天大学学报, 2017, 43(5): 902-907.
[7]	王晓亮, 马亚冰, 王鹏, 吴仁彪. 复杂多约束条件通航飞行垂直剖面规划方法[J]. 北京航空航天大学学报, 2016, 42(6): 1126-1133.
[8]	张涛, 居鹤华. 基于SA^*的CE-3巡视器机械臂就位探测任务规划[J]. 北京航空航天大学学报, 2016, 42(6): 1286-1294.
[9]	徐肖豪, 孟令航, 赵嶷飞. 基于几何方法的洲际航空编队飞行路径规划[J]. 北京航空航天大学学报, 2015, 41(7): 1155-1164.
[10]	刘洋, 章卫国, 李广文, 史静平. 动态环境中的无人机路径规划方法[J]. 北京航空航天大学学报, 2014, 40(2): 252-256.
[11]	岳荣刚, 王少萍. 基于混合整数线性规划的爬壁机器人路径规划[J]. 北京航空航天大学学报, 2013, (6): 792-797.
[12]	高庆吉, 王磊, 牛国臣, 王维娟. 基于目标导向的连续型机器人路径规划[J]. 北京航空航天大学学报, 2013, 39(11): 1486-1490.
[13]	郑磊, 张军, 薛瑞. 基于相似性传播聚类算法的机会信号选择[J]. 北京航空航天大学学报, 2012, (9): 1230-1234,1266.
[14]	赵振宇, 卢广山, 廖沫, 陈宗基. 基于DTC和GPGP的多UCAV任务规划方法[J]. 北京航空航天大学学报, 2011, 37(3): 305-310.
[15]	高彬, 毛士艺, 孙进平. 基于RGPO的编队ECAVs协同航迹欺骗[J]. 北京航空航天大学学报, 2011, 37(11): 1343-1346.