面向突发性事件的卫星自主任务规划*

薛志家，杨 忠，李 晶，赵 鞭

(1.南京航空航天大学自动化学院，江苏 南京 210016;2.西安卫星测控中心宇航动力学国家重点实验室，陕西 西安 710043)

突发性事件是指前兆不充分，具有明显的复杂性特征和潜在次生衍生危害，破坏性严重的事件［1］。近年来，国内外重大非常规突发事件形势严峻，如2008年汶川大地震、2010年舟曲泥石流、2011年日本大地震等都对社会经济发展、人民生命财产安全造成了巨大的冲击和损害。而卫星作为一种快速获取地面信息的重要手段，其快速、合理、高效的任务规划能够帮助灾害应急处置部门即时获取全面、精确的灾情信息，进而使其迅速制定更为有效的灾害处置策略。

卫星自主任务规划是指卫星在接收到地面用户发送的任务请求后，自主产生完成任务所需的计划或指令序列。目前，国内外的卫星任务规划研究主要针对常规性任务，文献［2-3］研究了单星任务模型，文献［4-7］研究了多星调度和协同的模型及相应问题求解的禁忌、遗传、粒子群、模拟退火等算法，文献［8-9］研究了突发事件下的卫星任务规划。

上述文献模型仅考虑了载荷约束，且求解算法大多针对多星调度或协同。但是，当多星调度或协同出现覆盖盲区或快速性不能满足应急任务要求时，就需要单星的自主任务规划，且多星任务调度完成后须通过单星自主任务规划去实现。因此，本文针对突发任务的特点，首先利用PDDL(Planning Domain Definition Language)语言建立了综合考虑载荷与平台相关约束的单颗卫星一体化任务模型SP-PIM(Satellite Platform-Payload Integration Model)，然后采用启发式搜索与改进的计划评审技术(Program Evaluation and Review Technique，PERT)相结合的双阶段规划算法，求解完成目标任务所需的满足载荷和平台相关约束的时序规划解，即带时间戳的低级指令序列。最后通过仿真案例验证了本文方法的有效性和时效性。

1 突发性任务的特点及约束分析

由于对地观测卫星在军事和民用领域均有广泛的应用，因此，这里以对地观测任务为例说明突发性卫星任务的特点。

1.1 突发性对地观测卫星任务特点

突发性事件具有爆发突然、事件起因不易察觉、破坏程度巨大3个特点［10］。灾害发生后，对地观测任务需要卫星平台和星上载荷的协调配合来获取仅载荷运动无法获取的目标信息。因此，对地观测任务主要涉及目标观测、数据传输和轨道机动3种类型的任务。例如在一些紧急情况下，当前轨道无法获取有效的目标信息，则需将卫星机动至能够获取目标信息的轨道，再利用星载光学相机或雷达采集目标数据，然后将采集到的目标数据通过数传系统传回至地面站，地面站再将该信息转发给地面控制中心和卫星用户，供分析研判，制定应急策略。

由此可见，突发性对地观测任务不仅涉及观测设备、数传天线等载荷的控制，还与卫星平台的控制相关。这类任务受观测设备性能(如分辨率)、动作间时序关系、动作持续时间、资源、时间窗口、姿态、轨道等约束条件的限制，且这些约束分别属于智能规划领域定义的逻辑、数值、时间初始化文字(Timed Initial Literals，TIL)、时序等约束。因此，突发性卫星任务规划是一类含数值约束的时序规划问题。

1.2 突发性卫星任务的约束分析

观测设备性能、持续时间、资源、时序等约束在文献［2-3］中有较为详细的描述，这里重点分析时间窗口约束和与平台控制关系密切的姿态及轨道约束。

1.2.1 时间窗口约束

与航空飞行器能在有限空间内自由飞行不同，卫星只能沿着一定的空间轨道飞行。因此，卫星在空间执行任务时受时间窗口的约束，该时间窗口由卫星轨道和地面目标及数传设备的位置共同决定，表现为特定的任务必须在相应的确定性的时间窗口内执行。如图1所示，对地观测卫星执行目标观测、数据传输、轨道机动等任务时，都必须满足可见时间窗口约束。例如，动作“采集数据”必须在数据采集窗口内进行。

图1 时间窗口

1.2.2 姿态约束

卫星姿态角可以用卫星本体坐标系三轴和轨道坐标系三轴间的关系来描述，其大小由卫星姿态控制系统自动控制。目前，星载观测设备主要采用星体整体偏转方式，即观测设备的指向调整依赖于卫星姿态的调整。一般的星载观测设备能够垂直于轨道方向摆动［4］，当卫星在轨飞行时，可观测到以星下点轨迹为中心线的带状区域。当需要观测目标在卫星可观测范围外侧，且在卫星当前轨道上通过调整观测设备指向就可观测到目标时，则可通过调整卫星姿态来带动观测设备指向调整，以完成观测任务。

星载数传天线由于需要传输大量的观测数据，一般采用高频定向天线，这类数传天线主要采用自偏转模式，即天线指向的调整仅需天线自身的转动，但卫星姿态的调整会对天线的指向有间接的影响。

1.2.3 轨道约束

卫星轨道通过地心惯性坐标系来描述，对地观测卫星一般处于太阳同步轨道，以保证卫星能够长时间有效观测地面目标。几类需要对地观测卫星进行轨道机动的情况如下:

1)需紧急观测目标处于某卫星可观测范围外侧，星载观测设备指向调整无法满足要求，且短时间内无其它卫星过顶，可进行轨道机动，使该卫星尽早经过目标上空;

2)目标可观测时间太短或无法获取观测目标全局信息时，可通过增加轨道高度使得卫星过顶时间和对地幅宽增加;

3)观测效果不够清晰，且观测设备焦距调整无法满足任务需求，可降低轨道高度来提高观测分辨率。

卫星轨道机动时一般首先将卫星姿态调整至适当位置，然后通过轨控推力器改变卫星速度的大小和方向来实现变轨。一般情况下，卫星在接收到变轨指令时，其飞行程序如表1所示。

表1 轨道机动飞行程序

轨道机动可以分为脉冲式变轨和有限推力变轨等方式，轨控推力器对速度的改变量与燃料消耗质量的关系如式(1)［11］:

式(1)中，Δv为速度增量，Ve为推力器比冲，mi为轨控前燃料贮箱中燃料质量，Δm为轨控过程消耗燃料质量。轨道机动燃料消耗较多，对卫星影响寿命较大，因此轨道机动仅用于一些紧急或必需的状况。

基于上述约束条件的分析，建立突发性卫星任务模型SP-PIM。

2 突发性任务模型及其PDDL描述

SP-PIM是将卫星任务规划问题抽象为一个存在数值约束的时序规划问题，通常可以表示为一个五元组［12］:

其中，V是数值变量v的集合;F是有限原子命题f的集合;A是可用动作a的集合，动作a是一个三元组＜ pre(a)，add(a)，del(a)＞，其中pre(a)、add(a)和del(a)均为原子命题的集合，分别表示a的前提条件、添加效果和删除效果，a∈A;I是初始状态，I⊂F;G是目标状态，G⊂F。

PDDL是规划领域一种成熟的模型描述语言，通常用对象(objects)、谓词(predicates)、初始状态(init)、目标(goal)、动作(action)、函数(function)6种基本成分来描述一个规划问题P。其中对象是构成原子命题f的最基本元素;谓词表示系统的状态属性，用于描述原子命题f，f∈F;动作a的作用是使得状态发生转变，其定义可反映卫星任务中存在的约束关系;函数用于表示数值变量v的变化，v∈V;初始状态描述I，目标状态描述G。

PDDL用域文件(domain file)和问题文件(problem file)来包含上述6种成分，其中谓词、动作、函数位于与领域知识(约束)相关的域文件中，对象、初始状态、目标状态位于与具体问题相关的问题文件中。

因此，对于对地观测任务的建模主要是利用域文件中的3种成分来描述卫星任务规划的领域知识。而对象、初始条件、目标条件则在后续的具体的问题中进行说明。限于篇幅，这里仅给出域文件中的核心部分，即动作列表(表2)，并以轨控推力器点火工作动作fire-obt-thr为例作简单说明，如图2所示。

由于涉及轨道机动的对地观测任务相对复杂，在建模过程中作以下简化处理:1)假设轨控前对地观测卫星已收到或推算得到其当前轨道根数;2)简化变轨时轨控推力器点火工作过程为一次点火;3)假设轨控后的精确定轨工作延后执行。

表2 动作列表

3 求解算法

针对突发性卫星任务规划的特点，本文在Metric-FF(Fast Forward)［12］、SGPlan(SubGoal Plan)［13-14］两类规划器实现算法的基础上，将卫星任务规划这类时序规划问题分解为序列规划和时间调度两个阶段进行处理(如图3)。在序列规划阶段(PhaseⅠ)，将带有时间信息的动作简化为一个原子动作，即不考虑动作的前件、后件、持续时间等信息中的任何与时间相关的信息，然后采用基于松弛规划图的启发式搜索算法，生成一个序列规划解(Sequential Plan，SPlan);在时间调度阶段(PhaseⅡ)，对上一阶段产生的SPlan中的动作进行时间上的调度，即首先根据SPlan建立作业表，然后利用以TIL作为一类特殊紧前动作的改进版PERT［15］算法绘制其对应的计划网络图，并最终生成带有时间戳的时序规划解(Temporal Plan，TPlan)。

据上文所述，突发任务相关的7类约束分别属于规划领域的逻辑、数值、时间初始化文字、时序4类约束。因此，下面分别从这4类约束处理的角度阐述本文的双阶段规划算法。

3.1 逻辑和数值约束

逻辑约束是指动作执行的先后关系，即某个动作的执行是否要在另一个动作完成的基础上再来执行。卫星任务中的分辨率、姿态、轨道、动作次序等约束均属于这一类约束;数值约束一般出现在动作的前件或者目标状态中。卫星任务中的资源约束属于数值约束，如电能、存储空间、燃料等。

图2 fire-obt-thr定义

图3 求解算法结构图

序列规划阶段处理逻辑和数值约束。该阶段主要利用规划器Metric-FF的3大核心技术:放松规划图(Relax GRAPHPLAN，RGP)、加强爬山算法(Enforced Hill-Climbing，EHC)、有用动作(Help Actions，HA)的剪枝策略。如图3，对于一个放松规划问题，RGP用于获取当前状态s的启发值h(s);在EHC对每一个状态进行搜索时，都要调用RGP来生成当前状态的启发值h(s)，并且向EHC提供当前状态的HA信息，即EHC利用当前状态s的HA(s)扩展生成新状态s'，一旦发现存在h(s')＜h(s)的状态s'时，就更新状态s为s'，不断重复上述机制，直至出现状态s″⊃G，或者失败。否则调用最佳优先搜索算法(Best First Search，BFS)。

3.2 时间初始化文字的约束

卫星任务规划领域的TIL约束是指时间窗口约束，其处理过程如下:

1)将TIL作为一种特殊的无前件动作，PhaseⅠ生成的SPlan中包含这类动作;

2)删除SPlan中的TIL类动作;

3)在上文中的时序约束中调用改进的PERT处理TIL约束。

3.3 时序约束

卫星任务中动作的持续时间(Duration，Dur)、开始时刻以及时间窗口约束均属于时序约束，在满足这类约束的前提下，SPlan中的动作可并行执行，约束的处理流程如下:

1)预处理阶段删除动作的持续时间、时间窗口等信息;

2)PhaseⅡ时，将对应的持续时间、时间窗口信息添加到SPlan中的每个动作上;

3)在已知SPlan的基础上，按照PERT算法进行时间调度，最终生成带时间戳的并行规划解。PERT处理流程如下:

Step1:判断SPlan中各动作间的依赖关系。通过SPlan中两个动作前件和后件的关系，判别动作的依赖关系(即两个动作的先后执行关系)，判别准则如下:

ai、aj分别是 SPlan 中的第 i和第 j个动作，且 j＜ i，j=0…i-1(其中，0≤j＜ i＜m，m≥0，m∈Z+，m 为 SP-lan中动作的个数):

a)若pre(ai)⊆add(aj)，则aj是ai的紧前动作(即aj必须在ai开始执行前执行完毕);

b)若del(ai)⊆pre(aj)，则aj是ai的紧前动作;

c)若pre(ai)包含TIL信息，则将TIL作为ai的一类特殊紧前动作。

Step2:根据Step1中得到的依赖关系，生成作业表，作业表反映每个动作的紧前动作和持续时间。

Step3:根据Step2中得到的作业表绘制PERT网络图，并计算PERT图中每个动作的最早开始时间(Earliest Start time，ES)，最早结束时间(Earliest Finish time，EF)，以及关键路线(Critical Path，CP)。其中，ES为动作a所有紧前动作的EF的最大值，如果该动作的前件中涉及TIL时，ES为所有紧前动作的EF和TIL开始时间的最大值;EF为动作a的ES与Dur之和;CP为PERT网络图中耗时最长的一条动作路径。若动作ak的最早开始时间为ESak，

ESaj-1＜ESak＜ESaj，且j＜k＜m， m∈Ζ+则

ESaj=ESak，ESaj+1=ESaj…ESak=ESak-1。

Step4:删除TIL动作，然后将动作a的最早开始时间ES+0.001s(0.001s是一个修正值)作为a的时间戳，再依据时间戳对SPlan中的动作进行排序，输出TPlan，TPlan是一个并行规划解，其时间长度为PERT网络图的CP上动作的Dur之和。

综上所述，突发性任务规划问题有解与否取决于是否存在一个同时满足上述四类约束的带时间戳的动作序列。在序列规划阶段，若RGP能从当前状态扩展至目标状态，则可能有解，然后再进行启发式搜索，如果能够求得满足逻辑和数值约束的动作序列，则存在序列规划解，可进行时间调度处理。否则，无解;若RGP无法扩展至目标状态，则说明该问题一定无解。在时间调度阶段，若序列规划解能满足时序约束，则可求得带时间戳的动作序列，若无法满足，则无解。

4 仿真案例

针对突发性事件的单颗卫星自主任务规划是指卫星在接收到地面任务请求的前提下，星载计算机依据任务模型、初始状态及求解算法求得能够完成任务且满足模型中各项约束条件的低级指令序列。这里通过仿真实例来验证本文模型和算法的有效性及时效性，仿真平台是Linux，编译环境为gcc。

4.1 仿真实例

1)任务背景及需求:目前得到消息，某较大范围海域PHENOMENON6(图 4矩形区域，经度［82°-107°］，纬度［-46°-(-15)°］)发生客机坠毁事件，且当前我方在轨运行观测卫星均无法紧急覆盖该区域，则需紧急调动某高分辨率卫星至应急轨道，以获取疑似海域全局信息，并将所获信息尽快传回地面信息处理中心处理，进而为救援飞机、舰船提供信息支援，缩小搜寻范围(任务需求经PDDL形式化描述后作为高级指令注入卫星)。

2)卫星配置及初始状态:对地观测卫星s携带地面像元分辨率为8m的光学侦查设备一台;星地Ka波段数传天线一台;星载存储器容量15Gbit，电能300W，燃料380kg。

卫星s当前处于太阳同步轨道O0上，观测设备指向地面，数传天线指向O0可视范围内的地面站g1上。当前轨道O0和应急轨道O1的轨道根数如表3，O1比O0轨道高度高20km，因此，卫星s在O1上比O0上的对地幅宽更大。轨道O0和O1的星下点轨迹如图4。

图4 星下点轨迹及疑似海域

表3 O0和O1轨道根数

观测任务涉及的轨道机动、数据采集、数据传输的时间窗口分别为［130s-190s］、［210s-230s］、［240s-260s］。

4.2 结果分析

表4左侧两栏列出了PhaseⅠ生成的不带时间戳的序列规划解SPlan，其中A，B，C 3个动作分别代表激活数传、数据采集、变轨个时间窗口的动作(在PhaseⅠ阶段无实际意义)。表4右侧一列为根据3.3节中Step2得出的动作间的紧前关系，由紧前关系绘制PERT图得出该图中各动作的 ES、EF、Dur，如表5所示。分析PERT图得出CP:M→D→E→F→G→H→I→J→K→L→N→O→P→Q→R→S。完成目标任务需消耗时间为CP的时间长度，经计算时长为249s。

根据3.3节Step4可得完成目标任务的时序规划解TPlan及其甘特图如图5(各动作参数与表4一致)。TPlan就是规划系统根据任务需求产生的带时间戳且动作可并行执行的低级指令序列，它代表通过依次执行观测设备开机，变轨，观测设备指向调整、调焦、数据采集，数传天线指向调整、与地面站捕获跟踪，发送数据等一系列动作，最终将采集到的疑似海域PHENOMENON6的全局信息传回地面站。如图5所示，变轨、数据采集、数据传输等受时间窗口约束的动作须在对应窗口内执行。里程碑代表持续时间为零的动作，是阶段性任务完成的标志，这里用DUMMY-ORBIT-MANEUVER来表示变轨过程的结束。

由此可见，本文所提出的规划方法能够解决突发情况下的对地观测任务规划问题。其模型能够较完整的描述突发情况下卫星任务特点;对应的双阶段求解算法能够处理与平台和载荷相关的分辨率、时序、持续时间、资源、时间窗口、姿态、轨道等约束，最终得到解决突发性任务的时序规划解，即低级指令序列。

表4 序列规划解(SPlan)、紧前动作

表5 动作最早开始时间(ES)、最早结束时间(EF)、持续时间(Dur)

5 结束语

本文在深入分析突发性卫星任务特点的基础上，提出了一种新的卫星自主任务规划方法。该方法采用一种启发式搜索与改进的PERT相结合的双阶段规划算法，来求解以SP-PIM作为模型的突发性任务规划问题。最后通过仿真实例验证该方法，给出了带有时间戳且动作可并行执行的时序规划解。

图5 时序规划解(TPlan)甘特图

与仅考虑载荷约束的模型相比，SP-PIM考虑了与平台关系密切的姿态、轨道约束，使其更能反映突发性事件的特点，实际应用价值更大，但模型动作集中动作的数量增加，各动作的参数个数增多，增加了问题的求解难度。启发值求解是启发式搜索算法中最耗时的部分，本文采用的双阶段规划算法在序列规划阶段忽略了动作的时间信息，使得每个状态启发值的求解仅与逻辑数值约束相关，然后将包含时间窗口约束在内的时序约束统一交由时间调度阶段的改进版PERT来处理，这就减少了每个状态启发值的计算时间，提高了问题的求解效率，有利于对突发性事件的快速响应。

［1］ 韩志勇，翁文国，张维，等.重大研究计划“非常规突发事件应急管理研究”的科学背景、目标与组织管理［J］.中国基金管理，2009，23(4):215-220.

［2］ 程思微，张辉，沈林成，等.基于状态-动作模型的中继卫星操作规划问题建模［J］.系统工程与电子技术，2010，32(5):1001-1006.

［3］ 陈克伟.基于 PDDL的成像卫星操作规划问题研究［D］.长沙:国防科学技术大学，2008.

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

［5］ Wang P，Reinelt G，Gao P，et al.A model，a heuristic and a decision support system to solve the scheduling problem of an earth observing satellite constellation［J］.Computers ＆ Industrial Engineering，2011，61(2):322-335.

［6］ 郭玉华.多类型对地观测卫星联合任务规划关键技术研究［D］.长沙:国防科学技术大学，2009.

［7］ Li J，Yang A，Jing N，et al.Coordinated planning of space-aeronautics earth-observing based on CSP theory［C］∥Geoinformatics，2013 21st International Conference on.IEEE，2013:1-5.

［8］ Li J，Li J，Chen H，et al.A data transmission scheduling algorithm for rapid-response earth-observing opera-tions［J］.Chinese Journal of Aeronautics，2014，27(2):349-364.

［9］ 王钧，李军，陈慧中，等.一种应急条件对地观测卫星成像调度方法［J］.电子学报，2008，36(9):1275-1282.

［10］ Zhang Z，Xiao L，Li S.How to build a preparedness system of unconventional emergency:A case study on Wenchuan earthquake［C］∥ Emergency Management and Management Sciences，2010 IEEE International Conference on.IEEE，2010:269-272.

［11］ JohnosonW. ContentsandcommentaryonWilliam Moore’s a treatise on the motion of rockets and an essay on naval gunnery［J］.International Journal of Impact Engineering，1995，16(3):499-521.

［12］ Hoffmann J.The Metric-FF Planning System:Translating”Ignoring Delete Lists”to Numeric State Variables［J］.Journal of Artificial Intelligence Research，2003，20:291-341.

［13］Chen Y，Wah B W，Hsu C W.Temporal Planning using Subgoal Partitioning and Resolution in SGPlan［J］.JournalofArtificialIntelligence Research， 2006， 26:323-369.

［14］ Hsu C W.Solving Automated Planning Problems with Parallel Decomposition［D］.Illinois:University of Illinois Urbana-Champaign，2011.

［15］ Hillier F S，Lieberman G J.Introduction to operations research［M］.Boston:Tata McGraw-Hill Education，2001.