Julien Clement
email: jclement@liafa.jussieu.fr

Xavier Défago
email: defago@jaist.ac.jp

Maria Gradinariu Potop-Butucaru

Stephane Messika
email: messika@lri.fr

Philippe Raipin-Parvedy
email: philippe.raipin@orange-ft.com

Stéphane Messika

Philippe Raipin-Parvédy

Fault and Byzantine Tolerant Self-stabilizing Mobile Robots Gathering

whether they are published or not. The documents may come

Introduction

Many applications of mobile robotics envision groups of mobile robots self-organizing and cooperating toward the resolution of common objectives. In many cases, the group of robots is aimed at being deployed in adverse environments, such as space, deep sea, or after some natural (or unnatural) disaster. It results that the group must self-organize in the absence of any prior infrastructure (e.g., no global positioning), and ensure coordination in spite of the presence of faulty robots and unanticipated changes in the environment.

The gathering problem, also known as the Rendez-Vous problem, is a fundamental coordination problem in cooperative mobile robotics. In short, given a set of robots with arbitrary initial location and no initial agreement on a global coordinate system, gathering requires that all robots, following their algorithm, reach the exact same location-one not agreed upon initially-within a finite number of steps, and remain there.

Similar to the Consensus problem in conventional distributed systems, gathering has a simple definition but the existence of a solution greatly depends on the synchrony of the systems as well as the nature of the faults that may possibly occur. In this paper, we investigate some of the fundamental limits of deterministic and probabilistic gathering in the face of various synchrony and fault assumptions.

To study the gathering problem, we consider a system model first defined by Suzuki and Yamashita (1999), and some variants with various degrees of synchrony. The model represents robots as points that evolve on a plane. At any given time, a robot can be either idle or active. In the latter case, the robot observes the locations of the other robots, computes a target position, and moves toward it. The time when a robot becomes active is governed by an activation daemon (scheduler). In the original definition of Suzuki and Yamashita, called the SYm model, activations (i.e., lookcompute-move) are atomic, and the scheduler is assumed to be fair and distributed, meaning that each robot is activated infinitely often and that any subset of the robots can be active simultaneously. In the CORDA model of Prencipe (2001), activations are completely asynchronous, for instance allowing robots to be seen while moving.

Suzuki and Yamashita (1999) proposed a gathering algorithm for non-oblivious robots in the SYm model. They also proved that gathering can be solved in systems with three or more oblivious robots, but not in systems with only two.1 Prencipe (2005) studied the problem of gathering in both SYm and CORDA models. He showed that the problem is impossible without additional assumptions such as being able to detect the multiplicity of a location (i.e., knowing the number of robots that may simultaneously occupy that location). Flocchini et al (2005) proposed a solution to gathering, for oblivious robots with limited visibility in the CORDA model, where robots share the knowledge of a common direction (e.g., as given by a compass). Based on that work, Souissi et al (2009) consider a system in which compasses are not necessarily consistent initially. Ando et al (1999) propose a gathering algorithm for SYm model with limited visibility. Cohen and Peleg (2006) study the problem when robots' observations and movements are subject to errors.

None of the studies mentioned above address the feasibility of gathering in fault-prone environments. One of the first steps in this direction was done by [START_REF] Agmon | Fault-tolerant gathering algorithms for autonomous mobile robots[END_REF]. They prove that gathering of correct robots (referred in this paper weak gathering) can be achieved in the SYm model even in the face of the crash of a single robot. Furthermore, they prove that no deterministic gathering algorithm exists in SYm model that can tolerate a Byzantine2 robot. Finally, they consider a stronger model, called fully synchronous, in which all robots are always activated simultaneously, and show that weak gathering can be solved in that model provided that less than one third of the robots are Byzantine.

Contribution.In this paper, we study further the feasibility of gathering in the SYm model in both fault-free and faultprone (crash and Byzantine) environments. In particular, we consider centralized schedulers3 (i.e., activations occurring in mutual exclusion) and bounded schedulers (i.e., between any two consecutive activations of a robot, no other robot is activated more than a bounded number of times).

More specifically, we obtain the following important results. Firstly, we strengthen the impossibility results of [START_REF] Agmon | Fault-tolerant gathering algorithms for autonomous mobile robots[END_REF] since we show that their impossibility results also hold in strictly stronger models. Secondly, we outline the limits under which Byzantine and crash-tolerant gathering become possible. In particular, we propose interesting lower bounds on the value k that a k-bounded scheduler must take for the problem to become solvable. Thirdly, we show in what situations randomized algorithms can help solve the problem, and when they cannot. To the best of our knowledge our work was the first to study the feasibility of probabilistic gathering in both fault-free and fault-prone systems. 4Structure of the paper.The rest of the paper is structured as follows. Section 2 describes the system model and basic terminology. Section 3 formally defines the gathering problem and recalls important lemmas found in the literature. Section 4 proposes possibility and impossibility results for deterministic and probabilistic gathering in fault-free environments. Section 5 and 6 extend the study to crash and Byzantine prone environments. Section 7 summarizes the results, and Section 8 concludes the paper.

Model

We define the system model used in the paper, as well as define important terminology. Most definitions are due to Suzuki and Yamashita (1999); Prencipe (2001); [START_REF] Agmon | Fault-tolerant gathering algorithms for autonomous mobile robots[END_REF].

Robot networks

We consider a robot network consisting of a finite set of robots arbitrarily deployed in a geographical area. A robot is a device with the ability to sense, compute and move. It can observe (sense) the positions of the other robots in the plane, it can perform local computations based on these observations, and it can move toward a target location it has computed.

When robots are able to sense the entire set of robots (regardless of the distance) it is said that they have unlimited visibility; otherwise robots are said to have limited vis-ibility. In this paper, we consider that robots have unlimited visibility.

The robots are said to have multiplicity knowledge when they are able to distinguish, in their observations, those locations that are shared by several robots.

System model

A network of robots that exhibit a discrete behavior can be modeled as an I/O automaton (Lynch (1996)). A network of robots exhibiting a continuous behavior can be modeled as a hybrid I/O automaton (Lynch et al (2003)). This framework allows for a modeling of systems that exhibit both a discrete and continuous behavior and in particular the modeling of robots networks.

The automaton modeling a robot can perform the following actions:

-Observation (input type action).

An observation returns a snapshot of the positions of all the robots within the visibility range. In our case, this observation returns a snapshot of the positions of all robots; -Local computation (internal action).

A local computation returns a target destination (point); -Motion (output type action).

A motion directs the actual motion of the robot towards a target destination. The robot may or may not reach the destination, but a progress assumption ensures that it travels a non-infinitesimal distance.

The local state of a robot at time t is the state of its input/output variables and the state of its local variables and registers. A network of robots is modeled by the parallel composition of the individual automata modeling each of the robots. A configuration of the system at time t is the union of the local states of the robots in the system at time t.

An execution e = (c 0 , . . . , c t , . . .) of the system is an infinite sequence of configurations, where c 0 is the initial configuration5 of the system, and every transition c i → c i+1 is associated with the execution of a subset of the previously defined actions.

Schedulers. A scheduler decides, for every configuration, which subset of the robots is activated (i.e., allowed to perform their actions). A scheduler is (weakly)6 fair if, in an infinite execution, a robot is activated infinitely often. In this paper we consider the fair version of the following schedulers:

arbitrary (unfair): At each activation, any non-empty subset of the robots is activated, without further limitations. Among other things, this means that the scheduler may decide to never activate some subset of the robots. The only guarantee is that, in an infinite execution, one of the correct robots must be activated infinitely often. unfair centralized: The scheduler is unfair (as described above) with the additional restriction that at most one (i.e., exactly one) robot is activated at each activation. fair: At each activation, any non-empty subset of the robots is activated, with the guarantee that every robot becomes active infinitely often in an infinite execution. fair centralized: The scheduler is fair (see above) with the additional guarantee that no more than one (i.e., exactly one) robot is activated at each activation. fair bounded: The scheduler is fair with the additional guarantee that there exists some bound k (unknown to the robots) such that between any two consecutive activations of some robot, no other robot is activated more than k times. fair k-bounded: The scheduler is fair bounded, but the bound k is fixed and known to the robots. fair bounded regular: The scheduler is fair k-bounded with k = 1. fair centralized bounded regular: The scheduler is fair bounded regular with the additional guarantee that exactly one robot is active at each activation. fully synchronized: Every robot is active at every activation.

We now summarize the relationships between the schedulers presented above. Given two schedulers A and B, A ⊃ B means that the set of all possible executions allowed by scheduler A strictly contains the set of all executions allowed by scheduler B. As a result, any algorithm that is correct under scheduler A is also correct under scheduler B. Likewise, any impossibility proven under scheduler B also holds under scheduler A.

unfair ⊃ fair unfair ⊃ unfair centralized unfair ⊃ fair centralized fair ⊃ fair centralized fair ⊃ fair bounded fair bounded ⊃ fair k-bounded fair k-bounded ⊃ fair bounded regular fair centralized ⊃ fair centralized bounded regular fair bounded regular ⊃ fair centralized bounded regular fair bounded regular ⊃ fully synchronized

The schedulers presented so far are deterministic in the sense that a scheduler can make any choice according to an algorithm that meets the constraints set by its type. In contrast, we consider the following probabilistic scheduler:

probabilistic: At each activation the robots that become active are selected randomly.

There are many variants of probabilistic schedulers (e.g., fair, centralized, . . .), similar to the deterministic ones. In the paper, we only consider the fair probabilistic scheduler, which ensures that, in an infinite execution, a robot is activated infinitely often with probability 1.

Faults. In this paper, we address the following failures:

crash failures: In this class, we further distinguish two subclasses: (1) robots physically disappear from the network, and (2) robots stop all their activities, but remain physically present in the network; -Byzantine failures: In this case, robots may have an arbitrary behavior.

Computational Models

The literature proposes mainly two computational models, namely, SYm and CORDA. The SYm model was introduced by Suzuki and Yamashita (1999). In this model each robot performs, once activated by the scheduler, a computation cycle composed of the following three actions: observation, computation and motion. The atomic action performed by a robot in this model is a computation cycle. The execution of the system can be modeled as an infinite sequence of rounds. In a round one or more robots are activated and perform a computation cycle. The SYm model was refined by [START_REF] Agmon | Fault-tolerant gathering algorithms for autonomous mobile robots[END_REF]. The authors distinguish the case of hyperactive systems where all robots are activated simultaneously and non-hyperactive systems where a strict subset of robots are simultaneously activated.

The CORDA model was introduced by Prencipe (2001). This model refines the atomicity of the actions performed by each robot. Hence, robots may perform in a decoupled fashion, the atomic actions of a computation cycle. They may be interrupted by the scheduler in the middle of a computation cycle. Moreover, while a robot performs an action A, where A can be one of the following atomic actions: observation, local computation or motion, another robot may perform a totally different action B.

In this paper, we consider the SYm model,7 refined with the scheduling strategies presented above. We consider that robots are oblivious (i.e., stateless) in that they do not conserve any information between two computational cycles. Additionally, we make no assumption on the initial positions of the robots. 8 As stated earlier, we assume that robots have unlimited visibility.

The Gathering Problem

A network of robots is in a terminal (legitimate) configuration with respect to the gathering requirement if all the robots share the same position in the plane. Let denote by P Gathering this predicate.

An algorithm solves the gathering problem in an oblivious system if the following two properties are verified:

-Convergence Any execution of the system starting in an arbitrary configuration reaches in a finite number of steps a configuration that satisfies P Gathering . -Termination Any execution starting in a terminal configuration with respect to the P Gathering predicate contains only legitimate configurations.

Gathering is difficult to achieve in most of the environments. Therefore, weaker forms of gathering were studied so far. An interesting version of this problem requires robots to converge toward a single location rather than reach that location in a finite time. The convergence is however considerably easier to deal with. For instance, with unlimited visibility, convergence can be achieved trivially by having robots moving toward the barycenter of the network [Suzuki and Yamashita (1999)].

Note that an algorithm that solves the gathering problem with oblivious or stateless robots is self-stabilizing [Dolev (2000)].

Existing Results

We now present a few lemmas proved previously by others, that are related to our study. When appropriate, the lemmas have been rephrased in order to keep the terminology consistent. First, the following two lemmas have been proved by Suzuki and Yamashita (1999) and refer to oblivious robots under a fair scheduler.

Lemma 1 (Suzuki and Yamashita (1999); Th. 3.1) There is no deterministic algorithm that solves gathering in the SYm model for n = 2 robots.

Notice that, although the above lemma is expressed according to a fair scheduler (SYm model), the execution used in the proof to show the impossibility is compatible with a fair bounded regular scheduler. It follows that the result also applies to a system based on that scheduler.

Lemma 2 (Suzuki and Yamashita (1999); Th. 3.4) Gathering of n ≥ 3 robots can be solved deterministically in the SYm model with multiplicity detection.

The following lemma, proved by Prencipe (2005), also refers to oblivious robots under a fair scheduler.

Lemma 3 (Prencipe (2005); Th. 2) In the SYm model (with a fair scheduler), there is no deterministic algorithm that solves gathering for n ≥ 2 oblivious robots without additional assumptions (e.g., multiplicity detection).

Finally, the following two lemmas, proved by [START_REF] Agmon | Fault-tolerant gathering algorithms for autonomous mobile robots[END_REF], refer to models with the presence of faulty robots. These lemmas propose results for the correct robots gathering.

Lemma 4 [START_REF] Agmon | Fault-tolerant gathering algorithms for autonomous mobile robots[END_REF]; Th. 3.5) Gathering can be solved deterministically in a (3, 1)-Crash model in the SYm model (under a fair scheduler with multiplicity detection).

Note 1 [START_REF] Agmon | Fault-tolerant gathering algorithms for autonomous mobile robots[END_REF] also show (Th. 3.8) that gathering can be solved deterministically in a (n, 1)-Crash model for any n ≥ 3, but under the restriction that the system is never in a configuration with more than one point of multiplicity.

Lemma 5 [START_REF] Agmon | Fault-tolerant gathering algorithms for autonomous mobile robots[END_REF]; Th. 4.1) In the SYm model, any deterministic non-hyperactive algorithm fails to solve gathering in a (3, 1)-Byzantine model.

Lemma 6 [START_REF] Agmon | Fault-tolerant gathering algorithms for autonomous mobile robots[END_REF]; Th. 4.4) In the SYm model (with a fair scheduler), there is no deterministic algorithm that solves gathering in a (3, 1)-Byzantine model.

Obviously, the above impossibility also holds in a (n, f )-Byzantine model for any number of robots n ≥ 3 and in the presence of any number of faulty robots 1 ≤ f ≤ n.

Lemma 7 [START_REF] Agmon | Fault-tolerant gathering algorithms for autonomous mobile robots[END_REF]; Th. 5.3) Gathering can be solved in an (3, 1)-Byzantine system in the fully synchronized model.

Lemma 8 [START_REF] Agmon | Fault-tolerant gathering algorithms for autonomous mobile robots[END_REF]; Th. 5.10) Gathering can be solved in an (n, f )-Byzantine system in the fully synchronized model for any n ≥ 3 f + 1.

Gathering in Fault-Free Environments

In this section, we refine results showing the impossibility of gathering [Prencipe (2005); [START_REF] Agmon | Fault-tolerant gathering algorithms for autonomous mobile robots[END_REF]] by proving first that these results hold even under more restrictive schedulers than the ones considered by Prencipe (2005) and [START_REF] Agmon | Fault-tolerant gathering algorithms for autonomous mobile robots[END_REF]. Interestingly, we also prove that some of these impossibility results hold even in probabilistic settings. Additionally, to circumvent these impossibility results, we propose a probabilistic algorithm that solves the fault-free gathering, under a special class of schedulers, known as bounded schedulers.

The following lemma shows that the impossibility result of Prencipe (2005) (Lemma 3) holds even under a weaker scheduler-the centralized fair bounded regular scheduler. Intuitively, a schedule of this particular scheduler is characterized by two properties: each robot is activated infinitely often and between two executions of a robot every robot in the network executes its actions exactly once. Moreover, in each configuration a single robot is allowed to execute its actions.

Lemma 9 There is no deterministic algorithm that solves gathering for n ≥ 3 under a fair centralized bounded regular scheduler, without additional assumptions (e.g., multiplicity knowledge).

Proof With no loss of generality, consider a system with three robots: r 1 , r 2 and r 3 arranged as shown on Figure 1. In the following, we construct an infinite execution that never converges. Consider a schedule Sch that invariably applies the following scenario: r 3 is chosen first, then r 1 , then r 2 . The schedule verifies the fair centralized bounded regular scheduler.

Consider now an initial configuration of the system such that robots r 2 and r 3 have the same initial location. Since r 3 does not have the ability to detect multiplicity, it observes the existence of two groups of robots but does not know how many robots are in each group. Since r 3 is oblivious, it cannot deterministically localize r 2 in the groups. Then, according to Sch, we can always find a scenario in which the system will cycle infinitely. For instance, Sch can generate the following change in robots topology: (r 1 , r 2 r 3 ) → (r 1 r 3 , r 2 ) → (r 3 , r 1 r 2 ) → (r 2 r 3 , r 1 ). It follows that the system never converges.

Algorithm 4.1 Probabilistic gathering for robot p.

Functions: observe neighbors :: returns the set of robots within visibility range of robot p (the set of p's neighbors). Note that, in a system with unlimited visibility, observe neighbors returns all the robots in the network.

Actions:

A 1 :: true -→ N p = observe neighbors(); with probability α = 1 |Np {p}| do select a robot q ∈ N p {p}; move towards q; Remark: with probability 1α, the position remains unchanged;

Note that Suzuki and Yamashita (1999) have proved that the deterministic gathering of two oblivious robots is impossible. The scenario is the following: the two robots are always activated simultaneously. Consequently, they continuously swap positions, and the system never converges. In the following, we prove that, for the case of two robots, there exists a probabilistic solution for gathering in the SYm model, under any type of scheduler. Algorithm 4.1 describes the probabilistic strategy of a robot. When chosen by the scheduler, a robot decides, with probability α, whether it will actually compute a location and move whereas, with probability 1α, the robot will remain stationary. The following lemma shows that Algorithm 4.1 reaches a terminal configuration with probability 1.

Lemma 10 Algorithm 4.1 solves the 2-gathering problem probabilistically under an arbitrary scheduler. It converges in 2 steps in expectation.

Proof Consider two robots r 1 and r 2 , and an arbitrary initial configuration c.

If r 1 and r 2 are gathered at the same location, they are already in a terminal configuration and thus neither will move, regardless of activations and the probability t. This leaves the case when r 1 and r 2 are not gathered initially.

Consider some step i when the two robots have distinct locations. If only one of the robots is activated by the scheduler, then there is a probability α that the robot moves, and thus the robots end up gathered in the next configuration (terminal). If both robots are activated at step i, then, they end up in a terminal configuration if either one of them change its position. This occurs with probability 2α(1α).

Consequently, the probability of reaching a terminal configuration during step i is at least q = min (α, 2α (α -1)) > 0, regardless of the choice of the scheduler. It follows that the probability of reaching a terminal configuration at step s > i is at least p = 1-(1-q) s . Thus, the probability for the system to reach a terminal configuration is lim s→∞ (1

-(1 -q) s ) = 1.
In the following we evaluate the convergence time of the algorithm. Let X t be the probabilistic variable that models the configuration of the system at time t. Let L be the set of terminal configurations (robots are gathered at the same location). Let T L the time to reach a configuration in L , T L = min{t, X t ∈ L }. The convergence time of the algorithme (also known as the hitting time) is

E[T L ] = ∑ ∞ i=1 i( 1 2 ) i = 2.
We complement Lemma 10 with two very simple lemmas.

Lemma 11

The 2-gathering problem can be solved deterministically under a centralized scheduler (fair or unfair).

Proof Let r 1 and r 2 be the two robots. Consider the simple algorithm which consists for one robot to move to the location of the next robot. Given that the scheduler is centralized, at most one robot must become active, thus the situation where the two robots exchange their position does not occur. Besides, since there are only two robots, at least one of them must repeatedly become active even if the scheduler is unfair. Thus, gathering is eventually reached.

The next lemma extends the impossibility result proved in Lemma 9 to probabilistic algorithms under fair schedulers.

Lemma 12 There is no probabilistic algorithm that solves the n-gathering problem, for n ≥ 3, under a fair centralized scheduler without additional assumptions (e.g., multiplicity knowledge).

Proof Consider an initial configuration in which nodes form two groups, G 1 and G 2 . Consider a schedule such that robots move from G 1 to G 2 and vice-versa, without ever reaching a terminal configuration. Consider now the following simple schedule: select one robot from the group with maximal multiplicity.9 With no loss of generality, let the selected robot be from G 1 . Recall that the algorithm executed by each robot is probabilistic. Therefore, it is possible that the selected robot needs to be activated several times until its coin allows it to actually move. Once the selected robot arrives in the opposite group, G 2 , select one of the robots in G 2 and activate it until it is ready to move.

Even if the scheduler is fair the above schedule generates an infinite execution that does not lead to a terminal configuration.

The key issue leading to the above impossibility is the freedom that the scheduler has in selecting a robot r until its probabilistic local computation allows r to actually move.

The scenario can however no longer hold with systems in which the scheduler is k-bounded. That is, in systems where a robot cannot be activated more than k times before the activation of another robot. In this type of game robots win against the scheduler and the system converges to a terminal configuration.

Lemma 13 Algorithm 4.1 probabilistically solves the n-gathering problem, n ≥ 3, under a fair bounded scheduler and without multiplicity knowledge.

Proof We show that with high probability a group of at least two robots is formed and then, with high probability this group will attract the other robots (even if these robots are not aware of the system multiplicity). Assume an arbitrary initial configuration -no two robots share the same position. Let c 0 be this configuration. Initially, the scheduler chooses s robots (s ≥ 1). With probability α s all the s robots choose as meeting point the same robot and move towards this robot. Let's call this robot the core of G. Let G be the group formed by these s+1 robots. Let G be the robots which do not share the same position as the robots in G. Let c 1 be the configuration obtained after the first choice of the scheduler. Starting with c 1 consider the following scenario. Each time a robot in G is chosen by the scheduler it selects with probability α a node in G (itself for example or the core of G). Each time a robot in G is chosen by the scheduler it selects with probability α a robot in G (for example the core of G). In the worst case, the robots in G have to wait to enter in G until each robot, already in this set, is chosen at most k times where k is the scheduler bound. Note that each time a robot in G is chosen, the size of G probabilistically decreases and the size of G probabilistically increases. Following the above scenario, the probability to obtain a configuration c 2 such that the size of G increases by one and the size of G decreases by one is superior to α k(s+1) α. The size of G is bounded. Therefore, by applying the previous scenario a terminal configuration is reached in a finite number of steps with positive probability,

superior to α s α k ∑ i=1,(n-s-1) (s+i) α n-s-1 ≥ α k n(n-1) 2 +(n-1) = ε,
where k is the scheduler bound. The probability that the system converges to a terminal configuration is lim m→∞ ε(1

+ ∑ i=1,m (1 -ε) i ) = 1.
5 Fault-tolerant and Self-stabilizing Gathering

In the following we extend the study of the gathering feasibility to fault-prone environments. In this section, (n, f ) denotes a system with n robots and up to f < n are faulty (i.e., they can crash). As mentioned in the model, Section 2, in an (n, f ) crash-prone system there are two types of crashes:

(1) the crashed robots completely disappear from the system, and (2) the crashed robots are still physically present in the system, however they stop the execution of any action.

In the first case the problem reduces to the situation where the number of robots in the systems becomes nf and for this point onward all the results proposed in the fault-free case apply. Therefore, in the sequel we analyze only the case where the faulty robots are still present in the system.

Lemma 14 In a crash-prone system, (3, 1)-strong gathering is deterministically impossible under a fair centralized bounded regular scheduler even with multiplicity knowledge.

Proof Assume a (3, 1) system where the faulty robot is still present in the system. Let us denote the three robots r 1 , r 2 and r 3 . Assume there exists an algorithm, A , that solves the strong gathering problem under a fair centralized bounded regular scheduler. We will analyze in the following two infinite suffixes of an execution of A , named e and e , starting in a configuration c where robots r 1 and r 2 share the same location while r 3 is on a different position. Let e be an execution in which no robot crashes, and let e be an execution where r 3 crashes. Consider the execution e. Since r 1 and r 2 share the same position in configuration c, the robots r 1 and r 2 will be instructed to not move, and thus continue to share the same location. Otherwise the system may never converge following Lemma 9. Consider now the execution e starting in the same configuration c. Since r 1 and r 2 have the same view as in the execution e then they will be instructed by Algorithm A to not move. Assume robot r 3 crashes in c, just before being scheduled. Therefore, even if r 3 is scheduled in c it cannot move and the strong gathering cannot be achieved. Overall, there is no algorithm that solves (3, 1)strong gathering even under fair centralized bounded regular scheduler.

The following two corollaries extend the result to systems with more than three robots. The corollaries derive trivially from Lemma 9 and Lemma 12 respectively.

Corollary 1 (of Lemma 9) In a crash-prone system, there is no deterministic algorithm that solves the (n, 1)-gathering problem, n ≥ 4, under a fair centralized bounded regular scheduler without additional assumptions (e.g, multiplicity knowledge).

Corollary 2 (of Lemma 12) In a crash-prone system, there is no probabilistic algorithm that solves the (n, 1)-gathering problem, n ≥ 3, under a fair centralized scheduler without additional assumptions (e.g., multiplicity knowledge).

Lemma 15 In a crash-prone system, (3, 1)-strong gathering is probabilistically impossible under a fair centralized scheduler even with multiplicity knowledge.

Proof Assume a (3, 1) system where the faulty robot is still present in the system. Let us denote the three robots r 1 , r 2 and r 3 . Assume there exists a probabilistic algorithm, A , that solves the strong gathering problem under a fair centralized scheduler. We will analyze in the following two infinite suffixes of an execution of A , named e and e , starting in a configuration c where robots r 1 and r 2 share the same location while r 3 is on a different position. Let e be an execution in which no robot crashes, and let e be an execution where r 3 crashes. Consider the execution e. Since r 1 and r 2 share the same position in configuration c, the robots r 1 and r 2 will be instructed to not move, and thus continue to share the same location. Consider now the execution e starting in the same configuration c. Since r 1 and r 2 have the same view as in the execution e then they will be instructed by Algorithm A to not move. Assume robot r 3 crashes in c, just before being scheduled. Therefore, even if r 3 is scheduled in c it cannot move and the strong gathering cannot be achieved.

Assume in c, r 1 is instructed to move and r 3 is crashed. Since the scheduler is centralized fair the next configuration is symmetrical with c and assume the scheduler chooses r 3 , then r 2 till it moves then r 1 till it moves, then again r 3 and r 1 till it moves back. The new configuration is identical to the configuration c and it verifies the fair scheduler predicate.

Overall, there is no algorithm that solves (3, 1)-strong gathering even with multiplicity knowledge under fair centralized scheduler.

The following lemma proves that (n, 1)-gathering is probabilistically possible under a bounded scheduler and without additional assumptions.

Lemma 16 In a crash-prone system, Algorithm 4.1 is a probabilistic solution for the gathering problem in systems with n correct robots but one and under a bounded scheduler.

Proof If the faulty robot disappears from the system then the result directly follows from Lemma 13 applied to a system with (n -1) robots.

Assume the faulty robot is still physically present in the system. We have to prove that with high probability all correct robots are attracted by the faulty robot. From this point further the proof is identical with the proof of Lemma 13.

In the following, we extend our study to systems with more than one faulty robot. Hereafter, (n, f )-gathering refers to the gathering problem in a system with n correct robots but f < n. If the faulty robots disappear from the system, then the problem trivially reduces to the study of a faultfree gathering with n-f correct robots. In contrast, in systems where faulty robots remain physically present in the network after crashing, the problem is far from being trivial. Obviously, gathering all the robots including the faulty ones, is impossible since faulty robots may possibly have crashed at different locations.

From this point on, we study the feasibility of a weaker version of gathering, referred to as weak gathering. The (n, f )weak gathering problem requires that, in a terminal configuration, only the correct robots must share the same position. The following lemma proves the impossibility of deterministic and probabilistic weak gathering under centralized, bounded, and fair schedulers, without additional assumptions.

Lemma 17 In a crash-prone system, there is neither a probabilistic nor a deterministic algorithm that solves the (n, f )weak gathering problem, n ≥ 3 and f ≥ 2, under a fair centralized regular scheduler without additional assumptions.

Proof Consider without restraining the generality f = 2. We will prove that each of the faulty robots becomes an attraction point and the correct robots will infinitely migrate between the faulty nodes. Therefore the system never converges. Assume an initial configuration such that the faulty nodes do not share the same position and all the correct robots are quasi-equitable divided in two groups -each group including a faulty node. Let color white and black the two groups respectively. The impossibility result for the deterministic case follows using the same construction as in the proof of Lemma 1. In the probabilistic case, with high probability a correct robot migrates between the two groups.

Algorithm 5.1 Deterministic fault-tolerant weak gathering for robot p Functions: observe neighbors :: returns the set of robots within the vision range of robot p (the set of p's neighbors); maximal multiplicity :: returns a robot in the group with the maximal multiplicity; or, if several such groups exists, makes an arbitrary choice among them (different from the curent location)

Actions:

A 1 :: true -→ N p = observe neighbors(); q = maximal multiplicity(N p ); move towards q;

An immediate consequence of the previous lemma is the necessity of an additional assumption (e.g., multiplicity knowledge), even for probabilistic solutions under bounded schedulers.

In the sequel, we identify the conditions under which the weak gathering accepts deterministic and probabilistic solutions. Algorithm 5.1 proposes a deterministic solution for the weak gathering that works under both centralized and bounded schedulers. The idea of the algorithm is as follows: a robot, once chosen by the scheduler, moves to the group with the maximal multiplicity -"attraction action". In case that all groups have the same multiplicity, the chosen robot will go to the location of another robot -"unbalanced action". The attraction action helps the convergence while the unbalanced action breaks the symmetry.

Lemma 18 In a crash-prone system, Algorithm 5.1 deterministically solves the (n, f )-weak gathering problem, with n > f under a centralized scheduler (fair or unfair) if robots are aware of the system multiplicity.

Proof The idea of the proof is the following. We show that eventually a group of maximal multiplicity is created and this group further attracts all correct robots.

Assume an initial configuration such that all nodes have the same multiplicity. More precisely, nodes are evenly distributed in the plane. After the scheduler choice, the chosen robot will create with its target a group of maximal multiplicity. Let denote this group attractor. Each subsequent choice of the scheduler will increase the size of the attractor. Since the number of the correct robots is finite, eventually the system converges to a terminal configuration.

Assume that in the initial configuration all robots are organized in two or more groups with equal multiplicity. After one choice of the scheduler one of these groups increases its multiplicity, hence the above described scenario applies and the system converges to a terminal configuration.

Note that in the previous lemma we considered unfair scheduling strategies with respect to the correct robots. Otherwise, the scheduler can choose infinitly often the crashed robot.

Algorithm 5.2 Probabilistic fault-tolerant gathering for robot p with multiplicity knowledge

Functions: observe neighbors :: returns the set of robots within the vision range of robot p (the set of p's neighbors); maximal multiplicity :: returns the set of robots with the maximal multiplicity;

Actions:

A

1 :: true -→ N p = observe neighbors(); if p ∈ maximal multiplicity(N p ) ∧ |maximal multiplicity (N p )| > 1 then
with probability 1 |maximal multiplicity(Np)| do select a robot q ∈ maximal multiplicity(N p ); move towards q; else select a robot q ∈ maximal multiplicity(N p ); move towards q;

In the following we show that (n, f )-weak gathering can be solved under arbitrary schedulers using a probabilistic algorithm, Algorithm 5.2, and multiplicity knowledge. Algorithm 5.2 works as follows. When a robot is chosen by the scheduler it moves to the group with maximal multiplicity. When all groups have the same size, then the robot tosses a coin to decide if it moves or holds the current position.

Lemma 19 In a crash-prone system, Algorithm 5.2 probabilistically solves the (n, f )-weak gathering problem, n > f , under an unfair scheduler if robots are aware of the system multiplicity.

Proof If the system starts in a configuration with an unique group of maximal multiplicity then this group will be the attraction point for the other robots in the network. The proof is similar with the proof of Lemma 18. Each robot, once chosen by the scheduler, will deterministically choose as destination the group with maximal multiplicity. Since the number of robots is finite, then the system converges to a terminal configuration in a finite number of steps.

In the case when the system starts in a configuration with equal sized (multiplicity) groups, we will show that with high probability an unbalanced group is formed. Then all the other nodes will be attracted by this group. Assume without restraining the generality, the scheduler chooses a robot in each group with maximal multiplicity. Let α = 1 |maximal multiplicity(N p )| be the probability that a robot chooses a particular target. In the following we evaluate the probability that the initial configuration does not change. With probability s!α s the system reaches a new configuration which is a permutation of the old configuration (either the s robots didn't change their positions or, once all robots have reached their targets, all groups are again equilibrated). The probability that the new obtained configuration is symmetrical to the old configuration is s!α s . However, the probability that the previous scenario repeats as the number of scheduler choices goes to infinite is lim m→∞ (s!α s ) m = 0. Eventually, with high probability the system reaches a configuration where an unique group has the maximal multiplicity. Starting from this point further the proof is similar to the previous case since nodes execute only deterministic actions.

Byzantine Tolerant and Self-stabilizing Gathering

In the following we study the gathering feasibility in systems prone to Byzantine failures. In the sequel (n, f ) denotes a system with n correct robots but f . [START_REF] Agmon | Fault-tolerant gathering algorithms for autonomous mobile robots[END_REF] proved that gathering in Byzantine environments is impossible in SYm and CORDA models for the case (3, 1). The impossibility proof is given for the case of the SYm model and algorithms that are not hyperactive. The following lemma proves the (3, 1)-gathering impossibility under the weakest scheduler, in particular the centralized, fair and regular.

Lemma 20 In a Byzantine-prone system, there is no deterministic algorithm that solves (3, 1)-weak gathering under a fair centralized bounded regular scheduler without additional assumptions.

Proof Consider the following scheduling strategy. Every time a byzantine robot is chosen it chooses to move to an arbitrary location. In particular, it can chose to move to the previous location of the correct robot that moved in the previous round. In the following we show that the system may cycle between two non-terminal configurations. Assume 3 robots, r 1 ,r 2 , r 3 and assume r 3 byzantine. Assume that robots initially does not share the same position. The system topology changes from the topology (r 1 , r 2 , r 3 ) to (-, r 2 , r 1 r 3 ) → (r 3 , r 2 , r 1 ) → (r 3 r 2 , -, r 1 ) → (r 1 r 2 r 3 , -, -). Let's denote c the configuration corresponding to the last topology. Since r 3 is byzantine it can move and the system may reach the following topology (r 1 r 2 , r 3 , -) (robots r 1 and r 2 are gathered). If robots do not have the multiplicity knowledge they can be attracted by the byzantine node, hence the system evolves to the following topology (r 1 , r 2 r 3 , -) then (-, r 1 r 2 r 3 , -). Note that the system reached again the configuration c. Overall, the system never reaches a terminal configuration.

2 Note that Algorithm 5.1 solves the Byzantine (3, 1)weak gathering under a fair centralized bounded regular scheduler and multiplicity knowledge. The cycle created in the impossibility proof is broken because the Byzantine robot cannot play the attractor role.

The following lemma shows that if the scheduler is relaxed, the (3, 1)-weak gathering becomes impossible even if robots are aware of the system multiplicity.

Lemma 21 In a Byzantine-prone system, there is no deterministic algorithm that solves the (3, 1)-weak gathering, even when robots are aware of the system multiplicity, under a fair centralized k-bounded scheduler with k ≥ 2.

Proof The general proof idea is the following : the byzantine node plays the attractor role, hence the system never reaches a terminal configuration. Consider a schedule Sch such that after each execution of a correct robot the scheduler gives the permission to the byzantine robot to move. This schedule verifies the specification of the 2-bounded scheduler. Assume that each time a correct node chooses to move, it chooses as target the location of the Byzantine node. Then, following the scheduler Sch the Byzantine node will replace the location of the node that just joined its location. Therefore, the system never converges.

Note 3 Byzantine (n, 1)-weak gathering for any odd n > 4 is possible under any fair centralized scheduler and multiplicity knowledge. The algorithm is trivial: a robot moves to the group with maximal multiplicity.

The following lemma establishes a lower bound for the fair centralized bounded scheduler that prevents the deterministic gathering.

Lemma 22 In a Byzantine-prone system, there is no deterministic algorithm that solves (n, 1)-weak gathering, with n ≥ 2 even, under a fair centralized k-bounded scheduler for k ≥ (n -1). This result holds even when robots are aware of the system multiplicity.

Proof Assume by contradiction that there is an algorithm, A , that solves the (n-1)-gathering under a fair k-bounded scheduler for k ≥ (n -1). Assume the following initial configuration: robots are organized in two groups of equal size. One of the groups contains the byzantine robot. Let refer the group containing the byzantine robot as the black group and the other group -the white group. Assume the scheduler applies iteratively the following two choices: (C1) choose a robot in the white group; (C2) choose the byzantine robot. Since A is a deterministic algorithm that solves gathering whenever a correct robot is chosen it moves towards another robot, otherwise the termination property is not verified. Consider in the following that the byzantine robot always moves towards the group with the weaker weight. After the choices C1 and C2 the system reaches a configuration symmetrical to the initial configuration: two groups of equal size one black and one white. In order to win the game the byzantine robot should do a move for each move of a correct robot. Therefore, for any fair centralized k-bounded scheduler with k ≥ (n -1) the byzantine robot wins and the gathering becomes impossible.

Corollary 3 Byzantine (n, 1)-weak gathering is possible under a centralized scheduler in systems where n ≥ 4 is odd, robots have multiplicity knowledge and the scheduler is fair.

Corollary 4 Byzantine (n, 1)-weak gathering is possible under a fair centralized scheduler in systems where n ≥ 2 is even, robots have multiplicity knowledge and the scheduler is k-bounded with k ≤ (n -2).

The following lemma states the lower bound for a bounded scheduler that prevents deterministic gathering.

Lemma 23 In Byzantine-prone systems, there is no deterministic algorithm that solves (n, f )-weak gathering, f ≥ 2, under a fair centralized k-bounded scheduler with k ≥ n-f f when n is even, and with k ≥ n-f f -1 when n is odd, even when the robots can detect multiplicity.

Proof -Even case. Similar to the (n, 1) case above, assume that the system starts in an initial configuration in which all robots are arranged in two groups. Assume the same scheduler as in the (n, 1) case: for each move of a correct robot the scheduler chooses a Byzantine robot.

The Byzantine robot will try to balance the system equilibrium hence it will move towards the old location of the correct robot. In order to win the game the Byzantine robots need to move each time a correct robot moves.

Since there are n-f correct robots in the system, the scheduler has to be bounded by no less than n-f f for the Byzantine team to win.

-Odd case. For the odd case assume an initial configuration where robots but one (a Byzantine one) are arranged in two groups. When chosen by the scheduler the Byzantine robot not member of a group moves such that the equilibrium between the two groups does not change.

Let denote G 1 and G 2 the two groups. Consider the following schedule. Every time a correct robot, member of G i , moves, a Byzantine robot moves as well in the opposite direction. Hence the system equilibrium does not change. The game is similar to the even case. The only difference is that the number of Byzantine robots that influence the faith of the game is f -1. Therefore, in order to win the game, the Byzantine team needs a fair k-bounded scheduler bounded by k ≥ n-f f -1 .

The next lemma is a possibility result when randomization is used. Note that this possibility results needs probabilistic behavior from both algorithm and scheduler.

Lemma 24 In systems with Byzantine faults, Algorithm 5.2 probabilistically solves the (n, f )-weak gathering, n ≥ 3, problem under a probabilistic scheduler and multiplicity detection.

Proof The proof is based on the fact that as soon as there exists a group of N 2 + 1 correct robots gathered, it just needs a"few" more rounds to achieve convergence. This idea is that every time a robot is selected by the scheduler, it joins this group. Therefore, beyond this point, the convergence time only depends on the scheduler.

Let's study the probability for such a group to be created. We define L : There exists a group of N 2 + 1 correct robots gathered.

P reach L in N 2 + 1 steps > 1 N ( N 2 +1) = ε So P ¬(reach L in ( N 2 + 1) steps) ≤ (1 -ε) Therefore : ∀k P ¬(reach L in k( N 2 + 1) steps) ≤ (1 -ε) k lim k→∞ P ¬(reach L in k( N 2 + 1) steps) = 0
Note that in our scenario the convergence time is exponential. In order to simplify the calculations we look at :

1 N N instead of 1 N ( N 2 +1) . So, 1 -1 N N t ≤ α. This leads to: tln 1 -1 N N ≤ lnα. Overall, t verifies: t ≥ lnα ln 1-( 1 N ) N ∼ ln 1 α N N 7 Summary 8 Conclusion
The results presented here extend the prior work on the possibility and impossibility of gathering in fault-free and both crash-prone and Byzantine-prone systems. For instance, we strengthen several prior impossibility results by showing that they still hold against weaker schedulers, and under various failure models. We also mark out more accurately the limit between possibility and impossibility by deriving appropriate upper and lower bounds.

To the best of our knowledge, this is actually the first extended study that considers probabilistic solutions to solve the gathering problem in both fault-free and fault-prone models. Here, we identify conditions under which a probabilistic solution exists, as well as conditions for which not even a probabilistic solution exists. The main results of the paper are summed up in Table 1 for fault-free systems; in Table 2 and Table 3 for strong respectivelly weak gathering in crash-prone systems; and in Table 4 for the weak gathering problem in Byzantine-prone systems. Several research directions are opended by our study: 1. Our work is only a first step in investigating the Byzantine tolerant gathering. It should be noted that the only probabilistic possibility result is derived only under a probabilistic scheduler. This open a vaste field of investigation related to the possibility of probabilistic gathering under different schedulers. Also the investigation of the deterministic case is not completly closed. 2. Some of the proofs proposed in the curent document only consider the use of randomization for determining whether a robot takes actions or not when it is activated. One can argue that using randomization in a different way may possibly change some of the lower bounds presented here. 3. The impossibility results and the scheduler lower bounds are computed only for the memoriless robots. An interesting exercise would be to revisit these lower bounds and impossibility results when robots are enhanced with memory and communication skils. 4. In order to close the problem a similar study can be conducted for the CORDA model. Note that the impossibility results we proposed for the SYm model also hold for the CORDA model. As far as the possibility results are concerned we conjecture that our probabilistic algorithms verify the gathering specification in the CORDA model under bounded schedulers. NO(L.17) NO(L.17) a The unfair behavior of the scheduler is restricted only to correct processes, otherwise the impossibility result follows trivially (the scheduler chooses only the crashed process). b Note that the results derived from Lemma 4 hold for the case (3,1). According to Note 1 in the case (n,1) weak gathering is possible only if during the execution each configuration has at most one multiplicity point. Therefore, the self-stabilizing (n,1) weak-gathering is impossible since the initial configuration can contain more than one multiplicity point.

Fig. 1

 1 Fig. 1 Lemma 9: constructing an infinite execution.

  82, DOI http://dx.doi.org/10.1137/050645221 Ando H, Oasa Y, Suzuki I, Yamashita M (1999) Distributed memoryless point convergence algorithm for mobile robots with limited visibility. IEEE Trans on Robotics and Automation 15(5):818-828 Cohen R, Peleg D (2006) Convergence of autonomous mobile robots with inaccurate sensors and movements. In: Durand B, Thomas W (eds) 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS'06), Springer, Marseille, France, LNCS, vol 3884, pp 549-560 Défago X, Gradinariu M, Messika S, Raipin-Parvédy P (2006) Faulttolerant and self-stabilizing mobile robots gathering: Feasibility study. DISC'06 pp 46-60 Dolev S (2000) Self-Stabilization. MIT Press Flocchini P, Prencipe G, Santoro N, Widmayer P (2005) Gathering of asynchronous mobile robots with limited visibility. Theor Comput Sci 337:147-168 Lynch NA (1996) Distributed Algorithms. Morgan Kaufmann, San Francisco, CA, USA Lynch NA, Segala R, Vaandrager FW (2003) Hybrid I/O automata. Information and Computation 185(1):105-157 Prencipe G (2001) CORDA: Distributed coordination of a set of autonomous mobile robots. In: Proc. 4th European Research Seminar on Advances in Distributed Systems (ERSADS'01), Bertinoro, Italy, pp 185-190 Prencipe G (2005) On the feasibility of gathering by autonomous mobile robots. In: Pelc A, Raynal M (eds) Proc. Structural Information and Communication Complexity, 12th Intl Coll., SIROCCO 2005, Springer, Mont Saint-Michel, France, LNCS, vol 3499, pp 246-261 Souissi S, Défago X, Yamashita M (2009) Using eventually consistent compasses to gather memory-less mobile robots with limited visibility. ACM Trans Autonomous and Adaptive Systems 4(1):9:1-27

  centr. (Γ (n, f ) ≤ k ≤ n -2)-bound. NO(L.6)+NO(L.5) OK(C.4) OK(N.3) NO(L.22) NO(L.23) centr. (2 ≤ k < Γ (n, f ))-bound. .8) if n ≥ 3 f + 1 Γ (n, f ) = n-f f if n even ; Γ (n, f ) = n-f f -1 if n odd.The unfair behavior of the scheduler is limited to correct processes only, or else the impossibility would be trivial. Suzuki I, Yamashita M (1999) Distributed anonymous mobile robots: Formation of geometric patterns. SIAM Journal of Computing 28(4):1347-1363

Table 1

 1 Summary: strong gathering; fault-free model.

	multiplicity

Table 2

 2 Summary: strong gathering; crash model.

	multiplicity

Table 3

 3 Summary: weak gathering; crash model.

	f = 1

Table 4

 4 Summary: weak gathering; Byzantine model.

	multiplicity; deterministic
	f = 1		f ≥ 2
	n ≥ 4	n ≥ 4	n ≥ 4	n ≥ 4

With two robots, all configurations are symmetrical and may lead to robots endlessly swapping their positions. In contrast, with three or more robots, an algorithm can be made such that, at each step, either the robots remain symmetrical and they eventually reach the same location, or symmetry is broken and this is used to move one robot at a time into the same location.

2 A Byzantine robot is a faulty robot that behaves arbitrarily, possibly in a way to deliberately prevent the other robots from gathering in a stable way.

The rationale for considering a centralized scheduler is that, with communication facilities, the robots can synchronize by running a mutual exclusion algorithm, such as token passing.

 4 An extended abstract of this work was published as[Défago et al (2006)].

Unless stated otherwise, this paper makes no specific assumption regarding the respective positions of robots in initial configurations.

Weak fairness requires that every robot that is continuously ready to take an action is eventually activated. But, since a robot is always ready to be activated in our model, a distinction between weak and strong fairness is not relevant.

Note that all impossibility results proven in the SYm model also hold in the CORDA model

One of the major motivations for considering oblivious robots is that, as observed bySuzuki and Yamashita (1999), algorithms designed for that model are inherently self-stabilizing.

If the groups have the same multiplicity then select one of the two groups arbitrarily.


Dimo Brockhoff
email: dimo.brockhoff@inria.fr

Anne Auger
email: anne.auger@inria.fr

Nikolaus Hansen
email: nikolaus.hansen@inria.fr

On the Effect of Mirroring in the IPOP Active CMA-ES on the Noiseless BBOB Testbed

Keywords: G.1.6 [Numerical Analysis]: Optimization-global optimization, unconstrained optimization; F.2.1 [Analysis of Algorithms and Problem Complexity]: Numerical Algorithms and Problems Benchmarking, Black-box optimization

Mirrored mutations and active covariance matrix adaptation are two recent ideas to improve the well-known covariance matrix adaptation evolution strategy (CMA-ES)-a stateof-the-art algorithm for numerical optimization. It turns out that both mechanisms can be implemented simultaneously. In this paper, we investigate the impact of mirrored mutations on the so-called IPOP active CMA-ES. We find that additional mirrored mutations improve the IPOP active CMA-ES statistically significantly, but by only a small margin, on several functions while never a statistically significant performance decline can be observed. Furthermore, experiments on different function instances with some algorithm parameters and stopping criteria changed reveal essentially the same results.

INTRODUCTION

The covariance matrix adaptation evolution strategy (CMA-ES) is a state-of-the-art algorithm for numerical optimization. If after each restart, its population size is increased by a factor of two, we talk about the IPOP-CMA-ES which showed good and competitive results on a variety of test problems [START_REF] Auger | A Restart CMA Evolution Strategy With Increasing Population Size[END_REF][START_REF] Ros | Black-box optimization benchmarking the IPOP-CMA-ES on the noiseless testbed: comparison to the BIPOP-CMA-ES[END_REF] as well as in practice. A recent variant c ACM, 2012.

This is the authors' version of the work.

It is posted here by permission of ACM for your personal use. Not for redistribution.

The definitive version was published at GECCO Companion '12, July 7-11, 2012, Philadelphia, PA, USA. http://doi.acm.org/10.1145/2330784.2330824 of the standard CMA-ES is the active CMA-ES [START_REF] Jastrebski | Improving evolution strategies through active covariance matrix adaptation[END_REF] where also "bad" steps are taken into account to shrink the covariance matrix of the search distribution along axes with inferior performance. When combined with the IPOP-CMA-ES, a substantial performance gain can be observed on the BBOB test bed [START_REF] Hansen | Benchmarking a weighted negative covariance matrix update on the BBOB-2010 noiseless testbed[END_REF]. Another recent algorithm development for evolution strategies is the idea of mirrored mutations [START_REF] Brockhoff | Mirrored Sampling and Sequential Selection for Evolution Strategies[END_REF][START_REF] Auger | Mirrored Sampling in Evolution Strategies With Weighted Recombination[END_REF]. The main idea here is to use dependent, mirrored mutations instead of the standard independent ones with the additional trick to only evaluate the mirrors of solutions with bad function values (selective mirroring). This variant has shown improved performance over the standard CMA-ES in particular on the sphere function. Both ideas can, in principle, be easily combined and in this paper we investigate the impact of mirrored mutations on the IPOP active CMA-ES.

It turns out that on the one hand, the additional mirrored mutations have a positive effect on the performance of the IPOP active CMA-ES and on the other hand that small changes in the algorithm parameters and stopping criteria do not essentially change the results on the BBOB test functions.

ALGORITHM PRESENTATION

The IPOP-CMA-ES

The standard CMA-ES samples in each iteration λ normally distributed solutions xi = mt + σtN (0,Ct)i nt h e search space R D , given the current mean mt,s t e ps i z eσt, and covariance matrix Ct at time t. After evaluating the λ new search points on the objective function, the best µ solutions x 1:λ ,...,x µ:λ are recombined via weighted recombination to the new mean mt+1 = µ i=1 wix i:λ andstepsize and covariance matrix are adapted via the so-called cumulative evolution path(s) [START_REF] Hansen | Completely Derandomized Self-Adaptation in Evolution Strategies[END_REF]. The so-called IPOP-CMA-ES where IPOP stands for increasing population size, restarts the algorithm with a doubled population size when convergence is detected by some stopping criteria [START_REF] Auger | A Restart CMA Evolution Strategy With Increasing Population Size[END_REF]. With an initial population size of λ s =4+⌊3log(D)⌋, the algorithm is quasi parameter-free.

The IPOP Active CMA-ES

A CMA-ES variant with negative or active covariance matrix adaptation allows negative weights in the update of the covariance matrix taking into account also the worst solutions. The main idea behind this update is "to use information about unsuccessful offspring candidate solutions in order to actively reduce variances of the mutation distri-bution in unpromising directions of the search space" [START_REF] Jastrebski | Improving evolution strategies through active covariance matrix adaptation[END_REF]. The additional active covariance adaptation has been shown to improve the performance of the IPOP-CMA-ES on the BBOB test bed [START_REF] Hansen | Benchmarking a weighted negative covariance matrix update on the BBOB-2010 noiseless testbed[END_REF].

The IPOP-CMA-ES With Mirrored Mutations

The idea of mirrored mutations has been introduced recently into weighted recombination evolution strategies [START_REF] Auger | Mirrored Sampling in Evolution Strategies With Weighted Recombination[END_REF]. The main idea is thereby the following. Instead of sampling all λ new solutions in iteration t of the algorithm independently, only λ iid samples are drawn independently and identically distributed while the remaining λm solutions are mirrors of already sampled solutions. The mirror of a solution xi = mt + d (with d distributed according to σtN (0,Ct)) is the solution in the opposite direction of the mean mt, i.e., the solution

x ′ i = mt -d.
Pairwise selection is furthermore used to prevent a bias in the step size: at most one solution of each mirrored/unmirrored solution pair is used within the weighted recombination and to update the algorithm's evolution path(s). Finally, with the idea of selective mirroring, only the worst of the λ iid solutions are mirrored-improving the convergence rate of the algorithm significantly [START_REF] Auger | Mirrored Sampling in Evolution Strategies With Weighted Recombination[END_REF]. Here, we use selective mirroring with λm = ⌊0.5+0.159λ iid ⌋ (where pairwise selection becomes superfluous), and recombination weights as in [START_REF] Auger | Mirrored Sampling in Evolution Strategies With Weighted Recombination[END_REF].

Combining Active Covariance Matrix Adaptation and Mirrored Mutations

The implementations of active covariance matrix adaptation and mirrored mutations are, in principle, independent of each other and can be turned on and off individually. The additional active covariance matrix adaptation is thereby performed after the standard covariance matrix adaptation where the mirrored mutations are taken into account. Combining both approaches is of conceptual advantage even on the linear and the sphere function, where the updates tend to cancel each other out: if we denote a bad solution as x = mt + σtN and its mirrored counterpart as x ′ = mt -σtN ,t h e nw -NN T with w -< 0 is added to the covariance matrix within active covariance matrix adaptation and w + (-N )(-N ) T = w + NN T with w + > 0 is added to the covariance matrix during the default update, if -N turns out to be a successful direction. On the linear and the sphere function the mirrors of bad solutions tend to be successful thereby stabilizing the covariance matrix in its original shape. This is desirable in both cases.

Implementation Details

In the following, we compare three IPOP-CMA-ES variants: active CMA-ES as benchmarked for BBOB'2010 [START_REF] Hansen | Benchmarking a weighted negative covariance matrix update on the BBOB-2010 noiseless testbed[END_REF], denoted by IPOP-ACTCMA-ES, our current implementation of active CMA-ES (version 3.54.beta.mirrors), denoted as CMAa,a n dt h eC M A a with additional mirrored mutations which we denote as CMAma in the following. The first two algorithms use different parameters and stopping criteria. The CMAa uses

• cumulation parameter cc =( 4+µ eff /D)/(D +4+ 2µ eff /D) instead of cc =4 /(D + 4) for the IPOP- ACTCMA-ES,
• a maximum number of 1000(D +5) 2 / √ λ iterations per restart instead of 100 + 50(D +3) 2 / √ λ,

• TolX=2e-11 instead of TolX=2e-12

• TolHistFun=1e-13 instead of TolHistFun=1e-12

• TolUpSigma=inf (i.e., not implemented) instead of TolUpSigma=1e20, see [START_REF] Hansen | Benchmarking a BI-population CMA-ES on the BBOB-2009 function testbed[END_REF]. This difference is likely to have a noticeable impact on some multimodal functions like f19.

Additionally, in CMAma, the step-size damping is reduced by (1 -min(1, (λmirr/(0.159λ) -1)

TIMING EXPERIMENTS

In order to see the dependency of the algorithms on the problem dimension, the requested BBOB'2012 timing experiment has been performed for the CMA-ES variant with active covariance matrix adaptation without mirrored mutations (CMAa) and the same algorithm with mirrored mutations (CMAma) on an Intel Core2 Duo T9600 laptop with 2.80GHz, 4.0GB of RAM, and MATLAB R2008b on Windows Vista SP2. The algorithms have been restarted for up to 2•10 5 D function evaluations until 30 seconds have passed. The per-function-evaluation-runtimes were 25, 18, 13, 7.9, 5.5, 5.5, and 7.4t i m e s1 0 -4 seconds for the CMAa and 16, 16, 11, 6.5, 4.2, 4.6, and 7.2t i m e s1 0 -4 seconds for the CMAma in 2, 3, 5, 10, 20, 40, and 80 dimensions respectively. The used implementation is version 3.54.beta.mirrors and can be downloaded from http://canadafrance.gforge.inria. fr/mirroring/. In comparison, [START_REF] Hansen | Benchmarking a weighted negative covariance matrix update on the BBOB-2010 noiseless testbed[END_REF] correspondingly states 2.0, 1.7, 1.4, 1.2, 1.1, 1.4, and 3.6t i m e s1 0 -4 seconds per function evaluation on an Intel Core 2 6700 processor (2.66 GHz) with Linux 2.6.28-18 and Matlab R2008a for the 2010 implementation of the IPOP-ACTCMA-ES.

RESULTS

Results from experiments according to [START_REF] Hansen | Real-parameter black-box optimization benchmarking[END_REF] on the benchmark functions given in [START_REF] Finck | Real-parameter black-box optimization benchmarking 2009[END_REF][START_REF] Hansen | Real-parameter black-box optimization benchmarking 2009: Noiseless functions definitions[END_REF] are presented in Figures 1,2 and 3 and in Tables 1 and2. The expected running time (ERT), used in the figures and table, depends on a given target function value, ft = fopt +∆f , and is computed over all relevant trials as the number of function evaluations executed during each trial while the best function value did not reach ft, summed over all trials and divided by the number of trials that actually reached ft [START_REF] Hansen | Real-parameter black-box optimization benchmarking[END_REF][START_REF] Price | Differential evolution vs. the functions of the second[END_REF]. Statistical significance is tested with the rank-sum test for a given target ∆ft (10 -8 as in Figure 1) using, for each trial, either the number of needed function evaluations to reach ∆ft (inverted and multiplied by -1), or, if the target was not reached, the best ∆f -value achieved, measured only up to the smallest number of overall function evaluations for any unsuccessful trial under consideration.

Impact of Mirrored Mutations.

Mirrored mutations show a small but consistent improvement on seven unimodal functions, where on each function the effect is significant for at last one dimensionality. The effect is however small enough that it might be mainly explained by the setting of the step-size damping parameter dσ that depends on the number of mirrored mutations. Further effects of mirrored mutations are neither systematic nor significant and likely to have happened by chance. In particular, mirrored mutations seem not to be harmful on any of the 24 test functions.

Impact of Parameter Setting and Instance Numbers.

We find a statistically significant difference between CMAa and IPOP-ACTCMA-ES on f13 in 2D, on f16 in 40D, on f17 in 10D, and on f19 in 5D. Only the last two effects are quantitatively relevant and only in the last case, IPOP-ACTCMA-ES outperforms CMAa.F u r t h e r m o r e i s o n f19 and f20 the success rate in 20-D significantly higher with IPOP-ACTCMA-ES. No other statistically significant differences are observed (the test results not shown). The improvement of IPOP-ACTCMA-ES on f19,w h e r eI P O P -ACTCMA-ES seems to be consistently better than CMAa and on f20 (and possibly on f22) is likely to be caused by the TolUpSigma termination. The other parameter differences seem to have minor or no effect.

SUMMARY

Two main statements have been supported by empirical results on the noiseless BBOB testbed. First, additional mirrored mutations improve the performance of the IPOP active CMA-ES on several functions by a small margin while no detrimental effects can be observed. Second, changes of some parameters and stopping criteria in IPOP active CMA-ES do only have a comparatively small effect on the results and are only observable when restarts are necessary to solve the function.

Figure 1 :Figure 2 :

 12 Figure 1: Expected running time (ERT in number of f -evaluations) divided by dimension for target function value 10 -8 as log 10 values versus dimension. Different symbols correspond to different algorithms given in the legend of f1 and f24. Light symbols give the maximum number of function evaluations from the longest trial divided by dimension. Horizontal lines give linear scaling, slanted dotted lines give quadratic scaling. Black stars indicate statistically better result compared to all other algorithms with p<0.01 and Bonferroni correction number of dimensions (six). Legend: •:IPOP-ACTCMA-ES, ▽:CMA a, ⋆:CMA ma

  • 10 5 • D function evaluations. The implementations of the CMAa and the CMAma can be found at http://canadafrance.gforge.inria.fr/mirroring/.

	2 ))/2 ∈ [0, 1/2]. Since we used the original BBOB'2010 data for the IPOP-ACTCMA-
	ES, also the function instances differ. While for the IPOP-
	ACTCMA-ES, the instances 1,...,15 are used, the new re-
	sults for the CMAa and the CMAma,a r eo b t a i n e df o rt h e
	BBOB'2012 instances 1,...,5, 21,...,30.
	All algorithms are restarted maximally nine times and
	stopped after at most 2

Table 1 :

 1 Expected running time (ERT in number of function evaluations) divided by the respective best ERT measured during BBOB-2009 (given in the respective first row) for different ∆f values in dimension 5.T h e central 80% range divided by two is given in braces. The median number of conducted function evaluations is additionally given in italics,i fERT(10 -7 )=∞. #succ is the number of trials that reached the final target fopt +10 -8 . Best results are printed in bold. The first row ('1:I') shows results for the IPOP-ACTCMA-ES, '2:a' is the CMAa, and '3:ma' is the CMAma.

	separable fcts

2]

for all functions and subgroups in 5-D. The "best 2009" line corresponds to the best ERT observed during BBOB 2009 for each single target. divided by dimension (FEvals/D) for 50 targets in 10 [-8..2] for all functions and subgroups in 20-D. The "best 2009" line corresponds to the best ERT observed during BBOB 2009 for each single target.

Table 2 :

 2 Expected running time (ERT in number of function evaluations) divided by the respective best ERT measured during BBOB-2009 (given in the respective first row) for different ∆f values in dimension 20.T h e central 80% range divided by two is given in braces. The median number of conducted function evaluations is additionally given in italics,i fERT(10 -7 )=∞. #succ is the number of trials that reached the final target fopt +10 -8 . Best results are printed in bold. The first row ('1:I') shows results for the IPOP-ACTCMA-ES, '2:a' is the CMAa, and '3:ma' is the CMAma.