航天器任务规划中资源约束的可分配处理方法

陈德相，徐文明，杜智远，徐瑞

(1.北京理工大学 宇航学院，北京 100081； 2.中国人民解放军92493部队，葫芦岛 125000)

航天器任务规划中资源约束的可分配处理方法

陈德相1，徐文明1，杜智远2，徐瑞1

(1.北京理工大学 宇航学院，北京 100081； 2.中国人民解放军92493部队，葫芦岛 125000)

面对深空探测过程中环境的不确定性和扰动，航天器需要利用任务规划技术实现自主控制。航天器应用规划算法时，需要考虑到执行活动时满足的时间约束和资源约束。通过分析资源约束之间的关系，提出了可重复资源在规划执行时的可分配处理方法，和判断资源变量是否满足的可分配性条件。通过航天器仿真算例，验证了可重复资源的可分配处理方法在规划执行时的有效性。

可重复资源；规划执行；可分配性；资源约束网络

0 引 言

随着人类对于深空目标的探测，在航天器上实现自主控制的需求也越来越迫切。通过应用人工智能理论中的任务规划技术，可以使得航天器在执行空间任务时，通过星载自主管理系统处理敏感元件采集到的空间环境状态以及航天器的自身状态，并根据航天器的任务目标自主产生需要执行的动作序列，实现航天器的自主运行。

在实际应用规划技术时，需要考虑到在动作执行时的时间约束和资源约束是否满足，并为动作提供确切的执行时间和资源变化值。判定资源约束的有效性时，可以通过最大流方法计算资源的数值范围，并与资源总量相比较。

航天器执行动作时，受到环境的不确定性及扰动的影响，规划动作不是完全可控的，因此资源相关动作之间的关系也将受到实际执行过程的影响，在资源约束不满足时将导致规划失效。为了满足航天器规划的鲁棒性要求，规划结果需要能够对扰动作出动态响应，根据航天器执行情况的反馈，调整动作的执行时间，保持规划的动态可控性。在执行时确定动作的资源改变量的方法称为资源的可分配处理，需要在处理规划动作的约束时，判定资源约束的可调度性。

在Deep Space 1中，NASA-Ame中心针对航天器的规划执行过程，提出了规划执行中时间约束的可调度性。Muscettola等(1998)[1-2]在规划时生成时间约束网络的可分配形式，并在执行时通过可分配形式动态确定动作的执行时间。Wallace等(2000)[3]扩展了时间约束的可分配性，提出了规划中消耗性资源的可调度性，结合时间约束网络讨论了资源约束与时间约束的关系，并给出了消耗性资源的可分配处理方法及可分配性的判定条件。规划中需要处理的资源约束除了消耗性资源，还包括可重复资源，本文针对可重复资源讨论了可分配性的相关计算过程。

分析规划中的可重复资源时，需要求解规划中资源的变化情况。国内外学者对资源调度问题进行了比较深入的研究。Yalcinkaya等(2012)[4]采用时间表(time table)模型描述资源调度问题的时间和资源约束，将其转化为组合优化问题进行了处理。Nicola(2002)[5]分析了动作集随时间变化对资源数量的影响，采用最大流网络描述规划中的资源约束，可以计算资源数量随时间的变化。在国内，李玉庆等(2012)[6]研究了航天测控中的资源调度问题，针对约束优化问题建立模型，并采用遗传算法和蚁群优化-模拟退火算法寻求最优解。

本文在资源约束网络的最大流求解方法的基础上，讨论了航天器可重复资源的可分配处理方法。首先，介绍在航天任务的规划过程中，资源约束的概念以及资源约束网络的表达形式；然后，讨论了可重复资源的处理过程，并在计算资源数量的基础上，分析了可重复资源的可分配性及其条件；最后，通过实际航天器上资源变化的仿真算例，验证了本文算法的有效性。

1 航天器的资源约束模型

1.1 问题提出规划中的资源约束

在航天器进行连续任务规划的过程中，自主规划系统每执行一次规划将产生一个中间规划结果，即包含顺序约束的动作集合。验证规划结果的有效性，需要检验规划结果中动作的时间约束和资源约束是否满足。因此在每步规划完成后进行时间和资源分配，使规划过程中的动作序列成功执行。本文中仅讨论资源约束，假定规划结果中时间取值己经满足所有时间约束。

下面给出规划结果处理过程中的相关定义。

定义1. 规划结果定义为包含一组有限个动作的动作集

(1)

其中ai为规划结果中包含的动作，动作间根据执行条件的要求具有逻辑顺序，航天器根据规划结果中的逻辑顺序约束执行动作。

动作ai可以描述为动作所受约束的集合

(2)

定义2. 资源约束定义为动作执行时需求的资源，表示为

(3)

其中：ai为动作；r为动作ai需求的资源变量；令资源r的数量为qr，Qr为资源的最大数量，资源数量须满足qr∈[0，Qr]；Δqr为动作ai执行后，资源r数量的改变量。动作ai消耗资源时Δqr<0，生产资源时Δqr>0。

在任务规划中，资源可以分为可重复资源和消耗性资源两种类型进行处理。可重复资源在动作开始时消耗一定量的资源，并在动作结束时释放相同数量的资源，因此它的变化可以表示为一系列的阶跃变化。消耗性资源的资源量变化是连续的，可以通过生产或消耗活动变化。

1.2 资源约束网络

根据资源突变之间的时间关系，将规划结果中的资源约束全部表示为资源突变后，可以建立资源约束网络模型，表述所有规划结果中的资源约束。

定义3. 资源突变定义为资源数量的瞬时改变，表示为

(4)

在动作a开始和结束时，资源r的瞬时突变分别表示为资源突变δs和δe，则动作集A中的资源约束可表示为资源突变的集合

(5)

定义4. 资源约束网络，规划结果中的资源约束可表示为带权有向图GR=(VR，ER)，定义GR为资源约束网络。

在GR中，VR是网络顶点的集合，表示规划结果中的资源突变。VR包括所有表示资源突变δ的顶点v，并增加了源点σ和汇点τ，分别表示资源的生产和消耗。对表示资源突变δ的顶点v，根据δ对资源数量的改变情况，可以分为以下两类：

1)生产点VP：该点表示的δ生产资源，即资源数量改变值Δqr，δ>0，存在与源点σ相连的边；

2)消耗点VC：该点表示的δ消耗资源，即资源数量改变值Δqr，δ<0，存在与汇点τ相连的边。

ER是网络边的集合，表示资源突变间执行时间的关系或资源改变量，根据端点的不同，可以分为以下三类：

1)内部边EI=(vi，vj)：表示资源突变δi和δj的时间关系为tδi≥tδj，EI从执行时间晚的δi指向执行时间早的δj，边上的权值为

(6)

2)生产边EP=(σ，vi)：表示执行资源突变δi时生产资源，即Δqr，δi>0，边上的权值为

(7)

3)消耗边EC=(vi，τ)：表示执行资源突变δi时消耗资源，即Δqr，δi<0，边上的权值为

(8)

这样，规划结果中的资源约束就表示为资源约束网络GR=(VR，ER)，包括资源约束的时间关系和资源使用情况。图1所示的资源约束网络表示了包含动作集A的规划结果中的资源约束，其中动作集A={a1，a2，a3}，每个动作表示为两个资源突变点。根据执行动作时的时间顺序，资源突变点在纵向从上向下分布。

图1 资源约束网络Fig.1 Resource constraint network

在规划结果执行时，系统依据时间约束的顺序执行动作，并根据动作的资源约束，对资源数量做出相应改变。

(9)

下面分析各部分资源突变对t时刻资源数量qr(t)的影响。

(10)

对资源数量的改变值表示为

(11)

(12)

(13)

图2 资源约束增量网络Fig.2 Resource constraint incremental network

(14)

对资源数量的改变值表示为

(15)

根据以上对资源突变各部分的分析，在时刻t资源数量的改变值可由下式得出

(16)

随着执行时间t的增加，规划结果中的动作执行结束，各部分资源突变集也发生相应的变化。

(17)

(18)

1.3 可重复资源的可分配性条件

在确定性的规划结果中，资源约束的值为固定的值或区间。在执行规划动作时，动作将根据给定的值或从给定区间中选择合适的值作为资源变化量。但在保证事先给定的资源值或区间满足资源约束时，航天器资源未必能够得到充分利用。通过选择合适的资源分配方法，在执行规划结果的过程中动态调整资源突变的数量，可以更加灵活地利用资源。参考消耗性资源的相关概念，可重复资源的可分配性定义如下：

定义5. 可重复资源的可分配性定义为，在资源约束网络实例化的过程中，当任意一个资源突变在给定范围中取任意值时，都能对所有资源突变给定一组值，使得所有资源约束得到满足。

下面对可重复资源的可分配性条件进行讨论。当所有资源突变的上限总和小于资源总量时，则任意一组值都必然满足所有资源约束，如式(19-1)所示，其中的GR包括了规划结果中的所有动作。

(19-1)

式(19-1)表明了统计从0时刻开始规划结果中的所有活动，资源突变值的区间上限的总和小于资源总量。若在开始规划时资源已被占用一部分，则上式须调整如下，其中的GR包括了规划结果中的所有动作。

(19-2)

式(19)的条件虽然必然满足可分配性，但过于严格，若所有资源突变中某一突变仅可取某一个特定值时，其它突变取任意值仍可满足所有资源约束，则此时可分配性仍能得到满足，且此特定值必为该资源突变的范围下限，如式(20)所示，其中的GR包括了规划结果中除最后一个动作的所有动作。

(20)

式(20)成立时，若取范围下限的资源突变在执行时间上是最后一个动作，则在规划执行过程中，无论前面的动作取区间内的任何值，都能满足可分配性。

通过分析资源约束网络对应的时间约束网络中各动作的时间关系，可以获得动作的时间拓扑顺序。不同于消耗性资源，可重复资源的变化都是瞬时的。消耗性资源需要根据对应动作的时间相互关系确定它们之间互相影响的关系，而可重复资源的突变只需要考虑整体上满足资源约束即可，因此可将整个规划结果的资源突变统一采用式(20)进行检验，并根据时间关系确定可能最后一个执行的动作有哪些。

2 可重复资源的可分配处理算法

由于可重复资源的变化与时间值没有直接关系，只与时间顺序有关系，因此在分析资源数量变化时可以不考虑动作的时间值及时间长度。根据式(20)可得，若在最后一个动作之前的资源突变未达到区间上限，则可将其未使用完的资源在最后一次资源突变时使用掉，以免其仅使用了等于区间下限的资源，可表示为下式，其中的GR包括规划结果中除了最后一个动作的所有动作。

(21)

根据上述讨论，可以给出具有可分配性的可重复资源的执行算法，如图3所示。

图3 可分配性的可重复资源执行算法

Fig.3 Dispatchable execution algorithm of reusable resource

在图3所示算法中，输入数据为规划结果中的动作集合，以及动作集合的执行时间和需满足的资源约束。执行过程中动作的时间值可由可分配的时态规划执行算法生成，本文不作讨论。与资源变化量的值仅有各动作执行时的顺序。最终可生成各资源突变的资源变化量。

3 仿真结果及分析

为了验证算法的有效性，建立了一个描述航天器动作的仿真实例，并采用本文提出的算法进行了仿真验证。假设在航天器生成的规划结果中，动作的时间约束都已得到满足。动作的时间约束如图4所示，且考虑的资源为航天器的存储器。

图4 航天器规划结果中动作的时间约束网络Fig.4 Temporal constraint network of activities in spacecraft planning result

假设航天器中存储器的资源上限为Qr=30，资源初始值Qr，init=23。且为满足突发任务需求，在初始时间段[1，4]范围内，资源变量需满足qr≤20，保留一定的资源余量用于其他任务。在规划结果中，首先进行拍照动作，然后开始在航天器上进行一次数据处理过程，最后在与地面进行通信时，将数据传往地面。在规划结果的动作集合中，需要满足的资源约束如表1所示。

表1 航天器规划结果中的资源约束

下面检测在规划执行过程中，为动作分配资源的执行算法。与判断资源可分配性时类似，分段确定动作的资源变化量。在时间范围[1，4]内，若动作集合{TakePhoto.Begin， TakePhoto.End， ProcessData. Begin}的执行时间分别为2、3、6，则动作TakePhoto.Begin和TakePhoto.End执行时的资源取值可以在给定范围中任意取值。假设TakePhoto.Begin资源变化量取2，TakePhoto.End资源变化量取-4，此时动作ProcessData.Begin作为分段中最后一个动作，资源变化量可取值为(-2)+(3-2)+[(-4)-(-4)]=-1。

在时间范围[4，10]内，若动作集合{ProcessData.End， TransmitData.Begin}的执行时间分别为7、11，则动作ProcessData.End的资源取值可以在给定范围中任意取值。假设ProcessData.End资源变化量取4，则TransmitData.Begin资源变化量可以取区间上限2。

在整个规划的执行时间内，资源变化过程如图5所示。由图示可得，航天器的资源约束始终得到满足，证明了本文提出算法的有效性。

图5 航天器规划结果中资源的变化过程Fig.5 Change process of resource in spacecraft planning result

4 结 论

本文针对航天器环境不确定性和扰动的需要，分析了可重复资源的资源突变之间的关系。通过参考消耗性资源的相关概念，给出了可重复资源的可分配性定义及判定条件，并针对最大化利用资源的目标，给出了可重复资源的可分配处理方法，在满足规划中资源约束的同时，尽可能对资源进行了使用。通过航天器的仿真算例，验证了本文算法的有效性。在将来的工作中，我们将根据结合规划动作在可调度执行时约束参数对执行过程结果的影响，在规划启发式中将航天器资源利用率及灵活性作为评价函数考虑。

[1] Muscettola N， Morris P， Tsamardinos I. Reformulating temporal plans for efficient execution[C]∥Proceedings of the 6th Intelligence Conference on Principles of Knowledge Representation and Reasoning. Trento， Italy：[s.n.]， 1998：444-452．

[2] Tsamardinos I， Muscettola N， Morris P. Fast transformation of temporal plans for efficient execution[C]∥Proceedings of the 15th National Conference on Artificial Intelligence. Madison， USA :[s. n.]， 1998:254-261．

[3] Wallace R J， Freuder E C. Dispatchable execution of schedules involving consumable resources[C]∥Proceedings of the Fifth International Conference on Artificial Intelligence Planning Systems. Breckenridge， USA:[s.n.]， 2000:283-290．

[5] Muscettola N. Computing the envelope for stepwise-constant resource allocations[C]∥Principles and Practice of Constraint Programming-CP 2002. Berlin Heidelberg： Springer， 2002:139-154．

[6] 李玉庆，王日新，徐敏强，等.基于改进遗传算法的一类多资源测控调度问题研究[J].宇航学报，2012，33(1):85-90.[Li Y Q，Wang R X，Xu M Q，et al.An improved genetic algorithm for a class of multi-resource range scheduling problem[J]. Journal of Astronautics， 2012，33(1):85-90.]

[责任编辑：高莎]

Dispatchable Processing Method of Resource Constraint in Spacecraft Mission Planning

CHEN Dexiang1， XU Wenming1, DU Zhiyuan2， XU Rui1

(1.School of Aerospace Engineering， Beijing Institute of Technology， Beijing 100081， China； 2.Unit 92493 of PLA， Huludao 125000， China)

Considering the uncertainty and disturbance of environment in deep space exploration， spacecraft need to use mission planning technology to realize autonomous control. When a spacecraft applies the planning algorithm in aerospace engineering actirities， the time constraints and resource constraints should be considered. By analyzing the relationship between resource constraints， the dispatchable processing method of reusable resources in the execution of planning and the standard to determine whether resource value is dispatchable are proposed. Through the spacecraft simulation example， the dispatchable processing method of reusable resource in planning implementation is demonstrated to be valid．

reusable resource； planning implementation； dispatchability； resource constraint network

2014-10-14

2015-06-01

民用航天预研项目；国家自然科学基金(60803051)；国家863计划项目

TP18

A

2095-7777(2015)02-0180-06

10.15982/j.issn.2095-7777.2015.02.013

陈德相(1989—)，男，博士生，主要研究方向：航天器自主任务规划。 通信地址：北京理工大学宇航学院22信箱(100081) 电话：(010)68913550 E-mail：chendexiangbit@163.com