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

李朝玉，徐瑞

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

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

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

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

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

活動(dòng)名稱(chēng)含義Cam＿Ready準(zhǔn)備好相機(jī)Cam＿Open打開(kāi)相機(jī)Cam＿Takephoto相機(jī)拍照Cam＿Close關(guān)閉相機(jī)ATT＿M(jìn)aneuver探測(cè)器轉(zhuǎn)向Nav＿prepare準(zhǔn)備導(dǎo)航Nav＿process導(dǎo)航過(guò)程Prop＿warmingup推進(jìn)器預(yù)熱Prop＿startup推進(jìn)器啟動(dòng)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èn)題文件的建立

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

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

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

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

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

Fig.2 Description of goals of the deep space explorer

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

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

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

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

1)瞬時(shí)動(dòng)作

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

(1)壓縮動(dòng)作

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

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

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

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

壓縮動(dòng)作圖例如圖3所示。

圖3 壓縮動(dòng)作圖例Fig.3 Compressive actions

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

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

(2)開(kāi)始動(dòng)作

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

(3)等待動(dòng)作

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

圖4 等待動(dòng)作圖例Fig.4 Waiting actions

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

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

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

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

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

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

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

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

為了表明比較變量的變化情況，需要定義新的符號(hào)，如式(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使得變量值更新和一個(gè)子序列的公理更新。

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

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

在對(duì)啟發(fā)式函數(shù)進(jìn)行介紹前，需要對(duì)一些符號(hào)做出說(shuō)明[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中的變量。

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

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

(3)

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

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

(4)

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

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

(5)

2.3 規(guī)劃算法

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

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

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

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

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

Fig.5 Heuristic algorithm based on time constraints

3 仿真分析

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

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

從得到的規(guī)劃方案可看出，時(shí)間以0.000 1 s的單位向前推進(jìn)，以滿(mǎn)足“無(wú)移動(dòng)目標(biāo)規(guī)則”(no moving target rule)。對(duì)于第1節(jié)建立的探測(cè)器任務(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(shí)標(biāo)狀態(tài)及時(shí)間推進(jìn)小量∈，準(zhǔn)備相機(jī)和調(diào)整探測(cè)器指向可同時(shí)進(jìn)行，所以節(jié)省整個(gè)規(guī)劃任務(wù)解的時(shí)間，提高效率。

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 深空探測(cè)器小天體接近段任務(wù)的規(guī)劃方案

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

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

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

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

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

4 結(jié) 論

本文針對(duì)深空探測(cè)任務(wù)特點(diǎn)，采用規(guī)劃領(lǐng)域定義語(yǔ)言PDDL，建立深空探測(cè)領(lǐng)域中多個(gè)問(wèn)題模型，并對(duì)模型語(yǔ)句及定義方法舉例說(shuō)明，展示操作中遇到的時(shí)間與資源約束。隨后應(yīng)用以條件數(shù)為代價(jià)的啟發(fā)式搜索方法對(duì)深空探測(cè)模型求解，并將其與以動(dòng)作時(shí)間為代價(jià)的上下文增強(qiáng)累加啟發(fā)式搜索方法得到的結(jié)果對(duì)比，得出以條件數(shù)為代價(jià)的啟發(fā)式搜索方法在搜索速度方面略勝一籌，滿(mǎn)足深空探測(cè)自主規(guī)劃任務(wù)實(shí)時(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ù)策略的深空探測(cè)器自主任務(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)域定義語(yǔ)言的演進(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. 作者簡(jiǎn)介： 李朝玉(1990—)，女，博士，主要研究方向：深空探測(cè)器自主任務(wù)規(guī)劃。 通訊地址：北京市海淀區(qū)中關(guān)村南大街5號(hào)院北京理工大學(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

國(guó)家重點(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