基于分布式協同進化的星座自主任務規劃算法

高天旸, 胡笑旋, 夏 維

(1. 合肥工業大學管理學院, 安徽 合肥 230009; 2. 過程優化與智能決策教育部重點實驗室, 安徽 合肥 230009)

0 引 言

對地觀測衛星,即遙感衛星,是一種廣泛應用于地面勘探、環境監測、氣象預測、軍事偵查等重要領域的戰略資源。在傳統遙感衛星系統應用過程中,衛星任務規劃通常在地面進行,在應對突發需求時制定的新方案往往需要等待下一次衛星過境測控站才能上注執行,這極大地限制了遙感衛星系統的響應速度[1-2]。隨著星載計算能力的提升,衛星任務規劃自主化成為了可能,自主化即減弱衛星運行對地面系統的依賴,將任務規劃運算交由星載芯片進行,能一定程度擺脫測控可見性的限制[3-4]。當前,遙感衛星系統不斷由多星向星群、星座發展,其星間協作關系愈加密切,星座協同自主任務規劃逐漸成為自主化衛星管理與控制方法的主要發展方向[5]。

星座協同自主任務規劃旨在為不同物理結構的星座系統設計采用不同組織結構的協同策略與相應的優化算法,從而令星座內各星互相協同合作以共同制訂整體任務執行方案。自主協同星座的組織結構主要可分為全集中式、集中協調式、并行集中式(部分分布式)與全分布式4類,其中前三者可以被歸納為層級化結構[6]。文獻[7-8]面向主從結構星座系統,設計了一種全集中式混合動態變異遺傳算法與兩種重規劃方法,其方案由主星規劃形成并分發至各從星執行。文獻[9]提出了一種集中協調式規劃策略,先由主星將任務信息廣播至各從星,各從星評估自身觀測能力與成本形成報告返還主星,最終由主星選定各任務執行星。文獻[10]提出了一種多維多智能體協作模型,主星使用基于合同網協議的分配方法,通過公告、招標、授予等步驟對各從星進行任務分配與重分配。在層級化結構中,各星被分為主星與從星兩種角色,主星負責對系統進行統籌規劃并主持星間協調過程,從星被動地接收來自主星的籌劃結果、進行自我方案規劃并參與協調過程。采用層級化結構的方法具有清晰的規劃流程,能快速形成有效方案,但由于其流程圍繞主星節點開展,對其的計算能力與通信環境的要求較高,因此主要應用于擁有高算力節點或穩定通信總線的星座系統。

在采用層級化結構的自主星座中,當主星遭遇意外而失效時,整個系統將陷入癱瘓,而采用全分布式結構則可避免此類問題。文獻[11-12]將主星損壞后星座內剩余各從星看作多個互相通信與協商的獨立智能體,并分別對其效用函數進行識別,提出了基于效用的后悔博弈、煙霧信號博弈和基于廣播的博弈作為分布式協商策略,并改進混合動態變異遺傳算法以使其適用于分布式優化環境。文獻[13]設計了一種多星智能體協調協商任務分配算法,率先收到任務信息的衛星向其所有鄰近星廣播以構成群組,群組內各星首先評估自身對各任務的執行意向,隨后共同進入一種基于最大增益信息算法的分布式協調迭代優化過程以形成最終分配方案。文獻[14-15]提出了一種基于任務聯盟構建的星間協作方法,各星智能體通過基于信任度的知識傳播策略以不斷傳遞已知任務信息與他星執行意向信息,并據此改進自身意向以優化整體任務分配方案。在全分布式結構中,各星作為平等個體共同參與協調優化過程,通過積極的通信交互以對任務分配進行協調并生成相應的執行方案。采用全分布式結構的方法可利用不同星間的通信能力組成信息網絡以支持其協調過程,從而使各星承擔的通信與計算壓力更加平均,適用于不具備強算力節點或星間通信能力不穩定的星座系統。

基于上述分析,本文進一步探究全分布式結構方法對各星計算資源的運用方式,提出了一種全分布式星座協同迭代優化策略,將制定多星整體方案的總問題轉換為多個制訂單星方案的分問題。在該策略中,各星被看作為獨立智能體,通過“接收”“更新”“發布”的三階段協作行為在相應分問題解空間中探索總問題的優質解。在此基礎上,本文設計了一種分布式多智能體合作式協同進化遺傳算法,該算法對不同衛星方案進行編碼形成多個亞種群,利用不同自主衛星的計算資源實現各亞種群并行進化,并通過各亞種群特征信息的傳播與接受過程來協調任務在各星間的分配。同時,設計了一種包含時間窗間重疊度因素與自適應機制的適應度函數,能夠有效引導各亞種群共同朝著提升整體方案質量的方向進化,進一步增強算法的尋優能力。最后,本文在S698PM嵌入式開發環境下進行仿真實驗,結果表明,所提出方法在小規模問題中能求得與CPLEX效果相當的優質解,在大規模問題中表現出比貪婪算法與集中式遺傳算法更強的優化能力,同時在惡劣通信環境下展現出良好的適應性,適用于不同拓撲結構的星座系統。

1 問題描述

在一個由多顆自主遙感衛星組成的星座系統中,各星除了基本的觀測與通信能力外,還都擁有一定的星載算力,且具有計算任務目標訪問時間窗的功能。如圖1所示,當一批待觀測任務集合信息以地面上注或星上自生成等方式到達星座中任一衛星,該星作為規劃發起星,需要調動星座內的其他衛星與其共同針對該任務集合進行分配與規劃,以求整體方案中的被執行的任務權重的總和最大。該任務集合中包含一定數量的地面點目標,對其中任一目標的觀測都需要占用一顆遙感衛星的一段工作時間,且執行時間段必須在該衛星對目標的可見時間窗內。

1.1 概念定義

(1) 任務:T={t1,t2,…,ti,…,tNT}表示一批剛到達的待規劃任務集合,NT為集合中任務的數量,其中每一個任務ti可以通過一個二元組ti=(tvi,di)表示,i為任務序號,tvi表示該任務的權重,di表示該任務所需觀測持續時間。

(2) 衛星:S={s1,s2,…,sj,…,sNS}表示星座系統中所有衛星的集合,NS為集合中衛星的數量。

1.2 多星任務規劃問題模型

根據上述定義對星座內的多星任務規劃問題進行建模,可得模型如下:

(1) 決策變量

(2) 目標函數

在系統整體執行方案中所有被安排執行的任務的總權重之和最大。

(1)

(3) 約束條件

(2)

(3)

(4)

其中,式(2)表示每個觀測任務最多只能被執行一次;式(3)表示同一衛星對先后兩個任務的觀測持續時間不能有重疊;式(4)表示每個任務執行持續時間必須在其可見時間窗內。

1.3 全分布式環境下單星規劃分問題

在全分布式環境下,受限于全局信息(他星任務可見性與初始執行狀態)的缺失,單星智能體在協調優化過程中對星座內多星任務規劃問題的探索能力僅限于對自身規劃方案進行調整。如圖2所示,將制定多星整體方案的總問題轉化為多個制訂單星方案的分問題并分別交由對應各星智能體進行獨立探索。各分問題模型僅包含與本星方案相關的決策變量,其余變量則通過讀取他星方案作為已知常量輸入,而目標函數與約束條件則與總問題相同。將各分問題的解組合即可形成總問題的解,各星通過探索不同的單星方案組合以對整體方案進行尋優。

(5)

(6)

2 分布式協同規劃算法

針對上述遙感星座自主協同任務規劃問題,本文設計了一整套的全分布式協同優化策略與相應規劃算法,本節將對其進行具體描述。

2.1 全分布式星座協同迭代優化策略

受啟發于文獻[19]中描述的分布式多智能體組合優化啟發式(combinatorial optimization heuristic for distributed agents, COHDA)算法,本文設計了一種基于“接收”“更新”“發布”的三階段協作行為的全分布式星座協同迭代優化策略,如圖3所示。

其主要流程如下。

步驟1發起星將任務集合信息廣播至星座內其余各星,各星隨即針對任務集合進行自我規劃形成本星初始方案并儲存至本星方案集,系統進入方案優化階段。

步驟2在方案優化階段中,各星不斷循環進行以下三階段行為:① 向星座內其余各星發送本星方案集中的方案;② 將從他星接受到的最新方案儲存至本星方案集;③ 根據方案集中的他星最新方案優化更新自身方案并儲存至本星方案集,隨后返回階段①。

步驟3當到達預設的運行時限后,方案優化階段結束,此時各星上儲存的方案集內容均相同,都包含各星最新提出的本星方案,但不同星方案之間仍可能存在重復執行沖突;各星對其進行規則統一的沖突消解后形成最終整體方案。

2.2 多智能體合作式協同進化遺傳算法

基于上述全分布式星座協同迭代優化策略,本文設計了一種多智能體合作式協同進化遺傳算法(distributed agent-collaborative coevolution genetic algorithm,DA-CCGA),CCGA[20]是傳統遺傳算法的變體,其使用多個并行進化的亞種群將對復雜問題的優化搜索過程分解為對多個較簡單的分問題并行搜索,具有對分布式計算環境的先天適應性[21]。DA-CCGA由CCGA融合上述全分布式優化策略而形成,令代表不同星方案的亞種群分布于相應星上,各星亞種群相對獨立地進化以探索本星方案分問題,并通過交換種群特征信息以輔助適應度評價過程。DA-CCGA如算法1所示。

算法1 DA-CCGA輸入:衛星集合S;本星編號sid;待規劃元任務集合T;待規劃任務的本星時間窗集合TWsid;傳播周期Pspread;規劃運行時限Ptmax輸出:最終整體規劃方案P*1初始化最優印象集I*sid與抽樣印象集Isamsid2初始化本星初始亞種群P0sid←init(TWsid)3計算初始亞種群適應度estimate(P0sid,I*sid,Isamsid)4向他星傳播印象集spread(P0sid,I*sid,Isamsid)5初始化代數計數g←16 While 當前運行耗時ptPspread then15 向他星傳播印象集spread(P0sid,I*sid,Isamsid)16 增加代數計數g←g+117 End while18從最優印像集中提取最終方案P*←extract(I*sid)19 Return P*

(1) 染色體編碼與解碼

(2) 印象集

非小細胞肺癌表皮生長因子受體基因突變274例分析…………………………………………………… 王 艷等（20）：2817

在DA-CCGA中,各星儲存的方案集被擴充為“印象集”,即本星記錄的對他星亞種群特征個體的印象,包括“最優印象集”,即已知最新的各亞種群最優方案個體集合,與“抽樣印象集”,即已知最新的從各亞種群隨機抽取的方案個體集合。印象集中的所有方案個體均依據“最后更新時間戳”進行管理。各星通過不斷地傳播、接收、更新再傳播印象集信息,以滿足各亞種群在進行適應度評價時對他星方案信息的需求。

(3) 適應度函數

如圖5所示,各星亞種群中單條染色體的適應度值為其與他星染色體組成的整體方案的計算值,計算函數如下:

(7)

(4) 適應度評價過程

(8)

(5) 亞種群協作策略

如圖6所示,傳播種群特征即向所有鄰近星發送本星儲存的印象集信息,在每次發送前需要隨機從本星亞種群中抽取的一個方案個體以更新本星抽樣印象集。而接受種群特征即接收來自他星的印象集信息并根據其時間戳更新本星印象集,若接收后本星印象集發生變化則需重新計算本星亞種群內所有個體的適應度。

(6) 交叉與變異

如圖8所示,變異算子隨機作用于染色體的某個基因位上,將該基因位的執行任務去除后嘗試重新插入除任務以外的任務后得到變異后的染色體。

(7) 最終整體方案提取

3 仿真實驗分析

為了驗證本文所提出的方法的適用性與有效性,本節使用S698PM嵌入式開發環境模擬星座系統中分布式星載算力以對其自主任務規劃過程進行仿真實驗,該星座由5顆自主遙感衛星組成,其中2顆為中軌衛星,其余3顆為低軌。實驗模擬五星星座在一定規劃運行時限內對一定規模任務集合在特定規劃時域內的方案進行自主規劃,規劃使用的任務點目標坐標數據為隨機生成,其可見時間窗數據由仿真軟件模擬計算。

3.1 參數與通信環境敏感性測試

為了測試部分重要參數與星間通信環境變化對于DA-CCGA效能的影響,使用相應不同設置的多組實驗進行對比分析,每組重復運行50次并計算平均目標函數值,在測試中,待規劃任務數量為1 000,規劃時域長度為12 h,規劃運行時限為30 min(1 800 s)。

(1) 傳播周期影響

在DA-CCGA中,由于各亞種群的適應度評價過程依賴于對其他亞種群特征信息的獲取,故各衛星在優化過程中進行種群特征傳播的頻率變化必然會對算法效能造成影響,為探究其具體影響模式,設置不同傳播周期時長的實驗組進行對比,最終結果如圖10所示。

可見,傳播周期變化對算法效能的影響并非是單向的,過短或過長的傳播周期均會降低算法的尋優能力與穩定性,這通常是因為過于頻繁的傳播與接收將導致各星反復對亞種群進行重新評估,在大量占用計算資源的同時過度限制各亞種群的搜索方向,妨礙了搜索過程的有效進行。當傳播周期適中(15～20 s)時算法優化效能達到峰值,此時各星在整個規劃過程中可向他星傳播種群特征信息89～119次。隨后繼續增加傳播周期至450 s(傳播4次),算法仍能以良好的穩定性得到滿意解(與峰值的平均差距小于1.1%),但當傳播周期增加至600 s(傳播2次)以上時,在尋優能力降低的同時算法的穩定性也受到顯著影響?？梢奃A-CCGA能以較低的星間通信頻率到達接近高頻率的效果,對惡劣的星間通信環境具有良好的適應性,但仍需要一定次數的星間通信以支持其各亞種群的有效進化。

(2) 啟發式因子影響

(3) 星間拓撲與通信能力影響

在現實應用環境中,不同星座系統在不同時刻可能擁有不同的星間拓撲結構與相應的通信能力,為了檢驗DA-CCGA對不同通信環境的適應能力,設置以下通信拓撲場景,所有場景時長均為30 min:

① 穩定通信環境場景

S:其中一星與其他所有星之間可以穩定互相通信,其余星之間無法通信,即星形拓撲結構;

C:所有衛星均可以穩定與左右兩鄰星互相通信通信以組成環形拓撲結構;

L:去除環形拓撲中某兩星的相互通信能力以形成線形拓撲結構;

A:所有衛星均可以穩定與任意另一星互相通信的網狀拓撲結構。

② 不穩定通信環境場景

M:由仿真軟件模擬計算出2021年1月18日18:00至2021年1月18日18:30時間段內各星間真實可見性組成的不穩定通信環境場景；

S30-A30:場景開始后的30 s內為“S”,場景結束前的30 s內為“A”,其余時間任意兩星間均無法通信;

S1-A30:場景開始后的1 s內為“S”,場景結束前的30 s內為“A”,其余時間任意兩星間均無法通信。

使用以上通信環境設置不同實驗組進行對比,最終結果如圖12所示。

如圖12(a)所示,在穩定通信環境場景中,不同星間拓撲結構實驗組的結果均十分相似,其中A與C拓撲結構略優,S與L拓撲結構稍次之,可見DA-CCGA對不同拓撲結構的星座具有較強的適用性,但通信機會在星座內分布較為廣泛且平均的拓撲結構依然能對算法效能產生正向的影響。

如圖12(b)所示,DA-CCGA在M中的表現與其在穩定通信環境場景各實驗組中的非常接近,這再一次驗證了DA-CCG對惡劣的星間通信環境的適應性。而S30-A30與S1-A30均為僅允許衛星在規劃運行開始后與結束前的小段時間內進行通信的極端惡劣通信環境場景,但對算法性能的影響卻有巨大差距。算法在S30-A30中的表現僅略遜于各穩定通信環境場景與M(差距在0.4%以內),而S1-A30的結果卻與M擁有4.98%的差距,由此可見DA-CCGA適應惡劣通信環境的前提是:各星在優化搜索過程的初期擁有足夠的通信機會以充分了解他星初始亞種群的種群特征,從而有效指導本星亞種群在整個運行過程中的進化。

3.2 對比實驗

DA-CCGA作為一種全分布式搜索算法,可充分地利用分布于星座內的計算資源以不斷對問題進行尋優,但同時其搜索優化過程卻依賴于各節點間的通信協調。為了具體對比DA-CCGA與傳統集中式方法的尋優能力,設置了多組不同問題規模的實驗組,分別使用貪婪插入(greedy insert, GI)算法、集中式遺傳算法(centralized genetic algorithm,CGA)與DA-CCGA進行優化求解,同時將第1.2節中描述的多星任務規劃模型線性化后使用CPLEX嘗試求其精確解與上述算法優化結果進行對比,其中CGA僅使用單顆模擬衛星算力運行,CGA與DA-CCGA均重復運行50次并計算平均目標函數值,最終結果如表1所示。表1中“—”表示無法求解;規劃運行時限僅針對CGA與DA-CCGA,而CPLEX運行耗時并未給出。

表1 算法對比測試結果

當問題規模較小(任務量小于等于250)時,GI、CGA與DA-CCGA均能以較短的運行時間得出與CPLEX精確解相同或相近的結果,當問題規模擴大(任務量大于250)時,CPLEX由于模型約束數量限制被超過而無法求解,而CI、CGA與DA-CCGA之間的差距逐漸擴大,且DA-CCGA一直具有明顯的優勢。以1 000任務數測試組為例,如圖13所示,從單次運行結果的分布區間來看,DA-CCGA的穩定性略優于CGA,兩者的尋優效率都隨著運行時間的延長而減緩,但DA-CCGA的減緩速度明顯低于CGA,當到達25 min時,CGA已趨于收斂,而DA-CCGA則仍具有可繼續優化的趨勢。最終DA-CCGA搜索到的最優解目標函數值平均比CGA高出2.85%?？梢?DA-CCGA對于星座任務規劃問題,特別是大規模問題,具有相較于傳統集中式方法更強的優化搜索能力。

4 結 論