基于貪婪策略的靈巧衛星啟發式任務規劃算法

徐崇彥，何川東，鄒冬冬

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

0 引言

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

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

1 靈巧衛星任務規劃問題及模型

1.1 靈巧衛星成像特點

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

圖1 目標的成像時刻示意

1.2 靈巧衛星任務規劃特點

靈巧衛星任務規劃具有以下特點：

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

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

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

1.3 優化目標

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

設規劃方案的收益函數表示為：

P=v1×f1+v2×f2=

(1)

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

則規劃方案的優化目標為：

(2)

1.4 約束條件分析

1.4.1 姿態轉換時間約束

后一個目標的成像開始時間須大于前一個目標的成像結束時間，加前一個目標關機穩定時間，加姿態轉換時間，加后一個目標的開機準備時間。

(3)

1.4.2 任務間隔時間約束

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

(4)

(5)

1.4.3 最大連續工作時長約束

前后相鄰相機開機到相機關機的間隔時間須小于最大連續工作時長約束。

(6)

1.4.4 數傳約束

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

(7)

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

(8)

1.4.5 固存容量約束

不同數據壓縮比對應的所需存儲容量也不一樣，2次固存擦除動作之間所有目標的存儲容量之和須小于衛星最大固存容量。

(9)

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

1.4.6 能源約束

成像目標的能量消耗加衛星設備的長期功耗，須小于衛星初始能量加衛星在光照區補充的能量之和，

(10)

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

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

2 算法研究

2.1 貪婪算法基本思想

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

2.2 貪婪規則設計

2.2.1 目標選擇規則

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

① 判斷目標等級，優先選擇目標等級較高的；

② 判斷目標數量，優先選擇目標數量較多的；

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

④ 判斷太陽高度角，優先選擇太陽高度角較大的。

2.2.2 成像時間選擇規則

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

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

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

2.2.3 前瞻處理規則

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

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

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

2.2.4 接收方案生成規則

① 優先將指定接收站的目標安排給對應接收站；

② 能實傳近實傳的目標優先安排相應站為實傳站；

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

2.2.5 能源補充規則

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

2.2.6 固存擦除規則

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

2.3 算法流程

任務規劃算法總體流程如圖2所示。

圖2 任務規劃算法總體流程

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

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

步驟5：生成接收方案：依次對候選接收任務隊列S1中的接收任務進行安排，并考慮各接收站接收任務均衡原則，直到無待傳輸的成像目標或者當前接收站無剩余接收時間，此時，得到初步任務規劃方案，即目標序列M4∈M3，接收序列S2∈S1；

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

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

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

3 算法仿真實驗

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

表1 周期為12 h實驗情況

表2 周期為24 h實驗情況

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

4 結束語

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