基于多Agent的遙感星座自主協(xié)同任務(wù)規(guī)劃

王俊 夏維 胡笑旋 張任馳

1．合肥工業(yè)大學(xué)安徽合肥230000

遙感衛(wèi)星是一種重要的獲取地表信息資源的工具,其數(shù)據(jù)產(chǎn)品在軍事偵查、礦物探測(cè)、氣象預(yù)測(cè)、緊急救援等方面均有十分重要的應(yīng)用[1?2].相較于單顆衛(wèi)星,遙感星座在成像能力和觀測(cè)靈活性等方面都有顯著提升[3],但是隨著衛(wèi)星數(shù)量的增多,星座任務(wù)規(guī)劃的復(fù)雜性也急劇增加,其求解已經(jīng)被證明為NP-hard 問(wèn)題.星座自主任務(wù)規(guī)劃是星座中各衛(wèi)星通過(guò)協(xié)商自適應(yīng)地生成任務(wù)執(zhí)行序列的過(guò)程,可以顯著提升星座系統(tǒng)的協(xié)同觀測(cè)能力及快速響應(yīng)能力.

傳統(tǒng)的管控模式中,需先由地面生成觀測(cè)計(jì)劃,再將觀測(cè)計(jì)劃上傳至星上執(zhí)行.然而,指令只能在衛(wèi)星經(jīng)過(guò)地面站上空時(shí)上注,導(dǎo)致其存在應(yīng)變能力差,反應(yīng)周期長(zhǎng)、星地交互復(fù)雜等問(wèn)題[4],無(wú)法滿足部分時(shí)效性高、動(dòng)態(tài)性強(qiáng)的成像需求.隨著星載計(jì)算能力和星間通信能力的不斷提升,遙感星座的任務(wù)規(guī)劃正逐漸向著協(xié)同化、自主化的方向發(fā)展[5?7].近些年來(lái)航天強(qiáng)國(guó)愈加重視星座自主任務(wù)規(guī)劃方面技術(shù)的研究,如美國(guó)的Plant Lab 星座群、美國(guó)國(guó)防部先進(jìn)研究項(xiàng)目局(Defense Advanced Research Projects Agency,DARPA)的BlackJack 計(jì)劃等[8?9].

雖然衛(wèi)星自主規(guī)劃原型較早就被提出,但是完全的星座自主協(xié)同規(guī)劃概念近些年才出現(xiàn).星座自主任務(wù)規(guī)劃的主要研究方向是如何設(shè)計(jì)多星協(xié)同機(jī)制、星座自主規(guī)劃模型及自主運(yùn)行的必要性,分析了自主運(yùn)行模式面臨的困難和挑戰(zhàn),歸納了分布式衛(wèi)星自主運(yùn)行涉及的高層規(guī)劃與調(diào)度、有效載荷控制及數(shù)據(jù)處理等關(guān)鍵技術(shù)[10?11];HERZ E等[12?14]提出利用agent 技術(shù)實(shí)現(xiàn)地面系統(tǒng)以及航天器自主的初步方案,并給出了系統(tǒng)的功能和體系結(jié)構(gòu);BONNET J 等[15?17]提出自組織的方式來(lái)解決星座任務(wù)規(guī)劃這一高度動(dòng)態(tài)的問(wèn)題,但該方法只適用于小規(guī)模的應(yīng)急任務(wù);SINHA P K 等[18?19]基于multi-agent 的衛(wèi)星系統(tǒng)進(jìn)行建模,各個(gè)衛(wèi)星代理可以相互協(xié)作,仿真實(shí)驗(yàn)表明了多agent 技術(shù)在實(shí)時(shí)資源分配、調(diào)度和優(yōu)化方面的優(yōu)勢(shì).

星上自主任務(wù)規(guī)劃模型與算法是實(shí)現(xiàn)星間協(xié)作、自主規(guī)劃的關(guān)鍵,研究較為廣泛的任務(wù)規(guī)劃模式為集中式和兩階段半集中式[20]兩種模式.Li G等[21]針對(duì)單星動(dòng)態(tài)自主規(guī)劃的問(wèn)題提出了一種啟發(fā)式算法,但沒(méi)有涉及星座自主規(guī)劃問(wèn)題;ZHENG Z等[22?28]提出使用遺傳算法和蟻群算法等智能算法作為自主任務(wù)規(guī)劃算法,但該類算法只適用于需求規(guī)模小且固定的場(chǎng)景;王沖[29]提出了一種基于Nash最優(yōu)的多星分布式優(yōu)化算法,可以通過(guò)設(shè)置不同的Nash 迭代終止條件來(lái)平衡計(jì)算時(shí)間和系統(tǒng)性能之間的關(guān)系;薛志家[30]提出一種基于放松圖的兩階段規(guī)劃算法,包括序列規(guī)劃階段和時(shí)間調(diào)度階段,仿真實(shí)驗(yàn)證明了算法的有效性.以上研究主要是針對(duì)單星或是具有特定需求的星座場(chǎng)景設(shè)計(jì)的自主任務(wù)規(guī)劃模型和算法,且上述文獻(xiàn)均只在通用計(jì)算機(jī)上進(jìn)行了仿真實(shí)驗(yàn),為了驗(yàn)證提出方法的可行性和計(jì)算效率,本文在星載計(jì)算環(huán)境下進(jìn)行了仿真實(shí)驗(yàn).

針對(duì)星座自主任務(wù)規(guī)劃問(wèn)題,本文提出了一種通用的自適應(yīng)分布式自主協(xié)同任務(wù)規(guī)劃框架.通過(guò)構(gòu)建衛(wèi)星內(nèi)部多agent 功能模塊和協(xié)同機(jī)制,為星上自主管理和星間協(xié)同任務(wù)規(guī)劃提供支撐;在算法設(shè)計(jì)方面,提出了一種基于時(shí)間窗適應(yīng)度的啟發(fā)式任務(wù)規(guī)劃算法.

1 問(wèn)題建模

1.1 問(wèn)題描述

以中軌微波遙感星座為例描述星座自主任務(wù)規(guī)劃問(wèn)題,該星座包括5 顆同構(gòu)的中軌微波遙感衛(wèi)星,5 顆衛(wèi)星均勻分布在同一軌道平面上,相鄰衛(wèi)星之間存在穩(wěn)定的通信連接,支持寬幅低分辨率和窄幅高分辨率兩種成像模式,星座自主任務(wù)規(guī)劃過(guò)程如圖1所示.

圖1(a)主要體現(xiàn)的是任務(wù)的生成過(guò)程,在T0 ～T1 時(shí)間段為遙感星座進(jìn)行地面觀測(cè)成像,T1 ～T2 時(shí)間段是對(duì)成像結(jié)果進(jìn)行識(shí)別處理并生成觀測(cè)任務(wù)集.圖1(b)T2 ～T3 時(shí)間段是規(guī)劃準(zhǔn)備階段,在T3 ～T4 時(shí)間段主要體現(xiàn)的是星座自主任務(wù)規(guī)劃過(guò)程,遙感星座通過(guò)任務(wù)同步、任務(wù)規(guī)劃、方案迭代、重規(guī)劃和方案更新等步驟,自主生成任務(wù)規(guī)劃方案,T4 ～T5 時(shí)間段為規(guī)劃結(jié)束階段.圖1(c)主要體現(xiàn)的是執(zhí)行衛(wèi)星觀測(cè)方案和數(shù)據(jù)下傳的過(guò)程,在T5 ～T6 時(shí)間段為遙感星座進(jìn)行地面觀測(cè)成像階段,在T6 ～T7 對(duì)成像結(jié)果進(jìn)行識(shí)別處理并生成觀測(cè)任務(wù)集,T7 ～T8 時(shí)間段是將得到的觀測(cè)數(shù)據(jù)下傳至地面站點(diǎn).

圖1 星座自主任務(wù)規(guī)劃流程Fig.1 Constellation autonomous mission planning process

為方便問(wèn)題求解,對(duì)星座自主任務(wù)規(guī)劃問(wèn)題作出如下假設(shè):1)本文所涉及的問(wèn)題是星地一體任務(wù)規(guī)劃系統(tǒng)中的星上自主任務(wù)規(guī)劃部分,不考慮由地面系統(tǒng)驅(qū)動(dòng)的星地協(xié)同任務(wù)規(guī)劃問(wèn)題;2)不考慮衛(wèi)星之間通信的通信時(shí)延.

1.2 模型構(gòu)建

1.2.1 符號(hào)設(shè)定

T={1,2··· ,i,··· ,NT}表示任務(wù)集合;

S={1,2,··· ,j,··· ,NS}表示衛(wèi)星集合;

G={1,2,··· ,k,··· ,NG}表示地面站集合;

ti=表示每一個(gè)任務(wù)ti∈T可以通過(guò)一個(gè)四元組表示,其中,vei表示任務(wù)i權(quán)重,dui表示任務(wù)i觀測(cè)持續(xù)時(shí)間,ari表示任務(wù)i從外界到達(dá)系統(tǒng)的時(shí)間,dei表示任務(wù)i完成期限;

任務(wù)i在衛(wèi)星j上的第a個(gè)時(shí)間窗,是時(shí)間窗開(kāi)始時(shí)間,是時(shí)間窗結(jié)束時(shí)間;

LWj衛(wèi)星j上第d?1 個(gè)地面站開(kāi)始時(shí)間到第d個(gè)地面站開(kāi)始時(shí)間之間的任務(wù)時(shí)間窗集合;

gci表示執(zhí)行任務(wù)i產(chǎn)生的數(shù)據(jù)需要的存儲(chǔ)量;

gsj表示衛(wèi)星j的最大存儲(chǔ)容量.

1.2.2 線性模型

其中,式(1)表示目標(biāo)函數(shù),最大化觀測(cè)收益之和;式(2)～式(7)表示約束條件;式(2)表示每個(gè)觀測(cè)任務(wù)最多只能被執(zhí)行一次;式(3)表示每個(gè)地面站時(shí)間窗都會(huì)被執(zhí)行;式(4)表示同一顆衛(wèi)星先后兩個(gè)執(zhí)行時(shí)間窗不能有重疊;式(5)表示每個(gè)任務(wù)執(zhí)行時(shí)間窗必須在可見(jiàn)時(shí)間窗內(nèi);式(6)表示存儲(chǔ)限制;式(7)每個(gè)任務(wù)的執(zhí)行開(kāi)始時(shí)間必須晚于其到達(dá)系統(tǒng)的時(shí)間.

2 任務(wù)規(guī)劃算法

2.1 自主規(guī)劃agent

自主規(guī)劃agent 是一個(gè)獨(dú)立的智能體,它由通信、任務(wù)池、事件管理、規(guī)劃驅(qū)動(dòng)、自主規(guī)劃多個(gè)子agent 組成,這些子agent 具有相對(duì)獨(dú)立的功能,必須相互協(xié)同才能有效地完成任務(wù).具體架構(gòu)如圖2所示.

圖2 自主規(guī)劃agent 架構(gòu)Fig.2 Independent planning of agent architecture

通信agent 監(jiān)聽(tīng)來(lái)自其他agent 的消息,并將這些消息中的事件提取更新至事件隊(duì)列;事件管理agent 負(fù)責(zé)響應(yīng)并處理事件隊(duì)列中符合時(shí)間約束的事件,將任務(wù)和驅(qū)動(dòng)信息傳遞給規(guī)劃驅(qū)動(dòng)模塊;規(guī)劃驅(qū)動(dòng)agent 負(fù)責(zé)計(jì)算規(guī)劃相關(guān)的約束信息,并生成時(shí)間驅(qū)動(dòng)事件添加至事件隊(duì)列;任務(wù)池agent 負(fù)責(zé)對(duì)任務(wù)信息進(jìn)行管理,及時(shí)更新已規(guī)劃任務(wù)和未規(guī)劃任務(wù)信息;規(guī)劃算法agent 根據(jù)任務(wù)和已有方案信息進(jìn)行自主任務(wù)規(guī)劃,并將生成的方案?jìng)鬟f至方案執(zhí)行模塊等待執(zhí)行.具體過(guò)程如圖3所示.

圖3 agent 規(guī)劃用例圖Fig.3 Agent planning use case diagram

2.2 算法介紹

本文提出的分布式規(guī)劃方法主要包括3 部分,分別是任務(wù)時(shí)間窗適應(yīng)度、分布式協(xié)同規(guī)劃流程和算法策略.

2.2.1 任務(wù)時(shí)間窗適應(yīng)度

任務(wù)時(shí)間窗適應(yīng)度表示不同任務(wù)在同一顆衛(wèi)星上的時(shí)間窗競(jìng)爭(zhēng)度,具體如圖4所示.

圖4 任務(wù)時(shí)間窗適應(yīng)度示意圖Fig.4 Adaptability diagram of task time window

任務(wù)時(shí)間窗適應(yīng)度的計(jì)算公式如下:

2.2.2 分布式協(xié)同算法流程

分布式規(guī)劃是星座自主協(xié)同生成任務(wù)規(guī)劃方案的過(guò)程,具體算法流程如下.

輸入:任務(wù)集合Tj、衛(wèi)星集合S和時(shí)間窗集合TWj

輸出:衛(wèi)星方案FS chej

開(kāi)始

1)進(jìn)行衛(wèi)星j∈S的任務(wù)集合T的同步待規(guī)劃任務(wù)信息

2)fo reachi∈Tj,j∈S,a∈TTWi j

3)根據(jù)式(8)計(jì)算任務(wù)i在衛(wèi)星j上的時(shí)間窗a的適應(yīng)度

5)end for

8)通過(guò)星間信息傳遞實(shí)現(xiàn)方案S chej的傳遞,通過(guò)對(duì)比保留不同方案S chej中同一任務(wù)中時(shí)間窗適應(yīng)度最高的時(shí)間窗,同時(shí)移除同一任務(wù)其他已被安排的時(shí)間窗,實(shí)現(xiàn)規(guī)劃方案的迭代更新

9)如果衛(wèi)星方案S chej在迭代更新過(guò)程中有時(shí)間窗被移除,則調(diào)用重規(guī)劃算法進(jìn)行重規(guī)劃,更新衛(wèi)星方案S chej

10:循環(huán)上述規(guī)劃、迭代更新和重規(guī)劃操作,直至達(dá)到規(guī)劃終止條件,到達(dá)預(yù)設(shè)的最大規(guī)劃時(shí)間或已達(dá)最優(yōu)及陷入局部最優(yōu),停止規(guī)劃

11)在規(guī)劃過(guò)程結(jié)束后,確定觀測(cè)收益最大方案為系統(tǒng)最優(yōu)方案并同步至所有衛(wèi)星,更新各星最終執(zhí)行方案FS chej

12)end for

結(jié)束

2.2.3 算法策略

1)基于時(shí)間窗適應(yīng)度的移位插入算法

在規(guī)劃方案中無(wú)法進(jìn)行直接插入時(shí),對(duì)任務(wù)前后任務(wù)進(jìn)行時(shí)間向前、向后且在其可見(jiàn)時(shí)間窗范圍內(nèi)移動(dòng),進(jìn)行插入操作,如圖5所示.

圖5 移位插入算法Fig.5 Shift insertion algorithm

2)基于時(shí)間窗適應(yīng)度的刪除插入算法

在規(guī)劃方案中,選擇沖突度最小的沖突進(jìn)行刪除,然后對(duì)待插入任務(wù)進(jìn)行插入,沖突度指的是移除某個(gè)沖突任務(wù)集合對(duì)于整個(gè)星座系統(tǒng)收益的影響,如圖6所示.

圖6 刪除插入算法Fig.6 Delete insert algorithm

3)基于時(shí)間窗適應(yīng)度的重規(guī)劃算法

在規(guī)劃過(guò)程中,假設(shè)多個(gè)任務(wù)可以在同一顆衛(wèi)星上安排,且時(shí)間窗存在沖突.此時(shí)就需要計(jì)算不同時(shí)間窗對(duì)整個(gè)系統(tǒng)的適應(yīng)度增益大小,優(yōu)先安排適應(yīng)度增益最大的任務(wù),適應(yīng)度增益的計(jì)算公式為:如圖7所示,任務(wù)t3 安排在衛(wèi)星2上的適應(yīng)度增益大于任務(wù)t3 安排在衛(wèi)星1 加上任務(wù)t4 安排在衛(wèi)星2 上的適應(yīng)度增益之和,因此,最終選擇將任務(wù)t3 安排在衛(wèi)星2 上.

圖7 重規(guī)劃算法Fig.7 Reprogramming algorithm

3 仿真實(shí)驗(yàn)與分析

為驗(yàn)證本文提出方法的實(shí)用性和有效性,構(gòu)建了一個(gè)星載計(jì)算環(huán)境.基于S698PM 芯片模擬星上計(jì)算環(huán)境,該型SoC 已在我國(guó)多顆在軌遙感衛(wèi)星上搭載.采用芯片的CPU 運(yùn)算能力為500 Mips,運(yùn)行內(nèi)存為8 MB,編碼采用SPARC V8 指令集,在集成開(kāi)發(fā)環(huán)境Orion6.0 下使用C 語(yǔ)言編程,如圖8所示.

3.1 實(shí)驗(yàn)數(shù)據(jù)

構(gòu)建的中軌微波遙感星座自主任務(wù)規(guī)劃仿真實(shí)驗(yàn)包含 5 顆衛(wèi)星,任務(wù)規(guī)劃時(shí)域?yàn)?11 August 2020 08:00:00.000 UTCG—11 August 2020 20:00:00.000 UTCG,隨機(jī)生成50、100、150、200、250、300、350、400、450、500 個(gè)任務(wù)的10 組測(cè)試算例,每種算例運(yùn)行30 次,取平均值作為最終實(shí)驗(yàn)結(jié)果.表1 列舉了部分實(shí)驗(yàn)信息.

表1 部分任務(wù)信息Table 1 Partial task information

3.2 對(duì)比測(cè)試實(shí)驗(yàn)

針對(duì)10 組測(cè)試算例分別進(jìn)行集中式規(guī)劃、兩階段半集中式規(guī)劃、分布式規(guī)劃3 種算法和Cplex 求解器的對(duì)比實(shí)驗(yàn),分別比較觀測(cè)收益率、規(guī)劃耗時(shí)、負(fù)載均衡率,驗(yàn)證分布式規(guī)劃算法的有效性,部分實(shí)驗(yàn)結(jié)果如表2所示.

表2 分布式規(guī)劃算法實(shí)驗(yàn)結(jié)果Table 2 Experimental results of distributed programming algorithm

1)為驗(yàn)證分布式規(guī)劃算法在觀測(cè)收益率上的有效性,將上述1 組算例分別用集中式、兩階段式算法及Cplex 求解器進(jìn)行求解,所得觀測(cè)收益率結(jié)果與上述實(shí)驗(yàn)對(duì)比,如圖9所示.

從圖9 可以看出,當(dāng)任務(wù)規(guī)模超過(guò)400 時(shí),集中式出現(xiàn)內(nèi)存溢出導(dǎo)致無(wú)法完成規(guī)劃;當(dāng)任務(wù)規(guī)模超過(guò)450 時(shí),兩階段半集中式也出現(xiàn)內(nèi)存溢出的情況下.分布式規(guī)劃則順利完成較大規(guī)模情況下的任務(wù)規(guī)劃,從而證明了分布式規(guī)劃在較大規(guī)模情況下適應(yīng)性更強(qiáng).

由于問(wèn)題規(guī)模超過(guò)200 時(shí)Cplex 無(wú)法求得最優(yōu)解,所以只能對(duì)比任務(wù)規(guī)模在50、100、150 和200時(shí),分布式規(guī)劃算法與最優(yōu)解的Gap.

如圖9所示,任務(wù)規(guī)模為5 時(shí),分布式規(guī)劃可以求得最優(yōu)解,隨著任務(wù)規(guī)模的提高,分布式規(guī)劃算法與最優(yōu)解之間的Gap 約為2%.

圖9 觀測(cè)收益率對(duì)比Fig.9 Comparison for observed rate of return

集中式規(guī)劃模式下的觀測(cè)收益率在任務(wù)規(guī)模處于100 ～300 范圍內(nèi)時(shí),要相對(duì)優(yōu)于分布式規(guī)劃模式;隨著任務(wù)規(guī)模的增加,分布式規(guī)劃的觀測(cè)收益率逐漸靠近集中式規(guī)劃模式,解的Gap 小于0.25%,證明了分布式規(guī)劃算法在觀測(cè)收益率上的有效性.

2)為驗(yàn)證分布式規(guī)劃算法在規(guī)劃耗時(shí)上的有效性,將上述10 組算例分別用集中式、兩階段式算法及Cplex 求解器進(jìn)行求解,所得規(guī)劃耗時(shí)結(jié)果與上述實(shí)驗(yàn)對(duì)比,如圖10所示.

從圖10 可以看出,在任務(wù)規(guī)模小于300 的情況下,3 種模式的規(guī)劃耗時(shí)相差不大,因?yàn)樵谌蝿?wù)規(guī)模較小的情況下,求解空間較小,3 種算法的求解時(shí)間差距不大;當(dāng)任務(wù)規(guī)模大于300 時(shí),集中式和兩階段半集中式的規(guī)劃耗時(shí)迅速增加,呈現(xiàn)出指數(shù)型增長(zhǎng)趨勢(shì),而分布式規(guī)劃的規(guī)劃耗時(shí)要更小且增長(zhǎng)趨勢(shì)也要更加平緩,從而證明了分布式規(guī)劃在規(guī)劃耗時(shí)方面的優(yōu)勢(shì).

圖10 規(guī)劃耗時(shí)對(duì)比Fig.10 Comparison of planning time

從圖11 看出,在規(guī)劃耗時(shí)方面,分布式規(guī)劃算法要明顯快于Cplex 求解器,且當(dāng)問(wèn)題規(guī)模太大時(shí),Cplex 求解器無(wú)法求解,而分布式算法可順利求解,從而證明了分布式算法在規(guī)劃耗時(shí)方面的有效性.

圖11 分布式算法與Cplex 規(guī)劃耗時(shí)對(duì)比Fig.11 Time comparison between distributed algorithm and Cplex programming

3)為驗(yàn)證分布式規(guī)劃算法在負(fù)載均衡率上的有效性,將上述的10 組算例分別用集中式和兩階段式算法進(jìn)行實(shí)驗(yàn),所得結(jié)果與上述實(shí)驗(yàn)對(duì)比,如圖12所示.

從圖12 可以看出,隨著任務(wù)規(guī)模的增大,分布式規(guī)劃模式的負(fù)載均衡率一直高于另外兩種規(guī)劃模式.因?yàn)樵谶M(jìn)行分布式規(guī)劃的過(guò)程中,基于時(shí)間窗適應(yīng)度進(jìn)行了考慮,任務(wù)會(huì)被優(yōu)先安排在適應(yīng)度高的窗口位置,而時(shí)間窗適應(yīng)度考慮了負(fù)載均衡的因素,因此,隨著規(guī)劃過(guò)程的進(jìn)行,任務(wù)在不同衛(wèi)星上的安排會(huì)相對(duì)均衡.集中式和兩階段半集中式規(guī)劃缺乏對(duì)負(fù)載均衡的考慮,所以分布式規(guī)劃在負(fù)載均衡率上要優(yōu)于其他兩種模式.

圖12 負(fù)載均衡率對(duì)比Fig.12 Comparison of load balancing rate

4 結(jié)論

本文研究了星座自主任務(wù)規(guī)劃問(wèn)題,提出了一種自適應(yīng)的分布式協(xié)同規(guī)劃方法,包括星上自主agent 設(shè)計(jì)、分布式協(xié)同規(guī)劃模型和基于時(shí)間窗適應(yīng)度的自主任務(wù)規(guī)劃啟發(fā)式算法.通過(guò)板載實(shí)驗(yàn)對(duì)設(shè)計(jì)的方法進(jìn)行驗(yàn)證,實(shí)驗(yàn)結(jié)果證明了本文所提方法的有效性和實(shí)用性.在本文研究的基礎(chǔ)上,下一步的研究主要考慮:1)當(dāng)星座的通信鏈路不穩(wěn)定或者出現(xiàn)衛(wèi)星故障的情況下,如何設(shè)計(jì)合理的星間協(xié)同機(jī)制來(lái)完成規(guī)劃過(guò)程,提高星座的魯棒性;2)當(dāng)需要多個(gè)星座共同完成任務(wù)集的情況下,如何設(shè)計(jì)合理的機(jī)制實(shí)現(xiàn)星座之間的協(xié)同規(guī)劃處理.