-
为实现深空探测任务规划知识图模型构建以及自动推理机制,首先根据深空探测器任务规划的领域知识[9-10]给出相关的参数定义如下。
定义1:深空探测器一共
$ m $ 个子系统中,第$ i $ 个子系统的$ n $ 个状态构成子系统状态集合其中:
$s_{i1},s_{i2}, \cdots ,s_{in} ,s_{in} $ 表示深空探测器的该子系统在执行深空探测任务中执行动作之前或者之后自身能够达到的状态,且$1 \leqslant i \leqslant m,m \geqslant 2,n \geqslant 2,i,m,n \in {{N}}$ 。定义2:深空探测器不同子系统能够到达的状态为
$ m $ 个子系统的状态集合,记为定义3:对于
$\forall s_{ij} \in {\boldsymbol{S}}$ ,在到达该状态时都标记一个相对时间戳[8],表示深空探测器从起始时间$\xi_ 0$ 到达该状态的时刻$ {\xi '_{ij}} $ 的相对时刻差值,即其中,
$ i,j $ 均为正整数。定义4:对于
$\forall s_{ij} \in {\boldsymbol{S}}$ ,都有其中:
$ \alpha_{ij} $ 是该状态的名称;$\,\mu_{ij}$ 是该状态所属的子系统;$ \xi _{ij} $ 是该状态的时间戳,$ i,j $ 均为正整数,满足$ 1 \leqslant i \leqslant m,1 \leqslant j \leqslant n $ 。定义5:定义元动作ma(meta action)为深空探测器可执行的最小动作单位,不可再分解。记第
$ i $ 个子系统的第$ u $ 个元动作记为$ a_{iu} $ ,一共$ o $ 个元动作构成集合$\left\{ {a_{i1},a_{i2}, \cdots ,a_{io}} \right\}$ ,$ i,u,o $ 均为正整数。其中任意一个元动作$ a_{iu} $ 可以表示为其中:
$\,\beta_{iu}$ 是该元动作的名称;$\,\mu_{iu}$ 是该元动作所属的子系统;$ r_{iu} $ 是深空探测器执行该元动作时所需资源,包括可再生资源消耗$rc_{iu}$ 和不可再生资源消耗$rc_{iu}$ ;$ t_{iu} $ 是完成该元动作所需要的时间;$ 1 \leqslant i \leqslant m $ ,$ 1 \leqslant u \leqslant o $ ,$ i,u,o $ 均为正整数。定义6:资源约束集合
$R_a $ 包含可再生资源约束$R_c $ 和不可再生资源约束$ R_u $ ;其中可再生约束包含深空探测器可使用最大存储空间$ c_{\max} $ 、最大电量$ e_{\max} $ 等;不可再生约束包含深空探测器携带最大燃料$ f_{\max} $ 等;同时还应当满足任务最长允许执行时间$ t_{\max} $ ,即定义7: 对于
$\forall s_{ij},s_{i'j'} \in S$ ,若$ s_{ij} $ 与$s_{i'j'}$ 存在元动作$ a_{iu} $ ,使得深空探测器得以从状态$ s_{ij} $ 通过执行元动作$ a_{iu} $ 转到状态$s_{i'j'}$ ,那么$ s_{ij} $ 与$s_{i'j'}$ 存在状态转换关系,且元动作$ a_{iu} $ 唯一。即有序二元组$< s_{ij},s_{i'j'} >$ 可唯一确定一个元动作$ a_{iu} $ 。其中,$ 1 \leqslant i,i' \leqslant m,1 \leqslant j,j' \leqslant n $ 。深空探测领域中的所有元动作构成元动作矩阵A,记为
-
综合1.1中的定义,深空探测任务规划问题的解可表示为多个子系统的元动作和状态相间的序列,如表1所示。
子系统 $ \xi_ 1 $ $ \xi _2 $ $ \xi_ 3 $ $ \cdots $ $ \xi_{ z - 2} $ $ \xi_{ z - 1} $ $ \xi_{z }$ $\,\mu_1$ $ s_{11} $ $ a_{11} $ $ s_{12} $ $ \cdots $ $\,\mu_2$ $ s_{21} $ $ a_{21} $ $ \cdots $ $ s_{2(n - 1)} $ $ a_{2o} $ $ s_{2n} $ $ \vdots $ $ \vdots $ $ \vdots $ $ \vdots $ $ \vdots $ $ \vdots $ $ \vdots $ $ \vdots $ $\,\mu_ m$ $ s_{m(n - 1)} $ $ a_{mo} $ $ s_{mn} $ Table 1.Solution to deep space exploration mission planning
其中横向有序集合
$\{ \xi_1,\xi_2, \cdots ,\xi_z\}$ 表示深空探测器在执行任务过程中的时刻,纵向有序集合$\{ \mu_1,\mu_2, \cdots ,\mu_m\}$ 表示子系统。其中$ z $ 为正整数且$ z > 2 $ 。若将其分解为状态时间矩阵
${{\boldsymbol{S}}_{\rm{T}}}$ 与元动作时间矩阵${{\boldsymbol{A}}_{\rm{T}}}$ ,则有其中,
$ m,n,o \geqslant 2 $ ,且$ m,n,o $ 为正整数。对于矩阵
${{\boldsymbol{S}}_{\rm{T}}}$ ,行向量表示不同时间下深空探测器中某一子系统的状态排列,值为0时代表当前状态与上一状态相同;列向量表示同一时刻不同子系统所处的不同状态。对于矩阵${{\boldsymbol{A}}_{\rm{T}}}$ ,行向量表示不同时间下深空探测器中某一子系统所执行的元动作;列向量表示不同的子系统在同样的时刻正在执行的不同元动作。综上,对深空探测任务规划问题的求解转化为求满足资源约束
$R_a $ 和时序关系的动作时间。矩阵${{\boldsymbol{S}}_{\rm{T}}}$ 与${{\boldsymbol{A}}_{\rm{T}}}$ 的求解,即传统规划结果中各子系统应执行的动作序列集合。 -
认知图谱在基于感知的机器学习基础上加入基于认知的符号计算,将数据与知识融合,构建可解释的人工智能用于实现知识的逻辑、推理和决策[10]。本文在文献[11]的基础上提出了深空探测自主任务规划认知图谱的系统框架。该框架主要分为两大部分:
1)深空探测任务规划的知识建模与规则匹配
将深空探测器任务规划的多模态异构数据转换为深空探测器领域知识,根据深空探测器任务规划知识构建三元组数据,抽取与深空探测器任务规划问题相关的实体和关系,并扩展节点及边的属性,汇总深空探测任务规划的语义。通过深空探测器状态与动作的属性关联和关系映射实现状态与动作之间的转换规则约束。
2)深空探测任务规划的认知推理与约束冲突检测
在1)中深空探测领域知识和三元组规则的基础上采用图学习算法展开认知推理,实现深空探测器的自主任务规划探索,生成可行的规划序列解空间,并通过时序分析、约束检验和冲突检测,最终按给定要求进行决策输出。
由此1.2中规划问题的求解可转化为利用图神经网络在所构建的认知图谱知识集上进行自动推理计算并自动输出所有符合任务规划目标的元动作时间矩阵
$ {A_{\rm{T}}} $ ,同时在认知图谱知识集中采用基于边的多重属性权值的算法对资源约束集合$R_a $ 进行冲突检测,最终决策输出目标规划动作序列。 -
用三元组SPO(Subject Predicate Object)[13]知识表示方法描述深空探测器各子系统状态与动作之间的转换关系及时序约束,如式(10)所示
其中:
$ 1 \leqslant i,i' \leqslant m,1 \leqslant j,j' \leqslant n $ ;$ s_{ij} $ 与$s_{i'j'}$ 为深空探测器的可达状态;$ a_{iu} $ 代表深空探测器可执行的动作,该三元组表示在状态$ s_{ij} $ 下执行某元动作$ a_{iu} $ 可到达状态$s_{i'j'}$ ;尖括号表示该三元组具有从$ s_{ij} $ 到$s_{i'j'}$ 的方向。在上述结构化的深空探测知识表述基础上,可用有向图模型
$ G = (E,R,S) $ [12-13]表示深空探测任务规划知识空间,其中$E = \{ \varepsilon_ 1,\varepsilon_ 2, \cdots \varepsilon_ e'\}$ 是状态集合,包含$ e' $ 种不同状态,深空探测器所有子系统的状态集${\boldsymbol S}$ 构成$ G $ 中的点集合;$ R = \{ \gamma_ 1,\gamma_ 1, \cdots ,\gamma_ r'\} $ 是知识库中的动作集合,包含$ r' $ 种不同动作,深空探测器所有子系统的动作集A构成图谱$ G $ 中的边集合,而S则代表深空探测任务规划知识库中的三元组集合。由此,物理系统中的深空探测任务规划问题通过基于矩阵的数学模型转化为图模型,其原理如图1所示。根据定义4和定义5,可将式(10)中的三元组扩展为如式(11)中所示的多元组
将执行动作所受到的资源约束用有向图中两状态节点之间边的多属性权值进行表示,其中,状态节点
$ s_{ij} $ 的属性元组表达为$ (\alpha_{ij},\mu_{ij},\xi_{ij}) $ ,分别代表节点的名称、所属子系统以及进入该状态的时间戳。$ a_{iu} $ 的属性元组表达为$ (\beta_{iu},\mu_{iu},r_{iu},t_{iu}) $ ,分别代表该元动作的名称、深空探测器执行该元动作时所需资源以及完成该元动作所需要的时间。状态节点$s_{i'j'}$ 的属性元组表达为$(\alpha_{i'j'},\mu_{i'j'},\xi_{i'j'})$ ,分别代表节点的名称、所属子系统以及进入该状态的时间戳。得到如图2所示的多属性三元组图模型,可实现深空探测任务规划过程中的规则匹配与知识表达。例如姿态子系统中的三元组<就绪状态,转向目标动作,运行状态>可扩展为多元组<就绪状态,姿态子系统,转向目标,运行状态,姿态子系统,转向目标的资源消耗,转向目标的时间消耗>。在图数据库neo4j[14]中采用三元组存储深空探测任务规划中的知识,由此可得到深空探测自主任务规划认知图谱知识集。用于实现深空探测任务规划问题的知识建模与规则匹配算法的伪代码如表2所示。
Algorithm 1: Create Mission Planning Cognitive Graph for Deep Space Input: SPO sheet spos, Cognition Graph cg, Point Sets in cg ps, Edge Sets in cg es; Output: cg ; 1: build $V_1 \leftarrow \phi ,V_2 \leftarrow \phi$ for saving points temporarily 2: build $ V \leftarrow \phi $ for saving points permanently 3: build $ E \leftarrow \phi $ for saving edges temporarily 4: For $ v $ in cg do: 5: $V_1 \leftarrow V_1 + \{ s_{ij}\} ,V_2 \leftarrow V_2 + \{ s_{i'j'}\}$ 6: End For 7: $V \leftarrow V_1 \cup (V_1 - V_2)$ 8: For $v_{ij}$ in $ V $do: 9: draw $v_{ij}$ in cg representing $s_{ij}$ 10: End For 11: For $\varepsilon_{ iu}$ in $ E $ do: 12: build $v_s \leftarrow v_{ij}$ for the start of ${\rm{ma}}_{iu}$ 13: build $v_e \leftarrow v_{i'j'}$ for the end of ${\rm{ma}}_{iu}$ 14: draw $\varepsilon_{ iu}$ from $v_s$ to $v_e$ representing ${\rm{ma}}_{iu}$ 15: End For Table 2.Multi-attributes triple model in cognitive graph
-
在2.2节的基础上,通过基于关系同构的路径匹配算法[15],在深空探测自主任务规划认知图谱中自动生成从待规划任务的初始状态节点到终止状态节点的基本可行解,再针对图模型中边的多属性值,利用邻居节点聚合的图学习算法对基本可行解进行资源约束检测,从而实现深空探测自主任务规划认知图谱的认知推理过程。
考虑到深空探测器在执行实际的深空探测任务时,不可再生资源约束将无法再次获得,所以在深空探测任务规划问题的解中,
$ {{\boldsymbol{A}}_{\rm{T}}} $ 中的所有元动作构成的集合$ {\boldsymbol{A}}' $ ,将其中的元动作按照时间顺序记为$ \{ a_1,a_2, \cdots , a_k\} $ ,$ k $ 为正整数,则对于$ \forall {a_i} \in {\boldsymbol{A}}' $ ,由公式6能够将元动作属性扩充为$a_i = ({\beta _i},{\mu _i},{c_i},{e_i},{f_i},{t_i}, \cdots )$ ,应当满足约束其中,
$ 1 \leqslant i \leqslant k $ 。考虑到时间消耗掉同样不可获得,在判断过程中与不可再生资源同时判断。为了使得深空探测器在可再生资源不足以支撑接下来的元动作的进行的情况下有能力启动可再生能源的补充程序,定义可再生资源安全阈值
${R_{\rm safe}} = \{ {c_{\rm safe}},{e_{\rm safe}}, {f_{\rm safe}},{t_{\rm safe}}, \cdots \}$ ,对于深空探测任务规划的解,同理其元动作集合A′应当满足约束为了保证在任何情况下都能够满足约束,应当满足约束
深空探测任务规划结果中的解中所有元动作构成的解集
$ A' $ 在深空探测自主任务规划认知图谱上对应相应的边集合$ E = \{ \varepsilon_ 1,\varepsilon_ 2, \cdots \varepsilon_ k,\} $ ,$ k $ 为正整数,即$\{ \gamma_1,\gamma_2, \cdots , \gamma_k\} = \{ \gamma_{\varepsilon1},\gamma_{\varepsilon2}, \cdots ,\gamma _{\varepsilon k}\}$ 。由此,资源约束检验可以表示为深空探测器任务规划时序约束是指当深空探测器达到某一个状态
$s_{\rm ab}$ 需要优先从状态$s_{\rm xy}$ 经过元动作$a_{\rm hl}$ 执行后才能够满足的情况,即$s_{\rm ab}$ 的时间戳$\xi_{\rm ab}$ 、$s_{\rm xy}$ 的时间戳$\xi_{\rm xy}$ 以及$a_{\rm hl}$ 的消耗时间$t_{\rm hl}$ 满足约束深空探测器任务规划时序约束是指当深空探测器达到某一个状态
$s_{\rm ab}$ 需要执行元动作$ a_{\rm hl} $ 或从状态$ s_{\rm xy} $ 执行元动作$ a_{\rm wp} $ 后能够达到状态$s_{\rm gl}$ 的情况,则须满足节点的并联约束,即若深空探测器从状态
$s_{\rm ab}$ 经过元动作$ a_{\rm hl} $ 达到状态$ s_{\rm qv} $ ,紧接着经过元动作$ a_{\rm wp} $ 达到状态$ s_{\rm xy} $ ,则应当满足约束为实现深空探测任务规划的认知推理与多属性权值约束冲突检测算法流程的伪代码如表3所示。
Algorithm 2: Mission Planning in Cognitive Graph with Multi-attribute Constraint Conflict Detection Input: solutions ${S_{\rm T}}$ and ${A_{\rm T}}$, Cognitive Graph cg, capacity maximum constraint $c_{\max }$, electricity maximum constraint $e_{\max}$, fuel maximum constraint $f_{\max}$, time maximum constraint $t_{\max}$; Output: flag of ${S_{\rm T}}$ fs, flag of ${A_{\rm T}}$ fm; 1: ${S_{\rm T}} \leftarrow \phi ,{A_{\rm T}} \leftarrow \phi$ 2: build stack $ \leftarrow \phi $ checking constraint conflictions 3: For $s_{ij}$ in cg do : 4: push $s_{ij}$ into stack 5: While stack is not $ \phi $ do : 6: buildsfor saving popped item of stack 7: aggregate neighbors of $s_{ij}$ intoU 8: ForuinUdo : 9: IF $ u \notin $ stack do : 8: putuinto ${S_{\rm T}}$ 9: locate$a_{iu}$withuands 10: put $a_{iu }$ into ${A_{\rm T}}$ 11: End IF 12: End For 13: End While 14: End For 15: $\begin{aligned}[b] fm \leftarrow & (\sum\limits_{a_{iu} }^{ {\boldsymbol{A} }_{\rm T} } {c_{iu} } + c_{\rm safe} < c_{\max} ) \cap \;\; (\sum\limits_{a_{iu} }^{ { {\boldsymbol{A} }_{\rm T} } } {e_{iu} } + e_{\rm safe} < e_{\max} ) \cap \\ & (\sum\limits_{a_{iu} }^{ { {\boldsymbol{A} }_{\rm T} } } f_{iu} < f_{\max} ) \cap \;\;(\sum\limits_{a_{iu} }^{ { {\boldsymbol{A} }_{\rm T} } } t_{iu} < t_{\max} ) \\ \end{aligned}$ 16: $fs \leftarrow (s_{ij} \cap s_{i(j + 1)} \to s_{i(j + 2)}) \cup (s_{ij} \cup s_{i(j + 1)} \to s_{i(j + 2)})$ Table 3.Mission planning in cognitive graph with multi-attribute constraint conflict detection
-
为验证所提出方法的可行性,针对深空探测器在着陆过程中的环绕探测任务构建测试用例,考虑载荷相机、姿态系统、对地通信和太阳能等4个子系统,采用上文2.2节中的方法构造包含41个状态节点,65个动作以及203条约束条件的深空探测自主任务规划认知图谱,在此基础上构建了10个不同规模的深空探测器规划任务算例。规划目标为满足资源和时序约束且任务执行时间最短,即深空探测任务规划中的最优解在解空间
$ A' $ 中应当满足10个算例的各项资源约束条件如表2所示。如在算例10中,最大可使用存储空间
$ c_{\max} $ 为800 G,最大可使用的电量$ e_{\max} $ 为650$ {\text{kW}} \cdot {\text{h}} $ ,最大可使用燃料$ f_{\max} $ 为400 kg,最大允许执行时间$ t_{\max} $ 为3 000 min。实验算例说明见表4。项目 算例1 算例2 算例3 算例4 算例5 算例6 算例7 算例8 算例9 算例10 存储max 850 400 400 400 350 800 350 400 850 800 电量max 900 800 950 1 000 700 850 600 750 700 650 燃料max 300 400 450 500 200 300 300 400 300 400 时间max 2 900 3 000 3 550 3 500 2 500 3 500 2 500 3 000 3 500 3 000 Table 4.Experimental example description
本文的仿真环境中的操作系统为Windows11,编程语言为Python3,处理器为i7-1165G7,RAM16GB。
-
以算例10为例,深空探测器将在着陆之前完成对着陆目标点的特定环绕和探测任务,要规划的总任务序列包括载荷相机拍照、姿态系统指向目标、通信子系统传输数据、太阳帆板充电提供能源等动作,各子系统需满足时序要求且存在如表2中所示的资源约束。
采用上文2.2节和2.3节中的算法进行深空探测自主任务规划仿真实验,采用2.2节中的图推理算法可得到包含各子系统状态与动作的可行解集输出结果如图3所示。其中左侧为不同的规划输出解结果,其表达形式是基于深空探测自主任务规划认知图谱的状态/行为序列转换图,右侧是其对应的任务规划结果甘特图。左侧图谱中不同颜色代表不同的子系统,其中橙色部分是深空探测器的太阳帆板子系统,蓝色部分是姿态子系统,红色部分是载荷相机子系统,卡其色部分是对地通信子系统。
图3中规划结果A中部分深空探测器的动作多元组按照式(11)可以表示为:<就绪状态,姿态子系统,深空探测器姿态子系统进入就绪状态的时间,转向目标,姿态子系统,转向目标资源消耗量,转向目标时间消耗量,运行状态,姿态子系统,深空探测器姿态子系统进入运行状态的时间>。
图4表示单次任务规划实验中算例10的规划解空间结果。其中:灰色代表检测到约束冲突的不可用规划序列;蓝色代表没有约束冲突的有效规划结果;橙色代表所有没有约束冲突的深空探测任务规划结果中的最短任务完成时间,即第11个深空探测任务规划序列为设定深空探测规划目标下的最终决策输出结果;红色的线表示当前统计资源种类可以使用的资源最大值。
-
1)规划求解时间对比实验
为测试本文算法的效果,对表4中所示的10个不同规模的算例分别采用本文算法、启发式算法、带约束的启发式算法、遗传算法和进化神经网络展开了任务规划实验,对每个算例分别进行多次规划实验,任取其中的10次实验结果进行分析,图5是本文算法与对比算法对不同规模规划序列的规划求解时间对比图。
从图中结果可以看出,由于本文深空探测自主任务规划认知图谱的规则推理和约束冲突检测方法减少了大量的冗余计算,因此在同等规模的规划任务进行的对比试验结果显示本文方法所需规划求解时间更少,相对于启发式算法和带约束的启发式算法,10个算例中在时间上的提升如图6所示。
将图5结果取算术平均值后进行对比,可以得到如图7所示的平均规划求解时间。
2)规划算法解空间对比实验
随着规划问题规模的增大,传统启发式算法的解空间将不可避免地出现组合爆炸现象[16]。本文对相同规模算例任务规划过程中的解空间变化情况进行了统计与对比。由于进化神经网络及遗传算法均采用编码后寻优求解,编码后的解空间数量巨大且非原始解空间,因此没有可对比性。本文算法与启发式算法和带约束的启发式算法在解空间上的变化对比如图8所示。
3)规划算法内存消耗对比实验
由于深空探测器的机载计算资源有限,因此规划算法在运行时需要用到内存空间大小也是衡量规划算法的重要指标之一。本文对不同算法运行过程中的内存消耗情况进行了对比,结果如图9所示。在本文所给出的同等规模算例任务规划实验中,遗传算法的内存消耗最大,但较为平稳;启发式算法所需内存随算例规模的增加呈明显的升高趋势,预估在更大规模算例中将难以满足其内存需求;进化神经网络规划算法的内存消耗较为平稳且较小;带约束的启发式算法在小规模规划算法中的内存消耗较小,随算例规模的增加其内存需求量与传统启发式算法类似也呈上升趋势,但所需内存消耗量明显小于上述3种算法;本文算法在本文实验算例中的内存需求量最小且较平稳。
在本文的10个实验算例中,分别比遗传算法、传统启发式算法、带约束的启发式算法及进化神经网络算法降低的比率如图10所示。
此外由于本文方法与遗传算法和进化神经网络算法均为机器学习算法,在求解过程中存在随机性和不确定性,因此对3种方法的规划成功率也进行了对比。对于上述的10个算例,在不考虑规划求解时间的条件下,遗传算法、进化神经网络和本文算法的平均规划成功率分别为78.2%、85.3%和88.1%,在本文实验环境下本文算法的规划成功率虽然略优于其它两种算法,由于前两种算法中的参数与超参数的影响较大且不稳定,算法在规划成功率上的优越性还需进一步展开验证。
Cognitive Graph for Autonomous Deep Space Mission Planning and Multi-Constraints Collision Detection
doi:10.15982/j.issn.2096-9287.2023.20220064
- Received Date:2022-07-01
- Rev Recd Date:2022-08-05
- Available Online:2023-03-01
- Publish Date:2023-02-28
-
Key words:
- deep space exploration/
- cognitive graph/
- graph model/
- mission planning/
- multi-constraints collision detection
Abstract:To deal with the multi-constraints in multi-subsystems coordination mechanism in deep space exploration mission planning, in this paper a cognitive graph architecture and a multi-attributes constraint conflict detection method were proposed for deep space exploration mission planning. In this paper, the graph representation method was adopted to realize knowledge modeling of task planning, the state transition diagram was constructed into triples to realize rule matching during task planning, and a multi-attributes constraint conflict detection algorithm was proposed based on the graph model inference method, so multi-subsystems cognitive reasoning and constraint conflict testing for task planning were realized. Simulation experiments were carried out with different scales of deep space exploration mission planning examples. The experimental results show that compared with genetic algorithm, traditional heuristic algorithm, constrained heuristic algorithm, and evolutionary neural network algorithm, the method proposed in this paper can effectively shorten planning time, and reduce the solution space and memory consumption, effectively improving the success rate and feasibility of deep space exploration mission planning.
Citation: | LIU Jingxing, WANG Bin, MAO Weiyang, XIONG Xin. Cognitive Graph for Autonomous Deep Space Mission Planning and Multi-Constraints Collision Detection[J].Journal of Deep Space Exploration, 2023, 10(1): 88-96.doi:10.15982/j.issn.2096-9287.2023.20220064 |