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

Sep 20, 2026cs.DC

Conflicting Pattern Formation by Teams of Anonymous, Fully Disoriented Robots

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.

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

Ask PDF

Mar 19, 2026cs.CG

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

We study unlabeled MRMP for unit-disk robots in a polygonal environment. Although the problem is hard in general, polynomial-time solutions exist under appropriate separation assumptions on start and target positions. Banyassady et al.(SoCG'22) guarantee feasibility in simple polygons under start--start and target--target distances of at least

4

, and start--target distances of at least

3

, but without optimality guarantees. Solovey et al.(RSS'15) provide a near-optimal solution in general polygonal domains, under stricter conditions: start/target positions must have pairwise distance at least

4

, and at least

\sqrt{5}\approx2.236

from obstacles. This raises the question of whether polynomial-time algorithms can be obtained in even more densely packed environments. In this paper we present a generalized algorithm that achieve different tradeoffs on the robots-separation

ρ

and obstacles-separation

ω

, all significantly improving upon the state of the art. Specifically, we obtain polynomial-time constant-approximation algorithms to minimize the total path length when (i)

ρ=2\frac{2}{3}

and

ω=1\frac{2}{3}

, or (ii)

ρ\approx3.291

and

ω\approx1.354

. These solutions are weakly-monotone; we also provide a monotone solution requiring

ω=\approx1.614

and

ρ=4

. We prove that monotone plans may not exist when

ω<1.614

, and weakly-monotone plans may not exist when

ω<1.354

. We then present tradeoffs between the separation bounds and the approximation factor, specifically achieving an (almost) optimal bound of

ρ=2

at the cost of a linear approximation factor and requiring

ω=2

. This applies also for the labeled variant of MRMP, in which case we show a tight bound on

ω

. Finally, we show that without any robots-separation assumption, obstacles-separation of at least

1.5

may be necessary for a solution to exist.

Tsuri Farhana, Omrit Filtser, Shalev Goldshtein

Department of Computer Science, Ben Gurion University, Beer Sheva, Israel. · Department of Mathematics and Computer Science, The Open University of Israel, Ra’anana, Israel

Multi-Robot Motion Planning Approximation Algorithms Planning Motion Separation

Ask PDF

Jul 16, 2026cs.RO

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

The simultaneous arrival of multiple mobile robots at a target point is crucial for cooperation tasks such as cooperative encirclement, disaster relief, and environmental monitoring. Although the simultaneous arrival problem itself is already complex, the problem becomes more challenging when there are constraints on the robot trajectory curvatures and the speeds are required to be constant (possibly different for different robots), and the control law for robots needs to be distributed. These constraints are typical for a multi-robot system consisting of, e.g., fixed-wing UAVs. To address this challenge, this paper proposes a distributed switching control method based on the maximum consensus protocol. By exploiting the geometric properties of Dubins paths along with optimization principles, a virtual time variable is introduced, and a hybrid control law that combines optimal control with saturated proportional control is designed. Under the proposed control law, each robot is driven to approach the maximum virtual time among its neighbors, thereby achieving simultaneous arrival under some mild conditions. Furthermore, we prove that in certain cases the proposed method attains a theoretically optimal arrival time. The approach is scalable and real-time, with low communication overhead. Its effectiveness and robustness are validated through extensive simulations and experiments.

Zhouru Xiao, Yang Lu, Weijia Yao +2

School of Artificial Intelligence and Robotics, Hunan University, China · College of Intelligence Science and Technology, National University of Defense Technology, China

Multi-Robot Systems Queue Control

Ask PDF