高 薇 蔡敦波

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

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

高 薇1,2蔡敦波3

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

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

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

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

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

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

1 基本概念

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

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

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

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

2)A是動作集：動作a∈A具有形式〈da,Ca,Ea〉，da表示動作的持續(xù)時間；Ca是a的執(zhí)行條件集合(簡稱：條件集)，描述在動作執(zhí)行過程中必須成立的條件；Ea是a的執(zhí)行效果集合(簡稱：效果集)，包含動作a在開始執(zhí)行時刻產(chǎn)生的效果和結(jié)束時刻產(chǎn)生的效果。對于條件c∈Ca，如果它約束邏輯變量，則具有形式〈(sc,ec)v=r〉，r∈Dom(v)，sc和ec分別為條件“v=r”應(yīng)成立的“開始時刻”和“結(jié)束時刻”；如果它約束數(shù)值變量，則有形式〈(sc,ec〉voxgt;，o∈{gt;, ≥ , lt;, ≤, =}是比較算符，x是由數(shù)值變量和常量組成的數(shù)學(xué)表達(dá)式。對于效果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)集，其中每個目標(biāo)命題具有形式〈v=r〉，其中v∈V，這些目標(biāo)在規(guī)劃方案執(zhí)行后必須成立；

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

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

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

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

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

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

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

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

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

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

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

運用定義1的TP模型，能對上述實例進(jìn)行建模，具體建模過程如下。設(shè)邏輯變量集VL={at_A, at_B, reachable_A_B, in_sun, work_done}。各邏輯變量的含義如下：用T和F表示邏輯“真”和邏輯“假”，at_A = T表示巡視器在停泊點A，at_B=F表示巡視器不在停泊點B，reachable_A_B=T表示停泊點A和B在空間上可達(dá)，in_sun=T表示巡視器處于光照范圍內(nèi)，work_done=F表示探測工作未完成。設(shè)數(shù)值變量集VM={energy}，energy變量建模巡視器的當(dāng)前電量值，其余2個變量分別表示移動動作和探測動作的電量消耗。初始狀態(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兩點間的移動動作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點工作的動作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〉}。 “定時觸發(fā)文字”集TL={〈[30] in_sun=T〉}表示巡視器在時間30上位于太陽光照內(nèi)。

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

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

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

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

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

2.1 “有利動作”剪枝策略

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

(1)

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

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

3 資源分析增強型剪枝策略

針對剪枝策略HA的不足，本文提出一種改進(jìn)型的剪枝策略RAEHA。改進(jìn)的思路是根據(jù)定理1及其證明過程，在RAEHA中首先定義與實現(xiàn)目標(biāo)相關(guān)的資源變量，然后定義與該資源變量相關(guān)的動作，最后將在當(dāng)前狀態(tài)上可用的、與資源變量相關(guān)的動作定義為有利動作。根據(jù)該方式，為當(dāng)前狀態(tài)s計算的有利動作集合記為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)在某個動作的前提中，而同時該動作的動作效果中含有目標(biāo)相關(guān)的變量。本文僅考慮與目標(biāo)相關(guān)的資源變量，因此進(jìn)行如下定義。

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

(2)

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

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

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

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

命題2的證明過程分為2部分：1)根據(jù)命題1，任何一個通過運用HA能求解的問題，運用RAEHA也能求解；2)構(gòu)造一個簡單的規(guī)劃任務(wù)∏′，該規(guī)劃任務(wù)能運用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 實驗與分析

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

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

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

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

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

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

5 結(jié)論

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

表1 RAEHA策略與HA策略的對比實驗數(shù)據(jù)

[1] 吳偉仁, 周建亮, 王保豐, 等. 嫦娥三號 “玉兔號” 巡視器遙操作中的關(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] 賈陽, 張建利, 李群智, 等. 嫦娥三號巡視器遙操作系統(tǒng)設(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] 高薇,蔡敦波,周建平,等. 嫦娥三號“玉兔號”巡視器行為規(guī)劃方法[J]. 北京航空航天大學(xué)學(xué)報,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ù)研究項目(Q20151516)

2017-03-15

高薇(1979-)，女，吉林通化人，碩士，工程師，主要研究方向為航天測控；蔡敦波(1981-)，男，內(nèi)蒙古通遼人，博士，副教授，主要研究方向為自動推理與智能規(guī)劃。