基于知識圖譜的深空探測器任務規(guī)劃建模

王 鑫，趙清杰，徐 瑞

（1.北京理工大學 計算機學院，北京 100081；2.北京理工大學 宇航學院，北京 100081；3.深空自主導航與控制工信部重點實驗室，北京 100081）

引 言

深空探測器自主性的首要表現(xiàn)是能夠自主規(guī)劃任務，根據(jù)要求選擇所要執(zhí)行的活動，自主分配資源和時間，使得探測器能夠完成相應的任務[1-3]。對任務規(guī)劃進行知識表示是實現(xiàn)探測器任務規(guī)劃前提。王曉暉等[4]采用基于時間線的方法對深空探測器的約束進行簡化。朱麗穎等[5]基于PDDL（Planning Domain Definition Language）將活動的時間信息、資源信息和活動之間的約束關系等信息進行建模。吳坤等[6]通過在MA-PDDL中加入連續(xù)的規(guī)劃元素對動態(tài)環(huán)境下多智能體協(xié)作問題進行建模。Fier等[7]采用有限域狀態(tài)變量對MA-PDDL（Multi-Agent Planning Domain Definition Language，MA-PDDL）中規(guī)劃任務進行簡潔表示。

知識圖譜[8-9]是人工智能的一個重要分支，它將復雜的知識領域通過數(shù)據(jù)挖掘、信息處理、知識計量和圖形繪制顯示出來，目前在金融[10]、醫(yī)療[11]、政務[12]等領域得到了廣泛的應用。知識圖譜的基本組成是一個<實體–關系–實體>三元組，以及實體及其相關屬性–值，實體間通過關系相互聯(lián)結，構成網(wǎng)狀的知識結構。鑒于傳統(tǒng)任務規(guī)劃表示方法的缺點和知識圖譜的優(yōu)點，本文對復雜的多智能體深空該探測器采用知識圖譜對其進行知識表示。

1 多智能體深空探測器任務規(guī)劃領域知識分析

多智能體深空探測器主要是智能體之間通過采用各智能體間的通訊、合作、協(xié)調(diào)、調(diào)度、管理及控制來表達深空探測器系統(tǒng)的結構、功能和特性。建立合適的任務規(guī)劃模型，對智能體進行知識表示是實現(xiàn)多智能體探測器任務規(guī)劃的重要前提。但是深空探測系統(tǒng)具有復雜的約束和較大的規(guī)劃空間，而且深空環(huán)境不確定，人類對天體的認知尚淺，對深空探測的任務規(guī)劃進行知識表示是非常困難的。

多智能體深空探測器任務規(guī)劃需要表達的基本要素有探測器子系統(tǒng)、星上資源和約束條件，多智能體探測器每個智能體節(jié)點具有柔性系統(tǒng)、導航系統(tǒng)、制導系統(tǒng)、姿態(tài)系統(tǒng)、推進系統(tǒng)、相機系統(tǒng)、熱控系統(tǒng)、通信系統(tǒng)和數(shù)據(jù)存儲系統(tǒng)等。每個系統(tǒng)涉及的動作如表1所示。星上資源主要包括可耗盡資源和非可耗盡資源。其中，可耗盡資源是指可以通過一定的手段重新獲得資源；非可耗盡資源是指資源有限，資源消耗完后相關系統(tǒng)無法運行。約束關系主要有有限資源、持續(xù)時間、活動并發(fā)性、計算資源約束。多智能體深空探測器任務規(guī)劃的部分狀態(tài)及其含義如表2所示，部分基本動作及其含義如表3所示。

表1 多智能體深空探測器系統(tǒng)及動作Table 1 Multi-agent deep space probe systems and actions

表2 多智能體深空探測器的狀態(tài)及其描述Table 2 States and descriptions of multi-agent space probe

表3 多智能體深空探測器系統(tǒng)基本動作及其描述Table 3 Basic actions and descriptions of multi-agent space probe

2 多智能體深空探測器任務規(guī)劃知識圖譜構建

針對深空探測器任務規(guī)劃的特點，本文提出采用知識圖譜對其進行知識表示。為便于描述，首先給出以下幾個定義。

定義1智能體是指深空探測器的節(jié)點。深空探測器可以由多個節(jié)點構成，本文以3個節(jié)點探測器作為示例。

定義2深空探測器任務規(guī)劃領域模型是用數(shù)學方法對深空探測器著陸過程的抽象，用一個四元組表示，Σ=(O,S,A,C)。O是系統(tǒng)中所有對象的集合，S是系統(tǒng)中所有可能出現(xiàn)的狀態(tài)集合，A是智能體可能執(zhí)行的動作集合，C是對探測器規(guī)劃時的約束條件集合。

定義3知識圖譜中的實體表示深空探測器的3個節(jié)點及節(jié)點上的系統(tǒng)設備。

定義4知識圖譜中的屬性表示深空探測器系統(tǒng)的狀態(tài)和動作。

定義5知識圖譜中的關系表示系統(tǒng)設備之間以及設備和其所具有的狀態(tài)及動作之間的關系。

知識圖譜的構建由知識抽取[13]、知識融合和知識加工3部分構成，構建流程如圖1所示。

圖1 多智能體深空探測器知識圖譜構建流程圖Fig.1 Flow chart of constructing knowledge graph of multi-agent deep space detector

2.1 知識抽取

知識抽取包括實體抽取、屬性抽取和關系抽取3部分。多智能體深空探測設備的知識抽取是指從文本數(shù)據(jù)中提取出智能體上系統(tǒng)設備名字、設備狀態(tài)和動作，以及它們之間的關系。

2.1.1 實體抽取

實體抽取也稱為命名實體識別（Named Entity Recognition，NER），是指從文本數(shù)據(jù)集中自動識別出命名實體。多智能體深空探測器的柔性附著需要經(jīng)歷主減速段、柔性展開段、協(xié)同減速段、避障決策段和最終附著段5個階段，不同階段探測器執(zhí)行不同的任務，某些系統(tǒng)設備隨著執(zhí)行的任務發(fā)生相應的變化。針對探測器系統(tǒng)動態(tài)變化這個特點，本文構建基于門控循環(huán)單元模型（Gated Recurrent Unit，GRU）的序列模型對多智能體深空探測器進行實體抽取，流程如圖2所示。3個智能體節(jié)點均具有計算設備，而且GRU的計算量Flops相對較小，因此采用分布式在線訓練GRU模型。

圖2 深空探測器實體抽取流程圖Fig.2 Entity extraction flow chart of deep space detector

智能體上的系統(tǒng)不同時刻會有不同的狀態(tài)，某個時間段內(nèi)的數(shù)據(jù)連接在一起構成一個時序數(shù)據(jù)，采用GRU對其進行特征提取，最后將特征圖和其對應的標簽一起訓練分類器。新的歷史數(shù)據(jù)在特征提取之后，通過分類器預測其實體標簽。在用GRU進行特征提取時，輸入輸出公式如式（1）～（4）所示

其中：St表示智能體在t 時刻的基本狀態(tài)向量；Ht?1表示前一隱層的狀態(tài)；?表示卷積，⊙ 表示元素相乘；W 表示權重；b 表示偏置；σ [·]表示logistic sigmoid函數(shù)；Zt表示t 時刻更新門的狀態(tài)；rt表示t時刻重置門的狀態(tài)。

2.1.2 關系抽取

關系抽取[14]是從文本中抽取系統(tǒng)設備之間的關系以及系統(tǒng)設備及其狀態(tài)和動作之間的關系。本文采用Att-BiLSTM[15]對表2所示的關系進行抽取。Att-BiLSTM的結構如圖3所示。Att-BiLSTM相較于GRU需要更多的計算量，雖然3個智能體設備均具有計算資源，但計算量有限，因此對Att-BiLSTM采用離線訓練。

圖3 Att-BiLSTM網(wǎng)絡結構圖Fig.3 Network structure of Att-BiLSTM

Att-BiLSTM由輸入層、Embedding層、LSTM層、Attention層和輸出層5部分構成。輸入層是描述探測器智能體的句子，用(x1,x2,···,xr)表示，Embedding層將句子中的每一個詞映射成一個固定長度的向量，然后LSTM層利用雙向LSTM對Embedding向量計算，在通過Attention層對雙向LSTM的結果進行加權，最后輸出層輸出探測器系統(tǒng)設備之間、系統(tǒng)設備及其所處的狀態(tài)和動作之間的關系。在關系抽取時，Attention層生成一個權重向量，為卷積層提取的詞匯分配不同大小的權重，這些詞匯與對應的權重相乘，可以在迭代過程中將詞匯級特征合并為句子級的特征，節(jié)省網(wǎng)絡的推理的時間以及計算資源。Attention層的計算方法如式（5）～（7）所示，采用Softmax對提取的向量進行分類，如公式（8）～（9）所示

2.1.3 屬性抽取

屬性抽取是指從文本數(shù)據(jù)中抽取出探測器系統(tǒng)設備的狀態(tài)和動作。本文采用ReNoun[16]方法對表2和表3所示的狀態(tài)和動作進行抽取，流程如圖4所示。

圖4 屬性抽取流程圖Fig.4 Attribute extraction flow chart

2.2 知識融合

多智能體深空探測器的知識抽取可以獲取實體、關系和屬性等知識要素，但是這些數(shù)據(jù)之間的關系是扁平化的、缺乏層次性和邏輯性，需要進行知識融合。知識圖譜的知識融合[17]包括實體鏈接和知識合并兩部分。

實體鏈接是指從文本中抽取得到的實體對象，將其鏈接到知識庫中對應的正確實體對象的操作，首先根據(jù)給定的實體指稱項從知識庫中選出一組候選實體對象，然后通過相似度計算將指稱項鏈接到正確的實體對象。例如多個系統(tǒng)具有開機和關機的動作，開機和關機就是實體指稱項，通過漢明距離（Hamming distance）計算它們與每個系統(tǒng)之間的相似性，選出相似性最高的系統(tǒng)與其進行匹配。但是在匹配過程中，可能因為系統(tǒng)設備名稱相同而產(chǎn)生歧義，通過實體消歧，將其與正確的設備進行匹配。此外，可能存在多個指稱對應同一實體的問題，通過共指消解進行處理。

知識合并主要包含兩部分，即合并外部知識庫和合并關系數(shù)據(jù)庫。合并外部知識庫是指將外部知識庫融合到本地知識庫，即是將深空探測器的外部數(shù)據(jù)庫與構建的本地知識庫進行數(shù)據(jù)層和模式層的融合。對于關系數(shù)據(jù)庫合并，采用資源描述框架進行融合。

2.3 知識加工

通過知識提取和知識融合，可以得到關于多智能體深空探測器任務規(guī)劃的基本事實表示，但是要最終獲得結構化、網(wǎng)絡化的知識體系，還需要本體構建以及知識推理對知識進行加工。

2.3.1 本體構建

本體是同一領域內(nèi)的不同主題之間進行交流的語義基礎，是樹狀結構，相鄰層次的節(jié)點（概念）之間有嚴格的“IsA”關系。在知識圖譜中，本體位于模式層，用于描述概念層次體系，是知識庫中知識的概念模板。

以數(shù)據(jù)驅動的自動化方式構建本體，包含3個階段。

1）實體并列關系相似度計算

實體并列關系相似度計算是考察任意兩個給定實體屬于同一類的指標測度，相似度越高，表明這兩個實體越有可能屬于同一語義類別。本文采用相關性聚類對實體并列關系的相似度進行計算。如式（10）～（12）所示

2）實體上下位關系抽取

實體上下位關系抽取即確定實體的屬性。深空探測器的設備采用字符串表示，而字符串又可以理解為一種集合，因此采用Dice系數(shù)來度量屬性的相似度

其中：S和T表示集合；|S|和|T|分別表示集合的個數(shù)；|S∩T|表示S和T的交集。

3）本體的生成

主要任務是對各層次得到的概念進行聚類，并對其進行語義類的標定（為該類中的實體指定一個或多個公共上位詞）。

2.3.2 知識推理

知識推理[18]是指從知識庫中已有的實體關系數(shù)據(jù)出發(fā)，進行計算及推理，建立實體間的新關聯(lián)，從而拓展和豐富知識網(wǎng)絡。由于深空環(huán)境不確定，多智體深空探測器在著陸過程中可能出現(xiàn)一些突發(fā)情況，比如某個智能體節(jié)點或者某個系統(tǒng)設備出現(xiàn)故障，或者探測器在運行過程中發(fā)現(xiàn)其它星體或者障礙物，此時探測器系統(tǒng)設備或者探測器與其它星體或障礙物之間存在一些隱藏關系，通過進行知識推理可以挖掘出這些隱藏關系，豐富對探測器任務規(guī)劃的知識，可以實現(xiàn)探測器更好的運行。本文基于張量神經(jīng)網(wǎng)絡（Neural Tensor Network，NTN）[19]進行知識推理，結構如圖5所示。

圖5 NTN神經(jīng)張量模型結構圖Fig.5 Network structure of NTN

3 實驗結果與分析

對于深空探測器本文以3個節(jié)點為基準，每個節(jié)點視為一個智能體，每個智能體以相機、數(shù)據(jù)存儲設備、太陽能充電器等設備以及每個設備所處的狀態(tài)和執(zhí)行的操作作為實體進行示例構建知識圖譜。

本實驗環(huán)境為ubuntu18.04，GPU顯卡為GeForce GTX 1 080，深度學習框架為PyTorch，CUDA10.1?；贕RU的序列模型的超參數(shù)如表4所示。Att-BiLSTM的超參數(shù)如表5所示。NTN模型的超參數(shù)如表6所示。知識提取實驗結果如圖6所示。

表4 GRU序列模型超參數(shù)Table 4 GRU sequence model hyperparameters

表5 Att-BiLSTM模型超參數(shù)Table 5 Att-BiLSTM hyperparameters

表6 NTN模型超參數(shù)Table 6 NTN model hyperparameters

本文以探測器智能體的部分設備進行示例。通過圖6可以看出通過知識抽取可以提取出探測器的節(jié)點以及節(jié)點上的設備如相機、數(shù)據(jù)存儲設備、燃料等實體。

圖6 知識提取結果圖Fig.6 The result of knowledge extraction

通過知識提取和知識融合獲得的實驗結果如表7所示。通過表7可以看出通過采用知識融合對提取的知識進行實體和關系之間的一一對應，例如，可以得到探測器距離著陸點具有1 km，探測器的著陸速度為13.5 m/s等。構建的知識圖譜整體結構如圖7所示，采用neo4j[20]對知識圖譜進行保存，保存格式為json格式。

圖7 多智能體深空探測器任務規(guī)劃知識圖譜示意圖Fig.7 Schematic diagram of the knowledge graph of multi-agent deep space detector mission planning

表7 多智能體探測器知識融合Table 7 Multi-agent detector knowledge fusion

復雜的約束關系是深空探測器規(guī)劃知識表示中的重要部分，本文以時間約束為例進行說明。深空探測器的大部分動作都無法瞬時完成，需要持續(xù)一定的時間。每個動作在執(zhí)行過程中都有自己的開始時間、持續(xù)時間和結束時間。此外，動作的持續(xù)時間會受探測器所處的狀態(tài)影響，可以將其分為動態(tài)時間和靜態(tài)時間。在構建知識圖譜時，將動作的持續(xù)時間作為動作的屬性，并且靜態(tài)時間添加標識符“static_taction”，動態(tài)時間添加標識符“dynamic_taction”，對動作持續(xù)時間有影響的因素添加標識符“A_effect_action”，其中A表示影響因素，action表示深空探測器的動作。以探測器的姿態(tài)轉動作為示例，結果如圖8所示。

圖8 姿態(tài)轉動時間約束示意圖Fig.8 Schematic diagram of attitude rotation time constraint

MA-PDDL采用通常采用一階邏輯或命題邏輯等形式化語言來描述系統(tǒng)狀態(tài)，通過狀態(tài)的遷移來表示動作，在建立探測器的任務規(guī)劃模型時，采用領域文件和問題文件進行描述。領域文件的定義如圖9所示，問題文件的定義如圖10所示。

圖9 領域描述的BNF定義Fig.9 BNF definition of domain description

圖10 問題描述的BNF定義Fig.10 BNF definition of problem description

通過圖7與圖9和圖10進行對比可以看出，MAPDDL需要人工根據(jù)先驗知識提前設計出領域文件和問題文件，無法簡單、直觀的對真實深空環(huán)境任務進行表示，而且深空環(huán)境存在不確定性，探測器時刻處于動態(tài)變化中，當出現(xiàn)意外情況時需要等待地面人工的指導，無法對任務進行實時的、精確的表示。

4 結 論

面對不確定的深空環(huán)境和復雜的多智能體深空探測系統(tǒng)，本文構建知識圖譜對其進行知識表示。該方法不僅可以全面直觀地展示出柔性多智能體之間的關系，而且面對不確定的深空環(huán)境，可以通過知識推理自動地挖掘探測器各系統(tǒng)設備之間、探測器與深空環(huán)境之間的關系，通過與傳統(tǒng)的MA-PDDL方法進行對比，本文提出的方法在不需要地面人工干預的情況下，可以對真實的情況建模，為后續(xù)進行任務規(guī)劃提供了較為精確的知識表示，更有助于探測器進行任務規(guī)劃，提高探測器成功著陸可能性。此外該方法的知識表示形式存儲為json格式，可以靈活地運用于各種任務規(guī)劃方法中。