Graduate/MS Course on Networked and Multi-Agent Control Systems, FEL3330/EL2910

Credits: The course is worth 7.5 credits. Grading is based on P/F system for PhD students and on A-F system for MS students.

 

Course category: PhD Course FEL3330, MS Course EL2910.

 

Course Responsible: Dimos Dimarogonas, dimos@kth.se, http://www.s3.kth.se/~dimos/

 

Lecturers

Dimos Dimarogonas

Guodong Shi

 

Abstract

 

Recent technological advances in computational and communication resources have facilitated the control of multi-agent systems. Such systems are comprised of a large number of entities (“agents”) that aim at achieving a global task. Distributed control designs are preferable, since they provide among others scalability, reduce of computational load and fault compensation. Moreover they are natural realizations of the limitations in communication, networking, and sensing capabilities which are inherent in multi-agent systems.

Multi-agent systems have a broad range of modern applications such as multi-robot and multi-vehicle coordination, control of sensor networks, air traffic management systems, unmanned vehicles, energy systems and logistics, just to name a few. This course will review the fundamental tools, problems and state of the art in the modeling and control of networked multi-agent systems. Moreover it will indicate possible future research directions.

 

Keywords

 

Multi-agent systems, networked systems, distributed control and estimation, distributed control under limited communications and sensing, formation control, sensor networks

 

Learning outcomes

 

After the course, the student should be able to:

·        know the essential theoretical tools to cope with Networked and Multi-Agent Systems

·        know the established problems and results in the area

·        apply the theoretical tools to problems in the area

·        contribute to the research frontier in the area

 

Course main content

 

A preliminary structure and exact dates are given below. Reading material for each course will be updated as the course evolves.

 

Lecture 1:  Introduction, motivation, applications, logistics, etc.  (May 6, Q2, 10-12 am)

Reading material for lecture 1:

  1. Chapter 1 from Graph Theoretic Methods in Multi-Agent Networks, by M. Mesbahi and M. Egerstedt, Princeton University Press, 2010 (publicly available)

 

Lecture 2:  Graphs and Matrices    (May 8, Q33, 3-5 pm, Guodong Shi) 

Reading material for lecture 2:

  1. Lecture Notes

 

Lecture 3: Consensus protocols (static graphs)  (May 13, Q2, 10-12 am)

Reading material for lecture 3:

1.       R. Olfati-Saber and R. M. Murray. "Consensus Problems in Networks of Agents with Switching Topology and Time-Delays," IEEE Trans. on Automatic Control, vol. 49(9), Sep., 2004.

2.       Wei Ren and Randal W. Beard, "Consensus seeking in multiagent systems under dynamically changing interaction topologies," IEEE Transactions on Automatic Control, Vol. 50, No. 5, May 2005,  pp. 655-661.

 

Lecture 4: Communication constraints: connectivity, connectivity maintenance, sampling, quantization.   (May 16, Q2, 3-5 pm)

Reading material for lecture 4:

1.       Meng Ji and Magnus Egerstedt, “Distributed Coordination Control of Multiagent Systems while Preserving Connectedness” IEEE Transactions on Robotics, Vol. 23, No. 4, pp. 693-703, Aug. 2007.

2.       D.V. Dimarogonas and K.H. Johansson, “Stability analysis for multi-agent systems using the incidence matrix: quantized communication and formation control”, Automatica,  46: 4, pp. 695-700, April 2010.

3.       Georg Seyboth, Dimos V. Dimarogonas and Karl H. Johansson, “Event-based Broadcasting for Multi-agent Average Consensus”, Automatica, Vol. 49, No. 1, pp. 245-252, January 2013.

 

Lecture 5: Formation control: position based formations, formation infeasibility, distance-based formations, flocking.    (May 20, Q2, 3-5 pm)

Reading material for lecture 5:

1.        P. 699-700 from D.V. Dimarogonas and K.H. Johansson, “Stability analysis for multi-agent systems using the incidence matrix: quantized communication and formation control”, Automatica,  46: 4, pp. 695-700, April 2010.

2.        P. 2648-2651 from D.V. Dimarogonas and K.J. Kyriakopoulos, “A connection between formation infeasibility and velocity alignment in kinematic multi-agent systems”, Automatica, Vol. 44, No. 10, pp. 2648-2654, October 2008.

3.        Herbert G. Tanner, Ali Jadbabaie and George J. Pappas, “Stable Flocking of Mobile Agents, Part I: Fixed Topology”  IEEE Conference on Decision and Control, 2003, pp. 2010-2015.

 

Lecture 6:  Containment control, network controllability, leader-follower architectures.    (May 23, Q2, 3-5 pm)

Reading material for lecture 6:

1.       Herbert G. Tanner, On the Controllability of Nearest Neighbor Interconnections.  IEEE Conference on Decision and Control, 2003, pp. 2010-2015.

2.       G. Ferrari-Trecate, M. Egerstedt, A. Buffa, and M. Ji. Laplacian Sheep: A Hybrid, Stop-Go Policy for Leader-Based Containment Control. Hybrid Systems: Computation and Control, Springer-Verlag, pp. 212-226, 2006.

3.       D.V. Dimarogonas, T. Gustavi, M. Egerstedt, and X. Hu. On the Number of Leaders Needed to Ensure Network Connectivity. IEEE Conference on Decision and Control, Cancun, Mexico, Dec. 2008.

 

Lecture 7:  Swarming-sensor networks.   (May 27, Q2, 3-5 pm)

Reading material for lecture 7:

1.       Dimos V. Dimarogonas and Kostas J. Kyriakopoulos, “Inverse Agreement Protocols with Application to Distributed Multi-agent Dispersion”, IEEE Transactions on Automatic Control, Vol. 54, No. 3, pp. 657-663, March 2009.

2.       Dimos V. Dimarogonas and Kostas J. Kyriakopoulos, "Connectedness Preserving Distributed Swarm Aggregation for Multiple Kinematic Robots", IEEE Transactions on Robotics, Vol. 24, No. 5, pp. 1213-1223, October 2008.

 

Lecture 8:  Cooperative searching, area coverage and pursuit of evaders  (May 30, Q2, 3-5 pm, guest lecture by Prof. Petter Ögren)

Reading material for lecture 8:

1.       Frank Hoffmann, Michael Kaufmann and Klaus Kriegel, ”The Art Gallery Theorem For Polygons With Holes”, 32nd Annual Symposium on  Foundations of Computer Science, 1991.

2.       Johan Thunberg, Petter Ögren, “A Mixed Integer Linear Programming approach to pursuit evasion problems with optional connectivity constraints”, Autonomous Robots, November 2011, Volume 31, Issue 4, pp 333-343.

3.       Volkan Isler, Sampath Kannan, and Sanjeev Khanna, ”Randomized Pursuit–Evasion in a Polygonal Environment”, IEEE Trans. On Robotics, VOL. 21, NO. 5, OCTOBER 2005.

4.       J. Cortés, S. Martínez, T. Karatas, F. Bullo, Coverage control for mobile sensing networks, IEEE Transactions on Robotics and Automation, 20 (2), 243-255, 2004. 

 

Lecture 9:  Consensus over Time-varying Graphs: Discrete and Continuous Models.     (June 3, Q2, 3-5 pm, Guodong Shi)

Reading material for lecture 9:

1.       L. Xiao and S. Boyd. Fast linear iterations for distributed averaging, Systems & Control Letters, vol. 53, pp. 65-78, 2004.

2.       L. Moreau. Stability of multi-agent systems with time-dependent communication links.  IEEE Trans. Automatic Control,  vol. 50, no. 2, pp.169-182, 2005.

Lecture  10: Consensus over Random Graphs and Gossip Algorithms.   (June 5, Q2, 3-5 pm, Guodong Shi)

Reading material for lecture 10:

1.       S. Boyd, A. Ghosh, B. Prabhakar and D. Shah. Randomized gossip algorithms, IEEE Trans. Information Theory, vol. 52, no. 6, pp. 2508-2530, 2006.

2.       S. Kar and J.M.F. Moura, Sensor networks with random links: topology design for distributed consensus, IEEE Transactions on Signal Processing, Vol.56, No.7, pp. 3315-3326, July 2008.

Lecture 11: Distributed Optimization.     (June 10, Q2, 3-5 pm, Guodong Shi)

Reading material for lecture 11:

1.     J. Tsitsiklis, D. Bertsekas, and M. Athans, Distributed asynchronous deterministic and stochastic gradient optimization algorithms, IEEE Trans. Autom. Control, vol. 31, no. 9, pp. 803-812, 1986.

2.     A. Nedich and A. Ozdaglar, Distributed subgradient methods for multi-agent optimization, IEEE Trans. Autom. Control, vol. 54, no. 1, pp. 48-61, 2009.

3.     A. Nedich, A. Ozdaglar and P. A. Parrilo, Constrained consensus and optimization in multi-agent networks, IEEE Trans. Autom. Control, vol. 55, no. 4, pp. 922-938, 2010.

 

Lecture 12:  At the research frontier.    (June 13, Q2, 3-5 pm)

Course disposition

 

Lectures, relevant list of papers/book chapters.

 

Prerequisites

 

Basic courses on Automatic Control, Linear Algebra. At least one advance course in automatic control will be of help, but not compulsory.

 

Requirements for final grade

 

Passing Grade based on homework and final take-home exam.

 

For MS students: 3 homework on the P/F scale and take-home exam on the A,B,C,D,E,F,Fx scale.

 

The difficulty of the homework and the final exam will be adjusted accordingly for MS and PhD students.

 

Course literature

 

The course will be primarily based on the lectures (slides and blackboard), as well as suggested reading for the topic of the lecture. Good supplementary textbooks are

 

Algebraic Graph Theory, by C. Godsil and G. Royle, Springer, 2001.

 

Graph Theoretic Methods in Multi-Agent Networks, by M. Mesbahi and M. Egerstedt, Princeton University Press, 2010.

 

Distributed Control of Robotic Networks, by F. Bullo, J. Cortes, and S. Martinez, Princeton, 2009.

 

Distributed Consensus in Multi-vehicle Cooperative Control, by Wei Ren, Randal W. Beard, Communications and Control Engineering Series, Springer-Verlag, London, 2008 (ISBN: 978-1-84800-014-8).