A pinboard by
Chris Reid

Research Fellow, Macquarie University


Like Voltron, ants can join together to increase their power. I want this ability for robot swarms.

How do nerve cells network to form a brain? How do ants build bridges to form smooth highways for their traffic? How do competing economic firms interact to form a system of global trade? These are all examples of complex systems; where groups of simple interacting units produce emergent, complex behaviour at the group level. Complex systems are all around us, but they are difficult to study; an individual nerve cell can be removed from a body and observed, but in doing so we have removed the cell from the very system we seek to understand. Our inability to observe the precise behaviour of individual units as they interact with their neighbours is a major impediment to understanding how complex systems function.

I use biological complex systems such as ant colonies, honey bees and slime moulds to circumvent this problem. These systems provide an extremely important resource for studying the properties of complex systems in general, because they allow me to design experiments to uncover the links between the behaviour of individual agents and the behaviour of the entire system. My work is naturally interdisciplinary, involving collaboration with biologists, engineers and mathematicians, and a combination of field work, lab work and computer modelling.

One of my main aims is to understand self-assembly. Self-assembly is the ability of certain species of ants to use simple, local behavioural rules to join their bodies together, spontaneously building structures such as hanging chains that act as rope ladders, pulling chains to roll leaves together to form nests, and bridges that span gaps and act as highways for foraging traffic. Made entirely of ants, these structures allow colonies to perform tasks that are impossible for individuals to do alone.

My research has two aims; 1) developing better models for understanding complex systems, such as tissue development and wound healing, and; 2) developing new control algorithms for swarms of simple robots. Just like the ants, these robot swarms will be able to self-assemble into functional structures in any environment, adapt to environmental changes, and maintain functionality when much of the group is lost or disabled, making them ideal for exploration and search-and-rescue operations. My approach will transform our understanding of other complex systems too, such as in finance (interacting economies), disease (tissue development, protein folding) and technology (autonomous vehicles, nano-assembly).


Army ants dynamically adjust living bridges in response to a cost–benefit trade-off

Abstract: The ability of individual animals to create functional structures by joining together is rare and confined to the social insects. Army ants (Eciton) form collective assemblages out of their own bodies to perform a variety of functions that benefit the entire colony. Here we examine ‟bridges” of linked individuals that are constructed to span gaps in the colony’s foraging trail. How these living structures adjust themselves to varied and changing conditions remains poorly understood. Our field experiments show that the ants continuously modify their bridges, such that these structures lengthen, widen, and change position in response to traffic levels and environmental geometry. Ants initiate bridges where their path deviates from their incoming direction and move the bridges over time to create shortcuts over large gaps. The final position of the structure depended on the intensity of the traffic and the extent of path deviation and was influenced by a cost–benefit trade-off at the colony level, where the benefit of increased foraging trail efficiency was balanced by the cost of removing workers from the foraging pool to form the structure. To examine this trade-off, we quantified the geometric relationship between costs and benefits revealed by our experiments. We then constructed a model to determine the bridge location that maximized foraging rate, which qualitatively matched the observed movement of bridges. Our results highlight how animal self-assemblages can be dynamically modified in response to a group-level cost–benefit trade-off, without any individual unit’s having information on global benefits or costs.

Pub.: 23 Nov '15, Pinned: 25 Aug '17

Decision-making without a brain: how an amoeboid organism solves the two-armed bandit.

Abstract: Several recent studies hint at shared patterns in decision-making between taxonomically distant organisms, yet few studies demonstrate and dissect mechanisms of decision-making in simpler organisms. We examine decision-making in the unicellular slime mould Physarum polycephalum using a classical decision problem adapted from human and animal decision-making studies: the two-armed bandit problem. This problem has previously only been used to study organisms with brains, yet here we demonstrate that a brainless unicellular organism compares the relative qualities of multiple options, integrates over repeated samplings to perform well in random environments, and combines information on reward frequency and magnitude in order to make correct and adaptive decisions. We extend our inquiry by using Bayesian model selection to determine the most likely algorithm used by the cell when making decisions. We deduce that this algorithm centres around a tendency to exploit environments in proportion to their reward experienced through past sampling. The algorithm is intermediate in computational complexity between simple, reactionary heuristics and calculation-intensive optimal performance algorithms, yet it has very good relative performance. Our study provides insight into ancestral mechanisms of decision-making and suggests that fundamental principles of decision-making, information processing and even cognition are shared among diverse biological systems.

Pub.: 10 Jun '16, Pinned: 21 Nov '17

Ant Colony Optimization for the Design of Small-Scale Irrigation Systems

Abstract: The optimal design of sprinkler irrigation systems is a complicated nonlinear programming problem that is related to the performance of the system and meanwhile an economic problem to farmers in developing countries. Ant colony optimization (ACO), a meta-heuristic algorithm with the strategies inspired by foraging ants, was considered. Exactly an Ant Cycle System was proposed to solve this problem. The performance of ACO was compared to that of Genetic Algorithm (GA), and the optimal results were further validated by field tests on four small-scale irrigation systems. In the optimization model, the objective function was minimizing the specific energy consumption subject to the constraints of pipe diameters, number of sprinklers and working pressure of the end sprinkler along the pipeline and pump-pipeline cooperation conditions. In the design of ACO, head loss between adjacent sprinklers was introduced in the heuristic function to represent the distance between two cities in a Travelling Salesman Problem (TSP). And the fitness composed of the specific energy consumption dealt with penalty function was taken instead of the total length of a route in the pheromone updating. The results indicate that the specific energy consumption has been decreased in average by 12.45 % through ACO, 10.27 % through GA and 11.27 % from field tests compared to that in the initial configurations with irrigation uniformities higher than 75 % in the field tests. ACO implementation outperforms genetic algorithm in efficiency and reliability especially in larger systems. The ACO may provide a promising approach for the optimization of irrigation systems.

Pub.: 04 Mar '15, Pinned: 22 Nov '17

An improved ant colony optimization algorithm with fault tolerance for job scheduling in grid computing systems.

Abstract: The Grid scheduler, schedules user jobs on the best available resource in terms of resource characteristics by optimizing job execution time. Resource failure in Grid is no longer an exception but a regular occurring event as resources are increasingly being used by the scientific community to solve computationally intensive problems which typically run for days or even months. It is therefore absolutely essential that these long-running applications are able to tolerate failures and avoid re-computations from scratch after resource failure has occurred, to satisfy the user's Quality of Service (QoS) requirement. Job Scheduling with Fault Tolerance in Grid Computing using Ant Colony Optimization is proposed to ensure that jobs are executed successfully even when resource failure has occurred. The technique employed in this paper, is the use of resource failure rate, as well as checkpoint-based roll back recovery strategy. Check-pointing aims at reducing the amount of work that is lost upon failure of the system by immediately saving the state of the system. A comparison of the proposed approach with an existing Ant Colony Optimization (ACO) algorithm is discussed. The experimental results of the implemented Fault Tolerance scheduling algorithm show that there is an improvement in the user's QoS requirement over the existing ACO algorithm, which has no fault tolerance integrated in it. The performance evaluation of the two algorithms was measured in terms of the three main scheduling performance metrics: makespan, throughput and average turnaround time.

Pub.: 26 May '17, Pinned: 22 Nov '17