張 淳 張 強 趙 陽 劉 鶴 劉曉敏

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

0 引言

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

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

本文針對成像衛(wèi)星運控系統(tǒng)中的高計算效率、動態(tài)任務調(diào)整應用需求，提出一種通用化的啟發(fā)式分層任務規(guī)劃方法，加速任務規(guī)劃計算，實現(xiàn)在保證原規(guī)劃方案結(jié)果繼承性基礎上響應新任務輸入。

1 任務規(guī)劃模型

1.1 調(diào)度路徑

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

1.2 收益函數(shù)

采用如下收益函數(shù)

(1)

(2)

(3)

S=(Fkey,Ford,Fsub)

(4)

其中，F(xiàn)key為關(guān)鍵任務收益，F(xiàn)ord為一般任務收益，F(xiàn)sub為次要任務收益，Tkey為關(guān)鍵任務集，Tord為一般任務集，Tsub為次要任務集，xi為任務i是否執(zhí)行的決策變量，S表示收益計分。

1.3 資源預算

為了保障規(guī)劃結(jié)果的可行性，降低任務調(diào)整的可能性，在任務規(guī)劃前對衛(wèi)星當前資源進行總體估算，評估當前資源能夠支持的運行時間或任務數(shù)量。主要考慮能源和存儲2種資源預算。

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

(5)

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

1)能源預算

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

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

(6)

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

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

(7)

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

2)存儲預算

在總體存儲預算中，考慮可規(guī)劃任務總量、平均持續(xù)時間、最大存儲容量、存儲容量消耗速率與衛(wèi)星當前可用存儲容量之間的關(guān)系獲得存儲預算

m+ntask,totalΔttotalΔm

(8)

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

1.4 約束復核

1)觀測約束

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

(9)

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

2)任務準備約束

任務準備約束主要考慮由前一個任務執(zhí)行過程中所需要的姿態(tài)機動到下一個待執(zhí)行任務姿態(tài)所需要的機動轉(zhuǎn)換時間約束

(10)

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

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

(11)

進一步，約束式可簡化為

(12)

3)存儲約束

存儲約束對任務規(guī)劃結(jié)果所消耗的存儲容量進行復核

(13)

4)能源約束

能源約束對規(guī)劃結(jié)果所消耗的能源進行復核

(14)

5)地影期時間約束

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

(15)

2 啟發(fā)式分層任務規(guī)劃

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

圖1 啟發(fā)式分層任務規(guī)劃

2.1 任務選取規(guī)則

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

(16)

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

2.2 時間窗選取規(guī)則

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

(17)

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

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

(18)

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

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

(19)

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

2.3 時間段選取規(guī)則

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

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

圖3 沖突區(qū)間示意

將選中時間窗tw,i,k內(nèi)的時間進行均勻采樣，獲得時間窗的采樣時刻總數(shù)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內(nèi)滑動寬度為Δti的子窗口，尋找cnum,i,k最小的位置，此時表示該時段與其他任務沖突度最低，令ws,l,i,k等于此刻子窗口的開始時間，we,l,i,k等于此刻子窗口的結(jié)束時間，從而獲得實際任務執(zhí)行時段。

2.4 活動序列更新規(guī)則

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

2.5 低收益任務消減規(guī)則

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

(22)

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

2.6 沖突任務消解規(guī)則

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

步驟1.待規(guī)劃應急關(guān)鍵任務序列已遍歷完畢，若是則轉(zhuǎn)步驟4；若否，則轉(zhuǎn)步驟2。

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

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

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

3 仿真驗證

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

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

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

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

表1 插入應急關(guān)鍵任務后結(jié)果

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

4 結(jié)論

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