AF: Small: An Algorithmic Approach to Collective Behavior

AF：小：集体行为的算法方法

• 批准号: 1420112
• 负责人: Bernard Chazelle
• 金额: $ 42万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1420112&HistoricalAwards=false
• 关键词: AF; Small; Algorithmic; Approach; Collective

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.

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