AiTF: Collaborative Research: Distributed and Stochastic Algorithms for Active Matter: Theory and Practice

AiTF：协作研究：活跃物质的分布式随机算法：理论与实践

• 批准号: 1733812
• 负责人: Dana Randall
• 金额: $ 40.8万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1733812&HistoricalAwards=false
• 关键词: AiTF; Collaborative; Research; Distributed; Stochastic

Swarm robotics explores how groups of robots can work towards a singular goal, which is typically achieved by equipping each robot with sensory capabilities, basic computing power, and movement. The sensors detect and use information about the environment to decide on the next action. Swarm robotics has made many advances in recent years, but is still in its infancy. This project proposes to explore swarm robotics systems in a non-standard way as physical systems. The PIs take a "task-oriented" approach to develop the distributed algorithmic rules that the robots will run (at the microscopic level) in order to converge to the desired collective behavior (at the macroscopic level). This will provide understanding of the minimal requirements for individuals to accomplish the desired behavior, for both algorithmic and physical realizations, and will provide a more principled approach for studying swarm robotics. The robots envisioned are small in scale, ranging in size from millimeters to centimeters, so that when deployed in dense environments, they will behave as programmable active matter.The PIs have strong records for interdisciplinary research, including initiating interdisciplinary areas (e.g., robo-physics, self-organizing particle systems, and the fusion of statistical physics and randomized algorithms). They have a strong commitment toward supporting minorities, women, and undergrad research (e.g., through NSF REUs, including through this project, NSF S-STEM programs at ASU; ADVANCE and S.U.R.E. programs at Georgia Tech). Any breakthrough in this combination of swarm and active matter systems will require employing analyses and techniques from stochastic systems, condensed matter physics, swarm systems, robotics, and distributed algorithms to understand and achieve the desired group dynamics, and hence will bring together and educate researchers from different disciplines and specialties. New research approaches and findings will be incorporated into multiple graduate courses and workshops will provide tutorials for bridging multiple disciplines, making material accessible to young researchers and helping to widely disseminate results. Findings (including open source code) will be published in the various disciplines, and will be be made available on our web pages and ArXiv. The project explores the fundamentals of swarm robotics from a physics standpoint, by viewing the ensemble as active matter composed of programmable elements at the micro-level. The project will follow a (macro-)task oriented approach, and design a distributed stochastic algorithmic framework to design and evaluate algorithms at the micro-level that will yield the targeted emergent macroscopic behavior. The emergent behaviors it addresses include compression (maintaining coherence of a connected community while minimizing perimeter), bridging (connecting two or more locations in the most efficient manner), alignment (determining an agreed upon direction of orientation), jamming (obstruction of movement by increased collective flow), and locomotion (collectively moving while maintaining cohesiveness). Many of these have interesting converse problems which are also equally worthwhile, such as exploration (maintaining a connected population, but exploring maximal area) and non-alignment (representing a disordered ensemble). In some cases the collective behavior acts like a physical system changing between a liquid (disordered) and a solid (ordered) state, as determined by phase transitions in the systems. The project will explore stochastic and distributed algorithms for rigorously achieving these goals.

群体机器人技术探索机器人群体如何实现单一目标，这通常是通过为每个机器人配备感知能力、基本计算能力和运动来实现的。传感器检测并使用有关环境的信息来决定下一步行动。近年来，群体机器人技术取得了许多进步，但仍处于起步阶段。该项目建议以非标准方式探索群体机器人系统作为物理系统。 PI 采用“面向任务”的方法来开发机器人将运行的分布式算法规则（在微观层面），以便收敛到所需的集体行为（在宏观层面）。 这将有助于理解个体在算法和物理实现方面完成所需行为的最低要求，并将为研究群体机器人技术提供更有原则性的方法。设想的机器人规模较小，尺寸从毫米到厘米不等，因此当部署在密集环境中时，它们将表现得像可编程活性物质。 PI 在跨学科研究方面拥有良好的记录，包括启动跨学科领域（例如，机器人物理、自组织粒子系统以及统计物理和随机算法的融合）。他们坚定地致力于支持少数族裔、女性和本科生研究（例如，通过 NSF REU，包括通过该项目、亚利桑那州立大学的 NSF S-STEM 项目；佐治亚理工学院的 ADVANCE 和 S.U.R.E 项目）。 群体和活性物质系统结合的任何突破都需要采用随机系统、凝聚态物理、群体系统、机器人和分布式算法的分析和技术来理解和实现所需的群体动力学，因此将聚集和教育研究人员来自不同学科和专业。 新的研究方法和发现将被纳入多个研究生课程，研讨会将提供跨学科的教程，使年轻研究人员能够获取材料并帮助广泛传播结果。研究结果（包括开源代码）将在各个学科中发布，并将在我们的网页和 ArXiv 上提供。 该项目从物理学的角度探索群体机器人的基础知识，将群体视为由微观层面的可编程元素组成的活性物质。 该项目将遵循面向（宏观）任务的方法，并设计一个分布式随机算法框架来设计和评估微观层面的算法，从而产生目标的紧急宏观行为。 它解决的紧急行为包括压缩（保持连接社区的连贯性，同时最小化周界）、桥接（以最有效的方式连接两个或多个位置）、对齐（确定商定的方向）、干扰（通过增加集体流动）和运动（集体移动，同时保持凝聚力）。其中许多都有有趣的相反问题，这些问题也同样值得，例如探索（维持连接的群体，但探索最大区域）和不对齐（代表无序的整体）。在某些情况下，集体行为就像一个在液态（无序）和固态（有序）状态之间变化的物理系统，由系统中的相变决定。该项目将探索随机和分布式算法来严格实现这些目标。

项目成果

A Stochastic Approach to Shortcut Bridging in Programmable Matter

可编程物质中捷径桥接的随机方法

• DOI: 10.1007/978-3-319-66799-7_9
• 发表时间: 2017-01
• 期刊: DNA23
• 作者: Andres Arroyo, Marta;Cannon, Sarah;Daymude, Joshua J;Randall, Dana;Richa, Andrea W
• 通讯作者: Richa, Andrea W

Collective clog control: Optimizing traffic flow in confined biological and robophysical excavation

集体堵塞控制：优化密闭生物和机器人物理挖掘中的交通流量

• DOI: 10.1126/science.aan3891
• 发表时间: 2018-08
• 期刊: Science
• 影响因子: 56.9
• 作者: Aguilar, J.;Monaenkova, D.;Linevich, V.;Savoie, W.;Dutta, B.;Kuan, H.;Betterton, M. D.;Goodisman, M. A.;Goldman, D. I.
• 通讯作者: Goldman, D. I.

Mixing times of Markov chains for self‐organizing lists and biased permutations

用于自组织列表和有偏排列的马尔可夫链的混合时间

• DOI: 10.1002/rsa.21082
• 发表时间: 2022-04
• 期刊: Random Structures & Algorithms
• 影响因子: 1
• 作者: Bhakta, Prateek;Miracle, Sarah;Randall, Dana;Streib, Amanda Pascoe
• 通讯作者: Streib, Amanda Pascoe

Phototactic supersmarticles

趋光性超级粒子

• DOI: 10.1007/s10015-018-0473-7
• 发表时间: 2018-12
• 期刊: Artificial Life and Robotics
• 影响因子: 0.9
• 作者: Savoie, William;Cannon, Sarah;Daymude, Joshua J.;Warkentin, Ross;Li, Shengkai;Richa, Andréa W.;Randall, Dana;Goldman, Daniel I.
• 通讯作者: Goldman, Daniel I.

Brief Announcement: A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems

简短公告：一种用于异质自组织粒子系统分离的局部随机算法

• DOI: 10.1145/3212734.3212792
• 发表时间: 2018-01
• 期刊: PODC
• 作者: Cannon, Sarah;Daymude, Joshua J;Gokmen, Cem;Randall, Dana;Richa, Andrea W
• 通讯作者: Richa, Andrea W