Search Results

Documents authored by Egan, Noah


Document
Single Bridge Formation in Self-Organizing Particle Systems

Authors: Shunhao Oh, Joseph L. Briones, Jacob Calvert, Noah Egan, Dana Randall, and Andréa W. Richa

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)


Abstract
Local interactions of uncoordinated individuals produce the collective behaviors of many biological systems, inspiring much of the current research in programmable matter. A striking example is the spontaneous assembly of fire ants into "bridges" comprising their own bodies to traverse obstacles and reach sources of food. Experiments and simulations suggest that, remarkably, these ants always form one bridge - instead of multiple, competing bridges - despite a lack of central coordination. We argue that the reliable formation of a single bridge does not require sophistication on behalf of the individuals by provably reproducing this behavior in a self-organizing particle system. We show that the formation of a single bridge by the particles is a statistical inevitability of their preferences to move in a particular direction, such as toward a food source, and their preference for more neighbors. Two parameters, η and β, reflect the strengths of these preferences and determine the Gibbs stationary measure of the corresponding particle system’s Markov chain dynamics. We show that a single bridge almost certainly forms when η and β are sufficiently large. Our proof introduces an auxiliary Markov chain, called an "occupancy chain," that captures only the significant, global changes to the system. Through the occupancy chain, we abstract away information about the motion of individual particles, but we gain a more direct means of analyzing their collective behavior. Such abstractions provide a promising new direction for understanding many other systems of programmable matter.

Cite as

Shunhao Oh, Joseph L. Briones, Jacob Calvert, Noah Egan, Dana Randall, and Andréa W. Richa. Single Bridge Formation in Self-Organizing Particle Systems. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 34:1-34:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{oh_et_al:LIPIcs.DISC.2024.34,
  author =	{Oh, Shunhao and Briones, Joseph L. and Calvert, Jacob and Egan, Noah and Randall, Dana and Richa, Andr\'{e}a W.},
  title =	{{Single Bridge Formation in Self-Organizing Particle Systems}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{34:1--34:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.34},
  URN =		{urn:nbn:de:0030-drops-212606},
  doi =		{10.4230/LIPIcs.DISC.2024.34},
  annote =	{Keywords: Self-organizing particle systems, programmable matter, bridging, jump chain}
}
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