Modern supercomputers rely on graphics processing units (GPUs) to achieve unprecedented computational capabilities. Multi-node computation with GPUs promises to accelerate and scale simulations dramatically across many domains, and many scientific simulations have been adapted to this new paradigm of supercomputing. However, agent-based models (ABMs) are a class of simulations that to date have seen little development for multinode, multi-GPU supercomputers because their computation flow poses unique algorithmic and communication challenges for effective performance on GPU enabled supercomputers. In particular, many ABMs have irregular and dynamic communication patterns, resource competition that causes race conditions, and unpredictable effects on load balancing. We studied the Spatial Immune Model of Coronavirus, or SIMCoV, as a target ABM application for acceleration. SIMCoV is a large-scale ABM which simulates the spread of viral infection through the epithelial tissue of the lungs and models the immune response with diffusing inflammatory signals and mobile T cell agents. Our multinode, multi-GPU implementation of SIMCoV achieves significant speedups over a competitive baseline version, up to 11.9x with a ratio of 32 CPU cores to a single GPU. The paper describes SIMCoV's GPU-specific optimizations, reports empirical results, and demonstrates effective solutions to the challenges of accelerating ABMs on modern supercomputers.

A key question in SARS-CoV-2 infection is why viral loads and patient outcomes vary dramatically across individuals. Because spatial-temporal dynamics of viral spread and immune response are challenging to study in vivo, we developed Spatial Immune Model of Coronavirus (SIMCoV), a scalable computational model that simulates hundreds of millions of lung cells, including respiratory epithelial cells and T cells. SIMCoV replicates viral growth dynamics observed in patients and shows how spatially dispersed infections can lead to increased viral loads. The model also shows how the timing and strength of the T cell response can affect viral persistence, oscillations, and control. By incorporating spatial interactions, SIMCoV provides a parsimonious explanation for the dramatically different viral load trajectories among patients by varying only the number of initial sites of infection and the magnitude and timing of the T cell immune response. When the branching airway structure of the lung is explicitly represented, we find that virus spreads faster than in a 2D layer of epithelial cells, but much more slowly than in an undifferentiated 3D grid or in a well-mixed differential equation model. These results illustrate how realistic, spatially explicit computational models can improve understanding of within-host dynamics of SARS-CoV-2 infection.

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.

Finding and retrieving resources in unmapped environments is an important and difficult challenge for robot swarms. Central-place foraging algorithms can be tuned to produce efficient collective strategies for different resource distributions. However, efficiency decreases as swarm size scales up: larger swarms produce more inter-robot collisions and increase competition for resources. We propose a novel extension to central-place foraging in which multiple nests are distributed in the environment. In this multiple-place foraging algorithm, robots depart from a home nest but always return to the nest closest to them. We simulate robot swarms that mimic foraging ants using the multiple-place strategy, employing a genetic algorithm to optimize their behavior in the robot simulator ARGoS. Experiments show that multiple nests produce higher foraging rates and lower average travel time compared to central-place foraging for three different resource distributions. Time spent avoiding robot-robot collisions is not always reduced as was expected, primarily because the use of pheromone-like waypoints leads to more collisions when robots forage for clustered resources. These results demonstrate the importance of careful design in order to create efficient multiple collection points to mitigate the central-place bottleneck for foraging robot swarms.

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.

The complete collection of resources from a predefined search area is a challenging task for autonomous robot swarms. Because naturally-occurring resources are likely to be distributed in clusters, foraging robot swarms can identify and exploit these resource clusters to improve collection efficiency. We describe an ant-inspired robot swarm foraging system that searches for and collects resources from a variety of distributions, and a cluster prediction and exploitation algorithm that augments swarm foraging by directing robots to residual resources. By characterizing the cumulative resource collection time for a robot swarm foraging in a variety of clustered resource distributions, we can identify the relationship between the “clusteredness” of the distribution and the change in the resource collection rate over time. Experiments show that collection efficiency is most significantly increased when robots switch from ant-inspired foraging to focused exploitation of clusters after approximately 90% of resources have been collected. Not surprisingly, clustering algorithms are most effective when resources are highly clustered in the environment. This work demonstrates the feasibility of efficient, complete resource collection using simple, range-limited robot swarms programmed with ant-inspired foraging behaviors.

Central-place foraging is a canonical task in swarm robotics. For this task, robots are programmed to search an area for resources and aggregate these resources at a central location. Foraging can be instantiated in a number of real-world applications, such as hazardous waste clean-up, search and rescue, and in-situ resource utilization. We extend our prior work by using coevolutionary methods to evolve iAnt robot swarm foraging strategies in real robots and in real time. Each robot maintains a private agent-based simulation, which models the physical environment according to the robot’s own approximation of the realworld resource distribution. The robot uses a private genetic algorithm (GA) to evolve parameters for a central-place foraging algorithm (CPFA) which maximize the foraging success of the simulated agents; it then employs these evolved parameters as a foraging strategy in the real world. In addition to evolving individual foraging strategies, the entire swarm executes a distributed GA to evolve a population of resource distribution approximations that is shared across all robots. In this way, coevolution evolves both the foraging strategy and the resource distribution approximation for each robot. Over time, this allows the swarm to adapt its behavior to previously unknown environments.

Collective foraging is a canonical problem in the study of social insect behavior, as well as in biologically inspired engineered systems. Pheromone recruitment is a well-studied mechanism by which ants coordinate their foraging. Another mechanism for information use is the memory of individual ants, which allows an ant to return to a site it has previously visited. There is synergy in the use of social and private information: ants with poor private information can follow pheromone trails; while ants with private information can ignore trails and instead rely on memory. We developed an agent-based model of foraging by harvester ants, and optimized the model to maximize foraging rate using genetic algorithms. We found that ants' individual memory provided greater benefit in terms of increased foraging rate than pheromone trails in a variety of food distributions. When the two strategies are used together, they out-perform either strategy alone. We compare the behavior of these models to observations of harvester ants in the field. We discuss why individual memory is more beneficial in this system than pheromone trails. We suggest that individual memory may be an important addition to ant colony optimization and swarm robotics systems, and that genetic algorithms may be useful in finding an adaptive balance between individual foraging based on memory and recruitment based on communication.

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.

Distributed search problems are ubiquitous in Artificial Life (ALife). Many distributed search problems require identifying a rare and previously unseen event and producing a rapid response. This challenge amounts to finding and removing an unknown needle in a very large haystack. Traditional computational search models are unlikely to find, nonetheless, appropriately respond to, novel events, particularly given data distributed across multiple platforms in a variety of formats and sources with variable and unknown reliability. Biological systems have evolved solutions to distributed search and response under uncertainty. Immune systems and ant colonies efficiently scale up massively parallel search with automated response in highly dynamic environments, and both do so using distributed coordination without centralized control. These properties are relevant to ALife, where distributed, autonomous, robust and adaptive control is needed to design robot swarms, mobile computing networks, computer security systems and other distributed intelligent systems. They are also relevant for searching, tracking the spread of ideas, and understanding the impact of innovations in online social networks. We review design principles for Scalable Robust, Adaptive, Decentralized search with Automated Response (Scalable RADAR) in biology. We discuss how biological RADAR scales up efficiently, and then discuss in detail how modular search in the immune system can be mimicked or built upon in ALife. Such search mechanisms are particularly useful when components have limited capacity to communicate and when physical distance makes communication more costly.

Rapid advances in VLSI technology have increased the number of transistors that fit on a single chip to about two billion. In such complex designs, a primary design goal is to limit the power consumption of the chip. Power consumption depends on capacitance, which depends on the length of wires on the chip and the number of vias which connect wires on different layers of the chip. We use ant colony optimization (ACO) algorithms to minimize wirelength, vias and capacitance. ACO provide a multi-agent framework for combinatorial optimization by combining memory, stochastic decision making and strategies of collective and distributed learning by ant-like agents. This paper applies ACO to the NP-hard problem of finding optimal routes with minimum capacitance for interconnect routing on VLSI chips. The constraints on interconnect routing are used by ants as heuristics which guide their search process. We implemented ACO algorithms on both manhattan and non-manhattan routing architectures. The results are compared with several state of the art academic routers. The ACO routing algorithm was able to obtain an overall improvement of 8% in terms of wire-length, 7% in terms of vias and capacitance. Running times were longer than those routers, but very similar to the other router which is able to route all wires on all benchmark chips.