適用于深空探測器的時間線轉移路標啟發式規劃方法

金 顥，徐 瑞，朱圣英，李朝玉，梁子璇

(1. 北京理工大學深空探測技術研究所，北京 100081；2. 深空自主導航與控制工業和信息化部重點實驗室，北京 100081)

0 引 言

航天器自主任務規劃技術的發展很大程度上緩解了復雜航天器系統人工決策的壓力[1-2]。它能夠根據任務設定的目標，按照一定的行為推理方式，給出符合規則的可行活動安排[3-5]。這種自主決策方式使得地面人員得以從繁重的指令編排工作中解放出來，能夠在保障航天器平穩運行的同時節約任務成本[6-8]。

深空探測任務的難度與日俱增，愈發復雜的物理系統導致傳統建模方法已經無法滿足其知識描述的需求。探測器各子系統的行為是隨時間變化的函數，故探測器任務規劃需要一種更為簡潔且表達力強的形式對問題域進行描述。另外，系統功能的多樣性會增加模型的復雜度，甚至影響規劃算法的決策。例如，火星車上存在兩個可交替使用的加熱設備用于現場試驗。這種情況為規劃器提供了更多樣化的選擇，會增大局部搜索范圍，增加規劃時間。因此，需要更有效的搜索引導策略來提高規劃的效率，在短時間內獲取一個正確的可執行活動序列。

自主規劃技術在航天中的應用一直是學術討論的熱點，并且已有部分方法在航天任務中得到了成功的應用。可擴展的通用遠程規劃框架(Extensible universal remote operations planning architecture, EUROPA)在NASA“深空一號”任務中得到了在軌應用，完成了自主任務規劃技術的星上驗證。EUROPA將規劃過程中復雜的約束關系統一表示為token之間的時間約束，并采用基于約束的搜索策略進行規劃求解，優化了規劃問題的描述方法[9-11]。但是，它所采用的深度優先搜索算法，在搜索節點的選取和擴展方面缺乏合適的評價方法，會對規劃效率產生一定程度的影響。自主科學飛行器實驗(Autonomous science experiment, ASE)是地球觀測1號(Earth observation 1, EO-1)的星載自主軟件[12]。ASE通過調用連續活動規劃執行和重規劃(Continuous activity scheduling planning execution and replanning, CASPER)軟件，能夠根據星載科學分析模塊提供的目標自動生成任務規劃活動序列。CASPER采用基于迭代修復技術的規劃算法，同時還應用啟發式方法在選擇修復策略時排除不相關的搜索選項。但是，該啟發式方法主要關注于不同修復沖突方法的比較，而鮮有對當前部分規劃中所有可選活動的評價。先進規劃調度框架(Advanced planning and scheduling initiative, APSI)是設計應用于火星快車任務的規劃系統。ASPI的開發是為了提高人工智能規劃和調度工具開發的效益和靈活性[13]。APSI采用基于迭代缺陷的方法，在選擇缺陷時使用啟發式策略削減搜索空間，但在缺陷求解步驟方面并未做深入的研究。王曉暉、李爽針對深空探測器任務規劃方法在處理系統間復雜約束時存在的約束復雜度高、計算效率低等問題，提出一種新的約束簡化方法和啟發式連續任務規劃方法[14]。牟帥等針對空間站在軌運營出現突發任務的情況，考慮活動間復雜約束關系傳播的影響，提出時間回溯迭代沖突化解策略完成對原任務執行序列的重規劃[15]。為了更好地應對航天器日益復雜的任務需求以及可能的外部干擾信息，規劃器需要具備在短時間內形成正確決策的能力。因此，規劃搜索的效率就顯得尤為重要。通過在搜索中加入啟發式評價，能夠輔助規劃器刪除錯誤或不“明智”的決策，實現加速求解的目的。

在啟發式評價技術方面，各類思想相互碰撞，方法策略層出不窮。其中，基于路標的方法由于其在搜索引導方面效果顯著，自Porteus等[16]提出了第一種利用事實路標的規劃算法后，迅速發展壯大成為啟發式搜索中的一個重要分支。Karpas和Dom-shlak首次提出了析取動作路標的概念[17]，Helmert和Domshlak在該概念的基礎上提出了著名的Landmark-cut方法[18]。隨后，Blai[19]、Pommerening等[20]、R?ger等[21]和Seipp等[22]都紛紛對這些方法進行了改進。然而，這些研究都集中于狀態空間中的啟發式設計，對于時間線規劃方向鮮有涉及。因此，本文將路標思想與時間線規劃相結合，設計一種時間線轉移路標啟發式評價策略，提高規劃搜索的效率。

文章主要結構如下：第一節對時間線規劃及路標相關的基礎知識進行了解釋；第二節設計了一種時間線知識框架下的hmax評價方法；在該方法的基礎上，第三節提出了時間線路標提取方法以及時間線轉移路標啟發式規劃算法；第四節進行了仿真實驗，對比討論分析各算法的性能；最后對所有內容進行了總結，得出結論。

1 基礎知識釋義

深空探測器時間線轉移路標啟發式規劃方法使用時間線知識描述模型，并在其基礎上進行啟發式算法研究。為了便于后文的描述，首先解釋幾個基本概念。

對hmax評價圖進行消環處理，需要盡可能的不影響到路標迭代搜索的過程，保證更多的路標存留。由于析取狀態路標的搜索是通過在初始狀態頂點到目標頂點的轉移路徑上不斷選取必要的析取狀態集合，所以對于存在環路的狀態轉移路徑，刪除其他狀態轉移到初始狀態的邊，既實現了轉移路徑消環，又不會對該搜索過程產生影響。如圖4所示，圖(a)中中心狀態I為初始狀態，其他狀態與狀態I之間均存在雙向轉移，所以該狀態轉移存在閉環。根據規則1可知，需刪除所有轉移到初始狀態I的邊，圖(b)中的“放射狀”轉移即為消環后的轉移圖。

狀態變量是對深空探測器系統知識的抽象，它能夠表示探測器的某個分系統、設備或某種資源在一段時間內的變化。狀態變量x可以表示為一個三元組x=，其中：V表示狀態變量x的值域，是一個非空集合；T表示狀態變量值域空間中所有取值之間的轉移規則；D表示狀態變量所有取值的持續時間。

狀態s是狀態變量在某個時間點或時間區間上的取值，可表示為一個三元組s=，其中：ts、te和d分別表示狀態s的開始時間、結束時間和持續時間。并且，由于深空探測任務中環境的不確知可能影響規劃序列的正常執行，將狀態s的所有時間參數均定義為一定的時間區間，即ts=[tsl,tsu]、te=[tel,teu]以及d=[dl,du]。通過獲取魯棒性更高的規劃解來應對執行過程中可能出現的不確定性問題。

析取狀態路標：假設存在狀態集l，若集合l至少存在一個狀態在規劃任務Π的所有可行解中均為真，則該狀態集l被稱為規劃任務Π的一個析取狀態路標。

根據上述方法將深空探測器描述為離散、并行的狀態轉移系統，然后針對該系統設計提出合適的啟發式規劃方法。時間線轉移路標啟發式規劃方法是建立在hmax評價方法的基礎上。因此，下一節中首先提出了時間線規劃中的hmax評價方法。

2 時間線規劃hmax評價方法

2.1 規劃問題實例

首先，給出一個簡化的深空探測器任務規劃問題實例。某巡視探測器的任務包括采樣和簡單的現場試驗，試驗步驟為對樣本進行加熱并在加熱的過程中采集數據。該實例的規劃模型中共包含兩條時間線：采樣設備時間線和加熱設備時間線。各時間線的狀態轉移如圖1所示，兩個設備之間的約束僅考慮加熱狀態與采樣狀態的時間關系：加熱需在采樣之后。任務開始時采樣設備處于卸載狀態，加熱設備處于關機狀態，任務目標為完成一次現場試驗。

2.2 最大約束轉移代價計算

時間線規劃hmax評價方法通過計算時間線上目標的轉移代價估計狀態到目標的距離，并以此作為節點的啟發式評價。時間線Lx上狀態s1到s2的轉移代價由兩部分構成：

J(s1,s2)=max(αJT,βJC)

(1)

其中:αJT為該狀態轉移影響時間線Lx內部狀態分布所帶來的代價，JT表示轉移路徑中實際轉移的數量，α為比例系數表示內部轉移代價的影響因子；βJC表示該狀態轉移對其他時間線的影響，JC為各段狀態轉移條件的代價，β為比例系數表示轉移條件代價的影響因子。

如圖1所示，該探測器在進行試驗前需要先完成采樣任務，即“采樣”狀態需要在“加熱”狀態之前。那么，加熱設備時間線上所有到“加熱”狀態的轉移都需要滿足采樣設備時間線上完成“采樣”狀態這一約束條件。因此，采樣設備時間線上的狀態分布，會影響到加熱設備時間線上狀態轉移的代價評估。

圖1 采樣設備和加熱設備狀態轉移圖

由于轉移條件可能涉及其他時間線的狀態，即實現時間線Lx上的某個狀態轉移，需要其轉移條件s′∈x′所在時間線Lx′的取值為對應該轉移條件s′∈x′的狀態s′。所以轉移條件代價受該時間線狀態分布的影響——時間線Lx′上當前狀態s*到狀態s′的轉移代價。然而，時間線規劃中采用的偏序搜索模式和節點中大量時序并行的狀態使得獲取準確的轉移條件代價會占用大量的計算資源。為簡化計算過程中的時序處理，使用初始狀態[22]作為s*的替代進行轉移條件代價計算。

若某段轉移的轉移條件集合中存在多個狀態，如s′和s″，則分別計算各轉移條件的代價后選擇其中的最大值作為該段轉移的條件代價，即最大約束轉移代價：

JC=max(J(Is′,s′),J(Is″,s″)) (2)

圖2 最大約束狀態轉移代價算法

Fig.2 The maximum transitioncondition algorithm

其中:Is′和Is″分別表示狀態s′和s″所在時間線的初始狀態。算法如圖2所示，這里取系數α=β=1，表示內部轉移與外部條件對整體轉移代價影響的比例相同。

2.3 時間線hmax節點評價

時間線規劃算法的輸入為問題的初始狀態集合和目標條件集，輸出是滿足所有約束的由各初始狀態到目標狀態的轉移路徑集合。規劃器在目標集合G中挑選合適的目標(或子目標)狀態g∈G實例化到部分規劃中，經約束傳播并滿足一致性條件后，將目標(或子目標)狀態g的所有約束作為子目標加入G{g}，更新目標集合。迭代上述過程，當目標集合G為空時，算法停止，并得到該問題的一個規劃解(否則該問題無解)。

在石英巖、片麻巖、片巖、變粒巖中，石榴石廣泛發育，十字石常與藍晶石和石榴石共生；黑云變粒巖及黑云片麻巖中常可見到矽線石；藍晶十字黑云變粒巖、黑云母石英片巖及黑云母片巖中均有堇青石出現，這些都是典型變質特征礦物，反映變質相為中低變質相，即角閃巖相。

時間線hmax節點評價方法采用上文所述的最大約束代價法計算得到各目標(不包含子目標)的評價值，并選取其中最大的評價值作為當前節點的代價。若目標g存在析取約束集合C1(g)和C2(g)，則分別計算各約束集的最大約束代價值，并選取其中最小的代價作為該目標的啟發式評價。在規劃過程中，規劃器會調用啟發式函數計算所有候選節點的評價值，選擇其中評價值最小的節點完成擴展。

觀察組患者用藥后，復發率為17.95%(7/39)，進展率為2.56%(1/39)；對照組患者用藥后復發率為23.08%(9/39)，進展率為5.13%(2/39)，兩組間比較無明顯差異(P>0.05)不具備統計學意義。

時間線hmax節點評價流程如下所示:

1)在目標集合G中選擇狀態g∈G,G:=G{g}；

對于我國社會發展而言，其擁有全球最廣闊的工業機器人應用市場，并且隨著我國工業產業結構的轉型升級和人口紅利的退減，導致的中國機器人應用市場的快速發展。并且可以預見在未來我國工業機器人的范圍和使用將會呈現出柔性化、智能化等方向發展。

2)搜索與g位于同一時間線的初始狀態Ig；

3)計算狀態轉移代價J(Ig,g)；

5)重復2～4，直到N*中包含初始狀態頂點，停止；

5)返回所有代價的最大值。

3 時間線轉移路標啟發式

由于深空探測器具有系統復雜、約束耦合以及時序并行的特點，經典規劃方法難以對深空探測任務進行規劃求解。而且，復雜的模型信息導致規劃搜索過程中搜索空間急劇膨脹，嚴重影響了規劃求解的效率。針對這一問題，從啟發式設計的角度出發，圍繞狀態路標的提取及動態更新、狀態路標代價計算以及最大路標集合節點篩選策略等方面進行研究，提出了時間線轉移路標啟發式規劃方法。通過快速準確地評估搜索空間中的候選節點，實現無關節點剪枝、削減搜索空間以及加速深空探測任務規劃求解的目的。

3.1 時間線規劃路標提取方法

3.1.1構建hmax狀態評價圖

以聚氯乙烯和煤焦油為主要原材料，摻入適量的外加劑，以水為分散介質而制成的水乳型防水涂料，稱為聚氯乙烯防水涂料。聚氯乙烯防水涂料在施工應用中，也需要鋪設玻璃纖維布或聚酯無紡布等材料進行增強處理，以達到增強的效果。

1)選擇一個狀態s∈x約束集中的狀態s′；

2)計算J(Is′,s′)；

3)重復1、2，遍歷整個約束集；

3.2.1狀態路標代價計算

2.規范抗暈訓練和運動中操作訓練：海上醫療人員的暈船、操作不精準等可通過陸地抗暈訓練和運動中操作訓練來強化克服。在醫院平時的陸地訓練中，一方面加強體能訓練，提高身體素質，同時通過滾輪、浪木等器材進行前庭功能訓練，增強抗暈能力。另一方面可通過在行駛車輛中練習靜脈穿刺等方法來提高運動中操作的精準度。醫務人員在陸地訓練的基礎上，通過海上適應性訓練熟悉船體搖擺、顛簸、振動條件下的技術操作要領，掌握患者、固定裝備和操作者的三方固定方法，可以強化海上操作行為的準確性和安全性，降低職業暴露風險。

全部狀態的約束集合經過上述“變形”，都映射為評價圖中的點和邊的集合。從而，狀態評價圖中初始狀態到目標狀態的所有路徑的必經頂點集合表示所有規劃解中必然存在的狀態。所以，規劃任務的一個析取狀態路標l可以表示為評價圖中的一個頂點集合Vl，使得評價圖中所有從初始狀態集合到目標集合的路徑均至少包含集合Vl中的一個頂點。因此，在評價圖中搜索所有具有上述性質的頂點集合，可得到規劃任務的狀態路標集合M。根據評價圖的特點可知，包含全部頂點的集合一定是滿足上述約束的一個頂點集合，所以對于任意狀態評價圖，頂點集合一定存在且不為空集。為了獲取盡可能多的路標集合l完成對規劃搜索的評價，提出多目標迭代擴張算法進行路標搜索。

正說著，一個小媳婦裊裊娜娜地走過來，她端著盆，是來河邊淘米的。老砍頭見她來了，低下頭，四處望。小媳婦笑著問：“一大早的在找什么呢？”

3.1.2多目標迭代擴張路標搜索算法

對于目標g∈G，考慮評價圖中存在的兩類區域，一是能夠通過代價為0的路徑到達目標g的頂點集合N*，另一區域為初始狀態的所有可達頂點集合中與N*不相交的部分NI。由于評價圖中由初始狀態到達目標狀態的轉移路徑必然包含區域N*中的頂點，則所有由NI指向N*中頂點的邊集El即為規劃解中必需的狀態轉移。從而，集合El中各邊指向的頂點構成了一個析取狀態路標l，路標l的代價為El中的最小轉移代價。將El中所有轉移的代價分別減去l的代價并對應更新到評價圖中，完成路標l對評價圖的代價劃分。由于代價劃分可能導致出現新的代價為零的邊，所以需要對集合N*和NI進行更新，這樣就實現了集合N*的一次“擴張”。重復上述步驟，迭代擴張集合N*，直到找到從初始狀態頂點到目標頂點的一條代價為0的路徑。具體步驟如下所示：

1)初始化集合NI、N*；

質譜條件:Agilent HP-5色譜柱(25 m × 0.32 mm × 1.05 μm); 柱流量:1 mL/min; 質量范圍:29～420 AMU; 電子倍增電壓(EMV):1 435 V; 電離電壓:70 eV; 離子源溫度:230 ℃; 四極桿溫度:150 ℃。

2.討論形成方案。將學生分為10個小組，以小組為單位進行討論，研究制訂相關方案，方案內容包括了解霧霾的嚴重性、成因、解決措施以及對應的英語詞匯。

2)搜索由NI指向N*的邊集El；

該區域加深鉆井采用高密度鉆井液支撐井壁，提高抑制性能防止泥頁巖水化分散脫落，并選擇合適鉆井工藝防塌措施的施工方案。以152井為例，該井鉆井液密度控制為1.85～1.90g／cm3，漏斗黏度為50～70s，pH值為9～11，切力為（8～12）／（15～20）Pa／Pa，動切力為12～16Pa，塑性黏度為25～35mPa·s，常規濾失量為3～5mL，高溫高壓濾失量（150℃）為8～10mL，固相含量36%～40%，含砂量為0.3%～0.5%。

經hmax評價圖構建、消環和路標提取過程后，得到規劃任務Π的析取狀態路標集合M。假設圖中轉移邊的代價均相等，則多目標迭代擴張路標搜索算法如圖6所示。下一節將集中討論如何有效的利用析取狀態路標集合M加速規劃搜索。

4)更新集合NI、N*；

4)重復1～3，直到G為空集，停止；

6)提取析取狀態路標集合M={l1,l2,…,ln}。

如圖3所示，評價圖中頂點g為目標狀態，I1和I2為初始狀態，圖中邊的權值均為0或1。則由步驟1得到的集合N*={C，E，F，g}(圖中實心圓表示的頂點)，NI={I1，I2，A，B，D}(圖中空心圓表示的頂點)。然后搜索從NI到N*的邊集El={，}，并提取El對應的析取狀態路標l={C，E}，代價為1。將評價圖中的邊，的權值減去1后，重新搜索集合N*={B，D，C，E，F，g}，NI={I1，I2，A}。迭代上述過程，得到該評價圖對應的析取狀態路標集合為：M={{C，E}，{B，D}}。

圖3 評價圖中N*集合的一次擴張

通過上述步驟1～6，可計算得到目標g的析取狀態路標集Mg。為了進一步增強路標對規劃搜索過程的控制，需要獲取盡可能多的析取狀態路標對節點進行更準確的評估。因此，將集合G中的全部目標作為上述路標提取步驟的輸入，對任意g∈G，建立獨立的評價圖進行計算，最終得到各目標的析取狀態路標集合M=∪Mg, ?g∈G。通過實現析取狀態路標對規劃任務全部目標的覆蓋，引導規劃搜索過程中各目標最短轉移路徑的建立，加速規劃求解。

由于多目標迭代擴張算法是對評價圖的節點集合迭代劃分的過程，若評價圖中出現環路，則該算法可能陷入重復計算而導致求解失敗。因此，需要對狀態評價圖進行去環。考慮模型約束對hmax評價圖的影響，設計了如下時序轉移消環策略：

1)若某時間線的狀態轉移形成一個大的閉環，則在初始狀態處進行切斷，即刪除轉移到初始狀態的邊；

2)若某時間線的狀態轉移形成局部閉環，刪除向靠近初始狀態方向轉移的邊。

一個深空探測規劃任務為一個四元組Π=，V為狀態變量集合，C表示約束集，I?V為初始狀態，G?V為目標集[23]。

固本拓新--基于傳統住宅的裝配式住宅建筑設計…………………………………………………… 彭敏，萬莉（7-18）

4.3 化學防治 2017年我們進行了大生M-45、多霉清、復方多菌靈、甲基托布津等殺菌劑防治金絲小棗漿爛果病對比試驗。結果表明，不同藥劑防治金絲小棗漿爛果病效果差異顯著，其中800倍液80%大生M-45防效最好。

圖4 整體閉環的轉移圖消環

同理，目標g2和g3的距離估計值分別為hg2和hg3。綜合各目標的評價值，為避免出現節點過評估的情況，選取其中的最大值作為節點N的評價值。

圖5 轉移圖中局部回退邊消環

3)提取析取狀態路標l，完成l的代價劃分；

圖6 多目標迭代擴張路標搜索算法

3.2 深空探測器時間線轉移路標啟發式規劃算法

4)只保留最大代價的約束s′max。

啟發式方法是基于規劃問題的目標集合，給出一定的規則來評價一個狀態的代價。例如，快速正向(Fast forward，FF)搜索算法通過生成一個從當前狀態到目標的松弛規劃解來估計該狀態到目標的距離，然后將生成的規劃解中的動作數量用作啟發式評價。同理，針對深空探測規劃任務Π，利用上一節計算得到的析取狀態路標集合M進行啟發式評價能夠保證規劃器優先選擇規劃解中必然存在的狀態，從而，進一步實現對無關節點的剪枝，削減規劃問題的搜索空間。

時間線規劃路標提取方法實現了對各目標狀態析取路標的獨立搜索。故對于目標gi∈G，存在析取狀態路標集合Mgi與之對應。假設節點N∈N擴(N擴表示下一步可擴展的候選節點集合)中存在目標g1、g2和g3，以及各目標的析取狀態路標集合Mg1、Mg2和Mg3。更全面準確的評估節點N需要綜合其全部目標的距離信息。對于目標g1，節點N中的析取狀態路標集合Mg1既包含了到目標g1的最短轉移路徑節點，又記錄了途經該節點需付出的代價。從而，節點N中目標g1的距離估計值可表示為g1在該節點的析取狀態路標集合Mg1中的所有析取狀態路標的代價和，即：

hg1=Σc(li), ?li?Mg1

(3)

第二條規則針對轉移圖中的局部“回退”邊進行處理。hmax評價圖中對目標距離的估計值為初始狀態頂點到該目標頂點的最短路徑距離。而轉移中的回退邊(即朝向靠近初始狀態方向的轉移)會導致局部環路，干擾路徑搜索。從而，通過刪除圖中的回退邊進行消環，既能夠有效防止搜索陷入局部循環，又能夠盡量降低對目標最短路徑距離的影響。如圖5所示，圖(a)中狀態I為初始狀態，中心狀態F與其他狀態之間均存在雙向轉移，所以該圖存在局部閉環。根據規則2刪除圖中的回退邊得到圖(b)，完成對原圖的消環處理。

h(N)=max(hgi), ?gi∈G

(4)

析取狀態路標l表示在所有規劃解中都為真的狀態集合。由于hmax評價圖中各邊具有相同的代價，節點N的評價值越低，其包含的析取狀態路標數量可能就越少，規劃過程中需要實例化的狀態數量可能就越少。因此，在規劃節點擴展過程中，需計算下一步所有候選節點的評價值，并選擇其中評價值最小的節點進行擴展。

3.2.2狀態路標增量式更新方法

選擇評價值最低的節點完成擴展后，需要更新其所有候選節點中的析取狀態路標集合。由于每次擴展節點后都會涉及大量候選節點路標集合的更新，若每次更新都對節點中的所有目標執行重新構建hmax評價圖、消環和路標提取的流程，雖然能夠得到更準確的路標集合和節點評價，但同時會引入大量的計算消耗，與加速搜索的初衷背道而馳。若是不更新候選節點的路標集合，則隨著規劃過程的進行，節點的析取狀態路標集合對其目標距離估計的偏差會越來越大，甚至還有可能給出“錯誤”的估計結果。為了保證評價準確性的同時盡可能地降低不必要的計算耗時，采用路標增量式更新方法(見圖7)，在規劃過程中動態更新各候選節點的析取狀態路標集合。

圖7 路標增量式更新方法

假設候選節點N中新實例化的狀態為sn，則目標g的析取狀態路標集合Mg的動態更新流程如下：

2)刪除路標集合lj；

佛陀是怎么回答的呢？用我們今天的話說，就是我們平時所經歷的各種身心的煩惱，就好像一支支利箭向我們射來。比如，在病中的人，要承受身體的痛苦。而這個時候，人往往會憂慮，擔心自己的病不知什么時候好，擔心自己耽擱了工作，擔心不能照顧好小孩，等等。這樣，他所承受的就不只是身體有病的痛苦了，而是在這個痛苦之上又添加了一重痛苦。如果說身體最初的痛苦，是射向我們的“第一箭”，那么后來添加的痛苦，就是“第二箭”了。

由于lj為析取狀態路標，則所有規劃解中均至少包含一個lj中的狀態。當實例化狀態sn后，該路標得到滿足，所以在Mgi中刪除lj。同時，由于lj中的其他狀態不再為目標gi的析取狀態路標，所以將對應狀態的權值加回圖中，在新圖上搜索是否存在新增的析取狀態路標集合。

3.2.3最大路標集合節點篩選策略

針對搜索空間中的每個候選節點，狀態路標啟發式需要分別計算每個節點中各目標對應的狀態路標集合，然后取其中最大的代價作為每個候選節點的啟發式評價。這種多目標綜合評價的模式雖然能夠加強狀態路標對整個搜索過程的控制并提高啟發式評價的準確性，但同樣會帶來極大的計算負擔。為了平衡狀態路標啟發式的計算消耗和評價準確度二者的潛在收益，在規劃搜索過程中，對候選節點集合進行初步篩選，盡可能地降低需要計算狀態路標集合的節點數量。

將當前局部規劃中目標距離估計值最大的目標記作gmax，目標gmax的狀態路標集合記作Mgmax。考慮采用狀態路標集合進行啟發式評價時的兩個重要特征：首先，候選節點的啟發式評價值越低，表示該節點距離規劃問題的某個可行解越近，故優先選擇評價值最低的節點進行擴展；其次，由于候選節點的啟發式評價值為全部目標距離估計的最大值，所以若候選節點中新實例化的狀態不是Mgmax中的狀態，則該候選節點的代價肯定不低于hgmax，其中hgmax為Mgmax中所有狀態路標的代價和。只有當候選節點中對Mgmax中狀態進行實例化，才有可能進一步得到更低的評價值。

例如，表1中列出了某局部規劃中所有目標的狀態路標集合及各狀態路標集合的代價值。假設該局部規劃的所有候選節點均能夠實現一個或多個狀態路標集合中的狀態路標(由于與狀態路標集合無關的節點不會影響到狀態路標集合的代價，這里僅考慮能實現狀態路標的候選節點)。由表中數據可知，目標g1為當前局部規劃中距離估計值最大的目標gmax，狀態路標集合Mg1即為Mgmax。表中每一個狀態路標集合都對應一個候選節點集合，該候選節點集合中的節點能夠實例化對應狀態路標集合中的狀態，即實現對應集合內的狀態路標。由于所有候選節點均與一個或多個狀態路標集合相關，則對表中任意候選節點進行擴展必然會引起相關狀態路標集合中狀態路標的改變，進而影響狀態路標集合的代價。然而，候選節點的啟發式評價為該節點中所有狀態路標集合的最大代價，所以若實例化的狀態不屬于最大狀態路標集合，則不會減少節點的評價值。例如，節點nd2中實例化了狀態路標集合Mg2狀態，但由于最大路標集合Mg1中的狀態路標數量不會減少，所以節點nd2的評價值不會低于原節點的評價值。

表1 狀態路標集合代價及對應候選節點示例

因此，使用狀態路標集合Mgmax對所有候選節點進行篩選，既能夠削減當前局部規劃的搜索空間，又能夠在避免大量計算的同時優先挑選評價值最低的候選節點進行擴展。在搜索過程中優先選取實例化Mgmax中狀態的候選節點進行進一步評價，能夠加速規劃器朝候選節點評價值降低的方向搜索，更容易得到規劃問題的一個可行解。另外，若存在多個gmax，則采用隨機策略在代價相同的目標中進行挑選。

綜上，深空探測器時間線轉移路標啟發式規劃算法如圖8所示。

圖8 時間線轉移路標啟發式規劃算法

4 仿真校驗

為驗證深空探測器時間線轉移路標啟發式算法的性能，在EUROPA2的基礎上分別對時間線hmax啟發式規劃算法和時間線轉移路標啟發式規劃算法進行實現，并構建火星車測試場景對上述兩種規劃算法進行仿真測試。

該測試場景中，火星車通過鉆機打孔的方式能夠采集火星地表不同深度的樣本。每次鉆孔取樣都會在三個不同的深度獲取土壤樣本：表面土壤樣本、20 cm深的土壤樣本以及50 cm深的土壤樣本。在三種樣本中選取一種作為收集的土壤取樣，其他樣本均用于現場試驗。此外，火星車還能夠使用星載照相機采集火星地表圖像數據，并通過數據分析模塊檢測提取圖像特征。這些收集的數據信息經壓縮后存入火星車的數據緩沖區，并能夠在合適的時候上傳數據至軌道器中。測試場景的詳細模型信息見表2。

表2 火星車測試場景詳細模型信息

通過改變火星車初始位置、設備狀態以及任務目標，構建十個該火星車場景的測試用例。測試問題依編號順序目標數量逐漸增多。實驗中對每個測試問題均統計其十次計算的平均值，所有計算結果如圖9到圖12所示。圖中hmax啟發式算法表示時間線hmax啟發式規劃算法，LM(Levenberg-Marquardt)啟發式算法表示時間線轉移路標啟發式算法。不失一般性，將前者簡略稱作hmax算法，后者稱作路標算法，Europa2算法稱作原算法。

圖12 規劃效率提升對比圖

仿真測試環境為：Windows 7 64位操作系統，i3-2350M CPU，主頻2.30GHz，內存4.00 GB。圖中的所有數據均為使用同等環境下原算法的計算結果減去兩種啟發式算法的結果得到的差值。

針對所有測試問題，啟發式算法的計算時間均小于原算法的計算時間，且兩種啟發式算法中，路標算法的用時更少，如圖9所示。隨著測試問題目標數量的增加，啟發式算法計算時間的優勢雖然在部分問題上有所回落，但整體仍呈現上升趨勢。另外，在對復雜問題進行規劃求解時(如問題I、J)，啟發式算法的優勢更大，且漲幅更明顯。如圖5中計算時間曲線所示，自問題H后，曲線斜率陡增。hmax算法雖然在問題J處時間差值漲幅略緩，但與前面測試問題相比(問題A到問題G)，曲線斜率仍有較大提升。而路標算法在問題J處的計算時間差值仍然保持較高增長，甚至與問題I處相比曲線斜率仍有微弱提升。從而，在降低算法規劃時間方面，路標啟發式算法全面壓制了hmax啟發式算法。針對所有測試問題的規劃求解，路標啟發式算法的表現更穩定，效果更好，用時更少。

礦區內V-04、V-38、VI-09、VI-11、VI-16、VI-17、VI-20、VI-218個礦體為前5年開采礦體。

圖9 規劃時長差對比圖

為進一步討論和驗證啟發式算法的性能，探究啟發式算法時間優勢的緣由，對所有測試問題中兩種算法的規劃步數進行了統計，得到兩種啟發式算法相對原算法的規劃步數差值曲線。如圖9所示，兩條曲線與圖5中的計算時間差值曲線呈現出類似的增長變化趨勢，但整體而言增長幅度低于時間差值曲線。hmax算法前期步數差值增幅不大，曲線平緩，問題E后曲線逐漸下降，于問題H處下降至最低點后“反彈”。雖有稍許回升但在問題J處再次回落，整體趨向于在某值附近穩定。

路標算法曲線雖然亦有兩處“凹陷”，但整體變化較為平緩，且在問題J處仍呈現一定的上升趨勢。二者雖然在問題A處的步數優勢相同，但隨著問題復雜度的提高，hmax算法在問題J處只提高約一倍的步數差，而路標算法在問題J處的步數差值約為問題A處的4倍。

同時，計算時間和規劃步數之間并不是簡單的線性關系。隨著規劃步數的增長，參與約束推理的節點數也就越多，由于原算法使用時間約束網絡進行約束一致性檢測，當網絡中頂點數量到達一定基數時，每一步的增加都會帶來大量的計算耗時。因此，圖10中的曲線走勢較圖9而言略顯平緩。規劃步數差值曲線是對間差值結果曲線的有力支撐，反映出路標啟發式算法的表現要整體優于hmax啟發式算法。下面進一步討論規劃步數中節點擴展數量的差異對規劃結果的影響。

圖10 規劃步數差對比圖

算法的規劃步數可根據其是否生成新節點劃分為兩類：算法迭代過程中存在新節點生成的步驟，稱作節點擴展步；不存在新節點生成的步驟，稱作非節點擴展步，例如節點回溯。對于同一個規劃問題，hmax算法與路標算法所需擴展的節點數量能夠直接的反映出其節點評價的準確性。如圖11所示，圖中每個測試問題對應有兩列堆疊柱形，分別表示四部分數據：hmax算法節點擴展步與非節點擴展步同原算法的差值、路標算法節點擴展步與非節點擴展步同原算法的差值。從圖中可以清晰地看出，除問題A外，路標算法規劃步數的減少量均大于對應問題中hmax算法規劃步數的減少量，即路標算法求解各測試問題所需的規劃步數均不超過hmax算法所需步數。對于簡單問題的規劃求解，由于其涉及節點數量較少且搜索空間規模較小，啟發式的作用并不明顯，故問題A出現兩種算法步數完全一致的情況。但隨著目標數量的增多，規劃求解愈顯復雜，算法的每一次迭代都會向搜索空間中加入大量候選規劃節點。另外，搜索空間中亦存在大量“死區”節點，即從該節點繼續搜索無法得到問題的規劃解。因此，啟發式評價函數的性能將直接影響規劃問題的求解速度。

圖11 節點擴展與非節點擴展步數的減少量對比圖

如圖11所示，在規劃步數中，節點擴展步數占有大約一半的比重。即所有減少的規劃迭代步數中，有一半及以上的數量來自于節點擴展數目的減少。而節點擴展數目的減少則直接對應于啟發式算法的節點評價能力。對于所有測試問題，hmax算法和路標算法均能夠保證對原算法的性能提升，而后者的節點擴展數量均不超過前者，故路標算法在節點評價的準確性上更勝一籌。啟發式規劃算法能夠通過節點評價決定節點擴展順序，直接減少冗余節點的擴展數量；又間接的降低規劃陷入“死區”的概率和次數，減少了不必要的回溯步驟。通過兩方面的共同作用來提高規劃求解的效率。

圖12中的曲線展示了兩種啟發式算法在所有測試問題上相較原算法的規劃效率提升。其中路標啟發式算法對應曲線的數值大約在40上下變化；而hmax算法在問題A上達到效率提升的峰值，然后逐漸降低，最終回升到30附近。綜上，hmax算法和路標算法在所有測試問題上對比原算法均能加速搜索，提高規劃效率，且路標算法的性能更好。

5 結論

深空探測器任務規劃具有系統復雜、約束耦合且任務多的特點，導致傳統規劃技術效率低下難以直接應用。針對這一問題，本文提出了一種深空探測器時間線轉移路標啟發式算法，通過搜索實現任務目標必需的狀態集合，減少規劃過程中冗余節點擴展數量，實現加速搜索的目的。另外，為了降低啟發式計算帶來的時間消耗，在不影響路標數量的前提下提出了增量式路標更新方法以及最大目標篩選策略。最后，仿真實驗結果表明時間線路標轉移啟發式算法能夠提高規劃求解效率，且與時間線hmax規劃算法相比計算性能更具優勢。