李朝玉，徐瑞

(1.北京理工大學(xué) 深空探測技術(shù)研究所，北京 100081；2.飛行器動力學(xué)與控制教育部重點(diǎn)實(shí)驗(yàn)室，北京 100081)

一種基于時標(biāo)狀態(tài)的啟發(fā)式航天器任務(wù)規(guī)劃算法

李朝玉1，2，徐瑞1，2

(1.北京理工大學(xué) 深空探測技術(shù)研究所，北京 100081；2.飛行器動力學(xué)與控制教育部重點(diǎn)實(shí)驗(yàn)室，北京 100081)

深空探測領(lǐng)域?qū)?shí)時性要求較高，在較短時間內(nèi)找到規(guī)劃解是深空探測自主任務(wù)規(guī)劃中的一個要求，運(yùn)用啟發(fā)式規(guī)劃算法是達(dá)到該要求的方法之一。而深空探測自主任務(wù)規(guī)劃的另外一個特點(diǎn)是需要處理持續(xù)動作和數(shù)值信息。針對深空探測任務(wù)特點(diǎn)，采用規(guī)劃領(lǐng)域定義語言PDDL，建立深空探測領(lǐng)域中知識模型，描述操作中遇到的時間與資源約束；隨后應(yīng)用以條件數(shù)為代價的啟發(fā)式搜索方法對深空探測規(guī)劃問題進(jìn)行求解，并將其與TFD規(guī)劃器中以動作時間為代價的上下文增強(qiáng)累加啟發(fā)式搜索方法得到的結(jié)果進(jìn)行對比，得出以條件數(shù)為代價的啟發(fā)式搜索方法在搜索速度方面效果更佳，滿足深空探測自主規(guī)劃任務(wù)實(shí)時性要求。

深空探測；啟發(fā)式；持續(xù)動作；數(shù)值

0 引 言

深空探測領(lǐng)域?qū)?shí)時性要求較高，在較短時間內(nèi)找到規(guī)劃解是深空探測自主任務(wù)規(guī)劃中的一個要求。近些年，規(guī)劃領(lǐng)域蓬勃發(fā)展，規(guī)劃效率不斷提高，有很多具有發(fā)展前景的規(guī)劃方法出現(xiàn)，而啟發(fā)式搜索方法就是其中之一。這種方法的中心思想就是在搜索過程中運(yùn)用啟發(fā)式信息引導(dǎo)搜索向希望的節(jié)點(diǎn)進(jìn)行，直至找到目標(biāo)節(jié)點(diǎn)為止。在深空探測自主任務(wù)規(guī)劃中運(yùn)用啟發(fā)式信息進(jìn)行搜索會減少搜索時間，大大提高產(chǎn)生規(guī)劃解的效率[1]。

深空探測中約束復(fù)雜，任務(wù)執(zhí)行必須精準(zhǔn)，運(yùn)用啟發(fā)式過程中不宜過多地進(jìn)行放松；與此同時，探測器運(yùn)行速度快，有時遇到觀測的現(xiàn)象時需要能夠較快產(chǎn)生規(guī)劃解，因此探測器自主任務(wù)規(guī)劃系統(tǒng)要求具有較高的搜索速度，尋找一種快速高效的啟發(fā)式顯得尤為重要[2]。起初設(shè)計(jì)啟發(fā)式時，對時間和數(shù)值方面沒有考慮，深空探測領(lǐng)域中時間信息和數(shù)值量都是無法避免的，如電量、存儲量等[3]。因此，當(dāng)引進(jìn)持續(xù)動作和數(shù)值量后，必須對啟發(fā)式進(jìn)行改進(jìn)，才能用于深空探測中的時間和數(shù)值規(guī)劃[4-5]。

本文針對深空探測任務(wù)要求規(guī)劃解質(zhì)量高、搜索速度快的特點(diǎn)，在TFD規(guī)劃器中采用的以動作時間為代價的上下文增強(qiáng)累加啟發(fā)式[6]基礎(chǔ)上，對代價計(jì)算方法進(jìn)行改進(jìn)，設(shè)計(jì)了一種基于時標(biāo)狀態(tài)的啟發(fā)式規(guī)劃算法，該算法以條件數(shù)為代價，以達(dá)到對時間和數(shù)值信息的處理和對搜索過程的快速引導(dǎo)。應(yīng)用到深空探測領(lǐng)域，一定程度上能夠提高實(shí)時處理問題的能力。

1 深空探測器自主任務(wù)規(guī)劃模型

用傳統(tǒng)的離散動作表示深空任務(wù)中的動作已經(jīng)無法解決實(shí)際問題，因此需要采用持續(xù)動作，即用一定的值表示動作執(zhí)行時間。此外，還需考慮動作與動作間的并行性，以此可減少執(zhí)行任務(wù)的完成時間，提高效率。

對于深空探測任務(wù)來說，探測器進(jìn)入接近段后，速度非常快，姿態(tài)軌道等的調(diào)整很頻繁，因此對實(shí)時性要求非常高[7]。因此本文以此階段為例，采用規(guī)劃領(lǐng)域定義語言PDDL[8]對其進(jìn)行描述建模，并對其進(jìn)行求解。不僅能表示任務(wù)的持續(xù)時間和約束， 還利于后面規(guī)劃算法對時間進(jìn)行處理。

1.1 領(lǐng)域文件的建立

深空探測器天體探測接近段中，涉及到的動作有轉(zhuǎn)向、校準(zhǔn)相機(jī)、打開相機(jī)、拍照、關(guān)閉相機(jī)、下傳數(shù)據(jù)等活動。下面將對接近段任務(wù)進(jìn)行領(lǐng)域建模。

建模過程中，包括類型、謂詞、函數(shù)以及持續(xù)動作的說明[9]。其中，謂詞指深空探測器中各個對象的屬性，具有一定的取值范圍；函數(shù)則表示動作之間的轉(zhuǎn)換；持續(xù)動作的說明中則包含了動作涉及的參數(shù)，持續(xù)時間，需要滿足的開始條件、持續(xù)條件、結(jié)束條件以及動作產(chǎn)生的效果[10]。在描述過程中，會有數(shù)值量的出現(xiàn)，這些數(shù)值量則表示各個活動所涉及到的數(shù)值變量和資源情況，如存儲器的存儲空間、燃料使用情況、電量儲存量等[11]。

表1為該任務(wù)建模中所涉及的活動及其含義描述。領(lǐng)域文件中對相機(jī)系統(tǒng)、姿態(tài)系統(tǒng)、導(dǎo)航系統(tǒng)、推進(jìn)系統(tǒng)和通信系統(tǒng)進(jìn)行建模，共15個活動，且文件中對每個活動的持續(xù)時間、參數(shù)、開始條件和結(jié)束效果都作了定義。

表1 深空探測器小天體接近段任務(wù)模型的活動及其含義描述

Table 1 Description of activities in mission model of the deep space explorer for the closing phase to a small body

活動名稱含義Cam＿Ready準(zhǔn)備好相機(jī)Cam＿Open打開相機(jī)Cam＿Takephoto相機(jī)拍照Cam＿Close關(guān)閉相機(jī)ATT＿M(jìn)aneuver探測器轉(zhuǎn)向Nav＿prepare準(zhǔn)備導(dǎo)航Nav＿process導(dǎo)航過程Prop＿warmingup推進(jìn)器預(yù)熱Prop＿startup推進(jìn)器啟動Prop＿thrust推進(jìn)器進(jìn)行推進(jìn)Prop＿closing推進(jìn)器關(guān)閉Com＿system＿prepare數(shù)據(jù)傳遞系統(tǒng)準(zhǔn)備Com＿uplink上傳數(shù)據(jù)Com＿downlink下傳數(shù)據(jù)Com＿close數(shù)據(jù)傳遞系統(tǒng)關(guān)閉

1.2 問題文件的建立

問題文件用于描述探測任務(wù)的對象、初始狀態(tài)以及任務(wù)目標(biāo)，也是地面工作者操作探測器的接口。本文所建立的問題模型包括相機(jī)、導(dǎo)航系統(tǒng)、推進(jìn)系統(tǒng)、探測器指向以及探測目標(biāo)。拍照時，相機(jī)需要對準(zhǔn)探測目標(biāo)進(jìn)行拍照。

圖1表示出該探測任務(wù)的初始狀態(tài)。在初始狀態(tài)中，相機(jī)cam1處于閑置關(guān)閉狀態(tài)；剩余電量為800 W，剩余數(shù)據(jù)儲存量為500 MB，推進(jìn)劑剩余500 g；推進(jìn)機(jī)prop1預(yù)熱時間為25 s，推進(jìn)時間為10 s；數(shù)據(jù)傳輸準(zhǔn)備時間需要20 s，數(shù)據(jù)上傳時間需要35 s，下傳時間需要50 s；探測器開始指向?yàn)槌跏挤较騃nitial。此次設(shè)定的科學(xué)觀測任務(wù)目標(biāo)為：利用相機(jī)cam1對小天體asteroid1和恒星star1進(jìn)行拍照。具體描述如圖2所示。

圖1 深空探測器小天體接近段任務(wù)的初始狀態(tài)

Fig.1 Initial states of the deep space explorer in the closing phase to a small body

圖2 深空探測器小天體接近段的任務(wù)目標(biāo)

Fig.2 Description of goals of the deep space explorer

2 基于時標(biāo)狀態(tài)的啟發(fā)式規(guī)劃算法

早期的規(guī)劃方法并不能處理具有連續(xù)動作的規(guī)劃問題，因此啟發(fā)式函數(shù)也只是對瞬間的動作節(jié)點(diǎn)進(jìn)行計(jì)算。然而，深空探測任務(wù)中，動作都具有持續(xù)時間，傳統(tǒng)的啟發(fā)式處理方法已經(jīng)不再適用。隨著規(guī)劃技術(shù)的發(fā)展，產(chǎn)生了可對連續(xù)動作和數(shù)值量進(jìn)行處理計(jì)算的啟發(fā)式，啟發(fā)式搜索方法也得到了相應(yīng)的改進(jìn)，以適應(yīng)現(xiàn)實(shí)問題的需要。本文設(shè)計(jì)一種以條件數(shù)為代價的上下文增強(qiáng)累加啟發(fā)式， 達(dá)到對連讀動作和數(shù)值量處理的目的。

2.1 持續(xù)動作和數(shù)值處理方法

對啟發(fā)式的改進(jìn)涉及到兩個方面：將持續(xù)動作轉(zhuǎn)換為操作，使之可以用來進(jìn)行啟發(fā)式的計(jì)算；對規(guī)劃任務(wù)中的數(shù)值部分進(jìn)行處理。在這里采用的方法是引入瞬時動作(instant actions)處理持續(xù)動作部分，估計(jì)改變比較變量值的代價處理數(shù)值部分[12]。

1)瞬時動作

為了處理持續(xù)動作，需要引入瞬時動作的概念來估計(jì)時態(tài)任務(wù)。瞬時動作又可分為四部分：壓縮動作、開始動作、等待動作、由邏輯公理導(dǎo)出的瞬時動作。

(1)壓縮動作

主要是通過對原時態(tài)規(guī)劃任務(wù)中的條件與效果進(jìn)行簡化處理。壓縮條件三元組， 一個瞬時動作的壓縮邏輯效果表示為

其中：o為動作；v和v′為變量；w和w′為變量可取值；z為部分狀態(tài)。

壓縮的數(shù)值效果表示為：o:z→v°v′(°為符號+=，-=，*=，/=，:=)。

每個瞬時動作都分配給一個代價cost(o)，這個代價可能是真實(shí)的值或者數(shù)值變量。在不同的代價計(jì)算公式中，cost(o)計(jì)算的方法也是不同的。

壓縮動作圖例如圖3所示。

圖3 壓縮動作圖例Fig.3 Compressive actions

壓縮動作轉(zhuǎn)換后為：

條件：cond={a，b}； 效果：eff={c，d，d}

(2)開始動作

將持續(xù)動作進(jìn)行壓縮，導(dǎo)致忽略了持續(xù)動作執(zhí)行過程中到達(dá)的中間狀態(tài)的啟發(fā)式值，因此引入開始動作。它包含持續(xù)動作的開始效果，以及壓縮動作所包含的所有條件，即開始、持續(xù)和結(jié)束條件。與壓縮動作的唯一不同是沒有結(jié)束效果。開始動作代價計(jì)算：原始持續(xù)操作的持續(xù)時間。

(3)等待動作

當(dāng)啟發(fā)式計(jì)算需要用到結(jié)束效果時，就用壓縮動作，因?yàn)殚_始動作沒有結(jié)束效果。而當(dāng)持續(xù)動作已經(jīng)在時標(biāo)狀態(tài)S下運(yùn)行了，則認(rèn)為動作的條件已經(jīng)得到了滿足，此時引入等待動作。每個調(diào)度效果<Δt，c?，c┤，e>中增加一個等待動作o，其中效果為effect→e，代價根據(jù)采用的方法計(jì)算。圖4為等待動作圖例。

圖4 等待動作圖例Fig.4 Waiting actions

等待動作轉(zhuǎn)換為：

條件：cond=?； 效果：eff={goal}

(4)由邏輯公理導(dǎo)出的瞬時動作

最后一組瞬時動作是從邏輯公理導(dǎo)出的，例如公理z→v=w可得到瞬時動作o，其代價cost(o)=0，效果為{v=w′，z→v=w|w′∈Dv{w}}。

2)數(shù)值信息處理

數(shù)值方面是指有些變量需要用數(shù)值表示，例如深空探測器的電量是有一定值的，如果按以前沒有數(shù)值量時的情況，只能用0和1表示沒電還是有電，這樣就無法表示實(shí)際用電量。

在變量處理過程中，數(shù)值量沒有出現(xiàn)在條件或者目標(biāo)當(dāng)中。因此通過估計(jì)改變比較變量需要的代價是一種處理數(shù)值量的有效方法。

考慮未滿足條件v=w，其中v∈Vc是比較變量，w∈{true，false}，v=v′??0是相關(guān)的比較公理；數(shù)值變量v′代表數(shù)值流集合F(v)中的算術(shù)表達(dá)式，集合F(v)是輸入度為0的變量的集合，也稱為v′的祖先。來自于瞬時動作的規(guī)則集合influencing(v)={o:z→v1°v2|v1∈F(v)}作用在變量上，接下來，就從influencing(v)中選擇對原子有積極效應(yīng)的規(guī)則。

為了表明比較變量的變化情況，需要定義新的符號，如式(1)所示

(1)

在擴(kuò)展?fàn)顟B(tài)s中，如果式(1)成立，influencing(v)中的規(guī)則o:z→v1°v2是可以改變變量v的值w(v=v′??0是與之相關(guān)的比較公理)。

(2)

其中，s[v1°v2]是與s相似的狀態(tài)，但是其v1°v2使得變量值更新和一個子序列的公理更新。

2.2 以條件數(shù)為代價的上下文增強(qiáng)累加啟發(fā)式

由于TFD規(guī)劃器中以動作時間為代價的上下文增強(qiáng)累加啟發(fā)式計(jì)算較復(fù)雜，因此對代價計(jì)算方法進(jìn)行簡單化，盡量能夠減小搜索時間。由代價值得到啟發(fā)式值h(n)，h(n)值的好壞直接影響到下個節(jié)點(diǎn)的選取，因此找到一種計(jì)算快速、易于理解的啟發(fā)式函數(shù)算法對整個搜索過程有著極為重要的作用[2]。

在對啟發(fā)式函數(shù)進(jìn)行介紹前，需要對一些符號做出說明[12]。s表示狀態(tài)，v=w為原子(以下用x表示)，s[v=w]表示一種狀態(tài)，在這種狀態(tài)下，除了變量v的值以外，其他與s都相同；相似地，s[s′]也為一種狀態(tài)，此狀態(tài)下，某些變量值與狀態(tài)s′下相同，其他變量的值則與狀態(tài)s下相同。var(x)指原子x中的變量。

一個操作是效果的集合，形式為v=w′，z→v=w，其中z是一個部分狀態(tài)，v是一個變量，w′和w屬于變量值域Dv，對應(yīng)于v不同狀態(tài)下的值。這一效果意味著在與部分狀態(tài)z相符合的當(dāng)前狀態(tài)s下，變量v的值為w′，作用操作o后，生成繼承狀態(tài)s′，此狀態(tài)下變量v的值變?yōu)閣。為了將此意義表示清楚，通常寫作以下形式：o:v=w′，z→v=w。

啟發(fā)式h(S)定義如下

(3)

其中：xs是狀態(tài)s下的變量var(x)對應(yīng)的原子；h(x|xs)是指變量var(x)由狀態(tài)s下的值改變到狀態(tài)s★下的值所用代價。

對于上面介紹的規(guī)則o:v=w′，z→v=w，條件v=w′需要先實(shí)現(xiàn)，然后條件z在得到的狀態(tài)s下進(jìn)行評估。拓展式(3)得到

(4)

以條件數(shù)為代價的啟發(fā)式計(jì)算仍以瞬時動作為基礎(chǔ)。對于壓縮動作和開始動作，代價cost=|conditions|，即代價為壓縮動作后的前提條件數(shù)，例如對于圖3來說，cost=2。對于等待動作，cost=0，因?yàn)閯幼饕呀?jīng)在執(zhí)行，說明該動作的條件數(shù)已經(jīng)得到滿足；從邏輯公理導(dǎo)出的瞬時動作，例如公理z→v=w可得到瞬時動作o，其代價cost(o)=0，效果為{v=w′，z→v=w|w′∈Dv{w}}。

以條件數(shù)為代價，式(4)進(jìn)行拓展，如式(5)所示。

(5)

2.3 規(guī)劃算法

在整個搜索過程中，采用的主要搜索算法為A*算法。A*算法是一種靜態(tài)網(wǎng)絡(luò)中求解最短路徑的最有效方法。啟發(fā)式則是用來引導(dǎo)搜索算法的，并在父節(jié)點(diǎn)的確定過程中，對各個動作間進(jìn)行時間約束的判斷，即判斷動作間是否滿足先后順序條件，不滿足時間約束的節(jié)點(diǎn)即被移除掉，選擇下一個節(jié)點(diǎn)，使其搜索效率更高。

在本文的搜索算法中，使用的啟發(fā)式為以條件數(shù)為代價的上下文增強(qiáng)累加啟發(fā)式。搜索過程如圖5所示。

此算法將創(chuàng)建兩個表，名稱分別為OpenList和CloseList。OpenList存放已經(jīng)生成而未被考察的節(jié)點(diǎn)，CloseList則存放記錄已經(jīng)訪問過的節(jié)點(diǎn)。首先將初始節(jié)點(diǎn)放入OpenList中，因?yàn)樵诘谝徊街校瑳]有別的節(jié)點(diǎn)可供選擇，所以將初始節(jié)點(diǎn)直接從OpenList移除，放入到CloseList中，并將初始節(jié)點(diǎn)的所有子節(jié)點(diǎn)放入到OpenList中。然后根據(jù)啟發(fā)式信息對初始節(jié)點(diǎn)的子節(jié)點(diǎn)進(jìn)行排序，選擇優(yōu)先級最高且滿足時間約束的節(jié)點(diǎn)放入到CloseList。再次將此節(jié)點(diǎn)的子節(jié)點(diǎn)(OpenList中沒有并且也不是CloseList中的節(jié)點(diǎn))放入到OpenList中，并對OpenList中節(jié)點(diǎn)重新計(jì)算啟發(fā)式，然后再選擇優(yōu)先級最高的節(jié)點(diǎn)重復(fù)處理[3]。

在搜索過程中，有兩個特殊量值得注意。首先，引入一個時間小量 ，用來滿足“無移動目標(biāo)”規(guī)則，當(dāng)一個動作加入時標(biāo)狀態(tài)后就會引入此小量。其次，引入一個特殊動作“l(fā)et_time_pass”，此動作可應(yīng)用在任何一個狀態(tài)下，此動作僅讓時間流逝，而不會產(chǎn)生任何效果。

圖5 基于時間約束的啟發(fā)式規(guī)劃算法

Fig.5 Heuristic algorithm based on time constraints

3 仿真分析

在規(guī)劃系統(tǒng)中，搜索算法的選取對結(jié)果的產(chǎn)生有著重要的作用，當(dāng)然在利用啟發(fā)式的搜索中，啟發(fā)式信息的好壞對得到的規(guī)劃質(zhì)量和搜索速度也至關(guān)重要。其中一個發(fā)展方向則是針對某個領(lǐng)域設(shè)計(jì)出具有針對性的啟發(fā)式，在此領(lǐng)域能夠取得理想的效果即可。因?yàn)楸疚氖轻槍ι羁仗綔y器設(shè)計(jì)的啟發(fā)式，因此就需要分析這種啟發(fā)式在深空探測問題中所取得的結(jié)果和效果。

采用第1節(jié)所建立的深空探測器小天體接近段的任務(wù)模型，利用基于時標(biāo)狀態(tài)的規(guī)劃器進(jìn)行規(guī)劃的搜索求解，獲得了任務(wù)的規(guī)劃結(jié)果。如圖6所示。

從得到的規(guī)劃方案可看出，時間以0.000 1 s的單位向前推進(jìn)，以滿足“無移動目標(biāo)規(guī)則”(no moving target rule)。對于第1節(jié)建立的探測器任務(wù)，規(guī)劃器只需要40.000 3 s即可實(shí)現(xiàn)目標(biāo)。實(shí)現(xiàn)目標(biāo)所需要的步數(shù)根據(jù)初始狀態(tài)和目標(biāo)狀態(tài)決定的。因?yàn)椴捎昧藭r標(biāo)狀態(tài)及時間推進(jìn)小量∈，準(zhǔn)備相機(jī)和調(diào)整探測器指向可同時進(jìn)行，所以節(jié)省整個規(guī)劃任務(wù)解的時間，提高效率。

Time： Action：ActionDuration：000000000：(cam＿readycam1)[1000000000]000000000：(att＿maneuveratt1initialasteroid1)[1500000000]10．00000000：(cam＿opencam1)[100000000]15．00000000：(cam＿takephotocam1asteroid1)[500000000]20．00000000：(att＿maneuveratt1asteroid1star1)[1500000000]35．00000000：(cam＿takephotocam1star1)[500000000]Time： Action：ActionDuration：000000000：(cam＿readycam1)[1000000000]000000000：(att＿maneuveratt1initialasteroid1)[1500000000]10．00010000：(cam＿opencam1)[100000000]15．00010000：(cam＿takephotocam1asteroid1)[500000000]20．00020000：(att＿maneuveratt1asteroid1star1)[1500000000]35．00030000：(cam＿takephotocam1star1)[500000000]Solutionwithoriginalmakespan40found(ignoringno?moving?targets?rule)．Solutionwasepsilonizedandrescheduledtoamakespanof400003．Planlength：6step(s)．Makespan：400003

圖6 深空探測器小天體接近段任務(wù)的規(guī)劃方案

Fig.6 Plans for missions in the closing phase to a small body

按照第1節(jié)的建模方法建立多個深空探測領(lǐng)域問題模型。然后分別運(yùn)用以動作時間為代價的和以條件數(shù)為代價的啟發(fā)式搜索方法求解，記錄搜索時間和規(guī)劃解的完成時間，將兩種結(jié)果對比，進(jìn)而分析兩種啟發(fā)式信息的效果。用曲線圖7表示，形象地比較兩種啟發(fā)式在搜索時間方面的優(yōu)劣。

圖7 啟發(fā)式搜索時間曲線比較圖Fig.7 Comparison of heuristic 1 and heuristic 2

在圖7中，啟發(fā)式1為使用以動作時間為代價的上下文增強(qiáng)累加啟發(fā)式(TFD中)得到的搜索結(jié)果，啟發(fā)式2為使用以條件數(shù)為代價的啟發(fā)式搜索方法得到的結(jié)果。橫坐標(biāo)是問題號數(shù)，問題號數(shù)是以問題復(fù)雜程度由簡單到復(fù)雜排列，而問題復(fù)雜程度的判定是以領(lǐng)域描述復(fù)雜度及問題難易度為標(biāo)準(zhǔn)。以問題搜索時間為縱坐標(biāo)，單位為秒(s)，單位長度為0.5 s，因此同一個橫坐標(biāo)下，曲線在下方的啟發(fā)式方法搜索時間短，效果好。由圖可知，隨著問題復(fù)雜度的增加，問題搜索時間也增加；在兩種啟發(fā)式結(jié)果比較中，起初區(qū)別并不明顯，而隨著問題復(fù)雜度的增加，差別逐漸拉開，以條件數(shù)為代價的啟發(fā)式搜索方法顯示出優(yōu)勢。

從上述實(shí)驗(yàn)結(jié)果可知，對于深空探測領(lǐng)域問題，應(yīng)用以條件數(shù)為代價的啟發(fā)式搜索算法仍能得到規(guī)劃結(jié)果，并且搜索時間仍然比較理想。當(dāng)兩種啟發(fā)式得到的規(guī)劃解質(zhì)量相同時，在搜索時間方面，以條件數(shù)為代價的啟發(fā)式搜索方法略勝一籌，適合實(shí)時性要求高的深空探測器。

4 結(jié) 論

本文針對深空探測任務(wù)特點(diǎn)，采用規(guī)劃領(lǐng)域定義語言PDDL，建立深空探測領(lǐng)域中多個問題模型，并對模型語句及定義方法舉例說明，展示操作中遇到的時間與資源約束。隨后應(yīng)用以條件數(shù)為代價的啟發(fā)式搜索方法對深空探測模型求解，并將其與以動作時間為代價的上下文增強(qiáng)累加啟發(fā)式搜索方法得到的結(jié)果對比，得出以條件數(shù)為代價的啟發(fā)式搜索方法在搜索速度方面略勝一籌，滿足深空探測自主規(guī)劃任務(wù)實(shí)時性要求。

[1] Bonet B， Geffner H. Planning as heuristic search[J]. Artificial Intelligence， 2001，129:5-33．

[2] Edelkamp S， Schr?dl S. Heuristic search: theory and application [M]. United States of America: Margan Kaufmann， 2011:1-427．

[3] Cushing W， Kambhampati S， Mausam，et al. When is temporal planning really temporal？ [C]∥The International Joint Conference on Artificial Intelligence. Hyderabad， India：[s.n.]， 2007.

[4] Haslum P， Geffner H. Heuristic planning with time and resources[C]∥Proceedings of the Sixth European Conference on Planning. Toledo， Spain:[s.n.]， 2001.

[5] Minh B D， Kambhampati S. Sapa: a multi-objective metric temporal planner[J]. Journal of Artificial Intelligence Research， 2003，20:155-194．

[6] Helmert M， Geffner H. Unifying the causal graph and additive heuristics[C]∥Proceeding of the 18th International Conference on Automated Planning and Scheduling(ICAPS). Sydney， Australia: [s.n.], 2008.

[7] 彭婷.基于修復(fù)策略的深空探測器自主任務(wù)規(guī)劃方法研究[D].北京:北京理工大學(xué)，2012.[Peng T. Autonomous mission planning method of deep space explorer based on repair planning strategy[D]. Beijing∶Beijing Institute of Technology， 2012.]

[8] Fox M， Long D. PDDL2.1: an extension to PDDL for expressing temporal planning domains[J]. Journal of Artificial intelligence research， 2003，20:61-124．

[9] Smith B， Sherwood R， Govindjee A， et al. Representing spacecraft mission planning knowledge in ASPEN[C]∥Artificial Intelligence Planning Systems Workshop on Knowledge Acquisition. Pittsburgh: [s.n.]， 1998.

[10] 饒東寧，蔣志華，姜云飛.規(guī)劃領(lǐng)域定義語言的演進(jìn)綜述[J].計(jì)算機(jī)工程與應(yīng)用，2010，46(22):23-25.[Rao D N， Jiang Z H， Jiang Y F. Review on evolution of planning domains definition language[J]. Computer Engineering and Applications， 2010，46(22):23-25.]

[11] Helmert M. The fast downward planning system[J]. Journal if Artificial Intelligence Research， 2006(26):191-246．

[12] Eyerich P， Mattmüller R， R?ger C. Using the context-enhanced additive heuristic for temporal and numeric planning[C]∥Proceeding of the 19th International Conference on Automated Planning and Scheduling (ICAPS). Thessaloniki， Greece: [s.n.], 2009. 作者簡介： 李朝玉(1990—)，女，博士，主要研究方向：深空探測器自主任務(wù)規(guī)劃。 通訊地址：北京市海淀區(qū)中關(guān)村南大街5號院北京理工大學(xué)宇航學(xué)院(100081) 電話：(010)68918910 E-mail:handylzy@163.com

[責(zé)任編輯：高莎]

Time Stamped States based Heuristic Algorithm for Spacecraft Mission Planning

LI Zhaoyu1，2， XU Rui1，2

(1.Institute of Deep Space Exploration Technology， Beijing Institute of Technology， Beijing 100081， China;2.Key Laboratory of Dynamics and Control of Flight Vehicle， Ministry of Education， Beijing 100081， China)

For real time in deep space exploration， it is a requirement of autonomous mission planning for the explorer to find a plan as soon as possible. A kind of method is to use heuristic algorithm. At the same time， durative actions and numeric information have to be processed. According to these characteristics， this paper adapts planning domain definition language (PDDL) to establish knowledge models and describe time and resource constraints. Then the heuristic algorithm based on condition number is proposed to solve planning problems of deep space exploration. Finally， we compare this heuristic with context-enhanced additive heuristic based on action time in TFD (Temporal Fast Downward) planner. The result of the experiment shows that the heuristic algorithm we proposed is better to solve the planning problems in deep space from the point of view of real time．

deep space exploration; heuristic; durative actions; numeric

2014-12-20

2015-02-10

國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(973計(jì)劃)(2012CB720000)；民用航天項(xiàng)目

V44

A

2095-7777(2015)01-0020-07

10.15982/j.issn.2095-7777.2015.01.003