最小化完成測繪時間的衛星成像任務規劃算法

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

上海交通大學航空航天學院，上海200240

?

最小化完成測繪時間的衛星成像任務規劃算法

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

上海交通大學航空航天學院，上海200240

針對應急條件下的成像觀測任務，考慮衛星成像條帶切換時間等約束建立成像任務調度模型，以最小化完成測繪任務時間為優化目標。通過改進蟻群算法進行求解，結合實際約束、加入任務執行間隔等因素來控制轉移概率。為地面運管系統提供了一種新的成像策略優化目標，能夠根據不同的測繪任務以及用戶需求，選擇優化方案對實際衛星測繪做規劃。 關鍵詞 測繪完成時間；蟻群算法；成像規劃；應急

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

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

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

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

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

1 問題描述與調度模型建立

1.1 問題描述

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

圖1 衛星成像波位掃描條帶及衛星成像角度圖

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

圖2 衛星成像波位掃描條帶圖

因此在單星調度問題中，每個測繪任務觀測時間和觀測波位的確定，成像衛星調度問題是對單軌內的測繪任務進行測繪先后選擇和排序，同時需要滿足衛星最大開關機次數、單軌最大成像時間、最短開機時間和波位切換時間等約束。

以往的研究是在固定時間內對測繪任務進行選擇、排序，以求得最大測繪收益，本文將所有測繪任務排序，規劃星載開關機時間和波位，求解測繪目標區域最小完成時間。

圖3 區域目標劃分結果圖

1.2 調度模型

決策變量為：

目標函數：

(1)

約束條件：

(2)

(3)

ng≤g_onum

(4)

(5)

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

(6)

(7)

(8)

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

2 改進蟻群算法

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

在求解該類問題時，測繪元任務類比螞蟻所需經過的節點，測繪衛星類比螞蟻，螞蟻同一時間只能經過一個節點，即測繪衛星同一時間只能執行一個元任務，螞蟻按照狀態轉移規則依次經過所有的節點，最終得到一條完整的路徑，即得到測繪任務的執行序列。判斷測繪任務執行序列的目標函數值更新信息素，以此反饋給螞蟻下次的搜索過程。

2.1 尋優策略

螞蟻從當前所在節點選擇下一途徑節點時，按照偽隨機比例規則選擇，當q≤q0：

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

(9)

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

(10)

其中，q為區間[0,1]均勻分布的隨機數，q0為輸入參數，當q≤q0時，按照式(11)的概率分布，通過輪盤賭注法選擇一個隨機變量。

(11)

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

2.2 信息素更新策略

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

(12)

(13)

其中，ρ為信息素揮發率。

如果g>gbest，則對此次螞蟻所經過路徑上的信息素揮發

τij=(1-ρ)3τij

(14)

為了避免陷入局部最優解，當所有信息素更新結束后，對信息素進行判斷控制:

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

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

2.3 算法流程

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

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

步驟2：螞蟻從當前開始時間最小的任務節點出發，開機時間為起始任務測繪開始時間，onoff=1，標記是否所有任務被排序執行；如果onoff=1，轉步驟3；否則，轉步驟10；

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

步驟4:按照轉移規則選擇下一個任務，任務tj被選中，當前螞蟻停在任務tj節點；判斷當前星載是否開機，如果沒有開機，轉步驟5；否則，轉步驟6；

步驟5：從未排序執行任務列表中刪除任務tj，即將記錄未安排任務數組中記錄該任務序號的值計0，轉步驟8；

步驟6：令開機次數onffnum加1，判斷是否當前軌道開機次數小于單軌最大開機次數g_onum，如果是，開機時間為任務tj的wsj,轉步驟5；否則，轉步驟7；

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

步驟8：統計已安排執行的任務數，如果所有的任務都安排執行了，令onoff=0;轉步驟2；

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

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

否則，揮發路徑上的信息素。判斷任務節點間的信息素，按照最大最小蟻群系統原則修改；

步驟11，若n

3 仿真實驗分析

研究單星測繪任務時間最短調度問題，因此在衛星一個軌道測繪區域隨機生成不同規模的目標數量，包括點目標和區域目標，對區域目標進行預處理，生成元任務。由于計算結果要與單軌最大化收益為目標結果作對比，定義任務的優先級為[0，1]之間的隨機數。

仿真環境的參數如下：

1)衛星回歸周期為15d，軌道數為227，衛星星下點軌跡以及測繪目標如圖4；

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

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

圖4 衛星星下點軌跡及測繪目標

圖5 任務規模為500

圖6 任務規模為600

圖7 任務規模為800

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

4 結論

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

[1] 姜維,郝會成,李一軍. 對地觀測衛星任務規劃問題研究述評[J].系統工程與電子技術,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] 賀仁杰,高鵬,白保存. 成像衛星任務規劃模型、算法及應用[J].系統工程理論與實踐, 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] 于海,郭玉華,李軍. 一種衛星成像調度的約束修正方法[J].宇航學報,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] 郝會成,姜維,李一軍. 基于混合遺傳算法的敏捷衛星任務規劃求解[J].科學技術與工程, 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] 靳肖閃,李軍,等. 基于拉格朗日松弛與最大分支算法的衛星成像調度算法[J].宇航學報,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]. 宇航學報,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] 張帆,李軍,王鈞,等. 基于有效準則矢量生成的成像調度方法[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-)，女，山西運城人，碩士，主要研究方向為衛星成像規劃；王繼河(1982-)，男，黑龍江佳木斯人，博士，主要研究方向為編隊/集群飛行構形設計與控制;張德新(1982-)，男，江蘇興化人，博士，主要研究方向為分布式航天器系統仿真技術；邵曉巍(1974-)，男，安徽肖市人，博士，副教授，主要研究方向為航天器導航與控制、系統仿真技術。

TP301.6

A

1006-3242(2016)04-0064-06