Consensus optimization on manifolds

consensus algorithms; decentralized control; swarm control; synchronization; differential geometry; mean on manifolds; special orthogonal group; Grassmann manifold

Abstract :

[en] The present paper considers distributed consensus algorithms that involve N agents evolving on a connected compact homogeneous manifold. The agents track no external reference and communicate their relative state according to a communication graph. The consensus problem is formulated in terms of the extrema of a cost function. This leads to eﬃcient gradient algorithms to synchronize (i.e., maximizing the consensus) or balance (i.e., minimizing the consensus) the agents; a convenient adaptation of the gradient algorithms is used when the communication graph is directed and time-varying. The cost function is linked to a speciﬁc centroid deﬁnition on manifolds, introduced here as the induced arithmetic mean, that is easily computable in closed form and may be of independent interest for a number of manifolds. The special orthogonal group SO(n) and the Grassmann manifold Grass(p,n) are treated as original examples. A link is also drawn with the many existing results on the circle.

Disciplines :

Engineering, computing & technology: Multidisciplinary, general & others

Author, co-author :

Sarlette, Alain ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation

Sepulchre, Rodolphe ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation

Language :

English

Title :

Consensus optimization on manifolds

Publication date :

January 2009

Journal title :

SIAM Journal on Control and Optimization

ISSN :

0363-0129

eISSN :

1095-7138

Publisher :

Society for Industrial & Applied Mathematics, Philadelphia, United States - Pennsylvania

Special issue title :

Control and Optimization in Cooperative Networks

Volume :

Issue :

Pages :

56-76

Peer reviewed :

Peer Reviewed verified by ORBi

Funders :

F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]

Available on ORBi :

since 24 March 2009

Statistics

Number of views

150 (9 by ULiège)

Number of downloads

287 (1 by ULiège)

More statistics

Scopus citations^®

176

Scopus citations^®
without self-citations

166

OpenCitations

147

Bibliography

P. A. ABSIL, R. MAHONY, AND R. SEPULCHRE, Riemannian geometry of Grassmann manifolds with a view on algorithmic computation, Acta Appl. Math., 80 (2004), pp. 199-220.
P. A. ABSIL, R. MAHONY, AND R. SEPULCHRE, Optimization Algorithms on Matrix Manifolds, Princeton University Press, Princeton, NJ, 2007.
A. BARG, Extremal problems of coding theory, in Coding Theory and Cryptography, H. Niederreiter, ed., Notes of Lectures at the Institute for Mathematical Sciences of the University of Singapore, World Scientific, Singapore, 2002, pp. 1-48.
A. BARG AND D.Y. NOGIN, Bounds on packings of spheres in the Grassmann manifold, IEEE Trans. Inform. Theory, 48 (2002), pp. 2450-2454.
A. K. BONDHUS, K. Y. PETTERSEN, AND J. T. GRAVDAHL, Leader/follower synchronization of satellite attitude without angular velocity measurements, in Proceedings of the 44th IEEE Conference on Decision and Control, IEEE Press, Piscataway, NJ, 2005, pp. 7270-7277.
R. W. BROCKETT, Dynamical systems that sort lists, diagonalize matrices, and solve linear programming problems, Linear Algebra Appl., 146 (1991), pp. 79-91.
M. BROOKES, Matrix Reference Manual, Imperial College London, London, UK, 2005. Available online at http://www.ee.ie.ac.uk/hp/staff/ dmb/matrix/intro.html.
F. BULLO AND R. MURRAY (ADVISOR), Nonlinear Control of Mechanical Systems: A Riemannian Geometry Approach, Ph.D. thesis, CalTech, Pasadena, CA, 1998.
S. R. BUSS AND J. P. FILLMORE, Spherical averages and applications to spherical splines and interpolation, ACM Trans. Graphics, 20 (2001), pp. 95-126.
F. R. K. CHUNG, Spectral Graph Theory, Reg. Conf. Ser. Math. 92, AMS, Providence, RI, 1997.
J. H. CONWAY, R. H. HARDIN, AND N. J. A. SLOANE, Packing lines, planes, etc.: Packings in Grassmannian spaces, Exper. Math., 5 (1996), pp. 139-159.
J. CORTES, S. MARTINEZ, AND F. BULLO, Coordinated deployment of mobile sensing networks with limited-range interactions, in Proceedings of the 43rd IEEE Conference on Decision and Control, IEEE Press, Piscataway, NJ, 2004, pp. 1944-1949.
T. D. DOWNS, Orientation statistics, Biometrika, 59 (1972), pp. 665-676.
A. EDELMAN, T. A. ARIAS, AND S. T. SMITH, The geometry of algorithms with orthogonality constraints, SIAM J. Matrix Anal. Appl., 20 (1998), pp. 303-353.
G. A. GALPERIN, A concept of the mass center of a system of material points in the constant curvature spaces, Comm. Math. Phys., 154 (1993), pp. 63-84.
D. GROISSER, Newton's method, zeroes of vector fields, and the Riemannian center of mass, Adv. Appl. Math., 33 (2004), pp. 95-135.
P. GRUBER AND F. J. THEIS, Grassmann clustering, in Proceedings of the 14th European Signal Processing Conference, Florence, Italy, 2006.
U. HELMKE AND J. B. MOORE, Optimization and Dynamical Systems, Springer-Verlag, London, 1994.
J. J. HOPFIELD, Neural networks and physical systems with emergent collective computational capabilities, Proc. Nat. Acad. Sci., 79 (1982), pp. 2554-2558.
K. HUEPER AND J. MANTON, The Karcher mean of points on SO (n), Talk presented at Cesame (UCL, Belgium), 2004.
M. HURLEY, Chain recurrence, semiflows, and gradients, J. Dynam. Differential Equations, 7 (1995), pp. 437-456.
A. JADBABAIE, J. LIN, AND A. S. MORSE, Coordination of groups of mobile autonomous agents using nearest neighbor rules, IEEE Trans. Automat. Control, 48 (2003), pp. 988-1001.
E. JUSTH AND P. KRISHNAPRASAD, A Simple Control Law for UAV Formation Flying, Tech. report TR 2002-38, ISR, University of Maryland, College Park, MD, 2002.
H. KARCHER, Riemannian center of mass and mollifier smoothing, Comm. Pure Appl. Math., 30 (1977), pp. 509-541.
T. R. KROGSTAD AND J. T. GRAVDAHL, Coordinated attitude control of satellites in formation, in Group Coordination and Cooperative Control, Lecture Notes in Control and Inform. Sci. 336, Springer-Verlag, Berlin, 2006, pp. 153-170.
Y. KURAMOTO, Self-entertainment of population of coupled nonlinear oscillators, in Proceedings of the International Symposium on Mathematical Problems in Theoretical Physics, Lecture Notes in Phys. 39, Springer-Verlag, Berlin, 1975, pp. 420-422.
J. R. LAWTON AND R. W. BEARD, Synchronized multiple spacecraft rotations, Automatica, 38 (2002), pp. 1359-1364.
N. E. LEONARD, D. PALEY, F. LEKIEN, R. SEPULCHRE, D. FRANTANTONI, AND R. DAVIS, Collective motion, sensor networks and ocean sampling, Proc. IEEE, 95 (2007), pp. 48-74.
A. MACHADO AND I. SALAVESSA, Grassmannian manifolds as subsets of Euclidean spaces, Res. Notes in Math., 131 (1985), pp. 85-102.
K. MISCHAIKOW, H. SMITH, AND H. R. THIEME, Asymptotically autonomous semi-flows, chain recurrence and Lyapunov functions, Trans. AMS, 347 (1995), pp. 1669-1685.
M. MOAKHER, Means and averaging in the group of rotations:, SIAM J. Matrix Anal. Appl., 24 (2002), pp. 1-16.
L. MOREAU, Stability of continuous-time distributed consensus algorithms, in Proceedings of the 43rd IEEE Conference on Decision and Control, IEEE Press, Piscataway, NJ, 2004, pp. 3998-4003.
L. MOREAU, Stability of multi-agent systems with time-dependent communication links, IEEE Trans. Automat. Control, 50 (2005), pp. 169-182.
S. NAIR AND N. E. LEONARD, Stabilization of a coordinated network of rotating rigid bodies, in Proceedings of the 43rd IEEE Conference on Decision and Control, IEEE Press, Piscataway, NJ, 2004, pp. 4690-4695.
R. OLFATI-SABER AND R. M. MURRAY, Consensus problems in networks of agents with switching topology and time-delays, IEEE Trans. Automat. Control, 49 (2004), pp. 1520-1533.
X. PENNEC, Probabilities and Statistics on Riemannian Manifolds: A Geometric Approach, Research report 5093, INRIA, Le Chesnay, France, 2004.
A. SARLETTE, R. SEPULCHRE, AND N. E. LEONARD, Discrete-time synchronization on the N-torus, in Proceedings of the 17th Annual International Symposium on Mathematical Theory of Networks and Systems, Kyoto, Japan, 2006, pp. 2408-2414.
A. SARLETTE, R. SEPULCHRE, AND N. E. LEONARD, Cooperative attitude synchronization in satellite swarms: A consensus approach, in Proceedings of the 17th IFAC Symposium on Automatic Control in Aerospace, Toulouse, France, D. Alazard, ed., CD-Rom, 2007.
L. SCARDOVI, A. SARLETTE, AND R. SEPULCHRE, Synchronization and balancing on the N-torus, Systems Control Lett., 56 (2007), pp. 335-341.
L. SCARDOVI AND R. SEPULCHRE, Collective optimization over average quantities, in Proceedings of the 45th IEEE Conference on Decision and Control, IEEE Press, Piscataway, NJ, 2006, pp. 3369-3374.
R. SEPULCHRE, D. PALEY, AND N. E. LEONARD, Group coordination and cooperative control of steered particles in the plane, in Group Coordination and Cooperative Control, Lecture Notes in Control and Inform. Sci. 336, Springer-Berlin, Verlag, 2006, pp. 217-232.
R. SEPULCHRE, D. PALEY, AND N. E. LEONARD, Stabilization of planar collective motion with all-to-all communication, IEEE Trans. Automat. Control, 52 (2007), pp. 811-824.
R. SEPULCHRE, D. PALEY, AND N. E. LEONARD, Stabilization of planar collective motion with limited communication, IEEE Trans. Automat. Control, 53 (2008), pp. 706-719.
S. H. STROGATZ, From Kuramoto to Crawford: Exploring the onset of synchronization in populations of coupled nonlinear oscillators, Phys. D, 143 (2000), pp. 1-20.
S. H. STROGATZ, Sync: The Emerging Science of Spontaneous Order, Hyperion, New York, 2003.
J. N. TSITSIKLIS AND D. P. BERTSEKAS, Distributed asynchronous optimal routing in data networks, IEEE Trans. Automat. Control, 31 (1986), pp. 325-332.
J. N. TSITSIKLIS, D. P. BERTSEKAS, AND M. ATHANS, Distributed asynchronous deterministic and stochastic gradient optimization algorithms, IEEE Trans. Automat. Control, 31 (1986), pp. 803-812.
T. VICSEK, A. CZIRÓK, E. BEN- JACOB, I. COHEN, AND O. SHOCHET, Novel type of phase transition in a system of self-driven particles, Phys. Rev. Lett., 75 (1995), pp. 1226-1229.
J. C. WILLEMS, Lyapunov functions for diagonally dominant systems, Automatica, 12 (1976), pp. 519-523.