金 顥，徐 瑞，崔平遠(yuǎn)，朱圣英

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

引 言

深空探測(cè)器自主任務(wù)規(guī)劃技術(shù)是解決遠(yuǎn)距離探測(cè)器自主運(yùn)行問(wèn)題的一項(xiàng)關(guān)鍵技術(shù)[1]。由于探測(cè)器系統(tǒng)功能復(fù)雜以及外界環(huán)境不確定等特性，經(jīng)典的規(guī)劃技術(shù)很難直接應(yīng)用到深空探測(cè)器任務(wù)規(guī)劃中。探測(cè)器在軌運(yùn)行過(guò)程中，需要具備能夠?qū)σ幌盗锌茖W(xué)目標(biāo)進(jìn)行規(guī)劃的能力，即根據(jù)空間環(huán)境的感知及探測(cè)器本身的能力和狀態(tài)，運(yùn)用自主規(guī)劃技術(shù)在約束和資源模型的基礎(chǔ)上進(jìn)行推理，生成一組有序的活動(dòng)序列。同時(shí)，當(dāng)深空探測(cè)器面臨執(zhí)行長(zhǎng)期任務(wù)的挑戰(zhàn)時(shí)，復(fù)雜和動(dòng)態(tài)的外部環(huán)境會(huì)成為實(shí)現(xiàn)任務(wù)目標(biāo)的阻礙[2-3]。這些都需要可靠的自主規(guī)劃方法，以避免在缺乏對(duì)環(huán)境充分認(rèn)知的情況下做出導(dǎo)致任務(wù)失敗的決策。

深空探測(cè)器自主任務(wù)規(guī)劃技術(shù)的研究和發(fā)展主要具有如下幾方面的意義：①系統(tǒng)的自主性可使深空探測(cè)器在整個(gè)任務(wù)過(guò)程中減少地面干預(yù)，從而降低航天任務(wù)費(fèi)用以及對(duì)航天網(wǎng)絡(luò)的需求；②系統(tǒng)自身具備自主能力，可以進(jìn)一步應(yīng)對(duì)空間任務(wù)中的不確定性，增加任務(wù)的可靠性；③系統(tǒng)通過(guò)自主規(guī)劃技術(shù)能夠?qū)Ω鞣N資源進(jìn)行合理分配和利用，提高任務(wù)的科學(xué)回報(bào)。

可擴(kuò)展的通用遠(yuǎn)程操作規(guī)劃架構(gòu)（Extensible Universal Remote Operations Planning Architecture，EUROPA）中，自主規(guī)劃模型能夠?qū)γ鞔_的時(shí)間概念進(jìn)行描述，算法使用基于約束的規(guī)劃范式對(duì)問(wèn)題進(jìn)行求解[4]。但是，其核心的搜索算法采用深度優(yōu)先的搜索方式，缺乏合適的搜索引導(dǎo)策略，會(huì)在一定程度上影響規(guī)劃的效率。“羅塞塔”任務(wù)中，探測(cè)器首次實(shí)現(xiàn)了與彗星的交會(huì)并最終成功登陸彗星。在任務(wù)執(zhí)行周期內(nèi)，探測(cè)器使用科學(xué)規(guī)劃（Master Science Plan，MSP）軟件制定的觀測(cè)方案，保證了在動(dòng)態(tài)外部環(huán)境中科學(xué)任務(wù)目標(biāo)的成功實(shí)現(xiàn)[5-6]。由于探測(cè)器長(zhǎng)時(shí)間處于未知且動(dòng)態(tài)變化的環(huán)境中，MSP更注重制定靈活的策略來(lái)保障探測(cè)器的安全性，從而在算法搜索技術(shù)方面并未有太過(guò)深入的研究。王丹等研究了載人航天器上自主任務(wù)規(guī)劃飛行程序的設(shè)計(jì)[7]；王曉暉等對(duì)深空探測(cè)器的約束簡(jiǎn)化與動(dòng)態(tài)不確定因素進(jìn)行了研究[8]。但在實(shí)際飛行過(guò)程中，探測(cè)器復(fù)雜的系統(tǒng)功能及科學(xué)任務(wù)突發(fā)性對(duì)任務(wù)規(guī)劃技術(shù)提出了更高的要求，使得尋求一種更有效的規(guī)劃搜索算法成為深空探測(cè)器自主任務(wù)規(guī)劃中亟待解決的問(wèn)題之一。

本文針對(duì)探測(cè)器系統(tǒng)并行及約束耦合的特點(diǎn)，采用基于時(shí)間線的問(wèn)題建模方法?？紤]系統(tǒng)內(nèi)部約束復(fù)雜及狀態(tài)切換的特性，建立狀態(tài)轉(zhuǎn)移圖描述各子系統(tǒng)狀態(tài)轉(zhuǎn)移路徑方案，設(shè)計(jì)了狀態(tài)轉(zhuǎn)移代價(jià)函數(shù)。然后，在轉(zhuǎn)移圖的基礎(chǔ)上提出了規(guī)劃節(jié)點(diǎn)啟發(fā)式評(píng)估策略，對(duì)問(wèn)題搜索空間進(jìn)行削減，實(shí)現(xiàn)減少無(wú)效迭代次數(shù)，提高規(guī)劃效率的目標(biāo)。最后通過(guò)仿真實(shí)驗(yàn)，驗(yàn)證了啟發(fā)式搜索算法的有效性。

1 時(shí)間線規(guī)劃知識(shí)表示

為了便于對(duì)任務(wù)規(guī)劃方法進(jìn)行描述，首先給出時(shí)間線模型中的幾個(gè)基本的概念。

定義1.狀態(tài)變量是建模時(shí)對(duì)于系統(tǒng)知識(shí)的抽象結(jié)果，可定義為一個(gè)四元組：SV=。

其中：N為該狀態(tài)變量的名稱；V是該狀態(tài)變量的取值空間，即狀態(tài)變量的值域，為一個(gè)非空集合；T為該狀態(tài)變量各取值之間的轉(zhuǎn)換規(guī)則或約束；D表示該狀態(tài)變量各取值的持續(xù)時(shí)間。

定義2.狀態(tài)是狀態(tài)變量在某一個(gè)時(shí)間點(diǎn)或某一時(shí)間區(qū)間上的取值，可用一個(gè)四元組進(jìn)行表示：s=。

其中：Ns為該狀態(tài)的名稱；ts、te、d分別為該狀態(tài)的起始時(shí)間、結(jié)束時(shí)間和持續(xù)時(shí)間，并且均表示為區(qū)間的形式，即ts=[s,s′]，te=[e,e′]，d=[d,d′]，用于應(yīng)對(duì)執(zhí)行過(guò)程中所可能出現(xiàn)的不確定性問(wèn)題。

定義3.狀態(tài)時(shí)間線用于表示系統(tǒng)狀態(tài)變量在規(guī)劃周期內(nèi)取值（即狀態(tài)）隨時(shí)間的變化情況。每一條狀態(tài)時(shí)間線都是系統(tǒng)在規(guī)劃周期內(nèi)的連續(xù)狀態(tài)序列，即STL={s0,s1,…,sn-1,sn}。

2 狀態(tài)轉(zhuǎn)移代價(jià)計(jì)算方法

根據(jù)時(shí)間線知識(shí)表示方法，利用狀態(tài)轉(zhuǎn)移圖來(lái)描述每個(gè)狀態(tài)變量自身狀態(tài)變化的方式以及實(shí)現(xiàn)這種狀態(tài)改變所需要滿足的條件。每個(gè)狀態(tài)變量都有對(duì)應(yīng)的一個(gè)轉(zhuǎn)移圖，圖中的點(diǎn)為狀態(tài)，點(diǎn)之間的邊表示轉(zhuǎn)移規(guī)則且每條邊上標(biāo)有狀態(tài)轉(zhuǎn)移需要滿足的約束集合。例如，圖1表示了在火星車測(cè)試用例中設(shè)備時(shí)間線的狀態(tài)轉(zhuǎn)移圖。

圖1 火星車設(shè)備時(shí)間線狀態(tài)轉(zhuǎn)移圖Fig.1 A state transition graph for an Instrument timeline

狀態(tài)轉(zhuǎn)移圖中任意2個(gè)狀態(tài)s1和s2之間可能存在多條轉(zhuǎn)移路徑，計(jì)算所有路徑的代價(jià)，并選擇其中最低的代價(jià)作為狀態(tài)s1到s2的轉(zhuǎn)移代價(jià)cost(s1,s2)。同一時(shí)間線上兩個(gè)狀態(tài)間的轉(zhuǎn)移代價(jià)由兩部分構(gòu)成：一部分為實(shí)際的狀態(tài)轉(zhuǎn)移次數(shù)所帶來(lái)的代價(jià)；另一部分為每次轉(zhuǎn)移的約束條件所引發(fā)的代價(jià)計(jì)算。不失一般性，在本文中每次狀態(tài)轉(zhuǎn)移所需代價(jià)為1，而轉(zhuǎn)移約束的代價(jià)計(jì)算則是一個(gè)迭代的過(guò)程。

假設(shè)狀態(tài)轉(zhuǎn)移圖中兩相鄰狀態(tài)s1到s2的一個(gè)轉(zhuǎn)移約束為狀態(tài)s3，其中s1和s2屬于時(shí)間線TL1，s3屬于時(shí)間線TL2，時(shí)間線TL2上存在初始狀態(tài)s0。則實(shí)現(xiàn)轉(zhuǎn)移約束s3的代價(jià)即為時(shí)間線TL2上狀態(tài)s0到s3的轉(zhuǎn)移代價(jià)。同理，狀態(tài)s0到s3的轉(zhuǎn)移代價(jià)計(jì)算同樣涉及轉(zhuǎn)移次數(shù)代價(jià)和轉(zhuǎn)移約束代價(jià)。如此反復(fù)迭代計(jì)算，最終能夠得到實(shí)現(xiàn)轉(zhuǎn)移約束s3的代價(jià)。而狀態(tài)s1到s2轉(zhuǎn)移約束代價(jià)為實(shí)現(xiàn)其轉(zhuǎn)移約束集合中所有轉(zhuǎn)移約束的代價(jià)和。計(jì)算出狀態(tài)轉(zhuǎn)移圖中每?jī)蓚€(gè)相鄰狀態(tài)之間的轉(zhuǎn)移代價(jià)后，則任意兩狀態(tài)之間的轉(zhuǎn)移代價(jià)可由轉(zhuǎn)移路徑上所有相鄰狀態(tài)的轉(zhuǎn)移代價(jià)求和得到。

圖2 狀態(tài)轉(zhuǎn)移代價(jià)計(jì)算Fig.2 The procedure of compute-cost algorithm

計(jì)算轉(zhuǎn)移圖中任意兩狀態(tài)之間轉(zhuǎn)移代價(jià)的算法如圖2所示。針對(duì)上述狀態(tài)轉(zhuǎn)移代價(jià)計(jì)算方法，本文設(shè)計(jì)了基于狀態(tài)轉(zhuǎn)移圖的啟發(fā)式任務(wù)規(guī)劃算法，能夠在合理描述實(shí)際物理系統(tǒng)的同時(shí)，較為高效地實(shí)現(xiàn)問(wèn)題規(guī)劃。

3 基于狀態(tài)轉(zhuǎn)移圖的啟發(fā)式規(guī)劃算法

深空探測(cè)器具有多子系統(tǒng)并行、運(yùn)行約束復(fù)雜等特點(diǎn)，狀態(tài)空間搜索會(huì)導(dǎo)致搜索空間指數(shù)爆炸。本文采用規(guī)劃空間搜索方法，針對(duì)轉(zhuǎn)移圖代價(jià)計(jì)算特點(diǎn)形成啟發(fā)式評(píng)價(jià)策略。規(guī)劃空間搜索是搜索缺陷、挑選缺陷和解決缺陷3部分反復(fù)迭代的過(guò)程。每迭代一步需要進(jìn)行一次約束傳播檢測(cè)，驗(yàn)證規(guī)劃操作的合理性，并在必要時(shí)可以進(jìn)行回溯，直到搜索出規(guī)劃問(wèn)題的一個(gè)可行解。

狀態(tài)轉(zhuǎn)移圖能夠?qū)γ總€(gè)狀態(tài)變量?jī)?nèi)部的轉(zhuǎn)移規(guī)則進(jìn)行描述，從而狀態(tài)轉(zhuǎn)移代價(jià)計(jì)算較經(jīng)典規(guī)劃的啟發(fā)式而言更適合于時(shí)間線描述框架。在規(guī)劃過(guò)程中，規(guī)劃器不斷實(shí)例化目標(biāo)狀態(tài)g∈G到當(dāng)前部分規(guī)劃，并將g的約束作為子目標(biāo)加入目標(biāo)集合G{g}，直到目標(biāo)集合為空時(shí)，算法就找到了該問(wèn)題的一個(gè)規(guī)劃解。目標(biāo)g通常存在析取約束集，即當(dāng)前部分規(guī)劃存在多個(gè)可擴(kuò)展候選節(jié)點(diǎn)，使用狀態(tài)轉(zhuǎn)移代價(jià)計(jì)算能夠?qū)λ阉鬟^(guò)程中規(guī)劃節(jié)點(diǎn)的展開(kāi)進(jìn)行評(píng)價(jià)，刪除不必要的目標(biāo)約束集合，實(shí)現(xiàn)搜索空間剪枝，加快搜索效率的目的。

假設(shè)狀態(tài)s屬于目標(biāo)g的一個(gè)候選約束集合，則實(shí)例化s到當(dāng)前部分規(guī)劃的代價(jià)計(jì)算存在2類情況。

1）將狀態(tài)s與時(shí)間線TL上另一滿足約束的狀態(tài)s'相融合，即

2）在時(shí)間線TL上添加狀態(tài)s

第1類情況通過(guò)狀態(tài)融合實(shí)現(xiàn)目標(biāo)約束，由于對(duì)當(dāng)前部分規(guī)劃不作任何改變，所以代價(jià)為0。第2類情況需要對(duì)當(dāng)前時(shí)間線上的狀態(tài)分布進(jìn)行改變，所以需要計(jì)算新的轉(zhuǎn)移代價(jià)進(jìn)行評(píng)估。在搜索過(guò)程中，每次迭代都伴隨著目標(biāo)集合的更新，動(dòng)態(tài)計(jì)算目標(biāo)代價(jià)會(huì)帶來(lái)大量的計(jì)算耗時(shí)。而問(wèn)題的初始狀態(tài)集合在規(guī)劃迭代的過(guò)程中不發(fā)生任何變化。從而選用時(shí)間線TL上的初始狀態(tài)s0進(jìn)行第2類情況的代價(jià)計(jì)算，將初始狀態(tài)到狀態(tài)s的轉(zhuǎn)移代價(jià)作為添加狀態(tài)s的評(píng)價(jià)值。實(shí)例化狀態(tài)s的代價(jià)計(jì)算為

則實(shí)現(xiàn)目標(biāo)g該候選約束集合的代價(jià)為

通過(guò)對(duì)目標(biāo)g不同候選約束集合的代價(jià)進(jìn)行計(jì)算，最終選擇代價(jià)最低的約束集作為下一步要實(shí)現(xiàn)的子目標(biāo)集加入到目標(biāo)集合中，完成對(duì)規(guī)劃節(jié)點(diǎn)的擴(kuò)展。通過(guò)轉(zhuǎn)移圖，每條時(shí)間線能夠找到多條由初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)移路徑，而啟發(fā)式對(duì)所有可能的轉(zhuǎn)移路徑進(jìn)行評(píng)價(jià)并挑選出轉(zhuǎn)移代價(jià)最低的路徑作為下一次迭代的輸入。

本文的規(guī)劃算法采用規(guī)劃空間搜索的形式，在其架構(gòu)的基礎(chǔ)上，根據(jù)狀態(tài)轉(zhuǎn)移圖的定義和結(jié)構(gòu)特點(diǎn)，同時(shí)考慮上述啟發(fā)式搜索策略，設(shè)計(jì)了圖3所示的基于狀態(tài)轉(zhuǎn)移圖的啟發(fā)式規(guī)劃算法。該算法能夠有效地減少由于節(jié)點(diǎn)擴(kuò)展不合理引發(fā)的節(jié)點(diǎn)回溯，提高算法的效率。

圖3 啟發(fā)式規(guī)劃算法Fig.3 Heuristic planning algorithm

4 仿真計(jì)算結(jié)果及分析

為了驗(yàn)證算法的有效性，建立了一個(gè)描述火星車領(lǐng)域的模型，并采用本文提出的算法進(jìn)行了仿真驗(yàn)證。通過(guò)與EUROPA2算法仿真結(jié)果進(jìn)行對(duì)比，驗(yàn)證了該算法能夠有效提高規(guī)劃搜索的效率。

本文在火星車領(lǐng)域中構(gòu)建了10個(gè)測(cè)試用例。火星車上攜帶了采樣設(shè)備對(duì)火星土壤進(jìn)行采樣，并置入自身的質(zhì)譜儀中對(duì)土壤成分進(jìn)行分析。同時(shí)火星車上還備有相機(jī)實(shí)現(xiàn)對(duì)火星表面地形數(shù)據(jù)收集。在該測(cè)試場(chǎng)景中，火星車模型總共需要對(duì)11個(gè)狀態(tài)及資源時(shí)間線進(jìn)行建模，包括：采樣設(shè)備、電池電量、數(shù)據(jù)存儲(chǔ)及相機(jī)等。并且需要對(duì)狀態(tài)同步約束、變量約束及資源約束進(jìn)行描述，例如通信時(shí)同樣需要姿態(tài)系統(tǒng)保證一定的指向，狀態(tài)消耗能源的總和不能超過(guò)能源最大值等。

考慮上述建模方法和約束形式，該模型包括9個(gè)設(shè)備或子系統(tǒng)（表1）。各并行子系統(tǒng)或設(shè)備間約束相互耦合，共包含32個(gè)狀態(tài)模型和48個(gè)約束關(guān)系。

表1 火星車領(lǐng)域模型Table 1 Summary of subsystems in Mars Rover domain

本文選取深空探測(cè)器領(lǐng)域中10個(gè)不同的問(wèn)題進(jìn)行了仿真測(cè)試，結(jié)果如圖4～6所示。由于測(cè)試問(wèn)題按序號(hào)順序所包含的目標(biāo)的數(shù)量是逐漸增多的，故兩種算法的計(jì)算處理時(shí)間是遞增的。并且，為避免出現(xiàn)偶然性，本文的測(cè)試用例中對(duì)每個(gè)問(wèn)題統(tǒng)計(jì)其10次計(jì)算的平均值。

通過(guò)仿真結(jié)果可以看出：狀態(tài)轉(zhuǎn)移啟發(fā)式算法的處理時(shí)間要低于采用EUROPA2算法的處理時(shí)間，且曲線的走勢(shì)表明，隨著問(wèn)題所含任務(wù)目標(biāo)數(shù)量的增加，EUROPA2算法運(yùn)行時(shí)間的增長(zhǎng)速率要高于后者。對(duì)于復(fù)雜任務(wù)而言，更多的任務(wù)目標(biāo)要求規(guī)劃器能夠在搜索中做出更明智的決策。EUROPA2在搜索中采用深度優(yōu)先策略，雖然保證了算法的完全性，但是對(duì)無(wú)效節(jié)點(diǎn)過(guò)多的擴(kuò)展大大降低了搜索的效率（如圖6所示）。

本文的啟發(fā)式算法通過(guò)計(jì)算狀態(tài)轉(zhuǎn)移代價(jià)，完成對(duì)部分無(wú)效搜索節(jié)點(diǎn)的剪枝，既能夠保證規(guī)劃的準(zhǔn)確性，又減少了不必要的回溯步數(shù)。如圖5所示，啟發(fā)式算法所需的規(guī)劃步數(shù)全部低于EUROPA2求解所用步數(shù)，進(jìn)一步證明了本文設(shè)計(jì)的啟發(fā)式能夠有效地保證規(guī)劃的效率，提高問(wèn)題求解的速度。

圖4 運(yùn)行時(shí)間結(jié)果曲線Fig.4 Computational results of runtime curves

圖5 規(guī)劃步數(shù)結(jié)果曲線Fig.5 Computational results of planning steps

圖6 擴(kuò)展節(jié)點(diǎn)結(jié)果曲線圖Fig.6 Experimental results on explored plans

5 結(jié) 論

本文針對(duì)深空探測(cè)器任務(wù)規(guī)劃中多系統(tǒng)并行、功能復(fù)雜且約束耦合等特點(diǎn)，采用時(shí)間線知識(shí)表示框架對(duì)系統(tǒng)及任務(wù)進(jìn)行建模。通過(guò)分析時(shí)間線的結(jié)構(gòu)特點(diǎn)，引入狀態(tài)轉(zhuǎn)移圖結(jié)構(gòu)，并設(shè)計(jì)了狀態(tài)轉(zhuǎn)移代價(jià)計(jì)算方法。結(jié)合規(guī)劃空間搜索策略，提出了基于狀態(tài)轉(zhuǎn)移圖的啟發(fā)式規(guī)劃算法，實(shí)現(xiàn)了削減搜索空間、優(yōu)化規(guī)劃搜索的目的。最后選用EUROPA2算法進(jìn)行對(duì)比實(shí)驗(yàn)，并針對(duì)火星車任務(wù)規(guī)劃系統(tǒng)進(jìn)行建模仿真，仿真結(jié)果驗(yàn)證了本文的啟發(fā)式算法能夠有效地對(duì)搜索空間進(jìn)行剪枝，減少不必要的規(guī)劃步數(shù)，提高了任務(wù)規(guī)劃的效率。