基于知识图谱的深空探测器任务规划建模

王 鑫，赵清杰，徐 瑞

（1.北京理工大学 计算机学院，北京 100081；2.北京理工大学 宇航学院，北京 100081；3.深空自主导航与控制工信部重点实验室，北京 100081）

引 言

深空探测器自主性的首要表现是能够自主规划任务，根据要求选择所要执行的活动，自主分配资源和时间，使得探测器能够完成相应的任务[1-3]。对任务规划进行知识表示是实现探测器任务规划前提。王晓晖等[4]采用基于时间线的方法对深空探测器的约束进行简化。朱丽颖等[5]基于PDDL（Planning Domain Definition Language）将活动的时间信息、资源信息和活动之间的约束关系等信息进行建模。吴坤等[6]通过在MA-PDDL中加入连续的规划元素对动态环境下多智能体协作问题进行建模。Fier等[7]采用有限域状态变量对MA-PDDL（Multi-Agent Planning Domain Definition Language，MA-PDDL）中规划任务进行简洁表示。

知识图谱[8-9]是人工智能的一个重要分支，它将复杂的知识领域通过数据挖掘、信息处理、知识计量和图形绘制显示出来，目前在金融[10]、医疗[11]、政务[12]等领域得到了广泛的应用。知识图谱的基本组成是一个<实体–关系–实体>三元组，以及实体及其相关属性–值，实体间通过关系相互联结，构成网状的知识结构。鉴于传统任务规划表示方法的缺点和知识图谱的优点，本文对复杂的多智能体深空该探测器采用知识图谱对其进行知识表示。

1 多智能体深空探测器任务规划领域知识分析

多智能体深空探测器主要是智能体之间通过采用各智能体间的通讯、合作、协调、调度、管理及控制来表达深空探测器系统的结构、功能和特性。建立合适的任务规划模型，对智能体进行知识表示是实现多智能体探测器任务规划的重要前提。但是深空探测系统具有复杂的约束和较大的规划空间，而且深空环境不确定，人类对天体的认知尚浅，对深空探测的任务规划进行知识表示是非常困难的。

多智能体深空探测器任务规划需要表达的基本要素有探测器子系统、星上资源和约束条件，多智能体探测器每个智能体节点具有柔性系统、导航系统、制导系统、姿态系统、推进系统、相机系统、热控系统、通信系统和数据存储系统等。每个系统涉及的动作如表1所示。星上资源主要包括可耗尽资源和非可耗尽资源。其中，可耗尽资源是指可以通过一定的手段重新获得资源；非可耗尽资源是指资源有限，资源消耗完后相关系统无法运行。约束关系主要有有限资源、持续时间、活动并发性、计算资源约束。多智能体深空探测器任务规划的部分状态及其含义如表2所示，部分基本动作及其含义如表3所示。

表1 多智能体深空探测器系统及动作Table 1 Multi-agent deep space probe systems and actions

表2 多智能体深空探测器的状态及其描述Table 2 States and descriptions of multi-agent space probe

表3 多智能体深空探测器系统基本动作及其描述Table 3 Basic actions and descriptions of multi-agent space probe

2 多智能体深空探测器任务规划知识图谱构建

针对深空探测器任务规划的特点，本文提出采用知识图谱对其进行知识表示。为便于描述，首先给出以下几个定义。

定义1智能体是指深空探测器的节点。深空探测器可以由多个节点构成，本文以3个节点探测器作为示例。

定义2深空探测器任务规划领域模型是用数学方法对深空探测器着陆过程的抽象，用一个四元组表示，Σ=(O,S,A,C)。O是系统中所有对象的集合，S是系统中所有可能出现的状态集合，A是智能体可能执行的动作集合，C是对探测器规划时的约束条件集合。

定义3知识图谱中的实体表示深空探测器的3个节点及节点上的系统设备。

定义4知识图谱中的属性表示深空探测器系统的状态和动作。

定义5知识图谱中的关系表示系统设备之间以及设备和其所具有的状态及动作之间的关系。

知识图谱的构建由知识抽取[13]、知识融合和知识加工3部分构成，构建流程如图1所示。

图1 多智能体深空探测器知识图谱构建流程图Fig.1 Flow chart of constructing knowledge graph of multi-agent deep space detector

2.1 知识抽取

知识抽取包括实体抽取、属性抽取和关系抽取3部分。多智能体深空探测设备的知识抽取是指从文本数据中提取出智能体上系统设备名字、设备状态和动作，以及它们之间的关系。

2.1.1 实体抽取

实体抽取也称为命名实体识别（Named Entity Recognition，NER），是指从文本数据集中自动识别出命名实体。多智能体深空探测器的柔性附着需要经历主减速段、柔性展开段、协同减速段、避障决策段和最终附着段5个阶段，不同阶段探测器执行不同的任务，某些系统设备随着执行的任务发生相应的变化。针对探测器系统动态变化这个特点，本文构建基于门控循环单元模型（Gated Recurrent Unit，GRU）的序列模型对多智能体深空探测器进行实体抽取，流程如图2所示。3个智能体节点均具有计算设备，而且GRU的计算量Flops相对较小，因此采用分布式在线训练GRU模型。

图2 深空探测器实体抽取流程图Fig.2 Entity extraction flow chart of deep space detector

智能体上的系统不同时刻会有不同的状态，某个时间段内的数据连接在一起构成一个时序数据，采用GRU对其进行特征提取，最后将特征图和其对应的标签一起训练分类器。新的历史数据在特征提取之后，通过分类器预测其实体标签。在用GRU进行特征提取时，输入输出公式如式（1）～（4）所示

其中：St表示智能体在t 时刻的基本状态向量；Ht−1表示前一隐层的状态；∗表示卷积，⊙ 表示元素相乘；W 表示权重；b 表示偏置；σ [·]表示logistic sigmoid函数；Zt表示t 时刻更新门的状态；rt表示t时刻重置门的状态。

2.1.2 关系抽取

关系抽取[14]是从文本中抽取系统设备之间的关系以及系统设备及其状态和动作之间的关系。本文采用Att-BiLSTM[15]对表2所示的关系进行抽取。Att-BiLSTM的结构如图3所示。Att-BiLSTM相较于GRU需要更多的计算量，虽然3个智能体设备均具有计算资源，但计算量有限，因此对Att-BiLSTM采用离线训练。

图3 Att-BiLSTM网络结构图Fig.3 Network structure of Att-BiLSTM

Att-BiLSTM由输入层、Embedding层、LSTM层、Attention层和输出层5部分构成。输入层是描述探测器智能体的句子，用(x1,x2,···,xr)表示，Embedding层将句子中的每一个词映射成一个固定长度的向量，然后LSTM层利用双向LSTM对Embedding向量计算，在通过Attention层对双向LSTM的结果进行加权，最后输出层输出探测器系统设备之间、系统设备及其所处的状态和动作之间的关系。在关系抽取时，Attention层生成一个权重向量，为卷积层提取的词汇分配不同大小的权重，这些词汇与对应的权重相乘，可以在迭代过程中将词汇级特征合并为句子级的特征，节省网络的推理的时间以及计算资源。Attention层的计算方法如式（5）～（7）所示，采用Softmax对提取的向量进行分类，如公式（8）～（9）所示

2.1.3 属性抽取

属性抽取是指从文本数据中抽取出探测器系统设备的状态和动作。本文采用ReNoun[16]方法对表2和表3所示的状态和动作进行抽取，流程如图4所示。

图4 属性抽取流程图Fig.4 Attribute extraction flow chart

2.2 知识融合

多智能体深空探测器的知识抽取可以获取实体、关系和属性等知识要素，但是这些数据之间的关系是扁平化的、缺乏层次性和逻辑性，需要进行知识融合。知识图谱的知识融合[17]包括实体链接和知识合并两部分。

实体链接是指从文本中抽取得到的实体对象，将其链接到知识库中对应的正确实体对象的操作，首先根据给定的实体指称项从知识库中选出一组候选实体对象，然后通过相似度计算将指称项链接到正确的实体对象。例如多个系统具有开机和关机的动作，开机和关机就是实体指称项，通过汉明距离（Hamming distance）计算它们与每个系统之间的相似性，选出相似性最高的系统与其进行匹配。但是在匹配过程中，可能因为系统设备名称相同而产生歧义，通过实体消歧，将其与正确的设备进行匹配。此外，可能存在多个指称对应同一实体的问题，通过共指消解进行处理。

知识合并主要包含两部分，即合并外部知识库和合并关系数据库。合并外部知识库是指将外部知识库融合到本地知识库，即是将深空探测器的外部数据库与构建的本地知识库进行数据层和模式层的融合。对于关系数据库合并，采用资源描述框架进行融合。

2.3 知识加工

通过知识提取和知识融合，可以得到关于多智能体深空探测器任务规划的基本事实表示，但是要最终获得结构化、网络化的知识体系，还需要本体构建以及知识推理对知识进行加工。

2.3.1 本体构建

本体是同一领域内的不同主题之间进行交流的语义基础，是树状结构，相邻层次的节点（概念）之间有严格的“IsA”关系。在知识图谱中，本体位于模式层，用于描述概念层次体系，是知识库中知识的概念模板。

以数据驱动的自动化方式构建本体，包含3个阶段。

1）实体并列关系相似度计算

实体并列关系相似度计算是考察任意两个给定实体属于同一类的指标测度，相似度越高，表明这两个实体越有可能属于同一语义类别。本文采用相关性聚类对实体并列关系的相似度进行计算。如式（10）～（12）所示

2）实体上下位关系抽取

实体上下位关系抽取即确定实体的属性。深空探测器的设备采用字符串表示，而字符串又可以理解为一种集合，因此采用Dice系数来度量属性的相似度

其中：S和T表示集合；|S|和|T|分别表示集合的个数；|S∩T|表示S和T的交集。

3）本体的生成

主要任务是对各层次得到的概念进行聚类，并对其进行语义类的标定（为该类中的实体指定一个或多个公共上位词）。

2.3.2 知识推理

知识推理[18]是指从知识库中已有的实体关系数据出发，进行计算及推理，建立实体间的新关联，从而拓展和丰富知识网络。由于深空环境不确定，多智体深空探测器在着陆过程中可能出现一些突发情况，比如某个智能体节点或者某个系统设备出现故障，或者探测器在运行过程中发现其它星体或者障碍物，此时探测器系统设备或者探测器与其它星体或障碍物之间存在一些隐藏关系，通过进行知识推理可以挖掘出这些隐藏关系，丰富对探测器任务规划的知识，可以实现探测器更好的运行。本文基于张量神经网络（Neural Tensor Network，NTN）[19]进行知识推理，结构如图5所示。

图5 NTN神经张量模型结构图Fig.5 Network structure of NTN

3 实验结果与分析

对于深空探测器本文以3个节点为基准，每个节点视为一个智能体，每个智能体以相机、数据存储设备、太阳能充电器等设备以及每个设备所处的状态和执行的操作作为实体进行示例构建知识图谱。

本实验环境为ubuntu18.04，GPU显卡为GeForce GTX 1 080，深度学习框架为PyTorch，CUDA10.1。基于GRU的序列模型的超参数如表4所示。Att-BiLSTM的超参数如表5所示。NTN模型的超参数如表6所示。知识提取实验结果如图6所示。

表4 GRU序列模型超参数Table 4 GRU sequence model hyperparameters

表5 Att-BiLSTM模型超参数Table 5 Att-BiLSTM hyperparameters

表6 NTN模型超参数Table 6 NTN model hyperparameters

本文以探测器智能体的部分设备进行示例。通过图6可以看出通过知识抽取可以提取出探测器的节点以及节点上的设备如相机、数据存储设备、燃料等实体。

图6 知识提取结果图Fig.6 The result of knowledge extraction

通过知识提取和知识融合获得的实验结果如表7所示。通过表7可以看出通过采用知识融合对提取的知识进行实体和关系之间的一一对应，例如，可以得到探测器距离着陆点具有1 km，探测器的着陆速度为13.5 m/s等。构建的知识图谱整体结构如图7所示，采用neo4j[20]对知识图谱进行保存，保存格式为json格式。

图7 多智能体深空探测器任务规划知识图谱示意图Fig.7 Schematic diagram of the knowledge graph of multi-agent deep space detector mission planning

表7 多智能体探测器知识融合Table 7 Multi-agent detector knowledge fusion

复杂的约束关系是深空探测器规划知识表示中的重要部分，本文以时间约束为例进行说明。深空探测器的大部分动作都无法瞬时完成，需要持续一定的时间。每个动作在执行过程中都有自己的开始时间、持续时间和结束时间。此外，动作的持续时间会受探测器所处的状态影响，可以将其分为动态时间和静态时间。在构建知识图谱时，将动作的持续时间作为动作的属性，并且静态时间添加标识符“static_taction”，动态时间添加标识符“dynamic_taction”，对动作持续时间有影响的因素添加标识符“A_effect_action”，其中A表示影响因素，action表示深空探测器的动作。以探测器的姿态转动作为示例，结果如图8所示。

图8 姿态转动时间约束示意图Fig.8 Schematic diagram of attitude rotation time constraint

MA-PDDL采用通常采用一阶逻辑或命题逻辑等形式化语言来描述系统状态，通过状态的迁移来表示动作，在建立探测器的任务规划模型时，采用领域文件和问题文件进行描述。领域文件的定义如图9所示，问题文件的定义如图10所示。

图9 领域描述的BNF定义Fig.9 BNF definition of domain description

图10 问题描述的BNF定义Fig.10 BNF definition of problem description

通过图7与图9和图10进行对比可以看出，MAPDDL需要人工根据先验知识提前设计出领域文件和问题文件，无法简单、直观的对真实深空环境任务进行表示，而且深空环境存在不确定性，探测器时刻处于动态变化中，当出现意外情况时需要等待地面人工的指导，无法对任务进行实时的、精确的表示。

4 结 论

面对不确定的深空环境和复杂的多智能体深空探测系统，本文构建知识图谱对其进行知识表示。该方法不仅可以全面直观地展示出柔性多智能体之间的关系，而且面对不确定的深空环境，可以通过知识推理自动地挖掘探测器各系统设备之间、探测器与深空环境之间的关系，通过与传统的MA-PDDL方法进行对比，本文提出的方法在不需要地面人工干预的情况下，可以对真实的情况建模，为后续进行任务规划提供了较为精确的知识表示，更有助于探测器进行任务规划，提高探测器成功着陆可能性。此外该方法的知识表示形式存储为json格式，可以灵活地运用于各种任务规划方法中。