Wajdi Dandach
email: dandach@emse.fr

Jérôme Molimard
email: bmolimard@emse.fr

Pascal Picart
email: cpascal.picart@univ-lemans.fr

Direct strain and slope measurement using 2D DSPSI Title

Keywords: Interferometry, Digital speckle pattern shearing interferometry (DSPSI), Strain measurements, Optical full-field technique (OFFT)

come

Introduction

We used an optical full-field technique (OFFT) for measuring surface strain fields of composite coupon submitted to bending and shear in a modified Iosipescu device. Most of OFFT measure displacements (Electronic Speckle Patter Interferometry, Grid Method, Moiré Interferometry and so on); one of the challenging parts of displacement measurement techniques is the calculation of the strain map from the displacement map. In particular, noise propagation and lens distortion has to be carefully treated. Adjacent to the methods measuring displacements, DSPSI measures directly displacement derivatives of surfaces. More accurately, it eliminates the reference beam of holographic or speckle interferometry, which leads to a simplified optical set-up, not requiring special vibration isolation. These advantages have exhibited practically DSPSI a surface strain and rotation measurement system. Historically, main drawback of the technique is the use of an image doubling element, and a loose of spatial resolution. Since this technique combines temporal phase shifting with the use of a small shear distance (50µm in this experiment) [START_REF] Aebischer | [END_REF], it is shown here that it is possible to find a very good compromise between resolution, spatial resolution and sensitivity.

Experimental Conditions

Optical Set-up.

The set-up used for this experiment is optimised to reduce signal upon noise ratio and to maximise spatial resolution (Fig. 1). A laser (λ=532 nm) illuminates the front surface of the specimen [4]. Light is sequentially injected in the four optical fibers by using an optical switch . The outputs fibers are attached to a device, manufactured in the laboratory, which allows the laser collimated beam illuminates the surface of the specimen by four directions (Fig. 1). This way, the four necessary directions of illumination can be realized, with equivalent illumination angle. The diffracted beam from the specimen is sheared by Michelson interferometer containing a beam splitter and two mirrors. First mirror is fixed; the second is controlled by a 3-axis PTZ device PSH 1z NV from Piezo-system Jena, capable of tilting or translating the mirror. As follow, we can realize the shear in x or y directions by tilting one mirror, similarly the piston movement for the temporal phase stepping, we can observe images.

Acquisition is performed using a 12 bit Jai camera equipped with a zoom lens, connected to a gigabit Ethernet card plugged into a PC. Two images can be observed due to shearing distance, these two images are recovered by a Labview program that controls shear distance and performs their difference. The same is done for the deformed state. As a result two images are obtained and named respectively reference image and deformed image. These two images are called by a Matlab program to process image data.

Mechanical conditions:

The Iosipescu mechanical set-up based on the EMSE fixture [START_REF] Pierron | design and experimental procedure[END_REF] is presented in Fig 2 .  Measurements are performed in the middle of the specimen (grid lines). On the movable jaw we imposed a vertical displacement. A classical load cell is used to control the load. The specimen has been loaded at 675 N. for this experiment; the sample width is 20 mm and its thickness 3 mm, the distance between the two clamps being 17.9 mm.

Experimental procedure

During the Iosipescu test, the surface strains of specimen induced by external loads have been digitised in the form of phase maps corresponding to the changes on the attached specimen. At each load step, eight phase difference maps for the combination between 4 directional illuminations and 2 applied shear directions have been determined. Ten intensity maps obtained by a phase stepping technique enable to calculate one phase map for each of the eight combinations. Subsequently, Matlab calculated the phase change maps for each combination between two different load steps. In this calculation, no fitting or filtering methods are used, thus spatial resolution remains maximum. Then, in-plane strains and out-of plane displacement derivatives have been analysed at each load step using Matlab. Finally, salt and pepper filtering was applied to in-plain strain maps and out-ofplane displacement derivative maps to increase the map visibility. In the end, all filtered images with physical information have a spatial resolution of about 1 mm. However, the original image before filtering keeps the spatial resolution of about 0.114 mm.

Results will be presented during the conference. Conclusion

This paper presents an original set-up for the direct measurement of strain map using quantitative DSPSI. Application to the Iosipescu shear test demonstrated the feasibility of the measurement. Further work will focus on strain map optimization and metrology.

Fig. 1 :

 1 Fig. 1 : DSPSI Set-up

Fig. 2 :

 2 Fig. 2 : Iosipescu Mechanical set-up


François Bonnet

Alessia Milani

Maria Potop-Butucaru

Sébastien Tixeuil

Asynchronous Exclusive Perpetual Grid Exploration without Sense of Direction

In this paper, we investigate the exclusive perpetual exploration of grid shaped networks using anonymous, oblivious and fully asynchronous robots. Our results hold for robots without sense of direction (i.e. they do not agree on a common North, nor do they agree on a common left and right ; furthermore, the "North" and "left" of each robot is decided by an adversary that schedules robots for execution, and may change between invocations of particular robots). We focus on the minimal number of robots that are necessary and sufficient to solve the problem in general grids. In more details, we prove that three deterministic robots are necessary and sufficient, provided that the size of the grid is n × m with 3 ≤ n ≤ m or n = 2 and m ≥ 4. Perhaps surprisingly, and unlike results for the exploration with stop problem (where grids are "easier" to explore and stop than rings with respect to the number of robots), exclusive perpetual exploration requires as many robots in the ring as in the grid. Furthermore, we propose a classification of configurations such that the space of configurations to be checked is drastically reduced. This pre-processing lays the bases for the automated verification of our algorithm for general grids as it permits to avoid combinatorial explosion.

Introduction

We consider a set of autonomous robots that have to collaborate to perpetually explore an area modeled as a grid graph. Each robot has to visit each vertex of the grid infinitely many times, with the additional constraint that no two robots may be present at the same vertex at the same time or may switch their positions by crossing the same edge. Introduced in [START_REF] Baldoni | On the solvability of anonymous partial grids exploration by mobile robots[END_REF], this problem is called the exclusive perpetual exploration.

Robots are endowed with visibility sensors and motion actuators and operate in cycles that comprise look, compute, and move phases. The look phase consists in taking a snapshot of the other robots positions using its visibility sensors. In the compute phase a robot computes a target destination based on the previous observation. The move phase consists in moving toward the computed destination using motion actuators. We consider an asynchronous scheduling model, i.e. a finite yet unbounded amount of time may elapse between any two phases of a robot's cycle.

The difficulty to solve the exclusive perpetual exploration on the grid, depends on the restricted robot capabilities and on their asynchronous behavior. In particular, robots are anonymous (they execute the same protocol and have no mean to distinguish themselves from other robots), oblivious (their memory is not persistent between cycles), and they have no sense of direction (i.e. they may not agree on a common direction or orientation in the grid as each local direction and orientation are chosen by an adversary and may change between cycles). Asynchrony makes the problem harder because robots have to coordinate their movements despite the fact that a robot can decide to move according to an old snapshot of the system and that different robots may be in different phases of their cycles at the same time.

The robots' positions in the grid is the only information that can be use to decide moving. In this context, the number of robots on the grid directly impacts on the ability to break initial symmetry and to provide a grid reference "milestone" to help robots in their exploration process. Observe that due to the mutual exclusion constraints on the vertices occupancy, we cannot exploit the usual approach [START_REF] Flocchini | Computing without communicating: Ring exploration by asynchronous oblivious robots[END_REF] of creating "towers" (having more than one robot on the same node) to construct a reference milestone in the graph to be explored.

Related work

While the vast majority of literature on coordinated distributed robots considers that those robots are evolving in a continuous two-dimensional Euclidean space and use visual sensors with perfect accuracy that permit to locate other robots with infinite precision, a recent trend was to shift from the classical continuous model to the discrete model. In the discrete model, space is partitioned into a finite number of locations. This setting is conveniently represented by a graph, where nodes represent locations that can be sensed, and where edges represent the possibility for a robot to move from one location to the other. Thus, the discrete model restricts both sensing and actuating capabilities of every robot. For each location, a robot is able to sense if the location is empty or if robots are positioned on it (instead of sensing the exact position of a robot). Also, a robot is not able to move from a position to another unless there is explicit indication to do so (i.e., the two locations are connected by an edge in the representing graph). The discrete model permits to simplify many robot protocols by reasoning on finite structures (i.e., graphs) rather than on infinite ones. However, as noted in most related papers [START_REF] Devismes | Optimal probabilistic ring exploration by asynchronous oblivious robots[END_REF][START_REF] Flocchini | Computing without communicating: Ring exploration by asynchronous oblivious robots[END_REF][START_REF] Flocchini | Remembering without memory: Tree exploration by asynchronous oblivious robots[END_REF][START_REF] Kamei | Asynchronous mobile robot gathering from symmetric configurations without global multiplicity detection[END_REF][START_REF] Klasing | Taking advantage of symmetries: Gathering of asynchronous oblivious robots on a ring[END_REF][START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF][START_REF] Lamani | Optimal deterministic ring exploration with oblivious asynchronous robots[END_REF], this simplicity comes with the cost of extra symmetry possibilities, especially when the authorized paths are also symmetric.

Assuming visibility capabilities, anonymous and oblivious robots, the three main problems that have been studied in the discrete robot model are gathering [START_REF] Kamei | Asynchronous mobile robot gathering from symmetric configurations without global multiplicity detection[END_REF][START_REF] Klasing | Taking advantage of symmetries: Gathering of asynchronous oblivious robots on a ring[END_REF][START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF] (all robots are requested to reach a single node, not known beforehand), exploration with stop [START_REF] Devismes | Optimal grid exploration by asynchronous oblivious robots[END_REF][START_REF] Devismes | Optimal probabilistic ring exploration by asynchronous oblivious robots[END_REF][START_REF] Flocchini | Computing without communicating: Ring exploration by asynchronous oblivious robots[END_REF][START_REF] Flocchini | Remembering without memory: Tree exploration by asynchronous oblivious robots[END_REF][START_REF] Lamani | Optimal deterministic ring exploration with oblivious asynchronous robots[END_REF] (all nodes must be visited by at least one robot, and eventually all robots must stop moving forever), and exclusive perpetual exploration [START_REF] Baldoni | On the solvability of anonymous partial grids exploration by mobile robots[END_REF][START_REF] Blin | Exclusive perpetual ring exploration without chirality[END_REF] (all nodes must be visited by all robots infinitely often, and no node or edge should be occupied by more than one robot at any time).

For the exploration with stop problem, the fact that robots need to stop after exploring all locations requires robots to "remember" how much of the graph was explored, i.e., be able to distinguish between various stages of the exploration process since robots have no persistent memory. As configurations can be distinguished only by robot positions, the main complexity measure is then the number of robots that are needed to explore a given graph. The vast number of symmetric situations induces a large number of required robots. For tree networks, [START_REF] Flocchini | Remembering without memory: Tree exploration by asynchronous oblivious robots[END_REF] shows that Ω(n) robots are necessary for most n-sized tree, and that sublinear robot complexity is possible only if the maximum degree of the tree is 3. In uniform rings, [START_REF] Flocchini | Computing without communicating: Ring exploration by asynchronous oblivious robots[END_REF] proves that the necessary and sufficient number of robots is Θ(log n), although it is required that the number k of robots and the size n of the ring are coprime. Note that both approaches are deterministic, i.e., if a robot is presented twice the same situation, its behavior is the same in both cases. In [START_REF] Devismes | Optimal exploration of small rings[END_REF][START_REF] Devismes | Optimal probabilistic ring exploration by asynchronous oblivious robots[END_REF], the authors propose to adopt a probabilistic approach to lift constraints and to obtain tighter bounds. They show that four identical probabilistic robots are necessary and sufficient to solve the exploration problem in any anonymous unoriented ring, also removing the coprime constraint between the number of robots and the ring size. The impossibility presented in [START_REF] Devismes | Optimal probabilistic ring exploration by asynchronous oblivious robots[END_REF] for three robots to explore a ring is for the semi-synchronous model and naturally extends to the asynchronous model. This impossibility result extends to four robots in the deterministic setting, while five robots are sufficient to explore and stop a ring deterministically [START_REF] Lamani | Optimal deterministic ring exploration with oblivious asynchronous robots[END_REF]. By contrast, it was recently pointed out that in the general case three robots are necessary and sufficient to explore an n × m grid-shaped network with m > 3 [START_REF] Devismes | Optimal grid exploration by asynchronous oblivious robots[END_REF].

So, with respect to the required number of robots to explore and stop a graph, grid exploration is easier that ring exploration.

Most related to our task is the exclusive perpetual exploration of anonymous graphs [START_REF] Baldoni | On the solvability of anonymous partial grids exploration by mobile robots[END_REF][START_REF] Blin | Exclusive perpetual ring exploration without chirality[END_REF]. Baldoni et al. [START_REF] Baldoni | On the solvability of anonymous partial grids exploration by mobile robots[END_REF] prove that the mutual exclusion constraint and the underlying graph structure drive an upper bound on the number of robots that can perpetually and exclusively explore a graph. They also provide a method to compute this upper bound for a given graph. In the same paper, they provide an algorithm to perpetually and exclusively explore any partial grid provided that the number of robots enables a solution. However, the considered scheduling model is synchronous and contrary to the vast majority of existing solutions in the literature [START_REF] Devismes | Optimal grid exploration by asynchronous oblivious robots[END_REF][START_REF] Devismes | Optimal probabilistic ring exploration by asynchronous oblivious robots[END_REF][START_REF] Flocchini | Computing without communicating: Ring exploration by asynchronous oblivious robots[END_REF][START_REF] Flocchini | Remembering without memory: Tree exploration by asynchronous oblivious robots[END_REF][START_REF] Kamei | Asynchronous mobile robot gathering from symmetric configurations without global multiplicity detection[END_REF][START_REF] Klasing | Taking advantage of symmetries: Gathering of asynchronous oblivious robots on a ring[END_REF][START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF][START_REF] Lamani | Optimal deterministic ring exploration with oblivious asynchronous robots[END_REF], robots have a strong sense of direction as they agree on the four basic directions: North, South, East, and West. This strong settings permits to break all cases of initial symmetry since a global total order can be inferred on the vertices of the graph. Finally, Blin et al. [START_REF] Blin | Exclusive perpetual ring exploration without chirality[END_REF] investigate exclusive perpetual exploration of an anonymous ring. Considering asynchronous scheduling and no sense of direction, they prove that three robots are necessary and sufficient to perpetually and exclusively explore a ring.

Our contribution First, we prove that three deterministic robots are necessary and sufficient, provided that the size of the grid is n × m with 3 ≤ n ≤ m or n = 2 and m ≥ 4. Perhaps surprisingly, and unlike results for the exploration with stop problem (where grids are "easier" to explore and stop than rings with respect to the number of robots), exclusive perpetual exploration requires as many robots in the ring and in the grid.

Second, we propose a general classification of all possible system configurations. Observing that in each symmetric configuration, deterministic robots act in the same manner, we consider a single representative configuration for each set of such symmetric configurations. Moreover, we classify representative configurations with respect to the positions of robots and their mobility constraints. Some configurations are more complex to manage than others, as several robots may be scheduled to move concurrently. Then, due to asynchrony one robot can move before the other, leading to a new unstable configuration where the second robot may move according to an old snapshot. We expect that our classification benefits protocol designers to ease the proving of exploration process and lays the basis of their automatic verification.

Model and Problem Specification

We consider a distributed system of k mobile robots that are scattered on an n×m grid graph where 2 ≤ n ≤ m. The grid is anonymous, i.e., there exists no labeling to distinguish nodes or edges. The robots are identical, i.e., they cannot be distinguished using their appearance and they execute the same protocol. Moreover, the robots are oblivious, i.e., they have no memory of their past actions, and they neither have a common North direction, nor a common chirality (handedness). Robots cannot explicitly communicate, but have the ability to sense their environment and see the position of the other robots.

Robots operate in three phase cycles: Look, Compute and Move. During the Look phase robots take a snapshot of the grid together with the robots. The collected information (position of the other robots in the egocentered view) are used in the compute phase in which robots decide to move or to stay idle. In the move phase, robots may move to one of their adjacent nodes computed in the previous phase.

The computational model we consider is the asynchronous CORDA model [START_REF] Flocchini | Arbitrary pattern formation by asynchronous, anonymous, oblivious robots[END_REF][START_REF] Prencipe | Instantaneous actions vs. full asynchronicity : Controlling and coordinating a set of autonomous mobile robots[END_REF] in a discrete setting. Thus, when a robot takes a snapshot of the grid, it sees the other robots on nodes only. On the other hand, the time between Look, Compute, and Move operations is finite but unbounded, and it is decided by the adversary for each action of each robot. Thus, because of the asynchrony, different robots can execute concurrently different phases (e.g., a robot can perform a look operation while another robot is moving), and a robot can use an outdated snapshot of the grid to compute where to move and whether to move. A configuration at a given time is defined by the positions of all robots at that time. We assume that initially every vertex of the grid contains at most one robot.

Exclusive Perpetual Exploration Problem

We study the Exclusive Perpetual Exploration problem introduced by Baldoni et al. [START_REF] Baldoni | On the solvability of anonymous partial grids exploration by mobile robots[END_REF] for the synchronous setting. We restate the problem for the asynchronous setting.

Definition 1 (Perpetual Exclusive Grid Exploration). For any grid G of size n × m and for any initial configuration where all robots are located on different vertices, an algorithm solves the perpetual exclusive grid exploration problem if it guarantees the following two properties:

-liveness Each robot visits each vertex in G infinitely often.

-no collision No two robots visit the same vertex or traverse the same edge at the same time.

Classification of configurations

The lack of a global orientation implies that many configurations are alike from a robot's point of view. Two configurations are indistinguishable if they are symmetric in the robots egocentered view (see Figure 1). However, when the grid is not square (that is, when n = m) robots can distinguish landscape and portrait orientation. In this paper, we suppose w.l.o.g. that all configurations are in a landscape orientation. Representative Configuration For notation purpose, we label each cell of a grid n × m with an integer in the set {0, . . . , nm -1} according to the left-to-right-top-to-bottom reading direction. This labeling is not available to the robots.

X X X X X X X X X
Given an n×m grid, any configuration involving three robots on different vertices is conveniently represented by a unique sorted sequence s = (s 1 , s 2 , s 3 ) where each s i ∈ {0, . . . , nm -1} is different and represents one of the cells occupied by the robots. The three configurations on Figure 1, for example, are respectively denoted by the sorted sequences [START_REF] Devismes | Optimal probabilistic ring exploration by asynchronous oblivious robots[END_REF][START_REF] Klasing | Taking advantage of symmetries: Gathering of asynchronous oblivious robots on a ring[END_REF][START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF], [START_REF] Blin | Exclusive perpetual ring exploration without chirality[END_REF][START_REF] Devismes | Optimal exploration of small rings[END_REF][START_REF] Devismes | Optimal probabilistic ring exploration by asynchronous oblivious robots[END_REF], and [START_REF] Flocchini | Computing without communicating: Ring exploration by asynchronous oblivious robots[END_REF][START_REF] Flocchini | Arbitrary pattern formation by asynchronous, anonymous, oblivious robots[END_REF][START_REF] Kamei | Asynchronous mobile robot gathering from symmetric configurations without global multiplicity detection[END_REF].

Since robots are identical, deterministic, and execute the same code, in every indistinguishable configuration, robots perform the same actions. In each set of indistinguishable configurations, we choose a representative.

Definition 2 (representative configuration).

Let G be a grid with left-to-right-top-to-bottom labeling, and any non-empty set I of indistinguishable configurations of G, we say that a configuration s ∈ I is the representative configuration of every configuration in I iff s is the smallest in I w.r.t. the lexicographic order, ≺. That is, there is no s ∈ I such that s ≺ s.

Considering Figure 1, the natural labeling is 0 1 2 3 4 5 6 7 8 9 1011 and X X X is the representative configuration, whose corresponding sorted sequence is (0, 1, 6), which is the smallest amongst all indistinguishable configurations. In the sequel, we consider only representative configurations that are thus simply called configurations.

Classes of configurations (for grids with 3 robots)

Given a particular configuration, we say that two robots are indistinguishable iff there is no deterministic way of distinguishing them. For example, in the second grid on Figure 2, the robots respectively located at cell 5 and cell 9 are indistinguishable. Formally, in a configuration C there are two indistinguishable robots iff C is axially symmetric and two robots are symmetric in this axial symmetry 4 . For the second grid on Figure 2, the axis of symmetry is the vertical line that goes through the middle of the third column. For the third grid on Figure 2, the axis of symmetry is the diagonal line that goes from top-left to bottom-right.

Breaking and avoiding symmetric configurations is crucial to guarantee both liveness and the absence of collisions. Thus, we classify the set of configurations into four classes, depending on the amount of symmetry (with respect to the three robots) and the move possibilities of robots:

1. Asymmetrical configuration: every robot is uniquely distinguishable. In this case, even an adversarial scheduling cannot lead to ambiguous situations. 2. Semi-symmetrical configuration: two robots have symmetrical views but the third. This third robot can break the symmetry, possibly in more than one step. 3. Semi-symmetrical blocked configuration: two robots are indistinguishable, the other robot cannot move, but the two indistinguishable robots can move, without violating the vertex mutual exclusion (the no collision property). These configurations are difficult to deal with, since there is no immediate way of breaking the symmetry. One can nevertheless observe that any algorithm solving the perpetual exclusive exploration problem has to enable the movement of the two indistinguishable robots (the third robot is blocked). 4. Symmetrical blocked configuration: no possible move. For any possible move, an adversarial scheduling can decide an activation order that would lead to a collision. From an algorithmic point of view, configurations of type 1 and 2 are ideal, while the configuration of type 4 is a dead-end. Thus, when designing an algorithm one should focus on configurations of type 3 which are the most complex to deal with. The complexity arises from the fact that the two indistinguishable robots may be scheduled to execute concurrently, but due to the asynchrony one robot may move first, bringing the system to a new configuration, while the second robot will move later and according to an old snapshot. This means that the system may transiently be in configurations of type 1 or 2 but having a robot move later because of a snapshot it took when in a configuration of type 3. The algorithm should be resilient to this unexpected movement.

X X X X X X X X X X X X
4 Algorithms for the Perpetual Grid Exploration

Impossibility results

Theorem 1. There is no algorithm that solves the perpetual exploration problem with one robot for any grid but the 1 × 1 and 1 × 2 grid, with two robots for any grid.

Proof. With one robot, since there are less configurations than the number of vertices, it is not possible to design a deterministic algorithm 5 .

With two robots, there exist symmetric configurations, e.g. robots on two corners. If the scheduler always activate simultaneously both robots, it is not possible to break the symmetry and thus robots cannot explore the grid; each robot will stay in its half-side of the grid.

Theorem 2. There is no algorithm that solves the perpetual exploration problem with three robots in the 2 × 2 grid or 2 × 3 grid.

Proof. In the grid of size 2 × 2 there is only one possible configuration with three robots and it is of type 4. Therefore, no move can be scheduled. Otherwise, robots would collide.

Consider then a grid size 2×3 and suppose there is an algorithm A that solves the problem from the initial configuration (0, 1, 2). From this configuration, A can only decide to move the central robot, or to move the two other robots (we can suppose that the scheduler will always activate both of them simultaneously). In both situations, the system arrives in the configuration (0, 2, 4) from which A needs to move the robot located on position 4, otherwise the system comes back to the initial configuration. It is important to notice that the scheduler decides if the moving robot moves to the left or to the right; in both cases the system arrives in the configuration (0, 2, 3) but the robot does not visit the same cell.

From the configuration (0, 2, 3), the algorithm A can only move (i) the robot located on position 2 to the left, or (ii) the robot on position 0 to the right; any other move will bring the system back to a previous configuration, that will create a perpetual loop which does not achieve the perpetual exploration. Let us consider only the case (i), the other case can be analyzed similarly. After the move, the system arrives in configuration (0, 1, 3) and the algorithm has only the choice to move the robot on position 3 to position 4 and then the same robot to position 5 and finally to position 3 to arrive in the previous configuration (0, 1, 3) from which the algorithm will repeat forever the same loop. During this loop, all the cells have been explored, but not by all robots; in particular the robot located on position 0 never moved.

It is important to notice that this impossibility comes from the ability of the scheduler to decide if the robot located on position 4 of configuration (0, 2, 4) moves to the right or left.

X X X X X X X X X X X X X X X X X X (0, 1, 2)
(0, 2, 4) (0, 2, 3) (0, 1, 3) (0, 1, 4) (0, 1, 5) Fig. 3. Some configurations for the 2 × 3 grid.

Decomposition in two sub-problems

The exclusive perpetual exploration problem as defined in Section 2 can be decomposed into two independent sub-problems. To complete the exclusive perpetual exploration, one needs to solve both problems. The first sub-problem is directly related to the perpetual exploration, while the second sub-problem deals with the transient period starting from the (arbitrary) initial configuration.

1. Find a sequence of asymmetrical configurations (i.e. configurations of type 1) such that when robots "execute" this sequence, each robot visits each cell. This sequence must start and end with the same configuration, and in each step of the sequence exactly one robot moves. 2. From any initial configuration, find an algorithm that allows robots to reach, in a finite number of steps, a configuration that belongs to the previous sequence. (It does not need to be the first one, since the sequence is a cycle.)

One can see the first sub-problem as a weaker version of the perpetual exploration problem when the initial configuration of robots is chosen by the algorithm.

Grid 3 × 3

Theorem 3. There exists an algorithm that solves the exclusive perpetual exploration with three robots starting from any initial configuration in the 3 × 3 grid.

Proof. Sub-problem 1 The Figure 4 describes how the perpetual exploration is executed. For each configuration, the blue robot represents the robot that is allowed to move in that configuration. After 4 moves, the initial configuration is reached again with a rotation of the grid by 90 • and a circular permutation of the positions of robots. In this process, one robot (the one initially on position 5) has visited the four colored cells. The union of this set of cells and the same sets of cells after rotations of 90 • , 180 • , and 270 • covers the entire grid. Thus after 12 iterations6 of this sequence (i.e. 48 moves) every robot has visited every cell of the grid. Sub-problem 2 There is no configuration of type 4 and exactly one of type 3. For all other configurations (i.e. configurations of type 2, there is no problem since an algorithm can deterministically select one robot and make it move to reach a configuration of type 1; for example from configuration (0, 1, 8), the system evolves to configuration (0, 1, 7). Figure 5 explains how the algorithm deals with the single configuration of type 3. The main problem lies in the fact that only the two indistinguishable robots can move but due to asynchrony, it is possible that (a) only one robot sees this configuration and moves (the other one never sees this configuration); the system arrives in (0, 1, 6), or (b) both robots see the configuration, compute their moves and then one robot moves; the system arrives in (0, 1, 6). The color red for the robot in position 1 means that the system is in the configuration where this robot has computed its move (phase look/compute) according to a previous configuration but has not yet accomplished its move (phase move). This is problematic because the system arrives in a configuration (0, 1, 6) where the robot located at position 0 is supposed to be the (only) robot to move (from our sequence of moves described in Figure 4). Thus from configuration (0, 1, 6), three cases are possible depending on the first moving robot:

X X X X X X X X X X X X X X X (0, 1, 5) (0, 1, 4) (0, 1, 7) (0, 1, 6) (1, 3, 6) = (0, 1, 5) Explored area
-The robot in 1 moves before the robot in 0 sees the current configuration. The system reaches (0, 2, 6). -The robot in 1 moves after the robot in 0 sees the current configuration. The system reaches (0, 2, 6) and then (0, 1, 8). -The robot in 0 sees the current configuration and moves before the robot in 1 moves. The system arrives in (0, 1, 5) and then (0, 1, 8).

In all cases, the system leaves the "bad" configuration (0, 1, 3) of type 3 and arrives, in at most three steps, in a configuration of type 1 or 2 without any "red" robot. The complete list of moves appears in Appendix A.

X X X X X X X X X X X X X X X X X X X X X (0, 1, 3) (0, 1 , 6) (0, 1, 6) (0, 2, 6) (0, 2, 6) (0, 1, 5) (0, 1, 8)
Fig. 5. From the configuration (0, 1, 3) of type 3 to a configuration of type 1 or 2.

Grids 2 × m with m ≥ 4

Theorem 4. There exists an algorithm that solves the exclusive perpetual exploration with three robots starting from any initial configuration in 2 × m grids, with m ≥ 4.

Proof. Sub-problem 1 One valid sequence is described informally on Figure 6 and the formal definition appears in Appendix B. After 2m moves, the system returns to the initial configuration with a circular permutation of the robot positions. In this process, one robot (the one initially in position 1) has visited all positions but 0 (Position 0 will be visited by this robot within the next 2m moves). Thus, after 3 iterations of this sequence (i.e. 3 × 2m moves), every robot has visited every cell of the grid. Sub-problem 2 There is no configuration of type 3 or 4. There exist configurations of type 2 only when m is odd; from these configurations it is easy to break the symmetry by moving the robot which is uniquely distinguishable. From any configuration of type 1, it is sufficient to move successively one robot to position 0, then one robot to position 1, then the last one in a position between m -1 and 2m -1. The total number of moves in this process is bounded by m + m + 1.

X X X X X X X X X X X X (0, 1, 5) (0, 2, 5) (0, 3, 5) (0, 4, 5) X X X X X X X X X X X X (1, 4, 5) = (0, 3, 9) (0, 1, 4) (0, 1, 9) (0, 1, 8) X X X X X X X X X (0, 1, 7) (0, 1 , 6) (0, 1, 5) Explored area
The complete list of moves appears in Appendix B.

Grids n × m with 3 ≤ n < m

Theorem 5. There exists an algorithm that solves the exclusive perpetual exploration with three robots starting from any initial configuration in n × m grids, with 3 ≤ n < m.

Proof. Sub-problem 1 One valid sequence is described informally on Figure 7 and formally in Appendix C. After (2n -2) × (m -3) + n + 1 + (n -3) + (m -2) + (n -1) + 1 moves, the configuration of the system returns to the initial configuration with a circular permutation of the three robots and a rotation of the grid by 180 • . Doing zigzag moves, one robot (the one initially located on position 2m -1) explores all the grid but the first line and the two first columns. Thus, after 6 iterations7 every robot has visited every vertex of the grid. Sub-problem 2 There exists no configuration of type 3 or 4. There exist configurations of type 2 only when m or n is odd; from these configurations it is easy to break the symmetry by moving the robot which is uniquely distinguishable. As for the previous case, we show that, for any configuration of type 1, it is possible to reach one configuration used during the perpetual exploration. It is sufficient to move successively one robot to the position 0, then one robot to the position 1 and finally one robot to the position (n -1)m to reach configuration C = (0, 1, (n -1)m). However, depending on the initial configuration, it may happen that, while executing these moves, the system reaches a configuration C used in the perpetual exploration phase; in that case, the sub-problem 2 is solved and robots start the perpetual exploration from this configuration C , without reaching C. Indeed, a move is already defined from C and it is not possible to define a different one for this phase since robots are oblivious. The total number of moves is grossly bounded by nm + nm + nm. The complete list of moves appears in Appendix C.

Grids n × n with n ≥ 4

Theorem 6. There exists an algorithm that solves the exclusive perpetual exploration with three robots starting from any initial configuration in n × n grids, with n ≥ 4.

Proof. Sub-problem 1 One valid sequence is described informally on Figure 8 and formally in Appendix D. After (2n -2) × (n -3) + n + 1 moves, the configuration of the system returns to the initial configuration with a rotation of the grid by 90 • and a circular permutation of the positions of robots. In this process, one robot (the one initially in 2n -1) has explored all the grid but the first line and the two first columns. Since n ≥ 4, after 12 iterations every robot has visited every vertex of the grid8 .

Sub-problem 2 In the transient phase, robots try to reach configuration C = (0, 1, (n -1)n) by successively moving one robot to position 0, then one to position 1, and finally the last one to position (n-1)n. There is however one main difference with the previous case: there exist symmetric configurations where the three robots are not on the same line/column, namely configurations (0, x, xn), with 1 ≤ x ≤ n -1 and in particular configuration (0, 1, n), which is of type 3. To deal with these "bad" initial configurations we need a special behavior that is described on Figure 9. Informally, we first move the robot located in 0 to break the symmetry 9 and then we move another robot away from the side of the grid, so that a bad configuration cannot be reached again when the system evolves towards the configuration (0, 1, (n -1)n). The total number of moves is grossly bounded by 4 + n 2 + n 2 + n 2 . The complete list of moves appears in Appendix D.

Conclusions and open problems

We proved that three robots are necessary and sufficient to solve the problem of the exclusive perpetual exploration of grids. Similarly to [START_REF] Baldoni | On the solvability of anonymous partial grids exploration by mobile robots[END_REF], it would be interesting to generalize our result to any partial grid. Of course, only partial grids that preserve symmetry patterns are to be considered, as asymmetric partial grids give a global sense of direction for free.

Studying the coordination of robots to solve basic tasks, such as exploration, in a distributed manner requires considering all possible reachable configurations. Our proposal for defining and classifying configurations considerably simplifies the design and verification of our algorithms. We believe it can be extended to address an arbitrary number of robots and be a first step in providing a complete framework to study coordination problems in mobile robots networks.

A Grid 3 × 3

Perpetual exploration (sub-problem 1):

• (0, 1, 4) → (0, 1, 7) • (0, 1, 5) → (0, 1, 4) • (0, 1, 6) → (1, 3, 6) = (0, 1, 5) • (0, 1, 7) → (0, 1, 6)
Transient phase (sub-problem 2): A "red" robot means that the robots has computed its next move (phase look/compute) in a previous configuration, but has executed it (phase move). Since there is no ambiguity, we do not need to pr

• (0, 1, 8) → (0, 1, 7) • (0, 1, 2) → (0, 2, 4) • (0, 2, 4) → (0, 2, 3) = (0, 1, 6) or (0, 2, 5) = (0, 1, 6) 10 • (0, 2, 6) → (1, 2, 6) = (0, 1, 8) or (2, 3, 6) = (0, 1, 8) 11 • (0, 2, 7) → (0, 2, 6) • (0, 4, 8) → (0, 1, 8) 12 • (0, 5, 7) → (1, 5, 7) = (1, 3, 5) or (3, 5, 7) = (1, 3, 5) 13 • (1, 3, 4) → (1, 3, 5) • (1, 3, 5) → (0, 3, 5) = (0, 1, 7) • (1, 4, 7) → (1, 3, 7) = (1, 3, 5) or (1, 5, 7) = (1, 3, 5) 14 • (0, 1, 3) → (0, 1, 6) or (0, 1, 6) • (0, 1, 6) → (0, 2, 6) or (1, 3, 6) = (0, 1, 5) or (0, 2, 6) • (0, 1, 5) → (0, 1, 8) • (0, 2, 6) → (2, 3, 6) = (0, 1, 8) C Grids n × m (with 3 ≤ n < m)
Perpetual exploration (sub-problem 1): The first, third, and fourth rules correspond to the zigzag moves executed by the robot which explores all the grid but the first line and the two first columns.

-Going "down"; ∀x ∈ {1, . . . , m -2} and ∀y ∈ {1, . . . , n -2}:

• (0, x, y × m + x + 1) → (0, x, (y + 1) × m + x + 1) -Going "left"; ∀x ∈ {2, . . . , m -2}:

• (0, x, (n -1) × m + x + 1) → (0, x -1, (n -1) × m + x + 1) -Going "up'; ∀x ∈ {2, . . . , m -2} and ∀y ∈ {1, . . . , n -2}:

• (0, x -1, (y + 1) × m + x + 1) → (0, x -1, y × m + x + 1) -Going "left"; ∀x ∈ {2, . . . , m -2}: • (0, x -1, m + x + 1) → (0, x -1, m + x) -End of the sequence: • (0, 1, (n -1) × m + 2) → (0, 1, (n -1) × m + 1) • (0, 1, (n -1) × m + 1) → (0, 1, (n -1) × m) • (0, 1, (n -1) × m) → (1, m, (n -1) × m) = (0, (n -2) × m, (n -1) × m + 1) • (0, x × m, (n -1) × m + 1) → (0, (x -1) × m, (n -1) × m + 1) ∀x ∈ {2, . . . , n -2} • (0, m, (n -1) × m + x) → (0, m, (n -1) × m + x + 1) ∀x ∈ {1, . . . , m -2} • (0, m, x × m -1) → (0, m, (x -1) × m -1) ∀x ∈ {3, . . . , n} • (0, m, 2m -1) → (0, m -1, m) • (0, m -1, m) → (1, m -1, m) = (0, m -2, 2m -1)
Transient phase (sub-problem 2): These moves are defined only for configurations that do not appear above. Indeed when the system arrives in one of the previous configurations, the transient phase is over and the perpetual exploration starts.

-Breaking the symmetry of configurations of type 3 that exist iif m or n is odd18 .

• If the three robots are in adjacent position, move the one which is in the middle to the top/bottom/right/left to break the alignment. • If the three robots are not in adjacent position, move the one which is distinguishable to the top/bottom/right/left to break the symmetry. -Moving one robot to position 0:

• (x, y, z) → (x -m, y, z) if x ≥ m • (x, y, z) → (x -1, y, z) if 1 ≤ x ≤ m -1 -Moving one robot to position 1:

• (0, y, z) → (0, y -m, z) if y ≥ m + 1 • (0, m, z) → (0, m + 1, z) if y = m • (0, y, z) → (0, y -1, z) if 2 ≤ y ≤ m -1 -Moving one robot to position (n -1)m:

• (0, 1, z) → (0, 1, z + m) if z ≤ (n -1)m • (0, 1, z) → (0, 1, z -1) if z ≥ (n -1)m + 1 D Grids n × n (with n ≥ 4)

Perpetual exploration (sub-problem 1): The first, third, and fourth rules correspond to the zigzag moves executed by the robot which explores all the grid but the first line and the two first columns.

-Going "down"; ∀x ∈ {1, . . . , n -2} and ∀y ∈ {1, . . . , n -2}:

• (0, x, y × n + x + 1) → (0, x, (y + 1) × n + x + 1) -Going "left"; ∀x ∈ {2, . . . , n -2}:

• (0, x, (n -1) × n + x + 1) → (0, x -1, (n -1) × n + x + 1) -Going "up'; ∀x ∈ {2, . . . , n -2} and ∀y ∈ {1, . . . , n -2}:

• (0, x -1, (y + 1) × n + x + 1) → (0, x -1, y × n + x + 1) -Going "left"; ∀x ∈ {2, . . . , n -2}:

• (0, x -1, n + x + 1) → (0, x -1, n + x) -End of the sequence ("left" twice, then "bottom" once):

• (0, 1, (n -1) × n + 2) → (0, 1, (n -1) × n + 1)

• (0, 1, (n -1) × n + 1) → (0, 1, (n -1) × n)

• (0, 1, (n -1) × n) → (1, n, (n -1) × n) = (0, n -2, 2n -1)

Transient phase (sub-problem 2): These moves are defined only for configurations that does not appear above. Indeed when the system arrives in one of the previous configurations, the transient phase is over and the perpetual exploration starts.

-Breaking the symmetry of symmetric configurations where robots are not aligned:

• (0, 1, n) → (0, 1, 2n) or (0, 1, 2n)

• (0, 1, 2n) → (0, 2, 2n) • (0, 1, 2n) → (0, 2, 2n) • (0, x, x × n) → (1, x, x × n) ∀x ∈ {2, . . . , n -1}

• (1, x, x × n) → (1, x, x × n + 1) ∀x ∈ {2, . . . , n -1} -Breaking the symmetry of symmetric configurations where robots are aligned:

• If the three robots are in adjacent position, move the one which is in the middle to the top/bottom/right/left to break the alignment. • If the three robots are not in adjacent position, move the one which is distinguishable to the top/bottom/right/left to break the symmetry. -Moving one robot to position 0:

• (x, y, z) → (x -n, y, z) if x ≥ n • (x, y, z) → (x -1, y, z) if 1 ≤ x ≤ n -119 -Moving one robot to position 1:

• (0, y, z) → (0, y -n, z) if y ≥ n + 120 • (0, y, z) → (0, y -1, z) if 2 ≤ y ≤ n -1 -Moving one robot to position (n -1)n:

• (0, 1, z) → (0, 1, z + n) if z ≤ (n -1)n • (0, 1, z) → (0, 1, z -1) if z ≥ (n -1)n + 1

Fig. 1 .

 1 Fig. 1. Three indistinguishable configurations on a 3 × 4 grid.

Fig. 2 .

 2 Fig. 2. The four types of configurations.

Fig. 4 .

 4 Fig. 4. Sequence that achieves the perpetual exploration for the 3 × 3 grid.

Fig. 6 .

 6 Fig. 6. Sequence for the perpetual exploration for 2 × m grids (m ≥ 4). Here m = 5.

If such an axis exists, it is necessarily the perpendicular bisector of the segment whose extremities are the two indistinguishable robots. The third robot lies on that axis.

One probabilistic robot can explore any grid using a simple random walk.

12 = 3positions×4orientations: It guarantees that each robot starts in position 5 for each of the four orientations of the grid.

6 = 3 positions × 2 orientations: It guarantees that each robot starts in position 2m -1 for each of the two orientations of the grid.

n ≥ 4 is necessary since for n = 3, the central vertex is never visited with this algorithm as "avoiding" the first line and the two first columns prevents robots to visit the central vertex.

Contrary to the 3×3 grid, configuration (0, 1, n) does not raise issues since configuration (0, 1, 2n) (reached after one move) does not belong to the set of configurations used during the perpetual exploration. From this configuration, we can decide to move the robot in position 2 to position 3, thus this robot executes the same move if it sees the previous configuration or the current configuration.

The robot on position 4 cannot distinguish the move to the position 3 or 5, but in both cases, the system arrives in the same configuration (0, 1, 6).

The robot on position 0 cannot distinguish the move to the position 1 or 3, but in both cases, the system arrives in the same configuration (0, 1, 8).

The robot on position 4 cannot distinguish the move to the position 1, 3, 5, or 7, but in all cases, the system arrives in the same configuration (0, 1, 8).

The robot on position 0 cannot distinguish the move to the position 1 or 3, but in both cases, the system arrives in the same configuration[START_REF] Baldoni | On the solvability of anonymous partial grids exploration by mobile robots[END_REF][START_REF] Devismes | Optimal exploration of small rings[END_REF][START_REF] Devismes | Optimal probabilistic ring exploration by asynchronous oblivious robots[END_REF].

The robot on position 4 cannot distinguish the move to the position 3 or 5, but in both cases, the system arrives in the same configuration[START_REF] Baldoni | On the solvability of anonymous partial grids exploration by mobile robots[END_REF][START_REF] Devismes | Optimal exploration of small rings[END_REF][START_REF] Devismes | Optimal probabilistic ring exploration by asynchronous oblivious robots[END_REF].

We do not give the rules in a formal notation, because there are many special cases that would require special notations. We think that it is more easily understandable with this informal notation. Since no other rule considers configuration of type 3 there is no multiple rules for the same configuration.

This rule does not apply for configurations (1, k, k × n) with 2 ≤ k ≤ n -1 since we already defined a specific rule before.

Note that y = n is not possible since it will be equivalent to a configuration (0, 1, -).

(1, 4, 5) = (0, 3, 9) Explored area Fig. 7. Sequence for the perpetual exploration of n × m grids. Here (n, m)

Explored area Fig. 8. Sequence for the perpetual exploration for n × n grids (n ≥ 4). Here n

Fig. 9. From the configurations (0, 1, n) and (0, x, xn) with 2 ≤ x ≤ n -1 .

B Grids 2 × m (with m ≥ 4)

Perpetual exploration (sub-problem 1):

-Going "right"; ∀x ∈ {1, . . . , m -2}:

Transient phase (sub-problem 2):

-Breaking the symmetry of configurations of type 2 that exist only if m is odd. Let define the middle position M = m 2 : 16 ∀x ∈ {0, . . . , M -1} -Reaching one configuration used in the perpetual exploration:

. . , m -1} and ∀y ∈ {x + 1, 2m -1} • (0, x, y) → (0, x -m, y) ∀x ∈ {m + 1, . . . , 2m -3} 17 and ∀y ∈ {x + 1, 2m -2}

• (x, y, z) → (x -1, y, z) ∀x, y, z such that it does not correspond to any other configuration (i.e. non-symmetric configurations with x ≥ 1).

Note that the last rule cannot create a symmetric configuration.

15 The robot on position M cannot distinguish the move to the position M -1 or M + 1, but in both cases, the system arrives in the same configuration (x, M -1, m -1 -x). 16 The robot on position M + m cannot distinguish the move to the position M + m -1 or M + m + 1, but in both cases, the system arrives in the same configuration (x, M + m -1, m -1 -x). 17 The case x = m is not considered because all configurations (0, m, y) are part of the perpetual exploration.


Rémi Flamary

Florian Yger

Alain Rakotomamonjy

Selecting from an infinite set of features in SVM

Dealing with the continuous parameters of a feature extraction method has always been a difficult task that is usually solved by cross-validation. In this paper, we propose an active set algorithm for selecting automatically these parameters in a SVM classification context. Our experiments on texture recognition and BCI signal classification show that optimizing the feature parameters in a continuous space while learning the decision function yields to better performances than using fixed parameters obtained from a grid sampling.

Introduction

The choice or the design of a kernel plays a primary role on the performance of a kernel machine such as an SVM or a KFDA. In order to overcome the difficulty that such a choice may bring, several recent works have investigated approaches for combining kernels. Multiple kernel learning (MKL) helps in designing kernels functions by jointly learning a decision function and a combination of bases kernel [START_REF] Lanckriet | Learning the kernel matrix with semi-definite programming[END_REF]. Another interesting point of MKL is that, when considered kernels have parameters, it can be used for model selection by including in the combination several instances of the same kernel but with different parameter values. This framework of MKL has been recently extended so as to handle an infinite number of kernels or kernels with continuous parameters [START_REF] Gehler | Let the kernel figure it out: Principled learning of preprocessing for kernel classifiers[END_REF].

In this work, we consider a specific case of the kernel method framework where feature maps are defined explicitly instead of being defined implicitly through the kernel function. There are many practical situations in which such a situation occurs. For instance, in face recognition problems, Gabor based features are extracted using filter convolutions [START_REF] Tan | Enhanced local texture feature sets for face recognition under difficult lighting conditions[END_REF]. The problem we address is thus the problem of automated selection of feature maps in a supervised learning framework using Support Vector Machines. We consider a situation where the feature maps involve some parameters (which can be continuous). In such a situation, the common approach is either to optimize the parameters by crossvalidation (if their number is relatively small) or to fix the parameter values beforehand. The latter strategy is for instance very common when extracting Gabor features where scale and frequency are sampled from predefined intervals.

We deal with this problem of feature map parameter selection by fitting the problem into the framework of feature selection through sparsity-inducing norm. The main particularity of our problem compared to classical ones [START_REF] Bradley | Feature selection via concave minimization and support vector machines[END_REF] is that the number of features we have to deal with can be potentially infinite since the feature parameters are continuous. In some ways, we follow recent works that learn from an infinite set of kernels [START_REF] Gehler | Let the kernel figure it out: Principled learning of preprocessing for kernel classifiers[END_REF]. However, by considering feature maps, we provide an optimization framework that consider the problem in its primal version from which we derive a simple and efficient active constraint algorithm. Furthermore, since the problem is still linear in the feature maps, we are able to deal with a large number of training examples. We show in our experiments on texture recognition and BCI electro-encephalogram signal classification that considering features with continuous parameters can yield to better classification performances than feature with sampled parameters.

Selecting from an infinite set of features

We detail in this section the algorithm we develop for dealing with an infinite set of features as well as examples of such infinite sets.

The algorithm

Let us formally define the framework of our problem. Consider a set of n training examples {x i , y i } n i=1 with the data x i belonging to some space X and the labels y i ∈ {-1, 1}. For instance, in a context of signal or image classification, X would respectively be R d or R d×d . We define a θ-parametrized function φ θ (•) that maps an element of X into X θ , this function being explicitly known. In this context, we are looking for a decision function of the form

f (x) = N j=1 w j , φ θj (x) X θ j (1)
that is able to predict most accurately as possible the label of a novel example x. Note that the decision function considers only a finite number N of feature maps each of which has a parameter value θ j . According to Bach et al. [START_REF] Bach | Multiple kernel learning, conic duality, and the SMO algorithm[END_REF], this decision function can be understood as a feature map version of a MKL one.

For performing feature selection, we want some of the w i to vanish. This can be enforced by a sparsity inducing norm while learning the weight vectors w i through the minimization of a regularized empirical risk.

Before delving into the details on how we deal with an infinite set of features, we first describe an efficient active set approach for addressing the finite number of features case. Let us define w the vector of stacked w j , Φ θj the matrix which rows i are φ θj (x i ) and Φ the matrix of feature maps, resulting from the concatenation of the N matrices {Φ θj }. Each column of Φ is normalized to unit norm and Φ = diag(y)Φ, with y being the vector of labels {y i }. We define w as the solution of the following learning problem where the loss function is a square hinge loss min w,b

J(w) = C 2n (1I -Φw) T + (1I -Φw) + + Ω(w) (2)
Algorithm 1 Active set method algorithm for SVM finite/infinite feature selection

1: Set A = ∅ initial active set 2: Set w = 0 3: repeat 4:
w ← solve problem (2) with features from A 5:

θ, i ← max i∈A c ||r i || 2 6: if θ > 1 then 7: A = A ∪ i 8:
end if 9: until θ ≤ 1 where [ Φw] i = f (x i ), 1I is a unitary vector, (•) + = max(0, .) is the element-wise positive part of a vector, Ω is a regularization term that induces sparsity and C is a trade-off parameter that balances training error and regularization. Typical sparsity inducing norms are the ℓ 1 norm defined as Ω 1 (w) = w 1 and the mixed ℓ 1-2 norm Ω 1,2 (w) = i w i 2 which induces sparsity on groups of features. The optimality condition of problem ( 2) is -C n Φ T (1I -Φw) + + c = 0 where c is a subgradient of the norm Ω. We focus in the sequel on the the mixednorm Ω 1,2 (w). By definition of the subgradient of the w i 2 norm and because Ω 1,2 (w) is group-separable, it can be shown that the optimality conditions are :

-r i + wi ||wi||2 = 0 ∀i w i = 0 ||r i || 2 ≤ 1 ∀i w i = 0 (3)
with r i = C n Φ T i (1I -Φw) + . These conditions suggest an active-set method for solving the unconstrained optimization problem. Indeed, since the problem is supposed to have a sparse solution, many w i are expected to be 0 at optimality. Then, in a block-coordinate descent approach, it seems reasonable to optimize on variables that violate their constraints while keeping the other fixed and repeat procedures as long as some w i violate their optimality constraints. Hence the algorithm runs as follows : at some given iteration, we have a subset A of features defined as the active ones and optimize the problem only over w A . At this point, depending on the value of r i , some of the w i that do belong to the complementary set A c may not satisfy their own optimality condition. Such a violating-constraint feature is added to the active set and optimization over A is repeated again until all w i satisfy their optimality conditions. Note that if several w i violate their constraints, the choice of the one to integrate to the active set impacts on the speed of convergence of the algorithm. While adding any violating feature or group of features into the active set leads to decrease the objective value, it is more appropriate to add the most violating one. This consists in solving the problem max i∈A c ||r i || 2 . The overall procedure is described in Algorithm 1.

When dealing with the infinite set φ θ of features, θ being a continuous parameter, we cast the problem as min |Θ|<∞ min w J(w) where Θ = {θ j } is the set of feature map parameter values involved in Φ and |Θ| is the cardinality of this set. This optimization problem searches for a finite number of features {φ θj } which achieves the lowest objective value of J(w). The optimality conditions of (3) can be readily extended to this infinite case as

-r i + wi ||wi||2 = 0 ∀i w i = 0 , ||r i || 2 ≤ 1 ∀i w i = 0 Φ T θs (1I -Φw) + 2 ≤ 1 ∀ θ s ∈ Θ (4)
Indeed, it is easy to show that if a feature Φ θs violates the third condition then adding that feature into the finite feature subset leads to a decrease of J(w) objective value. In the same way, adding a feature Φ θs which satisfies this third condition would not improve the objective value since it would get a zero weight.

From an algorithmic point of view, there is only one major difference when dealing with finite or infinite set of features. While in the former, it may be always possible to find the most violating constraint by sweeping all over them, in the latter case, finding this constraint is a difficult problem since we have to solve the maximization problem given Line 5 of Algorithm 1. Hence, the strategy we adopt consists in randomly sampling a given number of feature parameters {θ s }, so as to build a set of candidate features {Φ θs }, and then in adding to the finite set the one among those that violates the most its constraints. Similarly to the finite case, while not optimal this step always yields to a decrease in the objective value. Checking for the full optimality of the problem is also difficult since again one has to verify the third condition of Equation ( 4). In practice, we stop the algorithm when the maximal number of iterations is reached or when the sampling strategy does not return any violating feature.

Either in finite or infinite feature cases, solving Line 4 of the algorithm involves the resolution of problem (2) over the set of active features. Problem ( 2) is an unconstrained optimization problem where the loss function is differentiable with L-Lipschitz gradient and the mixed norm Ω 1,2 admits a simple and closed-form proximal operator. Hence, the problem nicely fits into the class of problem that can be solved efficiently through fast iterative shrinkage thresholding algorithm (FISTA) [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF] with some guarantee of convergence.

Examples of infinite set of features

There exists several feature extraction methods that need parameters tuning. In this paragraph, we review two of them that are of interest for our experimental analysis.

Gabor functions based features are typically features that need parameter tuning. Gabor features are usually built by convolving an image with a Gabor filter with angle ϕ, frequency f and Gaussian shape σ 1 , σ 2 as parameters. Unlike usual approaches, instead of fixing these parameters to some predefined values, our approach is able to select them automatically during the learning process.

In BCI application such as motor imagery signal discrimination task, a common feature extraction consists in extracting the Power Spectral Density in a frequency band. Usually the common choice is [8,30] Hz for a motor imagery task [START_REF] Lotte | Regularizing common spatial patterns to improve bci designs: Unified theory and new algorithms[END_REF] but the choice of these frequency bands might be seen as parameter tuning in a continuous space.

Experiments

We describe in this section some experiments that show that using infinite set of features may help improving performances by selecting the ones that are relevant. We consider two real-world applications on texture recognition and EEG signal classification for Brain-Computer Interface.

The texture recognition problem consists in classifying 16 × 16 patches extracted from two Brodatz textures D29 and D92. The Gabor features are obtained by computing the inner product of all Gabor functions located at some pre-defined location and the patch and then by summing the absolute value of the response. By doing so, we obtain features that are translation-invariant. When Gabor parameters are sampled, we have a number of features that depends on the number of samples used for each parameter ϕ,f , σ 1 and σ 2 . In order to be fair, in the infinite feature case, the number of sampled feature considered for the constraints violation checking problem (Line 5) is equal to the number of features used in the finite feature Gabor approach. We can see in Figure 1 that automatically selecting the relevant features from an infinite set leads to notable increase of performances.

The BCI dataset is the dataset IIa of the BCI competition IV. It consists of EEG signals of 9 subjects performing motor imagery. The signals have been acquired over 22 channels. In this study, we want to classify EEG trials of left/right hand motor imagery movement. For each class, we have 72 trials for learning and testing. For each trial, we have extracted the time segment from 0.5 to 2.5 seconds after the cue asking the subject to perform motor imagery. As a fixed feature, we have used the band-pass power over the [8, 30] Hz, while for our infinite feature algorithm, we allow slight modification of the band-pass filter since we randomly draw filter which band-pass size of at least 20 Hz included in [8, 30] Hz. By doing so, we hope that the classifier is able to adjust the most discriminant frequencies for each subject. In both cases, we perform CSP on the 1 and they show that the advantage of learning the filter cut-off frequencies. We should however note that allowing more flexibilities to these cut-off frequencies leads to overfitting.

Conclusion

In this work, we proposed an efficient algorithm for selecting from an infinite set of features. This approach allows the automated selection of features with continuous parameters. The optimization problem is handled by an active set algorithm. At each iteration, the algorithm adds to the active feature set a relevant feature which is determined according to the optimality conditions of the problem. The approach was tested on a texture recognition dataset and on a BCI motor imagery task providing empirical evidences that dealing with infinite set of features may enhance performances of learning algorithms. Finally, as the algorithm has linear complexity and may be parallelized, we intend in future works to test our approach on large-scale datasets.

Fig. 1 :

 1 Fig. 1: Examples of accuracy performance in the finite and infinite feature cases with different numbers of sampled features (left) 81. (right) 1296. For these experiments, C has been set to 10.

Table 1 :

 1 Classification accuracy on the test set for classical CSP approach, fixed and random bandpass filter for feature extraction on the BCI dataset. filtered EEG and include in the cross-validation stage the choice of the number of CSP filters and regularization parameter C. Results are summarized in Table

						Subjects
	Methods	S1	S2	S3	S4	S5	S6	S7	S8	S9	Avg
	CSP [7]	88.89 51.39 96.53 70.14 54.86 71.53 81.25 93.75 93.74 78.01
	Fixed	88.19 53.47 96.53 63.89 60.42 69.44 79.17 97.92 93.06 78.01
	Random 90.97 52.78 95.14 73.61 62.50 72.92 82.64 97.22 92.36 80.01

* This work is funded in part by the FP7-ICT Programme of the European Community, under the PASCAL2 Network of Excellence, ICT-216886 and by the French ANR Project ASAP ANR-09-EMER-001 and by the INRIA ARC MaBi project.