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

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

• 批准号: 1733680
• 负责人: Andrea Richa
• 金额: $ 20.8万
• 依托单位: Arizona State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1733680&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
• 期刊: DNA23
• 作者: Andres Arroyo, Marta;Cannon, Sarah;Daymude, Joshua J;Randall, Dana;Richa, Andrea W
• 通讯作者: Richa, Andrea W

Bio-Inspired Energy Distribution for Programmable Matter

• DOI: 10.1145/3427796.3427835
• 发表时间: 2020-07
• 期刊: Proceedings of the 22nd International Conference on Distributed Computing and Networking
• 作者: Joshua J. Daymude;A. Richa;Jamison Weber

On the runtime of universal coating for programmable matter

• DOI: 10.1007/s11047-017-9658-6
• 发表时间: 2018-03-01
• 期刊: NATURAL COMPUTING
• 影响因子: 2.1
• 作者: Daymude, Joshua J.;Derakhshandeh, Zahra;Strothmann, Thim
• 通讯作者: Strothmann, Thim

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

Convex Hull Formation for Programmable Matter

可编程物质的凸包构造

• DOI: 10.1145/3369740.3372916
• 发表时间: 2020
• 期刊: International Conference on Distributed Computing and Networking (ICDCN
• 作者: Daymude, Joshua J.;Gmyr, Robert;Hinnenthal, Kristian;Kostitsyna, Irina;Scheideler, Christian;Richa, Andréa W.
• 通讯作者: Richa, Andréa W.