**Syllabus**

**Textbook**

M. Mesbahi and M. Egerstedt. Graph Theoretic Methods in Multiagent Networks, Princeton University Press, 2010.

**Book website** (with links to supplementary information)

https://sites.google.com/site/mesbahiegerstedt/

**Moodle** (with links to the lecture videos/discussion board/chat/annoucements)

http://moodle.extn.washington.edu/course/view.php?id=1997

**Schedule**

**3/27:** (chapters 1 and 3) Introduction, networked systems, applications, rendezvous/consensus problem; **slides**

**3/29:** (chapters 2 and 3) matrices associated with graphs, spectrum of the Laplacian; **slides**;
homework assignment (Due 4/5): 2.1, 2.2, 2.3, 2.5, 2.8, 3.1, 3.4, 3.6

**4/3:** (chapters 2 and 3) convergence of the consensus protocol, Laplacian spectrum for complete and cycle graphs, implications; **slides**

**4/5:** (chapter 3) consensus on directed graphs; **slides**;
homework assignment (Due 4/12): 2.4, 2.6, 2.7, 3.3, 3.5, 3.7, 3.12

**4/10:** (chapters 2 and 3): Laplacian eigenvalues and graph structure; **slides**

**4/12:** (chapter 4) switching graphs; **slides**

**4/17:** (chapter 6) formation control; **slides**

**4/19:** (chapter 6) formation control; **slides**;
homework assignment (Due 4/26): 4.3, 4.5, 4.7, 4.9, 6.5

**4/24:** (chapters 4,6): unicycle formation, passivity; **slides**

**4/26:** (chapter 4): more on passivity, projects, intro. to distributed estimation;
homework assignment (Due 5/3): 6.8, 6.9, simulate figure 6.8, 8.1

**5/1:** (chapter 8): distributed estimation+finish unicyle model **slides**

**5/3:** (chapter 7): mobile robotics **slides**; homework assignment (Due 5/10): 1) 6.4
2) implement the distributed protocol (7.14) for various values of delta. Consider
the scenario shown in Figure 7.1 for the tradition agreement protocol and explore
how (7.14) leads to a distinct behavior from that shown in this figure.
3) implement the distributed protocol (7.20) for various values of Delta and d_{ij};
once your code works for set of d_ij's and \Delta, see how the algorithm behaves as you choose different
values for d_ij's
4) 7.1
5) 7.3
6) 7.11

**5/4:** project white paper due at 5:00 pm- email instructor/TA

**5/8:** (chapter 7): mobile robotics **slides**

**5/10:** (chapter 9): network synthesis **slides**; homework assignment (Due 5/17): 7.2, 7.5, 7.6, 7.9, 7.12, 11.7, 11.9

**5/15:** (chapter 11): network synthesis **slides**

**5/17:** (chapter 11): social networks and games **slides**

**5/22:** (chapter 10): chip firing **slides**

**5/24:** (chapter 10): controlling networks **slides**

**5/29:** (chapter 10): controlling networks **slides**; review

**5/29 Presentations:** (1) Nick Burgan-Illig (9:35-9:50am): Target Search and Capture for Multi-Agent Systems;
(2) Saghar Hosseini (9:50-10:05am) : Power-Aware Rendezvous Problem in Mobile Sensors;
Mehran: Continues the lecture on network controllability/review/intro to control/estimation on random graphs

**5/31 Presentations:** (1) Nathan Banka (9:30-9:45 am) : An Array of Cilia as a Networked Dynamic System;
(2) Josh Maximoff (9:45-10:00am): Relative-State Gain Control for Formation Motion;
(3) David Swartzendruber Jr. (10:00-10:15am): Distributed phased array antenna control
(4) Hossein Ali Safavi-Naeini, Mohammad Haghighipanah, & Yue Yang (10:15-10:30am): Localized Load-Balancing in Connected Networks;
Few last words/course wrap up/evaluations: (10:30-10:45am)

**6/4:** project reports are due for those who have NOT presented in class (email the report to the instructor by 5:00 pm)

**6/7:** project reports are due for those who have presented in class (email the report to the instructor by 5:00 pm)

Presentations/Reports

The report format:

I) abstract, 2) problem setup and assumptions, 3) basic results, simulations, 4) critique, 5) references.

The paper for single-member groups should be no more than 5 pages (single space, 11 pts fonts, two-column) except the simulation/code.
Depending on the size of the group, the page limitation can be relaxed; please check with the instructor.

References

**Graph Theory**

R. Diestel, Graph Theory, (3rd Edition), Springer, 2005

B. Bollobas, Modern Graph Theory, Springer, 1998

Graph Theory resources

Graph Theory Tutorials

mathworld

mathworld-graph theory

mathworld- directed graphs

mathworld- random graphs

**Networks and Dynamics**

National Research Council report on Network Science

M. E. J. Newman, Random graphs as models of networks

M. E. J. Newman, The structure and function of complex networks

S. H. Strogatz, Exploring complex networks

D. J. Watts and S. H. Strogatz, Collective dynamics of 'small-world' networks

L. Lovasz: Random walks on graphs: a survey

J. N. Tsitsiklis, Problems in Decentralized Decision Making and Computation, Ph.D. Thesis, Department of EECS, MIT, November 1984.

**Graphs, Systems, and Control**

Special issue on Networked Control Systems,Transactions on Automatic Control, vol. 49, no. 9, September 2004

Y. Hatano and M. Mesbahi, Agreement over random networks

A. Jadbabaie, J. Lin, and A. S. Morse, Coordination of groups of mobile autonomous agents using nearest neighbor rules

M. Mesbahi, On state-dependent dynamic graphs and their controllability properties

R. Olfati-Saber and R. M. Murray, Consensus and Cooperation in NetworkedMulti-Agent Systems

L. Moreau, Stability of multiagent systems with time-dependent communication links, IEEE Transactions on Automatic Control, (50) 2:169 - 182, 2005.

W. Ren, R. W. Beard, and E. Atkins, Information consensus in multi-vehicle cooperative control: collective group behavior through local interaction, IEEE Control Systems Magazine, 2007.

W. Ren and R. Beard, Distributed Consensus in Multivehicle Cooperative Control: Theory and Applications.

A. Muhammad and M. Egerstedt. Connectivity graphs as models of local interactions. Journal of Applied Mathematics and Computation, 168 (1): 243-269, 2005.

F. Bullo, J. Cortes, and S. Martinez. Distributed Algorithms for Robotic Networks

**Formations and Flocking**

Formation Flying at JPL

M. Mesbahi and F. Y. Hadaegh. Formation flying of multiple spacecraft via graphs, matrix inequalities, and switching , AIAA Journal of Guidance, Control, and Dynamics, (24) 2: 369-377, 2001.

R. Olfati-Saber. Flocking for multi-agent dynamic systems: algorithms and theory, IEEE Transactions on Automatic Control, (51) 3:401 - 420, 2006.

H. G. Tanner, A. Jadbabaie, and G. J. Pappas, Flocking in fixed and switching networks, IEEE Transactions on Automatic Control.

F. Cucker and S. Smale, The mathematics of emergence

F. Cucker and S. Smale, Emergent behavior in flocks

**Language Evolution**

F. Cucker, S. Smale, and D-X. Zhou, Modeling language evolution

**Chemical Reaction Networks**

M. Feinberg, Lectures on Chemical Reaction Networks

**Network Synthesis**

J. Sun, S. Boyd, L. Xiao, and P. Diaconis, The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem, SIAM Review, 48(4):681-699, Nov. 2006.

A. Ghosh and S. Boyd, Growing well-connected graphs, IEEE Conference on Decision and Control, December 2006.

Y. Kim and M. Mesbahi. On maximizing the second smallest eigenvalue of a state-dependent graph Laplacian, IEEE Transactions on Automatic Control, (51) 1: 116-120, 2006.

**Search Engines**

How Google Finds Your Needle in the Web's Haystack.

D. J. Higham, Google PageRank as mean playing time for pinball on the reverse web, Applied Mathematics Letters, (18) 12: 359-1362, 2005.

**Social Networks**
More on this soon.