中国中西医结合肾病稿件信息
时空谱多星协同任务规划算法研究
张 新1,2※，仵倩玉1,3，彭玉3
(1. 中国科学院遥感与数字地球研究所 遥感科学国家重点实验室，北京 100101；2.美国威斯康辛大学密尔沃基分校，密尔沃基，53201； 3.中国科学院大学，北京 100049 )
摘 要：基于多源遥感卫星的时间、空间、光谱的多星协同观测任务规划是对地观测技术研究的重要内容。介绍了多星协同任务规划的重要性以及时空谱多星协同任务规划的优点，基于时间、空间和光谱协同观测约束优化模型，以金矿尾矿库污染、水资源污染和耕地荒漠化问题为例，分别在新疆伊犁河流域尾矿库区域、塔里木河流域和阿克苏区域随机产生观测任务，根据观测任务选取了多个成像卫星，通过仿真实验研究了基于启发式规则的贪婪算法、遗传算法和爬山算法对模型的求解效率和优化结果。验证了引入适宜度的必要性，以未观测点、任务适宜度、优先级、任务总价值为比较指标，综合分析和比较任务的总价值，验证了贪婪算法在本文模型中优于遗传算法和爬山算法。
关键词：多星协同观测、任务规划、贪婪算法、遗传算法、爬山算法
中图分类号：TP391 文献标识码：A
1 引言
对地观测卫星视角高、探测范围广、运行时间长，通过对地观测卫星获取地面影像数据并进行分析、处理，对研究地球资源、地球信息意义重大，同时，遥感信息的应用也日益融入人们的生活，在许多方面发挥着重要作用[1]。当前，对地观测卫星数量和种类不断增加，对地观测任务需求也变得更为复杂、任务量更为庞大。尽管有多种传感器分辨率、多种观测模式以及海量遥感数据，对地观测卫星资源仍无法完全满足日益复杂的观测任务需求。并且单颗卫星在限制时间内观测能力有限，只有少量的时间窗口可以利用，因此，往往需要多星协同观测，充分利用航天资源，协商完成观测任务。如何对多星进行任务规划，使观测目标合理分配到每一颗卫星，成为了亟待解决的难题。多星任务规划即根据用户提出的对地观测需求，对给定的卫星资源进行优化部署，使总体观测收益最大[2]，。
时空谱多星协同任务规划将拥有多尺度的时间、空间、光谱分辨率的多种类别卫星纳入任务体系，得到可以相互验证的丰富的目标电磁特征信息，增强对目标的综合感知，充分发挥对卫星资源的最大效益[3]。
目前，时空谱多星协同任务规划有多种优化模型，目前，国内外学者对该问题主要采用启发式算法[4-5]和群智能算法[6-7]进行研究，本文介绍了具有较好的全局搜索能力并得到广泛应用的基于启发式规则的贪婪算法、遗传算法和爬山算法[8]，并对各个算法的求解效率和优化结果进行了比较，并引入了适宜度，分析当目标函数考虑任务适宜度时，不同算法结果，验证了引入适宜度的必要性，并通过实验验证了贪婪算法对本文模型的优越性。
2 问题描述
面对有限的对地观测卫星资源和复杂的对地观测任务需求，对完成同一成像任务的卫星进行任务调度，避免重复成像，最大化的分配资源、获取收益是十分重要的[9]。随着卫星技术的发展以及用户需求的变化卫星任务规划不断涌现出新的问题和解决方法，任务规划模型建立和模型求解是多源卫星协同观测任务规划的两部分，目前有多种任务规划模型，包括约束满足模型[10]、数学规划模型[11]等模型，在国内的研究中，陈浩等[12] 对电磁探测卫星星间自主协同规划问题进行了研究，建立了基于多 Agent 技术的分布式自主规划模型，王冲等[13] 针对卫星规划任务动态重调度过程中的时效性和最优性之间的矛盾，提出了一种基于多 Agent 混合学习的策略.
本文依据观测目标的图像类型、图像分辨率需求、太阳光照条件和相关遥感器的时间窗口为观测目标选择可用的成像卫星，根据轨道参数和观测任务，选择约束满足模型描述多星对点目标协同观测任务规划问题,建立模型，并分别使用不同算法对模型进行验证。
3 求解算法
在模型求解算法方面，目前已有许多智能优化算法研究，如：深度优先搜索、动态规划、禁忌搜索算法、贪婪算法、遗传算法和爬山算法[14-16]等。智能优化算法是通过多种智能优化搜索方式寻找可接受的解或解集，不强调找到问题的最优解，而是寻求在解的最优程度和求解成本的合理取舍。由于卫星任务规划问题已经被证明是一个多项式复杂程度的非确定性难解问题，因此当前更多的研究中倾向于采用智能优化算法来探索和研究卫星任务规划问题。
在多种智能优化算法中，贪婪算法是按照既定的启发式规则逐步构造可行解的一种算法,它无须迭代,不能保证最优,甚至无法给出可行解与最优解之间的差异,但是它的时间性能最佳，并能按照设定的启发式规则安排任务。其基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。贪婪算法的优点在于在求解问题的每一步它都是选择最优解，这样算法就容易实现也易于理解，同时也提高了效率并节省了时间。遗传算法是对一种问题进行高效全局搜索的方法，它在搜索过程中有效地利用已有信息来自动获取和积累有关搜索空间的知识，并自适应地控制搜索方向使其最终走向最优解。遗传算法的优点是它不需要知道待解决问题的结构特性并且很容易编码，还通常能给出很好的解，具有群体搜索特性，有较高的搜索能力和极强的鲁棒性。 爬山算法是一种局部择优的方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策。爬山算法的优点是能够避免遍历，通过启发选择部分节点，从而达到提高效率的目的。
由于贪婪算法具有时间性能佳，并能按照设定的启发式规则安排任务的特点，所以采用基于启发式规则的贪婪算法对本文模型进行求解，并将启发式规则设为按照任务优先级和卫星适宜度的高低逐个安排任务。
4 仿真实验分析
4.1 卫星轨道信息
仿真时间：2018/5/18 00:00:00 – 2018/5/19 00:00:00。
依据观测目标的图像类型需求、图像分辨率需求、太阳光照条件和相关遥感器的时间窗口为观测目标选择可用的成像卫星。成像卫星集合中
为高分一号，
为高分二号，
为环境一号A星，
为环境一号B星，
为资源三号01星，
为资源一号02C星。六颗卫星
轨道参数信息如表1所示。
表 1 卫星轨道信息表
Table1 The satellite orbit information
|
|
卫星 |
|||||
|
参数 |
|
|
|
|
|
|
|
轨道高度/km |
645.00 |
631.00 |
649.09 |
649.09 |
506.00 |
780.10 |
|
轨道倾角/（°） |
98.05 |
97.91 |
97.95 |
97.95 |
97.42 |
98.50 |
|
回归周期（天） |
41.00 |
69.00 |
31.00 |
31.00 |
59.00 |
55.00 |
|
降交点地方时 |
10:30AM |
10:30AM |
10;30AM |
10:30AM |
10:30AM |
10:30AM |
|
遥感器侧摆角/（°） |
|
|
|
- |
|
- |
图1 卫星轨道图
Fig. 1 The picture of satellite orbit
观测任务：本文以金矿尾矿库污染、水资源污染和耕地荒漠化问题为例，分别在新疆伊犁河流域尾矿库区域、塔里木河流域和阿克苏区域随机产生20个优先级为[1,10]的观测任务去验证模型和算法的正确性和优化性能。每个观测任务所对应的观测点地理坐标、观测所需时间、任务优先级如表2所示。
表2 观测点信息表
Table 2 The coordinates of polygon targets
|
分类 |
观测任务 |
经度 |
纬度 |
观测任务 持续时间（sec） |
任务优先级 |
|
|
|
81.62 |
44.23 |
800.00 |
7 |
|
|
83.81 |
43.40 |
700.00 |
10 |
|
|
|
81.13 |
43.46 |
700.00 |
5 |
|
|
|
80.68 |
42.52 |
600.00 |
9 |
|
|
|
81.17 |
43.71 |
500.00 |
3 |
|
|
|
|
87.63 |
46.79 |
300.00 |
5 |
|
|
88.33 |
45.55 |
400.00 |
1 |
|
|
|
86.25 |
46.13 |
800.00 |
3 |
|
|
|
84.33 |
45.54 |
800.00 |
7 |
|
|
|
90.37 |
45.82 |
700.00 |
4 |
|
|
|
|
82.45 |
42.03 |
300.00 |
1 |
|
|
83.53 |
41.16 |
500.00 |
10 |
|
|
|
83.72 |
42.10 |
700.00 |
4 |
|
|
|
79.41 |
41.17 |
400.00 |
2 |
|
|
|
82.85 |
40.01 |
700.00 |
6 |
|
|
|
|
88.42 |
43.40 |
700.00 |
8 |
|
|
87.21 |
43.30 |
300.00 |
8 |
|
|
|
87.92 |
43.62 |
700.00 |
6 |
|
|
|
88.56 |
43.68 |
600.00 |
9 |
|
|
|
87.59 |
43.81 |
800.00 |
2 |
本文采用C#语言在Visual Studio 2017中对算法进行实现。采用贪婪算法求得的卫星任务规划方案如表3所示。
