王雨琦 王海強(qiáng) 劉丹 仲小清 韓笑冬

1．中國(guó)空間技術(shù)研究院通信與導(dǎo)航衛(wèi)星總體部北京100094 2．鵬城實(shí)驗(yàn)室廣東深圳518000

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

遙感任務(wù)規(guī)劃問(wèn)題是對(duì)衛(wèi)星觀(guān)測(cè)任務(wù)的選擇和調(diào)度[3].衛(wèi)星在飛行過(guò)程中按時(shí)序有多個(gè)互斥的任務(wù),其目標(biāo)是在滿(mǎn)足所有復(fù)雜運(yùn)行約束的前提下,需要規(guī)劃執(zhí)行哪些觀(guān)測(cè)任務(wù)來(lái)獲得最大收益.任務(wù)規(guī)劃問(wèn)題[4]在近20年的研究中在衛(wèi)星與無(wú)人機(jī)領(lǐng)域[5]得到了學(xué)界廣泛的關(guān)注.

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

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

1 遙感任務(wù)規(guī)劃問(wèn)題

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

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

1.1 變量符號(hào)定義

為了便于模型描述,給出了建模過(guò)程中應(yīng)用的所有變量符號(hào)及其含義:

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

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

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

k為軌道編號(hào),k∈Oj,j∈S.

Θjk為候選觀(guān)測(cè)任務(wù)集合,k∈Oj,j∈S.

p,q為觀(guān)測(cè)任務(wù)編號(hào),p,q∈Θjk.

ρjkp為軌道k∈Oj,j∈S上任務(wù)p的觀(guān)測(cè)收益.

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

sjk,ejk為任務(wù)開(kāi)始時(shí)間sjk和任務(wù)結(jié)束時(shí)間ejk,k∈Oj,j∈S.

Vp代表以任務(wù)p的目標(biāo)為中心目標(biāo)時(shí)所有在中心目標(biāo)視場(chǎng)內(nèi)目標(biāo)的集合.

1.2 任務(wù)規(guī)劃問(wèn)題建模

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

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

滿(mǎn)足約束

其中,ρjkp為k∈Oj軌道上任務(wù)p對(duì)應(yīng)的目標(biāo)收益,Θjk∪s= Θjk∪sjk,Θjk∪e= Θjk∪ejk,Θjk為k∈Oj軌道上與觀(guān)測(cè)目標(biāo)i相關(guān)的任務(wù)集.

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

1.3 中心收益函數(shù)

考慮到遙感衛(wèi)星觀(guān)測(cè)時(shí)成像視場(chǎng)角投影到地面上會(huì)形成一個(gè)對(duì)地視場(chǎng),位于視場(chǎng)內(nèi)的目標(biāo)都能通過(guò)相機(jī)進(jìn)行一次成像[14],因此,定義了中心目標(biāo)收益函數(shù)作為效用函數(shù)對(duì)觀(guān)測(cè)收益進(jìn)行評(píng)價(jià).即

其中,Vp代表以任務(wù)p的目標(biāo)為中心目標(biāo)時(shí)所有在中心目標(biāo)視場(chǎng)內(nèi)目標(biāo)pl的集合(包括中心目標(biāo)本身).

圖2 給出了中心目標(biāo)對(duì)應(yīng)相機(jī)視場(chǎng)中可累加收益任務(wù)目標(biāo)的示意圖,這里作了一定的簡(jiǎn)化,將相機(jī)視場(chǎng)內(nèi)接圓內(nèi)的任務(wù)目標(biāo)記為可累加收益的目標(biāo).

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

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

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

2.1 并查集定義

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

定義1(并查集).在無(wú)向圖G(V,E)中,將元素映射在點(diǎn)集V上,通過(guò)兩個(gè)點(diǎn)之間的邊連通E的方式來(lái)表示兩個(gè)元素關(guān)系互斥,由相應(yīng)元素組成的集合稱(chēng)為并查集.

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

圖3 并查集Fig.3 Disjoint set

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

定義3(完全最小并查集).最小并查集中元素兩兩互斥,即該集合無(wú)向圖中的所有元素滿(mǎn)足全連通關(guān)系,該并查集稱(chēng)為完全最小并查集.

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

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

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

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

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

2.2 算法描述

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

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

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

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

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

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

2.3 算法復(fù)雜度

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

3 算例仿真

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

3.1 算例設(shè)計(jì)

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

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

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

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

3.2 結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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