Conflicting Pattern Formation by Teams of Anonymous, Fully Disoriented Robots

Animesh Maiti; Prakhar Shukla; Subhash Bhagat

cs.DCSep 20, 2026

Conflicting Pattern Formation by Teams of Anonymous, Fully Disoriented Robots

Authors: Animesh Maiti, Prakhar Shukla, Subhash Bhagat

Organizations: Department of Mathematics, Indian Institute of Technology Jodhpur Jodhpur, Rajasthan, India

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.

Figures & tables

Figure 1 : Illustrations of the circles $C_{k}(t)$ for $k\geq 1$ : blue robots represent the set $\mathcal{R}_{f}$ and red robots represent the set $\mathcal{R}_{g}$ .

Panel of Figure 2 — Figure 2 : (a) Illustration of the successor relation and the string of angles around the centre $c$ . In the clockwise ordering, $S(r_{i},c)=r_{j}$ , $S(r_{j},c)=r_{k}$ , $S(r_{k},c)=r_{l}$ , and so on. The string of angles is $SA(\mathcal{R},c)=(\alpha,0,\beta,\alpha,0,\beta,\alpha,0,\beta,\alpha,0,\beta)$ , which can be written as $SA(\mathcal{R},c)=X^{4},\hskip 9.24994pt\text{where }X=(\alpha,0,\beta)$ . Therefore, the configuration is regular with $reg(\mathcal{R})=4$ . (b) Illustration of a quasi-regular configuration $\mathcal{R}(t)$ with centre of quasi-regularity $c_{q}$ , where $\mathcal{B}(t)=\mathcal{R}(t)\setminus\{r_{c_{q}}(t)\}$ . The half-line $qrad_{i}(t)$ denotes the ray starting from $c_{q}$ and passing through $r_{i}(t)$ .

Panel of Figure 3 — Figure 3 : Illustration of different types of quasi-regular configurations: (a) a free-path quasi-regular robot configuration which is also totally symmetric , (b) a quasi-regular configuration which is not free-path quasi-regular , (c) a quasi-regular configuration with $\mathcal{O}(t)\neq c_{q}$ .

Panel of Figure 4 — Figure 4 : High-level execution of Algorithm PatternFormation() .

Panel of Figure 5 — Figure 5 : Illustrations of different scenarios of pivotal selection: (a) both $p_{1}$ and $p_{2}$ contain robot positions, (b) exactly one of $p_{1}$ and $p_{2}$ contains a robot position, and (c) none of $p_{1}$ and $p_{2}$ contains a robot position.

Panel of Figure 6 — Figure 6 : Step-in movement for computing $d_{i}$ : (a) The line segment $\overline{r_{i}(t)p}$ intersects the dotted line in $H_{i}(t)$ , (b) None of the line in $H_{i}(t)$ intersect $\overline{r_{i}(t)p}$ .

Panel of Figure 7 — Figure 7 : Step-aside movement for computing $x_{i}$ when $p_{m}=\mathcal{O}(t)$ : (a) Dotted lines in $H_{i}(t)$ intersect the arc $C_{ij}(t)$ of circle $C_{l}(t)$ (with $l=3$ ), (b) None of the lines in $H_{i}(t)$ intersect $C_{ij}(t)$ .

Panel of Figure 8 — Figure 8 : Step-aside movement for computing $x_{i}$ when $p_{m}\neq\mathcal{O}(t)$ : (a) Dotted lines in $H_{i}(t)$ intersect the circle $C^{*}_{k}$ , (b) None of the lines in $H_{i}(t)$ intersect $C^{*}_{k}$ .

Panel of Figure 9 — Figure 9 : Step-out movement for computing $u_{i}(t)$ and $x_{i}$ : (a) The line segment $\overline{r_{i}(t)u_{i}(t)}$ contains no other robot when $r_{i}(t)\neq\mathcal{O}(t)$ , (b) the segment $\overline{r_{i}(t)u_{i}(t)}$ contains multiple robots with $r_{i}(t)\neq\mathcal{O}(t)$ , and (c) the case when $r_{i}(t)=\mathcal{O}(t)$ .

Configuration class	Sub-case	$\mathcal{R}_{g}$ robots	$\mathcal{R}_{f}$ robots
${\mathcal{D}ense}$	free-path Q-regular	direct $\to c_{q}$	stationary
${\mathcal{D}ense}$	Q-regular, not free-path	direct/step-aside $\to\mathcal{O}(t)$	stationary
${\mathcal{D}ense}$	not quasi-regular a	direct/step-aside $\to\mathcal{O}(t)$	stationary
${\mathcal{N}on-Dense}$	free-path Q-regular	direct $\to c_{q}$	stationary
${\mathcal{N}on-Dense}$	Q-regular, $c_{q}\neq\mathcal{O}(t)$	stationary (non-pivotal step-in)	stationary (non-pivotal step-in)
${\mathcal{N}on-Dense}$	Q-regular, $c_{q}=\mathcal{O}(t)$	step-aside w.r.t. $\mathcal{O}(t)$ if blocked	step-aside w.r.t. $\mathcal{O}(t)$ if blocked

Table 1: Summary of movement rules during the multiplicity-creation phase.

Explore similar work

Min-Max Uniform Circle Formation by Asynchronous Mobile Robots
Oct 4, 2026Animesh Maiti, Prakhar Shukla, Subhash BhagatOptimistic Follow-The-Regularized-Leader
Department of Mathematics Indian Institute of Technology Jodhpur Jodhpur, Rajasthan, India
An Infrastructure-less, Control-Independent Solution to Relative Localisation of a Team of Mobile Robots using Ranging Measurements
Jun 18, 2026Paolo Golinelli, Tommaso Faraci, Daniele FontanelliMulti-Robot Systems Indoor Localization
Department of Industrial Engineering, University of Trento, Trento, Italy · Department of Information Engineering and Computer Science, University of Trento, Trento, Italy
Acting on the Unseen: Communication-Free Collaborative Filtering for Decentralized Multi-Robot Task Allocation
May 25, 2026Alexander Apartsin, Yigal Meshulam, Yehudit ApersteinMulti-Robot Systems Collaborative Filtering
Holon Institute of Technology, Holon, Israel. · Afeka Tel Aviv Academic College of Engineering, Tel Aviv, Israel

Oct 4, 2026, cs.DCJ/K move · Enter open · S save

Min-Max Uniform Circle Formation by Asynchronous Mobile Robots

Animesh Maiti, Prakhar Shukla, Subhash Bhagat

Department of Mathematics Indian Institute of Technology Jodhpur Jodhpur, Rajasthan, India

Optimistic Follow-The-Regularized-Leader

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Min-Max Uniform Circle Formation by Asynchronous Mobile Robots

An Infrastructure-less, Control-Independent Solution to Relative Localisation of a Team of Mobile Robots using Ranging Measurements

Acting on the Unseen: Communication-Free Collaborative Filtering for Decentralized Multi-Robot Task Allocation