留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

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

张启钱, 许卫卫, 张洪海, 等 . 复杂低空物流无人机路径规划[J]. 北京航空航天大学学报, 2020, 46(7): 1275-1286. doi: 10.13700/j.bh.1001-5965.2019.0455
引用本文: 张启钱, 许卫卫, 张洪海, 等 . 复杂低空物流无人机路径规划[J]. 北京航空航天大学学报, 2020, 46(7): 1275-1286. doi: 10.13700/j.bh.1001-5965.2019.0455
ZHANG Qiqian, XU Weiwei, ZHANG Honghai, et al. Path planning for logistics UAV in complex low-altitude airspace[J]. Journal of Beijing University of Aeronautics and Astronautics, 2020, 46(7): 1275-1286. doi: 10.13700/j.bh.1001-5965.2019.0455(in Chinese)
Citation: ZHANG Qiqian, XU Weiwei, ZHANG Honghai, et al. Path planning for logistics UAV in complex low-altitude airspace[J]. Journal of Beijing University of Aeronautics and Astronautics, 2020, 46(7): 1275-1286. doi: 10.13700/j.bh.1001-5965.2019.0455(in Chinese)

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

doi: 10.13700/j.bh.1001-5965.2019.0455
基金项目: 

国家自然科学基金 61573181

国家自然科学基金 71971114

南京航空航天大学研究生创新基地(实验室)开放基金 kfjj20180726

详细信息
    作者简介:

    张启钱 男, 博士, 副研究员, 硕士生导师。主要研究方向:交通运输规划与管理

    张洪海 男, 博士, 教授, 博士生导师。主要研究方向:交通运输规划与管理

    通讯作者:

    张洪海. E-mail:honghaizhang@nuaa.edu.cn

  • 中图分类号: V279.3

Path planning for logistics UAV in complex low-altitude airspace

Funds: 

Foundation items: National Natural Science Foundation of China 61573181

Foundation items: National Natural Science Foundation of China 71971114

Nanjing University of Aeronautics and Astronautics Graduate Innovation Base (Lab) Open Fund kfjj20180726

More Information
  • 摘要:

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

     

  • 图 1  规划环境栅格化

    Figure 1.  Grid of planning environment

    图 2  栅格危险度因子计算

    Figure 2.  Calculation of grid risk

    图 3  双向交叉判断法

    Figure 3.  Bidirectional cross judgment method

    图 4  本文算法流程

    Figure 4.  Flowchart of proposed algorithm

    图 5  物流无人机路径规划环境

    Figure 5.  Environment for path planning of logistics UAV

    图 6  物流无人机路径规划结果

    Figure 6.  Path planning results of logistics UAV

    图 7  不同算法路径规划结果

    Figure 7.  Path planning results of different algorithms

    图 8  栅格粒度大小的影响

    Figure 8.  Influence of grid length

    图 9  代价权重值的影响

    Figure 9.  Influence of cost weight

    表  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. https://depts.washington.edu/sctlctr/research/publications/delivery-drone-evaluation-unmanned-aerial-vehicle-technology-reducing-co2
    [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. http://d.old.wanfangdata.com.cn/Periodical/nyjxxb201707004

    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). http://d.old.wanfangdata.com.cn/Periodical/nyjxxb201707004
    [6] 郑翔.无人机物流业发展的法律障碍和立法思考[J].北京交通大学学报(社会科学版), 2018, 17(1):136-142. doi: 10.3969/j.issn.1672-8106.2018.01.017

    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). 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. https://www.sciencedirect.com/science/article/pii/S0360835218302146
    [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. http://d.old.wanfangdata.com.cn/Periodical/qyggygl201508158

    WENG D N.Analysis on the main influencing factors of UAV logistics distribution[J].Enterprise Reform and Management, 2015(8):170(in Chinese). http://d.old.wanfangdata.com.cn/Periodical/qyggygl201508158
    [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. https://ieeexplore.ieee.org/document/7513397/
    [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. http://d.old.wanfangdata.com.cn/Periodical/dqxxkx201904010

    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). http://d.old.wanfangdata.com.cn/Periodical/dqxxkx201904010
    [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. http://d.old.wanfangdata.com.cn/Periodical/jsjzdclykz201804046

    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). http://d.old.wanfangdata.com.cn/Periodical/jsjzdclykz201804046
  • 加载中
图(9) / 表(6)
计量
  • 文章访问数:  1183
  • HTML全文浏览量:  291
  • PDF下载量:  205
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-08-26
  • 录用日期:  2019-10-12
  • 网络出版日期:  2020-07-20

目录

    /

    返回文章
    返回
    常见问答