空间站运营在轨任务并行规划技术研究

邱冬阳，卜慧蛟，王 帅，王功波，罗亚中∗

（1.国防科学技术大学航天科学与工程学院，长沙410073；2.载人航天总体研究论证中心，北京100094）

空间站运营在轨任务并行规划技术研究

邱冬阳1，卜慧蛟1，王 帅2，王功波2，罗亚中1∗

（1.国防科学技术大学航天科学与工程学院，长沙410073；2.载人航天总体研究论证中心，北京100094）

空间站运营任务规划技术是空间站长期稳定运营的核心技术。面向我国空间站建设运营需求，对空间站运营任务层建模与规划技术进行了研究。针对任务层规划任务类型多样、约束复杂及资源受限等问题，基于约束满足理论，建立了任务层规划模型；同时针对任务层规划问题规模大、耦合性强及难于求解的特性，提出了一种任务层规划问题并行求解方法。仿真结果表明，本文提出的并行求解方法相较传统的串行规划算法加速比可达14.19，能有效快速求解空间站运营任务层规划问题。研究结论可为我国空间站运营相关规划系统研制提供参考。

空间站；运营；任务规划；并行计算

1 引言

从1971年4月19日，前苏联成功发射世界上第一个试验空间站“礼炮1号”至今，世界上已成功发射了十余座空间站［1］。经过40余年的发展，美国、俄罗斯及欧洲等国相继突破和掌握了一系列空间站核心工程技术，开发了相应的任务规划系统并在空间站上得到了成功运用。

2020年前后我国将建成并运营近地空间站［2］，目前我国的空间站工程正处于起步阶段，开展空间站运营在轨任务规划技术研究、掌握相关技术，对空间站的长期稳定安全运营具有重要意义。

空间站运营在轨任务规划不同于一般航天器任务规划，其涵盖的规划对象和内容更为广泛，任务周期长，规划工作更繁重、难度更大。借鉴当前国际上常用的空间站任务规划层次划分方法，可将我国空间站运营在轨任务规划划分为战略、战术、任务和执行四个层次［3⁃4］。目前，国内一些学者对空间站战略、战术及执行层任务的建模与规划技术进行了研究［4⁃8］。空间站运营任务层规划主要面向两次载人飞船访问间隔时间内的任务规划，具有规划任务种类多样、约束复杂及需求多样的特性，目前的规划模型和算法不能直接有效应用于任务层规划领域，还需进一步研究任务层规划的建模方法和规划算法。

在前期针对任务层规划算法的研究中，由于未充分考虑任务层规划数据规模庞大的问题，导致在使用传统优化算法求解时，计算效率低，计算资源占用量大，无法以合理的时间代价求得可行解。如何提高算法求解效率，是下一步亟待解决的关键问题。

针对上述问题，本文对空间站运营任务层规划的建模与规划技术展开研究，构建了面向工程实际的任务层规划模型，同时借助并行计算技术，提出了能够有效提高规划效率的任务层规划问题并行求解方法。

2 任务层规划模型

2.1 规划问题分析

空间站运营任务层规划的规划周期一般在6个月左右（1个任务周期）。主要依据战术层规划方案和当前空间站运营状态，结合任务设计者的目标期望，在满足空间站各项约束并保证其安全平稳运营的前提下，制定某次载人飞行任务周期内的在轨任务的编排方案，输出以月为单位的在轨操作概要［4，9］。

空间站在轨任务规划涉及到任务、活动、设备和资源等多个要素。其任务通常由一个或多个活动构成，活动按照其规定的次序，由航天员操作空间站站上设备及使用相关资源完成。相较于其它规划层次，任务层规划涉及到的在轨任务种类更为多样，除了常规的轨道姿态控制任务外，还包括空间站平台管理维护、航天员操作、空间载荷应用等，同时，任务层规划具有更细的规划粒度，其规划周期内包含几百至上千个任务。

由于空间站运营所处特殊的内外部环境，各项任务的执行将受到空间站姿态、设备功耗、散热、在轨资源（水、氧气、氮气等）及天地通信数据窗口等约束的限制，一些任务的执行还需考虑任务内部活动间的逻辑关系约束等。此外，空间站运营任务层规划的显著特点是在任务规划周期内长期有航天员驻留，任务的安排还需考虑航天员的安全及生理作息规律的约束。

综上，空间站运营任务层规划问题是一个规划内容多样、约束复杂、耦合性强的大规模复杂系统规划问题。

2.2 规划模型

空间站运营任务层规划问题是在各种约束限制下，有效调度在轨资源，合理安排每个活动的执行时间，本质上是一个约束满足问题。本文在卜慧蛟等对空间站在轨任务规划领域建模研究的基础上［8］，建立了任务层规划模型如式（1）：

其中，V为规划变量集合，D为变量域集合，C为约束集合，F为目标函数集合。

1）规划变量集合

将规划任务中第一个活动的开始时间作为规划设计变量，如式（2）所示：

其中，n是规划任务数。

2）变量域集合

每个规划变量的取值都在相应任务的最早开始时间和最晚结束时间范围内，如式（3）所示：

其中，EarStaTimei和LatEndTimei分别是第i个任务的最早开始时间和最晚结束时间。

3）约束集合

（1）额定功率约束模型

某一时刻执行活动的总功率值不得超过空间站额定功率，如式（4）所示：

其中，t是当前时刻，N是当前时刻执行活动的个数，Mn是活动Activityn在当前时刻t执行所需设备数，Power是设备运行所需功率，W是空间站额定功率。

（2）额度通信带宽约束模型

某一时刻执行活动的总需带宽不得超过空间站额定通信带宽，如式（5）所示：

其中，Bandwidth是活动执行所需通信带宽，BD是空间站额定通信带宽。

（3）在轨航天员人时约束模型

任务规划时，保证活动的执行时间在航天员的工作时间内，尽可能避免占用航天员休息时间，如式（6）所示：

其 中，Activityi.StartTime和Activityi.EndTime分别是航天员i参与执行活动的开始时间 和结束时间， CrewiWorkTimeStart和

CrewiWorkTimeEnd是航天员每天工作开始时间和工作结束时间。

（4）活动间先验关系约束模型

多活动任务的执行需要满足其活动间的先验关系约束，这里定义了“先于（before）”、“同时（e⁃qual）”和“延后（after）”三种类型，如式（7）所示：

其中，ActivityA是 ActivityB的先验活动，TimeNode是时间节点，RaletionType是先验关系类型。先验关系描述如图1所示。

图1 先验关系描述Fig.1 The description of precedence relationship

4）目标函数集合

优先级是评价任务重要性的一个重要指标，在空间站运营过程中希望重要任务尽可能多的得到执行，因此，将规划方案中任务优先级收益最大设定为目标函数，如式（8）所示：

其中，U是规划方案中任务总数。

3 任务层规划问题并行求解方法

智能优化算法是求解规划与调度问题的有效方法。由于任务层规划问题具有变量规模大、约束复杂、搜索区间大等特性，在使用传统智能优化算法进行优化求解时，算法难于收敛，无法在合理的时间代价内求得最优解，只能在计算时间和规划效果上进行折衷。

并行计算（Parallel Computing）是指同时利用多种计算资源解决问题的过程，在求解大规模复杂规划问题上具有显著优势［10］。为了有效求解任务层规划问题，借助并行计算技术，提出一种任务层规划问题并行求解方法。

3.1 并行规划策略

3.1.1 任务并行规划

任务并行规划，即根据问题特性，找到其内在的并行性，在此基础上，将规划任务分解成若干个相互独立的子任务，同时对多个子任务进行并行规划，以提高计算效率［11］。

任务分解是任务并行规划的核心，由2.1节知，任务层规划主要考虑任务内部活动的先验关系约束，其各任务间具有相互独立性。因此，可将整个任务周期，按照设计者的规划需求，以特定的时间步长，划分成若干个子任务周期，同时对各子任务周期内的在轨任务进行规划。

1）任务周期分解

任务层规划的任务周期跨度为一个月至几个月不等，为了充分利用并行计算资源，考虑将整个任务周期根据可调用的并行计算CPU数目进行分解，子任务规划周期如式（9）所示：

其中，Interval为子任务规划时间，EndTerm和StartTerm分别为原任务周期的开始时间和结束时间，n（CPU）为并行计算CPU数目。

由此得到n个子任务周期，其中第i个子任务周期的规划时间区间为：

2）在轨任务并行规划

根据各子任务周期的规划时间区间，搜索在该区间执行的在轨任务，构成各子任务周期的规划任务集合，将其分配给多个CPU进行并行规划，从而达到缩小算法搜索空间、减小求解问题的规模的目的。

3.1.2 算法改进

考虑任务层规划问题约束复杂，为提高算法收敛性能，结合遗传算法，提出一种采用约束冲突修复策略的改进遗传算法，算法流程如图2。

算法中，每个个体代表一个任务规划方案，在初始化种群后，通过约束冲突修复策略，基于时间线，检测方案的约束满足情况，从有约束冲突的不可行初始解开始，迭代性地进行修复，以减少冲突数目，最后得到无冲突的可行解。

图2 改进遗传算法流程图Fig.2 Flow chart of improved GA

约束冲突修复流程：

Step 1：根据初始任务规划方案，设定迭代开始时间t＝t0，t0为子规划周期的规划开始时刻，按设定的时间步长Step对方案仿真推进；

Step 2：判断所有任务在当前时刻t的执行情况，根据执行状态，对相应的资源进行调度，从而获得当前时刻的执行任务集合和资源集合；

Step 3：根据空间站约束条件，检测当前时刻任务方案的约束满足情况；

Step 4：如果方案存在约束冲突，则在执行任务集合中，根据规划决策准则，推迟或取消一个任务，放入未执行任务集合中，同时在资源集合中释放该任务占用的资源；反之则执行Step 5；

Step 5：判断当前时刻是否小于该子规划周期的规划结束时间，若小于则执行Step 2；反之迭代终止。

3.2 并行计算实现

3.2.1 并行环境分析

当前比较流行的并行计算环境可以分为三类：共享式存储、消息传递和数据并行［12］。由于数据并行环境仅适用于数据并行问题，对于非数据并行类的问题，如果通过数据并行的方式来解决，一般难以取得较高的效率。结合求解问题特性，并综合考虑规划算法基本框架及进一步算法集成的单机运行环境，主要采用共享式存储和消息传递两种并行环境实现并行计算。

OpenMP（Open Multi⁃Processing）和MPI（Mes⁃sage Passing Interface）是两种并行计算环境的典型代表，均可调用高性能计算机自身的多核计算资源，即实现基于单机系统的并行计算，其主要特征分析见表1。

表1 并行计算环境主要特征Table 1 Main features of parallel computing environment

OpenMP实现简单，直接将原串行算法中具有并行性的部分进行并行化，其创建的各线程间无需通信，节省了消息传递带来的时间开销，是实现并行计算的理想方法［13］。但在实际算法并行改造过程中，由于任务层规划问题各变量间数据相关性强，其共享式存储机制导致线程间极易出现内存抢占现象，同时规划算法中约束冲突修复策略本身所具有的串行特性导致算法无法有效运用OpenMP进行并行化改造。

MPI应用较为复杂，需对原有串行算法进行良好的并行结构设计，但其可有效解决OpenMP并行实现过程中遇到的问题，同时MPI具有良好的可扩展性，可为下一步空间站运营任务规划系统开发大规模并行计算平台奠定基础。因此，采用MPI实现对任务层规划问题并行求解。

3.2.2 并行程序设计

1）MPI并行程序设计

MPI根据各进程间执行关系可分为主从式并行和对等式并行两种并行模式，主从式并行即主进程根据特定算法对问题进行分解后分配子任务到各从进程，不担任具体的运算任务，接收各从进程的计算结果；对等式并行模式即在任务分解后，主从进程均分配得到子任务进行规划计算［11］。

基于3.1.1节提出的任务并行规划方法，采用MPI对等并行模式及块分配的任务分配策略（将总任务连续分成若干个任务块，每个处理器负责一个块的计算），根据任务规划需求，启动与子任务周期数相同个数的进程，各进程分配一个规划任务，同时调用规划算法对问题进行优化求解，使各进程间负载均衡，降低消息传递时间开销，以获得最大的加速性能。并行规划流程见图3。

2）加速比分析

加速比（speedup）是衡量并行程序加速性能的重要指标，其计算公式如式（11）所示：

其中，Ts和Tp分别为程序串行和并行的计算时间。

（1）串行计算时间

串行计算即在空间站全任务周期下开展的规划计算，其规划时间的计算公式如式（12）所示：

其中，tpretreatment为规划信息读取，任务分配等规划预处理操作时间开销，tmissionplan为任务规划时间开销。

规划时间主要取决于算法计算时间，设Gmax为遗传算法最大进化代数，Psize为种群规模，为一次迭代计算的平均时间，则规划时间如式（13）所示：

由于算法采用了基于时间迭代的约束冲突修复策略，在迭代时间步长一定的情况下，其规划时间受任务周期和规划任务数的影响。

（2）并行计算时间

通过并行程序设计，知各进程间无通信时间开销，根据3.1节的并行规划策略，对任务周期进行分解后，其各子任务周期的规划时间区间和规划任务数均近似为原来的1/n（CPU）。各子规划周期同时计算，则并行计算时间如式（14）所示：

加速比为：

当tmissionplan》tpretreatment时，S≈n2（CPU），即最大加速比可近似达到并行计算CPU数目的平方。

图3 并行规划流程Fig.3 Parallel planning process

4 算例仿真及结果分析

4.1 问题配置

以我国空间站运营为背景，设定任务周期为2023年9月1日—2023年12月31日，驻留2人。参考国际空间站运营需求，需规划的任务包含空间站例行维护维修、空间生物技术实验、医学生物学研究及观测科学研究等，共9大类，3127项子任务，其任务分布如图4所示。表2展示了一个典型的任务模型描述实例。

图4 任务分布Fig.4 Distribution of mission

表2 任务模型描述Table 2 Description of mission model

任务的优先级共分为5级，其中1、2级任务为保证航天员安全驻留和空间站正常运营的关键任务，必须执行；3到5级任务主要为空间应用类任务，在空间站资源受限的情况下，希望该类任务尽可能多的完成，以提高空间站的运营收益。本文以任务优先级作为规划决策准则，即当发生约束冲突时，优先保证优先级较高的任务执行。

表3给出了在轨航天员信息。这里定义航天员休息事件的优先级为3，优先级大于3的任务可以占用航天员休息时间，以保证空间站交会对接、加注及舱外实验等重要任务的执行。

表3 在轨航天员信息Table 3 On⁃orbit astronaut information

设定空间站额定功率为3200 W，额定通信带宽为600 Mbps。规划算法参数及并行环境配置分别见表4和表5。

表4 算法参数配置Table 4 Algorithm parameter configuration

表5 并行环境配置Table 5 Parallel environment configuration

4.2 结果分析

由于任务周期跨度为4个月，因此考虑将任务周期分解成4个子任务周期，同时调用4个CPU进行并行计算。表6和图5分别给出了并行计算的加速效果和并行计算时CPU使用情况。

表6 CPU并行程序加速效果Table 6 Speed⁃up of CPU parallel program

图5 CPU使用情况Fig.5 CPU usage

根据3.2.2节的加速比分析，当n（CPU）＝4时，其理想加速比S≈16，但在实际规划过程中由于受到规划预处理等操作时间开销的影响，实际加速比达到了14.19。由此可知，本文提出的并行规划策略可有效快速求解任务层规划问题。

任务层规划获得的是以月为单位的空间站每天的执行任务列表，但不精确到任务具体执行时刻。由于任务数据量过大，表7以航天员 A在2023年9月1日的执行任务列表为例展示了典型的任务层规划结果方案。

表7 2023年9月1日任务列表（航天员A）Table 7 2023⁃09⁃01 mission list（Astronaut A）

规划结果方案均满足空间站各项约束要求。图6展示了不同优先级任务的完成情况如，其中优先级1、2级的任务完成率达100%，保证了在轨航天员安全驻留及空间站平台的正常运行；3到5级任务的完成率分别达到92%、99%和73%，实现了较高的空间应用收益，其任务未执行的主要原因是航天员工作人时、电能、设备及带宽等资源不满足任务的执行需求。空间站工程总体将根据任务层规划得到的任务初步执行方案及工程目标，对未执行任务需求进行调整，最终确定满足工程要求的任务执行方案。

图6 不同优先级任务的完成情况Fig.6 The completion of different priority missions

5 结论

经验证本文建立的规划模型，能有效描述多类型任务、复杂约束以及多样化需求的空间站运营任务层规划问题，提出的基于MPI并行计算的任务层规划问题并行求解方法能够充分利用计算资源，获得良好的运行加速比，快速求得问题可行解，可为我国研制空间站运营相关规划系统提供参考。

（

）

［1］Popov A.Mission planning on the International Space Station program concepts and systems［C］//IEEE Aerospace confer⁃ence，2003：3427⁃3434.

［2］周建平.我国空间站工程总体构想［J］.载人航天，2013，19（2）：1⁃10.Zhou Jianping.Chinese space station project overall vision［J］.Manned spaceflight，2013，19（2）：1⁃10.（in Chinese）.

［3］罗亚中，林鲲鹏，唐国金.空间站运营任务规划技术评述［J］.载人航天，2012，18（2）：7⁃13.Luo Yazhong，Lin Kunpeng，Tang Guojin.Review on space station operation mission planning technology［J］.Manned spaceflight，2013，18（2）：7⁃13.（in Chinese）

［4］朱阅訸.空间站运营在轨事件与货运补给规划方法研究［D］.长沙：国防科学技术大学，2015.Zhu Yehe.Study on Space Station Operation On⁃Board Events and Cargo Supplying Planning Approach［D］.Changsha：Na⁃tional University of Defiance Technology，2014.（in Chinese）

［5］李志海，侯永青，严厚民，等.空间站长期运营任务规划建模初步研究［J］.载人航天，2013，19（5）：52⁃58.Li Zhihai，Hou Yongqing，Yan Houmin，et al.Preliminary modeling study on long⁃term operation mission planning of space station［J］.Manned spaceflight，2013，19（5）：52⁃58.（in Chinese）

［6］林鲲鹏.空间站长期运营总体任务规划与仿真方法［D］.长沙：国防科学技术大学，2014.Lin Kunpeng.Overall Mission Planning and Simulation Ap⁃proaches for Space Station Long⁃duration Operations［D］.Changsha：National University of Defiance Technology，2014.（in Chinese）

［7］Bu H J，Zhang J，Luo Y Z，et al.Multi⁃objective optimiza⁃tion of space station short⁃term mission planning［J］.SCI⁃ENCE CHINA Technological Sciences.2015，58（12）：2169⁃2185.

［8］卜慧蛟，张进，罗亚中，等.基于本体理论的空间站短期任务规划领域建模研究［J］.载人航天，2016，22（2）：191⁃201.Bu Huijiao，Zhang Jin，Luo Yazhong，et al.Modeling of Space Station Short⁃Term Mission Planning Domain Based on Ontology Theory［J］.Manned spaceflight，2016，22（2）：191⁃201.（in Chinese）

［9］林鲲鹏.空间站运营总体任务规划技术研究［D］.长沙：国防科学技术大学，2010.Lin Kunpeng.Study on Space Station Operation Mission Plan⁃ning Technology［D］.Changsha：National University of Defi⁃ance Technology，2010.（in Chinese）

［10］陈国良，孙广中，徐云，等.并行计算的一体化研究现状与发展趋势［J］.科学通报，2009，54（8）：1043～1049.Chen G L，Sun G Z，Xu Y，et al.Integrated research of par⁃allel computing：Status and future［J］.Chinese Sci Bull，2009，54（11）：1845⁃1853.（in Chinese）

［11］安竹林，基于MPI的并行遗传算法研究［D］.合肥：合肥工业大学，2006.An Zhulin.Research on Parallel Genetic Algorithms Based on MPI［D］.Hefei：Hefei University of Technology，2006.（in Chinese）

［12］都志辉.高性能计算并行编程技术—MPI并行程序设计［M］.北京：清华大学出版社，2001：7⁃9.Du Zhihui.Parallel Programming technology for High Per⁃formance Computing⁃MPI parallel programming［M］.Beijing：Tsinghua University Press，2001：7⁃9（in Chinese）

［13］陈树敏，罗俊博，陈青.并行计算技术的几种实现方式研究［J］.计算机技术与发展，2015，25（9）：174⁃181.Chen Shumin，Luo Junbo，Chen Qing.Research on ways of parallel computing technology［J］.Computer Technology and Development，2015，25（9）：174⁃181.（in Chinese）

Research on Parallel Planning Technology for On⁃Board Mission Planning of Space Station Operation

QIU Dongyang1，BU Huijiao1，WANG Shuai2，WANG Gongbo2，LUO Yazhong1∗
（1.College of Aerospace Science and Engineering，National University of Defense Technology，Changsha 410073，China；2.Manned Space System Research Center，Beijing 100094，China）

Mission planning of the space station operation is a key technology to keep the long⁃term steady on⁃orbit operation of a space station.In terms of the operation requirements of China's space station（CSS），the modeling and planning methods of the space station pre⁃increment planning were studied.The pre⁃increment planning model，combining the theory of constraint satisfaction，was es⁃tablished to deal with issues such as multi⁃type missions，complex constraints，limited resources et al.Considering the features including the great⁃scale of problems，strong coupling，and solving diffi⁃culties，a parallel planning method was proposed.The simulation results showed that the speed⁃up ratio of the parallel planning method was 14.58 as compared with the traditional serial algorithm，which could effectively solve the problem.The implication of the current research conclusion may provide references for the development of CSS operation system.

space station；operation；mission planning；parallel computing

V423.7

A

1674⁃5825（2016）06⁃0680⁃07

2016⁃05⁃30；

2016⁃10⁃25

湖南省自然科学基金（2015JJ3020）；国防科学技术大学科研计划（JC14⁃01⁃05）；载人航天预先研究项目（010103）

邱冬阳（1991－），女，硕士研究生，研究方向为空间站运营任务规划。E⁃mail：gfkdqiu＠163.com

∗通讯作者：罗亚中（1979－），男，博士，教授，研究方向为载人航天任务规划。E⁃mail：luoyz＠nudt.edu.cn