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

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

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

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

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

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

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

中圖分類(lèi)號(hào)：N945; V47

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. 1 問(wèn)題描述

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

2. 2 模型表示

2. 2. 1 圖論問(wèn)題模型

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

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

2. 2. 2 背包問(wèn)題

Vasquez等人[26]將衛(wèi)星對(duì)地觀測(cè)任務(wù)規(guī)劃問(wèn)題表示成一個(gè)多維背包問(wèn)題，并建立了如下數(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是表示觀測(cè)任務(wù)i是否被安排的布爾變量。模型中可以表示存儲(chǔ)容量和能量等多個(gè)維度的約束，當(dāng)任務(wù)的觀測(cè)機(jī)會(huì)不止一個(gè)時(shí)，最多選擇其中的一個(gè)安排執(zhí)行。問(wèn)題的優(yōu)化目標(biāo)是最大化已安排任務(wù)的加權(quán)和。

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

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

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

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

2. 2. 4 約束滿足問(wèn)題模型

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

2. 2. 5 其他模型表示

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

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

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

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

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

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

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

3. 2 樹(shù)搜索

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

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

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

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

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

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)星對(duì)地觀測(cè)任務(wù)規(guī)劃問(wèn)題（任務(wù)數(shù)達(dá)到數(shù)百個(gè)、衛(wèi)星數(shù)達(dá)到數(shù)個(gè)）中表現(xiàn)良好。

3. 5 貪婪算法

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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

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

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

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

參考文獻(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)度問(wèn)題研究[D]. 長(zhǎng)沙：國(guó)防科學(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).對(duì)地觀測(cè)衛(wèi)星的區(qū)域目標(biāo)分割與優(yōu)選問(wèn)題研究[J]. 測(cè)繪科學(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)星觀測(cè)系統(tǒng)整體調(diào)度的收發(fā)問(wèn)題模型及求解[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.