Collaborative Research: AF: Medium: Markov Chain Algorithms for Problems from Computer Science, Statistical Physics and Self-Organizing Particle Systems

自组织可以被看作是一种现象，在这种现象中，一个集体的不可预见的全球配置和模式从每个个体执行的完全分布和简单化的规则中出现，没有任何全球协调或外部干预。 自组织和涌现行为自然出现在许多领域：计算机科学中的分布式系统和群体机器人，物理学中的相互作用粒子系统，生物学中的种群动力学和群体协调，机器人和控制理论中的自治系统，以及智能材料，仅举几例。最近，离散概率、算法和统计物理之间的协同作用为通过利用物理系统的集体涌现行为来设计自组织粒子系统提供了一种新方法。 物理定律在纳米和微米尺度的集体行为中发挥着越来越重要的作用，特别是因为个体代理的能力远远低于宏观对手。 然而，虽然统计物理学的原理已经激励了许多实验系统，但在使相应的底层分布式算法严格化方面却做得很少。 该项目研究如何通过将动态建模为自组织粒子系统，通过可以严格分析的局部相互作用执行马尔可夫链的步骤，来编程代理的集合以执行任务。 这些链的极限分布具有不同的平衡特征，可以用来编程集体行为。主要研究人员采取三管齐下的方法：首先，他们介绍和研究常见的统计物理模型，如Potts，Ising和硬核模型，以更好地捕捉相互作用的微尺度系统所施加的约束。 接下来，他们探索方法，以更好地了解这些系统的非平衡动力学收敛之前很久，可能受到的力量，使马尔可夫链不可逆。最后，他们探索了如何通过在环境中故意放置障碍物和特征来编程集体系统，而不是对代理本身进行编程，因为这些微小的代理中有许多无法进行任何复杂的（传统的）计算。作为规划环境的一个例子，人们正在研究一个新版本的谢林隔离模型，如果人们对他们社区的当地人口统计数据不满意，他们会以更高的概率移动，但这些偏好可以通过放置修改个人激励结构和偏见的理想城市基础设施来减轻。 该项目在促进和推进跨学科研究在许多领域的影响;教育，通过先进的研究生课程和广泛的，跨学科的谈话;多样性在研究生，本科生和教师的水平;推广到公众和K-12教育;城市规划，该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的学术价值和更广泛的影响评审标准。

Self-organization can be viewed as a phenomenon whereby unanticipated global configurations and patterns of a collective emerge from fully distributed and simplistic rules performed by each individual, without any global coordination or external intervention. Self-organization and emergent behavior arise naturally across many fields: distributed systems and swarm robotics in computer science, interacting particle systems in physics, population dynamics and flock coordination in biology, autonomous systems in robotics and control theory, and smart materials, to name a few. Recently, the synergy between discrete probability, algorithms and statistical physics has provided a new approach for designing self-organizing particle systems by harnessing collective, emergent behavior of physical systems. The laws of physics play an increasingly important role in collective behavior at the nano- and micro-scales, especially since individual agents are far less capable than their macroscopic counterparts. Yet, while the principles of statistical physics have motivated many experimental systems, little has been done to make the corresponding underlying distributed algorithms rigorous. This project investigates how to program collections of agents to perform tasks by modeling the dynamics as self-organizing particle systems performing steps of Markov chains through local interactions that can be rigorously analyzed. The limiting distributions of these chains have distinct equilibrium characteristics that can be used to program collective behavior. The principal investigators take a three-pronged approach: First, they introduce and study generalizations of common statistical physics models, such as the Potts, Ising and hard-core models, to better capture the constraints imposed by micro-scale systems of interacting agents. Next, they explore methods to better understand the nonequilibrium dynamics of these systems long before convergence and possibly subject to forces that make the Markov chains nonreversible. Finally, they explore how collective systems might be programmed through deliberate placement of obstacles and features in the environment, rather than programming the agents themselves, as many of these tiny agents are incapable of any sophisticated (traditional) computation. As an example of programming the environment, a new version of the Schelling segregation model is being studied where people move with higher probabilities if they are unhappy with the local demographics of their neighborhoods, but these preferences can be somewhat mitigated by the placement of desirable urban infrastructures that modify individuals' incentive structures and biases. The project is having impact in promoting and advancing interdisciplinary research across many fields; education, through advanced graduate courses and broad, interdisciplinary talks; diversity at the graduate, undergraduate, and faculty levels; outreach to the general public and for K-12 education; and municipal planning, through coordination with regional planning faculty and the City of Atlanta.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.