April 15, 2021

Ode to the ants, muses of the algorithms | Trends

Ode to the ants, muses of the algorithms | Trends

The importance of the contribution of ants to computer science is inversely proportional to the insignificance of these insects. The Italian researcher Marco Dorigo began to realize in 1992 and baptized the phenomenon as "the ant system". We've all seen it in action, when we forget some food on the countertop and the condemned bugs do not just find it, but they lead the feast to the rest of the anthill. In the kitchen they are a problem. In computing, the solution.

The fact is that in addition to finding food, these hymenopterans make sure to attract the rest of their congeners by the shortest route. The key is the pheromones that leave in their wake: the travel time is longer where the trail is lighter, so the ants discard little by little the most extensive routes to opt for those where pheromones are more easily detectable .

By the way, if seeing one of these tingling columns crossing the floor of your house does not seem spectacular enough, try to be seated when you see the next GIF. Legionary ants are capable of doing the same, but in vertical.

With such formidable muses, the result of Dorigo's research was consolidated in what we know today as ant colony optimization algorithms. The resulting models are used to solve problems of optimization and distributed control and have applications by land, sea and air: routes for vehicles, planning landings of aircraft, detection of borders in pictures, mining of data, plotting trajectories safe for boats and even analysis of long DNA sequences. And all inspired by the coordination of the ants in their collection routes.

But the great contribution of the tiny insects does not end here, and Dorigo was responsible for doing them justice in a book about the topic. Their methods of classifying offspring, which consist of compacting smaller eggs and larvae in the center and larger ones in the outside, have been applied in robotic systems capable of constructing clusters of objects without the need for centralized control.

The division of labor of the colonies, with workers who specialize in specific tasks but maintain the necessary flexibility to adapt to others, has been key in problems of distribution of resources in changing environments. Even his way of transporting a bee among all, which is for its dimensions what for ours, a car, has found applications beyond the anthill. The problems of cooperative transport, where several robots must, for example, push or pull a box to a specific destination can be addressed from this point of view.

How many surprises does the brain of an ant harbor? God knows. For now, it seems that they fit even a pedometer. In 2009, researcher Mathias Whittlinger showed that desert ants have their own system to trace their return routes, since pheromones are not so persistent in sandy terrain. Whittlinger's proposal is that can you tell.


Source link