# A New Algorithm for Distributed Control Problem with Shortest-Distance Constraints

Authors: Yu Zhou; Wenfeng Zheng; Zhixi Shen
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

This paper investigates the distributed shortest-distance problem of multiagent systems where agents satisfy the same continuous-time dynamics. The objective of multiagent systems is to find a common point for all agents to minimize the sum of the distances from each agent to its corresponding convex region. A distributed consensus algorithm is proposed based on local information. A sufficient condition also is given to guarantee the consensus. The simulation example shows that the distributed shortest-distance consensus algorithm is effective for our theoretical results.


---

## Body

## 1. Introduction

In recent years, distributed control of multiagent systems has attracted considerable attention within control community because of its important applications including distributed task allocation, distributed motion planning, and distributed alignment problems [1–8]. For example, in [1], Nedić et al. introduced a distributed projected consensus algorithm for discrete-time multiagent systems where each agent lies in a closed convex set and gave corresponding convergence analysis on dynamically changing balanced graphs. Founded on the work of [1], [5, 6] considered the networks of fixed and switching topologies. In [7], Matei and Baras proposed the consensus-based multiagent distributed subgradient method to solve the collaborative optimization of an objective function. In [8], Lin and Ren studied the constrained consensus problem in unbalanced networks with communication delays.In this paper, we will study the distributed control problem with shortest-distance constraints. Distributed shortest-distance consensus problem is one important problem in the distributed control of multiagent systems. The objective of multiagent systems is to find a common point for all agents to minimize the sum of squared distances from each agent to its corresponding convex region. For example, [9] investigated consensus and optimization problems for directed networks of agents with external disturbances. Currently, most of the existing related works concentrate on the case where the intersection set of all convex regions is nonempty [1, 10–12]. A projected consensus algorithm was proposed to solve the constrained consensus problem where each agent is restricted in its own convex set [1]. Reference [10] proposed a class of subgradient-based methods, where some estimate of the optimal solution can be delivered over the network through randomized iteration. In [11], Johansson et al. introduced a subgradient method based on consensus steps to solve coupled optimization problems with fixed undirected topology. In [12], Lou et al. proposed an approximately projected consensus algorithm to achieve the intersection of convex sets. In [13], Wang and Elia proposed a distributed continuous-time algorithm to achieve optimization by controlling the sum of subgradients of convex functions. However, the case where the intersection set of all convex regions is empty is rarely concerned. In [14], the case of no intersection is studied, but the sign functions are used to make the system nonsmooth. Reference [15] investigated a distributed optimization problem and proposed a subgradient projection algorithm for multiagent systems subject to nonidentical constraints and communication delays under local communication. Comparing with [1, 12], this paper focuses on the constrained problem where all convex regions have no intersection and the undirected graph is connected. Following the work of [14], we investigate the distributed control problem with shortest-distance constraints and propose a new distributed shortest-distance consensus algorithm. By a Lyapunov approach, a sufficient condition is given to make all agents converge to the optimal set of the shortest-distance problem. Finally, we provide a simulation example to show that the distributed shortest-distance consensus algorithm is effective for our theoretical results. Different from [14], we calculate the difference and the Euclidean norm between two different agents and use the ratio of them to replace the sign function. It makes the system smoother than that of [14].


## 2. Preliminaries

### 2.1. Graph Theory

LetG(V,E,A) be an undirected graph of node n, where V={s1,…,sn} is the set of nodes and ε⊆V×V is the set of edges. The node indexes belong to a finite index set I={1,2,3,…,n}. An edge of G is denoted by eij=(si,sj), where node si can obtain information from node sj. The weighted adjacency matrix is denoted by A={aij}, where aii=0,aij=aji>0 if and only if (si,sj)∈ε and si≠sj. Since the graph is considered undirected, the adjacency matrix A is a symmetric nonnegative matrix. The set of neighbors of node si is denoted by Ni={sj∈V;(si,sj)∈E}. The in-degree and out-degree of node si are defined as din(si)=∑j=1naji and do(si)=∑j=1naij. Then, the Laplacian corresponding to the undirected graph is defined as L=[lij], where lij=do(si) and lij=-aij,i≠j. Obviously, the Laplacian of any undirected graph is symmetric. A path is a sequence of ordered edges of the form (si1,si2),(si2,si3),…, where ij∈I and sij∈V. If there is a path from every node to every other node, the graph is said to be connected [16].Lemma 1 (see [16]).
If the undirected graphG is connected, then the Laplacian L of G has the following properties:(1)
Zero is an eigenvalue ofL, and 1n is the corresponding eigenvector; that is, L1n=0.(2)
The restn-1 eigenvalues are all positive and real.


### 2.2. Convex Theory

Letdist⁡x¯,X be the standard Euclidean distance of a vector x¯ from a set X; that is, (1)dist⁡x¯,X=infx∈Xx¯-x. The projection of vector x on a closed convex set X is denoted by the projection term SX(x); that is,(2)SXx=arg⁡minx¯∈X⁡x-x¯,where x denotes the standard Euclidean norm, x=xTx [17].Lemma 2 (see [1]).
Suppose thatX is a nonempty closed convex set in Rm, the squared distance function ρ(x)=(1/2)(x-SX(x))2, x∈Rm is continuously differentiable in x. Then, we have (3)SXx-y2≤x-y2-SXx-x2,SXx-SXz≤x-z,SXx-SXzTx-z≥SXx-SXz2,d12x-SXx2=SXx-xdx, where x,z∈Rm, y∈X, and d(·) is differential operator.Lemma 3 (see [18]).
LaSalle’s invariance principle: consider an autonomous system of the formx˙=f(x), with f(x) continuous, and let V(x):Rn→R be a scalar function with continuous first partial derivatives on Ωl=x∈Rn:Vx≤l. Assume that(1)
for somel>0 the set Ωl defined by V(x)≤l is bounded.(2)
V˙(x)≤0 for all x in Ωl.
IfΩl extends to the whole space Rn, then global asymptotic stability can be established. Define R={x∈Rn:V˙(x)=0}. Then if R contains no other trajectories other than x=0, then the origin 0 is asymptotically stable. In summary,(1)
ifV(x) is a negative semidefinite in a region Ω, where V(x)≤0, then a solution starting in the interior of Ω remains there;(2)
if, in addition, no solutions (except the equilibriumx=0) remain in R (the subset of Ω where V˙(x)=0), then all solutions starting in the interior of Ω will converge to the equilibrium.Lemma 4 (see [19]).
Letf0(χ):Rm→R be a differentiable convex function. f0(χ) is minimized if and only if df0(χ)/dχ=0.


## 2.1. Graph Theory

LetG(V,E,A) be an undirected graph of node n, where V={s1,…,sn} is the set of nodes and ε⊆V×V is the set of edges. The node indexes belong to a finite index set I={1,2,3,…,n}. An edge of G is denoted by eij=(si,sj), where node si can obtain information from node sj. The weighted adjacency matrix is denoted by A={aij}, where aii=0,aij=aji>0 if and only if (si,sj)∈ε and si≠sj. Since the graph is considered undirected, the adjacency matrix A is a symmetric nonnegative matrix. The set of neighbors of node si is denoted by Ni={sj∈V;(si,sj)∈E}. The in-degree and out-degree of node si are defined as din(si)=∑j=1naji and do(si)=∑j=1naij. Then, the Laplacian corresponding to the undirected graph is defined as L=[lij], where lij=do(si) and lij=-aij,i≠j. Obviously, the Laplacian of any undirected graph is symmetric. A path is a sequence of ordered edges of the form (si1,si2),(si2,si3),…, where ij∈I and sij∈V. If there is a path from every node to every other node, the graph is said to be connected [16].Lemma 1 (see [16]).
If the undirected graphG is connected, then the Laplacian L of G has the following properties:(1)
Zero is an eigenvalue ofL, and 1n is the corresponding eigenvector; that is, L1n=0.(2)
The restn-1 eigenvalues are all positive and real.


## 2.2. Convex Theory

Letdist⁡x¯,X be the standard Euclidean distance of a vector x¯ from a set X; that is, (1)dist⁡x¯,X=infx∈Xx¯-x. The projection of vector x on a closed convex set X is denoted by the projection term SX(x); that is,(2)SXx=arg⁡minx¯∈X⁡x-x¯,where x denotes the standard Euclidean norm, x=xTx [17].Lemma 2 (see [1]).
Suppose thatX is a nonempty closed convex set in Rm, the squared distance function ρ(x)=(1/2)(x-SX(x))2, x∈Rm is continuously differentiable in x. Then, we have (3)SXx-y2≤x-y2-SXx-x2,SXx-SXz≤x-z,SXx-SXzTx-z≥SXx-SXz2,d12x-SXx2=SXx-xdx, where x,z∈Rm, y∈X, and d(·) is differential operator.Lemma 3 (see [18]).
LaSalle’s invariance principle: consider an autonomous system of the formx˙=f(x), with f(x) continuous, and let V(x):Rn→R be a scalar function with continuous first partial derivatives on Ωl=x∈Rn:Vx≤l. Assume that(1)
for somel>0 the set Ωl defined by V(x)≤l is bounded.(2)
V˙(x)≤0 for all x in Ωl.
IfΩl extends to the whole space Rn, then global asymptotic stability can be established. Define R={x∈Rn:V˙(x)=0}. Then if R contains no other trajectories other than x=0, then the origin 0 is asymptotically stable. In summary,(1)
ifV(x) is a negative semidefinite in a region Ω, where V(x)≤0, then a solution starting in the interior of Ω remains there;(2)
if, in addition, no solutions (except the equilibriumx=0) remain in R (the subset of Ω where V˙(x)=0), then all solutions starting in the interior of Ω will converge to the equilibrium.Lemma 4 (see [19]).
Letf0(χ):Rm→R be a differentiable convex function. f0(χ) is minimized if and only if df0(χ)/dχ=0.


## 3. Problem Description and Results

### 3.1. Problem Description

The multiagent system under consideration containsn agents, where each agent corresponds to a certain bounded convex set, denoted by Xi. Our objective is to design a distributed consensus algorithm for the system to make all agents able to reach consensus and minimize the sum of squared distances between the global point and the convex sets.(4)12∑i=1nx-SXix2,Xi∈Rm.We assume that the closed setXi∈Rm is nonempty, Rm is the set of all dimensional real column vectors, and ⋂i=1nXi=∅. In other words, we need to find a global optimal point that minimizes the sum of squared distances form i to its all closed convex sets. Each agent is assumed to have the following continuous-time dynamics: (5)x˙it=uit,i∈I,where xi∈Rm is the state of the ith agent, I is the index set {1,2,…,n}, and ui(t) is the control input of the ith agent.


### 3.2. A New Distributed Shortest-Distance Consensus Algorithm

We propose a new distributed shortest-distance consensus algorithm as the following form:(6)uit=α∑j∈Nitxjt-xitxjt-xit+SXixit-xit,i∈I,where α>0 is a positive integer and I is the index set {1,2,…,n} and xj(t)≠xi(t). Ni(t) is neighbor set of agent i at time t, and xi(t) is the state of agent i at the time t. If xj(t)=xi(t), we define ∑j∈Ni(t)((xjt-xit)/xj(t)-xi(t))=0.Assumption 5.
Suppose that, fori, the closed set Xi is compact set; that is,(7)x≤g,g>0,where i∈I and x∈Xi.Assumption 6.
Suppose that the setXi∈Rm is nonempty and the set Xi satisfies(8)⋂i=1nXi=∅.Theorem 7.
Suppose that the undirected graphG is connected. Under Assumption 6, if α>2ng, using Lemmas 2 and 3 for (4), the convex function (4) is minimized as t→+∞.Proof.
Define a Lyapunov function(9)Vat=12∑i=1nxit-1n∑j=1nxjt2.
According tod(1/2)xi-xj2/dx=(xi-xj)T(x˙i-x˙j) and (5)-(6), we get(10)V˙at=∑i=1nxit-1n∑j=1nxjtTx˙it=∑i=1nxit-1n∑j=1nxjtTα∑j∈Nitxjt-xitxjt-xit+SXixit-xit.
Suppose that the undirected graphG is connected. It follows that(11)V˙at=∑i=1n∑j∈Nitα2xit-xjtTxjt-xitxjt-xit+∑i=1nxit-1n∑j=1nxjtTSXixit-∑i=1nxit-1n∑j=1nxjtTxit-1n∑j=1nxjt=∑i=1n∑j∈Nitα2xit-xjtTxjt-xitxjt-xit+∑i=1nxit-1n∑j=1nxjtTSXixit-∑i=1nxit-1n∑j=1nxjt2.
Letxim(t)-xjm(t) denote the maximum distance between agent i and agent j at time t; that is,(12)ximt-xjmt=maxi,j∈I⁡xit-xjt.From im,jm∈I, we get(13)xit-1n∑j=1nxjt≤ximt-xjmt.
Since undirected graphG(V,E,A) is connected, the distance between node vim and node vjm is less than the sum of squared distances between agent i and its neighbors; that is,(14)ximt-xjmt≤∑i=1n∑j∈Nitxit-xjt,(15)xit-xjt≤-xit-xjtTxjt-xitxjt-xit.
Combining (13)–(15), we have(16)xit-1n∑j=1nxjt≤ximt-xjmt≤-∑i=1n∑j∈Nitxit-xjtTxjt-xitxjt-xit.
Ifα>2ng, substituting (7) and (11), we have(17)V˙at=-∑i=1n∑j∈Nitα2xit-xjt+∑i=1nxit-1n∑j=1nxjtTSXixit-∑i=1nxit-1n∑j=1nxjt2≤-∑i=1n∑j∈Nitxit-xjtα2-ng-∑i=1nxit-1n∑j=1nxjt2≤-∑i=1n∑j∈Nitxit-xjtα2-ng.
From (14), (18)∑i=1n∑j∈Nitxit-xjt≥ximt-xjmt≥2Vatn. Thus (19)V˙at≤-2Vatn. That is, V˙a(t)/Va(t)≤-2/n. And integrating both sides of this inequality from 0 to t, we have (20)Va+∞-Va0≤-2nt. Since Va(t)≥0, it is clear that Va(t) vanishes to zero in finite time and hence all agents reach a consensus in finite time. Thus, there is a constant T>0 such that Va(t)=0 and xi(t)=xj(t) for all i,j∈I and all t>T. Thus (21)limt→+∞⁡xjt-xit=0.
Consider the average value of all agents, denoted byx∗(t)=(1/n)∑i=1nxi(t), for t>T. It is clear that(22)x˙∗t=1n∑k=1nSXkx∗t-x∗tfor all t>T. Consider the Lyapunov function(23)Vbt=12∑i=1nx∗t-SXix∗t2≤0 for t>T.
CalculatingV˙b(t), for all t>T, we have(24)V˙bt=∑i=1nx∗t-SXix∗tT1n∑k=1nSXkx∗t-x∗t=-1n∑i=1nx∗t-SXix∗t2. Since each Xi is bounded and V˙b(t)≤0, thus Vb(t) is bounded. And from Lemma 2, (1/n)∑k=1nSXk(x∗(t))-x∗(t) is continuous. Note that Vb(t)≤0; then from Lemma 3, we have x∗(t) converges to the set {V˙b(t)=0} as t→+∞. V˙b(t)=0 implies that (1/n)∑k=1nSXk(x∗(t))-x∗(t)=0. Thus(25)limt→+∞1n∑k=1nSXkx∗t-x∗t=0. Note that (d/dt)(1/2)∑i=1n(x∗(t)-SXi(x∗(t)))2=x∗(t)-(1/n)∑k=1nSXk(x∗(t)). From Lemma 4 and (25), the convex function (4) is minimized as t→+∞.Remark 8.
In Theorem7, we only discuss the undirected connected graphs and our future work will be directed to the general jointly connected graphs.


## 3.1. Problem Description

The multiagent system under consideration containsn agents, where each agent corresponds to a certain bounded convex set, denoted by Xi. Our objective is to design a distributed consensus algorithm for the system to make all agents able to reach consensus and minimize the sum of squared distances between the global point and the convex sets.(4)12∑i=1nx-SXix2,Xi∈Rm.We assume that the closed setXi∈Rm is nonempty, Rm is the set of all dimensional real column vectors, and ⋂i=1nXi=∅. In other words, we need to find a global optimal point that minimizes the sum of squared distances form i to its all closed convex sets. Each agent is assumed to have the following continuous-time dynamics: (5)x˙it=uit,i∈I,where xi∈Rm is the state of the ith agent, I is the index set {1,2,…,n}, and ui(t) is the control input of the ith agent.


## 3.2. A New Distributed Shortest-Distance Consensus Algorithm

We propose a new distributed shortest-distance consensus algorithm as the following form:(6)uit=α∑j∈Nitxjt-xitxjt-xit+SXixit-xit,i∈I,where α>0 is a positive integer and I is the index set {1,2,…,n} and xj(t)≠xi(t). Ni(t) is neighbor set of agent i at time t, and xi(t) is the state of agent i at the time t. If xj(t)=xi(t), we define ∑j∈Ni(t)((xjt-xit)/xj(t)-xi(t))=0.Assumption 5.
Suppose that, fori, the closed set Xi is compact set; that is,(7)x≤g,g>0,where i∈I and x∈Xi.Assumption 6.
Suppose that the setXi∈Rm is nonempty and the set Xi satisfies(8)⋂i=1nXi=∅.Theorem 7.
Suppose that the undirected graphG is connected. Under Assumption 6, if α>2ng, using Lemmas 2 and 3 for (4), the convex function (4) is minimized as t→+∞.Proof.
Define a Lyapunov function(9)Vat=12∑i=1nxit-1n∑j=1nxjt2.
According tod(1/2)xi-xj2/dx=(xi-xj)T(x˙i-x˙j) and (5)-(6), we get(10)V˙at=∑i=1nxit-1n∑j=1nxjtTx˙it=∑i=1nxit-1n∑j=1nxjtTα∑j∈Nitxjt-xitxjt-xit+SXixit-xit.
Suppose that the undirected graphG is connected. It follows that(11)V˙at=∑i=1n∑j∈Nitα2xit-xjtTxjt-xitxjt-xit+∑i=1nxit-1n∑j=1nxjtTSXixit-∑i=1nxit-1n∑j=1nxjtTxit-1n∑j=1nxjt=∑i=1n∑j∈Nitα2xit-xjtTxjt-xitxjt-xit+∑i=1nxit-1n∑j=1nxjtTSXixit-∑i=1nxit-1n∑j=1nxjt2.
Letxim(t)-xjm(t) denote the maximum distance between agent i and agent j at time t; that is,(12)ximt-xjmt=maxi,j∈I⁡xit-xjt.From im,jm∈I, we get(13)xit-1n∑j=1nxjt≤ximt-xjmt.
Since undirected graphG(V,E,A) is connected, the distance between node vim and node vjm is less than the sum of squared distances between agent i and its neighbors; that is,(14)ximt-xjmt≤∑i=1n∑j∈Nitxit-xjt,(15)xit-xjt≤-xit-xjtTxjt-xitxjt-xit.
Combining (13)–(15), we have(16)xit-1n∑j=1nxjt≤ximt-xjmt≤-∑i=1n∑j∈Nitxit-xjtTxjt-xitxjt-xit.
Ifα>2ng, substituting (7) and (11), we have(17)V˙at=-∑i=1n∑j∈Nitα2xit-xjt+∑i=1nxit-1n∑j=1nxjtTSXixit-∑i=1nxit-1n∑j=1nxjt2≤-∑i=1n∑j∈Nitxit-xjtα2-ng-∑i=1nxit-1n∑j=1nxjt2≤-∑i=1n∑j∈Nitxit-xjtα2-ng.
From (14), (18)∑i=1n∑j∈Nitxit-xjt≥ximt-xjmt≥2Vatn. Thus (19)V˙at≤-2Vatn. That is, V˙a(t)/Va(t)≤-2/n. And integrating both sides of this inequality from 0 to t, we have (20)Va+∞-Va0≤-2nt. Since Va(t)≥0, it is clear that Va(t) vanishes to zero in finite time and hence all agents reach a consensus in finite time. Thus, there is a constant T>0 such that Va(t)=0 and xi(t)=xj(t) for all i,j∈I and all t>T. Thus (21)limt→+∞⁡xjt-xit=0.
Consider the average value of all agents, denoted byx∗(t)=(1/n)∑i=1nxi(t), for t>T. It is clear that(22)x˙∗t=1n∑k=1nSXkx∗t-x∗tfor all t>T. Consider the Lyapunov function(23)Vbt=12∑i=1nx∗t-SXix∗t2≤0 for t>T.
CalculatingV˙b(t), for all t>T, we have(24)V˙bt=∑i=1nx∗t-SXix∗tT1n∑k=1nSXkx∗t-x∗t=-1n∑i=1nx∗t-SXix∗t2. Since each Xi is bounded and V˙b(t)≤0, thus Vb(t) is bounded. And from Lemma 2, (1/n)∑k=1nSXk(x∗(t))-x∗(t) is continuous. Note that Vb(t)≤0; then from Lemma 3, we have x∗(t) converges to the set {V˙b(t)=0} as t→+∞. V˙b(t)=0 implies that (1/n)∑k=1nSXk(x∗(t))-x∗(t)=0. Thus(25)limt→+∞1n∑k=1nSXkx∗t-x∗t=0. Note that (d/dt)(1/2)∑i=1n(x∗(t)-SXi(x∗(t)))2=x∗(t)-(1/n)∑k=1nSXk(x∗(t)). From Lemma 4 and (25), the convex function (4) is minimized as t→+∞.Remark 8.
In Theorem7, we only discuss the undirected connected graphs and our future work will be directed to the general jointly connected graphs.


## 4. Simulation

In this section, we provide a numerical example to show the effectiveness of Theorem7. We use the fixed topology which is showed in Figure 1. And let α=10, X1={(x11,x12)T∈R2∣(x11,x12)T≤5}, X2={(x21,x22)T∈R2∣(x21,x22)T-(-10,30)T≤2.5}, X3={(x31,x32)T∈R2∣(x31,x32)T-(20,10)T ≤ 2.5}, and X4={(x41,x42)T∈R2∣(x41,x42)T-(30,30)T≤2.5}. Figure 2 shows the simulation results.Figure 1
Topology.Figure 2
State trajectories of agents 1, 2, 3, and 4.Figures3 and 4 show the position trajectories, respectively. It is obvious that all agents reach a consensus point that is the optimal point of the function (4). This is consistent with Theorem 7.Figure 3
Position-time (a).Figure 4
Position-time (b).


## 5. Conclusion

In the paper, we purpose a new distributed shortest-distance algorithm for multiagent systems. The objective of multiagent systems is to find a common point for all agents to minimize the sum of squared distances from each agent to its corresponding convex regions. A sufficient condition also is given to guarantee the consensus. And the simulation example is given to show that the distributed shortest-distance consensus algorithm is effective for our theoretical results.



---

*Source: 1604824-2016-12-28.xml*