# Decentralized Discrete-Time Formation Control for Multirobot Systems

Authors: E. G. Hernandez-Martinez; J. J. Flores-Godoy; G. Fernandez-Anaya
Journal: Discrete Dynamics in Nature and Society
 (2013)

---

## Abstract

Inspired from the collective behavior of biological entities for the group motion coordination, this paper analyzes the formation control of mobile robots in discrete time where each robot can sense only the position of certain team members and the group behavior is achieved through the local interactions of robots. The main contribution is an original formal proof about the global
convergence to the formation pattern represented by an arbitrary Formation Graph using attractive potential functions. The analysis is addressed for the case of omnidirectional robots with numerical simulations.


---

## Body

## 1. Introduction

In the last years, the control community has a special interest in the study of the coordination of multiple mobile robots [1]. This idea originated in the observation and simulation of the collective behavior of some biological entities, like ants, fishes, or birds, where they achieve complex group behaviors trough some network communication channels and an ordered motion coordination. Therefore, research areas as Multi-Agent Systems, sensor networks, and distributed control systems assume that the modeling and implementations of these natural behaviors could solve the coordination of mobile robots in industrial and service applications [2].According to [3], when a group of animals work together, they combine their local sensors to maximize the detection range to find food or to alert the presence of predators more efficiently. So, the collective behavior is induced by survival intentions and the group behavior exhibits a complex self-organization constructed by the local interactions of the team members. The literature of small robots that reproduce the behavior of small collective animals is commonly named as swarms robots and there exist a wide range of approaches related to self-organization, fault tolerance and repairs, and so forth [4]. Another field of study is about the motion coordination found in some species of birds. In [5], Reynolds proposed that the mobile agents, referred to as boids, have a common leader (role assignment), and each agent has a local strategy based on three components: separation, alignment, and cohesion to maintain the formation during the flight. It is proposed that the movement rules must be decentralized, reactive for the collision avoidance and the eventual appearance of different roles in the group. The natural behavior of biological entities, as those studied by Reynolds, has inspired the motion coordination of mobile robots, for instance [6–8]. Finally, another cooperative control strategy deals with the reproduction of complex behaviors observed in herd of animals which more intentional than being innate or reactive to survival, for instance, the prey-hunter behavior, hierarchical social organization, group searching and rescue tasks, and else. These high level behaviors maximize the individual capacities and have been implemented in robot soccer competitions, military operations, robotic-based vigilance, manufacturing systems, and so forth, where the game theory, artificial intelligence, ethology, and discrete-event systems have some important contributions [9].This paper is related to a motion coordination problem, named Formation control, where the robots converge to some static formation patterns [10]. Following the principles of motion coordination of the nature, all the robots must be formed obeying a local control law based on the partial knowledge about the position of certain team members measure of their local sensors. Formation control is a basic problem of robot coordination because it is contained in the majority of the tasks of multirobot systems, where the agents must occupy strategic postures or displacements within a workspace [10]. For example, in vigilance and exploration tasks, the robots are moved in a specific formation to maximize their detection capacities and eventually change the formation if an agent is broken down [3]. In searching and rescue operations, the robots share the information captured by each robot and eventually they are regrouped in formation patterns [11]. Finally, in the case of manipulation of large objects, the robots must conserve a rigid formation to carry out the workpiece [1, 12].The formation control strategies based in biological systems can be classified in two schemes. The first proposes reactive schemes that includes the majority of theswarms intelligence, where the robots are formed following simple reactive behavior rules, as maintaining a distance between neighbors without a specific position within the formation. The second scheme is based in a prescribed topology of interrobot communication, commonly represented by a Formation Graph (FG) [13, 14], where each node is related to the position of an agent and the edges represented the possible communication (bidirectional or unidirectional channel) between pair of robots. A well-defined FG must be connected; that is, there are no isolated nodes, and for every edge is associated a relative vector of desired position between robots [9].This FG-based scheme can provide specific postures of robots in the formation and the facility to analyze eventual changes of formation and leader roles, intermittent and delayed communication, and other dynamic behaviors [15, 16]. The majority of the approaches are analyzed for the case of continuous time, where commonly the analysis is reduced to some special topologies of FG identified as the most representatives of the collective behavior of biological systems. For instance, the complete FG [17], where there exists bidirectional communication in any pair of robots, cyclic pursuit formation [8], the start-like formation centered on a leader [18], or the open-chain or convoy configuration [19]. Few works address the general case of undirected FG [20], and more recently, in our previous work [21], we present a formal proof about the convergence for all kinds of FG with attractive potential functions.On the other hand, the discrete-time formation control has been primarily studied by some consensus algorithms [22] that conceptually differ from formation control due to the incorporation of the relative position vectors, which could cause a formation infeasibility due to the disappearance of equilibria, and the interrobot collisions in physical implementations. Other works as [23] address the case of flocking behavior in discrete-time only. Recently, [24] analyzes the global convergence in discrete-time for two topologies of FG only and its extension to unicycle-type robots. Then, inspired from our previous work [21], this paper extends the analysis of formation convergence in continuous time using potential functions to the case of an arbitrary well-defined FG in discrete time. The analysis is focused on the case of omnidirectional robots or point robots in the plane. The main contribution is an original formal proof about the convergence of robots to multiple equilibria where the robots are placed in the desired formation. The collision avoidance is not included in the analysis following the practical assumptions of [8, 25, 26] where reactive routines appear momentarily if the robots detect a shock danger or if the initial postures of robots generated free-collision trajectories, which occur frequently in the nature behaviors.The rest of the paper is organized as follows. Section2 introduces the kinematic models and the main concepts of FG. The discrete-time formation control and the analysis of the global convergence are presented in Section 3. Some numerical simulations are given in Section 4. Finally, some concluding remarks are given in Section 5.


## 2. Problem Statement and Formation Graphs

### 2.1. Kinematic Models and Problem Statement

Denote byN={R1,…,Rn} a set of n agents moving in plane with positions zi(t)=[xi(t),yi(t)]T, i=1,…,n. The kinematic model of each agent or robot Ri is described by
(1)z˙i=ui,i=1,…,n,
where ui=[ui1,ui2]T∈ℜ2 is the velocity of ith robot along the x- and y-axes. Using the Euler-based discretization, the approximated model of (1) now is given by
(2)zi(kT+T)=zi(kT)+Tz˙i=zi(kT)+Tui(kT),i=1,…,n,
where T is the sampling and k=0,1,2,…. For a more compact notation, in the rest of the paper, we denote zi+=zi(kT+T),zi=zi(kT) and ui=ui(kT), respectively, then
(3)zi+=zi+Tui,i=1,…,n.LetNi⊆{z1,…,zn}, Ni≠∅, i=1,…,n denote the subset of positions of the agents which are detectable for Ri. Let cji=[hji,vji]T, for all  j∈Ni  denote a time-invariant vector which represents the desired position of Ri with respect to Rj in a particular formation. Thus, we define the desired relative position of every Ri in the formation by
(4)zi*=φi(Ni)=1ni∑j∈Ni‍(zj+cji),i=1,…,n,
where ni is the cardinality of Ni. Thus, the desired relative position of Ri can be considered as a combination of the desired positions of zi with respect to the positions of all elements of Ni.Problem Statement. The control objective is to design a control law ui(t)=gi(Ni(t)) for every robot Ri, such that limt→∞(zi-zi*)=0,i=1,…,n.


### 2.2. Formation Graphs

According to [14, 20, 27], the desired formations of an agents’ group can be represented by a Formation Graph (FG) defined by:Definition 1.
A Formation GraphG={Q,E,C} is a triplet that consists in (i) a set of vertices Q={R1,R2,…,Rn} related to the team members, (ii) a set of edges E={(j,i)∈Q×Q}, i≠j containing pairs of nodes that represent interagent communications, therefore (j,i)∈E if and only if j∈Ni, and (iii) a set of vectors C={cji},  for all  (j,i)∈E that specify the desired relative position between agents i and j, that is, zi-zj=cji∈ℜ2, for all  i≠j,  j∈Ni in a desired formation pattern.If(i,j)∈E, the the vertices i and j are called adjacent. The degree gi of the ith vertex is defined as the number of its adjacent vertices. A path from vertex i to j is a sequence of distinct vertices starting with i and ending with j such that consecutive vertices are adjacent. The underlying graph of a FG, is the graph where for all  (i,j)∈E, is added a new edge (j,i), if it does not appear on the original FG. The underlying graph is always an undirected graph. If there is a path between any two vertices of the underlying graph of FG, then the FG is said to be connected. Thus, a FG is said to be well defined if it satisfied the following conditions: (1) the graph is connected, (2) there are no conflicts in the desired vectors of positions, in the sense that if cij,cji∈C, then cij=-cji, and (3) the desired vectors of positions establish a closed-formation, that is, if there exist the vectors  cjm1,cm1m2,cm2m3,…,cmrj, then they must satisfy
(5)cjm1+cm1m2+cm2m3+⋯+cmrj=0.
The previous condition establishes that some position vectors form closed-polygons. Figure 1 shows an example of the formation of four robots with their detectable subsets Ni and the FG, including the closed formation conditions of vectors cji.Figure 1
Example of Formation Graph.The matrix of a FG that captures the topological properties of the graph is called theLaplacian matrix and it is defined in what follows.Definition 2.
The Laplacian matrix of a Formation GraphG is the matrix ℒ(G)=Δ-Ad, where Δ=diag[g1,…,gn], where gi is the degree of the vertex i and Ad∈ℝn×n is called the Adjacency matrix with elements
(6)aij={1,if(j,i)∈E(orequivalentlycji∈C),0,otherwise.For a connected FG, the Laplacian matrix has a single zero eigenvalue and the corresponding eigenvector is the vector[1,…,1]T∈ℝn [20]. Figure 1 shows an example of the Laplacian matrix of a FG. Note that, in general gi=ni, i=1,…,n.Finally, a FG is said to bedirected if for all  (j,i)∈E, then (i,j)∉E (or j∈Ni but i∉Nj), that is, the communication between pair of agents is one-way, undirected if forall(j,i)∈E then for all  (i,j)∈E (or j∈Ni and i∈Nj) and the communication between each pair of agents is a bidirectional channel, and mixed otherwise. For the case of undirected FG, the Laplacian is always a symmetric semidefinite matrix [20]. Note that Figure 1 presents a mixed FG.For completeness of the paper, we introduce the next matrix operation [20].Definition 3 (Kronecker product).
LetA∈ℝn×m with elements aij and let B∈ℝp×q, then, the Kronecker product of A and B (denoted by (A⊗B)∈ℝnp×mq) is given by
(7)A⊗B=[a11B⋯a1mB⋮⋱⋮an1B⋯anmB].
The Kronecker product allows a more compact notation for systems’ equations.


## 2.1. Kinematic Models and Problem Statement

Denote byN={R1,…,Rn} a set of n agents moving in plane with positions zi(t)=[xi(t),yi(t)]T, i=1,…,n. The kinematic model of each agent or robot Ri is described by
(1)z˙i=ui,i=1,…,n,
where ui=[ui1,ui2]T∈ℜ2 is the velocity of ith robot along the x- and y-axes. Using the Euler-based discretization, the approximated model of (1) now is given by
(2)zi(kT+T)=zi(kT)+Tz˙i=zi(kT)+Tui(kT),i=1,…,n,
where T is the sampling and k=0,1,2,…. For a more compact notation, in the rest of the paper, we denote zi+=zi(kT+T),zi=zi(kT) and ui=ui(kT), respectively, then
(3)zi+=zi+Tui,i=1,…,n.LetNi⊆{z1,…,zn}, Ni≠∅, i=1,…,n denote the subset of positions of the agents which are detectable for Ri. Let cji=[hji,vji]T, for all  j∈Ni  denote a time-invariant vector which represents the desired position of Ri with respect to Rj in a particular formation. Thus, we define the desired relative position of every Ri in the formation by
(4)zi*=φi(Ni)=1ni∑j∈Ni‍(zj+cji),i=1,…,n,
where ni is the cardinality of Ni. Thus, the desired relative position of Ri can be considered as a combination of the desired positions of zi with respect to the positions of all elements of Ni.Problem Statement. The control objective is to design a control law ui(t)=gi(Ni(t)) for every robot Ri, such that limt→∞(zi-zi*)=0,i=1,…,n.


## 2.2. Formation Graphs

According to [14, 20, 27], the desired formations of an agents’ group can be represented by a Formation Graph (FG) defined by:Definition 1.
A Formation GraphG={Q,E,C} is a triplet that consists in (i) a set of vertices Q={R1,R2,…,Rn} related to the team members, (ii) a set of edges E={(j,i)∈Q×Q}, i≠j containing pairs of nodes that represent interagent communications, therefore (j,i)∈E if and only if j∈Ni, and (iii) a set of vectors C={cji},  for all  (j,i)∈E that specify the desired relative position between agents i and j, that is, zi-zj=cji∈ℜ2, for all  i≠j,  j∈Ni in a desired formation pattern.If(i,j)∈E, the the vertices i and j are called adjacent. The degree gi of the ith vertex is defined as the number of its adjacent vertices. A path from vertex i to j is a sequence of distinct vertices starting with i and ending with j such that consecutive vertices are adjacent. The underlying graph of a FG, is the graph where for all  (i,j)∈E, is added a new edge (j,i), if it does not appear on the original FG. The underlying graph is always an undirected graph. If there is a path between any two vertices of the underlying graph of FG, then the FG is said to be connected. Thus, a FG is said to be well defined if it satisfied the following conditions: (1) the graph is connected, (2) there are no conflicts in the desired vectors of positions, in the sense that if cij,cji∈C, then cij=-cji, and (3) the desired vectors of positions establish a closed-formation, that is, if there exist the vectors  cjm1,cm1m2,cm2m3,…,cmrj, then they must satisfy
(5)cjm1+cm1m2+cm2m3+⋯+cmrj=0.
The previous condition establishes that some position vectors form closed-polygons. Figure 1 shows an example of the formation of four robots with their detectable subsets Ni and the FG, including the closed formation conditions of vectors cji.Figure 1
Example of Formation Graph.The matrix of a FG that captures the topological properties of the graph is called theLaplacian matrix and it is defined in what follows.Definition 2.
The Laplacian matrix of a Formation GraphG is the matrix ℒ(G)=Δ-Ad, where Δ=diag[g1,…,gn], where gi is the degree of the vertex i and Ad∈ℝn×n is called the Adjacency matrix with elements
(6)aij={1,if(j,i)∈E(orequivalentlycji∈C),0,otherwise.For a connected FG, the Laplacian matrix has a single zero eigenvalue and the corresponding eigenvector is the vector[1,…,1]T∈ℝn [20]. Figure 1 shows an example of the Laplacian matrix of a FG. Note that, in general gi=ni, i=1,…,n.Finally, a FG is said to bedirected if for all  (j,i)∈E, then (i,j)∉E (or j∈Ni but i∉Nj), that is, the communication between pair of agents is one-way, undirected if forall(j,i)∈E then for all  (i,j)∈E (or j∈Ni and i∈Nj) and the communication between each pair of agents is a bidirectional channel, and mixed otherwise. For the case of undirected FG, the Laplacian is always a symmetric semidefinite matrix [20]. Note that Figure 1 presents a mixed FG.For completeness of the paper, we introduce the next matrix operation [20].Definition 3 (Kronecker product).
LetA∈ℝn×m with elements aij and let B∈ℝp×q, then, the Kronecker product of A and B (denoted by (A⊗B)∈ℝnp×mq) is given by
(7)A⊗B=[a11B⋯a1mB⋮⋱⋮an1B⋯anmB].
The Kronecker product allows a more compact notation for systems’ equations.


## 3. Formation ControL Strategy

For system (3), local Attractive Potential Functions (APFs) are defined by
(8)γi=∥zi-zi*∥2,i=1,…,n.The functionsγi are always positives and reach their minimum (γi=0) when zi=zi*, i=1,…,n. Then, a discrete-time control law based only on APFs is defined as
(9)ui=-K2T(∂γi∂zi)T=-KT(zi-zi*),i=1,…n,
where K>0 is a gain parameter.Theorem 4.
Consider the system (3) and the control law (9). Suppose that 0<K<1 and the desired formation is based on a well-defined FG. Then, in the closed-loop system, formed by (3) and control law (9), the agents converge exponentially to the desired formation pattern, that is, limt→∞(zi-zi*)=0, i=1,…,n.The proof requires some preliminary lemmas.Lemma 5.
LetA∈ℝn×n, if around every principal diagonal element aii one draws a circle with radius given by the sum of the absolute values of the other elements on the same row, that is, ri=∑j=1,j≠in|aij|, then every eigenvalue of A lies in one of these circles, known as Gershgorin circles [28].Lemma 6.
If the matrixA∈ℝn×n has eigenvalues [λ1,…,λn], where |λi|<1, i=1,…,n, then discrete-time linear system x+=Ax is asymptotically stable [29].Proof of Theorem4.
The closed-loop system, formed by (3) and the control law (9), the discrete-time dynamics of each coordinate zi, is given by
(10)zi+=zi-K(zi-zi*)=-Kgi∑j∈Ni‍(zi-zj-cji),i=1,…,n
and the dynamics of all coordinates zi in matrix form are given by
(11)z+=-KΔ((ℒ(G)⊗I2)z-c),
where z=[z1,…,zn]T∈ℝ2n,  ℒ(G) is the Laplacian matrix of the FG, ⊗ denotes the Kronecker product, I2 is the 2×2 identity, and
(12)c=[∑j∈N1‍cj1⋮∑j∈Nn‍cjn]∈ℝ2n.
The matrixΔ forces the multiplication of the ith row of the Laplacian matrix and vector c by the vertex degree gi. Define the formation errors as
(13)ei=zi-zi*,i=1,…,n.
Note thatzi+=zi-Kei,i=1,…,n. The dynamics of the formation errors are given by
(14)ei+=zi+-(zi*)+=zi-Kei-1gi∑j∈Ni‍(zj++cji+),i=1,…,n.
Substitutingzj+=zj-Kej and cji+=cji for the case of time-invariant vectors of position, then
(15)ei+=zi-Kei+Kgi∑j∈Ni‍ej-1gi∑j∈Ni‍(zj+cji)︸zi*,i=1,…,n,ei+=(1-K)ei+Kgi∑j∈Ni‍ej,i=1,…,n,
and written in matrix form,
(16)e+=(B⊗I2)e,
where e=[e1,…,en]T and B∈ℜn×n is a matrix with elements
(17)bij={1-K,ifi=j,Kgi,ifi≠j.
Using Lemma5, from the linear system (16), it is possible to draw n circles where the center of every circle i is 1-K>0 with radio equal to K. Therefore if 0<K<1 all the eigenvalues of matrix B remains within the unitarian circle, and therefore by Lemma 6, the system is asymptotically stable and the formation errors converge exponentially to zero.
Note that the convergence of the formation errors is translated into the stability of the equilibrium pointe=0, which do not prove directly the convergence of the robots to the desired formation, due to possibility of solutions that could appear in these equilibrium point. Analyzing this, the system equations of the errors ei=zi-zi*=(1/gi)∑j∈Ni‍(zi-zj-cji),i=1,…,n given in (13) can be expressed in matrix form as
(18)e=(Δ-1ℒ(G)⊗I2)z-(Δ-1⊗I2)c,
where e=[e1,…,en]T and z=[z1,…,zn]T. When the formation errors have converged to zero, then it is satisfied that
(19)(Δ-1⊗I2)-1(Δ-1ℒ(G)⊗I2)z=c
by the properties of the Kronecker [29]
(20)(ℒ(G)⊗I2)z=c.
Thus, the solution ofz can be decomposed in z=zh+zp, the homogeneous and a particular solution, respectively. As mentioned before, for a connected FG, the Laplacian matrix ℒ(G) has a single zero eigenvalue and the corresponding eigenvector is the vector [1,…,1]T∈ℜn; this means that all the rows of the Laplacian matriz sum zero. Therefore, the homogeneous solution is given by zh=[1,…,1]Tq,  q∈ℜ. Then it is possible to reduce the last row of the Laplacian matrix in (20) through the premultiplication of an appropriated matrix; that is,
(21)(Sℒ(G)⊗I2)z=(S⊗I2)c,
where
(22)S=[10⋯001⋯0⋮⋮⋱⋮11⋯1],
generating the next reduced general equation
(23)([L1M01×(n-1)0])⊗I2[z1⋮zn-1zn]=[c1∑i=1n∑j∈Nicji],
where c1=[∑j∈N1‍cj1,…,∑j∈Nn-1‍cj(n-1)]T,L1∈ℜ(n-1)×(n-1) is the (n-1)×(n-1) submatrix form with the first (n-1) rows and columns from ℒ(G), and M∈ℜ(n-1)×1 is the last column from ℒ(G) with just the n-1 rows. Note that there exist an infinity number of equilibrium points since ∑i=1n‍∑j∈Ni‍cji=0 which is the closed-formation condition given by (5) of a FG, where all the sums of all relative position vectors of the connected FG sum zero. The solution to (23) is
(24)[z1⋮zn-1]=(L1⊗I2)-1c1-(L1-1M⊗I2)zn
with zn∈ℜ2 being the absolute position of last robot. On the other hand the desired position from the first n-1 robots (4), can be expressed in a matrix form as
(25)[z1*⋮zn-1*]=(Δn-1-1(Δn-1-L1)⊗I2)[z1⋮zn-1]-(Δn-1-1M⊗I2)zn+(Δn-1-1⊗I2)c1,
where Δn-1=diag[g1,…,gn-1]. Substituting (24) in (25) we obtain
(26)[z1*⋮zn-1*]=(L1⊗I2)-1c1-(L1-1M⊗I2)zn=[z1⋮zn-1]
this means that the formation is preserved even though there are an infinite number of equilibria. We can interpret (24) as the position of the first n-1 robots relative to the position of the n robot.


## 4. Numerical Simulations

Figure2 shows a numerical simulation of the closed-loop system (3)–(9) for n=5,  T=0.1, and K=0.1. The interrobot communication is a mixed FG given in the Figure 2(a) where the adjacent subsets Ni, the desired positions and the vectors of relative position that establish a rhombus shape centered in R5 are illustrated. The initial position of the robots is z1(0)=[6,-1], z2(0)=[4,4], z3(0)=[0,3], z4(0)=[0,0], and z5(0)=[0,6]. Note that robots converge to the desired formation in the plane (Figure 2(b)). It is proved by the convergence of the formation errors showing in the Figure 2(c).Formation control of a mixed FG.
(a)
Formation Graph
(b)
Trajectories of the robots
(c)
Error coordinatesTo compare the previous simulation, Figure3 shows a different simulation with a different FG but with the same n=5,  T=0.1,  K=0.1  and the initial positions of the robots as of the previous simulation. Now, the communication links of the FG of the Figure 3(a) have changed to the case of an undirected or bidirectional cyclic pursuit. Observe that the robots converge to the formation and the formation errors converge to zero too, but performing different trajectories in the plane. So, the addition or subtraction of communication links to the same formation pattern modifies the dynamics of the agents and the convergence time of the formation errors.Formation control of an undirected cyclic pursuit FG.
(a)
Formation Graph
(b)
Trajectories of the robots
(c)
Error coordinatesNote that the performance of the control actions improves as the sampling periodT decreases to small values, due to the Euler’s discretization and the control strategy based on attractive potential functions with a simple constant gain. Note that the value T=0.1 used in both simulations ensures a well performance, that is more than enough for real implementation in robots.


## 5. Conclusions

This paper deals the case of discrete-time formation control for the case of omnidirectional robots. The main contribution is a formal proof about the global convergence of the robots to the desired formation pattern, showing the stability of multiple equilibrium points when the formation errors converge to zero. The approach is based on the coordination of biological entities were the motion coordination is defined by the local communication between robots and the available information is the position of some robots measures by local sensors. In further researches, the collision avoidance, the flocking behavior with group path-following, and the extension for the case of nonlinear models, like unicycle-type robots, will be addressed.



---

*Source: 746713-2013-02-26.xml*