基于并查集搜索的衛(wèi)星任務規(guī)劃方法

王雨琦 王海強 劉丹 仲小清 韓笑冬

1．中國空間技術研究院通信與導航衛(wèi)星總體部北京100094 2．鵬城實驗室廣東深圳518000

遙感衛(wèi)星的主要目的是通過星載相機收集地面圖像[1],由于其觀測覆蓋范圍大等優(yōu)點,在災害監(jiān)測、環(huán)境監(jiān)測和資源勘探等領域得到了廣泛的應用[2].

遙感任務規(guī)劃問題是對衛(wèi)星觀測任務的選擇和調度[3].衛(wèi)星在飛行過程中按時序有多個互斥的任務,其目標是在滿足所有復雜運行約束的前提下,需要規(guī)劃執(zhí)行哪些觀測任務來獲得最大收益.任務規(guī)劃問題[4]在近20年的研究中在衛(wèi)星與無人機領域[5]得到了學界廣泛的關注.

衛(wèi)星任務規(guī)劃問題最初在單一、敏捷航天器中得到了廣泛的研究,近年來擴展到多衛(wèi)星星座任務規(guī)劃問題的研究[6].Gabrel 等[7]于1997年首次提出了遙感任務規(guī)劃問題的概念,對連續(xù)的可見時間窗口進行了離散化,在有向無環(huán)圖上建立了線性模型,在此基礎上設計了一種分支定界(Branch and Bound,B&B)方法來解決實例中的問題.Valicka 等[8]在該問題中引入了一種新的確定性混合整數(shù)線性規(guī)劃(Mixed Integer Linear Programming,MILP)模型,采用相對較大的時間步長使模型變得易于處理,通過商業(yè)求解器得到的上界來計算最優(yōu)間隔,從而保證解的最優(yōu).Chu 等[9]假設一些運行約束如存儲和能量約束在某些情況下不是緊約束,因此,問題中只剩下時間窗口和任務過渡約束.Chu 針對簡化后的模型,提出了一種B&B 算法,該算法能很好地獲得最優(yōu)解.在提出的B&B 框架中,首先采用預先構造的方法獲得高質量的下界,并結合3 種互補的剪枝策略來加速算法的執(zhí)行.根據(jù)計算結果,提出的精確方法可以解決多達55 個目標規(guī)模的計算.進一步考慮采用雙星觀測方案,建立了雙星自主模型,并提出了任意時刻B&B 方法,在范圍500 km?2 000 km 海域的真實場景對25 個目標進行觀測任務調度,試驗對30 顆高分辨率衛(wèi)星的自主調度進行了演示.Kucuk等[10]考慮到實際操作中的復雜約束條件,建立了單星遙感任務規(guī)劃問題的約束規(guī)劃模型,并使用商業(yè)求解器求解,根據(jù)仿真結果,在55 個目標的情況下求解器半小時內得到了最優(yōu)解,然而該模型無法處理更多觀測目標的算例.

為了解決大規(guī)模任務規(guī)劃時傳統(tǒng)方法無法快速求解的問題,本文針對此類問題的求解優(yōu)化進行了創(chuàng)新,提出了一種基于圖模型的并查集搜索(Disjoint Set Search,DSS)方法,該方法將衛(wèi)星任務規(guī)劃問題等效為互斥圖模型,其中成像機會由節(jié)點表示,而連接頂點的邊表示兩個互斥的成像機會.在這個模型中,通過并查集搜索的方式將大規(guī)模的任務規(guī)劃問題簡化為若干個可解的子問題,在提升求解效率的同時保證了求解質量.

1 遙感任務規(guī)劃問題

圖1 展示了遙感衛(wèi)星不同時刻采集圖像過程的示意圖[11],其中,遙感衛(wèi)星的覆蓋視場沿著星下點軌跡以一定的覆蓋寬度移動,衛(wèi)星側擺的角度決定了視場覆蓋的寬度.

圖1 衛(wèi)星遙感示意圖Fig.1 Satellite remote sensing

1.1 變量符號定義

為了便于模型描述,給出了建模過程中應用的所有變量符號及其含義:

S為衛(wèi)星集合.

j為衛(wèi)星編號,j∈S.

Oj為衛(wèi)星j軌道集合,j∈S.

k為軌道編號,k∈Oj,j∈S.

Θjk為候選觀測任務集合,k∈Oj,j∈S.

p,q為觀測任務編號,p,q∈Θjk.

ρjkp為軌道k∈Oj,j∈S上任務p的觀測收益.

xjkpq為離散時間模型的0-1 決策變量,p,q∈Θjk,k∈Oj,j∈S.xjkpq= 1 表示任務q是任務p的接續(xù)觀測任務,反之xjkpq=0.

sjk,ejk為任務開始時間sjk和任務結束時間ejk,k∈Oj,j∈S.

Vp代表以任務p的目標為中心目標時所有在中心目標視場內目標的集合.

1.2 任務規(guī)劃問題建模

根據(jù)文獻[12] 中的方法,遙感任務規(guī)劃問題可以離散化為序列調度問題,即每個可見時間窗口對同一目標生成多個觀測任務.在k∈Oj軌道上定義二元決策變量xjkpq,其中,p和q都是觀測任務的編號,當任務q為任務p的直接連續(xù)觀測任務時,xjkpq= 1,否則,xjkpq= 0.同時在每個軌道上定義了任務開始和結束時刻sjk和ejk.

然后,在離散時間模型中應用預處理來檢查任務過渡約束[13].對于每個軌道k∈Oj,當且僅當任務p的觀測結束時間加上任務過渡時間不大于任務q的觀測開始時間時,決策變量xjkpq才能被定義.為了滿足任務過渡約束,與其他任務沖突的相應任務的決策變量需被排除.遙感任務規(guī)劃問題模型的目標函數(shù)建立為

滿足約束

其中,ρjkp為k∈Oj軌道上任務p對應的目標收益,Θjk∪s= Θjk∪sjk,Θjk∪e= Θjk∪ejk,Θjk為k∈Oj軌道上與觀測目標i相關的任務集.

目標函數(shù)式(1)是使所有目標的總觀測收益最大化.約束條件式(2)表明,對目標i∈T的調度觀測任務不能超過所需的最大觀測數(shù)Ni.決策變量xjkpq是在檢查任務過渡約束之前生成的,過渡約束用式(3)表示.

1.3 中心收益函數(shù)

考慮到遙感衛(wèi)星觀測時成像視場角投影到地面上會形成一個對地視場,位于視場內的目標都能通過相機進行一次成像[14],因此,定義了中心目標收益函數(shù)作為效用函數(shù)對觀測收益進行評價.即

其中,Vp代表以任務p的目標為中心目標時所有在中心目標視場內目標pl的集合(包括中心目標本身).

圖2 給出了中心目標對應相機視場中可累加收益任務目標的示意圖,這里作了一定的簡化,將相機視場內接圓內的任務目標記為可累加收益的目標.

圖2 中心目標與可累加收益目標示意圖Fig.2 A central target and accumulative revenue targets

2 并查集搜索任務規(guī)劃方法

基于并查集搜索的遙感任務規(guī)劃方法通過判定單星下任務間的互斥關系,將任務調度問題表示為一個稀疏的、無向的互斥圖,其中,成像機會由節(jié)點表示,而連接頂點的邊表示兩個互斥的成像機會,最后采用并查集搜索的方式,將大規(guī)模的任務規(guī)劃問題切分為多個子問題來并行求解.

2.1 并查集定義

并查集概念最早由Gabow 在1983年提出[15],是一種非常精巧而實用的數(shù)據(jù)結構,主要用于處理一些互斥元素集合的合并問題[16],針對多任務的遙感任務規(guī)劃問題的特點,對并查集的概念進行定義:

定義1(并查集).在無向圖G(V,E)中,將元素映射在點集V上,通過兩個點之間的邊連通E的方式來表示兩個元素關系互斥,由相應元素組成的集合稱為并查集.

圖3 展示了5 個元素組成的一個并查集D,其中元素1 與元素2、3 互斥,元素3 與元素4、5 互斥.

圖3 并查集Fig.3 Disjoint set

定義2(最小并查集).單個并查集中任意元素與其他任意元素都有連通.

定義3(完全最小并查集).最小并查集中元素兩兩互斥,即該集合無向圖中的所有元素滿足全連通關系,該并查集稱為完全最小并查集.

圖4 元素1、2、3、4 分別組成的一個完全最小并查集DC1(左圖)和元素5、6 組成的一個完全并查集DC2(右圖).若最小并查集為完全最小并查集,則該集合中的點和邊的數(shù)量關系滿足:

圖4 完全最小并查集Fig.4 Complete minimum disjoint set

定義4(非完全最小并查集).最小并查集中的元素并非兩兩互斥,將該最小并查集稱為非完全最小并查集.

圖5 分別展示了元素1、2、3、4 組成的非完全最小并查集DN1(左圖)和元素5、6、7 組成的非完全最小并查集DN2(右圖).若最小并查集為非完全最小并查集,則該集合中的點和邊的數(shù)量關系滿足:

圖5 非完全最小并查集Fig.5 Non-complete minimum disjoint set

2.2 算法描述

在確定待觀測任務的序列后,需要確定無法在同一顆衛(wèi)星的觀測周期內被同時規(guī)劃調度的任務對,因此,定義了規(guī)劃約束矩陣C,即C中的元素是決策變量xjkpq的補集.每個約束函數(shù)將兩個不同的任務p和q作為輸入(任務p發(fā)生在任務q之前),根據(jù)任務間的各種約束關系進行判定,并將其映射到Cpq,如果兩個任務在同一顆衛(wèi)星的觀測周期內能夠被同時規(guī)劃調度,則Cpq= 0,如果兩者互斥,則Cpq= 1.該方法的好處是在動作空間生成過程中應用集合約束降低了規(guī)劃問題的計算復雜度,規(guī)劃之前消除互斥的任務,可以顯著降低計算復雜度和規(guī)劃時間.

本文主要考慮了任務間衛(wèi)星姿態(tài)機動約束要求有足夠的時間在任務之間重新改變衛(wèi)星的姿態(tài),具體的算法流程如圖6所示,說明如下:

圖6 基于并查集搜索的任務規(guī)劃方法流程圖Fig.6 Mission planning method based on disjoint set search

1)排列.將待觀測任務按照時序先后進行排列,根據(jù)單星下任務間姿態(tài)機動時間滿足兩者被同一顆衛(wèi)星觀測的規(guī)劃約束矩陣,生成任務集合的互斥圖.

2)劃分.按照最小并查集原則對互斥圖模型進行并查集搜索,將圖模型劃分成多個最小并查集.

3)求解.分別判定各最小并查集是否為完全最小并查集,若為完全最小并查集,該集合中的任務兩兩互斥,選取最大優(yōu)先級任務直接輸出該子集的求解結果;若為非完全最小并查集,采用混合整數(shù)規(guī)劃求解器對該子集進行求解并輸出求解結果.當所有子集求解完成后輸出最終的規(guī)劃結果.

2.3 算法復雜度

考慮到采用并行計算的方式對模型進行求解,因此,算法時間復雜度為子集中元素最多的非完全最小并查集規(guī)劃結果的求解時間復雜度,時間復雜度為

3 算例仿真

通過5 個典型算例來驗證算法的有效性.仿真的計算環(huán)境為Windows 10 Intel(R)Core(TM)i7-10870H CPU @2.21 GHz,16 G RAM,編譯環(huán)境為Matlab 2018b.

3.1 算例設計

基于并查集搜索的遙感任務規(guī)劃方法,針對不同數(shù)量任務進行觀測任務規(guī)劃的算例仿真,并與MILP 方法進行驗證對比,遙感衛(wèi)星參數(shù)如表1所示.

表1 衛(wèi)星參數(shù)Table 1 Satellite parameters

仿真中任務目標坐標在200 km?1 000 km 隨機生成,且任務優(yōu)先級為[1,9]上的隨機整數(shù),等級越高優(yōu)先級越高,觀測傳感器的側擺角滿足視場內的所有目標,算例的任務數(shù)量規(guī)模、任務觀測時長及任務密度如表2所示.

表2 不同算例數(shù)據(jù)集Table 2 Different example datasets

3.2 結果分析

針對3.1 中給出的5 種規(guī)模的算例,分別采用MILP 算法和DSS 算法進行了蒙特卡洛仿真驗證,其中,兩種算法中的MILP 求解器均采用Matlab 自帶的intlinprog 函數(shù),求解器模型和參數(shù)配置相同,以保證結果對比的公平性.對每個算例采用100 次仿真取平均值的方法,以保證結果的客觀性,避免單次仿真偏差較大的影響,實驗結果如表3所示.

表3 兩種方法求解效率對比Table 3 The comparison of two methods

圖7、圖8 分別展示了算例1、算例2 的仿真結果,上圖是根據(jù)該算例中的任務互斥關系生成的并查集圖,下圖是該算例的任務規(guī)劃結果,其中,標記為紅色的目標是視場中心目標,黑色圓圈區(qū)域代表相機成像視場內接圓.可以看出在低任務密度的情況下,相比于MILP 算法,DSS 算法在效率提升40%～45%的同時能獲得同等的最大規(guī)劃收益.

圖7 任務數(shù)量50 的并查集圖和規(guī)劃結果Fig.7 Disjoint set graph and planning result of 50 targets

圖8 任務數(shù)量100 的并查集和規(guī)劃結果Fig.8 Disjoint set and planning result of 100 targets

圖9 展示了算例3 的仿真結果,上圖是根據(jù)該算例中的任務互斥關系生成的并查集圖,下圖是該算例的任務規(guī)劃結果.可以看出在中任務密度的情況下,DSS 方法的求解效率能夠提升28.1%.

結合圖7 ～圖9 可以看出,在任務密度不高的情況下,DSS 算法按照最小并查集的原則整個任務集合被劃分為若干個子集,之后并行求解子集時整體的計算復雜度為元素最多的子集求解的計算復雜度,而MILP 算法的計算復雜度涉及整個任務集合,因此,求解的計算復雜度遠大于DSS 算法.

圖9 任務數(shù)量200 的并查集和規(guī)劃結果Fig.9 Disjoint set and planning result of 200 targets

圖10、圖11 展示了算例4、算例5 中高任務密度的情況下的結果,上圖是根據(jù)該算例中的任務互斥關系生成的并查集圖,下圖是該算例的任務規(guī)劃結果.可以看到獲得同等收益的同時效率的優(yōu)化結果不是很顯著,主要原因是DSS 算法并沒有能夠將任務集合拆分開來,因此,求解效率與MILP 算法幾乎相同.

圖10 任務數(shù)量300 的并查集和規(guī)劃結果Fig.10 Disjoint set and planning result of 300 targets

圖11 任務數(shù)量500 的并查集和規(guī)劃結果Fig.11 Disjoint set and planning result of 500 targets

4 結論

研究了衛(wèi)星大規(guī)模任務規(guī)劃的問題,將任務調度問題表示為一個稀疏的、無向的互斥圖;采用化整為零的思路,提出了DSS 算法,通過并查集搜索的方式將大規(guī)模的任務規(guī)劃問題簡化為若干個可解的子問題;最后進行仿真,驗證了DSS 算法的有效性,DSS 算法在提升求解效率的同時保證了求解質量,為衛(wèi)星任務規(guī)劃這類組合優(yōu)化問題提供了求解思路.下一步研究將在此基礎上開展多星情況下的任務規(guī)劃方法研究,以支撐未來巨型低軌星座的遙感任務規(guī)劃的需求.