Search Algorithm Inspired by Arboreal Ant Trail Networks

Innovation: Academia

Stanford

2017

Image: Prince Patel / Unsplash / CC BY SA - Creative Commons Attribution + ShareAlike

Compute

Computation allows an organism to take in and process information to make decisions. Whether it be calculating how fast prey is moving or deciding where to build a nest, computation is an important part of an organism’s life.

Search this Function

Respond to Signals

To interact with its environment, a living system must not only sense a variety of signals, but also respond to them. To be energy- and material-efficient, those responses must be appropriate to the signal. This generally requires sensing thresholds to trigger an appropriate level of response (for example, hiding under a shrub versus running away to avoid a predator). Response strategies are tied to a specific signal and often have a response threshold, which determines how strong a signal must be to warrant expending energy to respond. One example is a plant that lives in arid regions in South Africa. Its seed capsules remain closed until rainfall triggers them to open to release the seeds. But the plant only responds to a second rainfall, thus protecting against releasing its seeds before there is enough sustained water for them to grow.

Search this Function

Coordinate by Self-Organization

To create and maintain a healthy community of individuals and ecosystems requires that living systems coordinate their activities. Coordination doesn’t necessarily mean that there’s a leader orchestrating what happens. In nature, coordination is usually achieved through self-organization. In a flock of geese flying in a V-formation, for example, there’s no lead goose controlling where all of the others fly. The flock uses this formation because each goose gains energy from air vortices created by the goose in front of it. The lead goose doesn’t gain that benefit, so when it tires, it moves back and another goose takes the front position.

Search this Function

Coordinate Systems

Nature is full of systems that work in harmony by following simple rules that lead to complex behavior, such as fish swimming in a school or migrating grasshoppers flying in swarms. Coordinated behavior is also observed in how a slime mold grows, how our own neural network functions, and how some animals vote on where to live or move.

Search this Function

Algorithm from Stanford is parameterized by field data enabling it to quickly fix network disruptions.

Benefits

Efficient
Systematic
Adaptive

Applications

Search engine optimization
Utilities

UN Sustainable Development Goals Addressed

Goal 11: Sustainable Cities & Communities

The Challenge

Sampling methods used in many probability-based algorithms do not track previously sampled components. This methodology leads to inefficiency because the program cannot remember what it has already done and could end up repeating the process.

Innovation Details

The search algorithm is developed using field data based on ant behavior. It is a distributed algorithm in which there is no centralized controller but rather individual agents monitoring the system. The algorithm efficiently circumvents network disruptions using fewer computational resources, which increases efficiency.

Biomimicry Story

Arboreal ants, such as the arboreal turtle ant, maintain trail networks that connect their nests to their food sources. If a trail is disrupted, they retrace their steps and follow the next most efficient path at the previous junction. The ants leave pheromones as they walk the paths, but the chemicals slowly evaporate, enabling the other ants to find the most recently used path.

See Related Content

two yellow gold ants walk diagonally down a tree branch against a blurry green background

Biological Strategy

Ant Colonies Respond Quickly to Distribute Food

Rock ant

Ant colonies distribute food effectively and safely after famine using a decentralized response to quickly spread food.

a red ant emerges from an underground colony surrounded by sand and rock

Biological Strategy

Ant Colonies Speed Information Flow

Red harvester ant

Red harvester ant colonies speed information flow by varying levels of connectivity.

References

Journal article

A distributed algorithm to maintain and repair the trail networks of arboreal ants

bioRxiv

embedly preview

AskNature