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

自我组织可以被视为一种现象，即在没有任何全球协调或外部干预的情况下，集体的意外全球配置和模式从每个人执行的完全分散和简单化的规则中产生。自组织和紧急行为自然地出现在许多领域：计算机科学中的分布式系统和群体机器人，物理学中的相互作用粒子系统，生物学中的种群动力学和群体协调，机器人学和控制理论中的自主系统，以及智能材料，仅举几例。最近，离散概率、算法和统计物理的协同作用为利用物理系统的集体涌现行为来设计自组织粒子系统提供了一种新的方法。物理定律在纳米和微观尺度的集体行为中发挥着越来越重要的作用，特别是因为单个代理人的能力远远低于他们的宏观同行。然而，尽管统计物理学的原理激励了许多实验系统，但在使相应的基础分布式算法变得严谨方面，几乎没有做什么工作。本项目研究如何对代理集合进行编程，以执行任务，方法是将动力学建模为自组织粒子系统，通过可以严格分析的局部相互作用执行马尔可夫链的步骤。这些链的极限分布具有明显的平衡特征，可用于规划集体行为。主要研究人员采取三管齐下的方法：首先，他们介绍和研究常见统计物理模型的泛化，如Potts、Ising和Hard-core模型，以更好地捕捉相互作用的微尺度系统施加的约束。接下来，他们探索了更好地理解这些系统的非平衡动力学的方法，这些系统在收敛之前很久就可能受到使马尔可夫链不可逆的力的影响。最后，他们探索了如何通过故意在环境中放置障碍和功能来对集体系统进行编程，而不是对代理本身进行编程，因为许多这些微小的代理无法进行任何复杂的(传统)计算。作为环境规划的一个例子，谢林隔离模型的一个新版本正在研究中，在该模型中，如果人们对所在社区的当地人口结构不满意，他们搬家的可能性更高，但这些偏好可以通过放置令人满意的城市基础设施来略微缓解，这些基础设施改变了个人的激励结构和偏见。该项目在促进和推进许多领域的跨学科研究方面产生了影响；通过高级研究生课程和广泛的跨学科讲座促进教育；研究生、本科生和教职员工层面的多样性；面向公众和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.