基于多階段決策的偵察衛(wèi)星任務規(guī)劃研究＊

喬熔巖，趙新國

（解放軍裝備學院，北京101416）

0 引言

偵察衛(wèi)星是利用光電遙感器或無線電設備等偵察傳感設備，從軌道上對目標實施偵察、監(jiān)測或跟蹤，通過搜索地面、海洋或空中來獲取軍事情報的人造地球衛(wèi)星［1］。偵察衛(wèi)星的任務規(guī)劃主要涉及兩個問題：一是任務分配問題，即如何把任務科學合理地分配給衛(wèi)星，以最大化滿足用戶的需求；二是傳輸調(diào)度問題，即如何調(diào)配地面接收站和衛(wèi)星傳輸信息的時間，以滿足各個衛(wèi)星在互不沖突的時間窗口內(nèi)，傳輸所獲得的目標信息。

目前任務規(guī)劃模型主要包括：1）Gabrel［2］等人提出的基于圖論的模型，將偵察衛(wèi)星的任務排列轉(zhuǎn)換為一個加權有向無環(huán)圖，求解的目標是尋找一條最大化完成任務的路徑，該模型的缺點在于無法體現(xiàn)完成任務所需的其他約束條件，而且模型只適用于單顆衛(wèi)星；2）Vasquez［3］等人提出的背包模型，該模型的缺點是不能描述復雜任務的約束條件，而且也只適用于單顆衛(wèi)星；3）Bensana［4］等人建立的更一般的線性整數(shù)規(guī)劃，該模型能夠描述完成任務的各個約束，但求解效率會因約束太多而降低；4）Venfaillie［5］等人提出的加權約束模型，該模型可用更自然的語言來描述約束，建立過程較為直觀，但當問題較大時，求解效率較低；5）Damiani［6］等人提出的有限階段序貫決策模型，該模型可以考慮到一些影響局部贏得的不確定因素，但對于某些復雜約束，其求解效率將成指數(shù)速度下降；6）Chien［7］等人建立的狀態(tài)與活動模型，該模型可以描述超出觀察活動以外的所有可能的活動，但模型沒有很好的優(yōu)化功能。上述的這些模型大多都適用于單星，其中的一些模型只涉及了任務分配階段的規(guī)劃，沒有專門對傳輸調(diào)度階段進行建模；還有一些模型將多個過程都建立在一個模型里，造成約束條件較多，目標決策過于復雜，影響了求解的效率。為解決上述問題，本文將結(jié)合偵察衛(wèi)星的特點，根據(jù)任務規(guī)劃不同階段的目標決策，建立基于多階段決策的偵察衛(wèi)星任務規(guī)劃模型。

1 偵察衛(wèi)星的工作特點

偵察衛(wèi)星具有以下特點：第一，軌道相對固定；第二，存儲比較有限；第三，需要時間轉(zhuǎn)換［8］（即衛(wèi)星在連續(xù)執(zhí)行兩個以上任務時，需要有一定的時間轉(zhuǎn)換，否則衛(wèi)星只能完成其中一個任務）。除此之外，偵察衛(wèi)星還具有數(shù)量有限、成本較高的特點，所以在規(guī)劃任務時，應充分利用衛(wèi)星資源，使其盡量兼顧多個任務，以彌補供需的不足。通常衛(wèi)星要靠太陽能供電，其存儲電池可提供應急所需的能量，所以本文在建立模型時，將假設衛(wèi)星可進行全天候的工作。

2 任務分配模型

偵察衛(wèi)星的任務分配是一個動態(tài)過程，但在一段時間內(nèi)基本上是靜態(tài)的，即各用戶不會連續(xù)不斷地提出任務需求。由此本文將整個規(guī)劃過程，分成若干個時間段，將時間段內(nèi)所提出的任務集中處理，以提高分配任務的效率。

2.1 相關定義

定義1：設集合W ＝｛w1，w2，…，wm｝表示某段時間內(nèi)的偵察任務集，其中wi（ri1，ri2，…，rin）表示某項具體任務，riq表示任務wi的一個具體需求，如目標類型、偵察范圍、目標分辨率等。

定義2：設集合S＝｛s1，s2，…，sk｝表示偵察衛(wèi)星集，其中sj（cj1，cj2，…，cjp）表示某顆具體衛(wèi)星，Cj＝｛cj1，cj2，…，cjp｝表示衛(wèi)星sj的屬性（性能）集，cjl（ajl）表示某一具體屬性（性能），如存儲量、數(shù)據(jù)傳輸速率、飛行軌道等，ajl表示屬性（性能）cjl的具體數(shù)值或內(nèi)容。

定義3：如果存在映射f，使得集合S 中的任意元素sj，都能在集合W 中找到若干個元素w1，w2，…，wk與之相對應，則稱映射f 為一個任務分配策略，即。

定義3中的“對應”是指wi分配給衛(wèi)星sj，但有的任務需要一顆衛(wèi)星分多次偵察或多顆衛(wèi)星共同來偵察，對于這種情況，可將該項任務進行分解，變成若干個由單顆衛(wèi)星偵察一次就可完成的子任務，將這些子任務作為一個個獨立的任務來處理，使其符合定義3。

2.2 模型的建立

根據(jù)每項任務的具體需求，結(jié)合衛(wèi)星的屬性（性能），建立如表1所示的對應表。

通過表1對衛(wèi)星進行篩選，找出符合wi需求的擬分配衛(wèi)星集Si＝｛si1，si2，…，siq｝（不考慮Si＝φ 的情況），將與完成任務wi相關的衛(wèi)星屬性集記為Ci＝｛ci1，ci2，…，cil｝，其中衛(wèi)星sij的各屬性值集合記為通 過 層 級 分 析 法［9］，可 確 定 出各衛(wèi)星完成wi的質(zhì)量權重集Zi＝｛zi1，zi2，…，ziq｝，將記為W 的擬分配衛(wèi)星集，且SW?S，建立表2。

表1 對應表

表2 完成質(zhì)量權重表

在表2 中，當sj∈Si時，＝zij；當sj?Si時，＝0。將表2轉(zhuǎn)化為：

式中，xij＝1表示任務wi分配給衛(wèi)星sj，否則xij＝0；dij表示完成wi需占用衛(wèi)星sj的存儲量，d′j表示衛(wèi)星sj的剩余存儲量，利用求解0-1整數(shù)規(guī)劃［10］的方法，可得出衛(wèi)星sj的擬分配任務集Wj。對于衛(wèi)星sj來說，分配任務是一個動態(tài)過程，即在分配新任務之前，衛(wèi)星sj可能還有預定的任務要完成，這就要求新任務不能與原有任務發(fā)生沖突，而且新任務之間也不能有沖突，為此本文建立如圖1所示的任務關系圖。

圖1 任務關系圖

圖1中集合Wj＝｛wj1，wj2，wj3，wj4｝，w＊為原有待完成的任務，將有沖突的兩個任務用直線連接，為找出合理的分配方案，進行如下的圖上作業(yè)法：1）將原任務和與原任務有連線的新任務在圖中刪除（包括連線），即刪除w＊和wj3；2）在剩下的圖中，找出連線最多的任務，即任務wj2；3）找出將與任務wj2沒有沖突的任務，并將它們和wj2編成一組，記為分配策略1；4）將策略1中的任務（包括連線）在圖中去除；5）在剩下的圖中重復第二步驟操作，以此類推，直到把任務全部編組完成；6）比較各分配策略，找出包含任務最多的編組，將該編組作為sj的分配策略Wj0（即初始分配策略）。

按照上述的方法，可以求出每顆衛(wèi)星初始任務的分配策略，然后求出，其 中W′＝｛w′1，w′2，…，w′k｝表示沒有分配到衛(wèi)星的剩余任務集，建立式（2）：

式中，當w′i∈Wj時（避免重復沖突），當w′i?Wj時，d″j表示衛(wèi)星sj在假設完成Wj0中任務后，還剩余的存儲量。通過對式（2）的求解，又可建立各衛(wèi)星新的任務關系圖，然后按照圖上作業(yè)法，確定出新的分配策略，以此類推，直到把所有任務都分配完畢或各衛(wèi)星均已達到飽和狀態(tài)為止。將最終的分配策略記為定義3中的映射f，如果此時還有任務沒有被分配，則這些任務只能等待各衛(wèi)星完成任務后，重新參加下一輪的分配。

2.3 模型的改進

上述的分配模型主要以衛(wèi)星完成任務的質(zhì)量為參考標準，該模型適用于常規(guī)任務的分配需求，而在實際中，有時會出現(xiàn)一些緊急任務或需求用戶的級別較高，用戶需要衛(wèi)星及時提供某區(qū)域的情報，這就要求分配任務時，不但要考慮衛(wèi)星的性能，還要考慮執(zhí)行偵察的時段和完成任務的時限，為解決這一問題，本文將建立如下的改進模型：

根據(jù)任務wi的級別將W 分為兩類，即優(yōu)先任務集W（1）和普通任務集W（2），其中W（1）包括緊急任務和高級別用戶的任務，W（2）包括非緊急的常規(guī)任務，且滿足W ＝W（1）∪W（2），W（1）∩W（2）＝φ。在分配衛(wèi)星資源時，應首先保障W（1）中的任務，然后再考慮W（2）中的任務。假設通過表1確定出為完成W（1）的擬分配衛(wèi)星集，集合表示各衛(wèi)星完成偵察的最短延遲時間，其中表示衛(wèi)星完成任務的最小時延，其大小等于飛到偵察區(qū)域的時間加上執(zhí)行偵察的時間。定義衛(wèi)星完成任務的效能權重為，其中為衛(wèi)星完成任務的質(zhì)量權重，e為調(diào)節(jié)系數(shù)。下面建立目標決策模型，如式（3）所示，其中表示任務占用衛(wèi)星的存儲量表示衛(wèi)星的剩余存儲量，但與式（2）中的d′j不同，因為現(xiàn)在所要執(zhí)行的是優(yōu)先級任務，如果原來預定的任務不是優(yōu)先的，其數(shù)據(jù)可以被替代，以確保優(yōu)先級任務的完成，所以的值只是存儲總量與預定優(yōu)先級任務所需存儲量的差。

3 傳輸調(diào)度模型

將地面接收站集記為集合G＝｛g1，g2，…，gk｝，假設一個接收站在同一時間內(nèi)，只能接受一個衛(wèi)星的數(shù)據(jù)，通常情況下，集合S 與G 不是一一對應關系。一般接收站都會先滿足優(yōu)先級任務，而當多個衛(wèi)星都承擔優(yōu)先級任務時，就要盡量避免這些衛(wèi)星在有沖突的時間段進行數(shù)據(jù)傳輸，為解決這一問題，本文將建立如下的傳輸調(diào)度模型：

第一步，將矩陣中每一列的數(shù)值相加，找出實數(shù)部分最小的一列，并選出該列所對應的時間窗口，例如或（這里以為例）；

第七步，檢驗剩下的矩陣，如果該矩陣為零矩陣，則停止操作，將該矩陣中的時間窗口記為一個調(diào)度策略

第八步，將策略1中的時間窗口在式（4）中刪除，然后重復第一步的操作，以此類推，直到找出新的策略為止，例如策略

第九步，比較各個策略，找出包含時間窗口數(shù)最多的一個，如果數(shù)量相同，則選擇完成時延最小的一個策略。例如策略和假設對于用戶來說，衛(wèi)星選擇比選擇的時延要小，而對于和來說，選擇和要比選擇和的時延要小，那么綜合比較就采用策略

4 結(jié)束語

本文結(jié)合偵察衛(wèi)星的工作特點，依據(jù)任務規(guī)劃不同階段的目標決策，建立了基于多階段決策的偵察衛(wèi)星任務規(guī)劃模型，即任務分配模型和傳輸調(diào)度模型。該模型首先將任務進行分級和分解，然后根據(jù)對應表建立擬分配任務的衛(wèi)星集，從而縮小所涉及衛(wèi)星的范圍，以減少目標決策的數(shù)量規(guī)模，利用層次分析法確定衛(wèi)星完成任務的效能權重，并建立任務分配的決策模型；為避免計算的復雜性，分配模型中的約束沒有涉及完成任務時可能出現(xiàn)的時間沖突，而是在得出擬分配方案后，利用所建立的任務關系圖，通過圖上作業(yè)法來解決，以此使得分配模型更加簡明，計算流程更加清晰，從而提高求解的效率；為解決衛(wèi)星傳輸數(shù)據(jù)時可能發(fā)生的沖突，本文根據(jù)假設的情況，建立了衛(wèi)星傳輸時間的關系矩陣，給出了一種求解模型的基本方法，從而較好地解決了這一問題。綜上所述，本文建立的基于多階段決策的偵察衛(wèi)星任務規(guī)劃模型，具有一定的理論與應用價值?！?/p>

［1］王永剛，劉玉文.軍事衛(wèi)星及應用概論［M］.北京：國防工業(yè)出版社，2003.

［2］Gabrel V，Vanderpooten D.Enumeration and interactive selection of efficient paths in a multiple criteria graph for scheduling an earth observing satellite［J］.European Journal of Operational Research，2002，139（3）：533-542.

［3］Vasquez M，Hao JK.A “Logic-constrained”knapsack formulation and a Tabu algorithm for the daily photograph scheduling of an earth observation satellite［J］.Computational Optimization and Applications，2001，20（2）：137-157.

［4］Bensana E，Verfaillie G，Agnese JC，et al.Exact and approximate methods for the daily management of an earth observing satellite［C］∥Munich，Germany：Symposium on Space Mission Operations and Ground Data Systems，1996.

［5］Bensana E，Verfaillie G.Exact and approximate methods for the daily management of an earth observation satellite［C］∥Proceeding of the 4th International symposium On Space Mission Operation and Control Date System，1996.

［6］Verfaillie G.Russian doll search for solving constraint optimization problems［C］∥Portland，Oregon，USA：Proceedings of AAAI-96，1996.

［7］Chien S，Sherwood R，Rabideau G.The Techsat-21 autonomous space science agent［C］∥Proc of the 1st International Conference on Autonomous Agents.NewYork：ACM Press，2002.

［8］黃文清，等.空間信息系統(tǒng)建模與效能仿真［M］.北京：解放軍出版社，2010：96-97.

［9］胡運權.運籌學教程［M］.北京：清華大學出版社，2007.

［10］陳慶華，等.裝備運籌學教程［M］.北京：國防工業(yè)出版社，2007.

［11］陳慶華，呂彬，李曉松.系統(tǒng)工程理論與實踐［M］.北京：國防工業(yè)出版社，2011.

［12］陳寶林.最優(yōu)化理論與算法［M］.2版.北京：清華大學出版社，2005：37-50.