面向月面遙操作任務規劃系統的搜索剪枝策略研究*

高 薇 蔡敦波

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

面向月面遙操作任務規劃系統的搜索剪枝策略研究*

高 薇1,2蔡敦波3

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

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

月面遙操作；任務規劃；剪枝策略

嫦娥三號任務取得了中國首次在月球上實施巡視器軟著陸和巡視勘察的成功[1]。“玉兔號”巡視器與著陸器脫離后，在月面前進實施科學探測任務，每項探測任務均在地面“遠程遙操作”的控制方式下完成[2]。地面站對綜合巡視器的各項數據進行邏輯抽象，構建“時態規劃問題”(Temporal Planning Problem)，調用專門設計的“自動規劃系統”進行求解，輸出規劃方案，上傳至巡視器[3]。這種自動地進行任務規劃的方法相對于以往人工編制規劃的方法在任務完成效率上具有顯著優勢。

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

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

1 基本概念

1.1 月面巡視器任務規劃與時態規劃

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

運用定義1的TP模型，能對上述實例進行建模，具體建模過程如下。設邏輯變量集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在空間上可達，in_sun=T表示巡視器處于光照范圍內，work_done=F表示探測工作未完成。設數值變量集VM={energy}，energy變量建模巡視器的當前電量值，其余2個變量分別表示移動動作和探測動作的電量消耗。初始狀態I={at_A=T, at_B=F, reachable_A_B=T, in_sun=F, work_done=F, energy=80}。目標集G={work_done=T}，表示任務目標：要完成探測工作。

巡視器的行為建模如下： 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〉}。 “定時觸發文字”集TL={〈[30] in_sun=T〉}表示巡視器在時間30上位于太陽光照內。

可見，月面巡視器任務規劃問題涉及函數與數值變量的處理、時態關系的處理及外部事件的處理等多個復雜的方面，對求解算法的效率提出了挑戰。

1.2 啟發式狀態空間搜索與剪枝策略

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

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

首先簡要介紹Hoffmann等為經典規劃模型STRIPS設計的“有利動作”剪枝策略，然后分析該策略在時態規劃模型上的不適用性。本節證明了“有利動作”策略在時態規劃上導致不完備性。

2.1 “有利動作”剪枝策略

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

(1)

2.2 HA策略可導致的不完備性

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

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

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

1)?(v=d)∈G；

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

從含義上講，條件1)定義了在目標條件中直接包含的變量是目標相關的；條件2)定義了與目標間接相關的變量，這種變量出現在某個動作的前提中，而同時該動作的動作效果中含有目標相關的變量。本文僅考慮與目標相關的資源變量，因此進行如下定義。

根據目標相關的資源變量，可以為當前狀態s分析得到可用的、通過改變資源而與目標相關的動作集合，如下：

(2)

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

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

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

命題2 相比于運用HA剪枝策略，運用RAEHA剪枝策略的搜索算法能求解更多的時態規劃任務。

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

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 實驗與分析

在時態規劃系統Sapa的基礎上，使用Java語言實現了本文設計的剪枝策略RAEHA。Sapa采用的搜索算法為前向A*算法[11]，針對時態規劃模型提出了運用“時態規劃圖”評估搜索狀態的目標距離。該技術在近年來多次用于新型經典規劃算法[12]和概率規劃算法的設計[13]，因而Sapa是時態規劃領域的一個代表系統。

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

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

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

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

以上數據和分析表明，本文提出的搜索剪枝策略RAEHA在工程應用方面對HA策略實現了有效的改進。

5 結論

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

表1 RAEHA策略與HA策略的對比實驗數據

[1] 吳偉仁, 周建亮, 王保豐, 等. 嫦娥三號 “玉兔號” 巡視器遙操作中的關鍵技術 [J]. 中國科學信息科學 (中文版), 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] 賈陽, 張建利, 李群智, 等. 嫦娥三號巡視器遙操作系統設計與實現[J]. 中國科學技術科學 (中文版), 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] 高薇,蔡敦波,周建平,等. 嫦娥三號“玉兔號”巡視器行為規劃方法[J]. 北京航空航天大學學報,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

*湖北省教育廳科學技術研究項目(Q20151516)

2017-03-15

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