敏捷成像卫星自主规划模型与算法*

刘　嵩，陈英武

(1.国防科技大学 信息系统与管理学院， 湖南 长沙　410073；

2. 驻沈阳铁路局长春军事代表办事处， 吉林 长春　130051)



敏捷成像卫星自主规划模型与算法*

刘嵩1,2，陈英武1

(1.国防科技大学 信息系统与管理学院， 湖南 长沙410073；

2. 驻沈阳铁路局长春军事代表办事处， 吉林 长春130051)

摘要：针对敏捷成像卫星自主规划问题，将规划、决策、执行和信息反馈相结合，提出星上自主规划框架，并介绍框架结构和模块功能。在分析主要约束条件的基础上，建立基于时间线约束网络的问题模型。通过将各种卫星动作前后衔接，组合成能够完成不同任务的动作序列，提出一种面向卫星动作序列的启发式算法。该算法分为规划和决策两个部分，并在卫星执行每一个动作序列的同时基于多种启发式规则进行规划，在动作序列执行结束时进行决策。实验结果表明了自主规划框架和模型的合理性以及算法的有效性。

关键词：敏捷成像卫星；自主规划；时间线约束网络；卫星动作序列；启发式

敏捷成像卫星与传统卫星相比具有俯仰、侧摆、偏航等姿态机动能力，具有更大的观测范围和更强的观测能力，因此已经成为航天大国竞相研制的对象[1-2]。但是在传统管控模式下，卫星系统所依赖的指挥控制指令都是由地面测控系统发出的，由于测控限制、通信延迟以及受限的通信带宽和时间窗口等因素存在，即便是敏捷成像卫星也无法在较短的时间内对观测需求的动态变化做出快速响应。另外，地面控制中心必须通过预测卫星状态的方式进行任务规划，所以根本无法避免星上资源的浪费。为解决上述问题且充分发挥敏捷成像卫星的观测效能，最有效的方式就是减少人的干预，并赋予卫星更多的“智能”，使其能够根据观测需求和卫星状态进行自主规划[3-4]。

文献[5-6]对星上自主规划的可行性进行研究，提出反应慎思型自主规划结构，设计了一种迭代式随机贪婪算法，但是没有考虑任务执行结果对自主规划过程造成的影响。文献[7-11]针对EO-1卫星自主规划问题进行深入研究，但是规划方法耗时较长，所以应急响应能力较弱。文献[12]利用迭代修复的方法进行自主规划，但卫星状态实时变化，修复时机很难把握，而且每一次规划的持续时间无法确定。文献[13]提出了逆向动态规划方法，但是问题模型比较简单，没有考虑卫星动作。

1问题描述与自主规划框架

星上工作环境随时间动态变化，主要体现在任务和卫星状态两个方面。任务分为观测任务和数据回传任务，任务的动态变化是由用户需求和天气情况造成的，如用户随时可能提出新的任务需求，又或者由于云层遮挡等天气原因使得某个任务被临时取消。卫星状态的动态变化是指卫星每执行一个任务都会对固存、电量等资源造成一定的影响，但影响程度在任务完成之前是无法准确预测的。因此敏捷成像卫星自主规划问题可以描述为：面对星上动态工作环境，卫星在不需要或较少依靠地面人员干预的情况下，自主为任务指定观测或回传时段，并生成卫星可以执行的动作序列指令，在满足各种约束条件的同时，实现以尽可能少的资源消耗获得尽可能大的观测收益。

在星上使用传统的规划方式，比如文献[2]和文献[14-18]中所使用的方法，将无法解决敏捷成像卫星自主规划问题。因为这些方法要求卫星必须严格执行每一个长周期下的规划方案，不考虑星上动态环境以及任务执行效果。自主规划框架能够实现规划与执行之间的交叉，边规划边执行，是一种在星上将决策、规划、执行与信息反馈相结合的设计，该框架由4个功能模块构成，如图1所示。决策模块：负责确定规划过程结束的时间，并触发规划模块，选择规划结果中的部分动作作为决策结果。根据决策触发时机可以分为普通决策和应急决策。普通决策是指每次产生决策结果之后所触发的决策。应急决策是指当任务发生变化，或是由于卫星状态发生变化而导致决策结果无法执行时所触发的决策。应急决策被触发时，如果正在进行普通决策，那么普通决策将会被终止，从而进行应急决策。

图1　自主规划框架Fig.1　Framework of automatic planning

规划模块：负责根据用户需求、卫星状态和各种约束条件针对规划周期内的卫星动作进行规划。

状态检测模块：负责实时检测和提供当前卫星状态信息，如果决策结果不满足当前星上约束条件，将触发应急决策；如果满足，则将决策结果转换成硬件可执行的动作指令。

执行模块：负责根据动作指令控制硬件执行，并及时反馈执行结果和参数信息。

2CNT模型

应用CNT建模方法对敏捷成像卫星自主规划问题进行建模。CNT建模方法是一种基于约束网络的建模方法，能够针对离散事件动态系统进行建模，文献[19-20]对该方法进行了详细阐述。模型构建考虑了9种敏捷成像卫星动作和5种约束[2]。9种动作分别是观测、数据回传、姿态转换、对日定向、对地定向、相机开机、相机关机、天线开机和天线关机。5种约束分别是时间窗口约束、固存约束、姿态转换时间约束、星上载荷约束和能量约束。模型描述主要用到以下符号：

1)实验模拟的开始时间和结束时间分别表示为STA和END；

2)卫星最大固存容量表示为MMmax，电量的上限和下限分别表示为ENmax和ENmin，单位时间充电量表示为Psun，卫星运行、观测和数据回传时单位时间耗电量分别表示为Psat，Pob，Pdl，姿态转换速度表示为MS；

3)待观测任务集合表示为OB，每个观测任务o∈OB，占用固存大小表示为SZo，收益值表示为Po，即任务的优先级，观测和数据回传时所需要的持续时间分别表示为DOo和DDOo，可用观测时间窗口数量表示为NOo，每个时间窗口的开始和结束时间分别表示为SOo,k和EOo,k，k∈[1,NOo]，卫星姿态角度表示为ORo，待回传任务集合表示为DL；

4)卫星可用的数据回传时间窗口数量表示为ND，每个时间窗口的开始和结束时间分别表示为SDk和EDk，k∈[1，ND]；

5)卫星处于阳照区的时间窗口数量表示为NS，每个时间窗口的开始和结束时间分别表示为SSk和ESk，k∈[1，NS]；

卫星必须依次执行各种动作，动作之间不能重叠，动作在执行过程中必须满足电量和固存约束，而且任何动作都不能永远处于执行状态，卫星的不同状态会对星上电量造成不同程度的影响：

∀i∈[2，h-1],tr∈{obon,ob,oboff,dlon,dl,

dloff,sp,ge,sw}

(tri=1)→((tri+1=0)∧

gei+swi=1)∧(tii=Str)∧(tii+1=Etr)∧

(mmi=mmi-1)∧(0≤mmi≤MMmax)∧

(0≤mmi+1≤MMmax)∧

(eni=eni-1-(tii-tii-1)·Psat)∧

(eni+1=(tii+1-tii)·(spi·Psun-obi·Pob-Psat))∧

(ENmin≤eni≤ENmax)∧

(ENmin≤eni+1≤ENmax))

(1)

观测动作的开始和结束时间必须在某个观测任务的某个观测时间窗口内，动作的持续时间等于该观测任务所需要的观测持续时间，动作开始时卫星固存减少：

(2)

数据回传动作的开始和结束时间必须在某个数据回传时间窗口内，动作的持续时间等于被回传任务所需要的数据回传持续时间，动作结束时卫星固存增加：

(3)

对地定向动作可以在模拟周期内的任意时刻进行，动作执行期间卫星固存不变：

(4)

对日定向动作的开始和结束时间必须在某个阳照区时间窗口内，动作执行期间卫星固存不变：

(5)

姿态转换动作必须在观测、数据回传、对日定向、对地定向这4种动作中的任何一种动作之后连续执行，动作的开始和结束时间由这4种动作的开始时间确定，动作执行期间卫星固存不变：

∀i∈[3，h-3],tr∈{ob,dl,sp,ge},

(swi=1)→((swi+1=0)∧

(tri+2=1)∧(tri+3=0)∧(Esw=tri+2-1)∧

(6)

相机(天线)开机动作必须在姿态转换动作、观测(数据回传)动作之前连续执行，相机(天线)开机动作的开始和结束时间由姿态转换动作的开始时间确定，动作执行期间卫星固存不变：

(7)

相机(天线)关机动作必须在观测(数据回传)动作之后连续执行，相机(天线)关机动作的开始和结束时间由观测(数据回传)动作的结束时间确定，动作执行期间卫星固存不变：

(8)

观测(数据回传)动作之后可能连续执行姿态转换、观测(数据回传)动作，或者相机(天线)关机、相机(天线)开机动作，或者相机(天线)关机、天线(相机)开机动作，或者相机(天线)关机、姿态转换动作和对日定向动作，或者相机(天线)关机、姿态转换和对地定向动作：

∀i∈[2，h-7],tr∈{ob,dl},

tr′∈{ob,dl}-{tr},tr″∈{sp,ge},

((tri=1)∧(tri+1=0))→(((swi+2=1)∧(swi+3=0)∧

(tr″i+6=1)∧(tr″i+7=0)))

(9)

如果观测(数据回传)动作和姿态转换动作连续执行，说明观测(数据回传)动作结束时间与姿态转换动作的开始时间之间的时间较短而且姿态转换动作之后将连续执行观测(数据回传)动作：

(10)

如果相机(天线)关机动作和相机(天线)开机动作连续执行，说明观测(数据回传)动作、相机(天线)关机动作、相机(天线)开机动作、姿态转换动作和观测(数据回传)动作连续执行，而且前一次观测(数据回传)动作结束时间与姿态转换动作的开始时间之间的时间较长：

(11)

对日(对地)定向动作之后可能连续执行姿态转换、对日定向动作，或者姿态转换、对地定向动作，或者相机开机动作，或者天线开机动作：

(12)

3算法设计

根据CNT模型可知，卫星动作之间并不是任意衔接的，前一个动作决定了后一个动作。因此本算法将9种卫星动作组合成为4种动作序列，分别是数据回传动作序列、观测动作序列、对日定向动作序列和对地定向动作序列。每个动作序列可能包含的卫星动作如表1所示。算法分为规划和决策两个阶段，规划结果是由若干个动作序列构成的动作序列组合，而决策结果是指规划结果中的第一个动作序列，也是本算法的输出结果，即卫星下一个将要执行的动作序列。每当卫星开始执行一个动作序列时，将启动算法对下一个规划周期内的动作序列进行规划和决策，从而实现执行与规划同时进行。

表1　动作序列表

为确保卫星每次出地影时都能够有足够的电量，算法的规划周期被设定为从当前正在执行的动作序列的结束时刻至最近一次地影区时间窗口的结束时刻，优化目标为观测并回传的任务收益最大化。考虑星上有限的计算能力，求解速度显得格外重要，因此提出一种基于规则的启发式算法，算法流程如图2所示。求解过程分为4个步骤，分别为选择动作序列、选择动作、选择任务和确定动作时间。规划周期内，算法进行迭代规划，最终的规划结果是收益最高的动作序列组合。

步骤1：选择动作序列。每次以概率p选择优先级最高的动作序列，这意味着选择低优先级动作序列的概率为1-p。数据回传动作序列、观测动作序列、对日定向动作序列和对地定向动作序列的优先级由前至后，由高至低。

步骤2：选择动作。选择动作序列之后，根据前一个动作序列的结束动作和CNT模型约束条件，依据表1确定所包含的具体动作。

图2　算法流程图Fig.2　Process of algorithm

步骤3：选择任务。如果是回传动作序列将选择回传任务，如果是观测动作序列将选择观测任务。选择回传任务时，依据概率在两种规则中选择一种规则进行任务选择：一种是按优先级选择任务，优先选择高优先级的任务进行回传，概率为r；另一种是随机选择任务进行回传，概率为1-r。选择观测任务时，依据概率在三种规则中选择一种规则进行任务选择：一种是按优先级选择任务，优先选择高优先级的任务进行观测，概率为g；第二种是按时间窗口先后顺序选择，优先选择时间窗口靠前的任务进行观测，概率为f；第三种是随机选择观测任务进行观测，概率为1-g-f。步骤4：确定动作时间。如果选择的是数据回传任务，选择当前最早可以使用的回传时间窗口的开始时间作为动作的开始时间，并根据任务的持续回传时间确定动作的结束时间。如果选择的是观测任务，那么选择当前最早可以使用的观测时间窗口的开始时间作为动作的开始时间，并根据任务的持续观测时间确定动作的结束时间。根据观测动作或者回传动作的开始和结束时间可以确定动作序列中其他动作的开始和结束时间。如果选择的是对日定向或对地定向动作，那么根据前一个动作序列的结束时间可以从前至后依次确定动作序列中各动作的开始和结束时间。对日定向和对地定向动作的持续时间随机生成。如果无法确定每个动作的开始和结束时间，或者无法满足模型约束，那么会按照优先级由高至低的顺序选择下一个动作序列。

4实验结果

本实验中采用的数据是参照敏捷卫星IKONOS的轨道和姿态性能，由卫星工具箱(Satellite Tool Kit，STK)软件仿真得到。共设置了6组不同规模的仿真实验，每组实验由10个相同规模的仿真实验构成，采用每组实验结果的平均值作为最终的实验结果。实验模拟24h内的卫星自主规划情况，期间任务与卫星状态动态变化，任务收益范围为1～10。经过反复尝试，将概率参数p设为0.8，r设为0.8，g设为0.6，f设为0.3较为合理。任务完成率表示观测并回传的任务占任务总数的百分比。回传带宽资源利用率表示用于回传数据的时间占全部可用回传时间窗口总时长的百分比。实验还将本算法与文献[2]中的前瞻启发式算法(Look Ahead algorithm,LA)算法进行对比，对比结果中规划一次平均耗时表示规划过程中每迭代一次的平均计算时间。实验结果如表2所示。

表2　实验结果

从实验结果可以看出，虽然随着任务数量的递增，任务完成率逐渐下降，但是不同任务规模的任务完成率均能保持在70%以上。之所以会出现下降趋势，主要是由于任务数量增加的同时加大了任务之间的冲突，而星上资源有限，只能完成部分任务。回传带宽资源利用率保持在80%以上，这说明本算法能够很好地利用回传带宽资源，从而减少了资源浪费。之所以没有达到100%的利用率，主要是由于在规划过程中观测、数据回传、对日定向、对地定向动作交替考虑，所以数据回传时间窗口不能被整体利用。本算法与LA算法的平均耗时是有明显差异的。LA算法是针对地面上静态任务规划问题而设计的，目的是规划出一个近似最优解，所以算法规则比较复杂，耗时较长。但当星上环境突然变化时，即便求得近似最优解，也很可能瞬间变为无效解。因此，针对动态环境和较弱的星上计算能力，能够快速求得一个可行解才是最合适的方式。本算法没有像LA算法那样面向动作进行规划，而是面向动作序列进行规划，搜索空间被大大减少，且省略了对任务进行规划的环节，直接规划动作序列，从而再一次提高了求解效率，因此大大缩短了规划耗时。

5结论

针对动态环境下的敏捷成像卫星自主规划问题展开研究，提出星上自主规划框架和一种与之相适应的启发式算法，并取得了以下成果：

1)星上自主规划框架将规划、决策、执行和信息反馈结合考虑，在控制流程上实现了真正的闭环。因此卫星能够实时根据任务和卫星状态进行规划，充分、合理地利用星上资源。

2)问题的CNT模型能够更加清晰地描述卫星动作之间的约束关系，为动作与动作序列之间的转换工作创造了条件。通过对模型的分析，详细总结每一种动作序列中各种动作的组合情况，并在此基础上提出面向动作序列的启发式算法。算法基于多种启发式规则，能够在动态环境下快速求得可行解，并及时调整规划方案。

3)实验验证自主规划框架和模型的有效性，并将算法与LA算法进行比较。实验结果表明，该启发式算法不但具有更快的求解速度，而且在不同任务数量的情况下均能表现出较高的性能，从而满足敏捷成像卫星自主规划的需求。

参考文献(References)

[1]郝会成, 姜维, 李一军, 等. 基于 Multi-Agent 敏捷卫星动态任务规划问题[J]. 国防科技大学学报, 2013,35(1): 53-59.

HAO Huicheng, JIANG Wei, LI Yijun, et al. Research on agile satellite dynamic mission planning based on multi-agent[J]. Journal of National University of Defense Technology, 2013,35(1): 53-59. (in Chinese)

[2]孙凯, 白国庆, 陈英武, 等. 面向动作序列的敏捷卫星任务规划问题[J]. 国防科技大学学报, 2012, 34(6): 141-147.

SUN Kai, BAI Guoqing, CHEN Yingwu, et al. Action planning for agile earth-observing satellite mission planning problem[J]. Journal of National University of Defense Technology, 2012, 34(6): 141-147. (in Chinese)

[3]姚敏, 赵敏. 基于模糊神经网络的小卫星任务自主调度设计[J]. 宇航学报, 2007, 28(2): 385-388.

YAO Min, ZHAO Min. Small satellite task autonomous scheduling design method based on fuzzy neural network[J].Journal of Astronautics, 2007, 28(2): 385-388. (in Chinese)

[4]陈浩, 景宁, 李军, 等. 基于外包合同网的自治电磁探测卫星群任务规划[J]. 宇航学报, 2009, 30(6): 2285-2291.

CHEN Hao, JING Ning, LI Jun, et al. An approach for autonomous electromagnetic detection satellite constellation scheduling based on outsourcing contract net[J].Journal of Astronautics, 2009, 30(6): 2285-2291. (in Chinese)

[5]Beaumet G, Verfaillie G, Charmeau M C. Feasibility of autonomous decision making on board an agile earth-observing satellite[J]. Computational Intelligence, 2011, 27(1): 123-139.

[6]Beaumet G, Verfaillie G, Charmeau M C. Decision-making on-board an autonomous agile earth-observing satellite[C]//Proceedings of the 8th International Conference on Automated Planning and Scheduling, Australia, 2008.

[7]Abramson M, Carr F, Carter D, et al. Robust planning for the earth observing-1 (EO-1) mission[C]//Proceedings of AIAA Infotech@ Aerospace Conference, 2009.

[8]Rabideau G, Tran D, Chien S, et al. Mission operations of earth observing-1 with on board autonomy[C]//Proceedings of the 2nd IEEE International Conference on Space Mission Challenges for Information Technology, 2006: 367-373.

[9]Sherwood R L, Chien S, Davies A, et al. Real-time decision making on EO-1 using on board science analysis[C]//Proceedings of the 4th International Asia-Pacific Environmental Remote Sensing Symposium, 2005: 47-55.

[10]Chien S, Sherwood R, Tran D, et al. The EO-1 autonomous science agent[C]//Proceedings of the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems, 2004: 420-427.

[11]Sherwood R, Chien S, Tran D, et al. Intelligent systems in space: the EO-1 autonomous sciencecraft [C]//Proceedings of the Infotech@ Aerospace Conference, 2005.

[12]Chien S, Knight R, Stechert A, et al. Using iterative repair to improve the responsiveness of planning and scheduling[C]//Proceedings of the 5th International Conference on Artificial Intelligence Planning and Scheduling, 2000: 300-307.

[13]Verfaillie G, Bornschlegl E. Designing and evaluating an on-line on-board autonomous earth observation satellite scheduling system[C]// Proceedings of the 2nd NASA International Workshop on Planning and Scheduling for Space, 2000: 122-127.

[14]Grasset-Bourdel R. Interaction between action and motion planning for an agile earth-observing satellite[R]. ONERA, 2009.

[15]Rabideau G, Knight R, Chien S, et al. Iterative repair planning for spacecraft operations using the ASPEN system[C]//Proceedings of Artificial Intelligence, Robotics and Automation in Space,1999, 440: 99.

[16]Grasset R, Verfaillie G, Flipo A. Building a really executable plan for a constellation of agile earth observation satellites[C]//Proceedings of International Workshop on Planning and Scheduling for Space, Germany, 2011.

[17]庞秀丽, 于渤, 姜维. 成像卫星任务周规划模型与算法[J]. 国防科技大学学报, 2013, 35(5): 44-51.

PANG Xiuli, YU Bo, JIANG Wei. The weekly task scheduling model and solving algorithm of imagining satellites[J]. Journal of National University of Defense Technology, 2013, 35(5): 44-51. (in Chinese)

[18]刘刚, 王建江, 李志猛. 卫星对地观测任务全周期规划模型[J]. 国防科技大学学报, 2013, 35(4): 62-66.

LIU Gang, WANG Jianjiang, LI Zhimeng. The model of whole cycle mission planning for satellite observation[J]. Journal of National University of Defense Technology, 2013, 35(4): 62-66. (in Chinese)

[19]Verfaillie G, Pralet C. How to model planning and scheduling problems using timelines[C]// Proceedings of the 18th International Conference on Automated Planning and Scheduling,Australia, 2008.

[20]Pralet C, Verfaillie G. Using constraint networks on timelines to model and solve planning and scheduling problems[C]//Proceedings of the International Conference on Artificial Intelligence Planning and Scheduling, 2008: 272-279.

http://journal.nudt.edu.cn

Model and algorithm of automatic planning for agile imaging satellite

LIUSong1,2,CHENYingwu1

(1. College of Information System and Management, National University of Defense Technology, Changsha 410073, China；

2. The Military Representative Office Stationed in Changchun， Changchun 130051， China)

Abstract：Aiming at the problem of automatic planning for agile imaging satellite, the architecture of automatic planning combined with planning, decision making and information feedback was presented. The architecture, components and functions of automatic planning were introduced. The model based on constraint network on timelines was constructed according to the satellite physical constrains and operational constrains. The activity sequences were constructed through connecting various activities. And a heuristic algorithm based on activity sequences was presented. The algorithm was composed of two parts: planning and decision making. The algorithm could plan based on heuristic rules when satellite was performing every activity sequence, and make decision when the activity sequence was completed. Finally, satisfactory results are obtained through experiments, which show that the architecture of automatic planning and the model are reasonable, and the algorithm is efficient.

Key words：agile imaging satellite; automatic planning; constraint network on timelines; satellite activity sequence; heuristic

中图分类号：TP391

文献标志码：A

文章编号：1001-2486(2015)06-096-07

作者简介：刘嵩(1980—)，男，吉林吉林人，博士研究生，E-mail：liusongnudt@sina.com；陈英武(通信作者)，男，教授，博士，博士生导师，E-mail：ywchen@nudt.edu.cn

基金项目：国家自然科学基金资助项目(71331008，61203180)；高分辨率对地观测青年基金资助项目(04060103-5-18)

收稿日期：*2015-01-12

doi:10.11887/j.cn.201506019