空間站運營在軌任務并行規劃技術研究

邱冬陽，卜慧蛟，王 帥，王功波，羅亞中?

（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］?？臻g站運營任務層規劃主要面向兩次載人飛船訪問間隔時間內的任務規劃，具有規劃任務種類多樣、約束復雜及需求多樣的特性，目前的規劃模型和算法不能直接有效應用于任務層規劃領域，還需進一步研究任務層規劃的建模方法和規劃算法。

在前期針對任務層規劃算法的研究中，由于未充分考慮任務層規劃數據規模龐大的問題，導致在使用傳統優化算法求解時，計算效率低，計算資源占用量大，無法以合理的時間代價求得可行解。如何提高算法求解效率，是下一步亟待解決的關鍵問題。

針對上述問題，本文對空間站運營任務層規劃的建模與規劃技術展開研究，構建了面向工程實際的任務層規劃模型，同時借助并行計算技術，提出了能夠有效提高規劃效率的任務層規劃問題并行求解方法。

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%，實現了較高的空間應用收益，其任務未執行的主要原因是航天員工作人時、電能、設備及帶寬等資源不滿足任務的執行需求?？臻g站工程總體將根據任務層規劃得到的任務初步執行方案及工程目標，對未執行任務需求進行調整，最終確定滿足工程要求的任務執行方案。

圖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