一種面向成像衛(wèi)星的啟發(fā)式分層任務(wù)規(guī)劃方法

張 淳 張 強(qiáng) 趙 陽(yáng) 劉 鶴 劉曉敏

北京空間飛行器總體設(shè)計(jì)部，北京 100190

0 引言

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

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

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

1 任務(wù)規(guī)劃模型

1.1 調(diào)度路徑

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

1.2 收益函數(shù)

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

(1)

(2)

(3)

S=(Fkey,Ford,Fsub)

(4)

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

1.3 資源預(yù)算

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

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

(5)

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

1)能源預(yù)算

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

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

(6)

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

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

(7)

其中tduty,max表示地影期最長(zhǎng)工作時(shí)間。

2)存儲(chǔ)預(yù)算

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

m+ntask,totalΔttotalΔm

(8)

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

1.4 約束復(fù)核

1)觀測(cè)約束

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

(9)

其中Wtotal為全部時(shí)間窗口集，Ttotal為全部任務(wù)集，xi,k表示在第k個(gè)時(shí)間窗口安排對(duì)第i個(gè)任務(wù)進(jìn)行觀測(cè)的決策變量。

2)任務(wù)準(zhǔn)備約束

任務(wù)準(zhǔn)備約束主要考慮由前一個(gè)任務(wù)執(zhí)行過(guò)程中所需要的姿態(tài)機(jī)動(dòng)到下一個(gè)待執(zhí)行任務(wù)姿態(tài)所需要的機(jī)動(dòng)轉(zhuǎn)換時(shí)間約束

(10)

其中ws,l,i,k為活動(dòng)開(kāi)始時(shí)間；we,l,i,k為活動(dòng)結(jié)束時(shí)間,as,l和ae,l分別表示第l活動(dòng)的第一組和最后一組姿態(tài)角。考慮到

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

(11)

進(jìn)一步，約束式可簡(jiǎn)化為

(12)

3)存儲(chǔ)約束

存儲(chǔ)約束對(duì)任務(wù)規(guī)劃結(jié)果所消耗的存儲(chǔ)容量進(jìn)行復(fù)核

(13)

4)能源約束

能源約束對(duì)規(guī)劃結(jié)果所消耗的能源進(jìn)行復(fù)核

(14)

5)地影期時(shí)間約束

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

(15)

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

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

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

2.1 任務(wù)選取規(guī)則

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

(16)

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

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

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

(17)

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

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

(18)

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

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

(19)

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

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

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

圖2 基于任務(wù)重疊度的時(shí)間段分配示意

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

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

(20)

而對(duì)于整個(gè)窗口，有總沖突量為

(21)

采用滑動(dòng)窗口機(jī)制，在tw,i,k內(nèi)滑動(dòng)寬度為Δti的子窗口，尋找cnum,i,k最小的位置，此時(shí)表示該時(shí)段與其他任務(wù)沖突度最低，令ws,l,i,k等于此刻子窗口的開(kāi)始時(shí)間，we,l,i,k等于此刻子窗口的結(jié)束時(shí)間，從而獲得實(shí)際任務(wù)執(zhí)行時(shí)段。

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

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

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

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

(22)

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

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

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

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

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

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

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

3 仿真驗(yàn)證

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

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

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

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

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

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

4 結(jié)論

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