基于改進合同網協議的多星分布式任務規劃

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

關鍵詞：任務規劃；分布式衛星；多星任務規劃；合同網

中圖分類號：Ｖ５７ 文獻標志碼：Ａ

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

０ 引言

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

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

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

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

１ 問題描述

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