A distributed self-clustering algorithm for autonomous multi-agent systems

In this paper, we consider clustering in autonomous multi-agent systems where the agents, assumed to belong to either `blue´ or `red´ type, engage in local location-swaps to physically separate the network into two connected clusters. The groupings (red/blue) may reflect hardware differences or some other distinguishing factor that differs across groups. We present a randomized algorithm, Naïve Swap, where the agents randomly swap their locations with an arbitrary neighbor. We then provide two modifications to this naïve strategy, Intelligent Swap and Stable Marriage Swap, that are based on truncated average-consensus and the Gale-Shapley algorithm for solving the stable marriage problem, respectively. These modifications serve as an improvement upon the randomized (naïve) location-swaps by using information on the group association of neighbors to guide swapping decisions. We provide a sketch for the analysis of the proposed schemes via an irreducible Markov chain analogy. We further show the effectiveness of the proposed strategies via simulations.