航天器任務(wù)調(diào)度模型、算法與通用求解技術(shù)綜述

杜永浩 邢立寧 姚 鋒 陳盈果

21 世紀(jì)以來(lái),我國(guó)航天事業(yè)步入快速發(fā)展時(shí)期.隨著“高分辨率對(duì)地觀測(cè)系統(tǒng)”、“北斗衛(wèi)星導(dǎo)航定位系統(tǒng)”等國(guó)家重大專(zhuān)項(xiàng)的相繼開(kāi)展,以及商業(yè)航天產(chǎn)業(yè)的蓬勃發(fā)展,我國(guó)在軌航天器規(guī)模持續(xù)增加,總數(shù)位居世界第二.在此期間,各類(lèi)航天器平臺(tái)與載荷能力也經(jīng)歷了深刻變革.為適應(yīng)大規(guī)模、復(fù)雜化的航天器管控新常態(tài),融合現(xiàn)代運(yùn)籌學(xué)、計(jì)算科學(xué)與相關(guān)領(lǐng)域知識(shí)的航天器任務(wù)調(diào)度技術(shù)起到了舉足輕重的作用.

航天器任務(wù)調(diào)度技術(shù)是指在航天器使命任務(wù)與管控需求的驅(qū)動(dòng)下,通過(guò)對(duì)任務(wù)與資源的建模,消解航天器任務(wù)執(zhí)行過(guò)程中的約束沖突,最大化航天器任務(wù)與管控效益的一種優(yōu)化技術(shù).在諸多學(xué)者與航天從業(yè)人員的推動(dòng)下,航天器任務(wù)調(diào)度技術(shù)得到了快速的發(fā)展,在美國(guó)DigitalGlobe 高分辨率對(duì)地觀測(cè)系統(tǒng)、歐盟Galileo 衛(wèi)星導(dǎo)航系統(tǒng)和我國(guó)“高分”系列對(duì)地觀測(cè)系統(tǒng)、“北斗”衛(wèi)星導(dǎo)航系統(tǒng)等國(guó)內(nèi)外先進(jìn)的航天系統(tǒng)中得到了充分的實(shí)踐與驗(yàn)證.在此過(guò)程中,作為調(diào)度技術(shù)的兩大要素,航天器任務(wù)調(diào)度模型與調(diào)度算法的重要性也日益凸顯.

調(diào)度模型是航天器任務(wù)調(diào)度的重要基礎(chǔ),是決定問(wèn)題描述方式、指導(dǎo)算法設(shè)計(jì)、影響問(wèn)題復(fù)雜度的關(guān)鍵因素.現(xiàn)階段,線性規(guī)劃模型、圖論模型、約束滿(mǎn)足模型等各類(lèi)調(diào)度模型已被廣泛運(yùn)用于航天器任務(wù)調(diào)度問(wèn)題研究中.在這些研究中,一方面,許多調(diào)度模型表現(xiàn)出鮮明的問(wèn)題特色與針對(duì)性,引入了與調(diào)度問(wèn)題緊密相關(guān)的決策手段;另一方面,許多模型也表現(xiàn)出了較大的相似性,折射出航天器任務(wù)調(diào)度問(wèn)題的一些共性特征.因此,面對(duì)模型種類(lèi)和應(yīng)用場(chǎng)景繁多的航天器任務(wù)調(diào)度技術(shù)發(fā)展現(xiàn)狀,建立一個(gè)怎樣的調(diào)度模型,是決定調(diào)度問(wèn)題是否可解、問(wèn)題特征是否可描述、應(yīng)用場(chǎng)景是否可拓展的重要環(huán)節(jié).

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

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

本文分別對(duì)航天器任務(wù)調(diào)度模型、算法和通用求解技術(shù)等三個(gè)方面進(jìn)行了梳理與總結(jié).第1 節(jié)根據(jù)航天器類(lèi)型的不同,將現(xiàn)階段具有調(diào)度需求的主要航天器任務(wù)分為遙感衛(wèi)星任務(wù)、中繼通信衛(wèi)星任務(wù)、導(dǎo)航衛(wèi)星任務(wù)和航天器測(cè)控任務(wù),分別闡述了各類(lèi)航天器任務(wù)調(diào)度的常用模型及特征.第2 節(jié)根據(jù)優(yōu)化原理的不同,將航天器任務(wù)調(diào)度算法分為啟發(fā)式算法、精確求解算法和元啟發(fā)式算法,重點(diǎn)討論了各類(lèi)算法的編碼特點(diǎn)和優(yōu)缺點(diǎn).第3 節(jié)分別介紹了CPLEX、STK/Scheduler、Europa2 和“高景一號(hào)”任務(wù)調(diào)度分系統(tǒng)等具有通用特色的航天器任務(wù)調(diào)度工具,并分析了其適用性與應(yīng)用前景.最后,第4 節(jié)綜合研究現(xiàn)狀,對(duì)航天器任務(wù)調(diào)度領(lǐng)域未來(lái)的研究趨勢(shì)進(jìn)行了展望.

1 航天器任務(wù)調(diào)度模型

在任務(wù)調(diào)度問(wèn)題的求解過(guò)程中,問(wèn)題建模往往是首要步驟.在航天器任務(wù)調(diào)度相關(guān)研究中,各類(lèi)航天器任務(wù)往往由不同的職能部門(mén)負(fù)責(zé)調(diào)度,并采用不同的問(wèn)題建模方式,影響著任務(wù)與資源處理、決策變量設(shè)計(jì)和模型編碼等諸多方面.根據(jù)職能部門(mén)的不同,可以將航天器任務(wù)分為運(yùn)控任務(wù)與測(cè)控任務(wù)兩大類(lèi):

定義1 (航天器運(yùn)控任務(wù)).為實(shí)現(xiàn)遙感衛(wèi)星、中繼通信衛(wèi)星和導(dǎo)航衛(wèi)星等航天器的使命任務(wù)和任務(wù)數(shù)據(jù)的回傳,在航天器特定工作模式和載荷的支撐下,由所屬運(yùn)控部門(mén)針對(duì)任務(wù)目標(biāo)或數(shù)據(jù)接收目標(biāo)制定的一類(lèi)專(zhuān)門(mén)任務(wù).

定義2 (航天器測(cè)控任務(wù)).為保障航天器正常運(yùn)行,滿(mǎn)足航天器遙測(cè)、跟蹤和指令上注等日常需要,在航天器載荷和地面管控資源的共同支撐下,由測(cè)控部門(mén)針對(duì)航天器統(tǒng)一制定的一類(lèi)任務(wù).

由此,在上述定義的基礎(chǔ)上,本節(jié)梳理了遙感衛(wèi)星、中繼通信衛(wèi)星、導(dǎo)航衛(wèi)星和航天器測(cè)控等常見(jiàn)的航天器任務(wù)調(diào)度模型,分析了不同航天器任務(wù)調(diào)度問(wèn)題的建模特色、決策變量形式和模型優(yōu)缺點(diǎn),揭示不同航天器任務(wù)調(diào)度模型之間的共性特征與區(qū)別,闡明建模過(guò)程中提升模型兼容性、適用性和求解效率等方面的必要性,為航天器任務(wù)調(diào)度的模型研究提供參考.

1.1 遙感衛(wèi)星任務(wù)調(diào)度模型

遙感衛(wèi)星任務(wù)是指針對(duì)地表、海洋、大氣和太空等環(huán)境中的目標(biāo),通過(guò)星上遙感載荷進(jìn)行信息數(shù)據(jù)收集并傳輸給地面設(shè)備的一類(lèi)航天器運(yùn)控任務(wù).遙感衛(wèi)星是目前在軌數(shù)量最多的航天器,在農(nóng)業(yè)、經(jīng)濟(jì)、軍事等領(lǐng)域發(fā)揮著不可替代作用.因此,遙感衛(wèi)星任務(wù)也是現(xiàn)階段種類(lèi)最為繁多、需求量最大、應(yīng)用最為廣泛的一類(lèi)航天器運(yùn)控任務(wù).

遙感衛(wèi)星任務(wù)調(diào)度是一類(lèi)具有NP-Hard (Nondeterministic polynomial-time hard)特性的組合優(yōu)化問(wèn)題[5],該問(wèn)題往往具有序列優(yōu)化與資源優(yōu)化的雙重特點(diǎn),既要決策任務(wù)執(zhí)行的先后順序,又要為任務(wù)合理地分配衛(wèi)星及其載荷資源.由此,根據(jù)調(diào)度模型中決策對(duì)象的不同,本節(jié)將遙感衛(wèi)星任務(wù)調(diào)度模型分為面向資源的任務(wù)排序模型(簡(jiǎn)稱(chēng)任務(wù)排序模型)和面向任務(wù)的資源分配模型(簡(jiǎn)稱(chēng)資源分配模型)兩大類(lèi),并基于此對(duì)遙感衛(wèi)星任務(wù)調(diào)度模型展開(kāi)進(jìn)一步的闡述.

1.1.1 任務(wù)排序模型

20 世紀(jì)末,面對(duì)遙感衛(wèi)星任務(wù)調(diào)度這一全新的問(wèn)題,人們嘗試從經(jīng)典運(yùn)籌學(xué)模型中尋找解決方案.在這些模型中,決策變量主要表示資源執(zhí)行任務(wù)的先后順序,反映任務(wù)連續(xù)執(zhí)行過(guò)程中的時(shí)序邏輯和能力約束,對(duì)早期遙感衛(wèi)星任務(wù)調(diào)度問(wèn)題的求解起到重要幫助.

1)車(chē)輛路徑規(guī)劃模型

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

2)圖論模型

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

3)車(chē)間調(diào)度模型

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

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

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

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

1.1.2 資源分配模型

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

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

然而,敏捷遙感衛(wèi)星技術(shù)的發(fā)展也暴露出了傳統(tǒng)VTW 分配模型的局限性.近年來(lái)發(fā)射的遙感衛(wèi)星通常具備俯仰成像能力,即能夠先于或晚于目標(biāo)上空進(jìn)行遠(yuǎn)距離的傾斜成像,這一技術(shù)為遙感衛(wèi)星在目標(biāo)上空過(guò)境時(shí)帶來(lái)了更長(zhǎng)的VTW 和更多的成像機(jī)會(huì)[37],如圖2(b)所示.因此,在敏捷遙感衛(wèi)星任務(wù)調(diào)度模型中,不僅需要決策任務(wù)執(zhí)行的VTW,還需要決定任務(wù)在該VTW 內(nèi)具體的開(kāi)始時(shí)刻.針對(duì)這一問(wèn)題,學(xué)者們通過(guò)以下三種方法對(duì)模型進(jìn)行了改進(jìn):

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

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

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

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

3)離散化VTW 分配模型

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

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

此外,還有學(xué)者將遙感衛(wèi)星任務(wù)調(diào)度問(wèn)題抽象為背包問(wèn)題[6,59-61],但通常忽略了衛(wèi)星執(zhí)行任務(wù)的先后順序,對(duì)問(wèn)題簡(jiǎn)化程度較高,且近年來(lái)沒(méi)有較大發(fā)展.許多學(xué)者基于Multi-Agent 模型[62-66]與機(jī)器學(xué)習(xí)模型[67-70]等研究了面向自主衛(wèi)星的分布式協(xié)同任務(wù)調(diào)度問(wèn)題,但此類(lèi)問(wèn)題通常突出星上自主性和快響性特點(diǎn),不屬于現(xiàn)階段用戶(hù)需求驅(qū)動(dòng)與地面統(tǒng)一管控體制下的衛(wèi)星日常任務(wù)調(diào)度范疇,故本節(jié)不討論這些模型.

1.2 中繼通信衛(wèi)星任務(wù)調(diào)度模型

隨著遙感衛(wèi)星數(shù)量和對(duì)地觀測(cè)數(shù)據(jù)量的不斷提升,地面數(shù)傳站難以滿(mǎn)足現(xiàn)階段遙感星群大規(guī)模、高頻率的數(shù)據(jù)傳輸需求.因此,為在軌衛(wèi)星與地面站提供數(shù)據(jù)中轉(zhuǎn)服務(wù)的中繼通信衛(wèi)星起到了十分重要的作用.由于在軌道上承擔(dān)的使命任務(wù)與地面數(shù)傳站相近,中繼通信衛(wèi)星也被稱(chēng)為“天基數(shù)傳站”.

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

圖4 中繼通信衛(wèi)星任務(wù)調(diào)度問(wèn)題與遙感衛(wèi)星任務(wù)調(diào)度問(wèn)題的類(lèi)比Fig.4 A comparison between the mission scheduling of relay satellites and remote sensing satellites

1)任務(wù)排序模型方面

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

2)VTW 分配模型方面

在中繼通信衛(wèi)星執(zhí)行任務(wù)的過(guò)程中,往往也會(huì)出現(xiàn)VTW 長(zhǎng)度超過(guò)任務(wù)時(shí)長(zhǎng)的情況,即相關(guān)研究中提到的“滑動(dòng)窗口”.在這些研究中,通常采用啟發(fā)式規(guī)則確定任務(wù)在VTW 內(nèi)的開(kāi)始時(shí)間.例如,顧中舜[80]、趙靜等[81-82]、Zhao 等[83]通過(guò)0-1 變量表示了中繼通信任務(wù)執(zhí)行的VTW,并基于優(yōu)先級(jí)順序和最早開(kāi)始原則依次計(jì)算任務(wù)的開(kāi)始時(shí)間;方炎申等[84-86]在啟發(fā)式規(guī)則的基礎(chǔ)上引入了專(zhuān)家系統(tǒng)規(guī)則;賀川等[87]以任務(wù)最小損失機(jī)會(huì)確定開(kāi)始時(shí)間;何敏藩等[88]設(shè)計(jì)了最早、最晚和隨機(jī)開(kāi)始策略等.

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

1.3 導(dǎo)航衛(wèi)星任務(wù)調(diào)度模型

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

1)GPS 與GLONASS 導(dǎo)航系統(tǒng)

GPS 是全球最早建成的導(dǎo)航定位系統(tǒng),并在2005 年就完成了全球范圍的地面站部署,可在任何時(shí)刻實(shí)現(xiàn)星地建鏈,通常無(wú)需考慮VTW 約束[90].GLONASS 也在俄羅斯本土與周邊國(guó)家大量部署地面站[91],衛(wèi)星的可見(jiàn)性也較高.由此,GPS 與GLONASS 系統(tǒng)中的星地通信鏈路充裕,對(duì)任務(wù)與資源調(diào)度的需求程度較低,相關(guān)的公開(kāi)文獻(xiàn)較少.

2)Galileo 導(dǎo)航系統(tǒng)

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

3)“北斗”導(dǎo)航系統(tǒng)

針對(duì)“北斗”導(dǎo)航系統(tǒng)星地建鏈任務(wù)調(diào)度問(wèn)題,龍運(yùn)軍等[97]基于0-1 變量表示了執(zhí)行任務(wù)的地面站及VTW,并通過(guò)另外兩個(gè)整數(shù)變量分別表示了任務(wù)的開(kāi)始與結(jié)束時(shí)間,處理了測(cè)站建鏈數(shù)量、天線轉(zhuǎn)換時(shí)間等實(shí)際約束,對(duì)建鏈時(shí)長(zhǎng)、任務(wù)完成度等目標(biāo)進(jìn)行了優(yōu)化.Tang 等[98]通過(guò)離散VTW 表示了導(dǎo)航任務(wù)的開(kāi)始時(shí)間,對(duì)任務(wù)完成度和負(fù)載均衡度等目標(biāo)進(jìn)行了優(yōu)化.考慮到任務(wù)等待時(shí)間和設(shè)備使用時(shí)間的雙重時(shí)間約束,閆俊剛等[99]將導(dǎo)航衛(wèi)星任務(wù)調(diào)度問(wèn)題抽象為帶有雙重VTW 約束的JSP 問(wèn)題.張忠山等[100]在星地建鏈任務(wù)的基礎(chǔ)上還考慮星間建鏈任務(wù),給出了基于任務(wù)排序模型的兩階段式任務(wù)調(diào)度方案.

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

1.4 航天器測(cè)控任務(wù)調(diào)度模型

航天器測(cè)控任務(wù)是航天器遙測(cè)、跟蹤、指令上注等一系列任務(wù)的統(tǒng)稱(chēng),是保障航天器正常運(yùn)行和長(zhǎng)效管控的重要前提.航天器測(cè)控任務(wù)以地基測(cè)控任務(wù)為主,也包含部分天基(基于中繼通信衛(wèi)星的)測(cè)控任務(wù).由圖5 可見(jiàn),與航天器運(yùn)控任務(wù)調(diào)度相似,資源與目標(biāo)的VTW 也是航天器測(cè)控任務(wù)調(diào)度的關(guān)鍵資源,其中低軌目標(biāo)測(cè)控任務(wù)的VTW 長(zhǎng)度通常等于任務(wù)時(shí)長(zhǎng),而高軌目標(biāo)測(cè)控任務(wù)的VTW長(zhǎng)度通常大于任務(wù)時(shí)長(zhǎng).因此,航天器測(cè)控任務(wù)調(diào)度問(wèn)題的研究很大程度上保留了與運(yùn)控任務(wù)調(diào)度相似的問(wèn)題描述方式與建模習(xí)慣,主要采用優(yōu)先級(jí)排序模型、圖論模型和VTW分配模型等進(jìn)行相關(guān)研究.

圖5 航天器測(cè)控任務(wù)調(diào)度示例Fig.5 Illustration of spacecraft tracking mission scheduling

1)優(yōu)先級(jí)排序模型

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

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

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

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

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

此外,還有0-1 背包模型[139]、基于本體與規(guī)則庫(kù)的模型[140-142]、博弈論模型[143-144]、Multi-Agent 模型[145-146]和機(jī)器學(xué)習(xí)模型[147-148]等也被應(yīng)用于航天器測(cè)控任務(wù)調(diào)度的研究中.

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

1.5 小結(jié)

1.5.1 模型共性與區(qū)別

本節(jié)從任務(wù)排序模型和VTW 分配模型兩個(gè)角度梳理了遙感衛(wèi)星、中繼通信衛(wèi)星、導(dǎo)航衛(wèi)星和航天器測(cè)控任務(wù)調(diào)度研究的主要模型,并對(duì)各類(lèi)模型的特點(diǎn)、決策變量形式和優(yōu)缺點(diǎn)進(jìn)行了分析.表1將上述內(nèi)容進(jìn)行了總結(jié),其中,結(jié)合衛(wèi)星型號(hào)項(xiàng)目研發(fā)經(jīng)歷,還梳理了我國(guó)航天器任務(wù)調(diào)度實(shí)際需求中極少被相關(guān)文獻(xiàn)考慮的業(yè)務(wù)約束.這些約束很大程度上限制了航天器任務(wù)調(diào)度最新研究成果的轉(zhuǎn)化和應(yīng)用.因此,如何通過(guò)標(biāo)準(zhǔn)化、模塊化和簡(jiǎn)潔化的方式將這些復(fù)雜的業(yè)務(wù)約束納入航天器任務(wù)調(diào)度模型中,應(yīng)成為未來(lái)研究的重要內(nèi)容之一.

從表1 中不難發(fā)現(xiàn),遙感衛(wèi)星、中繼通信衛(wèi)星、導(dǎo)航衛(wèi)星和航天器測(cè)控任務(wù)調(diào)度研究中的常用模型具有非常大的相似性,其本質(zhì)上是因?yàn)樯鲜龊教炱魅蝿?wù)調(diào)度問(wèn)題的相似性.盡管航天器會(huì)搭載不同的載荷、被賦予不同的任務(wù),但任務(wù)與資源在時(shí)、空、頻域的可見(jiàn)性始終是問(wèn)題建模的出發(fā)點(diǎn)和落腳點(diǎn).以遙感衛(wèi)星為例,調(diào)度模型中主要參數(shù)的實(shí)例化關(guān)系可由圖6 表示,其中資源類(lèi)包含了載荷、平臺(tái)等實(shí)際資源和VTW 等抽象資源,任務(wù)類(lèi)包含了屬性和決策變量等.基于任務(wù)與資源的可見(jiàn)性,任務(wù)類(lèi)中的開(kāi)始時(shí)間可與VTW 直接關(guān)聯(lián),形成貫通模型的信息流,還原航天器任務(wù)調(diào)度問(wèn)題的本來(lái)特點(diǎn).由此,圍繞“任務(wù)-資源”可見(jiàn)性這一共性特征,上述航天器任務(wù)調(diào)度問(wèn)題具有統(tǒng)一化描述與建模的可行性[58].

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

表1 航天器任務(wù)調(diào)度模型研究現(xiàn)狀總結(jié)Table 1 A summary of the studied models for spacecraft mission scheduling

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

1.5.2 不足與對(duì)策

綜上,在分析各類(lèi)航天器任務(wù)調(diào)度模型共性特征與區(qū)別的基礎(chǔ)上,本節(jié)總結(jié)了現(xiàn)有研究存在的三個(gè)方面的不足并給出對(duì)策:

1)不同類(lèi)型的航天器任務(wù)調(diào)度問(wèn)題模型相似卻又不兼容,缺乏統(tǒng)一的建模理論與建模語(yǔ)言.

通過(guò)本節(jié)的分析發(fā)現(xiàn),各類(lèi)航天器任務(wù)調(diào)度模型具有很大的相似性,其圍繞任務(wù)與資源在時(shí)、空、頻域可見(jiàn)性的建模原則是統(tǒng)一的.然而,這些模型又因應(yīng)用場(chǎng)景的約束特點(diǎn)、需求種類(lèi)和求解習(xí)慣等存在一定差異.因此,設(shè)計(jì)通用化、統(tǒng)一化的航天器任務(wù)調(diào)度建模方法與建模語(yǔ)言,是研究航天器通用建模與求解技術(shù),滿(mǎn)足未來(lái)不同類(lèi)型、不同約束和不同體制下航天器綜合管控需求的重要途徑.

2)諸多航天器任務(wù)調(diào)度問(wèn)題簡(jiǎn)化程度高,缺乏部署航天業(yè)務(wù)管控系統(tǒng)的實(shí)際應(yīng)用價(jià)值.

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

3)在模型層面降低航天器任務(wù)調(diào)度問(wèn)題規(guī)模、提升問(wèn)題求解效率的有效機(jī)制沒(méi)有得到重視.

一直以來(lái),調(diào)度算法是航天器任務(wù)調(diào)度問(wèn)題中主要研究的對(duì)象,而調(diào)度模型受到的重視程度遠(yuǎn)遠(yuǎn)不足.實(shí)際上,調(diào)度模型很大程度上決定了調(diào)度算法的編碼形式、鄰域結(jié)構(gòu)、搜索空間等影響優(yōu)化效率的關(guān)鍵因素.因此,在未來(lái)航天器任務(wù)調(diào)度問(wèn)題研究中,設(shè)計(jì)科學(xué)的調(diào)度模型和建模策略,是縮減問(wèn)題規(guī)模、降低算法編碼復(fù)雜度、提升算法求解效率、促進(jìn)模型與算法解耦的必然要求.

2 航天器任務(wù)調(diào)度算法

在航天器任務(wù)調(diào)度模型的基礎(chǔ)上,任務(wù)調(diào)度算法起到模型解算、收益優(yōu)化和方案輸出的作用,是實(shí)例化問(wèn)題模型、決定模型求解質(zhì)量的關(guān)鍵環(huán)節(jié).啟發(fā)式算法、精確求解算法和元啟發(fā)式算法是三類(lèi)常用的調(diào)度算法,在航天器任務(wù)調(diào)度領(lǐng)域得到了諸多應(yīng)用.實(shí)踐表明,這三類(lèi)算法通常具有獨(dú)特的性能優(yōu)勢(shì),例如,啟發(fā)式算法可以快速構(gòu)造高質(zhì)量的初始解,精確求解算法能夠給出特定場(chǎng)景下的最優(yōu)解,元啟發(fā)式算法具有良好的復(fù)雜解空間尋優(yōu)能力以及與前兩種算法的兼容性等.同時(shí),上述算法也往往與航天器任務(wù)調(diào)度的模型緊密相關(guān),存在適用性、可拓展性不足等現(xiàn)實(shí)問(wèn)題,亟待更多的發(fā)展和實(shí)踐的檢驗(yàn).

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

2.1 啟發(fā)式算法

1)優(yōu)先級(jí)排序算法

優(yōu)先級(jí)排序算法是在優(yōu)先級(jí)排序模型的基礎(chǔ)上,基于優(yōu)先級(jí)順序和其他規(guī)則為任務(wù)序列分配資源與時(shí)間的算法.該算法具有通俗易懂、結(jié)構(gòu)簡(jiǎn)單、運(yùn)算速度快等優(yōu)點(diǎn),符合人的主觀經(jīng)驗(yàn),是航天器任務(wù)調(diào)度研究與實(shí)際調(diào)度系統(tǒng)中的常用算法.

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

2)沖突消解算法

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

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

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

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

3)任務(wù)分配算法

任務(wù)分配算法是針對(duì)航天器任務(wù)調(diào)度規(guī)模較大、優(yōu)化效率偏低的問(wèn)題,依據(jù)某種經(jīng)驗(yàn)或規(guī)則對(duì)航天器任務(wù)進(jìn)行預(yù)分配的算法.與沖突消解算法一樣,任務(wù)分配算法通常也作為調(diào)度過(guò)程中的輔助算法.任務(wù)分配算法有助于緩解航天器任務(wù)調(diào)度問(wèn)題中的“組合爆炸”現(xiàn)象,對(duì)縮減任務(wù)調(diào)度解空間、提升優(yōu)化效率有著重要作用.

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

上述啟發(fā)式算法均有效降低了問(wèn)題的決策維度和求解難度,但其應(yīng)用效果很大程度上也取決于算法設(shè)計(jì)的合理程度,且大多與問(wèn)題場(chǎng)景、任務(wù)與資源特征緊耦合,對(duì)問(wèn)題的適應(yīng)性不足.對(duì)此,充分利用航天器任務(wù)調(diào)度場(chǎng)景的特征和經(jīng)驗(yàn),設(shè)計(jì)通用化、自適應(yīng)的啟發(fā)式算法,是解決新常態(tài)下大規(guī)模、復(fù)雜化航天器任務(wù)調(diào)度問(wèn)題的必要途徑.

2.2 精確求解算法

精確求解算法能夠在小規(guī)模的航天器任務(wù)調(diào)度問(wèn)題中求得全局最優(yōu)解,在動(dòng)態(tài)或不確定的環(huán)境中也能保證解的全局最優(yōu)性.雖然精確求解算法一般很難在有限的時(shí)間內(nèi)求解大規(guī)模、復(fù)雜約束的航天器任務(wù)調(diào)度問(wèn)題,但其中諸多思想對(duì)問(wèn)題建模、解空間優(yōu)化等方面也具有指導(dǎo)意義,故本節(jié)簡(jiǎn)要介紹相關(guān)研究中常用的兩種精確求解算法.

1)分支定界算法

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

2)動(dòng)態(tài)規(guī)劃算法

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

2.3 元啟發(fā)式算法

2.3.1 演化算法

演化算法主要指通過(guò)模擬自然界生物種群演化機(jī)理和群體行為,對(duì)組合優(yōu)化問(wèn)題進(jìn)行迭代尋優(yōu)的一類(lèi)元啟發(fā)式算法.演化算法在航天器任務(wù)調(diào)度領(lǐng)域應(yīng)用廣泛,本節(jié)選取遺傳算法、蟻群算法和粒子群算法等三類(lèi)典型的演化算法,對(duì)其在航天器任務(wù)調(diào)度問(wèn)題求解過(guò)程中的模型基礎(chǔ)、編碼方式和改進(jìn)策略等進(jìn)行介紹.

1)遺傳算法

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

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

圖7 遺傳算法求解航天器任務(wù)調(diào)度問(wèn)題編碼示例Fig.7 Illustrations of the GA encoding for spacecraft mission scheduling

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

可見(jiàn),基于任務(wù)排序模型和VTW 分配模型,GA 都能較好地完成解的表示和問(wèn)題求解.不過(guò),受任務(wù)排序模型本身編碼過(guò)程的限制,基于該模型的GA 可能會(huì)在優(yōu)化過(guò)程中丟失優(yōu)質(zhì)解;而基于VTW分配模型的GA 可能出現(xiàn)編碼長(zhǎng)度過(guò)長(zhǎng)、基因表示類(lèi)型過(guò)多的情況,對(duì)算法迭代與搜索效率可能產(chǎn)生一定的影響.因此,合理的航天器任務(wù)調(diào)度模型與編碼方式,以及有針對(duì)性地算法改進(jìn)措施,對(duì)GA求解航天器任務(wù)調(diào)度問(wèn)題起到重要作用.

2)蟻群算法

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

在遙感衛(wèi)星任務(wù)調(diào)度方面,邱滌珊等[182]、耿遠(yuǎn)卓等[183]基于蟻群系統(tǒng)、最大最小螞蟻、動(dòng)態(tài)轉(zhuǎn)移概率等策略求解了遙感衛(wèi)星任務(wù)調(diào)度問(wèn)題;嚴(yán)珍珍等[184]、陳宇寧等[185]在傳統(tǒng)ACO 中引入了知識(shí)學(xué)習(xí)與信息素限制策略;針對(duì)ACO 優(yōu)化周期長(zhǎng)、易陷入局部最優(yōu)的問(wèn)題,朱新新等[186]等基于綜合啟發(fā)信息、沖突消解和擾動(dòng)策略決策任務(wù)序列和VTW.此外,Gao 等[187]、Wu 等[188]在ACO 的框架中引入局部搜索策略,也取得了出色的優(yōu)化效果.

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

ACO 及其改進(jìn)策略在航天器任務(wù)調(diào)度問(wèn)題中得到諸多應(yīng)用,但由于ACO 路徑優(yōu)化的基本思想,相關(guān)研究中的ACO 通常以螞蟻路徑表示衛(wèi)星執(zhí)行任務(wù)的順序,其調(diào)度模型也以任務(wù)排序模型為主.因此,ACO 也會(huì)受解碼策略的影響導(dǎo)致優(yōu)質(zhì)解的丟失,在具有復(fù)雜約束邏輯的任務(wù)調(diào)度場(chǎng)景中可能不利于全局尋優(yōu).

3)粒子群算法

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

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

由于上述算法通常以面向離散優(yōu)化的DPSO為基礎(chǔ),故其調(diào)度模型也以VTW 分配模型為主.不過(guò),PSO 算法本身?yè)碛羞B續(xù)優(yōu)化與離散優(yōu)化的雙重特點(diǎn),過(guò)于側(cè)重離散化的編碼形式可能不利于算法的尋優(yōu).相反,采用離散優(yōu)化(決策VTW)與連續(xù)優(yōu)化(決策任務(wù)開(kāi)始時(shí)間)的編碼方式,可能更適合現(xiàn)階段具有長(zhǎng)VTW 特點(diǎn)的航天器任務(wù)調(diào)度問(wèn)題.

2.3.2 局部搜索算法

局部搜索算法是指從初始解出發(fā),不斷搜索鄰域空間并有選擇地向優(yōu)質(zhì)解移動(dòng)的一類(lèi)元啟發(fā)式算法.現(xiàn)階段航天器任務(wù)調(diào)度研究中常用的局部搜索算法包括禁忌搜索算法和模擬退火算法等.本節(jié)分別對(duì)兩種算法在航天器任務(wù)調(diào)度求解過(guò)程中的模型基礎(chǔ)、鄰域結(jié)構(gòu)和搜索策略等進(jìn)行介紹.

1)禁忌搜索算法

禁忌搜索(Tabu search,TS)算法是由Glover[201-202]于1986 年提出的一種帶有記憶策略的局部搜索算法.TS 算法通過(guò)禁忌表記錄尋優(yōu)過(guò)程中的局部最優(yōu)解或產(chǎn)生局部最優(yōu)解的操作,以避免對(duì)局部最優(yōu)空間的重復(fù)搜索,達(dá)到跳出局部最優(yōu)、開(kāi)辟優(yōu)質(zhì)解空間的效果.TS 算法操作簡(jiǎn)單、實(shí)用性好,是最早用于航天器任務(wù)調(diào)度問(wèn)題求解的算法之一.

在任務(wù)排序模型的基礎(chǔ)上,Cordeau 等[6-7]利用一種求解VRP 問(wèn)題的TS 算法實(shí)現(xiàn)了遙感衛(wèi)星單軌任務(wù)的調(diào)度;賀仁杰等[203]基于JSP 模型設(shè)計(jì)了工件插入、移動(dòng)、交換機(jī)器等鄰域結(jié)構(gòu);左春榮等[204]設(shè)計(jì)了在任務(wù)序列中增減、替換任務(wù)的鄰域結(jié)構(gòu);陳英武等[205]和李菊芳等[206]基于任務(wù)序列設(shè)計(jì)了多種鄰域結(jié)構(gòu),并設(shè)計(jì)了基于變鄰域策略的TS 算法;Bl?chliger 等[111]基于圖著色模型中的顏色選擇設(shè)計(jì)鄰域結(jié)構(gòu),并采用變禁忌長(zhǎng)度的TS 算法求解航天器測(cè)控任務(wù)調(diào)度問(wèn)題.

在VTW 分配模型的基礎(chǔ)上,Xhafa 等[136]通過(guò)對(duì)VTW 和開(kāi)始時(shí)間擾動(dòng)的方式構(gòu)造鄰域;Sarkheyli等[50]設(shè)計(jì)了任務(wù)增減和VTW 內(nèi)沖突消解等鄰域結(jié)構(gòu),并選取任務(wù)與VTW 的匹配關(guān)系作為禁忌對(duì)象;Habet 等[207]設(shè)計(jì)了鄰域評(píng)估機(jī)制,用于提升TS算法在遙感衛(wèi)星任務(wù)調(diào)度過(guò)程中的鄰域搜索效率.此外,禁忌搜索還被用于基于背包模型的航天器任務(wù)調(diào)度問(wèn)題[60]的求解中.

TS 算法表現(xiàn)出良好的問(wèn)題適用性和求解效果,但也由于機(jī)制較為簡(jiǎn)單,近幾年來(lái)應(yīng)用TS 算法直接求解航天器任務(wù)調(diào)度問(wèn)題的研究較少.因此,TS算法應(yīng)與最新的智能優(yōu)化技術(shù)深度融合,才能更好地適應(yīng)復(fù)雜化、多樣化的航天器任務(wù)調(diào)度問(wèn)題.

2)模擬退火算法

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

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

此外,針對(duì)航天器任務(wù)調(diào)度問(wèn)題規(guī)模巨大、易陷入局部最優(yōu)的特點(diǎn),近年來(lái)變鄰域搜索[217]、自適應(yīng)大鄰域搜索[44,56]等局部搜索算法也得到諸多應(yīng)用,取得了出色的優(yōu)化效果.

2.3.3 其他算法

1)模因算法

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

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

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

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

可見(jiàn),MA 實(shí)際上是一種演化算法與局部搜索算法組合的框架.針對(duì)復(fù)雜化、大規(guī)模的航天器任務(wù)調(diào)度需求,相互協(xié)同、取長(zhǎng)補(bǔ)短、優(yōu)勢(shì)互補(bǔ)的算法組合框架對(duì)問(wèn)題求解將起到十分重要的幫助.

2)基于機(jī)器學(xué)習(xí)的決策算法

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

在強(qiáng)化學(xué)習(xí)方面,針對(duì)遙感衛(wèi)星協(xié)同任務(wù)調(diào)度問(wèn)題,王沖等[68-69]分別通過(guò)Q 學(xué)習(xí)算法和進(jìn)化神經(jīng)網(wǎng)絡(luò)算法訓(xùn)練了衛(wèi)星在動(dòng)作集中的選擇策略;Wang等[70]通過(guò)A3C 算法訓(xùn)練了遙感衛(wèi)星任務(wù)調(diào)度決策模型,當(dāng)新任務(wù)達(dá)到時(shí),該模型將決定任務(wù)執(zhí)行與否,并為決定執(zhí)行的任務(wù)分配一個(gè)最長(zhǎng)的VTW,為星上任務(wù)的自主調(diào)度提供了解決方案.

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

2.4 小結(jié)

本節(jié)從啟發(fā)式算法、精確求解算法和元啟發(fā)式算法等三個(gè)角度梳理了航天器任務(wù)調(diào)度研究中的常用算法,并對(duì)各類(lèi)算法的編碼特點(diǎn)、鄰域結(jié)構(gòu)和優(yōu)缺點(diǎn)進(jìn)行了分析.表2 將上述內(nèi)容進(jìn)行了總結(jié).這些算法成功求解了諸多航天器任務(wù)調(diào)度難題,貢獻(xiàn)了重要的理論與實(shí)踐經(jīng)驗(yàn),但與此同時(shí),也存在以下兩點(diǎn)不足:

表2 航天器任務(wù)調(diào)度研究中常用算法總結(jié)Table 2 A summary of commonly used algorithms for spacecraft mission scheduling

1)航天器任務(wù)調(diào)度算法與模型緊耦合,算法設(shè)計(jì)的靈活性不足.

各類(lèi)航天器任務(wù)調(diào)度算法均有其適用的任務(wù)調(diào)度模型,這也是造成現(xiàn)階段航天器任務(wù)調(diào)度模型與算法緊耦合、調(diào)度算法通用性不足的主要原因.因此,結(jié)合航天器任務(wù)調(diào)度模型研究現(xiàn)狀,研究模型與算法解耦、算法靈活可配的航天器任務(wù)調(diào)度架構(gòu)具有重要的實(shí)踐意義.

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

各類(lèi)算法均有不同的優(yōu)缺點(diǎn)和適用性,例如啟發(fā)式算法常用于輔助決策,精確算法求解大規(guī)模問(wèn)題能力有限,演化算法全局尋優(yōu)能力強(qiáng)等.雖然模因算法給出了一種很好的算法協(xié)同思路,但其現(xiàn)階段在求解能力、問(wèn)題適用性等方面仍有提升空間.因此,對(duì)不同類(lèi)型的算法進(jìn)行合理搭配,形成深度協(xié)同、取長(zhǎng)補(bǔ)短、優(yōu)勢(shì)互補(bǔ)的算法組合框架也是求解大規(guī)模、復(fù)雜化航天器任務(wù)調(diào)度問(wèn)題的必要途徑.

3 航天器任務(wù)調(diào)度通用求解技術(shù)

航天器任務(wù)調(diào)度通用求解技術(shù)是指可以針對(duì)不同類(lèi)型的航天器任務(wù)建立通用化的任務(wù)調(diào)度模型,或采用不同任務(wù)調(diào)度算法進(jìn)行模型解算的通用求解器、工具箱、算法包等.航天器任務(wù)調(diào)度通用求解技術(shù)可以解決不同場(chǎng)景下的航天器任務(wù)調(diào)度、異構(gòu)多航天器協(xié)同任務(wù)調(diào)度等現(xiàn)實(shí)問(wèn)題,方便地調(diào)用多樣化、可拓展的調(diào)度算法,為從業(yè)人員提供便捷、豐富且有效的問(wèn)題建模與求解手段.因此,航天器任務(wù)調(diào)度通用求解技術(shù)對(duì)提升航天器綜合管控自動(dòng)化、智能化和一體化水平起到重要作用,是衡量一個(gè)國(guó)家航天綜合實(shí)力的重要標(biāo)準(zhǔn),也是航天部門(mén)亟需發(fā)展的關(guān)鍵技術(shù).

目前,具有通用建模與求解特色的航天器任務(wù)調(diào)度工具有CPLEX、STK/Scheduler、Europa2 和我國(guó)商業(yè)遙感衛(wèi)星“高景一號(hào)”任務(wù)調(diào)度分系統(tǒng)等.本節(jié)對(duì)上述四種通用求解技術(shù)的建模特色、求解算法和主要功能進(jìn)行梳理,總結(jié)上述通用求解技術(shù)的優(yōu)缺點(diǎn),結(jié)合航天綜合管控的發(fā)展現(xiàn)狀,指出我國(guó)自主研發(fā)航天器任務(wù)調(diào)度通用求解器的必要性和新的應(yīng)用思路,為航天器任務(wù)調(diào)度通用求解工具的研究與設(shè)計(jì)提供參考.

3.1 數(shù)學(xué)規(guī)劃求解器CPLEX

CPLEX 是美國(guó)IBM 公司開(kāi)發(fā)的一款數(shù)學(xué)規(guī)劃求解器,適用于線性規(guī)劃、二次規(guī)劃等問(wèn)題[222].在建模語(yǔ)言方面,CPLEX 語(yǔ)言簡(jiǎn)潔易懂,并可以與C++、Java 和Python 等主流編程語(yǔ)言兼容;在求解質(zhì)量方面,CPLEX 內(nèi)置了單純形、分支定界等一系列精確求解算法,可以給出問(wèn)題的最優(yōu)解,保持了一系列經(jīng)典運(yùn)籌學(xué)Benchmark 中的最優(yōu)記錄,因此也被應(yīng)用于航天器任務(wù)調(diào)度問(wèn)題的求解中.

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

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

上述研究表明,雖然CPLEX 在求解小規(guī)模航天器任務(wù)調(diào)度問(wèn)題、不確定性任務(wù)調(diào)度問(wèn)題和問(wèn)題邊界等方面表現(xiàn)出色,但在求解大規(guī)模任務(wù)調(diào)度問(wèn)題的時(shí)候效率低下,且無(wú)法準(zhǔn)確描述非線性的約束條件和收益.因此,在現(xiàn)階段任務(wù)規(guī)模不斷增長(zhǎng)的情況下,CPLEX 很難滿(mǎn)足航天管控部門(mén)對(duì)任務(wù)調(diào)度質(zhì)量與速率的雙重需要,很難在實(shí)際的航天業(yè)務(wù)調(diào)度系統(tǒng)中投入使用.

3.2 通用衛(wèi)星調(diào)度軟件STK/Scheduler

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

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

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

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

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

2)缺乏對(duì)任務(wù)、資源、收益或約束條件的動(dòng)態(tài)調(diào)整功能,常用于靜態(tài)的航天器任務(wù)調(diào)度問(wèn)題;

3)主要功能最后更新于2006 年,沒(méi)有包含進(jìn)化算法、禁忌搜索等現(xiàn)階段主流的智能優(yōu)化算法,對(duì)規(guī)則的依賴(lài)性較大.隨著近年來(lái)航天器任務(wù)調(diào)度問(wèn)題規(guī)模與復(fù)雜性的不斷提升,其內(nèi)置算法的求解效果可能不佳.

另一方面,2013 年,Herz 等[231]在航天器測(cè)控任務(wù)調(diào)度的問(wèn)題中使用了STK/Scheduler Online,通過(guò)互聯(lián)網(wǎng)訪問(wèn)了STK/Scheduler 服務(wù)器,完成了場(chǎng)景建模、參數(shù)配置、優(yōu)化調(diào)度等一系列功能.這種遠(yuǎn)程式的任務(wù)調(diào)度方式使得用戶(hù)的訪問(wèn)便捷、高效,有助于服務(wù)功能的迭代更新和故障的快速修復(fù),在高性能服務(wù)器的支持下也有助于調(diào)度效率的提升.因此,STK/Scheduler Online 也為航天器任務(wù)調(diào)度系統(tǒng)的設(shè)計(jì)與部署提供了一種新思路.

3.3 航天器任務(wù)規(guī)劃軟件Europa2

Europa2 (2nd generation of extensible universal remote operations architecture)是NASA開(kāi)發(fā)的面向航天器任務(wù)規(guī)劃的第二代可擴(kuò)展式通用遠(yuǎn)程操作體系結(jié)構(gòu)[232],已在NASA 哈勃空間望遠(yuǎn)鏡[233]、DS-1 自主衛(wèi)星[234]等項(xiàng)目中得到應(yīng)用.與規(guī)劃領(lǐng)域經(jīng)典語(yǔ)言PDDL (Planning domain description language)不同,Europa2 所基于的NDDL(New domain description language)是一種基于狀態(tài)變量、面向?qū)ο笈c聲明性的語(yǔ)言,故Europa2中主要通過(guò)定義標(biāo)記、事務(wù)、對(duì)象、類(lèi)、時(shí)間線和規(guī)劃解等完成對(duì)一類(lèi)航天器任務(wù)場(chǎng)景的描述,并通過(guò)約束傳播等約束規(guī)劃技術(shù)給出一個(gè)可行的方案[235-238].

基于狀態(tài)變量的特點(diǎn),Europa2 主要面向航天器任務(wù)規(guī)劃問(wèn)題,如航天器執(zhí)行任務(wù)的動(dòng)作邏輯、狀態(tài)轉(zhuǎn)移等.該問(wèn)題主要描述航天器任務(wù)的邏輯關(guān)系,給出滿(mǎn)足約束的可行方案,對(duì)資源調(diào)度的需求較少.而本文所探討的任務(wù)調(diào)度問(wèn)題主要解決任務(wù)資源與時(shí)間的分配,例如執(zhí)行任務(wù)的VTW、航天器及其電量、固存等載荷資源等.故針對(duì)航天器任務(wù)調(diào)度問(wèn)題,Europa2 存在以下不足:

1)缺乏收益函數(shù)和調(diào)度優(yōu)化機(jī)制,Europa2 通過(guò)約束規(guī)劃等方法給出可行的航天器動(dòng)作序列,但無(wú)法在收益函數(shù)的驅(qū)動(dòng)下迭代地給出更優(yōu)的調(diào)度方案;

2)基于約束傳播的約束規(guī)劃算法只能適用于小規(guī)模的任務(wù)場(chǎng)景,例如單星單軌20 個(gè)任務(wù)的規(guī)劃時(shí)間已非常長(zhǎng),且最新版本Europa2.6 發(fā)布于2011 年[232],已很難適應(yīng)現(xiàn)階段大規(guī)模、復(fù)雜化的航天器管控新常態(tài).

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

3.4 “高景一號(hào)”任務(wù)調(diào)度分系統(tǒng)

“高景一號(hào)”是我國(guó)首個(gè)商用敏捷遙感星座,目前由4 顆位于太陽(yáng)同步軌道的0.5 米分辨率光學(xué)成像衛(wèi)星構(gòu)成,每顆衛(wèi)星的軌道周期約為97 分鐘.按照相關(guān)計(jì)劃,還將陸續(xù)發(fā)射20 余顆敏捷遙感衛(wèi)星,與現(xiàn)有的4 顆衛(wèi)星組建新的“高景一號(hào)”星座網(wǎng)絡(luò).鑒于“高景一號(hào)”星座的商業(yè)化運(yùn)營(yíng)模式和不斷增加的衛(wèi)星數(shù)量,如何充分調(diào)度衛(wèi)星任務(wù)、最大化經(jīng)濟(jì)收益是“高景一號(hào)”運(yùn)控部門(mén)迫切關(guān)心的問(wèn)題.

目前,“高景一號(hào)”任務(wù)調(diào)度分系統(tǒng)采用的調(diào)度模型之一為任務(wù)排序模型,并基于成像質(zhì)量最高原則(即在VTW 中點(diǎn)處執(zhí)行任務(wù))對(duì)任務(wù)序列進(jìn)行解碼.由于在模型解碼過(guò)程中會(huì)對(duì)任務(wù)序列進(jìn)行約束檢查,解碼后均為可行方案.因此,該調(diào)度模型的通用性也較強(qiáng),在此過(guò)程中復(fù)雜任務(wù)約束也均能得到處理.

在任務(wù)排序模型的基礎(chǔ)上,“高景一號(hào)”任務(wù)調(diào)度分系統(tǒng)所采用的調(diào)度算法主要為任務(wù)分配算法和優(yōu)先級(jí)排序算法.例如,基于任務(wù)收益、持續(xù)時(shí)間、窗口數(shù)量等一系列任務(wù)與資源屬性,定義任務(wù)的綜合優(yōu)先級(jí),并基于優(yōu)先級(jí)降序構(gòu)建單星任務(wù)序列、依次分配資源.由于機(jī)制簡(jiǎn)單,“高景一號(hào)”任務(wù)調(diào)度分系統(tǒng)能夠較快地給出單星任務(wù)調(diào)度結(jié)果,但也暴露出任務(wù)調(diào)度效果不佳、衛(wèi)星缺乏協(xié)同、資源利用不充分等問(wèn)題.

另一方面,當(dāng)通過(guò)人工調(diào)整的方式對(duì)任務(wù)排序結(jié)果進(jìn)行進(jìn)一步優(yōu)化時(shí),仍需重新進(jìn)行解碼與約束檢查工作.由于人工調(diào)整的結(jié)果并不能得到實(shí)時(shí)反饋,故人工調(diào)整的方式存在一定的盲目性,即可能出現(xiàn)人工調(diào)整結(jié)果不及原方案的情況.由此,該模型與算法雖然能夠處理復(fù)雜的衛(wèi)星業(yè)務(wù)約束,但任務(wù)調(diào)度效率和快速響應(yīng)能力仍有待提高.

3.5 小結(jié)

本節(jié)梳理了CPLEX、STK/Scheduler、Europa2和“高景一號(hào)”任務(wù)調(diào)度分系統(tǒng)的基本原理、適用性和優(yōu)缺點(diǎn),表3 對(duì)本節(jié)內(nèi)容進(jìn)行了總結(jié).通過(guò)本節(jié)的綜述與分析可知:

表3 用于航天任務(wù)調(diào)度的通用求解器總結(jié)Table 3 A summary of the general techniques for spacecraft mission scheduling

1)現(xiàn)階段尚無(wú)能夠滿(mǎn)足航天器任務(wù)調(diào)度需求的通用求解器.

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

2)我國(guó)需要研發(fā)具有自主知識(shí)產(chǎn)權(quán)的航天器任務(wù)調(diào)度通用求解技術(shù).

綜合考慮約束描述能力、求解效果、版權(quán)與服務(wù)支持等因素,CPLEX、STK/Scheduler、Europa2并未在我國(guó)航天系統(tǒng)中得到應(yīng)用.或許STK/Scheduler和Europa2 等航天器任務(wù)調(diào)度通用求解器已有融合先進(jìn)技術(shù)的新版本,但并未對(duì)外公布.因此,我國(guó)需要研發(fā)適合我國(guó)國(guó)情、具有自主知識(shí)產(chǎn)權(quán)的航天器任務(wù)調(diào)度通用求解技術(shù),在核心技術(shù)上掌握主動(dòng)權(quán),為提升我國(guó)航天綜合管控實(shí)力提供技術(shù)支撐.

3)基于云平臺(tái)的遠(yuǎn)程航天器任務(wù)調(diào)度服務(wù)是一種新的應(yīng)用思路.

STK/Scheduler Online 提供了一種在線式的航天器任務(wù)調(diào)度服務(wù)新模式.該模式使用戶(hù)訪問(wèn)更加便捷、高效,有助于服務(wù)功能的迭代更新和故障的快速修復(fù),在高性能服務(wù)器的支持下也能提升任務(wù)調(diào)度的效率.因此,結(jié)合現(xiàn)階段云計(jì)算的技術(shù)優(yōu)勢(shì),向航天部門(mén)提供遠(yuǎn)程的任務(wù)調(diào)度服務(wù)是一種新穎、高效的應(yīng)用思路.

4 結(jié)束語(yǔ)

航天器任務(wù)調(diào)度是航天器管控的重要內(nèi)容,是發(fā)揮航天系統(tǒng)社會(huì)經(jīng)濟(jì)效益、實(shí)現(xiàn)航天器使命價(jià)值的重要保障.隨著航天事業(yè)的快速發(fā)展,作為調(diào)度技術(shù)的兩大要素,航天器任務(wù)調(diào)度模型與調(diào)度算法已得到廣泛研究,并在各大航天調(diào)度系統(tǒng)中得以檢驗(yàn).在此過(guò)程中,涌現(xiàn)出一批優(yōu)秀的調(diào)度模型、算法和通用求解技術(shù),為航天器任務(wù)調(diào)度研究貢獻(xiàn)了重要的理論體系與實(shí)踐經(jīng)驗(yàn).本文系統(tǒng)地梳理了近年來(lái)航天器任務(wù)調(diào)度研究中的模型、算法與通用求解技術(shù),總結(jié)了相關(guān)技術(shù)中的共性特征與區(qū)別,為未來(lái)航天器任務(wù)調(diào)度的研究工作提供了參考.

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

然而,通過(guò)本文的綜述也發(fā)現(xiàn),現(xiàn)階段航天器任務(wù)調(diào)度研究暴露出“模型-問(wèn)題-算法”緊耦合的弊端,模型與算法的兼容性與可拓展性不足,難以適應(yīng)航天系統(tǒng)靈活組網(wǎng)、快速響應(yīng)的新常態(tài).由此,本文指出以下幾點(diǎn)未來(lái)航天器任務(wù)調(diào)度研究的新方向:

1)研究航天器任務(wù)調(diào)度統(tǒng)一化建模語(yǔ)言.

航天器任務(wù)調(diào)度統(tǒng)一化建模語(yǔ)言是解決航天器任務(wù)調(diào)度模型兼容性問(wèn)題的根本途徑.通過(guò)本文綜述發(fā)現(xiàn),諸多航天器任務(wù)調(diào)度模型具有很大的相似性,其圍繞任務(wù)與資源在時(shí)、空、頻域可見(jiàn)性的建模原則是統(tǒng)一的.現(xiàn)階段已有幾款成熟的統(tǒng)一化建模語(yǔ)言,但這些語(yǔ)言缺乏航天領(lǐng)域和組合優(yōu)化領(lǐng)域的應(yīng)用特色.由此,研究統(tǒng)一化且具備領(lǐng)域特色的航天器任務(wù)調(diào)度建模語(yǔ)言,是發(fā)展航天器通用建模與求解技術(shù),滿(mǎn)足未來(lái)航天器靈活管控需要的內(nèi)在要求.

2)研究航天系統(tǒng)管控體制下有效應(yīng)對(duì)大規(guī)模任務(wù)調(diào)度問(wèn)題的解空間優(yōu)化技術(shù).

隨著航天器規(guī)模持續(xù)增加以及航天系統(tǒng)組網(wǎng)的常態(tài)化發(fā)展,解空間規(guī)模已成為限制航天器任務(wù)調(diào)度效率的關(guān)鍵因素.目前,任務(wù)分配、分層規(guī)劃等方法可將大規(guī)模航天器任務(wù)調(diào)度問(wèn)題分解為諸多子問(wèn)題,雖然提升了調(diào)度效率,但也違背了航天系統(tǒng)綜合管控、一體化調(diào)度的發(fā)展趨勢(shì),丟失了問(wèn)題的全局優(yōu)化特點(diǎn).近年來(lái),深度學(xué)習(xí)、強(qiáng)化學(xué)習(xí)等技術(shù)發(fā)展迅速,并在旅行商、車(chē)輛路徑規(guī)劃等經(jīng)典組合優(yōu)化問(wèn)題中得到了成功應(yīng)用.基于機(jī)器學(xué)習(xí)的技術(shù)優(yōu)勢(shì),可以研究航天器任務(wù)調(diào)度解空間優(yōu)化技術(shù),在保留全局性?xún)?yōu)化特點(diǎn)的基礎(chǔ)上,實(shí)現(xiàn)大規(guī)模任務(wù)調(diào)度解空間規(guī)模的精準(zhǔn)縮減,以滿(mǎn)足航天系統(tǒng)綜合管控與快速響應(yīng)的雙重需求.

3)共同打造航天器任務(wù)調(diào)度算法庫(kù)與測(cè)試集.

以往,調(diào)度模型兼容性不足是限制航天器任務(wù)調(diào)度算法通用化發(fā)展的主要原因,而上述航天器統(tǒng)一化建模語(yǔ)言可以解決這一問(wèn)題.以后,航天器任務(wù)調(diào)度算法不再局限于某一特定的航天應(yīng)用場(chǎng)景,而將適用于更多的具有普遍意義的航天器任務(wù)調(diào)度問(wèn)題.鑒于此,打造一個(gè)開(kāi)源的、持續(xù)更新的航天器任務(wù)調(diào)度算法庫(kù),有助于營(yíng)造世界范圍內(nèi)相關(guān)學(xué)者及業(yè)務(wù)人員共研共享的發(fā)展環(huán)境.同時(shí),為檢驗(yàn)算法性能、促進(jìn)良性競(jìng)爭(zhēng),打造兼具算法測(cè)試、教學(xué)、新案例發(fā)布等功能的航天器任務(wù)調(diào)度標(biāo)準(zhǔn)測(cè)試集也具有十分重要的意義.

4)研發(fā)具有自主知識(shí)產(chǎn)權(quán)的航天器任務(wù)調(diào)度通用求解技術(shù).

在上述研究方向的基礎(chǔ)上,研發(fā)適合我國(guó)國(guó)情、具有自主知識(shí)產(chǎn)權(quán)、滿(mǎn)足國(guó)家航天戰(zhàn)略發(fā)展需要的航天器任務(wù)調(diào)度通用求解技術(shù)勢(shì)在必行.通用求解技術(shù)的研發(fā)是實(shí)現(xiàn)我國(guó)在軌航天器綜合管控、靈活組網(wǎng)這一目標(biāo)的出發(fā)點(diǎn)和落腳點(diǎn).未來(lái),在通用求解技術(shù)的支撐下,資源衛(wèi)星、商業(yè)衛(wèi)星、偵察衛(wèi)星、導(dǎo)航衛(wèi)星、中繼衛(wèi)星、空間站與地面站網(wǎng)等不同類(lèi)型、隸屬不同部門(mén)的航天任務(wù)資源將密切聯(lián)動(dòng),更大限度地發(fā)揮我國(guó)航天系統(tǒng)的社會(huì)經(jīng)濟(jì)效益.