Min-Max Uniform Circle Formation by Asynchronous Mobile Robots

Animesh Maiti; Prakhar Shukla; Subhash Bhagat

cs.DCOct 4, 2026

Min-Max Uniform Circle Formation by Asynchronous Mobile Robots

Authors: Animesh Maiti, Prakhar Shukla, Subhash Bhagat

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

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.

Figures & tables

Problem	Input circle	Additional capabilities	Movement	Optimization criterion	Reference
$\mathcal{CF}$	No	Lights	Non-rigid	Yes	Solved in [ 3 ]
$\mathcal{UCF}$	No	None	Non-rigid	No	Solved in [ 16 ]
$\mathcal{UCF}$	No	Persistent lights	Rigid	No	Solved in [ 25 ]
$\mathcal{UCF}$	Yes	One axis and lights	Non-rigid	Yes	This paper

Table 1 : Related work on circle formation and uniform circle formation.

Figure 1 : An illustration of target point set and corresponding assignments: initial positions of six robots $r_{1},\ldots,r_{6}$ and the corresponding target set is $\mathcal{P}=\{p_{1},\ldots,p_{6}\}$ . Here, $\lambda^{*}_{\mathbf{C}}(\mathcal{R}(t_{0}))=|\overline{r_{2}p_{2}}|=|\overline{r_{5}p_{5}}|$ and $\{r_{1},r_{5}\}$ is the critical set . There are two different assignments for the given configuration: (i) $\{r_{1}\rightarrow p_{1},r_{2}\rightarrow p_{2},r_{3}\rightarrow p_{3},r_{4}\rightarrow p_{4},r_{5}\rightarrow p_{5},r_{6}\rightarrow p_{6}\}$ and (ii) $\{r_{1}\rightarrow p_{6},r_{2}\rightarrow p_{2},r_{3}\rightarrow p_{4},r_{4}\rightarrow p_{3},r_{5}\rightarrow p_{5},r_{6}\rightarrow p_{1}\}$

Figure 2 : Illustration for the proof of Theorem 1 . In this symmetric configuration of $\mathcal{R}=\{r_{1},r_{2},\ldots,r_{8}\}$ , the min-max distance is $\lambda_{\mathbf{C}}^{*}(t_{0})=d(r_{5},p_{1})=d(r_{6},p_{3})=d(r_{7},p_{5})=d(r_{8},p_{7})$ . Consequently, the critical robots are $r_{5},r_{6},r_{7},$ and $r_{8}$ .

Panel of Figure 3 — Figure 3 : Illustration for the proof of Theorem 2 . (a) A symmetric initial configuration $\mathcal{R}(t_{0})=\{r_{1}(t_{0}),\ldots,r_{6}(t_{0})\}$ , where the optimal min-max distance is $\lambda_{\mathbf{C}}^{*}(t_{0})=d(r_{i}(t_{0}),p_{i})$ for $i=1,\ldots,6$ . (b) A symmetric configuration $\mathcal{R}(t)=\{r_{1}(t),\ldots,r_{6}(t)\}$ , where the optimal min-max distance is $\lambda_{\mathbf{C}}^{*}(t)=d(r_{1}(t_{0}),p_{1}^{\prime})=d(r_{3}(t_{0}),p_{3}^{\prime})=d(r_{5}(t_{0}),p_{5}^{\prime})$ .

Panel of Figure 4 — Figure 4 : An illustration in the proof of Theorem 3 : (A) In this configuration of $\mathcal{R}(t_{0})=\{r_{1}(t_{0}),r_{2}(t_{0}),\ldots,r_{6}(t_{0})\}$ , the min-max distance is $\lambda_{\mathbf{C}}^{*}(\mathcal{R}(t_{0}))=d(r_{1},p_{1})=d(r_{2},p_{2})$ . (B) In this configuration of $\mathcal{R^{\prime}}=\{r_{1}(t),r_{2}(t),r_{3}^{\prime}(t),r_{4}^{\prime}(t),r_{5}(t),r_{6}(t)\}$ , the min-max distance is $\lambda_{\mathbf{C}}^{*}(\mathcal{R}(t))=d(r_{3}^{\prime}(t),p_{1})=d(r_{4}^{\prime}(t),p_{2})$ .

Class	Defining condition
$\mathcal{K}_{\mathrm{ucr}}^{\mathrm{nc}}$	$\|\mathcal{R}^{*}(t_{0})\|=1$ and the unique critical robot is not at $\mathcal{O}$
$\mathcal{K}_{\mathrm{ucr}}^{\mathrm{c}}$	$\|\mathcal{R}^{*}(t_{0})\|=1$ and the unique critical robot is at $\mathcal{O}$
$\mathcal{K}_{\mathrm{mcr}}^{\mathrm{all}}$	$\mathcal{R}^{*}(t_{0})=\mathcal{R}(t_{0})$
$\mathcal{K}_{\mathrm{mcr}}^{\mathrm{ot}}$	$\mathcal{N}(t_{0})\cap\mathcal{D}^{}(t_{0})=\emptyset$ and $\mathcal{P}_{\mathcal{N}}(t_{0})\setminus\mathcal{D}^{}(t_{0})\neq\emptyset$
$\mathcal{K}_{\mathrm{mcr}}^{\mathrm{ct}}$	$\mathcal{N}(t_{0})\cap\mathcal{D}^{}(t_{0})=\emptyset$ and $\mathcal{P}_{\mathcal{N}}(t_{0})\subseteq\mathcal{D}^{}(t_{0})$
$\mathcal{K}_{\mathrm{mcr}}^{\mathrm{ii}}$	$r_{c}\in\mathcal{D}^{}(t_{0})$ and $p_{c}\in\mathcal{D}^{}(t_{0})$

Table 2 : Classification of initial configurations based on the critical set.

Figure 5 : Illustration of secondary critical robot in a configuration of six robots $r_{1},r_{2},\dots,r_{6}.$ In this configuration, the critical distance is $\lambda_{\mathbf{C}}^{*}=d(r_{3},p_{2})$ and $r_{2}$ is a secondary critical robot with secondary critical target position $p_{6}$ .

Figure 6 : Illustration of a configuration of six robots $r_{1},r_{2},\dots,r_{6}$ . Here, $r_{c}=r_{1}$ , $\mathcal{P}^{*}={p_{1}}$ , and the optimal assignment $f_{opt}(r_{i})=p_{i}$ , $i=1,2,\ldots,6$ .

Figure 7 : Illustration of the target-point construction for a centre-critical robot $r_{c}$ for $\mathcal{R}=\{r_{c},r_{1},r_{2},r_{3},r_{4}\}$ . The maximum angular sector $S_{23}$ determines the bisector $\mathbf{L}$ , along which the auxiliary point $q_{c}$ and the target point $p_{c}$ are selected.

Figure 8 : A six-robot configuration with exactly two critical robots, $r_{a}^{*}=r_{1}$ and $r_{b}^{*}=r_{6}$ , and critical distance $\lambda_{\mathbf{C}}^{*}$ . The midpoint $m_{16}$ , selected region $H^{+}$ , and dummy point $w$ determine the invariant target-point set $\mathcal{P}_{0}$ .

Explore similar work

Conflicting Pattern Formation by Teams of Anonymous, Fully Disoriented Robots
Sep 20, 2026Animesh Maiti, Prakhar Shukla, Subhash BhagatMulti-Robot Systems Optimistic Follow-The-Regularized-Leader
Department of Mathematics, Indian Institute of Technology Jodhpur Jodhpur, Rajasthan, India
Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs
Mar 19, 2026Tsuri Farhana, Omrit Filtser, Shalev GoldshteinMulti-Robot Motion Planning Approximation Algorithms
Department of Computer Science, Ben Gurion University, Beer Sheva, Israel. · Department of Mathematics and Computer Science, The Open University of Israel, Ra’anana, Israel
Simultaneous Arrival Control for Distributed Multi-Robot Systems with Curvature and Constant-Speed Constraints
Jul 16, 2026Zhouru Xiao, Yang Lu, Weijia Yao +2Multi-Robot Systems Queue Control
School of Artificial Intelligence and Robotics, Hunan University, China · College of Intelligence Science and Technology, National University of Defense Technology, China

Sep 20, 2026, cs.DCJ/K move · Enter open · S save

Conflicting Pattern Formation by Teams of Anonymous, Fully Disoriented Robots

Animesh Maiti, Prakhar Shukla, Subhash Bhagat

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

Multi-Robot Systems Optimistic Follow-The-Regularized-Leader Robot Systems

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Conflicting Pattern Formation by Teams of Anonymous, Fully Disoriented Robots

Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs

Simultaneous Arrival Control for Distributed Multi-Robot Systems with Curvature and Constant-Speed Constraints