Connectivity-Preserving Formation Control via Clique-Based Approach Without Prior Assignment

This paper explores information sharing within cliques to enable flexible formation pattern control of networked agents with limited communication range, where each agent is not pre-assigned a fixed point in the pattern and is unaware of the total number of agents. To achieve this, we first present a new representation of formation patterns that enables the agents to reach a consensus on the desired pattern by negotiating formation motion and agent numbers. The problem of continuously assigning each agent a point in the desired pattern is then decomposed into small size problems in terms of $δ$-maximal cliques, which can be solved in a distributed manner. Furthermore, a maximal clique-based formation controller is employed to ensure that the agents converge to the desired pattern while preserving the connectivity of the communication topology. Simulation results demonstrate that the pattern assembly time of seven agents using the proposed algorithm is reduced by 55.1% compared with a state-of-the-art pre-assigned method, and this improvement tends to amplify with an increasing number of agents. In addition, we conduct a physical experiment involving five robots to verify the ability of the proposed algorithm in terms of formation shape assembly, manipulation, and automatic repair.