IEEE Paper, 18 Apr 05

From Murray Wiki
Revision as of 16:57, 18 April 2005 by Murray (talk | contribs) (→‎Agenda for next meeting)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Present: Fax, Murray, Olfati-Saber


  • Discuss papers we came up with last time
  • Add new papers to the list that we think we should read
    • Include papers from ACC 2005
  • Discuss common themes
  • Set agenda for next meeting

Discussion of papers


This is the paper that Ali cites and so everyone cites it. In the physics community, this is cited correctly. In controls, this paper is often credited with things that aren't really in the paper. Deals with alignment in flocking behavior.

Position of agenda matters (who are your neighbors). Uses a completely nonlinear protocol as his alignment rule. Agents move with velocity v in the plane. Looks at effects of change in density and change in noise.

Some further work on crowd control (published in Nature) using similar tools (purely computational).

Takeaways for our paper

  • Early example of a protocol
  • Focused on alignment (common problem)

Related papers

  • Jadbabaie
  • Blondel et al (incorrect citation?)


Currently at Notre Dame. Alex cited this in this thesis. Was done in the context of nonholonomic vehicle. What graphs would you set up to enable meaningful controls. Started with acyclic graphs. Paper was never accepted into a journal.

Takeaways for our paper

  • Might not cite this; Action (Demetri): look for follow up work (if any). If we can't find something more recent that is significant, probably won't include
  • Effects of dynamics (especially nonlinear)

Related papers

  • Naomi Leonard
  • Action (Richard): look for other papers on this topic


Would be nice to see more work in the area of performance and observer structure. Various follow-on results have not yet been followed up. Getting information from different sources (potentially at different times).

Action (Alex): look at papers that cite this one (google scholar) and make sure we understand what further results have been achieved.

Takeaways for our work

  • Starting point for Laplacian

Related papers

  • Double graph model by Zhipu?


We can use this paper for the basic definitions that we want to include. This paper also highlights the role of balanced graphs (and more generally the difference between directed and undirected). For balanced graphs, we can solve average consensus for any linear function.

Takeaways for our work

  • Basic problem definition
  • Initial setting for switching, time delays
  • Role of balanced graphs?

Related papers

  • Switching: Jadbabaie, Moreau, Beard
  • Time delays: Moreau (recent)


One of the early papers to look at switching and the stability properties in this case. We might be able to say this in a bit more consistent terminology with current work. First order linear process (so it doesn't quite apply to Viscek's model). Relies on undirected tools, makes use of tools from matrix theory.

Takeaways for our paper:

  • Eventual connectivity is sufficient for consensus in presence of switching and time delays
  • Different approach from Moreau

Related papers:

  • Moreau


Extends the results of Jadbabie:

  • Admits nonlinear update laws
  • Makes use of properties of stochastic matrices to get very short proof (for undirected graphs)
  • Proof for directed graphs is harder

Basic point is to define a disagreement metric in a Laplacian-like framework, you can show that disagreement metric contracts. Then look for conditions underwhich is reaches zero. Doesn't care about directed versus undirected. Shows that almost everything converges; we should point out that speed of convergence is not discussed.

Takeaways for our paper:

  • Shows how to extend most of the things we have done to nonlinear case, with switching

Related papers

  • Jadbabaie

Olfati-Saber, Flocking

Takeaways for our paper:

Related papers:


Results didn't see that useful. Might be bad presentation of a good set of ideas. Should reference in some of the flocking work that Reza did. Looks at state dependent connectivity, which is different than many other papers.

Takeaways for our paper:

  • May not play a major role in our paper, but reference in flocking

Related papers:

Xiao and Boyd

Showed how to select the weights (under fixed topology) to optimize lambda_2. Solution is highly centralized. Solves the average consensus problem. Only gives a slight improvement over sparse connectivity.

Takeaways for our paper:

  • Initial results for optimizing lambda_2

Related papers:

  • Olfati-Saber, small world

Ren and Beard

Can be viewed as an extension of Ali's results where weighted graphs are used. Requires spanning trees.

Takeaways for our paper:

  • Probably won't site

Related papers:


Probably too orthogonal to what we want to talk about. Focuses on rigidity, potential functions, etc.

Takeaways for our paper:

  • Mentioned in passing

Related papers:


Average consensus algorithm can be used to calculate two central sums in a Kalman filter in a sensor network. Basically a way to do distributed sensor fusion

Takeaways for our paper:

  • Example of how consensus can be used for other types of distributed compution

Related papers:

  • Should at least relate to Beard Kalman filter work


This paper shows how previous results can be used to study this problem. Difference between this paper and Ali's paper:

  • Tsitsiklis uses complete graphs (not distributed computation)
  • Want to put this into context in terms of the type of information flow

Takeaways for our paper:

  • Use the book as an example of how results in distributed computation can be applied

Related papers:

  • Bruck?
  • Hatano and Mesbahi - uses super martingales

New papers to consider

  • Distribute computation (Action (RMM): read Bertsekes and Tsitsiklis book)
  • Technical results in graph theory in Moreau's paper. Reza has gone through this a bit. Related to this: we should include as part of a review of relevant results in graph theory.
  • Bullo results on consensus (w/ Cortes). Claim consensus papers are special case. Action (Reza): summarize this for the group next time

Common themes

"Protocols" for concensus and cooperation

  • Distributed setting (doesn't require complete connectivity)

Laplacians and Graph Theory

  • Introduce Laplacian by average consensus example
  • Role of lamba_2 in performance
  • Try to summarize some of the main threads of results that are relevant to consensus and cooperation

From Consensus to Cooperation: Closing the Loop

  • Possible way to organize sections of the paper

Continuous versus Discrete

  • Are they solving the same problem?
  • Discussion of time delays and what they mean/imply

Switching and Time-Delays

  • Large collection of results looking at the impact of switching and different sorts of time delays

Role of Consensus in Distributed Estimation

  • Tie to distributed Kalman Filtering
  • Might also talk about role of observers/predictors here

Relationship to Distributed Computation

  • How do the results we cite here relate to older results in distributed computation
  • One difference is that we close the loop around the consensus
  • Another difference is the way switching topologies are handled
  • Action (Richard): We need to do a careful review of the work in that field


  • Current results are mainly tied to lambda_2

Open Problems

  • Performance

Agenda for next meeting

Original plan:

  • List tools
  • Open problems
  • Outline paper

Revised plan:

  • Focus on outlining the paper at the section, subsection level
  • Action items out of next meeting will be to come back with outline of contents for each subsection
  • Action (Demetri): put links up to papers