Optimal Convex Hull Formation on a Grid by Asynchronous Robots With Lights
Rory Hector, Ramachandran Vaidyanathan, Gokarna Sharma, Jerry L. Trahan · IEEE Transactions on Parallel and Distributed Systems · 2022
We consider the distributed setting of$n$autonomous mobile robots that operate in Look-Compute-Move cycles and communicate with other robots using a constant number of colored lights (therobots with lightsmodel). We assume obstructed visibility where collinear robots do not see each other. In addition, we consider a grid-based terrain embedded in the 2-dimensional euclidean plane. TheConvex Hull Formationproblem is to relocate the$n$robots (starting at arbitrary, but distinct, initial positions) so that each robot is positioned on a vertex of a convex hull. In this article, we provide a framework for solvingConvex Hull Formation. We then provide four asynchronous algorithms under this framework. Key measures of the algorithms’ performance include the time taken and the space occupied. The presented algorithms are randomized and their time bounds hold with high probability. The first$O(\max \lbrace n^{2},D\rbrace)$-time,$O({n^{2}})$-perimeter, and$O({n^{3}})$-area algorithm serves to introduce key ideas, where$D$is the diameter of the initial configuration. The subsequent algorithms, differing in computational requirements, run in$O(\max \lbrace n^{\frac{3}{2}},D\rbrace)$time with a perimeter of$O(n^{\frac{3}{2}})$and area of$O(n^{3})$. We also prove lower bounds of$\Omega (n^{\frac{3}{2}})$for time and perimeter and$\Omega (n^{3})$for area, for anyConvex Hull Formationalgorithm; i.e., our$O(\max \lbrace n^{\frac{3}{2}},D\rbrace)-$time algorithm is optimal in time, perimeter, and area.