Multiagent Following Multileader Algorithm Based on K-means Clustering

doi:10.16182/j.issn1004731x.joss.21-1158

Abstract

Abstract:

Three K-means clustering algorithms are proposed to prevent chaos in the formation of a multi-agent system (MAS) with multiple leaders. The algorithm divides the cluster into communities with the same number of leaders, and the agents within the community will follow the same leader. Among the three proposed algorithms, algorithm #1 is suitable for scenarios with widely distributed agents wherein rapid consensus can be achieved in the shortest time; algorithm #2 is suitable for scenarios with a sparse agent distribution and effectively prevented agent collisions; and algorithm #3 exhibits rapid convergence and considerably reduces the MAS control cost, but will sacrifice the convergence speed of the system.. Unlike the traditional method in which the agents are numbered and the leader-follower relationship is fixed, the proposed clustering methods can shorten the MAS convergence time and effectively adapt to task changes by rapidly assigning new suitable tasks to agents.

Key words: multi-agent, multiple leaders, K-means, pinning control, clustering methods

CLC Number:

TP391.9

Guodong Yuan, Ming He, Ziyu Ma, Weishi Zhang, Xueda Liu, Wei Li. Multiagent Following Multileader Algorithm Based on K-means Clustering[J]. Journal of System Simulation, 2023, 35(3): 616-622.

Figures/Tables 9

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Table 1

Fig. 5

Fig. 6

Table 2

Table 3

References 21

1	吴虎胜, 张凤鸣, 吴庐山. 一种新的群体智能算法——狼群算法[J]. 系统工程与电子技术, 2013, 35(11): 2430-2438.
	Wu Husheng, Zhang Fengming, Wu Lushan. New Swarm Intelligence Algorithm-Wolf Pack Algorithm[J]. Journal of Systems Engineering and Electronics, 2013, 35(11): 2430-2438.
2	Cavagna A, Cimarelli A, Giardina I, et al. Scale-Free Correlations in Starling Flocks[J]. Proceedings of the National Academy of Sciences (S0369-8211), 2010, 107(26): 11865-11870.
3	Li Xiaolei, Lu Fei, Tian Guohui, et al. Applications of Artificial Fish School Algorithm in Combinatorial Optimization Problems[J]. Journal of Shandong University (Engineering Science) (S1672-3961), 2004, 34(5): 64-67.
4	Tarasewich P, Mcmullen P R. Swarm Intelligence[J]. Communications of the Acm (S0001-0782), 2002, 45(8): 62-67.
5	Ren W, Beard R W. Consensus Seeking in Multiagent Systems under Dynamically Changing Interaction Topologies[J]. IEEE Transactions on Automatic Control (S0018-9286), 2005, 50(5): 655-661.
6	Li Zhongkui, Wen Guanghui, Duan Zhisheng, et al. Designing Fully Distributed Consensus Protocols for Linear Multi-agent Systems with Directed Graphs[J]. IEEE Transactions on Automatic Control (S0018-9286), 2015, 60(4): 1152-1157.
7	Liu Bo, Su Housheng, Li Rong, et al. Switching Controllability of Discrete-Time Multi-agent Systems with Multiple Leaders and Time-Delays[J]. Applied Mathematics & Computation (S0096-3003), 2014, 228: 571-588.
8	Hou Wenying, Wu Zongze, Fu Mingyue, et al. Constrained Consensus of Discrete-Time Multi-agent Systems with Time Delay[J]. International Journal of Systems Science (S0020-7721), 2018, 49(5): 1-7.
9	Wang Dong, Wang Wei. Necessary and Sufficient Conditions for Containment Control of Multi-agent Systems with Time Delay[J]. Automatica (S0005-1098), 2019, 103: 418-423.
10	Liang J, Liu K, Ji Z, et al. Event-Triggered Consensus Control for Linear Multi-agent Systems[J]. IEEE Access (S2169-3536), 2019, 7: 144572-144579.
11	Garcia E, Cao Y, Casbeer D W. Decentralized Event-Triggered Consensus with General Linear Dynamics[J]. Automatica (S0005-1098), 2014, 50(10): 2633-2640.
12	Olfati-Saber R. Flocking for Multi-agent Dynamic Systems: Algorithms and Theory[J]. IEEE Transactions on Automatic Control (S0018-9286), 2006, 51(3): 401-420.
13	Hu Y, Su H, Lam J. Adaptive Flocking with A Virtual Leader of Multiple Agents Governed by Locally Lipschitz Nonlinearity[J]. International Journal of Robust & Nonlinear Control (S1049-8923), 2013, 23(9): 978-990.
14	Fan S, Guo Y, Ji Y. Fixed-Time Consensus for Leader-Following Multi-groups of Multi-agent Systems with Unknown Non-Linear Inherent Dynamics[C]// The 38th Chinese Control Conference (CCC2019). Guangzhou: TCCT, 2019: 5903-5908.
15	Couzin I, Krause J, Franks N, et al. Effective Leadership and Decision-Making in Animal Groups on the Move[J]. Nature (S0028-0836), 2005, 433: 513-516.
16	Gao Leitao, Zhao Guangshe, Li Guoqi, et al. Containment Control of Directed Networks with Time-Varying Nonlinear Multi-agents Using Minimum Number of Leaders[J]. Physica, A. Statistical Mechanics and Its Applications (S0378-4371), 2019, 526: 120859.
17	Fortunato Santo. Community Detection in Graphs[J]. Physics Reports (S0034-4877), 2010, 486: 75-174.
18	Zhu X, Ghahramani Z. Learning from Labeled and Unlabeled Data with Label Propagation[J]. Tech Report (S1348-0677), 2002, 54: 2865.
19	X Y Leung Ian, Pan Hui, Lio' Pietro, et al. Towards Real-Time Community Detection in Large Networks[J]. Physical Review E (S1539-3755), 2009, 79(6): 066107.
20	Wong J, Wong M. Algorithm AS 136: A K-means Clustering Algorithm[J]. Journal of the Royal Statistical Society (S0952-8385), 1979, 28(1): 100-108.
21	何明, 马子玉, 刘锦涛, 等. 基于影响度介数中心性的多智能体牵制控制算法[J]. 控制与决策, 2021, 36(6): 1442-1448.
	He Ming, Ma Ziyu, Liu Jingtao, et al. Multi-agent Pinning Control Algorithm Based on Betweenness Centrality with Influence Degree[J]. Control and Decision, 2023, 36(6): 1442-1448.

领导者	初始位置	速度/(m/s)
1	(50, 10)	(0.8, -2)
2	(90, 28)	(0.2, -1.1)
3	(30, 55)	(1.2, 2.5)
4	(91, 95)	(2.2, -0.3)
5	(63, 78)	(0.8, 0)

算法	样本1	样本2	样本3	样本4	样本5
1	8.530 1	7.648 3	8.165 8	8.413 5	8.401 1
2	7.837 6	7.493 7	7.629 1	7.966 7	7.793 1
3	7.856 9	7.454 4	7.655 6	7.962 3	7.731 7

算法	样本1	样本2	样本3	样本4	样本5	平均值
1	29.0	48.2	52.5	48.5	78.6	51.36
2	34.4	56.6	84.2	89.1	90.3	70.92
3	59.2	88.4	90.4	102.1	96.2	87.26

[1]	Xu Wang, Weidong Ji, Guohui Zhou, Jiahui Yang. Multi-objective Optimization Algorithm Based on Multi-index Elite Individual Game Mechanism [J]. Journal of System Simulation, 2023, 35(3): 494-514.
[2]	Weidong Ji, Yuqi Yue, Xu Wang, Ping Lin. Large-scale Multi-objective Natural Computation Based on Dimensionality Reduction and Clustering [J]. Journal of System Simulation, 2023, 35(1): 41-56.
[3]	Junren Luo, Wanpeng Zhang, Weilin Yuan, Zhenzhen Hu, Shaofei Chen, Jing Chen. Research on Opponent Modeling Framework for Multi-agent Game Confrontation [J]. Journal of System Simulation, 2022, 34(9): 1941-1955.
[4]	Miaojia Lu, Chengyuan Huang, Jing Teng. Multi-agent Simulation for Online Fresh Food Autonomous Delivery [J]. Journal of System Simulation, 2022, 34(6): 1185-1195.
[5]	Lingjia Ni, Xiaoxia Huang, Hongga Li, Zibo Zhang. Research on Fire Emergency Evacuation Simulation Based on Cooperative Deep Reinforcement Learning [J]. Journal of System Simulation, 2022, 34(6): 1353-1366.
[6]	Xin Zhou, Weiping Wang, Yifan Zhu, Tao Wang, Tian Jing. An Unmanned Swarm Search Method Based on Human-Robot Cooperation [J]. Journal of System Simulation, 2022, 34(4): 735-744.
[7]	Feng Li, Ying Wei. Product Decisions in Presence of Social Learning and Reference Point Effect [J]. Journal of System Simulation, 2022, 34(2): 234-246.
[8]	Qiao Qiao, Yan Wang, Zhicheng Ji. Multi-robot Path Planning Based on CBS Algorithm [J]. Journal of System Simulation, 2022, 34(12): 2659-2669.
[9]	Qi Xiaolong, Yang Xuguang. Time-varying Output Formation Tracking Control of Discrete-time Heterogeneous Multi-agent Systems [J]. Journal of System Simulation, 2022, 34(1): 36-44.
[10]	Li Yuan, Geng Zewei. Fault Diagnosis of Industrial Process Based on LLE and K-means Clustering Algorithm [J]. Journal of System Simulation, 2021, 33(9): 2066-2073.
[11]	Cong Jiping, Cui Lijie, Ding Gang, Ren Bo. Simulation on Aviation Maintenance Support System Based on Goal-driven [J]. Journal of System Simulation, 2021, 33(9): 2157-2165.
[12]	Zhao Yu, Guo Jifeng, Yan Peng, Bai Chengchao. Self-learning-based Multiple Spacecraft Evasion Decision Making Simulation Under Sparse Reward Condition [J]. Journal of System Simulation, 2021, 33(8): 1766-1774.
[13]	Zhao Zhu, Wang Yi, Fan Ruifeng, Li Liya, Qi Meng. Modeling on Anti-UAV System-of-systems Combat OODA Loop Based on NetLogo [J]. Journal of System Simulation, 2021, 33(8): 1791-1800.
[14]	Gui Xindong, Ji Hongjiang, Fan Lingling, Liu Shida. Application of Trust Driven Adaptive Cooperative Control Algorithm [J]. Journal of System Simulation, 2021, 33(8): 1809-1817.
[15]	Li Wenxiang, Li Ye, Dong Jieshuang, Li Yiming. Development Paths of New Energy Vehicles Incorporating CO₂ Emissions Trading Scheme [J]. Journal of System Simulation, 2021, 33(6): 1451-1465.