3rd Workshop on Biological Distributed Algorithms

Abstract: I will discuss two kinds of distributed algorithms in ant colonies.

1) Nestmate recognition, based on odor cues, has been observed in many social insect species. In collaboration with Fernando Esponda, we proposed a distributed model of nestmate recognition, analogous to the one used by the vertebrate immune system, in which colony response results from the diverse reactions of many ants. The model describes how individual behaviour produces colony response to non-nestmates. No single ant knows the odour identity of the colony. Instead, colony identity is defined collectively by all the ants in the colony. Each ant responds to the odour of other ants by reference to its own unique decision boundary, which is a result of its experience of encounters with other ants. Each ant thus recognizes a particular set of chemical profiles as being those of non-nestmates. This model predicts, as experimental results have shown, that the outcome of behavioural assays is likely to be variable, that it depends on the number of ants tested, that response to non-nestmates changes over time and that it changes in response to the experience of individual ants. A distributed system allows a colony to identify non-nestmates without requiring that all individuals have the same complete information and helps to facilitate the tracking of changes in odor profiles, because only a subset of ants must respond to provide an adequate response.

2) In some species of ants, a colony has many nests, linked by long-lasting trails. Ants travel around these highway networks and search from the main highway to form new trails to food sources. The dynamics of the trail system is related to how long the nests and resources last, and how patchily the resources are distributed. Using very simple local communication and contact between ants, the colony must search for new resources and add to the trail system when resources are found, and rebuild the main highway in response to rupture. Differences among species in the distributed algorithms they use to solve these problems reflect ecological differences in the dynamics of their resources. I will discuss differences between two species in how they search, add to, and repair trail networks. In collaboration with Saket Navlakha and Arjun Chandrasekar, we are investigating the algorithm used by the the tropical arboreal turtle ant, Cephalotes goniodontus, to form trail networks in the trees to collect ephemeral nectar resources. Another example is the invasive Argentine ant, Linepithema humile, with a trail system that expands and contracts seasonally to connect many nests. This species is a worldwide invader that thrives on access to water and food provided by human development.

Abstract: Stochastic robotics borrows multi-scale modeling techniques from statistical mechanics to design stochastic algorithms for individual robots that, when combined in large ensembles of robots, achieve some desired macroscopic outcome. The resulting trajectories of the swarm of robots are often superficially similar in appearance to the trajectories of a swarm of insects completing a task, such as collective load transport by ants or honeycomb construction by honeybees. However, just as thermodynamic variables such as temperature, pressure, and density are tightly coupled in statistical mechanics, team-level outcomes in stochastic robotics are often highly sensitive to environmental parameters such as robot velocity, robot density, or number of robots. Social insects, on the other hand, do not have such sensitivity. For example, roughly the same number of ants form around collectively transported objects regardless of swarm size or activity level, and the same cell-type demographics are reproduced in honeycomb construction regardless of the number of comb-construction workers. In this extended abstract, we propose that stochastic robotics should be enriched with inspiration from bio-chemistry to create a time-scale separation that allows for the robustness to environmental variation seen in social-insect colonies without any use of explicit communication between individuals. As a proof of concept, we apply these ideas to communication-less multi-robot collective transport and show that the resulting teams can match statistical features of real ant teams. As an extension, we show how the same enzyme-inspired algorithms can be used in stochastic assembly problems to regulate cell demographics in honeybee-like fashion.

Abstract: Imagine that we had a piece of matter that can change its physical properties like shape, density, conductivity, or color in a programmable fashion based on either user input or autonomous sensing. This is the vision behind what is commonly known as programmable matter. Many proposals have already been made for realizing programmable matter, ranging from DNA tiles, shape-changing molecules, and cells created via synthetic biology to reconfigurable modular robotics. We are particularly interested in programmable matter consisting of simple elements called particles that can compute, bond, and move, and the feasibility of solving fundamental problems relevant for programmable matter with these particles. As a model for that programmable matter, we will use a generalized form of the amoebot model first proposed by Derakhshandeh et al. in SPAA 2014, and as an example of fundamental problems we will focus on leader election.

Prior results on leader election imply that in the general amoebot model there are instances in which leader election cannot be solved by a local-control protocol. Therefore, we also consider a geometric variant of the amoebot model by restricting the particle structures to form a connected subset on a triangular grid. For these structures we can show that there is a local-control protocol for the leader election problem. The protocol can also be adapted to other regular geometric structures demonstrating that it is advisable to restrict particle structures to such structures.

Abstract: Communication and coordination play a major role in the ability of bacterial cells to adapt to ever changing environments and conditions. Recent work has shown that such coordination underlies several aspects of bacterial responses including their ability to develop antibiotic resistance. Here we develop a new Belief Propagation method that both, helps explain how bacterial cells collectively search for food in harsh environments using extremely limited resources and computational complexity and that can also be used for computational tasks when agents are facing similar restricted conditions. We formalize the communication and computation assumptions required for successful coordination and prove that the method we propose leads to convergence even when using a dynamically changing interaction network. The proposed method improves upon prior models suggested for bacterial communication despite making fewer assumptions. Simulation studies illustrate the ability of the method to explain and further predict various several aspects of bacterial swarm food search.

Abstract: The organization of social groups involves an evolutionary interplay between natural selection and the self-organizational structures that emerge as a function of group dynamics. This can be illustrated by the organization of work, particularly the division of labor, in which different individuals specialize on different tasks. Division of labor is a fundamental component of social insect colony organization, but it is also an essential process in social systems more generally. In this presentation, I will discuss the self-organization of division of labor, as it emerges, and its scaling effects as groups increase in size.

Empirical work supports the assertion that task specialization and division of labor emerges spontaneously in social groups, even at the origins of sociality. I will discuss how this fits with models predicting the emergence of division of labor through simple self-organizational processes. Using harvester ant colonies as a model system, I will also discuss how work organization scales with group size. As colonies become larger and more complex, division of labor systematically increases, consistent with self-organizational models. Colonies also show other predicted allometric shifts in the organization of work, including the allocation of workers across tasks. These scaling effects on work organization are particularly interesting, because they may generate “economies of scale”, relevant to the hypometric scaling of colony-level metabolism. This relationship is of considerable biological interest, because a wide range of systems, from organisms to ecosystems, also show a hypometric scaling relationship between size and metabolism. Despite a wealth of theoretical models addressing hypotheses as to why, this general scaling relationship is not well understood. Thus, social insect colonies may provide one of the best empirical contexts to answer the question: what are the potential connections between scaling of organization and energy, as systems become larger and more complex?

Abstract: The cortex can perform different computational tasks using physiologically stereotypical hardware, neurons and synapses. Is it possible for the same neural algorithm to perform multiple tasks? If so, what determines the computational task that the algorithm performs? To tackle these questions, we focus on two key unsupervised learning tasks that the cortex must perform: clustering and feature discovery. We show that these tasks can be unified algorithmically by symmetric matrix factorization (SMF) of the similarity matrix of the streamed data. We demonstrate that the SMF cost function can be minimized online by a biologically plausible single-layer network with local learning rules. Unconstrained SMF leads to a neural network that extracts the principal subspace of the streamed data. But when we introduce the biologically inspired nonnegativity constraint on the output the network becomes multi-functional: if the streamed data has clear cluster structure, the network performs soft clustering; if the streamed data is generated by a mixture of sparse features, e.g. natural images, the network discovers those sparse features. Interestingly, just like in neural circuits, nonnegative SMF can both reduce and expand the dimensionality of the input. The derived nonnegative SMF network replicates many aspects of cortical anatomy and physiology including unipolar nature of neuronal activity and synaptic weights, sparse heavy-tailed distribution of neuronal activity, local synaptic plasticity rules and the dependence of learning rate on cumulative neuronal activity. By proposing a biologically plausible algorithm performing two different tasks we make a step towards a unified algorithmic theory of neuronal computation.

Abstract: Understanding the theoretical foundations of how memories are encoded and retrieved in neural populations is a central challenge in neuroscience. A popular theoretical scenario for modeling memory function is the attractor neural network scenario, whose prototype is the Hopfield model. The model simplicity and the locality of the synaptic update rules come at the cost of a poor storage capacity, compared with the capacity achieved with perceptron learning algorithms. Here, by transforming the perceptron learning rule, we present an on-line learning rule for a recurrent neural network that achieves near-maximal storage capacity without an explicit supervisory error signal, relying only upon locally accessible information. The fully-connected network consists of excitatory binary neurons with plastic recurrent connections and non-plastic inhibitory feedback stabilizing the network dynamics; the memory patterns to be memorized are presented on-line as strong afferent currents, producing a bimodal distribution for the neuron synaptic inputs. Synapses corresponding to active inputs are modified as a function of the value of the local fields with respect to three thresholds. Above the highest threshold, and below the lowest threshold, no plasticity occurs. In between these two thresholds, potentiation/depression occurs when the local field is above/below an intermediate threshold. We simulated and analyzed a network of binary neurons implementing this rule and measured its storage capacity for different sizes of the basins of attraction. The storage capacity obtained through numerical simulations is shown to be close to the value predicted by analytical calculations. We also quantified the statistics of the resultingsynaptic connectivity matrix, and found that the fraction of zero weight synapses increases with the number of stored patterns.

Abstract: We present fundamental progress on the computational universality of swarms of micro- or nanoscale particles in complex environments such as the vascular system of a biological organism. Components of the swarm are controlled not by individual navigation, but by a uniform global, external force. More specifically, we consider a 2D grid world, in which all obstacles and particles are unit squares, and for each actuation, particles move maximally until they collide with an obstacle or another particle. The objective is to control particle motion within obstacles, design obstacles in order to achieve desired permutation of particles, and establish controlled interaction that is complex enough to allow arbitrary computations. In this short paper, we summarize progress on all these challenges: we demonstrate NP-hardness of parallel navigation, we describe how to construct obstacles that allow arbitrary permutations, and we establish the necessary logic gates for performing arbitrary in-system computations.olonies.

Abstract: The brain performs many kinds of computation for which it is challenging to hypothesize any mechanism that does not contradict the quantitative evidence. Over a lifetime the brain performs hundreds of thousands of individual cognitive acts, of a variety of kinds, most having some dependence on past experience, and having in turn long-term effects on future behavior. It is difficult to reconcile such large scale capabilities, even in principle, with the known resource constraints on cortex, such as low connectivity and low average synaptic strength, and with the requirement that there be explicit algorithms that realize these acts.

Here we shall describe model neural circuits and associated algorithms that respect the brain's most basic resource constraints. These circuits simultaneously support a suite of four basic model tasks that each requires some circuit modification: memory allocation, association, supervised memorization, and inductive learning of threshold functions. The capacity of these circuits is established by simulating sequences of thousands of such acts in a computer, and then testing the circuits created for the cumulative efficacy of the many past acts. Thus the earlier acts of learning need to be retained without undue interference from the more recent ones.

A basic prerequisite for this endeavor is that of devising an appropriate model of computation that reflects the gross quantitative parameters of cortex, including timing, and can be used for expressing algorithms for these systems level tasks in a distributed environment.

Abstract: Genomic sequencing has become a standard research tool in biology, going within 20 years from a high-risk global project into clinical use. Connectomics, the generation (at this point through electron microscopy), of a connectivity graph for a volume of neural tissue, is still in its infancy. This talk will survey the road ahead, the various technical and computational problems we face, and the joint MIT/Harvard effort to devise an automated pipeline that will allow researchers to have connectomes generated on demand.

Abstract: We model and analyze the distributed task allocation problem, which is solved by ant colonies on a daily basis. Ant colonies employ task allocation in which ants are moved from one task to the other in order to meet changing demands introduced by the environment, such as excess or shortage of food, dirtier or cleaner nest, etc. The different tasks are: nursing (overseeing the hatching of newbies), cleaning, patrolling (searching for new food sources), and foraging (collecting and carrying the food to the nest). Ants solve this task allocation efficiently in nature and we mimic their mechanism by presenting a distributed algorithm that is a variant of the ants algorithm. We then analyze the complexity of the resulting task allocation distributed algorithms, and show under what conditions an efficient algorithm exists. In particular, we provide an \Omega(n) lower bound on the time complexity of task allocation when there are no idle ants, and a contrasting upper bound of O(\ln{n}) when a constant fraction of the ants are idle, where n is the total number of ants in the colony. Our analysis suggests a possible explanation of why ant colonies keep part of the ants in a colony idle, not doing anything. Joint work with: Roman Kecher, Moshe Sulamy.

Abstract: Decentralized task allocation has been studied extensively in both distributed computing and social insect biology. While the former often favors tractable mathematical analysis, the latter focuses on fidelity to the behavior observed in insect colonies. Inspired by the relative advantages of both lines of research, we study two families of models and algorithms for task allocation. The first family of models is derived from an existing biological model for task allocation in ants which treats ants as fungible agents. The second family of models and accompanying algorithms follows the mechanics of simulated annealing while capturing individual variations among the ants. Interestingly, despite significant differences among the models, the corresponding algorithms yield comparable results. Furthermore, our analyses provide insights into observed behaviors of ant colonies such as presence of idle ants and the insensitivity of task allocation convergence to colony size.

Abstract: Many social insects collectively construct large nests in complex substrates; such structures are often composed of narrow tunnels. The benefits of collective construction, including reduced construction costs per worker come with challenges of navigation in crowded, confined spaces. Here we studied the workforce organization of groups of S. invicta fire ants creating tunnels in wet granular media. We monitored the activity levels (number of the tunnel visits) of painted fire ant workers during the incipient nest excavation. The activity levels were described by a Lorenz curve with a Gini coefficient of ∼0.7 indicating that a majority of the excavation is performed by a minority of workers. We built a cellular automata model to reproduce nest excavation by fire ants and to test how different models of the workforce organization in small collectives of excavating workers affect excavation dynamics in confined spaces. The results of the simulations suggested that the unequal workload distribution may facilitate nest construction in crowded, confined conditions.

Abstract: In recent years, there has been an increasing focus on the development of robotic swarms that can perform tasks over large spatial and temporal scales. We are addressing the problem of reliably controlling swarms in realistic scenarios where the robots lack global position information, communication, and prior data about the environment. As in natural swarms, the highly resource-constrained platforms would be restricted to local information about swarm members and features that they randomly encounter in the course of exploration.

We are developing a rigorous control and estimation framework for swarms that are subject to these constraints and are deployed in dynamic, unstructured environments. This framework will enable swarms to operate largely autonomously, with user input consisting only of high-level directives that map to a small set of robot parameters. We use stochastic and deterministic models from chemical kinetics and fluid dynamics to describe the robots' roles, task transitions, spatiotemporal distributions, and manipulation dynamics at both the microscopic (individual) and macroscopic (population) levels. In this talk, I will describe our work on various aspects of the framework, including strategies for mapping, task allocation, boundary coverage, formation control, herding, and ant-inspired collective transport. To validate these techniques, we are building a swarm of small manipulator-equipped robots, called "Pheeno," that are designed to be low-cost, customizable platforms for multi-robot research and robotics education.

Abstract: Unicellular organisms exhibit elaborate collective behaviors in response to environmental cues. These behaviors are controlled by complex biochemical networks within individual cells and coordinated through cell-to-cell communication. Describing these behaviors requires new mathematical models that can bridge scales—from biochemical networks within individual cells to spatially structured cellular populations. I will present our recent work on “multiscale” models for the emergence of spiral waves in the social amoeba Dictyostelium discoideum (Physical Review E 91, 062711, 2015 and Molecular Systems Biology 11: 779, 2015). Our models exploit new experimental advances that allow for the direct measurement and manipulation of the small signaling molecule cyclic adenosine monophosphate (cAMP) used by Dictyostelium cells to coordinate behavior in cellular populations. Inspired by recent experiments, we model the Dictyostelium signaling network as an excitable system coupled to various preprocessing modules. We use this family of models to study spatially unstructured populations of “fixed” cells by constructing phase diagrams that relate the properties of population-level oscillations to parameters in the underlying biochemical network. These models suggest a generic strategy for controlling population level behaviors using simple dynamical systems and have the potential to serve as the basis for new biologically inspired algorithms.

Abstract: We extend the idea of distributed bio-inspired source seeking exhibited by fish schools by combining it with an enhanced version of a fish motion model. The combined model shows how the motion of a fish e.g. the speed and the angular steering, is effected by its neighbors or in the presence of a tank wall. The concept of neighborhood can further by simplified using a recent finding on fish interaction by Couzin et al where he shows that the influence on a fish by that of its neighbors can be given by a certain conditional probability measure dependent on the distance and the angular area of the neighbors. Getting inspiration from the aforementioned models, we successfully demonstrate an optimization algorithm in which individuals are able to explore sources at multiple sites by using a collaborated approach while remaining confined inside the region of interest.

Abstract: We show that, for any number $k$ of "opinions", both rumor spreading and plurality consensus with noisy communications channels can be efficiently solved using protocols suitable to biological systems. Our work generalizes the recent result by Feinerman, Haeupler, and Korman [PODC 2014] which holds for two opinions only. This generalization requires to revisit entirely the definitions of central notions such as majority bias and communication noise, and to address several technical issues which do not occur in the binary setting. In particular, Feinerman et al. give an analysis of the amplification of probability bias that results from the application of a majority mechanism, that does not extend to the plurality mechanism. We provide a general analysis technique that allow us to prove such generalization.

Abstract: Social insect colonies can self-regulate as a collective. The colony operates without a unit of central control, in consequence, individuals cannot assess pieces of global information at one specific place or from one specific nestmate. Still these superorganisms can evaluate their surroundings, process information, and make decisions. The limitations of individual workers (local information, simple behavioral rules) strongly contrast with the diversity of colony level reaction to environmental changes which allow them to efficiently track environmental opportunities and challenges. These societies typically develop parallel processing systems where an insect colony performs most of its operations concurrently instead of sequentially, thus frequent adjustment of the worker force engaging in different tasks is required. We propose a mathematical model for describing task partitioning in ant and wasp colonies. The model is based on the organizational capabilities of a ‘‘common stomach’’ through which the colony utilizes the availability of a natural substance as a major communication channel to regulate the income and expenditure of the very same substance. Joint work with Thomas Schmickl.

Abstract: Like the Roman Empire at its peak, a successful ant colony relies on an effective network of roads that facilitate the movement of its powerful army and industrious population across a vast territory. Fifty years ago, E. O. Wilson discovered the chemical nature of these transportation networks comprised of pheromone trails laid by the colony’s workers. His work paved the way for five decades of study on the incredibly efficient organization of ant colonies, based on simple behaviors, multiple interactions and powerful scents.

In this talk, I will briefly review recent discoveries from field, experimental and theoretical works on the construction and functioning of ant transportation networks. I will then focus more specifically on the latest work we have been doing in my group to understand how some species of ants (army ants in particular) build dynamic support structures out of their own bodies to facilitate the traffic along their very active trails. I will talk about what we have discovered so far on the construction mechanisms of these living architectures, present preliminary results of field experiments that we have recently performed, and discuss our plans for future research on this subject. two kinds of distributed algorithms in ant colonies.