分布式卫星集群博弈任务均衡分配方法

doi:10.12305/j.issn.1001-506X.2023.06.23

摘要/Abstract

摘要：

针对分布式卫星集群博弈任务中的分配不均衡问题，提出了一种基于偏好联盟博弈(hedonic coalition game，HCG)的任务分配方法。首先，在考虑燃料和时间最优的卫星集群任务分配模型的基础上，引入对敌毁伤概率以适应集群博弈背景；其次，为保证分配结果的均衡性，引入HCG设计个体联盟特征函数；最后，考虑卫量集群的一对多作战分配方式难以保证局部兵力优势，在一致性拍卖算法(consensus based auction algorithm，CBAA)结构上拓展性地提出了一种多对一任务分配算法。仿真结果表明，该算法在全局效益接近经典集中式算法全局效益98%的前提下，时间约为经典算法的70%，且该算法具有一定的问题规模拓展性。

关键词: 分布式卫星集群, 任务分配, 偏好联盟博弈, 一致性拍卖算法

Abstract:

Aiming at the unbalanced distribution of task allocation in distributed satellite swarm game, a task allocation method based on hedonic coalition game (HCG) is proposed in this paper. Firstly, the probability of enemy damage is introduced to adapt to the background of swarm game based on the satellite swarm task allocation model which considers the optimal fuel and time. Secondly, to ensure the balance of the allocation results, the HCG is introduced to design the individual coalition characteristic function. Finally, a single-task and multi-robot task allocation algorithm is designed based on consensus based auction algorithm (CBAA) structure, considering that it is difficult to guarantee the local force advantage of satellite swarm one-to-multiple combat mode. The simulation results show that the proposed algorithm could achieve 98% of the global efficiency and 70% of the time of the classical algorithm, and the proposed algorithm has a certain scalability of the problem size.

Key words: distributed satellite swarm, task allocation, hedonic coalition game (HCG), consensus based auction algorithm (CBAA)

中图分类号:

V474.2

钱寒雨, 田晓曼, 肖冰, 曹璐, 王锐, 吴西伟. 分布式卫星集群博弈任务均衡分配方法[J]. 系统工程与电子技术, 2023, 45(6): 1797-1804.

Hanyu QIAN, Xiaoman TIAN, Bing XIAO, Lu CAO, Rui WANG, Xiwei WU. Balanced task allocation method for distributed satellite swarm game[J]. Systems Engineering and Electronics, 2023, 45(6): 1797-1804.

图/表 12

图1

表1

表2

表3

表4

表5

图2

表6

表7

表8

图3

图4

参考文献 30

1	JAIN R . Efficient market mechanisms and simulation-based learning for multi-agent systems[M]. California: Press of University of California at Berkeley, 2004.
2	YANG W Y , HE L , LIU X L , et al. Onboard coordination and scheduling of multiple autonomous satellites in an uncertain environment[J]. Advances in Space Research, 2021, 68 (11): 4505- 4524. doi: 10.1016/j.asr.2021.09.003
3	MUSHET G , MINGOTTI G , COLOMBO C , et al. Self-organising satellite constellation in geostationary earth orbit[J]. IEEE Trans.on Aerospace and Electronic Systems, 2015, 51 (2): 910- 923. doi: 10.1109/TAES.2014.130690
4	CHEN B T , WANG L Q , JIANG X M , et al. Survey of task assignment for crowd-based cooperative computing[J]. Computer Engineering and Application, 2021, 57 (20): 1- 12.
5	SEENU N , CHETTY R M K , RAMYA M M , et al. Review on state-of-the-art dynamic task allocation strategies for multiple-robot systems[J]. Industrial Robot-the International Journal of Robotics Research and Application, 2020, 47 (6): 929- 942. doi: 10.1108/IR-04-2020-0073
6	WANG Z J , ZHU J L , GUO X P , et al. Distributed task allocation method based on self-awareness of autonomous robots[J]. Journal of Supercomputing, 2020, 76 (2): 831- 843. doi: 10.1007/s11227-019-02987-3
7	GUO C B , XIA X W , SI C M , et al. A survey of relative position and attitude measurement for formation flying satellite[J]. Aerospace Control, 2018, 36 (6): 83- 89.
8	颜骥, 李相民, 刘波. 考虑时序约束的多智能体协同任务分配[J]. 控制与决策, 2015, 30 (11): 1999- 2003. doi: 10.13195/j.kzyjc.2014.1114
	YAN J , LI X M , LIU B . Multi-agents cooperative task allocation with precedence constrains[J]. Control and Decision, 2015, 30 (11): 1999- 2003. doi: 10.13195/j.kzyjc.2014.1114
9	陈菲, 路长厚, 潘伟, 等. 微型卫星集群系统协同任务下的目标分配研究[J]. 宇航学报, 2010, 31 (5): 1374- 1380. doi: 10.3873/j.issn.1000-1328.2010.05.020
	CHEN F , LU C H , PAN W , et al. Research on target assignment in collaborative task of micro-satellite system[J]. Journal of Astronautics, 2010, 31 (5): 1374- 1380. doi: 10.3873/j.issn.1000-1328.2010.05.020
10	黄勇, 李小将, 张东来, 等. 分布式卫星系统在轨操作的多目标分配[J]. 宇航学报, 2013, 34 (11): 1475- 1482. doi: 10.3873/j.issn.1000-1328.2013.11.009
	HUANG Y , LI X J , ZHANG D L , et al. A multi-target assignment method for on-orbit operation of distributed satellites system[J]. Journal of Astronautics, 2013, 34 (11): 1475- 1482. doi: 10.3873/j.issn.1000-1328.2013.11.009
11	杜永浩, 邢立宁, 蔡昭权. 无人飞行器集群智能调度技术综述[J]. 自动化学报, 2020, 46 (2): 222- 241. doi: 10.16383/j.aas.c170681
	DU Y H , XING L N , CAI Z Q . Survey on intelligent scheduling technologies for unmanned flying craft clusters[J]. Acta Automatica Sinica, 2020, 46 (2): 222- 241. doi: 10.16383/j.aas.c170681
12	TRIPP H , PALMER P . Stigmergy based behavioural coordination for satellite clusters[J]. Acta Astronautica, 2010, 66 (7/8): 1052- 1071.
13	CHOI H L , BRUNET L , HOW J P . Consensus-based decentralized auctions for robust task allocation[J]. IEEE Trans.on Robotics, 2009, 25 (4): 912- 926. doi: 10.1109/TRO.2009.2022423
14	PONDA S S, REDDING J, CHOI H L, et al. Decentralized planning for complex missions with dynamic communication constraints[C]// Proc. of the IEEE American Control Conference, 2010.
15	YANG M , BI W H , ZHANG A , et al. A distributed task reassignment method in dynamic environment for multi-UAV system[J]. Applied Intelligence, 2022, 52 (2): 1582- 1601. doi: 10.1007/s10489-021-02502-3
16	万路军, 姚佩阳, 孙鹏. 有人/无人作战智能体分布式任务分配方法[J]. 系统工程与电子技术, 2013, 35 (2): 310- 316. doi: 10.3969/j.issn.1001-506X.2013.02.13
	WAN L J , YAO P Y , SUN P . Distributed task allocation method of manned/unmanned combat agents[J]. Systems Engineering and Electronics, 2013, 35 (2): 310- 316. doi: 10.3969/j.issn.1001-506X.2013.02.13
17	XIE B , CHEN S F , CHEN J , et al. A mutual-selecting market-based mechanism for dynamic coalition formation[J]. International Journal of Advanced Robotic Systems, 2018, 15 (1): 1- 10.
18	JANG I , SHIN H S , TSOURDOS A . Anonymous hedonic game for task allocation in a large-scale multiple agent system[J]. IEEE Trans.on Robotics, 2017, 34 (6): 1534- 1548.
19	BOND V R , ALLMAN M C . Modern astrodynamics: fundamentals and perturbation methods[M]. Princeton: Princeton University Press, 2021.
20	FARNOCCHIA D , CIOCI D B , MILANI A . Robust resolution of Kepler's equation in all eccentricity regimes[J]. Celestial Mechanics & Dynamical Astronomy, 2013, 116 (1): 21- 34.
21	ADURTHI N , MAJJI M . Uncertain Lambert problem: a probabilistic approach[J]. Journal of the Astronautical Sciences, 2020, 67 (2): 361- 386. doi: 10.1007/s40295-019-00205-z
22	GATLAND I R . Gravitational orbits and the Lambert problem[J]. American Journal of Physics, 2022, 90 (3): 177- 178. doi: 10.1119/5.0060998
23	XIN B , WANG Y P , CHEN J . An efficient marginal-return-based constructive heuristic to solve the sensor-weapon-target assignment problem[J]. IEEE Trans.on Systems, Man, Cybernetics: Systems, 2019, 49 (12): 2536- 2547. doi: 10.1109/TSMC.2017.2784187
24	SHALUMOV V , SHIMA T . Weapon-target-allocation strategies in multiagent target-missile-defender engagement[J]. Journal of Guidance, Control and Dynamics, 2017, 40 (10): 2452- 2464. doi: 10.2514/1.G002598
25	HOCAOGLU M F . Weapon target assignment optimization for land based multi-air defense systems: a goal programming approach[J]. Computers & Industrial Engineering, 2019, 128 (9): 681- 689.
26	NG J S , LIM W Y B , XIONG Z H , et al. Reputation-aware hedonic coalition formation for efficient serverless hierarchical federated learning[J]. IEEE Trans.on Parallel and Distributed Systems, 2022, 33 (11): 2675- 2686.
27	KARAKAYA M , KLAUS B . Hedonic coalition formation games with variable populations: core characterizations and (im)possibilities[J]. International Journal of Game Theory, 2017, 46 (2): 435- 455. doi: 10.1007/s00182-016-0533-y
28	CZARNECKI E , DUTTA A . Scalable hedonic coalition formation for task allocation with heterogeneous robots[J]. Intelligent Service Robotics, 2021, 14 (3): 501- 517. doi: 10.1007/s11370-021-00372-9
29	HE Q Z, TIAN Y, LI D C, et al. Satellite imaging task planning using particle swarm optimization and Tabu search[C]// Proc. of the IEEE 21st International Conference on Software Quality, Reliability and Security, 2021.
30	SHIMA T , RASMUSSEN S J , SPARKS A G , et al. Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms[J]. Computers & Operations Research, 2006, 33 (11): 3252- 3269.

轨道根数	半长轴/km	偏心率	轨道倾角/(°)	升交点赤经/(°)	近地点俯角/(°)
红方卫星轨道	8 735	0.05	15.0	30	45
蓝方卫星轨道	8 735	0.05	30.0	30	45

卫星编号	作战能力	位置/km			速度/(km/s)
卫星编号	作战能力	X	Y	Z	V_X	V_Y	V_Z
1	1.56	-6 713.0	222.2	5 648.2	-0.56	6.69	-0.41
2	1.20	-6 011.1	5 051.9	4 416.9	2.29	5.52	-2.67
3	1.81	-3 825.0	8 008.5	2 177.6	4.09	3.15	-3.87
4	1.04	-852.1	9 117.7	-483.2	4.89	0.21	-4.16
5	1.63	2 670.3	8 029.3	-3 318.6	4.53	-3.14	-3.42
6	1.28	6 178.3	2 830.6	-5 599.1	1.83	-6.41	-0.70
7	1.40	6 544.9	-1 576.2	-5 327.2	-0.78	-6.65	1.54
8	1.12	3 239.0	-7 459.8	-1 754.4	-4.72	-2.96	4.38

卫星编号	作战能力	位置/km			速度/(km/s)			目标价值
卫星编号	作战能力	X	Y	Z	V_X	V_Y	V_Z	目标价值
1	1.32	990.2	2 231.3	-8 471.0	-1.20	6.47	1.22	6.0
2	1.05	9.1	6 394.0	-6 374.9	-1.42	4.67	4.34	6.0
3	1.13	-940.4	8 707.3	-2 651.6	-1.24	1.81	6.05	4.0

红方编号	敌方编号
	卫星1		卫星2		卫星3
	燃料消耗/kg	变轨时长/s	燃料消耗/kg	变轨时长/s	燃料消耗/kg	变轨时长/s
1	9.91	2 531	9.66	2 695	9.57	2 767
2	8.16	3 849	8.67	3 321	8.79	3 235
3	9.86	2 448	9.29	2 768	8.76	3 151
4	9.15	2 747	8.50	3 255	6.43	3 060
5	10.33	2 175	6.49	2 043	6.49	2 550
6	6.70	3 280	8.12	3 821	6.71	2 497
7	6.88	2 361	9.11	3 601	10.33	2 903
8	11.31	2 090	9.74	3 492	11.07	2 455

全局效益	目标卫星	红方卫星	个体效益
7.843 8	1	1	0.973 2
		5	0.972 6
		8	0.972 9
	2	2	0.998 9
		3	0.998 9
		4	0.998 9
	3	6	0.964 3
	3	7	0.964 1