Elsevier

Automatica

Volume 68, June 2016, Pages 209-215
Automatica

Brief paper
Distributed constrained optimal consensus of multi-agent systems

https://doi.org/10.1016/j.automatica.2016.01.055Get rights and content

Abstract

We study a distributed optimal consensus problem of continuous-time multi-agent systems with a common state set constraint. Each agent is assigned with an individual cost function which is coercive and convex. A distributed control protocol is to be designed to guarantee a consensus, and in the meanwhile reach the minimizer of the aggregate cost functions within the constraint set. Three terms are included in the protocol: local averaging, local projection, and local subgradient with a diminishing but persistent gain. It is shown that the constrained optimal consensus can be achieved under a uniformly jointly connected communication network with bounded time-varying edge weights.

Introduction

As a basic problem in distributed cooperative control for multi-agent systems, consensus has gained much attention from researchers in recent years. The objective of distributed consensus is to reach an agreement of a certain variable of common interest by local information exchange. Many algorithms have been proposed and found widespread applications in coordination, rendezvous, flocking, source localization, etc. (Chai et al., 2014, Jadbabaie et al., 2003, Lin et al., 2003, Olfati-Saber, 2006).

In many practical problems, consensus with constraints are to be considered. The constraints include state constraint (Sun, Jin Ong, & White, 2013), motion constraint of maximum speed and acceleration (Lin et al., 2003), and network constraint to stay connected (Zavlanos & Pappas, 2008). By decomposition and incremental subgradient methods, Johansson, Speranzon, Johansson, and Johansson (2008) dealt with the consensus problem subject to convex input constraints and linear state constraints. With model predictive control of one-step horizon, Franceschelli, Egerstedt, Giua, and Mahulea (2009) were able to drive a network of agents to their centroid while staying connected and satisfying the motion constraint. Another focus is on constraint of the final consensus value. Using projection, Shi, Johansson, and Hong (2013) computed the consensus point within the non-empty intersection of different convex sets. A similar problem was addressed in Lee and Mesbahi (2011) via logarithmic barrier functions.

On the other hand, the consensus problem becomes a distributed optimization problem when the consensus value is required to minimize the sum of individual convex functions. Many works are based on subgradient method. Nedić and Ozdaglar (2009) obtained an approximate optimal solution with a common constant step size about the local subgradient. A projected subgradient method was proposed in Nedic, Ozdaglar, and Parrilo (2010) to deal with a set constraint, where the subgradient step is firstly taken on the local average for an intermediate estimate, and then the estimate is projected onto the common constraint for an update of the state. It was later extended to the dual problem with inequality and equality constraints in Yuan, Xu, and Zhao (2011) and Zhu and Martinez (2012). Note that all the above works are in discrete-time.

As for continuous-time case, fewer results have been obtained. Conditions to guarantee the convergence of distributed unconstrained convex optimization for strongly connected graphs were examined in Shi, Proutiere, and Johansson (2012). By including a quadratic penalty in the Lagrangian problem, Wang and Elia, 2010, Wang and Elia, 2011 applied saddle-point dynamics to reach the unconstrained minimizer of the sum of differential cost functions under a fixed undirected topology, which was extended later to the case of non-smooth convex functions (Gharesifard & Cortes, 2014). Compared with the discrete-time case, a continuous-time formulation enables to employ more techniques and arguably provide more insight due to its independence of particular realization. Still, there is much to be explored in applying distributed optimizing algorithms to continuous-time systems.

In this paper, we study a consensus problem considering both constraint and optimization: the distributed constrained optimal consensus for continuous-time multi-agent systems with a common convex set constraint. A motivational example comes from the constrained rendezvous of unmanned aerial vehicles (UAVs) within a prescribed safety area, when the choice of the rendezvous location depends on minimizing the aggregate distance from the starting points to the final location. Each node is assumed to be a continuous integrator system, and assigned with a local coercive convex cost function. A distributed control input for each agent is to be designed to attain a consensus value minimizing the sum of local functions over the constraint set. To this end, three terms are incorporated into the control input: a local averaging term to guarantee the asymptotic consensus, a projection term to make the state values approach the constraint set, and a subgradient term with a diminishing but persistent gain to drive the consensus state to the constrained minimum. Due to the non-uniqueness of subgradient, the algorithm is modeled as a differential inclusion, and the solving of the constrained optimal consensus problem relies on analyzing the limit set of its solution with non-smooth techniques.

The contributions of this paper are as follows. Compared with the discrete-time work (Nedic et al., 2010), we modify the projection term such that the state is to approach the constraint set rather than to be directly projected onto it. We also relax the condition about the diminishing scaling on subgradient without the extra requirement of being square-integrable. Besides, the bounded subgradient assumption can be completely removed under the mild assumption of coercive cost functions. And when compared with other continuous-time works (Shi et al., 2012), we are able to deal with more general non-smooth cost functions.

The rest of the paper is organized as follows. Some preliminaries are recalled in Section  2. The problem formulation is stated in Section  3, with the main result presented. The complete convergence analysis is conducted in Section  4. Numerical examples and concluding remarks are respectively provided in Sections  5 Simulation, 6 Conclusion.

Some notations and abbreviations are used throughout this paper. R and R0 respectively denote the real and nonnegative real numbers. 1n is an n dimensional vector of ones and J=1n1n1n. x,y and |xy| are standard inner product and the corresponding distance respectively for x,yRn. [M]i,j denotes the (i,j)-th entry of MRm×n and M its transpose, while M=sup|x|0|Mx|/|x| for a square matrix M. XY is the Kronecker product of X and Y. a is the smallest integer not less than a. i denotes a summation for all possible index i, which similarly applies to maxi. The terms “upper semi-continuous”, “absolutely continuous” and “almost everywhere” are abbreviated as u.s.c., a.c. and a.e., respectively.

Section snippets

Preliminaries

Some preliminaries, as well as main lemmas used in the analysis, are reviewed in this section.

Problem statement and main result

Consider n agents of continuous-time dynamics, with each agent i assuming a state value xiRm and a local function fi(xi). For the first order dynamics ẋi(t)=ui(t),i=1,,n, we shall design the control input ui in a distributed way to guarantee consensus in the constraint set X, and meanwhile minimize the total cost as a sum of fi’s. In summary, the problem of distributed constrained optimal consensus is equivalent to the following: minifi(xi),s.t.  x1==xn,xiX. Moreover, assume that

  • A1:

    X is

Convergence analysis

It is clear from (8) that three different kinds of ‘forces’, consisting of consensus, optimization (subgradient) and set projection, are applied to the state value of each node. The convergence analysis is challenging with these forces jointly in effect. However, the time-varying gain α(t) creates an imbalance among the forces, and allows us to first establish the set convergence and consensus, and finally reach the constrained optimization. To be more specific, once the globally bounded

Simulation

In this section, we illustrate our results by a numerical example mentioned in Section  3, i.e. the calculation of the constrained geometric median. Consider 4 agents with initial positions x1(0)=[00], x2(0)=[21], x3(0)=[33], x4(0)=[14]. To speed up the convergence, we choose the communication graph as a ring connecting 4 agents with 0–1 edge weights. Obviously, Gσ is uniformly jointly connected and the edge weights satisfy Assumption A4. The cost function for each agent is defined as fi(xi

Conclusion

In this paper we considered the distributed constrained optimal consensus problem for continuous-time multi-agent systems. Each agent is assigned with a local objective function and a common set constraint. The control input of each agent is comprised of three parts: local information averaging, local projection, and local subgradient. We investigated the problem under a uniformly jointly connected topology. Under a persistence condition and a standard assumption about varying edge weights, we

Acknowledgments

This research is partially funded by the Republic of Singapore National Research Foundation through a grant to the Berkeley Education Alliance for Research in Singapore (BEARS) for the Singapore-Berkeley Building Efficiency and Sustainability in the Tropics (SinBerBEST) Program, grants NRF-CRP8-2011-3 and NRF2013EWT-EIRP004-012, and National Natural Science Foundation of China (NSFC) under Grants 61120106011, 61304045, 61573220.

Zhirong Qiu received the B.Sc. and M.Sc. degrees in Applied Mathematics from Sun Yat-Sen University, Guangzhou, China in 2010 and 2012, respectively. He is currently pursuing a Ph.D. degree in the School of Electrical and Electronic Engineering at Nanyang Technological University, Singapore. His research interests include multi-agent systems and distributed optimization.

References (27)

  • B. Johansson et al.

    On decentralized negotiation of optimal consensus

    Automatica

    (2008)
  • G. Shi et al.

    Global target aggregation and state agreement of nonlinear multi-agent systems with switching topologies

    Automatica

    (2009)
  • M. Zhu et al.

    Discrete-time dynamic average consensus

    Automatica

    (2010)
  • J.R. Bunch et al.

    Direct methods for solving symmetric indefinite systems of linear equations

    SIAM Journal on Numerical Analysis

    (1971)
  • G. Chai et al.

    Consensus-based cooperative source localization of multi-agent systems with sampled range measurements

    Unmanned Systems

    (2014)
  • J.M. Danskin

    The theory of max–min, with applications

    SIAM Journal on Applied Mathematics

    (1966)
  • A.F. Filippov et al.

    Differential equations with discontinuous righthand sides: control systems, Vol. 18

    (1988)
  • M. Franceschelli et al.

    Constrained invariant motions for networked multi-agent systems

  • B. Gharesifard et al.

    Distributed continuous-time convex optimization on weight-balanced digraphs

    IEEE Transactions on Automatic Control

    (2014)
  • C.D. Godsil et al.

    Algebraic graph theory, Vol. 207

    (2001)
  • J.B. Hiriart-Urruty et al.

    Fundamentals of convex analysis

    (2001)
  • A. Jadbabaie et al.

    Coordination of groups of mobile autonomous agents using nearest neighbor rules

    IEEE Transactions on Automatic Control

    (2003)
  • V. Lakshmikantham et al.

    Differential and integral inequalities

    (1969)
  • Cited by (225)

    View all citing articles on Scopus

    Zhirong Qiu received the B.Sc. and M.Sc. degrees in Applied Mathematics from Sun Yat-Sen University, Guangzhou, China in 2010 and 2012, respectively. He is currently pursuing a Ph.D. degree in the School of Electrical and Electronic Engineering at Nanyang Technological University, Singapore. His research interests include multi-agent systems and distributed optimization.

    Shuai Liu received his B.E. and M.E. degrees in Control Theory and Engineering from Shandong University in 2004 and 2007, respectively, and his Ph.D. degree in Electrical and Electronic Engineering from Nanyang Technological University, Singapore, in 2012. Since 2011, he has been a research fellow with Berkeley education alliance for research in Singapore (BEARS). He obtained Qilu Youth Scholar from Shandong University in 2015.

    His research interests include cooperative control, optimal estimation and control, time-delay systems, optimization, fault detection and estimation.

    Lihua Xie received the B.E. and M.E. degrees in electrical engineering from Nanjing University of Science and Technology in 1983 and 1986, respectively, and the Ph.D. degree in Electrical Engineering from the University of Newcastle, Australia, in 1992. Since 1992, he has been with the School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore, where he is currently a professor and served as the Head of Division of Control and Instrumentation from July 2011 to June 2014. He held teaching appointments in the Department of Automatic Control, Nanjing University of Science and Technology from 1986 to 1989.

    Dr. Xie’s research interests include robust control and estimation, networked control systems, multi-agent networks, and unmanned systems. He has served as an Editor-in-Chief of Unmanned Systems, an editor of IET Book Series in Control and an Associate Editor of a number of journals including IEEE Transactions on Automatic Control, Automatica, IEEE Transactions on Control Systems Technology, and IEEE Transactions on Circuits and Systems-II. Dr. Xie is a Fellow of IEEE and Fellow of IFAC.

    The material in this paper was not presented at any conference. This paper was recommended for publication in revised form by Associate Editor Wei Ren under the direction of Editor Christos G. Cassandras.

    View full text