基于改进AGD-分布式多智能体系统的目标优化分配模型

doi:10.3969/j.issn.1001-506X.2020.04.17

Abstract

Abstract:

Because the modern battlefield environment is dynamic and the tasks are fulfilled in real-time, in view of the fact that the target allocation of weapons targets in current air defense operations is complex, traditional modeling cannot truly reflect the war process, with low confidence in the model, a weapon target assignment (WTA) model based on multi-Agent system (MAS) theory and distributed constrained optimization problem (DCOP) is proposed, and the improved accelerated gradient descent (AGD) algorithm is used to solve the model. The experiment proves that the algorithm has good convergence and low complexity, can adapt to the needs of modern air defense operations, meet the needs of large-scale optimization problems, and efficiently solve the problem of optimal allocation of multi-Agent targets.

Key words: multi-Agent system (MAS), distributed constraint optimization problem (DCOP), weapon target assignment (WTA), accelerated gradient descent (AGD)

CLC Number:

TP391.9

Jiayi LIU, Gang WANG, Jie ZHANG, Chuang WANG, Xituan SONG. Target optimal assignment model based on improved AGD-distributed multi-Agent system[J]. Systems Engineering and Electronics, 2020, 42(4): 863-870.

Figures/Tables 12

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Table 1

Table 2

Table 3

Fig.6

Fig.7

Table 4

Table 5

References 24

1	娄寿春. 地空导弹射击指挥控制模型[M]. 北京: 国防工业出版社, 2009.
	LOU S C . Ground-to-air missile firing command and control model[M]. Beijing: National Defense Industry Press, 2009.
2	LLOYD S P, WITSENHAUSEN H S.Weapons allocation is NP-complete[C]//Proc.of the IEEE Summer Conference on Simulation, 1986: 1054-1058.
3	韦刚, 高嘉乐, 孙文. 多目标-多武器系统目标分配模型与算法研究[J]. 飞航导弹, 2016, 5, 77- 82.
	WEI G , GAO J L , SUN W . Research on target assignment model and algorithm for multi-target-multi-weapon system[J]. Aerodynamic Missile Journal, 2016, 5, 77- 82.
4	郭张龙, 李为民, 王刚. 基于遗传算法的目标分配问题研究[J]. 现代防御技术, 2002, 30 (6): 3- 7. doi: 10.3969/j.issn.1009-086X.2002.06.002
	GUO Z L , LI W M , WANG G . The target allocation problem based on genetic algorithm[J]. Modern Defense Technology, 2002, 30 (6): 3- 7. doi: 10.3969/j.issn.1009-086X.2002.06.002
5	MODI P J , SHEN W M , TAMBE M , et al. Adopt: asynchronous distributed constraint optimization with quality guarantees[J]. Artificial Intelligence, 2005, 161 (1): 149- 180.
6	雷兴明, 邢昌风, 吴玲. 基于分布式约束优化的武器目标分配问题研究[J]. 计算机工程, 2012, 38 (7): 128- 130.
	LEI X M , XING C F , WU L . Research on weapon target assignment problem based on distributed constraint optimization[J]. Computer Engineering, 2012, 38 (7): 128- 130.
7	刘转.基于多智能体系统的兵棋推演模型研究[D].武汉:华中科技大学, 2016.
	LIU Z.Research on war game simulation based on multi-agent-system[D].Wuhan: Huazhong University of Science and Technology, 2016.
8	NGUYEN B, MIAH S.Analysis of maritime air defense scenarios[C]//Proc.of the 7th Symposlum on Computational Intelligence for Security and Defense Application, 2014: 687-695.
9	XUE L , SUN C , WUNSCH D C . A game-theoretical approach for a finite-time consensus of second-order multi-agent system[J]. International Journal of Control, Automation and Systems, 2019, 17 (5): 1071- 1083. doi: 10.1007/s12555-017-0716-8
10	HU W , LIU L , FENG G . .Output consensus of heterogeneous linear multi-agent systems by distributed event-triggered/self-triggered strategy[J]. IEEE Trans.on Cybernetics, 2017, 47 (8): 1914- 1924. doi: 10.1109/TCYB.2016.2602327
11	YIN X, TAN C, HUANG J J.Output consensus for networks of heterogeneous linear agents[C]//Proc.of the 36th Chinese Control Conference, 2017: 7679-7683.
12	YANG Y, ZHANG C X, WANG L, et al.Distributed event-triggered control with dynamic triggering mechanisms for multi-agent systems[C]//Proc.of the 29th Chinese Control and Decision Conference, 2017: 741-745.
13	KIM Y, LESSER V.DJAO: a communication-constrained DCOP algorithm that combines features of adopt and action-GDL[C]//Proc.of the 28th AAAI Conference on Artificial Intelligence, 2014: 2680-2687.
14	CHACHRA S, MAREFAT M. Distributed algorithms for sleep scheduling in wireless sensor networks[C]//Proc.of the International Conference on Robotics & Automation, 2006: 3101-3107.
15	王思远,王刚,张家瑞.基于变权TOPSIS法的防空目标威胁评估方法[EB/OL].[2019-04-09].http://kns.cnki.net/kcms/detail/61.1234.TJ.20190829.1517.007.html.
	WANG S Y, WANG G, ZHANG J R.Threat assessment method for air defense targets based on variable weight TOPSIS algorithm[EB/OL].[2019-04-09].http://kns.cnki.net/kcms/detail/61.1234.TJ.20190829.1517.007.html.
16	SOTNIK G . The SOSIEL platform:knowledge-based, cognitive, and multi-agent[J]. Biologically Inspired Cognitive Architectures, 2018, 26, 103- 117. doi: 10.1016/j.bica.2018.09.001
17	YOU X , HUA C C , GUAN X P . Distributed adaptive event-triggered control for leader following consensus of multi-agent systems[J]. Asian Journal of Control, 2017, 19 (6): 2155- 2164. doi: 10.1002/asjc.1516
18	CSDN.Detailed deep learning optimization functions[EB/OL].[2019-08-09].https://blog.csdn.net/tsyccnh/article/details/76064087.
19	BOTEV A, LEVER G, BARBER D.Nesterov's accelerated gradient and momentum as approximations to regularised update descent[C]//Proc.of the International Joint Conference on Neural Networks (IJCNN) 2017: 1899-1903.
20	SU W , BOYD S , CANDES E J . A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[J]. Advances in Neural Information Processing Systems, 2015, 3 (1): 2510- 2518.
21	JI S, YE J.An accelerated gradient method for trace norm minimization[C]//Proc.of the International Conference on Machine Learning, 2009: 457-464.
22	张杰, 王刚, 宋亚飞, 等. 基于自适应SGD-多智能体的防空资源部署优化[J]. 系统工程与电子技术, 2019, 41 (7): 1536- 1543.
	ZHANG J , WANG G , SONG Y F , et al. Optimization of air defense resource deployment based on adaptiveSGD-multi-agent[J]. Systems Engineering and Electronics, 2019, 41 (7): 1536- 1543.
23	LIU J M , JIN X L , ZHANG S W . Multi-agent systems.models and experimentation[M]. Beijing: Tsinghua University Press, 2003.
24	LI J , CHEN G , WU Z , et al. Distributed subgradient method for multi-agent optimization with quantized communication[J]. Mathematical Methods in the Applied Sciences, 2016, 40 (4): 1201- 1213.

算法	数据量	时间复杂度	空间复杂度
SGD	5 000 20 000 50 000	O(log₂n) O(log₂n) O(n²)	O(mⁿ) O(mⁿ) O(m)
改进AGD	5 000 20 000 50 000	O(n²) O(1) O(1)	O(m) O(m) O(m)

数据集	大小	训练集	测试集
Data_1	28×28	1 000	200
Data_2	28×28	1 000	500
Data_3	32×32	5 000	1 000

数据集	卷积层数	全连接层神经元个数	参数总数
Data_1	3	2¹⁰	2.8×10⁵
Data_2	3	2¹¹	1.9×10⁶
Data_3	8	2¹¹	2.0×10⁶

算法	限制时间/s	目标函数平均值
SGD	1 3 5	23.124 11.998 10.785
自适应SGD	1 3 5	22.333 10.556 10.116
改进AGD	1 3 5	9.417 9.065 8.913

算法	限制迭代次数	目标函数平均值
SGD	10 20 50	31.145 23.586 12.036
自适应SGD	10 20 50	29.566 22.223 10.014
改进AGD	10 20 50	20.865 9.874 9.135

Target optimal assignment model based on improved AGD-distributed multi-Agent system

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 24

Related Articles 6

Recommended Articles

Metrics

Comments

[1]	Ang GAO, Zhiming DONG, Liang LI, Jinghua SONG, Li DUAN. Parallel priority experience replay mechanism of MADDPG algorithm [J]. Systems Engineering and Electronics, 2021, 43(2): 420-433.
[2]	CHU Xiaogeng, MA Zhengwei, CHEN Xingjun. Look-ahead margin-greedy constructive algorithm for the multi-objective optimization of the weapon target assignment problem [J]. Systems Engineering and Electronics, 2019, 41(10): 2252-2259.
[3]	XU Hao, XING Qinghua, WANG Wei. WTA for air and missile defense based on fuzzy multi-objective programming [J]. Systems Engineering and Electronics, 2018, 40(3): 563-570.
[4]	TANG Su-yan, MEI Shan, ZHU Yi-fan, LEI Yong-lin, LI Qun. Distributed weapon target assignment algorithm based on extended contract net protocol [J]. Journal of Systems Engineering and Electronics, 2011, 33(3): 568-574.
[5]	MA Fei，CAO Ze-yang，LIU Hui. Construction and search of strategy space of target assignment based on game theory [J]. Journal of Systems Engineering and Electronics, 2010, 32(9): 1941-1945.
[6]	PENG Xingguang，GAO Xiaoguang. Dynamic target assignment method for UCAV fleet using memory enhanced dynamic UMDA [J]. Journal of Systems Engineering and Electronics, 2010, 32(10): 2166-2170.