We study the Uniform Circle Formation (UCF) problem, which asks a swarm of mobile agents, arbitrarily positioned onto the plane, to arrange on the vertices of a regular polygon. Each agent, customarily called robot, runs a distributed algorithm by executing a sequence of look-compute-move cycles. The robot swarm may adhere to three synchronization modes: fully synchronous, semi-synchronous, and asynchronous. Our robots are assumed to be punctiform, anonymous, and indistinguishable by their appearance; they do not store past actions or system snapshots, and they have neither a coordinate system nor chirality in common. Moreover, we consider opaque robots, i.e. they may have obstructed visibility due to collinearities. To cope with these strong limitations, we consider luminous robots, that is, they are equipped with a persistent light assuming diferent colors. This latter peculiarity represents the only way robots have to communicate. For all three synchronization modes, we solve the UCF problem with a constant number of colors. Concerning the running time, our solutions use a constant number of cycles (epochs) for fully synchronous (semi-synchronous) robots, and linearly many epochs in the worst-case for asynchronous robots.
A well consolidated trend in the literature on distributed computing studies models and
algorithms for agent-based computing systems, having great relevance in several real-world
applications. In these systems, a swarm of mobile computing entities, called robots, has to
cooperate to solve a given problem. Robots act under several assumptions on their capabilities and
on a particular scenario. Of great importance are models where robots are autonomous, i.e. they
work without a central control, and operate through a sequence of look-compute-move cycles
in which each robot: (i) takes the snapshot of the system (look), (ii) executes a deterministic
algorithm (compute), and (iii) travels to the computed destination, if any (move) [
Diferent modeling assumptions are considered, afecting the computational power of robots. For instance, robots may have distinct identifiers (yielding the ability of distinguishing one robot from another) or, on the contrary, they may be anonymous. They may have a finite but persistent memory, which is preserved from one look-compute-move cycle to the next one. If no such memory exists, robots are said to be oblivious. A “compromise” between memory and obliviousness is given by luminous robots, featuring a persistent light assuming diferent colors as a means of communication as well. Another step towards realistic models is to work with no point-like (punctiform model) but fat robots, where all robots are supposed to be solid discs with a certain radius. Moreover, robots can be transparent, enabling a complete visibility of the system, or opaque. Depending on the nature of the problem, robots can move either on the Euclidean plane, or on a graph which can either be known in advanced or not. For robot activation policy, three models are proposed in the literature: fully synchronous, where all robots execute their cycle synchronously, semi-synchronous, where a subset of robots executes its cycle synchronously whereas the others remain idle, and asynchronous, where each robot acts asynchronously.
Several research eforts focus on very basic classes of geometric pattern formation problems
to be solved within such distributed environments [
In [
So far, swarms of transparent robots have been mainly considered. In more realistic models,
robots are assumed to be opaque so that they can obstruct visibility in case of collinearity. In
this realm, the first natural problem to be tackled is Complete Visibility, where robots are
required to displace on the plane so that each robot is visible to all others. For the Complete
Visibility problem, opaqueness is a serious problem. Thus, additional robot capabilities
might be considered. Solutions in the literature are proposed for luminous robots (see, e.g., [
In [
Due to page limit, some material and proofs have been omitted.
We overview the distributed system we shall be dealing with (see, e.g., [
Robot swarms. Consider a finite set (swarm) of punctiform computational agents, called robots, which forms a distributed system located in the plane R2. These robots are: (i) anonymous and indistinguishable: they do not share any own identifier, (ii) autonomous: there is no central coordinator, (iii) homogeneous: they execute the same deterministic algorithm, (iv) oblivious: they do not remember any data about previous actions, (v) mobile: they can freely move on the plane, provided they never collide, (vi) rigid: they cannot be stopped before reaching the computed destination (i.e., no adversary can stop robot movement).
The robots are equipped with sensory capabilities to spot the positions of other robots.
Moreover, they are able to compute in finite time and infinite precision any algebraic function
of points in the plane. Also, we assume the following limitations on robots: (i) they do not know
how many they are, (ii) they are disoriented: no agreement among the individual coordinate
systems, nor on unit distance and chirality (roughly speaking, agreement on clockwise direction),
(iii) they are opaque (not transparent): collinearity causes obstructed visibility. Indeed, these
latter three inabilities introduce complications in algorithm design. E.g., due to opacity (iii) and
lack of knowledge of the number of robots (i), each robot may not be able to know whether or
not some robots are hidden at any given time. Clearly, this lack of the knowledge of the number
of robots makes the system easily scalable. Moreover, the disorientation (ii) might cause robot
collisions which may compromise system integrity. To deal with these adversities, we equip
robots with a light displaying a certain number of diferent colors they can communicate through
(see, e.g., [
When taking the system snapshot at any given time, a robot basically collects the coordinates —according to its own coordinate system — and the light color for any visible robot (itself included). So, operates in look-compute-move cycles, each executed in a single and atomic instant of time and consisting of the three phases: • Look: takes the instantaneous snapshot of the system. • Compute: runs a deterministic algorithm which, by having the snapshot as sole input, computes the destination point of and the (possibly) new color for the light of . • Move: sets its new color and moves straight towards the destination point computed above, without being stopped (rigidity assumption).
Diferent models of robot activation and synchronization are studied. In the fully synchronous model, time is logically subdivided into global rounds. All robots are activated at every round occurring at each time . Since look-compute-move cycles are executed atomically, all robots terminate their cycle by the next round. The semi-synchronous model coincides with the fully synchronous model, except that not all robots are necessarily activated at every round. However, every robot is activated infinitely often ( fair condition). In the asynchronous model, the robots are activated independently and each robot executes its look-compute-move cycle within an unpredictable but finite amount of time. There does not exist a common notion of time. Also, notice that the configuration perceived by a robot during its look phase — by which the robot computes its final destination — may significantly change before the robot starts moving. The UCF problem. We are now ready to present the UCF problem to be solved on fully, semi-, and asynchronous swarms of opaque robots with lights. Let a fully, semi-, or asynchronous swarm of robots be in any given initial valid configuration C0 (i.e. where all the robots occupy a distinct point of the plane). The UCF problem asks the swarm to move from C0 to a valid terminal configuration in which robots form a regular -gon.
Throughout the paper, we will be working with swarms of at least 5 robots. This is due to some technicalities that can be dealt with, but that will be omitted here.
Let a set of robots sit on their smallest enclosing circle (SEC). Two distinct robots , on the ⌢ SEC delimit two arcs (clockwise and counterclockwise). We say that and are adjacent ⌢ whenever there is at least one of the two arcs upon which no other robot sits. Clearly, in a robot swarm forming a regular -gon, each pair , of adjacent robots forms an angle of 2/ with the center of the SEC, formally ̂︂ = 2/ .
Definition 1. For any given 2 ≤ ≤ , let (1, 2, . . . , ) be a -tuple of distinct robots satisfying ˆ︂+1 = 2/ for every 1 ≤ < . Then, (1, 2, . . . , ) is said to be a regular -tuple. For odd (even > 2), the central robot (the central robots , 2 +1) is the pivot ⌈ 2 ⌉ 2 (are the pivots) of the regular -tuple.
Our strategies to move the robots on the vertices of a regular -gon (inscribed in the SEC) start by setting particular regular {3, 4, 5}-tuples. These tuples will not move for the whole computation, while the other robots will move to form the regular -gon. In particular, the pivots in such regular tuples will be crucial to set the main diameter of the SEC (see Definition 2). A key result for our algorithms is contained in the following Theorem 1. Let be the number of robots lying on the SEC.
• For odd , there is a diameter passing through a robot and dividing the SEC into two halves, each having ( − 1)/2 robots. • For even , there is a diameter dividing the SEC into two halves such that: () either the diameter passes through a robot and the half-SECs have /2 and (/2) − 1 robots, or () the diameter passes through two (opposite) robots and the half-SECs have (/2) − 1 robots each.
Another central role in our algorithms will be played by the notion of a main diameter. We distinguish between three cases, depending on the type of symmetry possessed by the robot swarm configuration: Definition 2.
• Asymmetry. A diameter settled according to Theorem 1 will be called the main diameter.
In this case, the main diameter has at least one robot at one endpoint, whose light will assume color pivot. • Symmetry with exactly one axis. We call main diameter the diameter laying on the symmetry axis. In this case, the main diameter does not necessarily pass through a robot with light of color pivot. • Rotational symmetry with two sectors. We call main diameter the diameter joining two opposite robots whose lights have color pivot.
Let be a main diameter by Definition 2. Let be one of the nearest robots to but not laying on , and let ℓ(, ) be the distance from to . Moreover, let be one of the closest but not belonging to vertices of the regular polygon that has to be formed by our robot swarm. Definition 3. Let ′ and ′′ be the two opposite chords parallel to a main diameter , at distance min{ℓ(,),ℓ(, )} from . We call ′ and ′′ the safe diameters of .
2
For rotational symmetries with more than two sectors, instead of safe diameters we will be considering safe chords: Definition 4. Let (1, 1⌢,2) and (3, 2, 4) be two adjacent regular 3-tuples (i.e., without any ⌢ other 3-tuple on the arcs 13 or 24), and suppose that 1 and 2 are not the two endpoints of a same diameter. The chord joining 1 and 2 is called a safe chord.
As we will see, a key operation of our algorithms is to set at most three robots on three points per each half-SEC, such points being actually three vertices of the regular polygon. The robots reaching such vertices will assume color angle or pivot. In the following theorem, we show that this can be done in a single cycle, provided robots share a common clockwise direction in the half-SEC they sit on: Definition 5. Two or more robots are said to be oriented whenever they agree on a common clockwise direction.
For a group of oriented robots, it is always possible to unambiguously spot robots to move within a cycle (e.g., the last ones according to the common orientation). This is crucial for the following Theorem 2. Given three oriented robots and three points on the same half-SEC, it is always possible for the robots to reach these points in a single cycle and avoiding collisions.
In a first phase, all robots gain complete visibility of the swarm [
Let CH be the swarm configuration at this point; without loss of generality, we assume robots
lights having the same color. Clearly, all robots are again vertices of a convex hull. The resulting
dynamic of the algorithm depends on the type of this convex hull, in particular on its degree of
symmetry. First of all, a special case occurs whenever the convex hull is perfect [
Let us show how our algorithm works.
From , we start setting the regular tuples which will be the reference points for the movements of the other robots. Once settled, a regular tuple will not move anymore, thus fixing once and for all for the whole robot swarm the angle 2/ of the regular -gon to be formed. As observed above, the dynamic of the algorithm depends on the degree of symmetry of . We distinguish between three cases: asymmetry, symmetry with exactly one axis, and rotational symmetry. Asymmetry. Consider the general case of asymmetry, i.e., no symmetry axis exists in . However, there exists at least one diameter passing through a robot and dividing the SEC into two halves, upon which robots distribute according to Theorem 1. The robot swarm must agree on one of such diameters, say , which by Definition 2 will be the main diameter. To ifnd , robots agree on starting from a commonly designated robot and following a common orientation on the SEC. To perform this task, we need Lemma 1. Starting from the configuration and in case of asymmetry, all robots on the SEC are able to unambiguously agree on a robot .
So, let be the robot chosen by the swarm according to Lemma 1 (i.e., has the
lexicograph1A set of ≥ 2 robots forms a biangular configuration if robots lie on a circle centered in , and two non zero
angles , exist such that for every pair and of robots consecutive on , we have ̂︂ ∈ {, } and and
alternate clockwise [
Even . By Theorem 1, one or two robots may sit at the endpoints of . In both cases, the robot at position has color pivot. Moreover, in the second case, the opposite robot on assumes color angle. Let us now continue discussing the first situation, since the second may be easily derived. By Theorem 1, one of the half-SEC, say +, has one more robot than the other, say − . So, a robot in + needs to move to the empty endpoint 3 (opposite to ) of and assume color angle. At the same time, two other positions 1 and 2 (regular polygon vertices) must be reached by two robots. These two positions correspond to the polygon vertices at the immediate left and right of . The three robots sat at positions 1, , 2 form the regular 3-tuple.
So, globally, three robots must be moved: two from + and one from − , so that both the half-SECs contain the same number of robots at the end of this cycle. To determine which robots in + and − must move at the vertices of the polygon, we use the orientation provided by and : for instance, we choose the last robots by such an orientation. Then, Theorem 2 ensures that the three vertices will be safely reached by the robots. Summing up, each robot performs: • Look-Compute: unambiguously spots the pivot position on the main diameter.
Furthermore, it computes the positions 1, 2, 3 and the robots heading to these positions. • Move: If is in the pivot position , then it does not move and sets its color as pivot. If is one of the robots heading to positions 1, 2, 3, it moves there and sets its color as angle. Otherwise, does nothing.
Symmetry with exactly one axis3. Let be the axis of symmetry in . By Definition 2, the diameter of the SEC lying on will be the main diameter. We consider three cases: odd , even with two axis pivots, and even with no axis pivot. Here, we discuss the odd case.
Odd . Suppose that passes through a robot, which will be the pivot , and splits the opposite edge of the polygon. So, divides the SEC into two symmetric halves, each with ( − 1)/2 robots ( excluded). Now, we aim to create the regular 3-tuple around , as well as setting two robots at the endpoints of the polygon edge opposite to . Therefore, two robots in each half-SEC must be moved. Even in this case, Theorem 2 ensures no crossing trajectories. However, notice that to apply Theorem 2 we need an orientation which in this case can be trivially settled in each half-SEC as being the direction from the pivot to the other endpoint of 2Let 0, . . . , − 1 be a listing of the robots on the SEC so that they are consecutive, i.e., and +1 are adjacent for every 0 ≤ < − 1. Let = ˆ︁(+1) mod . The corresponding angle-string is 0 · · · − 1. 3Two or more symmetry axes yield a rotational symmetry, considered in the next case. the diameter (namely, the main diameter) laying on the axis . To determine which robots in each half-SEC must move at the vertices of the polygon, we can choose, e.g., the last robots according to such an orientation. As in the asymmetric case discussed above, we call 1 and 2 the positions of the two polygon vertices around , while 3 and 4 are the positions of the two vertices of the polygon edge opposite to . Summing up, each robot performs: • Look-Compute: computes the axis of symmetry (and hence the main diameter) and the positions 1, 2, 3, 4 of the polygon vertices. • Move: If is on , it sets its color as pivot and stays put. If is one of the robots heading to positions 1, 2, 3, 4, it gets there and sets its color as angle. Otherwise, does nothing. Rotational symmetry. Let 0, . . . , − 1 be the sequence of robots consecutive on the SEC, starting from an arbitrary robot. If the related angle-string 0 · · · − 1 can be factored into identical substrings up to rotation, then the convex hull on the SEC can be divided into identical sectors, each being the 2 -rotation of the previous one. Let = { | ≡ mod /} be the class of symmetry which contains / robots sharing the same position in the diferent sectors. By using angle-strings, we can unambiguously choose one or two classes of symmetry. For the sake of simplicity, in what follows we assume a single4 main class of symmetry . The robots in will be the pivots. Note that, in case of rotational symmetry with two sectors, the diameter joining the two pivots will be the main diameter, by Definition 2. For more than two sectors, the chords joining pivots in two consecutive sectors will be the safe chords, by Definition 4. We now show how to set regular 3-tuples in this -angular configuration. Each robot performs: • Look-Compute: computes the main class of symmetry = {1, . . . , } and the positions {1 , 2 | ∈ {1, . . . , }} of the vertices which will be the nearest to elements in in the regular -gon. For a rotational symmetry with two (more than two) sectors, determining amounts to settle the main diameter (the safe chords) as well. • Move: If belongs to , it sets its color as pivot. If is the nearest robot to some 1 or 2 , it sets its color as angle and moves to its nearest destination point 1 or 2 . If two robots share the same distance from their destination, we can unambiguously choose one robot (as before) by considering the distance from the pivot. Otherwise, does nothing.
One or two regular 3-tuples, or 4-tuples. Let us consider the cases of asymmetry, symmetry with one axis, and rotational symmetry with two sectors. Let be their main diameter, which is uniquely determined as observed above. Let ′ and ′′ be their safe diameters. In this cycle, each robot performs: • Look-Compute: If is pivot or angle, it does nothing. Otherwise, computes: the safe diameters ′ and ′′, its destination point on the SEC, the point ⊥, which is the projection of on the safe diameter nearest to .
• Move: sets its color as internal and travels to ⊥.
Three or more regular 3-tuples. Let us consider the case of ≥ 3 regular 3-tuples. It is easy to see that this kind of configuration is a rotational symmetry. In this cycle, each robot performs: • Look-Compute: If is pivot or angle, it does nothing. Otherwise, computes: the nearest safe chord , its destination point on the SEC, the point ⊥, which is the projection of on .
• Move: sets its color as internal and travels to ⊥.
Lemma 2. The rappelling in Cycle 2 of robots on safe diameters and chords yields collision-free trajectories.
At the end of the previous cycle, each robot which is not pivot or angle colored lies on a safe diameter or on a safe chord. Our strategy was to move the robot to a position where enough information from the system configuration is available to compute its final destination on the SEC. So, in this cycle, each robot performs: • Look-Compute: If is pivot or angle colored, it does nothing. Otherwise, is within the SEC on a safe chord or a safe diameter, and sees at least three robots on the SEC which are pivot or angle colored. Thus, can reconstruct the SEC. So, computes: the original SEC upon which it has to travel, the safe chord or safe diameter it currently lies on, its destination arc , and the projection point of on .
• Move: sets its color as sec and travels to .
Let us outline our algorithm to solve UCF on the semi-synchronous model, pointing out main diferences with the fully synchronous algorithm presented in the previous section. Again, we let CH be the swarm configuration where all robots sit onto their SEC, thus knowing the exact number of robots in the system. We assume robots lights having the same color. The dynamic of the algorithm depends on the degree of symmetry of CH .
It is worth remarking that, for the semi-synchronous model, an appropriate way to measure time is addressed by the notion of an epoch. By epoch, we mean an amount of time within which each robot will be activated at least once. This must occur by the fairness condition on the system, pointed out in Section 2.
Asymmetry. In the first epoch , with the same dynamic as in the fully synchronous case, we set the color pivot to the robot through which the main diameter passes, dividing the swarm into two subs-swarms of the same cardinality.
In the second epoch, we set the color angle to robots, but now we need two diferent colors angle and angle_o to fix a common orientation. For odd (even) , we set one (two) regular 3-tuple(s) of type (angle, pivot, angle_o), plus two robots of colors angle_o and angle for odd . As in the fully synchronous setting, asymmetry always enables to provide a common orientation for the whole SEC.
In the third epoch, robots move to the main diameter. By the common orientation, the robots on a half-SEC can choose one of the two radiuses giving the main diameter. Then, they move onto such a radius as follows. An activated robot first checks whether it sits on an -gon vertex. If so and it is not already colored as pivot, angle, angle_o, then assumes color sec and ends its task. Otherwise, moves onto the radius in a position which univocally determines the polygon vertex on the SEC to be reached in the next epoch without collisions. At the beginning of the fourth epoch, all robots are on their own radius, except those on the SEC with light color pivot, angle, angle_o, sec. Each robot on the radiuses sees at least three lighted robots on the SEC. So, it computes its target vertex on the SEC by its current position. Symmetry with exactly one axis. While in the fully synchronous case, pivot and angle colors are both turned on in the first cycle, here we spend the first epoch to determine only those robots acting as pivot, and light them with new colors pivot_s1, pivot_s2, pivot_s3. Determining these robots takes place as in the fully synchronous case, while the new colors must be used to signal along the whole evolution the fact that the system starts in a configuration with a single symmetry axis. This latter fact turns out to be crucial since, due to semi-synchronous dynamics, at a certain instant it maybe the case that the initial symmetry is lost. We set pivot lights pivot_s1, pivot_s2, pivot_s3 depending on the odd or even number of robots and on the number of robots (zero, one or two) laying on the symmetry axis at the beginning of this epoch. Precisely: case a – pivot_s1 is used for an odd number of robots and one robot on the symmetry axis, case b – pivot_s2 is used for an even number of robots and no pivot on the symmetry axis, case c – pivot_s3 is used for an even number of robots and two pivots on the symmetry axis. So, in this first epoch , for cases a and c, the robots on the symmetry axis immediately assume color pivot_s1 and pivot_s3, respectively, and stay put. For case b, the robots nearest to the polygon vertices around the symmetry axis move to such positions and assume color pivot_s2 (the case of robots equally distant from these vertices can be dealt with, e.g., by considering their distance from the symmetry axis).
Now, the second epoch comes: we move some robots on polygon vertices, and light them up with angle color. As in the fully synchronous case, robots can agree on an upper and a lower direction. So, in case a, a regular 3-tuple (angle, pivot_s1, angle) is formed in the upper part of the SEC, and a regular 4-tuple (angle, angle, angle, angle) in the lower part. For case b, a regular 4-tuple (angle, pivot_s2, pivot_s2, angle) is formed in the upper part of the SEC, and a regular 2-tuple (angle, angle) in the lower part. For case c, a regular 3-tuple (angle, pivot_s3, angle) is formed in the upper part of the SEC, and a regular 5-tuple (angle, angle, pivot_s3, angle, angle) in the lower part. We stress that in all these cases, no more than three robots per each half-SEC move to reach their final destinations. Hence, by Theorem 2, no crossing trajectory exists.
For the following epochs, we note that, given the type of symmetry we are considering, the whole swarm cannot share a common sense of orientation. So, in the third epoch, along which robots move into the SEC, they cannot choose a radius to drop on, as in the asymmetric case. Instead, as in the fully synchronous case, they can set safe diameters and move onto them on the orthogonal projections of polygon vertices. At this point, in the fourth epoch, robots get back to the SEC by leaving perpendicularly from safe diameters. It is worth mentioning that during this latter epoch, in all three cases a, b, and c at least three robots with lights on are always visible, so that the SEC can be safely reconstructed.
Rotational symmetry. In the first epoch , we determine only those robots acting as pivot and light them with the new color pivot_r. This new color is used to signal along the whole evolution the fact that the system starts in a rotational symmetry configuration. Let ℎ > 2 be the number of rotational symmetry sectors (the case ℎ = 2 can be managed by adapting the asymmetric case technique). The following epochs basically take place as in the fully synchronous case. During the second epoch, we set ℎ regular 3-tuples (angle, pivot_r, angle); in the third epoch, robots drop down to the safe chords; in the fourth epoch, all robots get back to the SEC at polygon vertex positions.
In an asynchronous setting, severe problems may arise whenever robots are activated while other robots are moving to their destinations. In fact, the awoken robots would take snapshots which most likely will not be useful to exactly reconstruct some fundamental aspects of the system (e.g., SEC, main diameters, safe diameters and chords), crucial for their correct motion. This is basically due to the fact that moving robots can obscure other robots. Moreover, even if this is not the case, we cannot generally compute the final destination of a moving robot. Clearly, this could prevent an activated robot from targeting its correct final destination, e.g., when reaching angle and pivot positions, or right positions on main diameter, safe diameters and chords. To overcome the problem of moving robots, new light colors of type moving are lighted up as soon as a robot starts moving. Thus, we can use our semi-synchronous algorithm plus the following features, depending on the phases of the algorithm: • In the first phase, pivots and then angles must be set, according to the same precedence logic as in the semi-synchronous mode. More precisely, if an activated robot does not see such points and does not see moving robots (i.e., robots with some moving light colors), it establishes whether or not it has to move towards a pivot or angle position. In the afirmative, its light assumes color moving_pivot_s2, or moving_angle, or moving_angle_o depending on its final destination, and the robot moves there. Once re-activated, a robot with color moving_x simply changes its color into x ∈ {pivot_s2, angle, angle_o}, and stands still. Otherwise, if the robot does not have to reach a pivot or angle position, or it sees some robots with color light moving, then it stays put. • The second phase starts after setting angles and pivots. Robots enter the SEC on diameters and chords only if they see no other robot with color moving_internal. Activated robots that sit on -gon vertices and are not colored by pivot, angle, angle_o, assume color sec and stay put. When entering the SEC, a robot assumes color moving_internal. Once re-activated, a robot colored moving_internal simply switches its color into internal and stays put. • The third phase starts whenever on the SEC there are only robots with lights on (with colors pivot, pivot_r, pivot_s1, pivot_s2, pivot_s3, angle, angle_o, sec), and no robot is moving (i.e., has a light color of type moving). In this phase, robots get back to SEC from their positions on chords and diameters. A robot travels back only when it sees three light colors among pivot, angle, angle_o, so that it can reconstruct the SEC. If this is the case, it determines its -agon vertex position and moves there while assuming the color sec. Otherwise, it stays put. We notice that, along this phase, our algorithm takes full advantage of parallelization since the trajectory of moving robots cannot collide, as explained in the fully and semi-synchronous cases.
In this paper, we designed algorithms solving the Uniform Circle Formation (UCF) problem
on opaque luminous robot swarms. Our first algorithm solves the problem for fully synchronous
swarms of robots, by using a constant number of look-compute-move cycles as well as a constant
number of colors. In particular, with respect to our result in [
Among many possible future researches, we feel it interesting to pinpoint connections with Forma Language Theory. In the literature, and in the present paper as well, some interesting formal language aspects show up and, in our opinion, deserve further and more systematic investigations. For instance, as observed, recognizing certain types of symmetries in the robot swarm displacement reduces to verifying certain properties enjoyed by angle-strings. This is equivalent to accepting certain languages, such as the palindrome language, mirror language, copy language, etc.. Therefore, well established results on the hardness of language acceptance could carry over to distributed system investigation, stating the possibility or not to solving certain problems or the minimal amount of computational resources agents must posses to correctly operate.
In particular, considering the realm of luminous robots, the communication system provided
by a constant number of colors is easily seen to be modeled by a finite state automaton. This
observation might suggest, e.g., that minimizing the number of colors could be related to
minimizing the number of states in finite state automata. More generally, finite state automata
can be examined by so many points of view: descriptional complexity [
The authors wish to thank the anonymous referees for their very helpful comments and remarks. [35] C. Chofrut, A. Malcher, C. Mereghetti, B. Palano, First-order logics: some characterizations and closure properties, Acta Informatica 49 (2012) 225–248. [36] C. Mereghetti, B. Palano, Quantum automata for some multiperiodic languages, Theoretical
Computer Science 387 (2007) 177–186. [37] M. P. Bianchi, C. Mereghetti, B. Palano, Quantum finite automata: Advances on Bertoni’s ideas, Theoretical Computer Science 664 (2017) 39–53. [38] A. Kumar, D. A. de Jesus Pacheco, K. Kaushik, J. J.P.C. Rodrigues, Futuristic view of the Internet of quantum drones: Review, challenges and research agenda, Vehicular Communications 36 (2022) 100487.