Mean-Shift Shape Formation of Multi-Robot Systems Without Target Assignment

The methods of shape formation in robot swarms are usually classified into two categories by whether assignment is used or not. The first is to use target assignment to assemble precise formation. However, the additional algorithm for re-assignment is required to handle unreasonable situations, which results in lower efficiency. The second, also called assignment-free method, is to use local behaviors to assemble formation, however, existing methods can rarely achieve the precise formation. In this letter, we present a distributed assignment-free algorithm to achieve the precise shape formation based on the mean-shift algorithm. Specifically, each target location in robot's perception range is equally regarded as a point of the mean-shift vector. Then, the weight value of each point is computed according to the density of the target location. Here, each robot obtains the density of the target location according to the distribution of its neighbors. Moreover, this density calculation also considers the states of non-neighboring robots via the hop-count algorithm, thus avoiding conflicts among robots. Subsequently, each robot can regard the calculated mean-shift vector as its control command. Finally, simulation results show that our algorithm can form precise shapes at least 8 times more efficient than the assignment-based approach and physical experiment results confirm that the proposed algorithm exhibits promising potential for practical applications.