一種面向成像衛星的啟發式分層任務規劃方法

張 淳 張 強 趙 陽 劉 鶴 劉曉敏

北京空間飛行器總體設計部，北京 100190

0 引言

遙感衛星覆蓋區域廣，可長時間運行，不受飛行空域限制，是一種重要的對地觀測手段[1]。遙感衛星任務規劃負責分配衛星觀測資源、制定觀測計劃，利用有限存儲、能源和可見時段等資源充分完成用戶提交的成像任務，在遙感衛星成像業務應用過程中起到關鍵作用。隨著遙感衛星應用技術的發展，相關任務規劃問題得到了充分重視和廣泛研究[2-3]。

遙感衛星任務規劃問題與背包問題類似，均為NP難，不易獲得全局最優解[4]，潛在解隨遙感設備數量、衛星窗口數量、成像目標數量呈指數級增長，考慮多種因素下的優化搜索時間十分漫長。相關任務規劃研究內容包括動態調度[5]、貪婪迭代[6]、禁忌搜索[7-8]、線性規劃[9]、遺傳算法[10-11]、蟻群算法[12]、整數規劃[13-14]等等。這些任務規劃求解過程均基于一些簡化模型，或將任務規劃問題映射為某種問題的變體，或者忽略、簡化了衛星的部分實際運行約束，或者求解時間漫長，無法適應動態任務變化。目前，遙感衛星任務規劃問題求解大多采用靜態求解思路，即當任務需求發生變化時，將新需求與原需求整合后重新進行全局規劃，并未考慮任務規劃在實際運控系統中應用的實際動態響應需求。針對類似需求，采用基于規則的啟發式任務規劃具有更好的實用性?；谝巹t的啟發式算法簡單、直觀、便于實現、運算效率高，是現實成像衛星規劃系統中具有實際應用案例的算法[15-16]。

本文針對成像衛星運控系統中的高計算效率、動態任務調整應用需求，提出一種通用化的啟發式分層任務規劃方法，加速任務規劃計算，實現在保證原規劃方案結果繼承性基礎上響應新任務輸入。

1 任務規劃模型

1.1 調度路徑

設計如下總體任務調度路徑：首先對星上資源進行總體資源預算，評估規劃周期內可執行的任務數量；然后根據維護任務規劃結束后的剩余可用時間窗口，分別依序規劃各層級任務，具體分為關鍵任務、一般任務以及次要任務；在所有任務規劃完成后，進行資源復核，適時進行任務調整。

1.2 收益函數

采用如下收益函數

(1)

(2)

(3)

S=(Fkey,Ford,Fsub)

(4)

其中，Fkey為關鍵任務收益，Ford為一般任務收益，Fsub為次要任務收益，Tkey為關鍵任務集，Tord為一般任務集，Tsub為次要任務集，xi為任務i是否執行的決策變量，S表示收益計分。

1.3 資源預算

為了保障規劃結果的可行性，降低任務調整的可能性，在任務規劃前對衛星當前資源進行總體估算，評估當前資源能夠支持的運行時間或任務數量。主要考慮能源和存儲2種資源預算。

根據待規劃任務i的持續時間Δti項，計算所有待規劃任務集(Tkey、Tord和Tsub)的任務平均持續時間Δttotal，并使用下式計算滿負荷安排任務時的預期可規劃任務總量ntask,total

(5)

其中tcyc,total為規劃周期內總的可用時間窗口長度；tmnv,max=2?max/ω為衛星最長機動時間，?max為衛星最大俯仰或滾動角，ω是衛星平均機動速率；tst,max是衛星機動后觀測前的最長穩定時間。

1)能源預算

總體能源預算主要考慮衛星在光照期的充電能力和地影期的放電深度，通過計算地影期最大能源消耗、光照期充電能源、最小運行能源與衛星當前能源的關系獲得能源預算

p-(∪tw,i∩tw,es)Δpo+tw,illΔpc>pmin

(6)

其中tw,i為任務i的有效時間窗序列；p是當前初始能源；pmin是衛星最小運行能源，低于此限值衛星不應再執行對地觀測活動；Δpo為衛星載荷開機狀態下的平均能源消耗；Δpc為衛星蓄電池光照條件下平均充電速率；tw,es為地影期；tw,ill為光照期。

如果上式條件滿足，則衛星當前能源預算充足；如果條件不滿足，需要限制衛星在地影期的載荷最大開機時間，即

(7)

其中tduty,max表示地影期最長工作時間。

2)存儲預算

在總體存儲預算中，考慮可規劃任務總量、平均持續時間、最大存儲容量、存儲容量消耗速率與衛星當前可用存儲容量之間的關系獲得存儲預算

m+ntask,totalΔttotalΔm

(8)

其中m為衛星當前存儲容量；mmax是衛星最大可使用存儲容量；Δm是衛星觀測單位時間消耗的存儲容量。如果上式條件滿足，則衛星當前存儲預算滿足要求；如果條件不滿足，可添加數據下傳任務或限制衛星的可規劃任務總量進行處理。

1.4 約束復核

1)觀測約束

觀測約束主要考慮對目標的成像情況，考慮每個目標只能被觀測一次的規劃約束條件

(9)

其中Wtotal為全部時間窗口集，Ttotal為全部任務集，xi,k表示在第k個時間窗口安排對第i個任務進行觀測的決策變量。

2)任務準備約束

任務準備約束主要考慮由前一個任務執行過程中所需要的姿態機動到下一個待執行任務姿態所需要的機動轉換時間約束

(10)

其中ws,l,i,k為活動開始時間；we,l,i,k為活動結束時間,as,l和ae,l分別表示第l活動的第一組和最后一組姿態角?？紤]到

ws,l+1,i,k-we,l,i,k>tmnv,max+tst,max

(11)

進一步，約束式可簡化為

(12)

3)存儲約束

存儲約束對任務規劃結果所消耗的存儲容量進行復核

(13)

4)能源約束

能源約束對規劃結果所消耗的能源進行復核

(14)

5)地影期時間約束

能源約束中考慮了規劃周期內整體的能源平衡情況，但無法保證每一時刻衛星能源均大于最小運行能源。為保證解的合理性，根據能源預算中獲得的最大地影期工作時間，對地影期的任務執行時間進行約束，保證能源平衡，如式(15)：

(15)

2 啟發式分層任務規劃

為提高計算效率，縮小潛在的解空間搜索范圍，采用層次化的決策思路。先進行待規劃任務的選取，然后選取可用時間窗，在選中的時間窗內確定具體的執行任務時間段。通過這種規劃層級的劃分，可以將需要考慮多種因素的復雜規劃問題拆分為3個較小的決策問題，通過遞進式的搜索策略降低解空間維度，在啟發式規則引導下提高計算效率。

圖1 啟發式分層任務規劃

2.1 任務選取規則

任務規劃的第1層搜索為在待規劃任務集中選擇需要規劃的任務。評價任務選擇有2個維度，分別是任務權重和任務緊迫性。任務權重由任務構造模型定義，任務緊迫性則衡量任務可以被執行的機會，也即在規劃周期內該任務可以使用的觀測時間段的多少。為對任務權重和任務緊迫性進行綜合評估，定義任務需求度如式(16)：

(16)

其中nmission,i表示第i個任務的需求度，oi表示剩余觀測機會數量，即規劃周期tcyc,total內對任務觀測的剩余時間窗時間總和與該任務預期占用時間Δti之比。任務權重wi越高，任務權重越高，剩余觀測次數oi越少，任務緊迫性越高，因此任務需求度nmission,i可綜合評估剩余待規劃任務的優先級，選取其中最大者以作為本輪規劃的選取任務。

2.2 時間窗選取規則

任務規劃的第2層搜索是在已選中待規劃任務的可用時間窗口序列tw,i,k=[taccs,i,k,tacce,i,k]中選擇合適的時間窗口。由于每個待規劃任務可能對應了多個可用時間窗，因此需要對時間窗進行選擇。評價某個時間窗是否適合作為該任務的可執行窗口需要考慮2個方面，分別是該時間窗相對于任務所需要的執行時間Δti是否寬裕，以及該時間窗是否與其他任務所對應的可用時間窗或潛在執行時段存在沖突。為評價時間窗相對于任務執行時間的寬裕程度，定義時間窗自由度如式(17)：

(17)

其中fi,k表示任務i對其第k個可用時間窗口的時間窗自由度。顯然可用時間窗越寬，其自由度越高，表示選中該時間窗后進行后續時間段選取的靈活性越大。

比較使用所選任務可用時間窗與其他待規劃任務的所有可用時間窗，對沖突程度近似評估。定義時間窗沖突度如式(18)：

(18)

其中ci,k表示任務i第k個可用時間窗口所對應的沖突度；tconf,i,k,j表示任務j有效時間窗序列tw,j中與任務i中的第k個可用時間窗tw,i,k相沖突的時間長度，這里均考慮了tmnv,max和tst,max的影響，即用時間窗起始時刻減去機動和穩定時間，以近似獲得最大可能的沖突區間；nust表示當前規劃層未規劃任務中與時間窗tw,i,k存在沖突的剩余任務數，即計算沖突度時不再考慮已規劃完畢的任務。沖突區間tconf,i,k,j越長、所對應的沖突任務權重越高，表示當與其他高權重任務出現長時間交疊時，時間窗沖突度越大；選中的待規劃任務可用時間窗越小、任務權重越小，表示該任務時間窗越不重要，時間窗沖突度越大。

綜合考慮時間窗自由度與時間窗沖突度，定義時間窗需求度如式(19)：

(19)

時間窗自由度fi,k越高，任務段分配越自由，越不易與其他任務產生時間段沖突；時間窗沖突度ci,k越小，該任務窗口與其他任務的潛在可用時間窗口沖突程度越低。因此時間窗需求度nwindow,i,k可綜合評估所選取任務的時間窗序列的優先級，選取其中最大者以作為本輪規劃的選取時間窗。

2.3 時間段選取規則

任務規劃的第3層搜索是在已選中的可用時間窗口中進一步選擇實際執行任務時間段?？紤]基于任務重疊度的方式選取實際任務執行時間段，增強后續任務分配時間段的自由性，計算思路如圖3所示。

圖2 基于任務重疊度的時間段分配示意

圖3 沖突區間示意

將選中時間窗tw,i,k內的時間進行均勻采樣，獲得時間窗的采樣時刻總數nsi。對除選中任務外的任意剩余任務j，如果其所對應的時間窗序列tw,j包含時間窗tw,i,k的第m個采樣時刻，則設該時刻的沖突量為cnum,i,k,m,j=1，否則cnum,i,k,m,j=0。考慮除選中任務外的所有剩余任務，則有第m時刻的總沖突量為

(20)

而對于整個窗口，有總沖突量為

(21)

采用滑動窗口機制，在tw,i,k內滑動寬度為Δti的子窗口，尋找cnum,i,k最小的位置，此時表示該時段與其他任務沖突度最低，令ws,l,i,k等于此刻子窗口的開始時間，we,l,i,k等于此刻子窗口的結束時間，從而獲得實際任務執行時段。

2.4 活動序列更新規則

活動序列更細規則根據任務規劃過程結果更新任務列表，主要計算可用時間窗口的變化，即在給定當前任務序列和可見弧段序列基礎上，占用或釋放某時間段，并更新任務序列和相應可見弧段序列。限于篇幅，活動序列更新規則不再贅述。

2.5 低收益任務消減規則

對于任務規劃結果中不合理的部分，需要采用調整策略對規劃結果進行修改。低效益任務消減規則分為2步，首先確定消減的作用時間窗口范圍，對于資源約束，消減作用范圍一般為整個規劃周期，對于地影期時間約束，消減作用范圍為地影期，對于沖突任務則為沖突區間。其次，根據任務規劃結果計算最低級別各規劃任務的收益率，定義如下

(22)

將收益率最低的任務刪除，釋放可用資源和時間段，重新進行約束復核計算，如果滿足約束則停止，如果不滿足則繼續刪除任務。如果在最低級別任務已全部刪除時仍然無法滿足約束，則進一步刪除次低級別任務，以此類推。

2.6 沖突任務消解規則

當出現緊急任務需要插入已規劃出的任務序列中時，采用沖突任務消解規則進行應急任務插入，步驟如下：

步驟1.待規劃應急關鍵任務序列已遍歷完畢，若是則轉步驟4；若否，則轉步驟2。

步驟2.根據任務選取規則確定當前待規劃應急關鍵任務，嘗試在現有可用時間窗口下插入應急任務，若成功插入，則返回步驟1；若失敗，轉步驟3。

步驟3.分別確定當前待規劃應急關鍵任務與任務序列中已規劃未執行任務的沖突區間，針對存在多段沖突的情況，采用低收益任務消減規則依次刪除沖突任務，并嘗試插入當前應急任務，在刪除沖突任務但插入不成功情況下恢復原沖突任務，直至插入成功或全部沖突任務遍歷結束。若成功，或失敗但待規劃任務沒有與現有關鍵任務相沖突的區間，則返回步驟1；否則轉步驟4。

步驟4.若仍有未規劃的應急關鍵任務，且該應急任務與已安排應急任務存在沖突區間，則刪除全部未執行任務，將應急任務加入未執行任務形成新的待規劃任務序列，重新規劃任務。若沒有未規劃的應急關鍵任務，則結束。

3 仿真驗證

本節對所提出的啟發式分層規劃算法進行仿真驗證，仿真參數選擇某科學試驗衛星數據。最大俯仰角和滾動角45°，視場角8°*4°，衛星平均機動速率2(°)/s，衛星最長機動時間45s，最長穩定時間60s，規劃周期24h，半長軸24628km，偏心率0.72°，軌道傾角19.6°，近地點幅角290°，升交點赤經20°，真近點角0°。

配置含有108個觀測目標的高密度成像觀測任務表，觀測目標在地球表面沿經緯度均勻分布，其中經緯以(0°，0°)為起點，沿經度和緯度上分別每間隔30°、20°排布一個觀測目標。并分別定義不同任務層級(1至3)、權重和持續觀測時間(60s、180s、300s、600s)。使用STK對該108個目標的可見性進行分析仿真，除第84個目標點不可見外，其余均可見，可見窗口數量從1到4不等。使用本文所提算法對上述待規劃任務進行仿真計算，成功規劃任務107個，未規劃任務1個，其中未成功規劃的第84個任務沒有可見時間段。限于篇幅，這里不再單列任務規劃表。所有規劃結果滿足預先定義的任務要求，規劃時間窗口處于STK分析得到的可見弧段內，滿足任務規劃預期，規劃結束后按照式(4)得到的計分結果為(10,150,93)。

仿真驗證中任務規劃算法運行平臺配置為處理器Core i5-7200U 2.50GHz、內存8GB。108個成像任務規劃耗時2.8946s，所提啟發式分層任務規劃算法計算速度較高，同時能夠保證大量、多維度任務輸入下規劃解的覆蓋性和正確性。

在上述結果基礎上，于全球范圍內取隨機目標位置插入持續時間均為300s的關鍵任務，檢驗算法對動態輸入的響應能力。插入應急關鍵任務數量與結果如表1所示。

表1 插入應急關鍵任務后結果

除有一個應急關鍵任務沒有可見弧段外，其余任務均插入成功。當插入任務數量達到30時，觸發了沖突任務消解規則中規定的任務重排。由該組仿真可見，本文所提啟發式分層任務規劃算法能夠響應動態任務插入需求，保障對原規劃方案一定程度上的繼承性，當輸入變動過大時能夠支持快速任務重排，具備較強的實用性。

4 結論

針對成像衛星運控系統設計中的高計算效率、動態任務調整應用需求，提出了一種通用化的啟發式分層任務規劃方法，采用資源預算、分層規劃、約束復核、動態調整的思路構建任務調度路徑，引入了完整的觀測性、任務準備、存儲、能源、地影期等實際約束條件，利用啟發式貪婪策略，設計任務選取、時間窗選取、時間段選取三層復合搜索規則，逐級引導任務規劃求解過程，在每一層上縮減問題規模實現解空間的分步降維，從而加速任務規劃計算。同時提出低收益任務消減和沖突任務消解策略處理應急動態任務請求，實現在保證原規劃方案結果繼承性基礎上響應新任務輸入。仿真驗證結果表明所提算法能夠有效規劃高密度任務，同時具備較好的計算性能。