基于BP神经网络的星上任务可调度性预测方法

2015-05-17 05:45邢立宁何永明
中国管理科学 2015年1期

邢立宁,王 原,何永明,何 磊

(国防科学技术大学信息系统与管理学院,湖南 长沙 410073)

1 引言

对地观测是一种重要的获取地表信息资源的手段,其数据产品在军事、防灾、矿物探测、气象预测、紧急救援等方面均有十分重要的应用。成像卫星作为先进对地观测技术的产物,一直在对地观测任务中扮演极为重要的角色。随着对地观测信息在各个领域的广泛应用,用户对于对地观测数据的收集也提出了日趋复杂的要求,如智慧地球观测[1],遥感大数据分析[2]等。这些需求对于成像卫星的任务规划技术提出了极大的挑战。以往的单星甚至多星地面联合调度的方法由于其应变能力差,规划、反应周期长、需要大量星地交互等特点,已经难以适应新需求环境下的成像卫星任务规划要求[3]。为了应对复杂对地观测任务需求,成像卫星的开发和应用正逐渐向着协同化、智能化、网络化的方向发展[4]。利用智能化、组网式的新型成像卫星使用方式,能够使研究者获得比以前更加有价值的科学数据,同时减少了卫星操作所需要付出的资源量[5]。而成像卫星智能化、组网技术的发展,同样给成像卫星自主任务规划技术提出了新的挑战:

(1)同一成像卫星星座内不同成像卫星的资源约束、任务执行能力各不相同,极大提高了成像卫星星座任务规划的复杂度;另一方面,现代成像卫星星座通常面临大量的紧急需求,因此需要在充分考虑用户需求的基础上,用较快速度构建收益较较高的任务规划序列[6]。

(2)不同于以往的单星或多星联合调度问题,成像卫星星座自主任务规划的最终结果通常需要星座内不同成像卫星经过多次的交互和协商之后共同完成,因此给任务规划的结果的执行带来了较大的不确定性。

(3)任务规划执行结果的不确定性和用户需求的确定性产生了矛盾。由于成像卫星任务规划的输入通常由对确定的用户需求的标准化分解得到,其中的部分执行失败可能导致整个规划序列的结果无效,从而增加了规划收益的不确定性。

为了解决成像卫星自主任务规划导致的规划结果的不确定性、规划算法代价的持续增长和用户需求的确定性之间的冲突,近几年,成像卫星领域的研究者提出了任务可调度性的概念。这一概念着眼于根据不同卫星的任务执行能力、不同卫星当前的任务负载以及用户提供的对地观测需求,预测将任务分配给不同成像卫星的执行成功率,从而为用户需求的制定、成像卫星任务规划的优化方向提供借鉴依据。

目前,对成像卫星任务可调度性的研究仍然较少。Tinker等[7]通过基于案例推理的方式设计了单星单轨道圈次下的任务可调度性预测问题,并设计 了 基 于 SAGE (Self-Aware Generalization Engine)推理引擎的预测算法,计算结果显示成功率能够达到约80%。白国庆、陈英武[8]设计了基于地面历史数据信息的集成BP神经网络成像任务可调度性预测模型,对多星多轨道圈次的成像卫星任务可调度性进行了研究,一定程度上提高了预测的准确率。Li Jun,Jing Ning等[9]设计了一种基于用户“使命”需求的对地观测卫星任务可调度性预测算法,并通过鲁棒性决策树、支持向量机和人工神经网络等方法构造了相应的求解算法,并比较了其求解准确率和所需CPU时间等相关指标。然而,这些求解方法均存在预测所需数据维度较高、所占存储空间较大,算法设计较为复杂、所需运算代价较高的特点,对于星上运算能力和存储能力有限的硬件环境以及相应的需要较快决策的环境(如快响卫星星座所需求的任务规划时间一般为秒级)而言,不能较好的适用。

我国近年来正着力发展成像卫星组网技术,希望在2020年前建立高分辨率、高精度的时空协调、全天候、全地形的对地观测系统[10]。同时应该注意到,由于我国卫星管控部门长期采取分散式、“烟囱式”管理[11],不同的卫星管控部门均积累了大量成像卫星日常运行数据而没有良好的利用。而在此基础上,若需要达成真正面向用户需求的成像卫星星座自主任务规划技术,需要从这些历史数据中发掘一定的规律,设计能够满足星上软硬件环境要求且具有较高预测准确率的成像卫星任务可调度性预测方法。

为了解决以上问题,本文从实际卫星运行情况出发,结合对过往成像卫星实际运行数据的分析,设计了一种基于神经网络的自主卫星星上任务可调度性预测方法,并设计了相应的实验验证了其在环境参数和卫星参数发生变化的情况下的适应性。

2 成像卫星任务可调度性预测问题描述及分析

2.1 问题背景

成像卫星智能化是目前成像卫星领域发展的大趋势,其核心思想是结合当前飞速发展的星上硬件技术获得的更强的实时任务信息获取能力、更高的星上计算速度和更大的星上存储能力,提升成像卫星对于动态变化的任务属性的适应性,以提高成像卫星的使用效能。一个成像卫星星座通常由多颗成像卫星构成,每颗卫星一般对应一个智能体Agent,其结构一般包括“团队式”和“全分布式”[12]。

图1 团队式成像卫星星座

图2 全分布式成像卫星星座

传统的成像卫星任务调度方法通常由地面测控站提前较长时间(通常6到12天,最少1到3天)完成[13],该方法能够充分考虑到规划收益的全局性,且除了极小概率出现的卫星硬件故障之外,通常能够保证规划任务能够较高比例被成像卫星执行[14]。然而,这种规划方式无法考虑成像卫星任务环境动态性对于任务收益的影响,其收集的数据的可用率通常较低,且无法有效利用智能成像卫星强大的星上计算能力。因此,成像卫星星座的任务调度方法通常采用“星上任务分配+自主动态规划”方法进行的。该方法将实时获取的任务信息(如任务区域气象信息,卫星当前电量、固存信息等)加入任务规划的要素中进行综合考量(如,当任务区域云量较高时,可自主删除该区域成像数据并重新生成观测需求[15]),其任务数据的可利用率大大提高。但是,正是由于这一特点,星上自主任务规划方法的规划执行结果无法在事先准确预知,而从任务执行结束到数据回传完成通常需要经过数小时的时间,若在全部任务执行结束后再检查任务完成情况,则可能失去对未完成任务的重规划机会。为解决该问题,提出了成像卫星任务可调度性的概念,既通过对以往任务调度数据的学习,结合当前星座内各卫星的任务队列信息,对一系列未来任务调度到确定卫星时该星是否能够安排这些任务进行预测,从而提高成像卫星任务调度的成功率和规划的最终收益。

2.2 成像卫星任务可调度性预测问题描述

成像卫星任务可调度性问题可以通过对该成像卫星以往的历史调度数据结合当前任务的特征以及成像卫星的实时状态分析得到。因此,该问题可以归类为一个模式识别的问题。该方法的流程如下:

图3 成像卫星任务可调度性预测流程

显然的,成像卫星任务可调度性问题与成像卫星的任务执行能力密切相关。因此,首先定义与成像卫星任务可调度性问题相关的成像卫星属性:

(1)成像卫星的敏捷程度:主要影响成像卫星对具体任务的观测时间窗长度和成像卫星在不同任务之间的姿态转换时间。

(2)星上硬件资源:包括成像卫星的电池容量和固存容量,主要影响在确定时间单位内成像卫星能够执行的最高成像次数。

因此,调度场景中的成像卫星集合可描述如下:

其中,S为当前场景卫星集合,Si代表当前场景中的第i颗成像卫星,Capi为成像卫星i的硬件资源总量,用单位时间内成像卫星能够执行成像的最高次数衡量,Chi为成像卫星i的敏捷程度,用成像卫星在不同任务间的姿态转换时间衡量。

另外,成像卫星任务可调度性问题也与具体任务的任务需求以及其占用成像卫星的资源状况有关。通常,成像卫星对地观测任务对其可调度性具有影响的属性如下:

(1)任务ID:任务ID为成像卫星对地观测任务的唯一标示。

(2)任务观测时间窗:该属性决定了成像卫星对一个具体任务的可见时间,通常用任务最早开始时间和任务最迟结束时间标示。

(3)成像时长:成像卫星对一个具体目标成像所需要的时间长度,一般和用户需求以及星上载荷的能力有关。

(4)任务收益:成像卫星对具体目标完成成像任务之后的收益。

(5)资源消耗量:成像任务需要消耗的卫星资源,一般包括电量、固存容量等。

(6)任务区域实时气象条件:成像卫星对具体任务安排观测时任务区域的气象条件,较差的气象条件会对成像卫星的任务收益造成直接影响。

(7)任务区域预测气象条件:由于任务区域的实时气象条件一般不可知,为减小气象条件对任务收益的影响,在任务规划时一般用预测气象条件替代实时气象条件。

因此,成像卫星对地观测任务集合可描述如下:

其中,T代表当前场景的任务序列,idi为第i个任务具有的唯一任务编号,wij为第i个任务由成像卫星j完成时的观测时间窗,dij为第j颗成像卫星执行任务i所需的成像时长,pij为由成像卫星j执行任务i的收益,rij为成像卫星j执行任务i所需的资源。Enij为任务i由成像卫星j执行时的实时气象信息,cij为任务i由成像卫星j执行时的预测气象信息,xij为当前任务的调度性变量,xij取1代表任务i能够被成像卫星j调度执行,xij取值为0代表任务i不能被成像卫星j调度执行。

因此,成像卫星调度性预测问题可以描述为:在S确定的情况下,通过研究当前场景观测任务集合T中不同任务之间的特征关系,在任务未完成调度之前对xij进行赋值并使其尽量接近实际调度结果的问题。

2.3 成像卫星任务可调度性预测问题难点分析

通过对该问题环境及问题背景的分析可知,成像卫星任务可调度性预测问题的难点主要有:

(1)已知的未来任务信息集合T存在一定的不确定性,如通常情况下任务观测时间窗口内的气象状况是无法事先得知的,只能通过具有一定准确率的预测数据进行代替,因此需要考虑不准确的预测数据可能对预测结果产生的影响。

(2)星上自主任务规划可以实时根据环境的动态性信息调整自己的任务调度结果,其观测结果只有在观测结束后才能够得知。另外,星上任务规划的一次改动,可能会影响整个任务的规划序列,从而增加了对地观测任务可调度性预测的不确定性。

(3)成像卫星星上存储和计算资源通常极为有限,因此要求算法的计算复杂度和空间复杂度较小,且尽可能减少所需要的数据存储[16]。

(4)现代成像卫星技术先进、对地观测能力极强,而对地观测任务也日趋复杂,描述任务所需要的属性和约束极多,如何在这些约束和变量中选取对于对地观测任务调度结果据有决定性影响的属性并将其显式化,同样是一个十分重要的问题。

(5)成像卫星面临的任务环境复杂,且成像卫星在不同任务阶段其接受到的任务信息也不尽相同。由于通常情况下成像卫星与地面通信的能力受到星-地链路带宽的限制,通过改写方法的方式应对不同的任务环境极为困难,因此要求该方法在不同环境下均具有较好的鲁棒性,以应对不同的任务环境。

3 成像卫星任务可调度性预测问题求解

通过对以往的成像卫星实际运行数据以及成像卫星任务规划算法的研究和分析,发现以下三个指标对于成像卫星任务规划的结果影响较大:

(1)不同任务时间窗之间的重叠度Olpi;

(2)任务区域上空的气象条件Enij;

(3)任务的完成收益pi。

其中,任务重叠度是指一个任务时间窗与其他任务时间窗的重叠程度。由于成像卫星在执行两次不同的成像任务之间需要一定的时间进行姿态转换和成像载荷的稳定,因此当两个或以上的观测任务的时间窗重叠度较高的时候,通常成像收益较高的任务的执行将可能妨碍成像收益较低的任务执行,其主要影响如下:

任务i的任务重叠度可以通过如下方法计算:

算法名称:任务重叠度Olpi计算方法;

输入:

分配给当前卫星的任务集合T:{ti∈T|i=1,2……n};

图4 任务重叠度对任务执行的影响

任务ti的时间窗信息:ti= {wis,wie};

当前卫星在不同任务之间转换的姿态转换时间:Chi;

输出:任务重叠度Olpi。

由于任务区域上空的实时气象信息Enij通常无法事先预知,因此在进行任务可调度性预测时使用任务上空的预测气象信息cij代替。

因此,最终用于进行任务可调度性预测的输入的数据为:

(1)任务重叠度Olpi;

(2)任务区域的预测气象信息cij;

(3)任务的完成收益pi。

输出的数据为:任务是否执行的决策变量xi。

由于算法使用的输入信息中,任务区域上空的预测气象信息cij具有一定的不准确性,且成像卫星自主任务规划所面临的情况复杂,规划结果的不确定性较强,因此选择基于BP神经网络的方法对任务可调度性进行预测,BP神经网络的构建方法如下:

(1)输入层:在BP神经网络中,输入和输出层的节点数由问题的性质确定。在本问题中,采用全部三个输入数据Olpi,cij,pi做为输入,因此输入层节点数为3。

(2)隐藏层:在BP神经网络中,隐藏层节点数决定了算法的预测准确率和算法的收敛速度,为了在保证预测准确率的基础上加快收敛速度,采用如下经验公式确定该BP神经网络的隐藏层节点数:

其中,m代表隐藏层节点数,n代表输入层节点数,α代表经验参数,在n的数量较小时,通常α的取值为1。因此隐藏层节点数为3。

输出层:由于该问题的输出为任务是否执行,因此在这里取xi∈{0,1},其中xi=1代表预测任务调度成功,xi=0代表预测任务调度失败。因此输出层节点数为1。

最终得到的BP神经网络如下:

图5 BP神经网络结构

4 仿真实验及结果分析

4.1 实验平台及数据准备

实验平台:任务规划方法和任务可调度性预测方法均采用MATLAB2014a环境编写。由于基于启发式规则的任务规划算法具有一次迭代即可完成、规划速度较高的特点[17],比较符合动态环境下的自主任务规划的需求,因此任务规划方法采用基于收益优先规则的启发式算法。任务可调度性预测方法采用MATLAB神经网络工具箱实现。全部程序在Inter Core i7 4710HQ 2.50GHz,8GB内存的计算机下运行。

实验数据:实验训练数据使用随机生成的2000个一定时间范围之内分布的成像卫星任务数据,其中任务的开始时间和结束时间采取整数的秒数计,不考虑成像卫星视场之外可能出现的任务目标。任务分布时间范围最大为480000秒,任务成像时长,任务时间窗长度,任务收益,任务区域上空的实际气象信息均为服从高斯分布的随机数,任务区域天气预报信息的准确度为85%,任务区域的天气预测信息cij和实际情况Enij之间的差值服从高斯分布。成像卫星最大任务执行能力为1400,成像卫星在不同任务之间的姿态转换预留时间为120秒,最终生成的部分任务信息数据如下:

表1 任务属性举例

4.2 算法预测准确率基本结果

算法经过5793代之后由于梯度变化达到收敛要求而收敛,算法训练所需的CPU时间为189秒,在训练集上的最小均方差为0.134,算法训练的过程如下:

图6 训练过程误差变化情况

图7 训练过程梯度变化情况

训练结束后使用200个测试数据检验算法准确率。为保证测试数据的任务分布密度和训练数据相同,该200个测试数据的分布时间范围为32000秒,其他产生规则和训练数据相同。最终得到该神经网络的预测准确率为83%。

4.3 BP神经网络预测成功率鲁棒性结果

由于成像卫星是处于动态环境中,其任务环境、卫星能力、气象预测的准确度均不是固定不变的。因此星上任务可调度性预测方法在动态环境下的鲁棒性也是衡量该算法有效程度的一项重要指标。因此,另外设计了四种不同类型的场景以验证该预测算法在动态环境下的鲁棒性问题。

当成像卫星上的硬件损坏时,可能造成成像卫星任务调度的能力下降;当确定成像卫星面临的成像任务属性发生改变时,也有可能导致成像卫星任务调度能力发生波动。当发生这些变化时,成像卫星任务调度能力同样会发生变化。在本文中,成像卫星的能力Capi用成像卫星在一个任务集合中最大能够安排的任务数量表示。因此,设计如下测试算例验证该方法在卫星任务调度能力发生变化时的算法预测准确率变化。测试算例生成规则和训练样例相同,共包含200个任务,卫星星上资源Capi取值范围为[100,180],最终结果如下:

图8 卫星任务调度能力变化时的算法准确率鲁棒性

由于成像卫星具有能够实时获取任务区域气象信息的能力,因此任务区域的气象条件对成像卫星任务调度有很大影响。由于任务区域的实时气象信息通常无法事先获得,在任务可调度性预测阶段通常采用任务区域的预测气象信息cij代替实时气象信息Enij进行预测。因此,气象预测的精度对于任务可调度性预测的准确率同样具有一定的影响。因此设计如下测试验证该方法在不同气象预测准确率条件下的预测鲁棒性。测试算例生成规则和训练样例相同,共包含200个任务,气象预测准确率取值范围为[0.7,0.9],最终结果如下:

图9 气象预测准确率不同时的算法鲁棒性

另外,成像卫星的任务环境也会发生变化,主要体现在任务密集程度可能会随着时间的变化而发生改变。不同任务密集程度同样会对成像卫星任务调度产生影响,因此设计如下测试验证该方法在不同任务密集程度下的鲁棒性。其中,任务密集程度通过如下公式控制:

其中,wr为任务密集程度,n为当前场景任务总量为当前场景任务时间窗长度均值,Len为当前场景总时长。测试算例其他生成规则与训练样例相同。最终结果如下:

图10 不同任务密集程度的算法鲁棒性

最后,成像卫星的敏捷程度也会对卫星任务调度能力产生较大影响。如前文所述,卫星敏捷能力会影响卫星对单个任务的观测时间窗和在不同时间窗之间的任务转换时间。由于成像时间窗在任务密集程度中有一定体现,因此在这里只检验成像卫星的任务转换时间发生变化时该方法的鲁棒性。测试算例生成规则和训练样例相同,共包含200个任务,卫星任务转换时间Chi取值范围为[60,180],最终结果如下:

图11 不同卫星敏捷能力的算法鲁棒性

最终仿真结果如下表所示:

表2 算法仿真结果

5 结果分析

从仿真实验的结果可以得出如下结论:

(1)该方法在卫星状况正常的情况下具有83%的预测准确率,预测准确率较高。并且,由于成像卫星的星上环境的动态性、调度方法的不确定性等因素,成像卫星任务可调度性预测既不可能做到极高的精确程度,也不需要做到极高的精确程度,因此该准确率可认为能够满足星上任务可调度性预测的需求。

(2)在卫星运行状态发生变化时,该方法具有较好的鲁棒性,能够在卫星运行环境发生一定程度的变化时仍然能够维持方法的正常工作,因此能够适应成像卫星星上环境、任务需求方面的动态性。

(3)在四组鲁棒性实验中,只有最后一组卫星敏捷能力鲁棒性实验中,卫星敏捷能力与预测方法的精确度之间显示出了较为显著的正相关关系。其他三组实验中,成像卫星不同指标的变化与该方法的预测精确度之间均未显示出显著的联系。

(4)卫星任务调度能力的变化对该方法预测精确度的影响最大。从结果可以看出,当卫星任务调度能力发生显著波动时,该方法的预测精确度约出现了8%左右的显著下降。而其他三种情况则未显示出明显的变化。

通过以上分析可以得出如下结论:

(1)成像卫星的星上资源状态,既成像卫星的任务完成能力,对于该卫星的任务可调度性预测方法的准确率具有较大的影响。因此当卫星的星载硬件出现某些不可逆的状态变化时,需考虑停止使用该方法对任务可调度性进行预测。

(2)成像卫星的敏捷能力与任务可调度性预测的结果具有一定的正相关性,因此当成像卫星的敏捷能力发生变化时,可适当考虑修正任务可调度性预测的方法。同时,任务可调度性预测准确性的有序下降,亦可作为卫星故障诊断的一项辅助依据。

(3)在气象预测准确率波动的情况下,该方法仍能够保证该方法的准确率不发生较大的下降。同时可以看到,当气象预测准确率发生较大提升时,该方法的预测准确率也未发生较大程度的提升,因此可以认为,使用具有一定不准确性的气象预测数据代替准确的实施气象数据是可行的。

6 结语

本文设计了一种基于BP神经网络的成像卫星星上任务可调度性预测方法,并设计实验验证了其在动态环境下的鲁棒性问题。实验结果表明,该方法能够达到较好的预测准确度,基本满足星上任务可调度性预测的基本要求,且该方法具有较好的鲁棒性,能够应对一定程度的星上环境和任务需求的动态性变化。同时该方法需求输入少,也能够满足星上环境要求尽量节省算法空间复杂度的需求。该方法的后续研究方向主要有:

(1)研究影响成像卫星任务调度的关键因素,以期更好的抽取具有冲突的任务之间的显著特征。

(2)对于一定程度不准确的信息(如任务区域的预测气象信息),如何能够更好的运用,以减少这类信息的不准确性对预测方法准确性的影响。

(3)设计基于任务可调度性预测结果的任务调度算法,增强任务可调度性预测方法与任务调度算法之间的信息沟通,以提高成像卫星任务调度的成功率。

(4)当成像卫星的状态发生变化时,设计在线学习的方法对当前方法的状态进行修正,以适应星上的动态环境变化。

[1]Li Deren,Yao Yuan,Shao Zhenfeng,et al.From digital Earth to smart Earth[J].Chinese Science Bulletin,2014,59(8):722-733.

[2]李德仁,张良培,夏桂松.遥感大数据自动分析与数据挖掘[J].测绘学报,2014,43(12):1211-1216.

[3]Damiani S,Verfaillie G,Charmeau M C.An anytime planning approach for the management of an earth watching satellite[J].Proceedings of the 4th International Workshop on Planning and Scheduling for Space(IWPSS04),Darmstadt,Germany,June 23-25,2004.

[4]安培浚,高峰等.对地观测系统未来发展趋势及其技术需求[J].遥感技术与应用,2007,22(6):28-29.

[5]Chien S,Sherwood R,Tran D,et al.Using autonomy flight software to improve science return on earth observing one[J].Journal of Aerospace Computing Information & Communication,2012,2(4):196-216.

[6]Grasset-Bourdel R,Verfaillie G,Flipo A.Planning and replanning for a constellation of agile Earth observation satellites[C]//Proceedings of the ICAPS-11Workshop on Scheduling and Planning Applications(SPARK-11),Freiburg,Germang,June 11-16,2011.

[7]Tinker P,Fox J,Green C,et al.Analogical and case-based reasoning for predicting satellite task schedulability[M]//Mun02-Avila H,Ricci F.Case-based reasoning research & development.Berlin Heidelberg:Springer,2005:566-578.

[8]白国庆,陈英武.基于集成BP神经网络的成像卫星任务可调度性预测方法[C]//第二届高分辨率对地观测学术年会,北京,2013年12月20-21日.

[9]Li Jun,Li Jun,Jing Ning,et al.A satellite schedulability prediction algorithm for EO SPS[J].Chinese Journal of Aeronautics,2013,26(3):705-716.

[10]林宗坚,李德仁,胥燕婴.对地观测技术最新进展评述[J].测绘科学,2011,36(4):5-8.

[11]Bai Guoqing,Xing Lining,Chen Yingwu.The knowledgebased genetic algorithm to the disasters monitoring task allocation problem[J].Research Journal of Chemistry and Environment,2012,16(S2):43-50.

[12]高黎,沙基昌.分布式卫星系统自主运行体系结构模型研究[J].空間科學學報,2007,27(3):239-244.

[13]Chien S,Sherwood R,Tran D,et al.Lessons learned from autonomous sciencecraft experiment [C]//Proceedings of the Fourth International Joint Conference on Autonomous Agents& Multiage,Utrecht,Netherlands,July 25-29,2005.

[14]王钧,李军,陈健,等.多目标EOSs联合成像调度方法[J].宇航学报,2007,28(2):354-359.

[15]Sherwood R L,Chien S,Davies A,et al.Real-time decision making on EO1using onboard science analysis[C]//Proceedings of International Asia-Pacific Environmental Remate Sensing Symposium,Honoluu,Hawaii,November 8,2004.

[16]Chien S,Tran D,Rabideau G,et al.Timeline-based space operations scheduling with external constraints[C]//Proceedings of Twentieth International Conference on Automated Planning&Scheduling,Canada,May 12-16,2010.

[17]贺仁杰,高鹏,白保存,等.成像卫星任务规划模型、算法及其应用[J].系统工程理论与实践,2011,31(3):411-422.