<figure><img src="image_1.png" /></figure>

HAL
open science

# A Novel Strategy for Connectivity Maintenance and Recovery in Heterogeneous Multi-Robot Systems

Enrico Fiasché, Ezio Malis, Philippe Martinet

► To cite this version:

Enrico Fiasché, Ezio Malis, Philippe Martinet. A Novel Strategy for Connectivity Maintenance and Recovery in Heterogeneous Multi-Robot Systems. IROS 2025 - IEEE/RSJ International Conference on Intelligent Robots and Systems, Oct 2025, Hang Zhou, China, China. hal-05228241

HAL Id: hal-05228241

https://inria.hal.science/hal-05228241v1

Submitted on 28 Aug 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Novel Strategy for Connectivity Maintenance and Recovery in Heterogeneous Multi-Robot Systems

Enrico Fiasché<fnref n="1" />,<fnref n="2" />, Ezio Malis<fnref n="2" /> and Philippe Martinet<fnref n="2" />

*Abstract*— Ensuring connectivity and coordination in heterogeneous multi-robot systems (MRS) navigating complex environments is a critical challenge, especially when communication constraints and obstacles cause robots to become lost or disconnected. This paper presents a novel approach integrating Model Predictive Control (MPC) with Generalized Connectivity Maintenance (GCM) to enable real-time path adaptation while preserving connectivity. We introduce a decentralized decision-making framework that enables robots to recover lost members dynamically. When reconnection is infeasible, the system adapts the mission to continue while accounting for disconnected robots. Our method is evaluated through extensive simulations, showing its scalability and effectiveness in maintaining connectivity and ensuring mission success. Additionally, we propose a new evaluation metric that comprehensively assesses system performance, considering connectivity, coordination, and mission success in challenging environments.

## I. INTRODUCTION

Multi-robot systems (MRS) are widely used for tasks such as exploration, search and rescue, and environmental monitoring [1], [2]. However, maintaining coordination and connectivity in complex, constrained environments remains a major challenge, especially in heterogeneous teams with limited communication ranges. Connectivity loss can fragment the system, disrupt coordination, and jeopardize mission success. These challenges are amplified by differing robot capabilities, which may prevent all units from reaching the goal. Effective strategies are needed to adapt formations, recover isolated robots, or allow partial team progression while preserving overall mission objectives [3]. Connectivity maintenance techniques play a crucial role in ensuring that robots maintain communication and coordination despite environmental challenges [4]. These techniques can be categorized into different strategies. While rigid-link approaches (e.g., [5]) ensure strong connectivity, they often limit adaptability in complex environments. In contrast, flexible connectivity maintenance allows robots to adjust their positions while preserving communication links, making it more suitable for dynamic and unstructured scenarios. A widely used method for flexible connectivity maintenance relies on graph-theoretic principles, particularly the Fiedler eigenvalue, which quantifies the connectivity of a robot network within the Generalized Connectivity Maintenance (GCM) framework [6]. One application of this concept is the decentralized strategy proposed in [7], where a potential function derived from the Fiedler eigenvalue enables robots

to maintain formation while allowing flexibility. Similarly, [8] used a gradient-descent approach on a potential function based on algebraic connectivity to ensure that a multi-robot system could explore multiple targets without breaking communication links. The work [9] further leveraged the Fiedler eigenvalue to enable real-time adaptation for global connectivity maintenance, dynamically adjusting robot positions as needed. In [10], GCM was combined with randomized path planning and local optimization techniques, ensuring that connectivity constraints were met while still allowing globally feasible paths. The approach in [11] extended these methods by incorporating limited field-of-view constraints, using graph-based strategies to maintain connectivity while considering both communication and visibility among robots. These studies show the effectiveness of graph-theoretic approaches in multi-robot connectivity maintenance, particularly the use of the Fiedler eigenvalue as a foundation for adaptive and decentralized decision-making. This key metric has proven valuable for maintaining connectivity, which is essential for enabling successful mission completion. However, most of these works focus on homogeneous robots, without considering the complexities of heterogeneous MRS or dynamic environments where robots may become lost or disconnected. Few works have addressed these challenges. In [12], the authors propose a localization-based approach for a homogeneous MRS, where robots assist a member that has lost its localization. This approach assumes the affected robot is the only one to detect its own failure and request help, while the rest of the system continues the navigation. In this case, the robot is not truly lost, but simply unable to localize itself. In a different approach, [13] introduces a distributed method for restoring connectivity in a homogeneous MRS chain after failures caused by unpredictable environment changes. The approach assumes the robots can always predict the lost group' movements based on inferred observation to reconnect, which may not be reliable in unknown environments, and in some cases, it may not be feasible due to terrain constraints or obstacles. We propose a novel connectivity maintenance approach for heterogeneous MRS by leveraging graph theory to model the system while considering both robot heterogeneity and environmental complexity. Our method integrates Generalized Connectivity Maintenance (GCM) and a decentralized Model Predictive Control (MPC) framework, enabling real-time path adaptation and connectivity preservation. GCM enables continuous monitoring of the system's connectivity through the evaluation of the algebraic connectivity, allowing proactive responses to potential disruptions. In parallel, MPC provides

<footnote n="1">¹Université Côte d'Azur DS4H, Nice, France, enrico.fiasche@inria.fr</footnote>

<footnote n="2">²Inria Centre at Université Côte d'Azur, Sophia Antipolis, France, {ezio.malis, philippe.martinet}@inria.fr</footnote>
each robot with the capability to predict its own trajectory as well as those of its neighbors, which facilitates coordinated navigation and anticipatory actions to prevent disconnections. Additionally, we introduce a decentralized decision-making strategy for handling lost or disconnected robots, ensuring mission success. The predictive capacity is also critical for planning reconnection strategies when robots become lost or disconnected. To further validate the effectiveness of our approach, we conducted a comprehensive comparison with existing state-of-the-art solutions, which highlight its advantages in terms of connectivity maintenance and mission success. The main contribution of this paper is the integration of MPC and GCM for connectivity maintenance in heterogeneous multi-robot systems. Our approach ensures connectivity and coordination in complex environments, even when robots become lost or disconnected. First, we enable real-time path adaptation and connectivity preservation by integrating MPC and GCM. Second, we introduce a decentralized decision-making framework that balances recovery and mission continuity based on reconnection feasibility. Third, we propose a novel evaluation metric that provides a comprehensive assessment of connectivity, coordination, and mission success. The effectiveness and scalability of our method are shown through extensive simulations.

## II. BACKGROUND

In this section a brief overview of the key concepts and techniques used in this work is provided. We introduce the Generalized Connectivity Maintenance theory, and the Model Predictive Control framework, which are the main components of the proposed approach for connectivity maintenance in heterogeneous multi-robot systems.

### A. Graph Theory

Let $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ be an undirected graph, where $\mathcal{V} = \{1, \dots, N_R\}$ is the set of vertices, representing the robots, and $\mathcal{E} = \{(i, j) : i \in \mathcal{V}, j \in \mathcal{V}, i \neq j\}$ is the set of edges, corresponding to communication links between robots. An edge $e_{ij} \in \mathcal{E}$ exists if robot $i$ can communicate with robot $j$. Each edge is associated with a weight $A_{ij} \ge 0$, such that $A_{ij} > 0$ if communication exists and $A_{ij} = 0$ otherwise [7]. The adjacency matrix $\mathbf{A} \in \mathbb{R}^{N_R \times N_R}$ of the graph $\mathcal{G}$ is defined by the edge weights $A_{ij}$. Since the graph is undirected, $\mathbf{A}$ is symmetric, meaning $A_{ij} = A_{ji}$.

The Laplacian matrix $\mathbf{L} \in \mathbb{R}^{N_R \times N_R}$ of the graph $\mathcal{G}$ is defined as:

$$ \mathbf{L} = \mathbf{D} - \mathbf{A} \quad (1) $$

where $\mathbf{D} \in \mathbb{R}^{N_R \times N_R}$ is the degree matrix of the graph $\mathcal{G}$, with $D_{ii} = \sum_{j=1}^{N_R} A_{ij}$. Graph theory provides a clear and accurate framework to describe how a group of robots stays connected. In particular, the Laplacian matrix and the algebraic connectivity value, which is its second-smallest eigenvalues (Fiedler eigenvalue) $\lambda_2$. If $\lambda_2 > 0$, the graph is connected, meaning all robots form a single connected component. A high Fiedler value indicates strong connectivity, while a low value suggests weak connectivity. A value of $\lambda_i = 0$ implies that the robot team has split into at

least $i$ disjoint groups. Specifically, if $\lambda_2 = 0$, the graph is disconnected, the robot team has split into at least two disjoint groups [14], [15]. The corresponding eigenvector provides insight into how the graph is divided. The signs and relative magnitudes of its components indicate which robots belong to the same connected component. Specifically, robots with similar eigenvector value tend to be in the same group, while robots with significantly different values are likely in separate clusters [16], making it easy to identify the lost robots. This property makes the Fiedler eigenvector a useful tool for identifying and analyzing connectivity disruptions in multi-robot systems.

### B. System Dynamics

The multi-robot system consists of Automatic Guided Vehicles (AGVs) and Unmanned Aerial Vehicles (UAVs). The AGVs are holonomic robots controlled through linear velocities $v_x$ and $v_y$ along the $x$ and $y$ directions, respectively, and the angular velocity $w_z$ around the vertical axis. The quadrotor UAVs are velocity-controlled robots operating in six degrees of freedom (6-DoF), as described in [11], using linear and angular velocities $\mathbf{v} = [v_x; v_y; v_z; w_x; w_y; w_z]$.

### C. Model Predictive Control

Model Predictive Control (MPC) is an optimization-based control strategy that predicts the discrete-time system's future behavior over a finite horizon by solving a constrained optimization problem at each time step, satisfying system constraints [17]. Given the discretized state vector $\mathbf{x}_k \in \mathbb{R}^n$ and the discretized control input $\mathbf{u}_k \in \mathbb{R}^m$ at the $k^{th}$ time step, the optimization problem can be stated by the following:

$$ \min_{\mathbf{u}, \mathbf{x}} \left( \sum_{k=0}^{N_p} \|\mathbf{x}_k - \mathbf{x}^*\|_{\mathcal{Q}}^2 + \sum_{k=0}^{N_p-1} \|\mathbf{u}_k - \mathbf{u}_{k-1}\|_{\mathcal{R}}^2 \right) \quad (2a) $$

$$ \text{s.t.:} \quad \mathbf{x}_{k+1} - f_d(\mathbf{x}_k, \mathbf{u}_k) = 0 \quad k = 0, \dots, N_p - 1 \quad (2b) $$

$$ \mathbf{x}_k \in \mathcal{X} \quad k = 1, \dots, N_p \quad (2c) $$

$$ \mathbf{u}_k \in \mathcal{U} \quad k = 0, \dots, N_p - 1 \quad (2d) $$

Here, $\mathbf{x}^*$ is the desired state, $\mathcal{Q}$ and $\mathcal{R}$ are positive definite matrices, $N_p$ replaces the prediction horizon $T_p$, and $f_d$ denotes the system dynamics. MPC is widely used in robotics for its ability to handle complex environments and constraints [18], though it can be computationally demanding. To address this, we adopt the control parameterization method from [17], which reduces complexity by optimizing a subset of control inputs, enabling efficient real-time MPC for heterogeneous multi-robot navigation.

## III. METHODOLOGY

### A. Proposed Method

In the proposed MPC framework, each robot independently solves an optimization problem at each time step, predicting its own and its neighbors' future trajectories considering connectivity constraints and obstacles avoidance. The objective is to generate control commands that enable smooth navigation while preserving network connectivity. To limit communication overhead, each robot shares only its
pose with its neighbors, which is sufficient for predicting relative motion and maintaining connectivity. Moreover, this formulation is designed to be general and modular, allowing adaptation to different robot types, dynamic models, and physical constraints.

The optimal control problem for the i^th robot consists of three key terms.

$$c_i = (c_{\text{goal},i} + c_{\text{goal},n} + c_{\text{conn}}) \quad (3)$$

$c_{\text{goal},i}$, the state tracking term, penalizes deviation from the desired state and enforces smooth control input variation:

$$c_{\text{goal},i} = \left( \sum_{k=0}^{N_p} \|\mathbf{x}_{ik} - \mathbf{x}_i^*\|_{\mathcal{Q}}^2 + \sum_{k=0}^{N_p-1} \|\mathbf{u}_{ik} - \mathbf{u}_{i,k-1}\|_{\mathcal{R}}^2 \right) \quad (4)$$

Similar to the first term, $c_{\text{goal},n}$, the neighbor prediction cost, penalizes the deviation of the neighbor robots' states from the desired state and the minimization of the control input variation. This helps in accurately predicting their future motion and improves coordination.

$$c_{\text{goal},n} = \sum_{j=0}^{N_{\text{neig}}} (c_{\text{goal},j}) \quad (5)$$

where the $N_{\text{neig}}$ represents the number of neighbors the i^th robot can communicate with. $c_{\text{conn}}$, the connectivity cost, discourages the loss of communication links by penalizing excessive separation between robots. This encourages robots to maintain proximity and reinforces system connectivity:

$$c_{\text{conn}} = \sum_{j=0}^{N_{\text{neig}}} \left( \sum_{k=0}^{N_p} \| \exp(\mathbf{x}_{ik} - \mathbf{x}_{jk}) \|_{\mathbf{W}}^2 \right) \quad (6)$$

where $\mathbf{W}$ is a positive definite matrix that penalizes the separation between robots. In order to avoid collisions with obstacles and other agents, the optimization problem is subject to several constraints. The connectivity constraint based on the positions of the i^th and j^th robot at k^th time step ($g_{\text{conn}}(i, j, k), i \neq j$) ensures that the 3D Euclidean distance between robots is within a predefined communication range, preventing the loss of connectivity:

$$\sqrt{(x_{ik} - x_{jk})^2 + (y_{ik} - y_{jk})^2 + (z_{ik} - z_{jk})^2}, \forall j \in N_{\text{neig}} \quad (7)$$

Similarly, to avoid collision with obstacles, the obstacle avoidance constraint based on the position of the i^th robot at k^th time step ($g_{\text{obs}}(i, k)$) ensures that each robot maintain a minimum safe distance from known obstacles.

The final formulation of the optimal control problem for the i^th robot is:

$$\min_{\mathbf{u},\mathbf{x}} c_i = \min_{\mathbf{u},\mathbf{x}} (c_{\text{robot}} + c_{\text{neig}} + c_{\text{conn}}) \quad (8a)$$

$$\text{s.t.: } d_{\min} \le g_{\text{conn}}(i, j, k) \le d_{\max} \quad k = 0, \dots, N_p \quad (8b)$$

$$d_{\text{safe}} \le g_{\text{obs}}(i, k) \quad k = 0, \dots, N_p \quad (8c)$$

$$\nu_{\min} \le \nu_k \le \nu_{\max} \quad k = 0, \dots, N_p - 1 \quad (8d)$$

where $d_{\min}$ and $d_{\max}$ are the minimum distance between robots and maximum communication range, respectively,

$d_{\text{safe}}$ is the minimum safe distance from obstacles, and $\nu_{\min}$ and $\nu_{\max}$ are the minimum and maximum control inputs vector, respectively.

## B. Connectivity Recovery Strategy

Even though the proposed MPC framework ensures strong connectivity and coordination among robots, the system may still face disruptions due to communication failures or obstacles. When connectivity is lost, our approach leverages the MPC framework to restore coordination and maintain mission success. For each possible connectivity disruption scenario, the recovery strategy consists of two main steps, as shown in Fig. 1: detection and reconnection.

<figure><img src="image_3.png" /><figcaption>Fig. 1: Block diagram of the decentralized decision-making framework for connectivity recovery strategy.</figcaption></figure>

Connectivity loss is detected using the Fiedler eigenvalue of the system's Laplacian matrix. When this value equals 0, the MRS identifies a disconnection event, and all robots stop moving to assess the situation. The specific lost robots are identified using the corresponding eigenvector, as described in Section II-A. Connectivity disruptions can arise due to two main factors: either a robot becomes unable to move forward due to terrain or obstacles, or a temporary communication failure causes a break in the network. In the first case, the robots may reach an untrable area where reconnection is no longer feasible through direct movement. In the second case, even if the disruption is momentary, the system follows the same approach: the closest UAV from the leading group is dispatched to the last known position of the lost robots, and a feasibility check is performed to determine whether reconnection is possible by adjusting robot positions. Once the lost robots are identified, the closest UAV from the leading group is dispatched to their last known position. The lost robots, like the rest of the MRS, remain stationary, as they have also detected the connectivity disruption. Upon reaching the lost robots, the UAV, thanks to its ability to fly over obstacles, first evaluates the surrounding environment to identify any constraints that could prevent reconnection. This local assessment allows the UAV to determine whether a feasible meeting point exists, where reconnection is possible without major deviations from the mission. Using the previously mentioned MPC framework, the UAV then computes a potential trajectory for the lost group and the main team. If reconnection is feasible, the UAV returns to notify the
leading group, and all robots adjust their positions accordingly. Once the Fiedler value is greater than 0 ($\lambda_2 > 0$), connectivity is restored, and the mission resumes towards the goal. However, when terrain constraints prevent lost robots, typically AGVs, from moving forward, reconnection may not be possible in the short term. In such cases, the UAV instructs them to remain in place while the rest of the team reorganizes the network and continues the mission. Once the task is completed, the team returns to recover the stationary robots before proceeding to the next objective. By adapting its response to the nature of the disruption, the system ensures that connectivity is either quickly restored or managed in a way that does not compromise the overall mission.

## IV. EVALUATION METHODOLOGY

Evaluating autonomous multi-robot systems in constrained environments demands comprehensive metrics. While prior work focuses on navigation efficiency, time, energy, and performance [19]–[21], connectivity loss and recovery remain overlooked. We extend existing metrics by incorporating connectivity maintenance and recovery, enabling a fuller assessment. Our evaluation framework, supporting our first claim, focuses on trajectory quality and connectivity preservation.

### A. Trajectory Quality

Trajectory quality is essential for ensuring safe and efficient navigation, especially in complex environments where robots must reach their goal while avoiding obstacles and collisions. It assesses the effectiveness of the robot's path execution based on three primary factors. The Traveled Distance ($T_D$) reflects the energy consumption, as distance directly impacts exploration strategies. It is widely used in the literature [19] and is computed as:

$$T_D = \sum_{i=0}^{N_R} d_i \qquad (9)$$

where $d_i$ is the distance traveled by the $i^{th}$ robot. The Navigation Efficiency ($N_E$) measures how efficiently robots navigate toward the goal. Traditional approaches define it as the ratio between the shortest straight-line path, from the starting and goal position, and the actual path taken. However, we propose an improved evaluation that accounts for obstacles, offering a more realistic assessment of how connectivity constraints impact robot trajectories and deviations from the optimal path. The best path is calculated using an RRT-based graph search algorithm, and efficiency is calculated as:

$$N_E = \frac{L_{\text{best}}}{T_D} \qquad (10)$$

where $L_{\text{best}}$ is the length of the shortest feasible path considering obstacles. The Total Time to Goal ($TT_G$) measures the time required for robots to reach their target goal. It provides insights into the efficiency of the navigation strategy, particularly in balancing connectivity constraints with overall mission performance. Additionally, we introduce the Collision Rate ($C_R$), which quantifies the number of

collisions that occurred during navigation. This metric is crucial for assessing the system's ability to avoid obstacles and maintain safe operation.

### B. Connectivity Maintenance

In addition to trajectory quality, we introduce key metrics to assess the system's ability to handle connectivity disruptions and recover lost robots:

* Number of Lost Robots ($N_{RL}$): The total number of robots that lost connectivity during the navigation.

* Number of successfully Reconnected Robots ($N_{R_S}$): The number of robots that successfully reconnected to the system after losing connectivity.

* Number of Robots Awaiting Recovery ($N_{RAR}$): The number of robots that, due to unfeasible reconnection, were instructed to remain in place instead of rejoining the leading group.

Given the previously defined metrics, we also introduce the Success Rate ($R_S$), which quantifies the effectiveness of the system in recovering lost robots. It is defined as the ratio of successfully recovered robots (either reconnected or sent to a recovery position) to the total number of lost robots:

$$R_S = \frac{N_{R_S} + N_{RAR}}{N_{RL}} \qquad (11)$$

Additionally, we define the Recovery Time ($T_R$), which measures the time required for lost robots to regain connectivity and rejoin the system. This provides insight into the efficiency of the recovery process. These additional metrics provide a deeper understanding of how well the system adapts to connectivity challenges, ensuring both efficient navigation and robust coordination in dynamic environments.

## V. SIMULATION AND DISCUSSION

This section presents the simulation setup used to evaluate our proposed approach to connectivity maintenance and recovery in a heterogeneous Multi-Robot System (MRS). Our primary objective is to show the robustness, effectiveness, and scalability of our method in diverse and complex environments in several contexts. To achieve this, we conduct extensive simulations designed to test all critical aspects of our approach, including connectivity maintenance, task completion, and recovery strategies.

### A. Simulation Setup

The Model Predictive Control (MPC) framework operates with a prediction horizon of 4 seconds under normal conditions. However, when recovery is required, the prediction horizon is extended to 20 seconds to facilitate better long-term decision-making. The system is simulated in randomized dense forest environments with varying obstacle densities, positions, and sizes. These conditions introduce connectivity risks due to obstructed communication, local minima trapping robots, and navigation challenges requiring adaptive decision-making. Testing under such constraints evaluates the system's ability to maintain connectivity and achieve mission goals. Simulations are conducted in three contexts, each addressing a key aspect of our approach: (1) maintaining
connectivity in challenging environments, (2) handling cases where AGVs cannot reach the goal due to terrain constraints, requiring UAVs to proceed alone, and (3) recovering from temporary connectivity loss to ensure mission success. Each scenario is tested across four different environments where obstacles are modeled as vertical cylinders (trees) randomly distributed in the 2D plane, with varying radii and heights to create diverse spatial configurations and complexity levels. For each environment, we evaluate teams of 5, 8, 10, and 15 robots, evenly distributed between AGVs and UAVs. In total, we perform 480 simulations, with 40 runs per team size per context (10 per environment, 4 environments per context scenario, and 3 contexts). Table I details the distribution.

<table><caption>TABLE I: Number of simulations performed for each context scenario and team size.</caption><thead><tr><th>Scenario</th><th>Feasible path for AGV</th><th>Expected loss</th><th>Simulations per team size</th><th>Total Sim.</th></tr></thead><tbody><tr><td>S.1</td><td>✓</td><td>✗</td><td>40, 40, 40, 40</td><td>160</td></tr><tr><td>S.2</td><td>✗</td><td>✓</td><td>40, 40, 40, 40</td><td>160</td></tr><tr><td>S.3</td><td>✓</td><td>✓</td><td>40, 40, 40, 40</td><td>160</td></tr></tbody></table>

## B. Comparison

To validate our results, we compare our strategy with two existing approaches. The first comparison is with the connectivity maintenance strategy from [11], which enforces connectivity by considering distance constraints and field of view limitations. In this method, only the leader robot knows the final goal, while the others focus solely on maintaining connectivity. Originally, the leader was human-controlled, but for a fair comparison, we implement it using Model Predictive Control (MPC). A key challenge in this approach is that when only the leader is aware of the goal, follower robots optimize for local connectivity without considering global task completion. This can lead to local minima, especially in dense forest environments where obstacles further restrict movement. A specific issue arises when the leader pauses to allow a follower to reposition, as shown in Fig. 2.

<figure><img src="image_4.png" /><figcaption>Fig. 2: Top view stationary robots of [11] approach.</figcaption></figure>

Since followers prioritize connectivity over goal-reaching, they remain stationary, leading to system deadlocks despite maintaining connectivity. This limitation illustrates a fundamental trade-off in decentralized connectivity strategies: prioritizing local connectivity prevents disconnections but

may hinder overall mission progress in obstacle-rich environments. In contrast, our approach avoids this issue by equipping each robot with its own MPC, ensuring both connectivity and goal-directed navigation. This decentralized control balances connectivity preservation with global movement, preventing deadlocks and enabling efficient task completion. The second comparison is with the approach from [13], which focuses on connectivity recovery in a homogeneous MRS deployed in a chain formation. This method assumes identical robot capabilities and prioritizes re-establishing connectivity after failures caused by environmental changes. A key limitation of this approach is that the chain formation is constrained by three conditions: (i) a valid path $\rho_{chain}$ must exist from the base station to the goal, (ii) the number of robots must be sufficient to maintain connectivity along this path, i.e., $length(\rho_{chain}) \le Nc_{range}$, and (iii) obstacles must not obstruct the line-of-sight between relay robots. If any of these conditions are violated, the algorithm deems the problem unsolvable. In our forest environment, these constraints severely limit applicability. The available robots are insufficient to maintain a continuous chain from the base to the goal, leading the method from [13] to fail in finding a solution.

<figure><img src="image_5.png" /><figcaption>Fig. 3: Comparison results $T_D$ and $N_E$ with [13].</figcaption></figure>

To ensure a fair comparison in the first scenario, where a feasible solution always exists, we define a smaller environment with 8 robots, allowing all three constraints to be satisfied. For a more extensive evaluation, we conduct large-scale simulations in randomly generated environment, varying obstacle count, density, and size. Additionally, we randomize both the robots’ initial positions and goal locations to eliminate bias and ensure robustness in the comparison. To thoroughly cover the search space, we perform 300 simulations for each algorithm.

<figure><img src="image_6.png" /><figcaption>Fig. 4: Environment used for the comparison.</figcaption></figure>

Both approaches show similar results in terms of Traveled Distance $T_D$ and Navigation Efficiency $N_E$, as shown in Fig. 3, without losing any robots. The time to reach the goal
is also comparable, with a slight advantage for our method, faster than 4 seconds on average. However, as obstacle density increases and the environment expands, approach [13] becomes up to twice as slow due to its need to replan every step.

### C. Results Evaluation

In the first scenario, robots successfully navigate in the dense forests, avoiding obstacles while maintaining connectivity, achieving a Collision Rate of $C_R = 0$, which confirms the robustness and efficiency claimed in our second contribution. As shown in Fig. 5, Traveled Distance $T_D$ and Navigation Efficiency $N_E$ remain stable despite variations in team size. However, as the number of robots increases from 5 to 15, slight degradation in these metrics occurs due to increased coordination demands. Despite this, the system remains stable, showing scalability.

<figure><img src="image_7.png" /><figcaption>Fig. 5: First Scenario mean $T_D$ and mean $N_E$</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 6: Example environment first scenario.</figcaption></figure>

The computational time required by the MPC remains consistent, with an average of 42.93 ms for 5 robots and 75.28 ms for 15 robots. The Time to Goal $TT_G$ remains nearly constant across all cases, with an average of 95 seconds. The system achieves 100% Success Rate, with no lost robots $N_{RLs}$ and consequently no robots to recover $N_{Rs}$ and no awaiting $N_{RAR}$. This confirms the approach's reliability in maintaining mission completion even as the number of robots increases.

In the second scenario, the system successfully recognize the impossibility of reaching the goal due to terrain constraints. After evaluating the surrounding environment around the AGVs impassable terrain, the designed UAV determine that reconnection is unfeasible and instruct the AGVs to remain stationary. The MRS adapts its strategy to ensure mission completion letting the UAVs continue toward the goal, while the AGVs remain stationary, awaiting recovery.

<figure><img src="image_9.png" /><figcaption>Fig. 7: Example environment second scenario.</figcaption></figure>

As shown in Fig. 8, $T_D$ and $N_E$ remain stable despite terrain constraints, though they deteriorate slightly due to the UAV rescue operation. The system consistently maintains an optimal path while avoiding collisions with $C_R = 0$.

<figure><img src="image_10.png" /><figcaption>Fig. 8: Second Scenario mean $T_D$ and mean $N_E$</figcaption></figure>

Table II summarizes Success Rate $R_S$, the number of lost robots $N_{RL}$, those awaiting recovery $N_{RAR}$, and those successfully recovered $N_{RR_S}$. The number of AGVs affected varies from 3 to 8, depending on the team size.

Scenario n.2

<table><caption>TABLE II: Connectivity maintenance metrics 2^nd^ scenario</caption><thead><tr><th>N<sub>R</sub></th><th>5</th><th>8</th><th>10</th><th>15</th></tr></thead><tbody><tr><th>N<sub>RL</sub></th><td>3</td><td>4</td><td>5</td><td>8</td></tr><tr><th>N<sub>RS</sub></th><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>N<sub>RAR</sub></th><td>3</td><td>4</td><td>5</td><td>8</td></tr><tr><th>R<sub>S</sub></th><td>100%</td><td>100%</td><td>100%</td><td>100%</td></tr><tr><th>T<sub>R</sub></th><td>13.73s</td><td>20.56s</td><td>34.18s</td><td>38.53s</td></tr></tbody></table>

The system successfully recognizes the situation and adapts to these constraints, ensuring mission completion while maintaining connectivity. The MRS always identifies the issue and recovers the awaiting robots, leading to a 100% $R_S$. The reconnection time increases with team size, from 13.73 seconds for 5 robots to 38.53 seconds for 15 robots. This increase is due to the growing constraints and the larger group size that needs to be recovered. The computational time required by the MPC remains stable, and the average $TT_G$ is stable to 221 seconds, including the time for the first recovery attempt and the time to recover the awaiting robots at the end of the mission. These results validate the third claim regarding the system's ability to handle terrain constraints effectively.

In the third scenario, the robots successfully recognize the connectivity loss. When part of the team becomes temporarily lost, the designed UAV dynamically identify feasible meeting points to restore connectivity before resuming the mission.
<figure><img src="image_11.png" /><figcaption>Fig. 9: Example environment third scenario.</figcaption></figure>

Fig. 10 shows that $T_D$ and $N_E$ remain stable, though slightly degraded due to UAV recovery maneuvers. Despite this, the system maintains optimal paths and ensures $C_R = 0$.

<figure><img src="image_12.png" /><figcaption>Fig. 10: Third Scenario mean $T_D$ and mean $N_E$</figcaption></figure>

<table><caption>TABLE III: Connectivity maintenance metrics 3rd scenario</caption><caption>Scenario n.3</caption><thead><tr><th>N<sub>R</sub></th><th>5</th><th>8</th><th>10</th><th>15</th></tr></thead><tbody><tr><th>N<sub>R<sub>L</sub></sub></th><td>2</td><td>4</td><td>5</td><td>8</td></tr><tr><th>N<sub>R<sub>S</sub></sub></th><td>2</td><td>4</td><td>5</td><td>8</td></tr><tr><th>N<sub>R<sub>AR</sub></sub></th><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>R<sub>S</sub></th><td>100%</td><td>100%</td><td>100%</td><td>100%</td></tr><tr><th>T<sub>R</sub></th><td>14.9s</td><td>23.85s</td><td>26.2s</td><td>39.74s</td></tr></tbody></table>

The number of lost robots varies from 2 to 8, depending on team size. The MRS reliably detects and resolves connectivity issues, ensuring full reconnection and achieving a 100% $R_S$. Reconnection time $T_R$ increases with team size, from 14.9 seconds with 5 robots to 39.74 seconds with 15 robots, due to the growing constraints given from the larger group size. As in previous scenarios, the computational time for MPC remains stable, and $TT_G$ is stable with an average of 127 seconds, accounting for the recovery maneuvers, predicting the possible reconnection, and the time to restore the full connectivity. This further confirms our third claim regarding the system's adaptability to challenging environments. The proposed approach shows better performance in all scenarios compared to existing methods, effectively maintaining connectivity, completing tasks, and recovering from failures or terrain constraints.

## VI. CONCLUSIONS

This paper presents a robust approach for maintaining connectivity and completing tasks in a heterogeneous Multi-Robot System (MRS) consisting of AGVs and UAVs. By leveraging Model Predictive Control (MPC) and the Generalized Connectivity Maintenance (GCM) theory, our method ensures efficient navigation and recovery even in complex environments with dynamic obstacles and terrain constraints.

Through extensive simulations, we show that our approach outperforms existing methods, achieving a 100% success rate, stable performance across team sizes, and minimal computational overhead. These results confirm the scalability and reliability of our approach for real-world applications, offering significant improvements over current solutions in terms of connectivity maintenance and mission success, considering robots lost due to terrain or obstacle constraints.

## ACKNOWLEDGMENT

This work has been supported by the French government, through the UCA DS4H Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-17-EURE-0004.

## REFERENCES

[1] A. Franchi, P. Stegagno, and G. Oriolo, "Decentralized multi-robot encirclement of a 3D target with guaranteed collision avoidance," *Autonomous Robots*, 2016.

[2] T. Nestmeyer, P. Robuffo Giordano, H. H. Buslthoff, and A. Franchi, "Decentralized simultaneous multi-target exploration using a connected network of multiple robots." Springer London, 2017.

[3] Y. Rizk, M. Awad, and E. W. Tunstel, "Cooperative heterogeneous multi-robot systems: A survey," *ACM Comput. Surv.*, 2019.

[4] L. Sabattini, N. Chopra, and C. Secchi, "On decentralized connectivity maintenance for mobile robotic systems," in *IEEE ECC*, 2011.

[5] D. Koung, O. Kermorgant, I. Fantoni, and L. Belouaer, "Cooperative multi-robot object transportation system based on hierarchical quadratic programming," *IEEE RA-L*, 2021.

[6] *Algebraic Connectivity*. Springer London, 2010, pp. 81–94.

[7] P. R. Giordano, A. Franchi, C. Secchi, and H. H. Bülthoff, "A passivity-based decentralized strategy for generalized connectivity maintenance," *The International Journal of Robotics Research*, 2013.

[8] T. Nestmeyer, A. Franchi, H. Bülthoff, and P. Giordano, "Decentralized multi-target exploration and connectivity maintenance with a multi-robot system," 2015.

[9] D. Cai, S. Wu, and J. Deng, "Distributed global connectivity maintenance and control of multi-robot networks," *IEEE Access*, 2017.

[10] Y. Solana, M. Furci, J. Cortés, and A. Franchi, "Multi-robot path planning with maintenance of generalized connectivity," in *IEEE MRS*, 2017.

[11] M. Bernard, C. Pacchierotti, and P. R. Giordano, "Decentralized connectivity maintenance for quadrotor uavs with field of view constraints," in *IEEE/RSJ IROS*, 2023.

[12] P. J. Bonczek and N. Bezzo, "A cooperative recovery framework for resilient multi-robot swarm operations under loss of localization in unknown environments," in *IEEE/RSJ IROS*, 2024.

[13] Y. Marchukov and L. Montano, "Multi-robot coordination for connectivity recovery after unpredictable environment changes," *IFAC-PapersOnLine*, 2019.

[14] M. Fiedler, "Algebraic connectivity of graphs," *Czechoslovak mathematical journal*, 1973.

[15] M. Mesbahi and M. Egerstedt, "Graph theoretic methods in multiagent networks," 2010.

[16] F. R. Chung, *Spectral graph theory*. American Mathematical Soc., 1997.

[17] E. Fiasché, P. Martinet, and E. Malis, "Towards autonomous robot navigation in human populated environments using an universal sfm and parametrized mpc," in *IEEE/RSJ IROS*, 2023.

[18] M. Kamel, J. Alonso-Mora, R. Siegwart, and J. Nieto, "Robust collision avoidance for multiple micro aerial vehicles using nonlinear model predictive control," in *IEEE/RSJ IROS*, 2017.

[19] Z. Yan, L. Fabresse, J. Laval, and N. Bouraqadi, "Metrics for performance benchmarking of multi-robot exploration," in *IEEE IROS*, 2015.

[20] P. Monier, A. Doniec, S. Piechowiak, and R. Mandiau, "Metrics for the evaluation of discsp: Some experiments on multi-robot exploration," in *IEEE/WIC WI-IAT*, 2010.

[21] N. Michael, J. Fink, and V. Kumar, "Experimental testbed for large multirobot teams," *IEEE RAM*, 2008.