適用于深空探測器的時間線轉(zhuǎn)移路標(biāo)啟發(fā)式規(guī)劃方法

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

(1. 北京理工大學(xué)深空探測技術(shù)研究所，北京 100081；2. 深空自主導(dǎo)航與控制工業(yè)和信息化部重點(diǎn)實驗室，北京 100081)

0 引 言

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

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

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

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

文章主要結(jié)構(gòu)如下：第一節(jié)對時間線規(guī)劃及路標(biāo)相關(guān)的基礎(chǔ)知識進(jìn)行了解釋；第二節(jié)設(shè)計了一種時間線知識框架下的hmax評價方法；在該方法的基礎(chǔ)上，第三節(jié)提出了時間線路標(biāo)提取方法以及時間線轉(zhuǎn)移路標(biāo)啟發(fā)式規(guī)劃算法；第四節(jié)進(jìn)行了仿真實驗，對比討論分析各算法的性能；最后對所有內(nèi)容進(jìn)行了總結(jié)，得出結(jié)論。

1 基礎(chǔ)知識釋義

深空探測器時間線轉(zhuǎn)移路標(biāo)啟發(fā)式規(guī)劃方法使用時間線知識描述模型，并在其基礎(chǔ)上進(jìn)行啟發(fā)式算法研究。為了便于后文的描述，首先解釋幾個基本概念。

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

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

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

析取狀態(tài)路標(biāo)：假設(shè)存在狀態(tài)集l，若集合l至少存在一個狀態(tài)在規(guī)劃任務(wù)Π的所有可行解中均為真，則該狀態(tài)集l被稱為規(guī)劃任務(wù)Π的一個析取狀態(tài)路標(biāo)。

根據(jù)上述方法將深空探測器描述為離散、并行的狀態(tài)轉(zhuǎn)移系統(tǒng)，然后針對該系統(tǒng)設(shè)計提出合適的啟發(fā)式規(guī)劃方法。時間線轉(zhuǎn)移路標(biāo)啟發(fā)式規(guī)劃方法是建立在hmax評價方法的基礎(chǔ)上。因此，下一節(jié)中首先提出了時間線規(guī)劃中的hmax評價方法。

2 時間線規(guī)劃hmax評價方法

2.1 規(guī)劃問題實例

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

2.2 最大約束轉(zhuǎn)移代價計算

時間線規(guī)劃hmax評價方法通過計算時間線上目標(biāo)的轉(zhuǎn)移代價估計狀態(tài)到目標(biāo)的距離，并以此作為節(jié)點(diǎn)的啟發(fā)式評價。時間線Lx上狀態(tài)s1到s2的轉(zhuǎn)移代價由兩部分構(gòu)成：

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

(1)

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

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

圖1 采樣設(shè)備和加熱設(shè)備狀態(tài)轉(zhuǎn)移圖

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

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

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

圖2 最大約束狀態(tài)轉(zhuǎn)移代價算法

Fig.2 The maximum transitioncondition algorithm

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

2.3 時間線hmax節(jié)點(diǎn)評價

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

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

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

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

時間線hmax節(jié)點(diǎn)評價流程如下所示:

1)在目標(biāo)集合G中選擇狀態(tài)g∈G,G:=G{g}；

對于我國社會發(fā)展而言，其擁有全球最廣闊的工業(yè)機(jī)器人應(yīng)用市場，并且隨著我國工業(yè)產(chǎn)業(yè)結(jié)構(gòu)的轉(zhuǎn)型升級和人口紅利的退減，導(dǎo)致的中國機(jī)器人應(yīng)用市場的快速發(fā)展。并且可以預(yù)見在未來我國工業(yè)機(jī)器人的范圍和使用將會呈現(xiàn)出柔性化、智能化等方向發(fā)展。

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

3)計算狀態(tài)轉(zhuǎn)移代價J(Ig,g)；

5)重復(fù)2～4，直到N*中包含初始狀態(tài)頂點(diǎn)，停止；

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

3 時間線轉(zhuǎn)移路標(biāo)啟發(fā)式

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

3.1 時間線規(guī)劃路標(biāo)提取方法

3.1.1構(gòu)建hmax狀態(tài)評價圖

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

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

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

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

3.2.1狀態(tài)路標(biāo)代價計算

2.規(guī)范抗暈訓(xùn)練和運(yùn)動中操作訓(xùn)練：海上醫(yī)療人員的暈船、操作不精準(zhǔn)等可通過陸地抗暈訓(xùn)練和運(yùn)動中操作訓(xùn)練來強(qiáng)化克服。在醫(yī)院平時的陸地訓(xùn)練中，一方面加強(qiáng)體能訓(xùn)練，提高身體素質(zhì)，同時通過滾輪、浪木等器材進(jìn)行前庭功能訓(xùn)練，增強(qiáng)抗暈?zāi)芰ΑＡ硪环矫婵赏ㄟ^在行駛車輛中練習(xí)靜脈穿刺等方法來提高運(yùn)動中操作的精準(zhǔn)度。醫(yī)務(wù)人員在陸地訓(xùn)練的基礎(chǔ)上，通過海上適應(yīng)性訓(xùn)練熟悉船體搖擺、顛簸、振動條件下的技術(shù)操作要領(lǐng)，掌握患者、固定裝備和操作者的三方固定方法，可以強(qiáng)化海上操作行為的準(zhǔn)確性和安全性，降低職業(yè)暴露風(fēng)險。

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

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

3.1.2多目標(biāo)迭代擴(kuò)張路標(biāo)搜索算法

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

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

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

2.討論形成方案。將學(xué)生分為10個小組，以小組為單位進(jìn)行討論，研究制訂相關(guān)方案，方案內(nèi)容包括了解霧霾的嚴(yán)重性、成因、解決措施以及對應(yīng)的英語詞匯。

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

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

經(jīng)hmax評價圖構(gòu)建、消環(huán)和路標(biāo)提取過程后，得到規(guī)劃任務(wù)Π的析取狀態(tài)路標(biāo)集合M。假設(shè)圖中轉(zhuǎn)移邊的代價均相等，則多目標(biāo)迭代擴(kuò)張路標(biāo)搜索算法如圖6所示。下一節(jié)將集中討論如何有效的利用析取狀態(tài)路標(biāo)集合M加速規(guī)劃搜索。

4)更新集合NI、N*；

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

6)提取析取狀態(tài)路標(biāo)集合M={l1,l2,…,ln}。

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

圖3 評價圖中N*集合的一次擴(kuò)張

通過上述步驟1～6，可計算得到目標(biāo)g的析取狀態(tài)路標(biāo)集Mg。為了進(jìn)一步增強(qiáng)路標(biāo)對規(guī)劃搜索過程的控制，需要獲取盡可能多的析取狀態(tài)路標(biāo)對節(jié)點(diǎn)進(jìn)行更準(zhǔn)確的評估。因此，將集合G中的全部目標(biāo)作為上述路標(biāo)提取步驟的輸入，對任意g∈G，建立獨(dú)立的評價圖進(jìn)行計算，最終得到各目標(biāo)的析取狀態(tài)路標(biāo)集合M=∪Mg, ?g∈G。通過實現(xiàn)析取狀態(tài)路標(biāo)對規(guī)劃任務(wù)全部目標(biāo)的覆蓋，引導(dǎo)規(guī)劃搜索過程中各目標(biāo)最短轉(zhuǎn)移路徑的建立，加速規(guī)劃求解。

由于多目標(biāo)迭代擴(kuò)張算法是對評價圖的節(jié)點(diǎn)集合迭代劃分的過程，若評價圖中出現(xiàn)環(huán)路，則該算法可能陷入重復(fù)計算而導(dǎo)致求解失敗。因此，需要對狀態(tài)評價圖進(jìn)行去環(huán)。考慮模型約束對hmax評價圖的影響，設(shè)計了如下時序轉(zhuǎn)移消環(huán)策略：

1)若某時間線的狀態(tài)轉(zhuǎn)移形成一個大的閉環(huán)，則在初始狀態(tài)處進(jìn)行切斷，即刪除轉(zhuǎn)移到初始狀態(tài)的邊；

2)若某時間線的狀態(tài)轉(zhuǎn)移形成局部閉環(huán)，刪除向靠近初始狀態(tài)方向轉(zhuǎn)移的邊。

一個深空探測規(guī)劃任務(wù)為一個四元組Π=，V為狀態(tài)變量集合，C表示約束集，I?V為初始狀態(tài)，G?V為目標(biāo)集[23]。

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

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

圖4 整體閉環(huán)的轉(zhuǎn)移圖消環(huán)

同理，目標(biāo)g2和g3的距離估計值分別為hg2和hg3。綜合各目標(biāo)的評價值，為避免出現(xiàn)節(jié)點(diǎn)過評估的情況，選取其中的最大值作為節(jié)點(diǎn)N的評價值。

圖5 轉(zhuǎn)移圖中局部回退邊消環(huán)

3)提取析取狀態(tài)路標(biāo)l，完成l的代價劃分；

圖6 多目標(biāo)迭代擴(kuò)張路標(biāo)搜索算法

3.2 深空探測器時間線轉(zhuǎn)移路標(biāo)啟發(fā)式規(guī)劃算法

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

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

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

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

(3)

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

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

(4)

析取狀態(tài)路標(biāo)l表示在所有規(guī)劃解中都為真的狀態(tài)集合。由于hmax評價圖中各邊具有相同的代價，節(jié)點(diǎn)N的評價值越低，其包含的析取狀態(tài)路標(biāo)數(shù)量可能就越少，規(guī)劃過程中需要實例化的狀態(tài)數(shù)量可能就越少。因此，在規(guī)劃節(jié)點(diǎn)擴(kuò)展過程中，需計算下一步所有候選節(jié)點(diǎn)的評價值，并選擇其中評價值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。

3.2.2狀態(tài)路標(biāo)增量式更新方法

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

圖7 路標(biāo)增量式更新方法

假設(shè)候選節(jié)點(diǎn)N中新實例化的狀態(tài)為sn，則目標(biāo)g的析取狀態(tài)路標(biāo)集合Mg的動態(tài)更新流程如下：

2)刪除路標(biāo)集合lj；

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

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

3.2.3最大路標(biāo)集合節(jié)點(diǎn)篩選策略

針對搜索空間中的每個候選節(jié)點(diǎn)，狀態(tài)路標(biāo)啟發(fā)式需要分別計算每個節(jié)點(diǎn)中各目標(biāo)對應(yīng)的狀態(tài)路標(biāo)集合，然后取其中最大的代價作為每個候選節(jié)點(diǎn)的啟發(fā)式評價。這種多目標(biāo)綜合評價的模式雖然能夠加強(qiáng)狀態(tài)路標(biāo)對整個搜索過程的控制并提高啟發(fā)式評價的準(zhǔn)確性，但同樣會帶來極大的計算負(fù)擔(dān)。為了平衡狀態(tài)路標(biāo)啟發(fā)式的計算消耗和評價準(zhǔn)確度二者的潛在收益，在規(guī)劃搜索過程中，對候選節(jié)點(diǎn)集合進(jìn)行初步篩選，盡可能地降低需要計算狀態(tài)路標(biāo)集合的節(jié)點(diǎn)數(shù)量。

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

例如，表1中列出了某局部規(guī)劃中所有目標(biāo)的狀態(tài)路標(biāo)集合及各狀態(tài)路標(biāo)集合的代價值。假設(shè)該局部規(guī)劃的所有候選節(jié)點(diǎn)均能夠?qū)崿F(xiàn)一個或多個狀態(tài)路標(biāo)集合中的狀態(tài)路標(biāo)(由于與狀態(tài)路標(biāo)集合無關(guān)的節(jié)點(diǎn)不會影響到狀態(tài)路標(biāo)集合的代價，這里僅考慮能實現(xiàn)狀態(tài)路標(biāo)的候選節(jié)點(diǎn))。由表中數(shù)據(jù)可知，目標(biāo)g1為當(dāng)前局部規(guī)劃中距離估計值最大的目標(biāo)gmax，狀態(tài)路標(biāo)集合Mg1即為Mgmax。表中每一個狀態(tài)路標(biāo)集合都對應(yīng)一個候選節(jié)點(diǎn)集合，該候選節(jié)點(diǎn)集合中的節(jié)點(diǎn)能夠?qū)嵗瘜?yīng)狀態(tài)路標(biāo)集合中的狀態(tài)，即實現(xiàn)對應(yīng)集合內(nèi)的狀態(tài)路標(biāo)。由于所有候選節(jié)點(diǎn)均與一個或多個狀態(tài)路標(biāo)集合相關(guān)，則對表中任意候選節(jié)點(diǎn)進(jìn)行擴(kuò)展必然會引起相關(guān)狀態(tài)路標(biāo)集合中狀態(tài)路標(biāo)的改變，進(jìn)而影響狀態(tài)路標(biāo)集合的代價。然而，候選節(jié)點(diǎn)的啟發(fā)式評價為該節(jié)點(diǎn)中所有狀態(tài)路標(biāo)集合的最大代價，所以若實例化的狀態(tài)不屬于最大狀態(tài)路標(biāo)集合，則不會減少節(jié)點(diǎn)的評價值。例如，節(jié)點(diǎn)nd2中實例化了狀態(tài)路標(biāo)集合Mg2狀態(tài)，但由于最大路標(biāo)集合Mg1中的狀態(tài)路標(biāo)數(shù)量不會減少，所以節(jié)點(diǎn)nd2的評價值不會低于原節(jié)點(diǎn)的評價值。

表1 狀態(tài)路標(biāo)集合代價及對應(yīng)候選節(jié)點(diǎn)示例

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

綜上，深空探測器時間線轉(zhuǎn)移路標(biāo)啟發(fā)式規(guī)劃算法如圖8所示。

圖8 時間線轉(zhuǎn)移路標(biāo)啟發(fā)式規(guī)劃算法

4 仿真校驗

為驗證深空探測器時間線轉(zhuǎn)移路標(biāo)啟發(fā)式算法的性能，在EUROPA2的基礎(chǔ)上分別對時間線hmax啟發(fā)式規(guī)劃算法和時間線轉(zhuǎn)移路標(biāo)啟發(fā)式規(guī)劃算法進(jìn)行實現(xiàn)，并構(gòu)建火星車測試場景對上述兩種規(guī)劃算法進(jìn)行仿真測試。

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

表2 火星車測試場景詳細(xì)模型信息

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

圖12 規(guī)劃效率提升對比圖

仿真測試環(huán)境為：Windows 7 64位操作系統(tǒng)，i3-2350M CPU，主頻2.30GHz，內(nèi)存4.00 GB。圖中的所有數(shù)據(jù)均為使用同等環(huán)境下原算法的計算結(jié)果減去兩種啟發(fā)式算法的結(jié)果得到的差值。

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

礦區(qū)內(nèi)V-04、V-38、VI-09、VI-11、VI-16、VI-17、VI-20、VI-218個礦體為前5年開采礦體。

圖9 規(guī)劃時長差對比圖

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

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

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

圖10 規(guī)劃步數(shù)差對比圖

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

圖11 節(jié)點(diǎn)擴(kuò)展與非節(jié)點(diǎn)擴(kuò)展步數(shù)的減少量對比圖

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

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

5 結(jié)論

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