Adaptive collective responses to local stimuli in anonymous dynamic networks
Adaptive collective responses to local stimuli in anonymous dynamic networks
复制标题
DOI：
10.1016/j.tcs.2024.114904
复制
发表时间：
2025-01-12
影响因子：
1.1
通讯作者：
Richa，Andrea W.
中科院分区：
文献类型：
--
作者：
Oh，Shunhao;Randall，Dana;Richa，Andrea W.
我们开发了一个可编程物质自诱导相变的框架，其中具有有限计算和通信能力的一组代理可以集体执行适当的全局任务，以响应动态出现和消失的局部刺激。智能体由动态图G中的顶点表示，其边集随着时间的变化而变化，刺激被相反地放置在G的顶点上，其中每个智能体只能识别共同定位的刺激。代理通过沿边缘传递令牌来通知其他代理，当刺激存在时转换到有意识状态，当刺激消失时转换到不知道状态。我们提出了一种自适应刺激算法，它可以处理任意的对抗性刺激动态，而对手(或代理本身)随着时间的推移以受控的方式重新配置G的连接(边)。该算法可用于解决可重构图上的觅食问题，在可重构图中，除了食物来源(刺激物)被任意发现、移除或移动外，我们希望代理一致地自组织，仅使用局部相互作用，以便如果食品保持在一个位置足够长的时间，代理转换到聚集阶段，在该阶段中，许多代理共同形成食品周围具有小周长的单个大组件。或者，如果最近没有食物来源，这些代理应该经历一个自我诱导的集体相变，并切换到搜索阶段，在这个阶段，它们在整个图中随机分布以搜索食物。与以前的觅食方法不同，这个过程是无限可重复的，经受住了可能相互干扰的相互竞争的状态转换广播波。就像物理相变一样，比如用于觅食的采集和搜索算法背后的铁磁模型，环境中的微观变化会触发这些宏观的、系统范围的转变，因为代理共享信息并在本地做出响应，以获得所需的集体响应。
We develop a framework for self-induced phase changes in programmable matter in which a collection of agents with limited computational and communication capabilities can collectively perform appropriate global tasks in response to local stimuli that dynamically appear and disappear. Agents are represented by vertices in a dynamic graph G whose edge set changes over time, and stimuli are placed adversarially on the vertices of G where each agent is only capable of recognizing a co-located stimulus. Agents communicate via token passing along edges to alert other agents to transition to an Aware state when stimuli are present and an Unaware state when the stimuli disappear. We present an Adaptive Stimuli Algorithm that can handle arbitrary adversarial stimulus dynamics, while an adversary (or the agents themselves) reconfigures the connections (edges) of G over time in a controlled way. This algorithm can be used to solve the foraging problem on reconfigurable graphs where, in addition to food sources (stimuli) being discovered, removed, or shifted arbitrarily, we would like the agents to consistently self-organize, using only local interactions, such that if the food remains in a position long enough, the agents transition to a gather phase in which many collectively form a single large component with small perimeter around the food. Alternatively, if no food source has existed recently, the agents should undergo a self-induced collective phase change and switch to a search phase in which they distribute themselves randomly throughout the graph to search for food. Unlike previous approaches to foraging, this process is indefinitely repeatable, withstanding competing broadcast waves of state transition that may interfere with each other. Like a physical phase change, such as the ferromagnetic models underlying the gather and search algorithms used for foraging, microscopic changes in the environment trigger these macroscopic, system-wide transitions as agents share information and respond locally to get the desired collective response.