Scalability is a significant challenge for robot swarms. Generally, larger groups of cooperating robots produce more inter-robot collisions, and in swarm robot foraging, larger search arenas result in larger travel costs. This paper demonstrates a scale-invariant swarm foraging algorithm that ensures that each robot finds and delivers targets to a central collection zone at the same rate regardless of the size of the swarm or the search area. Dispersed mobile depots aggregate locally collected targets and transport them to a central place via a hierarchical branching transportation network. This approach is inspired by ubiquitous fractal branching networks such as tree branches and animal cardiovascular networks that deliver resources to cells and determine the scale and pace of life. We demonstrate that biological scaling laws predict how quickly robots forage in simulations of up to thousands of robots searching over thousands of square meters. We then use biological scaling to predict the capacity of depot robots that overcome scaling constraints to produce scale-invariant robot swarms. We verify the claims for large swarms in simulation and implement a simple depot design in hardware.

Designing resource-collection algorithms for relatively simple robots that are effective given the noise and uncertainty of the real world is a challenge in swarm robotics. This paper describes the performance of two algorithms for collective robot foraging: the stochastic central-place foraging algorithm (CPFA) and the distributed deterministic spiral algorithm (DDSA). With the CPFA, robots mimic the foraging behaviors of ants; they stochastically search for targets and share information to recruit other robots to locations where they detect multiple targets. With the DDSA, robots travel along pre-planned spiral paths; robots detect the nearest targets first and, in theory, guarantee eventual complete coverage of the arena with minimal overlap. We implemented both algorithms and compared their performance in a Gazebo simulation and in physical robots in a large outdoor arena. In a realistic Gazebo simulation, the DDSA outperforms the CPFA. However, in real-world experiments with obstacles, collisions, and errors, the movement patterns of robots implementing the DDSA become visually indistinguishable from the CPFA. The CPFA is less affected by noise and error, and it performs as well as, or better than, the DDSA. Physical experiments change our conclusion about which algorithm has the best performance, emphasizing the importance of systematically comparing the performance of swarm robotic algorithms in the real world.

Central-place foraging (CPF) is a canonical task in collective robotics with applications to planetary exploration, automated mining, warehousing, and search and rescue operations. We compare the performance of three Central-Place Foraging Algorithms (CPFAs), variants of which have been shown to work well in real robots: spiral-based, rotating-spoke, and random-ballistic. To understand the difference in performance between these CPFAs, we define the price of ignorance and show how this metric explains our previously published empirical results. We obtain upper-bounds for expected complete collection times for each algorithm and evaluate their performance in simulation. We show that site-fidelity (i.e. returning to the location of the last found target) and avoiding search redundancy are key-factors that determine the efficiency of CPFAs. Our formal analysis suggests the following efficiency ranking from best to worst: spiral, spoke, and the stochastic ballistic algorithm.

A key factor limiting the performance of central place foraging algorithms is the awareness of the agent(s) about the location of food items around the nest. We study the ratio of how much time an ignorant agent takes relative to an omniscient forager for complete collection of food items in the arena. This effectively quantifies the penalty each algorithm pays for not knowing (or choosing to ignore information gained about) where the resources are located. We model the effect of depletion of food items from the arena on the foraging efficiency over time and analytically verify that returning to the location of the last food item found strongly helps in counteracting this effect. To the best of our knowledge, these results have only been empirically argued so far.

As robot swarms become more viable, efficient solutions to fundamental tasks such as swarm search and collection are required. We propose the distributed deterministic spiral algorithm (DDSA) which generalises a spiral search pattern to robot swarms. While being an effective search strategy in its own right, the DDSA is also a useful point of comparison for other swarm search strategies. Such a benchmark for robot swarm search is currently needed but missing. As a case study, we compare the DDSA to a biologically-inspired central-place foraging algorithm that uses stochastic search, memory, and communication to efficiently collect resources in a variety of different resource distributions.

Effective search strategies have evolved in many biological systems, including the immune system. T cells are key effectors of the immune response, required for clearance of pathogenic infection. T cell activation requires that T cells encounter antigen-bearing dendritic cells within lymph nodes, thus, T cell search patterns within lymph nodes may be a crucial determinant of how quickly a T cell immune response can be initiated. Previous work suggests that T cell motion in the lymph node is similar to a Brownian random walk, however, no detailed analysis has definitively shown whether T cell movement is consistent with Brownian motion. Here, we provide a precise description of T cell motility in lymph nodes and a computational model that demonstrates how motility impacts T cell search efficiency. We find that both Brownian and Lévy walks fail to capture the complexity of T cell motion. Instead, T cell movement is better described as a correlated random walk with a heavy-tailed distribution of step lengths. Using computer simulations, we identify three distinct factors that contribute to increasing T cell search efficiency: 1) a lognormal distribution of step lengths, 2) motion that is directionally persistent over short time scales, and 3) heterogeneity in movement patterns. Furthermore, we show that T cells move differently in specific frequently visited locations that we call "hotspots" within lymph nodes, suggesting that T cells change their movement in response to the lymph node environment. Our results show that like foraging animals, T cells adapt to environmental cues, suggesting that adaption is a fundamental feature of biological search.

In order to trigger an adaptive immune response, T cells move through lymph nodes (LNs) searching for dendritic cells (DCs) that carry antigens indicative of infection. We hypothesize that T cells adapt to cues in the (LN) environment to increase search efficiency. We test this hypothesis by identifying locations that are visited by T cells more frequently than a random model of search would suggest. We then test whether T cells that visit such locations have different movement patterns than other T cells. Our analysis suggests that T cells do adapt their movement in response to cues that may indicate the locations of DC targets. We test the ability of our method to identify frequently visited sites in T cells and in a swarm of simulated iAnt robots evolved to search using a suite of biologically-inspired behaviours. We compare the movement of T cells and robots that repeatedly sample the same locations in space with the movement of agents that do not resample space in order to understand whether repeated sampling alters movement. Our analysis suggests that specific environmental cues can be inferred from the movement of T cells. While the precise identity of these cues remains unknown, comparing adaptive search strategies of robots to the movement patterns of T cells lends insights into search efficiency in both systems.

Organisms that can more effectively exploit information about their environments to improve foraging success have a competitive and selective advantage over others. Thus, animals are expected to evolve strategies that use information to improve foraging success. We study how desert seed harvesters use information to improve the rate they collect seeds, which contributes to the colony's fitness. Through field studies and computer simulations, we manipulated the information available to the ants in the spatial distribution of seeds and measured the resulting foraging rates. In field observations, seeds were collected faster when seeds could be found with less information. The increase in foraging rate with clustering was indistinguishable across three related species that vary over an order of magnitude in colony size. Computer simulations show similar systematic increases in foraging rates when information about the food location is communicated among nestmates.

SUMMARY: GetBonNie is a web-based application for building, analyzing and sharing rule-based models encoded in the BioNetGen language (BNGL). Tools accessible within the GetBonNie environment include (i) an applet for drawing graphs that correspond to BNGL code; (ii) a network-generation engine for translating a set of rules into a chemical reaction network; (iii) simulation engines that implement generate-first, on-the-fly and network-free methods for simulating rule-based models; and (iv) a database for sharing models, parameter values, annotations, simulation tasks and results. AVAILABILITY: GetBonNie is free at (http://getbonnie.org).