楊舒，陳浩，李軍，景寧

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

一種面向任務的對地觀測衛(wèi)星Agent團隊構建方法

楊舒，陳浩，李軍，景寧

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

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

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

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

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

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

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

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

隨著航天科技的飛速發(fā)展，逐漸出現了由多種異構衛(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èi)星團隊，簡稱衛(wèi)星團隊)，即可完成一組對地觀測任務。

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

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

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

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

1 問題描述

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

1.1 符號定義

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

1.2 目標函數

面向任務的對地觀測衛(wèi)星團隊構建問題的目標是從衛(wèi)星集群中找到一個能夠勝任這些任務的衛(wèi)星團隊，并使團隊的總代價最小，即當team∈TEAMM時：

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

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

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

在團隊構建過程中，衛(wèi)星使用代價隨著承擔任務數增多，而不斷增長。

表1 符號定義

1.3 約束模型

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

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

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

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

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

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

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

2 基于分枝限界的衛(wèi)星任務團隊構建算法

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

算法1 TFCA

功能基于分枝限界思想的團隊構建算法的主算法；

輸入TaskSet, SatSet, 初始的空團隊team0；

1)Begin

5)End

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

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

算法2 TFOfEachTask

功能從第m個任務開始搜索構建團隊的迭代算法。

北大語料庫中“吃虧”用例共1578個，其中多數充任謂語成分，也可作賓語(如：怕吃虧)，充任主語的最具代表性的例子是“吃虧是?！?共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的團隊的迭代算法；

輸入n, team, teamSet,m；

輸出當前team下能完成taskm的團隊集合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尋找在當前team下，能完成taskm的所有團隊的迭代算法。在當前team的情況，依次判斷每顆衛(wèi)星Satn能否完成taskm，如果能完成，則生成新團隊team1，并將該team1加入teamSet。

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

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

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

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

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

0lt;εlt;1記為team1lt;team2，則剪去team1這個團隊所在的結點。其中，i是TEAMi中的每個團隊完成的任務個數，ε根據衛(wèi)星初始狀態(tài)調整，盡量為團隊挑選承擔任務數少的衛(wèi)星。

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

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

算法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的輸入順序可能會影響算法最終輸出結果。如果在隨機的任務集合中，代價小的任務排在前面，HTFA將會優(yōu)先挑選代價小的衛(wèi)星執(zhí)行該任務，代價大的任務只能選擇代價大的衛(wèi)星，會使最終構建出的衛(wèi)星團隊的代價偏大。為此，對輸入任務集合TaskSet進行排序：

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

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

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

4 實驗與分析

為了驗證TFCA算法、HTFA-S算法、HTFA-C算法、HTFA-RC算法的性能，設計了4組實驗。

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

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

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

實驗1 隨機生成6組任務，在10顆衛(wèi)星構成的小規(guī)模集群上采用TFCA、HTFA-S、HTFA-C、HTFA-RC構建團隊，比較4種算法的性能。實驗結果如圖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算法構建的團隊效果接近TFCA算法。HTFA-S算法由于任務輸入的無序性，在大部分情況下構建團隊的效果比HTFA-RC、HTFA-C算法差。表2展示了4種算法的時間特性，TFCA算法的運行時間隨著任務的增多，呈現指數增長趨勢，HTFA-S、HTFA-RC、HTFA-C算法的運行時間增長緩慢。

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

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

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

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

實驗3 隨機生成一組由10個任務構成的任務集合，在不同規(guī)模的衛(wèi)星集群上構建團隊，比較TFCA、HTFA-S、HTFA-C、HTFA-RC算法性能，實驗結果如表3、圖4所示。

表34種算法的運行時間對比

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

實驗4 為了進一步比較3種啟發(fā)式算法在大規(guī)模衛(wèi)星集群上的性能，隨機生成一組由20個任務組成的任務集合，在10、20、30、40、50顆衛(wèi)星組成的衛(wèi)星集群上進行實驗。由于TFCA算法運行時間太長(在20顆衛(wèi)星組成的集群上，對20個任務構建團隊時，運行超過12 h仍然不能給出有效結果)，我們僅對比HTFA-S、HTFA-RC和HTFA-C的實驗結果，如圖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)星集群上運行時間Fig.6 Time comparison of three algorithms in different scales of SC

圖6中隨著衛(wèi)星規(guī)模的增大，對同一組任務構建的團隊代價逐漸減少，而構建團隊的時間逐漸增大。這是因為規(guī)模增大，可以挑選多個衛(wèi)星承擔任務，無需一個衛(wèi)星承擔多個任務，團隊代價隨之降低。

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

5 結束語

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

在下一步的工作中，我們將從理論上分析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)星任務規(guī)劃問題研究述評[J].系統(tǒng)工程與電子技術, 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)星聯合任務規(guī)劃關鍵技術研究[D]. 長沙：國防科技大學, 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年生，碩士研究生，主要研究方向為衛(wèi)星任務規(guī)劃、多Agent協(xié)同規(guī)劃。

陳浩,男，1982年生，副教授，主要研究方向為計算機智能、機器學習、衛(wèi)星智能規(guī)劃。

李軍,1973年生，教授，博士生導師，主要研究方向為大數據分析與處理、衛(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èi)星Agent團隊構建方法J.智能系統(tǒng)學報， 2017, 12(5): 653-660.

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

2017-06-07. < class="emphasis_bold">網絡出版日期

日期：2017-08-31.

國家自然科學基金項目(61101184; 61174159).

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