Hungarian algorithm and drone swarm

Researchers at the Department of Biological Physics at Eötvös Loránd University have discovered how flocks of birds can overcome the theoretical difficulties of moving in a group and can now coordinate the fast-reacting, yet harmonious co-movement of more drones than ever before with a solution from nature.

The study of their findings was the cover story of the Royal Journal of the British Scientific Society’s Interface journal over the summer.

Group movements, local interactions

One of the most spectacular performers of the group movement is the flocks of birds. The basic question of the research of collective behavior, which is becoming more and more important nowadays, has long been, among other things, the subtle ways in which the movement of individual birds evolves the dance of huge swarms. One of the founders of the field is the physicist Tamás Vicsek, who for a quarter of a century published the model named after him today, and with this he was the first to describe the group movements in the living world mathematically.

The phenomenon of group motion is multifaceted, produced by a wide variety of living beings, occurring on a wide variety of size scales, that is, using the usual terminology in statistical mechanics: universal. This universality forces physicists to explain the formation of the pattern in a generalized mathematical form, using simple models, ”said Vicsek, a full member of the Hungarian Academy of Sciences, a researcher in biological physics and the formation of complex shapes in nature.

According to Professor Vicsek, one of the most important features of the models is that the interactions are limited to the information available in the tight environment, i.e. local, yet lead to system-wide, i.e. global behavior. In the model bearing his name, for example, it is enough for each individual to look around and fly in the average direction of movement experienced in order for the entire swarm of up to ten thousand to arrange and march together. Such so-called agent-based models, in which simple rules prescribe unique behavior, have progressed in recent decades in describing complex systems — as agents can be simulated one by one in increasing masses as computing capacity increases.

Over the years, more and more laws of group movement have become clear. Vicsek won an ERC tender in 2009 with the aim of developing an autonomous robot start with his research team, building on the new results achieved by modeling group motion. The award for the largest scientific source available in the European Union at the time was that the calculations that a bird would make for its flight would, at the time, be thought to be able to be developed by a robotic on-board processor with the advancement of technology. this resource.

The first stage of the research was therefore the observation of the living world. The result of the method developed by motion analysis of pigeons flying with GPS positioning is demonstrated by the following video:

Vicsek’s research group also used what he learned from the animal kingdom to develop autonomous drones moving together in a swarm. The drone-based research results of the Department of Biological Physics of ELTE and the Research Group of Biology and Statistical Physics of MTA-ELTE entered the world for the first time in 2014, long before today’s obvious drone era. A research team led by Vicsek created the world’s first ten-unit outdoor self-organizing quadrocopter fleet.

Evolutionary algorithms

The researchers used biologically motivated algorithms to create group drone control and then the principle of evolution to optimize them. Drones have been developed that fly in large swarms to communicate with each other towards their common goal, avoiding obstacles in groups, just like birds.

Gábor Vásárhelyi, head of the robotics laboratory at the Department of Biological Physics of Eötvös Loránd University, said that the control algorithm complements the basic components of models describing the group motion of living things with drone-specific motion characteristics and a certain degree of intelligent route planning. Many parameters of the complex algorithm were optimized for the task using an evolutionary algorithm run on ELTE’s supercomputers, creating the second, more advanced prototype of the drone swarm, from which the cover story of Science Robotics in 2018 revolved.

At the same time, the fleet drew attention to another problem that seemed insoluble. When more than thirty drones tried to move together indoors, congestion developed at the walls, the movement became dangerous.

“Think about it: the first robot to fly to the wall is trying to slow down or turn, but for him, the dominant stimulus is not the turn, but the herd spirit progression, as its neighbors are decisively – without seeing the wall – still going straight. If basic individual behavior wants to adjust to the average speed, the group’s inertia inevitably increases. If the group size is small, this is not a big problem, when approaching a wall, each individual perceives the wall roughly at the same time, so their joint turn does not endanger anyone. However, if the group size is large, the former must either go against the will of the group to turn or slow down, or obediently move on with their peers. They can choose in Hungarian to hit their peers or rather the wall, ”Vásárhelyi explained.

So does it all depend on the slow spread of change in the group ?

“Apparently yes. But it’s actually deeper, ”says Boldizsár Balázs, a doctoral candidate in the research group, who is the first author of an article presenting the current results. “There are ways to tune the behavior so that instead of the average – and vice versa – the deviation from it is taken by each individual. So the change runs smoothly through the swarm. The only problem is that everything can be considered a change. Whatever disruption happens at one point in the system, it reaches everyone. But there are always disturbances: a little gust of wind here, a sizzling flutter of wings there. Such a hypersensitive team can’t do a single meter, it jerks in a place entangled in itself, and even if it starts, it just taps ”.

Stable and reactive

Physicists have related this problem to one of the basic contexts of statistical mechanics, the fluctuation-dissipation theorem. According to this, two important properties of a physical system – how much its states fluctuate when left alone and how intensely it reacts to an external effect – mutually determine each other.

Certain living systems have been forced by evolution to somehow solve what the inanimate matter is mathematically demonstrably incapable of: a flock of birds is stable but also responsive. They march up to a hundred miles in an orderly fashion, yet when a predator appears, they vanish almost as an entity in a batting.

Researchers have been looking for the simplest elementary process that life can live through to be tough but not stubborn; to be flexible so as not to lose the target. They came to the conclusion that the key is the ability of individuals to distinguish, moreover, to correctly distinguish each other’s momentary significance, and to adapt to this, to create temporary hierarchies led by signifiers.

The mathematics of intentional attribution

There are several ways to do this. When an individual receives information that is important to everyone, he or she can make it known to others with an active signal (howling, waving), but it is also possible that a sudden, instinctive, abnormal change in his movement is the key stimulus for others. With the right filters, you can tell if the perceived change is worth spreading or suppressing. In line with this, the flock of birds can still fly with a fast reaction time.

The principle that every individual attaches intent to the behavior of peers is widespread among humans and can be transferred to robots. In transport, for example, the use of index and brake lights is one such tool for both stability and fast response time. But not only moving in physical space, but also in the thousands of dimensions of human social behavior, the discriminatory behaviors necessary for effective harmony appear. If we think it’s significant what we want to say, we raise our voices or tie a tie, depending on the situation. But we also have a built-in sign, the lamp fever, which unmistakably signals to others that what we are just saying is important to us. An important step is that our environment then even decides if it is for him or her.

Thanks to the same principle, i.e. adaptive, information hierarchy-based leadership, the research team has overcome previous limitations and is now able to fly more than fifty drones in natural harmony, and based on computer simulations, the new paradigm can smoothly coordinate thousands of robots.