楊舒，陳浩，李軍，景寧

(國防科技大學(xué) 電子科學(xué)與工程學(xué)院，湖南 長沙 410073)

一種面向任務(wù)的對地觀測衛(wèi)星Agent團(tuán)隊(duì)構(gòu)建方法

楊舒，陳浩，李軍，景寧

(國防科技大學(xué) 電子科學(xué)與工程學(xué)院，湖南 長沙 410073)

隨著航天科技的飛速發(fā)展，逐漸出現(xiàn)了由多種異構(gòu)衛(wèi)星組成的衛(wèi)星集群。相比于傳統(tǒng)的衛(wèi)星系統(tǒng)，衛(wèi)星集群具有規(guī)模大、平臺多、載荷異構(gòu)的特點(diǎn)，傳統(tǒng)的衛(wèi)星任務(wù)規(guī)劃方法難以適用。針對衛(wèi)星集群任務(wù)規(guī)劃中的關(guān)鍵問題——面向任務(wù)的衛(wèi)星Agent團(tuán)隊(duì)構(gòu)建問題，建立了數(shù)學(xué)模型，提出了基于分支限界的精確搜索算法，并對其時間復(fù)雜度進(jìn)行了分析。針對精確算法時間復(fù)雜度較高的缺點(diǎn)，引入了啟發(fā)式剪枝機(jī)制，并按照任務(wù)集合排序策略的不同設(shè)計了3種啟發(fā)式衛(wèi)星團(tuán)隊(duì)構(gòu)建算法。最后，通過多組實(shí)驗(yàn)分析了衛(wèi)星團(tuán)隊(duì)構(gòu)建精確搜索算法與啟發(fā)式剪枝搜索算法的性能，驗(yàn)證了我們提出算法的有效性和實(shí)用性。

Agent團(tuán)隊(duì)構(gòu)建；對地觀測衛(wèi)星集群；分支限界；啟發(fā)式算法；剪枝策略；任務(wù)集合排序策略；衛(wèi)星任務(wù)規(guī)劃；時間復(fù)雜度

對地觀測衛(wèi)星(earth observing satellite, EOS)利用衛(wèi)星遙感器對地球表面進(jìn)行探測，以獲取有關(guān)信息，具有覆蓋區(qū)域廣、不受空域國界限制、不涉及人員安全等特點(diǎn)，在大地測繪、自然災(zāi)害檢測、海洋搜救、軍事應(yīng)用等領(lǐng)域產(chǎn)生了巨大效益[1]。

為了更好地利用寶貴的衛(wèi)星資源，最大化地滿足用戶需求，衛(wèi)星任務(wù)規(guī)劃得到了全世界學(xué)者的廣泛關(guān)注。當(dāng)前，衛(wèi)星任務(wù)規(guī)劃的對象是整個衛(wèi)星集合，規(guī)劃的目的是安排整個衛(wèi)星集合的動作，使得在滿足衛(wèi)星所有約束的前提下，能夠最大化滿足用戶需求。主要的研究工作可以分為集中式規(guī)劃和分布式規(guī)劃兩個類別。

集中式的任務(wù)規(guī)劃方法[2]通常采用約束滿足問題模型[3]、圖模型[4]等對多星任務(wù)調(diào)度問題進(jìn)行統(tǒng)一建模，然后采用貪婪算法、啟發(fā)式算法[5]以及各種智能優(yōu)化算法[6-7]進(jìn)行求解，處理的衛(wèi)星均為同種類型。

而分布式任務(wù)規(guī)劃研究則主要是將衛(wèi)星建模為具有自主性、協(xié)同性、社會性的Agent，多顆衛(wèi)星通過自主協(xié)商完成任務(wù)優(yōu)化分配，目前多采用基于拍賣的協(xié)商協(xié)議[8]。例如，采用基于方案融合的合同網(wǎng)方法[9]，采用聚類降載與演化計算相結(jié)合的協(xié)同方法[10]，基于協(xié)同進(jìn)化與遷移學(xué)習(xí)的協(xié)同方法[11]等。分布式衛(wèi)星任務(wù)規(guī)劃較集中式衛(wèi)星任務(wù)規(guī)劃而言，有更大的靈活性，可以將不同類型的衛(wèi)星建模為異構(gòu)的衛(wèi)星規(guī)劃Agent，從而能處理不同種類衛(wèi)星的任務(wù)規(guī)劃問題，且可采用Agent并行協(xié)同方式提升規(guī)劃效率。但隨著衛(wèi)星規(guī)模的增加，任務(wù)協(xié)同計算代價增長明顯。

傳統(tǒng)衛(wèi)星任務(wù)規(guī)劃問題中，衛(wèi)星數(shù)量通常在幾顆到十幾顆左右，當(dāng)問題規(guī)模上升為數(shù)十顆乃至上百顆衛(wèi)星時，集中式規(guī)劃方法會因?yàn)閱栴}規(guī)模巨大很難給出用戶滿意解，分布式規(guī)劃方法也會因?yàn)閰f(xié)同耗時太長很難在有效時間內(nèi)給出問題可行解。

隨著航天科技的飛速發(fā)展，逐漸出現(xiàn)了由多種異構(gòu)衛(wèi)星組成的衛(wèi)星集群[12]，如用于木星大氣層探測的SMARA微型衛(wèi)星群[13]、用于小行星探測的ANTS群衛(wèi)星系統(tǒng)[14]、用于天文觀測的OLFAR衛(wèi)星集群[15]等，這些衛(wèi)星集群的規(guī)模都在幾十顆到上百顆之間。與傳統(tǒng)的衛(wèi)星系統(tǒng)相比，衛(wèi)星集群的規(guī)模更大，能力更多，通常只需從集群中挑選一個子集(稱為面向任務(wù)的衛(wèi)星團(tuán)隊(duì)，簡稱衛(wèi)星團(tuán)隊(duì))，即可完成一組對地觀測任務(wù)。

可見，衛(wèi)星群任務(wù)規(guī)劃在規(guī)劃場景、規(guī)劃目的、問題規(guī)模上均與傳統(tǒng)的衛(wèi)星任務(wù)規(guī)劃方法存在較大差別，傳統(tǒng)的任務(wù)規(guī)劃方法難以直接應(yīng)用。

基于上述分析，對衛(wèi)星集群的任務(wù)規(guī)劃可分解為兩個子問題：子問題1，根據(jù)任務(wù)集特點(diǎn)從整個衛(wèi)星集群中篩選出一個能夠勝任該任務(wù)集的衛(wèi)星團(tuán)隊(duì)；子問題2，針對篩選出的衛(wèi)星團(tuán)隊(duì)采用傳統(tǒng)任務(wù)規(guī)劃方法優(yōu)化安排每一顆衛(wèi)星的觀測動作，從而達(dá)到縮減任務(wù)規(guī)劃中衛(wèi)星資源規(guī)模，降低時間復(fù)雜度的目的。

我們擬對子問題1展開研究。但由于衛(wèi)星異構(gòu)的特性，不同團(tuán)隊(duì)執(zhí)行同一組對地觀測任務(wù)的代價通常不同。如何構(gòu)建能夠完成多組觀測任務(wù)的最小衛(wèi)星團(tuán)隊(duì)(團(tuán)隊(duì)中不存在冗余觀測能力)，且執(zhí)行代價最小，已經(jīng)成為衛(wèi)星任務(wù)規(guī)劃領(lǐng)域出現(xiàn)的新而亟待解決的問題。

T. Okimoto等[16]處理巴黎火災(zāi)救援問題時，將救援設(shè)備建模為Agent，根據(jù)火勢大小，向各個火災(zāi)點(diǎn)組織消防車團(tuán)隊(duì)進(jìn)行救援，是一種面向任務(wù)的Agent團(tuán)隊(duì)構(gòu)建思想。受此啟發(fā)，我們擬對觀測任務(wù)集合、衛(wèi)星集群能力[17]進(jìn)行建模，研究面向任務(wù)的衛(wèi)星Agent團(tuán)隊(duì)構(gòu)建方法。設(shè)定衛(wèi)星集群中的每顆衛(wèi)星在執(zhí)行每一個對地觀測任務(wù)時，可以獲得對應(yīng)的收益和代價，執(zhí)行不同的任務(wù)，代價不同。因此在勝任集合中所有任務(wù)的前提下，合理挑選衛(wèi)星，使衛(wèi)星團(tuán)隊(duì)執(zhí)行所有任務(wù)的總代價最小[18]。

1 問題描述

面向任務(wù)的對地觀測衛(wèi)星團(tuán)隊(duì)構(gòu)建問題就是在已知系統(tǒng)的初始狀態(tài)、可用資源、每顆衛(wèi)星的負(fù)載情況的前提下，針對對地觀測任務(wù)集合，基于衛(wèi)星在執(zhí)行任務(wù)時產(chǎn)生的代價從衛(wèi)星集群中挑選出一組能勝任所有觀測任務(wù)的衛(wèi)星，組成衛(wèi)星團(tuán)隊(duì)，使得執(zhí)行所有任務(wù)的總代價最小。

1.1 符號定義

為了方便描述，首先給出相關(guān)符號定義，如表1所示。

1.2 目標(biāo)函數(shù)

面向任務(wù)的對地觀測衛(wèi)星團(tuán)隊(duì)構(gòu)建問題的目標(biāo)是從衛(wèi)星集群中找到一個能夠勝任這些任務(wù)的衛(wèi)星團(tuán)隊(duì)，并使團(tuán)隊(duì)的總代價最小，即當(dāng)team∈TEAMM時：

團(tuán)隊(duì)的總代價是團(tuán)隊(duì)中所有衛(wèi)星執(zhí)行任務(wù)的代價之和。

衛(wèi)星Sati執(zhí)行任務(wù)taskj的代價CST(Sati,taskj)可由SCi和TCj計算得到：

SCi由衛(wèi)星Sati當(dāng)前時刻執(zhí)行任務(wù)情況決定。衛(wèi)星的使用代價SCi與執(zhí)行的任務(wù)數(shù)、被占用的時間窗數(shù)正相關(guān)：

在團(tuán)隊(duì)構(gòu)建過程中，衛(wèi)星使用代價隨著承擔(dān)任務(wù)數(shù)增多，而不斷增長。

表1 符號定義

1.3 約束模型

衛(wèi)星Sati能夠執(zhí)行任務(wù)taskj的條件：在衛(wèi)星擁有的時間資源TWi中，找到一組觀測時間窗TWtasks，勝任Btasksi和taskj，且與衛(wèi)星上已經(jīng)被占用的時間窗集合TW_usedi不產(chǎn)生沖突?？紤]衛(wèi)星在執(zhí)行任務(wù)時，受星上電源容量、載荷硬件特性、軌道參數(shù)等限制，將一個時間窗看作一次觀測活動，對TWtasks和TW_usedi組成的時間窗集合TWdet進(jìn)行以下約束檢測，TWdet中的TW按照ts排序。

1)兩次觀測活動不能同時進(jìn)行。衛(wèi)星一次只能進(jìn)行一個觀測活動，即

2)兩次觀測活動最短時間間隔。衛(wèi)星關(guān)機(jī)后需要一段時間才能重新開機(jī)，即

3)單圈最長觀測時間約束。衛(wèi)星單圈累計觀測時間要小于單圈最長開機(jī)時間，即

式中TWcirP表示TWdet中所有圈號為P的時間窗。

4)單天最長觀測時間約束。衛(wèi)星單天累計觀測時間限制要小于單天最長觀測時間，即

式中TWdayQ表示TWdet中所有時間窗起始時間在第Q天內(nèi)的時間窗集合。

2 基于分枝限界的衛(wèi)星任務(wù)團(tuán)隊(duì)構(gòu)建算法

由上述模型可知，該問題是一個典型的組合優(yōu)化問題，我們擬采用樹構(gòu)建與搜索方法，以初始的空團(tuán)隊(duì)team0作為根節(jié)點(diǎn)，以完成任務(wù)為條件向下分支，形成新的團(tuán)隊(duì)，遍歷完所有任務(wù)，可建構(gòu)一顆廣義的搜索樹。

算法1 TFCA

功能基于分枝限界思想的團(tuán)隊(duì)構(gòu)建算法的主算法；

輸入TaskSet, SatSet, 初始的空團(tuán)隊(duì)team0；

1)Begin

5)End

則減去Curteam這個節(jié)點(diǎn)向下的所有分枝。

基于這種搜索剪枝策略，提出了基于分枝限界思想的團(tuán)隊(duì)構(gòu)建算法(team formation complete algorithm based-on a branch and bound techniques，TFCA)，偽代碼如算法1、2、3所示。

算法2 TFOfEachTask

功能從第m個任務(wù)開始搜索構(gòu)建團(tuán)隊(duì)的迭代算法。

北大語料庫中“吃虧”用例共1578個，其中多數(shù)充任謂語成分，也可作賓語(如：怕吃虧)，充任主語的最具代表性的例子是“吃虧是?！?共17例)，由此可見“吃虧”作謂語的比例是最大的；可以受“不”修飾，共有157個用例；能用肯定否定形式(V不V)提問，如：您感到種糧[吃虧不吃虧]？重疊式“吃虧吃虧”和“吃吃虧虧”無用例，可見不能重疊；概括意義是表“受損失或者在某方面條件不利”的動作。綜上，“吃虧”符合動詞的主要語法特征。

1)Begin

2)if(mgt;M)

5)Return

7)Return

8)end if

9)solve(1,team,teamSet,m)

10)for each team in teamSet

12)end for

13)End

算法3 solve

功能尋找team向下能完成taskm的團(tuán)隊(duì)的迭代算法；

輸入n, team, teamSet,m；

輸出當(dāng)前team下能完成taskm的團(tuán)隊(duì)集合teamSet。

1)Begin

2)if(ngt;N)

3)Return

4)else if(Satn能完成taskm)

5)team1=Update(team)

6)teamSet=teamSet∪{team1}

7)solve(n+1,team,teamSet,m)

8)end if

9)End

算法3尋找在當(dāng)前team下，能完成taskm的所有團(tuán)隊(duì)的迭代算法。在當(dāng)前team的情況，依次判斷每顆衛(wèi)星Satn能否完成taskm，如果能完成，則生成新團(tuán)隊(duì)team1，并將該team1加入teamSet。

由上述分析可知，在最壞的情況下，算法時間復(fù)雜度將呈指數(shù)增長，該問題組合爆炸特征明顯。為了降低基于分枝限界思想的團(tuán)隊(duì)構(gòu)建算法的時間復(fù)雜度，提出了一種基于剪枝策略的啟發(fā)式算法。

3 基于剪枝策略的啟發(fā)式算法

通過TFCA算法進(jìn)行樹搜索，首先要找到一個勝任所有任務(wù)的團(tuán)隊(duì)，以這個團(tuán)隊(duì)的代價作為上界才可以進(jìn)行剪枝操作，運(yùn)行時間較長，剪掉的分支有限，效率較低，為了提高樹搜索效率，需要尋找一種新的剪枝策略。

我們將深度優(yōu)先的搜索方式改成廣度優(yōu)先，對每一層的團(tuán)隊(duì)集合TEAM進(jìn)行剪枝操作，從而達(dá)到減少樹分枝，降低時間復(fù)雜度的目的。

首先，給出剪枝策略。設(shè)team1,team2∈TEAMi，如果

0lt;εlt;1記為team1lt;team2，則剪去team1這個團(tuán)隊(duì)所在的結(jié)點(diǎn)。其中，i是TEAMi中的每個團(tuán)隊(duì)完成的任務(wù)個數(shù)，ε根據(jù)衛(wèi)星初始狀態(tài)調(diào)整，盡量為團(tuán)隊(duì)挑選承擔(dān)任務(wù)數(shù)少的衛(wèi)星。

基于這種剪枝策略，提出了啟發(fā)式團(tuán)隊(duì)構(gòu)建算法(heuristic team formation algorithm based-on a pruning strategy, HTFA)，算法偽碼如算法4所示。

算法4是基于剪枝策略的啟發(fā)式算法，以team0作為根節(jié)點(diǎn)，從第1個任務(wù)開始搜索，TEAM1是所有完成task1的team集合，對TEAM1中每個team，搜索task2，以此類推直到搜索到TEAMM。語句8)～22)是根據(jù)剪枝策略對TEAMM進(jìn)行的剪枝操作。

算法4 HTFA

功能基于剪枝策略的啟發(fā)式算法;

輸入TaskSet, SatSet,team0;

1) Begin

2) set TEAMi=?,i∈(0,M)

3)TEAM0=TEAM0∪{team0}

4)for(i=1;i≤M;i++)

5)for each teaminTEAMi-1

6)set TEAMi=?

7)solve(1,team,teamSet,i)

8)for each team1in teamSet

9)if(TEAMi=?)

10)TEAMi=TEAMi∪{team1}

11)else

12)for each team2in TEAMi

13)if(team1gt;team2)

14)TEAMi=TEAMi/{team2}

15)TEAMi=TEAMi∪{team1}

16)else

17)if(team2gt;team1)

18)break

19)else

20)TEAMi=TEAMi∪{team1}

21)end for

22)end for

23)end for

24)end for

25)for each team in TEAMM

28)end for

30) End

由于HTFA算法的這種剪枝策略，TaskSet的輸入順序可能會影響算法最終輸出結(jié)果。如果在隨機(jī)的任務(wù)集合中，代價小的任務(wù)排在前面，HTFA將會優(yōu)先挑選代價小的衛(wèi)星執(zhí)行該任務(wù)，代價大的任務(wù)只能選擇代價大的衛(wèi)星，會使最終構(gòu)建出的衛(wèi)星團(tuán)隊(duì)的代價偏大。為此，對輸入任務(wù)集合TaskSet進(jìn)行排序：

1)記無序的任務(wù)集合為TaskSet-S，以TaskSet-S作為輸入的HTFA算法為HTFA-S；

2)根據(jù)任務(wù)代價由高到低排序的任務(wù)集合為TaskSet-C，以TaskSet-C作為輸入的HTFA算法為HTFA-C；

3)根據(jù)任務(wù)性價比由高到低排序的任務(wù)集合為TaskSet-RC，以TaskSet-RC作為輸入的HTFA算法為HTFA-RC。

4 實(shí)驗(yàn)與分析

為了驗(yàn)證TFCA算法、HTFA-S算法、HTFA-C算法、HTFA-RC算法的性能，設(shè)計了4組實(shí)驗(yàn)。

計算平臺：Intel(R) Core(TM) i5-6400 CPU @ 2.70 GHz (4 CPUs)，內(nèi)存 8192 MB RAM，操作系統(tǒng)Win7，采用Microsoft Visual Studio 2010 C#編碼。

實(shí)驗(yàn)數(shù)據(jù)在STK衛(wèi)星數(shù)據(jù)庫中選取50顆低軌衛(wèi)星數(shù)據(jù)模擬衛(wèi)星集群的運(yùn)行，以全球100個重要城市作為觀測目標(biāo)，從中隨機(jī)挑選。設(shè)定每顆衛(wèi)星上攜帶可見光、紅外、電磁探測、多光譜、超光譜5種載荷。根據(jù)衛(wèi)星硬件情況，設(shè)置衛(wèi)星使用代價SCi=α(|Btasksi|+|TW_usedi|)中的參數(shù)α，隨機(jī)挑選1～5個時間窗作為衛(wèi)星上已經(jīng)被占用的時間窗集合TW_used。采用隨機(jī)生成一組任務(wù)的方式，模擬真實(shí)環(huán)境下一段時間內(nèi)衛(wèi)星系統(tǒng)接收到的待規(guī)劃任務(wù)集合。

衛(wèi)星集群按照衛(wèi)星成員的數(shù)量可以分為小規(guī)模衛(wèi)星集群(small-scale satellite cluster, SSC)和大規(guī)模衛(wèi)星集群(large-scale satellite cluster, LSC)。小規(guī)模衛(wèi)星集群中成員數(shù)量在10顆以下，大規(guī)模衛(wèi)星集群的成員數(shù)量大于10顆。

實(shí)驗(yàn)1 隨機(jī)生成6組任務(wù)，在10顆衛(wèi)星構(gòu)成的小規(guī)模集群上采用TFCA、HTFA-S、HTFA-C、HTFA-RC構(gòu)建團(tuán)隊(duì)，比較4種算法的性能。實(shí)驗(yàn)結(jié)果如圖1和表 2。

圖1 4種算法在小規(guī)模衛(wèi)星集群上的性能對比Fig.1 Performances of four algorithms in SSC

Table 2 Running time of four algorithms in SSCs

從圖1可以看出，在小規(guī)模衛(wèi)星集群中，HTFA-S、HTFA-RC、HTFA-C算法構(gòu)建的團(tuán)隊(duì)效果接近TFCA算法。HTFA-S算法由于任務(wù)輸入的無序性，在大部分情況下構(gòu)建團(tuán)隊(duì)的效果比HTFA-RC、HTFA-C算法差。表2展示了4種算法的時間特性，TFCA算法的運(yùn)行時間隨著任務(wù)的增多，呈現(xiàn)指數(shù)增長趨勢，HTFA-S、HTFA-RC、HTFA-C算法的運(yùn)行時間增長緩慢。

實(shí)驗(yàn)2 為了進(jìn)一步驗(yàn)證我們提出的算法在大規(guī)模衛(wèi)星集群上的性能，在50顆衛(wèi)星組成的衛(wèi)星集群上重新測試實(shí)驗(yàn)1中的6組任務(wù)數(shù)據(jù)。但由于TFCA算法運(yùn)行時間太長(在50顆衛(wèi)星組成的集群上，對12個任務(wù)構(gòu)建團(tuán)隊(duì)時，運(yùn)行超過12 h仍然不能給出有效結(jié)果)我們僅對比HTFA-S、HTFA-RC和HTFA-C的實(shí)驗(yàn)結(jié)果，如圖2、3所示。

圖2 3種啟發(fā)式算法在LSC上的性能對比Fig.2 Performances of three algorithms in LSC

圖3 3種啟發(fā)式算法在LSC上的運(yùn)行時間對比Fig.3 Time comparison of three algorithms in LSC

圖2展現(xiàn)了在大規(guī)模衛(wèi)星集群上HTFA-S、HTFA-RC、HTFA-C算法的性能差異。HTFA-RC、HTFA-C算法構(gòu)建團(tuán)隊(duì)的效果普遍優(yōu)于HTFA-S算法。從圖3中可以看出，隨著任務(wù)增多，HTFA-S、HTFA-RC、HTFA-C算法構(gòu)建團(tuán)隊(duì)時間都在逐漸增加，而HTFA-C構(gòu)建團(tuán)隊(duì)時間的增長速度明顯高于HTFA-S和HTFA-RC，這是因?yàn)镠TFA-C任務(wù)的有序性在相同的剪枝策略下相比于其他兩種算法，HTFA-C在每一層會更多地保留效果好的分枝，因此整個團(tuán)隊(duì)構(gòu)建過程中，搜索的分枝更多。

實(shí)驗(yàn)3 隨機(jī)生成一組由10個任務(wù)構(gòu)成的任務(wù)集合，在不同規(guī)模的衛(wèi)星集群上構(gòu)建團(tuán)隊(duì)，比較TFCA、HTFA-S、HTFA-C、HTFA-RC算法性能，實(shí)驗(yàn)結(jié)果如表3、圖4所示。

表34種算法的運(yùn)行時間對比

Table 3 Running time of four algorithmss

圖4 4種算法在不同規(guī)模衛(wèi)星集群上的性能對比Fig.4 Performances of four algorithms in different scales of SC

圖4是在中小規(guī)模的多個衛(wèi)星集群上對同一組任務(wù)數(shù)據(jù)構(gòu)建團(tuán)隊(duì)對比4種算法的性能。隨著衛(wèi)星規(guī)模的逐步增大，團(tuán)隊(duì)的代價越來越小。多數(shù)情況下，HTFA-C、HTFA-RC算法的性能優(yōu)于HTFA-S算法。從表 3中可以看出，TFCA算法的運(yùn)行時間隨著集群規(guī)模增大爆發(fā)式增長。而HTFA-S、HTFA-RC、HTFA-C算法的運(yùn)行時間增長不明顯。

實(shí)驗(yàn)4 為了進(jìn)一步比較3種啟發(fā)式算法在大規(guī)模衛(wèi)星集群上的性能，隨機(jī)生成一組由20個任務(wù)組成的任務(wù)集合，在10、20、30、40、50顆衛(wèi)星組成的衛(wèi)星集群上進(jìn)行實(shí)驗(yàn)。由于TFCA算法運(yùn)行時間太長(在20顆衛(wèi)星組成的集群上，對20個任務(wù)構(gòu)建團(tuán)隊(duì)時，運(yùn)行超過12 h仍然不能給出有效結(jié)果)，我們僅對比HTFA-S、HTFA-RC和HTFA-C的實(shí)驗(yàn)結(jié)果，如圖5、6所示。

圖5 3種啟發(fā)式算法在不同規(guī)模衛(wèi)星集群上的性能對比Fig.5 Performances of three algorithms in different scales of SC

圖6 3種啟發(fā)式算法在不同規(guī)模的衛(wèi)星集群上運(yùn)行時間Fig.6 Time comparison of three algorithms in different scales of SC

圖6中隨著衛(wèi)星規(guī)模的增大，對同一組任務(wù)構(gòu)建的團(tuán)隊(duì)代價逐漸減少，而構(gòu)建團(tuán)隊(duì)的時間逐漸增大。這是因?yàn)橐?guī)模增大，可以挑選多個衛(wèi)星承擔(dān)任務(wù)，無需一個衛(wèi)星承擔(dān)多個任務(wù)，團(tuán)隊(duì)代價隨之降低。

整體上來看，3種啟發(fā)式算法HTFA-S、HTFA-RC和HTFA-C構(gòu)建團(tuán)隊(duì)所需的時間成本遠(yuǎn)小于TFCA算法，而其性能與TFCA相差不大，對任務(wù)集合根據(jù)任務(wù)代價排序的HTFA-C構(gòu)建的團(tuán)隊(duì)的代價最接近TFCA算法構(gòu)建的團(tuán)隊(duì)的代價，也就是最接近全局最優(yōu)解，HTFA-RC次之。

5 結(jié)束語

面向任務(wù)的對地觀測衛(wèi)星團(tuán)隊(duì)構(gòu)建問題，是衛(wèi)星任務(wù)規(guī)劃領(lǐng)域出現(xiàn)的新而亟待解決的問題。在對問題進(jìn)行分析的基礎(chǔ)上，建立了數(shù)學(xué)模型，提出了基于分枝限界的衛(wèi)星團(tuán)隊(duì)構(gòu)建精確搜索算法(TFCA)。針對TFCA算法時間復(fù)雜度高的缺點(diǎn)，引入了啟發(fā)式剪枝策略，并根據(jù)算法輸入中任務(wù)集合的次序不同，提出了3種啟發(fā)式衛(wèi)星團(tuán)隊(duì)構(gòu)建算法：HTFA-S、HTFA-RC和HTFA-C算法。實(shí)驗(yàn)結(jié)果表明：3種啟發(fā)式算法HTFA-S、HTFA-RC和HTFA-C，構(gòu)建團(tuán)隊(duì)所需的時間成本遠(yuǎn)小于TFCA算法，而其性能與TFCA算法相差不大，對任務(wù)集合根據(jù)任務(wù)代價排序的HTFA-C構(gòu)建的團(tuán)隊(duì)的代價最接近TFCA算法構(gòu)建的團(tuán)隊(duì)的代價。

在下一步的工作中，我們將從理論上分析HTFA-S、HTFA-RC和HTFA-C算法近似程度，并給出算法性能上界。

[1]LIN Zhenhai. Mission planning for electromagnetic environment monitors satellite based on simulated annealing algorithm[C]//2015 IEEE 28th Canadian Conference on Electrical and Computer Engineering (CCECE). Halifax, Canada, 2015: 530-535.

[2]姜維,郝會成,李一軍.對地觀測衛(wèi)星任務(wù)規(guī)劃問題研究述評[J].系統(tǒng)工程與電子技術(shù), 2013, 35(9):1878-1885.

JIANG Wei, HAO Huicheng, LI Yijun. Review of task scheduling research for the earth observing satellites[J]. Systems engineering and electronics,2013,35(9):1878-1885.

[3]WANG Jun, JING Ning, LI Jun, et al. A multi-objective imaging scheduling approach for earth observing satellites[C]//Proceedings of the 9th annual conference on Genetic and evolutionary computation. London, England, 2007: 2211-2218.

[4]CHEN Hao, LI Jun, JING Ning. User-oriented data acquisition chain task planning algorithm for operationally responsive space satellite[J]. Journal of systems engineering and electronics, 2016, 27(5): 1028-1039.

[5]WANG P, REINELT G, GAO P, et al. A model, a heuristic and a decision support system to solve the scheduling problem of an earth observing satellite constellation[J]. Computers amp; industrial engineering, 2011, 61(2): 322-335.

[6]郭玉華. 多類型對地觀測衛(wèi)星聯(lián)合任務(wù)規(guī)劃關(guān)鍵技術(shù)研究[D]. 長沙：國防科技大學(xué), 2009: 19-57.

GUO Yuhua. The study on key technologies of multiple types of earth observing satellites united scheduling[D]. Changsha: national university of defense technology,2009: 19-57.

[7]BIANCHESSI N, RIGHINI G. Planning and scheduling algorithms for the COSMO-SkyMed constellation[J]. Aerospace science amp; technology, 2008, 12(7): 535-544.

[8]BOTELHO S C, Alami R. M+: a scheme for multi-robot cooperation through negotiated task allocation and achievement[C]//1999 IEEE International Conference on Robotics and Automation. Detroit, USA, 1999, 2: 1234-1239.

[9]PENG Shuang, CHEN Hao, LIN Jun, et al. Multi-agent collaborative planning method of emergency mission based on scheme fusion strategy[C]//2014 IEEE Symposium on Computer Applications and Communications(SCAC). Weihai, China, 2014: 87-92.

[10]FENG Peng, CHEN Hao, PENG Shuang, et al. A method of distributed multi-satellite mission scheduling based on improved contract net protocol[C]//2015 11th International Conference on Natural Computation (ICNC). Zhangjiajie, China, 2015: 1062-1068.

[11]WANG Chong, JING Ning, et al. A distributed cooperative dynamic task planning algorithm for multiple satellites based on multi-agent hybrid learning[J].Chinese journal of aeronautics , 2011, 24(4):493-505.

[12]董云峰, 王興龍. 衛(wèi)星集群概念研究[J]. 航天器工程, 2012, 21(4):83-88.

DONG Yunfeng, WANG Xinglong. Research on conception of satellite cluster[J].Spacecraft engineering, 2012, 21(4): 83-88.

[13]MOORES J E, CARROLL K A, DESOUZE I, et al. The small reconnaissance of atmospheres mission platform concept, part 2: design of carrier spacecraft and atmospheric entry probes[J]. International journal of space science amp; engineering, 2014, 2(4): 345-364.

[14]HINCHEY M G, STERRITT R, ROUFF C. Swarms and swarm intelligence[J]. Computer, 2007, 40(4):111-113.

[15]DEKENS E, ENGELEN S, NOOMEN R. A satellite swarm for radio astronomy[J]. Acta astronautica, 2014, 102:321-331.

[16]OKIMOTO T, SCHWIND N, CLEMENT M, et al. How to form a task-oriented robust team[C]//Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems. Istanbul, Turkey, 2015: 395-403.

[17]HE L, IOERGER T R. A quantitative model of capabilities in multi-agent systems[C]//Proceeding of the International Conference on Artificial Intelligence(IC-AI) Las Vegas, USA , 2003: 730-736.

[18]CRAWFORD C, RAHAMAN Z, Sen S. Evaluating the efficiency of robust team formation algorithms[C]//International Conference on Autonomous Agents and Multiagent Systems. Tulsa, USA, 2016: 14-29.

楊舒, 女，1992年生，碩士研究生，主要研究方向?yàn)樾l(wèi)星任務(wù)規(guī)劃、多Agent協(xié)同規(guī)劃。

陳浩,男，1982年生，副教授，主要研究方向?yàn)橛嬎銠C(jī)智能、機(jī)器學(xué)習(xí)、衛(wèi)星智能規(guī)劃。

李軍,1973年生，教授，博士生導(dǎo)師，主要研究方向?yàn)榇髷?shù)據(jù)分析與處理、衛(wèi)星智能規(guī)劃和控制。

Agentteamformationapproachfortask-orientedearthobservationsatellite

YANG Shu, CHEN Hao, LI Jun, JING Ning

(School of Electronic Science and Engineering, National University of Defense Technology, Changsha 410073, China)

With the ongoing development of aerospace science and technology, satellite clusters consisting of many kinds of heterogeneous satellites have gradually appeared. Compared with traditional satellite systems, satellite clusters have some particular characteristics, including large-scale heterogeneous satellite platforms and various loads. It is difficult to use traditional methods to program satellite tasks. To address the problem of the formation of an agent team for task-oriented satellites, which is one of the key problems of satellite cluster task scheduling, in this study, we built a mathematical model, designed a precise searching algorithm based on branch and bound techniques, and analyzed the associated time complexity. To overcome the high time complexity that characterizes this precise algorithm, we introduced a heuristic pruning mechanism and designed three heuristic algorithms for the formation of the satellite team according to different task sequencing strategies. Finally, we conducted a series of experiments to analyze the performances of the precise search algorithm developed for the satellite team and the heuristic pruning search algorithm and demonstrated the effectiveness and practicability of both the proposed algorithms.

Agent team formation; earth observing satellite cluster; branch and bound; heuristic algorithm; pruning tactics; task sequencing strategy; task scheduling on satellite; time complexity

10.11992/tis.201706017

http://kns.cnki.net/kcms/detail/23.1538.TP.20170831.1058.008.html

TP391

A

1673-4785(2017)05-0653-08

中文引用格式：楊舒，陳浩，李軍，等.一種面向任務(wù)的對地觀測衛(wèi)星Agent團(tuán)隊(duì)構(gòu)建方法J.智能系統(tǒng)學(xué)報， 2017, 12(5): 653-660.

英文引用格式：YANGShu，CHENHao，LIJun，etal.Agentteamformationapproachfortask-orientedearthobservationsatelliteJ.CAAItransactionsonintelligentsystems, 2017, 12(5): 653-660.

2017-06-07. < class="emphasis_bold">網(wǎng)絡(luò)出版日期

日期：2017-08-31.

國家自然科學(xué)基金項(xiàng)目(61101184; 61174159).

陳浩. E-mail：hchen@nudt.edu.cn.