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

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

引 言

深空探測器自主任務(wù)規(guī)劃技術(shù)是解決遠(yuǎn)距離探測器自主運行問題的一項關(guān)鍵技術(shù)[1-4]。由于深空距離遠(yuǎn)、外部環(huán)境復(fù)雜且不確定性強、科學(xué)目標(biāo)的突現(xiàn)性等特點，傳統(tǒng)的地面控制方法已經(jīng)逐漸無法滿足深空探測的需求[5-7]，需要探測器在在軌運行過程中，根據(jù)對空間環(huán)境的感知和認(rèn)識及其本身的能力和狀態(tài)，利用智能規(guī)劃理論技術(shù)，依據(jù)一段時間內(nèi)的任務(wù)目標(biāo)，對若干可供選擇的活動或狀態(tài)及所建模的約束進行推理，自動地生成一組時間有序活動或狀態(tài)序列來支持探測器在未來一段時間內(nèi)的自主運行[8-10]。探測器系統(tǒng)復(fù)雜，且存在約束類型多、子系統(tǒng)耦合性強、運行環(huán)境不確知等特點，傳統(tǒng)規(guī)劃模型難以準(zhǔn)確描述系統(tǒng)的功能特性，從而降低了探測器在軌自主任務(wù)規(guī)劃的可靠性[11-13]。針對自主任務(wù)規(guī)劃中系統(tǒng)模型難于精確描述、規(guī)劃效率低等難點，尋求一種新的合適的建模方法成為深空探測器自主任務(wù)規(guī)劃中亟待解決的問題之一。

深空探測器自主任務(wù)規(guī)劃需要對問題進行更簡潔、明確的描述。通過將探測器各子系統(tǒng)的行為表示為時間的函數(shù)，對任務(wù)規(guī)劃中涉及的時間約束關(guān)系進行統(tǒng)一處理。并且子系統(tǒng)的狀態(tài)轉(zhuǎn)換由若干事件組成，需要定義在一定的時間區(qū)間上[14]。如相機拍照前需要進行一系列的準(zhǔn)備事件:主通道開啟、大容量上電等。狀態(tài)轉(zhuǎn)移能夠表示時間線上狀態(tài)之間的邏輯關(guān)系，并且轉(zhuǎn)移的持續(xù)時間會對問題的規(guī)模和局部搜索技術(shù)產(chǎn)生影響，為了應(yīng)對規(guī)劃執(zhí)行時的不確定性，需要在規(guī)劃過程中對狀態(tài)轉(zhuǎn)移進行顯式處理。

知識建模是知識推理的前提。Fike和Nilsson提出的斯坦福研究委員會問題求解器（STanford Research Institute Problem Solve，STRIPS）[15]由于引入了STRIPS操作符而使得規(guī)劃可以非常容易地進行描述和操作。但STRIPS的表達(dá)能力存在很大的局限性，它不能描述具有一定持續(xù)時間的動作，不能描述動作間復(fù)雜的約束關(guān)系等。O-Plan和IxTeT規(guī)劃器采用動作的概念對物理系統(tǒng)進行描述，并且能夠?qū)r間約束進行處理[16-17]。然而，它們一般默認(rèn)只考慮在動作開始點和結(jié)束點上需要滿足的約束，這樣的處理方式可能會影響到模型的準(zhǔn)確性。APSI（Advanced Planning and Scheduling Initiative） 規(guī)劃系統(tǒng)，作為“火星快車”任務(wù)中自主規(guī)劃系統(tǒng)的開發(fā)框架，能夠有效地處理任務(wù)規(guī)劃中復(fù)雜的時間、資源及參數(shù)約束[18-19]。但是，規(guī)劃器中并沒有涉及狀態(tài)轉(zhuǎn)換時間的處理問題。在EUROPA（Extensible Universal Remote Operations Planning Architecture）規(guī)劃系統(tǒng)中，將各子系統(tǒng)的活動與狀態(tài)等統(tǒng)一采用token的形式進行描述，并引入時間線的概念，直觀地描述token之間的時間約束關(guān)系[20-21]。模型中采用統(tǒng)一的形式對動作、狀態(tài)、目標(biāo)等概念進行描述，在描述探測器時并不能真實地體現(xiàn)各子系統(tǒng)狀態(tài)或活動信息。任務(wù)規(guī)劃領(lǐng)域知識建模技術(shù)的發(fā)展趨向于更合理準(zhǔn)確全面的描述實際問題[22-25]，實際系統(tǒng)狀態(tài)變化靈活、功能高度復(fù)雜的特性，往往導(dǎo)致模型并不能很好地描述。

本文針對規(guī)劃問題中系統(tǒng)間狀態(tài)轉(zhuǎn)換頻繁及狀態(tài)間切換并非瞬時完成的特點，引入了擴展?fàn)顟B(tài)的概念。建立基于擴展?fàn)顟B(tài)的任務(wù)規(guī)劃模型對各子系統(tǒng)復(fù)雜功能進行描述，設(shè)計基于擴展?fàn)顟B(tài)的任務(wù)規(guī)劃算法，對問題搜索空間進行削減，實現(xiàn)降低規(guī)劃步數(shù)，提高規(guī)劃效率的目標(biāo)。最后通過仿真計算，驗證了模型的合理性及算法的有效性。

1 狀態(tài)知識表示

狀態(tài)是一個不斷變化的系統(tǒng)的條件描述，它表示被控系統(tǒng)在一段時間內(nèi)的行為表現(xiàn)。為了便于對本文中任務(wù)規(guī)劃方法進行描述，首先給出狀態(tài)知識表示中幾個基本的概念。

定義1.狀態(tài)變量SV（State Variable）是建模時對于系統(tǒng)知識的抽象結(jié)果，可定義為一個四元組的形式。

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

定義2.狀態(tài)S是狀態(tài)變量在某一個時間點或某一時間區(qū)間上的取值，可用一個四元組進行表示。

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

定義3.狀態(tài)時間線STL（State Time Line）用于表示系統(tǒng)狀態(tài)變量在規(guī)劃周期內(nèi)取值（即狀態(tài)）隨時間的變化情況。每一條狀態(tài)時間線都是系統(tǒng)在規(guī)劃周期內(nèi)的連續(xù)狀態(tài)序列，即

規(guī)劃問題的一個可行解就是一個狀態(tài)時間線的集合。定義4.運行規(guī)則表示狀態(tài)之間或者狀態(tài)和資源之間的約束關(guān)系。

定義5.基于狀態(tài)時間線規(guī)劃問題P可表示為一個二元組為

其中:SV表示狀態(tài)變量的集合；OP表示涉及SV中變量的運行規(guī)則的集合。

定義6.規(guī)劃解Ω的形式為一個時間線集合。

其中:STLk為一條狀態(tài)時間線，是一個在時間上連續(xù)的狀態(tài)序列。

STL0,STL1,···,STLk-1,STLk為滿足規(guī)劃問題目標(biāo)及狀態(tài)間同步性約束，并且在時間關(guān)系上并行的狀態(tài)序列集合。

2 擴展?fàn)顟B(tài)知識描述

由定義可以得到，每一條狀態(tài)時間線都由連續(xù)排列的狀態(tài)序列組成，用于描述系統(tǒng)狀態(tài)隨時間的變化情況。而狀態(tài)序列的連續(xù)排列表示系統(tǒng)狀態(tài)的轉(zhuǎn)換是瞬時完成的，即狀態(tài)轉(zhuǎn)換事件定義在某個時間點上，并不考慮該事件本身對規(guī)劃過程產(chǎn)生的影響，如圖1所示。但是，對于實際任務(wù)規(guī)劃系統(tǒng)來說，每個狀態(tài)轉(zhuǎn)換描述一個事件集合，即狀態(tài)轉(zhuǎn)換不可能瞬時完成，需要一定的持續(xù)時間，并且可能同樣涉及資源、變量等約束關(guān)系。因此，若是在規(guī)劃中忽略狀態(tài)轉(zhuǎn)換帶來的影響，可能會致使規(guī)劃結(jié)果無法適用于實際系統(tǒng)，導(dǎo)致執(zhí)行過程的失敗。

圖1 狀態(tài)轉(zhuǎn)換示意圖Fig.1 Illustration of state transitions

為了更準(zhǔn)確地描述規(guī)劃問題，確保規(guī)劃結(jié)果成功執(zhí)行，本文在原有模型的基礎(chǔ)上，引入過渡狀態(tài)的概念，補充對于轉(zhuǎn)換事件的建模，如圖2所示。過渡狀態(tài)鏈接同一時間線上兩個不同的狀態(tài)，用于描述不同狀態(tài)之間的轉(zhuǎn)換活動。例如，相機進行圖像獲取前需要進行一系列準(zhǔn)備動作，如主通道開啟、大容量上電等。由于這一系列動作持續(xù)時間短、事件數(shù)量多且不可避免，在規(guī)劃中需要對這一類事件進行處理。若是對所有事件都進行描述并在規(guī)劃過程中搜索，會大大增加問題的搜索空間，降低規(guī)劃的效率。于是，考慮這些事件持續(xù)時間短、與其他時間線狀態(tài)約束少等特性，特引入過渡狀態(tài)這一概念，將這一系列事件作為一個整體對其進行描述。既能滿足對模型描述的需求，也不會給規(guī)劃搜索帶來太大負(fù)擔(dān)。同時，過渡狀態(tài)應(yīng)具有下列特點:

1）過渡狀態(tài)的約束關(guān)系中包含較少的邏輯約束。

2）過渡狀態(tài)的持續(xù)時間較短或與同時間線狀態(tài)相比較短。

3）過渡狀態(tài)在整個規(guī)劃周期中所占時間比例一般較小。

圖2 過渡狀態(tài)示意圖Fig.2 Illustration of transition states

在同一時間線上，每個過渡狀態(tài)的后繼狀態(tài)是唯一確定的。為了達(dá)到削減規(guī)劃搜索空間的目的，本文將過渡狀態(tài)與其后繼狀態(tài)進行組合，并通過時間約束關(guān)系將二者進行綁定（過渡狀態(tài)的結(jié)束時間與其綁定的后繼狀態(tài)的起始時間相同），作為搜索空間中規(guī)劃操作新的基本對象。考慮過渡狀態(tài)的約束關(guān)系中邏輯約束數(shù)量較少，這表明過渡狀態(tài)被挑選添加到規(guī)劃中的概率會小于其后繼狀態(tài)的概率。

定義7.擴展?fàn)顟B(tài)κ可表示為一個六元組的形式為

其中:N表示擴展?fàn)顟B(tài)的名稱；Υ表示后繼狀態(tài)為S′的過渡狀態(tài)的集合；ts，te，d分別表示κ的起始時間、結(jié)束時間和持續(xù)時間。

通過擴展?fàn)顟B(tài)κ的定義可以看出，過渡狀態(tài)并不獨立出現(xiàn)在問題的搜索空間中，而是被視為類似于κ的一種屬性參與規(guī)劃。另外，擴展?fàn)顟B(tài)κ的定義并沒有對原有問題的搜索空間進行擴展，合理有效地解決了過渡狀態(tài)可能引起的搜索空間急劇膨脹的問題。針對上述擴展?fàn)顟B(tài)定義，本文設(shè)計了基于擴展?fàn)顟B(tài)任務(wù)規(guī)劃算法，能夠在合理描述實際物理系統(tǒng)的同時，較為高效地實現(xiàn)問題規(guī)劃。

3 基于擴展?fàn)顟B(tài)規(guī)劃算法

深空探測器具有多子系統(tǒng)并行、運行約束復(fù)雜等特點，狀態(tài)空間搜索會導(dǎo)致搜索空間指數(shù)爆炸。本文采用規(guī)劃空間搜索策略，針對擴展?fàn)顟B(tài)模型定義過渡狀態(tài)挑選策略，設(shè)計基于擴展?fàn)顟B(tài)規(guī)劃算法實現(xiàn)縮減搜索空間、提高規(guī)劃效率的目的。

3.1 缺陷類型設(shè)計

規(guī)劃空間規(guī)劃方法主要是搜索缺陷、挑選缺陷和解決缺陷3部分反復(fù)迭代的過程。每迭代一步需要進行一次約束傳播檢測，驗證規(guī)劃操作的合理性，并在必要時可以進行回溯。整個規(guī)劃是對初始部分規(guī)劃不斷迭代求精的過程，直到搜索出規(guī)劃問題的一個可行解。

在規(guī)劃空間搜索中，缺陷是指導(dǎo)致當(dāng)前部分規(guī)劃不一致的潛在因素。規(guī)劃搜索就是不斷地檢測當(dāng)前部分規(guī)劃中存在的不一致的因素，并逐步進行解決的過程。考慮到缺陷的語義和深空探測器系統(tǒng)復(fù)雜的運行約束，這里定義了下述5類缺陷:

1）擴展?fàn)顟B(tài)缺陷:如果當(dāng)前部分規(guī)劃中存在一個或多個擴展?fàn)顟B(tài)前提條件未得到滿足，則該部分規(guī)劃存在擴展?fàn)顟B(tài)缺陷。

2）未綁定過渡狀態(tài)缺陷:如果當(dāng)前部分規(guī)劃中存在一個或多個未確定過渡狀態(tài)的擴展?fàn)顟B(tài)，則該部分規(guī)劃存在未綁定過渡狀態(tài)缺陷。

3）變量缺陷:如果當(dāng)前部分規(guī)劃中存在包含一個或多個未賦值變量的擴展?fàn)顟B(tài)，則該部分規(guī)劃存在變量缺陷。

4）互斥缺陷:如果當(dāng)前部分規(guī)劃中存在同一時間線，時間區(qū)間存在交叉的擴展?fàn)顟B(tài)，則該部分規(guī)劃存在互斥缺陷。

5）資源缺陷:如果當(dāng)前部分規(guī)劃中資源分配不合理，如擴展?fàn)顟B(tài)的資源分配超出該資源的總量，則該部分規(guī)劃存在資源缺陷。

解決缺陷過程中需要對挑選出的狀態(tài)進行實例化，而狀態(tài)的實例化又會向當(dāng)前候選部分規(guī)劃中引入缺陷。如果一個候選規(guī)劃中不存在缺陷，那么該候選規(guī)劃就是規(guī)劃問題的一個可行解。

3.2 過渡狀態(tài)挑選策略

每個擴展?fàn)顟B(tài)對應(yīng)一個可能的過渡狀態(tài)集合，針對這一特點，本文設(shè)計了下列4種過渡狀態(tài)挑選策略:

1）約束導(dǎo)向策略，與擴展?fàn)顟B(tài)相關(guān)的約束決定它綁定的過渡狀態(tài)。

2）最小缺陷導(dǎo)向策略，首先選擇引入缺陷最少的過渡狀態(tài)，如果有兩個及以上的過渡狀態(tài)滿足最佳選擇，它們將按任意順序進行選擇或用其他方法進行評估。

3）資源導(dǎo)向策略，首先選擇涉及資源類型最少的過渡狀態(tài)，如果有兩個及以上的過渡狀態(tài)滿足最佳選擇，它們將按任意順序進行選擇或用其他方法進行評估。

4）隨機策略，如果對于過渡狀態(tài)選擇順序沒有特定需求，則按隨機策略進行選擇。

為了獲取合適的過渡狀態(tài)，本文對上述策略進行組合，并且采用資源導(dǎo)向及隨機策略作為二次評估標(biāo)準(zhǔn)，保證了搜索策略的完備性。具體方法如圖3所示。

圖3 過渡狀態(tài)搜索流程Fig.3 The process of transition state searching

3.3 規(guī)劃搜索算法

本文的規(guī)劃算法采用規(guī)劃空間搜索的策略，在其架構(gòu)的基礎(chǔ)上，根據(jù)擴展?fàn)顟B(tài)的定義和結(jié)構(gòu)特點，同時考慮上述過渡狀態(tài)選擇策略，設(shè)計了表1所示的基于擴展?fàn)顟B(tài)的任務(wù)規(guī)劃算法。該算法能夠有效地減少由于算法缺陷挑選順序不合理和引發(fā)的回溯，提高算法的效率。

表1 基于擴展?fàn)顟B(tài)規(guī)劃算法Table 1 Planning algorithm based on extensible states

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

為了驗證算法的有效性，建立了一個描述深空探測器領(lǐng)域的模型，并采用本文提出的算法進行了仿真驗證。選取美國航空航天局在“深空1號”上已在軌驗證的規(guī)劃算法Europa算法進行比較，通過與Europa算法仿真結(jié)果進行對比，驗證了該算法能夠提高規(guī)劃搜索的效率，進一步證明了該模型的合理性和有效性。

本文對深空探測器任務(wù)規(guī)劃系統(tǒng)進行建模。每個狀態(tài)變量描述一個探測器子系統(tǒng)，如推進子系統(tǒng)，太陽帆板子系統(tǒng)等。同時，將科學(xué)載荷亦作為子系統(tǒng)進行建模，每一種載荷視為一個子系統(tǒng)模型，并將載荷的操作作為規(guī)劃問題的目標(biāo)，例如導(dǎo)航相機的拍照操作。在實現(xiàn)目標(biāo)獲取規(guī)劃解的過程中，主要處理下列幾種約束關(guān)系:

1）狀態(tài)同步約束:例如在拍照前，探測器的姿態(tài)需要指向所要拍攝的目標(biāo)，對地通信時同樣需要姿態(tài)系統(tǒng)保證一定的指向。

2）變量約束:探測器機動的角度應(yīng)與下一時刻姿態(tài)的指向相對應(yīng)。

3）資源約束:能源的最大值是一定的，任何時刻，狀態(tài)消耗能源的總和不能超過能源最大值等。

考慮上述建模方法和約束關(guān)系，該模型包括11個子系統(tǒng)，共包含56個狀態(tài)模型和92個約束關(guān)系。

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

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

由于過渡狀態(tài)的引入，對于同一個規(guī)劃問題能夠有效地削減問題搜索空間，減少規(guī)劃過程中的搜索對象，提高規(guī)劃搜索的效率。通過仿真結(jié)果可以看出，采用擴展?fàn)顟B(tài)算法的處理時間要低于采用Europa算法的處理時間，且隨著問題中所含目標(biāo)數(shù)量的增多，后者運行時間增加的速率亦超過前者。同時，過渡狀態(tài)對一系列狀態(tài)轉(zhuǎn)換事件進行統(tǒng)一描述，可以減少規(guī)劃迭代步數(shù)，從而進一步降低規(guī)劃的時間消耗，使得擴展?fàn)顟B(tài)算法相比Europa算法能夠較快獲得規(guī)劃結(jié)果。從仿真結(jié)果可得，基于擴展?fàn)顟B(tài)算法的規(guī)劃步數(shù)也全部低于Europa算法，如圖5所示，可以看出，針對同一領(lǐng)域中不同的問題，前者的規(guī)劃步數(shù)均近似等于后者的一半。仿真試驗結(jié)果表明，基于擴展?fàn)顟B(tài)規(guī)劃算法能夠減少無效的規(guī)劃步數(shù)，降低規(guī)劃搜索時間，有效地提高算法的求解速度。

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

5 結(jié) 論

本文針對深空探測器任務(wù)規(guī)劃中系統(tǒng)功能復(fù)雜、狀態(tài)轉(zhuǎn)換頻繁且并非瞬時完成等問題，引入過渡狀態(tài)的定義，并在此基礎(chǔ)上提出了擴展?fàn)顟B(tài)的概念，縮減了問題搜索空間，優(yōu)化了規(guī)劃搜索過程。通過分析擴展?fàn)顟B(tài)的結(jié)構(gòu)特點，設(shè)計了過渡狀態(tài)挑選策略，并提出基于擴展?fàn)顟B(tài)的規(guī)劃搜索算法。最后針對深空探測器任務(wù)規(guī)劃系統(tǒng)進行建模仿真，并選用Europa算法進行對比實驗。數(shù)值仿真結(jié)果驗證了本文的算法能夠有效地減少規(guī)劃過程中的規(guī)劃步數(shù)，提高任務(wù)規(guī)劃的效率。