基于貪婪策略的靈巧衛(wèi)星啟發(fā)式任務(wù)規(guī)劃算法

徐崇彥，何川東，鄒冬冬

(北京市遙感信息研究所，北京 100192)

0 引言

近年來(lái)，高分辨率靈巧型衛(wèi)星[1-2]已成為成像衛(wèi)星應(yīng)用的主流，比如美國(guó)的IKONOS-2、Quick Bird、WorldView-1衛(wèi)星、俄羅斯的Topsat衛(wèi)星、法國(guó)的SPOT-5(HRG)、PLEIADES星座和以色列的EROS-2衛(wèi)星等，這些靈巧衛(wèi)星具有大范圍快速姿態(tài)機(jī)動(dòng)能力，可實(shí)現(xiàn)側(cè)視、前視、后視等靈活成像動(dòng)作，已經(jīng)在軍民重要領(lǐng)域發(fā)揮了巨大作用，并顯現(xiàn)出更加廣闊的應(yīng)用前景。

靈巧衛(wèi)星在功能和性能上大幅提高、應(yīng)用靈活性不斷提升的同時(shí)，也給衛(wèi)星任務(wù)規(guī)劃帶來(lái)了新的挑戰(zhàn)。國(guó)內(nèi)外學(xué)者對(duì)靈巧衛(wèi)星任務(wù)規(guī)劃問(wèn)題進(jìn)行了相關(guān)研究，如針對(duì)法國(guó)PLEIADES靈巧衛(wèi)星，歐空局的Lemaitre[3-4]等將問(wèn)題簡(jiǎn)化為單星單圈次的任務(wù)選擇與調(diào)度問(wèn)題；DJamal Habet[5-6]等采用禁忌搜索來(lái)解決靈巧衛(wèi)星任務(wù)規(guī)劃問(wèn)題，并通過(guò)約束傳播策略來(lái)保證鄰域搜索時(shí)的一致性；國(guó)內(nèi)的陳宇寧[7]、郭浩[8]、嚴(yán)珍珍[9]等通過(guò)分析靈巧衛(wèi)星任務(wù)規(guī)劃問(wèn)題特點(diǎn)，設(shè)計(jì)了基于蟻群算法的靈巧衛(wèi)星任務(wù)規(guī)劃方法；向仍湘[10]針對(duì)不同問(wèn)題規(guī)模，提出了基于模擬退火遺傳算法的大規(guī)模問(wèn)題求解算法和基于列生成算法的小規(guī)模問(wèn)題求解算法。上述研究中，從不同側(cè)面解決了靈巧衛(wèi)星任務(wù)規(guī)劃問(wèn)題，但是，為了問(wèn)題求解方便，規(guī)劃模型都做了一定簡(jiǎn)化。貪婪算法由于其無(wú)需迭代、求解速度快的特點(diǎn)，常被用來(lái)解決最優(yōu)化問(wèn)題，本文從工程應(yīng)用角度出發(fā)，全面考慮衛(wèi)星約束和實(shí)際應(yīng)用特點(diǎn)，設(shè)計(jì)了基于貪婪策略的靈巧衛(wèi)星啟發(fā)式任務(wù)規(guī)劃算法。

1 靈巧衛(wèi)星任務(wù)規(guī)劃問(wèn)題及模型

1.1 靈巧衛(wèi)星成像特點(diǎn)

靈巧衛(wèi)星利用其俯仰能力可以在一個(gè)較長(zhǎng)的時(shí)間窗口內(nèi)自由選擇成像時(shí)間，對(duì)單個(gè)目標(biāo)可進(jìn)行成像的機(jī)會(huì)增多。如圖1所示，非靈巧衛(wèi)星基本僅具備側(cè)擺的方式成像，因此對(duì)目標(biāo)的成像時(shí)刻固定為一點(diǎn)；靈巧衛(wèi)星具備星下點(diǎn)一定角度范圍內(nèi)任意角度成像的能力，拓寬了對(duì)單個(gè)目標(biāo)的可見(jiàn)時(shí)間窗口，因此對(duì)單個(gè)目標(biāo)觀測(cè)的成像時(shí)刻可在較長(zhǎng)成像范圍內(nèi)任選。靈巧衛(wèi)星還可以在一次可見(jiàn)窗口內(nèi)通過(guò)快速姿態(tài)機(jī)動(dòng)對(duì)同一目標(biāo)實(shí)施連續(xù)多次成像，實(shí)現(xiàn)同軌立體成像功能，進(jìn)一步增強(qiáng)了衛(wèi)星的成像能力。

圖1 目標(biāo)的成像時(shí)刻示意

1.2 靈巧衛(wèi)星任務(wù)規(guī)劃特點(diǎn)

靈巧衛(wèi)星任務(wù)規(guī)劃具有以下特點(diǎn)：

① 觀測(cè)目標(biāo)成像時(shí)間選取靈活。靈巧衛(wèi)星利用俯仰能力使成像窗口可以在一個(gè)較長(zhǎng)的可視窗口內(nèi)自由地選擇，這種自由度使靈巧衛(wèi)星能夠執(zhí)行更多的成像任務(wù)，這是靈巧衛(wèi)星最大的優(yōu)點(diǎn)。

② 衛(wèi)星姿態(tài)機(jī)動(dòng)時(shí)間與前后目標(biāo)成像時(shí)間的選擇緊密相關(guān)。由于衛(wèi)星運(yùn)行過(guò)程中姿態(tài)的變化，靈巧衛(wèi)星對(duì)前后目標(biāo)的不同成像時(shí)刻選擇，決定了對(duì)前后目標(biāo)的不同成像角度；不同成像角度決定了衛(wèi)星前后的姿態(tài)機(jī)動(dòng)位置不一樣，所以，也決定了不同的衛(wèi)星姿態(tài)機(jī)動(dòng)時(shí)間。

③ 靈巧衛(wèi)星任務(wù)規(guī)劃增加了衛(wèi)星動(dòng)作序列規(guī)劃[11-12]，擴(kuò)大了搜索空間、增加了難度。靈巧衛(wèi)星有效載荷動(dòng)作可以靈活地組合使用，比如對(duì)于非靈巧衛(wèi)星完成記錄時(shí)，衛(wèi)星動(dòng)作序列可以簡(jiǎn)單的理解為：相機(jī)開(kāi)機(jī)—記錄開(kāi)始—記錄停止—相機(jī)關(guān)機(jī)，這些動(dòng)作必須全部執(zhí)行，而靈巧衛(wèi)星可以根據(jù)實(shí)際情況，只安排部分動(dòng)作執(zhí)行、部分動(dòng)作不執(zhí)行，這就顯著增加了任務(wù)規(guī)劃難度。

1.3 優(yōu)化目標(biāo)

任務(wù)規(guī)劃的優(yōu)化目標(biāo)一般可以設(shè)為規(guī)劃方案的收益最大，目前，在衛(wèi)星數(shù)量有限、成像需求較多的情況下，規(guī)劃方案的收益可以定義為：成像目標(biāo)數(shù)量盡可能多、成像目標(biāo)重要性等級(jí)盡可能高，這2個(gè)因素可以采用加權(quán)和得到規(guī)劃方案的收益評(píng)價(jià)值。

設(shè)規(guī)劃方案的收益函數(shù)表示為：

P=v1×f1+v2×f2=

(1)

式中，v1、v2分別為目標(biāo)數(shù)量、目標(biāo)等級(jí)對(duì)應(yīng)的準(zhǔn)則重要性權(quán)值；f1，f2分別為目標(biāo)數(shù)量、目標(biāo)重要性準(zhǔn)則評(píng)價(jià)值；M為成像目標(biāo)集合；N(i)為成像目標(biāo)序列中成像節(jié)點(diǎn)i(一個(gè)衛(wèi)星開(kāi)關(guān)機(jī)時(shí)段稱之為一個(gè)成像節(jié)點(diǎn))所含地面目標(biāo)的數(shù)目；dg，dm分別表示最高、最低目標(biāo)等級(jí)，且dg

則規(guī)劃方案的優(yōu)化目標(biāo)為：

(2)

1.4 約束條件分析

1.4.1 姿態(tài)轉(zhuǎn)換時(shí)間約束

后一個(gè)目標(biāo)的成像開(kāi)始時(shí)間須大于前一個(gè)目標(biāo)的成像結(jié)束時(shí)間，加前一個(gè)目標(biāo)關(guān)機(jī)穩(wěn)定時(shí)間，加姿態(tài)轉(zhuǎn)換時(shí)間，加后一個(gè)目標(biāo)的開(kāi)機(jī)準(zhǔn)備時(shí)間。

(3)

1.4.2 任務(wù)間隔時(shí)間約束

前后目標(biāo)的成像間隔時(shí)間須大于衛(wèi)星載荷設(shè)備工作時(shí)間之和。

(4)

(5)

1.4.3 最大連續(xù)工作時(shí)長(zhǎng)約束

前后相鄰相機(jī)開(kāi)機(jī)到相機(jī)關(guān)機(jī)的間隔時(shí)間須小于最大連續(xù)工作時(shí)長(zhǎng)約束。

(6)

1.4.4 數(shù)傳約束

成像衛(wèi)星一般有多種不同數(shù)據(jù)壓縮比，不同數(shù)據(jù)壓縮比對(duì)應(yīng)的數(shù)據(jù)錄放比(記錄時(shí)長(zhǎng)與回放時(shí)長(zhǎng)之比)也不一樣，單次回放目標(biāo)的回放時(shí)長(zhǎng)之和須小于等于接收站最大接收時(shí)長(zhǎng)，

(7)

其次，單次規(guī)劃的所有目標(biāo)的回放時(shí)長(zhǎng)之和也必須小于等于所有接收站的最大接收時(shí)長(zhǎng)之和，

(8)

1.4.5 固存容量約束

不同數(shù)據(jù)壓縮比對(duì)應(yīng)的所需存儲(chǔ)容量也不一樣，2次固存擦除動(dòng)作之間所有目標(biāo)的存儲(chǔ)容量之和須小于衛(wèi)星最大固存容量。

(9)

式中，hi為目標(biāo)i的固存容量；H為衛(wèi)星總存儲(chǔ)容量。

1.4.6 能源約束

成像目標(biāo)的能量消耗加衛(wèi)星設(shè)備的長(zhǎng)期功耗，須小于衛(wèi)星初始能量加衛(wèi)星在光照區(qū)補(bǔ)充的能量之和，

(10)

式中，ei為目標(biāo)i的消耗能量；Ef為衛(wèi)星設(shè)備長(zhǎng)期功耗；Es為本次規(guī)劃時(shí)的衛(wèi)星初始能量；Ea為衛(wèi)星在光照區(qū)補(bǔ)充的能量。

這是個(gè)具有復(fù)雜約束的約束滿足、多目標(biāo)優(yōu)化問(wèn)題，完全搜索算法難以在合理的時(shí)間內(nèi)得到問(wèn)題的解，而貪婪搜索算法在大量實(shí)踐中被證明能有效求解該問(wèn)題。

2 算法研究

2.1 貪婪算法基本思想

貪婪算法是一種解決最優(yōu)化問(wèn)題的近似方法[13]，在對(duì)問(wèn)題求解時(shí)總是做出在當(dāng)前看來(lái)是最好的選擇，也就是說(shuō)所做出的是在某種意義上的局部最優(yōu)解。貪婪算法的關(guān)鍵在于貪婪準(zhǔn)則的設(shè)定[14]，它是決策的依據(jù)和標(biāo)準(zhǔn)，即在求解的每一步依據(jù)何種標(biāo)準(zhǔn)對(duì)變量進(jìn)行賦值。它無(wú)須迭代，不能保證最優(yōu)，但是它的時(shí)間性能最佳，對(duì)于一些大規(guī)模的任務(wù)規(guī)劃問(wèn)題或涉及復(fù)雜約束的規(guī)劃問(wèn)題，當(dāng)其它算法在有限時(shí)間內(nèi)無(wú)能為力時(shí)，貪婪算法無(wú)疑是一種不錯(cuò)的選擇[15]。

2.2 貪婪規(guī)則設(shè)計(jì)

2.2.1 目標(biāo)選擇規(guī)則

當(dāng)多個(gè)成像目標(biāo)不滿足衛(wèi)星某一約束時(shí)，指導(dǎo)按照何種順序選取目標(biāo)。主要考慮目標(biāo)等級(jí)、目標(biāo)數(shù)量、機(jī)動(dòng)角度和太陽(yáng)高度角等因素。

① 判斷目標(biāo)等級(jí)，優(yōu)先選擇目標(biāo)等級(jí)較高的；

② 判斷目標(biāo)數(shù)量，優(yōu)先選擇目標(biāo)數(shù)量較多的；

③ 判斷機(jī)動(dòng)角度，優(yōu)先選擇由前一目標(biāo)到當(dāng)前目標(biāo)機(jī)動(dòng)角度較小的；

④ 判斷太陽(yáng)高度角，優(yōu)先選擇太陽(yáng)高度角較大的。

2.2.2 成像時(shí)間選擇規(guī)則

針對(duì)可以俯仰成像的目標(biāo)在較長(zhǎng)可視窗口范圍內(nèi)，指導(dǎo)按照何種原則選擇成像時(shí)間。

① 當(dāng)前目標(biāo)與前后目標(biāo)沒(méi)有沖突，則優(yōu)先選擇俯仰角最小的時(shí)刻為該目標(biāo)的中心成像時(shí)刻；

② 如果當(dāng)前目標(biāo)與已安排目標(biāo)存在沖突，則在當(dāng)前目標(biāo)可視窗口范圍內(nèi)從前向后進(jìn)行滑動(dòng)選擇，最早不存在沖突的時(shí)刻作為當(dāng)前目標(biāo)的成像開(kāi)始時(shí)間。

2.2.3 前瞻處理規(guī)則

對(duì)于密集分布的目標(biāo)，當(dāng)任務(wù)連續(xù)沖突且優(yōu)先級(jí)依次上升的時(shí)候，可能出現(xiàn)只有連續(xù)沖突的最后一個(gè)任務(wù)被安排，前面的任務(wù)全部被舍棄的情況，此時(shí)，加入前瞻處理方法。

① 前瞻步長(zhǎng)：就是在候選任務(wù)隊(duì)列中前瞻任務(wù)的數(shù)量，前瞻步長(zhǎng)是可變的。如果當(dāng)前目標(biāo)與后續(xù)目標(biāo)可視窗口間隔大于衛(wèi)星最大機(jī)動(dòng)時(shí)間，則結(jié)束前瞻。

② 回滾操作：當(dāng)前任務(wù)安排后，在前瞻范圍內(nèi)再次從后向前判斷前面的目標(biāo)是否能夠安排。

2.2.4 接收方案生成規(guī)則

① 優(yōu)先將指定接收站的目標(biāo)安排給對(duì)應(yīng)接收站；

② 能實(shí)傳近實(shí)傳的目標(biāo)優(yōu)先安排相應(yīng)站為實(shí)傳站；

③ 對(duì)于回放接收站，依次安排成像目標(biāo)進(jìn)行回放，直到該接收站時(shí)間被用盡或沒(méi)有目標(biāo)需要回放。

2.2.5 能源補(bǔ)充規(guī)則

為了快速補(bǔ)充衛(wèi)星能源，當(dāng)衛(wèi)星在陽(yáng)照區(qū)且空閑時(shí)間超過(guò)一定時(shí)限，安排衛(wèi)星對(duì)日定向進(jìn)行能源補(bǔ)充。

2.2.6 固存擦除規(guī)則

為了便于固存管理和提高固存使用效率，每次回放后如果星上記錄數(shù)據(jù)全部回放完畢，則進(jìn)行固存擦除。

2.3 算法流程

任務(wù)規(guī)劃算法總體流程如圖2所示。

圖2 任務(wù)規(guī)劃算法總體流程

步驟2：根據(jù)成像目標(biāo)、接收站的開(kāi)始時(shí)間進(jìn)行排序，形成候選任務(wù)隊(duì)列M1，S1；

步驟4：對(duì)目標(biāo)序列M2檢驗(yàn)相機(jī)工作時(shí)間、單圈側(cè)擺次數(shù)等約束，如果不滿足約束則根據(jù)目標(biāo)選擇規(guī)則進(jìn)行沖突消解，生成目標(biāo)序列M3∈M2；

步驟5：生成接收方案：依次對(duì)候選接收任務(wù)隊(duì)列S1中的接收任務(wù)進(jìn)行安排，并考慮各接收站接收任務(wù)均衡原則，直到無(wú)待傳輸?shù)某上衲繕?biāo)或者當(dāng)前接收站無(wú)剩余接收時(shí)間，此時(shí)，得到初步任務(wù)規(guī)劃方案，即目標(biāo)序列M4∈M3，接收序列S2∈S1；

步驟6：生成接收方案后再次檢驗(yàn)衛(wèi)星約束，如工作時(shí)間約束、固存約束等，如果不滿足約束則根據(jù)目標(biāo)選擇規(guī)則進(jìn)行沖突消解，得到目標(biāo)序列M5∈M4，轉(zhuǎn)步驟5；否則轉(zhuǎn)步驟7，此時(shí)M5=M4；

步驟7：根據(jù)能源補(bǔ)充規(guī)則與動(dòng)作序列組合使用規(guī)則，添加對(duì)日定向、對(duì)地定向動(dòng)作，生成衛(wèi)星動(dòng)作序列A；

步驟8：檢驗(yàn)衛(wèi)星能源約束，如果不滿足約束則根據(jù)目標(biāo)選擇規(guī)則進(jìn)行沖突消解，得到目標(biāo)序列M6∈M5，轉(zhuǎn)步驟5；否則(M6=M5)，生成最終任務(wù)規(guī)劃方案(包括目標(biāo)序列M6、接收序列S2與衛(wèi)星動(dòng)作序列A)，算法結(jié)束。

3 算法仿真實(shí)驗(yàn)

目前，各個(gè)國(guó)家成像衛(wèi)星的使用約束不盡相同，在衛(wèi)星任務(wù)規(guī)劃領(lǐng)域尚沒(méi)有公認(rèn)的benchmark測(cè)試問(wèn)題集，很難與現(xiàn)有的解決方法進(jìn)行比較[16]。本文參考法國(guó)PLEIADES衛(wèi)星的主要參數(shù)，其主要參數(shù)為：空間分辨率全色0.5 m，多光譜2 m；標(biāo)準(zhǔn)幅寬20 km；軌道高度694 km，軌道周期98.64 min/圈；側(cè)視角度±30°；每8 h制定并更新成像計(jì)劃，每天3次。分別模擬規(guī)劃周期為12 h與24 h，基于STK軟件分別生成10組，共20組實(shí)驗(yàn)數(shù)據(jù)，展示本算法的有效性。詳細(xì)實(shí)驗(yàn)情況如表1和表2所示。

表1 周期為12 h實(shí)驗(yàn)情況

表2 周期為24 h實(shí)驗(yàn)情況

由實(shí)驗(yàn)結(jié)果可以看出，20組實(shí)驗(yàn)數(shù)據(jù)中成像目標(biāo)平均安排率為84.15%，算法平均耗時(shí)為11.4 s。未安排目標(biāo)原因主要有2點(diǎn)：① 由于目標(biāo)密集分布，衛(wèi)星機(jī)動(dòng)能力不足導(dǎo)致目標(biāo)沒(méi)有安排，在20組測(cè)試數(shù)據(jù)中均有此原因，并且在目標(biāo)數(shù)較少的時(shí)候該因素是未安排目標(biāo)的主要原因；② 由于模擬的國(guó)境內(nèi)地面站由于地理位置限制，導(dǎo)致數(shù)據(jù)傳輸有一定時(shí)間延遲，同時(shí)，衛(wèi)星存儲(chǔ)容量不足從而導(dǎo)致目標(biāo)沒(méi)有安排；并且，隨著目標(biāo)數(shù)量增加，該因素成為未安排目標(biāo)的顯著因素之一。綜上可知，本文算法可以處理靈巧衛(wèi)星的所有約束條件、適應(yīng)不同模式的成像目標(biāo)(點(diǎn)目標(biāo)、立體成像目標(biāo))，生成衛(wèi)星動(dòng)作序列與任務(wù)規(guī)劃方案，算法耗時(shí)較短、成像目標(biāo)落實(shí)率較高，能夠滿足工程應(yīng)用要求。

4 結(jié)束語(yǔ)

本文針對(duì)新一代靈巧衛(wèi)星對(duì)地成像任務(wù)規(guī)劃問(wèn)題，針對(duì)靈巧衛(wèi)星機(jī)動(dòng)能力強(qiáng)、衛(wèi)星載荷動(dòng)作使用靈活的特點(diǎn)，通過(guò)分析靈巧衛(wèi)星任務(wù)規(guī)劃特點(diǎn)、優(yōu)化目標(biāo)與約束條件，建立了靈巧衛(wèi)星任務(wù)規(guī)劃模型；基于貪婪思想，運(yùn)用專家知識(shí)的任務(wù)規(guī)劃啟發(fā)式規(guī)則，建立了基于貪婪策略的靈巧衛(wèi)星任務(wù)規(guī)劃算法。該算法能針對(duì)靈巧衛(wèi)星多種工作模式，綜合考慮成像目標(biāo)與衛(wèi)星動(dòng)作序列，在較短時(shí)間內(nèi)生成任務(wù)規(guī)劃方案，并通過(guò)仿真實(shí)例驗(yàn)證了模型和算法的有效性。