# Holistic Connectivity Controller for Multirobot Dispersion

Authors: Zhenqiang Mi; Yang Yang; Jiajia Sun
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Dispersion of mobile robots in a certain formation is prerequisite in many applications; one of the most important issues during the entire process is to maintain the interagent connections, as well as to restore them whenever they were broken. We investigate the aforementioned problem in this work by designing a holistic connectivity controller (HCC) to regulate and restore the interagent connections during the dispersion of the mobile network. HCC consists of two core structures. Firstly, to illustrate the multirobot dispersion, we adopt the distributed link removal algorithm (DLRA), which is able to remove redundant links in the multirobot network to facilitate the dispersion and only requires local information of no more than two-hop neighbors. Secondly, the proposed approach is extended to the problem of connectivity restoration with consideration of simultaneous failure of multiple agents. A connectivity restoration strategy is proposed, and then the recoverability of network connectivity is investigated. The proposed HCC has also integrated motion controller to regulate the movement of the mobile robots, so that interrobot collisions can be effectively avoided. Theoretical analysis and computer simulations have confirmed the efficiency and scalability of the proposed schemes.


---

## Body

## 1. Introduction

The cooperative control of large groups of mobile agents (vehicles/robots) is rapidly developing because of technological advances in wireless communication and networking technologies. Mobile ad hoc network based on the IEEE 802.11 standard [1] is currently the predominant technology for such applications, through which a large number of mobile agents can coordinate their actions and perform various challenging tasks, such as planet exploration [2], operation under hazardous circumstances (search and rescue) [3], and surveillance [4]. The development of multirobot systems (MRS) has attracted numerous research efforts. Among various topics that have been covered, emphasis is placed on the consensus (flocking and rendezvous) of a group of agents, as well as coverage and connectivity control of multirobot networks. Multirobot dispersion, on the other hand, is another fundamentally essential aspect yet need more research efforts.Dispersion of mobile robots is a particular procedure to maximize spatial coverage with a minimum number of mobile agents. Evidently, dispersion of a team of mobile robots is of great importance in a number of scenarios. For instants, a team of mobile robots is usually dispatched in a compact formation that is, several mobile robots are distributed in one spot with minimal interagent distances. More often than not, to execute certain tasks, for example, combat and monitoring, they are required to be dispersed right after distribution to cover a larger area, as shown in Figure 1. These significant application potentials of multirobot dispersion have recently led to a surge of research attentions. Techniques including inverse agreement control law [5], clique-intensity algorithm [6], and “artificial physics” framework [7] have been developed to regulate the dispersion of multirobot or mobile sensor systems. Another promising research area that is closely related to multi-agent dispersion is coverage control of mobile robot a number of methods are proposed either to optimize the deployment of mobile robotic sensors [8, 9] or to maximize the coverage of autonomous mobile agents to achieve different goals [10–12]. The proposed methods have already been applied to the important problem of multirobot exploration in unknown area. Unfortunately, the important issue of connected underlying networks is often neglected in the aforementioned works.Seven mobile robots are initially deployed in a dense manner and configured to their final formation with sparse network structure and better coverage of the area.
(a)
Initial configuration (before dispersion)
(b)
Final configuration (after dispersion)Maintaining the connectivity of MRS can be vital for achieving network-wide collaboration and the success of the entire mission, given the thought that in most scenarios mobile robots need to communicate with each other constantly to coordinate or even negotiate the execution of every task, if not just for synchronization. Due to the level of importance of interrobot communication, theconnectivity control of mobile multirobot networks is now rapidly becoming a hot research topic in the field of MRSs, and a variety of strategies have been developed in recent years [13–17]. Recent research works have focused on both fixed and switching networks, with application to coordination control [18], aggregation [19, 20], and flocking [21]. In [13], Laplacian matrix of a graph and its spectral properties are used as a model for connectivity for the MRS; then artificial potential function is adopted to drive the mobile robot away from the undesired location to avoid disconnection of the network; the control of the network is centralized. Reference [14] utilized the similar concept of Laplacian matrix of graph to represent the network connectivity and solving the connectivity control problem by maximizing the second smallest eigenvalue. A distributed connectivity preservation algorithm is present in [15] with respect to graph transitions, and the methods are further applied in multirobot coordination. As efficient as they are, these approaches, however, often result in a tight network structure with dense communication links, which may severely restrict the movement of mobile robots and jeopardize the coverage and cooperation efficiency. To deal with these problems, Zavlanos and Pappas [16] proposed a distributed market-based control strategy, which is able to reduce redundant communication links based on local estimation of spanning subgraph. This strategy, however, requires full knowledge of the network structure, which may cause large delay in dense and large-scale networks [22, 23]. Moreover, none of these works have applied the connectivity control (topology control) methods multirobot dispersion. In our previous work [24], a self-organized connectivity control framework is designed with application to the dispersion of mobile ad hoc sensor networks we have solved the problem of redundant link reduction by means of only two-hop neighboring information, and the objective of connectivity preserving multiagent dispersion is effectively achieved. Nevertheless, to the best of our knowledge, none of the proposed multirobot dispersion methods takes the risk of agent failure into consideration. Overlooking this issue might be fatal while dispersing a team of mobile robots, since network connectivity may be more fragile and sensitive with respect to the failure of a single or multiple robots simultaneously, considering the sparse network topology generated by the dispersion and the extreme environment in most multirobot application scenarios. This phenomenon is revealed in Figure 2, where two snapshots of the dispersing robot teams are provided. In Figure 2(a), the failure of the robot A will not result in the partition of the network. However, the failure of robot B in Figure 2(b) has partitioned the network into two connected subgraphs. We argue that, when the network is sparse, the probability that the network is disconnected due to the failure of mobile agents is high, since alternate routes in the communication network are limited. Furthermore, when simultaneous failures of multiple robots happen during the dispersion (such as robot B and robot C failed the same time in Figure 2(b)), the connectivity of the underlying network will normally be damaged.Failure of mobile robot may reduce in partition of the underlying networks.
(a)
Failure of noncritical robot
(b)
Failures of critical robotsConsidering the autonomous nature of multi-agent system, to design a distributed local connectivity restoration mechanism is obligatory for dealing with such situations. Recently, closely related problems have been investigated in wireless sensor and actor networks (WSAN), and a class of connectivity restoration algorithms has been proposed to fix the network structure whenever failure of actor(s) occurs [25–30]. In [25], several algorithms are proposed for achieving a 2-connectivity fault-tolerant configuration in multirobot networks by moving a subset (block) of mobile robots. A distributed actor recovery algorithm, called DARA, is presented in [26] to address the 1- and 2-connectivity requirements in WSAN subject to single failure of actor, and similar approaches can be found in [27, 28]. Akkaya et al. have proposed a partition detection algorithm called PADRA in [29], which also handles the connectivity restoration in presence of single failure of agents. The work is then further extended in [30], and a distributed connectivity restoration algorithm, denoted as MPADRA, is presented to deal with concurrent failure of multiple actors. Due to the energy critical nature of WSAN, the scope of the aforementioned works focuses on energy conservation and computing complexity, rather than the dynamic control of mobile multi-agent system. Similar problem is solved in [31], where a control system named HERO is designed to restore the broken connection in multirobot networks whenever it occurs, and stability analysis is also provided. However, to the best of our knowledge, the important problem of restoring the connectivity subjected to single or multiple robot failures during dispersion has not been solved in the literature.Aiming at bridging the gap between dispersion and connectivity restoration, we investigate the aforementioned problem in this work by designing a holistic connectivity controller (HCC) to regulate and restore the interagent connections during the dispersion of the mobile network. HCC consists of two core structures. First, to illustrate the multirobot dispersion, we adopt the distributed link removal algorithm (DLRA) [24], which is able to remove redundant links in the multirobot network to facilitate the dispersion and only requires local information of no more than two-hop neighbors. Furthermore, considering the hazardous environment of most multi-agent applications and the sparse network structure caused by dispersion, we proposed the HCC to deal with connectivity restoration with consideration of concurrent failure of multiple agents during the dispersion of the MRS, and a connectivity restoration strategy is proposed to restore the network connectivity whenever a single or multiple robots fail. A preliminary version of this paper is presented in [32]; we extend this work by providing the theoretical analysis in the recoverability of network connectivity and a more detailed study in experimental simulation. The proposed HCC has also integrated motion controller to regulate the movement of the mobile robots, so that interrobot collisions can be effectively avoided.The rest of the paper is organized as follows. Section2 reviews DLRA and provides some necessary terminologies and notations. Section 3 extends the connected dispersion method to a single or multiple concurrent failures of mobile robots. HCC is proposed to restore the network connectivity with the aid of a connectivity restoration algorithm (CRA). Section 4 provides the theoretical proof of the restorability of the HCC in case of failure of single mobile robots and then provides an illustrative introduction of the restorability when multirobot failures occur. Computer simulations are included in Section 5, and this paper is concluded in Section 6 with a discussion of future research works.


## 2. Problem Formulation and Multirobot Dispersion

### 2.1. Problem Formulation

ConsiderN single integrator mobile agents whose motions obey the model
(1)ξ˙i(t)=ui(t),
where ξ˙i(t)∈ℝ2 denotes the position and ui(t)∈ℝ2 denotes the velocity (control input) of each mobile robot i∈[1,…,N].Furthermore, let the dynamic graph𝒢(t)=(𝒱,E(t)) denote a mobile network of n robot, where 𝒱=(1,…,n) denotes the set of vertices indexed by the set of mobile agents and E(t)={i,j∣fij(t)≥ε,i,j∈𝒱}, 0<ε<1 denotes the time-variant set of communication links. We define 0≤fij(t)≤1 to be a normalized nonnegative weighting function symmetric in its arguments, that is, fij(t)=fji(t), and assume that fij(t)≠fik(t), j≠k. In this case, the adjacency matrix 𝒜(t)=(aij(t))∈ℝn×n (we define aij(t)≡0 for all i; thus there are no self-loops in the network) can be defined as
(2)aij(t)={aji(t)=fij(t),(i,j)∈E(t),0,otherwise.Note that any normalized nonnegative function can be treated as a weighting function. Nevertheless, to associate with the link quality, it is rather a natural choice thatfij(t) denotes received signal strength, which could be accurately measured with the aid of RSSI (received signal strength indication) at the radio interface of each agent [24]. Now, we have the following definitions.Definition 1.
An undirected weighted dynamic graph𝒢(t)=(𝒱,E(t)) is defined as connected at time t if and only if there is at least one communicative path between any two vertices within it.Now the main objectives of this paper can be described as follows.Objective A(Link Removal). For any nodes i and j in 𝒢(t)=(𝒱,E(t)), remove redundant communication links with the aid of two-hop neighboring information. The generated subgraph 𝒢s(t)=(𝒱,Es(t)) contains only necessary communication links for connectivity maintenance, that is, (i,j)∈Es(t).Objective B(Connectivity Preserving Multirobot Dispersion). Dispersing the MRS with the assumption that concurrent failure of multiple agents, that is, i and j, occurs at time t=tf, determine the best available candidate for each failed agent such that, by replacing i and j with the candidate agents and controlling the movement of correlative mobile nodes, the global connectivity can be restored within a finite time t<∞.


### 2.2. Review of the DLRA

To achieve the Objective A, we will need the DLRA algorithm [24]. In the following part, we give a brief introduction of DLRA and provide its applicability in the HCC and multirobot dispersion. First, we have the following definitions.Definition 2.
Nodej is in the physical neighbor set of i, denoted as j∈𝒩p[i](t), if and only if (i,j)∈E(t).Definition 3.
Nodej is the logical neighbor set of  i, denoted as j∈𝒩l[i](t), if and only if (i,j)∈Es(t).Definition 4.
For any nodei in the network, we denote 𝒩r[i](t)=(ajk(t)) as the neighbor relationship matrix (NRM) at time t, where j∈𝒩l[i](t) and k∈𝒩l[j](t).Based on the aforementioned definitions, the proposed DLRA is described as follows.Determine the Redundant Communication Links. Each mobile robot periodically sends and receives Hello messages to/from all its neighbors in 𝒩p[i](t). The message contains the following information: node ID, position, logical neighbor set 𝒩l[j](t), and link weight with all its logical neighbors. Upon receiving Hello message from each individual physical neighbor, node i updates 𝒩p[i](t). As it is assumed that the initial network is connected, DLRA starts at time t=t0. Then, the process is started with initial condition that 𝒩p[i](t0)=𝒩l[i](t0), and 𝒩r[i](t0) is constructed for each i. Each agent compares the link weights of the related triangle; that is, the agent is a vertex of the triangle, and the weakest link in that triangle will be denoted as a redundant link. For instance, as is shown in Figure 3(a), based on the condition that aij(t)≜max[aij(t),aik(t),ajk(t)], link (i,j,t) will be denoted as redundant link by agents i and j. In the second step, each agent i updates 𝒩r[i](t). Let 𝒩r[ik](t)=[ajk(t),alk(t),…,ank(t)] be the column vector of 𝒩r[i](t), where (j,l,…,n)∈𝒩l[i](t). Look up 𝒩r[ik](t) for every k∈𝒩r[i](t), if there exist ajk(t), alk(t), where j≠l, and ajk(t)×alk(t)≠0; then compares the link weights aij(t), ail(t), ajk(t), and  alk(t). Based on the condition that aij(t)≜max[aij(t),ail(t),ajk(t),alk(t)] as shown in Figure 3(b), link (i,j) will be denoted as redundant communication link by agents i and j. Upon the determination of the redundant link, for example, (i,j), agent i will put j into a candidate neighbor removing set, denoted as 𝒞d[i](t), which will be used in the synchronization process to construct 𝒢s(t).Redundant link removal process in DLRA.
(a)
(b)Synchronized Link Removal. In particular, a request and acknowledge mechanism is utilized to dynamically synchronize the disconnection of any redundant communication links between the corresponding vertices. Refer to [24] for a detailed description.To provide the applicability of HCC and multirobot dispersion, we recall the following lemma.Lemma 5 (Corollary 7 in [24]).
For any subgraph𝒢s(t)=(𝒱,Es(t))  generated from DLRA, the shortest cycle is 5; that is, there are no such links as i↔v↔u↔i or i↔v↔u↔j↔i.What Lemma5 tells us is that DLRA can effectively reduce the redundant communication links in the multirobot network, with the aid of only two-hop neighboring information. Particularly, it can constrain the shortest cycle in the network within the value of 5, which makes the generated subgraph sparse enough to be dispersed. We simulated the DLRA with stationary network scenario, as shown in Figure 4. It can be seen that, given a dense initial configuration in Figure 4(a), a much sparse network topology can be generated with DLRA as in Figure 4(b), which eliminates most unnecessary constrains when dispersing the team of mobile robot. Nevertheless, all merits come with some drawbacks, when the multirobot network becomes so sparse with DLRA; what bothering us now is its loss in robustness and increasing venerability. That is, with a sparse network topology, loss of any mobile robot and/or communication links may easily result in the partition of the entire network, and the connectivity is then jeopardized. Interestingly, in most cases the MRSs are deployed into dangerous and extreme environment, where loss of some mobile nodes may become inevitable subject to external damages, not even to mention the unstable quality of some robot productions. Inspired by the observation, a holistic connectivity controller (HCC) is presented in the next section to regulate and restore the interagent connections during the dispersion of the mobile multirobot networks.DLRA under stationary network scenario.
(a)
(b)


## 2.1. Problem Formulation

ConsiderN single integrator mobile agents whose motions obey the model
(1)ξ˙i(t)=ui(t),
where ξ˙i(t)∈ℝ2 denotes the position and ui(t)∈ℝ2 denotes the velocity (control input) of each mobile robot i∈[1,…,N].Furthermore, let the dynamic graph𝒢(t)=(𝒱,E(t)) denote a mobile network of n robot, where 𝒱=(1,…,n) denotes the set of vertices indexed by the set of mobile agents and E(t)={i,j∣fij(t)≥ε,i,j∈𝒱}, 0<ε<1 denotes the time-variant set of communication links. We define 0≤fij(t)≤1 to be a normalized nonnegative weighting function symmetric in its arguments, that is, fij(t)=fji(t), and assume that fij(t)≠fik(t), j≠k. In this case, the adjacency matrix 𝒜(t)=(aij(t))∈ℝn×n (we define aij(t)≡0 for all i; thus there are no self-loops in the network) can be defined as
(2)aij(t)={aji(t)=fij(t),(i,j)∈E(t),0,otherwise.Note that any normalized nonnegative function can be treated as a weighting function. Nevertheless, to associate with the link quality, it is rather a natural choice thatfij(t) denotes received signal strength, which could be accurately measured with the aid of RSSI (received signal strength indication) at the radio interface of each agent [24]. Now, we have the following definitions.Definition 1.
An undirected weighted dynamic graph𝒢(t)=(𝒱,E(t)) is defined as connected at time t if and only if there is at least one communicative path between any two vertices within it.Now the main objectives of this paper can be described as follows.Objective A(Link Removal). For any nodes i and j in 𝒢(t)=(𝒱,E(t)), remove redundant communication links with the aid of two-hop neighboring information. The generated subgraph 𝒢s(t)=(𝒱,Es(t)) contains only necessary communication links for connectivity maintenance, that is, (i,j)∈Es(t).Objective B(Connectivity Preserving Multirobot Dispersion). Dispersing the MRS with the assumption that concurrent failure of multiple agents, that is, i and j, occurs at time t=tf, determine the best available candidate for each failed agent such that, by replacing i and j with the candidate agents and controlling the movement of correlative mobile nodes, the global connectivity can be restored within a finite time t<∞.


## 2.2. Review of the DLRA

To achieve the Objective A, we will need the DLRA algorithm [24]. In the following part, we give a brief introduction of DLRA and provide its applicability in the HCC and multirobot dispersion. First, we have the following definitions.Definition 2.
Nodej is in the physical neighbor set of i, denoted as j∈𝒩p[i](t), if and only if (i,j)∈E(t).Definition 3.
Nodej is the logical neighbor set of  i, denoted as j∈𝒩l[i](t), if and only if (i,j)∈Es(t).Definition 4.
For any nodei in the network, we denote 𝒩r[i](t)=(ajk(t)) as the neighbor relationship matrix (NRM) at time t, where j∈𝒩l[i](t) and k∈𝒩l[j](t).Based on the aforementioned definitions, the proposed DLRA is described as follows.Determine the Redundant Communication Links. Each mobile robot periodically sends and receives Hello messages to/from all its neighbors in 𝒩p[i](t). The message contains the following information: node ID, position, logical neighbor set 𝒩l[j](t), and link weight with all its logical neighbors. Upon receiving Hello message from each individual physical neighbor, node i updates 𝒩p[i](t). As it is assumed that the initial network is connected, DLRA starts at time t=t0. Then, the process is started with initial condition that 𝒩p[i](t0)=𝒩l[i](t0), and 𝒩r[i](t0) is constructed for each i. Each agent compares the link weights of the related triangle; that is, the agent is a vertex of the triangle, and the weakest link in that triangle will be denoted as a redundant link. For instance, as is shown in Figure 3(a), based on the condition that aij(t)≜max[aij(t),aik(t),ajk(t)], link (i,j,t) will be denoted as redundant link by agents i and j. In the second step, each agent i updates 𝒩r[i](t). Let 𝒩r[ik](t)=[ajk(t),alk(t),…,ank(t)] be the column vector of 𝒩r[i](t), where (j,l,…,n)∈𝒩l[i](t). Look up 𝒩r[ik](t) for every k∈𝒩r[i](t), if there exist ajk(t), alk(t), where j≠l, and ajk(t)×alk(t)≠0; then compares the link weights aij(t), ail(t), ajk(t), and  alk(t). Based on the condition that aij(t)≜max[aij(t),ail(t),ajk(t),alk(t)] as shown in Figure 3(b), link (i,j) will be denoted as redundant communication link by agents i and j. Upon the determination of the redundant link, for example, (i,j), agent i will put j into a candidate neighbor removing set, denoted as 𝒞d[i](t), which will be used in the synchronization process to construct 𝒢s(t).Redundant link removal process in DLRA.
(a)
(b)Synchronized Link Removal. In particular, a request and acknowledge mechanism is utilized to dynamically synchronize the disconnection of any redundant communication links between the corresponding vertices. Refer to [24] for a detailed description.To provide the applicability of HCC and multirobot dispersion, we recall the following lemma.Lemma 5 (Corollary 7 in [24]).
For any subgraph𝒢s(t)=(𝒱,Es(t))  generated from DLRA, the shortest cycle is 5; that is, there are no such links as i↔v↔u↔i or i↔v↔u↔j↔i.What Lemma5 tells us is that DLRA can effectively reduce the redundant communication links in the multirobot network, with the aid of only two-hop neighboring information. Particularly, it can constrain the shortest cycle in the network within the value of 5, which makes the generated subgraph sparse enough to be dispersed. We simulated the DLRA with stationary network scenario, as shown in Figure 4. It can be seen that, given a dense initial configuration in Figure 4(a), a much sparse network topology can be generated with DLRA as in Figure 4(b), which eliminates most unnecessary constrains when dispersing the team of mobile robot. Nevertheless, all merits come with some drawbacks, when the multirobot network becomes so sparse with DLRA; what bothering us now is its loss in robustness and increasing venerability. That is, with a sparse network topology, loss of any mobile robot and/or communication links may easily result in the partition of the entire network, and the connectivity is then jeopardized. Interestingly, in most cases the MRSs are deployed into dangerous and extreme environment, where loss of some mobile nodes may become inevitable subject to external damages, not even to mention the unstable quality of some robot productions. Inspired by the observation, a holistic connectivity controller (HCC) is presented in the next section to regulate and restore the interagent connections during the dispersion of the mobile multirobot networks.DLRA under stationary network scenario.
(a)
(b)


## 3. Holistic Connectivity Control and Restoration

Dispersing a team of mobile agents often results in a sparse structure of the underlying network. This phenomenon represents the vulnerability of connectivity subjected to failure of mobile agent(s). Upon the failure of critical agent(s), the initially connected multi-agent network will be partitioned into disjoint segments. In such case, network-wide collaboration will not be possible and certain missions can be in jeopardy due to the fatal network disconnection. In this section, we present a connectivity restoration strategy and further design a motion controller to integrate the multirobot dispersion with restoration of the mobile networks. And most importantly, the HCC also requires only two-hop information of neighboring robots.


### 3.1. Connectivity Restoration Algorithm (CRA)

Denote the topology control algorithm of the connectivity restoration strategy as CRA, and the following definitions are first introduced.Definition 6.
Assume that nodej fails at time t=tf, denoted as a collapsarjf, where jf≜j(t-).Definition 7.
Denote≺j(t) as the order list of j’s neighbor nodes within two hops with respect to decreasing link quality. Note that the first two-hop neighbor appears behind the last one-hop neighbor.Definition 8.
Nodei is a potential prey of jf if and only if i≺j(t).Associated with the aforementioned definitions, CRA is described in Algorithm1. The main notion of CRA is for every logical neighbor within two hops of j to continuously track its position. Whenever j fails, one of the potential preys in ≺j(t), for example, i, will be selected as the prey to the collapsarjf; the selection of preyi is according to the following standards: (1)
i is not a current potential preyto any collapsarother than  jf;(2)
≺j(t-)∪𝒩l[i](t-)≠(𝒩l[i](t-),i);(3)
among all thecandidate preys that meet (1) and (2), the order of i is the smallest in ≺j(t).Algorithm 1:Connectivity restoration algorithm (CRA).
Upon Detecting failure of nodej at time t, jf=j(t-)
(1)  Fori∈≺j(t-) at time t=t-
(2) while  ∄k∈𝒱 where i∈≺k(t1-),t1-≤t-   do
(3)  Denote h as the position of i in vector ≺j(t-)
(4)  if  ≺j(t-)∪𝒩l[i](t-)≠(𝒩l[i](t-),i)
(5)   if  h=1
(6)    i is the prayer of jf, denote i→jf, Broadcast ack=h
(7)   else  hold until time t=(h-1)ΔT
(8)    if  Receive(ack)=0
(9)     i is the prayer of jf, denote i→jf, Broadcast ack=h
(10)    end if
(11)   end if
(12)  else
(13)     remove ≺j(t-)
(14)  end if
(15) end while
(16) End
Upon Finishing Connectivity Restoration at timet=tf
(17) For  i∈≺j(t-)
(18) if  i→jf
(19)  Broadcast Suc(jf), remove ≺j(t-)
(20) else if  Receive(Suc(jf))=1
(21)  Remove ≺j(t-)
(22) end if
(23)  End


### 3.2. Holistic Connectivity Controller (HCC)

When dispersing a team of mobile robots, the invariance of network topology in generated subgraph𝒢s(t) is prerequisite for the realization of connectivity preserving. The aim of this section is to develop a holistic distributed controller that (1) regulates the dispersion of mobile agents in continuous space, (2) reconnects the network subjected to partitions from single or multiple concurrent robots’ failures, that is, configure the prey to the optimal location, (3) avoids any link disconnection and interrobot collisions induced by the movement of mobile robots.We first utilize the combined potential function in [24] to ensure that all essential links remain connected and interagent collisions are avoided all the time during multi-agent dispersion between any two consecutive topology updates.A repulsive potential function is introduced in the HCC to deal with the dispersion of mobile multirobot networks between nodei and all its physical neighbors j∈𝒩p[i](t), defined as ψijr(t), where ψir(t)=∑j∈𝒩p[i](t)ψijr(t). In particular, we have
(3)ψijr(t)≜(1-fij(t)-ε1-ε)-ρ,
where ρ∈ℝ+, and in this paper, associated with fij(t) in (2), it yields
(4)ψijr(t)≜(1-exp[-β(∥ξi(t)-ξj(t)∥-a0)]-ε1-ε)-ρ.The design principle of repulsive potential function is to assign each mobile robot an artificial potential force; this virtue force can drive the mobile robot to move in certain direction in a way that is opposite to each other. More specifically, whenever the distance between two neighboring mobile robots in the network is small, the repulsive potential force will drive them into different direction, so that during a small time period, the distance is enlarged, and the two mobile robots are dispersed from each other. It is worthwhile to notice that the smaller the distance, the greater the repulsive force.Similarly, to restrict all essential communication links withinfij(t)≥ε for all j∈𝒩l[i](t), we introduce an attractive potential function, denoted as ψija(t), where ψia(t)=∑j∈𝒩l[i](t)ψija(t). Specifically, we have
(5)ψija(t)≜(1-fij(t)-φε-φ)-ρ=(1-exp[-β(∥ξi(t)-ξj(t)∥-a0)]-φε-φ)-ρ.The attractive potential functions work in the way that any essential communication links in𝒢s(t)  remain connected during the dispersion and any reconfiguration of the network. The attractive potential function will provide artificial forces between any two logical neighbors in the multirobot network, so that they will move in the pattern to shrink their interrobot distance whenever it endangers the essential communication link between them.Furthermore, to integrate the restoration methods into multirobot dispersion, a distributed prey motion controller is developed as follows:(6)ψic(t)≜12Kc∥ξi(t)-ξjf(t)∥.The design principle of the prey motion controller is straightforward. When a mobile robot is assigned the role of prey, it is driven by the prey controller towards the last updated location of the particular failed robot, that is, itscollapsar.The proposed potential functions and controllers entitle us to assign each nodei in the network a distributed control law, which is given as the combination of the negative gradients of the aforementioned three potentials in the ξi(t) direction as follows:
(7)ui′(t)≜{-Kr∇ξi(t)∑j∈𝒩p[i](t)ψijr(t)-Ka∇ξi(t)×∑j∈𝒩l[i](t)ψija(t)-ψic(t),ifi⟶jf-Kr∇ξi(t)∑j∈𝒩p[i](t)ψijr(t)-Ka∇ξi(t)×∑j∈𝒩l[i](t)ψija(t),otherwise.It is easy to observe from (7) that the potential force can become infinite between pairs of agents whenever fij(t)→1 or fij(t)→ε. In practice, such unbounded actuation is unrealistic for most MRSs. In this paper, a piecewise-continuous function method is proposed with respect to robots’ actuation to approach the objective of boundedinput.Denoteuim(t) as the upper bound of velocity for node i, in particular, for homogeneous systems; we have uim(t)=ujm(t), where i≠j and i,j∈𝒱.Definition 9.
Given a mobile multiagent system with fixed underlying network structure𝒢*(t), a distributed piecewise-continuous control law is assigned to each mobile agent as follows:
(8)ui(t)≜{ui′(t),ui′(t)≤uim(t),uim(t)×u^i′(t),ui′(t)>uim(t),
where u^i′(t)=ui′(t)/∥ui′(t)∥ represents the unit vector of ui′(t).However, (8) may generate another problem when restoring the connectivity of the network. That is, as shown in Figure 5, when robot i is moving towards the collapsarand trying to restore the disconnection induced by the failure of node j, the formal neighboring agent of robot j (candidate prey of j, i.e., in the set ≺j(t-)) may move out of communication range centered by the last updated location of j  (this is because the original attractive potential from robot j no longer exists), shown as robot k in Figure 4. In this case, the network will still be in partition, even though robot i moves into the last updated location of j. To fix this dilemma, a nonfurther rule is designed. Specifically, whenever the network is partitioned due to the failure of mobile robot, any robot in the candidate prey set, that is, i∈≺j(t-), will only be allowed to move closer or stay stationary to its collapsar until released by the reconnection of the particular connection. The nonfurther rule is able to guarantee the reconnection of the links without further position. Therefore, the final controller yields
(9)uic(t)≜{min(ui′(t),uim(t)×u^i′(t)),i∈≺j(t-),u^i′(t)·(ξi(t)-ξjf(t))≥0,0,i∈≺j(t-),u^i′(t)·(ξi(t)-ξjf(t))<0,ui(t),i∉≺j(t-).Figure 5
Connectivity is not restorable if the candidate prey moves away from the location of the failure robots.When integrating the control law (9) into each mobile robot in the network, the DLRA and CRA will continuously update two-hop neighboring information. Relying on the information, the control law will calculate the velocity and moving direction of each mobile robot in the next step, so that the dispersion of the mobile MRS as well as the connectivity restoration can be achieved simultaneously. We name the integral control system holistic connectivity controller (HCC), which contains DLRA, CRA, and the motion control law (9), as shown in Figure 6.Figure 6
Specification design of the holistic connectivity controller (HCC).Furthermore, to understand the efficiency and capability of the HCC, in the next section, we present theoretical analysis about the restorability of the mobile MRS with HCC.


## 3.1. Connectivity Restoration Algorithm (CRA)

Denote the topology control algorithm of the connectivity restoration strategy as CRA, and the following definitions are first introduced.Definition 6.
Assume that nodej fails at time t=tf, denoted as a collapsarjf, where jf≜j(t-).Definition 7.
Denote≺j(t) as the order list of j’s neighbor nodes within two hops with respect to decreasing link quality. Note that the first two-hop neighbor appears behind the last one-hop neighbor.Definition 8.
Nodei is a potential prey of jf if and only if i≺j(t).Associated with the aforementioned definitions, CRA is described in Algorithm1. The main notion of CRA is for every logical neighbor within two hops of j to continuously track its position. Whenever j fails, one of the potential preys in ≺j(t), for example, i, will be selected as the prey to the collapsarjf; the selection of preyi is according to the following standards: (1)
i is not a current potential preyto any collapsarother than  jf;(2)
≺j(t-)∪𝒩l[i](t-)≠(𝒩l[i](t-),i);(3)
among all thecandidate preys that meet (1) and (2), the order of i is the smallest in ≺j(t).Algorithm 1:Connectivity restoration algorithm (CRA).
Upon Detecting failure of nodej at time t, jf=j(t-)
(1)  Fori∈≺j(t-) at time t=t-
(2) while  ∄k∈𝒱 where i∈≺k(t1-),t1-≤t-   do
(3)  Denote h as the position of i in vector ≺j(t-)
(4)  if  ≺j(t-)∪𝒩l[i](t-)≠(𝒩l[i](t-),i)
(5)   if  h=1
(6)    i is the prayer of jf, denote i→jf, Broadcast ack=h
(7)   else  hold until time t=(h-1)ΔT
(8)    if  Receive(ack)=0
(9)     i is the prayer of jf, denote i→jf, Broadcast ack=h
(10)    end if
(11)   end if
(12)  else
(13)     remove ≺j(t-)
(14)  end if
(15) end while
(16) End
Upon Finishing Connectivity Restoration at timet=tf
(17) For  i∈≺j(t-)
(18) if  i→jf
(19)  Broadcast Suc(jf), remove ≺j(t-)
(20) else if  Receive(Suc(jf))=1
(21)  Remove ≺j(t-)
(22) end if
(23)  End


## 3.2. Holistic Connectivity Controller (HCC)

When dispersing a team of mobile robots, the invariance of network topology in generated subgraph𝒢s(t) is prerequisite for the realization of connectivity preserving. The aim of this section is to develop a holistic distributed controller that (1) regulates the dispersion of mobile agents in continuous space, (2) reconnects the network subjected to partitions from single or multiple concurrent robots’ failures, that is, configure the prey to the optimal location, (3) avoids any link disconnection and interrobot collisions induced by the movement of mobile robots.We first utilize the combined potential function in [24] to ensure that all essential links remain connected and interagent collisions are avoided all the time during multi-agent dispersion between any two consecutive topology updates.A repulsive potential function is introduced in the HCC to deal with the dispersion of mobile multirobot networks between nodei and all its physical neighbors j∈𝒩p[i](t), defined as ψijr(t), where ψir(t)=∑j∈𝒩p[i](t)ψijr(t). In particular, we have
(3)ψijr(t)≜(1-fij(t)-ε1-ε)-ρ,
where ρ∈ℝ+, and in this paper, associated with fij(t) in (2), it yields
(4)ψijr(t)≜(1-exp[-β(∥ξi(t)-ξj(t)∥-a0)]-ε1-ε)-ρ.The design principle of repulsive potential function is to assign each mobile robot an artificial potential force; this virtue force can drive the mobile robot to move in certain direction in a way that is opposite to each other. More specifically, whenever the distance between two neighboring mobile robots in the network is small, the repulsive potential force will drive them into different direction, so that during a small time period, the distance is enlarged, and the two mobile robots are dispersed from each other. It is worthwhile to notice that the smaller the distance, the greater the repulsive force.Similarly, to restrict all essential communication links withinfij(t)≥ε for all j∈𝒩l[i](t), we introduce an attractive potential function, denoted as ψija(t), where ψia(t)=∑j∈𝒩l[i](t)ψija(t). Specifically, we have
(5)ψija(t)≜(1-fij(t)-φε-φ)-ρ=(1-exp[-β(∥ξi(t)-ξj(t)∥-a0)]-φε-φ)-ρ.The attractive potential functions work in the way that any essential communication links in𝒢s(t)  remain connected during the dispersion and any reconfiguration of the network. The attractive potential function will provide artificial forces between any two logical neighbors in the multirobot network, so that they will move in the pattern to shrink their interrobot distance whenever it endangers the essential communication link between them.Furthermore, to integrate the restoration methods into multirobot dispersion, a distributed prey motion controller is developed as follows:(6)ψic(t)≜12Kc∥ξi(t)-ξjf(t)∥.The design principle of the prey motion controller is straightforward. When a mobile robot is assigned the role of prey, it is driven by the prey controller towards the last updated location of the particular failed robot, that is, itscollapsar.The proposed potential functions and controllers entitle us to assign each nodei in the network a distributed control law, which is given as the combination of the negative gradients of the aforementioned three potentials in the ξi(t) direction as follows:
(7)ui′(t)≜{-Kr∇ξi(t)∑j∈𝒩p[i](t)ψijr(t)-Ka∇ξi(t)×∑j∈𝒩l[i](t)ψija(t)-ψic(t),ifi⟶jf-Kr∇ξi(t)∑j∈𝒩p[i](t)ψijr(t)-Ka∇ξi(t)×∑j∈𝒩l[i](t)ψija(t),otherwise.It is easy to observe from (7) that the potential force can become infinite between pairs of agents whenever fij(t)→1 or fij(t)→ε. In practice, such unbounded actuation is unrealistic for most MRSs. In this paper, a piecewise-continuous function method is proposed with respect to robots’ actuation to approach the objective of boundedinput.Denoteuim(t) as the upper bound of velocity for node i, in particular, for homogeneous systems; we have uim(t)=ujm(t), where i≠j and i,j∈𝒱.Definition 9.
Given a mobile multiagent system with fixed underlying network structure𝒢*(t), a distributed piecewise-continuous control law is assigned to each mobile agent as follows:
(8)ui(t)≜{ui′(t),ui′(t)≤uim(t),uim(t)×u^i′(t),ui′(t)>uim(t),
where u^i′(t)=ui′(t)/∥ui′(t)∥ represents the unit vector of ui′(t).However, (8) may generate another problem when restoring the connectivity of the network. That is, as shown in Figure 5, when robot i is moving towards the collapsarand trying to restore the disconnection induced by the failure of node j, the formal neighboring agent of robot j (candidate prey of j, i.e., in the set ≺j(t-)) may move out of communication range centered by the last updated location of j  (this is because the original attractive potential from robot j no longer exists), shown as robot k in Figure 4. In this case, the network will still be in partition, even though robot i moves into the last updated location of j. To fix this dilemma, a nonfurther rule is designed. Specifically, whenever the network is partitioned due to the failure of mobile robot, any robot in the candidate prey set, that is, i∈≺j(t-), will only be allowed to move closer or stay stationary to its collapsar until released by the reconnection of the particular connection. The nonfurther rule is able to guarantee the reconnection of the links without further position. Therefore, the final controller yields
(9)uic(t)≜{min(ui′(t),uim(t)×u^i′(t)),i∈≺j(t-),u^i′(t)·(ξi(t)-ξjf(t))≥0,0,i∈≺j(t-),u^i′(t)·(ξi(t)-ξjf(t))<0,ui(t),i∉≺j(t-).Figure 5
Connectivity is not restorable if the candidate prey moves away from the location of the failure robots.When integrating the control law (9) into each mobile robot in the network, the DLRA and CRA will continuously update two-hop neighboring information. Relying on the information, the control law will calculate the velocity and moving direction of each mobile robot in the next step, so that the dispersion of the mobile MRS as well as the connectivity restoration can be achieved simultaneously. We name the integral control system holistic connectivity controller (HCC), which contains DLRA, CRA, and the motion control law (9), as shown in Figure 6.Figure 6
Specification design of the holistic connectivity controller (HCC).Furthermore, to understand the efficiency and capability of the HCC, in the next section, we present theoretical analysis about the restorability of the mobile MRS with HCC.


## 4. Restorability of the Mobile MRS with HCC

As is described in Section3, HCC is able to handle the network partition induced by not only failure of a single robot, but also simultaneous failures of multiple robots. Therefore, in this section, the restorability of the multirobot network is analyzed in both scenarios.To understand how HCC works in the case of single robot failure, we first have the following lemma.Lemma 10.
The disconnection of𝒢(t) induced by the failure of j is recoverable if and only if there exists at least one i∈≺j, such that the network can be reconnected by replacing j with i in every 𝒩l[k](t), k∈𝒱.The proof is straightforward and is omitted in this paper. With the aid of  Lemma10, we first investigate the case of single agent failure.Theorem 11.
Assume a mobile multi-agent network𝒢(t) with initial connectedness. Further assume that the network is disconnected by the failure of a single node j. The HCC guarantees that the connectivity of 𝒢(t) can be restored within finite time t<∞.Proof.
The result is obvious for the case that𝒱≤2. For 𝒱>2, there is at least one node i, where i→jf. To see this, suppose that there is no prey for jf; from Algorithm 1 we have ≺j⊆∅; thus 𝒩l[j](t-)⊆∅, so that j is an information island (information Island is a body of information (i.e., agent information) that needs to be shared but has no network connection) at time t-, since 𝒱>2, so the network is disconnected at time t-, contradiction reached. Furthermore, from (6) it is easy to observe that limt→∞ψic(t)=0, for example, limt→∞∥ξi(t)-ξjf(t)∥=0. Since the artificial potential rules out the possibility of further disconnection of communication links between any logical neighbors, we conclude that no disconnection by the failure of a single agent in 𝒢(t) is unrecoverable within finite time t<∞, which completes the proof.To understand the connectivity restorability of mobile multirobot networks with respect to the case of multiple simultaneous agent failures, we provide the following illustrative analysis.First, we denote thecollapsar setof all collapsars at time t to be 𝒞, where 𝒞≜{jfl∣l=1,2,…,n,jfl=jl(t-)∈𝒱}, and the one-hop potential prey setto be 𝒫, where 𝒫≜{i∣i∈≺jl(t-)∩i∈𝒩l[jl](t-)}. We denote a mapping from 𝒞 to 𝒫 as 𝒞⇄𝒫 if there exists at least one i, where i∈𝒫, for every jfl∈𝒞, as is shown in Figure 7.Figure 7
With a loop circuit structure, the network disconnection induced by concurrent multiple failures of agents is unrecoverable.With the aforementioned notions, we conclude the following.Theorem 12.
With respect to the simultaneous failure of multiple robots in MRS system, the connectivity of the network is not restorable by HCC if𝒞  and 𝒫 form a consecutive loop circle formation.Proof.
Refer to Figure7 for the consecutive loop circle formation of the network topology. As was described, 𝒫≜{i∣i∈≺jl(t-)∩i∈𝒩l[jl](t-)} denotes the one-hop potential prey set. And 𝒞≜{jfl∣l=1,2,…,n,jfl=jl(t-)∈𝒱} represents their dedicated sets ofcollapsars. Here, let us take 𝒞1, 𝒞2, and 𝒫1; for example, as the mobile robot in 𝒞1 and 𝒞2 failed, the potential prey in 𝒫1 will be assigned to restore the connectivity, recalling that the potential preys are all one-hop, so that while they are trying to restore the dedicatedcollapsars, for instance, the one in 𝒞1, their movements have to be restricted to avoid further partition of the network, according to the nonfurther rule presented in Section 3.2. Therefore, the network disconnection induced by 𝒞1 and 𝒞2  is not restorable by 𝒫1. Consequently, if 𝒞 and 𝒫 form a consecutive loop circle formation, none of the collapsar sets in the underlying network topology is restorable by HCC.


## 5. Experimental Simulations

To evaluate the performance of the proposed HCC for multirobot dispersion with respect to failure of mobile nodes, a variety of simulations have been conducted, and the results are presented in this section. The simulations are categorized into three subcategories: (1) multirobot dispersion without failure of mobile robot, (2) multirobot dispersion with the failure of a single robot, and (3) multirobot dispersion with respect to simultaneous failure of multiple mobile robots. General parameters are set as in Table1.Table 1
Simulation parameters.
Symbol
Quantity
Value
Δ
t
Execution time slot
0.01 s
Δ
T
Interval of consecutive switches
0.1 s
ε
Minimum sensing capability of normalized RSSI
10%
φ
Optimized sensing value of normalized RSSI
40%
a
0
Restricted radium (reference distance)
2 m
β
Path loss (outdoor, 802.11b)
0.02
ρ
Exponential gain
0.7
K
r
Repulsive potential gain
2500
K
a
Attractive potential gain
200
K
c
Restoration potential gain
10
u
m
(
t
)
Maximum agent velocity
5 m/s−1


### 5.1. Multirobot Dispersion without Failure of Mobile Robot

In case no mobile robot failed during dispersion, the HCC will not trigger CRA, and the motion controller law (7) will be simplified as
(10)ui′(t)≜-Kr∇ξi(t)∑j∈𝒩p[i](t)ψijr(t)-Ka∇ξi(t)∑j∈𝒩l[i](t)ψija(t).We simulate the dispersion of 20 mobile robots initially located within 100 m × 100 mℝ2 space. The snapshot of the MRS’s evolution is shown in Figure 8. The dark squares represent the mobile robots, and the green circles represent the semidistance (semidistance represents a value that is 5% shorter than half of the communication range; the use of it here is for the sake of facilitating the observation) of communication range. The mobile robots are under the communication range of each other if and only if the two corresponding circles overlap. With the control of DLRA and HCC, a mobile network consisting of 20 mobile robots in a dense initial formation (as in Figure 8(a)) can disperse into a much sparse configuration (as shown in Figure 8(d)) within limited time. Moreover, the redundant communication links can be removed effectively during the dispersion, and the connectivity of the network is always preserved.The evolution trajectory of a mobile MRS under the HCC. (a)t=0 s, (b) t=20 s, (c) t=40 s, (d) t=60 s.
(a)
(b)
(c)
(d)We further conducted simulations to evaluate the effectiveness and the stability of the HCC in multirobot dispersion without robot failures. It can be seen from Figure9(a) that the average communication links of each mobile robot in the initial configuration are 19; this is because the initial interrobot distance is relatively small, compared to the radio range of the mobile devices, so that the network is a complete graph. During the dispersion, the average communication links of each mobile robot declined rapidly and converged to near the value of 2 in 60 seconds, which is almost the structure of a tree, so that the network can be sparse enough to facilitate the dispersion. In the meantime, the velocities of the mobile robots in X and Y axis during the dispersion are revealed in Figures 9(b) and 9(c), respectively. From the observation, it is safe to say that the velocities of the mobile robots are always bounded, and the whole system will converge to a stable status within finite time.Average communication links and robots’ velocities during dispersion.
(a)
Average communication links
(b)
Robots’ velocity inX axis
(c)
Robots’ velocity inY axis


### 5.2. Multirobot Dispersion with the Failure of a Single Robot

To evaluate the HCC in case of single robot failure, we further conduct an experimental simulation with a networked MRS scenario with 11 mobile robots. At a certain point during dispersion, one of the mobile robots failed, and the network is partitioned into two connected subgraphs. The results can be found in Figure10.Restoration process with respect to the failure of single mobile robot during dispersion. (a)t=0 s, (b) t=10 s, (c) t=20 s, (d) t=30 s.
(a)
(b)
(c)
(d)In Figure10(a), the mobile robot fails at a certain time during simulation; we denote it at time t = 0 s and mark the last updated location of the failed robot as a green circle. It can be seen from Figure 10(b) that, within a short time period (in less than 10 s), the connectivity of mobile network is recovered with the aid of HCC. Furthermore, Figures 10(c) and 10(d) reveal that the dispersion of the mobile MRS is not affected by the failure of the single mobile robot, and the network continues to configure into their final formation to fulfill the mission of the multirobot dispersion. In the meantime, further partition of the network is avoided, and the mobile robots are always collision-free. Since DLRA is also working in the HCC, the shortest circle of the network is bounded, in accordance with Lemma 5. In this simulation scenario, the shorted circle is 7, as shown in Figure 10(d).


### 5.3. Multirobot Dispersion with respect to Simultaneous Failure of Multiple Mobile Robots

A scenario of 18 mobile robots is then evaluated with the control of HCC, as shown in Figure11. During the dispersion, 3 mobile robots failed concurrently at a certain time. And the mobile network is partitioned into 3 connected segments, as in Figure 11(a). HCC first selects 3 preys for each of the failed robots using CRA, and then the motion controller drives each of the preys towards their collapsar to restore the disconnection induced by the failed robots. In the meantime, the MRS is still configured into their desired formation to enhance the coverage of the system, with guaranteed connectivity and collision avoidance. It is noticeable that during the restoration, the mobility of all potential preys is constrained with nonfurther rule, and they are only allowed to stay still or move towards their collapsar. Note that Figure 11(d) only shows the time when every prey moved into the last updated location of their collapsars, so that there is a short circle of 3 in the snapshot, since the dispersion is not finished yet.Restoration process with respect to the simultaneous failures of multiple mobile robots during dispersion. (a)t=0 s, (b) t=15 s, (c) t=30 s, (d) t=40 s.
(a)
(b)
(c)
(d)As is argued in Section4, the disconnection induced by simultaneous failures of multiple mobile robots is not always restorable, as is shown in Theorem 12. The scenario in Figure 11, apparently, fulfills the requirement of restorable network structure. However, there are cases where the connectivity is not always restorable with respect to the failure of multiple mobile robots. Whereas this phenomena is inevitable, HCC only relies on local information of no more than two-hop neighbors.As is shown in Figure12, the network of 10 mobile robots is initially connected during the dispersion; 4 of the robots failed concurrently at the same time. Due to the fact that only two-hop neighboring information is available and the network is consecutive loop circle formation, the damaged connectivity is not restorable using HCC. It is worthwhile to notice that there are existing methods to restore network connectivity in any disconnection. However, global information is always required.Unrecoverable network with respect to the simultaneous failures of multiple mobile robots during dispersion. (a)t=0 s, (b) t=30 s.
(a)
(b)


## 5.1. Multirobot Dispersion without Failure of Mobile Robot

In case no mobile robot failed during dispersion, the HCC will not trigger CRA, and the motion controller law (7) will be simplified as
(10)ui′(t)≜-Kr∇ξi(t)∑j∈𝒩p[i](t)ψijr(t)-Ka∇ξi(t)∑j∈𝒩l[i](t)ψija(t).We simulate the dispersion of 20 mobile robots initially located within 100 m × 100 mℝ2 space. The snapshot of the MRS’s evolution is shown in Figure 8. The dark squares represent the mobile robots, and the green circles represent the semidistance (semidistance represents a value that is 5% shorter than half of the communication range; the use of it here is for the sake of facilitating the observation) of communication range. The mobile robots are under the communication range of each other if and only if the two corresponding circles overlap. With the control of DLRA and HCC, a mobile network consisting of 20 mobile robots in a dense initial formation (as in Figure 8(a)) can disperse into a much sparse configuration (as shown in Figure 8(d)) within limited time. Moreover, the redundant communication links can be removed effectively during the dispersion, and the connectivity of the network is always preserved.The evolution trajectory of a mobile MRS under the HCC. (a)t=0 s, (b) t=20 s, (c) t=40 s, (d) t=60 s.
(a)
(b)
(c)
(d)We further conducted simulations to evaluate the effectiveness and the stability of the HCC in multirobot dispersion without robot failures. It can be seen from Figure9(a) that the average communication links of each mobile robot in the initial configuration are 19; this is because the initial interrobot distance is relatively small, compared to the radio range of the mobile devices, so that the network is a complete graph. During the dispersion, the average communication links of each mobile robot declined rapidly and converged to near the value of 2 in 60 seconds, which is almost the structure of a tree, so that the network can be sparse enough to facilitate the dispersion. In the meantime, the velocities of the mobile robots in X and Y axis during the dispersion are revealed in Figures 9(b) and 9(c), respectively. From the observation, it is safe to say that the velocities of the mobile robots are always bounded, and the whole system will converge to a stable status within finite time.Average communication links and robots’ velocities during dispersion.
(a)
Average communication links
(b)
Robots’ velocity inX axis
(c)
Robots’ velocity inY axis


## 5.2. Multirobot Dispersion with the Failure of a Single Robot

To evaluate the HCC in case of single robot failure, we further conduct an experimental simulation with a networked MRS scenario with 11 mobile robots. At a certain point during dispersion, one of the mobile robots failed, and the network is partitioned into two connected subgraphs. The results can be found in Figure10.Restoration process with respect to the failure of single mobile robot during dispersion. (a)t=0 s, (b) t=10 s, (c) t=20 s, (d) t=30 s.
(a)
(b)
(c)
(d)In Figure10(a), the mobile robot fails at a certain time during simulation; we denote it at time t = 0 s and mark the last updated location of the failed robot as a green circle. It can be seen from Figure 10(b) that, within a short time period (in less than 10 s), the connectivity of mobile network is recovered with the aid of HCC. Furthermore, Figures 10(c) and 10(d) reveal that the dispersion of the mobile MRS is not affected by the failure of the single mobile robot, and the network continues to configure into their final formation to fulfill the mission of the multirobot dispersion. In the meantime, further partition of the network is avoided, and the mobile robots are always collision-free. Since DLRA is also working in the HCC, the shortest circle of the network is bounded, in accordance with Lemma 5. In this simulation scenario, the shorted circle is 7, as shown in Figure 10(d).


## 5.3. Multirobot Dispersion with respect to Simultaneous Failure of Multiple Mobile Robots

A scenario of 18 mobile robots is then evaluated with the control of HCC, as shown in Figure11. During the dispersion, 3 mobile robots failed concurrently at a certain time. And the mobile network is partitioned into 3 connected segments, as in Figure 11(a). HCC first selects 3 preys for each of the failed robots using CRA, and then the motion controller drives each of the preys towards their collapsar to restore the disconnection induced by the failed robots. In the meantime, the MRS is still configured into their desired formation to enhance the coverage of the system, with guaranteed connectivity and collision avoidance. It is noticeable that during the restoration, the mobility of all potential preys is constrained with nonfurther rule, and they are only allowed to stay still or move towards their collapsar. Note that Figure 11(d) only shows the time when every prey moved into the last updated location of their collapsars, so that there is a short circle of 3 in the snapshot, since the dispersion is not finished yet.Restoration process with respect to the simultaneous failures of multiple mobile robots during dispersion. (a)t=0 s, (b) t=15 s, (c) t=30 s, (d) t=40 s.
(a)
(b)
(c)
(d)As is argued in Section4, the disconnection induced by simultaneous failures of multiple mobile robots is not always restorable, as is shown in Theorem 12. The scenario in Figure 11, apparently, fulfills the requirement of restorable network structure. However, there are cases where the connectivity is not always restorable with respect to the failure of multiple mobile robots. Whereas this phenomena is inevitable, HCC only relies on local information of no more than two-hop neighbors.As is shown in Figure12, the network of 10 mobile robots is initially connected during the dispersion; 4 of the robots failed concurrently at the same time. Due to the fact that only two-hop neighboring information is available and the network is consecutive loop circle formation, the damaged connectivity is not restorable using HCC. It is worthwhile to notice that there are existing methods to restore network connectivity in any disconnection. However, global information is always required.Unrecoverable network with respect to the simultaneous failures of multiple mobile robots during dispersion. (a)t=0 s, (b) t=30 s.
(a)
(b)


## 6. Conclusion

In most mobile multirobot applications, dispersion of mobile robots in a certain formation is often required. However, due to the complex and extreme environments in deploying robot team, single or multiple concurrent failures of mobile robot are inevitable. One of the most important problems induced by the failure of mobile robot is the disconnection in the underlying network. In this paper, we investigated and solved the aforementioned problem by designing a holistic connectivity controller (HCC). The proposed HCC can regulate and restore the interagent connections during the dispersion of the mobile multirobot network. Two main components are included in the HCC. Firstly, to illustrate the multirobot dispersion, we adopt the distributed link removal algorithm (DLRA), which is able to remove redundant links in the multirobot network to facilitate the dispersion. Secondly, the proposed approach is extended to the problem of connectivity restoration with consideration of concurrent failure of multiple agents. A connectivity restoration strategy is proposed, and then the recoverability of network connectivity is provided to unfold the capability of HCC with respect to simultaneous failure of multiple robots. The proposed HCC has also integrated motion controller to regulate the movement of the mobile robots, so that interrobot collisions can be effectively avoided. It is worthwhile to mention that the HCC only relies on local information of no more than two-hop neighbors, so the message complexity can be minimized. Finally, theoretical analysis and computer simulations are also provided to confirm the efficiency and scalability of the proposed schemes.



---

*Source: 630175-2013-05-12.xml*