## Abstract

Communication connectivity is desirable for the safe and efficient operation of multi-robot systems. While decentralized algorithms for connectivity maintenance have been explored in recent literature, the majority of these works do not account for robot motion and sensing uncertainties. These uncertainties are inherent in practical robots and result in robots deviating from their desired positions which could potentially result in a loss of connectivity. In this paper, we present a decentralized connectivity maintenance algorithm accounting for robot motion and sensing uncertainties (DCMU). We, first, propose a novel weighted graph definition for the multi-robot system that accounts for the aforementioned uncertainties along with realistic connectivity constraints such as line-of-sight connectivity and collision avoidance. We, then, design a decentralized gradient-based controller for connectivity maintenance with which we derive the gradients of the weighted graph edge weights required for computing the control. Finally, we perform multiple simulations to validate the connectivity maintenance performance of our DCMU algorithm under robot motion and sensing uncertainties, showing an improvement compared to previous work.

- connectivity maintenance
- decentralized algorithms
- gradient-based control
- motion and sensing uncertainties
- multi-robot systems

## 1 INTRODUCTION

Multi-robot systems are increasingly being used for various tasks such as exploration, target tracking, and search and rescue (Cortés & Egerstedt, 2017; Rizk et al., 2019). One of the primary advantages of multi-robot systems is their ability to coordinate using inter-robot communication, which allows them to execute complex tasks in a safe and efficient manner (Alanwar et al., 2019; Bhamidipati & Gao, 2019; Park & Hutchinson, 2018). Thus, it is highly desirable to maintain communication connectivity within a multi-robot system.

Existing literature has explored decentralized algorithms for connectivity maintenance due to their communication efficiency and scalability properties (Khateri et al., 2019). These works typically represent the system as a weighted graph, where each node represents a robot and each edge represents the communication connection between two robots (Giordano et al., 2013; Sabattini et al., 2013; Yang et al., 2010). The edge weights between robots are formulated as a function of the robot position subject to constraints such as maximum communication range, line-of-sight communication, and collision avoidance (both inter-robot and obstacles). One commonly used metric for the connectivity of the system is algebraic connectivity, which depends on the graph edge weights as explained later in Section 2. A value greater than zero indicates that the system is connected. Thus, in order to maintain connectivity within the system, previous works (Giordano et al., 2013; Sabattini et al., 2013; Yang et al., 2010) derived a decentralized gradient-based controller to maintain the algebraic connectivity above a specified lower limit.

While previous works present efficient decentralized algorithms for connectivity maintenance, they assume that the robot positions are deterministic and do not explicitly account for robot motion and sensing uncertainties. Here, motion uncertainties refer to the errors between the actual robot motion and a mathematical motion model, whereas sensing uncertainties refer to errors in measurements such as errors in localization measurements. These motion and sensing uncertainties, which are inherent in practical robots, result in robots deviating from their desired nominal positions. These deviations, if not accounted for, can potentially result in a loss of connectivity in the multi-robot system. Thus, it is important to account for robot motion and sensing uncertainties while designing connectivity maintenance algorithms.

In our prior work (Shetty et al., 2020), we defined a weighted graph to represent the connectivity of the multi-robot system while accounting for deviations due to motion and sensing uncertainties. We, then, used a distributed trajectory planner to maintain connectivity within the system. However, our planner in Shetty et al. (2020) required a centralized communication setup (i.e., each robot communicates with all other robots in the system in a single planning iteration). While such communication is possible (perhaps via multi-hop connections), in practice, it introduces additional communication delays and does not scale favorably to large systems. Thus, decentralized algorithms, as proposed in Giordano et al. (2013), Sabattini et al. (2013), and Yang et al. (2010), are desirable since they require a robot to communicate only with its immediate neighboring robots in a single planning iteration. Additionally, the weighted graph in Shetty et al. (2020) assumed a simplistic connectivity model subject to only a maximum communication range constraint, as opposed to the more realistic line-of-sight communication and collision avoidance constraints in Giordano et al. (2013).

In this work, we present a decentralized algorithm (referred to as DCMU) for connectivity maintenance of multi-robot systems while accounting for motion and sensing uncertainties. A decentralized gradient-based controller is implemented in order to maintain system connectivity subject to constraints of maximum communication range, line-of-sight communication, and collision avoidance. Table 1 outlines the contributions of this work in comparison to previous connectivity maintenance works. This paper is based on our work in Shetty et al. (2021). The main contributions of this work are listed as follows:

We propose a weighted graph that accounts for deviations in robot positions arising due to motion and sensing uncertainties. Compared to our prior work (Shetty et al., 2020), we include more realistic constraints of line-of-sight communication and collision avoidance (both inter-robot and obstacles) in addition to a maximum communication range.

We derive a decentralized gradient-based controller in order to maintain the algebraic connectivity of the proposed weighted graph above a specified lower limit. Here, we derive the gradients of the edge weights of our weighted graph that are required for computing the control. These edge weights account for deviations in robot positions instead of assuming deterministic robot positions as in Sabattini et al. (2013) and Yang et al. (2010).

We present extensive simulation results to evaluate our DCMU algorithm under motion and sensing uncertainties. We compare our connectivity maintenance performance with Sabattini et al. (2013) and validate our algorithm on a high-fidelity simulator (Shah et al., 2018).

The remainder of the paper is organized as follows. We, first, introduce relevant background from graph theory in Section 2. Next, in Section 3, we describe the models used for the robot motion and sensing uncertainties, and formulate the connectivity maintenance problem. Section 4 provides details of our DCMU algorithm including the weighted graph definition and the gradient-based controller. Finally, in Section 5, we present our simulation results validating the connectivity maintenance performance of our algorithm.

## 2 PRELIMINARIES: GRAPH THEORY

A multi-robot system can be represented as an undirected graph in which each node represents a robot and each edge represents the communication connection between two robots. Let *n* be the number of nodes in the graph. The adjacency matrix, *A*, of the graph is defined as an *n* × *n* matrix where *a _{ij}* ∈ [0,1] represents the edge weight between two nodes,

*i*and

*j*, with

*a*= 0 (Grone et al., 1990). The degree of a node is defined as . The vector of node degrees

_{ii}**d**= [

*d*

_{1}…,

*d*] is then used to define the degree matrix,

_{n}*D*, of the graph as

*D*= diag(

**d**). Given matrices

*A*and

*D*, the Laplacian matrix,

*L*, of the graph is defined as

*L*=

*D*−

*A*(Grone et al., 1990).

Let *λ*_{1} ≤ *λ*_{2} ≤ ⋯ ≤ *λ _{n}* be the eigenvalues of

*L*. The algebraic connectivity of the graph, also known as the Fiedler value, is defined as the second-smallest eigenvalue of

*L*(i.e.,

*λ*

_{2}). As mentioned in Section 1, algebraic connectivity is a commonly used metric to represent the connectivity of multi-robot systems. It varies from zero (if the graph is disconnected) to the number of nodes in the graph (if the graph is fully connected), i.e. 0 ≤

*λ*

_{2}≤

*n*. Figure 1 illustrates the algebraic connectivity for different configurations of a graph. Thus,

*λ*

_{2}remains greater than zero as long as there exists a (potentially multi-hop) communication path between any two robots in the system.

## 3 PROBLEM FORMULATION

### 3.1 Robot Description

For each robot, *i*, in the multi-robot system, we consider a discrete-time, single-integrator motion model:

1

where *t* represents the time instant, **x**_{i,t} is the state vector representing the robot position, **u**_{i,t} is the velocity control input, *B* is the control input matrix, and **w**_{i,t} is a zero-mean Gaussian-distributed error vector with covariance matrix, *Q _{i,t}*, i.e., . The control input matrix in Equation (1) is set as

*B*= (Δ

*t*)

*I*, where Δ

*t*is the discrete time-step. Note that, while this is a simplified motion model, it can still be used to control real robots as demonstrated in previous works on aerial robots (Lee et al., 2013; Soukieh et al., 2009). For the sensing model, we assume each robot,

*i*, obtains position measurements:

2

where **z**_{i,t} is the measurement vector representing position measurements and **v**_{i,t} is a zero-mean, Gaussian-distributed error vector with covariance matrix *R _{i,t}*, i.e., . Given the linear motion and sensing models with Gaussian uncertainties, we set each robot to use a Kalman filter (KF) for state estimation. The prediction step of the KF is performed as:

3

4

where *P _{i,t}* is the state estimation covariance matrix such that . The correction step of the KF is performed as:

5

6

7

where *G _{i,t}* is the Kalman gain matrix. In order to track a desired nominal state, , we assume that each robot uses linear feedback control, where the total control input,

**u**

_{i,t}, is of the form:

8

where is the feedback control gain, which can be designed using methods such as classical control theory or Linear-Quadratic Regulator (LQR) design (Doyle et al., 2013), and is the nominal control input which relates to the nominal states as:

9

Later in Section 3.2, we discuss how nominal control input is obtained for different robots in the multi-robot system.

Given the above setup for each robot, *i*, the distribution of the robot’s true state, **x**_{i,t}, about its nominal state, , can be obtained using the method described in Bry and Roy (2011). The authors derived the following Gaussian distribution for the robot’s true state:

10

where . Here, *P _{i,t}* is the state estimation covariance matrix from Equation (7), and Λ

_{i,t}can be obtained iteratively as follows (Bry & Roy, 2011):

11

where *I* is an identity matrix and Λ_{i,0} = *O*. In essence, the distribution in Equation (10) captures the deviations of the robot’s position from its desired nominal position that arise due to the motion and sensing uncertainties.

### 3.2 Multi-Robot System: Connectivity Maintenance

We consider the multi-robot system to be comprised of two types of robots: leader robots and follower robots. For the leader robots, we assume that the nominal control inputs in Equation (9) are available from a high-level planner, such as from an exploration or a search and rescue strategy (Baxter et al., 2007; Burgard et al., 2005). On the other hand, the objective of follower robots is to maintain connectivity within the multi-robot system. Our DCMU algorithm presented in Section 4 focuses on deriving the nominal control inputs for these follower robots.

In practice, the communication connectivity between two robots can be considered to be binary (i.e., the robots are either connected if certain constraints are satisfied [such as minimum signal strength, bandwidth, etc.] or they are disconnected). We consider any two robots, *i* and *j*, in the multi-robot system to be connected if the following constraints are satisfied:

**Communication range constraint**: The distance between the robots is within a maximum communication range,*ρ*(i.e., ||**x**_{i,t}–**x**_{j,t}||_{2}≤*ρ*).**Line-of-sight constraint**: The robots maintain a direct line of sight (i.e., the line segment connecting**x**_{i,t}and**x**_{j,t}is not obstructed by obstacles in the environment).**Collision avoidance constraint**: The robots are not colliding with any obstacles or other robots in the system; this constraint helps ensure that the communication equipment is not damaged due a collision.

Let represent the binary connectivity between robots *i* and *j*, i.e., if the robots are connected (if the above constraints are satisfied) and otherwise (if any of the above constraints is not satisfied). Note that, by definition, . These values can then be used to obtain the algebraic connectivity, (as explained in Section 2), of the graph which represents the connectivity of the multi-robot system based on the actual robot positions, **x**_{i,t}. Thus, implies that the multi-robot system is connected.

We define the problem for our DCMU algorithm as: Given a multi-robot system as described in this section, derive nominal control inputs ( in Equation [9]) for the follower robots such that is always above a specified lower limit *ϵ* (i.e., ). Figure 2 illustrates the defined problem.

## 4 PROPOSED CONNECTIVITY MAINTENANCE ALGORITHM: DCMU

During execution, each robot, *i*, in the multi-robot system deviates from its desired nominal position, , due to motion and sensing uncertainties. Previous connectivity maintenance works (Gasparri et al., 2017; Giordano et al., 2013; Sabattini et al., 2013; Siligardi et al., 2019; Yang et al., 2010) that do not account for these uncertainties essentially assume that the robots are at their nominal positions (i.e., ). In contrast, our DCMU algorithm accounts for the deviations of **x**_{i,t} from as modeled by Equation (10).

In this section, we provide the details of our DCMU algorithm. We, first, define a weighted graph to represent the connectivity of the multi-robot system where the edge weights account for deviations due to motion and sensing uncertainties. Next, we implement a decentralized power iteration method for each robot to estimate connectivity information of the weighted graph. Finally, each follower robot uses a gradient-based controller to obtain the nominal control input, , for maintaining connectivity of the weighted graph. Here, we derive the expressions for the gradients of our weighted graph edge weights, which are required to compute the nominal control input, . While, for simplicity, we drop the time notation in the remainder of this section, the nominal control input computed by our DCMU algorithm is applicable for all time instants, *t*.

### 4.1 Weighted Graph Definition

For the edge weights to represent connectivity between robots, we need to consider the constraints listed in Section 3.2. Thus, for our weighted graph, we define the edge weight between any two robots, *i* and *j*, as a product of four factors:

12

where *α _{ij}* is a factor for the communication range constraint,

*β*is a factor for the line-of-sight constraint, and

_{ij}*γ*and

_{i}*γ*are factors for the collision avoidance constraints of the two robots. Note that Equation (12) ensures that the edge weight,

_{j}*a*, is equal to zero (i.e., robots

_{ij}*i*and

*j*are not connected) if any of the factors

*α*,

_{ij}*β*,

_{ij}*γ*, or

_{i}*γ*is equal to zero (which occurs when the corresponding constraint is not satisfied). Next, we define the smooth functions for each of these factors that allow us to compute gradient-based control inputs as discussed later in Section 4.3.

_{j}**Communication range factor (**): This factor indicates how well robots*α*_{ij}*i*and*j*are connected in terms of being within a maximum communication range. We begin by defining a conservative measure, , for the range between two robots while accounting for their deviations from their nominal positions up to a desired confidence level. is defined as:13

where and are the nominal positions,

*s*is a scalar value obtained using the chi-square distribution for a desired confidence level (Hoover, 1984), and and are the largest eigenvalues of the covariance matrices, Σ_{i}and Σ_{j}. Later in Section 5, we demonstrate that a 3*σ*confidence level (reflecting a ~ 99.7% confidence level) results in acceptable connectivity maintenance performance. Figure 3(a) illustrates the conservative measure, .Given and a maximum communication range,

*ρ*, we define the communication range factor in Equation (12) as:14

where

*ρ*_{0}is a parameter such that*ρ*_{0}<*ρ*. Figure 4(a) shows how*α*varies with ._{ij}**Line-of-sight range factor (**): This factor indicates how well robots*β*_{ij}*i*and*j*are connected in terms of being in line of sight with each other. Similar to in Equation (13), we define a conservative measure, , for how close the line-of-sight vector between two robots is to nearby obstacles, as illustrated in Figure 3(b). Thus, is defined as:15

where

**x**_{β,ij}is the closest obstacle point,*s*is a scalar value reflecting the desired confidence level (Hoover, 1984; similar to Equation [14]), and are the largest eigenvalues of the covariance matrices, Σ_{i}and Σ_{j}, and**x**_{l,ij}is the point on the line segment connecting and that is closest to**x**_{β,ij}, and can be expressed as:16

where

*ζ*∈[0,1]. Note that finding the closest obstacle point,**x**_{β,ij}can be computationally challenging in practice, especially in the presence of a large number of obstacles. Techniques such as efficient nearest neighbor searches (Atramentov & LaValle, 2002) have been explored to reduce this computational load and are beyond the scope of this paper.Given and given parameters for the minimum and maximum desired distances, and , from the obstacle, we define the line-of-sight factor in Equation (12) as:

17

Figure 4(b) shows how

*β*varies with ._{ij}**Collision factor (**): This factor indicates how close robot*γ*_{i}*i*is to a collision. Here, again, we define a conservative measure, , of the distance from the robot to the nearest possible collision point. This nearest collision point can be a neighboring robot or a nearby obstacle. As mentioned above, techniques to reduce the computational load in obtaining the nearest collision point are beyond the scope of this paper. Figure 3(c) illustrates the conservative measure for two robots,*i*and*j*(i.e., and ). We define the measure as:18

where is the nominal position and

*s*is a scalar value reflecting the desired confidence level (Hoover, 1984; similar to Equation [14]). Here, if the nearest collision point for robot*i*is robot*j*, then and . Otherwise, if the nearest collision point for robot*i*is an obstacle, then**x**_{γ,i}is the center of the obstacle and*b*represents the width of the obstacle. Given and given parameters for the minimum and maximum desired distances, and , we define the collision factor in Equation (12) as:_{i,o}19

Figure 4(c) shows how

*γ*varies with . Note that, similar to_{i}*γ*, the collision factor,_{i}*γ*, indicates how close robot_{j}*j*is to a collision.

Thus, given the nominal position, , and covariance matrix, Σ_{i}, for all robots in the system, Equations (12)–(19) can be used to obtain the edge weights for our weighted graph. The main objective of these edge weights is to model the connectivity constraints listed in Section 3.2. If desired, alternate functions (such as exponential-based functions presented in Sabattini et al. [2013] and Yang et al. [2010]) can be used to model these constraints as long as the edge weights remain in the range [0, 1] (as described in Section 2) and are differentiable (required by our gradient-based controller described later in Section 4.3). The gradients of these edge weights with respect to the robot nominal positions are eventually used to compute robot control inputs.

Note that the factors *α* (Equation [14]), *β* (Equation [17]), and *γ* (Equation [19]) conservatively represent the connectivity constraints listed in Section 3.2 since these factors depend on the conservative measures defined in Equations (13), (15), and (18). For instance, the conservative measure for the range between two robots (shown in Figure 3[a]) is typically larger than the true distance (greater than 99.7% of the time for a 3*σ* confidence level), consequently leading the communication range factor, *α*, to have a conservative representation of the communication range constraint. Thus, the algebraic connectivity of our weighted graph, *λ*_{2}, conservatively measures the true algebraic connectivity of the system, . A detailed analysis comparing *λ*_{2} and can be found in our prior work (Shetty et al., 2020). Hence, in order to maintain according to the connectivity maintenance requirement stated in Section 3, our DCMU algorithm attempts to maintain *λ*_{2} > *ϵ*, detailed later in Section 4.3.

### 4.2 Decentralized Power Iteration

In order to compute the nominal control input for connectivity maintenance, each robot needs to obtain information on how well connected the weighted graph is. To obtain this information in a decentralized manner, we implement a decentralized power iteration method similar to previous works (Sabattini et al., 2013; Yang et al., 2010). Here, each robot communicates in a decentralized manner (i.e., only with other robots it is connected to) and shares information related to its estimate of the system connectivity. Based on the information received from connected robots, each robot is able to gradually improve its estimates of system connectivity. Further details of the method can be found in Sabattini et al. (2013). At the end of each iteration of the power method, each robot *i* estimates the following two quantities:

The

*i*-th component of the Fiedler vector (Section 4.1) of the weighted graph, , contains information on how well robot*i*is connected to the system.The algebraic connectivity (Section 4.1) of the weighted graph, , contains information of how well connected the entire multi-robot system is.

For additional details of the decentralized power iteration method, we refer our readers to Sabattini et al. (2013).

### 4.3 Decentralized Gradient-Based Controller

As mentioned in Section 3.2, the objective of the controller is to derive the nominal control input, , for each follower robot, *i*, to maintain the algebraic connectivity, , above a specified lower limit, *ϵ*. In order to achieve this, we instead maintain the algebraic connectivity of our weighted graph, *λ*_{2}, above *ϵ*, which is a conservative representation of the multi-robot system connectivity as explained at the end of Section 4.1.

We use a similar approach to Sabattini et al. (2013), where we first define a value function, *V*, that depends on algebraic connectivity of our weighted graph, *λ*_{2}, and then design a gradient-based controller for the follower robots to increase *λ*_{2}. The value function is defined as:

20

Figure 5(a) shows the variation of the value function with *λ*_{2}. To maintain connectivity in the system, we seek to adjust the robots’ nominal positions in order to perform a gradient descent of the value function. This consequently results in increasing the value of *λ*_{2} as seen in Figure 5(a). Thus, after simplification of the value function gradient (Sabattini et al., 2013; Yang et al., 2010), the desired change in the robot’s nominal position can be expressed as:

21

where the gradient of the value function, , is evaluated at . Here , and are obtained from the decentralized power iteration method as explained in Section 4.2. Figure 5(b) shows the gradient of the value function. Note that, as *λ*_{2} approaches *ϵ*, the magnitude of the gradient sharply increases, resulting in a large . This consequently leads to the follower robots moving faster (limited by their maximum velocity) to maintain connectivity when *λ*_{2} approaches *ϵ*.

Note that, if desired, alternate value functions can be used instead of Equation (20). Given that the gradient of the value function affects the change in the robots’ nominal positions (as shown in Equation [22]; Sabattini et al., 2013) mentions the required properties for this function. It needs to be continuously differentiable, non-negative, and non-increasing ∀ *λ*_{2} > *ϵ*. Additionally, it needs to suddenly increase as *λ*_{2} approaches *ϵ* (resulting in large changes in positions when the system is near loss of connectivity) and it needs to approach a constant value for large values of *λ*_{2} (resulting in small changes in positions when the system is well connected).

Next, using Equations (9) and (21), the nominal control input can be obtained as:

22

where the control input matrix, *B* = (Δ*t*)*I*, as defined in Equation (1). In order to compute the nominal control input, , using the above equation, we require the gradients of the edge weights, *a _{ij}*, with respect to the robot nominal position, (i.e., ). Given the definition of the edge weight in Equation (12), the required gradient can be expressed as:

23

In the remainder of this section, we proceed to derive the expressions for the gradient of the factors *a _{ij}*,

*β*,

_{ij}*γ*, and

_{i}*γ*with respect to . From Equation (14), the gradient of

_{j}*α*can be expressed as:

_{ij}24

where using Equation (13), the gradient of with respect to the *m*-th element of is:

25

Next, for the gradient of *β _{ij}*, using Equation (17) we get:

26

where, using Equation (15), the gradient of with respect to the *m*-th element of is:

27

Using Equation (19), the gradient of *γ _{i}* can be expressed as:

28

where, using Equation (18), the gradient of with respect to the *m*-th element of is:

29

Since *γ _{j}* indicates how close robot

*j*is to a collision, its gradient with respect to is non-zero only when the closest collision point for robot

*j*is robot

*i*. As explained below Equation (18), this implies and . Thus, if the closest collision point for robot

*j*is robot

*i*, then, using Equation (19), the gradient of

*γ*can be expressed as:

_{j}30

where, using Equation (18), the gradient of with respect to the *m*-th element of is:

31

In order to compute the gradients of the factors using Equations (24), (26), (28), and (30), we need to derive the gradients of the eigenvalues of covariance matrices Σ* _{i}* and Σ

*required in Equations (25), (27), (29), and (31). The equations in Section 3.1 show how the covariance matrix for a robot, Σ*

_{j}_{i}, varies with its position, . From Equation (10), note that Σ

_{i}=

*P*+ Λ

_{i}_{i}. Thus, as the robot nominal position, , changes from time instant

*t*to

*t*+1, the covariance matrix updates to ∑

_{i,t+1}as:

32

33

34

Note that the updated covariance matrix, Σ_{i,t+1}, only depends on *P _{i,t}*,

*Q*

_{i,t+1},

*B, K*

_{i,t+1}, and Λ

_{i,t}, and does not depend on the new nominal position, . Consequently, the eigenvalue also does not depend on , which implies . Thus, the terms involving gradients of the eigenvalues in Equations (25), (27), (29), and (31) are equal to zero.

In summary, our DCMU algorithm obtains nominal control inputs, , for the follower robots using Equation (22), which relies on quantities estimated using the decentralized power iteration method mentioned in Section 4.2 and relies on gradients of our weighted graph edge weights derived in Equations (23)–(32). In Equation (22), note that the magnitude of the nominal control input, , depends directly on the magnitude of the value function gradient (shown in Figure 5[b]), which grows large as the system algebraic connectivity decreases. Thus, when the system is close to losing connectivity, Equation (22) obtains large nominal control inputs, , for the follower robots to maintain connectivity.

Note that the connectivity maintenance performance of our DCMU algorithm depends on the nominal trajectories of the leader robots, which are assumed to be obtained from a high-level planner as mentioned in Section 3.2. While our algorithm attempts to move the follower robots such that connectivity is maintained, in some cases, the nominal trajectories of the leader robots might be such that connectivity maintenance is not possible—for example, a system with two leader robots and one follower robot in which the leader robots move indefinitely in opposite directions. On the other hand, our algorithm does guarantee collision avoidance for the robots with the desired confidence level (greater than 99.7% for a 3*σ* confidence level). If a robot, *i*, gets close to a collision point, the corresponding collision factor, *γ _{i}*, decreases, consequently decreasing the weighted graph algebraic connectivity. The nominal control input, , obtained using Equation (22) then attempts to move the robot away from the collision point. We validate the connectivity maintenance and collision avoidance performance of our DCMU algorithm on a few multi-robot systems below in Section 5.

## 5 SIMULATION RESULTS

In this section, we validate the performance of our DCMU algorithm in two 2D simulation setups: MATLAB and AirSim (Shah et al., 2018). We, first, present the MATLAB simulations that allowed us to quantitatively compare our algorithm with related previous work in Sabattini et al. (2013), which we refer to as *the Sabattini algorithm* for simplicity. We, then, discuss the AirSim simulations that validate our algorithm on a high-fidelity simulator in which the motion of the robots was more realistically simulated. For both simulation setups, we first demonstrated our DCMU algorithm on a simple two-robot setup with one leader robot and one follower robot, and then proceeded to more complex multi-robot configurations. As mentioned in Section 3.2, the leader robots were given predefined nominal trajectories (which we assume are available from some high-level planner such as an exploration strategy), and the follower robots implement nominal control inputs from our DCMU algorithm (i.e., from Equation [22]). A video containing the simulation results can be viewed online at https://youtu.be/SbE-ejQ_zm8.

For both our simulation setups, we set the discrete time-step Δ*t* = 0.2 s. We assumed an inter-robot communication rate of 1,000 Hz for the decentralized power iteration method. The motion and sensing model covariance matrices were set as *Q _{i,t}* = (0.02 m

^{2})

*I*and

*R*= (5 m

_{i,t}^{2})

*I*, respectively. These covariance matrices were used to add zero-mean Gaussian-distributed errors to the state and measurement vectors (Equations [1] and [2]) for both the leader and the follower robots in the system. The initial state estimation covariance matrix was set as

*P*= (0.1 m

_{i,t}^{2})

*I*and the control feedback gain used in Equation (8) was set as .

For a 3*σ* confidence level (reflecting a ~ 99.7% confidence level) in our weighted graph, we obtained the scalar value *s* = 3.494 using the chi-square distribution (Hoover, 1984). For the MATLAB simulations, we limited the maximum velocity control input (in each direction) in the motion model (Equation [1]) to be 2 ms^{−1} in order to reflect the physical constraints of practical robots. The AirSim simulator inherently implements maximum velocity constraints while simulating the robot motion. We specified the lower limit for the algebraic connectivity of the system to be *ϵ* = 0.01, where the connectivity maintenance objective was to maintain .

For the weighted graph in Section 4.1, the parameters *ρ*, , and represent the maximum desired communication range between robots, the minimum desired distance between robot line-of-sight vectors and obstacles, and the minimum desired distance between robots and their nearest collision points, respectively. The parameters *ρ*_{0}, , and represent the distances at which the communication range factor, the line-of-sight factor, and the collision factors, respectively, start affecting the nominal control input.

For instance, the communication range factor between two robots affects their nominal control inputs only when the conservative measure in Equation (13) is greater than *ρ*_{0}. Thus, setting the value of *ρ*_{0} close to *ρ* results in the communication range factor affecting the nominal control inputs only when the conservative measure (Equation [13]) is close to *ρ*. Setting *ρ*_{0} to be much smaller than *ρ* would result in the nominal control inputs being affected much earlier. In practice, these parameters can be set based on the desired performance of the multi-robot system. For our simulations, we heuristically set these parameter values as *ρ* = 20m, *ρ*_{0} = 18m, , and .

### 5.1 MATLAB Simulations

For the MATLAB simulations, our primary objective was to compare the connectivity maintenance performance of our algorithm with the Sabattini algorithm (Sabattini et al., 2013) for various multi-robot system configurations. As mentioned in the beginning of Section 4, previous works (Gasparri et al., 2017; Giordano et al., 2013; Sabattini et al., 2013; Siligardi et al., 2019; Yang et al., 2010) in essence assumed that the robots were already at their desired nominal positions. In contrast, our DCMU algorithm accounts for the deviations arising due to motion and sensing uncertainties.

As shown in Figure 6, we first analyzed a simple two-robot setup with one leader robot and one follower. The leader robot was provided a nominal trajectory that covered a distance of 120 m in a duration of 120 s. Figure 6(a)–(d) show snapshots of a single simulation run in which the follower robot implemented our DCMU algorithm to maintain connectivity with the leader robot. Starting from an initial position (Figure 6[a]), the follower robot follows the leader robot to stay within communication range (Figure 6[b]). As the leader robot moves upwards, the follower robot maintains line-of-sight connectivity while maintaining a safe distance from the obstacles (Figure 6[c]), while also maintaining a safe distance from the leader robot, itself (Figure 6[d]). Figure 6(e)–(g) show snapshots of different simulation runs where the follower robot implements the Sabattini algorithm (i.e., not accounting for the motion and sensing uncertainties [Sabattini et al., 2013]). We observed that not accounting for these uncertainties could potentially lead to a loss of connection due to the robots getting further away from the communication range (Figure 6[e]), the robots losing line-of-sight communication (Figure 6[f]), or due to a collision (Figure 6[g]).

In Figure 7, we quantitatively compare the connectivity maintenance performance for the above two-robot setup with the Sabattini algorithm (Sabattini et al., 2013). Here, we varied the amount of motion and sensing uncertainties in the multi-robot system and performed 1,000 simulation runs for each scenario for both our DCMU algorithm and the Sabattini algorithm. For both of these algorithms, we compared the ratio of runs for which the algebraic connectivity based on the actual robot positions, , was maintained above the specified lower limit *ϵ* = 0.01 throughout the run, as stated in the problem formulation in Section 3. Note that, for a given set of nominal trajectories for the leader robots, the nominal trajectories for the follower robots obtained using our DCMU algorithm remained the same. However, the actual robot trajectories varied across the 1,000 simulation runs due to the presence of Gaussian-distributed motion and sensing uncertainties. We began with the trivial case of zero motion model uncertainty, i.e., *Q _{i,t}* = (0 m

^{2})

*I*where the robots follow the nominal trajectories exactly. Here, we could observe that our DCMU algorithm performed the same as the Sabattini algorithm and maintained throughout all 1,000 simulation runs. We, then, compared the connectivity maintenance performance for the following motion and sensing model covariance matrices:

*Q*= (0.01m

_{i,t}^{2})

*I*and

*Q*= (0.02 m

_{i,t}^{2})

*I*;

*R*= (1 m

_{i,t}^{2})

*I, R*= (2 m

_{i,t}^{2})

*I*,

*R*= (3 m

_{i,t}^{2})

*I, R*= (4 m

_{i,t}^{2})

*I*, and ‘

*R*= (5 m

_{i,t}^{2})

*I*. Our DCMU algorithm maintained throughout all 1,000 simulation runs for the different motion and sensing uncertainties. However, as the amount of uncertainty increased, we observed that the connectivity maintenance performance of the Sabattini algorithm decreased sharply.

We, then, compared our algorithm with the Sabattini algorithm on different multi-robot system configurations as shown in Figure 8. Snapshots of a single simulation run with follower robots using our DCMU algorithm are shown for three different configurations: Figure 8(a)–(c), Figure 8(d)–(f), and Figure 8(g)–(i). The nominal trajectories for the leader robots covered distances of 80 m in 80 s, 60 m in 60 s, and 60 m in 60 s, respectively, for the three configurations. Note that the follower robots were not assigned to follow specific leader robots. Instead, our DCMU algorithm computed nominal control inputs for the follower robots directly based on each robot’s estimate of the system connectivity. Thus, in Figure 8, we can observe that the follower robots rearranged themselves in order to maintain connectivity within the system while accounting for the deviations arising due to motion and sensing uncertainties. Figure 9 quantitatively compares the connectivity maintenance performance of our DCMU algorithm and the Sabattini algorithm for 1,000 simulation runs of each of the three multi-robot configurations. Similar to the two-robot case, we observed that our algorithm was able to maintain throughout all 1,000 runs, whereas the ratio of runs for which Sabattini algorithm maintained throughout the runs sharply decreased as the amount of motion and sensing uncertainties increased. These simulations validate the applicability of our algorithm towards maintaining connectivity in the system under robot motion and sensing uncertainties.

### 5.2 AirSim Simulations

For the AirSim simulations, we validated our algorithm on multi-robot systems comprised of unmanned aerial vehicles (UAVs). The motion of the UAVs was modeled using Equation (1), while sensing uncertainties were introduced according to Equation (2). We show snapshots with the follower UAVs using our DCMU algorithm for three different configurations: Figure 10(a)–(c), Figure 10(d)–(f), and Figure 10(g)–(i). The nominal trajectories for the leader robots covered distances of 105 m in 105 s, 180 m in 180 s, and 45 m in 90 s, respectively, for the three configurations. The main objective of the snapshots shown in Figure 10 was to demonstrate that our DCMU algorithm is able to compute nominal trajectories for the follower UAVs such that connectivity is maintained for different multi-UAV configurations while the leader UAVs follow their predefined nominal trajectories. Figure 11 shows how the algebraic connectivity, , is maintained above the lower limit, *ϵ*, throughout the simulation for the different configurations. Note that the AirSim simulations were executed in real time, thus validating the real-time applicability of our DCMU algorithm.

## 6 CONCLUSION

In this paper, we presented the decentralized connectivity maintenance algorithm that accounts for robot motion and sensing uncertainties (DCMU). We, first, defined a weighted graph to account for these uncertainties along with constraints such as a maximum communication range, line-of-sight communication, and collision avoidance. Next, we designed a decentralized gradient-based controller by deriving the gradients of our weighted graph edge weights. Finally, we validated the connectivity maintenance performance of our algorithm in two simulation setups: MATLAB and AirSim. We quantitatively compared our DCMU algorithm with previous related work (Sabattini et al., 2013) and demonstrated that our algorithm performed better under motion and sensing uncertainties. Additionally, we demonstrated the connectivity maintenance performance of our algorithm on AirSim, which is a higher-fidelity simulator compared to MATLAB.

Possible directions for future work include exploring alternate geometric representations that reduce the conservatism in our weighted graph, evaluating connectivity maintenance performance for a range of graph parameter values, and accounting for more complex robot motion models such as ground robots with nonholonomic constraints. Additionally, we plan to evaluate our DCMU algorithm on real hardware and analyze the effects of communication latency on system connectivity maintenance.

## HOW TO CITE THIS ARTICLE

Shetty, A., Hussain, T., & Gao, G. (2023). Decentralized connectivity maintenance for multi-robot systems under motion and sensing uncertainties. *NAVIGATION, 70*(1). https://doi.org/10.33012/navi.552

This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.