arXiv preprint ·
Min-Max Uniform Circle Formation by Asynchronous Mobile Robots
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Distributed & Parallel Computing
Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation
Rubix: Global Correspondence-Free Point Set Alignment through Assignment Geometry
Deterministic Distance Selection in $O(n^{4/3})$ Time
Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation
Peeling Half the Onion: Embedding $k$-Outerplanar Graphs into $\ell_1$ and Trees with a Polynomial Distortion (in $k$)
Get the few papers worth your time in Distributed & Parallel Computing every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.