面向批量应急任务的分布式卫星在线协同方法

杨唯一, 何磊, 刘晓路, 杜永浩, 陈英武

系统工程理论与实践 ›› 2025, Vol. 45 ›› Issue (1) : 310-325.

PDF(20869 KB)
中国科学院数学与系统科学研究院期刊网
PDF(20869 KB)
系统工程理论与实践 ›› 2025, Vol. 45 ›› Issue (1) : 310-325. DOI: 10.12011/SETP2023-0876
论文

面向批量应急任务的分布式卫星在线协同方法

    杨唯一, 何磊, 刘晓路, 杜永浩, 陈英武
作者信息 +

A distributed satellite online collaboration method for batch emergency tasks

    YANG Weiyi, HE Lei, LIU Xiaolu, DU Yonghao, CHEN Yingwu
Author information +
文章历史 +

摘要

随着卫星能力的提升和应急需求的常态化, 传统的集中式任务规划或面向单个应急任务的分布式协同规划已经难以满足现有卫星的协同规划需求. 针对批量应急任务需求, 研究分布式卫星在线协同问题. 首先, 基于合同网机制, 针对批量到达任务所导致的通信量激增和循环求解问题, 提出了一种基于双层禁忌搜索的改进合同网机制(improved contract network protocol based on two-layer tabu search, ICNPTS). ICNPTS将原问题分为标书制作问题和评标问题, 并利用历史招投标信息, 对传统合同网流程提出三个改进机制. 其次, 为标书制作问题提出冲突消解的禁忌搜索算法以生成标书; 将评标问题建模为二部图最大权多重匹配并采用基于支配边集的多重匹配算法进行求解. 最后, 通过数值实验, 验证了ICNPTS在减小卫星间通信量和提升协同效果上的有效性.

Abstract

With the improvement of satellite capabilities and the normalization of emergency requirements, it becomes difficult for the traditional centralized mission planning or distributed cooperative planning for a single emergency task to meet the needs of existing satellite collaborative planning. Therefore, we study the distributed satellite online coordination problem for batch arrival emergency tasks. Firstly, based on the online collaboration mechanism of contract net, this paper aims at the problem of communication surge and cyclic solving caused by batch arrival tasks. This paper proposed an improved contract network protocol based on two-layer tabu search (ICNPTS). ICNPTS divides the original problem into two sub-problems: bid making problem and bid evaluation problem, and uses the historical bidding information to propose three improvement mechanisms. Secondly, a tabu search algorithm for conflict resolution is proposed to generate bids. The contract net bid evaluation problem is solved by multiple matching algorithm based on dominating edge set. Finally, numerical experiments verify the effectiveness of ICNPTS in reducing the communication traffic and improving the coordination effect.

关键词

分布式系统 / 在线协同 / 禁忌搜索 / 任务规划 / 有权二部图

Key words

distributed system / online collaboration / tabu search / task allocation / weighted bipartite graph

引用本文

EndNote

Ris (Procite)

Bibtex

导出引用
杨唯一 , 何磊 , 刘晓路 , 杜永浩 , 陈英武. 面向批量应急任务的分布式卫星在线协同方法. 系统工程理论与实践, 2025, 45(1): 310-325 https://doi.org/10.12011/SETP2023-0876
YANG Weiyi , HE Lei , LIU Xiaolu , DU Yonghao , CHEN Yingwu. A distributed satellite online collaboration method for batch emergency tasks. Systems Engineering - Theory & Practice, 2025, 45(1): 310-325 https://doi.org/10.12011/SETP2023-0876
中图分类号： V19   

参考文献

[1] 齐伟华, 刘晓路, 姚锋, 等. 面向智能敏捷卫星的自主任务规划与调度[J/OL]. 计算机集成制造系统, 2022. http://kns.cnki.net/kcms/detail/11.5946.TP.20220902.1818.010.html. Qi W H, Liu X L, Yao F, et al. Autonomous task planning and scheduling for intelligent agile satellite [J/OL]. Computer Integrated Manufacturing System, 2022. http://kns.cnki.net/kcms/detail/11.5946.TP.20220902.1818.010.html.
[2] Wang J J, Demeulemeester E, Hu X, et al. Exact and heuristic scheduling algorithms for multiple earth observation satellites under uncertainties of clouds[J]. IEEE Systems Journal, 2019, 13(3): 3556-3567.
[3] 刘嵩, 陈英武, 邢立宁, 等. 敏捷成像卫星时间依赖型调度问题、 模型与算法[J]. 系统工程理论与实践, 2016, 36(3): 788-794.Liu S, Chen Y W, Xing L N, et al. Model and algorithm of the time-dependent agile imaging satellite scheduling problem[J]. Systems Engineering—Theory & Practice, 2016, 36(3): 788-794.
[4] He L, Weerdt M D, Yorke-Smith N. Time/sequence-dependent scheduling: The design and evaluation of a general purpose tabu-based adaptive large neighborhood search algorithm[J]. Journal of Intelligent Manufacturing, 2020, 31(4): 1051-1078.
[5] Peng G S, Dewil R, Verbeeck C, et al. Agile earth observation satellite scheduling: An orienteering problem with time-dependent profits and travel times[J]. Computers & Operations Research, 2019, 111: 84-98.
[6] Niu X N, Tang H, Wu L X, et al. Imaging-duration embedded dynamic scheduling of earth observation satellites for emergent events[J]. Mathematical Problems in Engineering, 2015(1): 731734.
[7] 姜维, 庞秀丽. 面向成像卫星组网的群任务规划方法研究[J]. 系统工程理论与实践, 2014, 34(8): 2155-2161.Jiang W, Pang X L. The group scheduling method for the tasks of imaging satellite network[J]. Systems Engineering—Theory & Practice, 2014, 34(8): 2155-2161.
[8] 刘祥, 罗开平, 王海红, 等. 基于BFA的SPOT5卫星日常拍摄任务调度算法[J]. 系统工程理论与实践, 2020, 40(3): 783-794.Liu X, Luo K P, Wang H H, et al. BFA-based algorithm for the SPOT5 daily photograph scheduling problem[J]. Systems Engineering—Theory & Practice, 2020, 40(3): 783-794.
[9] 陈英武, 姚锋, 李菊芳, 等. 求解多星任务规划问题的演化学习型蚁群算法[J]. 系统工程理论与实践, 2013, 33(3): 792-801.Chen Y W, Yao F, Li J F, et al. A learnable ant colony optimization to the mission planning of multiple satellites[J]. Systems Engineering—Theory & Practice, 2013, 33(3): 792-801.
[10] Sarkheyli A, Bagheri A, Ghorbani V B, et al. Using an effective tabu search in interactive resources scheduling problem for LEO satellites missions[J]. Aerospace Science & Technology, 2013, 29(1): 287-295.
[11] 李菊芳, 贺仁杰, 姚锋, 等. 成像卫星集成调度的变邻域禁忌搜索算法[J]. 系统工程理论与实践, 2013, 33(12): 3041-3044.Li J F, He R J, Yao F, et al. Variable neighborhood tabu search algorithm for integrated imaging satellites scheduling problem[J]. Systems Engineering—Theory & Practice, 2013, 33(12): 3041-3044.
[12] Skobelev P O, Simonova E V, Ivanov A, et al. Real time scheduling of data transmission sessions in a microsatellites swarm and ground stations network based on multi-agent technology[C]// International Conference on Evolutionary Computation Theory and Applications, 2014.
[13] Yang W, He L, Liu X, et al. Onboard coordination and scheduling of multiple autonomous satellites in an uncertain environment[J]. Advances in Space Research, 2021, 68(11): 4505-4524.
[14] Zheng Z, Guo J, Gill E. Distributed onboard mission planning for multi-satellite systems[J]. Aerospace Science and Technology, 2019, 89: 111-122.
[15] Sun C, Wang X, Qiu H, et al. Game theoretic self-organization in multi-satellite distributed task allocation[J]. Aerospace Science and Technology, 2021, 112(1): 106650.
[16] Song B, Chen Y, Yang Q, et al. On-board decentralized observation planning for LEO satellite constellations[J]. Algorithms, 2023, 16(2): 114-123.
[17] 李政阳, 云昕, 杨怡欣, 等. 在轨空间智能制造: 分布式调度建模与优化[J]. 系统工程理论与实践, 2019, 39(3): 705-724.Li Z Y, Yun X, Yang Y X, et al. In-space intelligent manufacturing: Distributed scheduling and optimization[J]. Systems Engineering—Theory & Practice, 2019, 39(3): 705-724.
[18] 郭兴海, 计明军, 温都苏, 等. "最后一公里"配送的分布式多无人机的任务分配和路径规划[J]. 系统工程理论与实践, 2021, 41(4): 946-961.Guo H X, Ji M J, Wen D S, et al. Task assignment and path planning for distributed multiple unmanned aerial vehicles in the "last mile"[J]. Systems Engineering—Theory & Practice, 2021, 41(4): 946-961.
[19] 高黎, 沙基昌. 基于合同网的分布式卫星系统任务优化分配研究[J]. 宇航学报, 2009, 30(2): 815-820.Gao L, Sha J C. Research on task optimization assignment of distributed satellite system based on contract network[J]. Journal of Astronautics, 2009, 30(2): 815-820.
[20] Du B, Li S. A new multi-satellite autonomous mission allocation and planning method[J]. Acta Astronautica, 2019, 163: 287-298.
[21] Li G. Online scheduling of distributed Earth observation satellite system under rigid communication constraints[J]. Advances in Space Research, 2020, 65(11): 2475-2496.
[22] 靳鹏, 李康. 基于改进合同网协议的分布式卫星资源调度[J]. 系统工程与电子技术, 2022(10): 3165-3173.Jin P, Li K. Distributed satellite resource scheduling based on improved contract net protocol[J]. Systems Engineering and Electronics, 2022(10): 3165-3173.
[23] Dutta A, Asaithambi A. One-to-many bipartite matching based coalition formation for multi-robot task allocation[C]// International Conference on Robotics and Automation, 2019.
[24] 于昕曜, 朱宁, 马延明, 等. 考虑异常车次的公交车辆调度计划问题研究[J]. 系统工程理论与实践, 2023, 43(3): 910-928.Yu X Y, Zhu N, Ma Y M, et al. Bus scheduling problem with disruptions[J]. Systems Engineering—Theory & Practice, 2023, 43(3): 910-928.
[25] 周光辉, 敬帅, 梁伟. 基于图着色理论的多飞艇多载荷协同对地观测和数据传输调度模型与算法[J]. 系统工程理论与实践, 2021, 41(9): 2338-2354.Zhou G H, Jin S, Liang W. Model and algorithm for coordinated observation and data transmission scheduling of multi-airship and multi-payload by graph coloring theory[J]. Systems Engineering—Theory & Practice, 2021, 41(9): 2338-2354.
[26] He L, Weerdt M D, Yorke-Smith N. Time/sequence-dependent scheduling: The design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm[J]. Journal of Intelligent Manufacturing, 2020, 31(4): 1051-1078.

基金

National Natural Science Foundation of China (72001212, 72201272);Young Elite Scientists Sponsorship Program by CAST (2022QNRC001);Graduate Student Innovation Project of Hunan Province (XJQY2024008)
PDF(20869 KB)

268

Accesses

0

Citation

Detail
段落导航
相关文章

/

〈 〉