Distributed Coordination and Consensus algorithms with boundary: from flocking and synchronization to geographic routing in adhoc networks

Dr. Ali Jadbabaie, University of Pennsylvania

In this talk we provide a unified view of several distributed coordination  and consensus algorithms which have appeared in various disciplines such as distributed systems, statistical physics, biology, computer graphics,  robotics, and control theory over the past 2 decades. These algorithms have  been proposed as a mechanism for demonstrating emergence of a global  collective behavior (such as social aggregation in animals, schooling,  flocking and synchronization) using purely local interactions. Utilizing  tools from spectral graph theory and control and dynamical systems theory,  we provide an analysis of these algorithms. Furthermore, we show that by  imposing fixed boundary conditions (e.g., designating a leader in a swarm) ,  one can obtain algorithms for a wide range of applications, from  leader-follower swarms to synchronization in oscillator networks, and from  shortest path routing to geographic routing without location information.  Finally, we describe a one-parameter family of distributed consensus  algorithms with boundary conditions, which at one extreme, recovers the  well-known Bellman-Ford Algorithm for shortest-path routing, and at the  other, results in a routing scheme based on diffusion, and mean-first passage times. Connections between these algorithms and harmonic functions, electric networks, and discrete Dirichlet problems are also discussed.  

                                                                                      
BIOGRAPHY                                                                              
                                                                                      
Ali Jadbabaie got his BS from Sharif University of Technology in Tehran, Iran in 1995. He received a Masters degree in Electrical and Computer Engineering from the University of New Mexico, Albuquerque in 1997 and a Ph.D. degree in Control and Dynamical Systems from California Institute of  Technology (Caltech) in June 2001. From July 2001-July 2002 he was a  postdoctoral associate at the department of Electrical Engineering at Yale  University. Since July 2002 he has been an assistant professor in the department of Electrical and Systems Engineering at the University of Pennsylvania. He is a recipient of an NSF Career Award, an ONR Young Investigator award, and the George S. Axelby Outstanding Paper Award of the IEEE Control Systems Society.