李朝玉，徐 瑞，曾 豪，朱圣英，梁子璇

(1. 北京理工大學(xué)宇航學(xué)院，北京 100081；2. 深空自主導(dǎo)航與控制工信部重點(diǎn)實(shí)驗(yàn)室，北京 100081；3. 北京空間飛行器總體設(shè)計(jì)部，北京 100094)

0 引 言

航天器系統(tǒng)級(jí)自主性是衡量其一定時(shí)間內(nèi)在沒有地面站支持的情況下實(shí)現(xiàn)任務(wù)目標(biāo)的能力，智能規(guī)劃技術(shù)是航天器實(shí)現(xiàn)自主運(yùn)行的核心技術(shù)[1]。作為人工智能領(lǐng)域中研究較早的方向之一，20世紀(jì)50年代后期，Newell和Simon設(shè)計(jì)出了邏輯理論家程序及問題求解程序，在人工智能領(lǐng)域具有重要的地位[2]。20世紀(jì)70年代至90年代中期，非線性規(guī)劃方法在領(lǐng)域無關(guān)規(guī)劃中占有主導(dǎo)地位，以此Fikes和Nilsson設(shè)計(jì)了最具影響力的STRIPS規(guī)劃系統(tǒng)，其采用與文字相關(guān)的術(shù)語至今仍被使用[3]。20世紀(jì)90年代后期，空間探測(cè)等領(lǐng)域?qū)ψ灾餍缘男枨笸苿?dòng)了考慮時(shí)間等信息的面向現(xiàn)實(shí)問題規(guī)劃技術(shù)的研究和發(fā)展。

隨著航天任務(wù)增多和探測(cè)空間越來越遠(yuǎn)，為了能夠降低運(yùn)行成本、提高總體任務(wù)回報(bào)率、提高對(duì)感知數(shù)據(jù)反應(yīng)能力和保證在有限監(jiān)督下不確定環(huán)境中航天器安全運(yùn)行，自主任務(wù)規(guī)劃技術(shù)備受美國國家航空航天局(NASA)與歐洲航天局(ESA)等各航天大國和機(jī)構(gòu)的關(guān)注[4]。

深空1號(hào)(DS-1)上的遠(yuǎn)程智能體(RA)和地球觀測(cè)1號(hào)(EO-1)上的自主科學(xué)飛船實(shí)驗(yàn)最具代表性，實(shí)現(xiàn)了在軌自主任務(wù)規(guī)劃技術(shù)的飛行驗(yàn)證和應(yīng)用[5]。RA中任務(wù)規(guī)劃思想在NASA開發(fā)的可擴(kuò)展通用遠(yuǎn)程操作規(guī)劃框架(EUROPA)[6]中得到延續(xù)和拓展。美國噴氣推進(jìn)實(shí)驗(yàn)室(JPL)開發(fā)的自主調(diào)度與規(guī)劃環(huán)境系統(tǒng)(ASPEN)[7]是EO-1中連續(xù)規(guī)劃軟件CASPER的基礎(chǔ)，同時(shí)應(yīng)用到雷達(dá)衛(wèi)星RADARSAT和軌道快運(yùn)太空任務(wù)。ESA最初在硬件編碼環(huán)境下對(duì)基于時(shí)間線的規(guī)劃技術(shù)和約束可滿足技術(shù)進(jìn)行了使用和驗(yàn)證，兩個(gè)決策支持系統(tǒng)MEXAR2和SKeyP分別用于火星快車號(hào)(MEX)在軌內(nèi)存操作的調(diào)度和太陽及日光層觀察航天器(SOHO)在資源受限情況下的操作規(guī)劃[8]。先進(jìn)規(guī)劃與調(diào)度計(jì)劃(APSI)軟件框架進(jìn)一步推動(dòng)了AI技術(shù)在ESA航天項(xiàng)目中的應(yīng)用[9-10]，例如用于火星快車任務(wù)長期規(guī)劃器(MrSPOCK)[11]和國際伽瑪射線天體物理實(shí)驗(yàn)室衛(wèi)星(INTEGRAL)[12]。

上述研究表明：設(shè)計(jì)、實(shí)現(xiàn)和驗(yàn)證自主任務(wù)規(guī)劃技術(shù)非常困難。經(jīng)典規(guī)劃問題采用具有限制性假設(shè)的狀態(tài)轉(zhuǎn)移系統(tǒng)模型，包括規(guī)劃解是序列式的、隱去時(shí)間表示等[13]。在此模型下，動(dòng)作或者事件具有瞬時(shí)性，兩者之間不存在時(shí)間約束，無法有效全面地描述和求解航天器任務(wù)規(guī)劃問題。由于空間環(huán)境動(dòng)態(tài)多變和無法預(yù)知的特點(diǎn)以及航天器系統(tǒng)復(fù)雜性，給航天器自主任務(wù)規(guī)劃技術(shù)帶來以下難點(diǎn)問題[14-16]：

1)活動(dòng)和目標(biāo)具有持續(xù)時(shí)間和截止期限要求：航天器活動(dòng)非瞬時(shí)發(fā)生，具有一定的持續(xù)時(shí)間，多數(shù)活動(dòng)具有特定時(shí)間窗口(例如通信)；任務(wù)通常要求在一定時(shí)間內(nèi)實(shí)現(xiàn)，而不能無限期等待；

2)活動(dòng)間存在時(shí)間約束：大部分活動(dòng)開始時(shí)間、持續(xù)時(shí)間和結(jié)束時(shí)間具有約束，例如航天器需要在相對(duì)于零點(diǎn)的10 min后執(zhí)行拍照動(dòng)作?；顒?dòng)間存在順序、并行、交錯(cuò)等多種時(shí)間約束；

3)有限的資源：航天器的燃料和存儲(chǔ)能力等有限，資源需要在一定的時(shí)間區(qū)間內(nèi)進(jìn)行管理和分配，以保證資源的合理利用和航天器任務(wù)的完成；

4)不確定性：空間環(huán)境復(fù)雜惡劣、不完全可觀，導(dǎo)致航天器活動(dòng)時(shí)間不固定，如火星車轉(zhuǎn)移到指定地點(diǎn)受火星表面崎嶇地形影響造成持續(xù)時(shí)間不確定。同時(shí)由于部件老化或損壞，航天器無法控制某些動(dòng)作的精準(zhǔn)實(shí)現(xiàn)，會(huì)出現(xiàn)執(zhí)行時(shí)間或效果偏差；

5)航天器系統(tǒng)復(fù)雜：航天器具有多個(gè)不同功能的子系統(tǒng)，不僅包含姿態(tài)控制等基本保障系統(tǒng)，還需要考慮執(zhí)行特定任務(wù)的專用系統(tǒng)，如有效載荷。不同子系統(tǒng)下，包含不同層級(jí)的執(zhí)行器或控制器，如閥門、傳感器等，航天器模型呈現(xiàn)復(fù)雜多樣性。

以上難點(diǎn)問題給航天器任務(wù)規(guī)劃技術(shù)提出新的挑戰(zhàn)：航天器模型復(fù)雜多樣，時(shí)間要求苛刻、約束密集耦合。針對(duì)具有時(shí)間屬性的規(guī)劃問題，通常采用先規(guī)劃生成順序動(dòng)作序列再進(jìn)行調(diào)度的方式，但會(huì)出現(xiàn)調(diào)度無法滿足時(shí)間和資源約束，需要重新規(guī)劃的情況，無法滿足航天器實(shí)時(shí)性要求。因此，面對(duì)航天器自主控制和運(yùn)行的實(shí)際應(yīng)用和發(fā)展趨勢(shì)，開展考慮時(shí)間屬性的航天器自主任務(wù)規(guī)劃技術(shù)具有重大的理論和現(xiàn)實(shí)意義。本文首先對(duì)航天器時(shí)態(tài)規(guī)劃技術(shù)進(jìn)行定義和規(guī)劃模型建立方法分析，隨后梳理國內(nèi)外任務(wù)規(guī)劃技術(shù)研究成果，最后分析主要方法優(yōu)缺點(diǎn)和發(fā)展趨勢(shì)，并對(duì)未來航天器時(shí)態(tài)規(guī)劃技術(shù)的研究方向提出建議。

1 航天器時(shí)態(tài)規(guī)劃的定義和建模方法

考慮航天器系統(tǒng)模型、領(lǐng)域約束和所處環(huán)境特征，給出航天器時(shí)態(tài)規(guī)劃技術(shù)定義，如下：

定義1.(航天器時(shí)態(tài)規(guī)劃技術(shù))航天器時(shí)態(tài)規(guī)劃技術(shù)是指根據(jù)空間環(huán)境感知和認(rèn)識(shí)以及航天器本身的能力和狀態(tài)，對(duì)時(shí)間屬性進(jìn)行顯示表示，利用人工智能搜索技術(shù)、知識(shí)建模技術(shù)和智能推理技術(shù)等，針對(duì)一定時(shí)間內(nèi)的任務(wù)目標(biāo)，對(duì)若干可供選擇的動(dòng)作進(jìn)行選擇和所涉及的約束進(jìn)行推理，自動(dòng)生成時(shí)間有序的活動(dòng)序列，實(shí)現(xiàn)將動(dòng)作的選擇和調(diào)度進(jìn)行整合。

時(shí)態(tài)規(guī)劃技術(shù)同時(shí)考慮航天器動(dòng)作之間的因果關(guān)系和時(shí)間約束，可以更真實(shí)地對(duì)航天應(yīng)用進(jìn)行建模和規(guī)劃。規(guī)劃問題定義是規(guī)劃前對(duì)規(guī)劃問題進(jìn)行的描述，因此規(guī)劃建模語言是自主規(guī)劃發(fā)展的關(guān)鍵。目前，時(shí)態(tài)規(guī)劃建模方法主要有兩種形式[17]：(1)擴(kuò)展?fàn)顟B(tài)空間表示方法，其基于狀態(tài)之間的時(shí)間限定持續(xù)區(qū)間；(2)時(shí)間線表示方法，其依賴于單個(gè)狀態(tài)變量隨時(shí)間的演化及時(shí)間線元素之間的約束。

1.1 狀態(tài)空間時(shí)態(tài)規(guī)劃建模方法

1.1.1以動(dòng)作為中心的模型表示語言

國際智能規(guī)劃大賽(IPC)公認(rèn)標(biāo)準(zhǔn)規(guī)劃領(lǐng)域定義語言(PDDL)[18]是一種以動(dòng)作為中心的建模語言，以STRIPS操作符和ADL語言為基礎(chǔ)，對(duì)動(dòng)作和狀態(tài)進(jìn)行標(biāo)準(zhǔn)化定義，使用前置條件和效果描述動(dòng)作的可用性和狀態(tài)轉(zhuǎn)換。針對(duì)實(shí)際規(guī)劃問題需求，提出使用較為廣泛的PDDL2.1版本[19]，在PDDL1.2基礎(chǔ)上定義持續(xù)動(dòng)作，增加了數(shù)值流、連續(xù)效果及靈活的規(guī)劃質(zhì)量度量等，核心思想是將持續(xù)動(dòng)作看作兩個(gè)瞬間的開始時(shí)和結(jié)束時(shí)的動(dòng)作，通過持續(xù)時(shí)間約束(限制動(dòng)作開始和結(jié)束時(shí)間之間的可能延遲)和持續(xù)性條件(要求在動(dòng)作執(zhí)行過程中的所有狀態(tài)都要保持一定條件)連接在一起。

PDDL2.1存在兩個(gè)局限性:(1)條件和效果只能放在動(dòng)作的開始和結(jié)束點(diǎn)?？梢酝ㄟ^將一個(gè)具有中間時(shí)間點(diǎn)的復(fù)雜持續(xù)動(dòng)作拆分為多個(gè)子動(dòng)作來避免這種限制，但手工編碼持續(xù)性動(dòng)作是困難的且容易出錯(cuò)。(2)問題定義僅由初始狀態(tài)和目標(biāo)狀態(tài)組成，導(dǎo)致無法輕松表達(dá)環(huán)境的演變知識(shí)(如航天器預(yù)計(jì)將在11∶05進(jìn)行對(duì)地觀測(cè))和對(duì)解決方案進(jìn)行時(shí)間上的限定約束(如從20點(diǎn)到22點(diǎn)發(fā)動(dòng)機(jī)不能工作)，以上兩種功能都在語言的后期版本中引入。PDDL2.2[20]的定時(shí)初始字元可用來描述環(huán)境的演化，它允許在任意時(shí)間對(duì)謂詞進(jìn)行真值賦值(如在時(shí)間11∶05時(shí)謂詞Point(dir1)將成為真值)。PDDL3.0[21]引入的狀態(tài)軌跡約束可用來表達(dá)時(shí)間上的擴(kuò)展目標(biāo)如截止期限。盡管這些擴(kuò)展在表示現(xiàn)實(shí)世界的問題上是必不可少的，但針對(duì)它們?cè)跁r(shí)態(tài)規(guī)劃領(lǐng)域的研究和應(yīng)用非常有限。

盡管以STRIPS為基礎(chǔ)的建模語言對(duì)規(guī)劃領(lǐng)域做出了很大貢獻(xiàn)，但是用來表示具有時(shí)間、資源、相互排斥關(guān)系和并行性仍具有一定困難。例如，為了表示時(shí)間和資源，需要引入大量的命題和領(lǐng)域原子，同時(shí)很難決定哪些動(dòng)作可以同時(shí)發(fā)生，無法指定動(dòng)作內(nèi)部中間時(shí)間點(diǎn)和解決多個(gè)動(dòng)作的共同影響。因此，要想解決航天任務(wù)這類現(xiàn)實(shí)問題必須尋找表達(dá)能力更強(qiáng)的規(guī)劃知識(shí)表達(dá)方式。

1.1.2以動(dòng)作為中心的時(shí)態(tài)規(guī)劃問題定義

以PDDL2.2為基礎(chǔ)，給出時(shí)態(tài)規(guī)劃問題和關(guān)鍵元素定義，其中在活動(dòng)、條件和效果的建模中體現(xiàn)出領(lǐng)域時(shí)間屬性。

定義2.時(shí)態(tài)規(guī)劃問題P由五元組定義P=(V,I,T,G,A)表示，式中：

V為命題條件集合；

I是初始狀態(tài)，對(duì)V中的所有命題的值分配T或F的完整集合；

T是一組定時(shí)初始字元，為一個(gè)元組([t]f:=v)，其中f∈V，t∈R+是壁鐘時(shí)間，在該時(shí)間f將被賦予布爾值v；

G?V是目標(biāo)狀態(tài)，當(dāng)規(guī)劃執(zhí)行完需要實(shí)現(xiàn)的命題條件集合；

1.2 基于時(shí)間線的時(shí)態(tài)規(guī)劃建模方法

1.2.1基于時(shí)間線的模型表示語言

基于時(shí)間線的任務(wù)規(guī)劃從不同角度處理時(shí)態(tài)規(guī)劃問題，不明確區(qū)分狀態(tài)、動(dòng)作和目標(biāo)，而是將規(guī)劃領(lǐng)域表示為獨(dú)立但相互作用的組件組成的系統(tǒng)，組件表示為時(shí)間線，由給定的時(shí)間約束集合支配。這種范式誕生于空間操作規(guī)劃和調(diào)度的背景下，在過去20年里已被應(yīng)用于空間探測(cè)任務(wù)的短期到長期規(guī)劃任務(wù)以及航天器在軌自主運(yùn)行等復(fù)雜情況。例如，DS-1采用的領(lǐng)域描述語言(DDL)[22]，使用狀態(tài)變量時(shí)間線表示航天器子系統(tǒng)，標(biāo)記用來代表某一狀態(tài)變量處于特定狀態(tài)的時(shí)間跨度或者間隔，協(xié)調(diào)條件用于描述時(shí)間約束。

以DDL語言為基礎(chǔ)，NASA提出了新領(lǐng)域定義語言(NDDL)[6]，用于規(guī)劃系統(tǒng)EUROPA的建模，采用兼容性來支配時(shí)間線上斷言得到合理安排(如代表著火星車移動(dòng)r到x的活動(dòng)，必須通過將r放在x處的斷言來滿足)。針對(duì)時(shí)間關(guān)系采用Allen的區(qū)間代數(shù)方法顯式定量指定了需要改變和保持的約束。一個(gè)解是一組斷言之間不存在空隙的時(shí)間線，并滿足所有的兼容性。這個(gè)范例允許描述帶有時(shí)間項(xiàng)的規(guī)劃領(lǐng)域、資源、并行活動(dòng)、活動(dòng)集合的互斥現(xiàn)象、分割先前條件和條件效果。ASPEN建模語言AML[23]是考慮分層任務(wù)網(wǎng)絡(luò)(HTN)思想的基于時(shí)間線的表示語言，核心部分是活動(dòng)，可以用來表示目標(biāo)、高級(jí)任務(wù)或基本動(dòng)作，子活動(dòng)用于將目標(biāo)和高層次任務(wù)細(xì)化為原始動(dòng)作。

其與基于STRIPS操作符的規(guī)劃建模語言相比，存在幾個(gè)主要不同點(diǎn)：

1)使用變量/值的表示方法而不是命題邏輯；

2)不區(qū)分狀態(tài)和動(dòng)作，僅使用區(qū)間和區(qū)間之間的約束來描述，規(guī)劃問題只是需要將時(shí)間線用區(qū)間填滿即可；

3)對(duì)于時(shí)間要求嚴(yán)格的空間環(huán)境，使用基于時(shí)間線的表示方式使得規(guī)劃解魯棒性更強(qiáng)，有利于與規(guī)劃序列執(zhí)行相結(jié)合。

由于航天器需要同時(shí)支持時(shí)間和資源的處理，且需要考慮規(guī)劃序列的執(zhí)行，因此，基于時(shí)間線的建模方法在航天任務(wù)規(guī)劃系統(tǒng)中得到廣泛應(yīng)用。但同樣存在缺點(diǎn)，主要體現(xiàn)在缺乏因果關(guān)系的明確表示，在規(guī)劃過程中較難應(yīng)用啟發(fā)式和直接描述冗余約束，修改模型困難。同時(shí)缺少像PDDL一樣的規(guī)范標(biāo)準(zhǔn)[24]。

1.2.2基于時(shí)間線的時(shí)態(tài)規(guī)劃問題定義

根據(jù)航天器任務(wù)規(guī)劃特點(diǎn)并結(jié)合當(dāng)前研究，給出基于時(shí)間線的時(shí)態(tài)規(guī)劃問題的規(guī)范化定義。

定義3.狀態(tài)變量x是個(gè)四元組x=(N，V,T,D)，式中：N是狀態(tài)變量名稱；V是狀態(tài)變量值的非空集合；T:V→2V為狀態(tài)變量值轉(zhuǎn)換函數(shù)；D:V→T×T∞是狀態(tài)變量值持續(xù)函數(shù)，D(v)=(dmin,dmax)，dmin≥0且dmax≥dmin，表明狀態(tài)變量在時(shí)間(dmin,dmax)內(nèi)保持值為v。

定義4.如果x=(N，V,T,D)是一個(gè)狀態(tài)變量，對(duì)于x的標(biāo)記形式為：xi=(v,[e,e′],[d,d′])，其中xi是標(biāo)記名稱，i∈N；v∈V，e,e′,d,d′∈T，對(duì)于D(v)=(dmin,dmax)，e≤e′且dmin≤d≤d′≤dmax。

對(duì)于狀態(tài)變量x的時(shí)間線Lx是對(duì)于x的標(biāo)記的有限序列，形式為x1=(v1,[e1,e′1],[d1,d′1]),…,xk=(vk,[ek,e′k],[dk,d′k])，其中i=1,…,k-1，vi+1∈T(vi)且e′i≤ei+1。最后一個(gè)標(biāo)記的區(qū)間[ek,e′k]被稱為時(shí)間線的時(shí)間范圍，標(biāo)記數(shù)量k為組成時(shí)間線的長度。狀態(tài)變量和時(shí)間線如圖1所示。

圖1 狀態(tài)變量示意圖Fig.1 Diagram of state variable

一組時(shí)間線的規(guī)劃時(shí)間范圍H是每個(gè)時(shí)間線時(shí)間范圍的最小值。

時(shí)間關(guān)系是基于時(shí)間線的規(guī)劃模型中重要元素，它們可以是兩個(gè)時(shí)間段之間的關(guān)系，也可以是一個(gè)時(shí)間段和一個(gè)時(shí)間點(diǎn)之間的關(guān)系。

定義5.時(shí)間段之間時(shí)間關(guān)系表示形式為Aγ[l,u]B，其中A=[sA,eA]和B=[sB,eB]為時(shí)間段，sA,eA，sB,eB∈T，l∈T，u∈T∞且γ∈R，R為Allen十三種時(shí)間約束關(guān)系集合，即R={before, meet, overlap, start, during, finish, after, it-met-by, is-overlapped-by, is-started-by, includes, is-finished-by, equal}。

定義6.原子是指定常量⊥或者時(shí)間關(guān)系形式aiγ[l,u]aj或aiγ′[l,u]t，其中ai和aj是標(biāo)記變量，l,t∈T，u∈T∞，γ∈R和γ′∈R′。

特稱命題定義為?a1[x1=v1]…an[xn=vn].C形式，其中a1,…,an是不同的標(biāo)記變量；對(duì)于所有i=1,…,n，xi是狀態(tài)變量，vi∈V(xi)(即ai[xi=vi]是被標(biāo)注的標(biāo)記變量)；C是原子的結(jié)合。

命題的界限變量是a1,…,an，任何可能發(fā)生在C中的與a1,…,an不同的變量在命題中是自由發(fā)生的。特稱命題的析取組成了同步規(guī)則。

定義7.同步規(guī)則表示為a0[x0=v0]→ξ1∨…∨ξk(k≥1)，其中ξi是一個(gè)特稱命題，其邊界變量是與a0不同的所有變量，只有a0是可能自由發(fā)生的。a0[x0=v0]被稱為規(guī)則觸發(fā)條件。當(dāng)觸發(fā)條件為空的時(shí)候，形式為⊥→ξ1∨…∨ξk(k≥1)，其中ξi是沒有自由變量的特稱命題。

定義8.基于時(shí)間線的規(guī)劃領(lǐng)域定義為二元組D=(VS，S)，其中VS為狀態(tài)變量集合；S為同步規(guī)則集合。

定義9.對(duì)于領(lǐng)域D=(VS，S)的規(guī)劃目標(biāo)G是雙元組(Γ,Δ)，其中Γ是形式(g,x,v)的集合，g是目標(biāo)標(biāo)記變量的名字，x∈VS且v∈V(x)；Δ為關(guān)系目標(biāo)，是正向布爾公式，僅包含發(fā)生在Γ中的目標(biāo)。

定義10.基于時(shí)間線的時(shí)態(tài)規(guī)劃問題定義為三元組PT=(D,G,H)，其中D為規(guī)劃領(lǐng)域，G為規(guī)劃目標(biāo)，H∈T是規(guī)劃時(shí)間范圍。

定義11.靈活計(jì)劃Π是二元組(L,R)，其中L是時(shí)間線集合，R是標(biāo)記間關(guān)系集合，包含標(biāo)記名稱和所屬時(shí)間線。

定義12.對(duì)于規(guī)劃問題PT=(D,G,H)，靈活計(jì)劃Π=(L,R)是有效的當(dāng)且僅當(dāng)：L是對(duì)狀態(tài)變量VS的時(shí)間線集合，Π滿足S中的所有同步規(guī)則。

對(duì)于規(guī)劃問題PT=(D,G,H)，當(dāng)靈活規(guī)劃Π有效且滿足目標(biāo)G，則該規(guī)劃為問題的一個(gè)規(guī)劃解。

2 時(shí)態(tài)規(guī)劃技術(shù)研究現(xiàn)狀

航天器時(shí)態(tài)規(guī)劃問題中，通常需要處理持續(xù)活動(dòng)、目標(biāo)截止時(shí)間、并行性、軌跡約束和連續(xù)變化等時(shí)間屬性。由于缺少特定標(biāo)準(zhǔn)，研究人員通常以經(jīng)典規(guī)劃技術(shù)為核心，挑選有限的關(guān)注因素進(jìn)行拓展，因此往往處理時(shí)間能力不足。同時(shí)，由于規(guī)劃知識(shí)建模語言限制，沒有基于時(shí)間線的規(guī)劃器參加IPC大賽(除2002年的IxTeT)，缺少標(biāo)準(zhǔn)化的對(duì)比與評(píng)價(jià)。根據(jù)規(guī)劃技術(shù)特點(diǎn)，將時(shí)態(tài)規(guī)劃技術(shù)分為前向鏈、模型轉(zhuǎn)換、規(guī)劃空間和HTN四種類別，每類所包含的規(guī)劃方法以及各自的特點(diǎn)如表1所示。

2.1 前向鏈時(shí)態(tài)規(guī)劃方法

大部分時(shí)態(tài)規(guī)劃器直接由經(jīng)典規(guī)劃器拓展而來，時(shí)間屬性滿足方向由前向鏈時(shí)態(tài)規(guī)劃器主導(dǎo)。根據(jù)前向鏈規(guī)劃器的搜索空間將其分為三類：

2.1.1首次適應(yīng)時(shí)態(tài)規(guī)劃方法

首次適應(yīng)時(shí)態(tài)規(guī)劃器本質(zhì)上為經(jīng)典規(guī)劃器，通過采用經(jīng)典規(guī)劃器生成順序解決方案，然后進(jìn)行重新調(diào)度實(shí)現(xiàn)時(shí)間約束滿足，用最簡(jiǎn)單明了的方法來處理時(shí)間屬性，如圖2所示。2008年IPC組織者利用MetricFF[25]規(guī)劃器為比賽提供對(duì)比的基礎(chǔ)方案，最終贏得了該屆時(shí)間滿足方向的比賽。YAHSP[26-28]規(guī)劃器的第二版和第三版在規(guī)劃過程中使用Bonet和Geffner的hadd啟發(fā)式方法[29]，增加了從當(dāng)前狀態(tài)構(gòu)建的松弛規(guī)劃圖中所有目標(biāo)流的深度。DAEYAHSP2[30]規(guī)劃器在任意時(shí)間規(guī)劃方法中，進(jìn)行多次后處理，通過遺傳規(guī)劃技術(shù)來進(jìn)一步找到優(yōu)化的規(guī)劃序列。其他類型規(guī)劃器如MIPS[31]和LPG的早期版本[32]也采用重新調(diào)度的方法來支持時(shí)態(tài)規(guī)劃問題。

圖2 首次適應(yīng)時(shí)態(tài)規(guī)劃方法示意圖Fig.2 Diagram of first-fit temporal planning

盡管此類規(guī)劃器在大賽中取得一定優(yōu)勢(shì)，但它們只能解決簡(jiǎn)單時(shí)態(tài)規(guī)劃問題，不能求解具有必須并行動(dòng)作的規(guī)劃問題，例如“姿態(tài)定向”和“目標(biāo)拍照”兩個(gè)動(dòng)作只能同時(shí)執(zhí)行而不能順序執(zhí)行(如圖3所示)。在實(shí)際應(yīng)用中，先規(guī)劃后調(diào)度方式容易造成重規(guī)劃，無法滿足航天器實(shí)時(shí)性要求。

圖3 必須并行動(dòng)作示意圖Fig.3 Diagram of required concurrency action

2.1.2決策時(shí)點(diǎn)時(shí)態(tài)規(guī)劃方法

狀態(tài)空間下的時(shí)態(tài)規(guī)劃器需要克服一個(gè)重要的技術(shù)障礙：每個(gè)動(dòng)作可以從無限多的時(shí)間點(diǎn)中的任一時(shí)間點(diǎn)開始。大部分規(guī)劃器通過將動(dòng)作的可能開始時(shí)間限制在一小部分的特殊時(shí)間點(diǎn)(稱為決策時(shí)點(diǎn))內(nèi)避免無限分支因素。規(guī)劃器在時(shí)間狀態(tài)空間進(jìn)行搜索，時(shí)間狀態(tài)N的核心是世界狀態(tài)state(N)，使其可以利用可達(dá)性啟發(fā)式，通過增殖和推進(jìn)兩種方式生成子節(jié)點(diǎn)。該方法的關(guān)鍵特性是決策時(shí)點(diǎn)的選擇：在一些動(dòng)作剛結(jié)束或剛開始的時(shí)候選擇開始一個(gè)動(dòng)作。

TLPlan[33]規(guī)劃器首先在前向鏈中引入了決策時(shí)點(diǎn)，通過在時(shí)間戳上啟動(dòng)新的動(dòng)作或?qū)r(shí)間戳提前(通常在下一個(gè)效果之后)生成搜索節(jié)點(diǎn)的后繼節(jié)點(diǎn)，使用線性時(shí)間邏輯進(jìn)行搜索控制，具有明顯領(lǐng)域相關(guān)性，可處理必須并行活動(dòng)。許多有影響力的時(shí)態(tài)規(guī)劃器以此為基礎(chǔ)，如SAPA規(guī)劃器[34]建立在Fast Forward規(guī)劃器上，將決策時(shí)點(diǎn)思想應(yīng)用到領(lǐng)域無關(guān)規(guī)劃中，首次提出時(shí)間松弛規(guī)劃圖(TRPG)來計(jì)算時(shí)間標(biāo)記狀態(tài)的啟發(fā)式值，可處理具有連續(xù)時(shí)間區(qū)間的活動(dòng)、具有截止時(shí)間的目標(biāo)和度量資源約束。TFD規(guī)劃器[35]基于Fast Downward規(guī)劃器，將多值規(guī)劃任務(wù)作為輸入，將持續(xù)并行動(dòng)作分為多類瞬時(shí)動(dòng)作，進(jìn)而繼續(xù)使用因果圖啟發(fā)式和上下文增強(qiáng)累積啟發(fā)式進(jìn)行搜索。TP4規(guī)劃器[36]使用反向狀態(tài)空間搜索以及與時(shí)間或資源相關(guān)的可采納啟發(fā)式，可求解部分時(shí)態(tài)規(guī)劃問題，其中持續(xù)時(shí)間以單位時(shí)間衡量。

與經(jīng)典規(guī)劃相比，決策時(shí)點(diǎn)規(guī)劃方法在幾乎每個(gè)搜索節(jié)點(diǎn)都有一個(gè)額外的分支，造成計(jì)算資源極大浪費(fèi)。支持具有必須并行活動(dòng)的情況，但對(duì)于豐富的時(shí)間表達(dá)問題仍然不完備[37]。此外，由于它們先選擇可以執(zhí)行動(dòng)作的時(shí)間，后選擇執(zhí)行哪個(gè)動(dòng)作，導(dǎo)致缺乏系統(tǒng)性，例如對(duì)于完全獨(dú)立于計(jì)劃其余部分的動(dòng)作，規(guī)劃器將在每個(gè)決策時(shí)點(diǎn)都會(huì)考慮其執(zhí)行，導(dǎo)致了許多可被視為等同的計(jì)劃。

2.1.3時(shí)間提升規(guī)劃方法

時(shí)間提升規(guī)劃器利用時(shí)間提升的思想突破了決策時(shí)點(diǎn)規(guī)劃器的局限性，即延遲關(guān)于何時(shí)執(zhí)行動(dòng)作的決策，直到所有關(guān)于執(zhí)行哪些動(dòng)作的決策完成，并通過簡(jiǎn)單時(shí)間網(wǎng)絡(luò)(STN)跟蹤時(shí)間約束。CRIKEY規(guī)劃器[38]是首次針對(duì)時(shí)態(tài)PDDL問題的完整的前向鏈規(guī)劃方法，核心為MetricFF規(guī)劃算法，利用松弛規(guī)劃圖計(jì)算啟發(fā)式和有用的動(dòng)作輔助動(dòng)作選擇，在檢測(cè)到包絡(luò)動(dòng)作后，通過綁定STN和使用貝爾曼算法檢測(cè)并行活動(dòng)的時(shí)間一致性，從而處理活動(dòng)交錯(cuò)并行的問題，規(guī)劃完成后使用時(shí)間約束網(wǎng)絡(luò)對(duì)整體規(guī)劃進(jìn)行推理，確定活動(dòng)準(zhǔn)確執(zhí)行時(shí)間。

以上思想在CRIKEY3[39]，POPF[40]，COLIN[41]和OPTIC[42]規(guī)劃器中均得到使用。例如，POPF規(guī)劃器在前向搜索基礎(chǔ)上支持偏序規(guī)劃，采用后期承諾方法實(shí)現(xiàn)部分排序和靈活性，即延遲對(duì)排序決策、時(shí)標(biāo)和數(shù)值參數(shù)值的承諾，在動(dòng)作開始和結(jié)束時(shí)管理約束集。同時(shí)受益于前向規(guī)劃的信息搜索控制，通過線性規(guī)劃求解器實(shí)現(xiàn)時(shí)間和度量決策。POPF2規(guī)劃器在POPF上進(jìn)行拓展，對(duì)順序約束做更少承諾和改進(jìn)時(shí)間松弛規(guī)劃圖啟發(fā)式方法，采用Stochastic-POPF的代價(jià)優(yōu)化，并使用了隨時(shí)搜索功能，可以找到更多完成時(shí)間有效的規(guī)劃解。COLIN規(guī)劃器值得注意的是它能夠處理并行性甚至線性連續(xù)變化的情況。

與首次適應(yīng)時(shí)態(tài)規(guī)劃器和決策時(shí)點(diǎn)時(shí)態(tài)規(guī)劃器不同，時(shí)間提升規(guī)劃器對(duì)于PDDL2.1的語義是完備的，并且可以解決具有必須并發(fā)和相互依賴的動(dòng)作的問題。

以上所有前向鏈規(guī)劃器主要依靠改進(jìn)經(jīng)典規(guī)劃器的啟發(fā)法來指導(dǎo)搜索，其中大部分是基于忽略了動(dòng)作的刪除效果而構(gòu)建的TRPG，例如SAPA，CRIKEY，COLIN和OPTIC等。盡管這些啟發(fā)式方法對(duì)規(guī)劃大賽中問題非常有效，但其效率依賴于完全定義的狀態(tài)，對(duì)于具有必須并行動(dòng)作的規(guī)劃問題使用啟發(fā)式仍是挑戰(zhàn)，因此對(duì)于航天器規(guī)劃情景有效適應(yīng)存在一定困難。

2.2 模型轉(zhuǎn)換時(shí)態(tài)規(guī)劃方法

模型轉(zhuǎn)換規(guī)劃方法通常將任務(wù)規(guī)劃模型轉(zhuǎn)換為可滿足問題模型或使用特殊數(shù)據(jù)結(jié)構(gòu)，并采用相應(yīng)技術(shù)進(jìn)行求解。根據(jù)轉(zhuǎn)換后模型，可分為基于圖規(guī)劃和可滿足技術(shù)的時(shí)態(tài)規(guī)劃方法。

2.2.1基于圖規(guī)劃的時(shí)態(tài)規(guī)劃方法

圖規(guī)劃(GraphPlan)技術(shù)主要思想是構(gòu)造一個(gè)包含所有可能狀態(tài)的緊湊搜索樹，并在該樹中找到一個(gè)解。該算法包括圖擴(kuò)展和解提取兩個(gè)階段，采用可達(dá)性分析排除許多不相容的動(dòng)作序列以及組合，豐富的規(guī)劃圖結(jié)構(gòu)使得對(duì)規(guī)劃研究和拓展道路更為寬廣。對(duì)于時(shí)態(tài)規(guī)劃領(lǐng)域，通常在動(dòng)作層或命題層引入時(shí)間進(jìn)行拓展。TGP規(guī)劃器[43]首次在GraphPlan規(guī)劃器上考慮了持續(xù)STRIPS動(dòng)作。在規(guī)劃圖動(dòng)作層引入時(shí)間信息，構(gòu)建時(shí)從一命題層開始，通過在所有可能的動(dòng)作中選擇一個(gè)最早結(jié)束的動(dòng)作來推進(jìn)。該規(guī)劃器具有決策時(shí)點(diǎn)規(guī)劃方法特點(diǎn)，對(duì)于豐富時(shí)間屬性規(guī)劃問題不完備。TPSYS[44]規(guī)劃器做出改進(jìn)，可以處理PDDL2.1 Level3時(shí)態(tài)規(guī)劃域，動(dòng)作可以在開始時(shí)具有效果。TGP和TPSYS在動(dòng)作持續(xù)時(shí)間差別很大時(shí)，規(guī)劃圖的構(gòu)建非常緩慢。

LPGP規(guī)劃器[45]是針對(duì)PDDL2.1首個(gè)領(lǐng)域無關(guān)的完備方法，在GraphPlan框架中將時(shí)間引入命題層，避免了因動(dòng)作持續(xù)時(shí)間差別大造成的效率低。每個(gè)持續(xù)動(dòng)作被分為開始動(dòng)作、結(jié)束動(dòng)作和不變性檢查動(dòng)作，通過一種新穎的規(guī)劃圖時(shí)間泛化方法歸約為線性規(guī)劃處理時(shí)間信息，如圖4所示。TLP-GP[46]規(guī)劃器進(jìn)行了類似的工作，但使用了析取時(shí)間網(wǎng)絡(luò)處理時(shí)間約束。LPG[32]規(guī)劃器在規(guī)劃圖中應(yīng)用隨機(jī)局部搜索，最新版本使用LPGP方法生成規(guī)劃圖處理交錯(cuò)并行性，同時(shí)目標(biāo)函數(shù)中考慮了并行動(dòng)作的個(gè)數(shù)和從當(dāng)前狀態(tài)開始的整個(gè)規(guī)劃的執(zhí)行時(shí)間。優(yōu)化時(shí)態(tài)規(guī)劃系統(tǒng)CPPlanner作為第一個(gè)基于Graphplan的優(yōu)化規(guī)劃器可以處理更豐富的時(shí)間領(lǐng)域(即動(dòng)作可以產(chǎn)生中間效應(yīng))。

圖4 LPGP規(guī)劃圖示意圖Fig.4 Diagram of LPGP plan graph

圖規(guī)劃方法在處理時(shí)態(tài)規(guī)劃領(lǐng)域時(shí)，采用將持續(xù)動(dòng)作分解為瞬時(shí)動(dòng)作處理，在時(shí)間處理豐富性方面一直在進(jìn)步，但針對(duì)具有豐富時(shí)間約束的航天器規(guī)劃問題仍然存在搜索空間大的問題。

2.2.2基于可滿足技術(shù)的時(shí)態(tài)規(guī)劃方法

基于可滿足技術(shù)(SAT)的規(guī)劃方法將規(guī)劃問題編碼為SAT公式，其中每個(gè)變量表示相應(yīng)動(dòng)作或命題在潛在規(guī)劃中的發(fā)生位置，因果關(guān)系被表示為若干底層子句，輸出規(guī)劃具有有效步驟數(shù)，每個(gè)步驟可包含多個(gè)動(dòng)作，通過SAT求解器尋找一個(gè)模型。如果模型存在，則會(huì)從中提取一個(gè)規(guī)劃。在優(yōu)化經(jīng)典規(guī)劃和并行規(guī)劃中，可滿足性規(guī)劃性能表現(xiàn)一直很強(qiáng)。為了能夠處理時(shí)態(tài)規(guī)劃，STEP、SCP2和T-SATPLAN規(guī)劃器等利用離散時(shí)間表示方法，為每個(gè)步驟分配一個(gè)離散時(shí)間標(biāo)簽，但無法有效利用并行性，且造成計(jì)算代價(jià)較大[47]。

最新的ITSAT[47]規(guī)劃器將可滿足性檢查方法擴(kuò)展到時(shí)態(tài)規(guī)劃領(lǐng)域，支持求解具有必須并發(fā)性的PDDL2.1問題。首先將所有持續(xù)性動(dòng)作分解為兩個(gè)瞬時(shí)動(dòng)作，通過求解非時(shí)態(tài)問題得到因果關(guān)系有效規(guī)劃，然后，規(guī)劃器通過STN對(duì)規(guī)劃問題中的時(shí)間約束進(jìn)行推理從而實(shí)現(xiàn)調(diào)度。如果不存在這樣的調(diào)度，則通過附加子句擴(kuò)展問題，避免造成時(shí)間不一致的因素，然后重新啟動(dòng)該過程，直到找到時(shí)間有效的規(guī)劃解，流程如圖5所示。

圖5 ITSAT規(guī)劃流程示意圖Fig.5 Diagram of TISAT planning method

2.3 規(guī)劃空間時(shí)態(tài)規(guī)劃方法

在規(guī)劃空間規(guī)劃中，節(jié)點(diǎn)是部分規(guī)劃，弧是進(jìn)一步完成部分規(guī)劃的細(xì)化操作，算法從一個(gè)空規(guī)劃開始，經(jīng)過細(xì)化操作，以最終包含實(shí)現(xiàn)所有目標(biāo)的解決方案的節(jié)點(diǎn)為目標(biāo)。特點(diǎn)是使用最小承諾原則，將有關(guān)動(dòng)作順序和參數(shù)綁定的決策推遲到強(qiáng)制執(zhí)行為止，產(chǎn)生的規(guī)劃序列更具魯棒性和靈活性，對(duì)于解決時(shí)態(tài)規(guī)劃問題具有一定優(yōu)勢(shì)。對(duì)于時(shí)間拓展，使用時(shí)間區(qū)間來表示動(dòng)作和命題，動(dòng)作之間的因果關(guān)系被部分規(guī)劃中的時(shí)間順序所取代，通過時(shí)間映射管理器啟發(fā)的系統(tǒng)進(jìn)行沖突處理。根據(jù)規(guī)劃問題表示和求解方式的不同，分為結(jié)合偏序因果鏈和基于時(shí)間線的規(guī)劃空間時(shí)態(tài)規(guī)劃方法。

2.3.1偏序因果鏈規(guī)劃空間規(guī)劃方法

VHPOP[48]是一種基本的規(guī)劃空間規(guī)劃器和偏序因果鏈的完整應(yīng)用，建立在UCPOP規(guī)劃器基礎(chǔ)上，支持持續(xù)動(dòng)作并采用簡(jiǎn)單時(shí)間約束問題(STP)來進(jìn)行時(shí)間推理，并將領(lǐng)域無關(guān)規(guī)劃中的啟發(fā)式方法應(yīng)用到具有持續(xù)動(dòng)作的規(guī)劃領(lǐng)域。與以前的偏序規(guī)劃器相比，啟發(fā)式方法的使用很大程度上提高了規(guī)劃效率，但是VHPOP不支持?jǐn)?shù)值效果與前提條件，仍不具有競(jìng)爭(zhēng)力或可擴(kuò)展性，落后于當(dāng)前的領(lǐng)先技術(shù)。

Vidal和Geffner的CPT[49]是一個(gè)更全面的規(guī)劃空間規(guī)劃器，應(yīng)用偏序因果鏈并結(jié)合約束可滿足技術(shù)，通過推斷和搜索尋找具有最佳完成時(shí)間的規(guī)劃。CPT優(yōu)化規(guī)劃效率的關(guān)鍵是使用編碼為CSP的修剪規(guī)則，將時(shí)間約束編碼為STP并通過Lhomme的邊界一致性方法來檢查。然而，CPT限制動(dòng)作不會(huì)重疊，因此CPT雖可以處理持續(xù)性動(dòng)作，但無法處理必須并行性，是不完備的。

規(guī)劃空間規(guī)劃方法在時(shí)間拓展方面起到率先作用，基于時(shí)間線的方法和HTN方法均采用規(guī)劃空間規(guī)劃思想，且在航天器任務(wù)規(guī)劃中得到廣泛應(yīng)用。

2.3.2基于時(shí)間線規(guī)劃技術(shù)

迄今為止，基于時(shí)間線的規(guī)劃方法是空間領(lǐng)域?qū)嵺`中應(yīng)用最成功的方法[50-51]。受控制理論啟發(fā)，將領(lǐng)域知識(shí)建立為基于時(shí)間線的時(shí)態(tài)規(guī)劃模型，規(guī)劃過程在表示世界的初始已知事實(shí)的時(shí)間線集合上進(jìn)行操作，通常采用規(guī)劃空間搜索方法，根據(jù)期望要求迭代添加值和時(shí)間約束完善時(shí)間線的行為[52]，如圖6所示。方法重點(diǎn)在于約束系統(tǒng)的時(shí)間演化，而不是合成一組順序動(dòng)作，以實(shí)現(xiàn)期望的目標(biāo)狀態(tài)。

圖6 基于時(shí)間線的時(shí)態(tài)規(guī)劃方法示意圖Fig.6 Sketch of timeline-based planning method

基于時(shí)間線規(guī)劃方法可以追溯到IxTeT規(guī)劃器[53]，以規(guī)劃空間規(guī)劃方法支持顯式的時(shí)間和資源，使用年代記定義了時(shí)間點(diǎn)作為表示時(shí)間關(guān)系的基礎(chǔ)。采用基于最小承諾原則的領(lǐng)域無關(guān)搜索策略，內(nèi)部大部分表示和推理由特定的約束可滿足問題來處理。NASA和ESA等航天大國和機(jī)構(gòu)均開發(fā)了基于時(shí)間線框架的規(guī)劃系統(tǒng)，例如HSTS(RAX-PS)、ASPEN、EUROPA和APSI，均采用與時(shí)間線和令牌相似方法表示狀態(tài)變量值隨時(shí)間的變化和持續(xù)性，其中部分時(shí)間線與動(dòng)作和感知直接相關(guān)[54]，緊密集成規(guī)劃和調(diào)度，使用兼容性的概念來描述各時(shí)間線之間的相互作用以及時(shí)間線上令牌的關(guān)系。例如，在代表火星車位置的時(shí)間線上，與值going(a,b)相關(guān)的時(shí)間區(qū)間必須由at(a)和at(b)相連。規(guī)劃器通過缺陷挑選和求解的機(jī)制進(jìn)行規(guī)劃，并從規(guī)劃空間規(guī)劃中借鑒了大部分搜索技術(shù)，使用手工編碼的領(lǐng)域控制知識(shí)來指導(dǎo)搜索，尋找滿足所有兼容性的完全定義的時(shí)間線。EUROPA基于HSTS思想進(jìn)行拓展，將規(guī)劃視為一個(gè)動(dòng)態(tài)約束滿足問題，規(guī)劃器的選擇只會(huì)導(dǎo)致在底層約束網(wǎng)絡(luò)中添加約束。因此，EUROPA不僅用于規(guī)劃，而且還可用于處理留給CSP或SAT求解器的問題，如調(diào)度和優(yōu)化問題。

ESA啟動(dòng)了APSI計(jì)劃[9]，確定了基于時(shí)間線的表示框架(APSI-TRF)，但其目標(biāo)是基于時(shí)間線的審議層為實(shí)施基于時(shí)間線的規(guī)劃器提供便利，包括時(shí)間線表示和專門的約束求解器模塊，對(duì)時(shí)間約束和綁定約束進(jìn)行推理。它已被用作GOAC-APSI規(guī)劃器的構(gòu)建模塊和MrSPOCK的基礎(chǔ)層。

2.4 基于HTN的規(guī)劃技術(shù)

HTN規(guī)劃由于任務(wù)分層分解原理和領(lǐng)域知識(shí)表示的可表達(dá)性而適合于大規(guī)模的實(shí)際規(guī)劃問題。像規(guī)劃空間規(guī)劃器一樣，HTN規(guī)劃器維護(hù)具有因果關(guān)系的部分規(guī)劃表示，并進(jìn)一步通過分解將抽象動(dòng)作轉(zhuǎn)換為子動(dòng)作[55]。HTN方法發(fā)展于規(guī)劃空間規(guī)劃，SHOP和SHOP2規(guī)劃器引入了基于狀態(tài)的HTN規(guī)劃器，從而發(fā)生了分層規(guī)劃的重大轉(zhuǎn)變，其通過順序構(gòu)建計(jì)劃來遵循前向鏈機(jī)制[56]。為了處理時(shí)態(tài)規(guī)劃領(lǐng)域，SHOP2開發(fā)一種多時(shí)間線預(yù)處理(MTP)技術(shù)，將時(shí)間PDDL操作符轉(zhuǎn)換為SHOP2操作符，該操作符在當(dāng)前狀態(tài)下為多個(gè)時(shí)間線維護(hù)統(tǒng)計(jì)信息，跟蹤當(dāng)前狀態(tài)下的時(shí)間信息。規(guī)劃方法是圖靈完備的，并且針對(duì)大量規(guī)劃問題是健全而完整的。SHOP2的操作符與PDDL中的Level 2動(dòng)作具有相同的表現(xiàn)力，但是SHOP2不明確支持PDDL Level 3中的持續(xù)性動(dòng)作且沒有明確的機(jī)制來推理持續(xù)性和并發(fā)動(dòng)作。

SIADEX-TD[57]規(guī)劃器能夠應(yīng)對(duì)更豐富的時(shí)間規(guī)劃問題(如部分訂單度量結(jié)構(gòu)、截止日期、時(shí)間界標(biāo)、同步功能或活動(dòng)并行執(zhí)行)，通過動(dòng)作鏈構(gòu)建了一個(gè)內(nèi)在的順序解決方案，在原有SIADEX的規(guī)劃范式下，使用STN分兩步對(duì)時(shí)間約束進(jìn)行表示和推理：將抽象任務(wù)分解為子任務(wù)后，則在規(guī)劃中引入低細(xì)節(jié)定性時(shí)間約束，作為規(guī)劃的時(shí)間框架。隨后，一旦將其子操作明確包含在規(guī)劃中，便添加更精確的時(shí)間約束，以編碼規(guī)劃中每個(gè)最終操作之間的因果關(guān)系。另一方面，SIADEX-TD支持Allen和van Benthem獨(dú)立定義的所有關(guān)系，允許在持續(xù)性動(dòng)作中的任意時(shí)間點(diǎn)放置效果，條件僅限于動(dòng)作開始時(shí)間進(jìn)行。但是，如果多個(gè)順序解決方案將導(dǎo)致相同的調(diào)度計(jì)劃，則部分順序計(jì)劃將在搜索空間中出現(xiàn)多次，且無法處理并行性。

SHOP2會(huì)生成時(shí)間固定的調(diào)度表，與SIADEX-TD的STN帶有活動(dòng)最早執(zhí)行時(shí)間的調(diào)度表一致，但是SIADEX-TD能夠處理截止日期和地標(biāo)，并根據(jù)其他條件(即最新執(zhí)行時(shí)間)獲得不同的調(diào)度表。針對(duì)使用STN進(jìn)行時(shí)間推理的方法，Li[58]等進(jìn)行拓展，可生成靈活規(guī)劃解。為了能夠處理時(shí)間約束復(fù)雜的航天器規(guī)劃問題，HTN方法與基于時(shí)間線方法結(jié)合是當(dāng)前的一個(gè)研究方向[59]。

3 航天器時(shí)態(tài)規(guī)劃技術(shù)分析與發(fā)展建議

3.1 航天器時(shí)態(tài)規(guī)劃發(fā)展趨勢(shì)分析

針對(duì)航天器時(shí)態(tài)規(guī)劃具有規(guī)劃對(duì)象和動(dòng)作數(shù)量多、約束復(fù)雜和實(shí)時(shí)性要求高的特點(diǎn)，時(shí)態(tài)規(guī)劃技術(shù)不斷改進(jìn)和發(fā)展來滿足現(xiàn)實(shí)問題需求，其發(fā)展趨勢(shì)如下：

1)提升啟發(fā)式規(guī)劃方法求解航天器規(guī)劃問題的能力?；赑DDL的規(guī)劃方法在搜索過程中表示規(guī)劃和計(jì)算啟發(fā)式依賴于規(guī)劃知識(shí)的根本表達(dá)形式，使得開發(fā)的啟發(fā)式規(guī)劃方法難以適應(yīng)航天器規(guī)劃問題(可包含數(shù)千個(gè)對(duì)象和基本動(dòng)作實(shí)例)。因此，有些研究嘗試消除經(jīng)典規(guī)劃器的限制[60-61]，例如Ridder和Fox[60]構(gòu)建一個(gè)提升規(guī)劃圖用于啟發(fā)式評(píng)估，但其改進(jìn)仍是增量開發(fā)，未脫離經(jīng)典規(guī)劃的其他限制，并且尚未適應(yīng)于時(shí)態(tài)規(guī)劃。

2)規(guī)劃中時(shí)間知識(shí)表達(dá)和處理能力亟需進(jìn)一步加強(qiáng)。航天器模型中時(shí)間約束復(fù)雜，對(duì)于PDDL2.1語義完備的規(guī)劃器(如CRIKEY3)對(duì)任務(wù)規(guī)劃問題中時(shí)間屬性表示和處理能力有限。因此，拓展規(guī)劃器時(shí)間處理能力受到當(dāng)前研究重視，如OPTIC規(guī)劃器支持PDDL2.2及PDDL3子集，TLP-GP使用更具表現(xiàn)力的語言，可在操作中的任意固定時(shí)間使用定時(shí)的初始文字、期限、條件和效果。

3)高性能時(shí)態(tài)規(guī)劃算法是目前研究重點(diǎn)。為了能夠處理持續(xù)動(dòng)作，大部分基于PDDL的規(guī)劃方法將動(dòng)作分解為與原始操作中存在時(shí)間點(diǎn)一樣多的瞬時(shí)動(dòng)作。盡管可行，但使其適應(yīng)于具有任意數(shù)量時(shí)間點(diǎn)會(huì)導(dǎo)致復(fù)雜度增加，搜索空間膨脹，求解效率無法滿足航天器實(shí)時(shí)性要求。

由于對(duì)時(shí)間屬性表達(dá)能力和規(guī)劃技術(shù)處理能力限制，基于PDDL的時(shí)態(tài)規(guī)劃技術(shù)目前很少能夠在大型航天器任務(wù)規(guī)劃問題中使用。但基于時(shí)間線的規(guī)劃系統(tǒng)在許多空間應(yīng)用程序中得到廣泛應(yīng)用和發(fā)展，其關(guān)鍵在于靈活的基于時(shí)間線的表示形式，對(duì)時(shí)間屬性的表達(dá)能力強(qiáng)，且允許對(duì)基本規(guī)劃范式進(jìn)行擴(kuò)展。擴(kuò)展中最普遍的是可支持資源，由特定的缺陷求解器來處理。最小承諾原則允許更緊湊的搜索空間，在單個(gè)搜索節(jié)點(diǎn)中表示多個(gè)可能的規(guī)劃。盡管基于時(shí)間線規(guī)劃方法得到廣泛應(yīng)用，但仍存在一定缺點(diǎn)需要進(jìn)一步研究。

1)基于時(shí)間線的規(guī)劃器集成領(lǐng)域無關(guān)的搜索控制和啟發(fā)式困難。但可以利用規(guī)劃問題結(jié)構(gòu)，通過拓展部分規(guī)劃解決可見沖突，從而減輕對(duì)啟發(fā)式的需求。部分學(xué)者通過將松弛圖的思想引入到規(guī)劃空間規(guī)劃方法中，實(shí)現(xiàn)對(duì)部分規(guī)劃的評(píng)價(jià)[62]。

2)航天器復(fù)雜系統(tǒng)規(guī)劃模型的建立對(duì)專家經(jīng)驗(yàn)知識(shí)依賴較大，給工程人員增加負(fù)擔(dān)，且直接影響規(guī)劃搜索效率與質(zhì)量。因此，研究人員通過開發(fā)交互式建模軟件或者研究引入領(lǐng)域無關(guān)啟發(fā)式方法對(duì)時(shí)間線規(guī)劃方法進(jìn)行改進(jìn)。

3)缺少像PDDL的標(biāo)準(zhǔn)表達(dá)形式和規(guī)劃方法評(píng)價(jià)標(biāo)準(zhǔn)，導(dǎo)致基于時(shí)間線規(guī)劃方法之間相互對(duì)比和與基于狀態(tài)空間規(guī)劃方法性能比較困難。部分學(xué)者通過開發(fā)模型轉(zhuǎn)換工具、定義基于時(shí)間線規(guī)劃等方法，使其標(biāo)準(zhǔn)化和規(guī)范化。

3.2 航天器時(shí)態(tài)規(guī)劃發(fā)展建議

把時(shí)態(tài)規(guī)劃技術(shù)應(yīng)用到航天領(lǐng)域，需要考慮到航天領(lǐng)域的系統(tǒng)耦合性、資源有限性和時(shí)間約束復(fù)雜性等特殊性質(zhì)。從當(dāng)前的研究進(jìn)展和需要解決的問題來看，建議時(shí)態(tài)規(guī)劃技術(shù)在未來航天領(lǐng)域研究的發(fā)展方向?yàn)椋?/p>

1)模型中時(shí)間表示方法研究

規(guī)劃知識(shí)模型是對(duì)規(guī)劃對(duì)象直接的表示和自主規(guī)劃技術(shù)的基礎(chǔ)，會(huì)影響后續(xù)所采用的規(guī)劃技術(shù)。PDDL形式規(guī)劃語言通過動(dòng)作、條件和效果發(fā)生的時(shí)間表示，對(duì)于時(shí)間重疊或并行表達(dá)能力欠缺，且會(huì)造成規(guī)劃搜索空間爆炸式增長。時(shí)間線表示形式對(duì)時(shí)間的表達(dá)能力強(qiáng)，但弱化了活動(dòng)間因果關(guān)系。因此如何有效結(jié)合兩者優(yōu)點(diǎn)對(duì)時(shí)間特性進(jìn)行合理表示是任務(wù)規(guī)劃建模的關(guān)鍵，如目前開發(fā)的ANML建模語言。

2)時(shí)間約束推理技術(shù)研究

目前任務(wù)規(guī)劃方法均采用時(shí)間約束網(wǎng)絡(luò)或者線性規(guī)劃方法對(duì)時(shí)間約束進(jìn)行處理。以時(shí)間約束網(wǎng)絡(luò)為例，當(dāng)規(guī)劃問題復(fù)雜時(shí)，時(shí)間約束網(wǎng)絡(luò)規(guī)模較大，時(shí)間約束推理所需時(shí)間長。同時(shí)，規(guī)劃過程中活動(dòng)或約束是動(dòng)態(tài)加入，對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)和邊進(jìn)行推理，勢(shì)必造成時(shí)間推理效率低下。因此，需要考慮推理效率和所需計(jì)算空間，對(duì)時(shí)間約束表示和快速推理方法進(jìn)行研究。

3)規(guī)劃過程中活動(dòng)并行性處理方法研究

航天器任務(wù)規(guī)劃問題中活動(dòng)具有必須交錯(cuò)或并行執(zhí)行的特點(diǎn)，比如拍照過程中需要姿態(tài)定向。因此，時(shí)態(tài)規(guī)劃技術(shù)需要能夠處理必須并行活動(dòng)，這也是任務(wù)規(guī)劃技術(shù)對(duì)時(shí)間屬性處理能力最重要的體現(xiàn)?；跁r(shí)間線的任務(wù)規(guī)劃方法因采用時(shí)間區(qū)間表示方法從而可實(shí)現(xiàn)對(duì)并行活動(dòng)的表示和規(guī)劃，而基于動(dòng)作的時(shí)態(tài)規(guī)劃技術(shù)能夠處理并行動(dòng)作的能力仍有待提高，以適應(yīng)對(duì)航天器規(guī)劃問題的求解。

4)不確定時(shí)間下的時(shí)態(tài)規(guī)劃方法研究

受空間環(huán)境復(fù)雜多變等影響，航天器部分活動(dòng)執(zhí)行時(shí)間不完全可控，如衛(wèi)星觀測(cè)時(shí)間窗口受云層影響而不確定。規(guī)劃方法通常產(chǎn)生具有固定時(shí)刻的規(guī)劃序列，其執(zhí)行魯棒性較差，遇到突發(fā)事件時(shí)會(huì)導(dǎo)致重規(guī)劃，從而影響任務(wù)目標(biāo)的準(zhǔn)時(shí)實(shí)現(xiàn)甚至威脅航天器安全運(yùn)行。因此，如何在規(guī)劃過程中提前考慮時(shí)間不確定性，生成具有靈活性的規(guī)劃解是時(shí)態(tài)規(guī)劃技術(shù)在航天領(lǐng)域?qū)嶋H應(yīng)用需要研究的重點(diǎn)。

5)規(guī)劃序列時(shí)長優(yōu)化方法研究

航天器任務(wù)規(guī)劃方法通常以規(guī)劃出有效解為目標(biāo)，然而在任務(wù)完成時(shí)間要求嚴(yán)苛或星上資源非常有限情況下，需要求解最優(yōu)時(shí)長的規(guī)劃序列。目前，基于圖規(guī)劃和可滿足技術(shù)的時(shí)態(tài)規(guī)劃方法具有優(yōu)化規(guī)劃解的基礎(chǔ)，基于時(shí)間線的規(guī)劃方法對(duì)其較少研究。因此，需要結(jié)合航天任務(wù)工程實(shí)施需求進(jìn)一步對(duì)規(guī)劃序列時(shí)長優(yōu)化的必要性進(jìn)行論證和方法深入研究。

6)基于動(dòng)作與時(shí)間線的混合規(guī)劃方法研究

基于動(dòng)作的時(shí)態(tài)規(guī)劃方法能夠處理必須并行性的規(guī)劃器較少，處理任意時(shí)間點(diǎn)的效果和條件能力弱，但啟發(fā)式方法對(duì)規(guī)劃搜索起到良好的引導(dǎo)作用。基于時(shí)間線時(shí)態(tài)規(guī)劃方法時(shí)間能力表達(dá)較強(qiáng)，但弱化了對(duì)因果關(guān)系的表示和推理，同時(shí)缺少對(duì)規(guī)劃方法和規(guī)劃解質(zhì)量的評(píng)價(jià)機(jī)制。因此，對(duì)兩類時(shí)態(tài)規(guī)劃方法的理論分析以及如何利用兩者優(yōu)勢(shì)發(fā)展時(shí)態(tài)規(guī)劃技術(shù)值得未來進(jìn)一步研究。

4 結(jié) 論

自主任務(wù)規(guī)劃技術(shù)是實(shí)現(xiàn)航天器自主運(yùn)行的核心技術(shù)之一，空間環(huán)境動(dòng)態(tài)多變和無法預(yù)知的特點(diǎn)以及航天器系統(tǒng)復(fù)雜性，給自主規(guī)劃技術(shù)帶來了新的挑戰(zhàn)，其中時(shí)間屬性是航天器任務(wù)規(guī)劃中的重要因素。本文闡述了航天器時(shí)態(tài)規(guī)劃方法研究難點(diǎn)，并給出航天器時(shí)態(tài)規(guī)劃技術(shù)定義，從狀態(tài)空間時(shí)態(tài)規(guī)劃和基于時(shí)間線規(guī)劃兩方面對(duì)規(guī)劃知識(shí)建模方法和規(guī)劃技術(shù)進(jìn)行描述，分析當(dāng)前技術(shù)優(yōu)缺點(diǎn)和對(duì)航天器任務(wù)規(guī)劃問題的適用性，并討論了其發(fā)展方向。

實(shí)際航天器任務(wù)規(guī)劃需要綜合考慮動(dòng)作、時(shí)間、資源和數(shù)值參數(shù)等，基于PDDL模式的規(guī)劃方法缺少在以上因素同時(shí)出現(xiàn)時(shí)的理論研究，而基于時(shí)間線的規(guī)劃方法弱化了因果關(guān)系推理，同時(shí)缺少正式標(biāo)準(zhǔn)定義和方法評(píng)價(jià)標(biāo)準(zhǔn)，因此時(shí)態(tài)規(guī)劃技術(shù)在航天器規(guī)劃問題的應(yīng)用仍需要進(jìn)一步進(jìn)行理論研究和對(duì)比評(píng)價(jià)。同時(shí)，時(shí)態(tài)規(guī)劃技術(shù)的實(shí)際應(yīng)用需要輔以規(guī)劃序列執(zhí)行和重規(guī)劃或規(guī)劃修復(fù)等技術(shù)，形成閉環(huán)自主管理系統(tǒng)，進(jìn)而體現(xiàn)自主規(guī)劃技術(shù)的研究?jī)r(jià)值。

目前NASA和ESA分別開發(fā)出具有可拓展性的任務(wù)規(guī)劃框架，并成功進(jìn)行了星載試驗(yàn)或形成地面成熟的任務(wù)規(guī)劃系統(tǒng)，用以支持航天器長期和短期任務(wù)的規(guī)劃與調(diào)度。隨著我國航天任務(wù)不斷增加和深空探測(cè)任務(wù)的不斷推進(jìn)，有必要結(jié)合我國任務(wù)需求對(duì)自主任務(wù)規(guī)劃技術(shù)進(jìn)行更為深入的研究，為我國航天器自主運(yùn)行提供技術(shù)支撐。