對地觀測衛星動態任務調度優化算法研究

陳 昊，趙 斐，白建東

(北京跟蹤與通信技術研究所，北京 100094)

0 引言

對地觀測衛星任務規劃的目標就是選擇需要觀測的目標、確定觀測的衛星遙感器、觀測開始時間和結束時間。對于多顆衛星、多種遙感器和多個任務需求的情況下，如何充分分配衛星資源、高效地完成任務和發揮對地觀測衛星系統的能力，生成一個滿意的衛星任務規劃方案，顯得非常重要。

國內外對于衛星對地觀測任務規劃問題已經開展了較多研究。P.Wang等[1-2]建立了約束規劃模型，并比較了貪婪算法、動態規劃、約束規劃和局部搜索4種不同的求解策略；Han S M等[3-4]建立多目標敏捷衛星調度模型，并提出一種偏好的隨機遺傳算法求解該問題，研究了多種選擇策略和解碼策略；LI J F等[5]利用敏捷衛星的高機動性優勢，提出了一種針對區域目標的最優條帶劃分和觀測窗口計算方法；國內以國防科學技術大學信息系統工程團隊為代表，在單星以及多星對地觀測的任務規劃問題上進行了廣泛和深入的研究，取得了一系列的研究成果[6-14]。

但是，截止目前，國內外對于衛星對地觀測任務規劃問題的研究主要是針對靜態任務，即給定一定時間(通常為1天)進行一次，在調度前衛星觀測任務是預先提交確定的，規劃方案一經生成便不再改變，方案提交給衛星進行執行完成即可。然而這種情況在應急任務時并不合適。此外，衛星系統在運行過程中因為各種原因，導致當前調度方案無法順利執行下去，也需要對調度方案進行動態調整。

本文針對衛星任務規劃調度的動態調整需求，在每個動態調度決策點，將所有的任務劃分為已完成任務、已安排任務和新任務。首先對衛星任務動態調度問題進行統一描述，包括新任務的插入、已安排任務的取消、任務優先級的變更、天氣條件的變化和衛星資源狀態的變化描述為新任務的插入；其次以最大任務收益和最小任務擾動測度為目標函數構建完成任務動態調度優化模型，設計可見時間窗口擁擠度和執行時刻點重疊度2種啟發式因子，基于啟發式智能ISR-HA算法尋求最優任務編排結果。

1 任務動態調度問題的統一描述

由于衛星系統在運行過程中可能會遇到各種環境變化、任務擾動，導致當前調度方案無法順利地執行下去，需要對調度方案進行動態調整。衛星任務優化調度技術路徑如圖1所示。

圖1 衛星任務優化調度技術路徑Fig.1 Technical approach to optimal sechduling of satellite mission

本文分析各類擾動對姿態機動時間的影響，結合星上實時狀態信息，把動態調度問題統一用插入任務的衛星動態調度問題進行描述，在每個動態調度決策點，將所有的任務劃分為3種類型：己完成任務、已安排任務和新任務，如圖2所示。已完成任務不需要再考慮；已安排任務表示在當前調度方案中尚未執行的任務；新任務指的是新到達任務或因不滿足約束條件而暫時沒有安排進當前調度方案的任務。任務動態調整指的是有新任務或者是已安排任務中，因約束條件改變導致無法按當前調度方案執行，或當約束條件改變而導致某些任務無法按當前調度方案執行時，已安排任務就轉化為新任務。

圖2 動態調度任務的劃分Fig.2 Partition of dynamic sechduling tasks

可以把未安排任務看作是新任務集中的任務，并將取消的任務從已安排任務集中刪除；針對任務優先級變化，如已安排任務的收益變低，或未安排任務收益變高，需將新任務集中的高收益任務插入到調度方案中，同時可將低收益任務從調度方案中調整出任務集；對天氣情況變化和衛星資源變化，需要把這些因天氣條件不滿足暫無法執行的任務從已安排任務集調整到新任務集中，必要時將后續優先級低的任務從調度方案中調整出來。因此，動態調度調整問題中雖然擾動的類型不同，但本質上都可以歸結為一類插入任務的動態調度問題。

2 衛星任務動態調度優化模型

2.1 約束滿足問題

在人工智能領域中有一個比較重要的問題就是約束滿足問題。一個約束滿足問題由3部分組成：① 變量集合；② 對應變量所屬的值域；③ 求解過程中需要滿足的相關約束集合。

約束滿足問題的求解目標是滿足各項約束條件的前提下，為在每個變量相應的值域范圍內取某一個特定的值。約束滿足問題的描述形式有多種，一種較為有代表性的定義是把約束滿足問題以一個三元組P=〈V,D,C〉來表示，其中：V為變量集，V={V1,V2,...,Vn}；D為定義域集，D={D1,D2,...,Dn}，其中Di為Vi的值域；C為約束關系集，C={C1,C2,...,Cm}，每個約束Cj與V的一個子集相關，即Cj≤Vsub，其中Vsub是約束中包含的變量，Vsub=Vj1×Vj2×...×Vjn；R是與變量相關的值域：R=Dj1×Dj2×...×Djn，即每個約束關系確定了它所涉及的變量定義域的笛卡兒積的一個子集；R>表示一個約束關系。

約束滿足問題的解是組合{〈V1,d1〉,〈V2,d2〉,...,〈Vn,dn〉}，該組合滿足所有相關的約束條件，其中di∈Di。

在優化模型構建前，首先對問題進行假設，關注核心約束條件，實現模型約束條件的簡化，然后提出動態調度優化的目標函數與約束條件。多星任務動態調度問題涉及多顆衛星，每顆衛星都具有固定的運行狀態。同時，該問題也涉及多個地面觀測目標，每個地面觀測目標均有明確的經緯度信息。受衛星運行過程的限制，衛星在一天內通過地面觀測目標的時間是有限的，此時間范圍稱為可見時間窗口?？捎脮r間窗相對于衛星需要執行的任務而言往往是不足的，所以，需要編排合理的衛星調度執行方案。

S：表示衛星資源集合，即S={s1,s2,...,sn}；

Td：表示動態調度時刻點；

OriginTasks：表示原調度方案集合，即OriginTasks={t1,t2,...,tm}，其中ti表示原調度方案中第i個任務；

NewTasks：表示新任務集合，即NewTasks={t1,t2,...,tp}，其中ti表示新任務集中第i個任務；

Values：表示所有任務的價值集合，Values={v1,v2,...,vm+p}，其中任務數為m+p，即新任務與原調度方案任務數之和；

disturbi：布爾變量，表示任務ti是否受到擾動，是則為1，否則為0，其中ti∈OriginTasks；

tci：表示衛星遙感器的相鄰任務間切換時間，即tci表示衛星si的遙感器轉換時間，由于之前假設一個衛星只攜帶一種傳感器，那么si∈S；

di：表示任務ti需要滿足的持續觀測時間，其中ti∈NewTasks∪OriginTasks；

ai：表示任務ti到達的時刻點，其中ti∈NewTasks∪OriginTasks；

ei：表示任務ti必須在此之前完成，即任務的完成截止期限，其中ti∈NewTasks∪OriginTasks；

tmini：表示衛星si的遙感器最小開機時間；

tmaxi：表示衛星si的遙感器最長開機時間。

2.2任務動態調度模型

衛星動態調度問題可描述為：已知衛星資源S，在動態調度決策時刻點Td，有一批新任務集NewTasks需要插入到原調度方案中OriginTasks。在滿足衛星任務各種約束條件下，獲取盡量大的任務總價值，由于動態調度問題需要滿足時效性，所以應保證盡量快地制定出新的調度方案，并保證新方案與原調度方案的差異性越小越好。

針對對地觀測衛星在執行初始調度方案的過程中經常遇到各種突發事件的情況，分析導致動態調度的主要擾動因素以及主要的約束條件，并將其歸為一類復雜約束下的新任務插入問題，以最大化完成任務優先級之和，并將對原調度計劃調整最小作為另一個目標，建立了具有兩級優化目標的動態約束滿足問題模型。

衛星對地觀測動態調度問題可以描述為七元組：

〈SimTime,S,Td,OriginTasks,Windows,Constraints,Values〉。

SimTime為整個仿真周期，SimTime=[tb,te]，tb表示仿真周期起始點，te表示仿真周期結束點。TimeWindows為所有任務的時間窗口集，即TimeWindows={tw1,tw2,...,twm+p}。Constraints表示任務所要滿足的所有約束集。

優化目標函數如下：

(1)

(2)

式(1)為第一級目標，表示最大化完成任務總權值，反映了調度方案整體的收益。式(2)為第二級目標，表示最小化受干擾的原計劃任務數目，反映了新任務對原調度方案的震蕩程度。

約束條件如下：

(3)

(4)

(5)

(6)

(7)

式(3)表示每個任務最多被某顆衛星執行一次， 如果任務i被成功安排在資源i的綠色部分，對于同一資源上和其他資源上的任何位置都不能再安排任務i。

式(4)表示每個任務的執行時間必須在可見時間窗口內，且滿足相應的持續時間。

式(5)表示為了保證任務的時效性，每個任務必須安排在其規定的截止時間之前，比如雖然任務i在資源1、資源2及資源3上均有2個不同的時間窗口，但考慮到任務的截至期限，實際上，任務在各個資源上的有效時間窗口均只有一個，各個資源上位于任務的截至期限之后的時間窗口均為無效時間窗口。

式(6)表示在同一個衛星上相鄰的2個被安排任務，必須滿足相應的轉換時間，以保證衛星有足夠的時間完成姿態轉換。

式(7)表示一顆衛星資源在同一時刻只能完成一個任務。

3 衛星任務動態調度優化算法

對地觀測衛星動態調度問題實質是在滿足各項約束條件的前提下，為各項任務合理分配衛星資源以及確定執行起止時間。雖然可以撤銷原方案，利用整體重新規劃調度的方法對所有的任務進行新的分配，理論意義上能得到全局最優解，但是這種方式沒有充分利用原調度方案的優良特性，而且處理數據規模過大，無法滿足時效性要求，并且產生的新調度方案對原調度方案干擾過大，不利于后續工作的開展。本文基于對地觀測衛星任務安排中2個關鍵過程，即可見時間窗口的選取和執行時刻點的確定，給出了2種比較合理的啟發因子，并將其加入了設計的基于啟發式規則的ISR-HA算法。

3.1 啟發因子設計

3.1.1 可見時間窗口擁擠度

可見時間窗口擁擠度，是指當將任務i安排在某個可見時間窗口后，對其他未安排新任務可能造成的干擾程度，以及對原調度方案中已安排任務干擾之和，計算公式如下：

(8)

式中，NT為新任務集中所有在衡量任務ti時還未安排的任務；OT為原調度方案任務集；λ為權衡對新任務和原任務干擾程度比重因子，根據需要進行調整，本方案中取λ=3。

3.1.2 執行時刻點重疊度

每個任務都需要確定它的執行開始時刻和結束時刻，而每個任務的持續時間是一定的，那么只需要確定每個任務的開始時刻即可。若按照最早開始原則選擇，有些情況會導致有些任務無法執行。如在同一個資源r上，若選擇最早開始原則安排任務j，那么若后續任務i在該資源上的時間窗口也比較靠前，則將無法分配時間段執行觀測。若按圖3方式安排任務j，那么任務i和任務j均能得到安排。由此引入第二個啟發因子，即執行時刻點重疊度。

圖3 按基于執行時刻點重疊度插入任務Fig.3 Insert task based on overlap of execution time

3.2 啟發式ISR-HA算法設計

3.2.1 預處理

在預處理過程中，主要完成3大任務：

① 將動態調度時刻點以前的任務安排為已完成；② 刪除動態調度時刻點以前的任務時間窗口；③ 刪除不滿足任務觀測時長的時間窗口。

3.2.2 基于遺傳算法的初始調度方案

在新任務動態插入之前，需要對原始任務集生成初始調度方案，在本文中使用遺傳算法(GA)對原始任務集生成初始調度方案。具體流程包括編碼設計—適應度函數設計，由于遺傳算法比較成熟，本文不再贅述，需要強調的是：在編碼設計中本文采用“衛星資源-時間窗次序編號”形式定義單個染色體，其示意如圖4所示。

圖4 動態調度遺傳算法編碼示意Fig.4 Diagram of genetic algorithm coding for dynamic sechduling

第1號任務分配給第4顆衛星的第2個可見時間窗口，第2號任務分配給第5顆衛星的第3個可見時間窗口，第3號任務分配給第1顆衛星的第4個可見時間窗口，第5號任務分配給第2顆衛星的第2個可見時間窗口。其中“0-0”表示第4號任務沒有對應的衛星資源進行分配。

3.2.3 ISR-HA算法

ISR-HA算法步驟如下：

① 需要動態插入的新任務集合NewTasks中共有N個任務，將N個任務降序排列。

② 令i= 1。

③ 選擇NewTasks集合中第i個任務，計算任務i每個可見時間窗口的擁擠度，并按非降序原則排列。

④ 按排序后的可見時間窗口順序，依次考察每個可見時間窗口，計算該時間窗口內每個時刻點的重疊度，并按非降序原則排列。依次考察排序后每個時刻點，嘗試無沖突的直接插空安排任務i，若成功，則轉③；否則，轉⑤。

⑤ 分別計算任務i插入到每個可選時刻點后，與任務i相沖突的已安排任務的數目。設任務i共有mi個可選時刻點，則得到任務i的任務沖突數向量ΔNi=[Δn1,Δn2,...,Δnmi]，并記錄相應的任務沖突集，并按非降序排列ΔNi。

⑥ 依次從小到大考察ΔNi(為了保證對原調度方案擾動最小)，令k=1。

⑦ 選擇Δnk，若k>mi， 則轉⑧，否則將任務i安排到此時所選擇的時刻點，將此時與任務i沖突的所有任務集移位，移位的原則是在不刪除任何任務的前提下，將這些沖突任務重新安排。若成功，則轉③;否則，恢復任務i插入前的狀態，k=k+1，轉⑦。

⑧ 分別計算ΔNi中每個相應任務沖突集的任務價值之和ΔWi=[Δw1,Δw2,...,Δwmi]，選擇ΔWi中價值和最小的Δwk(為了保證最大化收益總值)，如果任務i的權值小于等于Δwk，表示任務i不能替代相應的沖突任務集，那么刪除任務i，并將其加入任務集Delete，轉③；否則，將相應的任務沖突任務集加入優先級隊列Q中(Q的排序準則是按任務權值從小到大排序)。

⑨ 循環處理Q中每個任務，若隊列為空則轉⑩，否則取出隊首元素j，若無沖突直接安排任務j成功，那么繼續處理下一個隊首元素；否則，找出與任務j沖突的最小權值任務集Δwj，若任務j的權值大于Δwj，那么任務j安排成功，并將與任務j沖突的任務加入Q中，繼續處理下一個隊首元素；否則刪除任務j，并將其加入任務集Delete，繼續處理下一個隊首任務。

⑩ 若i≥N，轉；否則i=i+1， 轉③。

其中，關鍵步驟④任務直接插入過程的流程如圖5所示。

圖5 任務直接插入流程Fig.5 Direct task insertion flow chart

其中步驟⑦任務移位插入過程示意如圖6所示(插入任務k在不同執行窗口下的情況)。由此可知，如果要將動態任務k插入在資源r的執行窗口1，則此時與任務4及任務5在資源r上的執行時間窗口沖突，為了能夠將動態任務k插入在資源r的執行窗口1上，此時必須將任務4及任務5的執行時間窗口在其可見時間窗口范圍內移動到對應的虛線框內的時間段。同樣，如果要將動態任務k插入在資源r的執行窗口2，則此時與任務1、任務2及任務3在資源r上的執行時間窗口沖突，為了能夠將動態任務k插入在資源r的執行窗口2上，此時必須將任務1、任務2及任務3的執行時間窗口在其可見時間窗口范圍內移動到對應的虛線框內的時間段。

圖6 任務移位過程圖Fig.6 Task shift process diagram

綜上，ISR-HA算法流程如圖7所示。

圖7 ISR-HA算法流程Fig.7 ISR-HA algorithm flow chart

4 仿真實驗

本次仿真實驗環境為Core i7-8550 @1.8 GHz CPU，8 GB RAM，Windows 10，64位操作系統的筆記本電腦。設置仿真實驗的 5顆衛星軌道參數，以及初始任務、新任務等相關基本參數，最后通過 Matlab R2016a 仿真對比驗證所提出算法的有效性。

4.1仿真參數設置

實驗的初始調度任務集數為150個，經度范圍[76°E，131°E]，緯度范圍[17°N，45°N]內隨機生成的點目標任務;動態任務集數為200個，經度范圍[80°E，120°E]， 緯度范圍[20°N，42°N]內隨機生成的點目標任務。實驗通過衛星工具包(STK)生成相應的衛星觀測任務集，動態任務集的經緯度范圍更集中，有利于增加與原任務集的時間沖突度。仿真實驗總調度周期設置為24 h(2020年5月15日0:00-24:00)，動態調度時刻點設置為2020年5月15日6:00。

仿真實驗衛星軌道基本參數設置如表1所示。

表1 仿真實驗衛星軌道基本參數表Tab.1 Basic paramaters of simulation experimental satellite orbit

4.2 仿真實驗及結果分析

通過前一節設置的任務觀測集數據和衛星軌道參數即可獲得每個觀測任務的衛星過境窗口來進行衛星觀測任務的調度。由于反應式調度基于初始預調度進行重新調度，仿真實驗首先采用GA對初始任務集生成初始預調度方案，生成的初始調度方案如表2所示。

表2 仿真實驗初始調度方案(部分)Tab.2 Initial schedule scheme of simulation experiment (partial) 單位：s

為了驗證啟發因子本身設計的有效性，本文從2種設計的算法中分別加入和不加入啟發因子2種情況進行對比，為了方便對以下實驗結果管理，做以下名稱替換：

(a) 表示未加任何啟發式策略的改進迭代法；

(b) 表示加了時間窗口擁擠度，以及基于重疊度的開始執行時間啟發因子的改進迭代法；

(c) 表示沒有加入任何啟發因子的ISR-HA算法；

(d) 表示在直接插入過程、移位插入過程和替換插入過程中均加入了兩種啟發因子的ISR-HA算法。

通過設置動態任務集的個數(10、20、100和200)來對上述各個算法分組仿真，為避免少數實驗的隨機性造成的影響，本文將每種算法迭代 10 次，得到的衛星調度結果如表3所示。

表3 各算法動態插入任務規劃仿真實驗結果表Tab.3 Simuliation experiment result of dynamic insertion of algorithms into a task planning

以任務收益和擾動測度作為最后對比的參考結果，具體結果如圖8所示。

圖8 4種算法任務調度收益對比Fig.8 Comparision of task scheduling benefits among four algorithms

由圖8可以看出，當動態任務集個數較少時(個數為10和20)，緊急任務集與已安排任務集沖突度較小，4種算法都能完成已安排任務和動態任務集，無觀測收益上的差別；當動態任務集個數較多時(個數為100和200)，緊急任務集與已安排任務集沖突度較大，ISR-HA算法的觀測收益要高于II-HA算法的觀測收益，其中ISR-HA比II-HA平均收益提高5.8%，并且加入2種啟發式因子的算法與不加啟發式因子的算法對比，明顯有觀測收益上的提高，其中II-HA和ISR-HA的平均收益分別增加5.2%和9.5%，證明了本研究2種啟發因子的有效性。4種算法任務擾動測度對比如圖9所示。

圖9 4種算法任務擾動測度對比Fig.9 Comparision of task disturbance measures among four algorithms

由圖9可以看出，當動態任務集個數較少時(個數為10和20)，緊急任務集與已安排任務集沖突度較小，4種算法都能完成已安排任務和動態任務集，在任務擾動測度上無明顯區別；當動態任務集個數較多時(個數為100和200)，緊急任務集與已安排任務集沖突度較大，II-HA算法的擾動測度起初低于ISR-HA算法的擾動測度，但隨著沖突度的增加，II-HA算法的擾動測度迅速增加并遠遠超過ISR-HA算法的擾動測度，另外加入2種啟發式因子的算法與不加啟發式因子的算法對比，明顯有擾動測度上的降低，其中II-HA和ISR-HA的平均擾動測度下降34%和34.4%，證明了本研究2種啟發因子的有效性。

5 結束語

衛星對地觀測任務規劃問題已經被證明是NP-Hard問題。本文針對衛星任務規劃調度的動態調整需求，將所有的任務劃分為已完成任務、已安排任務和新任務。第一步，對衛星任務動態調度問題進行統一描述，包括新任務的插入、已安排任務的取消、任務優先級的變更、天氣條件的變化和衛星資源狀態的變化描述為新任務的插入；第二步，以最大任務收益和最小任務擾動測度為目標函數構建完成任務動態調度優化模型，設計可見時間窗口擁擠度和執行時刻點重疊度2種啟發式因子；最后，提出基于啟發式智能ISR-HA算法尋求最優任務編排結果。