Coordination of groups of mobile autonomous agents using nearest neighbor rules

Ali Jadbabaie, Yale University

In this talk, we provide a theoretical proof of convergence for a simple but plausible model, developed independently in the physics and computer graphics literature, of a set of point-mass agents moving in the plane with constant speed but variable heading. The model has been inspired by flocking behavior of birds, schooling of fish, etc. Each agents heading angle is updated as the average of the heading of itself and its nearest neighbors. Simulations (under various conditions) have indicated that the above simple rule will result in the alignment of all agents with each other, hence establishing an "ordered behavior" starting from random initial conditions. The above model has been extensively studied in the computer graphics literature as well as the statistical physics literature as an example of "emergent ordered behavior" and as a "pioneering work in artificial life", but no formal proof of the convergence result has been provided.

We will show that the above phenomenon can be analytically explained and proven using tools from control theory, graph theory, and theory of non-negative matrices and Markov chains. It is shown that when the graph induced by the neighboring relation is connected enough of the time, all headings will converge to the same value. Furthermore, we show that when one of the agents does not change its heading and acts as a group leader, all headings converge to that of the leader. Some further generalizations and connections to graph Laplacians are also discussed, and simulation results are presented.