We propose a novel algorithm for forming arbitrarily shaped assemblies using decentralized robots. By relying on local interactions, the algorithm ensures there are no unreachable states or gaps in the assembly, which are global properties. The in-assembly robots attract passing-by robots into expanding the assembly via a simple implementation of signaling and alignment. Our approach is minimalistic, requiring only communication between attached, immediate neighbors. It is motion-agnostic and requires no pose localization, enabling asynchronous and order-independent assembly. We prove the algorithm's correctness and demonstrate its effectiveness in forming a 107-robot assembly.
Figures & tables
Figure 1: (a) Axial coordinate system for the 2-D hexagonal space H that Huddle uses, where p and q are the column and row coordinates, respectively. (b) An unreachable position shown by the dashed hexagon. (c) Layout of wall indices and their corresponding directional unit vectors u^w .
Figure 2: Example of a 5-robot assembly. Dashed hexagons are target positions in S . (a) A root robot (0,0) in its Signal Activation phase, signaling (green) on its F wall to attract passing-by robots. (b) A passing-by robot detects and follows the signal to attach to the root robot. Upon connection, the root robot communicates its position (0,0) and the unit vector of the admitting wall u^0 to the newly attached robot. As a right nucleus—determined prior to its entering the Signal Activation phase—the root robot now signals on its FR wall. (c) The newly attached robot enters the Initialization phase, computing its coordinate (0,1) and identifying its wall statuses. (d) The (0,1) robot determines its role as a left nucleus and its growth direction as gi=−1 , as it shares a row with the (rounded down) midpoint (−1,1) of the left column (Algorithms 1 – 4 ). (e) The (0,1) robot enters the Signal Activation phase, signaling its left flank (Algorithms 5 and 6 ). The robots remain in that phase until their connection walls are occupied.
Algorithm 1 Determine robot role
Algorithm 2 Determine robot role using self-wall status
Algorithm 3 Determine robot role using target adjacent column
Algorithm 4 Determine growth direction
Algorithm 5 Identify walls to activate signals
Figure 4: (a) Notable situations during robot i ’s determination of its role, where it lies on a different row from the midpoint m=(−1,3) of Q−1(2) . Dashed hexagons are target positions for S , with color overlays indicating membership to target segments. (i) Located on the midpoint’s row, a robot occupying (0,3) —in the future—will be the nucleus (Algorithm 3 , lines 12 – 13 ). (ii) Without a target (0,3) position, the new attachment point is m⋆=(−1,2) , thus (0,2) is the nucleus position (Algorithm 3 , lines 18 – 19 ). (iii) With its FL wall between two null walls, robot i is solely responsible for nucleating to the left (Algorithm 2 ). (b) Suppose gi=gj=−1 and robot i does not delay its signal (red) while robot j ’s front wall is free. An unreachable position will occur if robot i ’s front wall is occupied before robot j ’s.
Algorithm 6 Identify walls to delay signal activation
Figure 5: 256 -robot assembly example from the Monte Carlo experiments (one robot attachment per step). Dashed hexagons represent Xb , which are eventually populated by robots marked with red circles; hexagons marked with blue circles are interior robots. Note that our approach does not distinguish between perimeter and interior robots.
Figure 6: (a) Robot diffusion motion state diagram. (b) Completion time of a 107-robot assembly forming “ H ”, where \nicefrac230 trials timed out (1 robot remaining).
Figure 7: 107 robots forming “ H ”. (a) We place the root robot at the world origin, while the rest of the robots start in two clusters. (b) The robots diffuse within an arena bounded by four walls, joining the assembly as attracted by signals. (c) Each robot eventually finds an opening to attach, completing the assembly.
Two groups of autonomous, anonymous, and oblivious mobile robots are deployed in the two-dimensional Euclidean plane, each assigned a distinct task. We study a setting where the two groups must simultaneously solve two conflicting pattern formation problems: the gathering problem, where robots gather at a point not known to them a priori, and the circle formation problem, where robots occupy distinct positions on the boundary of a circle. Although each robot knows its own task, it cannot identify other members of its group. A prior solution~\cite{Conflict-1} addressed this problem for asynchronous robots having {\it direction-only axis agreement} and {\it global weak multiplicity detection} capability available to all robots in both groups. In contrast, in this work, we consider fully {\it disoriented robots} without any axis agreement or common chirality. We study the feasibility of a solution to this problem for {\it disoriented robots}. We propose a distributed algorithm that solves the problem for semi-synchronous disoriented robots with non-rigid movements. Our proposed algorithm assumes global weak multiplicity detection only for the gathering group, while for the circle formation group, it requires local weak multiplicity detection.
Animesh Maiti, Prakhar Shukla, Subhash Bhagat
Department of Mathematics, Indian Institute of Technology Jodhpur Jodhpur, Rajasthan, India
We study the optimal gathering problem over a finite set of designated meeting nodes for asynchronous, anonymous, and oblivious mobile robots on an infinite grid under crash faults. The robots have global visibility and strong multiplicity detection, but share neither a coordinate system nor chirality. The objective is to gather all non-faulty robots at a Weber Meeting Node, minimizing the total Manhattan distance from their initial positions. Up to n−2 robots may crash permanently, and such crashes are indistinguishable from arbitrary delays. Existing approaches often rely on a designated robot to break symmetry, whose crash may block the remaining robots indefinitely. Instead, our approach enables every robot to independently select the same target from its snapshot, while target-dependent restricted shortest paths preserve the target as a Weber Meeting Node. We prove that, under strong multiplicity detection, optimal gathering is impossible from certain fully symmetric configurations. For all remaining configurations, our algorithm CrashTolerantWeberGathering() selects a unique common target, preserves its optimality throughout the execution, and allows non-faulty robots to progress without waiting for crashed robots, thereby guaranteeing gathering in finite time.
Department of Mathematics, Indian Institute of Technology Jodhpur, Jodhpur, Rajasthan, India · Department of Mathematics, Birla Institute of Technology Mesra, Ranchi, Jharkhand, India
Accurate localization remains a key challenge in swarm robotics, particularly for self-reconfigurable systems that must identify relative positions to form diverse structures. Most existing approaches rely on external tracking infrastructure or high-cost sensors, which limit scalability and deployment in unstructured environments. In this paper, we propose a novel contact-driven localization method for modular robots that leverages only local communication through binary contact information (whether two robots are physically connected or not). To exploit these contact cues, we introduce a virtual-force framework in which robots iteratively refine their poses attracting toward dock-connected neighbors and repelling from non-connected ones. The method requires no external infrastructure and relies only on minimal onboard sensing. Simulations show effective localization during the assembly of towers and cantilevers, enabling accurate, scalable, free-form self-assembly.
Mohammadali Rashidioun, Michael Sosa, Petras Swissler
Institute of Technology · Industrial and Mechanical Engineering Department, New Jersey Institute of Technology