约束分级的飞行器任务指令序列编排方法
收稿日期: 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
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
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]. 系统工程理论与实践, 2011, 31(10): 1932-1939. |
WANG P, TAN Y J. Column generation for the earth observation satellites scheduling problem[J]. Systems Engineering-Theory & Practice, 2011, 31(10): 1932-1939 (in Chinese). | |
3 | 张军峰, 王菲, 葛腾腾. 基于分支定界法的进场航空器动态排序与调度[J]. 系统仿真学报, 2016, 28(8): 1909-1914. |
ZHANG J F, WANG F, GE T T. Dynamic arrival sequencing & scheduling based on branch & bound algorithm[J]. Journal of System Simulation, 2016, 28(8): 1909-1914 (in Chinese). | |
4 | 刘洋, 陈英武, 谭跃进. 卫星地面站系统任务调度的动态规划方法[J]. 中国空间科学技术, 2005, 25(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 Technology, 2005, 25(1): 44-47 (in Chinese). | |
5 | 柴敬轩, 赵寒冰, 梅杰, 等. 深空探测器指令序列智能执行技术进展[J]. 宇航学报, 2023, 44(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 Astronautics, 2023, 44(11): 1645-1658 (in Chinese). | |
6 | 刘嵩, 白国庆, 陈英武. 地球观测网络成像任务可调度性预测方法[J]. 宇航学报, 2015, 36(5): 583-588. |
LIU S, BAI G Q, CHEN Y W. Prediction method for imaging task schedulability of earth observation network[J]. Journal of Astronautics, 2015, 36(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 Computation, 2020, 24(4): 679-693. |
8 | LI J, LI J, JING N, et al. A satellite schedulability prediction algorithm for EO SPS[J]. Chinese Journal of Aeronautics, 2013, 26(3): 705-716. |
9 | 毛维杨, 王彬, 柳景兴, 等. 基于强化学习的深空探测器自主任务规划方法[J]. 深空探测学报(中英文), 2023, 10(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 Exploration, 2023, 10(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 Processing, 2010, 2(1): 10-18. |
13 | 孙凯, 白国庆, 陈英武, 等. 面向动作序列的敏捷卫星任务规划问题[J]. 国防科技大学学报, 2012, 34(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 Technology, 2012, 34(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]. 宇航学报, 2023, 44(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 Astronautics, 2023, 44(11): 1757-1766 (in Chinese). | |
16 | 刘雯, 李立钢. 基于改进遗传算法的天文卫星任务规划研究[J]. 计算机仿真, 2014, 31(12): 54-58. |
LIU W, LI L G. Mission planning of space astronomical satellite based on improved genetic algorithm[J]. Computer Simulation, 2014, 31(12): 54-58 (in Chinese). | |
17 | 周毅荣, 陈浩, 李龙梅, 等. 一种基于免疫遗传的卫星数传调度方法[J]. 小型微型计算机系统, 2015, 36(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 Systems, 2015, 36(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]. 宇航学报, 2021, 42(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 Astronautics, 2021, 42(11): 1427-1438 (in Chinese). | |
20 | 王海蛟, 贺欢, 杨震. 敏捷成像卫星调度的改进量子遗传算法[J]. 宇航学报, 2018, 39(11): 1266-1274. |
WANG H J, HE H, YANG Z. Scheduling of agile satellites based on an improved quantum genetic algorithm[J]. Journal of Astronautics, 2018, 39(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]. Aerospace, 2023, 10(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 Computation, 2023, 79: 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 Sciences, 2023, 24(2): 559-569. |
/
〈 |
|
〉 |