Decentralized coordinated motion for a large team of robots preserving connectivity and avoiding collisions

Abstract

We consider the general problem of moving a large number of networked robots toward a goal position through a cluttered environment while preserving network communication connectivity and avoiding both inter-robot collisions and collision with obstacles. In contrast to previous approaches that either plan complete paths for each individual robot in the high-dimensional joint configuration space or control the robot group as a whole with explicit constraints on the group's boundary and inter-robot pairwise distance, we propose a novel decentralized online behavior-based algorithm that relies on the topological structure of the multi-robot communication and sensing graphs to solve this problem. We formally describe the communication graph as a simplicial complex that enables robots to iteratively identify the frontier nodes and coordinate forward motion through the sensing graph. This approach is proved to automatically deform robot teams for collision avoidance and always preserve connectivity. The effectiveness of our approach is demonstrated using numerical simulations. The algorithm is shown to scale linearly in the number of robots.