4th Workshop on Biological Distributed Algorithms

Abstract: Natural systems are immensely more adaptable, flexible, and robust than anything built by humans. For example, ants thrive in forest canopies, desert sands and urban sidewalks. Each species uses its own decentralized strategy that tailors a small repertoire of individual sensing, navigation and communication behaviors to forage effectively in its environment. While spectacularly successful decentralized collective behaviors have evolved in ant colonies and immune systems, it remains a challenge to engineer flexible and effective cooperative robotic systems that can function in the real world. We emulate natural cooperative search behaviors in robot swarms whose behaviors are automatically tuned to produce efficient collective foraging strategies in varied environments. Effective foraging algorithms are distributed across the on-board code of each robot and generated by the evolutionary history of interactions between robots and their environment.

Abstract: The components of complex systems may vary in quality, robustness, and other traits. Individuals may for example be specialized for performing particular tasks. Employing specialists, however, comes at various costs: one is that these individuals perform badly if allocated to the 'wrong' tasks, which can lead to reduced group-level flexibility. Highly efficient individuals may also be fragile, i.e. not robust to disturbances (such as food shortages in insects), or they may be costly to produce. However, to achieve group-level flexibility, it is not necessary to have all individuals be flexible: only as many as needed to compensate for typical task demand fluctuations need to frequently switch tasks. Similarly, a small proportion of 'robust' workers may be enough to carry the group-level function over periods of disturbance while still achieving high group efficiency at other times. Groups may therefore benefit from not employing all-specialist workers, but instead maintaining a mixture of specialized and flexible, robust and fragile, and/or cheap and expensive workers. We discuss how these traits are associated with body size in the case of bumble bee colonies, and how this enables or limits collective function in different environments.

Abstract: Arboreal turtle ants live in the thick forest canopies of western Mexico, where their movements are constrained by a natural graph, formed by overlapping branches, vines, and twigs of trees. Numerous natural environmental perturbations can disconnect foraging trails, which must be repaired without the benefit of centralized control. Despite extensive study in distributed graph search, most algorithms for this problem require greater computational complexity and memory requirements of individual agents than those believed to be possessed by turtle ants. We develop a simple distributed algorithm for repairing network breaks by studying turtle ant behavior in their natural habitat. We validate our algorithm using simulation studies and field experiments.

Abstract: Many ant species employ distributed population density estimation in applications ranging from quorum sensing [Pra05], to task allocation [Gor99], to appraisal of enemy colony strength [Ada90]. It has been shown that ants estimate density by tracking encounter rates – the higher the population density, the more often the ants bump into each other [Pra05, GPT93]. We study distributed density estimation from a theoretical perspective. We show that a group of anonymous agents randomly walking on a grid are able to estimate their density d to within a multiplicative factor (1 +/- \epsilon) with probability (1 - \delta) in just \tilde O(log(1/\delta) log(1/d\epsilon)/d\epsilon^2) steps by measuring their encounter rates with other agents. Despite dependencies inherent in the fact that nearby agents may collide repeatedly (and, worse, cannot recognize when this happens), this bound nearly matches what is required to estimate d by independently sampling grid locations. From a biological perspective, our work helps shed light on how ants and other social insects can obtain relatively accurate density estimates via encounter rates. From a technical perspective, our analysis requires novel understanding of collision probabilities of multiple random walks using local mixing properties of the underlying graph. Our results extend beyond the grid to more general graphs and we discuss applications to biologically-inspired algorithms for social network size estimation, density estimation by robot swarms, and sensor network sampling.

Abstract: Neural networks are considered robust in the sense that the failure of neurons can be compensated by additional learning phases. Nevertheless, in a critical application such as flight control, for which neural networks are now appealing solutions, one cannot afford any additional learning at run-time. In this paper, we view a neural network as a distributed system of which neurons can fail, and we evaluate its robustness in the absence of any (recovery) learning phase. We give, for the first time, tight bounds on the number of neurons that can fail, without harming the result of a computation or making any assumption on the learning algorithm. To determine our bounds, we leverage the very fact that neuronal activation functions are Lipschitzian, in the sense that their growth is controllable. In particular, in the case of multilayer (often called "deep") neural networks, our results provide a guidance on how to distribute synaptic weights over layers to increase robustness, or what waiting rules to set per layer in case of asynchronously firing neurons without losing accuracy at the output level.

Abstract: I will discuss our finding that current neuroscience techniques are insufficient to even understand relatively simple systems, like microprocessors and try to sketch approaches one could take to overcome these problems. Many of these approaches boil down to fitting hierarchical, structural generative models to observed data. This is a surprisingly hard problem and even approximate methods will require massive scale computing. Lastly, I will discuss emerging methods that produce huge datasets about brains that could form the basis of structure discovery.

Abstract: There has recently been significant research interest in understanding the computational power of biological systems. Such systems have been studied by several different research communities, using a wide range of mathematical models and tools. Population protocols [AAD+06] are a popular such model, in which randomly-interacting agents with little computational power cooperate to jointly per- form computational tasks. While early work studied the computational power of population protocols, more recently research has focused on the complexity of fundamental tasks in the population model, such as leader election (which requires convergence to a single agent in a special ‘’leader” state), and majority or consensus (in which agents must converge to a decision as to which of two possible initial states had higher initial count). Recent upper and lower bound results point towards an inherent trade-off between the time complexity of these protocols, and the space complexity, i.e. size of the memory available to each agent. In this extended abstract, we describe new results exploring this trade-off. We exhibit a new unified lower bound, which relates the space available per node with the time complexity achievable by a protocol: for instance, our result implies that any protocol solving either leader election or majority for n agents using O(log log n) states must take Ω(n/polylog n) expected time. This is the first result to characterize time complexity for protocols which employ super-constant number of states per node, and proves that fast, poly-logarithmic running times require protocols to have non-trivial complexity in terms of space per node.

Abstract: We present a new formulation of the V-formation problem for migrating birds in terms of model predictive control (MPC). In our approach, to drive a collection of N birds towards a desired formation, an optimal velocity adjustment (acceleration) is performed at each time-step on each bird’s current velocity using a model-based prediction window of T time-steps. We present both centralized and distributed versions of this approach. The optimization criteria we consider are based on fitness metrics of candidate accelerations that V-formations are known to exhibit. These include velocity matching, clear view, and upwash benefit. We validate our MPC-based approach by showing that for a significant majority of simulation runs, the flock succeeds in forming the desired formation. Our results help to better understand the emergent behavior of formation flight, and provide a control strategy for flocks of autonomous aerial vehicles.

Abstract: We envision programmable matter consisting of systems of computationally limited devices (which we call particles) that are able to self-organize in order to achieve a desired collective goal without the need for central control or external intervention. A central problem for these particle systems is shape formation. In this paper, we present a universal shape formation algorithm which takes an arbitrary seed shape composed of equilateral triangles of unit size and lets the particles build that shape at a scale depending on the number of particles in the system. Our algorithm runs in O(sqrt(n)) asynchronous execution rounds, where n is the number of particles in the system, provided we start from a well-initialized configuration of the particles. This is optimal in a sense that for any shape deviating from the initial configuration, any movement strategy would require Omega(sqrt(n)) rounds in the worst-case (over all asynchronous activations of the particles). Our algorithm relies only on local information (e.g., particles do not have ids, nor do they know n, or have any sort of global coordinate/orientation system), and requires only a constant-size memory per particle.

Abstract: In the biological world, broadcast is a common phenomenon in which a piece of information is propagated from one or few individuals across the population. Examples for such a process include: a single ant that has found food and recruit others, few cells that trigger large population responses, a group of fish that reaches consensus around a group of leaders, or a small number of observant individuals that alert their herd. Such information propagation is achieved in what appears to be highly unpredictable, uncoordinated, noisy and limited communication settings. How biological systems manage to operate effectively despite such communication limitations is a fundamental question whose understanding is currently very preliminary. In this study we take a distributed computing perspective to tackle few aspects of the aforementioned general question. We study a simple, abstract broadcast problem in which a source agent wishes to broadcast a single opinion bit over a well mixed population. Our focus is on understanding the difficulties that arise from the inability of individuals to reliably detect when the protocol has actually started and if their current opinion is up-to-date. To capture such situations we consider a self-stabilizing context, in which the system must converge to a correct solution from any initial configuration. We find that efficient broadcast can be performed in a self-stabilizing manner using only 4 bits per interaction. Reducing the message size further remains an open problem. We provide some supporting evidence for the existence of efficient protocols that use a single bit per interaction.

Abstract: Living systems are often modeled as dynamical systems that enable the emergence of collective behavior from the distributed application of local rules. This approach raises two issues: How realistic are the models? Can their analyses go beyond numerical simulation? This talk will focus on the second question and report on our recent efforts to build new analytical tools to study processes in opinion dynamics, synchronization, swarming, and social learning.