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

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

Abstract

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)

CLC Number:

V474.2

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.

Figures/Tables 12

Fig.1

Table 1

Table 2

Table 3

Table 4

Table 5

Fig.2

Table 6

Table 7

Table 8

Fig.3

Fig.4

References 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

Balanced task allocation method for distributed satellite swarm game

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 30

Related Articles 10

Recommended Articles

Metrics

Comments

算法种类	平均运行时间/s	平均全局效益
SICBAA算法	0.12	7.845 1
GA算法	1.05	7.975 2
PSO算法	1.04	7.980 7

[1]	Chengfei YUE, Zhenghua XUE, Weiran YAO, Xibin CAO. Cooperative combat task allocation of multiple aerial vehicles based on the characteristic relation [J]. Systems Engineering and Electronics, 2022, 44(6): 1897-1906.
[2]	Jing ZHOU, Xiaozhe ZHAO, Zhen XU, Zhong LIN, Xiaopan ZHANG. Many-objective task allocation method based on D-NSGA-Ⅲ algorithm for multi-UAVs [J]. Systems Engineering and Electronics, 2021, 43(5): 1240-1247.
[3]	Han LI, Honghai ZHANG, Liandong ZHANG, Hao LIU. Multiple logistics unmanned aerial vehicle collaborative task allocation in urban areas [J]. Systems Engineering and Electronics, 2021, 43(12): 3594-3602.
[4]	WANG Jianhao, ZHANG Liang, SHI Chao, CHE Fei, ZHANG Pengtao. Task allocation modeling and solving algorithm for equipment support using DLS-BCIWBA [J]. Systems Engineering and Electronics, 2018, 40(9): 1979-1985.
[5]	CUI Ya-ni, REN Jia, DU Wen-cai. Time-sensitive task dynamic allocation algorithm for multi-UAVs in battlefield environments [J]. Systems Engineering and Electronics, 2016, 38(4): 828-835.
[6]	YAO Peiyang1， WAN Lujun1,2， SUN Peng1， ZHOU Xiangxiang3. Dynamic task allocation in multiple agent groups based on RHPIVFSA [J]. Systems Engineering and Electronics, 2014, 36(7): 1309-1319.
[7]	WAN Lu-jun， YAO Pei-yang， SUN Peng. Distributed task allocation method of manned/unmanned combat Agents [J]. Journal of Systems Engineering and Electronics, 2013, 35(2): 310-316.
[8]	LIANG Xiao-long，HU Jun-hua，JING Xian-yong，LIU An，FENG Jin-fu. Multi-stage optimization model and algorithm for near space multi-weapon platform attacking ground targets [J]. Journal of Systems Engineering and Electronics, 2010, 32(12): 2618-2622.
[9]	TANG Suyan，ZHU Yifan，LI Qun，LEI Yonglin. Survey of task allocation in multi Agent systems [J]. Journal of Systems Engineering and Electronics, 2010, 32(10): 2155-2161.
[10]	LI Wei-xiang, ZHANG Guang-ming, LI Bang-yi. Research on multi-attributes task allocation mechanism in MAS [J]. Journal of Systems Engineering and Electronics, 2009, 31(5): 1113-1116.

全局效益	目标卫星	红方卫星	个体效益
7.898 5	1	6	2.970 2
	2	3	2.967 9
	3	1	0.326 8
		2	0.326 8
		4	0.326 8
		5	0.326 9
		7	0.326 9
		8	0.327 0

全局效益	目标卫星	红方卫星	个体效益
7.900 2	1	4	2.971 0
	2	3	2.967 9
	3	1	0.326 8
		2	0.326 8
		5	0.326 9
		6	0.326 9
		7	0.326 9
		8	0.327 0