徐崇彥，何川東，鄒冬冬

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

0 引言

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

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

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

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

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

圖1 目標的成像時刻示意

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

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

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

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

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

1.3 優(yōu)化目標

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

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

P=v1×f1+v2×f2=

(1)

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

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

(2)

1.4 約束條件分析

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

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

(3)

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

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

(4)

(5)

1.4.3 最大連續(xù)工作時長約束

前后相鄰相機開機到相機關(guān)機的間隔時間須小于最大連續(xù)工作時長約束。

(6)

1.4.4 數(shù)傳約束

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

(7)

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

(8)

1.4.5 固存容量約束

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

(9)

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

1.4.6 能源約束

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

(10)

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

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

2 算法研究

2.1 貪婪算法基本思想

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

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

2.2.1 目標選擇規(guī)則

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

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

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

③ 判斷機動角度，優(yōu)先選擇由前一目標到當前目標機動角度較小的；

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

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

針對可以俯仰成像的目標在較長可視窗口范圍內(nèi)，指導按照何種原則選擇成像時間。

① 當前目標與前后目標沒有沖突，則優(yōu)先選擇俯仰角最小的時刻為該目標的中心成像時刻；

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

2.2.3 前瞻處理規(guī)則

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

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

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

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

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

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

③ 對于回放接收站，依次安排成像目標進行回放，直到該接收站時間被用盡或沒有目標需要回放。

2.2.5 能源補充規(guī)則

為了快速補充衛(wèi)星能源，當衛(wèi)星在陽照區(qū)且空閑時間超過一定時限，安排衛(wèi)星對日定向進行能源補充。

2.2.6 固存擦除規(guī)則

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

2.3 算法流程

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

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

步驟2：根據(jù)成像目標、接收站的開始時間進行排序，形成候選任務(wù)隊列M1，S1；

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

步驟5：生成接收方案：依次對候選接收任務(wù)隊列S1中的接收任務(wù)進行安排，并考慮各接收站接收任務(wù)均衡原則，直到無待傳輸?shù)某上衲繕嘶蛘弋斍敖邮照緹o剩余接收時間，此時，得到初步任務(wù)規(guī)劃方案，即目標序列M4∈M3，接收序列S2∈S1；

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

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

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

3 算法仿真實驗

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

表1 周期為12 h實驗情況

表2 周期為24 h實驗情況

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

4 結(jié)束語

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