| Speaker: | Dr. Stephen Morse, Yale University |
|---|---|
| Abstract: | Current interest in cooperative control of groups has led to the rapid increase in the application of graph theoretic ideas together with more familiar dynamical systems concepts to problems of analyzing and synthesizing a variety of desired group behaviors such as maintaining a formation, swarming, rendezvousing, or reaching a consensus. One line of research which “graphically” illustrates the combined use of these concepts is the recent theoretical work by a number of individuals which successfully explains the heading synchronization phenomenon observed in simulation by T. Vicsek and C. Reynolds more than a decade ago. Vicsek and co-authors consider a simple discrete-time model consisting of n autonomous agents or particles all moving in the plane with the same speed but with different headings. Each agent's heading is updated using a local rule based on the average of the headings of its “neighbors.” Agent i’s current neighbors are itself together with those agents which are either in or on a circle of pre-specified radius centered at agent i’s current position. In their paper, Vicsek et al. provide a variety of interesting simulation results which demonstrate that the nearest neighbor rule they are studying can cause all agents to eventually move in the same direction despite the absence of centralized coordination and despite the fact that each agent's set of nearest neighbors can change with time. Vicsek's problem is what in computer science is called a “consensus problem” or an “agreement problem.” Roughly speaking, one has a group of agents which are all trying to agree on a specific value of some quantity. Each agent initially has only limited information available. The agents then try to reach a consensus by passing what they know between them either just once or repeatedly, depending on the specific problem of interest. For the Vicsek problem, each agent always knows only its own heading and the headings of its neighbors. One feature of the Vicsek problem which sharply distinguishes it from other consensus problems is that each agent's neighbors change with time, because all agents are in motion. It has recently been explained why Vicsek's agents are able to reach a common heading. The explanation exploits ideas from gave graph theory and from the theory of non-homogeneous Markov chains. With the benefit of hindsight it is now reasonably clear that it is more the graph theory than the Markov chains which is key to this line of research. By appealing to the concept of graph composition, we side-step most issues involving products of stochastic matrices and present a variety of graph theoretic results which explain how convergence to a common heading is achieved. |
| Biography: | A. Stephen Morse was born in Mt. Vernon, New York. He received a BSEE degree from Cornell University, MS degree from the University of Arizona, and a Ph.D. degree from Purdue University. From 1967 to 1970 he was associated with the Office of Control Theory and Application {OCTA} at the NASA Electronics Research Center in Cambridge, Mass. Since 1970 he has been with Yale University where he is presently the Dudley Professor of Engineering and a Professor of Computer Science. His main interest is in system theory and he has done research in network synthesis, optimal control, multivariable control, adaptive control, urban transportation, vision-based control, hybrid and nonlinear systems, and most recently coordination and control of large grouping of mobile autonomous agents. He is a Fellow of the IEEE, a Distinguished Lecturer of the IEEE Control System Society , and a co-recipient of the Society’s 1993 and 2005 George S. Axelby Outstanding Paper Awards . He has twice received the American Automatic Control Council’s Best Paper Award. He is the 1999 recipient of the IEEE Technical Field Award for Control Systems . He is a member of the National Academy of Engineering and the Connecticut Academy of Science and Engineering . |
| Presentation On: | Friday, March 10, 2006, 11:00 a.m. in room 1115, CSIC |
| Videotape: | Morse.mov |
