The search for new ways of teamwork for a clever swarm

New algorithms demonstrate how a swarm of the simplest robots can be made to work together as a whole.

In the laboratory of the Georgia Institute of Technology, physicists experiment with robots that look as if they were bought in an “all for $ 1” store. Robots cannot move in space or communicate with each other. Mostly they flap their arms like beetles upturned on their backs.

But if you assemble a lot of these devices together, you can get something from nothing: they push, shove and grapple with each other. And as a result, they begin to work as one.
')
Researchers are studying how to control such systems so that they function in a manner similar to a swarm of bees or an ant colony: each individual acts on the basis of the same set of rules, but several individuals can come together to demonstrate complex behavior without central control.

“Our approach is as follows: find out what is the simplest computational model necessary to achieve these complex tasks? Says Dana Randol , a computer science specialist at GeorgeTech, one of the project leaders. “We are looking for elegance and simplicity.”

Randal, as a programmer, approaches the task from the point of view of algorithms: what is the simplest set of instructions on the basis of which individual swarm units can work, based on the scarce data they can collect, will inevitably lead to complex collaborative behavior necessary for researchers? Last November, Randal and colleagues published an algorithm to ensure that an ideal particle swarm can move in a controlled manner.

Working with such robots, which scientists nicknamed "smartikly" [smarticles; smart - smart, particle - particle / approx. transl.] - part of the research in the field of the possibility of creation and utility of self-organizing robots. Other similar examples include droplet-sized robots being developed at the University of Colorado, “ kilobots ” swarms from Harvard University, and welmanoids from the Belgian laboratory. In many cases, the idea is to mimic a phenomenon that manifests itself in nature, for example, the highly organized movement of a decentralized ant colony or an unconscious self-programmed assembly of DNA molecules.

“We know what we want from a whole swarm, but in order to program it, it’s necessary to figure out what each of the agents should do individually,” said Melvin Gauci , a Harvard researcher working in group robotics . “The most difficult thing is between these two levels.”


Dana Randal and Dan Goldman at the Goldman Lab

Watch out leaders

Daniel Goldman is a physicist from Georgetach, leading an experiment with smarts. He is mainly interested in the physics of active granular materials capable of changing their shape. Among his slides for conferences there is a moment from the film “Spiderman 3”, which demonstrates the birth of the supervillain Sandman - separate grains of sand scattered across the desert are collected in the shape of a man. Smartikla is Goldman's way to test active granular materials in the laboratory.

“They give us the opportunity to use geometry to control the properties of the material. If you defocus your gaze, you can imagine that this bunch of smartikl is real material, ”said Goldman.

Smartikla have short limbs that they can wave back and forth. They react to light and sound of different frequencies. They can be programmed to change the speed of waving limbs in response to the actions of other smartikla, located in close proximity to them.

Smartikla can be made to perform several actions: put together (cluck together), expand (distribute) and move. These maneuvers can serve as the basis for performing more complex functions, but such tasks are also quite difficult to solve, since smartartics do not understand how they are located in relation to the whole group.

To understand the possibilities and difficulties associated with the programming of complex behavior arising from simple parts, it is worth bearing in mind what each individual smartkit knows. Not so much. He cannot see, his memory is limited, and everything that he knows about other smartkillers with whom he has to coordinate actions, he learns when confronted with his immediate neighbors.

“Imagine a person sitting at a rock concert with eyes closed,” said Joshua Damad, a computer science graduate student at the University of Arizona, who works on a smartart project.



One strategy may be to appoint a leader to control the swarm - but this approach is vulnerable. If the leader suffers, the whole swarm will fail. The other is to give each robot its unique task, but on a large scale, this approach is impractical. “It’s almost impossible to program 1000 robots individually,” said Jeff Dasek , a researcher at the Olin College of Engineering and a former member of the Harvard self-organizing systems research group who worked on swarms of underwater robots . "But when every member of the group works according to the same rules, your code does not change, regardless of whether you have 10 robots, 1,000 or 10,000."

The swarm algorithm has two properties. First, it is distributed, that is, it works separately on each of the particles of the system (how each nomadic ant performs the simplest set of actions depending on information obtained from the environment). Secondly, it includes an element of chance. This means that if, say, a nomadic ant, feels the presence of five other ants nearby, then with a 20% chance he will move to the left, and with 80% - to the right. Algorithms with randomness differ from deterministic algorithms, in which each stage is completely determined by the previous ones.

Accident may seem unnecessary for algorithms - after all, when implementing a procedure, you usually want to achieve a certain result. But chance has unexpected advantages for efficiency, which is why algorithms with chance are well suited for use in swarms.

Random Warranties

In 2015, Goldman and Randal discussed the possibility of finding the rules by which smartikla could work together as a whole. Randal realized that the behavior to which Goldman wanted to lead the swarm is very similar to the behavior of idealized particle systems studied in computer science.

“And I immediately thought: I know exactly what needs to be done,” said Randal.

For Randal, the behavior of smartiklov was reminded of a phenomenon modeled by computer scientists in many other contexts. One of the most famous examples is the emergence of segregated areas. In the late 1960s, economist Thomas Schelling wanted to understand how segregation occurs by region in the absence of some kind of central force that sorts people by skin color. He presented a hypothetical man looking at his neighbors and deciding whether to move based on how many neighbors look the same as him. When a person moved, Schelling moved him to a random place of settlement, where the algorithmic process of observation and decision-making was repeated. Schelling found that according to his rules, the appearance of segregation of residents is almost guaranteed, even if some people prefer to live in heterogeneous areas.


William Savoy, graduate student in Goldman's lab

Randal understood that smartikly in their swarm resemble people in Schelling's model. In both cases, the individual units must make a decision, not knowing their position on the global scheme (they only know what they see in close proximity). In the Schelling model, decisions can be made with an element of chance - if the neighbors are different from you, then there is a chance that you will move, and there is a chance that you will remain.

In 2016, Randal and colleagues published a paper where they described idealized particles living on a lattice and deciding whether to stay or move depending on the number of particles observed around the particles. The decisions made were probabilistic - the particles each time “threw” a weighted die for selection. Randall and his co-workers showed that if the weight cube was correctly assigned, a dense swarm could be guaranteed (just as Schelling could prove that if tolerance to diversity was assigned to the residents at the right level, segregation would necessarily appear). By adjusting the algorithm, they could also ensure that the swarm of particles would move in an expanded state.

The randomness of the algorithm helps particles in the swarm to avoid getting stuck in local seals when many isolated subgroups accumulate together, but the whole swarm is not sealed as a whole. Accident ensures that when small seals appear, some units will still decide to move to another place, and the process will continue until a general seal is reached. To avoid local seals, a little randomness is needed; much more is required to go from a globally compressed state to an extended one.

To the real world

Proving that particles in the theoretical world can, by performing a simple algorithm, achieve a certain behavior in a swarm is one thing. Implementing the algorithm in cheap, prone to failure, real smartclicks, clicking limbs in the box - is quite another.

“Our theory colleagues are thinking up how to program these things, but for the time being we are at the very beginning of the way, and we cannot say that these schemes were transferred directly,” said Goldman.

One of the problems was to make smartikly move together. At first, when the researchers concluded smartikla in a limited space, this group simply jerked by chance. But once, when physicists observed this chaotic motion, one of the smartphones died of a battery. Goldman and his colleagues noticed that the swarm suddenly began to move in the direction of a fixed unit. Researchers reported this unexpected discovery to theorists, and they seized on this hint. The work led to the creation of a new version of the algorithm, which allows an idealized swarm to always move in a given direction.

Little by little, computer experiments and physical experiments are drawing closer. The researchers hope to prove theoretically in the end that the basic algorithm implemented by the common method in a large swarm of small, cheap robots is guaranteed to lead to the desired behavior of the swarm.

“We would like to achieve a state in which we would not simply detect some phenomenon when a battery dies,” said Damad. “We want it to be something of a deliberate achievement.”