AF: Small: An Algorithmic Approach to Collective Behavior

这一提议试图从“算法”的角度来解决有关集体行为的基本问题。所考虑的系统由相互通信的代理组成，并根据沿途收集的信息采取自主行动。代理人可以是社会网络的成员，成群的鸟，闪烁的萤火虫，成群的细菌等等。在所有情况下，代理都配备了自己的（可能不同的）决策程序，告诉他们在什么条件下做什么，听什么代理。在这种本地相互作用的多样性中，经常会出现引人注目的模式：鸟类会形成三角形；萤火虫会达到完美的同步；细菌会进行群体感应。如何研究这种突发性自组织呢？这项工作的前提是，研究集体行为的算法方法有望提供一种独特的、新颖的、强大的攻击路线。研究复杂系统的传统工具大多来自动力学和统计物理领域。PI的算法方法将分三个阶段展开。一个是发展将复杂系统分解为简单系统的一般方法。正如图聚类技术是网络分析工具包的重要组成部分一样，“重整化”方法对于自组织和集体出现的分析至关重要。该项目的第二阶段需要设计用于动态网络和时变随机漫步的新工具。第三阶段是研究集体行为的具体模型，特别是群体和意见动态的经典系统。这里的挑战是对这些系统的动态状态进行分类（吸引、周期、混沌、图灵泛等）。更广泛的影响包括在这个跨学科领域的课程开发和在各个层面的研究推广。

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.