Desynchronization: The Theory of Self-Organizing Algorithms for Round-Robin Scheduling

Florian Berlinger, Melvin Gauci, and Radhika Nagpal. 2021. “Implicit coordination for 3D underwater collective behaviors in a fish-inspired robot swarm.” Science Robotics, 6, 50.Abstract
scirob2021-blueswarm.pdf
Many fish species gather by the thousands and swim in harmony with seemingly no effort. Large schools display a range of impressive collective behaviors, from simple shoaling to collective migration and from basic predator evasion to dynamic maneuvers such as bait balls and flash expansion. A wealth of experimental and theoretical work has shown that these complex three-dimensional (3D) behaviors can arise from visual observations of nearby neighbors, without explicit communication. By contrast, most underwater robot collectives rely on centralized, above-water, explicit communication and, as a result, exhibit limited coordination complexity. Here, we demonstrate 3D collective behaviors with a swarm of fish-inspired miniature underwater robots that use only implicit communication mediated through the production and sensing of blue light. We show that complex and dynamic 3D collective behaviors—synchrony, dispersion/aggregation, dynamic circle formation, and search-capture—can be achieved by sensing minimal, noisy impressions of neighbors, without any centralized intervention. Our results provide insights into the power of implicit coordination and are of interest for future underwater robots that display collective capabilities on par with fish schools for applications such as environmental monitoring and search in coral reefs and coastal environments.
Cover Article -- Movies -- Focus and Science news.
Helen McCreery, Georgina Gemayal, Ana Pais, Simon Garnier, and Radhika Nagpal. 2022. “Hysteresis stabilizes dynamic control of self-assembled army ant constructions.” Nature Communications, 13, 1660. Open Access Link Abstract
Biological systems must adjust to changing external conditions, and their resilience depends on their control mechanisms. How is dynamic control implemented in noisy, decentralized systems? Army ants’ self-assembled bridges are built on unstable features, like leaves, which frequently move. Using field experiments and simulations, we characterize the bridges’ response as the gaps they span change in size, identify the control mechanism, and explore how this emerges from individuals’ decisions. For a given gap size, bridges were larger after the gap increased rather than decreased. This hysteresis was best explained by an accumulator model, in which individual decisions to join or leave a bridge depend on the difference between its current and equilibrium state.This produces robust collective structures that adjust to lasting perturbations while ignoring small, momentary shifts. Our field data support separate joining and leaving cues; joining is prompted by high bridge performance and leaving by an excess of ants. This leads to stabilizing hysteresis, an important feature of many biological and engineered systems.
Michael Rubenstein, Alejandro Cornejo, and Radhika Nagpal. 2014. “Programmable self-assembly in a thousand-robot swarm.” Science, 345, 6198.Abstract
Self-assembly enables nature to build complex forms, from multicellular organisms to complex animal structures such as flocks of birds, through the interaction of vast numbers of limited and unreliable individuals. Creating this ability in engineered systems poses challenges in the design of both algorithms and physical systems that can operate at such scales. We report a system that demonstrates programmable self-assembly of complex two-dimensional shapes with a thousand-robot swarm. This was enabled by creating autonomous robots designed to operate in large groups and to cooperate through local interactions and by developing a collective algorithm for shape formation that is highly robust to the variability and error characteristic of large-scale decentralized systems. This work advances the aim of creating artificial swarms with the capabilities of natural ones.
PDF - Supplement and Movies - Science Top10 Breakthroughs
Justin Werfel, Kirstin Petersen, and Radhika Nagpal. 2014. “Designing Collective Behavior in a Termite-Inspired Robot Construction Team.” Science, 343, 6172.Abstract
Complex systems are characterized by many independent components whose low-level actions produce collective high-level results. Predicting high-level results given low-level rules is a key open challenge; the inverse problem, finding low-level rules that give specific outcomes, is in general still less understood. We present a multi-agent construction system inspired by mound-building termites, solving such an inverse problem. A user specifies a desired structure, and the system automatically generates low-level rules for independent climbing robots that guarantee production of that structure. Robots use only local sensing and coordinate their activity via the shared environment. We demonstrate the approach via a physical realization with three autonomous climbing robots limited to onboard sensing. This work advances the aim of engineering complex systems that achieve specific human-designed goals.
PDF (Front Cover) - Supplement and Movies - Perspective - Science Top10
Robert Wood, Radhika Nagpal, and Gu-Yeon Wei. 2013. “Flight of the Robobees.” Scientific American.
sciam2013-robobee.pdf
Chih-han Yu and Radhika Nagpal. 2010. “A Self-Adaptive Framework for Modular Robots in Dynamic Environment: Theory and Applications.” Intl Journal of Robotics Research. (pdf)
Yong-Lae Park, Bor-Rong Chen, Diana Young, Leia Stirling, Rob Wood, Eugene Goldfield, and Radhika Nagpal. 2011. “Bio-inspired Active Soft Orthotic Device for Ankle Foot Pathologies.” In Intl. Conference on Robots and Systems (IROS). (pdf)
Matthew Gibson, Ankit Patel, Radhika Nagpal, and Norbert Perrimon. 2006. “The Emergence of Geometric Order in Proliferating Metazoan Epithelia.” Nature, 442, 7106.Abstract
The predominantly hexagonal cell pattern of simple epithelia was noted in the earliest microscopic analyses of animal tissues¹, a topology commonly thought to reflect cell sorting into optimally packed honeycomb arrays². Here we use a discrete Markov model validated by time-lapse microscopy and clonal analysis to demonstrate that the distribution of polygonal cell types in epithelia is not a result of cell packing, but rather a direct mathematical consequence of cell proliferation. On the basis of in vivo analysis of mitotic cell junction dynamics in Drosophila imaginal discs, we mathematically predict the convergence of epithelial topology to a fixed equilibrium distribution of cellular polygons. This distribution is empirically confirmed in tissue samples from vertebrate, arthropod and cnidarian organisms, suggesting that a similar proliferation-dependent cell pattern underlies pattern formation and morphogenesis throughout the metazoa.
PDF - Supplement - Perspective
Julius Degesys, Ian Rose, Ankit Patel, and Radhika Nagpal. 2007. “DESYNC: Self-Organizing Desynchronization and TDMA on Wireless Sensor Networks.” In International Conference on Information Processing in Sensor Networks (IPSN). Publisher's Version
Radhika Nagpal. 2002. “Programmable Self-Assembly Using Biologically-Inspired Multiagent Control.” In Proceedings of the 1st International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS). (pdf)

Self-Organizing Systems Research Group

Desynchronization: The Theory of Self-Organizing Algorithms for Round-Robin Scheduling

Citation:

Selected Articles