Document Open Access Logo

Adaptive Collective Responses to Local Stimuli in Anonymous Dynamic Networks

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

PDF
Thumbnail PDF

File

LIPIcs.SAND.2023.6.pdf
  • Filesize: 1.08 MB
  • 23 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

Funding

  • Oh, Shunhao: Funded in part by U.S. Army Research Office (ARO) award MURI W911NF-19-1-0233.
  • Randall, Dana: Supported by the National Science Foundation (NSF) award CCF-2106687 and by U.S. Army Research Office (ARO) award MURI W911NF-19-1-0233.
  • Richa, Andréa W.: Supported in part by the National Science Foundation (NSF) award CCF-2106917 and by U.S. Army Research Office (ARO) award MURI W911NF-19-1-0233.

Acknowledgements

The authors thank the anonymous reviewers for useful feedback on the presentation.

Cite AsGet BibTex

Shunhao Oh, Dana Randall, and Andréa W. Richa. Adaptive Collective Responses to Local Stimuli in Anonymous Dynamic Networks. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.SAND.2023.6

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Self-organization
  • Theory of computation → Random walks and Markov chains
Keywords
  • Dynamic networks
  • adaptive stimuli
  • foraging
  • self-organizing particle systems
  • programmable matter

Metrics

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

Related Versions

References

  1. Simon Alberti. Organizing living matter: The role of phase transitions in cell biology and disease. Biophysical journal, 14, 2018. Google Scholar
  2. Marta Andrés Arroyo, Sarah Cannon, Joshua J. Daymude, Dana Randall, and Andréa W. Richa. A stochastic approach to shortcut bridging in programmable matter. In 23rd International Con- ference on DNA Computing and Molecular Programming (DNA), pages 122-138, 2017. Google Scholar
  3. Chen Avin, Michal Koucký, and Zvi Lotker. Cover time and mixing time of random walks on dynamic graphs. Random Structures & Algorithms, 52(4):576-596, 2018. Google Scholar
  4. Sarah Cannon, Joshua J. Daymude, Cem Gökmen, Dana Randall, and Andréa W. Richa. A local stochastic algorithm for separation in heterogeneous self-organizing particle systems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), pages 54:1-54:22, 2019. Google Scholar
  5. 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
  6. Arnaud Casteigts. Finding structure in dynamic networks, 2018. URL: https://arxiv.org/abs/1807.07801.
  7. Bernard Chazelle. The convergence of bird flocking. J. ACM, 61(4), 2014. Google Scholar
  8. Andrea Clementi, Riccardo Silvestri, and Luca Trevisan. Information spreading in dynamic graphs. In Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing, pages 37-46, 2012. Google Scholar
  9. Nikolaus Correll and Alcherio Martinoli. Modeling and designing self-organized aggregation in a swarm of miniature robots. The Int'l J. of Robotics Research, 30(5):615-626, 2011. Google Scholar
  10. Paolo Dario, Renzo Valleggi, Maria Chiara Carrozza, M. C. Montesi, and Michele Cocco. Microactuators for microrobots: a critical survey. Journal of Micromechanics and Microengineering, 2(3):141-157, 1992. Google Scholar
  11. Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler. The Canonical Amoebot Model: Algorithms and Concurrency Control. In 35th International Symposium on Distributed Computing (DISC 2021), volume 209 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1-20:19, 2021. Google Scholar
  12. Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler. The canonical amoebot model: Algorithms and concurrency control. Distributed Computing, 2023. To appear. Google Scholar
  13. Oksana Denysyuk and Luís Rodrigues. Random walks on evolving graphs with recurring topologies. In Distributed Computing, pages 333-345. Springer Berlin Heidelberg, 2014. Google Scholar
  14. Michael Dinitz, Jeremy T. Fineman, Seth Gilbert, and Calvin Newport. Smoothed analysis of information spreading in dynamic networks. In Christian Scheideler, editor, 36th International Symposium on Distributed Computing (DISC), volume 246 of LIPIcs, pages 18:1-18:22, 2022. Google Scholar
  15. Chinmoy Dutta, Gopal Pandurangan, Rajmohan Rajaraman, Zhifeng Sun, and Emanuele Viola. On the complexity of information spreading in dynamic networks. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 717-736. SIAM, 2013. Google Scholar
  16. Nazim Fatès. Solving the decentralised gathering problem with a reaction–diffusion–chemotaxis scheme. Swarm Intelligence, 4(2):91-115, 2010. Google Scholar
  17. Nazim Fatès and Nikolaos Vlassopoulos. A robust aggregation method for quasi-blind robots in an active environment. In ICSI 2011, 2011. Google Scholar
  18. Simon Garnier, Jacques Gautrais, Masoud Asadpour, Christian Jost, and Guy Theraulaz. Self-organized aggregation triggers collective decision making in a group of cockroach-like robots. Adaptive Behavior, 17(2):109-133, 2009. Google Scholar
  19. Simon Garnier, Christian Jost, Raphaël Jeanson, Jacques Gautrais, Masoud Asadpour, Gilles Caprari, and Guy Theraulaz. Aggregation behaviour as a source of collective decision in a group of cockroach-like-robots. In Advances in Artificial Life, ECAL '05, pages 169-178, 2005. Google Scholar
  20. Bernhard Haeupler and David Karger. Faster information dissemination in dynamic networks via network coding. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pages 381-390, 2011. Google Scholar
  21. Walter Hussak and Amitabh Trehan. On termination of a flooding process. In Proc. of the 2019 ACM Symp. on Principles of Distributed Computing, PODC '19, pages 153-155, 2019. Google Scholar
  22. Hridesh Kedia, Shunhao Oh, and Dana Randall. A local stochastic algorithm for alignment in self-organizing particle systems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022), volume 245, pages 14:1-14:20, 2022. Google Scholar
  23. Fabian Kuhn, Nancy Lynch, and Rotem Oshman. Distributed computation in dynamic networks. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, pages 513-522, 2010. Google Scholar
  24. Fabian Kuhn and Rotem Oshman. Dynamic networks: Models and algorithms. SIGACT News, 42(1):82-96, 2011. Google Scholar
  25. 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, 2021. Google Scholar
  26. Jintao Liu, Arthur Prindle, Jacqueline Humphries, Marçal Gabalda-Sagarra, Munehiro Asally, Dong-Yeon D. Lee, San Ly, Jordi Garcia-Ojalvo, and Gürol M. Süel. Metabolic co-dependence gives rise to collective oscillations within biofilms. Nature, 523(7562):550-554, 2015. Google Scholar
  27. Anne E. Magurran. The adaptive significance of schooling as an anti-predator defence in fish. Annales Zoologici Fennici, 27(2):51-66, 1990. Google Scholar
  28. Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. Equation of State Calculations by Fast Computing Machines. The Journal of Chemical Physics, 21:1087-1092, 1953. Google Scholar
  29. Nathan J. Mlot, Craig A. Tovey, and David L. Hu. Fire ants self-assemble into waterproof rafts to survive floods. Proc. of the National Academy of Sciences, 108(19):7669-7673, 2011. Google Scholar
  30. Anil Özdemir, Melvin Gauci, Salomé Bonnet, and Roderich Groß. Finding consensus without computation. IEEE Robotics and Automation Letters, 3(3):1346-1353, 2018. Google Scholar
  31. Arthur Prindle, Jintao Liu, Munehiro Asally, San Ly, Jordi Garcia-Ojalvo, and Gürol M. Süel. Ion channels enable electrical communication in bacterial communities. Nature, 527(7576):59-63, 2015. Google Scholar
  32. Erol Şahin. Swarm robotics: From sources of inspiration to domains of application. In Swarm Robotics, pages 10-20, 2005. Google Scholar
  33. William Savoie, Sarah Cannon, Joshua J. Daymude, Ross Warkentin, Shengkai Li, Andréa W. Richa, Dana Randall, and Daniel I. Goldman. Phototactic supersmarticles. Artificial Life and Robotics, 23(4):459-468, 2018. Google Scholar
  34. Thomas C. Schelling. Dynamic models of segregation. The Journal of Mathematical Sociology, 1(2):143-186, 1971. Google Scholar
  35. Onur Soysal and Erol Şahin. Probabilistic aggregation strategies in swarm robotic systems. In Proceedings 2005 IEEE Swarm Intelligence Symposium, SIS 2005, pages 325-332, 2005. Google Scholar
  36. Tommaso Toffoli and Norman Margolus. Programmable matter: Concepts and realization. Physica D: Nonlinear Phenomena, 47(1):263-272, 1991. Google Scholar
  37. David H. Wolpert. The stochastic thermodynamics of computation. Journal of Physics A: Mathematical and Theoretical, 52(19):193001, 2019. Google Scholar
  38. Hui Xie, Mengmeng Sun, Xinjian Fan, Zhihua Lin, Weinan Chen, Lei Wang, Lixin Dong, and Qiang He. Reconfigurable magnetic microrobot swarm: Multimode transformation, locomotion, and manipulation. Science Robotics, 4(28):eaav8006, 2019. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact