Ant Colony: Inspiration for algorithms shaping the future from mathematics to robotics and self-driving cars

posted in: Art. Nature. Technology | 0

Emergent behavior in complex adaptive Ant colony: Inspiration for algorithms from mathematics to robotics and self-driving cars.

Many of us view ants as useless and annoying insects. Once you observe and study the behavior of ants you will see they are one of the most fascinating and collectively efficient, adaptive, and smart creatures; and modeling their behavior can lead to science fiction like world changing discoveries and innovations in a multitude of applications.

Some ants can carry over 100 times their own body weight and change the size and shape of the pads on their feet depending on the load they are carrying. Astonishing behaviors emerge from collective groups of ants interacting with each other and the environment.

Studies aimed at understanding and modeling the behavior of ants and other insects and species such as fish and birds can provide inspiration for the development of algorithms for solving difficult mathematical and computational problems. Some applications include network routing, robotics, and urban transportation systems. Imagine groups of robots that can communicate with each other to achieve a certain goal, adapt to the environment, and change their shape depending on the environment, whether they have to run, jump, swim, fly, or walk!

More than 10,000 known ant species exist around the world. Ants are adaptive and social creatures, they communicate by using chemicals known as pheromones that can alert others of danger or lead them to a food source. One ant by itself is not smart, however, when you have a group of ants interacting with each other and the environment, complex outcome is produced. This is a phenomenon known as Emergence. In addition, Stigmergy occurs when elements of the system interact indirectly through the environment. This behavior is also known as Swarm Intelligence, it consist typically of a population of simple agents interacting locally with one another and with their environment.

Imagine if we could mimic this behavior by developing a swarm of self-organized adaptable robots, sensors, connected objects that can be released to accomplish specific tasks, search and discover the physical space, be used for search and rescue, and wildlife conservation initiatives, or a swarm of driverless cars autonomously finding the shortest path for their routes!

In summary, studies of ants’ behavior have shown that: Ants drop pheromones as they move.   Ants have preference to follow high pheromone trails. More pheromones will accumulate on the shortest path.  Ants use stigmergy to find the shortest path between home and food. Pheromone deposit left by ants manifests stigmergy. When ants face an obstacle between nest and food  they choose to turn left or right with equal probabilities.  After some time period all ants have chosen the shorter path.

In grad school, I became fascinated with Artificial Intelligence and decided to research Ant Colony Optimization for my theses. I used an algorithmic approach to simulate ant colony behavior and focused on the Stigmergic Emergent behavior in complex adaptive ant colony.

I experimented with interactions of multiple parameters including multiple food sources, obstructions, two types of pheromones, and use of full grid.

Parameters of the model:

    • Number of ants
    • Grid size
    • Ant’s pheromone level and pheromone capacity
    • Pheromone capacity and level are changed by the same multiple.
    • Single vs. multiple food source.
    • Distance between food and home
    • No obstruction versus obstructions

 

Some questions that I addressed:

Does it help to have more ants? How many ants is enough?  Should ants have large stores of pheromones for their travel or is it better for them to have small stores? What factors must be adjusted when the distance between home and food changes? What is affected when obstructions are introduced into the grid?

 

Simulation Findings: If one parameter of the model changes, we can produce stigmergic behavior by making some appropriate changes in the values of other parameters.

  • The environmental factors, such as, place of food, place of home, obstructions, single or multiple food sources, or the grid size affect behavior, but they are not the determining factors.
  • Internal variables are the determining factors.
  • Pheromone capacity and the number of ants are internal determining variables.
  • Distance between home and food is the most important environmental variable.
  • As the home-food distance increases, both the pheromone capacity and the number of ants must be increased to achieve convergence to stigmergic behavior.
  • For each value of the home-food distance there is a minimum pheromone capacity that could lead to convergence.
  • Although more ants are required when the distance increases, no specific mathematical   formula between distance and number of ants was observed.
  • For each distance multiple, a minimum threshold for the number of ants is required for convergence.