航天器任務調度模型、算法與通用求解技術綜述

杜永浩 邢立寧 姚 鋒 陳盈果

21 世紀以來,我國航天事業步入快速發展時期.隨著“高分辨率對地觀測系統”、“北斗衛星導航定位系統”等國家重大專項的相繼開展,以及商業航天產業的蓬勃發展,我國在軌航天器規模持續增加,總數位居世界第二.在此期間,各類航天器平臺與載荷能力也經歷了深刻變革.為適應大規模、復雜化的航天器管控新常態,融合現代運籌學、計算科學與相關領域知識的航天器任務調度技術起到了舉足輕重的作用.

航天器任務調度技術是指在航天器使命任務與管控需求的驅動下,通過對任務與資源的建模,消解航天器任務執行過程中的約束沖突,最大化航天器任務與管控效益的一種優化技術.在諸多學者與航天從業人員的推動下,航天器任務調度技術得到了快速的發展,在美國DigitalGlobe 高分辨率對地觀測系統、歐盟Galileo 衛星導航系統和我國“高分”系列對地觀測系統、“北斗”衛星導航系統等國內外先進的航天系統中得到了充分的實踐與驗證.在此過程中,作為調度技術的兩大要素,航天器任務調度模型與調度算法的重要性也日益凸顯.

調度模型是航天器任務調度的重要基礎,是決定問題描述方式、指導算法設計、影響問題復雜度的關鍵因素.現階段,線性規劃模型、圖論模型、約束滿足模型等各類調度模型已被廣泛運用于航天器任務調度問題研究中.在這些研究中,一方面,許多調度模型表現出鮮明的問題特色與針對性,引入了與調度問題緊密相關的決策手段;另一方面,許多模型也表現出了較大的相似性,折射出航天器任務調度問題的一些共性特征.因此,面對模型種類和應用場景繁多的航天器任務調度技術發展現狀,建立一個怎樣的調度模型,是決定調度問題是否可解、問題特征是否可描述、應用場景是否可拓展的重要環節.

調度算法是航天器任務調度的優化手段,是實現模型解算、輸出調度方案、決定問題求解質量的關鍵因素.在航天器規模增長與能力發展的趨勢下,啟發式算法、精確求解算法和元啟發式算法等一系列形式各異的調度算法被應用于航天器任務調度問題的求解中.這些調度算法表現出良好的優化效果,但往往也暴露出與調度模型或應用場景緊耦合的編碼方式或設計思想,導致許多優秀的航天器任務調度算法在提出之后并沒有得到廣泛的應用或進一步的發展.由此,在琳瑯滿目的調度算法中挑選出合適的算法、設計合理的編碼結構、吸納優秀算法中的先進思想,也是航天器任務調度技術研究發展的必然要求.

為梳理航天器任務調度相關模型與算法、分析其特點與發展趨勢,一些綜述工作相繼開展[1-4].不過,這些文獻大多聚焦于某一類航天器(如遙感衛星)或某一種應用場景(如自主協同)的航天器任務調度模型或算法,很少站在航天領域的全局視角,探討不同類型航天器任務調度模型的共性特征與區別,分析不同調度算法的適用性與編碼特點.未來,航天器任務調度模型必須滿足復雜化、組網化的問題特點,調度算法也需滿足大規模、快速響應的優化需求,這就要求相關從業人員對各類航天器任務調度模型與算法深刻理解與熟練運用,擺脫“問題-模型-算法”緊耦合的傳統思維.鑒于此,本文試圖系統地梳理航天器任務調度研究中的模型與算法,揭示調度模型的共性特征,歸納調度算法的使用特點,為航天器任務調度技術研究未來發展提供參考.同時,在二者基礎上發展起來的通用求解技術是改善航天調度系統兼容性、提升綜合管控水平的關鍵技術,故本文也試圖梳理適用于航天器任務調度的通用求解工具,探索我國航天器任務調度通用求解技術發展的新道路.

本文分別對航天器任務調度模型、算法和通用求解技術等三個方面進行了梳理與總結.第1 節根據航天器類型的不同,將現階段具有調度需求的主要航天器任務分為遙感衛星任務、中繼通信衛星任務、導航衛星任務和航天器測控任務,分別闡述了各類航天器任務調度的常用模型及特征.第2 節根據優化原理的不同,將航天器任務調度算法分為啟發式算法、精確求解算法和元啟發式算法,重點討論了各類算法的編碼特點和優缺點.第3 節分別介紹了CPLEX、STK/Scheduler、Europa2 和“高景一號”任務調度分系統等具有通用特色的航天器任務調度工具,并分析了其適用性與應用前景.最后,第4 節綜合研究現狀,對航天器任務調度領域未來的研究趨勢進行了展望.

1 航天器任務調度模型

在任務調度問題的求解過程中,問題建模往往是首要步驟.在航天器任務調度相關研究中,各類航天器任務往往由不同的職能部門負責調度,并采用不同的問題建模方式,影響著任務與資源處理、決策變量設計和模型編碼等諸多方面.根據職能部門的不同,可以將航天器任務分為運控任務與測控任務兩大類:

定義1 (航天器運控任務).為實現遙感衛星、中繼通信衛星和導航衛星等航天器的使命任務和任務數據的回傳,在航天器特定工作模式和載荷的支撐下,由所屬運控部門針對任務目標或數據接收目標制定的一類專門任務.

定義2 (航天器測控任務).為保障航天器正常運行,滿足航天器遙測、跟蹤和指令上注等日常需要,在航天器載荷和地面管控資源的共同支撐下,由測控部門針對航天器統一制定的一類任務.

由此,在上述定義的基礎上,本節梳理了遙感衛星、中繼通信衛星、導航衛星和航天器測控等常見的航天器任務調度模型,分析了不同航天器任務調度問題的建模特色、決策變量形式和模型優缺點,揭示不同航天器任務調度模型之間的共性特征與區別,闡明建模過程中提升模型兼容性、適用性和求解效率等方面的必要性,為航天器任務調度的模型研究提供參考.

1.1 遙感衛星任務調度模型

遙感衛星任務是指針對地表、海洋、大氣和太空等環境中的目標,通過星上遙感載荷進行信息數據收集并傳輸給地面設備的一類航天器運控任務.遙感衛星是目前在軌數量最多的航天器,在農業、經濟、軍事等領域發揮著不可替代作用.因此,遙感衛星任務也是現階段種類最為繁多、需求量最大、應用最為廣泛的一類航天器運控任務.

遙感衛星任務調度是一類具有NP-Hard (Nondeterministic polynomial-time hard)特性的組合優化問題[5],該問題往往具有序列優化與資源優化的雙重特點,既要決策任務執行的先后順序,又要為任務合理地分配衛星及其載荷資源.由此,根據調度模型中決策對象的不同,本節將遙感衛星任務調度模型分為面向資源的任務排序模型(簡稱任務排序模型)和面向任務的資源分配模型(簡稱資源分配模型)兩大類,并基于此對遙感衛星任務調度模型展開進一步的闡述.

1.1.1 任務排序模型

20 世紀末,面對遙感衛星任務調度這一全新的問題,人們嘗試從經典運籌學模型中尋找解決方案.在這些模型中,決策變量主要表示資源執行任務的先后順序,反映任務連續執行過程中的時序邏輯和能力約束,對早期遙感衛星任務調度問題的求解起到重要幫助.

1)車輛路徑規劃模型

車輛路徑規劃(Vehicle routing problem,VRP)模型是最早用于遙感衛星任務調度問題求解的模型之一,其中衛星被視為車輛,任務目標被視為車輛訪問的城市,如圖1(a)所示.Cordeau 等[6]將遙感衛星對目標的可見性轉化為任務的時間窗口約束,并采用了一種VRP 求解算法[7]解決了單軌遙感衛星任務調度問題.隨后,Bianchessi 等[8]將該算法應用于多星多軌的任務調度場景中.李菊芳等[9]、郭玉華等[10]和蔡德榮[11]指出衛星成像任務與數傳任務可視為VRP 模型中的裝卸貨動作,求解了固存容量約束下的任務調度問題.雖然上述研究在衛星任務、工作模式、固存約束等方面進行了諸多簡化,但VRP 模型中任務排序的建模思想為衛星任務調度研究打開了新思路.

2)圖論模型

圖1(b)所示的圖論模型通過點和線的方式直觀地描述衛星任務之間的時序與沖突關系,在遙感衛星任務調度中也得到諸多應用.例如,Gabrel 等[12]、Bianchessi 等[13]和陳浩等[14]將成像任務調度問題抽象為有向無圈圖模型,陳祥國等[15]通過構造任務調度位置圖和任務調度關系圖分別描述了數傳任務的序列與執行資源.針對多星聯合調度問題,Xu 等[16]建立了基于最小生成樹的圖論模型,張帆等[17]和王鈞[18]構建了分層優化的圖論模型.不過,圖論模型的缺陷也十分明顯,由于該模型的約束表達能力有限,往往需要較大程度的問題簡化,諸如區域目標成像、成像數傳一體化調度、固存擦除等復合任務約束很難在傳統圖論模型中進行表示.

3)車間調度模型

作業車間調度(Job-shop scheduling problem,JSP)和流水車間調度(Flow-shop scheduling problem,FSP)等模型中關于工件加工順序的約束特點滿足衛星區域目標成像、立體成像等實際需求,故二者也常用于描述遙感衛星任務調度問題.早在1994 年,Hall 等[19]就給出了遙感衛星任務調度的JSP 模型.Cordeau 等[6]、李菊芳等[9]、顧中舜等[20]和賀仁杰等[21]指出,遙感衛星執行任務的過程可以看作為不同類型的機器(衛星、地面站)分配工序(成像任務、數傳任務)的過程,如圖1(c)所示.此外,Xiao 等[22]設計了一種兩階段式的任務調度框架,通過FSP 模型對衛星成像與數傳任務進行了一體化的調度.

上述任務排序模型便于檢查相鄰任務之間的轉換時間約束,貼近衛星管理的實際情況,加之早期遙感衛星幾乎均采用“順序回放”的工作模式,即數傳順序與成像順序保持一致,故諸多其他遙感衛星調度文獻中也保留著該建模思想.例如,Lema?tre等[23]研究法國敏捷星座Pleiades 時通過決策變量表示衛星任務的先后順序,并指出衛星電量與固存約束也可通過調整衛星任務順序得以滿足;Xu 等[24]通過決策變量表示了任務在執行序列中的位置;Lin 等[25]、程思微等[26]、任仙海等[27]、Sun 等[28]和Cui等[29]均通過決策變量表示了遙感衛星任務目標之間的路徑或順序等.

不過,任務排序模型存在一個明顯的解碼過程,通常仿照傳統VRP、圖論和JSP 模型盡可能早地執行任務,如圖1(c)所示.但實際上,該解碼過程在現階段衛星復雜的約束邏輯下(如時間依賴性約束、非線性收益等)可能會丟失優質解,即“最優序列”不一定等于“最優結果”.問題約束越復雜,任務排序模型就越可能丟失優質解,同時解碼過程的時間成本也越高.另一方面,隨著星載固存技術的發展,諸多近年來發射的遙感衛星(如“高景一號”)已無需滿足“順序回放”的約束,即成像序列與數傳序列可以不一致.若在數傳窗口稀缺或某些任務有特殊需求的情況下,分別優化衛星成像序列與數傳序列很可能更利于任務收益的最大化.對此,學者們提出了面向任務的資源分配模型,既保留了任務排序建模的思想,同時直接決策了任務執行的具體時間,成為各類遙感衛星任務調度研究中的重要模型.

圖1 遙感衛星任務排序模型示例Fig.1 Illustrations of mission-sequencing models for remote sensing satellites

1.1.2 資源分配模型

與任務排序模型相比,資源分配模型不再決策任務順序,而是面向任務需求,決策任務被執行的資源,如圖2(a)所示.由于衛星與任務目標的可見性是任務執行的前提,二者的可見時間窗口(Visible time window,VTW)一直以來都被視為衛星調度的關鍵資源,故資源分配模型又可稱為VTW分配模型.例如,Bensana 等[30]、Gabrel[31]、靳肖閃等[32]、Wang 等[33]、Liu 等[34]、Jiang 等[35]和Wu 等[36]以0-1決策變量表示了遙感衛星執行任務所選的VTW,求解了法國SPOT、韓國SATellite-2、我國“環境”系列和中巴“資源”系列等遙感衛星成像任務調度問題.在上述文獻中,由于0-1 變量所表示的VTW同時包含了衛星載荷信息和任務執行時間,反映了衛星執行任務的順序,無需VRP、JSP 模型中的解碼過程,使得模型表示更加簡潔.

圖2 遙感衛星VTW 分配模型示例Fig.2 Illustrations of VTW-allocation models for remote sensing satellites

然而,敏捷遙感衛星技術的發展也暴露出了傳統VTW 分配模型的局限性.近年來發射的遙感衛星通常具備俯仰成像能力,即能夠先于或晚于目標上空進行遠距離的傾斜成像,這一技術為遙感衛星在目標上空過境時帶來了更長的VTW 和更多的成像機會[37],如圖2(b)所示.因此,在敏捷遙感衛星任務調度模型中,不僅需要決策任務執行的VTW,還需要決定任務在該VTW 內具體的開始時刻.針對這一問題,學者們通過以下三種方法對模型進行了改進:

1)基于規則的VTW 分配模型

與上一節任務排序模型中的解碼思想相似,Lema?tre等[23]、He 等[38-39]、Mok 等[40]、Chu 等[41]和Song 等[42]基于最早開始原則,將衛星任務安排在VTW 內滿足約束的最早位置;張超等[43]、Liu 等[44]以成像質量優先原則安排任務,并在模型中處理了時間依賴的姿態轉換與梯段成像質量約束;Xu 等[24]根據任務安排過程中可能出現的不同情況設計了專門的衛星窗口更新策略;Kim 等[45]在SAR 星座成像調度問題中僅考慮了側視成像模式,即在VTW的中點安排成像任務;Wu 等[46]以合并任務優先、最早開始等原則安排成像任務,并指出任務合并的相關約束導致了其模型非線性的特征.不過,雖然這些解碼過程能夠幫助VTW 分配模型適用于敏捷遙感衛星調度問題,但基于規則的解碼方式一定程度也限制了算法對更大解空間的探索,在復雜約束情況下的時間成本可能也較高.

2)多重決策的VTW 分配模型

Lema?tre 等[23]、She 等[47]、Chen 等[48]和Frank等[49]在用0-1 變量表示任務VTW 的同時,還通過一個整數變量表示了任務在VTW 內的開始時刻.Sarkheyli 等[50]通過雙重決策變量表示了敏捷遙感衛星任務的VTW 和開始時刻,并考慮了星上固存整塊擦除的業務約束,該約束在其他研究中很少涉及;Niu 等[51]、Chen 等[52]也采用了相同的決策變量,并計算了非線性的姿態轉換時間約束.在該模型中,0-1 變量決策了執行任務的衛星以及VTW,整數變量決策了該任務的開始時間,避免了上一種方法中基于規則的解碼過程,具有更好的模型完備性.

3)離散化VTW 分配模型

Wang 等[33]、Valicka 等[53]、Nag 等[54]、Zhu 等[55]、He 等[56]、Li 等[57]和杜永浩等[58]將遙感衛星成像或數傳任務的VTW 進行離散化處理,通過0-1 變量直接決策了任務的離散VTW (即開始與結束時間),如圖3 所示.該方法與多重決策的VTW 分配模型在本質上是相同的,但減少了決策變量的數量,使得模型更加簡潔.與基于規則的VTW 分配模型相比,后兩種模型在解的表示過程中擺脫了啟發式規則的影響,能夠保障復雜約束條件下解的多樣性,更加貼近敏捷遙感衛星管控的實際情況.不過,這兩種模型很大程度上擴大了問題的解空間,可能產生較多的不可行解,求解難度隨之增加,故需要高性能優化算法的支持.同時,VTW 離散化的程度是可控的(現階段衛星任務的最小精度通常為秒級),故合理的VTW 離散粒度也有助于提升該模型的有效性.

圖3 敏捷遙感衛星任務離散VTW 分配模型示例Fig.3 An illustration of the discrete VTW-allocation model for agile remote sensing satellites

此外,還有學者將遙感衛星任務調度問題抽象為背包問題[6,59-61],但通常忽略了衛星執行任務的先后順序,對問題簡化程度較高,且近年來沒有較大發展.許多學者基于Multi-Agent 模型[62-66]與機器學習模型[67-70]等研究了面向自主衛星的分布式協同任務調度問題,但此類問題通常突出星上自主性和快響性特點,不屬于現階段用戶需求驅動與地面統一管控體制下的衛星日常任務調度范疇,故本節不討論這些模型.

1.2 中繼通信衛星任務調度模型

隨著遙感衛星數量和對地觀測數據量的不斷提升,地面數傳站難以滿足現階段遙感星群大規模、高頻率的數據傳輸需求.因此,為在軌衛星與地面站提供數據中轉服務的中繼通信衛星起到了十分重要的作用.由于在軌道上承擔的使命任務與地面數傳站相近,中繼通信衛星也被稱為“天基數傳站”.

中繼通信衛星的任務調度問題與遙感衛星任務調度問題中的數傳調度部分在諸多方面具有很大的相似度:1)二者均是在VTW 的基礎上對目標執行數傳任務,如圖4 所示;2)二者在工作模式、電量、固存等方面具有相似的約束;3)中繼通信鏈路的單址鏈路和多址鏈路支持不同的鏈路數與頻段,這與遙感衛星不同的成像載荷具有相似的特點.因此,中繼通信衛星任務調度模型也可參考遙感衛星任務調度模型進行分類.

圖4 中繼通信衛星任務調度問題與遙感衛星任務調度問題的類比Fig.4 A comparison between the mission scheduling of relay satellites and remote sensing satellites

1)任務排序模型方面

早在1986 年,Reddy 等[71-72]就用點和弧分別描述中繼通信衛星任務之間的優先關系;Rojanasoonthon 等[73-74]、莊樹峰等[75-76]、賀川等[77]和劉潤滋等[78]指出中繼衛星任務調度問題可視為一類VRP 問題或并行機器調度問題,并通過決策變量反映了衛星執行任務的先后順序;郭超等[79]結合任務緊急程度、執行難度和VTW 屬性分別定義了任務的綜合優先級,并基于優先級順序依次為任務分配VTW和開始時間.可見,此類模型延續了遙感衛星任務排序模型的建模特點,在決策變量表示和解碼原則等方面具有一致性.

2)VTW 分配模型方面

在中繼通信衛星執行任務的過程中,往往也會出現VTW 長度超過任務時長的情況,即相關研究中提到的“滑動窗口”.在這些研究中,通常采用啟發式規則確定任務在VTW 內的開始時間.例如,顧中舜[80]、趙靜等[81-82]、Zhao 等[83]通過0-1 變量表示了中繼通信任務執行的VTW,并基于優先級順序和最早開始原則依次計算任務的開始時間;方炎申等[84-86]在啟發式規則的基礎上引入了專家系統規則;賀川等[87]以任務最小損失機會確定開始時間;何敏藩等[88]設計了最早、最晚和隨機開始策略等.

在其他一些文獻中,中繼通信衛星的任務調度問題并不單獨考慮,例如,在遙感衛星成像與數傳一體化任務調度的研究中,Li 等[57]將中繼衛星視為一個地面數傳站,該處理方式也是現階段遙感衛星調度系統中的常用方法.此外,中繼衛星有時也承擔部分航天器的測控任務,故有相當一部分的中繼通信衛星任務被納入航天器測控任務范疇中[89].可見,中繼通信衛星常被視為一種保障其他航天器任務調度需求的通用資源.因此,考慮到中繼通信衛星的使命任務與管控特點,以及其在調度模型上與其他衛星調度問題的相似性,相關研究應側重與其他類型衛星任務調度問題的集成性與協同性.

1.3 導航衛星任務調度模型

目前,世界上主要的導航系統包括美國全球定位系統(Global positioning system,GPS)、歐洲“伽利略 (Galileo)”導航系統、俄羅斯全球定位系統(Global navigation satellite system,GLONASS)和我國“北斗”導航系統.導航衛星的運控任務主要是建立衛星與地面或與其他衛星之間通信鏈路,以保障導航系統的定位精度和授時精度,以及導航電文、星歷信息等數據的實時互傳.因此,導航衛星任務調度問題可以看作為星地建鏈任務與星間建鏈任務的調度問題.

1)GPS 與GLONASS 導航系統

GPS 是全球最早建成的導航定位系統,并在2005 年就完成了全球范圍的地面站部署,可在任何時刻實現星地建鏈,通常無需考慮VTW 約束[90].GLONASS 也在俄羅斯本土與周邊國家大量部署地面站[91],衛星的可見性也較高.由此,GPS 與GLONASS 系統中的星地通信鏈路充裕,對任務與資源調度的需求程度較低,相關的公開文獻較少.

2)Galileo 導航系統

早在1994 年,Gershman 等[92]和Marr[93]就討論了Galileo 導航系統的任務調度問題.Toribio 等[94]介紹了Galileo 導航系統任務調度過程中的主要設備信息和組織架構,給出了短期規劃、長期規劃和應急規劃的概念.Hall 等[95]介紹了Galileo 導航系統的調度系統(Spacecraft constellation planning facility,SCPF),給出了任務調度的主要流程,指出該系統每周約調度1 500 余項任務,周計劃調度時間為10 分鐘等.不過,上述研究均沒有給出導航衛星任務調度的具體模型或算法.Marinelli 等[96]基于離散VTW 的0-1 變量表示了導航任務的開始與結束時間,對30 顆Galileo 導航衛星的星地建鏈周計劃進行了調度.

3)“北斗”導航系統

針對“北斗”導航系統星地建鏈任務調度問題,龍運軍等[97]基于0-1 變量表示了執行任務的地面站及VTW,并通過另外兩個整數變量分別表示了任務的開始與結束時間,處理了測站建鏈數量、天線轉換時間等實際約束,對建鏈時長、任務完成度等目標進行了優化.Tang 等[98]通過離散VTW 表示了導航任務的開始時間,對任務完成度和負載均衡度等目標進行了優化.考慮到任務等待時間和設備使用時間的雙重時間約束,閆俊剛等[99]將導航衛星任務調度問題抽象為帶有雙重VTW 約束的JSP 問題.張忠山等[100]在星地建鏈任務的基礎上還考慮星間建鏈任務,給出了基于任務排序模型的兩階段式任務調度方案.

盡管關于導航衛星任務調度的公開文獻較少,但該問題中的星地建鏈任務和星間建鏈任務,分別與陸基航天器測控任務和天基航天器測控任務有較大的相似度.部分研究還將導航衛星任務調度納入航天器測控任務調度的范疇[96-98].因此,下面重點介紹一些航天器測控任務調度的模型.

1.4 航天器測控任務調度模型

航天器測控任務是航天器遙測、跟蹤、指令上注等一系列任務的統稱,是保障航天器正常運行和長效管控的重要前提.航天器測控任務以地基測控任務為主,也包含部分天基(基于中繼通信衛星的)測控任務.由圖5 可見,與航天器運控任務調度相似,資源與目標的VTW 也是航天器測控任務調度的關鍵資源,其中低軌目標測控任務的VTW 長度通常等于任務時長,而高軌目標測控任務的VTW長度通常大于任務時長.因此,航天器測控任務調度問題的研究很大程度上保留了與運控任務調度相似的問題描述方式與建模習慣,主要采用優先級排序模型、圖論模型和VTW分配模型等進行相關研究.

圖5 航天器測控任務調度示例Fig.5 Illustration of spacecraft tracking mission scheduling

1)優先級排序模型

優先級排序模型屬于一種面向資源的任務排序模型,其中任務的優先級指任務分配資源的優先級.該模型與VRP 等任務排序模型相似,但不會通過決策變量指明任務資源,而是直接根據任務排序結果依次分配資源.例如,Parish 等[101]、Barbulescu等[102-104]、鄭晉軍等[105]和張鵬等[106]通過0-1 變量表示了一個待調度的任務序列,并基于最早開始原則依次為任務分配VTW 與開始時間,將航天器測控任務調度問題轉換為任務集的最優排序問題.Barbulescu 等[107]還指出航天器測控任務調度問題可由一類帶準備時間的單機調度問題歸約得到,證明了該問題的NP-Complete 性.Li 等[108]將每一個測控VTW 都視為待執行的任務,并通過0-1 變量表示了待調度的任務序列.該模型編碼形式簡單,受到了諸多青睞,但也因其只決策任務資源分配的順序,且完全依靠啟發式規則為任務逐一分配資源與時間,該模型在復雜的航天器測控任務調度問題中可能表現不佳.

2)面向低軌航天器的圖論模型

作為另一種任務排序模型,圖論模型在航天器測控任務調度研究中也應用廣泛.早在1985 年,Arbabi 等[109]就給出了航天器測控任務的圖論模型.Zufferey 等[110]和Bl?chliger 等[111]將航天器測控任務視為圖,將測控資源描述為不同顏色,將任務調度問題轉化為圖著色問題,而其中任務開始時間也依賴于最早開始原則;張雁等[112]、徐小輝[113]、Zhang等[114-117]和陳祥國等[118-119]以節點表示航天器VTW,通過邊表示了任務在不同VTW 之間的沖突關系,處理了任務執行唯一性和無重疊等約束,將航天器測控任務調度問題轉化為最大獨立集問題;王海波等[120]、Vázquez 等[121]在航天器與測站可見關系圖的基礎上,以節點表示測控任務的開始時間,以邊表示同一個測站連續執行測控任務的轉換過程;Vázquez 等[122-123]還給出了分布式、魯棒性和實時調度的模型.此外,Petri 網模型也被用于航天器測控任務調度研究中[124-127].不過,上述研究中通常僅考慮低軌航天器,由于低軌航天器測控任務時長等于其VTW 長度,故任務間的資源沖突、天線仰角和轉換時間約束等相對確定、易于描述.但在高軌航天器測控任務中,VTW 長度通常超過任務所需的測控時間,故針對包含高軌航天器的測控任務調度問題,還需更加合適的模型加以描述.

3)考慮高軌航天器的VTW 分配模型

針對高、低軌航天器聯合測控任務調度問題,Gooley 等[128-129]建立了兩階段式的VTW 分配模型,基于0-1 變量表示了測控任務的VTW,并優先調度低軌航天器的測控任務,再通過一個整數變量表示高軌測控任務在VTW 內的開始時間;賀仁杰等[130]、劉洋等[131]和Luo 等[132]也采用同樣的決策變量描述了高、低軌航天器聯合測控調度問題,建立了一體化的測控任務調度模型;Xhafa 等[133-136]、Valicka 等[137]通過整數變量直接表示了航天器測控任務的開始時間;Marinelli 等[96]基于離散VTW和0-1 變量建立了Galileo 導航星座測控任務調度模型.針對大規模測控任務調度場景,Liu 等[138]基于0-1 變量表示了測控任務的VTW,并基于沖突消解規則決定任務在VTW 內的開始時間.上述VTW 分配模型不僅決策了測控任務的VTW 與資源,同時也確定了任務在長VTW 內的具體開始時間,適合于包含高軌航天器的測控任務調度場景.

此外,還有0-1 背包模型[139]、基于本體與規則庫的模型[140-142]、博弈論模型[143-144]、Multi-Agent 模型[145-146]和機器學習模型[147-148]等也被應用于航天器測控任務調度的研究中.

在上述研究中,航天器測控任務調度算例通常分為兩種:1)基于STK 的仿真算例,任務數通常小于100,測站數小于10;2)美國空軍(Air Force Satellite Control Network,AFSCN)發布的7 個高、低軌航天器聯合測控任務調度標準測試集(Benchmark)[149](最近更新于2003 年),其中平均每天測控任務規模為308,測站數為19.考慮到任務和資源規模上的差異,這兩類算例的求解難度也截然不同.而實際上,我國航天測控部門現階段面臨的任務規模早已超過AFSCN Benchmark 的規模.由此,當前諸多基于小規模算例的相關研究均存在一定的局限性.

1.5 小結

1.5.1 模型共性與區別

本節從任務排序模型和VTW 分配模型兩個角度梳理了遙感衛星、中繼通信衛星、導航衛星和航天器測控任務調度研究的主要模型,并對各類模型的特點、決策變量形式和優缺點進行了分析.表1將上述內容進行了總結,其中,結合衛星型號項目研發經歷,還梳理了我國航天器任務調度實際需求中極少被相關文獻考慮的業務約束.這些約束很大程度上限制了航天器任務調度最新研究成果的轉化和應用.因此,如何通過標準化、模塊化和簡潔化的方式將這些復雜的業務約束納入航天器任務調度模型中,應成為未來研究的重要內容之一.

從表1 中不難發現,遙感衛星、中繼通信衛星、導航衛星和航天器測控任務調度研究中的常用模型具有非常大的相似性,其本質上是因為上述航天器任務調度問題的相似性.盡管航天器會搭載不同的載荷、被賦予不同的任務,但任務與資源在時、空、頻域的可見性始終是問題建模的出發點和落腳點.以遙感衛星為例,調度模型中主要參數的實例化關系可由圖6 表示,其中資源類包含了載荷、平臺等實際資源和VTW 等抽象資源,任務類包含了屬性和決策變量等.基于任務與資源的可見性,任務類中的開始時間可與VTW 直接關聯,形成貫通模型的信息流,還原航天器任務調度問題的本來特點.由此,圍繞“任務-資源”可見性這一共性特征,上述航天器任務調度問題具有統一化描述與建模的可行性[58].

圖6 航天器任務調度模型主要參數關系的一種類圖表示(以遙感衛星為例)Fig.6 A class diagram of the relationships among the parameters in spacecraft mission scheduling(exampled by remote sensing satellites)

表1 航天器任務調度模型研究現狀總結Table 1 A summary of the studied models for spacecraft mission scheduling

不過,由于任務使命與資源的差異,上述航天器任務調度問題也存在著諸多不同,包括:1)固存約束差異,遙感衛星、中繼通信衛星通常需要重點考慮固存約束,而導航衛星任務中的數據量較小、航天器測控任務中的數據傳輸通常使用備用固存或無需數傳,故一般不考慮固存約束;2)陽照約束差異,可見光、高光譜和近紅外等光學遙感衛星任務通常對任務的陽照性有要求,而導航衛星、測控任務通常對陽照性沒有要求;3)資源能力約束差異,在遙感衛星任務中,出于對衛星的保護,通常設置一些復雜的業務約束,限制了衛星資源執行任務的能力;而導航衛星、航天器測控等任務主要依靠地面資源,故資源能力約束通常較少.4)任務時長差異,遙感衛星、中繼通信衛星和航天器測控任務時長通常為定值,而導航衛星的任務時長常為變量.上述約束差異是反映航天器任務調度問題特征、區別航天器任務調度類型的主要因素.

1.5.2 不足與對策

綜上,在分析各類航天器任務調度模型共性特征與區別的基礎上,本節總結了現有研究存在的三個方面的不足并給出對策:

1)不同類型的航天器任務調度問題模型相似卻又不兼容,缺乏統一的建模理論與建模語言.

通過本節的分析發現,各類航天器任務調度模型具有很大的相似性,其圍繞任務與資源在時、空、頻域可見性的建模原則是統一的.然而,這些模型又因應用場景的約束特點、需求種類和求解習慣等存在一定差異.因此,設計通用化、統一化的航天器任務調度建模方法與建模語言,是研究航天器通用建模與求解技術,滿足未來不同類型、不同約束和不同體制下航天器綜合管控需求的重要途徑.

2)諸多航天器任務調度問題簡化程度高,缺乏部署航天業務管控系統的實際應用價值.

表1 列舉了諸多相關研究中極少考慮的實際約束.雖然一定程度的問題簡化能夠縮減問題規模、提升求解效率,但有些簡化(如不考慮固存擦除)已影響問題的建模方式和調度方案的可用性,導致研究成果無法轉化并應用于實際航天管控系統中.因此,梳理各類航天器任務調度問題中關鍵約束、通用約束以及特色約束,盡可能在調度模型中還原各類航天器業務管理的真實需求,是保障相關技術實用性價值的重要前提.

3)在模型層面降低航天器任務調度問題規模、提升問題求解效率的有效機制沒有得到重視.

一直以來,調度算法是航天器任務調度問題中主要研究的對象,而調度模型受到的重視程度遠遠不足.實際上,調度模型很大程度上決定了調度算法的編碼形式、鄰域結構、搜索空間等影響優化效率的關鍵因素.因此,在未來航天器任務調度問題研究中,設計科學的調度模型和建模策略,是縮減問題規模、降低算法編碼復雜度、提升算法求解效率、促進模型與算法解耦的必然要求.

2 航天器任務調度算法

在航天器任務調度模型的基礎上,任務調度算法起到模型解算、收益優化和方案輸出的作用,是實例化問題模型、決定模型求解質量的關鍵環節.啟發式算法、精確求解算法和元啟發式算法是三類常用的調度算法,在航天器任務調度領域得到了諸多應用.實踐表明,這三類算法通常具有獨特的性能優勢,例如,啟發式算法可以快速構造高質量的初始解,精確求解算法能夠給出特定場景下的最優解,元啟發式算法具有良好的復雜解空間尋優能力以及與前兩種算法的兼容性等.同時,上述算法也往往與航天器任務調度的模型緊密相關,存在適用性、可拓展性不足等現實問題,亟待更多的發展和實踐的檢驗.

因此,本節從啟發式算法、精確求解算法和元啟發式算法等三個方面總結航天器任務調度研究中的常用算法,探討不同算法的編碼形式、鄰域結構、輔助策略和優缺點,闡明上述調度算法的適用模型,指出算法與模型解耦、算法深度融合等方面的必要性,為航天器任務調度的算法研究提供參考.

2.1 啟發式算法

1)優先級排序算法

優先級排序算法是在優先級排序模型的基礎上,基于優先級順序和其他規則為任務序列分配資源與時間的算法.該算法具有通俗易懂、結構簡單、運算速度快等優點,符合人的主觀經驗,是航天器任務調度研究與實際調度系統中的常用算法.

這些優先級排序算法中的排序規則通常是以任務優先級順序[81-82,105-106]為主,也包含一些與VTW時間、長度、數量等屬性有關的組合優先級順序[79-80];常用的資源分配規則包括最早開始原則[23,39-40,46,110-111]、最晚開始原則[88]、最大成像質量原則[43-44,150]和最小可能沖突原則等[138].由于此類算法往往與排序模型緊耦合,相關內容已于上文介紹,且算法原理相對簡單,故不再討論.

2)沖突消解算法

沖突消解(Conflict-avoidance 或De-conflicting)算法是指通過分析任務之間、任務與資源之間的可能沖突,在任務調度的過程中降低沖突程度、提供沖突解決方案的一類方法.

在遙感衛星任務調度應用方面,劉曉娣等[151]在任務排序模型的基礎上分別設計了基于成像概率和非互斥鏈的沖突消解算法;冉承新等[152]在調度的過程中引入了沖突判斷與沖突度評估策略,作為遺傳算法交叉與變異操作的先驗知識;劉彬彬等[153]通過對衛星成像任務持續時間進行壓縮,實現了部分約束的沖突消解;Chen 等[52]以最小化沖突的方式完成了初始任務序列的構造,并在迭代優化的過程中也引入了該沖突消解機制.

在航天器測控任務調度應用方面,金光等[154]基于最小沖突原則設計了任務資源的分配算法;楊萍等[155]計算了航天器測控任務的可能沖突集并設計了基于沖突的回調算法,實現了在資源分配過程中的“回溯”機制;Tsatsoulis 等[156]給出了基于案例、規則和迭代的多種沖突消解機制;Luo 等[132]計算了航天器測控任務的不可消解沖突集,進而設計了航天器測控任務預調度算法和重調度算法,取得了目前AFSCN Benchmark 中的最佳結果.

此外,圖論模型中邊的構造通常也蘊含著沖突識別與消解的思維.可見,沖突消解算法在諸多航天器任務調度研究中表現出快速、有效的優化特點,但很少直接作為任務調度問題的求解算法,大部分情況下用于生成調度初始解或輔助其他優化算法.此外,沖突消解算法大多圍繞任務與VTW 的約束關系,不同算法之間的沖突消解原理、方法較為相似,且與問題約束緊耦合,在算法理論方面難有突破.

3)任務分配算法

任務分配算法是針對航天器任務調度規模較大、優化效率偏低的問題,依據某種經驗或規則對航天器任務進行預分配的算法.與沖突消解算法一樣,任務分配算法通常也作為調度過程中的輔助算法.任務分配算法有助于緩解航天器任務調度問題中的“組合爆炸”現象,對縮減任務調度解空間、提升優化效率有著重要作用.

以遙感衛星任務調度應用場景為例,Lema?tre等[157]設計了遙感衛星任務公平分配原則,基于任務權重、衛星能力等將任務均勻地分配給不同的衛星;Xu 等[24]、Wang 等[33]計算了任務之間VTW 重疊度,并將任務分配給VTW 重疊度最低的衛星;Du等[158]通過VTW 重疊度、任務優先級等多種任務特征評估、預測了任務被衛星執行的可能性,并將任務分配給執行可能性最高的衛星;周軍升[159]在任務分配過程中引入了合同網的“ 招標、投標、評標”機制,提升了任務分配的可靠性;邱滌珊等[160]、孫凱等[161]將任務調度問題分解為任務分配和任務合成兩個子問題;He 等[56]設計了一種包含反饋機制的任務分配與調度框架,實現了任務調度進程中對未調度任務的重新分配,在大規模敏捷衛星任務調度場景中取得出色的優化效果.

上述啟發式算法均有效降低了問題的決策維度和求解難度,但其應用效果很大程度上也取決于算法設計的合理程度,且大多與問題場景、任務與資源特征緊耦合,對問題的適應性不足.對此,充分利用航天器任務調度場景的特征和經驗,設計通用化、自適應的啟發式算法,是解決新常態下大規模、復雜化航天器任務調度問題的必要途徑.

2.2 精確求解算法

精確求解算法能夠在小規模的航天器任務調度問題中求得全局最優解,在動態或不確定的環境中也能保證解的全局最優性.雖然精確求解算法一般很難在有限的時間內求解大規模、復雜約束的航天器任務調度問題,但其中諸多思想對問題建模、解空間優化等方面也具有指導意義,故本節簡要介紹相關研究中常用的兩種精確求解算法.

1)分支定界算法

分支定界(Branch and bound,B&B)算法是由Land 等[162]于1960 年提出,并由Little 等[163]于1963 年正式命名的一種精確求解算法.B&B 算法通過分支、剪支和定界等手段縮小解空間,再通過各個分支搜尋最優解,是現階段求解整數線性規劃問題最常用的算法之一.由于航天器任務調度問題常被簡化為線性規劃問題,故B&B 算法在該領域也得到了諸多應用[22,41,48,53].同時,為改善在大規模任務調度問題中的求解效率,B&B 算法也常與列生成法[8,33,164]、割平面法[165-166]和Lagrangian 松弛法[25,96,167]等共同用于航天器任務調度的問題求解或邊界求解中.此外,B&B 算法通常能夠利用數學規劃求解器CPLEX 完成設計、改進和問題求解工作,CPLEX 中的諸多剪支、松弛策略對航天領域的B&B 算法設計也起到重要的參考價值.

2)動態規劃算法

動態規劃算法(Dynamic programming,DP)是由Bellman 等[168]于1966 年提出的一種通過問題分解和遞歸手段搜尋最優解的一類精確求解算法.針對遙感衛星成像任務調度問題,Lema?tre 等[23]采用基于圖論模型的DP 算法對問題進行了求解;白保存等[169]將問題分解為單軌任務最優合成問題;Damiani 等[170]設計了一個包含當前任務、衛星電量和固存容量的評價向量,并將問題分解為評價向量的最優任務組合問題.針對遙感衛星數傳任務調度問題,劉洋等[171]將問題分解為VTW 中數傳任務的最優組合問題;秦麗等[172]將問題按時間劃分成了若干個階段.上述DP 算法所采用的問題分解思想對大規模航天器任務調度問題的求解也具有參考價值.

2.3 元啟發式算法

2.3.1 演化算法

演化算法主要指通過模擬自然界生物種群演化機理和群體行為,對組合優化問題進行迭代尋優的一類元啟發式算法.演化算法在航天器任務調度領域應用廣泛,本節選取遺傳算法、蟻群算法和粒子群算法等三類典型的演化算法,對其在航天器任務調度問題求解過程中的模型基礎、編碼方式和改進策略等進行介紹.

1)遺傳算法

遺傳算法(Genetic algorithm,GA)是由Holland[173]于1975 年提出的一種模擬進化論“自然選擇”原理和遺傳機理的演化算法.GA 以種群的形式和概率化的遺傳機理進行迭代優化,具有隱并行性、多樣化的解表示能力和出色的全局尋優能力,在航天器任務調度問題中得到廣泛應用.

在任務排序模型的基礎上,Parish[101]提出了求解AFSCN Benchmark 的經典算法Genitor,該算法利用基因段表示測控任務的資源分配順序,如圖7(a)所示,解碼過程即依次為任務3、5、2、4、6 和1 分配資源;周毅榮[174]和Chen 等[175]設計了一種包含免疫遺傳算法和學習策略的GA,在大規模多星多站測控任務調度中取得出色的優化效果.上述基因編碼方式與任務排序模型契合度高,成為航天器任務調度算法中一種常見的編碼方式.Sun 等[28]、Song等[42]、張鵬等[106]、李云峰等[176]和韓傳奇等[177]也基于該編碼形式,以及成像質量優先、局部搜索、深度優先搜索、沖突消解和精英保留等策略有效求解了航天器任務調度問題.

圖7 遺傳算法求解航天器任務調度問題編碼示例Fig.7 Illustrations of the GA encoding for spacecraft mission scheduling

在VTW 分配模型的基礎上,Kim 等[45]、Li 等[57]和Niu 等[178]通過0-1 基因值表示遙感衛星執行任務的VTW,如圖7(b)所示,解碼過程即為任務1分配VTW2,以此類推;Hosseinabadi 等[179]通過基因段分別表示了執行任務的衛星、VTW;孫凱等[161]用整數基因值表示遙感衛星執行任務的VTW,并在算法中引入知識模型與參數學習策略;Xhafa 等[133-134]采用直接編碼的形式表示了航天器測控任務,并設計了包含種群競爭與淘汰策略的GA;Tang 等[98]和Du 等[180]通過基因值分別表示了導航衛星任務和測控任務的離散化VTW,并進一步設計了多目標的優化算法;張超等[43]還在傳統GA 的迭代機制中引入Metropolis 準則,通過基因變量表示VTW和任務工作模式,實現了敏捷遙感衛星任務調度問題的優化.

可見,基于任務排序模型和VTW 分配模型,GA 都能較好地完成解的表示和問題求解.不過,受任務排序模型本身編碼過程的限制,基于該模型的GA 可能會在優化過程中丟失優質解;而基于VTW分配模型的GA 可能出現編碼長度過長、基因表示類型過多的情況,對算法迭代與搜索效率可能產生一定的影響.因此,合理的航天器任務調度模型與編碼方式,以及有針對性地算法改進措施,對GA求解航天器任務調度問題起到重要作用.

2)蟻群算法

蟻群優化(Ant colony optimization,ACO)算法是由Colorni 等[181]于1991 年提出的一種模擬蟻群尋徑行為的演化算法.ACO 通過蟻群尋徑過程中信息素的積累、反饋、揮發與通訊等機制不斷調整蟻群路徑,表現出良好的漸近收斂性、隱并行性和全局尋優能力.

在遙感衛星任務調度方面,邱滌珊等[182]、耿遠卓等[183]基于蟻群系統、最大最小螞蟻、動態轉移概率等策略求解了遙感衛星任務調度問題;嚴珍珍等[184]、陳宇寧等[185]在傳統ACO 中引入了知識學習與信息素限制策略;針對ACO 優化周期長、易陷入局部最優的問題,朱新新等[186]等基于綜合啟發信息、沖突消解和擾動策略決策任務序列和VTW.此外,Gao 等[187]、Wu 等[188]在ACO 的框架中引入局部搜索策略,也取得了出色的優化效果.

在導航衛星和航天器測控任務調度方面,Zhang等[114-117]設計了蟻群間的合作交流機制;邢立寧等[189]和姚鋒等[190]在ACO 中引入導向局部搜索策略和知識模型,提升了算法在大規模測控任務調度問題中的局部與全局尋優能力;陳祥國等[15]在螞蟻轉移概率中引入偽隨機影響,并基于測控任務的沖突消解策略縮減了ACO 的搜索空間.針對導航衛星任務調度的問題中,黃雙臨等[191]在蟻群系統的基礎上設計了動態的偏向探索概率,實現螞蟻探索比例的自適應性調整;Li 等[192]考慮到ACO 優化初期信息素匱乏的現象,混合使用了GA 與ACO,也取得了良好的優化效果.

ACO 及其改進策略在航天器任務調度問題中得到諸多應用,但由于ACO 路徑優化的基本思想,相關研究中的ACO 通常以螞蟻路徑表示衛星執行任務的順序,其調度模型也以任務排序模型為主.因此,ACO 也會受解碼策略的影響導致優質解的丟失,在具有復雜約束邏輯的任務調度場景中可能不利于全局尋優.

3)粒子群算法

粒子群優化(Particle swarm optimization,PSO)算法是由Kennedy 等[193]于1995 年提出的一種模擬鳥群覓食行為的演化算法.與GA 和ACO算法相比,PSO 結構簡潔、易于實現,也具有收斂快、魯棒性好的特點.最初的PSO 主要用于連續優化問題,現階段航天器任務調度研究中采用的PSO算法大部分是以Kennedy 等[194]于1997 年提出的離散粒子群優化(Discrete particle swarm optimization,DPSO)算法為基礎的.

考慮到傳統PSO 算法不能求解離散優化問題,湯紹勛等[195]通過粒子位置矢量表示執行任務的VTW,通過粒子維度表示VTW 的數量;常飛等[196]通過粒子表示任務VTW 被選擇的概率,基于概率順序完成解碼,并引入基于種群多樣性的粒子自動增減機制;Chen 等[197]在粒子向量中同時表示了數傳任務的VTW 和衛星工作模式,并引入量子行為和變異算子增強了算法全局尋優能力.此外,Chen等[198]、國曉博等[199]和劉建銀等[200]在粒子向量中表示了任務資源,并引入遺傳、禁忌和方向回溯等機制,完成了高低軌航天器聯合測控任務、森林遙感衛星區域目標觀測等任務調度問題的研究.

由于上述算法通常以面向離散優化的DPSO為基礎,故其調度模型也以VTW 分配模型為主.不過,PSO 算法本身擁有連續優化與離散優化的雙重特點,過于側重離散化的編碼形式可能不利于算法的尋優.相反,采用離散優化(決策VTW)與連續優化(決策任務開始時間)的編碼方式,可能更適合現階段具有長VTW 特點的航天器任務調度問題.

2.3.2 局部搜索算法

局部搜索算法是指從初始解出發,不斷搜索鄰域空間并有選擇地向優質解移動的一類元啟發式算法.現階段航天器任務調度研究中常用的局部搜索算法包括禁忌搜索算法和模擬退火算法等.本節分別對兩種算法在航天器任務調度求解過程中的模型基礎、鄰域結構和搜索策略等進行介紹.

1)禁忌搜索算法

禁忌搜索(Tabu search,TS)算法是由Glover[201-202]于1986 年提出的一種帶有記憶策略的局部搜索算法.TS 算法通過禁忌表記錄尋優過程中的局部最優解或產生局部最優解的操作,以避免對局部最優空間的重復搜索,達到跳出局部最優、開辟優質解空間的效果.TS 算法操作簡單、實用性好,是最早用于航天器任務調度問題求解的算法之一.

在任務排序模型的基礎上,Cordeau 等[6-7]利用一種求解VRP 問題的TS 算法實現了遙感衛星單軌任務的調度;賀仁杰等[203]基于JSP 模型設計了工件插入、移動、交換機器等鄰域結構;左春榮等[204]設計了在任務序列中增減、替換任務的鄰域結構;陳英武等[205]和李菊芳等[206]基于任務序列設計了多種鄰域結構,并設計了基于變鄰域策略的TS 算法;Bl?chliger 等[111]基于圖著色模型中的顏色選擇設計鄰域結構,并采用變禁忌長度的TS 算法求解航天器測控任務調度問題.

在VTW 分配模型的基礎上,Xhafa 等[136]通過對VTW 和開始時間擾動的方式構造鄰域;Sarkheyli等[50]設計了任務增減和VTW 內沖突消解等鄰域結構,并選取任務與VTW 的匹配關系作為禁忌對象;Habet 等[207]設計了鄰域評估機制,用于提升TS算法在遙感衛星任務調度過程中的鄰域搜索效率.此外,禁忌搜索還被用于基于背包模型的航天器任務調度問題[60]的求解中.

TS 算法表現出良好的問題適用性和求解效果,但也由于機制較為簡單,近幾年來應用TS 算法直接求解航天器任務調度問題的研究較少.因此,TS算法應與最新的智能優化技術深度融合,才能更好地適應復雜化、多樣化的航天器任務調度問題.

2)模擬退火算法

模擬退火(Simulated annealing,SA)算法由Metropolis 等[208]于1953 年提出,并由Kirkpatrick等[209]于1983 年應用于組合優化領域.SA 算法是一種源于固體退火原理的局部搜索算法,根據溫度變化概率性地接受劣解,達到跳出局部最優、開辟優質解空間的效果.由于SA 算法通常受初始解質量和問題規模影響較小,具有良好的漸進收斂性,在航天器任務調度問題中得到諸多應用.

在任務排序模型的基礎上,黃瀚等[210]通過插入或交換任務序列中互斥頂點等方式構造鄰域,并設計了包含二次搜索和精英策略的SA 算法.在VTW分配模型的基礎上,賀仁杰等[211]、Gao 等[212]設計了任務增減、合并或分解的鄰域結構,并在SA 算法中加入了隨機擾動、重調度等策略;徐歡等[213]、Du 等[214]通過交換決策變量的方式直接構造SA 算法的鄰域;黃生俊等[215]借鑒蟻群算法中的反饋特性,結合先驗、后驗知識進行鄰域設計,并在算法陷入局部最優時觸發擾動;Wu 等[46]基于自適應概率設計了任務增減、遷移等鄰域操作,并在SA 算法中引入自適應的溫度控制和禁忌策略;Lin 等[216]通過交換任務VTW 和載荷頻段的方式構造鄰域,并混合使用了SA 與DP 算法,有效求解了遙感衛星多載荷任務調度問題.

此外,針對航天器任務調度問題規模巨大、易陷入局部最優的特點,近年來變鄰域搜索[217]、自適應大鄰域搜索[44,56]等局部搜索算法也得到諸多應用,取得了出色的優化效果.

2.3.3 其他算法

1)模因算法

模因算法(Memetic algorithm,MA)是由Moscato[218]于1989 年提出的一種融合演化算法與局部搜索算法的一類混合元啟發式算法.其中,“Memetic”源于Dawkins 著作《The Selfish Gene》[219]中“Meme”一詞,寓意文化層面的遺傳基因,故MA 又稱為文化基因算法.MA 既保留了演化算法基于種群進化的優化特點,又具有局部搜索算法出色的局部尋優能力,起到了對二者取長補短的效果.MA 在航天器任務調度領域也得到了諸多應用,根據演化算法與局部搜索算法的混合形式,可以分為以下三種:

a)基于演化算法框架的MA,即Moscato[218]最早提出的MA.例如,Du 等[180]、邢立寧等[189]、姚鋒等[190]和劉建銀等[200]分別在求解航天器任務調度的GA、ACO 和PSO 算法中引入了局部搜索機制.此類MA 可以視為一種基于個體改進和修復策略的演化算法,是最常用的一類MA.不過,針對個體的局部搜索機制也將增加種群迭代的時間,故設計合理的搜索頻率、迭代次數與觸發條件是此類MA 的關鍵.

b)基于局部搜索框架的MA.例如,賀仁杰等[203]和黃生俊等[215]分別在TS 和SA 中引入了個體交叉、信息素反饋等演化策略.此類MA 可以視為一種通過演化策略設計鄰域結構、引導搜索方向的局部搜索算法,但由于缺乏種群的支持,此類MA 在解的多樣性、隱并行性等方面不及演化算法.

c)基于分層框架的MA.例如,為發揮GA 早期尋優和SA 深度搜索的能力,Zhu 等[55]設計了基于GA 和SA 的兩階段式優化算法,在遙感星座任務調度中也取得了出色的效果.不過,此類MA 對編碼形式的通用性、算法切換的合理性也有更高的要求.

可見,MA 實際上是一種演化算法與局部搜索算法組合的框架.針對復雜化、大規模的航天器任務調度需求,相互協同、取長補短、優勢互補的算法組合框架對問題求解將起到十分重要的幫助.

2)基于機器學習的決策算法

基于機器學習的決策算法是指通過監督學習、強化學習等機器學習手段,訓練航天器任務調度決策模型,進而對航天器任務進行調度的一類方法.在監督學習方面,Li 等[220]利用魯棒決策樹、支持向量機和人工神經網絡構造了一種遙感衛星任務可調度性預測模型;劉嵩等[221]從遙感衛星歷史數據中提取了任務優先級、持續時間和沖突度等特征,基于變隱含層的BP 神經網絡模型構造了任務可調度性預測模型;考慮云霧遮擋等不確定性因素,邢立寧等[67]提取了氣象特征,并利用任務可調度預測模型設計了遙感衛星自主任務調度算法;Du 等[158]通過進化神經網絡算法訓練任務可調度性預測模型,將任務分配給最有可能執行該任務的衛星,顯著提高了大規模敏捷遙感衛星任務調度的效率.

在強化學習方面,針對遙感衛星協同任務調度問題,王沖等[68-69]分別通過Q 學習算法和進化神經網絡算法訓練了衛星在動作集中的選擇策略;Wang等[70]通過A3C 算法訓練了遙感衛星任務調度決策模型,當新任務達到時,該模型將決定任務執行與否,并為決定執行的任務分配一個最長的VTW,為星上任務的自主調度提供了解決方案.

基于機器學習決策算法可視為一種利用高級規則指導任務排序或任務分配的算法,具有啟發式算法簡單、快速和機器學習技術自適應、自學習的綜合特征.目前各類航天器管控部門都積累了大量的任務調度歷史數據,故相關技術具有很強的應用前景.另一方面,雖然上述算法實現了航天器任務的自主調度,但也呈現出“來一個決策一個”的局限性,難以保障大規模任務調度的全局優化性.同時,上述算法均對所研究的問題進行了大幅度簡化,以便提取用于模型訓練的任務與資源特征,但在現階段航天器任務調度問題日趨復雜的情況下,基于簡單特征的決策模型可能很難取得理想的效果.

2.4 小結

本節從啟發式算法、精確求解算法和元啟發式算法等三個角度梳理了航天器任務調度研究中的常用算法,并對各類算法的編碼特點、鄰域結構和優缺點進行了分析.表2 將上述內容進行了總結.這些算法成功求解了諸多航天器任務調度難題,貢獻了重要的理論與實踐經驗,但與此同時,也存在以下兩點不足:

表2 航天器任務調度研究中常用算法總結Table 2 A summary of commonly used algorithms for spacecraft mission scheduling

1)航天器任務調度算法與模型緊耦合,算法設計的靈活性不足.

各類航天器任務調度算法均有其適用的任務調度模型,這也是造成現階段航天器任務調度模型與算法緊耦合、調度算法通用性不足的主要原因.因此,結合航天器任務調度模型研究現狀,研究模型與算法解耦、算法靈活可配的航天器任務調度架構具有重要的實踐意義.

2)不同算法之間深度協同、合理搭配的有效機制還未形成.

各類算法均有不同的優缺點和適用性,例如啟發式算法常用于輔助決策,精確算法求解大規模問題能力有限,演化算法全局尋優能力強等.雖然模因算法給出了一種很好的算法協同思路,但其現階段在求解能力、問題適用性等方面仍有提升空間.因此,對不同類型的算法進行合理搭配,形成深度協同、取長補短、優勢互補的算法組合框架也是求解大規模、復雜化航天器任務調度問題的必要途徑.

3 航天器任務調度通用求解技術

航天器任務調度通用求解技術是指可以針對不同類型的航天器任務建立通用化的任務調度模型,或采用不同任務調度算法進行模型解算的通用求解器、工具箱、算法包等.航天器任務調度通用求解技術可以解決不同場景下的航天器任務調度、異構多航天器協同任務調度等現實問題,方便地調用多樣化、可拓展的調度算法,為從業人員提供便捷、豐富且有效的問題建模與求解手段.因此,航天器任務調度通用求解技術對提升航天器綜合管控自動化、智能化和一體化水平起到重要作用,是衡量一個國家航天綜合實力的重要標準,也是航天部門亟需發展的關鍵技術.

目前,具有通用建模與求解特色的航天器任務調度工具有CPLEX、STK/Scheduler、Europa2 和我國商業遙感衛星“高景一號”任務調度分系統等.本節對上述四種通用求解技術的建模特色、求解算法和主要功能進行梳理,總結上述通用求解技術的優缺點,結合航天綜合管控的發展現狀,指出我國自主研發航天器任務調度通用求解器的必要性和新的應用思路,為航天器任務調度通用求解工具的研究與設計提供參考.

3.1 數學規劃求解器CPLEX

CPLEX 是美國IBM 公司開發的一款數學規劃求解器,適用于線性規劃、二次規劃等問題[222].在建模語言方面,CPLEX 語言簡潔易懂,并可以與C++、Java 和Python 等主流編程語言兼容;在求解質量方面,CPLEX 內置了單純形、分支定界等一系列精確求解算法,可以給出問題的最優解,保持了一系列經典運籌學Benchmark 中的最優記錄,因此也被應用于航天器任務調度問題的求解中.

針對遙感衛星成像與數傳任務一體化調度問題,Xiao 等[22]建立了分段式的FSP 模型,并通過CPLEX 對問題進行了求解.不過,由于問題的NPHard 特性,在7 200 s 的優化時間內只能完成20 個任務的調度;考慮到敏捷衛星時間依賴的姿態轉換約束無法由線性函數表示,Liu 等[44]通過CPLEX對簡化后的問題進行了優化,但也僅能完成12 個任務;為保障不確定環境下任務調度的最優性,Valicka 等[53]采用CPLEX 對考慮隨機云層遮擋的遙感衛星任務進行了調度,優化時間約為2 000～3 000 s;針對“資源三號”遙感衛星任務調度問題,徐忠良等[223]通過CPLEX 完成了11 個任務的優化調度;Bensana 等[59]成功利用CPLEX 對衛星單軌任務進行了調度,但無法完成多軌任務的有效調度.

另一方面,CPLEX 可與其他算法或策略混合使用,一定程度上能夠提升航天器任務調度問題的求解效率.例如,針對Galileo 導航星座任務調度問題,Marinelli 等[96]在CPLEX 中引入了Lagrangian 松弛和其他啟發式策略,能夠在18 000 s 的優化時間內對360 個導航衛星任務進行調度.同時,Marinelli 還指出在無其他輔助策略的情況下,CPLEX 的求解能力僅為120 個任務.Xu 等[24]、王沛等[224]將局部搜索算法與CPLEX 相結合,在1 800 s的時間內對100 個遙感衛星任務進行了調度.

上述研究表明,雖然CPLEX 在求解小規模航天器任務調度問題、不確定性任務調度問題和問題邊界等方面表現出色,但在求解大規模任務調度問題的時候效率低下,且無法準確描述非線性的約束條件和收益.因此,在現階段任務規模不斷增長的情況下,CPLEX 很難滿足航天管控部門對任務調度質量與速率的雙重需要,很難在實際的航天業務調度系統中投入使用.

3.2 通用衛星調度軟件STK/Scheduler

STK/Scheduler 是美國Orbit Logic 公司開發的一款衛星任務調度商用軟件[225],可在STK 6.0 以上版本中直接調用.STK/Scheduler 可以在STK模型和數據的基礎上快速地建立任務調度模型,通過內置的算法給出任務調度方案,并具有友好的用戶操作界面,如圖8 所示.其中,STK 所計算的衛星軌道與VTW 具有較高的準確性,故STK 也常作為航天器任務調度研究中VTW 的計算工具.

圖8 操作界面示例Fig.8 A view of the STK/Scheduler

STK/Scheduler 中包含以下5 種調度算法:1)One-Pass 算法,即基于任務優先級順序和內置的期望函數分別確定任務資源與開始時間,是一種典型的任務排序算法;2)Sequential 算法,即在One-Pass 算法的基礎上同時考慮任務VTW 時間、時長等其他因素;3)Multi-Pass 算法,即基于規則多次運行One-Pass 算法并調整調度方案,是一種任務排序與沖突消解相結合的算法;4)Neural network 算法,即基于規則為任務分配VTW 與開始時間并修復不可行解,是一種任務分配與沖突消解相結合的算法;5)Random 算法,與Neural Network 算法相似,但在分配VTW 與開始時間時采用隨機策略.

李英先等[226]基于STK/Scheduler 實現了中繼通信衛星的任務調度,但考慮約束較為簡單,沒有對頻段匹配、切換時間等具有中繼衛星特色的約束條件進行建模;李云峰等[227]指出STK/Scheduler 發送命令的時間較長,不利于大規模的任務調度;白敬培等[228]對5 種內置算法進行了測試,結果表明Multi-Pass 算法和Random 算法在短時間內的優化效果最佳;Li 等[229]在STK/Scheduler 的軟件基礎上引入了任務動態調整機制;Fisher 等[230]給出了STK/Scheduler 自定義算法的介紹,但也僅限于對排序規則、交換策略等的調整功能.以上,雖然STK/Scheduler 在航天器任務調度問題中取得了一定的效果,但在問題復雜化、多元化的發展趨勢下,STK/Scheduler 也暴露出一些不足:

1)雖然對航天器任務、資源進行了用戶友好化的封裝,但也很大程度上限制了任務、資源的屬性與約束格式,不利于包含復雜任務或約束的問題求解,二次開發的難度較大;

2)缺乏對任務、資源、收益或約束條件的動態調整功能,常用于靜態的航天器任務調度問題;

3)主要功能最后更新于2006 年,沒有包含進化算法、禁忌搜索等現階段主流的智能優化算法,對規則的依賴性較大.隨著近年來航天器任務調度問題規模與復雜性的不斷提升,其內置算法的求解效果可能不佳.

另一方面,2013 年,Herz 等[231]在航天器測控任務調度的問題中使用了STK/Scheduler Online,通過互聯網訪問了STK/Scheduler 服務器,完成了場景建模、參數配置、優化調度等一系列功能.這種遠程式的任務調度方式使得用戶的訪問便捷、高效,有助于服務功能的迭代更新和故障的快速修復,在高性能服務器的支持下也有助于調度效率的提升.因此,STK/Scheduler Online 也為航天器任務調度系統的設計與部署提供了一種新思路.

3.3 航天器任務規劃軟件Europa2

Europa2 (2nd generation of extensible universal remote operations architecture)是NASA開發的面向航天器任務規劃的第二代可擴展式通用遠程操作體系結構[232],已在NASA 哈勃空間望遠鏡[233]、DS-1 自主衛星[234]等項目中得到應用.與規劃領域經典語言PDDL (Planning domain description language)不同,Europa2 所基于的NDDL(New domain description language)是一種基于狀態變量、面向對象與聲明性的語言,故Europa2中主要通過定義標記、事務、對象、類、時間線和規劃解等完成對一類航天器任務場景的描述,并通過約束傳播等約束規劃技術給出一個可行的方案[235-238].

基于狀態變量的特點,Europa2 主要面向航天器任務規劃問題,如航天器執行任務的動作邏輯、狀態轉移等.該問題主要描述航天器任務的邏輯關系,給出滿足約束的可行方案,對資源調度的需求較少.而本文所探討的任務調度問題主要解決任務資源與時間的分配,例如執行任務的VTW、航天器及其電量、固存等載荷資源等.故針對航天器任務調度問題,Europa2 存在以下不足:

1)缺乏收益函數和調度優化機制,Europa2 通過約束規劃等方法給出可行的航天器動作序列,但無法在收益函數的驅動下迭代地給出更優的調度方案;

2)基于約束傳播的約束規劃算法只能適用于小規模的任務場景,例如單星單軌20 個任務的規劃時間已非常長,且最新版本Europa2.6 發布于2011 年[232],已很難適應現階段大規模、復雜化的航天器管控新常態.

不過,Europa2 中的約束傳播算法能夠在新任務到達、任務或資源屬性變更的情況下快速給出可行方案,這對面向快速響應需求的動態任務調度算法與框架設計具有啟發意義.此外,NASA 于2015年公布了一款基于Europa2 的開源規劃調度工具包OpenSPIFe (Open scheduling and planning interface for exploration)[239].OpenSPIFe 具備動作規劃、動態調整、界面可視化等功能,但相關應用較少,有待進一步研究.

3.4 “高景一號”任務調度分系統

“高景一號”是我國首個商用敏捷遙感星座,目前由4 顆位于太陽同步軌道的0.5 米分辨率光學成像衛星構成,每顆衛星的軌道周期約為97 分鐘.按照相關計劃,還將陸續發射20 余顆敏捷遙感衛星,與現有的4 顆衛星組建新的“高景一號”星座網絡.鑒于“高景一號”星座的商業化運營模式和不斷增加的衛星數量,如何充分調度衛星任務、最大化經濟收益是“高景一號”運控部門迫切關心的問題.

目前,“高景一號”任務調度分系統采用的調度模型之一為任務排序模型,并基于成像質量最高原則(即在VTW 中點處執行任務)對任務序列進行解碼.由于在模型解碼過程中會對任務序列進行約束檢查,解碼后均為可行方案.因此,該調度模型的通用性也較強,在此過程中復雜任務約束也均能得到處理.

在任務排序模型的基礎上,“高景一號”任務調度分系統所采用的調度算法主要為任務分配算法和優先級排序算法.例如,基于任務收益、持續時間、窗口數量等一系列任務與資源屬性,定義任務的綜合優先級,并基于優先級降序構建單星任務序列、依次分配資源.由于機制簡單,“高景一號”任務調度分系統能夠較快地給出單星任務調度結果,但也暴露出任務調度效果不佳、衛星缺乏協同、資源利用不充分等問題.

另一方面,當通過人工調整的方式對任務排序結果進行進一步優化時,仍需重新進行解碼與約束檢查工作.由于人工調整的結果并不能得到實時反饋,故人工調整的方式存在一定的盲目性,即可能出現人工調整結果不及原方案的情況.由此,該模型與算法雖然能夠處理復雜的衛星業務約束,但任務調度效率和快速響應能力仍有待提高.

3.5 小結

本節梳理了CPLEX、STK/Scheduler、Europa2和“高景一號”任務調度分系統的基本原理、適用性和優缺點,表3 對本節內容進行了總結.通過本節的綜述與分析可知:

表3 用于航天任務調度的通用求解器總結Table 3 A summary of the general techniques for spacecraft mission scheduling

1)現階段尚無能夠滿足航天器任務調度需求的通用求解器.

雖然上述航天器任務調度通用求解器均在一些應用場景中取得了良好的求解效果,但每一款求解器的局限性也非常明顯:例如,CPLEX 難以處理大規模與非線性問題,STK/Scheduler 復雜約束處理與二次開發難度大,Europa2 缺乏對收益函數的優化,“高景一號”任務調度分系統優化能力有限等.即使STK/Scheduler 與Europa2 能夠適用于簡單的航天器任務調度問題,但其內置算法也相對落后,已多年未發布新版本.目前,航天器任務調度問題正向著大規模、復雜化和動態需求常態化的趨勢快速發展,上述航天器任務調度通用求解器尚不能滿足發展的要求.

2)我國需要研發具有自主知識產權的航天器任務調度通用求解技術.

綜合考慮約束描述能力、求解效果、版權與服務支持等因素,CPLEX、STK/Scheduler、Europa2并未在我國航天系統中得到應用.或許STK/Scheduler和Europa2 等航天器任務調度通用求解器已有融合先進技術的新版本,但并未對外公布.因此,我國需要研發適合我國國情、具有自主知識產權的航天器任務調度通用求解技術,在核心技術上掌握主動權,為提升我國航天綜合管控實力提供技術支撐.

3)基于云平臺的遠程航天器任務調度服務是一種新的應用思路.

STK/Scheduler Online 提供了一種在線式的航天器任務調度服務新模式.該模式使用戶訪問更加便捷、高效,有助于服務功能的迭代更新和故障的快速修復,在高性能服務器的支持下也能提升任務調度的效率.因此,結合現階段云計算的技術優勢,向航天部門提供遠程的任務調度服務是一種新穎、高效的應用思路.

4 結束語

航天器任務調度是航天器管控的重要內容,是發揮航天系統社會經濟效益、實現航天器使命價值的重要保障.隨著航天事業的快速發展,作為調度技術的兩大要素,航天器任務調度模型與調度算法已得到廣泛研究,并在各大航天調度系統中得以檢驗.在此過程中,涌現出一批優秀的調度模型、算法和通用求解技術,為航天器任務調度研究貢獻了重要的理論體系與實踐經驗.本文系統地梳理了近年來航天器任務調度研究中的模型、算法與通用求解技術,總結了相關技術中的共性特征與區別,為未來航天器任務調度的研究工作提供了參考.

本文的主要工作如下:1)根據航天器任務目標的不同,將現階段具有調度需求的主要航天器任務分為遙感衛星任務、中繼通信衛星任務、導航衛星任務和航天器測控任務,闡述了各類航天器任務調度的常用模型及特征;2)根據優化原理的不同,將航天器任務調度算法分為啟發式算法、精確求解算法和元啟發式算法,探討了各類算法的編碼特點和優缺點;3)介紹了CPLEX、STK/Scheduler、Europa2和“高景一號”任務調度分系統等具有通用特色的航天器任務調度工具,分析了其適用性與應用前景.

然而,通過本文的綜述也發現,現階段航天器任務調度研究暴露出“模型-問題-算法”緊耦合的弊端,模型與算法的兼容性與可拓展性不足,難以適應航天系統靈活組網、快速響應的新常態.由此,本文指出以下幾點未來航天器任務調度研究的新方向:

1)研究航天器任務調度統一化建模語言.

航天器任務調度統一化建模語言是解決航天器任務調度模型兼容性問題的根本途徑.通過本文綜述發現,諸多航天器任務調度模型具有很大的相似性,其圍繞任務與資源在時、空、頻域可見性的建模原則是統一的.現階段已有幾款成熟的統一化建模語言,但這些語言缺乏航天領域和組合優化領域的應用特色.由此,研究統一化且具備領域特色的航天器任務調度建模語言,是發展航天器通用建模與求解技術,滿足未來航天器靈活管控需要的內在要求.

2)研究航天系統管控體制下有效應對大規模任務調度問題的解空間優化技術.

隨著航天器規模持續增加以及航天系統組網的常態化發展,解空間規模已成為限制航天器任務調度效率的關鍵因素.目前,任務分配、分層規劃等方法可將大規模航天器任務調度問題分解為諸多子問題,雖然提升了調度效率,但也違背了航天系統綜合管控、一體化調度的發展趨勢,丟失了問題的全局優化特點.近年來,深度學習、強化學習等技術發展迅速,并在旅行商、車輛路徑規劃等經典組合優化問題中得到了成功應用.基于機器學習的技術優勢,可以研究航天器任務調度解空間優化技術,在保留全局性優化特點的基礎上,實現大規模任務調度解空間規模的精準縮減,以滿足航天系統綜合管控與快速響應的雙重需求.

3)共同打造航天器任務調度算法庫與測試集.

以往,調度模型兼容性不足是限制航天器任務調度算法通用化發展的主要原因,而上述航天器統一化建模語言可以解決這一問題.以后,航天器任務調度算法不再局限于某一特定的航天應用場景,而將適用于更多的具有普遍意義的航天器任務調度問題.鑒于此,打造一個開源的、持續更新的航天器任務調度算法庫,有助于營造世界范圍內相關學者及業務人員共研共享的發展環境.同時,為檢驗算法性能、促進良性競爭,打造兼具算法測試、教學、新案例發布等功能的航天器任務調度標準測試集也具有十分重要的意義.

4)研發具有自主知識產權的航天器任務調度通用求解技術.

在上述研究方向的基礎上,研發適合我國國情、具有自主知識產權、滿足國家航天戰略發展需要的航天器任務調度通用求解技術勢在必行.通用求解技術的研發是實現我國在軌航天器綜合管控、靈活組網這一目標的出發點和落腳點.未來,在通用求解技術的支撐下,資源衛星、商業衛星、偵察衛星、導航衛星、中繼衛星、空間站與地面站網等不同類型、隸屬不同部門的航天任務資源將密切聯動,更大限度地發揮我國航天系統的社會經濟效益.