Decentralized Connectivity Maintenance for Multi-Robot Systems Under Motion and Sensing Uncertainties

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:

1. 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).

3. 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.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 2

The objective of our DCMU algorithm is to derive nominal control inputs (refer to the black arrows) for follower robots in order to maintain communication connectivity within the system.

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, β_ij is a factor for the line-of-sight constraint, and γ_i and γ_j are factors for the collision avoidance constraints of the two robots. Note that Equation (12) ensures that the edge weight, a_ij, is equal to zero (i.e., robots i and j are not connected) if any of the factors α_ij, β_ij, γ_i, or γ_j 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.

1. Communication range factor (α_ij): This factor indicates how well robots 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 ρ₀ is a parameter such that ρ₀ < ρ. Figure 4(a) shows how α_ij varies with .

2. Line-of-sight range factor (β_ij): This factor indicates how well robots 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 β_ij varies with .

3. Collision factor (γ_i): This factor indicates how close robot 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_i,o 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:

   19

   Figure 4(c) shows how γ_i varies with . Note that, similar to γ_i, the collision factor, γ_j, indicates how close robot j is to a collision.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 3

Conservative measures , and used to define our weighted graph in Section 4.1

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 4

Factors that define the edge weights of our weighted graph using Equation (12): (a) depicts the communication range factor (see Equation [14]), (b) depicts the line-of-sight factor (see Equation [17]), and (c) depicts the collision factor (see Equation [19]).

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, λ₂, conservatively measures the true algebraic connectivity of the system, . A detailed analysis comparing λ₂ 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 λ₂ > ϵ, 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:

1. 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.

2. 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, λ₂, 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, λ₂, and then design a gradient-based controller for the follower robots to increase λ₂. The value function is defined as:

20

Figure 5(a) shows the variation of the value function with λ₂. 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 λ₂ 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 λ₂ 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 λ₂ approaches ϵ.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 5

(a) The value function (Sabattini et al., 2013) defined in Equation (20), along with (b) the gradient of the value function required to compute the nominal control input in Equation (22)

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 ∀ λ₂ > ϵ. Additionally, it needs to suddenly increase as λ₂ 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 λ₂ (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, γ_i, and γ_j with respect to . From Equation (14), the gradient of α_ij can be expressed as:

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 γ_j can be expressed as:

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 Σ_j required in Equations (25), (27), (29), and (31). The equations in Section 3.1 show how the covariance matrix for a robot, Σ_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.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]).

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 6

Snapshots of two-robot simulation runs: (a)–(d) represent single runs in which the follower robot implements the DCMU algorithm and maintains connectivity, while (e)–(g) represent different simulation runs in which the follower robot implements the Sabattini algorithm and connectivity is lost.

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²)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_i,t = (0.01m²)I and Q_i,t = (0.02 m²)I; R_i,t = (1 m²)I, R_i,t = (2 m²)I, R_i,t = (3 m²)I, R_i,t = (4 m²)I, and ‘ R_i,t = (5 m²)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.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 7

Quantitative comparison for the two-robot MATLAB simulation shown in Figure 6; our DCMU algorithm performs better than the Sabattini algorithm (Sabattini et al., 2013) under increasing motion and sensing uncertainties.

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.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 8

MATLAB simulations for various multi-robot system configurations via snapshots of simulation runs in which the follower robots implement the DCMU algorithm in three different configurations: (a)–(c), (d)–(f), and (g)–(i); the simulation videos can be viewed online at https://www.youtube.com/watch?v=SbE-ejQ_zm8

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 9

Quantitative comparisons for the multi-robot MATLAB simulations shown in Figure 8; the DCMU algorithm performs better than the Sabattini algorithm (Sabattini et al., 2013) under increasing motion and sensing uncertainties for the three multi-robot configurations.

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.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 10

AirSim simulations for various multi-UAV system configurations via snapshots of simulation runs in which the follower UAVs implement the DCMU algorithm in three different configurations: (a)–(c), (d)–(f), and (g)–(i); the simulation videos can be viewed online at https://www.youtube.com/watch?v=SbE-ejQ_zm8

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 11

Algebraic connectivity of the multi-UAV AirSim simulations shown in Figure 10; the DCMU algorithm maintains (black lines) above the lower limit ϵ (red-dashed lines).