This proposal seeks to answer fundamental questions about collective behavior by attacking them from an "algorithmic" perspective. The systems under consideration consist of agents communicating with one another and taking autonomous actions based on the information gathered along the way. The agents could be members of a social network, flocking birds, flashing fireflies, swarming bacteria, etc. In all cases, agents are equipped with their own (possibly distinct) decision procedures that tell them what to do under what conditions and what agents to listen to. Out of this diversity of local interactions, striking patterns will often emerge: birds will form triangles; fireflies will reach perfect synchronization; bacteria will perform quorum sensing. How does one study emergent self-organization of this sort? The premise of this work is that an algorithmic approach to collective behavior holds the promise of a uniquely novel and powerful line of attack.
The traditional tools for the study of complex systems draw mostly from the fields of dynamics and statistical physics. The PI's algorithmic approach will unfold in three phases. One is to develop general methods for decomposing complex systems into simpler ones. Just as graph clustering techniques are essential parts of the toolkit of network analysis, so "renormalization" methods are crucial for the analysis of self-organization and collective emergence. The second phase of this project entails the design of new tools for dynamic networks and time-varying random walks. The third phase is to investigate specific models of collective behavior, in particular classical systems for swarming and opinion dynamics. The challenge there is to classify the dynamic regimes of these systems (attractive, periodic, chaotic, Turing-universal, etc).
Broader impacts include curriculum development on this inter-disciplinary field and outreach presentations of the research at all levels.
