The perfect swarm

Dr. Jelmer van Ast, who defended his thesis last Tuesday at the faculty of Mechanical, Maritime and Materials Engineering, is one of those Delft researchers who mimic nature to solve complex mathematical problems. At the Delft Centre for Systems and Control (DCSC), he developed an algorithm based on swarm intelligence.

“When you look at fish, birds and ants, at first glance you would think that there must be some intelligent leaders within the groups,” Van Ast says. “But these animals are not intelligent; it’s the swarm that’s intelligent.”
Or, as kindred spirit, dr. Justin Rice (who also worked at DCSC and who defended his thesis one week before) puts it eloquently in his thesis introduction: “No one has ever accused a herring of being intelligent, but a school of herring are certainly brilliant when dodging an attacking orca or porpoise and the most advanced distribution control methods in existence can’t compare to their performance for controlling a 3-D, nonlinearly coupled, dynamically changing configuration of fish.”

Swarms owe their intelligence to simple sets of rules that each animal follows. Each fish, for instance, observes its neighbours and keeps a certain distance from them, allowing the group to function as one entity.
As for ants, they find the shortest paths to food by communicating through chemical trails, called pheromone trails. A shorter path results in a faster accumulation of pheromones, which persuades other ants to choose that same path as well.

Basically, what the ants are doing while foraging is what in mathematics is called solving combinatorial optimisation problems.
Van Ast: “The exact same principles of swarm intelligence in nature can be used in engineering swarms that can be of use to humans. The basic idea of an engineered swarm is that it consists of a set of cooperating autonomous individuals, also called agents. These agents try to satisfy their own objectives through cooperation with other agents. Communication and coordination are central to achieving this, but are often limited to a certain range, so that cooperation between agents only takes place locally.” A growing number of mathematicians are working with ant colony optimisation models. These models come in handy for optimising navigation systems for cars, in which the cars communicate with each other to coordinate their movements and route choices. The cars are thus the actors instead of the ants. Another application is optimising the routing of internet data traffic.

Van Ast elaborates on this theme. He developed a model in which a virtual space is subdivided in squares, like a chessboard. The actors move through this space and communicate to each other what obstacles they encounter. By adding more actors it’s possible to increase the calculating speed.
The researcher also added fuzzy membership functions to the model, which is a way to interpolate data very efficiently. This makes it possible to make very fast and accurate calculations. Normally when you subdivide the space in smaller squares, in order to obtain a higher precision, the time it takes to perform the calculations increases exponentially. By adding fuzzy membership functions, the calculation time does not increase exponentially.
In the long run, Van Ast believes, ant colony optimisation models could be useful in situations involving natural disasters. “Swarms of robots may be deployed to analyse the situation in inaccessible places, such as in a tunnel filled with smoke, to localise the victims and coordinate rescue operations.”
 

Over belangstelling hadden de Beunhazen afgelopen weekeinde niet te klagen tijdens de Delftse Loop der Dingen bij Lijm en Cultuur. Voorafgaand aan de Loop beloofden de drie IO’ers te gaan ‘beunen en knutselen’. Ze zouden veel sloopmateriaal inzetten en zorgen voor vermaak. Ze hadden geen woord te veel gezegd. Geïnspireerd op de filmpjes van de Duitse Lauf der Dinge op Youtube, knutselden ze van ruw materiaal een imposant bouwwerk in elkaar. Grof werk in de vorm van bijlen, een fiets en hout werd gecombineerd met fijnere onderdelen als een muizenvalletje, touwtjes, slangen, flessen en een tere ballon. De installatie van de Beunhazen was onderdeel van een lange keten bouwsels, die als doel hadden om een beweging als een kettingreactie door te geven.