Brief Announcement: Foraging in Particle Systems via Self-Induced Phase Changes

Authors Shunhao Oh, Dana Randall, Andréa W. Richa



PDF
Thumbnail PDF

File

LIPIcs.DISC.2022.51.pdf
  • Filesize: 417 kB
  • 3 pages

Document Identifiers

Author Details

Shunhao Oh
  • School of Computer Science, Georgia Institute of Technology, Atlanta, GA, USA
Dana Randall
  • School of Computer Science, Georgia Institute of Technology, Atlanta, GA, USA
Andréa W. Richa
  • School of Computing and Augmented Intelligence, Arizona State University, Tempe, AZ, USA

Cite AsGet BibTex

Shunhao Oh, Dana Randall, and Andréa W. Richa. Brief Announcement: Foraging in Particle Systems via Self-Induced Phase Changes. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 51:1-51:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.DISC.2022.51

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Self-organization
  • Theory of computation → Random walks and Markov chains
Keywords
  • Foraging
  • self-organized particle systems
  • compression
  • phase changes

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Sarah Cannon, Joshua J. Daymude, Dana Randall, and Andréa W. Richa. A Markov chain algorithm for compression in self-organizing particle systems. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC '16, pages 279-288, 2016. Google Scholar
  2. Shengkai Li, Bahnisikha Dutta, Sarah Cannon, Joshua J. Daymude, Ram Avinery, Enes Aydin, Andréa W. Richa, Daniel I. Goldman, and Dana Randall. Programming active granular matter with mechanically induced phase changes. Science Advances, 7(17):eabe8494, 2021. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail