Error Diagnosis in Robot Swarms

In the first semester of my graduate research in Prof. Carlo Pinciroli's NEST Lab into swarm error diagnosis, I treated the 1,000 Kilobit communication error case from Gauci and Ortiz's "Error Cascades in Collective Behavior." These robots were stationary transmit/receive robots arranged in a pattern executing a one-hop gradient algorithm to determine the number of robots between each and a designated source.

My research focused on the finding that swarm algorithms, which are often touted for requiring low computational power or minimal data manipulation, can need very expensive diagnosis remedies, especially if the algorithm is prone to error cascades.

I worked with the malfunctioning Kilobot swarm in a simple Python simulation I created for the project, where the swarm suffered from constant, random hardware errors in affecting communication in a cascading manner.

The goal of my research is to create a generalizable algorithm that preserves the swarm paradigm of equal skill and distributed information.

The algorithm developed to treat this problem, chosen as a starter problem, used the principle of an edge detection filter to determine if the robot resided on a disturbance in the swarm distance information (which can be plotted as a smooth gradient). This required only knowledge of transmitted data from the robots immediately around the robot examined. This then identified a cascading lists of robots to perform a diagnostic, which eventually resulted in isolating source robots, which could be erroneous or the correct source. In this way, computation time is reduced, by not requiring the entire swarm to run what in this case we treat as a "full diagnostic."

Due to the nature of the problem and the low level of data shared, the robots are required to self-detect certain errors, which could be a topic for future work, as it is preferable to determine a faulty robot exogenously.

The algorithm works in the following manner, with a matched-neighbor heuristic:

The robots are treated as pixels in an image, with values varying based upon the distance from the source node (their “rank”). Robots independently process their data.

1. Robots form a list of robots that broadcasted a lower rank (their “parents”). Next, a generic edge detection convolution to the robot’s rank relative to its neighbors. This is broadcast.
2. Robots determine whether their edge value matches that of any of their neighbors. If true, the robot and all its parents are marked as suspicious from the perspective of that robot.
3. Robots marked as suspicious are investigated. If a robot has no parents and is of rank 0, it is labelled the erroneous source, otherwise, its parents are investigated if not already cleared of suspicion.

The simulation was run with a prescribed number errors, evenly spaced in time, and the position of created errors within the swarm modeled by uniform, Gaussian, and bimodal distributions to assess the algorithm's performance in general, with errors concentrated at the center of the swarm, and with errors concentrated at the edges.

Across uniform and Gaussian error distributions, and for all tested swarm sizes, the algorithm achieves an average success rate of about 94.61% with a 1.65% standard deviation in detecting and diagnosing errors.
When examining errors classified as “general errors” (errors not located at swarm borders or edges), the success rate is higher, at approximately 96.46% with a 0.79% standard deviation.
For “border errors” (errors adjacent to detected gradient borders), performance slightly declines, with an average success rate of about 94.96% and a 1.05% standard deviation.
For “edge errors” (errors located at the edge of the swarm), the algorithm’s performance is weaker, averaging around 83.56% success with a 3.27% standard deviation. As the percentage of injected error increases, both the average success rate for edge errors tends to drop and the variability in success rate (the distribution width) increases.
Under a bimodal error distribution scenario, where errors are concentrated toward the edges, the algorithm’s success rate falls significantly. The mean success rate in these cases is approximately 55.91% with a 7.85% standard deviation. This distribution consistently yields lower and more variable success outcomes compared to the uniform and Gaussian distributions.
The computational cost of running the algorithm, measured as the percentage of robots that must be examined, remains relatively stable at around 52.97% (with a 5.30% standard deviation) for uniform and Gaussian error distributions. In other words, slightly over half the swarm typically needs to be checked in these scenarios.
In contrast, for the bimodal error distribution, the cost increases substantially, averaging about 81.22% (with a 1.89% standard deviation). This indicates that when errors are concentrated toward swarm edges, diagnosing errors demands examining the vast majority of the robots, significantly raising the resource cost of the diagnosis process.