Quentin Bramas

Stéphane Devismes

Anaïs Durand

Pascal Lafourcade

Anissa Lamani

Beedroids: How Luminous Autonomous Swarms of UAVs Can Save the World?

Keywords: 2012 ACM Subject Classification Theory of computation → Distributed algorithms Bee extinction, luminous swarms of beedroids, perpetual flower pollination problem, greenhouse. Digital Object Identifier 10.4230/LIPIcs.CVIT.2016.23

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Bees are crucial for human beings. They have limited life span: only few weeks for the workers and up to 6 years for the queen. The United Nation (UN) dedicates the 20th of May as the "Bee day". 1 UN says that "we all depend on the survival of bees". Indeed, pollination is a fundamental process for the survival of our ecosystems. Nearly 90% of the world's wild flowering plant species depend on pollination. There are more than 800 wild bee species, seven of which are classified by the International Union for Conservation of Nature 2 (IUCN) as critically endangered. A further 46 are endangered, 24 are vulnerable, and 101 are near threatened. Many associations like Greenpeace 3 or World Wild Foundation 4 (WWF) are protecting bees and helping to avoid their extinction.

Our goal here is to anticipate by considering the worst-case: the bee extinction. We propose solutions to save humanity using Beedroids. Beedroids are artificial bees that aim at pollinating flowers autonomously in a greenhouse. Such a technology can also be used in the Mars colonization. For example, the Biosphere 2 project5 was meant to demonstrate the viability of closed ecological systems to support and maintain human life in outer space. Beedroids are mandatory to implement such a project since it is not yet clear whether bees can survive interstellar trips.

A beedroid is a small autonomous Unmanned Aerial Vehicles (UAV) that mimics the behavior of a real bee. A famous ability of bees is stigmergy, i.e., indirect communication through the movements. Implementing stigmergy requires perfect synchronization and visibility sensors. Consequently, we consider here a fully synchronous look-compute-move model of computation [START_REF] Suzuki | Distributed anonymous mobile robots: Formation of geometric patterns[END_REF] (FSYNC). As explained before, beedroids will be deployed in greenhouses. So, each beedroid swarm will have to perpetually explore its greenhouse to find flowers and pollinate them. We assume greenhouses are finite cuboids. Each of these cuboids should be divided into cells to visit. Thus, we conveniently discretized a cuboid-shaped greenhouse as a finite 3D grid. Then, the problem we have to solve consists in coordinating a swarm of beedroids to perpetually explore a finite 3D grid in an exclusive manner (meaning that two beedroids cannot occupy the same place simultaneously).

The world bee population constantly decreases but is still incredibly huge as compared to human population. As a matter of facts, a bee colony is constituted of around 50 000 bees and in 2018 it was estimated that there were around 800 000 bee colonies in Canada for example. So, to eventually be able to replace bees, we should (1) solve pollination of greenhouses with the smallest possible number of beedroids and (2) also be able to massively produced them. Consequently, the design of beedroids should be as simple as possible. Below we list and motivate our main design choices. Visibility Sensors: To maximize their flight time, we should save energy. Hence, the visibility range of beedroids should be as small as possible. Communication: As previously explained, the communication between beedroids, like real bees, is indirect and based on positions of other bees. To vastly increase stigmergic communication, without compromising production cost and energy consumption, we have only endowed them with LED lights of a few colors that can be sensed by other beedroids within a short distance. Memory: Still to save energy and manufacturing costs, beedroids have no permanent memory, except the color of their lights. They only have a short-term working memory allowing them to compute a decision (destination and new light color) at each step of their algorithm. Orientation: Manufacturing costs and energy consumption also prevent us from endowing beedroids with GPS. Instead, we use chirality facilities making beedroids able to distinguish the two sides of a symmetrically reflexive panorama.

Contribution. To bring our own stone to the world safeguarding, we propose to implement pollination into cuboid-shaped greenhouses using swarms of artificial bees, so-called beedroids. Solving this problem requires to coordinate each swarm so that it perpetually explores a 3D grid. As motivated before, we should both minimize the size of the swarm (i.e., the number of beedroids that compose it) and the capabilities used by those beedroids. We first study the problem in the FSYNC model assuming the optimal visibility range one. Under this assumption, we show that three beedroids are necessary and sufficient to solve the problem. For the sufficient part, we propose an algorithm that requires only five colors. Then, we look for another solution optimal in terms of colors, still in FSYNC model. Actually, the solution we propose works with oblivious beedroids, i.e., beedroids endowed with only one light color. This second solution requires five beedroids and visibility range two.

In order to help the reader, online animations illustrating the behavior of our algorithms are available for our two solutions: [3] and [4].

23:3

Roadmap. In the next section, we formally define the model, the beedroid skills, and the problem to solve, so-called the Perpetual Flower Pollination Problem (PFPP). In Section 3, we present the lower bound on the number of beedroids necessary to solve the PFPP under visibility range 1. In Sections 4 and 5, we present two algorithms solving the PFPP. Section 6 is dedicated to related work. Finally, we make concluding remarks in Section 7. Due to the lack of space, several proofs have been moved into the appendix.

Preliminaries

We consider a swarm of n > 0 beedroids (n.b., n is a priori unknown by beedroids) evolving in a greenhouse modeled as a finite 3D grid of size

S x × S y × S z , with S x ≥ n, S y ≥ n, S z ≥ n, i.e., an undirected graph G(V, E) where V = {(i, j, k) : i ∈ [0, S x -1], j ∈ [0, S y -1], k ∈ [0, S z -1]} and E = {(i, j, k), (i ′ , j ′ , k ′ )} : |i -i ′ | + |j -j ′ | + |k -k ′ | = 1 .
Note that coordinates are used for the analysis only, i.e., beedroids cannot access them.

We assume discrete time and at each round, the beedroids synchronously perform a Look-Compute-Move cycle. In the Look phase, a beedroid gets a snapshot of the subgraph induced by the nodes within distance Φ ∈ N * from its position. Φ is called the visibility range of the beedroids. The snapshot is not oriented in any way as the beedroids do not agree on the orientation of any of the three axes of the coordinate system. However, it is implicitly ego-centered since the beedroid that performs a Look phase is located at the center of the subgraph in the obtained snapshot. Then, each beedroid computes a destination in its local coordinate system (either Front, Back, Left, Right, Above, Below, or Idle) based on the received snapshot only. Finally, it moves towards its computed destination.

We forbid any two beedroids to occupy the same node simultaneously. A node is occupied when a beedroid is located at this node, otherwise it is empty. Beedroids have lights with maybe different colors that can be seen by beedroids within distance Φ from them. We denote by Cl the set of all possible colors (|Cl| = 1 corresponds to the case of oblivious beedroids).

The state of a node is either the color of the light of the beedroid located at this node, if it is occupied, or ⊥ otherwise. In the Look phase, the snapshot includes the state of the nodes (within distance Φ). During the compute phase, a beedroid may decide to change the color of its light (of course, if |Cl| > 1).

In all our algorithms, we also prevent any two beedroids from traversing the same edge simultaneously. Since we already forbid them to occupy the same position simultaneously, this means that we additionally prevent beedroids from swapping their positions. Algorithms verifying this property are said to be exclusive. However, to be as general as possible, we do not make this additional assumption in our impossibility result.

Configurations. A configuration C in a 3D grid G(V, E) is a set of pairs (p, c),
where p ∈ V is an occupied node and c ∈ Cl is the color of the beedroid located at p. A node p is empty if and only if ∀c, (p, c) / ∈ C. We sometimes just write the set of occupied nodes when the colors are clear from the context.

Views. We denote by G r the globally oriented view centered at the beedroid r, i.e., the subset of the configuration containing the states of the nodes at distance at most Φ from r, translated so that the coordinates of r is (0, 0). We use this globally oriented view in our analysis to describe the movements of the beedroids (see, for example, Figure 1): when we say "the beedroid moves Left", it is according to the globally oriented view. However, since beedroids do not agree on any axis, they have no access to the globally oriented view. When a beedroid looks at its surroundings, it instead obtains a local view. To model this, we assume that the local view acquired by a beedroid r in the Look phase is the result of an arbitrary indistinguishable transformation on G r . Here, we assume that beedroids are self-inconsistent, meaning that different transformations may be applied C V I T 2 0 1 6 at different rounds. An indistinguishable transformation consists of applying to each of the three axes (x-axis, y-axis, and z-axis) passing through r a rotation (maybe different for each axis) picked in the set {0, π 2 , π, 3π 2 }. We denote by IT the set of all possible indistinguishable transformations. Nevertheless, beedroids share a common chirality, which means that their local view is not a reflection (also called mirroring) of the global view. Having a common chirality allows a beedroid to distinguish a local view from its reflection and so take different decisions in such cases (e.g., chirality allows to discriminate Above from Below in Rule R 1 of Figure 1). In other words, having a common chirality allows, given two axes, to determine a third one using the right-hand rule.

It is important to note that when a beedroid r computes a destination d, it is relative to its local view f (G r ), which is the globally oriented view transformed by some f ∈ IT . So, the actual movement of the beedroid in the globally oriented view is f -1 (d). For example, if d = Above but the beedroid sees the 3D grid upside-down (f is the π-rotation along the y-axis), then the beedroid moves Below = f -1 (Above). In a configuration C, V C (i, j) denotes the globally oriented view of a beedroid located at (i, j).

A beedroid is said to be lost when it sees no wall and no other beedroids. Observe that in this case, if the beedroid decides to move, the destination is entirely determined by the choice of the transformation f done by the adversary.

Algorithm. An algorithm A is a tuple (Cl, Init, T ) where Cl is the set of possible colors, Init is a mapping from any considered 3D grid to a non-empty set of initial configurations in that 3D grid, and T is the transition function V iews → {Idle, Front, Back, Left, Right, Above, Below} × Cl, where V iews is the set of local views. When the beedroids are in Configuration C, a configuration C ′ obtained after one round satisfies: ((i, j, k), c ′ ) ∈ C ′ , if and only if there exists a color c ∈ Cl and a transformation f ∈ IT such that one of the following conditions holds:

((i, j, k), c) ∈ C and f -1 • T • f • V C (i, j, k) = (Idle, c ′ ), ((i -1, j, k), c) ∈ C and f -1 • T • f • V C (i -1, j, k) = (Right, c ′ ), ((i + 1, j, k), c) ∈ C and f -1 • T • f • V C (i + 1, j, k) = (Left, c ′ ), ((i, j -1, k), c) ∈ C and f -1 • T • f • V C (i, j -1, k) = (Front, c ′ ), ((i, j + 1, k), c) ∈ C and f -1 • T • f • V C (i, j + 1, k) = (Back, c ′ ), ((i, j, k -1), c) ∈ C and f -1 • T • f • V C (i, j, k -1) = (Above, c ′ ), or ((i, j, k + 1), c) ∈ C and f -1 • T • f • V C (i, j, k + 1) = (Below, c ′ ).
We denote by C ⇝ C ′ the fact that C ′ can be reached in one round from C (n.b., ⇝ is then a binary relation over configurations). An execution of Algorithm A in a 3D grid G is then a sequence

(C i ) i∈N of configurations such that C 0 ∈ Init(G) and ∀i ≥ 0, C i ⇝ C i+1 .
The Perpetual Flower Pollination Problem. An execution (C i ) i∈N in a 3D grid G = (V, E) achieves the Perpetual Flower Pollination Problem (PFPP) if for every node u ∈ V and for every time t, there exists a time t ′ ≥ t such that u is occupied in C t ′ .

An algorithm A that uses n beedroids solves the PFPP problem if, for every finite 3D grid G = (V, E) of size at least n × n × n and every initial configuration C 0 ∈ Init(G), we have every execution of A in G starting from C 0 that achieves the PFPP.

An Algorithm as a Set of Rules. We write an algorithm as a set of rules, where a rule is a triplet (V, d, c) ∈ V iews × {Idle, Front, Back, Left, Right, Above, Below} × Cl. We say that an algorithm (Cl, Init, T ) includes the rule (V, d, c), if T (V ) = (d, c). By extension, the same rule applies to indistinguishable views, i.e., ∀f ∈ IT , T (f (V )) = (f (d), c). Consequently, we forbid an algorithm to contain two rules (V, d, c) and (V ′ , d ′ , c ′ ) such that V ′ = f (V ) for some f ∈ IT .

As an illustrative example, consider the rule R 1 given in Figure 1. This rule is defined for beedroids having a visibility range of one. This rule means that, when a beedroid sees two beedroids, one with Color B on its left and the other with color green in front of it, then the red beedroid is dictated to move Above and change its color to O. By extension, the same rule applied if the view is rotated by π on the z-axis, but in that case, the destination would be Below.

In the same figure, Rule R 2 is a rule where a black node represent a part of the outer boundary of the 3D grid, that we call a wall in the remaining of the paper. In our algorithms, we often define similar rules that apply regardless of the presence of a wall in some part of the view. Thus, to avoid defining several time rules with very similar views, we propose a notation to represent several rules in just one picture. For example, Rule R 3 in Figure 1 has one node hatched with vertical lines, which means that the rule applies regardless of the presence of a wall located at this node. In practice, every rule that contains such vertical (resp. horizontal) hatched lines, represents a set of rules obtained by replacing each of those lines either by walls, or by empty nodes. For example, Rule R 3 in Figure 1 is a concise representation of Rules R 1 and R 2 .

Figure 2 shows an ambiguous rule. The beedroid has a symmetric view so that, depending on the transformation f chosen by the adversary, the beedroid executing this rule moves either above, or below. In the following, we represent in ambiguous rules all possible destinations that can be dictated by the adversary.

R1 R2 R3 G B R O G B R O G B R O Figure 1
Examples of rules. Colored letters inside nodes indicate the color of the beedroids occupying the nodes. The arrow indicates the destination and when a colored letter is given next to an arrow, this means that the rule dictates the beedroid to switch to that color.

R1 ρy,π(R1

) ρ z,π/2 • ρy,π(R1) B B R B R B B B R ⇒ B B R
Figure 2 An ambiguous rule. Since the destination depends on the choice of the adversary, we represent the rule abusively with multiple destinations, as illustrated on the right. Observe that if blue beedroids had different colors (as in Figure 1) the rule would not have been ambiguous. Indeed, having a common chirality allows the beedroid to determine a third direction, given two direction obtained from the view.

Impossibility Results

In this section, we establish that there is no algorithm solving the PFPP problem in 3D grids using two beedroids with visibility range one, whatever the finite number of available colors.

We first observe that in large enough grids, if beedroids travel a long distance without seeing a wall, then they execute a periodic sequence of movements. Indeed, in our settings, there are at most

B = |Cl| 2 = |Cl|(|Cl|+1)
2 different views without wall, and so at most B associated rules, where Cl is the set of available colors. Thus, if the two beedroids travel a distance at least B without seeing a wall, then they are executing a periodic sequence of movements. The definition of B, which depends on the algorithm, will be used throughout this section.

The above observation is important to prove our impossibility results. Actually, the outline of our proof is similar to the 2D case for luminous non-chiral robots studied in [START_REF] Rauch | Optimal exclusive perpetual grid exploration by luminous myopic robots without common chirality[END_REF]. However, the C V I T 2 0 1 6 existence of an axis of symmetry is replaced here by an axis of rotational symmetry. Indeed, robots in a 2D grid that do not agree on a common chirality cannot distinguish between two destinations that are symmetric with respect to an axis of symmetry. Similarly, two beedroids that do not agree on a common coordinate system, but agree on a common chirality, cannot distinguish between four destinations that are symmetric with respect to a rotational symmetry. Nevertheless, the proof of the main argument, given in Lemma 1 of [START_REF] Rauch | Optimal exclusive perpetual grid exploration by luminous myopic robots without common chirality[END_REF], cannot be adapted directly since it is more complex than in the 2D case.

The overview of the proof is as follows. We proceed by contradiction assuming that an algorithm solving the PFPP in 3D grids exists. Then, we show that once beedroids move far away from the walls, their possible movements are restricted. In more details, they can only move straight, otherwise they may not explore the whole grid. Next, we show that, once the exploration has reached specific places, the beedroids must always stay close to at least one wall (Lemma 1), leading to the final contradiction (Theorem 2). Due to the lack of space, several technical lemmas and proofs have been moved in Appendix A.

The lemma below is the cornerstone of our impossibility result. It states that there are configurations from which the two beedroids can remain forever at bounded distance from walls. To see this, we need to define a few concepts beforehand. We say that a beedroid is 2-close if it is at distance at most 2B from at least two walls. We say that beedroids are in a T -configuration if there is a line L of the 3D grid such that L contains the two beedroids and one of them is adjacent to a wall that is orthogonal to L.

▶ Lemma 1. Let A be an algorithm solving the PFPP in 3D grids using two beedroids under visibility range one. Assume some execution E reaches at a given time t (i) a configuration where a beedroid is 2-close or (ii) a T -configuration. Let C be the configuration of E at time t. Then, there exists an execution E ′ and a time t ′ > t such that C is reached in E ′ at time t, at time t ′ in E ′ , a beedroid is 2-close or the system is in a T -configuration, and between time t and t ′ in E ′ , the beedroids remain at distance at most 4B from a wall.

Sketch of proof.

The following sketch is illustrated with Figures 3 and4. Consider first the case where a beedroid is 2-close i.e., at distance at most 2B from two walls W 1 and W 2 . Due to the visibility range, the other beedroid must be located at a neighboring node. Then, we can show that to explore the whole 3D grid, the two beedroids must eventually be not 2-close. Now to become not 2-close, they have to move away from one wall, say W 1 . Consider the first time they become not 2-close. We can show that they are in a line parallel to another wall say W 2 and at distance at most 2B from that wall; see the solid line in Figure 3. Assume that both beedroids do not see W 2 when they becomes not 2-close. In this case, they see no wall at all (otherwise they are still 2-close). Two situations can happen. Either the beedroids move in a straight line for a distance B (Case (a)), or they eventually move away from the line (Case (b)).

In Case (a), they move in a straight line and, after B rounds without seeing any wall, they perform a periodic sequence of movements. So, they continue to move straight until reaching the wall opposite to W 1 . Consequently, one of then eventually becomes 2-close again while the two beedroids were constantly at distance at most 2B from W 2 , and the lemma holds.

In Case (b), at least one of them move away from the line by performing an ambiguous move before B + 1 rounds elapse. We can show that in this case the adversary can enforce them to reach a line L orthogonal to W 2 . We consider the square cuboid for which (1) one face is at distance 1 from W 2 , (2) the opposite one is at distance 2B from W 2 , (3) the closest face parallel to W 1 is at distance 2B from W 1 , and (4) L is an axis of rotational symmetry; see Figure 4. We can then show that there is an execution where the beedroids leave the square cuboid either from R rectangle 1 or from R triangle 1 . In the former case, a beedroid becomes 2-close again while the two beedroids remain at distance at most 2B from a wall, and the lemma holds. In the latter case, the beedroids traveled B rounds without seeing a wall. As a consequence, they perform a periodic sequence of movements in a straight line, parallel to W 1 , until reaching the wall opposite to W 2 while remaining at distance less than 3B from W 1 , and reach a T-configuration. So, the lemma also holds in this case.

The case where the beedroids see W 2 when they become not 2-close is treated similarly but requires to increase the distance from W 1 by B in Case (b). Finally, if we start from a T-configuration, again the proof is similar.

◀ A B b 1 b 2 W 1 W 2 (1) (2)
Figure 3 Position of the beedroids when they become not 2-close. Using the previous lemma, we can now conclude.

b 1 b 2 L R rectangle 1 R triangle 1 W 1 W 2
▶ Theorem 2. The PFPP is not solvable using two beedroids under visibility range 1 and any finite number of colors.

Proof. Assume that algorithm A solves the problem. Consider a grid of size 10B × 10B. Since the beedroids explore the entire grid, there exists a round where a beedroid is 2-close. By applying Lemma 1 repeatedly, we can construct an execution from there where beedroids forever remain at distance at most 4B from a wall, so that nodes at distance more than 4B from all the walls are not visited anymore, a contradiction. ◀ 4 Visibility range one: Vone 3 5

In this section, we address the PFPP using beedroids under visibility range one. We present an algorithm, denoted by Vone 3 5 , that solves PFPP using three beedroids endowed with five colors. By Theorem 2, under visibility range one, Vone 3 5 is optimal with respect to the number of beedroids. We encourage the reader to follow the overview of Vone 3 5 while looking at the animations available online [3], published as an additional material. The 3D grid can be seen as a building with several floors. The overall idea of the proposed algorithm is to make the beedroids explore the 3D grid floor by floor, as illustrated in Figure 6. While on a given floor, two beedroids will be in charge of exploring the floor line by line while the third one will be used as a landmark to keep track of the exploring direction: it will either designate the next line or the next floor to explore. Thus, the algorithm defines three main roles for the beedroids using colors: Leader (L), Follower (F) and Landmark. We use three different landmarks A, B, and C to distinguish different situations. Notice that a beedroid can change its role several times during the execution. Initially, beedroids respectively have colors C, C, and A, as shown in Figure 5. They are aligned and one beedroid with color C should be adjacent to the two others. This pattern can be arbitrary placed on the 3D grid. In that sense, the set of all possible initial configurations is locally-defined [6].

Starting from any such locally-defined initial configuration, beedroids first move towards a wall. If they are aligned along an edge of the 3D grid, they do so while keeping their respective color. Otherwise, they first switch to the color sequence A, L, F. Once a wall is reached, beedroids coordinate together to reach a particular kind of configurations, denoted by C p in the following, which will correspond to the effective start of the exploration. In other word, the initial prefix leading to a configuration C p occurs only once. Then, the system periodically goes through Configurations C p and all nodes are visited between two occurrences of them in the execution.

A configuration is of type C p if the beedroids are located on two adjacent lines ℓ i and ℓ i+1 of the 3D grid such that ℓ i hosts two adjacent beedroids colored F and L respectively at distance 2 and 3 from the same wall L; and and ℓ i+1 hosts a single beedroid with color A and adjacent to L. The rules to reach a configuration C p from a locally-defined initial configuration are given in Figure 8. As explained before, from configuration C p , the beedroids will perform a periodic exploring journey around the 3D grid visiting all its nodes floor by floor. As each floor of the 3D grid is a finite 2D grid, the strategy used to explore a given floor is similar to the one of [START_REF] Rauch | Optimal exclusive perpetual grid exploration by luminous myopic robots without common chirality[END_REF] i.e., two beedroids move and explore a given line while the third beedroid remains idle next to a wall to indicate the next line to explore. More precisely, let ℓ i be the current line of the floor f i being explored. The C V I T 2 0 1 6

23:10

Beedroids: How Luminous Autonomous Swarms of UAVs can save the World? leader moves away from the follower and the follower just follows the leader using the rules given in Figure 9. At the beginning, both the leader and the follower move away from the landmark which has color A, and move along the nodes of ℓ i until reaching a wall. When the leader sees the wall, it does not see the landmark (since the landmark was left on the opposite wall), then the leader and the follower exchange their respective roles and move back along the same line ℓ i . This role exchange is done in two rounds: first, the leader moves to one of its adjacent nodes changing its color to A to notify the follower that they have to change their role. As the follower does not sense the wall yet, it continues to follow the leader and hence it becomes neighbor to a wall. Next, by observing a beedroid with color A, the follower moves back to its previous position and changes its color to the leader's one L, while the ex-leader, the beedroid with color A, starts following the new leader and updates its color to become a follower. This is done by executing the rules of Figure 10. As the beedroids have switched their roles, they proceed again at the exploration of ℓ i but this time, in the reverse direction. When the leader reaches the opposite wall, it sees this time the landmark and hence knows that the current line ℓ i has been fully explored. Let ℓ i+1 be the line that hosts the landmark. Line ℓ i+1 is the next line to be explored. For this purpose, both the leader and the follower need to move to line ℓ i+1 while the landmark moves to another line ℓ i+2 , the line to visit after ℓ i+1 . This line switch is done in three rounds by executing the rules of Figure 11. Figure 12 illustrates the sequence of configurations reached during this latter process. The leader and the follower then simply proceed at the exploration of line ℓ i+1 in the same manner as line ℓ i .

(L1) L A F (L2) L A B (L3) F L B (L4) F B A (L5) F L B (L6) B F L (L7) L B F (L8)
In the case where ℓ i+1 is the last line to be explored on f i , the landmark moves to the next floor f i+1 to be explored when the leader moves to ℓ i+1 . Note that f i+1 is determined thanks to chirality. Indeed, as the landmark is at a corner and sense the leader at one side, it can identify the upper floor from the lower floor. Both the leader and the follower then proceed in the same manner as previously. That is, they explore the nodes of ℓ i+1 , exchange their roles and then move back on ℓ i+1 until they reach the wall again. When the leader and the follower reach the wall after exploring ℓ i+1 , they also move to Floor f i+1 indicated by the landmark. This is done by executing the rules of Figure 7. The beedroids will repeat the same process to explore Floor f i+1 . Note that in order to keep the same exploring direction, the landmark moves to the line such that the leader remains on the same side. This direction is again chosen using the chirality (recall that the beedroid is at the corner and senses a beedroid at Floor f i ). Figure 13 shows the sequence of configurations of this floor change. By doing so, the beedroids eventually explore each floor until they reach the last floor, called a roof in the sequel. This latter is explored similarly but the beedroids update their respective color differently when changing lines (this is done to ensure the beedroids remain on the roof without adding additional colors) using the rules shown in Figure 14. The beedroids then change the exploring direction to explore the 3D grid in the reverse direction. This is done by executing the rules of Figure 15. Figure 16 presents a sequence of configurations during the initiation of the exploring direction change and Figure 17 presents the sequence of configurations to terminate this process once the leader and the follower come back from exploring the last line of the roof. We have validated several base cases using our simulation tool [3]. Then, we have generalized the reasonning by induction to show that Vone 3 5 solves the PFPP. Due the lack of space the proofs leading to the theorem below are omitted but can be found in Appendix B.

▶ Theorem 3. Under visibility range one, Vone 3 5 solves the perpetual flower pollination problem with three beedroids endowed with five colors.

Visibility range two: Vtwo 1

In this section, we present an algorithm that uses five oblivious beedroids to solve the PFPP. The beedroids are oblivious in the sense that the lights of all the beedroids have the same color and cannot change, so they do not have any bit of persistant memory.

This algorithm works with a specific set of initial configurations that are not locally-defined. The initial configurations are those where the beedroids are close to a wall, like in the first configuration of Figure 18 but they must not be all adjacent to the same wall. Then, the principle is similar to Vone 5 3 i.e., beedroids explore the 3D grid floor by floor. Within a given floor, beedroids are able to fly in straight line when they form a ⊥ pattern, called moving group, composed of four beedroids. Initially, the moving group makes a U-turn while changing line (Figure 18). Then, they explore one line leaving a landmark beedroid adjacent to the wall. Upon reaching the opposite wall, they make a U-turn again and explore the same line again (Figure 19). When they meet the landmark again, beedroids are in the same configuration as initially, translated by one node.

Once they reach the corner, they move one floor above and explore this floor with the same pattern, rotated by π 2 (refer to Figure 20). Eventually, the beedroids finish exploring the roof and then switch the exploring direction to start exploring the floors of 3D grid in the reverse sense (refer to Figure 21). Due to space constraints, the set of rules can be found in the appendix. The animation is available online [4].

C V I T 2 0 1 6 R R R R R R R R R R R R R R R
Figure 18 In the initial configuration, beedroids should near a wall, as in the leftmost configuration. The beedroids then start a line change.

R R R R R R R R R R R R Figure 19 Sequence of configuration during a U-turn. R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R Bramas et al. 23:15 R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R Figure 21
Sequence of configurations when beedroids switch the exploring direction.

▶ Theorem 4. Under visibility range two, Vtwo 5 1 solves the perpetual flower pollination problem with five oblivious beedroids.

The proof of Theorem 4 is an induction similar to the one of Theorem 3 (actually it is even simpler due to the absence of any ambiguous rule).

C V I T 2 0 1 6 6 Related Work

The problem of perpetual flower pollination by a beedroid swarm is actually known in the literature as the perpetual exploration of a 3D grid by a swarm of luminous robots [START_REF] Peleg | Distributed coordination algorithms for mobile robot swarms: New directions and challenges[END_REF]. Exploration of discrete environment by a robot swarm has been widely studied. Various topologies have been already considered including lines [START_REF] Flocchini | How many oblivious robots can explore a line[END_REF], rings [1,8,11,[START_REF] Flocchini | Computing without communicating: Ring exploration by asynchronous oblivious robots[END_REF][START_REF] Ooshita | Ring exploration with myopic luminous robots[END_REF], trees [START_REF] Flocchini | Remembering without memory: Tree exploration by asynchronous oblivious robots[END_REF], torus [10], finite [2, 6, 9, 19], infinite 2D grids [5, 7], and even infinite n-dimensional grids [START_REF] Dobrev | Exploration of high-dimensional grids by finite automata[END_REF]. (In the infinite case, the exploration problem requires that each node is visited within finite time by at least one robot.) In the context of finite graphs, two main variants of the exploration problem have been studied: the terminating and perpetual exploration. The terminating exploration requires every possible location to be eventually visited by at least one robot, with the additional constraint that all robots stop moving after task completion. In contrast, the perpetual exploration requires each location to be visited infinitely often by all or a part of robots. Terminating exploration has been tackled in [8-11, 14-16], while [1, 2, 6, 19] deal with the perpetual exploration problem. Notice that Ooshita and Tixeuil consider the two variants of the problem in [START_REF] Ooshita | Ring exploration with myopic luminous robots[END_REF]. In contrast with the present paper, a large part of the literature is devoted to "non-myopic" robots, i.e., robots with an unbounded visibility range, meaning that the snapshot of each robot captures in the whole system configuration; see [1,2,9-11, [START_REF] Flocchini | Remembering without memory: Tree exploration by asynchronous oblivious robots[END_REF][START_REF] Flocchini | How many oblivious robots can explore a line[END_REF][START_REF] Flocchini | Computing without communicating: Ring exploration by asynchronous oblivious robots[END_REF]. In such a context, robots are always assumed to be anonymous and oblivious, i.e., they have no state and cannot remember the past. Furthermore, chirality has never been considered under such settings. Exploration algorithms satisfying exclusiveness are proposed in both finite [1, 2, 6, 19] and infinite graphs [5,7]. Assuming a common chirality is pretty usual in the 2D Euclidean plan; see e.g., [START_REF] Dieudonné | Leader election problem versus pattern formation problem[END_REF]. However, up to now only a few works dedicated to discrete environments, e.g., infinite [7] and finite [6] 2D grids, assume robots have a common chirality. Now, the common chirality has an impact on the number of robots necessary to solve exploration: for example, with visibility range one and three colors, two (resp. three) synchronous robots are necessary and sufficient to explore a finite 2D grid with (resp. without) the common chirality assumption [6,[START_REF] Rauch | Optimal exclusive perpetual grid exploration by luminous myopic robots without common chirality[END_REF]. To the best of our knowledge, perpetual exploration has been never addressed in finite 3D grids. However, the exploration of an infinite n-dimensional grid has been investigated in [START_REF] Dobrev | Exploration of high-dimensional grids by finite automata[END_REF]. In that paper, authors consider robots operating in two models: the semi-synchronous and synchronous ones. However, they do not impose the exclusivity at all since their robots can only sense the states of the robots located at the same node (in that sense, the visibility range is zero). Moreover, in contrast with our work, they assume all robots agree on a global compass, i.e., they all agree on the same directions North-South and East-West. They propose several solutions and bounds, in particular they show that, in the semi-synchronous model, four deterministic robots are necessary and sufficient to explore an infinite 3D grid.

Conclusion

We have studied how typically small swarms of chiral luminous beedroids can solve the perpetual flower pollination problem in 3D grids assuming the FSYNC model. Under the optimal visibility range one, we have shown that three beedroids are necessary and sufficient to solve the problem. For the sufficient part, we have proposed an algorithm that requires only five colors. Then, we have proposed another solution that is optimal in terms of colors: an algorithm working with five oblivious beedroids under visibility range two.

However, our industrial partners are still not fully satisfied by our proposal. Even if our solutions require a very few number of weak beedroids, they believe that we can still achieve some economies of scale. Like the character Peter Isherwell in the movie "Don't look up", they want to both save humanity and win money... So, we have to study whether we can reduce the number of colors used by the first algorithm. We should also study whether the number of beedroids and the visibility range of the second algorithm can be decreased. For this latter, we are pessimistic: we conjecture that the visibility range cannot be lowered to one in the oblivious case. Our idea is that skills necessary to solve the perpetual flower pollination problem in 3D grids with chiral oblivious beedroids are similar to those necessary to solve the 2D grid exploration problem with non-chiral oblivious beedroids. So, we expect that the impossibility proof given in [7] can be adapted to the context of chiral oblivious beedroids evolving in a 3D grid.

C V I T 2 0 1 6 A Omitted Proofs of Section 3

We first recall the overview of the proof. We proceed by contradiction assuming that an algorithm solving the PFPP in 3D grids exists. Then, we show that once beedroids move far away from the walls, their possible movements are restricted. In more details, they can only move straight (Lemma III), otherwise they may not explore the whole grid (Lemma IV). Next, we show that, once the exploration has reached specific places, beedroids must always stay close to at least one wall (Lemma 1), leading to the final contradiction (Theorem 2). The two first lemmas are technical results that are in particular used in the main lemma, Lemma 1. The first one states that to explore the 3D grid, beedroids should stay neighbors when they do not see any wall. The second one shows that if a beedroid b 1 is lost, at distance 2 from a wall, and at distance at least 4 from other walls, then the other beedroid b 2 should be adjacent to a wall; moreover b 1 should wait for b 2 which, in turn, should eventually leave the wall to meet b 1 .

▶ Lemma I. Let A be an algorithm solving the PFPP in 3D grids using two beedroids under visibility range one. In a 3D grid of size at least 4 × 4 × 4, no execution of A reaches a configuration where the two beedroids are lost.

Proof. Assume by the contradiction that an execution E of A contains a configuration C where the two beedroids are lost. In C, both beedroids, respectively denoted by b 1 and b 2 , see neither a wall nor a beedroid.

Assume that only one beedroid, say b 1 without the loss of generality, moves from C. The 6 possible destinations of b 1 look identical, so the adversary can choose any of them. Among those 6 destinations, at least 3 are at distance at least two from any wall, and among them at least one is at distance at least 2 from b 2 . So, there is a possible step from C that reaches a configuration where the two beedroids are still lost.

Assume that both beedroids moves from C. Again, for each beedroid, the 6 possible destinations look identical. Each beedroid r i has a set D i of at least three destinations that are at distance at least 2 from any wall. After choosing an arbitrary destination in d 1 ∈ D 1 for the first beedroid, there exists in D 2 , at least one destination d 2 that is also at distance at least 2 from d 1 (indeed, each pair of destination has only one common neighbor, and this common neighbor is distinct for each pair of destination). After their movement, the two beedroids are lost again.

In both cases, during the next step, the adversary can make any moving beedroid coming back to its position in C. So, there exists an execution where beedroids do not explore all nodes infinitely often, a contradiction. ◀ ▶ Lemma II. Let A be an algorithm solving the PFPP in 3D grids using two beedroids under visibility range one. Consider an execution E of A in a 3D grid of size at least 8 × 8 × 8. If E contains a configuration C where a beedroid b 1 is lost, at distance 2 from a wall, and at distance at least 4 from the other walls, then b 1 is idle, moreover the other beedroids b 2 is adjacent to a wall and is either idle or moves away from the wall during the next step. Proof of the claim: Assume by contradiction that b 2 is at distance at least 3 from b 1 in a configuration C 3 occurring at time t ′ in E ′ with t C ≤ t ′ < t m . We now show that there is a possible infinite suffix from C 3 where b 2 remains at distance at least 3 from b 1 . Actually, we can construct an execution where, after the prefix of E ′ leading to C 3 , every time b 2 is dictated to move from distance 3 to distance 2 from b 1 , then the adversary decides that b 2 moves at distance 4 from b 1 since the move of b 2 is ambiguous. Indeed, in C 3 , b 2 is at distance 3 from b 1 , which is lost. So, b 2 is adjacent to a wall otherwise we get a contradiction by Lemma I. In this case, b 2 is at distance at least 2 from any other wall since b 1 at distance 2 from the wall adjacent to b 2 and at distance at least 4 from the other walls. So, its view has an axis of rotational symmetry with respect to the line orthogonal to the wall. Hence, the adversary can rotate the local view of b 2 in such way that b 2 does not come closer to b 1 , but instead remains at distance at least 3 from it (n.b., b 1 may also move simultaneously). By repeating the same argument, we can create an infinite execution where b 2 remains at distance 3 from b 1 , so beedroids never meet, a contradiction. Claim 3: In C, b 2 is idle or moves away from the wall.

Proof of the claim: From Claim 2, we know that b 2 is at distance 2 from b 1 in C. Consequently, b 2 is at distance at least 2 from all the other walls. b 2 cannot move along its adjacent wall because its view has an axis of rotational symmetry and the adversary can decide that a destination at distance 3 from b 1 . In this case, if b 1 is idle, then the distance becomes 3. Otherwise, the adversary can also decide the destination of b 1 since it is lost so that the distance becomes 4. Hence, this contradicts Claim 2 in both cases. Thus, b 2 can either stay idle or move away from the wall, and cannot do anything else. Claim 4: In C, b 1 is idle.

Proof of the claim: If it is not, then, the adversary can decide that its destination is a node at distance 3 from b 2 (from Claim 2, we know that b 2 is at distance 2 from b 1 in C). If b 2 moves in the same step, then b 2 moves away from its adjacent wall, by Claim 3. By Claim 2, both beedroids are lost in the reached configuration, a contradiction to Lemma I. Otherwise, b 2 stays idle, and the distance between b 1 and b 2 becomes 3, contradicting Claim 2. The lemma directly follows from Claims 1,3, and 4. ◀ ▶ Lemma III. Let A be an algorithm solving the PFPP in 3D grids using two beedroids under visibility range one. If there exists an execution that reaches a configuration C where beedroids are at distance at least 2B from any wall and, from C, the beedroids perform a periodic sequence of movements without ambiguous rules, then there is a straight line of the 3D grid that contains the two beedroids while none of them sees a wall.

Proof. When a beedroid does not see any wall, a rule is unambiguous only if the beedroid sees the other one at distance one and the destination of the rule is on the axis passing through the other beedroid. Consequently, each beedroid can only stay idle, move away, or move towards the other beedroid. The formal proof is exactly the same as in [START_REF] Rauch | Optimal exclusive perpetual grid exploration by luminous myopic robots without common chirality[END_REF] (i.e., 2D grids without chirality).

◀ R 1 b 1 b 2 L Figure 22
If beedroids are on a line L, the adversary can decide from which side of the square cuboid the beedroids will exit. In particular, we can decide that the beedroids will exit toward R1, the blue area.

▶ Lemma IV. Let A be an algorithm solving the PFPP in 3D grids using two beedroids under visibility range one. There exists no execution that reaches a configuration C where beedroids are at distance at least 2B from any wall and, from C, the beedroids perform a periodic sequence of movements that includes an ambiguous rule.

Proof. Assume, by the contradiction, that there is an execution that reaches a configuration C where beedroids are at distance at least 2B from any wall and, from C, the beedroids perform a periodic sequence of movements which includes an ambiguous rule.

First, by definition, the ambiguous rule is executed during the B first steps from C, and when it is done, beedroids are still at least at distance B from any wall.

Assume that there is a configuration C reached during the B where the two beedroids are lost. Since beedroids are initially at distance 2B from any wall, the size of the 3D grid is at least 4 × 4 × 4 and we obtain a contradiction by Lemma I.

So, the two beedroids remains neighbors while they do not see any wall. Let b 1 be the beedroid executing the ambiguous rule and b 2 be the other one. The ambiguous rule executed by b 1 necessarily cause beedroids to either shift to a parallel line or make a turn. In the former case, both beedroids execute ambiguous rules, so the adversary can lost them instead of performing the shift, and we obtain a contradiction as previously. In the latter case, the adversary decides on which side the beedroids will turn among the at least four possibilities.

Hence, if the periodic sequence of movements contains an ambiguous move, the beedroids may make at least one turn per period and the adversary can make the beedroids remain in the same square grid of size B (the period of the sequence is at most B). While doing so, the beedroids do not see any wall, and do not explore the whole 3D grid, a contradiction. Again, the formal proof is similar to the proof in the 2D grid case without chirality [START_REF] Rauch | Optimal exclusive perpetual grid exploration by luminous myopic robots without common chirality[END_REF]. ◀

The next lemma states that if two beedroids are on the same line and inside an area that is rotationally symmetric, then they cannot break this symmetry without executing an ambiguous rule (due to the lack of agreement on the coordinate system). Hence, the adversary can decide on which side of the line the beedroids move. More formally, if beedroids move out of the area through a node u, then there exists an execution where the beedroids move out of the area through another node u ′ that is symmetric to u.

We need to define a few concepts beforehand; see Figure 22 configuration C where the two beedroids are located in some line of the 3D grid. We call blurred area of C any subset S of nodes such that the subgrid induced by S shapes a square cuboid for which L is an axis of rotational symmetry. A blurred area is non-trivial if it does not contain all nodes of the 3D grid. We denote by EH(S) the external hull of a blurred area S, i.e., the set of nodes in V \S at distance one from a node of S.

▶ Lemma V. Let A be an algorithm solving the PFPP in 3D grids using two beedroids under visibility range one. Assume an execution E reaching a configuration C where the two beedroids are on the same line L. Let S be a blurred area of C. Let R 1 ⊆ EH(S) such that the union of R 1 and its symmetrics w.r.t. the rotations around L is equal to EH(S). If S is non-trivial and L is also an axis of rotational symmetry of EH(S), then there exists an execution from C where a beedroid reaches EH(S) for the first time at a node u ∈ R 1 .

Proof. Once E has reached C, the beedroids have to explore the nodes outside S since S is nontrivial. So, in E, eventually a beedroid goes outside S for the first time from C by reaching a node u in EH(S), say at time t.

If u ∈ R 1 , we are done. Otherwise u ∈ EH(S) \ R 1 and, by assumption, there exists a node u ′ ∈ R 1 symmetric to u with respect to a rotation around L, i.e., u ′ = ϕ(u) where ϕ is a rotation around L. First, u ′ / ∈ L, because otherwise u = u ′ ∈ R 1 . So, to reach u, a beedroid has to move away from L at some round before t. Let t 0 be the first time, after configuration C, such that a beedroid, say r, moves away from L. In the configuration at time t 0 , C(t 0 ), the view of both beedroids have a rotational symmetric around axis L so that the rule executed by r is ambiguous. Consider now the execution E ′ similar to E, but where at time t 0 the adversary rotates the view of r by rotation ϕ, so that the beedroid r moves away from L on another side (and we do the same for the other beedroid if it moves away from L at time t 0 ). After that, we consider that the execution is similar to E but where everything is rotated by ϕ. Hence, at time t, a beedroid reaches the node u ′ and we are done. ◀

In particular, we can choose R 1 to be the union of one side and two triangles, as shown in Figure 22 (page 21), where R 1 and its symmetrics form the red external hull of the square cuboid. Remark that if the square cuboid leans against a wall (as illustrated in Figure 22 if the gray plan is a wall), then R 1 can consist only in one face and one triangle. By applying the lemma, we obtain that there is an execution where the beedroids escape from the blurred area either through a rectangular face or the top triangle.

▶ Lemma 1. Let A be an algorithm solving the PFPP in 3D grids using two beedroids under visibility range one. Assume some execution E reaches at a given time t (i) a configuration where a beedroid is 2-close or (ii) a T -configuration. Let C be the configuration of E at time t. Then, there exists an execution E ′ and a time t ′ > t such that C is reached in E ′ at time t, at time t ′ in E ′ , a beedroid is 2-close or the system is in a T -configuration, and between time t and t ′ in E ′ , the beedroids remain at distance at most 4B from a wall.

Proof. We consider a 3D grid whose size is more than 8B × 8B × 8B. The lemma otherwise trivially holds: by definition of A, a beedroid is infinitely often 2-close; moreover every beedroid is always at distance at most 4B from a wall in a 3D grid where at least one side is less or equal to 8B. Assume first that a beedroid is 2-close in a configuration C (the case where beedroids are in a T -configuration will be treated in the last paragraph of this proof). To explore the 3D grid, the two beedroids must sometimes be not 2-close. Indeed, if a beedroid remains 2-close forever, the other beedroid should in particular explore nodes at distance more than 2B + 2 from every wall. In this case, it would be lost and consequently, the adversary can make it alternating between two nodes forever, making the exploration fail. destinations each time D14 occurs in a prefix. The case of Rule U1 is less problematic. Indeed, U1 is executed only once per line during a floor exploration. Moreover, when U1 is executed by a beedroid, then, whatever be the destination, the beedroid goes back to its initial position rightafter by executing U4. Consequently, whatever be the destination chosen by the adversary, the reached configuration one round after U1 is the same. Hence, we just had to check four executions per initial configuration since the system is synchronous and so only influenced by the nondeterministic choice made by D14 during the default prefix. We ran those executions until reaching an already encountered configuration (actually C p ): at that time all nodes should have been visited.

We assume now that Vone 3 5 solves the PFPP problem in all 3D grids of size S x × S y × S z with 3 ≤ S x ≤ ℓ, 3 ≤ S y ≤ w, and 3 ≤ S z ≤ h for some values ℓ ≥ 5, w ≥ 5, and h ≥ 8.

From the previous discussion, the induction holds for the 3D grid of size (ℓ + 1) × w × h, ℓ × (w + 1) × h, and ℓ × w × (h + 1) since we can apply the induction on 3D grids of size ℓ × w × h and ℓ × w × (h -3). ◀ C V I T 2 0 1 6

Figure 4

 4 Figure 4 Position of the beedroids if they execute an ambiguous move after becoming not 2-close.

Figure 5

 5 Figure 5 Initial configuration of the beedroids Figure 6 Overview of the journey made by the exploring beedroids

Figure 7

 7 Figure 7 Moving to the next floor.

Figure 8 FFigure 9

 89 Figure 8Rules executed from a locally-defined configuration. Colored letters inside nodes indicate the color of the beedroids occupying the nodes. The arrow indicates the destination and when a colored letter is given next to an arrow, this means that the rule dictates the beedroid to switch to that color. Finally, self-loops indicate when a beedroid stays idle.

Figure 11 Figure 12

 1112 Figure 11 Moving to the next line.

Figure 13 Figure 14

 1314 Figure[START_REF] Dobrev | Exploration of high-dimensional grids by finite automata[END_REF] Sequence of configurations during a change of floor. The three first configurations replace the line change that cannot occur because the beedroid A is in a corner, then the moving group explore the last line of the floor. The three last configurations occurs when the moving group comes back.

Figure 15

 15 Figure 15 Switching exploring direction.

Figure 16

 16 Figure[START_REF] Flocchini | Computing without communicating: Ring exploration by asynchronous oblivious robots[END_REF] Sequence of configurations during the initiation of the exploring direction change.

Figure 17

 17 Figure[START_REF] Ooshita | Ring exploration with myopic luminous robots[END_REF] Sequence of configurations once the leader and follower come back to complete the exploring direction change.

Proof. First, b 2

 2 is not lost in C by Lemma I. So Claim 1: b 2 is adjacent to a wall in C. To complete the exploration, b 2 has to meet b 1 . Indeed, since b 1 is lost, whether or not b 1 is idle, the adversary can keep it at distance 2 from the same wall and at distance at least 4 from the other walls while it does not meet b 2 . In this situation, b 2 cannot move away from a wall without meeting b 1 , indeed otherwise the execution reaches a configuration where both beedroids are lost, which is C V I T 2 0 1 6 forbidden (by Lemma I). On the other hand, still in the aforementioned situation, if b 2 remains forever adjacent to a wall without meeting b 1 , then some nodes will be not visited anymore, a contradiction.Hence, b 2 eventually meets b 1 after C. Consider now any execution E ′ containing C where b 2 meets b 1 after C and where b 1 remains at distance 2 from the same wall and at distance at least 4 from the other walls until it meets b 2 (we have just seen that such execution exists). Let t C be the time at which C occurs in E ′ . Let t m be the first time b 1 and b 2 meet after C in E ′ . Claim 2: In E ′ , b 2 is at distance at most 2 from b 1 at every time t such that t C ≤ t < t m .

C

  for an illustration. Consider a Luminous Autonomous Swarms of UAVs can save the World?

1

  Lélia Blin, Alessia Milani, Maria Potop-Butucaru, and Sébastien Tixeuil. Exclusive perpetual ring exploration without chirality. In Nancy A. Lynch and Alexander A. Shvartsman, editors, Distributed Computing, 24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13-15, 2010. Proceedings, volume 6343 of Lecture Notes in Computer Science, pages 312-327, Boston, Massachusetts, USA, September 2010. Springer. 2 François Bonnet, Alessia Milani, Maria Potop-Butucaru, and Sébastien Tixeuil. Asynchronous exclusive perpetual grid exploration without sense of direction. In Antonio Fernández Anta, editor, Proceedings of International Conference on Principles of Distributed Systems (OPODIS 2011), number 7109 in Lecture Notes in Computer Science (LNCS), pages 251-265, Toulouse, France, December 2011. Springer Berlin / Heidelberg. URL: http://www.springerlink.com/content/9l3v424157681707/. 3 Quentin Bramas. Animation of the first algorithm, 2022. https://bramas.pages.unistra.fr/ Quentin Bramas, Stéphane Devismes, and Pascal Lafourcade. Optimal Exclusive Perpetual Grid Exploration by Luminous Myopic Opaque Robots with Common Chirality. In ICDCN'21: International Conference on Distributed Computing and Networking, Virtual Event, pages 76-85, Nara, Japan, 5-8 January 2021. ACM. 7 Quentin Bramas, Pascal Lafourcade, and Stéphane Devismes. Finding water on poleless using melomaniac myopic chameleon robots. In Martin Farach-Colton, Giuseppe Prencipe, and Ryuhei Uehara, editors, 10th International Conference on Fun with Algorithms, FUN 2021, May 30 to June 1, 2021, Favignana Island, Sicily, Italy, volume 157 of LIPIcs, pages 6:1-6:19. Schloss Dagstuhl -Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.FUN.2021.6. 8 Ajoy Kumar Datta, Anissa Lamani, Lawrence L. Larmore, and Franck Petit. Enabling ring exploration with myopic oblivious robots. In 2015 IEEE International Parallel and Distributed Processing Symposium Workshop, IPDPS 2015, pages 490-499, Hyderabad, India, May 25-29, 2015 2015. IEEE Computer Society. 9 Stéphane Devismes, Anissa Lamani, Franck Petit, Pascal Raymond, and Sébastien Tixeuil. Terminating exploration of A grid by an optimal number of asynchronous oblivious robots. Comput. J., 64(1):132-154, 2021. doi:10.1093/comjnl/bxz166. 10 Stéphane Devismes, Anissa Lamani, Franck Petit, and Sébastien Tixeuil. Optimal torus exploration by oblivious robots. Computing, 101(9):1241-1264, 2019. 11 Stéphane Devismes, Franck Petit, and Sébastien Tixeuil. Optimal probabilistic ring exploration by semi-synchronous oblivious robots. Theoretical Computer Science (TCS), 498:10-27, 2013.

	4 Quentin Bramas.	Animation of the second algorithm, 2022.	https://
	bramas.pages.unistra.fr/robot-grid-exploration-simulator/?/
	robot-grid-exploration-simulator/algo/finite-grid/chirality/range-2/
	algo-5-robots-oblivious.web-algo.
	5 Quentin Bramas, Stéphane Devismes, and Pascal Lafourcade. Infinite grid exploration by disoriented
	robots. In Chryssis Georgiou and Rupak Majumdar, editors, Networked Systems -8th International
	Conference, NETYS 2020, Marrakech, Morocco, June 3-5, 2020, Proceedings, volume 12129 of Lecture
	Notes in Computer Science, pages 129-145. Springer, 2020. URL: https://doi.org/10.1007/
	978-3-030-67087-0_9.
	6

robot-grid-exploration-simulator/?/robot-grid-exploration-simulator/ algo/finite-grid/chirality/range-1/3-robots-5-colors.web-algo.

https://biosphere2.org

Those choices have been motivated by the fact that values 3 and 4 are very specific since in those cases, 1 or 2 beedroids are necessarily adjacent to a wall initially.

Funding

This study was partially supported by the French ANR project ESTATE (ANR-16 CE25-0009-03).

1 https://www.un.org/en/observances/bee-day 2 https://www.iucn.org/ 3 https://cdn.buglife.org.uk/2019/08/CM-EofE-bee-report-2019-Headlines-FINAL-CJ. pdf 4 https://www.greenpeace.

Consider now an execution E ′ such that, whenever a beedroid executes an ambiguous moves that could make it not 2-close, then the adversary chooses a destination that is 2-close. This is possible because, in case of an ambiguous move, the adversary can chose among at least 4 destinations and if one destination would make the beedroid not 2-close, then the opposite destination (with respect to the beedroid's position) would keep it 2-close (because when a beedroids makes a move, only the distance to one wall increases).

In E ′ , let t 0 > t be the first time when no beedroid is 2-close. By assumption, at least one beedroid that is 2-close at time t 0 -1, say b 2 , makes an unambiguous move. To make this unambiguous move, b 2 necessarily moves toward the other one, b 1 that is not 2-close. So, at time t 0 -1, only b 2 is 2-close, i.e., at distance at most 2B from two walls W 1 and W 2 . Without loss of generality, at time t 0 , b 2 is at distance 2B + 1 from wall W 1 and at distance at most 2B from W 2 (b 2 is at distance more than 2B from other walls).

Since at time t 0 -1, b 2 is moving towards b 1 , then, at time t 0 -1, the two beedroids are on a line parallel to the wall W 2 . Assume first that beedroids are not adjacent to W 2 . Two cases can occur (both cases are represented in Figure 3) (page 7). Case (1): They remain on the same line parallel to W 2 , moving away from W 1 , until a beedroid is at distance 3B + 1 from W 1 . If they do so, since they traveled a distance B since t 0 -1, they are executing a periodic sequence of movements, hence, they continue to move on the same line until reaching the wall opposite to W 1 (Lemmas III and IV), in a T -configuration, while remaining at distance at most 2B from W 2 , and the lemma holds in this case. Case (2): Before being at distance 3B + 1 from W 1 , one or two beedroids move away from the line they were traveling through. These moves are necessarily ambiguous. If two beedroids moves away simultaneously, we get a contradiction because the adversary can choose the destination so that the two beedroids become lost (Lemma I). So, only one beedroid, say b 1 , moves away from the line. Again, since beedroids cannot become lost (Lemma I) and the destination of b 1 is chosen by the adversary, we can consider the case where the two beedroids end up, at time t 1 ≥ t 0 , in a line L orthogonal to W 2 . Consider now the case where the beedroids are adjacent to W 2 at time t 0 -1 when moving away from W 1 . Similar things occur. Case (a): They perform a periodic movement while remaining adjacent to W 2 and travel along the wall (but not necessarily in straight line) until reaching another wall (so they become 2-close), and the lemma holds in this case; Case (b): a beedroid moves away from W 2 and forms with the other beedroid a line L orthogonal to W 2 before being at distance 3B + 1 from W 1 ; or Case (c): both beedroids move away from W 2 (simultaneously or one after the other, as a lost beedroid must wait the other beedroid, by Lemma II) and they end up in a line L parallel to W 2 . In this case, since they traveled at most B from t 0 , they can travel again at most B before either performing a periodic movement (Case (1)) while staying at distance 2 from W 2 , and the lemma holds in this case. Otherwise, they make an ambiguous move to end up in a line L orthogonal to W 2 (Case (2)). In this latter case, the beedroids end up at distance at most 4B from W 1 . So, the only cases that remains to consider are those where the beedroids are in a line L orthogonal to W 2 at distance at most 4B from W 1 .

Consider the set of nodes

where R rectangle 1 is a rectangle of nodes at distance 2B from the wall W 1 and R triangle 1 a triangle of nodes at distance 2B from W 2 and at most 4B from W 1 , such that the union of R 1 and its image by the three rotations around L form the external hull of a square cuboid for which (1) one face is at distance 1 from W 2 and (2) L is axis C V I T 2 0 1 6

23:24

Beedroids: How Luminous Autonomous Swarms of UAVs can save the World? of rotational symmetry; see Figure 4 for an illustration (page 7). Using Lemma V, there exists an execution such that a beedroid reaches R 1 .

If a beedroid reaches R rectangle 1 , then a beedroid becomes 2-close and the lemma is proven. If a beedroid reaches R triangle 1 , then the beedroids have traveled a distance at least B without seeing a wall, hence are executing a periodic sequence of movements. The sequence cannot contain an ambiguous rule (using Lemma IV) because the beedroids are at distance at least 2B from any wall, so they are moving in a straight line (by Lemma III), and they end up in the wall opposite to W 2 and reach a T -configuration, while remaining at distance at most 4B from W 1 . Now we consider that the beedroids are in a T -configuration in configuration C. Then, they are on a line L orthogonal to a wall, say W 2 . Using a similar argument, we know that either the beedroids become 2-close, or move in a straight line to the opposite wall until they reach a T -configuration. ◀ B Correctness of Algorithm Vone 3 5 ▶ Theorem 3. Under visibility range one, Vone 3 5 solves the perpetual flower pollination problem with three beedroids endowed with five colors.

Proof. We consider 3D grids of size S x × S y × S z where S x ≥ 3, S y ≥ 3, S z ≥ 3 since Vone 3 5 uses three beedroids. In the following, we will respectively refer to S x as the length, S y as the width, and S z as the height of the 3D grid.

As a preliminary remark, we can observe that Vone 3 5 proceeds by phases. First, a default prefix where beedroids move toward a wall and then self-organize together to reach a configuration C p corresponding to the effective start of the exploration. Then, the system periodically goes through Configurations C p and all nodes should be visited at least once between two occurrences of C p in the execution. Between two occurences of C p , a finite exploration is split as follows. Nodes are visited floor by floor until reaching the roof, i.e., the S th z floor. After the visit of the roof, the exploration direction changes (from bottom-up to top-down or the reverse), and so on.

We have defined the rules in such a way that the processing of each phase is independent from the size of the grid (for example, colors are not used to compute any distance). In particular, the default prefix widely depends on the initial positions of beedroids. The grid size only impacts the duration of this prefix, precisely the time necessary to reach a wall.

The exploration of each floor is made line by line. The number of lines per floor as well as the length of lines do not impact the way lines are explored except from increasing the exploration time.

Concerning now the number of floors. The exploration of two consecutive non-roof floors is analogous up to a π 2 rotation. Hence, the exploration of the i th and j th floor is analogous provided that none of them is the roof and i mod 4 = j mod 4 (every 4 rotations of π 2 , we retrieve an analogous situation). Similarly, the exploration of the roof is similar for any two 3D grids with the same length, same width and whose respective heights i and j satisfy i mod 4 = j mod 4.

Hence, we proceed by induction on S x × S y × S z . We have validated several base cases, including heights h such that h mod 4 = x, for each value x ∈ {0, 1, 2, 3}. Precisely, we have checked that Vone 3 5 solves the PFPP on every 3D grid of size S x × S y × S z with S x ∈ {3, 4, 5}, S y ∈ {3, 4, 5}, and S z ∈ {3, 4, 5, 6, 7, 8}. 6 Such a checking is easy since, from a given initial configuration, we only need to check up to four executions. Actually, two rules of Vone 3 5 are ambiguous: D14 and U1. D14 is executed at most once during a default prefix and four destinations are possible. Hence, we add to check the four possible C Algorithm Vtwo 5 1 Here are the set of rules.

Bramas et al.

23:27

Bramas et al.

23:29


Florian Fontan

Pascal Lafourcade

Luc Libralesso

Benjamin Momège

Local search with weighting schemes for the CG:SHOP 2022 competition

Keywords: 2012 ACM Subject Classification Theory of computation → Computational geometry Keywords and phrases heuristics, vertex coloring, digital geometry Digital Object Identifier 10.4230/LIPIcs.SoCG.2022.XX Category CG Challenge

This paper describes the heuristics used by the LASAOFOOFUBESTINNRRALLDECA 1 team for the CG:SHOP 2022 challenge. We introduce a new greedy algorithm that exploits information about the challenge instances, and hybridize two classical local-search schemes with weighting schemes. We found 211/225 best-known solutions. Hence, with the algorithms presented in this article, our team was able to reach the 3rd place of the challenge, among 40 participating teams.

Introduction

The Fourth Geometric Optimization Challenge proposed in SoCG 2022 is about finding Minimum Plane Partitions. Given a geometric graph with vertices represented by points in the plane, and edges by straight-line connections between vertices, we aim to partition edges into as few subsets of disjoint lines, and to minimize the partition size.

Solving an instance of this challenge is equivalent to solving an instance of the classical vertex coloring problem (VCP). Indeed, we can define a graph G ′ = (V ′ , E ′ ) where V ′ is the set of lines, and there is an edge in E ′ between two intersecting lines. Finding a valid vertex coloring of G ′ with k colors is equivalent to finding a coloring of the original problem with k colors. We refer the reader to the competition survey for more details about the vertex coloring problem transformation [START_REF] Sándor | Minimum partition into plane subgraphs: The CG: SHOP Challenge 2022[END_REF], and to the other participants articles [START_REF] Crombez | Shadoks approach to minimum partition into plane subgraphs[END_REF][START_REF] Spalding-Jamieson | Conflict-based local search for minimum partition into plane subgraphs[END_REF][START_REF] Schidler | SAT-based local search for plane subgraph partitions[END_REF].

In our approach for the SoCG challenge, we made the choice to focus only on solving the equivalent vertex coloring problem instances instead of directly solving the competition

XX:2

Local search with weighting schemes for the CG:SHOP 2022 competition instances. We show that "classical" graph coloring algorithms are competitive, even with ad-hoc approaches for the SoCG challenge.

We combined some classical algorithms found in the vertex coloring literature (two localsearch neighborhoods presented below) with a dynamic weighting scheme present in many methods for solving other graphs problems (and closely related to the conflict optimizer used in the previous CG:SHOP competition [START_REF] Crombez | Shadoks Approach to Low-Makespan Coordinated Motion Planning[END_REF]). Furthermore, we show that this new algorithm is simple to implement, yet efficient as it enabled us to reach the 3rd place in the CG:SHOP 2022 competition.

The main idea of our approach is to optimize some solutions with some local search algorithms. We use two techniques to find some solutions: a segment orientation greedy ad-hoc algorithm, and DSATUR, one of the most common greedy algorithms in the vertex coloring literature. Then, using these initial solutions, we apply two optimization techniques: a conflict minimization approach with a weighting scheme: Conflict Weighting Local Search (CWLS), a partial coloring approach with a weighting scheme: Partial Weighting Local Search (PWLS).

In Section 2, we present some mainstream algorithmic components to solve the vertex coloring problem. Section 3 present the greedy algorithms we implemented (namely the saturation degree and orientation-based greedy algorithms). Sections 4 and 5 present the localsearch and weighting schemes we used for the competition (namely the conflict minimization, and vertices non-colored minimization). Finally, we compare our approaches in Section 6.

Related work

Multiple resolution methods were developed these last 40 years:

A first category consists of greedy algorithms. These algorithms are used to find good quality initial solutions in a short amount of time. We present two of most considered greedy approaches in Section 3.

A second category of algorithms consists of exact methods using branch-and-bound algorithms. These algorithms are complete search methods, thus are able to find an optimal solution and prove that they are indeed optimal. Such methods extend the DSATUR heuristic by allowing it to backtrack [START_REF] San | A new dsatur-based algorithm for exact vertex coloring[END_REF][START_REF] Furini | An improved dsatur-based branchand-bound algorithm for the vertex coloring problem[END_REF]. Another category of exact methods (branchand-cut-and-price) decompose the vertex coloring problem into an iterative resolution of two sub-problems [START_REF] Mehrotra | A column generation approach for graph coloring[END_REF][START_REF] Gualandi | Exact solution of graph coloring problems via constraint programming and column generation[END_REF][START_REF] Furini | Exact weighted vertex coloring via branch-and-price[END_REF]. The higher level that maintains a set of valid colors (defined by an independent set). It aims to cover all the vertices with a minimum-size set of colors, thus solving a set-covering problem (often described as the "master problem"). A lower level (solving a sub-problem) aiming to find a new valid coloring that would be promising, thus solving a maximum weight independent set problem (often described as the "pricing problem"). Such methods are usually able to find the optimal coloring for graphs with a few hundred vertices. However, the CG:SHOP 2022 competition instances involve at least a few thousands vertices, thus they appear to be not suited for this competition.

Finally, a third category of algorithms consists of local search algorithms. These methods start by an initial solution (often found by some greedy algorithm), remove some color, thus making the solution infeasible but with fewer colors, then apply some perturbations, aiming to make it feasible again. We present this approach in more details in Sections 4 and 5. Finding Initial Solutions Applying some local search scheme requires some initial solutions. We present in this section two greedy algorithms that enable us to find promising initial solutions quickly.

We use two approaches to find initial solutions. The best one is used for our other algorithms.

1. DSATUR. DSATUR is one of the most common greedy algorithms in the vertex coloring literature. It was introduced in 1979 [START_REF] Brélaz | New methods to color the vertices of a graph[END_REF]. It selects the vertex that has the most colors in its neighborhood, and assigns it to the first non-conflicting color until no vertex is left uncolored. Ties are broken by selecting the vertex with maximum degree. This algorithm does not take into account the specificities of the CG:SHOP 2022 competition. 2. Segment Oriented Greedy. We introduce a greedy algorithm that exploits the segment orientations. This algorithm is inspired from the Recursive Largest First algorithm, introduced in 1979 [START_REF] Thomson | A graph coloring algorithm for large scheduling problems[END_REF]. Recursive Largest first colors the graph one color at a time. The algorithm searches for an independent set of maximum size, assigns these vertices the same color, removes the newly colored vertices, and repeats until all vertices are assigned a color. The algorithm we propose (Segment Oriented Greedy) takes advantage of the fact that most of the challenge instances consist of long segments. Thus, if segments are almost parallel, it is likely that they do not intersect (thus forming an independent set). This greedy algorithm first sorts the segments by orientation, ranging fromπ 2 to π 2 . For each segment in this order, we try to color it using the first available color. If we fail, we introduce a new color. This algorithm is efficient, produces interesting initial solutions and takes into account the specificities of the competition.

Conflict Weighting Local Search (CWLS)

One classical approach for the vertex coloring involves allowing solutions with conflicting vertices (two adjacent vertices with the same color). It was introduced in 1987 [START_REF] Hertz | Using tabu search techniques for graph coloring[END_REF] and called TABUCOL (more details in Section 4). It starts with an initial solution, removes a color (usually the one with the least number of vertices), and assigns uncolored vertices with a new color among the remaining ones. This is likely to lead to some conflicts (i.e. two adjacent vertices sharing a same color). The local search scheme selects a conflicting vertex, and tries to swap its color, choosing the new coloring that minimizes the number of conflicts. If it reaches a state with no conflict, we obtain a new best-known solution. The process is repeated until the stopping criterion is met. Originally, TABUCOL also contains some tabu mechanism to avoid cycling through some states. In this article, we refer to this local-search neighborhood as conflict-minimization. TABUCOL and its conflict-minimization neighborhood, obtained at the time excellent performance. It was later embedded in a large variety of algorithms, including many state-of-the-art algorithms (to the best of our knowledge). For instance MACOL [START_REF] Lü | A memetic algorithm for graph coloring[END_REF] that uses TABUCOL as a mutation operator, and the GPX crossover to combine solutions. Learning scheme: While the original TABUCOL algorithm includes this "tabu-list" mechanism to avoid cycling, it is not always sufficient, and requires some hyperparameter tuning in order to obtain a good performance on a large variety of instances. To overcome this issue, we developed a weighting scheme inspired from recent work in graph problems (namely Row Weighting Local Search for the set covering problem [START_REF] Gao | An efficient local search heuristic with row weighting for the unicost set covering problem[END_REF]). The idea is to penalize each conflict the algorithm introduces, so frequently occurring conflicts have a larger penalty, thus less likely to be selected in the future. This allows the algorithm to naturally diversify

S o C G 2 0 2 2

XX:4

Local search with weighting schemes for the CG:SHOP 2022 competition the solutions it obtains. Similarly to the Row Weighting Local Search algorithm, we use a simple weighting scheme that initializes all the weights to 1 (thus one weight per edge). Each time a conflict is introduced, its weight is increased by 1. The algorithm minimizes the total weight instead of the total number of conflicts.

Partial Weighting Local Search (PWLS)

Another local search algorithm solving the vertex coloring problem was introduced in 2008 (PARTIALCOL). This algorithm proposes a new local search scheme that allows partial coloring (thus allowing uncolored vertices). The goal is to minimize the number of uncolored vertices. Similarly to TABUCOL, PARTIALCOL starts with an initial solution, removes one color (unassigning its vertices), and performs local search iterations until no vertex is left uncolored. When coloring a vertex, the adjacent conflicting vertices are uncolored. Then, the algorithm repeats the process until all vertices are colored, or the stopping criterion is met.

Learning scheme: We also introduce some weighting scheme for the PARTIALCOL local-search neighborhood. We assign a weight for each vertex, and the objective of the local search is to minimize the total weight of uncolored vertices. Each time a vertex becomes colored, its weight is increased by 1.

Results and Conclusions

All algorithms were executed on an Intel(R) Xeon(R) CPU E5-2687W v4 @ 3.00 GHz CPU, with 30 MB cache, and 768 GB RAM for 24 hours for each instance. To speed up the experiments, we ran 24 parallel runs on our machine. All algorithms have been implemented in the rust programming language and are publically available on a GitHub repository 2 . In order to compare the efficiency of our algorithms, we use the ARPD (Average Relative Percentage Deviation) as a comparison metric, which is defined as follows:

ARP D Ia = i∈I M ai -M * i M * i .
100

|I|
where I is a set of instances with similar characteristics (in the same instance class), M ai corresponds to the objective obtained by algorithm a on instance i. And M * i the reference solution objective for the instance i. The reference value is the best solution found by our team during the competition. The ARPD describes the performance of a given algorithm on a given instance class. This aggregation allows us to observe the overall behavior of some algorithm on some instance class. An ARPD close to 0 indicates that the algorithm is close to the best solutions we found during the competition (thus, the lower, the better).

Table 1 compares all the algorithms we implemented on each class of instances. Greedy algorithms report large ARPDs, thus being far from the best-known solutions. The orientation greedy generally outperforms the DSATUR algorithm as it handles instances with long segments, where the orientation is a good conflict predictor (thus all instances but the VISP-like). DSATUR outperforms the orientation greedy on the visp-like instances (where the segment localization is more important than the orientation). Local search weighting schemes allow getting closer to the best-known solutions. It is interesting to note that CWLS and PWLS are complementary, as CWLS seems to be more efficient than PWLS on RVISP/VISP classes of instances, and PWLS being more efficient on the others. Both local search methods are able to reach almost optimal solutions (less than 2% deviation to the best-known solution in average).

Figure 1 compares the solution quality over time of CWLS and PWLS on the SQRP and VISP instances. Both algorithms seem to be complementary depending on the instance class.

From this competition, we study that adding a weighting scheme significantly improves the algorithm performance, making the algorithm more robust. This weighting allows a simple adaptive diversification mechanism. We studied two local-search neighborhoods (conflictminimization and partial-coloring-minimization). For both of them, we presented some weighting scheme: Conflict Weighting Local Search (CWLS), and Partial Weighting Local Search (PWLS). CWLS and PWLS are both performant, and complementary depending on the instance class.

In the future, we plan to study the integration of such weighting schemes within memetic algorithms. Indeed, memetic algorithms are known to obtain excellent performance on classical vertex coloring instances.

Figure 1

 1 Figure 1 Comparison of the performance of CWLS and PWLS over time.

Table 1

 1 Average Relative Percentage Deviation comparison for all instance classes over 24h runs. Bold values indicate the algorithm that is statistically significantly better than the other one using a Wilcoxon signed-rank test with α = 0.05.

	Instance class CWLS PWLS DSATUR orientation greedy
	reecn	1.04	0.0	24.31	16.41
	rsqrp	0.51	0.11	24.03	5.89
	rsqrpecn	0.0	0.0	24.86	18.08
	rvisp	0.06	0.99	25.06	26.94
	rvispecn	0.0	0.14	30.9	49.93
	sqrp	1.06	0.0	31.22	4.9
	sqrpecn	0.88	0.03	22.74	14.11
	visp	0.19	1.77	29.23	27.6
	vispecn	0.49	0.08	34.75	54.66

https://github.com/librallu/dogs-color

Funding Pascal Lafourcade: This work is supported by the French ANR PRC grant MobiS5 (ANR-18-CE39-0019), DECRYPT (ANR-18-CE39-0007), and SEVERITAS (ANR-20-CE39-0005). the competition, we could not find some team name. Thus, we used a simple permutation of the first team members names letters, hence the funny name.

Supplementary Material https://github.com/librallu/dogs-color