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在跨学科研究方面有着良好的记录，包括启动跨学科领域(例如，机器人物理、自组织粒子系统，以及统计物理和随机算法的融合)。他们坚定地致力于支持少数民族、女性和本科生的研究(例如，通过国家科学基金会REUS，包括这个项目，国家科学基金会S-亚利桑那州立大学的STEM项目；佐治亚理工学院的高级和S.U.R.E.项目)。在群体和活动物质系统的这种组合上的任何突破都需要使用来自随机系统、凝聚态物理、群体系统、机器人学和分布式算法的分析和技术来理解和实现所需的群体动力学，因此将汇集和教育来自不同学科和专业的研究人员。新的研究方法和研究成果将被纳入多个研究生课程，讲习班将提供衔接多学科的教程，使年轻研究人员能够获得材料，并帮助广泛传播成果。研究结果(包括开放源代码)将在不同学科中发布，并将在我们的网页和Arxiv上提供。该项目从物理学的角度探索了群体机器人的基本原理，将群体视为由微观层面的可编程元素组成的活动物质。该项目将遵循(宏观)面向任务的方法，并设计一个分布式随机算法框架，在微观层面设计和评估算法，以产生有针对性的紧急宏观行为。它解决的紧急行为包括压缩(在最大限度地减少周长的同时保持连接社区的连贯性)、桥梁(以最有效的方式连接两个或更多位置)、对齐(确定商定的方向)、堵塞(增加的集体流动阻碍移动)和移动(集体移动，同时保持凝聚力)。其中许多都有有趣的相反问题，这些问题也同样值得考虑，例如探索(维持一个相连的人口，但探索最大的区域)和非对齐(代表一个无序的整体)。在某些情况下，集体行为就像一个物理系统在液体(无序)和固体(有序)之间变化一样，这是由系统中的相变决定的。该项目将探索随机和分布式算法，以严格实现这些目标。

项目成果

A Stochastic Approach to Shortcut Bridging in Programmable Matter

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

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

Sampling biased monotonic surfaces using exponential metrics

使用指数度量对有偏差的单调曲面进行采样

• DOI: 10.1017/s0963548320000188
• 发表时间: 2020
• 期刊: Probability and Computing
• 作者: Greenberg, Sam;Randall, Dana;Streib, Amanda Pascoe
• 通讯作者: Streib, Amanda Pascoe

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

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

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

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

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

• DOI: 10.1002/rsa.21082
• 发表时间: 2022
• 期刊: 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
• 期刊: 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.