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

合作研究：AF：中：计算机科学、统计物理和自组织粒子系统问题的马尔可夫链算法

• 批准号: 2106687
• 负责人: Dana Randall
• 金额: $ 70万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-07-01 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2106687&HistoricalAwards=false
• 关键词: Collaborative; Research; AF; Medium; Markov

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.

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

项目成果

Mathematically Quantifying Non-responsiveness of the 2021 Georgia Congressional Districting Plan

从数学角度量化 2021 年佐治亚州国会选区计划的无反应性

• DOI: 10.1145/3551624.3555300
• 发表时间: 2022-10
• 期刊: and Optimization
• 作者: Zhao, Zhanzhan;Hettle, Cyrus;Gupta, Swati;Mattingly, Jonathan Christopher;Randall, Dana;Herschlag, Gregory Joseph
• 通讯作者: Herschlag, Gregory Joseph

Adaptive Collective Responses to Local Stimuli in Anonymous Dynamic Networks

匿名动态网络中对局部刺激的适应性集体响应

• 发表时间: 2023-01
• 期刊: 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023
• 作者: Oh; Shunhao and
• 通讯作者: Shunhao and

Local Stochastic Algorithms for Alignment in Self-Organizing Particle Systems

自组织粒子系统中的局部随机对齐算法

• 发表时间: 2022-01
• 期刊: and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022
• 作者: Kedia, Hridesh;Oh, Shunhao;Randall, Dana
• 通讯作者: Randall, Dana

A Heterogeneous Schelling Model for Wealth Disparity and its Effect on Segregation

贫富差距的异质谢林模型及其对隔离的影响

• DOI: 10.1145/3551624.3555293
• 发表时间: 2022-10
• 期刊: and Optimization
• 作者: Zhao, Zhanzhan;Randall, Dana
• 通讯作者: Randall, Dana