張澤浩 王繼河 張德新 邵曉巍

上海交通大學(xué)航空航天學(xué)院，上海200240

?

最小化完成測繪時間的衛(wèi)星成像任務(wù)規(guī)劃算法

張澤浩 王繼河 張德新 邵曉巍

上海交通大學(xué)航空航天學(xué)院，上海200240

針對應(yīng)急條件下的成像觀測任務(wù)，考慮衛(wèi)星成像條帶切換時間等約束建立成像任務(wù)調(diào)度模型，以最小化完成測繪任務(wù)時間為優(yōu)化目標(biāo)。通過改進(jìn)蟻群算法進(jìn)行求解，結(jié)合實際約束、加入任務(wù)執(zhí)行間隔等因素來控制轉(zhuǎn)移概率。為地面運管系統(tǒng)提供了一種新的成像策略優(yōu)化目標(biāo)，能夠根據(jù)不同的測繪任務(wù)以及用戶需求，選擇優(yōu)化方案對實際衛(wèi)星測繪做規(guī)劃。 關(guān)鍵詞 測繪完成時間；蟻群算法；成像規(guī)劃；應(yīng)急

近幾年，干涉SAR成像技術(shù)趨于成熟，德國TerraSAR-X和TanDEM-X編隊衛(wèi)星干涉成像提供了高精度的全球高程數(shù)據(jù)。編隊衛(wèi)星系統(tǒng)不受白天，黑夜及云霧影響，可以全天候、全天時對全球進(jìn)行測繪，同時可以執(zhí)行應(yīng)急測繪任務(wù)，然而面對復(fù)雜多樣的應(yīng)急測繪任務(wù)，由于成像衛(wèi)星資源有限，單軌成像能力有限等因素，優(yōu)化測繪策略，高效利用衛(wèi)星資源成為提升衛(wèi)星系統(tǒng)整體效益的重要內(nèi)容。

優(yōu)化衛(wèi)星測繪策略即成像衛(wèi)星調(diào)度問題是指在滿足衛(wèi)星各項約束條件下，針對測繪區(qū)域合理規(guī)劃星載開關(guān)機(jī)時間及開關(guān)機(jī)波位，以實現(xiàn)衛(wèi)星資源高效利用。它是一類具有時間窗口約束的組合優(yōu)化問題。目前解決此類問題的方法主要有啟發(fā)式算法和智能優(yōu)化算法。隨著研究的深入，混合智能優(yōu)化算法正成為目前國內(nèi)外學(xué)者的主要研究方向[1]。

國外Bansana[2]等人建立整數(shù)規(guī)劃模型，以最大化任務(wù)收益為優(yōu)化目標(biāo)，運用深度優(yōu)先搜索、動態(tài)規(guī)劃對SPOT-5衛(wèi)星成像調(diào)度問題求解。M.Lemaitre[3]研究了Agile Earth Satellite對區(qū)域目標(biāo)的測繪調(diào)度問題，建立了約束滿足模型，比較了貪婪、整數(shù)規(guī)劃以及遺傳算法，實驗證明了遺傳算法雖性能較好，但對于大規(guī)模問題求解困難。Jinbong[4]提出了二進(jìn)制整數(shù)模型，采用了基于拉格朗日松弛和梯度的啟發(fā)式算法。

國內(nèi)賀仁杰、白保存[5]等考慮了任務(wù)間的合成觀測，建立了任務(wù)規(guī)劃模型。以最大化完成任務(wù)收益為優(yōu)化目標(biāo)，提出了快速模型退火算法和動態(tài)任務(wù)合成啟發(fā)式算法對問題求解。于海、郭玉華[6]等人提出了一種新的約束修正方法求解該類問題。郝會成[7]通過混合遺傳算法和蟻群算法求解敏捷衛(wèi)星任務(wù)調(diào)度模型。靳肖閃[8]等人提出了一種基于拉格朗日松弛與最大分支算法的多項式時間復(fù)雜度的優(yōu)化算法。冉承新[9]等研究了移動目標(biāo)成像偵測任務(wù)規(guī)劃問題，設(shè)計了一種基于模擬退火算法及遺傳算法的改進(jìn)遺傳算法。張帆[10]等通過將成像需求序列對應(yīng)為有向圖中的成像路徑，基于多個優(yōu)化準(zhǔn)則使用支配關(guān)系對成像路徑質(zhì)量進(jìn)行綜合評價，提出有效準(zhǔn)則矢量生成算法。Liu X L[11]等提出了基于任務(wù)合成的多星調(diào)度算法，在任務(wù)合成階段采用動態(tài)規(guī)劃算法求解，任務(wù)分配階段采用自適應(yīng)蟻群算法求解。

以上研究是以最大化任務(wù)收益和最小化資源消耗為優(yōu)化目標(biāo)，在完成測繪任務(wù)總時間方面沒有較多研究，本文針對應(yīng)急測繪任務(wù)，優(yōu)化衛(wèi)星測繪策略。首先對測繪任務(wù)進(jìn)行預(yù)處理，給出問題的形式化描述，分析各項約束條件，建立約束滿足模型，以最小化完成測繪任務(wù)總時間為優(yōu)化目標(biāo)，對蟻群算法進(jìn)行改進(jìn)，結(jié)合啟發(fā)式規(guī)則求解問題，最后通過實驗仿真驗證算法有效性,為地面運管系統(tǒng)提供了一種新的成像策略優(yōu)化目標(biāo)，能夠根據(jù)不同的測繪任務(wù)以及用戶需求，選擇不同的優(yōu)化方案對實際衛(wèi)星測繪做規(guī)劃。

1 問題描述與調(diào)度模型建立

1.1 問題描述

SAR成像衛(wèi)星通過SAR敏感器成像。SAR 敏感器以推掃方式對地面區(qū)域進(jìn)行成像，觀測范圍由多個載荷單幅幅寬觀測范圍組成，這里的載荷單幅幅寬觀測的范圍叫做成像條帶，它的長度依賴于觀測時間，它的幅寬度取決于成像的內(nèi)外側(cè)角度，如圖1所示。為簡單起見，假設(shè)所有的成像條帶幅寬相同，衛(wèi)星觀測范圍由固定幾組成像條帶組成，不同成像條帶會有少量重疊。

圖1 衛(wèi)星成像波位掃描條帶及衛(wèi)星成像角度圖

根據(jù)大小，所有的測繪區(qū)域可以分為2種類型：點目標(biāo)和區(qū)域目標(biāo)(regional target)。點目標(biāo)可以由成像條帶一次測繪完成覆蓋，區(qū)域目標(biāo)需要多個條帶成像完成覆蓋，因此，在做成像調(diào)度規(guī)劃前，需要區(qū)域目標(biāo)作處理。分解流程如圖2所示，將區(qū)域目標(biāo)分解成多個元任務(wù)(點目標(biāo))，根據(jù)衛(wèi)星星下點軌跡以及成像條帶對全球區(qū)域進(jìn)行柵格化分解，分解的最小單元能被成像條帶一次成像覆蓋，處理結(jié)果如圖3所示。

圖2 衛(wèi)星成像波位掃描條帶圖

因此在單星調(diào)度問題中，每個測繪任務(wù)觀測時間和觀測波位的確定，成像衛(wèi)星調(diào)度問題是對單軌內(nèi)的測繪任務(wù)進(jìn)行測繪先后選擇和排序，同時需要滿足衛(wèi)星最大開關(guān)機(jī)次數(shù)、單軌最大成像時間、最短開機(jī)時間和波位切換時間等約束。

以往的研究是在固定時間內(nèi)對測繪任務(wù)進(jìn)行選擇、排序，以求得最大測繪收益，本文將所有測繪任務(wù)排序，規(guī)劃星載開關(guān)機(jī)時間和波位，求解測繪目標(biāo)區(qū)域最小完成時間。

圖3 區(qū)域目標(biāo)劃分結(jié)果圖

1.2 調(diào)度模型

決策變量為：

目標(biāo)函數(shù)：

(1)

約束條件：

(2)

(3)

ng≤g_onum

(4)

(5)

ifbcij=1andbj≠bi,wej≥bt+t_sta

(6)

(7)

(8)

其中，式(1)為目標(biāo)函數(shù)，最小化完成所有測繪任務(wù)；約束(2)和(3)表示載荷一次開機(jī)時間有上下限；約束(4)為單軌衛(wèi)星雷達(dá)載荷開關(guān)機(jī)次數(shù)有限；約束(5)表示單軌衛(wèi)星雷達(dá)載荷最大成像總時間限制；約束(6)為載荷成像條帶切換時間間隔約束；約束(7)為載荷關(guān)機(jī)重啟時間間隔約束；約束(8)表示同一時間載荷只能一個成像條帶開機(jī)測繪，測繪完成的任務(wù)不需要再次測繪。

2 改進(jìn)蟻群算法

根據(jù)衛(wèi)星調(diào)度問題的約束條件及目標(biāo)函數(shù)，針對以上調(diào)度模型提出改進(jìn)蟻群算法，由于基本蟻群算法搜索速度慢、易陷入局部最優(yōu)解等缺點，因此本文借鑒蟻群系統(tǒng)和最大最小螞蟻系統(tǒng)的思想設(shè)計尋優(yōu)策略和信息素更新策略，即加入啟發(fā)式搜索條件因素，在螞蟻選擇下一節(jié)點時給予額外的信息量；同時把每條邊上的信息素限制在[τmin,τmax]區(qū)間內(nèi)。

在求解該類問題時，測繪元任務(wù)類比螞蟻所需經(jīng)過的節(jié)點，測繪衛(wèi)星類比螞蟻，螞蟻同一時間只能經(jīng)過一個節(jié)點，即測繪衛(wèi)星同一時間只能執(zhí)行一個元任務(wù)，螞蟻按照狀態(tài)轉(zhuǎn)移規(guī)則依次經(jīng)過所有的節(jié)點，最終得到一條完整的路徑，即得到測繪任務(wù)的執(zhí)行序列。判斷測繪任務(wù)執(zhí)行序列的目標(biāo)函數(shù)值更新信息素，以此反饋給螞蟻下次的搜索過程。

2.1 尋優(yōu)策略

螞蟻從當(dāng)前所在節(jié)點選擇下一途徑節(jié)點時，按照偽隨機(jī)比例規(guī)則選擇，當(dāng)q≤q0：

pij={(τij)α(ηij)β(bij)γ}

(9)

j=maxj∈nextallow(ti){(τij)α(ηij)β(bij)γ}

(10)

其中，q為區(qū)間[0,1]均勻分布的隨機(jī)數(shù)，q0為輸入?yún)?shù)，當(dāng)q≤q0時，按照式(11)的概率分布，通過輪盤賭注法選擇一個隨機(jī)變量。

(11)

nextallow(ti)為任務(wù)ti下一個可以執(zhí)行的任務(wù)，滿足時間窗口不沖突、波位切換時間約束，同時需要滿足最長開機(jī)時間約束。如果為空集，即沒有滿足條件的下一個測繪任務(wù)，有2種情況：1)當(dāng)前軌道測繪任務(wù)安排結(jié)束，下一個執(zhí)行任務(wù)未執(zhí)行測繪任務(wù)中開始測繪時間最短的元任務(wù)，該元任務(wù)為下一軌道周期執(zhí)行的第1個任務(wù)；2)衛(wèi)星開機(jī)時間結(jié)束，需要關(guān)機(jī)，等待下一次開機(jī)時間，下一次開機(jī)時間需要滿足星載重啟時間約束。

2.2 信息素更新策略

當(dāng)螞蟻走過所有節(jié)點，即構(gòu)造出可行的任務(wù)執(zhí)行序列，得到完成所有測繪任務(wù)需要的軌道圈次數(shù)，比較當(dāng)前軌道圈次g與全局最優(yōu)軌道圈次gbest；若軌道圈次小于gbest，則更新全局最優(yōu)解orderbest=order，gbest=g；為了加速收斂，只對每次循環(huán)中最優(yōu)解執(zhí)行序列上的信息濃度進(jìn)行更新，更新規(guī)則如下：τij=(1-ρ)τij+Δτij

(12)

(13)

其中，ρ為信息素?fù)]發(fā)率。

如果g>gbest，則對此次螞蟻所經(jīng)過路徑上的信息素?fù)]發(fā)

τij=(1-ρ)3τij

(14)

為了避免陷入局部最優(yōu)解，當(dāng)所有信息素更新結(jié)束后，對信息素進(jìn)行判斷控制:

如果τij≤τmin，則τij=τmin;

如果τij≥τmax，則τij=τmax。

2.3 算法流程

本文研究完成測繪任務(wù)的時間最短，因此，需要規(guī)劃出測繪序列，盡可能在每軌測繪的任務(wù)數(shù)最多，這里選擇開始測繪時間最小的任務(wù)作為每軌開始測繪任務(wù)。

步驟1：初始化各項參數(shù)α,β,γ,ρ0,Q；初始τij=τmin，迭代次數(shù)n=1；

步驟2：螞蟻從當(dāng)前開始時間最小的任務(wù)節(jié)點出發(fā)，開機(jī)時間為起始任務(wù)測繪開始時間，onoff=1，標(biāo)記是否所有任務(wù)被排序執(zhí)行；如果onoff=1，轉(zhuǎn)步驟3；否則，轉(zhuǎn)步驟10；

步驟3：判斷onoff=1，若等于，尋找螞蟻下一次可以經(jīng)過的節(jié)點集合nextallow(ti)，即未被安排執(zhí)行的任務(wù)集合中，滿足時間窗約束、波位切換約束、最長開機(jī)時間max_ont約束的測繪任務(wù)，并計算選擇概率pij；若集合不為空，則轉(zhuǎn)步驟4；否則，轉(zhuǎn)步驟9；

步驟4:按照轉(zhuǎn)移規(guī)則選擇下一個任務(wù)，任務(wù)tj被選中，當(dāng)前螞蟻停在任務(wù)tj節(jié)點；判斷當(dāng)前星載是否開機(jī)，如果沒有開機(jī)，轉(zhuǎn)步驟5；否則，轉(zhuǎn)步驟6；

步驟5：從未排序執(zhí)行任務(wù)列表中刪除任務(wù)tj，即將記錄未安排任務(wù)數(shù)組中記錄該任務(wù)序號的值計0，轉(zhuǎn)步驟8；

步驟6：令開機(jī)次數(shù)onffnum加1，判斷是否當(dāng)前軌道開機(jī)次數(shù)小于單軌最大開機(jī)次數(shù)g_onum，如果是，開機(jī)時間為任務(wù)tj的wsj,轉(zhuǎn)步驟5；否則，轉(zhuǎn)步驟7；

步驟7：判斷是否有未安排執(zhí)行的測繪任務(wù)，若存在，令軌道數(shù)g加1，開機(jī)次數(shù)onffnum加1，從未安排的任務(wù)序列中選擇開機(jī)時間最小的任務(wù)tl作為螞蟻下一個途徑的任務(wù),開機(jī)時間為任務(wù)tl的wsj,轉(zhuǎn)步驟5；

步驟8：統(tǒng)計已安排執(zhí)行的任務(wù)數(shù)，如果所有的任務(wù)都安排執(zhí)行了，令onoff=0;轉(zhuǎn)步驟2；

步驟10：得到測繪任務(wù)執(zhí)行序列order，判斷軌道圈次g是否小于最優(yōu)軌道圈次gmin，如果是，最優(yōu)執(zhí)行序列order=orderbest；gmin=g；按照信息素更新策略，更新當(dāng)前路徑上的信息素

τij=(1-ρ)τij+Δτij

否則，揮發(fā)路徑上的信息素。判斷任務(wù)節(jié)點間的信息素，按照最大最小蟻群系統(tǒng)原則修改；

步驟11，若n

3 仿真實驗分析

研究單星測繪任務(wù)時間最短調(diào)度問題，因此在衛(wèi)星一個軌道測繪區(qū)域隨機(jī)生成不同規(guī)模的目標(biāo)數(shù)量，包括點目標(biāo)和區(qū)域目標(biāo)，對區(qū)域目標(biāo)進(jìn)行預(yù)處理，生成元任務(wù)。由于計算結(jié)果要與單軌最大化收益為目標(biāo)結(jié)果作對比，定義任務(wù)的優(yōu)先級為[0，1]之間的隨機(jī)數(shù)。

仿真環(huán)境的參數(shù)如下：

1)衛(wèi)星回歸周期為15d，軌道數(shù)為227，衛(wèi)星星下點軌跡以及測繪目標(biāo)如圖4；

2)成像條帶的角度范圍為 [19°，43°]，12 個成像條帶；

3)蟻群算法參數(shù)：最大迭代次數(shù)Nmax=600；α=1,β=2,γ=1,ρ0=0.02,Q=0.5。

圖4 衛(wèi)星星下點軌跡及測繪目標(biāo)

圖5 任務(wù)規(guī)模為500

圖6 任務(wù)規(guī)模為600

圖7 任務(wù)規(guī)模為800

分析仿真結(jié)果，圖4是在任務(wù)規(guī)模為500時的對比圖，可以看出在前8個周期中，目標(biāo)函數(shù)為最大化收益時求解任務(wù)規(guī)劃每個周期獲得的收益大于以最小化時間為目標(biāo)函數(shù)的，但是以時間為最小時，在第9個周期能將所有的任務(wù)測繪完，時間提升了25%。若用戶提交的任務(wù)需要在10個周期內(nèi)得到測繪結(jié)果，應(yīng)采用以時間為目標(biāo)函數(shù)進(jìn)行任務(wù)規(guī)劃求解；若用戶提交的任務(wù)需要在5個周期內(nèi)獲得測繪結(jié)果，此時應(yīng)以收益為目標(biāo)進(jìn)行任務(wù)規(guī)劃求解。隨著任務(wù)規(guī)模的增大，以時間為目標(biāo)函數(shù)能使時間有顯著提升，在任務(wù)規(guī)模為600時，最短完成測繪任務(wù)時間為11個周期，而以收益為目標(biāo)函數(shù)時，需要14個回歸周期，根據(jù)用戶提交的任務(wù)需要可選擇不同的方案。在任務(wù)規(guī)模為800時，可以看到在5個周期后，以時間為目標(biāo)函數(shù)得到的收益優(yōu)于以收益為目標(biāo)函數(shù)的，同時在時間上有18.75%的提升，因此可以驗證以時間為目標(biāo)函數(shù)能夠得到較好的結(jié)果，能針對用戶遞交的任務(wù)選擇不同的任務(wù)規(guī)劃方案。

4 結(jié)論

針對應(yīng)急測繪任務(wù)，以最小化完成測繪任務(wù)時間為優(yōu)化目標(biāo)，考慮了星載雷達(dá)成像的各種約束，建立測繪任務(wù)調(diào)度模型，改進(jìn)蟻群算法對衛(wèi)星測繪任務(wù)調(diào)度問題進(jìn)行求解。為地面運管系統(tǒng)提供了一種新的成像策略優(yōu)化目標(biāo)，能夠根據(jù)不同的測繪任務(wù)以及用戶需求，選擇不同的優(yōu)化方案對實際衛(wèi)星測繪做規(guī)劃。今后的研究工作需要在以下幾方面改進(jìn)：考慮星載雷達(dá)測繪幅寬變化約束；加入星載數(shù)傳約束條件；對算法進(jìn)一步完善，解決多星成像任務(wù)調(diào)度問題，能夠在較短時間內(nèi)求解大規(guī)模測繪任務(wù)。

[1] 姜維,郝會成,李一軍. 對地觀測衛(wèi)星任務(wù)規(guī)劃問題研究述評[J].系統(tǒng)工程與電子技術(shù),2013,35(9):1878-1885. (Jiang Wei, Hao Huicheng, Li Yijun. Review of Task Scheduling Research for the Earth Observing Satellites [J]. System Engineering and Electronics, 2013, 35(9): 1878-1885.)

[2] Bensana E, Verfaillie G, Agnese, et al. Exact and Inexact Methods for The Daily Management of an Earth Observation Satellite [C]. Proceedings of the International Symposium on Space Mission Operations and Ground Data Systems. Munich, Germany, 2002, 507-514.

[4] Jinbong Jang, Jiwoong Choi, Hee Jin Bae, et al. Image Collection Planning for Korea Multi-Purpose Satellite-2 [J]. European Journal of Operational Research，2013，230:190-199.

[5] 賀仁杰,高鵬,白保存. 成像衛(wèi)星任務(wù)規(guī)劃模型、算法及應(yīng)用[J].系統(tǒng)工程理論與實踐, 2011, 31(3):411-422.(He R J, Gao P , Bai B C. Models, Algorithms and Applications to the Mission Planning Systems of Imaging Satellites [J]. Systems Engineering-Theory & Practice, 2011, 31(3): 411-422.)

[6] 于海,郭玉華,李軍. 一種衛(wèi)星成像調(diào)度的約束修正方法[J].宇航學(xué)報,2008,29(4):1402-1407. (Yu Hai, Guo Yuhua, Li Jun. A Constraint Modification Approach for Imaging Scheduling of Earth Observing Satellites[J].Journal of Astronautics, 2008,29(4):1402-1407.)

[7] 郝會成,姜維,李一軍. 基于混合遺傳算法的敏捷衛(wèi)星任務(wù)規(guī)劃求解[J].科學(xué)技術(shù)與工程, 2013,13(17):4972-4978. (Hao H C, Jiang W .Based on the Hybrid Genetic Algorithm of the Agile Satellite Mission Planning[J].Science Technology and Engineer 2013, 13(17):4972-4978.)

[8] 靳肖閃,李軍,等. 基于拉格朗日松弛與最大分支算法的衛(wèi)星成像調(diào)度算法[J].宇航學(xué)報,2008,29(3):694-699.(Jin Xiaoshan, Li Jun, et al.An Algorithm for Satellite Imaging Scheduling Based on Lagrangian Relaxation and Max Weighted Component Algorithm[J]. Journal of Astronautics,2008,29(3):694-699.)

[9] 冉承新,王慧林,熊綱要. 基于改進(jìn)遺傳算法的移動目標(biāo)成像偵測任務(wù)規(guī)劃問題研究[J]. 宇航學(xué)報,2010,31(2):457-465.(Ran Chengxin, Wang Huilin, Xiong Gangyao. Research on Mission-Planning of Ocean Moving Targets Imaging Reconnaissance Based on Improved Genetic Algorithm [J]. Journal of Astronautics, 2010, 31(2):457-465.)

[10] 張帆,李軍,王鈞,等. 基于有效準(zhǔn)則矢量生成的成像調(diào)度方法[J].航天控制,2005,23(6):81-84. (Zhang Fan, Li Jun, Wang Jun,et al. Imaging Scheduling Based on Efficient Criteria Vector Generation [J]. Aerospace Control, 2005, 23(6):81-84.)

[11] Liu X L, Bai B C, Chen Y W. Multi Satellites Scheduling Algorithm Based on Task Merging Mechanism [J]. Applied Mathematics and Computation, 2014, 230: 687-700.

[12] Hongrae Kim, Young Keun Chang. Mission Scheduling Optimization of SAR Satellite Constellation for Minimizing System Response Time [J]. Aerospace Science and Technology, 2015, 40:17-32.

[13] Chen Y W, Yao F. A Learnable Ant Colony Optimization to the Mission Planning of Multiple Satellites [J].Systems Engineering-Theory & Practice, 2013, 33(3):791-801.

Mission Scheduling Optimization Algorithm of Satellite for Minimizing Complete Imaging Task Time

Zhang Zehao， Wang Jihe， Zhang Dexin， Shao Xiaowei

School of Aeronautics and Astronautics，Shanghai Jiao Tong University，Shanghai 200240，China

Aimingatsolvingthemissionplanningproblemofsatelliteimagingunderemergencyconditions,byconsideringtheconstraintssuchasswitchingtimeofimagingstripstoestablishschedulingmodel,theobjectiveconsideredisminimizedtocompleteimagingtasktimeinthispaper.Inaddition,animprovedantcolonyalgorithmisusedtosolvethisproblem.Anewoptimizationobjectiveisprovidedforgroundtransportationmanagementsystem,whichcanselectdifferentoptimizationschemesforsatelliteimagingaccordingtousers’requirements.

Completeimagingtasktime;Antcolonyalgorithm;Scheduling;Emergency

2015-11-23

張澤浩(1992-)，女，山西運城人，碩士，主要研究方向為衛(wèi)星成像規(guī)劃；王繼河(1982-)，男，黑龍江佳木斯人，博士，主要研究方向為編隊/集群飛行構(gòu)形設(shè)計與控制;張德新(1982-)，男，江蘇興化人，博士，主要研究方向為分布式航天器系統(tǒng)仿真技術(shù)；邵曉巍(1974-)，男，安徽肖市人，博士，副教授，主要研究方向為航天器導(dǎo)航與控制、系統(tǒng)仿真技術(shù)。

TP301.6

A

1006-3242(2016)04-0064-06