Hardwired Pattern Formation by Mobile Robots with Common Unit Distance Yuta Kojima1 , Sébastien Tixeuil2[0000−0002−0948−7172] , and Yukiko Yamauchi3[0009−0009−8459−6676]
arXiv:2606.22386v1 [cs.DC] 21 Jun 2026
Kyushu University, Japan [email protected] Sorbonne Université, CNRS, LIP6, IUF, France [email protected] Kyushu University, Japan [email protected]
Abstract. The pattern formation (PTF) problem requires mobile robots to form a specified target pattern. Existing papers investigated the PTF problem and revealed the effect of obliviousness and synchronization on distributed coordination of mobile robots. However, the PTF problem allows translation, rotation, and scaling of the target pattern. In this paper, we introduce a novel pattern formation problem, called the hardwired pattern formation (HW-PTF) problem that requires the robots to form a given target pattern in a specified size. Although two oblivious semi-synchronous robots cannot solve the HW-PTF problem of multiplicity two (i.e., the rendezvous problem), we show that they can solve the HWPTF problem without multiplicity. We also show that two oblivious asynchronous robots equipped with lights can solve the HW-PTF problem, while oblivious asynchronous robots cannot. We finally present a size-adjusting algorithm for more than four oblivious semisynchronous robots, that yields a HW-PTF algorithm when combined with some existing pattern formation algorithms. Keywords: Mobile robots · pattern formation · unit distance
1
Introduction
The pattern formation (PTF) problem has been one of the most important problems in distributed coordination of mobile robots. The problem requires the robots to form a target pattern without any centralized control. Each robot is an autonomous mobile computing entity, that observes the positions of other robots, computes its next position, and moves toward the next position. The robots are anonymous and uniform in the sense that the robots are indistinguishable points and computes its next position by a common deterministic algorithm. The robots are not equipped with a common coordinate system nor memory to store past observations nor computation, i.e., they are disoriented and oblivious. Each robot performs a unit of action when it is activated and performs observation, computation, and movement. We consider three types of activation schedules, called the fully-synchronous (FSYNC) model, the semi-synchronous (SSYNC) model, and the asynchronous (ASYNC) model. Because the robots do not have a common coordinate system, the pattern formation problem allows translation, rotation, and scaling of the target pattern. Existing literature showed the class of formable patterns and the effect of obliviousness and synchronization [9, 11, 13], and these results are further extended from 2D space to 3D space [14]. For example, Suzuki and Yamashita introduced the notion of symmetricity of a set P of points, which is essentially the rotational symmetry of P . Then they showed that the robots can form a target pattern F from an initial configuration I if and only if ρ(I) divides ρ(F ) irrespective of obliviousness and synchronization. That is, the robots cannot resolve their initial rotational symmetry in their positions and local coordinate systems. However, there exists an exceptional case for the rendezvous problem, that requires two robots to form a single point of multiplicity two. When the robots are fully-synchronized, they can solve the rendezvous problem by moving to the midpoint. Suzuki and Yamashita showed that the two robots cannot solve the rendezvous problem when the robots are SSYNC or ASYNC [11]. Hence the rendezvous problem separates computational power of FSYNC robots from that of SSYNC or ASYNC robots.
2
Y. Kojima et al.
In this paper, we introduce a novel pattern formation problem, called the hardwired pattern formation (HW-PTF) problem, that requires the robots to form a given target pattern in a specified size. That is, the robots are required to reach a configuration congruent to the target pattern. We add the minimum requirement of a common unit distance for the robots to agree on the specified size. While the pattern formation problem has shed light to theoretical aspect of distributed coordination for mobile robots, its application to hardware robots, drones, and other mobile devices is limited. For example, consider surveillance of a large field by mobile sensors. Existing pattern formation algorithms [9, 11, 13] enable the mobile sensors to form an appropriate pattern to cover the field, however its size may disrupt communication connectivity or sensing coverage. Size specification has many applications including engineering, nanomanufacturing, structural biology, and so on. Our contribution. We show that the HW-PTF problem is both practically and theoretically important. First, we show that two SSYNC robots can solve the HW-PTF problem except the rendezvous problem. That is, two robots can stop at specified distance d(̸= 0) from an arbitrary initial configuration without multiplicity. Our key idea is the Z-move that enables two robots finish the HW-PTF under any SSYNC activation. We then show that two ASYNC robots cannot solve the HW-PTF problem for sufficiently large d. The Z-move plays an important role to show the impossibility because any SSYNC execution is also an ASNYC execution. That is, two ASYNC robots need the Z-move to finish HW-PTF. We will show that there exists an ASYNC activation that prevents two robots from solving the HW-PTF problem forever. These results also demonstrate that the HW-PTF problem for two robots separates computational power of oblivious SSYNC robots from that of oblivious ASYNC robots. We then show that oblivious ASYNC robots equipped with lights with two colors can solve the HW-PTF problem. Our key technique is to establish an isomorphism between an ASYNC execution of an rendezvous algorithm such as [5] and an ASYNC execution of a HW-PTF process. Finally, we present a HW-PTF algorithm for more than four oblivious SSYNC robots. Specifically, we present a size-adjusting algorithm, which yields a HWPTF algorithms when combined with some existing pattern formation algorithms [9, 11, 13]. Related work. Many papers investigate the effect of additional capabilities or restrictions on the formable patterns. Flocchini et al. showed that odd number of oblivious ASYNC robots can form an arbitrary pattern when they agree on the direction and orientation of one axis even when they have no common chirality [8]. Dieudonné et al. showed that oblivious ASYNC robots can form an arbitrary pattern when there exists a designated leader robot [6]. Cieliebak showed that more than two oblivious ASYNC robots can solve the point formation problem [2] while two oblivious SSYNC robots cannot [11]. Interestingly, if robots do not agree on the unit distance, SSYNC rendezvous and gathering becomes feasible [1] even if the starting configuration is bivalent (that is, with two location hosting an equal number of robots). While the effect of common directions or orientation on the pattern formation problem has been investigated, few papers consider the effect of common distance. Several papers consider the pattern formation problem for robots with limited visibility. Yamauchi et al. showed that non-oblivious SSYNC robots with limited visibility can form a “small” target pattern under the symmetricity condition. The trick is first gather the robots within their visibility range and then make them form the target pattern [15]. Hahn et al. showed that oblivious FSYNC robots with limited visibility can form a “large” target pattern under the symmetricity condition and additional connectivity condition [10]. However, in these papers, each robot does not know the size of its visibility. To the best of our knowledge, our result is the first result on the effect of a common unit distance to the pattern formation problem.
Hardwired Pattern Formation by Mobile Robots with Common Unit Distance
2
Preliminary
2.1
Robot System
3
We consider a set R = {r1 , r2 , . . . , rn } of n point robots. The robots are indistinguishable, and we use ri just for notation. Let pi (t) be the position of ri at time t in the global coordinate system Z0 . The configuration of R at time t is the multiset P (t) = {pi (t) | i = 1, 2, . . . , n}. We use dist(p, q) to describe the distance between two points p and q in Z0 . The robots repeat a Look-Compute-Move cycle, that consists of the following three phases. In the Look phase, robot ri obtains a snapshot of the robot system, i.e., the positions of all robots observed in its local coordinate system Zi . All global and local coordinate systems are righthanded x-y coordinate system with a common unit distance. For each robot ri , the directions and orientation of Zi never change, but the origin of Zi moves according to the movement of ri , that is, the origin is the current position of ri . Hence, the local coordinate system must be denoted by Zi (t), but we use Zi when it is clear by the context. We assume that the robots are equipped with a weak multiplicity detection capability, i.e., a robot can determine whether its current position is occupied by other robots or not.1 In the Compute phase, robot ri computes its next position by a common deterministic algorithm A. The sole input to A is the observation obtained in the preceding Look phase, i.e., we consider oblivious robots. The output of A is the coordinates of the next position of ri in Zi . In the Move phase, robot ri moves toward its next position, however, ri may stop en route after it moves by the minimum moving distance δ, which is not given to the robots, i.e., we consider non-rigid movement.2 We consider two types of schedulers (i.e., synchronization models) for mobile robots. In the semi-synchronous (SSYNC) model, we consider discrete time t = 0, 1, 2, . . . and non-empty subset of the robots are activated at each time step. The active robots execute a Look-Compute-Move cycle synchronously with each of the three phases completely synchronized. Hence, the configuration of the robots changes from P (t) to P (t + 1) according to the common algorithm A. We call the evolution P (0), P (1), P (2), . . . of the robot system R an execution of algorithm A. There exists multiple executions starting from P (0) because of the activation schedule and non-rigid movement. In the asynchronous (ASYNC) model, robots execute their Look-Compute-Move cycle independently. The length of each Look-Compute-Move cycle is finite but arbitrary, and a robot can be observed while moving. Let t0 , t1 , t2 , . . . , be the time instance where at least one robot obtains a snapshot in a Look phase. We consider P (t0 ), P (t1 ), P (t2 ), . . . as the execution P (0), P (1), P (2), . . . in the ASYNC model. For a given set of points P , let SEC(P ) and c(P ) denote the smallest enclosing circle (SEC) of P and its center, respectively. We use rad(P ) to represent the radius of SEC(P ). We call the largest circle centered at c(P ) and contains no point of P in its interior the largest empty circle (LEC) of P , denoted by LEC(P ). By definition, LEC(P ) contains at least one point of P on its boundary. Let dmin (P ) denote the minimum distance between the points of P . 2.2
Hardwired Pattern Formation Problem
The hardwired pattern formation problem requires the robots to form a given target pattern in a given size when the robots agree on the unit distance. The input to the problem is a multiset F of coordinates of n points in Z0 and the size d of the target pattern, which is 2 · rad(F ), i.e., the diameter of SEC(F ). We use HW-PTF(n, F, d) to describe the hardwired pattern formation problem for n robots, target pattern F , and its size d. We do not use multiplicity detection capability because our proposed algorithms does not make any multiplicity and we refer to multiplicity in only impossibility results. 2 Some of our impossibility result involve rigid movement, that allows robots always reach their next positions. 1
4
Y. Kojima et al.
An algorithm solves the HW-PTF(n, F, d) if any execution P0 , P1 , P2 , . . . has a finite t that satisfies Pt+i = Z ′ (F ) for i = 1, 2, . . . where Z ′ is obtained by a rotation and/or translation, but not scaling on the global coordinate system Z0 . That is, Pt+i is congruent to F . We assume that the initial configuration P (0) does not contain any multiplicity. 2.3
Symmetricity of a Set of Points
We briefly introduce the symmetricity of the set of points introduced by [9]. Given a set P of points, we consider the decomposition of P into regular k-gons centered at c(P ). Here, we say a set of k points is a regular k-gon if they are placed at the vertices of some regular k-gon. A point is a regular 1-gon with an arbitrary center and two points is a regular 2-gon. The symmetricity of P is the maximum number of such k with the following exception; ρ(P ) = 1 when c(P ) ∈ P . We show some examples of symmetricity: – When P forms a regular n-gon (|P | = n), ρ(P ) is n. – When P forms a square ρ(P ) = 4. – When P forms a non-square rectangle, ρ(P ) = 2. The ρ(P )-decomposition of P is a decomposition of P into subsets, say {P1 , P2 , . . . , Pk }, where each Pi forms a regular ρ(P )-gon centered at c(P ). Thus, k = n/ρ(P ). Suzuki and Yamashita showed that the robots can agree on the total ordering of {P1 , P2 , . . . , Pn/ρ(P ) } by introducing appropriate local view and ordering among them [11, 13]. We adopt a total ordering of the elements of the ρ(P )-decomposition of P so that P1 is on LEC(P ) and Pn/ρ(P ) is on SEC(P ), i.e., the distance from c(P ) is considered or added as the first criteria for ordering.
3
Hardwired Pattern Formation for Two Robots
In this section, we consider the HW-PTF problem for two robots. The target patterns of HWPTF(2, F, d) is either a point of multiplicity two (i.e., d = 0) or two points (i.e., d > 0). Hence, we use HW-PTF(2, d) instead of HW-PTF(2, F, d). 3.1
Two Oblivious SSYNC Robots
When d = 0, HW-PTF(2, d) degenerates into the rendezvous problem with a common unit distance. Suzuki and Yamashita showed that the rendezvous problem is not solvable by oblivious deterministic SSYNC robots without a common unit distance [11]. The impossibility result was later generalized by Courtieu et al [3] to an even number of robots, with the ability to detect multiplicity, and the same unit distance for all robots. Hence, the following observation holds: Observation 1 Two oblivious deterministic SSYNC robots with rigid movement cannot solve HWPTF(2, d) when d = 0. In the following, we will show HW-PTF(2, d) is solvable when d > 0 by a deterministic algorithm. Theorem 1. Two oblivious deterministic SSYNC robots with non-rigid movement can solve HWPTF(2, d) when d > 0. We present a HW-PTF algorithm for two oblivious deterministic SSYNC robots. First, consider the simple case of an initial configuration where the inter-robot distance is 3d, assuming collisionless and rigid movements. Then, the following algorithm can solve HW-PTF(2, d): An active robot moves toward the other robot by distance 2d. If only one of the robots is activated at time 0, rigid movement guarantees that the active robot approaches the other robot to distance d and stops.
Hardwired Pattern Formation by Mobile Robots with Common Unit Distance
5
𝑦
𝑝′
𝑑
𝑑
𝑑 𝑎 𝑝 = − ,0 2
q′
𝑥 𝑎 𝑞= ,0 2
Fig. 1. Z-move
If both robots are activated at time 0, rigid movement makes the two robots pass each other and stop at distance d. That is, from this initial configuration where robots are 3d apart, there exists an algorithm for the two robots to solve HW-PTF(d) in one SSYNC step. We then consider a more general initial configuration, where the inter-robot distance is a ̸= d. Specifically, we consider an initial configuration, where robot r1 is at p = (−a/2, 0) and r2 is at q = (a/2, 0) in Z0 . Let p′ and q ′ be the next positions for r1 and r2 to finish HW-PTF(2, d) in one SSYNC step with rigid movement. Hence, p′ and q ′ must satisfy the following three equations: dist(p′ , q ′ ) = d dist(p′ , q) = d dist(p, q ′ ) = d. Additionally, assume p′ and q ′ have symmetric positions with respect to (0, 0), since robots may have the same observation due to their inconsistent local coordinate systems. Hence, if p′ = (x, y), then q ′ = (−x, −y). By the above discussion, x and y must satisfy the following equations: p 2 x2 + y 2 = d (x − a/2)2 + y 2 = d2 Thus, we have a2 − 3d2 p4a (a + d)(a − d)(3d − a)(3d + a) y=± . 4a
x=
Additionally, we have a/2 − d ≤ x ≤ a/2 + d because p′ is on the circle centered at q. Thus, when d ≤ a ≤ 3d, we have points√p′ and q ′ that satisfy the three equations. (a+d)(a−d)(3d−a)(3d+a)
For simplicity, let y = . Then, the four points p, p′ , q ′ , and q forms Z, 4a and we call this movement the Z-move (Figure 1). Algorithm 1 shows our proposed algorithm for HW-PTF(2, d). The algorithm consists of three moves, the Z-move, the expanding move, and the shrinking move. Let a be the distance between the two robots. When d < a ≤ 3d, Algorithm 1 makes the robot perform the Z-move. When a < d, Algorithm 1 makes the robot move distance d away from the current position of the other robot so that the inter-robot distance is at least d in a resulting configuration. When a > 3d, Algorithm 1 makes the robot move to a point at distance d/2 from the midpoint of the current positions of the two robots. We then show the correctness of Algorithm 1 for two oblivious SSYNC robots with chirality and non-rigid movement. We need to consider the non-rigid movement in addition to the Z-move, which
6
Y. Kojima et al.
Algorithm 1 Form_Hw_Pattern_For_Two_Robots(P, d) at robot ri Input by the current observation P rj : the other robot p: current position of ri q: current position of rj a: distance between ri and rj Let Z0∗ be the right-handed x-y coordinate system s.t. p = (−a/2, 0) and q = (a/2, 0). Algorithm If d < a < 3d // Z-move p′ =
a2 −3d2 ,− 4a
√ (a+d)(a−d)(3d−a)(3d+a) 4a
Return p′ in Zi else if a < d // Expanding move p′ = (−(d − a2 ), 0) Return p′ in Zi else if 3d ≤ a // Shrinking move p′ = (− d2 , 0) return p′ in Zi end if end if
circumvent the SSYNC activation timing. For example, when the robots stop en route during the Z-move, their distance may become smaller than d, because the distance between the trajectories of the two robots (i.e., line segments pp′ and qq ′ ) can be smaller than d. Hence, the two robots perform the expanding move until their distance becomes larger than d. Then, the two robots execute the Z-move again. We will show when we focus on time steps, where some robot executes the Z-move, the inter-robot distance gradually decreases and eventually the moving distance of the Z-move becomes smaller than the minimum moving distance δ. Hence, an activated robot(s) can reach the next point of the Z-move and the two robots finish HW-PTF(2, d). For a given execution P0 , P1 , . . . of Algorithm 1, we focus on the sequence d0 , d1 , . . . of distance between the two robots, where dt = dist(pi (t), pj (t)). We first show that starting from an arbitrary initial configuration, the two robots eventually execute a Z-move. We have the following two lemmas. Lemma 1. When dt < d, there exists finite t′ > t such that d ≤ dt′ ≤ 3d. Proof. When dt < d, at least one robot executes the expanding move in P (t). The expanding move moves the two robots on the line containing pi (t) and pj (t), and each moving robot moves away from the other robot. Thus, we have dt+1 − dt ≥ δ. We also have dt+1 < 2d because dt+1 takes the largest value when the two robots move to their next positions in P (t). When dt+1 < d, at least one of the two robots perform the expanding move. Thus, we have dt < dt+1 < . . . and after at most ⌈(d − dt )/δ⌉ steps, the inter-robot distance becomes larger than d. ⊔ ⊓ Lemma 2. When dt ≥ 3d, there exists finite t′ > t such that d ≤ dt′ ≤ 3d. Proof. When dt ≥ 3d, at least one robot executes the shrinking move in P (t). The shrinking move moves the two robots on the line segment pi (t)pj (t), and each moving robot moves toward the other robot. Thus, we have dt − dt+1 ≥ δ. We also have dt+1 ≥ d because dt+1 takes the smallest value when the two robots move to their next positions in P (t). When dt+1 ≥ 3d, at least one
Hardwired Pattern Formation by Mobile Robots with Common Unit Distance
7
of the two robots perform the shrinking move. Thus, we have dt > dt+1 > . . . and after at most ⌈(dt − 3d)/δ⌉ steps, the inter-robot distance becomes smaller than 3d. ⊓ ⊔ We then show that the two robots eventually solve HW-PTF(2, d). Lemma 3. When d < dt < 3d, there exists finite t′ > t such that dt′ = d. Proof. Let pi (t) = p, pj (t) = q in P (t). If ri and/or rj are activated in P (t), they perform the Z-move. Let p′ and q ′ be the next positions of ri ’s Z-move and rj ’s next move, respectively. The moving distance of ri is q 1 ′ d2t − d2 , (1) dist(p, p ) = 2 which becomes smaller as dt becomes smaller. Due to non-rigid movement, robots may stop en route when they perform a Z-move. In this case, the inter-robot distance may become smaller than d and (at least) one robot performs the expanding move in P (t + 1). That is, an execution P (t), P (t + 1), P (t + 2), . . . may contain the expanding move. Let t′1 , t′2 , . . . be the time steps, such that at least one robot executes the Z-move in P (t′k ) for (k = 1, 2, . . .). We will show that dt′k+1 < dt′k for any k = 1, 2, . . ., that is, the input distance to the Z-move monotonically decreases. We first bound the inter-robot distance in t′k + 1, i.e., after some Z-move in t′k . We abuse the notation in the first paragraph: pi (t′k ) = p, pj (t′k ) = q, and p′ and q ′ be the next positions of ri ’s Z-move and rj ’s next move, respectively. If ri (rj , respectively) is not activated in t′k , p = p′ (q = q ′ , respectively). In the following, we use the coordinate system of Algorithm 1 and use Z0∗ to describe it. The trajectory of the Z-move for ri is the line segment pp′ , represented by the following equation of a line: q (dt′k + d)(dt′k − d)(3d − dt′k )(3d + dt′k ) dt′k x + y= 3(d2t′ − d2 ) 2 k
−
d ≤x≤ 2 t′k
d2t′ − 3d2 k
4dt′k
.
The trajectory of the Z-move for rj is the line segment qq ′ , represented by the following equation of a line: q (dt′k + d)(dt′k − d)(3d − dt′k )(3d + dt′k ) dt′k y= x − 3(d2t′ − d2 ) 2 k
−
d2t′ − 3d2 k
4d
t′k
≤x≤−
dt′k . 2
When ri ’s x coordinate changes by εi by a Z-move in P (t′k ), ri ’s coordinates in P (t′k + 1) is q (dt′k + d)(dt′k − d)(3d − dt′k )(3d + dt′k ) dt′k − + εi , εi . 2 3(d2t′ − d2 ) k
When rj ’s x coordinate changes by εj by a Z-move in P (t′k ), rj ’s coordinates in P (t′k + 1) is q (dt′k + d)(dt′k − d)(3d − dt′k )(3d + dt′k ) dt′k − εj , εj . 2 3(d2t′ − d2 ) k
8
Y. Kojima et al.
Thus, we obtain v u 2 (3d − dt′ )(3d + dt′ ) u 2 k k (εi + εj ) dt′k +1 = t εi + εj − dt′k + 9(d2t′ − d2 ) k
Let ε = εi + εj . We also have the following inequality. 0<ε≤ Putting all together, we obtain v u u 8d2t′ t k 9(d2t′ − d2 )
ε−
3d2t′ − 3d2 k
2dt′k
9(d2t′ − d2 )
.
!2
k
+
8dt′k
k
9d2 − d2t′
k
8
Hence, we obtain s
9d2 − d2t′
k
8
≤ dt′k +1 < dt′k .
We then show dt′k+1 < dt′k , that is, the input distance to the (k + 1)-st Z-move is smaller than that of the k-th Z-move. Case 1. When dt′k+1 > d, at least one of the two robots performs the Z-move in P (t′k + 1), i.e., t′k+1 = t′k + 1). Hence, we have dt′k+1 < dt′k . Case 2. When dt′k+1 < d, at least one of the two robots performs the expanding move in P (t′k + 1). By Lemma 1, there exists ℓ such that d ≤ dt′k +1+ℓ < 3d and t′k+1 = t′k + 1 + ℓ. By Algorithm 1, P (t′k + 2) obtained by the expanding move in P (t′k + 1) satisfies dt′k +1 < dt′ k+2 ≤ 2d − dt′ k+1 . By repeating this equation, dt′k +1 < dt′k +2 ≤ 2d − dt′k +1 dt′k +2 < dt′k +3 ≤ 2d − dt′k +2 ··· dt′k +1+ℓ < dt′k +ℓ ≤ 2d − dt′k +1+ℓ Hence, we have dt′k +1+ℓ = dt′k+1 < 2d − dt′k+1 . The maximum value of 2d − dt′k+1 is achieved when dt′k +1 takes the minimum value s 9d2 − d2t′ k . dt′k+1 < 2d − dt′k+1 ≤ 2d − 8 We will show
s 2d −
9d2 − d2t′
k
8
< dt′k .
(2)
By changing the inequality, we obtain s 2d − d
t′k
<
9d2 − d2t′
k
8
(3)
Hardwired Pattern Formation by Mobile Robots with Common Unit Distance
9
When 2d < dt′k < 3d, the right-hand side of equation (3) is positive and the left-hand side is negative. Hence, equation (3) holds. When d < dt′k ≤ 2d, by squaring both sides we obtain 2 16 49 9 dt′k − d − d2 < 0 9 9 This equation holds for d < dt′k ≤ 2d. Hence, for d < dt′k < 3d, equation (3) holds. Consequently, we have dt′k+1 < dt′k . That is, the input to the Z-move monotonically decreases even when the expanding moves are performed between two consecutive Z-moves. By the above discussion, we have dt′1 > dt′2 > . . .. By equation 1, the moving distance of the Z-move monotonically decreases, and there exists finite m such that in P t′m the moving distance of the Z-move is smaller than the minimum moving distance δ. Then, the moving robots reaches its destination and dt′m +1 = d holds. Of course, there might be other possibilities that the robots finish HW-PTF(2, d) by the expanding move or the shrinking move. ⊔ ⊓ By Lemma 1, 2, and 3, we have Theorem 1. 3.2
Two Oblivious ASYNC Robots
In this section, we show that two oblivious ASYNC robots cannot solve HW-PTF(2, d) by the fact that the two ASYNC robots must perform the Z-move in the final step. By definition, any SSYNC execution of some algorithm A is also an ASYNC execution of A. By the calculation of the Z-move for any SSYNC (thus ASYNC) activation, there exists no other next position except that of the Z-move that solves HW-PTF(2, d). On the other hand, Z-move does not consider all ASYNC schedules, that allows some robot to observe the position of moving robots. Each robot can observe the position of other robots, but cannot recognize which robot is moving. Hence, a robot may compute its next position for the Z-move without knowing whether the other robot is moving or not. We will first show that two robots cannot stop at distance d under such ASYNC schedule even when the robots always perform rigid movement. Lemma 4. Two oblivious deterministic ASYNC robots with rigid movement cannot finish HWPTF(2, d) by the Z-move for any d. Proof. The impossibility for d = 0 is clear from Theorem 1 because the set of all executions of the ASYNC model contains that of the SSYNC model, i.e., an impossibility result in the SSYNC model directly applies to the ASYNC model. We consider the following scenario shown in Figure 2. 1. In an initial configuration, ri is located at p = (−a/2, 0) and rj is located at q = (a/2, 0) (d < a < 3d). 2. First, ri is activated and computes its destination p′ of the Z-move, i.e., ! p (a2 − d2 )(9d2 − a2 ) a2 − 3d2 ′ , . p = 4a 4a 3. After ri has started its Z-move to p′ , rj observes ri at position p′′ such that dist(p′ , p′′ ) = δa . Then, rj computes its destination q ′′ of the Z-move. Assume that ri and rj succeeds in HW-PTF(2, d) in the above scenario, that is, dist(p′ , q ′′ ) = d. We first calculate the cosine of θ = ∠p′ qq ′′ under the above condition. Because p′′ lies on line pp′ , the coordinate of p′′ is ! r r p (a2 − d2 )(9d2 − a2 ) a2 − 3d2 9(a2 − d2 ) 9d2 − a2 − δa , − δa . 4a 8a2 4a 8a2
10
Y. Kojima et al. 𝑝′ 𝑝′′
𝑝
𝑑
𝑑
𝑑 𝑞
𝑞′′
Fig. 2. Z-moves under the ASYNC schedule
We can calculate dist(q, p′′ ) from the coordinates of q and p′′ . s r a2 − d 2 ′′ 2 2 dist(qp ) = d + δa + δa 2 For △p′ qp′′ , using the law of cosines, ′
2d2 + δa r
′′
cos ∠p qp =
q
a2 −d2 2
d2 + δa2 + δa
2d
q
!.
a2 −d2 2
We can calculate sin ∠p′ qp′′ from cos ∠p′ qp′′ . ′
δa
′′
sin ∠p qp =
q
9d2 −a2 2
r 2d
d2 + δa2 + δa
q
! a2 −d2 2
In an initial configuration where the inter-robot distance is a, the q q cosine of the angle formed
3 by the Z-move and the x-axis of Z0∗ is 2a dist(qp′′ ), we obtain
1 a2 −d2 2 , and its sine is 2a
9d2 −a2 . By replacing a with 2
v q u u δ 2 + δa a2 −d2 a 3 u 2 q cos ∠q ′′ qp′′ = √ t a2 −d2 2 2 d2 + δ 2 + δ a
a
2
v q u u 8d2 − δ 2 − δa a2 −d2 a 1 u 2 q . sin ∠q ′′ qp′′ = √ t a2 −d2 2 2 2 2 d + δ a + δa 2 Using the addition formulas of cosines, r q 3 2d2 + δa
cos ∠p′ qq ′′ =
a2 −d2 2
r q q q 2 2 2 2 9d2 −a2 δa2 + δa a −d − δ 8d2 − δa2 − δa a −d a 2 2 2 . (4) q √ 2 2 4 2 d2 + δa2 + δa a −d 2
We than calculate the cosine of ∠p′ qq ′′ under the condition that dist(p′ q ′′ ) = d. We also have dist(p′ q) = d by the Z-move and v q u r u 2 a2 −d2 ′′ 2 2 δ + δ t a a dist(qp ) − d 2 dist(qq ′′ ) = = . 2 2
Hardwired Pattern Formation by Mobile Robots with Common Unit Distance
11
△p′ qq ′′ is an isosceles triangle. So, we can calculate the cosine of ∠p′ qq ′′ directly. r q 2
2
δa2 + δa a −d 2 √ . (5) cos ∠p qq = 2 2d p p For simplicity, let a = sd (1 < s < 3) and δa = t (a2 − d2 )/2 = td (s2 − 1)/2 (0 < t < 1). We obtain the following equation by equations (4) and (5). p p 3(4 + t(s2 − 1)) (t2 + t)(s2 − 1) − t (s2 − 1)(9 − s2 )(16 − (t2 − t)(s2 − 1)) 16 + 8(t2 + t)(s2 − 1) p 2 2 (t + t)(s − 1) = 4 ′
′′
When t = (s − 1)/2 (1 < s < 3), the equation does not hold. Consequently, the ASYNC scheduler can forever prevent the two robots from solving HW-PTF(2, d) for and d > 0. ⊓ ⊔ Theorem 2. Two oblivious deterministic ASYNC robots cannot solve HW-PTF(2, d) for any d > δ. Proof. Assume that there exists an algorithm A that solves HW-PTF(2, d) from an arbitrary initial configuration for any d larger than the minimum moving distance δ. We will show that we can construct an infinite execution of A where the two robots never finish HW-PTF(2, d). Consider an execution P (0), P (1), P (2), . . . starting from an initial configuration P (0), and the sequence of inter-robot distance d0 , d1 , dt . . . at time t (t = 0, 1, 2, . . . ). We have the following three cases depending on the value of dt . – Case 1. 3d ≤ dt . If the two robots finish HW-PTF(2, d) in P (t + 1), at least one robot moves and its moving distance is equal to or larger than d. By d > δ, the adversary can stop that robot before it reaches its destination. Hence, we have an execution where dt+1 ̸= d. – Case 2. d < dt < 3d. If the two robots finish HW-PTF(2, d) after t, as already discussed, the two robots ri and rj must perform the Z-move. By Lemma 4, there exists an activation schedule, where ri first observes rj and starts a Z-move, and then rj observes ri en route and starts another Z-move, so that when ri and rj reach their destinations, the inter-robot distance is not d. – Case 3. dt < d. If the two robots finish HW-PTF(2, d) in P (t + 1), at least one robot moves away from the other robot. However, if ri moves away from rj when the inter-robot distance is dt , rj may perform the same movement when rj is also activated at t and obtain the same observation as ri . Hence, if HW-PTF(2, d) is finished in P (t + 1) by the movement of either ri or rj , there exists another execution where the adversary activates both robots in P (t), thus dt+1 ̸= d. Otherwise, HW-PTF(2, d) is finished in P (t + 1) by the simultaneous and same movement of ri and rj . There exists another execution where the adversary activates only one robot in P (t), thus dt+1 ̸= d. Hence, we can construct an infinite execution of A, where ri and rj never finish HW-PTF(2, d). ⊓ ⊔ 3.3
Two Luminous ASYNC Robots
In this section, we consider robots that are endowed with a light whose color belongs to a fixed palette [4]. Robots can see the light color of other robots, and modify the color of their own light during the compute phase. We present a positive result that two luminous deterministic robots can solve the HW-PTF problem, provided they share the same unit distance. Our approach is based on a bijection between a class of algorithms solving the rendezvous problem and their transformed version solving the HW-PTF for two robots.
12
Y. Kojima et al.
Luminous ASYNC Rendezvous Algorithms Let D > 0 denote the current inter-robot distance, with robot ri at position 0 and robot rj at position D in ri ’s local coordinate system. The rendezvous algorithms we consider are those that use only three kinds of moves: Stay The robot does not move. M2H (move to midpoint) The robot moves toward the other robot to the midpoint: target position D/2. If the robot is not interrupted, the new inter-robot distance is D/2. M2O (move to other) The robot moves to the other robot’s current position: target position D. If the robot is not interrupted, the new inter-robot distance is 0. These three movements are necessary and sufficient to achieve gathering [5]. A luminous rendezvous algorithm A for the ASYNC model is expressed as a table of guarded commands: each row maps a guard (typically the pair (my color, other’s color)) to a new color and a movement chosen from Stay, M2H, M2O. The guard “gathered” holds when both robots occupy the same position; “skip” means no change; “–” retains the current color; rule precedence is top-to-bottom. As a running example we use the Her2Cols algorithm of Heriban et al. [5]: Guard (Black, Black) (Black, White) gathered (White, Black) (White, White)
⇝ ⇝ ⇝ ⇝ ⇝ ⇝
New color, movement White, Stay skip skip –, M2O Black, M2H
The Her2Cols algorithm solves deterministic rendezvous in ASYNC [5] in a self-stabilizing manner (that is, starting from any initial configuration [7], regardless of the ASYNC scheduler). From Rendezvous ASYNC Algorithms to ASYNC HW-PTF(2, d) We first present new primitive movements that are dedicated to the HW-PTF(2, d). Let D > 0, D ̸= d, denote the current inter-robot distance. Define the signed excess distance D′ = D − d. We have D′ ∈ R \ {0}; in particular D′ < 0 when D < d. In ri ’s local coordinate system (with ri at 0 and rj at D), the two adapted movements are: M2Hd (halve the signed excess) Robot ri moves to the target position (D − d)/2 = D′ /2. – If D > d: this point is strictly between ri and rj ; the robot moves toward the other robot. – If D < d: this point lies on the opposite side of ri from rj (i.e., (D − d)/2 < 0); the robot moves away from the other robot. In both cases the new inter-robot distance is D − (D − d)/2 = (D + d)/2, and the new signed excess is D′ /2. M2D (reach distance exactly d) Robot A moves to the target position D − d. – If D > d: this point lies strictly between ri and rj ; the robot moves toward the other robot. – If D < d: this point lies on the opposite side of ri from rj (i.e., D − d < 0); the robot moves away from the other robot. In both cases the new inter-robot distance is |D − (D − d)| = d, and the new signed excess is 0. Both targets are computable and consistent for the two robots from the local snapshot alone: robot ri observes the distance D to rj , and d is a fixed parameter of the hardwired pattern. Since both robots share the same unit distance, the value of d is identical in the local coordinate systems of both robots. Setting D′ = D − d, the movements M2Hd and M2D act on the signed excess exactly as M2H and M2O act on the inter-robot distance in the rendezvous setting: M2Hd : D′ 7−→
D′ , 2
M2D : D′ 7−→ 0.
Hardwired Pattern Formation by Mobile Robots with Common Unit Distance
13
The goal condition “at distance d” corresponds to D′ = 0, exactly as “gathered” corresponds to D = 0. Given a gathering algorithm A, define its adapted algorithm Ad by applying the following three syntactic substitutions to every rule of A: 1. Replace every guard “gathered” with “at distance d”. 2. Replace every movement M2H with M2Hd . 3. Replace every movement M2O with M2D. The color palette, color guards, and color transitions are left unchanged. Applying this substitution to Her2Cols yields Her2Cols-d. The two algorithms are shown side by side below; only the three highlighted entries differ. Her2Cols (rendezvous) Guard ⇝ Color, move (Black, Black) ⇝ White, Stay (Black, White) ⇝ skip gathered ⇝ skip (White, Black) ⇝ –, M2O (White, White) ⇝ Black, M2H
Her2Cols-d (exact distance d) Guard ⇝ Color, move (Black, Black) ⇝ White, Stay (Black, White) ⇝ skip at distance d ⇝ skip (White, Black) ⇝ –, M2D (White, White) ⇝ Black, M2Hd
Guards match (my color, other’s color); “skip” means no change; “–” retains the current color; rule precedence is top-to-bottom. We now state our positive result. Theorem 3 (ASYNC Rendezvous ⇒ ASYNC HW-PTF(2, d)). Let d > 0. If a deterministic algorithm A using movements Stay, M2H, M2O solves rendezvous in the ASYNC model (starting from any initial configuration allowed by A), then its adapted algorithm Ad solves the HW-PTF(2, d) in the ASYNC model, starting from any initial configuration with D > 0 that corresponds to an allowed initial configuration of A via the map D 7→ D′ = D − d. Proof. We exhibit a bijection between executions of Ad and executions of A that preserves the scheduler, the color sequences, and the goal-achievement event. Step 1: Isomorphism of individual movements. Fix any execution of Ad with initial distance D0 > 0, D0 ̸= d. Define the signed excess distance at time t Dt′ = Dt −d, where Dt is the inter-robot distance at time t. – M2Hd maps Dt′ 7→ Dt′ /2, identical to the action of M2H on the inter-robot distance in the rendezvous setting. – M2D maps Dt′ 7→ 0, identical to the action of M2O. – Stay leaves Dt′ unchanged, identical to Stay. These identities hold regardless of the sign of Dt′ , i.e., for both D > d and D < d. Step 2: Isomorphism of movement resolution. The movement resolution rules of considered rendezvous algorithms govern what happens when two robots execute movements concurrently. The critical case is when both robots execute M2H simultaneously: the companion robot’s pending move is upgraded to M2O so that both robots eventually reach the same point. The analogous case in Ad is when both robots execute M2Hd simultaneously. In ri ’s coordinate system, ri starts at 0 and rj at D. ri moves to (D − d)/2. The companion robot rj ’s pending move is upgraded to M2D: rj moves to the point at distance d from ri ’s new position (D − d)/2, in the direction of rj from ri , i.e., to (D − d)/2 + d = (D + d)/2. rj therefore moves from D to (D + d)/2,
14
Y. Kojima et al.
which corresponds to moving by (D − d)/2 toward ri when D > d (since (D + d)/2 < D) and away from ri when D < d (since (D+d)/2 > D). The new inter-robot distance is |(D+d)/2−(D−d)/2| = d. In general, the movement resolution rules for Ad are obtained from those of A by replacing every occurrence of M2H by M2Hd , every occurrence of M2O by M2D , and every occurrence of “gathered” by “at distance d” (AT-D), and interpreting movements in terms of D′ . Because the excess distance at time t Dt′ follows the same arithmetic as Dt in the rendezvous setting, the outcome of every movement resolution event in Ad is identical (in terms of D′ ) to the outcome of the corresponding event in A. Step 3: Isomorphism of color dynamics. By Definition, the color guards and color transitions of Ad are identical to those of A. The only additional guard, “at distance d”, corresponds (via D′ = D − d) to D′ = 0, which corresponds to “gathered” in A. Hence the color sequence produced by Ad on any execution is identical to the color sequence produced by A on the corresponding execution in terms of D′ . Step 4: Conclusion. By Steps 1–3, there is a bijection φ between executions of Ad starting with excess D0′ = D0 − d and executions of A starting with distance D0 , that preserves the scheduler and the color sequence. Under φ, the event “Ad reaches the goal D = d (i.e., D′ = 0)” corresponds exactly to the event “A achieves rendezvous (D = 0)”. Since A solves rendezvous from any allowed initial configuration, A drives D0 to 0 in every fair execution. Equivalently, under φ, Ad drives D0′ = D0 − d to 0 in every fair execution, i.e., it drives D0 to d. Therefore, Ad solves HW-PTF(2, d) in ASYNC. ⊔ ⊓ Applying Theorem 3 to the Her2Cols algorithm [5], and observing that oblivious robots (so, with a single color) cannot solve HW-PTF for two robots (Theorem 2), yields the following corollary: Corollary 1 (Her2Cols-d). Her2Cols-d solves the HW-PTF problem for two robots in the ASYNC model, for any initial inter-robot distance D > 0. Moreover, it uses only two colors (which is optimal) and is self-stabilizing. Observe that our transformation applies to every deterministic gathering algorithm using only Stay, M2H, M2O —a necessary condition for gathering [5]. This covers, in particular, Vig3Cols (for ASYNC) [12], and Her2Cols (for ASYNC) [5]: in each case the adapted algorithm solves exact-distance-d under the same synchrony model with the same number of colors.
4
Hardwired Pattern Formation for More than Four SSYNC Robots
In this section, we present a HW-PTF algorithm for oblivious SSYNC robots. We present a “sizeadjusting” algorithm that shrinks or expands the SEC of the robots to a specified size d. We can obtain a HW-PTF algorithm by combining the proposed algorithm and some existing pattern formation algorithm [11], that does not change the SEC of the robots, i.e., the robots execute the proposed algorithm until their size becomes d, and a pattern formation algorithm after that. Existing papers showed that the robots can form a target pattern F from an initial configuration I only if ρ(F ) is divisible by ρ(I) due to impossibility of symmetry breaking [9, 11, 13]. That is, the robots at symmetric positions w.r.t. ρ(I) forever perform symmetric movement in the worst case. This impossibility also holds for the HW-PTF problem. We will prove that the condition is also sufficient by a HW-PTF algorithm. 4.1
Size-adjusting Algorithm
Consider a naive shrinking algorithm that moves the robots toward the center of the SEC so that the size of a resulting configuration is d. This algorithm guarantees the convergence to size d, but
Hardwired Pattern Formation by Mobile Robots with Common Unit Distance
15
not the adjustment to size d due to SSYNC activation of robots. Another issue is how to prevent the symmetricity of the robots from increasing. Our key idea is to keep the center c(P (0)) of an initial configuration P (0) by ρ(P (0)) robots closest to the center. Intuitively, the robots can adjust their size by moving to a point at distance d/2 from c(P (0)) along the radius of the SEC while the initial symmetricity is maintained by the ρ(P (0)) robots closest to the center. We explain the detail with the case where the robots shrink their size. There are two principles for the proposed algorithm. First, each robot moves on the radius, i.e., the half line starting from c(P (0)) and passing through its current position. Second, each radius has designated positions, i.e., Pi positions at distance d j=1 (1/2)j+1 (i = 1, 2, . . .) from c(P (0)). Let hi denote the i-th designated position. On each radius, the proposed algorithm relocates the i-th robot from c(P (0)) at hi . However, the first and the last designated positions can be empty because some robots closest to c(P (0)) move closer to keep c(P (0)) and some robots stop at distance d/2 from c(P (0)) to finish the adjustment. The center of P (0) can be easily maintained if the robots create a multiplicity at c(P (0)) and no other multiplicity is created. However, it is impossible to resolve a multiplicity by a deterministic algorithm once it is created. Instead, the proposed algorithm keeps c(P (0)) by the minimum distance between the robots. For a set P of points, let dh (P, q, d) denote the minimum distance between the points in P when all points are relocated at designated positions when the center (i.e., the starting point of radius) is q. That is, for each point p ∈ P , we consider the half line qp. Pi If p is the i-th point from q on qp, its designated position is hi = d j=1 (1/2)j+1 from q. Then, dh (P, q, d) is the minimum distance among the robots in such a virtual relocated configuration. Let {P (0)1 , P (0)2 , . . . , P (0)n/ρ(P ) } be the ρ(P (0))-decomposition of an initial configuration P (0). The proposed algorithm first sends the robots in P (0)1 toward c(P (0)) to create the minimum distance among the robots during any execution. The diameter of such regular ρ(P (0))gon must be smaller than dmin (P (0)), d/16, and dh (P (0), c(P (0)), d). Hence, we adopt d∗ = (1/2)(min{dmin (P (0)), d/16, dh (P (0), c(P (0)), d)}). When ρ(P (0)) = 1, the proposed algorithm selects the first two elements of the ρ(P (0))-decomposition of P (0), that does not change SEC(P (0)) when they move to the interior of SEC(P (0)). Let P (0)i , P (0)j (i < j) be these two elements. Then, P (0)i moves toward c(P (0)) along its radius but stops δ before the center. Then, P (0)j moves toward c(P (0)) along its radius and stops at the point where the inter-robot distance with P (0)i becomes smaller than d∗ . Thus, the center is perturbed but it is not a problem as explained later. In an arbitrary configuration P , the robots can agree on the center encoded by the above method by the following procedure. First, each robot checks the pairs of robots achieving the minimum inter-robot distance. Let k be the number of such robots. Second, it checks whether k ≤ n/2. Third, it checks whether the k robots form a regular k-gon containing no point of P . Finally, it checks whether the diameter of the SEC of the regular k-gon is smaller than d/16. If the regular k-gon satisfies all these conditions, the proposed algorithm considers its center as the center for adjustment, and we say the robots can recognize the center in P . We finally check the “fictitious” center in some initial configurations. For a set P of points and a point q ̸∈ P , we consider the symmetricity and decomposition w.r.t. q. Consider a decomposition of P into regular k-gons centered at q. The maximum value of such k is the symmetricity of P w.r.t. q denoted by ρ∗ (P, q). We also define SEC and LEC w.r.t. q. The SEC of P w.r.t. q is the smallest circle centered at q and contains all points of P in its interior of boundary. The LEC of P w.r.t. q is the largest circle centered at q and contains no point of P in its interior. We have the following property. Observation 2 For any set P of multiple points, ρ∗ (P, q) = 1 when q ̸= c(P ). ⌢
Proof. Let st be the diameter of SEC(P ) perpendicular to line segment qc(P ). The arc st of SEC(P ) (including the two endpoints) in the opposite side w.r.t. q contains at least one point
16
Y. Kojima et al.
u ∈ P . If ρ∗ (P, q) > 1, the circle C ′ centered at q with radius dist(qu) contains at least one symmetric point u′ for u. The two circles SEC(P ) and C ′ has at most two intersections, and let u′ be the another intersection. Because ∠uqu′ < π, circle C ′ must contain at least another point to have ρ∗ (P, q) > 1, a contradiction. ⊔ ⊓ Such a fictitious center can be generated by the movement toward c(P ) due to SSYNC activation. Whenever the center q is recognized in a configuration P , the size-adjusting algorithm checks ρ∗ (P, q) and rearranges the robots that keeps the minimum distance around q according to ρ∗ (P, q). Hence, symmetricity of the configuration does not increase during any execution. When a robot moves along its radius, it moves cautiously so that it does not create a new minimum distance. That is, on each radius if the i-th robot ri wants to move to its designated position hi and some other robots are on the trajectory, ri just wait these robots to reach their designated positions. This does not result in a deadlock because the robots do not need to pass the other robots. When the robots expand to size d, the center is recognized by a regular polygon of size smaller than (1/2)(min{dmin (P ), rad(P )/16}) and the robots are not required to relocate on designated positions. Consequently, the adjusting algorithm consists of the following three steps. Let P be the current configuration and P1 , P2 , . . . , Pn/ρ(P ) be the ρ(P )-decomposition of P . – Step 1. Form a single center. When the robots cannot recognize a center in P , P1 moves toward c(P ) to create a regular ρ(P )-gon with a size discussed above. – Step 2. Move to designated positions when rad(P ) > d. When the robots can recognize the single center q in P , let {P1′ , P2′ , . . . , Pn/ρ∗ (P,q) } be the decomposition of P into these regular ′ ρ∗ (P, q)-gons. Then, each robot in P \ P1′ ∪ Pn/ρ ∗ (P,q)−1 move to their designated positions. – Step 3. Shrink or expand w.r.t. the recognized center. When the robots can recognize the ′ single center q in P , and P2′ , P3′ , . . . , Pn/ρ ∗ (P,q)−1 are on their designated positions, the robots ′ in Pn/ρ∗ (P,q) move toward or away from q to form a circle with diameter d centered at q. Figure 3 shows an example of shrinking execution of the adjusting algorithm. The red circle is a circle of diameter d, and the blue circle is a circle of diameter d/2. In an initial configuration P (0) (Figure 3 (a)), ρ(P (0)) = 4 and only two robots on LEC(P ) moves toward c(P (0)) in Step 1. The robots can recognize the center in P (1) (Figure 3 (b)). Then, other robots move to their designated positions (Figure 3 (a)). In P (3) (Figure 3 (d)), the robots finish Step 2 and the robots on SEC(P (3)) moves toward the circle of diameter d. The proposed algorithm works for more than four robots because when the symmetricity of the configuration P is one, it sends two robots to the interior of SEC, which requires at most three robots to be kept. Algorithm 2 shows the proposed size-adjusting algorithm for robot ri . 4.2
Correctness
Let Cn be the set of all configurations of the n robots. Then, we consider the decomposition of Cn into the terminal configurations of the three steps. – Cd ∈ Cn be the set of all configurations P of the n robots, where the diameter of SEC(P ) is d. – Cn,center ⊆ Cn \Cd be the set of all configurations of the n robots, where the center is recognized. – Cn,aligned ⊆ Cn,center be the set of all configurations of the n robots, where the robots are on their designated positions. Lemma 5. In any execution P (0), P (1), P (2), . . . of Algorithm 2 starting from an initial configuration P (0) ∈ Cn \ Cd , there exists finite t such that P (t) ∈ Cn,center , P (t) does not contain any multiplicity, and ρ(P (0)) ≥ ρ(P (t)).
Hardwired Pattern Formation by Mobile Robots with Common Unit Distance
Algorithm 2 Hardwired_Pattern_For_Multi_Robots(P, T, d) at robot ri Input at robot ri P : current configuration T : target pattern d: size of the target pattern Notations P1 , P2 , . . . , Pn/ρ(P ) : ρ(P )-decomposition of P c′ (P ): single recognized center in P if any P1′ , P2′ , . . . , Pk′ : ρ∗ (P, c′ (P ))-decomposition of P SEC ′ (P ): the smallest enclosing circle of P centered at c′ (P ) LEC ′ (P ): circle centered at c′ (P ) and containing P1′ d∗ : Minimum distance to make a center recognized Movement rule All movements are along ri ’s radius toward c(P ) unless specified otherwise Algorithm If rad(P ) = d/2 then terminate Else If a single center is not recognized in P then // Step 1 If ρ(P ) = n then move to the point at distance d/2 from c(P ) If ρ(P ) = 1 then Let Pi and Pj (i < j) be the elements with the minimum indices of the ρ(P )-decomposition of P satisfying SEC(P ) = SEC(P \ (Pi ∪ Pj )). If ri ∈ Pi then move toward c(P ) but stop before reaching c(P ) Else if ri ∈ Pj then move to a position at distance d∗ from P1 If (ρ(P ) ̸= 1, n) and (ri ∈ P1 ) then move to a position at distance d∗ /2 from c(P ) Else // c′ (P ) is recognized If (radius of SEC ′ (P ) is larger than d/2) and (ri is not on its designated position) then // Step 2 If ((ρ∗ (P, c′ (P )) > 1) and (ri ∈ P \ (P1′ ∪ Pk′ ))) or ′ ((ρ∗ (P, c′ (P )) = 1) and (ri ∈ P \ (P1′ ∪ P2′ ∪ Pk−2 ∪ Pk−1′ ∪ Pk′ ))) then Move cautiously toward ri ’s designated position but stop before creating a new minimum distance pair Else // Step 3 If (radius of SEC ′ (P ) is not d/2) then If ((ρ∗ (P, c′ (P )) > 1) and (ri ∈ Pk′ )) or ′ ((ρ∗ (P, c′ (P )) = 1) and (ri ∈ Pk−2 ∪ Pk−1′ ∪ Pk′ ))) then Move to the position at distance d/2 from c′ (P ) Else // ρ∗ (P, c′ (P )) = 1 and rad(P ) ̸= d/2 // i.e., SEC ′ (P ) has an empty half arc If ri is the counterclockwise endpoint of the longest empty arc of SEC ′ (P ) then Move counterclockwise along SEC ′ (P ) until it form a diameter with another robot on SEC ′ (P )
17
18
Y. Kojima et al.
(a) P (0)
(b) P (1)
(d) P (3)
(e) P (4)
(c) P (2)
Fig. 3. Example of the adjusting algorithm when the robots shrink
Proof. We consider a configuration P ̸∈ Cn,center . The robots can agree on the total ordering among the elements of the ρ(P )-decomposition of P , say {P1 , P2 , . . . , Pn/ρ(P ) }. Algorithm 2 sends P1 to the interior of LEC(P ) so that their destinations form a new minimum distance. In the SSYNC model, at least one robot moves toward c(P ). If ρ(P ) < n, Pn/ρ(P ) does not move and in the resulting configuration P ′ , c(P ′ ) = c(P ). Thus, the distance to c(P ′ ) and the moving robot becomes smaller than that in P . During the transition from P to P ′ , ρ(P ′ ) may become smaller due to SSYNC activation and non-rigid movement. However, the first element of the ρ(P ′ )-decomposition of P ′ moves toward c(P ′ ) to form a new minimum distance. In this way, Step 1 of Algorithm 2 is repeated until the robots reach some configuration in Cn,center . The movements of Step 1 does not create any multiplicity because for each radius of SEC(P ), at most one robot nearest to c(P ) moves toward c(P ). If ρ(P ) = n, we have the following two cases. If the SEC(P ′ ) of the resulting configuration ′ P is the same as SEC(P ), the distance between c(P ′ )(= c(P )) and the moving robot becomes smaller. Otherwise, SEC(P ′ ) is contained in SEC(P ), and the distance between c(P ′ ) and the moving robot becomes smaller. In the same way as the previous case, the robots eventually reach some configuration in Cn,center . ⊔ ⊓ Lemma 6. We consider an initial configuration P (0) ∈ Cn,center such that rad(P (0)) is larger than d/2. In any execution P (0), P (1), P (2), . . . of Algorithm 2, there exists finite t such that P (t) ∈ Cn,aligned and ρ(P (0)) ≥ ρ(P (t)). Proof. Algorithm 2 sends the robots to their designated positions by cautious walk so that the robots do not create a new minimum distance. If no robot can move in P (t) ̸∈ Cn,aligned , there exists at least one pair of robots on the same radius heading to opposite directions. This is a contradiction because assignment of the designated positions does not contain any such intersections. Hence, the designated positions are gradually occupied and the robots eventually reach a configuration in Cn,aligned .
Hardwired Pattern Formation by Mobile Robots with Common Unit Distance
19
During the execution, the symmetricity among the robots does not increase because P (0) ∈ Cn,center and the robots nearest to the recognized center keeps the symmetricity. ⊔ ⊓ Lemma 7. In any execution P (0), P (1), P (2), . . . of Algorithm 2 there exists finite t where P (t) ∈ Cd . Proof. We first consider the case where the size of P (0) is larger than d. By Lemma 5 and 6, the robots eventually reach a configuration P (t) in Cn,aligned . In P (t), the robots on SEC(P (t)) move toward the recognized center. By P (t) in Cn,aligned , there is no other robot on the trajectory, and this movement does not create a new minimum distance. Hence, in P (t + 1), the recognized center is the same, and the robots at distance larger than d/2 from the recognized center move toward the center. In this way, Step 3 of Algorithm 2 is repeated until the size of the current configuration becomes d. When the size of P (0) is smaller than d, we have the same discussion. ⊓ ⊔ Consequently, we have the following theorem. Theorem 4. More than four oblivious SSYNC robots can translate an initial configuration P with rad(P ) ̸= d/2 into another configuration P ′ with rad(P ′ ) = d/2 and ρ(P ′ ) ≤ ρ(P ) by Algorithm 2. The size-adjusting algorithm allows the robots on the SEC centered at the recognized center to move in the final step. Hence, we have the following Corollary. Corollary 2. The size-adjusting algorithm terminates as soon as the size of SEC of the robots becomes the specified size d. Fujinaga et al. proposed a pattern formation algorithm for oblivious ASYNC robots [9], that does not change the SEC during any execution. We can obtain a HW-PTF algorithm by combining Algorithm 2 with the pattern formation algorithm in [9]: the robots switch between the two algorithms based on the size of their SEC, i.e., if their SEC is larger than the size of the target pattern, each robot executes our size adjusting algorithm, otherwise each robot executes the pattern formation algorithm. Theorem 5. When n(≥ 5) oblivious SSYNC robots agree on the unit distance, they can solve the HW-PTF problem for a target pattern F from any initial configuration I if and only if ρ(I) divides ρ(F ).
5
Conclusion
In this paper, we newly introduced the HW-PTF problem, that requires the robots to form a target pattern in a specified size. We started with the HW-PTF problem for two robots and showed the problem is solvable for oblivious SSYNC robots when the specified size is not zero. We then showed the problem is not solvable for oblivious ASYNC robots while it is solvable by oblivious ASYNC robots equipped with lights. Finally, we presented a size-adjusting algorithm for the oblivious SSYNC robots and showed that we can obtain a HW-PTF algorithm by combining it with an existing pattern formation algorithm. There are interesting future directions. First, the HW-PTF problem for more than two oblivious ASYNC robots is open. We believe that we can extend the impossibility for two ASYNC robots for initial configurations where n (n > 2) ASYNC robots forming a regular n-gon. On the other hand, size-adjusting could be possible for other initial configurations. Another direction is to consider HW-PTF problem in the 3D space; obviously this setting would require considering 3D rotational symmetry [14]. Finally, all results in this paper consider deterministic algorithms. We conjecture that our impossibility results for two deterministic ASYNC robots can be extended to the case of two probabilistic ASYNC robots.
20
Y. Kojima et al.
Acknowledgements We thank Nicola Santoro and Paola Flocchini for originally proposing the hardwired pattern formation problem studied in this paper.
References 1. Bramas, Q., Lamani, A., Tixeuil, S.: The agreement power of disagreement. Theor. Comput. Sci. 954, 113772 (2023). https://doi.org/10.1016/J.TCS.2023.113772, https://doi.org/10.1016/j.tcs.2023.113772 2. Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Distributed computing by mobile robots: gathering. SIAM J. Comput. 41(4), 829–879 (2012). https://doi.org/10.1137/100796534 3. Courtieu, P., Rieg, L., Tixeuil, S., Urbain, X.: Impossibility of gathering, a certification. Inf. Process. Lett. 115(3), 447–452 (2015). https://doi.org/10.1016/J.IPL.2014.11.001, https://doi.org/10.1016/j.ipl.2014.11.001 4. Das, S., Flocchini, P., Prencipe, G., Santoro, N., Yamashita, M.: Autonomous mobile robots with lights. Theor. Comput. Sci 609, 171–184 (2016). https://doi.org/10.1016/j.tcs.2015.09.018 5. Défago, X., Heriban, A., Tixeuil, S., Wada, K.: Using model checking to formally verify rendezvous algorithms for robots with lights in euclidean space. Robotics Auton. Syst. 163, 104378 (2023). https://doi.org/10.1016/J.ROBOT.2023.104378, https://doi.org/10.1016/j.robot.2023.104378 6. Dieudonné, Y., Petit, F., Villain, V.: Leader election problem versus pattern formation problem. In: Proceedings of the 24th International Symposium on Distributed Computing Distributed Computing. pp. 267–281 (2010). https://doi.org/10.1007/978-3-642-15763-9_26 7. Dijkstra, E.W.: Self-stabilizing systems in spite of distributed control. Commun. ACM 17(11), 643–644 (1974). https://doi.org/10.1145/361179.361202, https://doi.org/10.1145/361179.361202 8. Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Arbitrary pattern formation by asynchronous, anonymous, oblivious robots. Theor. Comput. Sci. 407, 412–447 (2008). https://doi.org/10.1016/j.tcs.2008.07.026 9. Fujinaga, N., Yamauchi, Y., Ono, H., Kijima, S., Yamashita, M.: Pattern formation by oblivious asynchronous mobile robots. SIAM J. Comput. 44(3), 740–785 (2015). https://doi.org/10.1137/140958682 10. Hahn, C., Harbig, J., Kling, P.: Forming Large Patterns with Local Robots in the OBLOT Model. In: Proceedings of the 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). pp. 14:1–14:20 (2024). https://doi.org/10.4230/LIPIcs.SAND.2024.14 11. Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: Formation of geometric patterns. SIAM J. Comput. 28(4), 1347–1363 (1999). https://doi.org/10.1137/S009753979628292X 12. Viglietta, G.: Rendezvous of two robots with visible bits. In: Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS). pp. 291–306 (2013). https://doi.org/10.1007/978-3-642-45346-5\_21 13. Yamashita, M., Suzuki, I.: Characterizing geometric patterns formable by oblivious anonymous mobile robots. Theor. Comput. Sci. 411, 2433–2453 (2010). https://doi.org/10.1016/j.tcs.2010.01.037 14. Yamauchi, Y., Uehara, T., Kijima, S., Yamashita, M.: Plane formation by synchronous mobile robots in the three dimensional euclidean space. Journal of the ACM 64, 16:1–16:43 (2017). https://doi.org/10.1145/3060272 15. Yamauchi, Y., Yamashita, M.: Pattern formation by mobile robots with limited visibility. In: Proceedings of the 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2013). pp. 201–212. Springer International Publishing (2013). https://doi.org/10.1007/9783-319-03578-9_17