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

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

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.