Abstract. This paper studies connectivity maintenance in robotic networks. We propose a distributed coordination algorithm that can be combined with the individual motion control strategies of the robotic agents to maintain the overall network connectivity. The coordination algorithm is based on the idea of maintaining the edges of an evolving spanning tree of the communication graph, termed the constraint tree. The evolution of this tree is determined by the preferences that each agent possesses as to which other agents it would like to maintain connectivity with, the network configuration, and the allowed set of re-arrangement operations. We analyze the reachability and repair properties of the proposed algorithm. Regarding reachability, we show that the constraint tree can transition between any two trees which are subgraphs of the current communication graph. Regarding repair, we show that the algorithm is robust against link drops in the constraint tree and can repair an initially disconnected constraint tree. We provide simulations of the performance of the algorithm in deployment scenarios. 1. Introduction. Given a group of robots with processing, motion, and communication capabilities executing a motion coordination algorithm to achieve some task, we set out to address the following problem: how can we guarantee that the graph induced by the inter-agent communication remains connected? Surprisingly, many coordination algorithms for robotic networks fail to maintain connectivity under simple communication models. Tasks such as "deploy over a region of interest" or "explore an area" are examples where the control objective naturally conflicts with the goal of staying close enough to maintain global network connectivity. Even tasks which appear not to conflict with the concept of network cohesiveness can cause connectivity to fail. Consider a robotic network where any pair of robots within a certain distance can communicate. For such networks, it turns out that simple averaging algorithms that achieve flocking [28] and rendezvous [24] can easily fail to maintain connectivity, see Figure 1 .1(a). Another example where connectivity maintenance is not guaranteed is the motion planning problem between two network configurations in physical space. A simple linear interpolation between the initial and final configurations does not guarantee that connectivity is preserved during the evolution, even if the network at the two configurations is connected, see Figure 1 .1(b). A strategy to solve the connectivity problem is to make custom modifications to each motion control algorithm to enforce inter-agent connectivity constraints. It is desirable, however, to synthesize a general methodology for maintaining connectivity that goes beyond a case by case study, and can be used in conjunction with any motion coordination algorithm. In this paper we take on this aim and propose an approach based on the preservation of a spanning tree of the underlying communication graph. The idea is to synthesize a distributed algorithm to agree upon "safe" re-arrangements of the spanning tree (i.e., re-arrangements that do not break connectivity or cause
In REF , a high-level method is presented for managing tree topologies, which can be combined with motion tasks such as coverage, but the connections between the successive trees and the minimum spanning tree of the communication graph have not been established yet.
DISTRIBUTED TREE REARRANGEMENTS FOR REACHABILITY AND ROBUST CONNECTIVITY ∗
SIAM J. Control and Optimization
SIAM J. Control and Optimization
Mathematics Computer Science