We consider the distributed setting of n autonomous mobile robots operating in Look-Compute-Move (LCM) cycles on the real plane. Robots may be without lights (the classic oblivious robots model) or equipped with lights (the robots with lights model). Under obstructed visibility, a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them, but it is not the case under unobstructed visibility. Robots are said to collide if they share positions or their paths intersect within concurrent LCM cycles. In this paper, we introduce and study Doorway Egress, the problem of robots exiting through a doorway from one side of a wall to the other; initially, the robots are positioned at distinct positions on one side of a wall.We study time-efficient solutions where time is measured using a standard notion of epochs – an epoch is a duration in which each robot completes at least one LCM cycle. For solutions to Doorway Egress with only 1 epoch, we: design an asynchronous algorithm if collisions are allowed; prove that an asynchronous algorithm is impossible if collisions are not allowed; and design a semi-synchronous algorithm without collisions. To further investigate asynchronous algorithms without collisions, we present algorithms with different combinations of robot abilities:•O(1) epochs with lights under obstructed visibility;•O(1) epochs without lights under unobstructed visibility; and•O(n) epochs without lights under obstructed visibility.Our results reveal dependencies and trade-offs among obstructed/unobstructed visibility, lights/no lights, and semi-synchronous/asynchronous settings.

We consider the distributed setting of$N$autonomous mobile robots that operate in Look-Compute-Move (LCM) cycles following either the robots with lights model or the classical oblivious robots model. For the lights model, we assume obstructed visibility so that a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. In contrast, we assume unobstructed visibility in the classical model so that a robot sees all others irrespective of their positions. In addition, we consider a grid-based terrain embedded in the 2-dimensional Euclidean plane that restricts each robot's movement to one of the four neighboring grid points from its current position. This grid setting is a natural discretization of the 2-dimensional real plane and extends the robot swarm model in directions of greater applicability. The Arbitrary Pattern Formationproblem is to relocate the$N$robots (starting at arbitrary but distinct initial positions on a grid) to form an arbitrary target pattern given as input. In this paper, we provide two asynchronous algorithms for Arbitrary Pattern Formation, one on the lights model and another on the classical model. Key measures of the algorithms' performance include the time taken and the number of moves by each robot. Both algorithms run in$O(\max\{D^{i}, D^{p}\})$time with$O(\max\{D^{i}, D^{p}\})$moves by each robot, where$D^{i}$and$D^{p}$, respectively, are the diameters of the initial and pattern configurations. The algorithm for the lights model uses$O(1)$colors. We also prove a lower bound of$\Omega(\max\{D^{i}, D^{p}\})$for time for any Arbitrary Pattern Formationalgorithm if scaling is not allowed on the target pattern. Therefore, our algorithms are optimal w.r.t. time. Furthermore, our algorithms are also optimal w.r.t. the number of moves given the existing lower bound of$\Omega(\max\{D^{i}, D^{p}\})$on the number of moves. In sum, our results show that having lights provides a trade-off on the unobstructed visibility requirement in the classical model for Arbitrary Pattern Formation.

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.

We consider the distributed setting of n autonomous mobile robots that operate in Look-Compute-Move (LCM) cycles and communicate with other robots using a constant number of colored lights (the robots with lights model). We assume obstructed visibility where a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. In addition, we consider a grid-based terrain embedded in the 2-dimensional Euclidean plane that restricts each robot movement to one of the four neighboring grid points from its current position. This grid setting is a natural discretization of the 2-dimensional real plane and extends the robot swarm model in directions of greater applicability. The CONVEX HULL FORMATION problem 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 paper, we provide two asynchronous algorithms for CONVEX HULL FORMATION, both using a constant number of colors. Key measures of the algorithms' performance include the time taken and the space occupied (measured as the perimeter of the smallest rectangle enclosing the convex hull formed). The first O(max{n2, D})-time and O(n2)-perimeter algorithm serves to introduce key ideas, where D is the diameter of the initial 3 configuration. The second algorithm runs in O(max{n3/2, D}) 3 time with a perimeter of O(n3/2). We also prove lower bounds of Ω(n2/3) for both the time and perimeter for any CONVEX HULL FORMATION algorithm; that is, we establish our second algorithm as optimal in both time and perimeter.