一种招投标机制的多星自主协同任务规划方法
|
摘要
针对多星自主协同遥感背景下非预期任务的快速响应问题,考虑到星上计算资源有限、计算能力较弱等特点,为寻找一种满足星上自主任务规划能力需求的优化算法,提升遥感卫星星群在非预期情况下的快速响应能力,通过多星自主协同规划问题建模、算法设计和仿真分析等模型及算法研究,提出了一种基于招投标机制的自主任务规划方法.该方法首先针对多星自主协同任务规划问题,构建了星上自主任务规划的数学模型,进而在问题求解过程中将一次完整的任务规划合理分解为招标、投标和评标3个过程,并详细设计了求解流程及相应的约束检验规则,由此得到基于招投标机制的多星自主协同任务规划求解算法.该方法与常用智能优化方法相比,能够显著降低计算量,更加适应星上紧张的计算资源约束.通过仿真算例结果表明,针对典型的非预期任务,算法平均仿真运行时间约为1 s,能够在40 s内完成对非预期任务的响应,并且充分保证了原规划任务的完成率,基于此验证了该方法的有效性与正确性.
Based on the bidding mechanism, an autonomous mission planning method was proposed to solve the rapid response problem of unexpected tasks in the background of multi-satellite cooperative remote sensing, which considers the limited computing resources and the weak computing power on the satellite. In order to find an optimization algorithm that satisfies the requirements of on-board autonomous mission planning and enhances the rapid response capability of the constellation of the remote sensing satellites in unexpected situations, the multi-satellite collaborative planning modeling, algorithm design, and simulation analysis were studied. First, the mathematical model of autonomous mission planning on the satellite for multi-satellite autonomous collaborative task planning was constructed. Then, in the problem solving process, a complete task planning was reasonably decomposed into three processes including invitation for bid, bidding, and evaluation. With the solving process and the corresponding constraint inspection rules designed, the multi-satellite autonomous collaborative mission planning algorithm based on bidding mechanism was obtained. Compared with commonly used intelligent optimization methods, this method can significantly reduce the computational complexity and adapt to the tight computational resource constraints on the satellite. The simulation example shows that for a typical unexpected task, the average simulation running time of the algorithm was about 1 s, the response to unexpected tasks could be completed within 40 s, and the completion rate of the original planning task was fully guaranteed, which verifies the validity and the correctness of the method.
Based on the bidding mechanism, an autonomous mission planning method was proposed to solve the rapid response problem of unexpected tasks in the background of multi-satellite cooperative remote sensing, which considers the limited computing resources and the weak computing power on the satellite. In order to find an optimization algorithm that satisfies the requirements of on-board autonomous mission planning and enhances the rapid response capability of the constellation of the remote sensing satellites in unexpected situations, the multi-satellite collaborative planning modeling, algorithm design, and simulation analysis were studied. First, the mathematical model of autonomous mission planning on the satellite for multi-satellite autonomous collaborative task planning was constructed. Then, in the problem solving process, a complete task planning was reasonably decomposed into three processes including invitation for bid, bidding, and evaluation. With the solving process and the corresponding constraint inspection rules designed, the multi-satellite autonomous collaborative mission planning algorithm based on bidding mechanism was obtained. Compared with commonly used intelligent optimization methods, this method can significantly reduce the computational complexity and adapt to the tight computational resource constraints on the satellite. The simulation example shows that for a typical unexpected task, the average simulation running time of the algorithm was about 1 s, the response to unexpected tasks could be completed within 40 s, and the completion rate of the original planning task was fully guaranteed, which verifies the validity and the correctness of the method.
引文
[1]祝周鹏. 面向任务的卫星平台载荷配置与应急规划技术[D]. 长沙: 国防科学技术大学, 2013: 13ZHU Zhoupeng. Task-oriented satellite platform payloads configuration and contingency scheduling technology[D]. Changsha: National University of Defense Technology, 2013: 13
[2]KARAPETYAN D, MITROVIC-MINIC S, MALLADI K T, et al. The satellite downlink scheduling problem: a case study of RADARSAT-2[M]//MURTY K G. Case Studies in Operations Research. New York: Springer, 2015: 497. DOI:10.1007/978-1-4939-1007-6_21
[3]ZHENG Zixuan, GUO Jian, GILL E.Swarm satellite mission scheduling & planning using Hybrid Dynamic Mutation Genetic Algorithm[J]. Acta Astronautica, 2017, 137: 243. DOI:10.1016/j.actaastro.2017.04.027
[4]BARBULESCU L, HOWE A, WHITLEY D. AFSCN Scheduling: how the problem and solution have evolved[J]. Mathematic and Computer Modeling, 2006, 43(9/10): 1023. DOI:10.1016/j.mcm.2005.12.004
[5]苗悦. 编队飞行成像卫星的自主任务规划技术研究[D]. 哈尔滨: 哈尔滨工业大学, 2016: 12MIAO Yue. Research on autonomous task planning of imaging satellite of formation flying[D]. Harbin: Harbin Institute of Technology, 2016: 12
[6]VERFAILLIE G, BORNSCHLEGL E. Designing and evaluating an on-line on-board autonomous Earth observation satellite scheduling system[C]//Proceedings of the 2nd NASA International Workshop on Planning and Scheduling for Space. California:[s.n.], 2013: 122
[7]刘嵩, 陈英武, 邢立宁, 等. 敏捷成像卫星时间依赖型调度问题、模型与算法[J]. 系统工程理论与实践, 2016, 36(3): 787LIU Song, CHEN Yingwu, XING Lining, et al. Model and algorithm of the time-dependent agile imaging satellite scheduling problem[J]. Systems Engineering——Theory & Practice, 2016, 36(3): 787. DOI:10.12011/1000-6788(2016)03-0787-08
[8]赵萍, 陈志明. 应用于卫星自主任务调度的改进遗传算法[J]. 中国空间科学技术, 2016, 36(6): 47ZHAO Ping, CHEN Zhiming. An adapted genetic algorithm applied to satellite autonomous task scheduling[J]. Chinese Space Science and Technology, 2016, 36(6): 47. DOI:10.16708/j.cnki.1000-758x.2016.0064
[9]LUO Kaiping, WANG Haihong, LI Yijun, et al. High-performance technique for satellite range scheduling[J]. Computers & Operations Research, 2017, 85: 12. DOI:10.1016/j.cor.2017.03.012
[10]王钧. 成像卫星综合任务调度模型与优化方法研究[D]. 长沙: 国防科学技术大学, 2007: 12WANG Jun. Research on modeling and optimization techniques in united mission scheduling of imaging satellites[D]. Changsha: National University of Defense Technology, 2007: 12
[11]XHAFA F, SUN Junzi, BAROLLI A, et al. Genetic algorithms for satellite scheduling problems[J]. Mobile Information Systems, 2012, 8(4): 351. DOI:10.1155/2012/717658
[12]WU Guohua, LIU Jin, MA Manhao, et al. A two-phase scheduling method with the consideration of task clustering for earth observing satellites[J]. Computers & Operations Research, 2013, 40(7): 1884. DOI:10.1016/j.cor.2013.02.009
[13]黄生俊, 邢立宁, 郭波. 基于改进模拟退火的多星任务规划方法[J]. 科学技术与工程, 2012, 12(31): 8293HUANG Shengjun, XING Lining, GUO Bo. Multi-satellites mission scheduling technique based on improved simulated annealing[J]. Science Technology and Engineering, 2012, 12(31): 8293
[14]MOUW C B, GREB S, AURIN D, et al. Aquatic color radiometry remote sensing of coastal and inland waters: challenges and recommendations for future satellite missions[J]. Remote Sensing of Environment, 2015, 160(2): 15. DOI:10.1016/j.rse.2015.02.001
[15]高黎. 对地观测分布式卫星系统任务协作问题研究[D]. 长沙: 国防科学技术大学, 2007: 68GAO Li. Resesrch on earth observation task cooperation for distributed satellites system[D]. Changsha: National University of Defense Technology, 2007: 68
[2]KARAPETYAN D, MITROVIC-MINIC S, MALLADI K T, et al. The satellite downlink scheduling problem: a case study of RADARSAT-2[M]//MURTY K G. Case Studies in Operations Research. New York: Springer, 2015: 497. DOI:10.1007/978-1-4939-1007-6_21
[3]ZHENG Zixuan, GUO Jian, GILL E.Swarm satellite mission scheduling & planning using Hybrid Dynamic Mutation Genetic Algorithm[J]. Acta Astronautica, 2017, 137: 243. DOI:10.1016/j.actaastro.2017.04.027
[4]BARBULESCU L, HOWE A, WHITLEY D. AFSCN Scheduling: how the problem and solution have evolved[J]. Mathematic and Computer Modeling, 2006, 43(9/10): 1023. DOI:10.1016/j.mcm.2005.12.004
[5]苗悦. 编队飞行成像卫星的自主任务规划技术研究[D]. 哈尔滨: 哈尔滨工业大学, 2016: 12MIAO Yue. Research on autonomous task planning of imaging satellite of formation flying[D]. Harbin: Harbin Institute of Technology, 2016: 12
[6]VERFAILLIE G, BORNSCHLEGL E. Designing and evaluating an on-line on-board autonomous Earth observation satellite scheduling system[C]//Proceedings of the 2nd NASA International Workshop on Planning and Scheduling for Space. California:[s.n.], 2013: 122
[7]刘嵩, 陈英武, 邢立宁, 等. 敏捷成像卫星时间依赖型调度问题、模型与算法[J]. 系统工程理论与实践, 2016, 36(3): 787LIU Song, CHEN Yingwu, XING Lining, et al. Model and algorithm of the time-dependent agile imaging satellite scheduling problem[J]. Systems Engineering——Theory & Practice, 2016, 36(3): 787. DOI:10.12011/1000-6788(2016)03-0787-08
[8]赵萍, 陈志明. 应用于卫星自主任务调度的改进遗传算法[J]. 中国空间科学技术, 2016, 36(6): 47ZHAO Ping, CHEN Zhiming. An adapted genetic algorithm applied to satellite autonomous task scheduling[J]. Chinese Space Science and Technology, 2016, 36(6): 47. DOI:10.16708/j.cnki.1000-758x.2016.0064
[9]LUO Kaiping, WANG Haihong, LI Yijun, et al. High-performance technique for satellite range scheduling[J]. Computers & Operations Research, 2017, 85: 12. DOI:10.1016/j.cor.2017.03.012
[10]王钧. 成像卫星综合任务调度模型与优化方法研究[D]. 长沙: 国防科学技术大学, 2007: 12WANG Jun. Research on modeling and optimization techniques in united mission scheduling of imaging satellites[D]. Changsha: National University of Defense Technology, 2007: 12
[11]XHAFA F, SUN Junzi, BAROLLI A, et al. Genetic algorithms for satellite scheduling problems[J]. Mobile Information Systems, 2012, 8(4): 351. DOI:10.1155/2012/717658
[12]WU Guohua, LIU Jin, MA Manhao, et al. A two-phase scheduling method with the consideration of task clustering for earth observing satellites[J]. Computers & Operations Research, 2013, 40(7): 1884. DOI:10.1016/j.cor.2013.02.009
[13]黄生俊, 邢立宁, 郭波. 基于改进模拟退火的多星任务规划方法[J]. 科学技术与工程, 2012, 12(31): 8293HUANG Shengjun, XING Lining, GUO Bo. Multi-satellites mission scheduling technique based on improved simulated annealing[J]. Science Technology and Engineering, 2012, 12(31): 8293
[14]MOUW C B, GREB S, AURIN D, et al. Aquatic color radiometry remote sensing of coastal and inland waters: challenges and recommendations for future satellite missions[J]. Remote Sensing of Environment, 2015, 160(2): 15. DOI:10.1016/j.rse.2015.02.001
[15]高黎. 对地观测分布式卫星系统任务协作问题研究[D]. 长沙: 国防科学技术大学, 2007: 68GAO Li. Resesrch on earth observation task cooperation for distributed satellites system[D]. Changsha: National University of Defense Technology, 2007: 68