ESE 635: Distributed Dynamical Systems


Department of Electrical and Systems Engineering
University of Pennsylvania
Spring 2007

:

  • Course Description:

    • This research seminar deals with tools, methods, and algorithms for analysis and design of distributed dynamical systems. The object of study in this research seminar are large collection of dynamical systems that are spatially interconnected to form a collective task or achieve a global behavior using local interactions. Over the past decade such systems have been studied in disciplines as diverse as statistical physics, computer graphics, robotics, and control theory. The purpose of this course is to build a mathematical foundation for study of such systems by exploring the interplay of control theory, distributed optimization, dynamical systems, graph theory, and algebraic topology. Basic knowledge of linear systems (ESE 500), linear algebra (Math 412 or equivalent), and optimization (ESE 504 or equivalent) and some familiarity with nonlinear systems (ESE 617 or equivalent) is required. Those without this background should consult the instructor. Assignments will consist of reading and resenting the recent literature in this area. Topic covered include distributed coordination, consensus and gossip algorithms over networks with applications to multi-vehicle systems and sensor networks, coverage problems, congestion control over the internet, effects of network topology on performance, small-world and power-law networks, power law graphs, synchronization phenomena in natural and engineered systems, and Google's page-rank algorithm. There is no text book for this course. Assignments include reading and presenting papers and presenting a final project.

  • Requirement:

    • Good knowledge of linear algebra is required. Knowledge of classical optimization theory is helpful but not required. This is a research seminar and requires a lot of independent work. We will have very few traditional lectures. Students are expected to be familiar with linear algebra, linear systems, optimization, and some basics of nonlinear dynamics and graph theory. Most importantly, students need to be able to critically read and analyze research papers across various disciplines.

  • Instructor

    • : Ali Jadbabaie , jadbabai@seas.upenn.edu
    Office hours : Wednesdays 2:00-4:00pm, 365 GRW Moore bldg
  • Lectures: Tue - Thur 3:00pm-4:#0, Towne 329

  • References

    • Graph Theory

    R. Diestel, Graph Theory (3rd Edition), Springer, 2005
    B. Bollobas, Modern Graph Theory, Springer, 1998
    R. Durrett, Random Graph Dynamics
    B. Mohar, Laplacian Spectrum of Graphs
    M. Newman, Laplacian Spectrum of graphs (PhD Thesis)
    C. Meyer, Perron Frobenius Theory of nonnegative matrices (DO NOT PRINT)
    D. Spielman, Lecture notes on spectral graph theory and its applications
    C. Meyer and A. Langville, Deeper inside PageRank (this is about how the famous PageRank algorithm works)
    Graph Theory resources
    Graph Theory Lessons
    Graph Theory Tutorials
    mathworld
    mathworld-graph theory
    mathworld- directed graphs (has a brief description for small world and scale-free networks
    mathworld- random graphs

    Networked Dynamic Systems

    Special issue of IEEE Transactions on Automatic Control
    A. Jadbabaie, J. Lin, and A. S. Morse, Coordination of groups of mobile autonomous agents using nearest neighbor rules
    M. E. J. Newman, The structure and function of complex networks
    M. E. J. Newman, Random graphs as models of networks
    R. Olfati-Saber, J.A. Fax, and R. M. Murray, Consensus and cooperation in networked, multi-agent systems

    S.P Boyd, L. Xiao, B. Phrabakar, and D. Shah, Randomized gossip algorithms

    Synchronization in Complex Networks

    S. H. Strogatz, Exploring complex networks
    D. J. Watts and S. H. Strogatz, Collective dynamics of 'small-world' networks
    S. Strogatz, From Kuramoto to Crawford: exploring the onset of synchronization in populations of coupled oscillators
    L. Pecora and M. Barahona, Synchronization of oscillators in complex networks
    M. Barahona and L. Pecora, synchronization in small world networks
    A. Jadbabaie, N. Motee and M Barahona, On stability of the Kuramoto model of coupled nonlinear oscillators
    T. Vicsek, A Czirok, E Ben-Jacob, I Cohen, and O Shoche, Novel types of phase transitions in systems of self propelled particles

    Small World Networks

    D. Watts and S. Strogatz, Collective dynamics of small-world networks
    J. Kleinberg, Small World Networks: an algorithmic perspective
    wikiNet entry of the Watts/Strogatz model
    J. Kleinberg, Navigation in a small world
    J. Kleinberg's website on The structure of informationnetworks

    Internet and Network Science

    Caltech's Netlab website on Self Similarity, powerlaws and robustness of the internet

    Chemical reaction networks

    M Feinberg and F. Horn, Dynamics of open chemical systems and the algebraic structure of the underlying chemical reaction networks
    M Feinberg, Chemical reaction network structure and the stability of complex isothermal reactors

    Consensus and agreement in social networks

    J. C. Dittmer, Consensus formation under bounded confidence
    R. Hegselman and U. Krauss, Opinion dynamics and bounded confidence models, analysis and ssimulation
    G Mckeown and N. Sheehy, Mass Media and Polarisation Processes in the Bounded Confidence Model of Opinion Dynamics

  • Other resources
    • John Doyle's website on Complex Engineering and Biological Networks
    National Research Council's report on Network Science

    Vincent Blondel's research seminar on Networks and Dynamics at MIT.
    You can use the lecture notes in your presentations.

  • Grading (tentative):
  • Tentative Schedule (please note that the order might change):

    Date Lecture Reading Contents and presenter
    January 9 Lecture 1 overview slides Introduction, course overview
    January 11 Lecture 2 more overview Course organization and topic assignment
    January 16 Lecture 3 Chapter 8 of Matrix Analysis by C. Meyer Nonnegative matrices and Perron Frobenius Theory, by Alireza Tahbaz Salehi
    January 18 Lecture 4 Dan Spielman's first 2 lectures on spectral graph theory and Survey paper by Mohar Graph Laplacians and Spectral graph theory, by Goran Lynch
    January 23 Lecture 5 survey paper by Olfati et al. , paper by Jadbabaie et al. Consensus, agreement and synchronization in networked systems, Michael Zavlanos
    January 25 Lecture 6 Xiao, Boyd and Lall, A scheme for robust distributed sensor fusion based on average consensus
    Yang, Freeman and Lynch, multiagent coordination by decentralized estimation and control    		 Distributed estimation in networked multiagent systems, by Savvas Loizou
    January 30 Lecture 7 Strogatz papers on Kuramoto model
    S. H. Strogatz, Exploring complex networks
    S. Strogatz, From Kuramoto to Crawford: exploring the onset of synchronization in populations of coupled oscillators
    		Synchronization in complex networks: The Kuramoto model, by Subhrajit
    February 1 Lecture 8 Watts and Strogatz paper on small world networks
    Kleinberg's algorithmic perspective on small world networks     		Small world networks, by Nima Moshtagh
    February 6 Lecture 9 Barabasi and Albert Emergence of scaling in random networks
    Barabasi, Albert, and Jiang, Scale-free characteristics of random networ ks     		Powerlaw networks and preferential attachment models by Jonathan Fink
    February 8 Lecture 10 Papers by Mung Chiang, and Stephen Low Congestion control and theory of dual decomposition for network utility maximization by Abubakr Muhammad (POSTPONED)
    February 13 Lecture 11 Durret's book, and survey paper by Newman Random graphs by Alireza Tahbaz Salehi
    February 15 Lecture 12 J. C. Dittmer, Consensus formation under bounded confidence
    R. Hegselman and U. Krauss, Opinion dynamics and bounded confidence models, analysis and ssimulation
    G Mckeown and N. Sheehy, Mass Media and Polarisation Processes in the Bounded Confidence Model of Opinion Dynamics     		Social networks by Bill Mather
    Fabruary 20 Lecture 13 papers by Feinberg Metabolic networks and reaction-rate equations by Mahmut Salman
    February 22 Lecture 14 Ogren, Fiorelli, and Leonard, Cooperative control of mobile sensor networks
    Tanner, Jadbabaie, and Pappas, Flocking in fixed and switching networks , full version     		Flocking and formation control by Spring Berman
    March 13 Lecture 15 C. Meyer and A. Langville, Deeper inside PageRank Inside Google's Page Rank by Goran Lynch
    March 15 Lecture 16 Rao et al., Geographic routing without location information
    A. Jadbabaie, On geographic routing without location information     		location-free geographic routing by Eric
    March 20, March 22 Lecture 18,19 L. Saul et al., Spectral methods for dimensionality reduction
    C. Burghes, Geometric methods for feature extraction and dimensionality reduction: A guided Tour     		Survey of dimensionality reduction methods in machine learning, by Throng
    March 27 Lecture 20 N. Motee and A. Jadbabaie, optimal control of Spatially Distributed Systems Distributed Optimal Control, by Nader Motee
    March 29 Lecture 21 M. Zavlanos, and G. Pappas, A dynamical systems approach to graph matching
    M. Zavlanos, and G. Pappas, Dynamic assignment in distributed motion planning with limited information     		multirobot assignment problems and graph matching by Michael Zavlanos
    April 3 Lecture 22 N. Motee and A. Jadbabaie, optimal control of Spatially Distributed Systems Distributed Optimal Control, by Nader Motee (continued from lecture 20)
    April 5 Lecture 23 J. Cortes et al., Coverage control in mobile sensing networks
    J. Cortes, S. Martinez and F. Bullo, Robust rendezvous for mobile autonomous agents via proximity graphs in arbitrary dimensions    		 Coverge and rendezvous problems in mobile sensor networks by Nima Moshtagh
    April 10 Lecture 23 R. Durrett, Random graph dynamics Mathematics of Random graphs, by Alireza Tahbaz Salehi
    April 12 Lecture 25 TBD TBD
    April 17 Lecture 26 TBD TBD
    April 19 Lecture 27 TBD TBD