留言板

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

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

应急测绘无人机资源多目标优化调度方法

朱庆 韩会鹏 于杰 杜志强 张骏骁 吴晨 沈富强

朱庆, 韩会鹏, 于杰, 杜志强, 张骏骁, 吴晨, 沈富强. 应急测绘无人机资源多目标优化调度方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(11): 1608-1615. doi: 10.13203/j.whugis20130000
引用本文: 朱庆, 韩会鹏, 于杰, 杜志强, 张骏骁, 吴晨, 沈富强. 应急测绘无人机资源多目标优化调度方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(11): 1608-1615. doi: 10.13203/j.whugis20130000
ZHU Qing, HAN Huipeng, YU Jie, DU Zhiqiang, ZHANG Junxiao, WU Chen, SHEN Fuqiang. Multi-objective Optimization Scheduling Method for UAV Resources in Emergency Surveying and Mapping[J]. Geomatics and Information Science of Wuhan University, 2017, 42(11): 1608-1615. doi: 10.13203/j.whugis20130000
Citation: ZHU Qing, HAN Huipeng, YU Jie, DU Zhiqiang, ZHANG Junxiao, WU Chen, SHEN Fuqiang. Multi-objective Optimization Scheduling Method for UAV Resources in Emergency Surveying and Mapping[J]. Geomatics and Information Science of Wuhan University, 2017, 42(11): 1608-1615. doi: 10.13203/j.whugis20130000

应急测绘无人机资源多目标优化调度方法

doi: 10.13203/j.whugis20130000
基金项目: 

国家自然科学基金 41471320

国家自然科学基金 41571390

国家自然科学基金 41501463

四川省测绘地理信息局局科技支撑项目 J2014ZC11

详细信息
    作者简介:

    朱庆, 博士, 教授, "长江学者奖励计划"特聘教授, 主要从事摄影测量、多维动态GIS与虚拟地理环境等方面研究。zhuq66@263.net

    通讯作者: 于杰, 博士。yujie_gsis@whu.edu.cn
  • 中图分类号: P208;P237.9

Multi-objective Optimization Scheduling Method for UAV Resources in Emergency Surveying and Mapping

Funds: 

The National Natural Science Foundation of China 41471320

The National Natural Science Foundation of China 41571390

The National Natural Science Foundation of China 41501463

the Science and Technology Support Project of Sichuan Surveying and Mapping Geographic Information Bureau J2014ZC11

More Information
    Author Bio:

    ZHU Qing, PhD, professor, Distinguished Professor of Changjiang Scholars Program of China, specializes in digital photogrammetry, multi-dimensional and dynamic GIS, virtual geographic environment. E-mail: zhuq66@263.net

    Corresponding author: YU Jie, PhD. E-mail:yujie_gsis@whu.edu.cn
  • 摘要: 应急测绘中的无人机调度存在时空环境约束复杂、调度方案多样的特点,现有调度主要以人为经验判断为主,方案粗放不可靠,难以综合考虑应急过程中复杂多变的因素,结果的精准性与可靠性较低。为实现灾后应急测绘的快速响应,提出了一种无人机资源的快速调度方法,综合考虑应急测绘任务需求、优先级、时间窗、作业区域地理环境和无人机测绘资源能力等约束条件,构建了以任务成果收益效率最大化、任务完成率最大化以及调度风险最小化等为多优化目标的应急测绘无人机资源调度模型,并运用蚁群算法实现对模型的求解。实验结果验证了调度方法的有效性。
  • 图  1  应急测绘任务与无人机资源调度示意图

    Figure  1.  ESM Missions and UAV Scheduling

    图  2  实验背景区域

    Figure  2.  Experimental Area

    图  3  无人机应急测绘调度方案示意图

    Figure  3.  UAV Scheduling Scheme in ESM

    图  4  目标函数的收敛过程

    Figure  4.  Convergence of Objective Function

    表  1  实验距离矩阵(基地+起降场)

    Table  1.   Distance Matrix(Base & Takeoff and Landing Field)

    距离/km 绵竹基地B1 绵阳基地B2 汶川县
    A1
    太子庙
    A2
    南新镇
    A3
    二里沟
    A4
    茂县
    A5
    清平乡
    A6
    大黑湾
    A7
    永和乡
    A8
    草坪乡
    A9
    北川县
    A10
    B1 0 37 54 29 49 68 46 20 37 60 35 54
    B2 37 0 91 66 76 95 73 43 60 77 36 48
    A1 54 91 0 25 16 19 30 49 47 44 70 74
    A10 54 48 74 63 58 72 44 40 30 42 19 0
    下载: 导出CSV

    表  2  应急测绘任务集合

    Table  2.   Emergency Surveying and Mapping Missions

    任务编号 任务区域 起降场位置 作业面积/km2 作业航程/km 优先级 开始时间窗/h 结束时间窗/h 海拔/m 所需传感器 区域天气 区域风速(风级)
    A-1 汶川县 A1 8 40 3 2 6 3 000 红外 阴天 4
    A-2 太子庙 A2 6 30 1 2 5 4 000 光学 阴天 3
    A-3 南新镇 A3 8 40 2 3 8 5 100 视频 小雨 4
    A-4 二里沟 A4 6 30 1 6 10 4 000 光学 阴天 4
    A-5 茂县 A5 9 45 3 0 6 3 500 SAR 小雨 5
    A-6 清平乡 A6 5 25 2 2 6 3 000 视频 阴天 5
    A-7 大黑湾 A7 7 35 1 5 9 2 000 红外 小雨 4
    A-8 永和乡 A8 10 50 2 4 7 3 000 SAR 阴天 5
    A-9 草坪乡 A9 6 30 2 2 5 2 000 光学 小雨 3
    A-10 北川县 A10 12 60 3 3 6 4 000 红外 中雨 4
    下载: 导出CSV

    表  3  无人机遥感系统集合

    Table  3.   UAV Remote Sensing Systems

    无人机系统编号 当前位置(距离矩阵) 巡航速度/(km·h-1) 续航时间/h 携带传感器(光学/红外/SAR/视频) 作业天气 抗风能力(风级) 最大作业海拔/m 地面转移速度/(km·h-1)
    U-1 B1 100 2.5 [1, 1, 1, 0] 小雨 5 5 000 50
    U-2 B1 80 1.5 [1, 0, 0, 1] 小雨 6 3 500 60
    U-3 B2 100 8 [1, 1, 1, 1] 小雨 6 6 000 50
    U-4 B2 110 3 [1, 1, 1, 0] 中雨 5 5 000 60
    下载: 导出CSV

    表  4  实验结果

    Table  4.   Experimental Results

    无人机系统 测绘任务 地面调度起止时间/h 作业起止时间/h 作业面积/km2 地面转移时长/h 作业时长/h 等待时长/h
    A-2 0~0.58 2~2.3
    U-1 A-5 2.3~2.92 2.92~3.37 25 1.48 1.25 1.77
    A-8 3.37~3.65 4~4.5
    U-2 A-6 0~0.33 2~2.31 5 0.33 0.31 1.67
    A-1 0~1.82 2~2.4
    U-3 A-3 2.4~2.72 3~3.4 22 2.52 1.1 2.68
    A-4 3.4~3.78 6~6.3
    A-9 0~0.6 2~2.27
    U-4 A-10 2.27~2.59 3~3.55 25 1.42 1.14 2.76
    A-7 3.55~4.05 55.32
    下载: 导出CSV

    表  5  实验对比结果

    Table  5.   Comparison of Experimental Results

    方法 模型 目标 方案作业时长/h 收益效率 方案风险
    执行风险 转移风险 时间风险
    传统方法 地理距离约束 时间最短 6.27 1.182 0.41 0.25 0.19
    本文方法 多约束 多目标 6.3 1.515 0.23 0.16 0.11
    下载: 导出CSV
  • [1] 周兴霞, 廖小露, 刘嘉.无人机航摄技术在四川省应急测绘保障中的应用研究[J].测绘与空间地理信息, 2014(10):239-242 doi:  10.3969/j.issn.1672-5867.2014.10.081

    Zhou Xingxia, Liao Xiaolu, Liu Jia. Application of Unmanned Aerial Vehicle Photogrammetric in Emergency Surveying and Mapping Support in Sichuan Province[J]. Geomatics & Spatial Information Technology, 2014(10):239-242 doi:  10.3969/j.issn.1672-5867.2014.10.081
    [2] 朱庆, 曹振宇, 林珲, 等.应急测绘保障体系若干关键问题研究[J].武汉大学学报·信息科学版, 2014, 39(5):551-555 http://ch.whu.edu.cn/CN/Y2014/V39/I5/551

    Zhu Qing, Cao Zhenyu, Lin Hui, et al. Key Technologies of Emergency Surveying and Mapping Service System[J]. Geomatics and Information Science of Wuhan University, 2014, 39(5):551-555 http://ch.whu.edu.cn/CN/Y2014/V39/I5/551
    [3] 田菁, 沈林成.多基地多无人机协同侦察问题研究[J].航空学报, 2007, 28(4):913-921 http://d.wanfangdata.com.cn/Periodical/hkxb200704026

    Tian Jing, Shen Lincheng. Research on Multi-Base Multi-UAV Cooperative Reconnaissance Problem[J]. Acta Aeronautica et Astronautica Sinica, 2007, 28(4):913-921 http://d.wanfangdata.com.cn/Periodical/hkxb200704026
    [4] Shima T, Rasmussen S J, Sparks A G, et al. Multiple Task Assignments for Cooperating Uninhabited Aerial Vehicles Using Genetic Algorithms[J]. Computers & Operations Research, 2006, 33(11):3252-3269 http://www.docin.com/p-512124636.html
    [5] 李炜, 张伟.基于粒子群算法的多无人机任务分配方法[J].控制与决策, 2010, 25(9):1359-1363 http://d.wanfangdata.com.cn/Periodical/jsjfz200907017

    Li Wei, Zhang Wei. Method of Tasks Allocation of Multi-UAVs Based on Particles Swarm Optimization[J]. Control & Decision, 2010, 25(9):1359-1363 http://d.wanfangdata.com.cn/Periodical/jsjfz200907017
    [6] Xu Zhiqiang, Yang Jiansi, Peng Chaoyong, et al. Development of an UAS for Post-Earthquake Disaster Surveying and its Application in Ms 7.0 Lushan Earthquake, Sichuan, China[J]. Computers & Geosciences, 2014, 68:22-30 doi:  10.1016/j.cageo.2014.04.001
    [7] Baiocchi V, Dominici D, Milone M V, et al. Development of a Software to Plan UAVs Stereoscopic Flight:An Application on Post Earthquake Scenario in L'Aquila City[C]. ICCSA 2013, Vietnam, 2013 doi:  10.1007/978-3-642-39649-6_11
    [8] Li G Q, Zhou X G, Yin J, et al. An UAV Scheduling and Planning Method for Post-Disaster Survey[J]. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2014, 40(2):169-172 http://adsabs.harvard.edu/abs/2014ISPAr.XL2..169L
    [9] Blanton J L, Wainwright R L. Multiple Vehicle Routing with Time and Capacity Constraints Using Genetic Algorithms[C]. International Conference on Genetic Algorithms, San Francisco, 1993 http://dl.acm.org/citation.cfm?id=645513.657758
    [10] Gambardella L M, Taillard R, Agazzi G. MACS-VRPTW:A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows[R]. IDSIA, Lugano, Switzerland, 1999 http://dl.acm.org/citation.cfm?id=870474
    [11] Wang Xiaole, Wu Jibing, Huang Hongbin, et al. Multiple Tasks Scheduling Algorithm for UAV Attacking in Uncertain Environment[C]. IEEE International Conference on Systems and Informatics, Yantai, 2012 http://ieeexplore.ieee.org/document/6223115/
    [12] 姜维, 庞秀丽, 郝会成.成像卫星协同任务规划模型与算法[J].系统工程与电子技术, 2013, 35(10):2093-2101 doi:  10.3969/j.issn.1001-506X.2013.10.13

    Jiang Wei, Pang Xiuli, Hao Huicheng. Collaborative Scheduling Model and Algorithm for Imaging Satellite Network[J]. Systems Engineering & Electronics, 2013, 35(10):2093-2101 doi:  10.3969/j.issn.1001-506X.2013.10.13
    [13] Dorigo M, Gambardella L M. Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem[J]. IEEE Transactions on Evolutionary Computation, 1997(1):53-66 http://citeseer.ist.psu.edu/viewdoc/citations?doi=10.1.1.145.8411
    [14] 苏菲, 陈岩, 沈林成.基于蚁群算法的无人机协同多任务分配[J].航空学报, 2008(S1):184-191 http://d.wanfangdata.com.cn/Thesis/Y2446290

    Su Fei, Chen Yan, Shen Lincheng. UAV Cooperative Multi-Task Assignment Based on Ant Colony Algorithm[J].Acta Aeronautica et Astronautica Sinica, 2008(S1):184-191 http://d.wanfangdata.com.cn/Thesis/Y2446290
    [15] 国博, 王社伟, 陶军.基于改进粒子群算法的多无人机任务分配研究[J].计算机仿真, 2009, 26(7):62-64 http://d.wanfangdata.com.cn/Periodical/jsjfz200907017

    Guo Bo, Wang Shewei, Tao Jun. Cooperative Task Allocation for Unmanned Combat Aerial Vehicles Using Improved Particle Colony Algorithm[J]. Computer Simulation, 2009, 26(7):62-64 http://d.wanfangdata.com.cn/Periodical/jsjfz200907017
    [16] Lei Ming, Yin Quanjun, Yao Xinyu. A Method for UAVs Detection Task Planning of Multiple Starting Points[C]. IEEE International Conference on Mechatronics and Automation, Beijing, 2015 http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=7237613
  • [1] 姚永祥, 段平, 李佳, 王云川.  联合对数极坐标描述与位置尺度特征的无人机影像匹配算法 . 武汉大学学报 ● 信息科学版, 2022, 47(8): 1271-1278. doi: 10.13203/j.whugis20200362
    [2] 朱秀丽, 赵勇, 刘万增, 李然, 赵婷婷, 彭云璐.  测绘地理信息应急快速制图系统研究 . 武汉大学学报 ● 信息科学版, 2020, 45(8): 1303-1311. doi: 10.13203/j.whugis20200139
    [3] 赵勇, 刘万增, 李然, 朱秀丽, 翟曦.  新时代应急测绘保障技术体系框架设计 . 武汉大学学报 ● 信息科学版, 2020, 45(8): 1312-1318. doi: 10.13203/j.whugis20200134
    [4] 李婉, 赵双明, 张卫龙, 刘骁, 喻国荣.  一种无人机影像滤波分频拼接算法 . 武汉大学学报 ● 信息科学版, 2018, 43(6): 943-950. doi: 10.13203/j.whugis20160108
    [5] 李鹏飞, 孙开敏, 李德仁, 王玮.  无人机影像应急并行处理负载均衡方法 . 武汉大学学报 ● 信息科学版, 2018, 43(2): 268-274. doi: 10.13203/j.whugis20130095
    [6] 李鹏飞, 孙开敏, 李德仁, 王玮.  无人机影像应急并行处理负载均衡方法 . 武汉大学学报 ● 信息科学版, 2018, 43(2): 268-274. doi: 10.13203/j.whugis20170022
    [7] 樊邦奎, 张瑞雨.  无人机系统与人工智能 . 武汉大学学报 ● 信息科学版, 2017, 42(11): 1523-1529. doi: 10.13203/j.whugis20170177
    [8] 杨楠, 邵振峰, 郭丙轩, 彭哲, 黄蕾.  基于非固定初始面元的无人机影像点云优化算法 . 武汉大学学报 ● 信息科学版, 2016, 41(8): 1013-1020. doi: 10.13203/j.whugis20140750
    [9] 占伟伟, 王伟, 陈能成, 王超.  一种利用改进A*算法的无人机航迹规划 . 武汉大学学报 ● 信息科学版, 2015, 40(3): 315-320.
    [10] 朱庆, 曹振宇, 林珲, 谢维挺, 丁雨淋.  应急测绘保障体系若干关键问题研究 . 武汉大学学报 ● 信息科学版, 2014, 39(5): 551-555. doi: 10.13203/j.whugis20130351
    [11] 巩现勇, 武芳, 姬存伟, 翟仁健.  道路网匹配的蚁群算法求解模型 . 武汉大学学报 ● 信息科学版, 2014, 39(2): 191-195. doi: 10.13203/j.whugis20120649
    [12] 刘亚文, 庞世燕, 左志奇.  蚁群算法的建筑立面点云数据提取 . 武汉大学学报 ● 信息科学版, 2012, 37(11): 1307-1310.
    [13] 徐亚明, 邢诚, 陈晓东.  一种基于拼接线的无人机序列影像拼接方法 . 武汉大学学报 ● 信息科学版, 2011, 36(11): 1265-1269.
    [14] 刘晋苏, 任沁源, 韩波, 李平.  基于微型无人机平台的航拍动态阴影检测 . 武汉大学学报 ● 信息科学版, 2010, 35(11): 1275-1278.
    [15] 陈杰, 邓敏, 肖鹏峰, 杨敏华.  利用Gabor滤波器与蚁群算法进行纹理分割 . 武汉大学学报 ● 信息科学版, 2010, 35(11): 1271-1274.
    [16] 刘朔, 武红敢, 温庆可.  基于遗传和蚁群组合算法优化的遥感图像分割 . 武汉大学学报 ● 信息科学版, 2009, 34(6): 679-683.
    [17] 张剑清, 孙明伟, 张祖勋.  基于蚁群算法的正射影像镶嵌线自动选择 . 武汉大学学报 ● 信息科学版, 2009, 34(6): 675-678.
    [18] 葛小三, 边馥苓.  蚁群算法求解三维表面路径方法的研究 . 武汉大学学报 ● 信息科学版, 2007, 32(4): 366-368.
    [19] 叶志伟, 郑肇葆.  蚁群算法中参数α、β、ρ设置的研究——以TSP问题为例 . 武汉大学学报 ● 信息科学版, 2004, 29(7): 597-301.
    [20] 郑肇葆.  协同模型与遗传算法的集成 . 武汉大学学报 ● 信息科学版, 2001, 26(5): 381-386.
  • 加载中
图(4) / 表(5)
计量
  • 文章访问数:  2038
  • HTML全文浏览量:  177
  • PDF下载量:  613
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-02-13
  • 刊出日期:  2017-11-05

应急测绘无人机资源多目标优化调度方法

doi: 10.13203/j.whugis20130000
    基金项目:

    国家自然科学基金 41471320

    国家自然科学基金 41571390

    国家自然科学基金 41501463

    四川省测绘地理信息局局科技支撑项目 J2014ZC11

    作者简介:

    朱庆, 博士, 教授, "长江学者奖励计划"特聘教授, 主要从事摄影测量、多维动态GIS与虚拟地理环境等方面研究。zhuq66@263.net

    通讯作者: 于杰, 博士。yujie_gsis@whu.edu.cn
  • 中图分类号: P208;P237.9

摘要: 应急测绘中的无人机调度存在时空环境约束复杂、调度方案多样的特点,现有调度主要以人为经验判断为主,方案粗放不可靠,难以综合考虑应急过程中复杂多变的因素,结果的精准性与可靠性较低。为实现灾后应急测绘的快速响应,提出了一种无人机资源的快速调度方法,综合考虑应急测绘任务需求、优先级、时间窗、作业区域地理环境和无人机测绘资源能力等约束条件,构建了以任务成果收益效率最大化、任务完成率最大化以及调度风险最小化等为多优化目标的应急测绘无人机资源调度模型,并运用蚁群算法实现对模型的求解。实验结果验证了调度方法的有效性。

English Abstract

朱庆, 韩会鹏, 于杰, 杜志强, 张骏骁, 吴晨, 沈富强. 应急测绘无人机资源多目标优化调度方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(11): 1608-1615. doi: 10.13203/j.whugis20130000
引用本文: 朱庆, 韩会鹏, 于杰, 杜志强, 张骏骁, 吴晨, 沈富强. 应急测绘无人机资源多目标优化调度方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(11): 1608-1615. doi: 10.13203/j.whugis20130000
ZHU Qing, HAN Huipeng, YU Jie, DU Zhiqiang, ZHANG Junxiao, WU Chen, SHEN Fuqiang. Multi-objective Optimization Scheduling Method for UAV Resources in Emergency Surveying and Mapping[J]. Geomatics and Information Science of Wuhan University, 2017, 42(11): 1608-1615. doi: 10.13203/j.whugis20130000
Citation: ZHU Qing, HAN Huipeng, YU Jie, DU Zhiqiang, ZHANG Junxiao, WU Chen, SHEN Fuqiang. Multi-objective Optimization Scheduling Method for UAV Resources in Emergency Surveying and Mapping[J]. Geomatics and Information Science of Wuhan University, 2017, 42(11): 1608-1615. doi: 10.13203/j.whugis20130000
  • 目前, 无人机以其快速、机动、灵活等优点被广泛地应用于应急测绘[1-2]。如何对现有无人机资源进行统一管理、合理调度,快速获取重要区域的高分辨率航空影像,为救灾减灾的紧急救援、灾民安置、灾害普查分析、恢复建设各个时期提供及时的测绘保障是应急测绘的关键问题之一。应急测绘要求在灾后多测绘任务条件下,实现多无人机测绘资源的快速任务规划与调度,合理安排各无人机测绘资源的任务执行序列,包括测绘任务执行顺序和时间,以求在灾后有限的时间内,最大程度发挥无人机测绘资源的能力,收获最多最好的应急测绘成果。

    关于无人机任务规划与调度的研究主要围绕无人机执行空中军事侦察与打击任务,目前有不同的适用模型,如多基地多无人机协同侦察模型[3]、无人机协同多任务分配模型[4]以及混合整数线性规划模型[5]等。这些研究偏重于通过对长航时无人机进行航线的规划实现无人机任务的分配,难以运用于灾后应急的区域性测绘工作中。灾后无人机应急测绘研究多针对灾害现场特定任务条件下的航迹规划、数据获取和处理等问题[6-7],而没有考虑多个任务的分配和不同任务间的地面转移等问题。比如以测绘任务完成时间最短为目标的无人机应急测绘任务分配与调度模型,没有考虑不同测绘任务的优先级和时间窗等因素影响[8]。此外,应急测绘无人机资源调度包括车载测绘无人机的地面运输,尽管与带时间窗的车辆调度问题具有相似之处[9-10],但相关成果均难以在复杂的应急测绘任务条件下直接运用于无人机的调度。

    关于任务规划与资源调度问题求解的算法,智能化启发式算法如遗传算法和群优化算法的应用最为广泛[3-4, 11-12]。遗传算法被大量应用在任务规划与车辆调度问题中,但遗传算法没有充分利用网络的反馈信息,搜索速度较慢,难以解决大规模计算问题。群优化算法中的蚁群算法在无人机任务规划和车辆调度问题中有较好的应用[13-16],蚁群算法本质的并行性和正反馈机制可充分利用网络的启发信息,快速获得收敛解,此外蚁群算法的鲁棒性使其易于应用于各种组合优化问题的求解。

    本文旨在构建多约束和多目标优化的无人机应急测绘资源优化调度模型,并采用蚁群算法求解调度方案。

    • 应急测绘中无人机资源调度问题是指利用现有的不同类型的无人机遥感系统,对灾后若干空间分散的任务区域制定应急测绘无人机资源的调度计划,即在满足应急测绘任务需求、作业区域地理条件、任务时间窗、测绘无人机遥感系统数量和性能等约束下,为无人机分配测绘任务和地面调度方案。如图 1所示,无人机从基地出发,按照调度方案的任务执行流程,经地面调度抵达测绘任务的起降场,依次完成各自的任务。每个测绘任务代表一个作业区域,包含主要地质灾害点、重点居民区等核心作业点。

      图  1  应急测绘任务与无人机资源调度示意图

      Figure 1.  ESM Missions and UAV Scheduling

      应急测绘中无人机资源的调度问题,可用4元组{E, R, M, C}表示。其中,E为调度问题所在的地理环境,主要包括地面交通、地形以及天气条件;R表示无人机遥感系统集合,R={R1, R2, …, Rr},r为无人机资源的数目,对无人机测绘资源的描述主要包括位置、所携带传感器和无人机性能等;M为应急测绘任务集合,M={M1, M2, …, Mm},m为应急测绘任务的个数,对应急测绘任务的初始描述主要包括任务作业区域、任务数据需求(图像类型、分辨率)、任务优先级和任务时限等;C为调度问题中约束条件的集合。

    • 任务Mi的执行起止时间限制范围Tsi=[tsi, tei];

      任务Mi的预计执行开始时间为si,预计执行结束时间为ei

      调度方案的总执行时间为T

      无人机Rj执行任务Mi所需时间为ti, j

      无人机集合R的初始位置集合PR={RPj, j=1, 2, …, r};任务集合M的起降场位置集合PM={MPi, i=1, 2, …, m};

      任意两点PiPj之间的地面调度距离为dPi, Pj,地面转移时间记为tPi, Pj,其中PiPj∈(PRPM);

      任务Mi执行的决策变量为Fi,成功执行时Fi=1,否则Fi=0;

      资源选择决策变量为di, j,如果无人机资源Rj被用来执行任务Mi,则di, j=1,否则di, j=0(1≤im,1≤jr)。

    • 1) 任务执行唯一性约束。根据问题模型中对测绘任务的描述可知,每个测绘任务由一个无人机资源在时间窗内执行一次,其形式化表达为∀Mi,∑jdi, j≤1。

      2) 任务执行时间约束。主要包括任务开始时间不小于任务执行起始限制时间,tsisi;任务结束时间不大于任务执行终止限制时间,eitei;任务执行的时间参数关系,si+ti, j=ei

      3) 资源转场时间约束。主要为无人机Rj执行任务Mi与前续任务Mk之间的时间关系,即Mi的执行开始时间不小于无人机执行完Mk后转移到Mi的时间tMk, Mi,留有足够的作业等待时间,减小方案的风险,ek+tMk, Misi;当Rj无前续任务时,有ek=0;PMk=PRj

      4) 任务资源匹配约束。对于特定无人机Rj,其执行某个测绘任务Mi的作业时长ti, j与该无人机对任务Mi的执行风险概率Risk(Mi, Rj),据测绘任务和无人机遥感系统的相关参数,结合作业区域的地理环境与实时气象信息进行匹配,数学描述为Match(Mi, Rj)= < ti, j, Risk(Mi, Rj)>。

    • 1) 任务成果收益效率最大化。无人机应急航飞测绘的目的是在灾后最短的时间内获取最大的测绘成果,将调度方案的测绘任务成果收益定义为任务优先级×完成时效性×作业航程,故有收益效率O1为:

      $$ {O_1} = \frac{{\sum {_{i = 1}^m{F_i} \cdot {r_i} \cdot P\left( {{M_i}} \right) \cdot {L_i} \cdot V} }}{T} $$ (1)

      式中,ri为任务优先级;∀Fi=1,即测绘任务Mi被分配执行时,任务完成时效性的定义为:$ P\left( {{M_i}} \right) = \left\{ \begin{array}{l} 1/3, 0 < g\left( {{M_i}} \right) < 1/3\\ g\left( {{M_i}} \right), 1/3 \le g\left( {{M_i}} \right) < 1 \end{array} \right., g\left( {{M_i}} \right) = \frac{{{e_i} + {s_i}}}{{{e_i}-{t_{{s_i}}}}}, $,其在时间窗内被完成的时间越早,完成时效性越高;Li为任务Mi的作业航程;V为单位归一化常量。

      2) 任务完成率最大化。测绘任务的完成率是衡量调度方案优劣的另一个主要条件,要保证调度方案有最大化的任务完成率。完成率O2定义为任务完成数/任务总数:

      $$ {O_2} = \frac{{\sum {_{i = 1}^m{F_i}} }}{m} $$ (2)

      3) 方案风险最小化。调度方案的执行受多种因素的影响,主要考虑任务执行风险和调度风险的影响。最小化调度方案的风险能够增加测绘任务按时完成的概率,增强调度方案的稳健性。方案风险O3的定义为:

      $$ {O_3} = \sum {{\rm{Risk}}\left( {{M_i}, {R_k}} \right) + } \sum {{\rm{Risk}}\left( {{M_i}, {M_j}} \right)} $$ (3)

      式中,Risk(Mi, Rk)为任务执行风险,由任务与资源匹配生成,在满足最低性能需求条件下,所选无人机对气象条件、地形条件的适应性越高,执行风险越小;Risk(Mi, Mj)为调度风险,由地面转移的路段风险以及调度过程中的时间风险组成,其计算表达式为$ \sum {{\rm{Risk}}\left( {{M_i}, {M_j}} \right)} = \sum {\left( {{r_{i, j}} + {s_{i, j}}} \right) + \sum {_{i = 1}^m{R_{{T_i}}}/m} } $。

      路段风险:记为∑(ri, j+si, j),其中ri, j表示路网中相邻结点i, j间气象致灾因子危险性的路段灾害强度,si, j表示相邻结点i, j间地形地貌等孕灾环境特征的路段敏感性。

      时间风险:每个任务的无人机地面调度时间风险记为RTi,有${R_{{T_i}}} = \frac{{{F_i} \cdot {t_{{P_{{M_k}}}, {P_{{M_i}}}}}}}{{\left( {{t_{{e_i}}}-{t_{i, j}}} \right)-{e_k}}} $。其中tPMk, PMi为资源Rj由前续任务Mk转移至任务Mi所需的调度时间,tei-ti, j为任务Mi的最晚开始时间,ekMi的前续任务Mk的结束时间。

      模型的综合评价目标O为上述3个目标的加权和:

      $$ O = \lambda \cdot {O_1} + \mu \cdot {O_2}-\omega \cdot {O_3} $$ (4)

      式中,λμω为3个目标的权重。

    • 无人机Rj的调度方案:

      $ {\rm{Pla}}{{\rm{n}}_j} = \left\{ {p_1^j, p_2^j, \cdots, p_{{m_j}}^j} \right\}, p_i^j = \left\{ {T_1^j, T_2^j, T_3^j, {M_i}} \right\}$式中,T1j为无人机Rj执行测绘任务Mi的预计到达时间;T2j为任务预计开始执行时间;T3j为预计完成任务时间。

    • 本文针对多种类无人机多任务调度问题构建分组映射的人工蚁群,构造状态转移中的启发因子,设计人工蚂蚁的状态转移规则和信息素的更新策略,实现了无人机应急测绘资源调度模型求解算法。

    • 在应急测绘无人机调度问题中,存在多种类型的无人机,其性能参数、携带传感器等不完全相同,执行任务的能力也不相同,需要对蚁群的构建方法进行改进。将每个无人机映射为m只蚂蚁,构建大小为m×r的人工蚁群AG,建立无人机集合Rr架无人机到蚂蚁子群AGv的一组映射,记为AGv={Ant1, v, Ant2, v, …, Antr, v}(v=1, 2, …, m),蚂蚁Antu, v对应于无人机Ru,通过蚂蚁子群AGv为无人机集合构造任务执行序列。

    • 在多无人机调度问题的蚁群算法中,蚂蚁的状态转移是指无人机由当前任务向下一任务的转移,本文选择下一任务的优先性原则为优先访问任务较重要、剩余转移时间较短以及优先级较高的任务。故t时刻蚂蚁Antu, vMi转移到Mj的启发因子为:

      $$ \eta \left( {i, j} \right) = \frac{{{r_j}}}{{{t_{{P_i}, {P_j}}} \cdot \left( {{t_{{e_i}}}-t} \right)}} $$ (5)
    • 本文采用伪随机比率选择规则,蚂蚁Antu, v执行完任务Mi后转移到任务Mj的转移规则由式(6)决定。

      $$ \begin{array}{l} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;j = \\ \left\{ \begin{array}{l} \arg \mathop {\max }\limits_{j \in {\rm{allowe}}{{\rm{d}}_{u, v}}} \left\{ {{{\left[{\tau \left( {i, j} \right)} \right]}^\alpha } \cdot {{\left[{\eta \left( {i, j} \right)} \right]}^\beta }} \right\}, q \le {q_0}\\ S, 其他 \end{array} \right. \end{array} $$ (6)

      式中,q0(0≤q0≤1)为参数,q为随机生成的概率值,q∈[0, 1];τ(i, j)为Antu, v状态转移时任务Mi到任务Mj之间路径上的信息素浓度;η(i, j)为Antu, v进行状态转移时的启发信息(式(5)定义);αβ表示信息素与启发式因子的权重;allowedu, v为Antu, v下一步可执行的候选任务集合;S根据概率转移公式(7)的选择规则得到,其中,Pt(u, v)(i, j)为蚂蚁Antu, v选择从Mi转移到Mj的概率。

      $$ \begin{array}{l} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;P_t^{\left( {u, v} \right)}\left( {i, j} \right) = \\ \left\{ \begin{array}{l} \frac{{\tau _t^\alpha \left( {i, j} \right) \cdot \eta _t^\beta \left( {i, j} \right)}}{{\sum\limits_{S \in {\rm{allowe}}{{\rm{d}}_{u, v}}} {\tau _t^\alpha \left( {i, S} \right) \cdot \eta _t^\beta \left( {i, S} \right)} }}, j \in {\rm{allowe}}{{\rm{d}}_{u, v}}\\ 0, 其他 \end{array} \right. \end{array} $$ (7)
    • 信息素采用全局更新规则,增强全局最优解路径上的信息素。

      $$ \begin{array}{l} {\tau _{c + 1}}\left( {i, j} \right) = \left( {1-\rho } \right) \cdot {\tau _c}\left( {i, j} \right) + \rho \cdot \mathit{\Delta }{\tau _c}\left( {i, j} \right)\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\mathit{\Delta }{\tau _c}\left( {i, j} \right) = \\ \left\{ \begin{array}{l} {\left( O \right)^{-1}}, \left( {i, j} \right) \in 全局最优解的转移边\\ 0, 其他 \end{array} \right. \end{array} $$ (8)

      式中,Δτc(i, j)表示第c次循环后从任务Mi到任务Mj的转移边(i, j)上的信息素增量;O为全局最优解对应的目标函数值;ρ表示信息素挥发系数,ρ∈[0, 1)。

    • 应急测绘无人机资源调度模型的蚁群求解算法主要步骤如下。

      1) 初始化系统参数αβρq0,无人机集合R,任务集合M。构建规模为m×r的蚁群,建立m组蚂蚁子群AGv(v=1, 2, …, m)。初始化信息素浓度为任务集合的最大时间窗,设置最大迭代次数Cmax并初始化算法初始迭代计数器c=0。

      2) 对m组蚂蚁子群AGv,按以下操作进行每组蚂蚁子群中各蚂蚁任务序列的求解:(1)随机选择下一步要走的蚂蚁Antu, vAGv,由状态转移规则式(5)~(7)构造每个蚂蚁对应无人机的任务序列。(2)当蚂蚁子群AGv中的所有蚂蚁Antu, v(u=1, 2, …, r)均无可执行任务时,由式(1)~(4)计算此组蚂蚁子群对应调度方案的评价目标函数值O

      3) 将当前迭代中m组蚂蚁子群的最优调度方案与全局最优调度方案进行比较,获得全局最优解的评价目标函数值,按照式(8)进行全局信息素的更新,同时更新全局最优调度方案。

      4) c=c+1,如果c>cmax,则算法结束,输出全局最优调度方案,否则转步骤2继续执行。

    • 以汶川地震中部分受灾区域无人机应急航飞测绘获取高分辨率遥感数据为例,进行实验验证。如图 2所示,绵竹和绵阳基地共有4套测绘无人机遥感系统,汶川附近受灾区域有10个应急测绘任务。

      图  2  实验背景区域

      Figure 2.  Experimental Area

      应急测绘任务其详细信息见表 1表 2,其中距离矩阵以及作业区域海拔等参数顾及实验需要进行了模拟,表 1为无人机基地以及各应急测绘任务起降场之间的距离矩阵,表 2为应急测绘任务集合描述。现有测绘无人机遥感系统的参数信息见表 3。实验结果见表 4

      表 1  实验距离矩阵(基地+起降场)

      Table 1.  Distance Matrix(Base & Takeoff and Landing Field)

      距离/km 绵竹基地B1 绵阳基地B2 汶川县
      A1
      太子庙
      A2
      南新镇
      A3
      二里沟
      A4
      茂县
      A5
      清平乡
      A6
      大黑湾
      A7
      永和乡
      A8
      草坪乡
      A9
      北川县
      A10
      B1 0 37 54 29 49 68 46 20 37 60 35 54
      B2 37 0 91 66 76 95 73 43 60 77 36 48
      A1 54 91 0 25 16 19 30 49 47 44 70 74
      A10 54 48 74 63 58 72 44 40 30 42 19 0

      表 2  应急测绘任务集合

      Table 2.  Emergency Surveying and Mapping Missions

      任务编号 任务区域 起降场位置 作业面积/km2 作业航程/km 优先级 开始时间窗/h 结束时间窗/h 海拔/m 所需传感器 区域天气 区域风速(风级)
      A-1 汶川县 A1 8 40 3 2 6 3 000 红外 阴天 4
      A-2 太子庙 A2 6 30 1 2 5 4 000 光学 阴天 3
      A-3 南新镇 A3 8 40 2 3 8 5 100 视频 小雨 4
      A-4 二里沟 A4 6 30 1 6 10 4 000 光学 阴天 4
      A-5 茂县 A5 9 45 3 0 6 3 500 SAR 小雨 5
      A-6 清平乡 A6 5 25 2 2 6 3 000 视频 阴天 5
      A-7 大黑湾 A7 7 35 1 5 9 2 000 红外 小雨 4
      A-8 永和乡 A8 10 50 2 4 7 3 000 SAR 阴天 5
      A-9 草坪乡 A9 6 30 2 2 5 2 000 光学 小雨 3
      A-10 北川县 A10 12 60 3 3 6 4 000 红外 中雨 4

      表 3  无人机遥感系统集合

      Table 3.  UAV Remote Sensing Systems

      无人机系统编号 当前位置(距离矩阵) 巡航速度/(km·h-1) 续航时间/h 携带传感器(光学/红外/SAR/视频) 作业天气 抗风能力(风级) 最大作业海拔/m 地面转移速度/(km·h-1)
      U-1 B1 100 2.5 [1, 1, 1, 0] 小雨 5 5 000 50
      U-2 B1 80 1.5 [1, 0, 0, 1] 小雨 6 3 500 60
      U-3 B2 100 8 [1, 1, 1, 1] 小雨 6 6 000 50
      U-4 B2 110 3 [1, 1, 1, 0] 中雨 5 5 000 60

      表 4  实验结果

      Table 4.  Experimental Results

      无人机系统 测绘任务 地面调度起止时间/h 作业起止时间/h 作业面积/km2 地面转移时长/h 作业时长/h 等待时长/h
      A-2 0~0.58 2~2.3
      U-1 A-5 2.3~2.92 2.92~3.37 25 1.48 1.25 1.77
      A-8 3.37~3.65 4~4.5
      U-2 A-6 0~0.33 2~2.31 5 0.33 0.31 1.67
      A-1 0~1.82 2~2.4
      U-3 A-3 2.4~2.72 3~3.4 22 2.52 1.1 2.68
      A-4 3.4~3.78 6~6.3
      A-9 0~0.6 2~2.27
      U-4 A-10 2.27~2.59 3~3.55 25 1.42 1.14 2.76
      A-7 3.55~4.05 55.32

      表 4的实验结果显示,所有测绘任务均能得到合适的无人机资源,资源的利用率较高;各无人机的作业等待时长较大,表明调度方案的时间风险较小;无人机U-1、U-3、U-4由于性能接近,均分配到3个任务,其作业区域总面积相近,表明本文方法具有均衡资源负载的效果。

      由调度方案示意图(图 3)可直观看出每个无人机所分配到的测绘任务之间具有空间上的邻近性,表明了实验结果方案的合理性。无人机U-2由于作业海拔和携带传感器的限制,仅分配到任务(A-6清平乡);无人机U-1由其最大作业海拔(5 000 m)的限制没有分配到距其较近的任务组合序列(A-1汶川县、A-3南新镇、A-4二里沟),表明了实验结果方案的准确性。

      图  3  无人机应急测绘调度方案示意图

      Figure 3.  UAV Scheduling Scheme in ESM

      为验证本文算法效率及其有效性,构造了50T_10U(50个任务、10套无人机系统)、100T_20U、150T_30U 3组实验样本数据,实验结果(见图 4)表明实验迭代收敛时间在实验样本数量下近似为线性增长,满足计算应用需求。

      图  4  目标函数的收敛过程

      Figure 4.  Convergence of Objective Function

      在实际应用中,一般按照行政区划或地图图幅分割方法生成调度方案,应急测绘调度多以空间距离为约束, 以完成时间最短为优化目标, 生成的方案难以适应复杂的灾区时空条件。实验结果表明本文方法在实际应用中的有效性(见表 5)。

      表 5  实验对比结果

      Table 5.  Comparison of Experimental Results

      方法 模型 目标 方案作业时长/h 收益效率 方案风险
      执行风险 转移风险 时间风险
      传统方法 地理距离约束 时间最短 6.27 1.182 0.41 0.25 0.19
      本文方法 多约束 多目标 6.3 1.515 0.23 0.16 0.11

      表 5实验对比结果显示,与传统单一优化目标的方法相比,本文方法提高了应急测绘的收益率,降低了调度方案的执行和调度风险,能够有效应用于应急条件下测绘无人机资源的调度问题的求解。

    • 利用无人机的全自动无人飞行和低空作业优势灵活获取灾区局部地区精细的高分辨率影像数据已经日益成为应急测绘的主要手段之一。本文的调度方法能够较好地应用于应急测绘条件下无人机航飞测绘任务的规划问题。进一步的研究包括:充分考虑灾害环境的复杂性和不确定性,根据历史方案数据获取无人机飞行方案的富裕航程,对调度模型进行改进,充分利用无人机的机动性; 同时发展顾及任务与灾区环境变化的应急测绘资源动态调度模型;考虑任务区域的航线规划, 以及相邻测绘任务区域多无人机协同航飞过程碰撞概率带来的无人机的航飞风险。从测绘任务设定的层面进行改进主要考虑增加任务的时序性约束,比如先驱测绘任务为第一时间获取通往灾区的主要道路、桥梁等交通设施的毁坏情况,沿主要道路进行航飞;后续任务为无人机到达城镇或目标区域上空时, 进行盘旋飞行以获取重要受灾区域更多的地面信息。

参考文献 (16)

目录

    /

    返回文章
    返回