Decentralized Coordinated Motion for Robot Teams Preserving Connectivity and Avoiding Collisions

Anqi Li
Tech. Report, CMU-RI-TR-17-14, Robotics Institute, Carnegie Mellon University, May, 2017

Download Publication

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.


In this thesis, we consider the general problem of moving a large number of networked robots toward a goal position through a cluttered environment under constraints on network connectivity and collision avoidance. 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 distances, 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 %to visit 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.

author = {Anqi Li},
title = {Decentralized Coordinated Motion for Robot Teams Preserving Connectivity and Avoiding Collisions},
year = {2017},
month = {May},
institution = {Carnegie Mellon University},
address = {Pittsburgh, PA},
number = {CMU-RI-TR-17-14},
keywords = {Multi-Robot Systems, Decentralized Algorithms, Algebraic Topology},
} 2017-09-13T10:38:06-04:00