摘 要：傳統(tǒng)的集中式任務(wù)規(guī)劃模式靈活性低、對中心節(jié)點的計算能力要求高，難以滿足快速增長的觀測需求。針對此問題，提出了一種分布式衛(wèi)星任務(wù)規(guī)劃方法。針對多星分布式任務(wù)規(guī)劃問題，考慮合同網(wǎng)中招標(biāo)者和投標(biāo)者的目標(biāo)差異，分別建立全局分配模型和局部規(guī)劃模型；改進合同網(wǎng)協(xié)議，提出了多任務(wù)集中招標(biāo)策略和任務(wù)組中標(biāo)策略，并改進了評標(biāo)策略以對重復(fù)規(guī)劃任務(wù)進行合理分配；設(shè)計了基于改進遺傳的修正合同網(wǎng)算法（Ｍｏｄｉｆｉｅｄ Ｃｏｎｔｒａｃｔ Ｎｅｔｗｏｒｋ ＡｌｇｏｒｉｔｈｍＢａｓｅｄ ｏｎ Ｉｍｐｒｏｖｅｄ Ｇｅｎｅｔｉｃｓ，ＭＣＮＡＩＧ） 用于求解問題；通過與Ｃｐｌｅｘ 和集中式任務(wù)規(guī)劃算法（Ｃｅｎｔｒａｌｉｚｅｄ Ｍｉｓｓｉｏｎ ＰｌａｎｎｉｎｇＡｌｇｏｒｉｔｈｍ，ＣＭＰＡ） 對比驗證了算法在觀測收益率和規(guī)劃耗時上的有效性。從任務(wù)完成率、觀測收益率以及協(xié)商次數(shù)３ 個指標(biāo)驗證了改進合同網(wǎng)算法的合理性；在３ 種不同場景下驗證了算法的穩(wěn)定性。實驗結(jié)果表明，算法適用于多星分布式任務(wù)規(guī)劃問題。

關(guān)鍵詞：任務(wù)規(guī)劃；分布式衛(wèi)星；多星任務(wù)規(guī)劃；合同網(wǎng)

中圖分類號：Ｖ５７ 文獻標(biāo)志碼：Ａ

文章編號：１００３－３１０６（２０２４）１０－２４３４－１２

０ 引言

對地觀測衛(wèi)星通過使用光學(xué)傳感器捕獲地面圖像，以滿足用戶的觀測需求，已廣泛應(yīng)用于國防、資源勘探、災(zāi)害監(jiān)測和氣象預(yù)測等領(lǐng)域［１－２］。衛(wèi)星任務(wù)規(guī)劃作為對地觀測衛(wèi)星指揮控制中的關(guān)鍵技術(shù)，已成為一個重要研究方向。衛(wèi)星任務(wù)規(guī)劃問題是一個ＮＰＨａｒｄ 問題，即在滿足衛(wèi)星資源與任務(wù)之間的各類約束的基礎(chǔ)上，給出衛(wèi)星對任務(wù)的觀測序列以及各任務(wù)的觀測時間，使得目標(biāo)函數(shù)盡可能的大（或?。郏常荨?/p>

目前，衛(wèi)星任務(wù)規(guī)劃模式主要分為集中式和分布式２ 種基本任務(wù)規(guī)劃模式。然而，現(xiàn)有研究大多采用了集中式任務(wù)規(guī)劃模式。傳統(tǒng)的集中式任務(wù)規(guī)劃過程由地面管控中心完成，高度依賴地面系統(tǒng)的命令，而地面站與衛(wèi)星之間的通信時間有限［４－５］，難以滿足衛(wèi)星任務(wù)規(guī)劃的時效性需求。隨著衛(wèi)星的載荷計算能力不斷提升，星上處理能力不斷增強，從而可以減少對地面站的依賴，實現(xiàn)衛(wèi)星任務(wù)規(guī)劃的自主化［６－８］。文獻［９ －１０］采用分支定界算法解決衛(wèi)星任務(wù)規(guī)劃問題。精確算法一般用于求解小規(guī)模問題，難以在有限時間內(nèi)實現(xiàn)大規(guī)模問題的求解。因此，啟發(fā)式算法被廣泛應(yīng)用于解決大規(guī)模問題。文獻［１１］提出了一種基于優(yōu)先規(guī)則的啟發(fā)式算法，能夠快速生成規(guī)劃方案。文獻［１２－１３］設(shè)計了混合動態(tài)變異遺傳算法，并提出了２ 種重規(guī)劃技術(shù)以滿足不同的任務(wù)需求。盡管集中式任務(wù)規(guī)劃模式能利用全局信息得到高質(zhì)量的規(guī)劃方案，但是其對規(guī)劃中心節(jié)點的計算能力要求高，且靈活性低。

與集中式任務(wù)規(guī)劃模式相比，分布式任務(wù)規(guī)劃模式更加靈活，具有可靠性高、容錯性好、可重構(gòu)、計算效率高等優(yōu)點［１４－１５］。分布式任務(wù)規(guī)劃模式中的關(guān)鍵問題是如何進行星間協(xié)商以完成任務(wù)規(guī)劃。合同網(wǎng)協(xié)議是一種經(jīng)典協(xié)商機制［１６］，在分布式系統(tǒng)的任務(wù)分配和調(diào)度中具有廣泛的應(yīng)用。文獻［１７］提出了一種包含任務(wù)預(yù)規(guī)劃和任務(wù)重規(guī)劃的兩階段任務(wù)規(guī)劃方法，并將合同網(wǎng)協(xié)議用于任務(wù)重規(guī)劃階段。文獻［１８－１９］將合同網(wǎng)協(xié)議用于解決多星分布式任務(wù)規(guī)劃問題，但已中標(biāo)任務(wù)的時間窗不可搶占，難以充分利用衛(wèi)星資源。文獻［２０］引入了外包機制以優(yōu)化已有規(guī)劃方案，提高了衛(wèi)星資源的利用率。文獻［２１ － ２２］采用買賣合同、交換合同及置換合同３ 種類型合同進行多星任務(wù)分配。文獻［２３］提出了一種多維多智能體協(xié)作模型，采用任務(wù)聚類進行預(yù)處理，并提出了基于合同網(wǎng)協(xié)議的二次分配策略以提高觀測收益。文獻［２４］將多星分布式任務(wù)規(guī)劃問題轉(zhuǎn)化為集覆蓋問題，提出了基于合同網(wǎng)的嚴(yán)格啟發(fā)式優(yōu)化算法，但該算法只適用于中小規(guī)模的情形。上述研究將合同網(wǎng)協(xié)議引入多星分布式任務(wù)規(guī)劃問題，并進行改進，但仍然存在一些不足：① “單任務(wù)招標(biāo)，單代理中標(biāo)”模式下每輪協(xié)商僅分配一個任務(wù)且只有一個代理中標(biāo)，造成協(xié)商效率低下、未中標(biāo)代理計算資源浪費、大規(guī)模任務(wù)場景下通信量巨大等問題［２５］；② 都只建立一個全局模型，忽略了單星局部規(guī)劃目標(biāo)與全局規(guī)劃目標(biāo)可能存在差異；③ 大多仍遵循傳統(tǒng)合同網(wǎng)中已規(guī)劃任務(wù)不可調(diào)整的規(guī)定，后續(xù)招標(biāo)任務(wù)可能與已規(guī)劃任務(wù)存在時間窗沖突而無法規(guī)劃，難以充分利用衛(wèi)星的時間窗資源。

綜合上述分析，針對多星分布式任務(wù)規(guī)劃問題，本文首先建立全局分配模型和局部規(guī)劃模型，全局分配模型的目標(biāo)是完成多個從星之間重復(fù)規(guī)劃任務(wù)的分配，局部規(guī)劃模型的目標(biāo)則是實現(xiàn)從星局部目標(biāo)最優(yōu)。其次，對傳統(tǒng)合同網(wǎng)協(xié)議進行改進，提出了多任務(wù)集中招標(biāo)策略和任務(wù)組中標(biāo)策略，提高星間協(xié)商效率、避免計算資源浪費；允許從星在生成投標(biāo)方案時對已規(guī)劃任務(wù)進行調(diào)整以充分利用衛(wèi)星資源；基于任務(wù)組中標(biāo)策略將沖突消解引入評標(biāo)過程中。然后，設(shè)計了基于改進遺傳的修正合同網(wǎng)算法（Ｍｏｄｉｆｉｅｄ Ｃｏｎｔｒａｃｔ Ｎｅｔｗｏｒｋ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｉｍｐｒｏｖｅｄ Ｇｅｎｅｔｉｃｓ，ＭＣＮＡＩＧ）用于多星分布式任務(wù)規(guī)劃。最后，進行了仿真驗證，實驗結(jié)果表明ＭＣＮＡＩＧ 是有效的。

１ 問題描述

多星分布式任務(wù)規(guī)劃是指在滿足在軌狀態(tài)和任務(wù)相關(guān)約束的條件下，各星根據(jù)自身的能力獨立地進行規(guī)劃以生成局部規(guī)劃方案，并通過協(xié)商調(diào)整局部規(guī)劃方案，最終通過協(xié)作生成全局規(guī)劃方案?；诤贤W(wǎng)協(xié)議的多星分布式任務(wù)規(guī)劃過程如圖１ 所示，當(dāng)一批待觀測任務(wù)到達時，分布式衛(wèi)星系統(tǒng)內(nèi)采用合同網(wǎng)協(xié)議進行星間協(xié)商，接收到待觀測任務(wù)的衛(wèi)星作為主星，充當(dāng)招標(biāo)者，系統(tǒng)內(nèi)的其他衛(wèi)星作為從星對主星的招標(biāo)進行響應(yīng)，充當(dāng)投標(biāo)者。由主星向從星廣播待觀測任務(wù)信息發(fā)起招標(biāo)，從星利用收到的招標(biāo)任務(wù)信息獨立地進行局部規(guī)劃，生成各自的投標(biāo)方案，并向主星發(fā)送投標(biāo)方案，主星根據(jù)評標(biāo)策略確定中標(biāo)方案返還給各從星。最終經(jīng)過多輪協(xié)商使得多星分布式任務(wù)規(guī)劃問題得到解決。