高 薇 蔡敦波

1.北京航空航天大學(xué)宇航學(xué)院，北京100083 2.北京航天飛行控制中心, 北京 100094 3.武漢工程大學(xué)智能機(jī)器人湖北省重點(diǎn)實(shí)驗(yàn)室，武漢 430205

面向月面遙操作任務(wù)規(guī)劃系統(tǒng)的搜索剪枝策略研究*

高 薇1,2蔡敦波3

1.北京航空航天大學(xué)宇航學(xué)院，北京100083 2.北京航天飛行控制中心, 北京 100094 3.武漢工程大學(xué)智能機(jī)器人湖北省重點(diǎn)實(shí)驗(yàn)室，武漢 430205

針對(duì)月面巡視器任務(wù)規(guī)劃涉及資源變量的特點(diǎn)，從理論上分析了經(jīng)典的“有利動(dòng)作”剪枝策略的不足,提出了一種適用于時(shí)態(tài)規(guī)劃模型的“資源分析增強(qiáng)型有利動(dòng)作”剪枝策略。此剪枝策略通過分析“資源變量”與動(dòng)作效果的關(guān)系,計(jì)算出被“有利動(dòng)作”策略忽視的動(dòng)作,能在裁剪問題空間的同時(shí)，提高搜索算法的求解能力。試驗(yàn)結(jié)果表明了本文剪枝策略的有效性。

月面遙操作；任務(wù)規(guī)劃；剪枝策略

嫦娥三號(hào)任務(wù)取得了中國首次在月球上實(shí)施巡視器軟著陸和巡視勘察的成功[1]?！坝裢锰?hào)”巡視器與著陸器脫離后，在月面前進(jìn)實(shí)施科學(xué)探測任務(wù)，每項(xiàng)探測任務(wù)均在地面“遠(yuǎn)程遙操作”的控制方式下完成[2]。地面站對(duì)綜合巡視器的各項(xiàng)數(shù)據(jù)進(jìn)行邏輯抽象，構(gòu)建“時(shí)態(tài)規(guī)劃問題”(Temporal Planning Problem)，調(diào)用專門設(shè)計(jì)的“自動(dòng)規(guī)劃系統(tǒng)”進(jìn)行求解，輸出規(guī)劃方案，上傳至巡視器[3]。這種自動(dòng)地進(jìn)行任務(wù)規(guī)劃的方法相對(duì)于以往人工編制規(guī)劃的方法在任務(wù)完成效率上具有顯著優(yōu)勢。

然而，時(shí)態(tài)規(guī)劃的計(jì)算復(fù)雜度一般為EXPSPACE-complete，僅在某些特殊情況下屬于難度略低的PSPACE-complete[4]。為設(shè)計(jì)有效的時(shí)態(tài)規(guī)劃算法，學(xué)界主要從“搜索算法”和“剪枝策略”2個(gè)方向開展研究。在搜索算法方向上，Hoffmann等提出了“增強(qiáng)爬山算法”[5]，Helmert等提出了結(jié)合“多優(yōu)先隊(duì)列”的貪婪最好優(yōu)先搜索算法[6]。這些算法與設(shè)計(jì)良好的啟發(fā)函數(shù)結(jié)合，將規(guī)劃算法的能力提高到了新的水平[7]。在剪枝策略上，Hoffmann等為經(jīng)典規(guī)劃模型STRIPS設(shè)計(jì)的“有利動(dòng)作”(Helpful Actions，HA)策略[5]，以及Helmert等提出的“有利轉(zhuǎn)移”策略[6]在自動(dòng)規(guī)劃領(lǐng)域最先出現(xiàn)，并一直具有重要影響，至今仍是國際先進(jìn)的規(guī)劃算法的關(guān)鍵技術(shù)[8-10]。

針對(duì)“玉兔號(hào)”月面巡視器控制任務(wù)的新特點(diǎn)，地面控制中心將以往的人工編制工作計(jì)劃的經(jīng)驗(yàn)與人工智能領(lǐng)域的自動(dòng)規(guī)劃技術(shù)結(jié)合，設(shè)計(jì)了具有自動(dòng)化任務(wù)建模和任務(wù)規(guī)劃能力的任務(wù)規(guī)劃系統(tǒng)。采用自動(dòng)規(guī)劃領(lǐng)域較成熟的PDDL語言(Planning Domain Definition Language)[3-4]進(jìn)行了任務(wù)建模和基于“狀態(tài)空間搜索”的規(guī)劃求解。在進(jìn)行規(guī)劃解搜索的過程中，因?yàn)闀r(shí)態(tài)規(guī)劃的計(jì)算復(fù)雜度是EXPSPACE-complete，對(duì)應(yīng)的問題空間規(guī)模較大，所以為了使搜索算法專注于問題空間中含有目標(biāo)狀態(tài)的部分，需要有效的剪枝策略。針對(duì)時(shí)態(tài)規(guī)劃模型，本文擴(kuò)展了Hoffmann等為經(jīng)典規(guī)劃模型STRIPS設(shè)計(jì)的剪枝策略HA，分析了HA在時(shí)態(tài)規(guī)劃模型上的不適用性，提出了一種改進(jìn)的剪枝策略“資源分析增強(qiáng)型有利動(dòng)作”(Resource Analysis Enhanced Helpful Actions，RAEHA)。在規(guī)劃系統(tǒng)Sapa[11]上實(shí)現(xiàn)了RAEHA，通過實(shí)驗(yàn)驗(yàn)證了RAEHA的有效性。

1 基本概念

1.1 月面巡視器任務(wù)規(guī)劃與時(shí)態(tài)規(guī)劃

月面巡視器任務(wù)規(guī)劃是在給定初始條件(包括月表環(huán)境條件和巡視器自身狀態(tài))、操作約束集以及目標(biāo)集合(包括目標(biāo)位置、到達(dá)目標(biāo)位置時(shí)的巡視器狀態(tài)及時(shí)間等)的前提下，事先規(guī)劃出巡視器的月面行使路線，安排在該路線上的行為(動(dòng)作)序列(如充電、拍照等)。該規(guī)劃使月面巡視器能按要求到達(dá)目標(biāo)狀態(tài)，且行進(jìn)過程滿足相關(guān)的操作約束。巡視器任務(wù)規(guī)劃問題被抽象為“時(shí)態(tài)規(guī)劃問題”。

定義1 時(shí)態(tài)規(guī)劃問題(Temporal Planning, TP)表示為∏=(V,A,I,G,TL,δ)，其中：

1)V由2個(gè)不相交的有限變量集組成：VL∪VM，變量的取值隨時(shí)間而變化。VL是(邏輯)命題變量集，l∈VL的值域?yàn)镈om(l)={T,F}；VM是數(shù)值變量集，m∈VM有值域Dom(m)?R；

2)A是動(dòng)作集：動(dòng)作a∈A具有形式〈da,Ca,Ea〉，da表示動(dòng)作的持續(xù)時(shí)間；Ca是a的執(zhí)行條件集合(簡稱：條件集)，描述在動(dòng)作執(zhí)行過程中必須成立的條件；Ea是a的執(zhí)行效果集合(簡稱：效果集)，包含動(dòng)作a在開始執(zhí)行時(shí)刻產(chǎn)生的效果和結(jié)束時(shí)刻產(chǎn)生的效果。對(duì)于條件c∈Ca，如果它約束邏輯變量，則具有形式〈(sc,ec)v=r〉，r∈Dom(v)，sc和ec分別為條件“v=r”應(yīng)成立的“開始時(shí)刻”和“結(jié)束時(shí)刻”；如果它約束數(shù)值變量，則有形式〈(sc,ec〉voxgt;，o∈{gt;, ≥ , lt;, ≤, =}是比較算符，x是由數(shù)值變量和常量組成的數(shù)學(xué)表達(dá)式。對(duì)于效果f∈Ea，如果它影響邏輯變量，則具有形式〈[t]v←r〉；如果影響數(shù)值變量，則有形式〈[t]vo′x〉，o′∈{=,+=, -=, *=, /=}；

3)I是規(guī)劃任務(wù)的初始狀態(tài)，它為l∈VL賦予真值“T”或“F”，為m∈VM賦予r∈Dom(m)；

4)G是目標(biāo)集，其中每個(gè)目標(biāo)命題具有形式〈v=r〉，其中v∈V，這些目標(biāo)在規(guī)劃方案執(zhí)行后必須成立；

5)TL是“定時(shí)觸發(fā)文字”的有限集，其中每個(gè)(命題)文字的形式為〈[t]v=r〉，表示變量v∈V在時(shí)刻t的取值更新為r；

6)δ:A→R是動(dòng)作的代價(jià)函數(shù)，表示執(zhí)行a需要付出代價(jià)，δ(a)lt;0表示執(zhí)行a獲得收益。

對(duì)動(dòng)作的時(shí)間語義進(jìn)一步說明如下。將動(dòng)作a的開始執(zhí)行時(shí)刻和結(jié)束時(shí)刻分別記為sa和ea。對(duì)于動(dòng)作執(zhí)行條件c∈Ca，如果sc=ec=sa,則要求條件c在a的開始時(shí)刻成立，稱此類條件為“開始條件”；如果sc=ec=ea,則要求c在a的結(jié)束時(shí)刻成立，稱此類條件為“結(jié)束條件”；如果sc=sa,ec=ea,則要求c在開區(qū)間(sa,ea)上成立，稱此類條件為“持續(xù)條件”。對(duì)于動(dòng)作a的效果〈[t]v←r〉，如果t=sa,則該效果在動(dòng)作的開始時(shí)刻發(fā)生，稱此類效果為“開始效果”；如果t=ea,則該效果在動(dòng)作的結(jié)束時(shí)刻發(fā)生，稱此類效果為“結(jié)束效果”。

TP模型中刻畫巡視其所處的外部環(huán)境變化所使用的技術(shù)為“定時(shí)觸發(fā)文字集”(Timed Initial Literals)，即TL集合反映了邏輯變量隨外部時(shí)間的變化信息。

給定TP問題實(shí)例，它的狀態(tài)s由V中變量的賦值組成。用s(v)表示s對(duì)變量v的賦值。狀態(tài)不一定為全部變量給出賦值：僅為部分變量賦值的狀態(tài)稱為“部分狀態(tài)”(Partial State)，為所有變量賦值的狀態(tài)稱為“完全狀態(tài)”(Full State)。

定義2 (動(dòng)作在狀態(tài)上的可執(zhí)行)在狀態(tài)s上，如果動(dòng)作a的“開始條件”在時(shí)刻sa成立、“結(jié)束條件”在時(shí)刻ea成立及“持續(xù)條件”在開區(qū)間(sa,ea)上成立，則稱a在s上可執(zhí)行，記為applicable(a,s)。同時(shí)，s上所有可執(zhí)行的動(dòng)作記為app_actions(s)={a|a∈A,applicable(a,s)}。

用π=(〈t(a1),a1,da1〉,…, 〈t(am),am,dam〉)表示動(dòng)作序列，其中變量ai表示在第i步執(zhí)行的動(dòng)作，t(ai)表示ai的計(jì)劃執(zhí)行時(shí)刻。

定義3 (有效動(dòng)作序列)對(duì)于狀態(tài)s，如果π中的動(dòng)作可依次執(zhí)行，則稱π為s上的“有效動(dòng)作序列”。

定義4 如果π為初始狀態(tài)I上的有效動(dòng)作序列，并且執(zhí)行am后的狀態(tài)滿足目標(biāo)集G的全部目標(biāo)，則稱π為TP問題∏ = (V,A,I,G,TL,EP,δ)的“規(guī)劃”(Plan)，也稱為“規(guī)劃解”或“規(guī)劃方案”。

通常一個(gè)TP問題的規(guī)劃解不止一個(gè)，記規(guī)劃解的集合為Solutions(∏)。

下面給出月面巡視器任務(wù)規(guī)劃問題的一個(gè)簡化實(shí)例，以及如何采用TP模型來建模本實(shí)例。假定月面上有2個(gè)停泊點(diǎn)：A和B，巡視器當(dāng)前位于A，其任務(wù)目標(biāo)是在B處完成探測工作。巡視器當(dāng)前能量為80，在相對(duì)時(shí)刻30開始處于太陽光照區(qū)域。任務(wù)約束為：在執(zhí)行探測動(dòng)作之前，巡視器的能量應(yīng)gt;50，在探測動(dòng)作的執(zhí)行過程中應(yīng)一直處于太陽光照區(qū)域。從A～B的移動(dòng)持續(xù)時(shí)間為10、能量消耗為30且要求當(dāng)前能量gt;40。在B處進(jìn)行探測動(dòng)作的持續(xù)時(shí)間為15、能量消耗為20且要求當(dāng)前能量大約30。這個(gè)規(guī)劃實(shí)例在時(shí)間跨度指標(biāo)上的最優(yōu)解是：在時(shí)刻0執(zhí)行從A～B的“移動(dòng)動(dòng)作”，在時(shí)刻30執(zhí)行“探測動(dòng)作”。

運(yùn)用定義1的TP模型，能對(duì)上述實(shí)例進(jìn)行建模，具體建模過程如下。設(shè)邏輯變量集VL={at_A, at_B, reachable_A_B, in_sun, work_done}。各邏輯變量的含義如下：用T和F表示邏輯“真”和邏輯“假”，at_A = T表示巡視器在停泊點(diǎn)A，at_B=F表示巡視器不在停泊點(diǎn)B，reachable_A_B=T表示停泊點(diǎn)A和B在空間上可達(dá)，in_sun=T表示巡視器處于光照范圍內(nèi)，work_done=F表示探測工作未完成。設(shè)數(shù)值變量集VM={energy}，energy變量建模巡視器的當(dāng)前電量值，其余2個(gè)變量分別表示移動(dòng)動(dòng)作和探測動(dòng)作的電量消耗。初始狀態(tài)I={at_A=T, at_B=F, reachable_A_B=T, in_sun=F, work_done=F, energy=80}。目標(biāo)集G={work_done=T}，表示任務(wù)目標(biāo)：要完成探測工作。

巡視器的行為建模如下： A和B兩點(diǎn)間的移動(dòng)動(dòng)作m=〈10,Cm,Em〉，它的條件集Cm={〈(sm,sm) at_A = T〉, 〈(sm,sm) reachable_A_B=T〉, 〈(sm,sm) energy gt;= 40〉}，它的效果集Em={〈(em,em) at_B = Tgt;, 〈(em,em) at_A = Fgt;, 〈(em,em) energy -= 30〉}。在B點(diǎn)工作的動(dòng)作w=〈15,Cw,Ew〉，它的條件集Cw={〈(sw,sw) at_B=T〉, 〈(sw,sw) energy gt;=30〉, 〈(sw,sw) work_done = F〉}，它的效果集Ew={〈(ew,ew) energy-=20〉, 〈(ew,ew) work_done=T〉}。 “定時(shí)觸發(fā)文字”集TL={〈[30] in_sun=T〉}表示巡視器在時(shí)間30上位于太陽光照內(nèi)。

可見，月面巡視器任務(wù)規(guī)劃問題涉及函數(shù)與數(shù)值變量的處理、時(shí)態(tài)關(guān)系的處理及外部事件的處理等多個(gè)復(fù)雜的方面，對(duì)求解算法的效率提出了挑戰(zhàn)。

1.2 啟發(fā)式狀態(tài)空間搜索與剪枝策略

目前，求解時(shí)態(tài)規(guī)劃問題的最有效方法是基于狀態(tài)空間搜索的方法[10]。其基本搜索過程為：對(duì)當(dāng)前狀態(tài)s，首先計(jì)算s的可用動(dòng)作集app_actions(s)，然后依據(jù)其中的動(dòng)作生成s的后繼狀態(tài)，再從后繼狀態(tài)中選擇一個(gè)作為新的當(dāng)前狀態(tài)。此過程持續(xù)到當(dāng)前狀態(tài)滿足目標(biāo)條件為止。當(dāng)app_actions(s)中含多個(gè)動(dòng)作時(shí)，優(yōu)先選擇哪個(gè)動(dòng)作對(duì)應(yīng)的后繼狀態(tài)，受啟發(fā)函數(shù)的引導(dǎo)，因而稱為“啟發(fā)式”狀態(tài)空間搜索。另一種互補(bǔ)的求解技術(shù)是從app_actions(s)中排除不可到達(dá)或無希望到達(dá)目標(biāo)狀態(tài)的動(dòng)作，這種技術(shù)稱為“剪枝策略”。因而，啟發(fā)函數(shù)和剪枝策略的有效性成為規(guī)劃算法求解效率的關(guān)鍵。

2 “有利動(dòng)作”剪枝策略的性質(zhì)分析

首先簡要介紹Hoffmann等為經(jīng)典規(guī)劃模型STRIPS設(shè)計(jì)的“有利動(dòng)作”剪枝策略，然后分析該策略在時(shí)態(tài)規(guī)劃模型上的不適用性。本節(jié)證明了“有利動(dòng)作”策略在時(shí)態(tài)規(guī)劃上導(dǎo)致不完備性。

2.1 “有利動(dòng)作”剪枝策略

在規(guī)劃求解的過程中，“有利動(dòng)作”剪枝策略為每個(gè)狀態(tài)s定義了候選動(dòng)作集HA(s)，且HA(s)?app_actions(s)。HA(s)的計(jì)算流程如下：首先，以s為初始狀態(tài)構(gòu)建一個(gè)“松弛規(guī)劃圖”(Relaxed Planning Graph)[6]；然后，從該圖中提取松弛規(guī)劃解，并根據(jù)這個(gè)規(guī)劃解確定在“松弛時(shí)態(tài)規(guī)劃圖”第1命題層的子目標(biāo)命題集G1；最后，將添加了命題p∈G1的動(dòng)作加入到HA(s)，即

(1)

2.2 HA策略可導(dǎo)致的不完備性

如果時(shí)態(tài)規(guī)劃搜索算法使用HA作為剪枝策略，即對(duì)于每個(gè)狀態(tài)s，只將HA(s)作為擴(kuò)展?fàn)顟B(tài)s的候選動(dòng)作，而排除集合app_actions(s)- HA(s)中的動(dòng)作，則算法是不完備的。這將導(dǎo)致某些規(guī)劃問題采用HA剪枝策略的搜索算法可能無法求解，但實(shí)際上該類問題并非無解。這類問題的主要特點(diǎn)是在規(guī)劃解中存在某個(gè)動(dòng)作，它的動(dòng)作效果只包含數(shù)值變量(資源變量),而不包含邏輯變量。

3 資源分析增強(qiáng)型剪枝策略

針對(duì)剪枝策略HA的不足，本文提出一種改進(jìn)型的剪枝策略RAEHA。改進(jìn)的思路是根據(jù)定理1及其證明過程，在RAEHA中首先定義與實(shí)現(xiàn)目標(biāo)相關(guān)的資源變量，然后定義與該資源變量相關(guān)的動(dòng)作，最后將在當(dāng)前狀態(tài)上可用的、與資源變量相關(guān)的動(dòng)作定義為有利動(dòng)作。根據(jù)該方式，為當(dāng)前狀態(tài)s計(jì)算的有利動(dòng)作集合記為RAEHA(s)。

1)?(v=d)∈G；

2)?a∈A:〈[x,x′]v=d〉∈Ca

從含義上講，條件1)定義了在目標(biāo)條件中直接包含的變量是目標(biāo)相關(guān)的；條件2)定義了與目標(biāo)間接相關(guān)的變量，這種變量出現(xiàn)在某個(gè)動(dòng)作的前提中，而同時(shí)該動(dòng)作的動(dòng)作效果中含有目標(biāo)相關(guān)的變量。本文僅考慮與目標(biāo)相關(guān)的資源變量，因此進(jìn)行如下定義。

根據(jù)目標(biāo)相關(guān)的資源變量，可以為當(dāng)前狀態(tài)s分析得到可用的、通過改變資源而與目標(biāo)相關(guān)的動(dòng)作集合，如下：

(2)

由式(2)可得，HA(s)?RAEHA(s)。

命題1 如果在任務(wù)∏的狀態(tài)s上，存在一個(gè)邏輯效果為空,并且與目標(biāo)相關(guān)的動(dòng)作a，則有HA(s)?RAEHA(s)。

在命題1中，HA(s)是RAEHA(s)的真子集的原因在于動(dòng)作a。一方面，動(dòng)作a是目標(biāo)相關(guān)的，但因?yàn)閯?dòng)作a的邏輯效果為空，所以動(dòng)作a一定是通過某個(gè)資源變量而與目標(biāo)相關(guān)的。由于a是通過某個(gè)資源與目標(biāo)相關(guān)，所以根據(jù)式(2)的定義，有a∈RAEHA(s)，同時(shí)，a?HA(s)。因此，命題1表明了RAEHA相比HA能收集更多的與目標(biāo)相關(guān)的動(dòng)作。

命題2 相比于運(yùn)用HA剪枝策略，運(yùn)用RAEHA剪枝策略的搜索算法能求解更多的時(shí)態(tài)規(guī)劃任務(wù)。

命題2的證明過程分為2部分：1)根據(jù)命題1，任何一個(gè)通過運(yùn)用HA能求解的問題，運(yùn)用RAEHA也能求解；2)構(gòu)造一個(gè)簡單的規(guī)劃任務(wù)∏′，該規(guī)劃任務(wù)能運(yùn)用RAEHA策略求解，但它不能用HA求解。任務(wù)∏′的具體描述如下：

V=VL∪VM,VL=φ,VM={v}；

A={a}，a=(6,Ca,Ea)；

Ca={([sa,sa]v=3)}；Ea={([ea]v=7)}；

TL=φ；δ(a)=20；

I={(v=3)}；G={(v=7)}。

4 實(shí)驗(yàn)與分析

在時(shí)態(tài)規(guī)劃系統(tǒng)Sapa的基礎(chǔ)上，使用Java語言實(shí)現(xiàn)了本文設(shè)計(jì)的剪枝策略RAEHA。Sapa采用的搜索算法為前向A*算法[11]，針對(duì)時(shí)態(tài)規(guī)劃模型提出了運(yùn)用“時(shí)態(tài)規(guī)劃圖”評(píng)估搜索狀態(tài)的目標(biāo)距離。該技術(shù)在近年來多次用于新型經(jīng)典規(guī)劃算法[12]和概率規(guī)劃算法的設(shè)計(jì)[13]，因而Sapa是時(shí)態(tài)規(guī)劃領(lǐng)域的一個(gè)代表系統(tǒng)。

為提高求解效率，Sapa在時(shí)態(tài)規(guī)劃模型上對(duì)HA剪枝策略進(jìn)行了擴(kuò)展，但它未考慮到本文提出的動(dòng)作與目標(biāo)在資源上的相關(guān)性。然而，在月面巡視器任務(wù)規(guī)劃中，頻繁涉及到影響資源的動(dòng)作，這類動(dòng)作對(duì)Sapa的求解效率提出了挑戰(zhàn)。同樣的，美國火星巡視器任務(wù)規(guī)劃也涉及資源操作。為對(duì)比分析HA和RAEHA對(duì)Sapa求解效率的影響，選用了智能規(guī)劃領(lǐng)域公開的、美國火星巡視器任務(wù)規(guī)劃的問題集“Satellite”[14-15]進(jìn)行實(shí)驗(yàn)和分析。

本實(shí)驗(yàn)主要從搜索算法的求解效率受資源相關(guān)動(dòng)作的影響方面分析本文提出的RAEHA策略相對(duì)于HA策略的優(yōu)勢。實(shí)驗(yàn)環(huán)境為CPU 2GHz、內(nèi)存限制2GB、求解時(shí)間7200s，JDK1.8。詳細(xì)的實(shí)驗(yàn)數(shù)據(jù)如表1所示，其中“-”表示無數(shù)據(jù)。“Satellite”問題集共包括20個(gè)具體的任務(wù)，任務(wù)名稱從prob1到prob20。Sapa在使用完整的求解技術(shù)時(shí)能夠求解如表1所含的11個(gè)任務(wù)[11]。因此，在這11個(gè)任務(wù)上分析RAEHA與HA對(duì)求解能力和效率的影響。主要得出如下結(jié)果：

1)在規(guī)劃任務(wù)prob10上，Sapa使用RAEHA策略能夠成功求解，僅在884ms內(nèi)就得到了一個(gè)包含4個(gè)資源相關(guān)動(dòng)作的規(guī)劃解。而它使用HA策略在7200s的時(shí)間限制內(nèi)未能成功求解,表明某些規(guī)劃任務(wù)對(duì)應(yīng)的方案需要資源相關(guān)的動(dòng)作，即，不使用資源相關(guān)的動(dòng)作，可能需要較長的規(guī)劃解，或者無法形成規(guī)劃解。因此，RAEHA策略對(duì)規(guī)劃系統(tǒng)的求解能力有本質(zhì)的提高;

2)在規(guī)劃任務(wù)prob4，prob7和prob8上，結(jié)合了RAEHA策略的Sapa分別構(gòu)造了包含1個(gè)、1個(gè)和2個(gè)資源相關(guān)動(dòng)作的規(guī)劃解。同時(shí)，結(jié)合HA策略的Sapa不使用資源相關(guān)動(dòng)作，也同樣成功求解。但是，運(yùn)用RAEHA時(shí)，評(píng)估的狀態(tài)數(shù)均一致地低于運(yùn)用HA時(shí)的水平。而且，結(jié)合RAEHA時(shí)，在這3個(gè)任務(wù)上的總求解時(shí)間優(yōu)于結(jié)合HA時(shí)的總求解時(shí)間，因此可提高求解效率。

以上數(shù)據(jù)和分析表明，本文提出的搜索剪枝策略RAEHA在工程應(yīng)用方面對(duì)HA策略實(shí)現(xiàn)了有效的改進(jìn)。

5 結(jié)論

從原理上分析了智能規(guī)劃領(lǐng)域有代表性的搜索剪枝策略HA擴(kuò)展到時(shí)態(tài)規(guī)劃后所導(dǎo)致的不完備性。提出了“資源分析增強(qiáng)型有利動(dòng)作”剪枝策略：RAEHA，并從支持規(guī)劃算法求解完備性的角度證明了RAEHA優(yōu)于HA。在開源的Sapa規(guī)劃系統(tǒng)上實(shí)現(xiàn)了RAEHA策略，并使用與我國月面巡視器任務(wù)規(guī)劃相關(guān)的美國火星巡視器測試問題集進(jìn)行了測試，表明了RAEHA在求解能力和求解效率上優(yōu)于HA。

表1 RAEHA策略與HA策略的對(duì)比實(shí)驗(yàn)數(shù)據(jù)

[1] 吳偉仁, 周建亮, 王保豐, 等. 嫦娥三號(hào) “玉兔號(hào)” 巡視器遙操作中的關(guān)鍵技術(shù) [J]. 中國科學(xué)信息科學(xué) (中文版), 2014, 44(4): 425-440. (Wu Weiren, Zhou Jianliang, Wang Baofeng, et al. Key Technologies in the Teleoperation of Chang′E-3 “Jade Rabbit” Rover[J]. Science in China Series F: In-formation Sciences, 2014, 44(4): 425-440.)

[2] 賈陽, 張建利, 李群智, 等. 嫦娥三號(hào)巡視器遙操作系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J]. 中國科學(xué)技術(shù)科學(xué) (中文版), 2014, 44(5): 470-482. (Jia Yang, Zhang Jianli, Li Qunzhi, et al. Design and Realization for Teleoperation System of the Chang′e-3 Rover[J]. Science in China Series E: Technological Sciences, 2014, 44(5): 470-482.)

[3] 高薇,蔡敦波,周建平,等. 嫦娥三號(hào)“玉兔號(hào)”巡視器行為規(guī)劃方法[J]. 北京航空航天大學(xué)學(xué)報(bào),2017, 43(2): 277-284.(Gao Wei, Cai Dunbo, Zhou Jianping, et al. Activity Planning Method for Chang′E-3 “Jade Rabbit” Rover[J]. Journal of Beijing University of Aeronautics and Astronsutics, 2017, 43(2): 277-284.)

[4] Rintanen J. Complexity of Concurrent Temporal Planning[C]//Proceedings of the Seventeenth International Conference on International Conference on Automated Planning and Scheduling. AAAI Press, 2007: 280-287.

[5] Hoffmann J, Nebel B. The FF Planning System: Fast Plan Generation Through Heuristic Search[J]. Journal of Artificial Intelligence Research, 2001, 14: 253-302.

[6] Richter S, Westphal M. The LAMA Planner: Guiding Cost-based Anytime Planning With Landmarks[J]. Journal of Artificial Intelligence Research, 2010, 39(1): 127-177.

[7] Seipp J, Sievers S, Helmert M, et al. Automatic Configuration of Sequential Planning Portfolios[C]//Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. AAAI Press, 2015: 3364-3370.

[8] Fickert M, Hoffmann J, Steinmetz M. Combining the Delete Relaxation with Critical-path Heuristics: a Direct Characterization[J]. Journal of Artificial Intelligence Research, 2016, 56(1): 269-327.

[9] Piotrowski W M, Fox M, Long D, et al. Heuristic Planning for PDDL+ Domains[C]//Workshops at the Thirtieth AAAI Conference on Artificial Intelligence. 2016.

[10] Krajňansky M, Hoffmann J, Buffet O, et al. Learning Pruning Rules for Heuristic Search Planning[C]//Proceedings of the Twenty-first European Conference on Artificial Intelligence. IOS Press, 2014: 483-488.

[11] Do M B, Kambhampati S. Sapa: A Multi-objective Metric Temporal Planner[J]. Journal of Artificial Intelligence Research, 2003, 20: 155-194.

[12] Muise C, Beck J C, McIlraith S A. Optimal Partial-order Plan Relaxation Via MaxSAT[J]. Journal of Artificial Intelligence Research, 2016, 57: 113-149.

[13] Marinescu L, Coles A. Heuristic Guidance for Forward-Chaining Planning with Numeric Uncertainty[C]//Proceedings of the Twenty-Sixth International Conference on Automated Planning and Scheduling (ICAPS 2016). AAAI Press, 2016: 230-234.

[14] Long D, Fox M. The 3rd International Planning Competition: Results and Analysis[J]. Journal of Artificial Intelligence Research (JAIR), 2003, 20: 1-59.

[15] Marzal E, Sebastia L, Onaindia E. Temporal Landmark Graphs for Solving Overconstrained Planning Problems[J]. Knowledge-Based Systems, 2016, 106: 14-25.

SearchPruningStrategyforMissionPlanninginLunarTeleoperation

Gao Wei1,2， Cai Dunbo3

1. School of Astronautics, Beijing University of Aeronautics and Astronautics, Beijing 100083, China 2. Beijing Aerospace Control Center, Beijing 100094, China 3. Hubei Provincial Key Laboratory of Intelligent Robot, Wuhan Institute of Technology, Wuhan 430205, China

Thewell-knownpruningstrategy“helpfulactions” (HA)isstudiedandextendedtothesettingsoftemporalplanningforChina’sLunarrover,whereresourcesarekeystosuccessfullyplan.Amorecapablepruningstrategycalled“resourceanalysisenhancedhelpfulactions” (RAEHA)isproposed.ThesetofRAEHAiscomputedthroughananalysisprocedureontherelationsamongresourcesandactions’effects.DuetoitsabilityinconsideringactionsthatareignoredbyHA,aplanningalgorithmisenabledbyRAEHAtosolveawiderrangeofproblemsthanHAdoes.TheexperimentalresultsshowthattheeffectivenessofRAEHAonasetofbenchmarksfortemporalplanningproblems.

Lunarteleoperation;Missionplanning;Pruningstrategy

TP181

A

1006-3242(2017)04-0073-06

*湖北省教育廳科學(xué)技術(shù)研究項(xiàng)目(Q20151516)

2017-03-15

高薇(1979-)，女，吉林通化人，碩士，工程師，主要研究方向?yàn)楹教鞙y控；蔡敦波(1981-)，男，內(nèi)蒙古通遼人，博士，副教授，主要研究方向?yàn)樽詣?dòng)推理與智能規(guī)劃。