Cognitive Graph for Autonomous Deep Space Mission Planning and 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.Highlights
● A system framework of cognitive graph for autonomous mission planning in deep space exploration is proposed. ● Using graph representations learning to implement knowledge modeling for task planning of deep spacecraft. ● Mapping state transition into triples to realize rules matching in the process of task planning. ● A multi-attributes constraint conflict detection algorithm is proposed and realized. -
图 1深空探测任务规划问题的知识建模
Fig. 1Knowledge modeling for deep space exploration mission planning
图 3认知图谱规划结果及对应的甘特图
Fig. 3Cognitive graph planning results and corresponding Gantt charts
图 4算例10中不同深空探测任务规划序列中电量消耗统计
Fig. 4Statistics of electricity consumption in different deep space exploration mission planning sequences in Example 10
图 5深空探测自主任务规划求解时间箱型图
Fig. 5Box plot of deep space exploration autonomous mission solver time
图 6本文算法相较于其他算法在不同算例中的时间提升率
Fig. 6Time improvement rate of our method compared with others in different examples
图 7本文算法与其他算法在不同算例中的平均求解时间
Fig. 7Average solution time of our method and that of others in different examples
图 8本文算法与其他算法在不同算例中的解空间
Fig. 8Solution space of our method and that of others in different examples
图 9本文算法相较于其他算法在不同算例中的内存消耗
Fig. 9Memory consumption of our method compared with that of others in different examples
图 10本文算法相较于其他算法在不同算例中的内存消耗降低率
Fig. 10Memory reduction rate of our method compared with that of others in different examples
表 1深空探测任务规划问题的解
Table 1Solution to deep space exploration mission planning
子系统 $ \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} $ 
下载:
导出CSV
表 2创建深空探测任务规划认知图谱
Table 2Multi-attributes triple model in cognitive graph
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 下载:
导出CSV
表 3基于认知图谱的任务规划方法中多属性权值约束冲突检测的实现
Table 3Mission planning in cognitive graph with multi-attribute constraint conflict detection
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)})$ 下载:
导出CSV
表 4实验算例说明
Table 4Experimental example description
项目 算例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 下载:
导出CSV
-
[1] 崔平远,徐瑞,朱圣英,等. 深空探测器自主技术发展现状与趋势[J]. 航空学报,2014,35(1):13-28.CUI P Y,XU R,ZHU S Y,et al. State of the art and development trends of on-board autonomy technology for deep space explorer[J]. Acta Aeronautica et Astronautica Sinica,2014,35(1):13-28. [2] 赵凡宇,徐瑞,崔平远. 启发式深空探测器任务规划方法[J]. 宇航学报,2015,36(5):496-503.ZHAO F Y,XU R,CUI P Y. Heuristic mission planning approach for deep space explorer[J]. Journal of Astronautics,2015,36(5):496-503. [3] 金颢,徐瑞,崔平远,等. 基于扩展状态深空探测器任务规划方法[J]. 深空探测学报(中英文),2018,5(6):569-574.doi:10.15982/j.issn.2095-7777.2018.06.010JIN H,XU R,CUI P Y,et al. Mission planning approach based on extensible states for deep space probes[J]. Journal of Deep Space Exploration,2018,5(6):569-574.doi:10.15982/j.issn.2095-7777.2018.06.010 [4] 王卓,徐瑞. 基于多目标优化的深空探测器姿态组合规划方法[J]. 深空探测学报(中英文),2021,8(2):147-153.WANG Z,XU R. Combination planning for attitude maneuver of deep space probes based on multi-objective optimization[J]. Journal of Deep Space Exploration,2021,8(2):147-153. [5] JARZĘBOWSKA E,PILARCZYK B. Design of a tracking controller for object interception in space[J]. Discontinuity,Nonlinearity,and Complexity,2017,6(4):435-443. [6] 陈超,徐瑞,李朝玉,等. 期望状态序列导向的深空探测器规划修复方法[J]. 宇航学报,2021,42(11):1385-1395.doi:10.3873/j.issn.1000-1328.2021.11.005CHEN C,XU R,LI Z Y,et al. Plan repair method of deep space probe based on the expected state sequence[J]. Journal of Astronautics,2021,42(11):1385-1395.doi:10.3873/j.issn.1000-1328.2021.11.005 [7] ZHAO Y T,XU R,JIANG H P,et al. Decentralized privacy-preserving onboard mission planning for multi-probe system[J]. Acta Astronautica,2021,179:130-145.doi:10.1016/j.actaastro.2020.10.041 [8] 王鑫,赵清杰,徐瑞. 基于知识图谱的深空探测器任务规划建模[J]. 深空探测学报(中英文),2021,8(3):315-323.WANG X,ZHAO Q J,XU R. Modeling of mission planning for deep space probe based on knowledge graph[J]. Journal of Deep Space Exploration,2021,8(3):315-323. [9] 金洋,王日新,徐敏强. 基于状态记忆的航天器自主故障诊断方法[J]. 系统工程与电子技术,2015,37(6):1452-1458.doi:10.3969/j.issn.1001-506X.2015.06.34 [10] JIN Y,WANG R X,XU M Q. Spacecraft autonomous fault diagnosis method based on state memory[J]. Systems Engineering and Electronics,2015,37(6):1452-1458. [11] 徐瑞,李朝玉,朱圣英,等. 深空探测器自主规划技术研究进展[J]. 深空探测学报(中英文),2021,8(2):111-123. [12] XU R,LI Z Y,ZHU S Y,et al. Research progress of autonomous planning technology for deep space probes[J]. Journal of Deep Space Exploration,2021,8(2):111-123. [13] LI Z Y, DING X, LIU T. Constructing narrative event evolutionary graph for script event prediction[C]//27th International Joint Conference on Artificial Intelligence （IJCAI'18）. AIAA: [s. n.], 2008. [14] DING M, ZHOU C, CHEN Q, et al. Cognitive graph for multi-hop reading comprehension at scale [C]// Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics. ACL: Italy, 2019. [15] 王军平,张文生,王勇飞,等. 面向大数据领域的事理认知图谱构建与推断分析[J]. 中国科学:信息科学,2020,50(7):988-1002.doi:10.1360/SSI-2019-0273WANG J P,ZHANG W S,WANG Y F,et al. Constructing and inferring event logic cognitive graph in the field of big data[J]. Scientia Sinica Informationis,2020,50(7):988-1002.doi:10.1360/SSI-2019-0273 [16] 王鑫,邹磊,王朝坤,等. 知识图谱数据管理研究综述[J]. 软件学报,2019,30(7):2139-2174.doi:10.13328/j.cnki.jos.005841WANG X,ZOU L,WANG C K. Research on knowledge graph data management:a survey[J]. Journal of Software,2019,30(7):2139-2174.doi:10.13328/j.cnki.jos.005841 [17] HOLZSCHUHER F, PEINL R. Performance of graph query languages: comparison of cypher, gremlin and native access in Neo4j[C]//Joint EDBT/ICDT 2013 Workshops （EDBT '13）. New York, NY, USA: Association for Computing Machinery, 2013. [18] HAMILTON W L, YING R, LESKOVEC J. Inductive representation learning on large graphs[C]//31st International Conference on Neural Information Processing Systems （NIPS'17）. Red Hook, NY, USA: Curran Associates Inc. , 2017. -
下载:
计量
- 文章访问数:7
- 被引次数:0
