Maximum-Leaf Spanning Trees for Efficient Multi-Robot Recovery with Connectivity Guarantees

This paper presents a self-stabilizing distributed algorithm for the recovery of a large population of robots in a complex environment—that is, to gather them
all in a goal location. We assume the robots do not have a map of the environment, but instead use short-range network communications and local sensing to physically
route themselves towards the goal location. Since the robot’s motion can disrupt robots network communication and localization in complex environments, we
desire an algorithm that can maintain connectivity while preserving efficient operation. Our approach constructs a spanning tree for physical routing, but only allows
the leaves of this tree to navigate the goal location. This distributed maximum-leaf
spanning tree (DMLST) ensures connectivity, while providing an efficient recovery
by allowing the maximum number of robots to be mobile. We present empirical results
on the competitive ratio of the DMLST and it is very good, approaching the
optimal solution for our communication network. DMLST recovery has been tested
in simulation, and implemented on a system of thirteen robots. While a basic recovery
fails in all experiments, the DMLST recovery succeeds efficiently in most

Golnaz Habibi, James McLurkin
International Symposium on Distributed Autonomous Robotic Systems