HSBMAS - Hierarchical Switching-Backbone Multi-agent System

Bibtex

If this work is helpful for your research, please consider citing the following BibTeX entry.

@article{xie2024consensus,
  title={Consensus seeking in large-scale multiagent systems with hierarchical switching-backbone topology},
  author={Xie, Guangqiang and Xu, Haoran and Li, Yang and Wang, Chang-Dong and Zhong, Biwei and Hu, Xianbiao},
  journal={IEEE Transactions on Neural Networks and Learning Systems},
  year={2024},
  publisher={IEEE}
}

1. Introduction

It is well known that network topology plays a key role in the convergence theory of multi-agent systems, a sufficient condition for convergence is that the topology be sufficiently well connected over periodic windows of time ^[1]. Consider a traditional peer-to-peer multi-agent architecture where each agent communicates directly with all other perceived neighbors based on Select-All-Neighbors (SAN), each agent needs to select all neighbors in a communication region to update its own state using the consensus algorithm (1). However, the evolution of each agent is computationally infeasible when the number of neighbors increases exponentially and, the multi-agent system is prone to split into multiple clusters when the distribution of agents are irregular.

(1)

In this paper, we propose is a fully decentralized framework (HSBMAS) of multi-agent system for consensus seeking. The framework can control the convergence evolution with hierarchical features of the network topology by only referring to local one-hop and two-hop neighbors' state. Notably, the proposed framework runs in a distributed and synchronous fashion. The diagram of our framework is shown as

Fig 1. Illustration of the proposed framework

2. Dataset

This project contains the dataset of 10 types of topological structures in the square 20r_c × 20r_c and, each of which has five different densities described as ρ=N/L² and is connected initially. The density ρ represents that N agents distributed in a square-shape area of linear size L ^[2]. A total of 50 topologies with different densities (ρ≈2,4,6,8,10) and different types are used for interesting and fair comparisons across proposed architecture HSBMAS and traditional architecture SAN. The naming format of these topologies is: Type-N.

• Uniform-N: N agents are uniformly distributed over the semi open closed interval [-4, 4).
• Ring-N: N agents are randomly distributed on the ring with radius of 4.
• Vase-N: N agents are randomly distributed on the curve of Vase which is formed according to ^[3].
• Taiji-N: N-30 agents are uniformly distributed on the curve of Taiji. Besides, a vertical line composed of 30 agents is added to the center of Taiji to ensure initial connectivity.
• Circle-N: N agents are randomly distributed in the circle with radius of 4.
• Triangle-N: N agents are randomly distributed in equilateral triangle with side length 9.
• Square-N: N agents are randomly distributed in four concentric squares centered at the origin, the length of their sides from outside to inside are 1.6, 1.12, 0.64 and 0.16, respectively.
• Arch-N: 0.34N and 0.63N agents are randomly distributed on the curve of left and right 'archimedean spiral antenna' (abbr. 'Arch') respectively, and 0.03N agents are designed to connect two Archs. (Inspired by ^[4])
• Neat square-N: It is a neat topology generated by dividing a circle into 20 equal parts and placing an agent at equal radian intervals.
• Neat radiation-N: There are N agents neatly placed in a square area, the longitudinal and lateral gaps between nearest two agents are same.

The statistics of these initial topologies with varying densities are shown in Table I which contains the number of edges of adjacency matrix (i.e. #A-edges).

Table I. The statistics of designed topologies in the same range L = 20r_c

#A-edges	ρ≈2	ρ≈4	ρ≈6	ρ≈8	ρ≈10
Uniform	200	684	2118	3387	5848
Ring	549	1562	4484	8329	13036
Vase	744	3650	7669	13998	21441
Taiji	667	2054	4849	8654	14036
Circle	267	1141	2693	4670	7419
Triangle	278	1603	3721	6298	10195
Square	272	1120	2867	4990	7985
Arch	486	1921	4705	8271	13044
Neat square	420	840	1200	1624	3906
Neat radiation	890	2440	5040	8610	13190

Each topology is saved with an NPY file created by NumPy library, researchers can read it with any NPY software interface. The file contains the state information of all agents, and this dataset only involves two-dimensional state. For example:

[
    [x1, y1],   # the state of 1st agent
    [x2, y2],   # the state of 2nd agent
    ...
    [xn, yn],   # the state of n-th agent    
]

2.1 ρ≈2

Uniform-200	Ring-200	Vase-200	Taiji-200	Circle-200
Triangle-200	Square-200	Arch-200	Neat square-225	Neat radiation-200

2.2 ρ≈4

Uniform-400	Ring-400	Vase-400	Taiji-400	Circle-400
Triangle-400	Square-400	Arch-400	Neat square-441	Neat radiation-400

2.3 ρ≈6

Uniform-600	Ring-600	Vase-600	Taiji-600	Circle-600
Triangle-600	Square-600	Arch-600	Neat square-625	Neat radiation-600

2.4 ρ≈8

Uniform-800	Ring-800	Vase-800	Taiji-800	Circle-800
Triangle-800	Square-800	Arch-800	Neat square-841	Neat radiation-800

2.5 ρ≈10

Uniform-1000	Ring-1000	Vase-1000	Taiji-1000	Circle-1000
Triangle-1000	Square-1000	Arch-1000	Neat square-1024	Neat radiation-1000

License

The proposed dataset is released under the MIT License.

Reference

• [1] Nedić A, Olshevsky A, Rabbat M G. Network topology and communication-computation tradeoffs in decentralized optimization[J]. Proceedings of the IEEE, 2018, 106(5): 953-976.

• [2] Vicsek T, Czirók A, Ben-Jacob E, et al. Novel type of phase transition in a system of self-driven particles[J]. Physical review letters, 1995, 75(6): 1226-1229.

• [3] Dongdong Zha, Di Zhang, Huayong Liu. Construction of smooth blending of three-parameter curves and optimization of parameters[J]. Journal of Graphics, 2020, 41(05): 725-732. (in Chinese)

• [4] Kaiser J. The Archimedean two-wire spiral antenna[J]. IRE Transactions on Antennas and Propagation, 1960, 8(3): 312-323.