Impossibility of Self-Organized Aggregation without Computation
Roy Steinberg *, Kiril Solovey * · 2025
Read Impossibility of Self-Organized Aggregation without Computation by Roy Steinberg *, Kiril Solovey * (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-00390.txt.
Introduction
Roy Steinberg and Kiril Solovey, two researchers in robotics, wrote this study of how simple robots can gather at one point. The work appeared in 2024 and takes up a basic task called aggregation. The robots in question have almost no hardware. They cannot compute, cannot store past states, and cannot talk to each other. Each one only senses whether another robot sits right in front of it.
Earlier work had shown a control rule that gathers two such robots from any start. The same rule often works for larger groups but not always, and whether any rule always works stayed open. Steinberg and Solovey show that no such rule exists for groups of any size. They also find a flaw in the old two-robot proof and give a new rule with a clean proof.
Catalog record
| CREATOR | Roy Steinberg *, Kiril Solovey * |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-00390
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Impossibility of Self-Organized Aggregation without Computation Roy Steinberg *, Kiril Solovey * Abstract In their seminal work, Gauci et al. (2014) studied the fundamental task of aggregation, wherein multiple robots need to gather without an a priori agreed-upon meeting location, using minimal hardware. That paper considered differential-drive robots that are memoryless and unable to compute. Moreover, the robots cannot communicate with one another and are only equipped with a simple sensor that determines whether another robot is directly in front of them. Despite those severe limitations, Gauci et al. introduced a controller and proved mathematically that it aggregates a system of two robots for any initial state. Unfortunately, for larger systems, the same controller aggregates empirically in many cases but not all. Thus, the question of whether a controller exists that aggregates for any number of robots remains open. In this paper, we show that no such controller exists by investigating the geometric structure of controllers. In addition, we disprove the aggregation proof of the paper above for two robots and present an alternative controller alongside a simple and rigorous aggregation proof. I Introduction Diverse species, from ants to birds, fish, and mammals, exhibit swarm intelligence, wherein relatively simple mechanisms deployed by individuals lead to an emergent collective behavior. Taking inspiration from the natural world, research on swarm robotics seeks to develop low-cost robots that can collectively execute complex tasks only by relying on simple and local control laws and without explicit communication. This includes collective decision-making between robots and animals [ 1 ] , robots building complex structures [ 2 ] , and particle assembly via global control [ 3 ] . A fundamental emergent behavior is aggregation (also known as gathering), where the robots must reach sufficiently close to one another without a priori agreeing upon a predefined meeting location. In recent years, various approaches have been introduced towards swarm aggregation, from genetic programming [ 4 ] , to settings with limited sensing abilities [ 5 , 6 ] , and algorithms relying on potential functions [ 7 , 8 ] . Although some approaches guarantee aggregation, they usually require complex computational abilities and memory. The distributed computation community has also considered aggregation (see, e.g., [ 9 , 10 , 11 ] ) where solutions that guarantee aggregation for any number of robots have been developed by relying on geometric control laws (e.g., moving towards the center of gravity of the robots). However, the proposed methods rely on strong assumptions such as knowledge of the locations of all the robots and the absence of kinematic motion or collision avoidance constraints, making them unsuitable in practice. Aggregation under a far less restrictive set of assumptions has been studied in [ 12 ] , where the authors considered a memoryless controller for a group of homogeneous differential-drive (DD) robots. Here, the robots can obtain information about other robots through a binary sensor indicating whether another robot is in front of them. Considering those constraints, the controller of a given robot is bimodal , as it specifies a robot’s action depending on whether there is another robot in front of it. In particular, a bimodal controller is a four-dimensional vector specifying the speed of each of the two robot wheels for every mode. To find an aggregating bimodal controller, the authors of [ 12 ] empirically obtained the controller u_{prev}:=(-0.7,-1,1,-1) through an exhaustive search of the four-dimensional control space. This controller yields a backward circular motion of the robot when no other robot is in sight, and a rotation on the spot otherwise. The paper provided a theoretical proof for aggregating two robots using the controller. However, no proof has been shown for a larger robot number n>2 . Instead, simulations and hardware experiments using ’e-puck’ DD robots [ 13 ] have demonstrated that aggregation occurs within the allotted time budget in most cases. The idea that u_{prev} leads to aggregation for any n\geq 2 has recently been challenged. The paper [ 14 ] has shown a counterexample consisting of initial robot locations in which no aggregation would occur for any n\geq 4 . In particular, by placing pairs of robots facing directly away from each other, deadlocking can occur (see Fig. 3a ), as each robot attempts to move backward but is blocked by its partner. This causes each pair to stagnate. Interestingly, it is demonstrated empirically in [ 14 ] that some levels of noise (with respect to sensor and motion models) can help in escaping deadlocks for u_{prev} , but too much noise can be detrimental for aggregation. Unfortunately, no theoretical analysis is provided. The question posed by the authors of [ 12 ] whether there exists an aggregating controller for any n\geq 2 remains open. Contribution. In this paper, we answer the above question in the negative for a general number of robots, alongside strengthening the understanding of the case of two robots. Our contributions are as follows. (i) We identify an implicit (and unreasonable) assumption made in the aggregation proof for two robots using u_{prev} in [ 12 ] , which deems the proof incomplete. (ii) We present an alternative controller alongside a simple and rigorous aggregation proof for two robots. (iii) We prove that no bimodal controller can achieve aggregation for all n>2 . (iv) We mathematically prove that for some controller types, initial robot states that lead to nonaggregation do not have to be singular. That is, we show that when the initial states are chosen at random, the probability of nonaggregation is strictly larger than zero. (v) Finally, we empirically demonstrate that our 2 -robot controller outperforms the controller u_{prev} , and test the effect of noise and slippage on nonaggregation. II Preliminaries and Problem Definition We consider a system of homogeneous disk-shaped DD robots operating in an obstacle-free environment. The left and right wheel speeds of a given robot are individually controlled and denoted by v_{l} and v_{r} , respectively. A robot’s state space is \mathbb{R}^{2}\times S^{1} , where a state consists of the (x,y) coordinates of the robot’s center, and its orientation \theta . The kinematic constraints of a robot are given as the ODE \left(\begin{smallmatrix}\dot{x}\\ \dot{y}\\ \dot{\theta}\end{smallmatrix}\right)=\left(\begin{smallmatrix}\cos\theta&0\\ \sin\theta&0\\ 0&1\end{smallmatrix}\right)\left(\begin{smallmatrix}v\\ \omega\end{smallmatrix}\right), where v=\frac{v_{l}+v_{r}}{2} is the tangential speed, \omega=\frac{v_{r}-v_{l}}{d_{iw}} is the angular velocity, with inter-wheel diameter d_{iw}>0 [ 15 ] . 1 1 1 In our calculation, we use the dimensions of the e-puck robot [ 13 ] . The robots are disc-shaped of radius r=3.7[\text{cm}] , inter-wheel diameter d_{iw}=5.1[\text{cm}] , and maximum wheel speed v_{i}=12.8\penalty\ \left[\frac{\text{cm}}{\text{s}}\right] each. Each robot is equipped with a binary sensor, which determines whether there is another robot along the infinite ray emanating from the ego robot’s center, with orientation \theta . If there is no robot in sight, the output is ’ 0 ’, and ’ 1 ’ otherwise. Before proceeding to the problem statement, we state four assumptions. (1) Following [ 12 ] , the robots are memoryless and cannot communicate. Next, we introduce several assumptions to make the analysis tractable. (2) The robots cannot push each other upon collision (i.e., all collisions are purely plastic, and no momentum is conserved). (3) No noise in the motion model or sensor measurements is present. (4) There