一種面向周期性連續觀測任務的多星協同規劃算法

邢立剛，徐啟勝，王執龍

(1.合肥工業大學 管理學院，安徽 合肥 230009；2．過程優化與智能決策教育部重點實驗室，安徽 合肥 230009；3.安徽三禾一科技信息有限公司，安徽 合肥 230031;4.智能互聯系統安徽省實驗室，安徽 合肥 230009)

0 引言

對地觀測衛星(Earth Observing Satellite,EOS)作為一種重要的航天飛行器，主要通過搭載的傳感器從太空中獲取地球表面相關圖像數據，并將數據傳回到地面供專業人員進行分析，提取有用信息交由用戶使用[1-3]。EOS具有覆蓋范圍廣、持續時間長、不受時間、地域和國界限制以及不涉及人員安全等優點，在資源勘探、環境監測、軍事偵查和災后救援等領域具有重要的作用[3-5]。

在EOS實際應用中，存在許多對目標進行周期性輪巡的需求，如針對火災易發區，需要采用高低軌衛星聯合拍攝的方式進行觀測，使用高軌衛星每日針對重點區域巡查，發現災害地點后，再通過多顆低軌高分辨率衛星對災害區域進行多次成像[6-8]。災害發生后，需要對災害地點進行持續一段時間的連續觀測，而這種聯合拍攝的方式不能滿足災害監測場景下的連續觀測時長需求，進而對衛星任務規劃帶來了新的挑戰。

衛星任務規劃技術是以滿足多源、時變的用戶需求為目標，對大量異質的星地資源運行過程進行協同優化的技術，其求解已經被證明為NP-hard問題[9-11]，該問題得到了國內外許多學者的高度關注。夏忠等[12-14]分別提出了針對移動目標的搜索方法，能有效解決多星聯合下的移動目標搜索問題。WU等[15-17]應用最小派系劃分思想實現衛星任務合成，基于圖論建立模型，并設計了啟發式算法對問題進行求解。然而，極少有學者針對周期輪巡類的任務需求展開研究，莊超然等[18]通過分析舉例說明了高分四號衛星可在1 d安排5～6次對火災高風險區域的高頻密集輪巡拍攝。王凌峰等[19]基于分解的多目標進化算法框架，提出了組網衛星周期性持續觀測任務規劃方法，但是也沒有滿足對地面目標進行連續觀測的需求。

為解決考慮連續觀測時長的周期輪巡問題，本文首先對任務進行預處理以滿足任務的周期性需求。然后，設計了連續觀測時間窗生成算法(Generation of Continuous Observation Time Windows Algorithm,GCOTWA)，將多顆衛星的時間窗進行拼接以實現對地面目標的連續觀測。最后，仿真試驗的結果充分驗證了該算法的可行性和有效性。

1 問題描述與建模

1.1 問題描述

不同的衛星分布在若干預先設定的軌道面上，衛星每次經過地球上空時會在地球上產生1條二維掃描帶(成像條帶)，這條掃描帶即衛星的觀測范圍，處于這個掃描帶范圍的地面目標都有機會被衛星觀測。衛星飛行至地面目標上空時，星載傳感器開機便可完成1次對目標的觀測，衛星對地面目標從可見到不可見的時間段稱為可見時間窗，簡稱時間窗。地面上的同一目標可被多個衛星的成像條帶所覆蓋，而不同軌道、不同衛星對該目標的可見時間窗不同。

與常規任務所要求的地面目標被觀測到為結束條件不同，周期輪巡任務要求多顆衛星相互協同對地面同一目標進行周期性多次觀測，而針對考慮連續觀測時長的周期輪巡任務，還要求在每個頻次內對地面目標進行一定時長的連續觀測，且任務要求的連續觀測時長遠遠大于衛星單次過境的成像時長。如何同時滿足該類任務中周期輪巡和對地連續觀測這2個需求是當下亟待解決的問題。

該問題中需要介紹一些相關概念如下：

① 頻次：周期輪巡任務的一個周期稱為頻次。

② 連續觀測時長要求：任務要求獲得某一地面目標持續一定時間的成像信息。

③ 執行時間窗：已成功被規劃到方案中的時間窗稱為執行時間窗。

④ 連續觀測時間窗：時間窗拼接后所生成的可以對地面目標進行連續觀測的時間窗集合。

1.2 模型構建

1.2.1 變量描述

文中變量定義如下：

T={1,2，…,i,…,NT}表示任務集合；

S={1,2,…,j,…,NS}表示衛星集合；

G={1,2,…,k,…,NG}表示地面站集合；

ti=表示每一個任務ti∈T可以通過一個五元組表示，其中，vei表示任務i收益，dui表示任務i的連續觀測時間，ari表示任務i從外界到達系統的時間，dei表示任務i完成期限，ni表示任務i需要執行的頻次；

ΔTj表示第j顆衛星相鄰2次執行任務間的最短時間間隔；

LWj表示衛星j上第d-1個地面站開始時間到第d個地面站開始時間之間的任務時間窗集合；

gci表示執行任務i產生的數據需要的存儲量；

gsj表示衛星j的最大存儲容量。

1.2.2 整數規劃模型

① 目標函數：所有任務的觀測收益之和最大。

(1)

② 同一衛星相鄰2次執行時間窗最短時間間隔約束。星載傳感器關機之后，必須經過一段時間才能再次開機。

(2)

③ 每個觀測任務最多只能被執行一次。

(3)

④ 每個地面站時間窗都會被執行。

(4)

⑤ 每個衛星對每個任務的執行時間窗必須在可見時間窗內。

(5)

⑥ 存儲限制。

(6)

⑦ 每個任務的執行開始時間必須晚于其到達系統的時間。

(7)

2 算法設計

針對考慮連續觀測時長的周期輪巡問題，本文首先通過預處理劃分周期頻次，在每個頻次內通過時間窗的拼接生成連續觀測時間窗；然后設計了3個啟發式因子計算所生成的連續觀測時間窗的優先級；最后依據優先級將連續觀測時間窗更新到當前方案，整個方案規劃流程如圖1所示。

圖1 方案規劃流程Fig.1 Scheme planning process

在連續觀測時間窗生成階段，由于單顆衛星對地面目標的觀測時長有限，為滿足該問題的連續觀測時長要求，將多顆位于不同軌道衛星的空閑時間窗進行統計并按照起始時間進行排序，然后將相繼過境的衛星時間窗進行拼接以生成連續觀測時間窗，多星協同實現對地面目標連續觀測的時間窗拼接流程如圖2所示。

圖2 時間窗拼接流程Fig.2 Process of time window splicing

2.1 周期性任務預處理

在進行方案規劃之前加入預處理階段，該階段主要目的是實現周期頻次劃分，其主要步驟如下：

周期性任務預處理輸入:任務數據taski、已有規劃方案Plan輸出:該頻次內的時間窗集合{TTWij|i∈T,j∈S}1.讀取任務數據taski、已有規劃方案Plan;2.識別任務所有時間窗中最早和最遲時間窗的開始時刻first_start和last_start;3.讀取規劃頻次i和當前規劃頻次開始時刻start_timei;4.ifi=0:5. start_timei=first_start;6.計算當前規劃頻次的結束時刻end_timei = start_timei+last_start-start_timein-i;7.讀取并返回開始時刻在時間start_timei和end_timei之間的時間窗集合{TTWij|i∈T,j∈S}。

2.2 GCOTWA設計

2.2.1 啟發式因子

針對周期性連續觀測任務的規劃特征，為計算所生成連續觀測時間窗的優先級，設計了3個啟發式因子用于指導方案的生成。

① 時間窗集合沖突度因子

考慮衛星資源的稀缺性，連續觀測時間窗占用的時間窗口數量越少表示與其余任務時間窗沖突度越低，具體計算過程如下：

(8)

(9)

(10)

式中，dui為任務要求的連續觀測時長(以秒計)；Numfloor為以1 020 s計算得出的時間窗數量的下限；Numup為以480 s計算得出的時間窗數量的上限；num為當前連續觀測時間窗內時間窗的數量；num_facti為該連續觀測時間窗的時間窗集合沖突度因子。

② 觀測時長滿足度因子

為保證任務的觀測時長要求，通過連續觀測時間窗時長與要求觀測時長進行計算，并對其進行分段映射處理，具體計算過程如下：

(11)

(12)

式中，first_starti和last_endi分別為任務i在連續觀測時間窗內最早觀測時間窗的開始時間和最遲觀測時間窗的結束時間；dui為任務要求的連續觀測時長；con_rati表示連續觀測時間窗與任務要求連續觀測時長的比值；sati_rati為該連續觀測時間窗口的時長滿足度因子。

③ 時間窗集合時效性因子

任務完成的時效性是一個重要影響因素，本文采用每個連續觀測時間窗口的最早觀測時間窗的開始時刻作為時效性因子計算的依據，具體計算過程如下：

time_idi=sort(win_starti),

(13)

(14)

式中，sort為排序函數，按照時間窗開始時間的先后順序進行排序，序號從0開始；win_starti為第i個連續觀測時間窗的首個觀測時間窗的開始時間；time_idi為該連續觀測時間窗的時效性序號；time_effi為該連續觀測時間窗的時效性因子。

2.2.2 連續觀測時間窗生成算法

GCOTWA可以對一個目標提供由多個時間窗拼接形成的連續觀測時間窗集合，具體算法如下：

GCOTWA輸入:任務數據taski、待規劃任務時間窗數據{TTWij|i∈T,j∈S}、已有規劃方案Plan輸出:更新后的方案new_Plan1.讀取taski,將時間窗按照開始時刻升序排列{ob_winii∈T};2.將當前時間窗標識now_winid初始化為排序后時間窗集合的首個時間窗標識;3.設置當前連續區間標識inter_id取值為0;4.調用算子2.2,返回可插入時間窗標識 now_winid、遍歷完成標識is_last;5.ifnow_winid!=null且is_last=false:6. inter_id+=1;7. 將now_winid根據inter_id更新到當前連續區間;8. 調用算子2.1,返回后續時間窗標識next_winid、遍歷完成標識is_last、帶有inter_id標識的復制方案集合;9.else if now_winid!=null且 is_last=true:10. inter_id+=1;11. 將now_winid根據inter_id更新到當前連續區間;12. 在當前時間窗對應位置保存時間間隔為0;13.else if inter_id==0:14. 跳轉至17;15.選擇連續時長大于15 min的連續觀測時間窗,并計算啟發式因子值及區間優先級;16.選用優先級最高的連續觀測時間窗對應的復制方案new_Plan替換當前方案;17.返回更新后的方案new_Plan。

在連續觀測時間窗計算方法中使用了2個非常重要的算子：連續區間判斷與生成算子和沖突判斷算子。

① 連續區間判斷與生成算子

連續區間判斷與生成算子主要通過時間閾值判斷時間窗的連續性，將連續時間窗歸為1個時間窗連續區間，并對同一連續區間內的時間窗加入連續區間編號標識和與其后時間窗的時間間隔(最小值為0)，每個連續區間的最后1個時間窗的時間間隔設置為0，具體計算流程如下：

② 沖突判斷算子

沖突判斷算子主要負責根據傳入的觀測時間窗標識判斷其對應時間窗與已有方案的沖突性，并將結果反饋，具體流程如下：

算子2.2.沖突判斷算子輸入:待判斷時間窗標識next_winid,排序后的時間窗集合{ob_winii∈T}、已有規劃方案Plan、當前連續觀測時間窗口集合內已被加入選擇標簽的時間窗集合輸出:可插入時間窗標識 now_winid、遍歷完成標識is_last1.根據next_winid和{ob_winii∈T}讀取待判斷時間窗子集{pend_ob_winii∈T},聲明是否遍歷完成變量is_last=false;2.for pend_ob_wini in {pend_ob_winii∈T}:3. if直接插入失敗且不為最后一個時間窗:4. Continue;5. else if直接插入失敗且為最后一個時間窗:6. is_last=true;7. return now_winid=null,is_last;8. else if直接插入成功且不為最后一個時間窗:9. return now_winid=pend_ob_wini對應標識,is_last;10. else if直接插入成功且為最后一個時間窗:11. is_last=true;12. return now_winid=pend_ob_wini對應標識,is_last。

3 仿真試驗

為了驗證本文提出算法的可行性和有效性，構建了時間窗拼接場景生成時間窗數據，并通過GCOTWA進行方案規劃。

3.1 仿真參數設置

構建了時間窗拼接場景，設置了16顆分布于不同軌道的電子衛星、2個地面站和10個待規劃的點目標任務，單頻次任務規劃時段為24 h，經過軌道計算最終生成時間窗數據共計324條。每個任務包含多個屬性，部分任務及屬性如表1所示。

表1 任務屬性Tab.1 Task attributes

3.2 仿真試驗及結果分析

經過仿真試驗對時間窗進行拼接，拼接結果顯示,每個任務都生成了不少于4個連續觀測時間窗。以任務1為例，時間窗拼接結果如表2所示。

表2 時間窗拼接結果Tab.2 Results of time window splicing

為選擇最優的時間窗集合插入方案，分別計算了它們的啟發式因子值，以任務1為例，所有生成的連續觀測時間窗的啟發式因子如圖3所示。

圖3 PT1啟發式因子值Fig.3 Heuristic factor values of PT1

由圖3可以看出，不同時間窗集合的3個因子值之間差距較大，因此任務屬性中對每個因子權重的要求會對方案插入時所選擇的時間窗產生較大影響。

方案更新結果如表3所示，PT1_1中的時間窗成功更新到方案中，時間窗持續時間為2 642 s，滿足任務所要求的1 800 s觀測時長，仿真試驗充分證明了GCOTWA的可行性和有效性。

表3 方案更新結果Tab.3 Results of scheme updates

4 結束語

針對考慮連續觀測時長的周期輪巡問題，建立了約束模型，提出了對任務進行周期頻次劃分的預處理方法，并設計了一種啟發式算法——GCOTWA對方案進行規劃。仿真試驗結果表明，GCOTWA能夠有效地進行時間窗的拼接，并將生成的連續觀測時間窗更新到方案中。

基于本文所提出的方法，有以下問題可以進一步思考。首先，在衛星數量足夠多時，必然會出現所拼接的連續觀測時間窗過長的問題，為避免衛星資源的浪費，可以考慮對子區間進行劃分。其次，在連續區間判斷與生成算子中，時間窗拼接時閾值的限制可以考慮放到沖突判斷算子中，進而減少時間窗的約束檢查以提高效率。