面向突發任務的空間站任務重規劃方法

牟帥,卜慧蛟,張進,羅亞中*

國防科學技術大學 航天科學與工程學院,長沙 410073

面向突發任務的空間站任務重規劃方法

牟帥,卜慧蛟,張進,羅亞中*

國防科學技術大學 航天科學與工程學院,長沙 410073

針對空間站在軌運營出現突發任務的情況,提出一種基于啟發式規則的任務重規劃方法,滿足了方案重規劃的快速響應需求。根據任務執行的連續性特點和沖突狀態,建立了空間站突發任務規劃領域模型。考慮重規劃過程中任務包含活動間復雜約束關系傳播的影響,提出了時間回溯迭代沖突化解策略,同時依據任務執行時間間隔,提出針對間隔插空的時間冗余啟發式規則。基于時間回溯迭代沖突化解策略和時間冗余啟發式規則,對原任務執行計劃進行實時重規劃,實現了突發任務的快速響應。應用算例分析表明,提出的重規劃方法可以成功地滿足空間站突發任務規劃需求,實現實時更新空間站在軌任務執行詳單的目的。

空間站;任務規劃;啟發式;突發任務;快速響應

空間站任務規劃是空間站長期運營、有效管理的關鍵技術,當前的空間站任務規劃研究主要滿足國際空間站運營需求。國際空間站已經在軌運行多年,參加運營的主要國家和組織已經開發了多種任務運營規劃系統。美國約翰遜中心開發的集成規劃系統(Integrated Planning System,IPS)是國際空間站的核心任務規劃系統[1]。JPL人工智能部開發了連續活動調度規劃執行和重規劃系統[2-3]。歐洲航天局針對其運營艙段,開發了運營準備與規劃系統(Operations Preparation and Planning System,OPPS)[4]。但是,上述文獻主要介紹了國際空間站軟件系統的功能架構,公開的國外文獻中很少有針對空間站任務規劃具體模型和方法的研究論述。

而國內在空間站任務規劃方面的研究還處在起步階段。文獻[5-6]結合國外空間站運營任務規劃概念和典型的空間站任務規劃系統,對中國空間站運營任務規劃關鍵技術提出了發展建議。文獻[7-8]對空間站長期運營任務規劃及建模進行了研究。文獻[9-10]對空間站短期任務規劃進行了分析研究,提出了基于本體模型的任務規劃模型和基于時間迭代的任務沖突化解策略。

上述研究中沒有考慮空間站任務執行過程中出現突發情況的影響,而在工程實際中,空間站在軌設備可能會發生故障,人員操作失誤等也難以完全避免。當這些突發情況發生時,航天員必須首先處理突發事件,這樣就會造成當前執行任務延遲或取消,原始的任務執行計劃便失去了時效性。所以,尋找一種應對突發任務的快速重規劃方法是十分必要的。在其他領域,文獻[11-13]對面向動態需求的衛星滾動式重調度方法進行了研究。文獻[14]解決了高空飛艇的應急調度問題。但是,這些研究主要針對包含單個活動的觀測任務,對于時效性強、包含活動多、約束復雜的空間站在軌運營任務,這些方法則不能完全適用。文獻[15-17]對深空探測器復雜約束和啟發式任務規劃方法進行了研究。但是,這些方法沒有考慮重規劃過程中約束傳播以及突發任務對原任務執行計劃帶來的影響,也不能直接應用于空間站任務重規劃。

本文主要針對空間站運營過程中出現突發情況時,對原任務執行計劃進行快速地重新規劃。提出時間回溯迭代沖突化解策略,以解決重規劃過程中復雜約束關系傳播造成的影響,提出時間冗余啟發式規則,以實現對突發任務的快速響應,并維持原任務執行計劃的相對穩定性。

1 問題描述

面向突發任務的空間站任務重規劃問題是指在空間站在軌運行期間,當設備故障、人員操作失誤、外部環境改變等不確定因素發生時,快速對突發情況進行分析處理,并對任務執行計劃進行重新規劃。

1.1 重規劃問題描述

重規劃問題可以視為一個快速求解的約束滿足問題,即不僅要求規劃方案結果滿足各項約束條件,還要求重規劃時間盡可能短并維持原任務執行計劃的相對穩定性,以實現對突發任務的快速響應。重規劃問題描述如圖1所示。

圖1 重規劃問題示意圖Fig.1 Illustration of re-planning problem

初始條件為原在軌任務執行詳單,當突發時刻(Pop-up Moment)有突發任務發生時,根據資源等約束條件對正在執行任務進行模型重構,并應用合理有效的規劃求解策略,對突發任務、重構后任務以及原計劃執行任務進行實時重新規劃,輸出新的、滿足要求的在軌任務執行詳單。

1.2 概念模型描述

文獻[8]應用本體模型對空間站短期任務規劃概念進行了詳細描述,建立了任務、活動、資源、約束等概念本體模型,并應用屬性集合和關系集合分別對各概念模型進行描述。本文在其工作基礎上增加了任務類型,明確了任務優先級定義,提出了任務連續性等概念,建立了面向突發任務的空間站任務重規劃模型。

任務概念描述如下:

式中:M 為任務;dM.I.為任務編號;NM.N.為任務名稱;tM.ST.為任務最早開始時間;tM.ET.為任務最晚結束時間;EM.P.為任務優先級,取值在0～100范圍內;OM.OI.為其他任務信息;SM.T.為任務類型,并根據任務重要級別分層定義其優先級:vCr為5級突發型(90～100),vEm為4級緊急型(70～89),vDa為3級日常維護型(50～69),vPa為2級載荷型(20～49),vUn為1級未知型(0～19);SM.C.為任務連續性類型:vNo為禁斷型,即如果任務執行過程中受到干擾不能連續執行,則該任務執行失敗,放入不可執行任務集合,vAl為允斷型,即任務在執行過程中可以暫停執行,而不影響其后續執行和任務結果,vNe為重拾型,即如果任務執行過程中受到干擾不能連續執行,其已經完成操作會對后面操作產生較大影響,不能繼續執行,但是在軌資源和任務執行條件允許該任務重新執行;A為任務包含活動。

活動概念描述如下:

式中:dA.I.為活動編號;DA.D.為活動持續時間;tA.S.為活動開始時間;OA.OI.為其他活動信息;SA.R.為活動間時序關系類型:vEq為與關系任務同時發生,vBe為早于關系任務發生,vAf為晚于關系任務發生;R為活動占用資源。

資源概念描述如下:

式中:dR.I.為資源編號;CR.Max.為資源額定容量;pR.P.為資源功耗;QR.Th.為資源散熱;OR.OI.為其他資源信息;SR.T.為資源類型:vSt為平臺型,vPa為載荷型,vUk為未知型。

1.3 規劃模型描述

1)設計變量

將突發任務開始時刻和由突發任務引起原任務執行計劃中發生調整任務的重新開始時刻作為設計變量。設計變量描述如下:

式中:X為設計變量;t(i)為第i個重規劃任務開始時刻;tM.ST.(i)為第i個重規劃任務最早開始時刻;tM.ET.(i)為第i個重規劃任務最晚結束時刻;n為由突發任務引起原任務執行計劃中發生調整任務總數。

2)約束分析

約束分析主要考慮空間站在軌運營功耗、散熱、數據傳輸帶寬、資源額定容量、天地通信窗口、活動間先驗關系等約束。各項約束描述如下:

式中:t為規劃時刻;nw為t時刻正在執行任務數;pR.P.(i)為t時刻正在執行任務功耗;pMax為額定功耗;QR.Th.(i)為t時刻正在執行任務散熱;QMax為額定散熱;bB.W.(i)為t時刻數據傳輸任務占用帶寬;bMax為額定帶寬;CR.A.(i)為t時刻資源占用量;tC.C.(j)為第j個通信任務執行時間;[tC.S.(j),tC.E.(j)]為通信窗口;m為通信任務個數。

3)目標函數

考慮空間站長期在軌運營的安全性與穩定性,應該盡量減小突發任務對原任務執行計劃產生的影響,因此本文提出任務執行計劃穩定性指標作為規劃的目標函數。

式中:f為穩定性指標;tri為執行時間發生改變任務的重排后開始時間;ti為執行時間發生改變任務的原開始時間;δm為任務重要級別系數;nc為取消執行任務總數。

2 重規劃方法

面向突發任務的空間站任務重規劃是當空間站在軌運營有突發任務發生時,對與突發任務存在約束沖突的正在執行任務相關參數進行實時更新,即任務模型重構,并對突發任務以及重構后任務進行合理再安排,并通過一系列快速、有效的沖突化解策略,得到不存在任何約束沖突的規劃結果,實時更新在軌任務執行詳單。

2.1 突發任務預處理策略

空間站在軌運營有突發任務發生時,首先對與突發任務存在約束沖突的正在執行任務進行搜索,再根據任務連續性對沖突任務相關參數進行實時更新,建立沖突任務重構模型。

1)沖突任務搜索。根據突發任務發生時刻搜索此時正在執行的任務,依次判斷此時資源、功耗、散熱、傳輸帶寬等約束條件是否滿足,如果有約束超出額定值,則依據任務優先級將其中最小優先級任務暫停執行并放入重構集合,循環判斷各約束條件直至無約束沖突存在。沖突任務搜索流程如圖2所示。

2)沖突任務模型重構。依次判斷上文得到的重構集合中任務連續性性質,若其為禁斷型,則直接取消執行該任務,并宣布任務執行失敗,放入不可執行任務集合;若其為允斷型,則依據未執行活動對該任務包含活動、活動的持續時間以及資源占用等相關參數信息進行更新,得到重構后任務;若其為重拾型,則不考慮其已經執行過活動,直接將該任務整體推遲;并將重構后任務和推遲后任務放入重規劃集合。沖突任務模型重構流程如圖3所示。

圖2 沖突任務搜索流程圖Fig.2 Flow chart of conflict mission search

2.2 時間回溯迭代沖突化解策略

針對每個空間站任務由多個活動組成,不同任務包含活動間存在一定的約束關系,在沖突化解過程中,由于任務執行時間調整可能會產生新的約束沖突的情況,提出基于時間回溯迭代的沖突化解策略。沖突化解流程如圖4所示。

圖4中,M1、M2為執行時間存在重疊的2個任務,且 M1優先級大于 M2。a11、a12、a13、a14、a15、a16為 M1包含活動,a21、a22、a23、a24、a25、a26為M2包含活動,a13與a21存在約束沖突,a15與a24存在約束沖突。時間回溯迭代沖突化解策略按照一定步長在時間線上推進,判斷每一個時間節點上正在執行任務活動的資源占用、功耗、散熱和傳輸帶寬等約束條件,如果存在約束沖突,如M2中a24與M1中a15存在約束沖突,則將正在執行任務中優先級最小的任務(M2)推遲一個步長,同時返回到任務的開始時刻進行回溯迭代,重新判斷每個時間節點上約束情況,直至無約束沖突存在,如M″2所示。

圖3 沖突任務模型重構示意圖Fig.3 Illustration of re-construction of conflict mission model

圖4 時間回溯迭代沖突化解策略示意圖Fig.4 Illustration of time backtrack iteration strategy

2.3 時間冗余啟發式規則

為了盡量減小突發任務對原任務執行計劃的影響,應盡可能地將2.1節中得到的重規劃任務安排在任務允許發生時間范圍內占用資源冗余量最大的時間段內。即遍歷任務占用資源,在時間線上找出每種資源冗余量最大時間段,取幾個時間段中最短的時間范圍,將重規劃任務首先安排在該時間段的起始時刻,并用時間回溯迭代沖突化解策略對所有任務進行約束沖突化解,以得到新的滿足約束條件的在軌任務執行詳單。其具體規劃流程如圖5所示。圖中:nrp為2.1節中重規劃任務集合中任務總數;nrw為正在執行的重規劃任務;tx為時間節點;Δt為時間步長;T為規劃結束時間。

步驟1 將2.1節中得到的重規劃任務集合中任務按優先級由大到小排列,并首先安排優先級最大的任務。

步驟2 根據重規劃任務中最大優先級任務占用的資源,在時間線上找到任務允許發生時間范圍內每種資源被占用時間段,從而找出每種資源占用最大冗余時間段。

步驟3 根據每種資源占用最大冗余時間段找出幾個時間段中最短的時間范圍,將重規劃任務安排在時間線上該時間段的起始時刻。

步驟4 從重規劃任務開始時刻開始,對時間線上每個時間迭代步長節點的約束沖突情況進行判斷。

步驟5 若存在約束沖突,則搜索存在約束沖突的正在執行任務,并將其中優先級最小任務的開始時間推遲一個時間步長。

步驟6 若任務執行時間超出允許發生時間范圍,則取消任務執行,放入不可執行任務集合,繼續執行步驟8。否則,執行步驟7。

步驟7 迭代時間返回到該任務的開始時刻,并重新對時間線上每個時間迭代步長節點的約束沖突情況進行判斷,直到規劃結束時間。

步驟8 依據任務優先級依次對重規劃任務集合中任務進行安排,直到所有重規劃任務安排結束。

步驟9 輸出更新后的在軌任務執行詳單。

圖5 時間冗余啟發式算法流程圖Fig.5 Flow chart of interval time heuristic algorithm

3 算例分析

為驗證本文方法的有效性和優越性,同時用本文提出的面向突發任務的空間站任務重規劃方法、文獻[10]中應用的時間迭代啟發式方法和文獻[9]中應用的改進遺傳算法對同一個算例進行測試。測試環境為Windows 7 32位操作系統,Intel(R)Core(TM)i7-4790 CPU3.60 GHz,內存為4 G,編程環境為Visual C++6.0。

3.1 算例配置

為方便分析,將任務周期壓縮,選取24 h內執行日常維護、載荷試驗等15項完整任務進行分析,其中包含單次執行活動25項,占用儀器、設備、物資等資源10種,涉及功耗、散熱、活動順序等約束條件8種。設置突發任務1項,突發時刻為10:00,空間站額定功耗為5 000 W,額定散熱能力為4 500 W,時間迭代步長為0.05 h。

3.2 規劃結果

為了更直觀地展現空間站任務間關系、活動間執行順序以及資源約束等關系,給出3種任務規劃方法規劃后的在軌任務執行詳單信息,如圖6所示。圖中:R1～R10代表10種不同資源;M1～M14和M01代表15個規劃任務(M01代表突發任務);a1～a23、a91和a92代表任務包含的25項活動;灰色框單元代表原任務執行詳單;黑色框單元代表更新后任務執行詳單;紅色單元代表突發任務。

為了方便對比分析3種規劃方法中不同算法策略對規劃結果的影響,將重規劃結果中各項參數信息統計如表1所示。

圖6 在軌任務執行詳單示意圖Fig.6 Illustration of onboard mission list

表1 3種不同方法規劃結果對比Table 1 Comparison of planning results of three methods

3.3 結果分析

1)規劃結果任務詳單分析

將圖6(b)中本文方法規劃結果任務詳單與圖6(a)中原任務詳單對比可知,當在任務執行過程中有突發任務(M01)發生時,通過本文提出的突發任務預處理策略,首先對突發任務進行了安排,同時暫停執行與突發任務存在約束沖突的正在執行任務(M3～M6),并對其進行任務模型重構,有效減少了沖突任務直接取消產生的影響。進一步可以看出,應用本文提出的時間回溯迭代沖突化解策略,除M5由于任務本身性質取消執行外,其余沖突任務均通過合理地推遲部分原任務而得到重新安排,顯著提高了任務執行計劃的穩定性。

將圖6(c)中文獻[10]方法規劃結果任務詳單與圖6(a)中原任務詳單對比可知,當在任務執行過程中有突發任務(M01)發生時,由于該方法沒有對突發任務的預處理策略和對重規劃任務的回溯迭代過程,所以與突發任務存在約束沖突的4項任務(M3～M6)均取消執行,如此將使任務的完成率明顯降低。

將圖6(d)中文獻[9]方法規劃結果任務詳單與圖6(a)中原任務詳單對比可知,該方法與本文方法結果基本相同,保證了原任務執行計劃的相對穩定性。

2)3種不同方法結果對比分析

從表1中本文方法和文獻[10]方法規劃結果數據對比可以看出,雖然本文方法計算時間比文獻[10]方法計算時間長,但前者規劃結果中任務的完成率明顯高于后者,并且規劃結果中穩定性指標后者顯著高于前者。因此,本文方法比文獻[10]方法具有更好的穩定性。

從表1中本文方法和文獻[9]方法規劃結果數據對比可以看出,雖然后者的穩定性指標略優于前者,但是其計算時間明顯大于前者,計算效率較低,不能滿足任務重規劃快速響應的需求。因此,本文方法比文獻[9]方法具有更好的時效性。

4 結 論

1)提出的突發任務預處理策略,有效減少了沖突任務直接取消對空間站產生的影響。

2)提出的時間回溯迭代沖突化解策略,顯著提高了空間站任務執行計劃的穩定性。

3)提出的時間冗余啟發式規則,可以有效減少任務重規劃時間。

4)本文方法可以同時滿足空間站任務重規劃快速響應和穩定性需求,具有一定的工程實用價值。

[1] SAINT R.Lessons learned in developing an international planning software system[C]//Proceedings of the 7th International Conference on Space Operations,2002:1-10.

[2] CHIEN S A,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.

[3] KNIGHT S,RABIDEAU G,CHIEN S,et al.Space exploration through continuous planning[J].IEEE Intelligent Systems,2001,16(5):70-75.

[4] ZOESCHINGER G A,WICKLER M,KOEHLER A,et al.A planning system for payload and system planning of the Columbus module on ISS[C]//Proceedings of the 8th International Conference on Space Operations,2004:1-6.

[5] 羅亞中,林鯤鵬,唐國金.空間站運營任務規劃技術評述[J].載人航天,2012,18(2):7-13.

LUO Y Z,LIN K P,TANG G J.Review on space station mission planning technology[J].Manned Spaceflight,2012,18(2):7-13(in Chinese).

[6] 田坤黌,侯永青.國際空間站運營管理體系架構分析[J].載人航天,2011,17(1):10-15.

TIAN K H,HOU Y Q.Analysis of international space station operation architecture[J].Manned Spaceflight,2011,17(1):10-15(in Chinese).

[7] LIN K P,LUO Y Z,TANG G J.Optimization of logistics strategies for long-duration space station operation[J].Journal of Spacecraft and Rockets,2014,51(5):1709-1720.

[8] 李志海,侯永青,嚴厚民,等.空間站長期運營任務規劃建模初步研究[J].載人航天,2013,19(5):52-58.

LI Z H,HOU Y Q,YAN H M,et al.Preliminary modeling study on long-term operation mission planning of space station[J].Manned Spaceflight,2013,19(5):52-58(in Chinese).

[9] BU H J,ZHANG J,LIN K P,et al.Short-term planning of the space station operation mission based on genetic algorithm[C]//Proceedings of 64th International Astronautical Congress,2013:1-9.

[10] BU H J,ZHANG J,LUO Y Z.Space station short-term mission planning using ontology modelling and time iteration[J].Journal of Systems Engineering and Electronics,2016,27(2):407-421.

[11] VERFAILLIE G,PRALET C,LEMAITRE M.Constraint-based modeling of discrete event dynamic systems[J].Journal of Intelligent Manufacturing,2010,21(1):31-47.

[12] 習婷,李菊芳.面向動態需求的成像衛星滾動式重調度方法研究[J].中國管理科學,2015,23(專輯):269-274.

XI T,LI J F.The rolling horizon method for EOS scheduling with dynamic request[J].Chinese Journal of Management Science,2015,23(Special Issue):269-274(in Chinese).

[13] 王建江,朱曉敏,吳朝波,等.面向應急條件的多星動態調度方法[J].航空學報,2013,34(5):1151-1164.

WANG J J,ZHU X M,WU C B,et al.Multi-satellite dynamic scheduling method for emergencies[J].Acta Aeronautica et Astronautica Sinica,2013,34(5):1151-1164(in Chinese).

[14] 賀川,邱滌珊,許光,等.面向對地成像觀測任務的高空飛艇應急調度[J].航空學報,2012,33(11):2082-2092.

HE C,QIU D S,XU G,et al.Emergency scheduling of earth-observing imaging tasks on high-altitude airships[J].Acta Aeronautica et Astronautica Sinica,2012,33(11):2082-2092(in Chinese).

[15] 趙凡宇,徐瑞,崔平遠.啟發式深空探測器任務規劃方法[J].宇航學報,2015,36(5):496-503.

ZHAO F Y,XU R,CUI P Y.Heuristic mission planning approach for deep space explorer[J].Journal of Astronautics,2015,36(5):496-503(in Chinese).

[16] 傅陽光,周成平,王長青,等.考慮時間約束的無人飛行器航跡規劃[J].宇航學報,2011,32(4):749-755.

FU Y G,ZHOU C P,WANG C Q,et al.Path planning for UAV considering time constraint[J].Journal of Astronautics,2011,32(4):749-755(in Chinese).

[17] 王曉暉,李爽.深空探測器約束簡化與任務規劃方法研究[J].宇航學報,2016,37(7):768-774.

WANG X H,LI S.Research on constraint simplification and mission planning method for deep space explorer[J].Journal of Astronautics,2016,37(7):768-774(in Chinese).

Re-planning method for space station pop-up missions

MU Shuai,BU Huijiao,ZHANG Jin,LUO Yazhong*

College of Aerospace Science and Engineering,National University of Defense Technology,Changsha 410073,China

Considering pop-up missions in space station operation,a re-planning method based on heuristic algorithm is proposed to satisfy the requirement for fast responses of mission re-planning.According to the continuity characteristic and conflict condition in mission execution,a model for space station pop-up mission planning domain is constructed.Considering the propagation effects of complicated constraints between the activities of missions,the time backtrack iteration strategy is adopted to solve the conflicts,and then an interval time heuristic algorithm is proposed according to the interval time between missions'execution.A fast response to the pop-up mission is achieved using the time backtrack iteration strategy and the interval time heuristic algorithm to re-plan the missions.The results show that the proposed mission re-planning method can successfully satisfy the requirement for pop-up mission planning and real-time updating of the onboard mission list.

space station;mission planning;heuristic;pop-up mission;fast response

2016-09-19;Revised:2016-10-18;Accepted:2016-12-07;Published online:2016-12-19 16:13

URL:www.cnki.net/kcms/detail/11.1929.V.20161219.1613.002.html

s:National Natural Science Foundation of China(11402295);National Basic Research Program of China(2013CB733100);Natural Science Foundation of Hunan Province of China(2015JJ3020)

V423.7

A

1000-6893(2017)07-320793-08

10.7527/S1000-6893.2016.320793

2016-09-19;退修日期:2016-10-18;錄用日期:2016-12-07;網絡出版時間:2016-12-19 16:13

www.cnki.net/kcms/detail/11.1929.V.20161219.1613.002.html

國家自然科學基金 (11402295);國家“973”計劃 (2013CB733100);湖南省自然科學基金 (2015JJ3020)

*通訊作者.E-mail:luoyz@nudt.edu.cn

牟帥,卜慧蛟,張進,等.面向突發任務的空間站任務重規劃方法[J].航空學報,2017,38(7):320793.MU S,BU H J,ZHANG J,et al.Re-planning method for space station pop-up missions[J].Acta Aeronautica et Astronautica Sinica,2017,38(7):320793.

(責任編輯:張玉)

*Corresponding author.E-mail:luoyz@nudt.edu.cn