一種面向周期性連續(xù)觀測任務(wù)的多星協(xié)同規(guī)劃算法

邢立剛，徐啟勝，王執(zhí)龍

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

0 引言

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

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

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

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

1 問題描述與建模

1.1 問題描述

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

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

該問題中需要介紹一些相關(guān)概念如下：

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

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

③ 執(zhí)行時間窗：已成功被規(guī)劃到方案中的時間窗稱為執(zhí)行時間窗。

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

1.2 模型構(gòu)建

1.2.1 變量描述

文中變量定義如下：

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

S={1,2,…,j,…,NS}表示衛(wèi)星集合；

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

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

ΔTj表示第j顆衛(wèi)星相鄰2次執(zhí)行任務(wù)間的最短時間間隔；

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

gci表示執(zhí)行任務(wù)i產(chǎn)生的數(shù)據(jù)需要的存儲量；

gsj表示衛(wèi)星j的最大存儲容量。

1.2.2 整數(shù)規(guī)劃模型

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

(1)

② 同一衛(wèi)星相鄰2次執(zhí)行時間窗最短時間間隔約束。星載傳感器關(guān)機之后，必須經(jīng)過一段時間才能再次開機。

(2)

③ 每個觀測任務(wù)最多只能被執(zhí)行一次。

(3)

④ 每個地面站時間窗都會被執(zhí)行。

(4)

⑤ 每個衛(wèi)星對每個任務(wù)的執(zhí)行時間窗必須在可見時間窗內(nèi)。

(5)

⑥ 存儲限制。

(6)

⑦ 每個任務(wù)的執(zhí)行開始時間必須晚于其到達系統(tǒng)的時間。

(7)

2 算法設(shè)計

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

圖1 方案規(guī)劃流程Fig.1 Scheme planning process

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

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

2.1 周期性任務(wù)預(yù)處理

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

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

2.2 GCOTWA設(shè)計

2.2.1 啟發(fā)式因子

針對周期性連續(xù)觀測任務(wù)的規(guī)劃特征，為計算所生成連續(xù)觀測時間窗的優(yōu)先級，設(shè)計了3個啟發(fā)式因子用于指導(dǎo)方案的生成。

① 時間窗集合沖突度因子

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

(8)

(9)

(10)

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

② 觀測時長滿足度因子

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

(11)

(12)

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

③ 時間窗集合時效性因子

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

time_idi=sort(win_starti),

(13)

(14)

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

2.2.2 連續(xù)觀測時間窗生成算法

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

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

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

① 連續(xù)區(qū)間判斷與生成算子

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

② 沖突判斷算子

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

算子2.2.沖突判斷算子輸入:待判斷時間窗標識next_winid,排序后的時間窗集合{ob_winii∈T}、已有規(guī)劃方案Plan、當前連續(xù)觀測時間窗口集合內(nèi)已被加入選擇標簽的時間窗集合輸出:可插入時間窗標識 now_winid、遍歷完成標識is_last1.根據(jù)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對應(yīng)標識,is_last;10. else if直接插入成功且為最后一個時間窗:11. is_last=true;12. return now_winid=pend_ob_wini對應(yīng)標識,is_last。

3 仿真試驗

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

3.1 仿真參數(shù)設(shè)置

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

表1 任務(wù)屬性Tab.1 Task attributes

3.2 仿真試驗及結(jié)果分析

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

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

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

圖3 PT1啟發(fā)式因子值Fig.3 Heuristic factor values of PT1

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

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

表3 方案更新結(jié)果Tab.3 Results of scheme updates

4 結(jié)束語

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

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