Distributed Multiple Shape Formation in Homogeneous Robot Swarms

摘要

In this paper, we study the problem of simultaneous formation of multiple shapes in homogeneous swarms, which is rarely explored. Compared to single shape formation, distributed multiple shape formation faces the following challenges: how to divide the swarm into several sub-swarms for multiple shapes and how to satisfy several constraints between shapes, such as avoiding overlap, maintaining shape order, and preserving swarm connectivity after shape completion. To handle these challenges, we propose the following novel results. First, a distributed game-theoretic clustering algorithm considering the sub-swarm size is proposed to divide the robot swarm into several balanced sub-swarms. This balanced division can ensure that each shape can be achieved by several robots, rather than none. Second, each robot can solve a mixed integer convex quadratic optimization problem to determine multi-shape parameters (shape sizes and positions) to satisfy several necessary constraints. Unlike existing shape optimization methods, this optimization does not require the states of all robots, thus achieving distributed control. Third, we propose a robust strategy for robots against swarm-scale variants via fine-tuning existing clustering results and shape parameters. In particular, the previous work on single shape control can drive each sub-swarm to achieve its corresponding shape. Finally, both simulation and experiment with 11 physical robots verify the effectiveness and robustness of the proposed algorithm.