分布式卫星系统动态任务协同规划算法研究

刘晔伟，周庆瑞，黄 昊

1. 中国空间技术研究院钱学森实验室，北京 100094 2. 北京全路通信信号研究设计院，北京 100070 3. 军事科学院国防科技创新研究院，北京 100071

0 引 言

分布式卫星系统是空间系统的发展趋势，这种体系化的发展，给任务规划带来了挑战.传统卫星任务规划由地面人员依据卫星状态、任务需求等预设条件制定任务方案，这种集中式的工作模式，需要地面充裕的星地通信时间，伴随着高昂的星地沟通成本[1-2].而且其需要考虑大量的参数和约束，要在短时间内生成有质量的规划涉及到复杂的模型求解，会耗费大量资源和时间[3].因而在轨的分布式任务规划是技术发展趋势.

分布式任务规划目前主要采用合同网协商机制，该方法要求分布式卫星系统(distributed satellites system，DSS)具有较理想的连通通信能力，而DSS的通信网络是一个动态切换的时序网络，在目前的技术条件网络通信能力很难满足合同网的需求.其次，合同网机制所需要的通信开销较大，并且很可能由于交互协商过程过于繁琐而通信水平不能与之匹配造成某些任务无法完成.除此之外，系统中的任务是动态随机出现的，要求合同网进行频繁的招投标，而通信受限的状况依然会导致任务无法执行.

针对天基网络通信能力受限下的动态任务规划问题，本文提出了一种基于贪婪算法与合同网结合的DSS动态任务规划算法.采用分布式的结构，其模型相对简单、耗费通信资源少、收敛速度快，并且具有很好的鲁棒性，同时综合贪婪算法与合同网二者的优点，可以实时完成动态任务规划，解决了通信开销过大及任务完成度低等问题.

1 基于贪婪算法与合同网的协同任务规划算法

目前，用于分布式多智能体系统任务分配的算法主要有合同网模型[4]、黑板模型[5]、博弈论[6]以及市场协议方法等.其中合同网模型是目前应用最广泛、也是最经典的任务规划算法.合同网的基本思想是节点之间通过 “招标—投标—中标”这一市场机制进行任务分配，达到系统以较低代价、较高质量完成委托和承揽构成的合同关系.然而在多星任务分配中也面临很多问题.例如在多卫星动态网络中，很多时候卫星之间的通信状况不理想，而合同网较为繁琐的协商过程可能导致卫星无法在规定时间内完成其机制内的多个过程步骤，这样就会发生任务没有被执行的情况.其次，合同网所要求的系统通信代价巨大，这对于目前的分布式卫星动态系统来说很难接受.本文提出采用贪婪算法与合同网混合的算法来解决上述问题.贪婪算法的结构简单，用其执行任务规划简单易行而且通信开销很小；但是当卫星遇到某些自身任务冲突的情况，继续使用贪婪算法可能导致任务执行代价增加，此时就需要合同网机制来解决.针对两个算法的优缺点，扬长避短，将二者有效结合起来使用.这样，既节省了大量通信开销，也可以以较高的优化目标完成任务，具有较高的工程应用价值.

1.1 贪婪算法

贪婪算法是解决最优化问题的一种简便方法，其优点是简单易行.在贪婪算法的每一步都会构造最优解，即它所作的每一个选择都是在当前步骤下某种意义的最优选择.决策一旦做出，就不可再更改.做出贪婪决策的依据称为贪婪准则，是决策的标准，在求解的每一步，依据此标准对变量进行赋值.贪婪算法的关键就在于贪婪准则的设定[7].

虽然贪婪算法机制简单，搜索速度较快，但其同时也有容易陷入局部最优解的缺陷[8].本文的贪婪算法是当系统中的卫星接收到其他卫星任务执行代价信息后，对执行代价进行排序，之后判断最小代价是否为自己执行的代价，若是就由其自己执行此任务.一般情况下经过这样的步骤后，任务集中的大部分任务会被完成，剩下未完成的任务则由合同网机制完成.

1.2 合同网模型

合同网模型 (contract net protocol，CNP) 是SMITH和DAVIS提出的关于任务和资源分配的经典协调策略[9].它最早应用于分布式传感器系统，完成系统控制的传递.合同网协议是用于分布式问题求解环境下各节点间进行协商的一种协作协议.协商方法主要解决分布式系统中当一个节点不具备完成某一任务的能力或由于某种原因需要迁移任务时，如何将任务分配给其它有能力的节点.基于合同网的协商方法是一个多层次的协商过程.在多智能体系统(multi-agent system, MAS)中，两个Agent就任务的委托和承揽构成合同关系.一组这样的Agent构成了合同网系统.根据承担责任的不同,可以将合同网中的Agent划分为:管理者Agent：负责分配任务；合同者Agent：负责执行具体任务.

如图1所示，当管理者Agent需要进行任务分配时，就向合同网中所有其它Agent广播有关任务的信息，即发出招标信息.接到招标的Agent检查自己对解决该问题的相关能力，然后发出自己的投标申请并使自己成为投标者，最后由管理者Agent对收到的投标申请进行评估并从中选择一个它认为最合适的投标者作为中标者，将任务分配给它.从合同网的招投标过程中可以看出，合同网中的各个Agent可以同时具有多种身份，即随着时间、条件和状态的变化，某个Agent既可以是一项任务的管理者，又可能是另一项任务的投标者和中标者.

图1 合同网协商模型Fig.1 Contract network negotiation model

本文中的合同网机制并不用于DSS任务规划的所有情况，只有卫星在当前任务执行时间窗口内具有其他自身冲突任务时，系统为优化任务的执行才会启用CNP算法.任务的优化目标通常包括代价最小和收益最高，在模型上可统一为一个优化目标函数.因此在本文中的为简化表述，将优化目标统一为代价约束.

例如当某卫星在同一时间窗口内有两个可执行任务，而且在获得其他卫星关于此两任务的执行代价信息后，此卫星根据贪婪算法判定两个任务都需要它自己来执行.那么这时候卫星会选择两任务中代价最小的一个去执行，而其会把另一个任务通过建立标书向其他卫星发出进行招标.

2 混合算法的建模与实现

本文将贪婪算法与合同网融合应用于DSS的动态任务规划.本算法以贪婪算法为基本框架，CNP算法应用于卫星自身任务冲突的某些情况.因为贪婪算法容易陷入局部最优的缺陷，此时如果继续使用贪婪算法就会大大增加任务的执行代价.其中具体的合同网应用于当由贪婪算法判定有不止一个的任务由同一卫星在同一时间窗口执行的情况.而贪婪算法则应用于除此之外的其他所有情况.需要强调的是，本算法考虑了实际工程背景，即DSS的通信状态是非理想的(卫星之间的通信是时断时续的，两卫星之间交互一次的时间间隔可能很长).

2.1 DSS任务规划建模

分布式卫星系统观测任务模式如图2所示.其结构为完全分布式结构，包括多颗带有观测能力的卫星，卫星之间在条件允许的情况下可以通信交互.

图2 分布式卫星系统观测任务模式示意图Fig.2 Schematic diagram of observation mission mode of distributed satellite system

假设对环境中的任务描述为Ti(n)(ui(n),ti(n),ci(n),si,ri)，其中i代表任务的编号，n代表卫星的编号，ui(n)代表编号为n的卫星执行任务i时所需要的代价.ti(n)表示卫星n对任务i的执行时间窗口，ci(n)代表在卫星n中与任务i相冲突(这里的冲突指任务执行时间窗口冲突并且用此卫星执行代价最小)的任务，si代表关于任务i的相关信息，例如可以是位置、速度以及图像信息等等.ri代表任务i被执行的次数.这里的任务执行代价ui(n)可以由多个条件进行约束，其可表示为

ui(n)=w1xi(n)+w2yi(n)+...+wnzi(n)

(1)

其中，w代表某个约束的权重，w后的元素代表具体的约束条件.例如本文使用时间条件和卫星传感器的机动代价进行约束，则ui(n)可表示为

ui(n)=w1tci(n)+w2qi(n)

(2)

其中，tci(n)表示任务i执行的具体时间，qi(n)表示卫星n执行任务i的机动代价.为了突出任务执行时间越早越好的重要性，本文设置的w1是要大于w2的.

整个系统有N颗卫星，A={A1,A2,…,AN}，有M个任务，T={T1,T2,…,TM}，这里的任务都是不可再分解的.对于卫星n中的任务i，其记录其他卫星对此任务的执行窗口的参数为

Gi(n)={ti(1),ti(2),…,ti(N)}

(3)

当没有自身任务冲突时，即ci(n)中的任务个数为零时，关于任务i在卫星n中的个体目标函数为

Pi(n)=min(ui(1),ui(2),…,ui(N))

(4)

反之，其个体目标函数为

(5)

其中，k为在卫星n中产生冲突的任务编号，uj(sl)是合同者卫星对某一任务j的执行代价，sl代表不同的合同者卫星.即对任务j有多个合同者对其有执行能力.

2.2 算法描述

如图3所示，具体算法流程如下：

图3 DSS任务规划算法流程图Fig.3 DSS task planning algorithm flowchart

1)初始阶段，任务Ti在卫星n中产生，其描述为Ti(n)(ui(n),ti(n),ci(n),si,ri)(这里可以是多个卫星产生多个任务).

2)卫星n向系统中所有其他卫星发送任务协作信息Ti(n)(ui(n),ti(n),ci(n),si,ri).

3)卫星n接收其他卫星关于此任务的信息.

4)对于卫星中的每个任务，每颗卫星在其任务执行窗口前的t时间(可根据工程约束设置)内对其自身冲突任务ci(n)进行判断.若ci(n)中的冲突任务个数为零，则执行步骤5，否则执行步骤6.

5)对于卫星n中没有与其冲突的任务i，卫星n在此任务执行窗口前的t1(t1

6)若ci(n)中有k个冲突任务，则卫星n会分别对这k个任务在所有卫星中可执行的时间窗口个数进行判断.若k个任务中所有任务的可执行时间窗口个数大于1，则执行步骤7.若k个任务中可执行时间窗口个数等于1的任务个数非零，则执行步骤9.

7)卫星n会分别对这k个任务的时间窗口ti(n)进行判断.若k个任务在此卫星的可执行时间窗口都符合ti(n)≠maxGi(n)，则执行步骤8，除以上之外的其他所有情况执行步骤10.

8)卫星n从多个任务中选择一个代价最小的执行，将此消息传递给其他所有卫星，并且将其余未执行的任务告知其他卫星，其他卫星会依此将这些任务关于卫星n的信息删除.

9)可执行时间窗口个数等于1的任务个数不为零时，卫星n从中选择以一个代价最小的任务执行，并将此结果信息传递给其他卫星.其他可执行时间窗口个数等于1但未执行的任务转向步骤11执行.

10)有多个任务在此卫星的可执行时间窗口符合ti(n)=maxGi(n)，则卫星n从这些任务中选择一个代价最小的任务执行，将此消息传递给其他所有卫星并将不符合ti(n)=maxGi(n)的任务告知其他卫星此卫星n不再执行.其余符合ti(n)=maxGi(n)的任务由步骤11执行.

11)剩余符合ti(n)=maxGi(n)或者符合可执行时间窗口个数等于1的任务由合同网机制执行.卫星n会作为管理者向其他卫星发布任务Ti(n)(ui(n),ti(n),ci(n),si,ri)进行招标.

需要说明的是，当任务没有在第一轮由贪婪算法完成而进入合同网算法中时，为了惩罚其没有尽早完成任务，本算法会将其执行代价增加，即

ui=λui

其中λ为增大的倍数，是一个经验值，本文将其设置为1.5.

12)接收到任务信息的卫星作为合同者会根据任务信息进行自我评定.若符合招标信息，则撰写标书把自身关于任务的信息情况发回管理者卫星n进行投标.

14)若合同者卫星在限制时间tc内接到中标通知或超时，则执行步骤15.反之，则执行步骤4.

15)合同者卫星收到中标通知后执行相关任务，并将此结果传递给其他卫星.

16)结束.

2.3 算法评价指标

DSS动态任务规划的目的是以尽可能少的资源完成更多的任务.因此，一个重要的评价标准就是任务完成度，其用P表示，即

其中，ri表示编号为i的任务的完成次数，用0或1表示，M表示所有任务的个数.

其次，第二个评价指标为任务执行代价(或收益)，如上述模型建立所示

其中，U代表完成所有任务所需的代价，M表示所有任务的个数.

最后一个评价指标是通信指标，通过完成任务所需的平均通信时间C和完成所有任务所需的通信代价，即信息跳数S来表示.C和S表示方法如下：

其中，ti表示完成第i个任务花费的时间，si表示完成第i个任务相关信息的总跳数，M表示所有任务的个数.

3 仿真校验

为验证本算法的有效性和分析算法性能，本文结合具体实例进行了仿真实验与分析.

3.1 实例设置

本文设置了如下场景，首先建立了20颗卫星的分布式天基系统，所有卫星均为对地观测的低轨卫星，与地表距离为500～700 km.假设每颗卫星在可视范围内是可以通信的，DSS的通信网络拓扑随着时间不断变化，因此系统内卫星之间的通信也不是时刻连通的.卫星资源的三维图像如图4所示.

图4 卫星资源三维示意图Fig.4 3D sketch of satellite resources

分别设置观测目标总个数为10、20、30和50的4种场景.需要说明的是，在所有场景中，并不是一次性把所有任务都给了卫星，而是随着时间的推移及卫星按其轨道的移动，这些任务动态地加入到当前DSS系统中.任务分配需要基于各卫星的资源属性、时间窗口属性和轨道信息属性等将任务分配给合适的具有观测能力卫星，本实例简化了资源属性和轨道信息属性的匹配，着重考察任务有效时间窗口与卫星任务可见时间窗口的匹配关系.其中有的卫星可能对同一任务有多个时间窗口，这里取时间最早的一个，目标分布图如图5所示.

图5 目标分布图Fig.5 Target map

此外，影响任务分配的因素还包括任务对遥感器的资源属性要求和分辨率要求、角度要求等，这里仅是为了简单明确任务与卫星的匹配关系，所以做了简化，在真正的卫星任务分配实践中还需要综合考虑多方面因素.

3.2 仿真结果

首先，为了验证贪婪算法与合同网算法在不同情况下的优缺点，分别进行了有自身冲突任务和无自身冲突任务的仿真分析.其中，无自身冲突任务的实例设置任务个数为10，其结果如图6所示.有自身冲突任务的实例设置任务个数为30，其结果如图7所示.两图的横轴为每个任务的编号，纵轴为任务执行代价大小.对于两种算法的任务完成度以及通信指标的对比如表1所示.

图6 无自身任务冲突的算法比较Fig.6 Algorithm comparison of tasks without self-conflict

图7 有自身任务冲突的算法比较Fig.7 Algorithm comparison of tasks with self-conflict

由图5～6以及表1的结果可知，当没有自身冲突任务的时候，贪婪算法和合同网都可以以最优的方案进行任务规划，即用最少的资源代价执行更多的任务，并且任务完成度都是100%，但合同网完成任务所需的平均通信时间比贪婪算法所需的平均通信时间多了不少，并且通信开销也比较大.当有自身冲突任务的时候，在完成任务所需的代价比较上，合同网要明显优于贪婪算法.但合同网的缺点是由于通信时间长的原因，其相对繁琐的协商过程有可能使卫星无法在规定时间内完成其机制内的多个过程步骤，这样就会导致任务完成度的降低，同样其通信开销也比较大.而此时的贪婪算法仍然可以达到100%的任务完成度，但其任务执行代价会高出很多.

表1 贪婪算法与合同网比较Tab.1 Comparison of greedy algorithm and contract net

在验证了贪婪算法与合同网算法在不同情况下的优缺点之后，我们用本文设计的算法与上述两者算法进行了比对，其结果如表2所示.

表2 贪婪算法、合同网协与本文算法的比较Tab.2 Comparison of greedy algorithm, contract net and collaboration algorithm

通过与贪婪算法以及合同网的对比，可以得出结论：本文所设计的贪婪算法与合同网协作的算法可以用较少的任务执行代价、较低的通信开销完成更多的任务.在综合能力上，将二者结合起来的效果要优于只用贪婪算法或只用合同网的情况.

4 结 论

分布式卫星系统任务规划是一个十分复杂的组合优化问题，天基系统的通信状态受限和动态任务等约束更加增大了任务的复杂度和难度.通过对实际约束的研究以及调度目标的分析，初步建立了DSS任务规划模型.在此基础上，通过对贪婪算法和经典分布式多智能体协商机制—合同网的研究分析，本文设计了一种贪婪算法与合同网结合的DSS动态任务规划算法.此算法结合了上述两种算法的优势，能够以较少的任务执行代价、较低的通信开销完成更多的任务，具有更好的工程适用性.