基于TVNS的敏捷對地觀測衛星自主動作規劃算法

劉 嵩，孔鴻濱，肖皇培

(廣州城市理工學院 計算機工程學院，廣東 廣州 510800)

0 引言

傳統管控模式下，衛星依靠地面上注的動作指令來完成觀測和數據回傳任務。上注指令前，地面首先要預估衛星狀態，再根據用戶需求提前為衛星制定任務執行方案，然后再將方案轉換成相應的衛星動作指令。該過程會受到地面預估誤差、星地通信時間窗口等限制，而且指令一旦上注無法隨意變更，這將導致衛星很可能錯過對重點目標的最佳成像時機，無法快速靈活地根據自身狀態應對隨時可能到達的動態觀測需求。

為了解決上述問題，各國學者越來越重視衛星自主任務調度技術方面的研究[1-8]，但關于衛星自主動作規劃方面的研究較少。自主任務調度和自主動作規劃考慮的約束不同[9]，比如任務調度不會考慮衛星動作對電量的消耗和姿態轉換時間等[10-11]。因此，任務調度結果并不能直接轉換成一個有效的動作執行序列，只有解決了自主動作規劃問題，才能真正實現衛星的自主性，從而實現對地觀測數據的智能化實時服務[12-14]。

針對衛星自主動作規劃問題，文獻[15]提出了一種啟發式算法，該算法首先根據概率選擇動作序列，確定動作序列中的各個動作，然后再根據動作序列的類型，在任務集合中選擇動作序列所對應的任務，并根據任務確定每個動作的執行時間。由于動作序列和任務的選擇都是隨機的，所以搜索過程存在盲目性，很難在有限的迭代次數中找到最優解。針對上述不足，本文提出了一種基于三階段變鄰域搜索(Three-stage Variable Neighborhood Search，TVNS)的敏捷對地觀測衛星自主動作規劃算法。算法考慮了衛星在工作過程中需要執行的9種衛星動作，通過仿真實驗驗證了該算法的有效性。

1 問題描述與建模

敏捷對地觀測衛星自主動作規劃問題可以描述為：面對隨時可能到達的觀測需求，敏捷對地觀測衛星能夠在不需要或較少依靠地面人員干預的情況下，自主制定動作規劃方案，在快速響應動態觀測需求、提高觀測時效性的同時，實現以盡可能少的資源消耗獲取盡可能大的觀測收益。

本文使用時間線約束網絡建模方法對問題進行建模，該方法能夠針對離散事件動態系統進行建模，文獻[16-17]對該方法進行了詳細闡述。模型考慮了9種衛星動作，分別是對地觀測動作ob，用于完成對地面目標的觀測；數據回傳動作dl，用于將目標圖像數據回傳至地面站；姿態轉換動作sw，用于使衛星從一種姿態轉換到另一種姿態，從而觀測不同的目標；對日定向動作sp，用于將太陽帆板保持正對太陽，從而使充電速率達到最大；對地定向動作ge，用于實現三軸穩定對地定向，使衛星持續保持最低能量消耗狀態；相機開機動作obon和天線開機動作dlon，用于使相機或天線達到工作狀態；相機關機動作oboff和天線關機動作dloff，用于使相機和天線結束工作狀態。

模型中將每個動作的開始時刻和結束時刻按時間先后順序進行編號，第1個動作的開始時刻的編號為1，即在時間編號1處開始執行，最后一個動作的結束時刻的編號為h，即在時間編號h處結束執行。ti表示時間編號i處的具體時間。如果用a表示9種衛星動作中的任意一種，則ai表示動作a在時間編號i處的狀態，如ai=1表示動作a在ti處開始執行，ai+1=0則表示動作a在ti+1處結束執行。sa表示動作a的開始時間，ea表示動作a的結束時間。

1.1 模型的輸入輸出

模型輸入：任務序列sequence可以是一個經過任務調度后的任務序列，也可以是一個按時間窗口先后順序進行排序的任務序列。任務序列中每個觀測任務j所對應的優先級wj，占用固存大小cj，觀測持續時間oj和數據回傳持續時間dj，能夠對任務j進行觀測的衛星圈次的集合Mj，以及在圈次k對任務j進行觀測時，所對應的觀測時間窗口的開始時間sj,k和結束時間ej,k。數據回傳時間窗口集合I中每個數據回傳時間窗口i所對應的開始時間bi和結束時間ri。衛星固存最大值C。電量的上限ENmax，電量的下限ENmin，姿態轉換速度MS。還包括每個地影區、陽照區的開始和結束時間。

模型輸出：任務序列sequence中每個任務j所對應的決策變量xj,k和yj,i。如果衛星可以在圈次k對任務j進行觀測，即該觀測任務能夠轉換成具體的衛星動作，則xj,k=1；否則xj,k=0。如果任務j的觀測數據在數據回傳窗口i中被回傳，即該數據回傳任務能夠轉換成具體的衛星動作，則yj,i=1；否則yj,i=0。還包括執行每個任務的具體動作和每個動作的開始時間和結束時間。

1.2 目標函數與約束條件

優化目標是使得完成觀測任務和數據回傳任務的累積收益最大，目標函數為：

(1)

約束條件：

?i∈[1,h-1],

ENmin≤eni≤ENmax∧ENmin≤eni+1≤ENmax，

(2)

式中，mmi和eni分別表示在時間編號i處的剩余固存和電量。任何動作都存在執行的結束時刻，任何2個動作不能同時執行。任意時刻的衛星固存都不能超出衛星最大固存限制。任意時刻的衛星電量都不能超出衛星電量上限和下限。

?i∈[1,h-2],

(3)

?i∈[3,h],

(eni+1=eni)，

(4)

?i∈[1,h-3],

(eni+1=eni)，

(5)

?i∈[3,h],

(eni+1=eni)，

(6)

?i∈[1,h-2],

(7)

觀測動作之后可以連續執行相機關機動作或者是姿態轉換動作。

?i∈[1,h-2],

(8)

數據回傳動作之后可以連續執行天線關機動作或者是數據回傳動作。

?i∈[1,h-4],

(obi=1)∧(swi+2=1)→(obi+4=1)∧(ti+4-ti≤obmax)，

(9)

如果觀測動作執行結束后連續執行姿態轉換動作，則說明連續2次觀測動作的時間間隔小于閾值obmax。此種情況不需要相機關機動作。

?i∈[1,h-2],

(dli=1)∧(dli+2=1)→(ti+2-ti≤dlmax)，

(10)

如果數據回傳動作執行結束后連續執行數據回傳動作，則說明在同一個數據回傳窗口連續回傳不同的觀測任務數據，并且連續2次數據回傳動作的時間間隔小于閾值dlmax。此種情況不需要天線關機動作。

?i∈[1,h-1],

(obi=1)→(?j,k,sj,k≤sob

(mmi+1=mmi-cj)∧(eni+1=eni-Pob·oj)，

(11)

式中，sj,k和ej,k分別表示在第k個軌道圈次上對任務j進行觀測的觀測時間窗口的開始時間和結束時間；oj表示觀測任務j的觀測持續時間；cj表示觀測任務j占用衛星固存的大小；Pob表示觀測動作單位時間耗電量。觀測動作的開始和結束時間必須在某個觀測任務的某個觀測時間窗口內，觀測動作的持續時間等于該觀測任務所需要的觀測持續時間，觀測過程中固存和電量都在減少。

?i∈[1,h-1],

(dli=1)→(?j″,k)(bk≤sdl

(mmi+1=mmi+cj)∧(eni+1=eni-Pdl·dj″)，

(12)

式中，j″表示觀測任務j對應的數據回傳任務；bk和rk分別表示第k個數據回傳窗口的開始時間和結束時間；dj″表示j″的回傳持續時間；Pdl表示數據回傳動作單位時間耗電量。數據回傳動作的開始和結束時間必須在某個數據回傳時間窗口內，動作的持續時間等于被回傳任務所需要的數據回傳持續時間，數據回傳過程中固存增加，電量在減少。

?i∈[1,h-3],

(13)

?i∈[1,h-1],

(gei=1)→(mmi+1=mmi)∧(eni+1=eni)，

(14)

對地定向動作執行期間衛星固存不變，電量不變。

?i∈[1,h-1],

(spi=1)→(?k,SSk≤ti

(eni+1=eni+Psun·(esp-ssp+1))，

(15)

式中，SSk表示在第k個軌道圈次上的陽照區的開始時間；ESk表示在第k個軌道圈次上的陽照區的結束時間。對日定向動作必須要在某個陽照區內進行，動作執行期間衛星固存不變，電量增加。

2 任務、動作之間的轉換方法

本文將衛星任務分為3類：對地觀測任務、數據回傳任務和對日定向任務。根據問題模型，將9種衛星動作組合成對地觀測動作序列、數據回傳動作序列和對日定向動作序列，分別用來完成上述3類任務。每一類動作序列可以由不同的衛星動作以不同的次序組合而成，動作的前后關系代表動作的執行順序。每一類動作序列都有3種可能的動作組合，如表1所示。

表1 動作序列構成表Tab.1 Constitute of action sequence

根據問題模型，可以確定前后2個動作序列的銜接關系，如表2所示。只要確定了前一個動作序列和當前動作序列的類型，即可確定當前動作序列的具體動作。比如針對一個觀測任務，首先可以確定要轉換成對地觀測動作序列。如果前一個動作序列是對地觀測序列，根據表2，應該選擇觀測動作序列中的②號動作組合。

表2 動作序列銜接關系選擇表Tab.2 Link relation between different action sequences

3 時間計算方法

動作序列確定后，要進一步確定動作序列中每個動作的開始和結束時間。針對每一個動作序列，首先計算該動作序列中最后一個動作的結束時間，再計算該動作的開始時間，然后由后至前計算每一個ti，即每個動作的結束時間和開始時間。方法流程如圖1所示。

圖1 對地觀測流程Fig.1 Earth observation process

針對對地觀測動作序列，首先對任務j(該動作序列要完成的任務)的時間窗口進行裁剪[6]。然后選擇離上一個動作序列中最后一個動作的結束時間Tlast最近的時間窗口。最后根據該窗口的結束時間winend計算觀測動作的結束時間，具體計算公式如表3所示。如果ssw

表3 時間計算公式Tab.3 Time calculation formula

針對數據回傳動作序列，首先對數據回傳窗口進行裁剪，然后在可用的數據回傳時間窗口中，選擇離Tlast最近的時間窗口，最后根據該窗口的結束時間winend計算數據回傳動作的結束時間。如果sdlon-edloff

針對對日定向動作序列，如果存在相機關機動作或者是天線關機動作，那么該動作應該在Tlast的下一秒開始執行。對日定向動作的持續時間為固定值，用dsp表示。

由于觀測動作序列和數據回傳動作序列中各動作的執行時間計算方法都使用了時間窗口的結束時間作為觀測或數據回傳動作的開始時間，因此動作開始時間存在向前移動的可能。具體移動方法步驟如下：

步驟①：從前至后，選擇第1個未調整的動作序列中的對地觀測動作或數據回傳動作。計算觀測或數據回傳動作的開始時間與該動作對應的時間窗口開始時間的時間間隔TL，如果小于等于4 s，則說明沒有移動的必要，則轉步驟④。

步驟②：以TL的1/4長度作為滑動步長，將觀測動作或數據回傳動作的開始時間向前滑動，重新計算觀測或數據回傳動作的執行時間，然后計算動作序列中其他動作的執行時間。

步驟③：進行約束檢查，如果滑動后，動作序列中的各個動作的執行時間都滿足約束條件，則采用滑動后的動作執行時間，并轉步驟①；否則，取消滑動，不改變動作序列中各個動作的執行時間。

步驟④：算法結束。

4 算法設計

4.1 算法思想

算法的求解過程分為3個階段：

第1階段，根據轉換規則，按任務序列中的任務次序，從前至后依次將任務轉換成所對應的衛星動作序列，并確定每個動作的開始和結束時間，從而獲得初始解。初始解由任務序列、決策變量和確定執行時間的全部衛星動作共同構成。該過程沒有考慮對日定向動作和對地定向動作，因此部分任務可能由于電量不足，無法轉換成衛星動作。

第2階段，針對初始解，采用變鄰域搜索的方法進行搜索，尋找更優解。在每一個鄰域內進行搜索的次數達到lmin時，則視為已經陷入局部最優，必須改變鄰域結構。搜索過程中，如果搜索到一個更優的解y，則說明該鄰域有利于解的改進，并將y替換x作為搜索起點，繼續在該鄰域內搜索。變鄰域搜索的目的有2個：一個是通過插入合適的對日定向任務，通過補充電量，從而完成更多的任務；另一個是通過調整對地觀測任務的執行次序，以獲得更高的收益。

第3階段，針對當前解中的動作，如果2個動作之間的時間間隔大于10 min，那么在這2個動作之間要插入一個對地定向動作。比如在地影區，如果不進行數據回傳，那么衛星需要執行對地定向動作。

算法的最大迭代次數為lmax，當達到該條件則算法停止，算法流程如圖2所示。

圖2 算法流程Fig.2 Algorithm flow chart

4.2 鄰域結構設計

(1) 對日定向任務插入鄰域

在當前解中找到最后一個決策變量xj,k=1的對地觀測任務j，該任務用x0表示。然后在x0左側，除了在2個連續數據回傳任務之間的任意位置，插入一個對日定向任務，或者在x0之后的第1個位置插入一個對日定向任務。對日定向任務用xk表示。每次選擇一種插入方式，2種方式的選擇概率均為50%。插入對日定向任務之后的任務序列即當前解的對日定向任務插入鄰域，如圖3所示。

圖3 對日定向任務插入鄰域Fig.3 Insertion neighborhood of sun-pointing tasks

插入對日定向任務之后，衛星將執行對日定向動作序列，電量將獲得提升，因此增加了該對日定向任務之后各個任務的完成機會。之所以不在連續2個數據回傳任務之間插入對日定向任務，是因為數據回傳資源比較有限，而且數據回傳任務有可能在地影區執行，此時無法對日定向。

(2) 對地觀測任務插入鄰域

在當前解中找到最后一個決策變量xj,k=1的對地觀測任務j，該任務用x0表示。然后在x0之后，選擇k個決策變量為0的觀測任務，這k個任務分別用x1,x2,…,xk表示。最后在x0左側任意位置插入x1,x2,…,xk，從而得到一個全新的任務序列，即當前解的對地觀測任務插入鄰域，如圖4所示。一般來說，如果將某些觀測任務移至更靠前的位置，這些任務能夠被執行的可能性會增加，從而有機會提高解的質量。如果x0之后，決策變量為0的觀測任務數量為n，那么k為1～0.1×n的隨機整數。

圖4 對地觀測任務插入鄰域Fig.4 Insertion neighborhood of earth observing tasks

5 實驗結果及分析

實驗中衛星的軌道參數來自北美空防司令部2017年5月公布的WorldView-2衛星軌道數據。觀測目標為點目標，分布在衛星星下點軌跡附近。每個觀測任務都由任務編號、軌道編號、任務優先級、觀測時間窗口和觀測持續時間等相關信息構成。實驗計算機配置為Intel(R) Core(TM) i5-7200U CPU@2.50 GHz，內存為8 GB，操作系統為Windows 10，編程環境為Matlab。

假設每個觀測任務的觀測持續時間5～30 s，每個觀測任務的數據回傳持續時間是觀測持續時間的2倍，每個觀測任務的優先級為1～10。實驗中用觀測持續時間代替具體的固存占用大小，假設衛星固存最大可容納2 400 s的觀測數據。根據地影預報，衛星每軌處于陽照區的時間大約是60 min。如果假設衛星在每個陽照區只要充電20 min剛好可滿足其余40 min的電量消耗，那么可以進一步假設對日定向動作每秒增加2個單位的電量，對地定向動作時不消耗電量，其他動作每秒消耗1個單位的電量。基于上述假設，衛星初始電量和最大電量可以設置為2 400個單位。假設衛星最大俯仰和側擺能力均為45°，姿態轉換速度為4 (°)/s。假設每一個對日定向動作的持續時間為5 min，相機開機穩定時間為5 s，相機關機延遲時間為2 s，天線開機和天線關機的持續時間為2 s。obmax和dlmax為30 s。假設有1個機動地面站可以提供5個數據回傳時間窗口，單個數據回傳時間窗口平均長度為720 s。

實驗分為11組，每組觀測任務數量不同，每組實驗進行10次，取平均值作為最終結果。lmax=100，lmin=lmax/3實驗過程中，首先使用文獻[18]中的算法進行任務調度，然后以任務調度結果作為輸入，進行動作規劃。

實驗結果如圖5所示。任務調度結果與動作規劃結果的曲線并沒有重合，而且任務調度結果所反映的任務完成率要明顯高于動作規劃結果。這說明，任務調度之后并不意味著調度方案全部都可以執行，有些任務是無法轉換成衛星動作的。這主要是因為在每個陽照區，不但要完成對地觀測，還要進行對日定向，完成必要的充電。因此對日定向會占用一些任務的時間窗口，導致部分任務無法完成。如果不進行對日定向，電量約束又會制約其他衛星動作的執行。另外，在任務調度結果中可行的2個連續任務，它們之間的時間間隔可能并不滿足衛星動作連續執行的條件，因此不能接續執行，即其中一個任務無法完成。

圖5 任務調度與動作規劃對比Fig.5 Comparison of task schedule and action planning

在有限的迭代次數下，本算法要優于文獻[15]中的算法，對比結果見圖5。這是因為實驗中，本算法是以調度結果為輸入，然后再根據輸入的任務次序確定動作序列。不但初始解相對較優，而且在搜索過程中用鄰域結構引導搜索方向。而文獻[15]中的算法，無論是動作序列還是任務，都是以一定的概率進行選擇，沒有明確的鄰域結構，因此在有限的迭代次數中對解的改進是有限的。另外，本算法還考慮了解中動作執行時間存在向前移動的可能，并給出了調整方法，使得在一定的時間內，能夠執行盡可能多的動作，因此可以得到更好的解。

觀測任務完成數量如圖6所示。隨著任務數量的不斷增加，衛星每天可以觀測的任務數量逐漸增加，并在230個任務附近處趨于平穩，這說明230個任務接近實驗中每天觀測的最大任務數量，這主要是由固存、數據回傳時間窗口、電量約束和衛星動作約束造成的。實驗中數據回傳時間窗口的利用率能夠穩定在80%～90%，如圖7所示。如果數據回傳時間窗口剩余時間不足以回傳下一個任務，那么該剩余部分將會被舍棄，該任務將放在下一個數據回傳時間窗口中回傳，這就造成了時間窗口不能被完全利用。另外，數據回傳任務需要一系列衛星動作完成，除數據回傳動作之外的衛星動作也會占用數據回傳時間窗口。

圖6 觀測任務完成數量Fig.6 Number of the completion of observing tasks

圖7 數據回傳時間窗口利用率Fig.7 Utilization rate of backhual time window

6 結束語

針對敏捷對地觀測衛星自主動作規劃問題展開研究，建立了基于時間線約束網絡的問題模型，并提出了基于TVNS的規劃算法。問題模型考慮了敏捷對地觀測衛星的特點以及9種衛星動作之間的約束條件。通過對模型的分析，不僅歸納出9種衛星動作序列，而且確定了各種動作序列之間的銜接關系，以及動作時間和調整的方法，大大提高了任務到衛星動作的轉換速度。算法以任務調度結果作為初始解，分3個階段，使用2種鄰域結構進行變鄰域搜索，能夠實現任務到動作的快速轉換。實驗結果表明，任務調度結果并不能百分百執行，在星上進行有效的動作規劃是必要的，而且相比文獻 [15]中的算法，基于TVNS的敏捷對地觀測衛星動作規劃算法能夠得到更優的規劃結果。