skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Brief Announcement: Foraging in Particle Systems via Self-Induced Phase Changes
The foraging problem asks how a collective of particles with limited computational, communication and movement capabilities can autonomously compress around a food source and disperse when the food is depleted or shifted, which may occur at arbitrary times. We would like the particles to iteratively self-organize, using only local interactions, to correctly gather whenever a food particle remains in a position long enough and search if no food particle has existed recently. Unlike previous approaches, these search and gather phases should be self-induced so as to be indefinitely repeatable as the food evolves, with microscopic changes to the food triggering macroscopic, system-wide phase transitions. We present a stochastic foraging algorithm based on a phase change in the fixed magnetization Ising model from statistical physics: Our algorithm is the first to leverage self-induced phase changes as an algorithmic tool. A key component of our algorithm is a careful token passing mechanism ensuring a dispersion broadcast wave will always outpace a compression wave.  more » « less
Award ID(s):
2106917 2106687
PAR ID:
10426591
Author(s) / Creator(s):
; ;
Editor(s):
Scheideler, Christian
Publisher / Repository:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Date Published:
Volume:
246
ISSN:
1868-8969
ISBN:
978-3-95977-255-6
Page Range / eLocation ID:
1-3
Subject(s) / Keyword(s):
Foraging self-organized particle systems compression phase changes Theory of computation → Self-organization Theory of computation → Random walks and Markov chains
Format(s):
Medium: X Size: 3 pages; 427947 bytes Other: application/pdf
Size(s):
3 pages 427947 bytes
Right(s):
Creative Commons Attribution 4.0 International license; info:eu-repo/semantics/openAccess
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Theoretical Computer Science)
    Doty, David; Spirakis, Paul (Ed.)
    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 whose edge set changes over time, and stimuli are placed adversarially on the vertices of 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 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. 
    more » « less
  2. ; ; (, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023))
    Doty, David; Spirakis, Paul (Ed.)
    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 reside on graph vertices, where each stimulus is only recognized locally, and 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 is robust to competing waves of messages as multiple stimuli change, possibly adversarially. Moreover, in addition to handling arbitrary stimulus dynamics, the algorithm can handle agents reconfiguring the connections (edges) of the graph over time in a controlled way. As an application, we show how this Adaptive Stimuli Algorithm on reconfigurable graphs can be used to solve the foraging problem, where food sources may be discovered, removed, or shifted at arbitrary times. 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 phase change and switch to a search phase in which they distribute themselves randomly throughout the lattice region to search for food. Unlike previous approaches to foraging, this process is indefinitely repeatable, withstanding competing waves of messages that may interfere with each other. Like a physical phase change, microscopic changes such as the deletion or addition of a single food source trigger these macroscopic, system-wide transitions as agents share information about the environment and respond locally to get the desired collective response. 
    more » « less
  3. ; ; (, Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023))
    Doty, David; Spirakis, Paul (Ed.)
    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 reside on graph vertices, where each stimulus is only recognized locally, and 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 is robust to competing waves of messages as multiple stimuli change, possibly adversarially. Moreover, in addition to handling arbitrary stimulus dynamics, the algorithm can handle agents reconfiguring the connections (edges) of the graph over time in a controlled way. As an application, we show how this Adaptive Stimuli Algorithm on reconfigurable graphs can be used to solve the foraging problem, where food sources may be discovered, removed, or shifted at arbitrary times. 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 phase change and switch to a search phase in which they distribute themselves randomly throughout the lattice region to search for food. Unlike previous approaches to foraging, this process is indefinitely repeatable, withstanding competing waves of messages that may interfere with each other. Like a physical phase change, microscopic changes such as the deletion or addition of a single food source trigger these macroscopic, system-wide transitions as agents share information about the environment and respond locally to get the desired collective response. 
    more » « less
  4. (, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023))
    Doty, David and (Ed.)
    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 reside on graph vertices, where each stimulus is only recognized locally, and 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 is robust to competing waves of messages as multiple stimuli change, possibly adversarially. Moreover, in addition to handling arbitrary stimulus dynamics, the algorithm can handle agents reconfiguring the connections (edges) of the graph over time in a controlled way. As an application, we show how this Adaptive Stimuli Algorithm on reconfigurable graphs can be used to solve the foraging problem, where food sources may be discovered, removed, or shifted at arbitrary times. 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 phase change and switch to a search phase in which they distribute themselves randomly throughout the lattice region to search for food. Unlike previous approaches to foraging, this process is indefinitely repeatable, withstanding competing waves of messages that may interfere with each other. Like a physical phase change, microscopic changes such as the deletion or addition of a single food source trigger these macroscopic, system-wide transitions as agents share information about the environment and respond locally to get the desired collective response. 
    more » « less
  5. ; ; ; ; (, Frontiers in Astronomy and Space Sciences)
    Radiation belt electrons are strongly affected by resonant interactions with cyclotron-resonant waves. In the case of a particle passing through resonance with a single, coherent wave, a Hamiltonian formulation is advantageous. With certain approximations, the Hamiltonian has the same form as that for a plane pendulum, leading to estimates of the change at resonance of the first adiabatic invariant I , energy, and pitch angle. In the case of large wave amplitude (relative to the spatial variation of the background magnetic field), the resonant change in I and its conjugate phase angle ξ are not diffusive but determined by nonlinear dynamics. A general analytical treatment of slow separatrix crossing has long been available and can be used to give the changes in I associated with “phase bunching,” including the detailed dependence on ξ , in the nonlinear regime. Here we review this treatment, evaluate it numerically, and relate it to previous analytical results for nonlinear wave-particle interactions. “Positive phase bunching” can occur for some particles even in the pendulum Hamiltonian approximation, though the fraction of such particles may be exponentially small. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email