航空计算与仿真技术专栏

约束分级的飞行器任务指令序列编排方法

  • 王路桥 ,
  • 王璐 ,
  • 庄慧盈 ,
  • 吴磊 ,
  • 李青山 ,
  • 田恒宇
展开
  • 西安电子科技大学 计算机科学与技术学院,西安 710126
.E-mail: wanglu@xidian.edu.cn

收稿日期: 2024-03-25

  修回日期: 2024-05-06

  录用日期: 2024-06-16

  网络出版日期: 2024-06-25

基金资助

国家自然科学基金(U21B2015);陕西省科协青年人才托举计划项目(20220113)

A hierarchical constraint-based method for arranging aircraft mission instruction sequences

  • Luqiao WANG ,
  • Lu WANG ,
  • Huiying ZHUANG ,
  • Lei WU ,
  • Qingshan LI ,
  • Hengyu TIAN
Expand
  • School of Computer Science and Technology,Xidian University,Xi’an 710126,China

Received date: 2024-03-25

  Revised date: 2024-05-06

  Accepted date: 2024-06-16

  Online published: 2024-06-25

Supported by

National Natural Science Foundation of China(U21B2015);Young Talent Fund of Association for Science and Technology in Shaanxi(20220113)

摘要

针对飞行器任务指令序列生成和优化问题,提出一种约束分级的任务指令序列处理框架,并进一步设计融合拓扑优化和优先级编码遗传的序列编排方法。首先,将指令及其约束建模成有向图,通过引入虚拟节点替代图中的强连通分量,实现去环效果。然后,针对生成的有向无环图,通过拓扑优化构建指令序列的基本初始框架。对于抽取的强连通分量,对其节点的优先级进行编码,并在遗传过程中将其作为交叉对象的基因索引,不断迭代生成优化的指令序列片段。最后,将片段集成到初始框架中,实现任务指令序列的生成和优化。仿真结果表明:在不同规模和复杂度的指令集合场景中,相较于其它方法,本文所提方法能够显著降低指令序列的生成时间,并压缩指令序列的长度。

本文引用格式

王路桥 , 王璐 , 庄慧盈 , 吴磊 , 李青山 , 田恒宇 . 约束分级的飞行器任务指令序列编排方法[J]. 航空学报, 2024 , 45(20) : 630445 -630445 . DOI: 10.7527/S1000-6893.2024.30445

Abstract

To address the problem of aircraft mission instruction sequence generation and optimization, we propose a hierarchical-constraint mission instruction sequence processing framework, and further design a sequencing? method that integrates topological optimization and the priority-encoded genetic algorithm. First, instructions and their constraints are modeled as a directed graph; virtual nodes are introduced to replace Strongly Connected Components (SCCs) in the graph, achieving cycle elimination. Then, for the generated Directed Acyclic Graph (DAG), a basic initial framework of the instruction sequence is constructed through topological optimization. For the extracted strongly connected components, the priorities of their nodes are encoded and used as the gene indexes of crossover objects, thereby iteratively generating optimized instruction sequence snippets. Finally, the snippets are integrated into the initial framework to achieve the generation and optimization of the mission instruction sequence. Simulation results display that in the scenarios with instruction sets of varying scales and complexities, the proposed method significantly reduces the generation time and compresses the length of instruction sequences compared to other encoding methods.

参考文献

1 王沛. 基于分支定价的多星多站集成调度方法研究[D]. 长沙: 国防科技大学, 2011: 1-5.
  WANG P. Research on branch-and-price based multi-satellite multi-station integrated scheduling method[D].Changsha: National University of Defense Technology, 2011: 1-5. (in Chinese).
2 王沛, 谭跃进. 多星联合对地观测调度问题的列生成算法[J]. 系统工程理论与实践201131(10): 1932-1939.
  WANG P, TAN Y J. Column generation for the earth observation satellites scheduling problem[J]. Systems Engineering-Theory & Practice201131(10): 1932-1939 (in Chinese).
3 张军峰, 王菲, 葛腾腾. 基于分支定界法的进场航空器动态排序与调度[J]. 系统仿真学报201628(8): 1909-1914.
  ZHANG J F, WANG F, GE T T. Dynamic arrival sequencing & scheduling based on branch & bound algorithm[J]. Journal of System Simulation201628(8): 1909-1914 (in Chinese).
4 刘洋, 陈英武, 谭跃进. 卫星地面站系统任务调度的动态规划方法[J]. 中国空间科学技术200525(1): 44-47.
  LIU Y, CHEN Y W, TAN Y J. The method of mission planning of the ground station of satellite based on dynamic programming[J]. Chinese Space Science and Technology200525(1): 44-47 (in Chinese).
5 柴敬轩, 赵寒冰, 梅杰, 等. 深空探测器指令序列智能执行技术进展[J]. 宇航学报202344(11): 1645-1658.
  CHAI J X, ZHAO H B, MEI J, et al. Review on intelligent execution technologies of deep space probe command sequences[J]. Journal of Astronautics202344(11): 1645-1658 (in Chinese).
6 刘嵩, 白国庆, 陈英武. 地球观测网络成像任务可调度性预测方法[J]. 宇航学报201536(5): 583-588.
  LIU S, BAI G Q, CHEN Y W. Prediction method for imaging task schedulability of earth observation network[J]. Journal of Astronautics201536(5): 583-588 (in Chinese).
7 DU Y H, WANG T, XIN B, et al. A data-driven parallel scheduling approach for multiple agile earth observation satellites[J]. IEEE Transactions on Evolutionary Computation202024(4): 679-693.
8 LI J, LI J, JING N, et al. A satellite schedulability prediction algorithm for EO SPS[J]. Chinese Journal of Aeronautics201326(3): 705-716.
9 毛维杨, 王彬, 柳景兴, 等. 基于强化学习的深空探测器自主任务规划方法[J]. 深空探测学报(中英文)202310(2): 220-230.
  MAO W Y, WANG B, LIU J X, et al. An autonomous planning method for deep space exploration tasks in reinforcement learning based on dynamic rewards[J]. Journal of Deep Space Exploration202310(2): 220-230 (in Chinese).
10 何永明. 集成确定性算法和强化学习的成像卫星任务规划技术研究[D]. 长沙: 国防科技大学, 2021: 1-7.
  HE Y M. Research on imaging satellite task planning technology by integrating deterministic algorithms and reinforcement learning[D].Changsha: National University of Defense Technology, 2021: 1-7. (in Chinese).
11 吴昭欣. 基于深度强化学习的飞行器自主机动决策方法研究[D]. 成都: 四川大学, 2021: 1-11.
  WU Z X. Research on autonomous maneuvering decision method for aircraft based on deep reinforcement learning[D].Chengdu: Sichuan University, 2021: 1-11. (in Chinese).
12 YAO F, LI J F, BAI B C, et al. Earth observation satellites scheduling based on decomposition optimization algorithm[J]. International Journal of Image, Graphics and Signal Processing20102(1): 10-18.
13 孙凯, 白国庆, 陈英武, 等. 面向动作序列的敏捷卫星任务规划问题[J]. 国防科技大学学报201234(6): 141-147.
  SUN K, BAI G Q, CHEN Y W, et al. Action planning for agile earth-observing satellite mission planning problem[J]. Journal of National University of Defense Technology201234(6): 141-147 (in Chinese).
14 齐伟华, 刘晓路, 姚锋, 等. 面向智能敏捷卫星的自主任务规划与调度[J/OL]. 计算机集成制造系统, (2022-09-05)[2024-03-01]..
  QI W H, LIU X L, YAO F, et al. Autonomous task planning and scheduling method for intelligent agile satellite[J]. Computer Integrated Manufacturing Systems, (2022-09-05) [2024-03-01]. (in Chinese).
15 马林, 秦阳, 秦嘉豪, 等. 大型星座混合模拟退火遗传算法测控任务规划[J]. 宇航学报202344(11): 1757-1766.
  MA L, QIN Y, QIN J H, et al. Massive constellation measurement and control scheduling based on hybrid simulated annealing genetic algorithm[J]. Journal of Astronautics202344(11): 1757-1766 (in Chinese).
16 刘雯, 李立钢. 基于改进遗传算法的天文卫星任务规划研究[J]. 计算机仿真201431(12): 54-58.
  LIU W, LI L G. Mission planning of space astronomical satellite based on improved genetic algorithm[J]. Computer Simulation201431(12): 54-58 (in Chinese).
17 周毅荣, 陈浩, 李龙梅, 等. 一种基于免疫遗传的卫星数传调度方法[J]. 小型微型计算机系统201536(12): 2725-2729.
  ZHOU Y R, CHEN H, LI L M, et al. Immune genetic algorithm for satellite data transmission scheduling[J]. Journal of Chinese Computer Systems201536(12): 2725-2729 (in Chinese).
18 CHEN H, ZHOU Y R, DU C, et al. A satellite cluster data transmission scheduling method based on genetic algorithm with rote learning operator[C]∥2016 IEEE Congress on Evolutionary Computation (CEC). Piscataway: IEEE Press, 2016: 5076-5083.
19 韩鹏, 郭延宁, 李传江, 等. 基于相对成像时刻编码遗传算法的敏捷成像卫星任务规划[J]. 宇航学报202142(11): 1427-1438.
  HAN P, GUO Y N, LI C J, et al. A relative imaging time coding-based genetic algorithm for agile imaging satellite task planning[J]. Journal of Astronautics202142(11): 1427-1438 (in Chinese).
20 王海蛟, 贺欢, 杨震. 敏捷成像卫星调度的改进量子遗传算法[J]. 宇航学报201839(11): 1266-1274.
  WANG H J, HE H, YANG Z. Scheduling of agile satellites based on an improved quantum genetic algorithm[J]. Journal of Astronautics201839(11): 1266-1274 (in Chinese).
21 LONG J, WU S M, HAN X D, et al. Autonomous task planning method for multi-satellite system based on a hybrid genetic algorithm[J]. Aerospace202310(1): 70.
22 SONG Y J, OU J W, WU J, et al. A cluster-based genetic optimization method for satellite range scheduling system[J]. Swarm and Evolutionary Computation202379: 101316.
23 AYANA S E, KIM H D. Optimal scheduling of imaging missions for multiple satellites using linear programming model[J]. International Journal of Aeronautical and Space Sciences202324(2): 559-569.
文章导航

/