HSBMAS - Hierarchical Switching-Backbone Multi-agent System

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*