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

Credits: The course is worth 7.5 credits. Grading is based on P/F system.

ACCESS Course category: Specialized Course

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

Lecturers

Dimos Dimarogonas

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

· develop a research project and give presentations 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 (March 30, 2011, Q11, 10.00-12.00): Introduction, motivation, applications, graph theory, logistics, etc.

Reading material for lecture 1:

1. Lecture note

2. Pages 1520-1524 from 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.

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

Lecture 2 (April 6, 2011, Q11, 15.00-17.00): Consensus: static, dynamic, directed graphs.

Reading material for lecture 2:

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 3 (April 13, 2011, Q13, 15.00-17.00): Communication constraints: connectivity, connectivity maintenance, sampling, quantization.

Reading material for lecture 3:

1. P. 693-698 from 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. P. 695-697 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.

3. Dimos V. Dimarogonas and Karl H. Johansson, “Event-Triggered Control for Multi-Agent Systems”, 48th IEEE Conference on Decision and Control, Shanghai, China, pp. 7131-7136, December 2009.

Lecture 4 (April 20, 2011, Q24, 15.00-17.00): Formation control 1: position based formations, formation infeasibility, flocking.

Reading material for lecture 4:

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 5 (April 27, 2011, Q17, 10.00-12.00): Containment control, network controllability, leader-follower architectures.

Reading material for lecture 5:

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 6 (May 4, 2011, Q22, 15.00-17.00): Formation control 2: distance based formations, rigidity, persistence.

Reading material for lecture 6:

1. Laura Krick, Mireille E. Broucke, and Bruce A. Francis, “Stabilization of Infinitesimally Rigid Formations of Multi-Robot Networks”, IEEE CDC 2008.

2. Florian Dorfler, and Bruce Francis, “Geometric Analysis of the Formation Problem for Autonomous Robots”, IEEE Transactions on Automatic Control, pp. 2379-2384, VOL. 55, NO. 10, OCTOBER 2010.

3. BRIAN D. O. ANDERSON , IMAN SHAMES, GUOQIANG MAO, AND BARIS FIDAN, “FORMAL THEORY OF NOISY SENSOR NETWORK LOCALIZATION”, SIAM J. DISCRETE MATH., Vol. 24, No. 2, pp. 684–698.

Lecture 7 (May 11, 2011, Q24, 15.00-17.00): Swarming-sensor networks: sensing constraints, aggregation, dispersion.

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 (May 18, 2011, Q24, 15.00-17.00): Collision avoidance: potential fields, navigation functions. Dynamics: nonholonomic, rigid body dynamics.

Reading material for lecture 8:

1. D.V. Dimarogonas, S.G. Loizou, K. J. Kyriakopoulos and M.M. Zavlanos, "A Feedback Stabilization and Collision Avoidance Scheme for Multiple Independent Non-point Agents ", Automatica, Vol. 42, No. 2, pp. 229-243, February 2006.

2. Dimos V. Dimarogonas and Kostas J. Kyriakopoulos, "On the Rendezvous Problem for Multiple Nonholonomic Agents", IEEE Transactions on Automatic Control, Vol. 52, No. 5, pp. 916-922, May 2007.

3. Dimos V. Dimarogonas, Panagiotis Tsiotras and Kostas J. Kyriakopoulos, “Leader-Follower Cooperative Attitude Control of Multiple Rigid Bodies”, Systems and Control Letters, 2009, Vol. 58, No. 6, pp. 429-435, June 2009.

Lecture 9 (May 25, 2011, Q24, 15.00-17.00): Guest lecture on vehicle routing algorithms by Dr. Ketan Savla.

Reading material for lecture 9:

1. D. J. Bertsimas and G. van Ryzin, "Stochastic and Dynamic Vehicle Routing in the Euclidean Plane with Multiple Capacitated Vehicles", Operations Research, Vo. 41, No. 1, Jan-Feb 1993, pages 60-76

2. F. Bullo, E. Frazzoli, M. Pavone, K. Savla and S. L. Smith, "Dynamic Vehicle Routing for Robotic Systems", Proceedings of the IEEE, Vol. 99, No. 8, 2011, In press.

Lecture 10 (June 1, 2011, Q11, 10.00-12.00): Coverage control, game theoretic approach.

Reading material for lecture 10:

1. 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.

2. J. R. Marden, G. Arslan, and J. S. Shamma, “Cooperative control and potential games,” IEEE Trans. Systems, Man, and Cybernetics; Part B: Cybernetics, no. 39, pp. 1393–1407, 2009.

3. H.-B. Durr, M. S. Stanković and K. H. Johansson, Distributed Positioning of Autonomous Mobile Sensors with Application to Coverage Control, American Control Conference 2011.

Lecture 11(June 8, 2011, Q15, 15.00-17.00): Distributed estimation.

Reading material for lecture 11:

1. Usman A. Khan and José M. F. Moura, “Distributing the Kalman Filters for Large-Scale Systems,” IEEE Transactions on Signal Processing, 56:10, pp. 4919-4935, October 2008.

2. R. Olfati-Saber. "Distributed Kalman Filtering for Sensor Networks," Proc. of the 46th IEEE Conference on Decision and Control, Dec. 2007.

3. M Deghat, I Shames, B D O Anderson, J M F Moura, “Distributed Localization Via Barycentric Coordinates: Finite-Time Convergence”, To appear in IFAC WC’11.

Lecture 12 (June 15, 2011, Q24, 15.00-17.00): At the research frontier.

Course disposition

Lectures, research project(s), relevant list of papers/book chapters some.

Requirements for final grade

Passing Grade based on homeworks and research projects.

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).

Acknowledgements

We would like to thank professors Emilio Frazzoli and Magnus Egerstedt for their valuable input for the preparation of this course.