权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

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

基本信息

批准号：
2106917
负责人：
Andrea Richa
金额：
$ 51.6万
依托单位：
Arizona State University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-07-01 至 2024-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2106917&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的法定使命，并被认为值得通过使用基金会的学术价值和更广泛的影响审查标准。

项目成果

期刊论文数量（8）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Invited Paper: Asynchronous Deterministic Leader Election in Three-Dimensional Programmable Matter

特邀论文：三维可编程物质中的异步确定性领导者选举

DOI：
10.1145/3571306.3571389
发表时间：
2023
期刊：
24th International Conference on Distributed Computing and Networking (ICDCN
影响因子：
0
作者：
Briones, Joseph L.;Chhabra, Tishya;Daymude, Joshua J.;Richa, Andréa W.
通讯作者：
Richa, Andréa W.

Brief Announcement: Foraging in Particle Systems via Self-Induced Phase Changes

简短公告：通过自诱导相变在粒子系统中搜寻

DOI：
发表时间：
2022
期刊：
36th International Symposium on Distributed Computing (DISC
影响因子：
0
作者：
Oh, Shunhao Oh;Randall, Dana;Richa, Andrea W.
通讯作者：
Richa, Andrea W.

Improved Throughput for All-or-Nothing Multicommodity Flows with Arbitrary Demands

提高具有任意需求的全有或全无多种商品流的吞吐量

DOI：
发表时间：
2021
期刊：
IFIP PERFORMANCE
影响因子：
0
作者：
Chaturvedi, Anya;Chekuri, Chandra;Richa, Andrea W.;Rost, Matthias;Schmid, Stefan;Weber, Jamison
通讯作者：
Weber, Jamison

Adaptive collective responses to local stimuli in anonymous dynamic networks