Reaching a Consensus in a Dynamically Changing Environment

Professor Steve Morse (Yale University)

DATE: 2006-04-07
TIME: 11:00:00 - 12:00:00
LOCATION: RSISE Seminar Room, ground floor, building 115, cnr. North and Daley Roads, ANU

ABSTRACT:
Current interest in cooperative control of groups of autonomous agents has led to the rapid increase in the application of graph theoretic ideas 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 illustrates this, 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 considered 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 within a closed disk of pre-specied radius centered at agent i's current position. In their paper, Vicsek et al. provided a variety of interesting simulation results which demonstrated that the nearest neighbor rule they were studying could 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 could 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 specic 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.

In this talk we will give an overview of two variants of the Vicsek problem, the first being a modified version in which integer-valued delays occur in sensing the values of headings which are available to agents. The second is a version in which each agent independently updates its heading at times determined by its own clock; in this case it is not assumed that the groups' clocks are synchronized or that the times any one agent updates its heading are evenly spaced. Using several concepts such as "analytic synchronization" and a number of key results concerned with the "composition" of directed graphs, we will explain why the conditions under which a consensus is achieved in the face of measurement delays or asynchronous decision making are essentially the same as those which are applicable in the synchronous, delay-free case.

This research was done in collaboration with M. Cao and B. D. O. Anderson

BIO:
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.

http://entity.eng.yale.edu/controls/ http://www.eng.yale.edu/faculty/vita/morse.html

MEDIA:
060407_morse.pdf
060407_morse_fish_redirect.html
060407_morse_lion_redirect.html
060407_morse_redirect.html

	Skip Navigation CECS Home \| ANU Home \| Search ANU \| HORUS \| Staff Home
	Seminars @ CECS ANU College of Engineering and Computer Science