“ A group of little robots who can't see the wall or know where they are, only exchange numbers with neighbors around them to determine the shape of their location.
Recently, the study was published in the internationally renowned journal Science Robotics, and researchers from institutions such as the University of Paris-Westphalia, Sorbonne University, the University of Tokyo, and the University of Waterloo have proposed a new framework called spectral swarm robotics, SSR.
Group robots have an old problem. The structure of a single robot is simple, often without reliable positioning and measurement sensors, and computing and memory are limited, while methods such as positioning and mapping (SLAM) cannot be used.
The idea behind this paper is that robots only interact locally, estimate the constancy of the Laplace spectrum using simulated scattering, and then classify the locations using this value.
01.
From listening to drums to clustering robots
The study was inspired by the mathematician Kac's classic 1966 paper Can a drum hear the shape of a drum? The question and subsequent studies suggest that the drum's inherent vibrational frequency, the spectrum of the Laplace algorithm on that shape, contains a large amount of geometric information.
The difficulty is that group robots do not have a "God's point of view" and each robot can only communicate with its nearby neighbors. Under fully distributed conditions, each robot is allowed to estimate the Lapp value locally, which has never been possible before.
Intuitively, information diffusion is greatly influenced by the slow shape: in a circular disk, heat can diffuse evenly in two-dimensional directions; in a thin oval, the diffusion is mainly limited in one direction. The better the shape of the connectivity, the larger the λ2; the shape of the information "bottle" such as a circular circle, the smaller the λ2.
This study compares the seven-shaped continuous Laplace arithmetic and the three-shaped Laplace arithmetic, and finds that a randomly scattered graph in the shape matches the characteristic vector and the continuity well, and that λ2 is very close after integration.
02.
Three more mathematical tricks to get each robot to calculate λ2 by itself.
The practical approach is this: each robot initiates the internal state as −1 or 1, after which each round is adjusted to the average value of the neighboring state, equivalent to the entire cluster in simulation of thermal diffusion.
This process can be broken down into the index decay superimposition of each characteristic model. In order to derive only λ2, the team used three techniques.
Zero-average technique: Set the average of the initial state to 0, and the first model disappears.
Disappearance Technique: The higher-order model decays faster, leaving only the one corresponding to λ2 after a period of time.
For numerical tricks: The absolute value of a state is a pair of numbers, and the problem becomes a linear equation that can be calculated locally, with slope −λ2.
In this way, each robot can make a local estimate of λ2 by observing its state decline as quickly as possible.
A single estimate noise is large, so the robot randomly navigates a segment, replaces neighbors, re-measures, and simultaneously runs a three-group propagation process each round. The estimate value is generated by reaching a global consensus with the neighbors repeatedly on average.
The entire algorithm does not require location, mapping, wall perception, global communication or centralized computing.
03.
A scaling law: the number of robots and the perceived radius should be evenly matched
The team first tested in a simulation using a maximum of 550 robots, and the test subjects were seven shapes.
At the end of the propagation, the clusters are stably divided into two regions opposite the symbols, with different shapes and convergence rates. After 30 iterations, the correct identification rate increases significantly, increasing from 66% to 94%, for example, on the disc.
What follows is a key finding: too few robots perceive too many hours of radius, and communication graphics break into several isolated islands; when too many robots are too large, each robot's neighborhood is close to "full connection" and does not reflect geometric details.
The team defined the coverage rate α = Nπσ2/S (S) as the surface area) and found, through quantitative analysis and simulation, that the optimal configuration is concentrated on the dual curve α = 17. When α is less than 7.5, the graph begins to break up into multiple connections; when α is higher than 32, the graph is overconnected, leading to numerical instability.
In better ranges, the classification accuracy of the r1 region is 100% and the r3 region is 86%. Furthermore, the convex shape of a circular disc transmits information at about 10 times the speed of a circle.
The team also compared averages, degree distribution statistics, and general consensus convergence times as baselines, indicators that could not be shaped like λ2 to stabilize regions in different regions.
04.
In two real-world tests, Pogobot took 100 percent.
The real experiment used two platforms.
Kilobot is a commonly used platform in the field of group robotics. It communicates at a distance of 85 millimeters, with an effective speed of about 5 bytes/second after a message collision, and without a location and speed sensor.
Pogobot is a new platform launched by the ISIR of Shandong University, with a communication distance of 135 millimeters and a maximum of 120 20 to 100 bytes per second of messages, which is about 30 to 500 times the speed of the Kilobot.
The team chose more demanding conditions: the two platforms used 25 robots, each running only one iteration, to distinguish between the disc and the circle.
The results showed that Kilobot's experimental accuracy was 73% and simulation was 95%; Pogobot's experimental and simulation accuracy were 100%.
In terms of speed, the Pogobot variation (which includes pre-expansion) is about 5 minutes, and the Kilobot is about 79 minutes, which is about 15 times the difference.
In terms of robustness, it is only necessary to adjust one parameter, namely how long a neighbor's message is retained locally. This parameter is not adjusted, and the accuracy rate may fall from 100% to 31%. The robot's internal clock can be synchronized with each other via the message, but if the clock deviation within the neighborhood reaches a few times that of t, there is serious numerical instability.
The significance of this study is that it demonstrates that robots with only the most basic perceptual and computational abilities can obtain the global information that was originally needed for centralized computation through local interaction. By repeatedly exchanging a number between robots, the spectral characteristics of the entire cluster can be read from the spread slowly, the whole process does not depend on location, map or global coordination. The study also notes that an error update in a gradient-based method can be transmitted along the cluster layer, while the spread process gradually smooths out temporary errors in the localization as the information spreads.
The main contribution of this work was to establish the cluster of spectral robots as a research direction: clusters could use the spectral nature of their interacting graphs as a basis for perception and control, calculate with their own connecting structures, extract universal variables from local exchanges, and adapt spatial structures and functions to the environment accordingly.
The link is as follows: