CS Paper Radar

Conflicting Pattern Formation by Teams of Anonymous, Fully Disoriented Robots

Animesh Maiti, Prakhar Shukla, Subhash Bhagat

cs.DC cs.CGcs.MAcs.RO ·submitted 2026-09-20 08:31 UTC · v1

Abstract

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 \textit{gathering problem}, where robots gather at a point not known to them a priori, and the \textit{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 \textit{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.

Closest papers

Nearest neighbours by meaning across the whole index.

Min-Max Uniform Circle Formation by Asynchronous Mobile Robots

cs.DC cs.CGcs.MA ·2026-10-04 ·Animesh Maiti, Prakhar Shukla, Subhash Bhagat
similarity 0.73
Abstract

Given a set of point robots $\mathcal{R}$ in the Euclidean plane and a target circle $\mathbf C$ enclosing all robot positions, the \textsc{Min-Max Uniform Circle Formation (MMUCF)} problem requires the robots to move to distinct positions on $\mathbf C$ such that the final configuration forms a regular $n$-gon while minimizing the maximum distance traveled by any robot. Uniform circle formation is a fundamental coordination task in swarm robotics with applications in perimeter monitoring, surveillance, boundary coverage, and pattern formation. The literature does not address the optimization of the maximum individual displacement during the formation process. In this work, we study the min--max versions of the circle formation and uniform circle formation problems, where the goal is to minimize the maximum distance traveled by any robot. We consider these problems under the $\mathcal{ASYNC}$ model, where robots are autonomous, anonymous, identical, homogeneous, oblivious, and silent, and operate under the \textit{Look--Compute--Move} model with non-rigid motion. We first give necessary conditions for a deterministic solution and then present deterministic, distributed, and collision-free algorithms that form a circle and a uniform circle in finite time while minimizing the maximum movement. The algorithms ensure that robots reach distinct positions on the circle and, in the uniform case, equally spaced positions on $\mathbf C$ under the considered model.

0.17

When Robots Crash: Optimal Asynchronous Gathering at Weber Meeting Nodes

cs.DC cs.CGcs.MA ·2026-10-03 ·Animesh Maiti, Prakhar Shukla, Abhinav Chakraborty, Subhash Bhagat
theory similarity 0.67
Abstract

We study the \textit{optimal gathering} problem over a finite set of designated \textit{meeting nodes} for \textit{asynchronous, anonymous,} and \textit{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 \textsc{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 \textsc{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 \textsc{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.

0.14

Budget-Constrained Fault-Tolerant Mutual Visibility for Autonomous Robots under the Mobility Fault Model

cs.DC cs.CGcs.MAcs.RO ·2026-10-03 ·Prakhar Shukla, Animesh Maiti, Shivam Kumar, Subhash Bhagat
similarity 0.64
Abstract

We investigate the mutual visibility problem for a swarm of $n\ge3$ autonomous mobile robots under the budget-constrained mobility fault model. The robots are opaque, so if three robots are collinear, the middle robot obstructs the visibility between the other two. Each robot is assigned a finite movement budget, reflecting its limited energy, that bounds the total distance it may traverse during the execution. Moreover, an arbitrary number of robots may become permanently immobile due to mobility faults. The objective is to design a distributed algorithm that enables the non-faulty robots to coordinate their movements so that, within a finite time, every non-faulty robot attains unobstructed visibility of all robots in the system, including the faulty ones, while respecting the prescribed movement budget. We consider luminous robots operating under the $\mathsf{SSYNC}$ model with non-rigid movements, without any agreement on their local coordinate systems, and equipped only with a {\it common fixed reference point}. We present a deterministic distributed algorithm that solves the problem despite an arbitrary number of mobility faults. The algorithm guarantees mutual visibility for the non-faulty robots, respects the movement budget of every robot, provides collision-free movements for the robots, and uses only 12 light colors.

0.26

Pass the Bucket: Efficient, Robust, Local Load Balancing for Teams of Heterogeneous Robots

cs.RO ·2026-08-27 ·Tobias Wallner, Dominik Krupke, Arne Schmidt, Sándor P. Fekete
similarity 0.62
Abstract · This paper was submitted to IROS 2026 on March 2nd and accepted on June 17th

We study the problem of decentralized, self-organized task sharing for a swarm of heterogeneous robots that collaborate in transportation or other objectives that require coordinated motion planning. To this end, we present theoretical and practical results for the simple but effective mechanism of \emph{bucket brigades} for load balancing, in which a team of heterogenous robots share a spatial task in a confined, one-dimensional space, while only being able to sense collisions with neighbors or walls. The goal is to optimize throughput of the overall system, without central control or information, aiming at an interval partition proportional to robot velocities. We address possible chaotic system behavior by developing a stabilization mechanism based on simple local aid, a ``token'', that temporarily decelerates robots after an encounter. This purely local change eliminates persistent oscillations, resulting in convergence towards a stable system state. We accelerate system convergence by comparing a single boundary token to ubiquitous two-directional tokens and optimizing the deceleration factor. Event-driven simulations report convergence times and robustness: For a large variety of perturbations (such as robot deletion, position or velocity jittering), the system reliably re-converges. The results suggest a local, practical mechanism for robust load balancing for heterogeneous teams of robots that promises an effective tool as basis for more complex scenarios.

0.30

Safe Formation Control of Open Multi-Robot Systems with Connectivity-Preserving Reconfiguration

eess.SY ·2026-09-24 ·Pelin Sekercioglu, Nicola De Carli, Dimos V. Dimarogonas
similarity 0.59
Abstract

We address the formation control problem for open multi-robot systems (OMRS), i.e., systems in which robots may join or leave the team during operation and new interaction links are established over time, subject to inter-robot collision-avoidance and connectivity-maintenance constraints. The robots are modeled by double integrators, and interact over a dynamic undirected graph. We design a distributed controller based on the gradient of a barrier-Lyapunov function. To enable team reconfiguration, we introduce a formation manager that coordinates robot additions and removals and establishes prospective edges whenever needed, either to connect a joining robot to the team or to preserve connectivity before a robot departs. The upper-distance constraints of prospective edges are temporarily relaxed through auxiliary dynamics that preserve feasibility while progressively recovering the nominal interaction range. The resulting open-team dynamics are modeled as a switched system, for which we establish uniform practical stability for almost all initial conditions under a transition-dependent average dwell-time condition. Finally, the proposed approach is validated in realistic Gazebo simulations with dynamically simulated quadrotors undergoing repeated joining and departure maneuvers.

0.20

Distributed Geometric Optimization and Control of Rigid Differential-Drive Formations from Relative-Position Measurements

eess.SY cs.ROmath.OC ·2026-11-04 ·Thanacha Choopojcharoen, Erman Selim, Ramisha Anjum, Baris Fidan
similarity 0.58
Abstract · 11 pages, 6 figures

Distance based formation control fixes the shape of a robot team but leaves its position and orientation unconstrained. We regulate all three for differential drive robots that have only one absolute position anchor, absolute headings, body frame relative position measurements, and communication with their neighbors. We derive a two layer estimation control scheme directly from optimization. The first half of the result is a set of graph-proximal estimators that reconstruct the centroid, the anchor vector, and the centered coordinates. Exact proximal updates reach consensus in finitely many steps, and a finite number of primal dual iterations leaves a bounded reconstruction error. The controller combines proximal centroid and orientation steps with distance gradient shape regulation, and a finite rotation removes the orientation drift caused by the shape step. A discrete Lyapunov analysis gives local exponential convergence once the estimators have converged. We validate the method in ROS 2 Gazebo and in experiments with five physical robots.

0.36

A Taxonomy on Collective Awareness

cs.RO ·2026-10-05 ·Guillermo GP-Lenza, Miguel Fernandez-Cortizas, Martín Molina, Ricardo Sanz, Pascual Campoy
position similarity 0.58
Abstract

As robotic teams tackle increasingly complex tasks in dynamic and unstructured environments, effective coordination requires agents to maintain accurate, aligned representations of their environment, teammates, and mission state. We argue that Mutual Awareness, Shared Situational Awareness, and Team Situational Awareness --- three concepts widely invoked in the multi-robot systems literature --- are not interchangeable: they form a containment hierarchy in which each type subsumes the previous in scope, and span a distribution spectrum from fully individualized understanding (MA) to fully uniform understanding (SSA), with TSA occupying a mixed position. We establish this through a two-dimensional taxonomy organized along the object of awareness and awareness distribution axes. Treating these terms as synonyms obscures the precise coordination requirements each imposes on a robotic system. A Search and Rescue case study with heterogeneous aerial and ground robots grounds each taxonomy position in concrete coordination requirements. These findings provide a conceptual foundation for principled specification, design, and comparison of collective awareness in multi-robot systems.

0.24

Byzantine Resilience of Robot Gathering under Round-Robin Scheduling

cs.DC ·2026-11-17 ·Fabian Frei, Yuichi Sudo, Koichi Wada
theory similarity 0.58
Abstract

We study deterministic gathering of $n$ anonymous, oblivious mobile robots in the plane under round-robin scheduling with rigid movement, in the presence of $f$ Byzantine robots. Robots observe all robot positions with their multiplicities, while their local coordinate systems may change adversarially between activations. The goal is for all correct robots to gather at a single point in finite time and remain there forever. We analyze ToMax, a simple algorithm that moves to a point of maximum multiplicity and stays still if and only if its current position is the unique maximum. We prove that ToMax achieves gathering whenever $f\le\lfloor\sqrt{n}/2\rfloor$, establishing an $Ω(\sqrt{n})$ lower bound on the achievable Byzantine resilience.

0.13