衛(wèi)星對地觀測任務(wù)規(guī)劃問題簡明綜述

收稿日期：2007-11-28；修回日期：2008-03-26

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目（70601035）

作者簡介：王沛（1982-），男，陜西寶雞人，博士研究生，主要研究方向?yàn)橄到y(tǒng)管理與綜合集成技術(shù)(peigongliu@hotmail.com)；譚躍進(jìn)（1958-），男，湖南長沙人，教授，博導(dǎo)，主要研究方向?yàn)橄到y(tǒng)集成與綜合技術(shù).

(國防科學(xué)技術(shù)大學(xué) 信息系統(tǒng)與管理學(xué)院，長沙410073)

摘 要：衛(wèi)星對地觀測任務(wù)規(guī)劃是為了滿足用戶的遙感圖像需求，對遙感衛(wèi)星系統(tǒng)資源和對地觀測任務(wù)進(jìn)行規(guī)劃與調(diào)度的過程。合理的任務(wù)規(guī)劃是提高遙感衛(wèi)星系統(tǒng)效能的重要手段。為此，分析了衛(wèi)星對地觀測任務(wù)規(guī)劃問題的主要特點(diǎn)，比較了這一問題的若干常用建模方法和求解技術(shù)，并探討了衛(wèi)星對地觀測任務(wù)規(guī)劃技術(shù)的未來發(fā)展趨勢。

關(guān)鍵詞：對地觀測衛(wèi)星；任務(wù)規(guī)劃；模型；算法

中圖分類號：N945; V47

文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2008)10-2893-05

Mission planning problem for earth observing satellites: a survey

WANG Pei， TAN Yue-jin

(School of Information Systems Management， National University of Defense Technology， Changsha 410073， China)

Abstract:Mission planning for earth observing satellites is defined as: in order to satisfy satellite users’ remote sensing observation requirements， scheduling earth observing satellites. Rational mission planning will improve the overall earth obser-ving efficiency of satellites. This paper analyzed the main characteristics of the mission planning problem for earth observing satellites， compared the related modeling methods and algorithms. At last， pointed out future research directions.

Key words：earth observing satellite; mission planning; model; algorithm

0 引言

衛(wèi)星對地觀測是人造衛(wèi)星按照既定的運(yùn)行軌道，利用攜帶的光電遙感器或無線電設(shè)備，對用戶感興趣的地面目標(biāo)進(jìn)行成像的過程。由于衛(wèi)星對地觀測具有覆蓋區(qū)域廣、持續(xù)時間長、成像效果好、不受空域國界限制等獨(dú)特優(yōu)勢，已在城鎮(zhèn)規(guī)劃、礦產(chǎn)調(diào)查以及防災(zāi)減災(zāi)等眾多關(guān)系國計(jì)民生的領(lǐng)域發(fā)揮著重要作用[1]。

遙感衛(wèi)星是按照預(yù)定的成像計(jì)劃進(jìn)行對地觀測的[2，3]。成像計(jì)劃中需要指定衛(wèi)星將要執(zhí)行的觀測任務(wù)，并確定觀測任務(wù)對應(yīng)的數(shù)據(jù)采集活動和數(shù)據(jù)下傳活動的起止時間。成像計(jì)劃的制訂直接源于對用戶遙感圖像需求進(jìn)行任務(wù)規(guī)劃的結(jié)果。任務(wù)規(guī)劃是指為了實(shí)現(xiàn)給定的目標(biāo)，對所有與目標(biāo)相關(guān)的資源和任務(wù)進(jìn)行規(guī)劃和調(diào)度的過程[4，5]。衛(wèi)星對地觀測任務(wù)規(guī)劃具體是指：在綜合考慮遙感衛(wèi)星能力和用戶遙感圖像需求的基礎(chǔ)上，將資源分配給相互競爭的多個觀測任務(wù)，并確定任務(wù)中各具體活動的起止時間，以排除不同任務(wù)之間的資源使用沖突，并最大化滿足用戶的需求[6，7]。

衛(wèi)星對地觀測任務(wù)規(guī)劃是一個復(fù)雜的問題，其中包含了許多與特定問題相關(guān)的實(shí)際約束，如衛(wèi)星與地面目標(biāo)之間的可見時間窗口、衛(wèi)星連續(xù)兩次觀測之間的調(diào)整時間、衛(wèi)星的側(cè)視調(diào)整次數(shù)、地面目標(biāo)要求的特定遙感器類型、星載存儲器的容量、氣象條件等[8，9]。隨著近年來不同部門對于遙感衛(wèi)星圖像數(shù)據(jù)的數(shù)量及質(zhì)量要求越來越高，同時航天技術(shù)的飛速發(fā)展也使遙感衛(wèi)星的靈巧性得到極大提高，從而為給定目標(biāo)的觀測提供了更多可供選擇的機(jī)會，這都使得衛(wèi)星對地觀測任務(wù)規(guī)劃問題變得更加復(fù)雜[10，11]。

衛(wèi)星對地觀測任務(wù)規(guī)劃的傳統(tǒng)方式需要操作人員考慮用戶需求及衛(wèi)星的各種約束，通過長時間的人工分析編制成像計(jì)劃。隨著衛(wèi)星數(shù)目的不斷增多、衛(wèi)星能力的不斷增強(qiáng)以及用戶需求復(fù)雜性的不斷增加，這種傳統(tǒng)的單星成像計(jì)劃編制方式已不能滿足實(shí)際需求，衛(wèi)星對地觀測任務(wù)規(guī)劃也正在逐漸從依賴于地面人員手工編制走向星上自主計(jì)劃生成，從單星自成系統(tǒng)管理走向多星編隊(duì)或成星座組網(wǎng)管理。

1 衛(wèi)星對地觀測任務(wù)規(guī)劃問題

遙感衛(wèi)星通常在數(shù)百公里的軌道高度上繞地球飛行，星載遙感器的視場角對應(yīng)于星下線兩側(cè)對稱的帶狀區(qū)域即衛(wèi)星的觀測帶。伴隨地球的自轉(zhuǎn)，觀測帶不斷變化并能覆蓋地球表面的大部分地區(qū)。當(dāng)衛(wèi)星經(jīng)過地面目標(biāo)上空時，可以利用星載遙感器采集目標(biāo)數(shù)據(jù)并存儲在星載存儲器內(nèi)，待衛(wèi)星經(jīng)過地面接收站上空，再將存儲的數(shù)據(jù)回傳至地面；如果衛(wèi)星在采集目標(biāo)數(shù)據(jù)的同時與地面接收站可見，也可以選擇不經(jīng)存儲器直接將數(shù)據(jù)回傳至地面。由于衛(wèi)星的成像操作需要消耗能量，衛(wèi)星的對地觀測將受到能量的限制。此外，某些星載遙感器如光學(xué)相機(jī)，其數(shù)據(jù)采集活動還需要在較低的云層覆蓋和一定的太陽光照條件下進(jìn)行，在安排觀測任務(wù)時必須考慮云層氣象條件的限制[2，8，9]。

遙感衛(wèi)星在成像過程中始終處于高速飛行狀態(tài)，其姿態(tài)控制能力有限，使得在同一軌道圈次只有部分地面目標(biāo)能夠獲得成像機(jī)會；另一方面，衛(wèi)星連續(xù)兩個圈次的赤道距離大約為幾千公里，在一個成像計(jì)劃編制周期內(nèi)衛(wèi)星通常要經(jīng)過數(shù)十個圈次，有時甚至要經(jīng)過幾個回歸周期。因此對相同的地面目標(biāo)，能夠?qū)ζ溥M(jìn)行成像的機(jī)會往往不止一個。特別是隨著航天技術(shù)的迅猛發(fā)展，衛(wèi)星的靈巧性越來越強(qiáng)，可以沿俯仰、側(cè)擺等多個自由度靈活調(diào)整觀測角度，從而增加與特定目標(biāo)的可見時間窗口數(shù)目或增加可見時間窗口長度[11~13]。衛(wèi)星對地觀測任務(wù)規(guī)劃需要在考慮衛(wèi)星資源能力和各種約束條件的基礎(chǔ)上，對在什么時間、采用何種姿態(tài)、對哪些地面目標(biāo)進(jìn)行觀測實(shí)施決策[14]。衛(wèi)星對地觀測任務(wù)規(guī)劃處于在軌衛(wèi)星遙感數(shù)據(jù)業(yè)務(wù)管理的關(guān)鍵環(huán)節(jié)[15]，如圖1所示。從圖中可見，衛(wèi)星對地觀測任務(wù)規(guī)劃的輸入是用戶提交的遙感數(shù)據(jù)需求和可用的衛(wèi)星資源；輸出是可行的衛(wèi)星對地觀測計(jì)劃，該計(jì)劃是編制衛(wèi)星控制指令的依據(jù)。任務(wù)規(guī)劃的質(zhì)量將決定對用戶需求的滿足程度和衛(wèi)星資源的使用效益。

衛(wèi)星對地觀測任務(wù)規(guī)劃已經(jīng)從早期依靠人工分析的計(jì)劃制訂階段發(fā)展到現(xiàn)今的計(jì)算機(jī)輔助自動生成觀測計(jì)劃階段。當(dāng)前的計(jì)算機(jī)輔助任務(wù)規(guī)劃主要基于以下幾個問題的解決：用戶需求的建模、衛(wèi)星能力的建模、基于實(shí)際約束的衛(wèi)星資源到觀測任務(wù)的映射建模、觀測計(jì)劃評價準(zhǔn)則的建立。其中前三個問題的確定性較強(qiáng)，可以借助于一些成熟的建模技術(shù)；最后一個問題中蘊(yùn)涵大量不確定因素[16]、人的主觀因素以及多個互相矛盾的目標(biāo)，其解決需要依賴于更多富含創(chuàng)造性的工作。具體來說，可以從以下幾個方面考慮觀測計(jì)劃的評價準(zhǔn)則：

a）當(dāng)用戶的需求數(shù)量超出遙感衛(wèi)星的觀測能力時，本問題作為一個過度約束資源調(diào)度問題，如何評價一個只滿足了部分需求的觀測計(jì)劃[17]？

b）多個遙感衛(wèi)星往往從屬于不同的應(yīng)用部門，如何對一個觀測計(jì)劃中衛(wèi)星在多個應(yīng)用部門間的使用公平性進(jìn)行度量[18~ 20]？

c）某些遙感需求涉及衛(wèi)星一次成像無法覆蓋的大面積區(qū)域，如何對一個只滿足了區(qū)域觀測部分需求的計(jì)劃進(jìn)行評價[11， 21]？

d）當(dāng)前的任務(wù)規(guī)劃作為一種離線的預(yù)先計(jì)劃，如何考慮突發(fā)需求、資源失效、氣象條件等不確定因素[16， 22]？

e）每個地面目標(biāo)可能具有多種觀測機(jī)會，不同的觀測方式對于用戶的效用是否相同？

f）一次對地觀測過程很難同時滿足成像需求完成數(shù)量多、質(zhì)量好且衛(wèi)星能量消耗少等目標(biāo)，如何對多種目標(biāo)進(jìn)行權(quán)衡，以取得更好的綜合效益[23]？

下面結(jié)合相關(guān)的大量國內(nèi)外文獻(xiàn)，主要從衛(wèi)星對地觀測任務(wù)規(guī)劃問題的建模和求解兩個方面進(jìn)行相關(guān)技術(shù)介紹。

2 衛(wèi)星對地觀測任務(wù)規(guī)劃問題建模方法

2. 1 問題描述

衛(wèi)星對地觀測任務(wù)規(guī)劃問題可以簡要描述為：一組衛(wèi)星、一組觀測任務(wù)，每個觀測任務(wù)的完成包含數(shù)據(jù)采集和數(shù)據(jù)回傳兩個活動。為每個觀測任務(wù)指定一個優(yōu)先級；觀測任務(wù)對應(yīng)的地面目標(biāo)與衛(wèi)星之間具有一組可用時間窗口；一個參考時間范圍作為任務(wù)規(guī)劃的起止時間。衛(wèi)星對地觀測需要滿足以下約束：每個觀測任務(wù)必須在其某個可用時間窗口內(nèi)完成；衛(wèi)星連續(xù)兩次觀測之間必須有足夠的調(diào)整時間；衛(wèi)星的側(cè)視調(diào)整次數(shù)、存儲容量和能量有限，使每個圈次的累積觀測時間有限，等等。問題的目標(biāo)是最大化完成觀測任務(wù)的加權(quán)和，也有可能要求盡可能多地完成高優(yōu)先級的任務(wù)，或在滿足任務(wù)需求的基礎(chǔ)上使衛(wèi)星能量消耗盡可能小，或多個目標(biāo)組合形成多目標(biāo)問題?？梢?，衛(wèi)星對地觀測任務(wù)規(guī)劃問題根據(jù)實(shí)際應(yīng)用背景的不同可能在描述上存在差異，但總的來說，該問題可以分為選擇（從觀測任務(wù)中選擇一個任務(wù)子集進(jìn)行安排，從每個觀測任務(wù)的多種觀測機(jī)會中選擇一種進(jìn)行安排）和調(diào)度（指定完成每個觀測任務(wù)的衛(wèi)星資源，指定每個觀測任務(wù)中數(shù)據(jù)采集活動和數(shù)據(jù)回傳活動的起止時刻）兩個子問題[24]。

2. 2 模型表示

2. 2. 1 圖論問題模型

Gabrel等人[23，25]將衛(wèi)星對地觀測任務(wù)規(guī)劃問題表示成一個加權(quán)有向無環(huán)圖G。其中，每個子圖Gi表示衛(wèi)星的一個運(yùn)行圈次，每個子圖中除首尾節(jié)點(diǎn)bi和ei表示圈次的開始和結(jié)束之外，其余各節(jié)點(diǎn)表示待安排的觀測任務(wù)，且都關(guān)聯(lián)一個與優(yōu)化目標(biāo)相關(guān)的權(quán)重。如果(s，t)∈Gi，則表示在Gi對應(yīng)的圈次中，任務(wù)t在任務(wù)s之后執(zhí)行。問題的求解目標(biāo)是找尋G的一條最長路徑（可以通過簡單的變換，借助最短路徑問題的成熟算法解決），如圖2所示。

圖論問題模型的優(yōu)勢在于模型直觀、便于理解，并且可以借助成熟有效的多項(xiàng)式時間圖論求解算法；其缺陷在于無法在模型中體現(xiàn)一些實(shí)際約束，如區(qū)域或立體觀測需求、側(cè)視調(diào)整次數(shù)限制等。

2. 2. 2 背包問題

Vasquez等人[26]將衛(wèi)星對地觀測任務(wù)規(guī)劃問題表示成一個多維背包問題，并建立了如下數(shù)學(xué)模型：

max∑ni=1gi×xi

subject to ∑ni=1mi×xi≤M

∑mi=1ei×xi≤E

{i，j}∈I， xi+xj≤1

i，xi∈{0，1}

其中xi是表示觀測任務(wù)i是否被安排的布爾變量。模型中可以表示存儲容量和能量等多個維度的約束，當(dāng)任務(wù)的觀測機(jī)會不止一個時，最多選擇其中的一個安排執(zhí)行。問題的優(yōu)化目標(biāo)是最大化已安排任務(wù)的加權(quán)和。

背包問題模型的優(yōu)點(diǎn)是形式簡單，可以表示多個維度的資源使用水平約束，有高效的最優(yōu)或近似最優(yōu)求解算法。模型的缺點(diǎn)與圖論模型相似，也是無法表示一些復(fù)雜實(shí)際約束，如區(qū)域觀測需求等，并且不利于擴(kuò)展到多星任務(wù)規(guī)劃的情況。

2. 2. 3 線性整數(shù)規(guī)劃模型

考慮到前述兩個模型的缺陷，Gabrel等人[27]和Bensana等人[6]提出用更一般的整數(shù)規(guī)劃模型來描述對地觀測衛(wèi)星任務(wù)規(guī)劃問題。其形式化描述如下：

max∑ni=1gi×yi

subject to ∑mj=1mi×xj≤M， ∑mj=1ej×xj≤E

{j，k}∈I， xj+xk≤1

{i，j}∈M， yi=xj

{i，j，k}∈S，yi=xi/2+xk/2

i，yi∈{0，1}，j，xj∈{0，1}

線性整數(shù)規(guī)劃模型可以描述衛(wèi)星觀測任務(wù)規(guī)劃問題中的所有線性約束，并且可以充分利用商用現(xiàn)貨軟件工具（如ILOG CPlex[28]）。但由于整數(shù)規(guī)劃問題本身的求解困難性，當(dāng)問題規(guī)模逐漸增大時，一旦缺乏有效的分支定界策略，求解效率將比較低，除非借助于一些復(fù)雜的問題分解方法，如列生成法[29]，找到問題最優(yōu)解的緊湊上界[30]以指導(dǎo)尋優(yōu)過程。此外，該模型對于一些非線性約束也顯得力不從心。

2. 2. 4 約束滿足問題模型

Bensana和Agnese等人[6，31]提出的加權(quán)約束滿足問題模型（valued constraint satisfaction problem）在模型表述上與線性規(guī)劃模型相似，但是可以對非線性約束和非線性目標(biāo)進(jìn)行描述，而且其變量及約束的表示更加簡單直觀，同時可以利用成熟的用于求解約束滿足問題的約束規(guī)劃軟件工具，如法國ILOG公司的產(chǎn)品ILOG Solver[32]。雖然這種模型的描述能力強(qiáng)，模型求解有約束傳播算法[33]支撐，但是通用的約束傳播算法的效率通常較低，主要原因也是由于缺乏有效的分支定界策略。

2. 2. 5 其他模型表示

賀仁杰[15]將衛(wèi)星對地觀測任務(wù)規(guī)劃問題看做是一個具有時間窗口約束的并行機(jī)器調(diào)度問題（parallel machine scheduling problem with time window，PMSPTW）。其中機(jī)器相當(dāng)于衛(wèi)星；工件相當(dāng)于觀測任務(wù)；機(jī)器加工工件的允許時間窗口就是衛(wèi)星對地面目標(biāo)的可見時間窗口；工件的加工時間就是衛(wèi)星觀測目標(biāo)的時間；機(jī)器在加工工件時的轉(zhuǎn)換時間即為衛(wèi)星在執(zhí)行觀測任務(wù)時的轉(zhuǎn)換時間。調(diào)度目標(biāo)是使所有加工工件的總權(quán)值最大，即完成的觀測任務(wù)總效益值最大。

李菊芳等人[34]從車輛路線問題的角度對衛(wèi)星對地觀測任務(wù)規(guī)劃問題建模，模型中把整個衛(wèi)星及其有效載荷看做是有一定容量的車輛，把地面目標(biāo)和地面接收站看做是顧客要求訪問節(jié)點(diǎn)，從而使衛(wèi)星對地觀測任務(wù)規(guī)劃問題轉(zhuǎn)換成一類有時間窗口和容量約束的車輛路線問題。問題的求解目標(biāo)可以設(shè)定為在完成對指定顧客訪問的基礎(chǔ)上，所有車輛的總行駛里程最短，或?qū)λ幸言L問顧客的總收益最大。

Verfaillie和Damiani等人[35，36]還從決策科學(xué)的角度提出了衛(wèi)星對地觀測任務(wù)規(guī)劃的序貫決策模型。模型中考慮了任務(wù)規(guī)劃中不確定因素的局部贏得（local gains），可以利用有效的動態(tài)規(guī)劃算法進(jìn)行求解，只是隨著模型中一些實(shí)際約束的加入，模型的復(fù)雜性將急劇增加。

Chien[37]、Frank[8]和Long[38]等人從人工智能規(guī)劃問題的角度提出了衛(wèi)星觀測任務(wù)規(guī)劃問題描述模型。該模型借助標(biāo)準(zhǔn)人工智能規(guī)劃建模語言，如PDDL[38]，對衛(wèi)星任務(wù)規(guī)劃中涉及的活動、狀態(tài)和條件等實(shí)體進(jìn)行建模。該語言的描述范圍不僅僅局限于衛(wèi)星的觀測任務(wù)，不足之處在于建模語言本身不提供優(yōu)化功能，模型的求解還需借助其他搜索技術(shù)。

3 衛(wèi)星對地觀測任務(wù)規(guī)劃問題的求解技術(shù)

3. 1 動態(tài)規(guī)劃

動態(tài)規(guī)劃[10]主要用于解決衛(wèi)星對地觀測任務(wù)規(guī)劃中的調(diào)度子問題（即確定完成觀測任務(wù)的資源和排定觀測任務(wù)之間的執(zhí)行順序），一旦調(diào)度子問題得到解決，選擇子問題也將不再困難。在序貫決策模型的求解中也使用了動態(tài)規(guī)劃方法[35]。動態(tài)規(guī)劃通常按照衛(wèi)星星下線軌跡對應(yīng)的地面目標(biāo)的地理位置順序確定觀測任務(wù)的執(zhí)行次序；然后基于對規(guī)劃時間、星載存儲容量、衛(wèi)星能量等要素的離散化進(jìn)行問題求解。求解時間可以達(dá)到多項(xiàng)式時間級。該方法的缺陷在于當(dāng)任務(wù)具有多個觀測機(jī)會，即多個任務(wù)之間執(zhí)行次序不惟一時，不能保證解的全局最優(yōu)。

3. 2 樹搜索

樹搜索[14]作為一種完全搜索技術(shù)，在求解線性整數(shù)規(guī)劃問題模型和約束滿足問題模型等需要使用分支定界算法的場合經(jīng)常使用。樹搜索技術(shù)分為深度優(yōu)先搜索（depth-first）和最佳優(yōu)先搜索（best-first）兩種。前者生成初始解的速度較快，算法空間耗費(fèi)小，但是依賴于初始搜索節(jié)點(diǎn)的選擇，解的平均性能較差；后者在良好設(shè)計(jì)的啟發(fā)式指引下，能夠生成性能較優(yōu)的解，只是可能需要指數(shù)級的存儲空間開銷，并且生成解的時間較長。樹搜索技術(shù)如果缺乏有效的剪枝策略，將只適用于中小規(guī)模的問題實(shí)例（觀測任務(wù)數(shù)只有數(shù)十個）。

3. 3 時間推理技術(shù)

對人工智能規(guī)劃領(lǐng)域模型而言，如果已經(jīng)選定了將要執(zhí)行的活動并確定了活動之間的執(zhí)行順序，那么確定活動的起止時間可以采用簡單時間網(wǎng)絡(luò)[36]（simple temporal network）這一時間推理技術(shù)，通過多項(xiàng)式時間算法獲得一個無時間沖突的活動執(zhí)行時間方案。不過，這種時間推理技術(shù)只能在任務(wù)規(guī)劃中涉及時間的決策變量求解中發(fā)揮效力，其應(yīng)用范圍不夠廣泛。

3. 4 局部搜索技術(shù)

局部搜索[10，24]是在衛(wèi)星對地觀測任務(wù)規(guī)劃模型求解中廣泛使用的一種技術(shù)。與樹搜索的完全搜索方式不同，它是一種迭代改進(jìn)的非精確搜索算法，雖然不能保證解的最優(yōu)性，但是求解過程時間耗費(fèi)小，可以在任何時候返回一個可行解。這種算法的設(shè)計(jì)需要一定的技巧，并且常常需要對算法的某些參數(shù)作實(shí)驗(yàn)。局部搜索沒有標(biāo)準(zhǔn)的形式，如禁忌搜索[26，39~41]、模擬退火[42，43]、遺傳算法[44，45]這些現(xiàn)代智能搜索算法均屬于局部搜索的范圍。局部搜索算法的效率依賴于以下幾個因素：

a）初始解的生成機(jī)制;

b）領(lǐng)域結(jié)構(gòu)的定義方式;

c）領(lǐng)域結(jié)構(gòu)的搜索機(jī)制和接受新解的方式;

d）算法的終止準(zhǔn)則和回溯搜索的方式。

很多研究者的大量實(shí)驗(yàn)表明[10，11，42]，禁忌搜索和模擬退火算法在較大規(guī)模的衛(wèi)星對地觀測任務(wù)規(guī)劃問題（任務(wù)數(shù)達(dá)到數(shù)百個、衛(wèi)星數(shù)達(dá)到數(shù)個）中表現(xiàn)良好。

3. 5 貪婪算法

貪婪算法[45~47]是按照既定的啟發(fā)式規(guī)則逐步構(gòu)造可行解的一種算法，它無須迭代，不能保證最優(yōu)，甚至無法給出可行解與最優(yōu)解之間的差異，但是它的時間性能最佳。對于一些大規(guī)模的任務(wù)規(guī)劃問題或是涉及復(fù)雜約束的規(guī)劃問題，當(dāng)其他算法在有限時間內(nèi)無能為力時，貪婪算法無疑是一種不錯的選擇。貪婪算法的啟發(fā)式規(guī)則是算法的關(guān)鍵因素，對于衛(wèi)星對地觀測任務(wù)規(guī)劃問題，啟發(fā)式規(guī)則可以是按照衛(wèi)星與任務(wù)可見時間窗口的時間先后順序逐個安排任務(wù)，也可以按照任務(wù)優(yōu)先級的高低逐個安排任務(wù)。貪婪算法的“短視”缺點(diǎn)可以通過在算法中引入一定的隨機(jī)機(jī)制得到改進(jìn)[45]。

綜合考察上述不同的衛(wèi)星對地觀測任務(wù)規(guī)劃問題求解技術(shù)，可說是各有所長。Verfaillie和Lemaitre等人[10，11]對法國空間局PLEIADES項(xiàng)目中的一種靈巧衛(wèi)星（可以在三個自由度上進(jìn)行姿態(tài)調(diào)整）的對地觀測任務(wù)規(guī)劃問題展開了模型和算法研究，針對六個不同規(guī)模的問題實(shí)例比較了貪婪算法、動態(tài)規(guī)劃、約束規(guī)劃和局部搜索四種求解方法的性能表現(xiàn)。結(jié)果表明，只有約束規(guī)劃和局部搜索可以考慮所有的線性和非線性約束；貪婪算法和動態(tài)規(guī)劃在不考慮某些約束（優(yōu)化目標(biāo)的非線性和立體觀測需求）的情況下，求解速度較快，解的質(zhì)量較高；動態(tài)規(guī)劃在給定了任務(wù)觀測次序的前提下性能最優(yōu)；約束規(guī)劃由于缺乏有效應(yīng)對求解空間組合爆炸特征的搜索策略，性能較差；局部搜索性能優(yōu)于約束規(guī)劃，但是局部搜索的不確定特征決定了算法中某些參數(shù)的調(diào)整工作比較費(fèi)時。

A. Globus等人[42]曾對十個實(shí)際規(guī)模的衛(wèi)星對地觀測任務(wù)規(guī)劃問題實(shí)例展開不同算法的比較研究。結(jié)果表明，局部搜索中的模擬退火算法表現(xiàn)最佳。其中算法參數(shù)的確定經(jīng)過了大量的實(shí)驗(yàn)以適合具體的問題實(shí)例，一種時間敏感交換算子被證明是最佳的解調(diào)整策略。

由于衛(wèi)星對地觀測任務(wù)規(guī)劃問題復(fù)雜、涉及大量非線性約束、求解目標(biāo)不惟一，使得不存在適用于所有問題的通用算法。大量學(xué)者的研究表明，具有一定智能的局部搜索算法是適用范圍最廣、綜合性能最好的一類算法，也是一個新興的研究方向。

4 結(jié)束語

隨著衛(wèi)星技術(shù)的飛速發(fā)展，遙感衛(wèi)星逐漸向小型化、智能化和組網(wǎng)的方向邁進(jìn)[48]。與此同時，衛(wèi)星對地觀測任務(wù)規(guī)劃技術(shù)需要面對以下幾個方面的挑戰(zhàn)：

a）建立應(yīng)對全球環(huán)境變化的環(huán)境監(jiān)測和災(zāi)害預(yù)警的衛(wèi)星對地觀測系統(tǒng)的需求日益迫切；

b）衛(wèi)星對地觀測系統(tǒng)整體性能的優(yōu)化缺乏理論支撐；

c）衛(wèi)星對地觀測系統(tǒng)內(nèi)部異構(gòu)衛(wèi)星的協(xié)同規(guī)劃問題[49]日漸突出；

d）衛(wèi)星有效載荷的遙感能力、數(shù)據(jù)分析能力和智能決策能力不斷增強(qiáng)；

e）多衛(wèi)星組成編隊(duì)或組網(wǎng)完成復(fù)雜對地觀測任務(wù)[50，51]逐漸成為趨勢。

衛(wèi)星對地觀測任務(wù)規(guī)劃問題是一個蓬勃發(fā)展、潛力巨大的研究領(lǐng)域，衛(wèi)星對地觀測的應(yīng)用需求層出不窮。為了充分發(fā)揮我國現(xiàn)有遙感衛(wèi)星對地觀測系統(tǒng)的整體效能，更好地為國防、經(jīng)濟(jì)、環(huán)境等關(guān)系國計(jì)民生的領(lǐng)域服務(wù)，衛(wèi)星對地觀測任務(wù)規(guī)劃的理論和各種技術(shù)方法有待大力探索。一方面，尋求為具體問題量身定制合適的模型和高效的求解算法；另一方面，著力抽象出不同問題的共性，在理論上兼容并包，把握衛(wèi)星對地觀測任務(wù)規(guī)劃問題的實(shí)質(zhì)。如何在以上兩個看似矛盾的方面加以權(quán)衡，是研究人員需要解決的一個難題。

參考文獻(xiàn)：

[1]LARSON J W， WERTZ R J. Space mission analysis and design[M].2nd ed.Boston:Kluwer Academic Publishers，1992.

[2]POTTER W， GASCH J. A photo album of earth: scheduling Landsat 7 mission daily activities[C]//Proc of the 5th International Confe-rence on Space Operations.1998.

[3]BENSANA E，LEMAITRE M，VERFAILLIE G. Earth observation sate-llite management[J]. Constraints，1999，4（3）:293-299.

[4]BRESINA L J， MORRIS A R，EDGINGTON R W. Optimizing observation scheduling objectives[C]//Proc of NASA Workshop on Planning and Scheduling for Space.1997.

[5]DEAN T，WELLMAN M.Planning and control[M].San Francisco:Morgan Kaufmann Publishers，1991.

[6]BENSANA E，VERFAILLIE G，AGNESE C G，et al. Exact and approximate methods for the daily management of an earth observation satellite[C]//Proc of the 4th International Symposium on Space Mission Operations and Ground Data System.1996:3-12.

[7]HALL N G，MAGAZINE M J. Maximizing the value of a space mission[J]. European Journal of Operations Research， 1994，78(2):224-241.

[8]FRANK J，JONSSON A，MORRIS R，et al. Planning and scheduling for fleets of earth observing satellites[C]//Proc of the 6th Internatio-nal Symposium on Artificial Intelligence， Robotics， Automation and Space. 2002.

[9]SHERWOOD R，GOVINDJEE A，YANETC D.Using ASPEN to automate EO-1 activity planning[C]//Proc of IEEE Aerospace Confe-rence. 1998:145-152.

[10]VERFAILLIE G，LEMAITRE M. Selecting and scheduling observations for agile satellites: some lessons from the constraint reasoning community point of view[C]//Proc of the 7th International Confe-rence on Practical and Principles of Constraint Programming.Berlin:Springer，2001:670-684.

[11]LEMAITRE M，VERFAILLIE G，JOUHAUD F，et al. Selecting and scheduling observations of agile satellites[J]. Aerospace Science and Technology， 2002， 6(5):367-381.

[12]JACKSON S E. Planning coverage of points of interest via multiple imaging surveillance assets: a multi-modal approach[R].[S.l.]: Air Force Inst of Tech Wright-Pateerson AFB OH， School of Enginee-ring and Management. 2003.

[13]PEMBERTON J. Towards scheduling over-constrained remote sensing satellites[C]//Proc of the 2nd International Workshop on Planning and Scheduling for Space. 2000.

[14]HARRISON A S，PRICE E M. Task scheduling for satellite based imagery[C]//Proc of the 18th Workshop of the UK Planning and Scheduling Special Interest Group.Mancheseter: University of Salford，1999:64-78.

[15]賀仁杰.成像偵察衛(wèi)星調(diào)度問題研究[D]. 長沙：國防科學(xué)技術(shù)大學(xué)， 2004.

[16]BENSANA E，VERFAILLIE G， MICHELON-EDERY C， et al. Dea-ling with uncertainty when managing an earth observation satellite[C]//Proc of the 5the International Symposium on Artifical Intelligence， Robotics and Automation in Space.1999:205.

[17]SMITH F S，PATHAK K D. Balancing antagonistic time and resource utilization constraints in over-subscribed scheduling problems[C]//Proc of the 8th IEEE Conference on Applications of Artificial Intelligence.1992:113-119.

[18]BATAILLE N，LEMAITRE M，VERFAILLIE G. Efficiency and fairness when sharing the use of a satellite[C]//Proc of the 5th International Symposium on Artificial Intelligence， Robotics and Automation in Space.1999.

[19]LEMAITRE M，VERFAILLIE G，BATAILLE N. Sharing the use of a satellite: an overview of methods[C]//Proc of the 5th International Symposium on Space Mission Operations and Ground Data Systems.1998.

[20]LEMAITRE M，VERFAILLIE G，BATAILLE N. Exploiting a common property resource under a fairness constraint: a case study[C]//Proc of the 16th Internetational Joint Conference on Artificial Intelligence. San Francisco: Morgan Kaufmann Publisher，1999:206-211.

[21] 阮啟明，譚躍進(jìn).對地觀測衛(wèi)星的區(qū)域目標(biāo)分割與優(yōu)選問題研究[J]. 測繪科學(xué)，2006，31(1):98-100.

[22]HERZ F A，MIGNOGNA A. Collection planning for the OrbView-3 high resolution image satellite on Space Mission Operations and Ground Data Systems[C]//Proc of Internetional Symposium on Space Mission Operations and Ground Data Systems.2006.

[23]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.

[24]HABET D，VASQUEZ M. Solving the selecting and scheduling photographs problem with a consistent neighborhood heuristic[C]//Proc of the 16th IEEE International Conference on Tools with Artificial Intelligence. Washington DC: IEEE Computer Society， 2004:302-309.

[25]GABREL V，MOULET A，MURAT C，et al. A new single model and derived algorithms for the satellite shot planning problem using graph theory concepts[J]. Annals of Operations Research， 1997，69(1):115-134.

[26]VASQUEZ M，HAO J K. A logic-constrained knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite[J]. Journal of Computational Optimization and Applications， 2001，20(2):137-157.

[27]GABREL V，MURAT C. Operations research in space and air[M]. Boston: Kluwer Academics Publishers， 2003.

[28]ILOG CPlex8.1 user’s manual[K]. Paris: ILOG Inc， 2003.

[29]MANCEL C. A column generation approach for earth observing satellites[C]//Proc of the 2nd Operational Research Peripatetic Postgra-duate Program. 2003.

[30]VASQUEZ M，HAO J K. Uppers bounds for the SPOT 5 daily photograph scheduling problem[J]. Journal of Combinatorial Optimization，2003，7(1):87-103.

[31]BENSANA E， VERFAILLIE G， AGNESE C J，et al. Exact and approximate methods for the daily management of an earth observation satellite[C]//Proc of the 4th International Symposicum on Space Mission Operation and Ground Data Systems. 1996:3-12.

[32]ILOG solver 5.3 user’s manual[K]. Paris: ILOG Inc， 2003.

[33]BAPTISTE P. A theoretical and experimental comparison of constraint propagation techniques for disjunctive scheduling[C]//Proc of the 14thInternational Joint Conference on Artificial Intelligence.San Francisco: Morgan Kaufmann Publisher， 1995:600-606.

[34]李菊芳，譚躍進(jìn).衛(wèi)星觀測系統(tǒng)整體調(diào)度的收發(fā)問題模型及求解[J].系統(tǒng)工程理論與實(shí)踐，2004，24(12): 65-71.

[35]VERFAILLIE G，LEMAITRE M，SCHIEX T. Russian doll search for solving constraint optimization problems[C]//Proc of the 13th National Conference on Artificial Intelligence.1996:181-187.

[36]DAMIANI S，VERFAILLIE G，CHARMEAU C M. An anytime planning approach for the management of an earth watching satellite[C]//Proc of the 4th International Workshop on Planning and Scheduling for Space. 2004.

[37]CHIEN S，SHERWOOD R，RABIDEAU G，et al. The Techsat-21 autonomous space science agent[C]//Proc of the 1st International Conference on Autonomous Agents. New York: ACM Press， 2002:570-577.

[38]LONG D，F(xiàn)OX M. Bridging the modeling gap: examining the expressiveness of planning domain description languages[C]//Proc of the 3rd International Workshop on Planning and Scheduling for Space.2002.

[39]LIN Wei-chen，LIAO Da-yin. A tabu search algorithm for satellite imaging scheduling[C]//Proc of IEEE International Conference on Systems， Man， and Cybernetics. 2004.

[40]HABET D，VASQUEZ M. Saturated and consistent neighborhood for selecting and scheduling photographs of agile earth observing satellite[C]//Proc of the 5th Metaheuristics International Conference.2003.

[41]CORDEAU F J，LAPORTE G. Maximizing the value of an earth observation satellite orbit[J]. Journal of the Operational Research Society， 2005，56(8):962-968.

[42]GLOBUS A，CRAWFORD J，LOHN J. A comparison of techniques for scheduling earth observing satellites[C]//Proc of the 6th Innovative Applications of Artifical Intelligence Conference. 2004:836-843.

[43]KUIPERS E J. Algorithm for the management of the missions of earth observation satellites[C]//Proc of the 5th ROADEF Annual Confe-rence on Booklet of Abstracts. 2003.

[44]GLOBUS A，CRAWFORD J，LOHN J，et al. Scheduling earth obser-ving satellites with evolutionary algorithms[C]//Proc of International Conference on Space Mission Changes for Information Technology. 2003.

[45]WOLFE W，SORENSEN S. Three scheduling algorithms applied to the earth observing systems domain[J]. Management Science，2000，46(1):148-168.

[46]MURAOKA H，COHEN R H，OHNO T，et al. ASTER observation scheduling algorithm[C]//Proc of the 5th International Symposium on Space Mission Operation and Ground Data Systems.1998.

[47]BURROWBRIDGE S. Optimal allocation of satellite networks resource[D]. Dayton， Ohio: American Air Force Institute of Techno-logy， 1999.

[48]ZHOU G，BAYSAL O，KAYE J，et al. Concept design of future intelligent earth observing satellites[J]. International Journal of Remote Sensing，2004，25(14):2667-2685.

[49]MORRIS R，DUNGAN J，GASCH J，et al. Coordinated science campaign planning for earth observing missions[C]//Proc of the 4th Annual Earth Science Technology Conference. 2004.

[50]DAMIANI S，VERFAILLIE G，CHARMEAU C M. Cooperating onboard and on the ground decision modules for the management of an earth watching constellation[C]//Proc of the 8th International Symposium on Artificial Intelligence， Robotics， and Automation for Space. 2005.

[51]MOHAMMED J. Mission planning for a formation-flying satellite cluster[C]//Proc of the 14th International Florida Artificial Intelligence Research Society Conference. Menlo Park: AAAI Press， 2001:58-62.