published or not. The documents may come

Learning motor dependent Crutchfield's information distance to anticipate changes in the topology of sensory body maps

Learning motor dependent Crutchfield's information distance to anticipate changes in the topology of sensory body maps

Thomas Schatz and Pierre-Yves Oudeyer

Abstract-What can a robot learn about the structure of its own body when he does not already know the semantics, the type and the position of its sensors and motors? Previous work has shown that an information theoretic approach, based on pairwise Crutchfield's information distance on sensorimotor channels, could allow to measure the informational topology of the set of sensors, i.e. reconstruct approximately the topology of the sensory body map. In this paper, we argue that the informational sensors topology changes with motor configurations in many robotic bodies, but yet, because measuring Crutchfield's distance is very time consuming, it is impossible to remeasure the body's topology for each novel motor configuration. Rather, a model should be learnt that allows the robot to predict Crutchfield's informational distances, and thus anticipate informational body maps, for novel motor configurations. We present experiments showing that learning motor dependent Crutchfield distances can indeed be achieved.

Index Terms-Crutchfield distance, information theory, sensorimotor learning, body map

THE DISCOVERY OF INFORMATIONAL TOPOLOGICAL BODY

MAPS

In developmental robotics [START_REF] Weng | Autonomous mental development by robots and animals[END_REF], one aims at building robot capable of learning progressively and continuously new skills in unknown changing bodies and environments. In particular, this involves mechanisms for discovering its own body and its relationships with the environment. In this context, learning body maps is a crucial challenge. Body maps are topological models of the relationships among body sensors and effectors, which human children learn progressively, abstract and build upon to learn higher-level skills involving the relationships between the shape of the body and the physical environment [START_REF] Gibson | The theory of affordances[END_REF]. Accordingly, inferring and re-using body maps from initially uninterpreted sensors and effectors has been identified as an important objective in developmental robotics [START_REF] Pierce | Map learning with uninterpreted sensors and effectors[END_REF].

Studies in developmental psychology [START_REF] Rochat | Self-perception and action in infancy[END_REF] showed that body babbling in infants, that is to say the systematic exploration of the consequences of their actions on their sensations, was an essential part in the building of a primary sense of bodily self. That sense being necessary to the ulterior development of complex sensorimotor abilities. Other studies in neuroscience and medical imaging unveiled the presence of sensoritopic and motor projections in the brain, i.e. neural circuits whose geometry reflects the topography of the different sensory and motor organs [START_REF] Kandel | Principles of Neural Science[END_REF]. [START_REF] Pierce | Map learning with uninterpreted sensors and effectors[END_REF] proposed an heuristics to allow an artificial system to build sensoritopic maps of its sensory organs Thomas Schatz is with ENS de Cachan -antenne de Bretagne Pierre-Yves Oudeyer is with INRIA Bordeaux -Sud-Ouest by exploring randomly its environment, i.e. by practicing a form of body babbling. This heuristics doesn't suppose any prior knowledge of the surrounding environment nor of the morphology of the system and its sensory and motor parts. It consists mainly in computing a metrics between the different sensory receptors from the series of successive values they take. [8] [9] then improved this heuristics, notably by using concepts from information theory in order to compute the Crutchfield information metrics between the different sensors. [START_REF] Kaplan | Information-theoretic framework for unsupervised activity classification[END_REF] computed the metrics while the system was performing a programmed activity (e.g. walking or dancing. . . ) instead of randomly moving. They made measures for different activities and then they used a clustering algorithm to associate automatically the measures of the metrics between each pair of sensors to the corresponding activity. The idea being to characterize an activity, robust to variations in the particular external conditions of the performance, by a set of values of the metrics recorded while the system performs the activity.

The work described in [START_REF] Pierce | Map learning with uninterpreted sensors and effectors[END_REF], [START_REF] Olsson | Sensory channel grouping and structure from uninterpreted sensor data[END_REF], [START_REF] Olsson | From unknown sensors and actuators to actions grounded in sensorimotor perceptions[END_REF] and, to a lesser extent, [START_REF] Kaplan | Information-theoretic framework for unsupervised activity classification[END_REF], is restricted by the fact that mean values of the metrics are computed without taking into account information characterizing motor commands and motor configurations. This boils down to assuming that the set of sensors of the body has a single fixed informational topology (or several discrete fixed topologies in the case of [START_REF] Kaplan | Information-theoretic framework for unsupervised activity classification[END_REF]), which is indeed the case in for the distance sensors of the Khepera robot or the pixel sensor matrices used as testbeds in these works. This is problematic since in many robot bodies, the informational topology of sensor will be dependant upon motor configurations: for example, the touch sensors in the fingers of two hands are informationally very close if the two hands are touching each other (double touch), but are informationally farther away if one hand is scratching the head (in which case the sensors in this hand will be informationally topologically close to the touch sensors of the head) and the other hand is freely hanging. Moreever, the number of possible motor configurations is generally very high (infinite with continuous actuators), and it is unpractical to measure Crutchfield metrics for each pair of sensors for each novel motor configuration. So it appears necessary to realize only a limited number of measures of Crutchfield metrics for certain motor configurations and to estimate from those the values of the metrics for other motor configurations. In what follows, we will first present and discuss in more details this previous work ( [10] [8] [START_REF] Olsson | From unknown sensors and actuators to actions grounded in sensorimotor perceptions[END_REF]), and then we will show how a learning algorithm can be used to anticipate the Crutchfield distance between pairs of sensors for novel motor configurations that modify the informational topology of these sensors.

I. INFERRING BODY MAPS FROM CRUTCHFIELD INFORMATIONAL METRICS

A. Introduction

We consider afterwards any system (e.g. a robot) possessing some sensors, which allow it to collect information about its state and its environment, some actuators, which allow it to change its state and to interact with its environment and a control system. The control system receives information from the sensors, then compute them to produce a command addressed to the actuators. Those information pass through real-valued communication channels. The control system can write on motor channels and read sensory channels. From the point of view of the different algorithms proposed in the studied works and of those proposed in this article, the system is a tabula rasa: the control system can only access the list of sensory channels and the list of motor channels, without any additional knowledge, such as the type, semantics or positions of the different sensory and motor parts.

Formally, the problem tackled in the presented works is to infer, from the sole knowledge of the values passing on the channels as time flows, a mathematical structure on the channel's set. The goal is to allow the system to structure automatically its perceptions and its actions. The inferred structure is a metrics on the set of the sensory channels for [START_REF] Pierce | Map learning with uninterpreted sensors and effectors[END_REF] and [START_REF] Olsson | Sensory channel grouping and structure from uninterpreted sensor data[END_REF], a metrics on a set of such metrics for [START_REF] Kaplan | Information-theoretic framework for unsupervised activity classification[END_REF], and a mapping from a value of the motor channels to a metrics on the set of the sensory channels in this article. Other structures may be possible. For instance, a number associated to each sensor/actuator pair, which would account for the correlation between the use of the actuator and the variation of the sensor's value. Those numbers could then be used to map the actuators on the sensoritopic maps. Then an oriented graph on the set of the motor channels, corresponding intuitively to the skeletton of the system, may be derived. These inferred structured may then be used to improve the computation of sensory information and the derivation of actuators' commands. For instance, [START_REF] Olsson | From unknown sensors and actuators to actions grounded in sensorimotor perceptions[END_REF] use the obtained sensoritopic maps to compute the optical flow through visual sensors with visual field of complex shapes.

B. Uniform binning and adaptive binning

Data received on a sensory channel are often more precise than desired, that is to say the information on the channel can take too many different values. It is then necessary to group certain classes of values. Pierce and Kuipers, for whom the sensory channels took their values in (a finite subset of) the interval [0; 1], used an uniform partition of this interval in order to be able to arbitrarily set the number of values a channel can take (uniform binning). For instance, if we set this number to 3: let

I 1 = [0; 1 3 [, I 2 = [ 1 3 ; 2 3 [ and I 3 = [ 2 3 ; 1], and let x 1 ∈ I 1 , x 2 ∈ I 2 et x 3 ∈ I 3 ,
then the value of the channel after binning for an initial value in I 1 would be x 1 , x 2 for an initial value in I 2 , etc. Notice that x i can be chosen arbitrarily in I i , as a matter of fact any symbol s i such as for all i, j we have i = j ⇒ s i = s j would fit, provided that the numerical properties of the channel's values are not used (as it is the case in [START_REF] Olsson | Sensory channel grouping and structure from uninterpreted sensor data[END_REF] et [START_REF] Olsson | From unknown sensors and actuators to actions grounded in sensorimotor perceptions[END_REF]).

A drawback of this approach is that if, for instance, only ten values are distinguished for a given canal whose values are in [0; 1] and if it always take its values between 0.2 and 0.3, the observed value for the system will always be the same and the sensor will be useless (it won't bring any information in the sense of information theory). [START_REF] Olsson | Sensory channel grouping and structure from uninterpreted sensor data[END_REF] proposed the use of adaptive binning rather than uniform binning. Adaptive binning allow an optimized use of the information provided by the sensors. The [0; 1] interval is then divided in such a way that the observed values on the sensory channels be dispatched as uniformly as possible in the different parts of the partition. This method maximizes the mean collected information for a partition of given size (in the sense of information theory). This is particularly useful for sensors whose characteristic isn't linear.

C. Creation of sensoritopic maps [START_REF] Pierce | Map learning with uninterpreted sensors and effectors[END_REF] proposed an heuristics to allow an artificial system to develop an approximative representation of the topography of its sensors relatively to a certain metrics, i.e. a sensoritopic map. This metrics is computed from the sole knowledge of the sequences of values taken by the sensor channels while the system moves randomly. The proposed algorithm was tested with a simulation of different robots in a simple environment. [START_REF] Olsson | Sensory channel grouping and structure from uninterpreted sensor data[END_REF] then introduced the concept of informational metrics (Crutchfield's metrics) and of adaptive binning in order to improve the algorithm. They tested the algorithm in simulation and on an AIBO robot.

There is three main steps in the heuristics. In a first step, a distance between each pair of sensors is measured, i.e. a positive real number, which grows bigger as the sensors are further apart. It doesn't have to be a metrics in the mathematical sense. In a second step, a well-fitted dimension for the sensoritopic map is computed. Eventually, the sensors are depicted by points in an euclidean space of that dimension, in such a way that the euclidean distance between two points be as close as possible to the distance between the two corresponding sensors.

Pierce and Kuipers consider sensory and motor channels with value in a uniform partition of [0; 1] of given size N . They propose two metrics on the set of sensory channels. For the first, two sensors are close if their values are close at any given time. Let s1 and s2 be two sensors, and (s 1 (1), s 1 (2)..., s 1 (T )), (s 2 (1), s 2 (2)..., s 2 (T )) the values taken by these sensors at T consecutive times, then:

d T (s 1 , s 2 ) = 1 T T t=1 |s 1 (t) -s 2 (t)|.
For the second, two sensors are close if they take each of their value with close frequency. Let s1 and s2 be two sensors and (s 1 (1), s 1 (2)..., s 1 (T )), (s 2 (1), s 2 (2)..., s 2 (T )) the values taken by these sensors at T consecutive times. Let (s f req

1 (1), s f req 1 (2)..., s f req 1 (N )) and
(s f req 2

(1), s f req 2

(2)..., s f req 2 (N )) be, where s f req i (f ) stands for the ratio of values taken by s i in the f th interval. Then:

d N,T (s 1 , s 2 ) = 1 2 N f =1 |s f req 1 (f ) -s f req 2 (f )|.
However, these metrics suffers several problems, notably they can't account for non-linear correlations between sensors, which are nonetheless very usual in the case of two sensors physically close, but of different modalities (e.g. cones and rod cells in the retina). Even an affine correlation won't be detected.

Olsson and al. introduced another metrics, originating from information theory: Crutchfield's metrics [START_REF] Crutchfield | Information and its metric. Nonlinear Structures in Physical Systems -Pattern formation[END_REF]. As a reminder, being given a random variable X of probability law p with values in E, X's Shannon entropy or mean information is:

H(X) = e∈E -p({X = e})log 2 (p({X = e})).
Being given a random vector (X, Y ) of probability law p with values in E × F , the conditional entropy of X knowing Y is:

H(X|Y ) = (e,f )∈E×F -p({(X, Y ) = (e, f )})log 2 ( p({(X, Y ) = (e, f )}) p({Y = f }) )
(See [START_REF] Cover | Elements of Information Theory[END_REF] for an in-depth presentation of information theory). Let s1 and s2 be two sensors, and (s 1 (1), s 1 (2)..., s 1 (T )), (s 2 (1), s 2 (2)..., s 2 (T )) the values taken by these sensors at T consecutive times. We consider this couple of time series as a T -sample of a random vector of dimension 2 (S 1 , S 2 ), S 1 and S 2 taking their values in finite sets. From the empiric probability law associated to the couple of samples, we then compute:

d T (s1, s2) = H T (S 1 |S 2 ) + H T (S 2 |S 1 ) H T (S 1 ) + H T (S 2 ) .
The only interest of the fraction's denominator is to normalize the metrics in [0; 1]. H T (S i |S j ) can be interpreted as the information brought in proper by S i , i.e. the information contained by S i , which isn't already in S j . So Crutchfield's metrics gives a measure of the quantity of information which isn't common to S i and S j , which is indeed a form of distance. Besides it's a pseudo-metrics in the mathematical sense, i.e:

• it's symetric: d T (S 1 , S 2 ) = d T (S 2 , S 1 ), • it's positive: d T (S 1 , S 2 ) ∈ R + ,
• it complies to triangular inequality:

d T (S 1 , S 3 ) ≤ d T (S 1 , S 2 ) + d T (S 2 , S 3 ).
It lacks the property of being defined to be a real metrics. Indeed it is possible to find S 1 , S 2 such as d T (S 1 , S 2 ) = 0 and S 1 = S 2 . However, it can be shown that Crutchfield's metrics between two random variables is zero if, and only if, they are two equivalent encoding of a same source. See [START_REF] Crutchfield | Information and its metric. Nonlinear Structures in Physical Systems -Pattern formation[END_REF] for proofs.

Once the metrics over the set of sensors is measured, [START_REF] Pierce | Map learning with uninterpreted sensors and effectors[END_REF] propose to determine a well-fitted dimension for the sensoritopic map with the metric scaling method: the distance Each pixel of the visual sensor is depicted by a number between 1 and 100. The infrared distance sensor is depicted by Ir, the accelerometers by Ba, La and Da, the temperature sensor by Te, the remaining power in the battery by P, the binary contact sensors of the paws by BLP, BRP, FLP and FRP, where FL means front right, BR back right, etc. Each paw has three degrees of freedom: E (elevation), R (rotation) et K (knee), for each degree of each paw there is a position sensor (for instance FLK for Front Left Knee) and a torque sensor, depicted in lower-case letters (for instance flk). The neck has three degrees of freedom too named tilt, pan and roll and so three position sensors NT, NP and NR and three torque sensors nt, np, nr. It's the same for the tail: TT, TP, TR, tt, tp, tr. At last the jaw has only one degree of freedom, and so only two sensors JAW and jaw. [After [START_REF] Olsson | Sensory channel grouping and structure from uninterpreted sensor data[END_REF]] between the pairs of sensors are represented by a square matrix (m i,j ) such as m i,j = d T (s i , s j ). This matrix is symetric real, so it's diagonalizable and it's eigenvalues are reals, let's call them λ 1 , λ 2 , ..., λ n , with λ 1 ≥ λ 2 ≥ ... ≥ λ n . We shall then be able to select information in a number of dimension more restricted than n while losing a minimum of information by retaining only the main eigenvalues. The selected dimension m is such that λ 2 m+1λ 2 m be maximal. Intuitively the selected dimension is such that there be the biggest possible difference between the quantity of information brought in by this dimension and the one brought in by a supplementary dimension. For a detailed presentation of principal component analysis, see [START_REF] Witten | Data Mining[END_REF].

Eventually, each sensor is depicted by a point in an euclidean space of dimension m, in such a way that the euclidean distance between two points coincide at best with the measured distance between the two corresponding sensors. There are numerous methods for this classic optimization problem, see [START_REF] Goodhill | Quantifying neighbourhood preservation in topographic mappings[END_REF]. One example of sensoritopic maps obtained by [START_REF] Olsson | Sensory channel grouping and structure from uninterpreted sensor data[END_REF] is given on figure 1.

II. AUTOMATED LEARNING OF CRUTCHFIELD'S METRICS

A. Introduction

In the work of [START_REF] Pierce | Map learning with uninterpreted sensors and effectors[END_REF] and [START_REF] Olsson | Sensory channel grouping and structure from uninterpreted sensor data[END_REF] the informational Crutchfield distance over all pairs of sensors was computed based on a series of sensor values measurements corresponding to randomly changing motor commands: this implicitly assumed that there was only one possible distance per pair of sensor, i.e. it assumed that the informational structure of the set of sensors was fixed. This is indeed the case in examples such as the distance sensors of Khepera robots or the pixel sensors of a camera. In [START_REF] Kaplan | Information-theoretic framework for unsupervised activity classification[END_REF]'s work, the motor commands changed according to one of several pre-defined activity: they identified the fact that a given motor activity or configuration, as well as a given dynamics of the environment itself, could modify the informational structure of a set of sensors. Yet, in their experiment, only a finite set of motor configurations was used and the pair wise Crutchfield metrics was computed for each configuration after many measurements of the sensor values. In most real robot bodies, a change in motor configuration will provoke a change in the informational structure of the set of sensors, and because with continuous motors there is an infinite (or very large) number of motor configurations, it is impossible to compute the Crutchfield metric for each of them. Rather, we argue that it is necessary that a model of Crutchfield distances, corresponding to all particular motor configurations, be learnt from a small finite set of really measured metrics, such that metrics for novel motor configurations can be accurately predicted. In the following, we will show that it is indeed possible to learn Crutchfield distances in motor dependant dynamically reconfigurable informational body maps.

B. Learning algorithm

A memory-based learning algorithm is chosen in this article, based on the use of a gaussian kernel on the k-nearest neighbours of a query point. Let a system with m motor channels be. From a database containing the distance obtained with Crutchfield's metrics between two sensors s 1 and s 2 of the system for n given motor command, a prediction of the distance between them for any command x is given by:

d s1,s2 (x) = k i=1 d s1,s2 (x i )e -||x-x i || 2 2 σ 2 k i=1 e -||x-x i || 2 2 σ 2
, where (x 1 , x 2 , .., x k ) are the k closest command to x in the database in the sense of the euclidean metrics on R m (with k n). The algorithm is parameterized by σ and k. A decrease in σ accelerate the decreasing of the influence of the k nearest neighbours on the prediction with the distance to the prediction point. See [START_REF] Mitchell | Machine Learning[END_REF] for more details on this algorithm. In the following experiments, optimal values of k and σ were chosen to maximize performances in generalizations (depending on the experiment, k is between 1 and 10).

C. Presentation of the simulation

To evaluate the performance of Crutchfield's metrics' automated learning, measures were made on different simulated systems. The simulated space is a plan. The bodies are made of rigid segments assembled together by pivot joints with a motor in each joint (cf. figure 2). Several types of sensors (distance, color, apparent angle and apparent diameter) can be placed on the segments. Figures 3, 4 and5 show the principles of distance, apparent angle and apparent diameter sensors respectively. The color sensor takes the value of the RGB encoding on 24 bits of the color of the nearest object present in its perceptive field. The environment is made of colored Fig. 2. Example of a body made of two segments. The segment in the bottom is linked to the ground by a pivot joint and the upper segment is linked to the segment in the bottom by another pivot joint. On this body, sensors can be attached at any place along the segments. There are four types of sensors, three of which are described in the following figures (the fourth one is a color sensor). These body are placed in an environment where colored disks move on a random path (see figure 6). disks of various radius moving in the plan. The movement of a disk is determined by two parameters, its speed and its instantaneous probability of changing its direction, the path of the disk being consequently a broken line (cf. figure 10). To preserve the simplicity of the model, collisions between the different elements in presence aren't taken into account. At any time it is possible to access the values of the sensors and to fixate the position of the joints.

D. Experiments and results

We ran experiments on four different simulated bodies illustrated on figure 7. The types of sensors on these bodies are randomly chosen (but fixed once chosen). Figure 8 summarizes the evolution of performances in predicting Crutchfield's information distance between the two sensors of each of the four bodies for various numbers of learning examplars. A learning examplar consists in an association between a random motor configuration and the associated Crutchfield metrics between the two sensors of the body computed directly with 100000 samples. For testing the learnt model of Crutchfield distances, we use a test database composed of 100 uniformly distributed motor configurations associated to the corresponding recomputed Crutchfield distances. Of course, the training and test databases are independant. As we can observe on figure 8, we see that the system is able to learn very efficiently to predict the Crutchfield distance between two sensors in all bodies and for motor configurations that were not encountered in the training database. This shows that a model of Crutchfield distances over the whole space of motor configuration has been efficiently learnt, and thus, reusing the body map reconstruction techniques presented in [START_REF] Kaplan | Information-theoretic framework for unsupervised activity classification[END_REF], [START_REF] Olsson | Sensory channel grouping and structure from uninterpreted sensor data[END_REF], could be used to dynamically anticipate informational sensory body maps when motor configurations are changing.

E. Discussion: Computational complexity and scalability

In the experiments presented above, 100000 measures were used for estimating the informational topology of a given motor configuration. This is a lot and may prevent the system to be applicable in realtime robotic experiments. Yet, on the one hand these measure can be done at a high-frequency without affecting the results, e.g. 100hz, if the sensori apparatus permits it, and we believe that accurate measures of informational distance can be realized with much less samples. This will be the topic of future experiments. Furthermore, it can be noted that increasing the number of sensors in the system would increase the complexity quadratically, since Crutchfield distances need only be measured, learnt and predicted pairwise to reconstruct the whole informational topology. As far as the motor space is concerned, increasing the number of degreesof-freedom to several dozens should not be problematic since mathematically, the regression performed here is quite similar to high-dimensional regression problems of robot motor learning adressed by techniques recently developped, such as LWPR [START_REF] Vijayakumar | Incremental online learning in high dimensions[END_REF]. 10. Comparison between the Crutchfield distances in the test database of body 3 with the corresponding predicted informational distances after 1024 learning examplars have been provided: one observes that the system predicts accurately the Crutchfield information distance among the two sensors for motor configurations that were not experimented beforehand. The sequence of examplars is generated in the same way than in the previous figure. The shape of the curve is not equivalent since rotations of the second effectors are not symmetric in relationship to rotations of the first effector.The peaks with low values correspond to motor configuration for which sensors perceive overlapping regions, and the peaks with values close to 1 correspond to motor configurations for which sensors perceive non-overlapping regions.

Fig. 1 .

 1 Fig. 1. Sensoritopic map of the AIBO robot with Crutchfield's metrics.Each pixel of the visual sensor is depicted by a number between 1 and 100. The infrared distance sensor is depicted by Ir, the accelerometers by Ba, La and Da, the temperature sensor by Te, the remaining power in the battery by P, the binary contact sensors of the paws by BLP, BRP, FLP and FRP, where FL means front right, BR back right, etc. Each paw has three degrees of freedom: E (elevation), R (rotation) et K (knee), for each degree of each paw there is a position sensor (for instance FLK for Front Left Knee) and a torque sensor, depicted in lower-case letters (for instance flk). The neck has three degrees of freedom too named tilt, pan and roll and so three position sensors NT, NP and NR and three torque sensors nt, np, nr. It's the same for the tail: TT, TP, TR, tt, tp, tr. At last the jaw has only one degree of freedom, and so only two sensors JAW and jaw. [After[START_REF] Olsson | Sensory channel grouping and structure from uninterpreted sensor data[END_REF]]

Fig. 3 .

 3 Fig. 3. Distance sensor. The location and orientation of the sensor are represented by the blue arrow. The perceived distance d correspond to the distance between the origin of the sensor and the nearest object of the environment within the perceptive field of the sensor (yellow-green area).

Fig. 4 .Fig. 5 .Fig. 6 .

 456 Fig. 4. Apparent angle sensor. The location and orientation of the sensor are represented by the blue arrow. Perceive the angle α under which is seen from the sensor the closest object of the environment within its perceptive field.

Fig. 7 .

 7 Fig. 7. Body 1 (with two rigid segments, two superposed joint and two sensors), Body 2 (with two chained rigid segments, two joints and two sensors), Body 3 (with two independant rigid segments, two joints and two sensors), Body 4 (with two independant chains of segments, four joints and two sensors)

  Figures 9 and 10 compares all Crutchfield distances in the test database with the corresponding distances predicted by the learnt model after 1024 learning examplars have been provided. This allows us to see that relatively to the global amplitude of the Crutchfield distance variations when motor configurations are varied, the prediction errors are low.

Fig. 8 .

 8 Fig.8. Evolution of mean squared errors in predicting Crutchfield's metrics between the two sensors of bodies 1, 2, 3 and 4 when various number of learning examplars are available (each learning examplar is an association between a random motor configuration and the associated measured Crutchfield informational distance) and with a test database composed of 100 motor configurations uniformly spread in the space of configurations.

Fig. 9 .

 9 Fig.9. Comparison between the Crutchfield distances in the test database of body 2 with the corresponding predicted informational distances after 1024 learning examplars have been provided: one observes that the system predicts accurately the Crutchfield information distance among the two sensors for motor configurations that were not experimented beforehand. The sequence of examplars is generated by fixing the position of the first effector, then rotating progressively the second effector around the clock, before rotating the first effector by adding it 2π 10 and rotating again the second effector around the clock, which is repeated until the first effector has itself rotated by 2π. The peaks where the Crutchfield distance is zero corresponds to motor configurations in which sensors superpose and perceive exactly the same thing.

Fig.

  Fig.10. Comparison between the Crutchfield distances in the test database of body 3 with the corresponding predicted informational distances after 1024 learning examplars have been provided: one observes that the system predicts accurately the Crutchfield information distance among the two sensors for motor configurations that were not experimented beforehand. The sequence of examplars is generated in the same way than in the previous figure. The shape of the curve is not equivalent since rotations of the second effectors are not symmetric in relationship to rotations of the first effector.The peaks with low values correspond to motor configuration for which sensors perceive overlapping regions, and the peaks with values close to 1 correspond to motor configurations for which sensors perceive non-overlapping regions.


Dobrina Boltcheva

Mariette Yvinec

Jean-Daniel Boissonnat

Mesh generation from 3D multi-material images ⋆

The problem of generating realistic computer models of objects represented by 3D segmented images is important in many biomedical applications. Labelled 3D images impose particular challenges for meshing algorithms because multi-material junctions form features such as surface pacthes, edges and corners which need to be preserved into the output mesh. In this paper, we propose a feature preserving Delaunay refinement algorithm which can be used to generate high-quality tetrahedral meshes from segmented images. The idea is to explicitly sample corners and edges from the input image and to constrain the Delaunay refinement algorithm to preserve these features in addition to the surface patches. Our experimental results on segmented medical images have shown that, within a few seconds, the algorithm outputs a tetrahedral mesh in which each material is represented as a consistent submesh without gaps and overlaps. The optimization property of the Delaunay triangulation makes these meshes suitable for the purpose of realistic visualization or finite element simulations.

Introduction

Motivation: Advanced medical techniques frequently require geometric representations of human organs rather than grey-level MRI or CT-scan images. The precondition for extracting geometry from a medical image is usually to segment it into multiple regions of interest (materials). This paper focuses on the next step: the automatic generation of meshes from 3D labelled images. These meshes are either surface meshes approximating the boundaries of anatomical structures or volume meshes of these objects.

The generation of geometric models from segmented images presents many challenges. In particular, the algorithm must handle arbitrary topology and multiple junctions. Multi-material junctions form surface patches (2-junctions), edges (1-junctions) and corners (0-junctions) which are expected to be accurately represented in the output mesh. However, it is still very challenging to construct a good mesh where each feature (surface patch, edge or corner) is accurately represented.

In this paper, we present a Delaunay refinement algorithm which addresses this issue. In a matter of seconds, the algorithm outputs a high-quality tetrahedral mesh where each anatomical structure is represented by a submesh with conforming boundaries.

Related work: There are only a few meshing strategies which directly provide volume meshes from multi-material images. Early grid-based methods deal with tetrahedral elements that are created from the original rectilinear volume subdivision [START_REF] Nielson | Computing the separating surface for segmented data[END_REF][START_REF] Hartmann | A fast algorithm for generating large tetrahedral 3d finite element meshes from magnetic resonance tomograms[END_REF]. More recently, an octree-based method has been proposed [START_REF] Zhang | Automatic 3d mesh generation for a domain with multiple materials[END_REF] that outputs tetrahedral or hexahedral meshes with consistent multi-material junctions. However, like the other grid-based methods, this algorithm does not offer a mesh quality control and elements of poor quality are always generated along boundaries. Quality improvement techniques are usually used as a postprocessing step to deliver acceptable meshes.

Another powerful strategy based on Delaunay refinement, has been proposed for meshing smooth surfaces [START_REF] Oudot | Meshing volumes bounded by smooth surfaces[END_REF] and volumes bounded by smooth and piecewise smooth surfaces [START_REF] Rineau | A generic software design for delaunay refinement meshing[END_REF][START_REF] Rineau | Meshing 3d domains bounded by piecewise smooth surfaces[END_REF]. The refinement process is controlled by highly customizable quality and size criteria on triangular facets and on tetrahedra. Pons et al. [START_REF] Pons | High-quality consistent meshing of multi-label datasets[END_REF] have adapted this mesh generation strategy to labelled images and have shown that the sizing criteria can be tissue-dependent leading to high-quality volume meshes of the different materials. However, in this work, 1-and 0-junctions are not explicitly handled and they are not accurately represented in the output mesh. It is well recognized that the presence of edges where different surface patches meet forming small angles, jeopardize the termination of Delaunay refinement in 3D [START_REF] Shewchuk | Mesh generation for domains with small angles[END_REF]. A recent method [START_REF] Cheng | Delaunay refinement for piecewise smooth complexes[END_REF] deals with this problem using the idea of protecting small angle regions with balls so that during the refinement no point is inserted into these protecting balls.

Very recently, Mayer et al. [START_REF] Meyer | Particle-based sampling and meshing of surfaces in multimaterial volumes[END_REF] proposed a sampling strategy for labelled images based on a dynamic particle system which explicitly samples corners, edges, and surface patches. The resulting set of well-distributed points is adapted to the underlying geometry of multi-material junctions. From these surface points, Delaunay-based meshing scheme outputs high-quality surface meshes. However, this sampling approach relies on heavy pre-processing computations and takes between 3 and 12 hours for small medical images.

Our contribution: In this paper, we propose a feature (edge and corner) preserving extension of the Delaunay refinement algorithm introduced by Pons et al. [START_REF] Pons | High-quality consistent meshing of multi-label datasets[END_REF]. The basic idea is to explicitly sample 1-and 0-junctions before launching the Delaunay refinement and to constrain the latter to preserve these features. The algorithm first extracts, from the input 3D image, all multi-material junctions where 3 or more materials meet. Then it samples and protects these junctions with protecting balls as in [START_REF] Cheng | Delaunay refinement for piecewise smooth complexes[END_REF]. The Delaunay refinement is then run using a weighted Delaunay triangulation, with the protecting balls as initial set of data points. This allows to preserve 0-junctions (corners) and to reconstruct accurately the 1-junctions (edges) with a sequence of mesh edges. In contrast to Mayer et al. [START_REF] Meyer | Particle-based sampling and meshing of surfaces in multimaterial volumes[END_REF], we sample only 0-and 1-junctions and not the 2-junctions which are meshed by the Delaunay refinement algorithm according to user-given quality and sizing criteria. Our multi-material junction detection and sampling algorithm is very fast and has little influence on the computation time of the Delaunay refinement algorithm.

The remainder of this paper is organized as follows: Section 2 gives a brief background and recalls the Delaunay refinement algorithm. Our multi-material junction detecting and protecting strategy is presented in Section 3. Section 4 reports some results and numerical experiments which demonstrate the effectiveness of our approach for segmented medical 3D images.

Delaunay refinement mesh generation from 3D images

The method is related to the concept of restricted Delaunay triangulation, borrowed from computational geometry. Background: Let E = {p 0 , ..., p n } be a set of points in R 3 called sites hereafter. The Voronoi cell, denoted Vor(p i ), associated to the site p i is the locus of points that are closer to p i than to any other site in E. The Voronoi diagram of E, denoted Vor(E), is the partition of space induced by the Voronoi cells Vor(p i ).

The Delaunay complex is the dual of the Voronoi diagram defined as follows: for esch subset of sites T ⊂ E, the convex hull conv(T ) is a cell of the Delaunay complex if and only if the intersection ∩ p∈T (V or(p)) of the Voronoi cells of sites in T is non empty. When the set E is in general position, i.e. there are no 5 sites lying on the same sphere, the Delaunay complex is a simplical complex called the Delaunay triangulation of E, denoted Del(E).

Let us now consider a subset Ω ⊂ R 3 and a set of points E. We call Delaunay triangulation of E restricted to Ω, and denote Del(E)|Ω, the subcomplex of Del(E) composed of Delaunay simplices whose dual Voronoi faces intersect Ω. Fig. 1 gives an example of these notions in 2D.

Let us consider a multi-material 3D image I as a function F : Z 3 → J, where J = {0, ..., n} is a set of labels where 0 represents the background and 1...n the other materials. Each label i defines a characteristic function f i : Z 3 → {0, 1} such as f i (p) = 1 iff F (p) = i and 0 otherwise. Let fi : R 3 → {0, 1} be the trilinear interpolation of f i . Then we define the extension F : R 3 → J of the image function F , as follows: F (p) = i iff fi (p) = max j∈J { fj (p)}. F defines a partition of the domain to be meshed Ω = ∪ i =0 Ω i , where

Ω i = F -1 (i), i ∈ J.
We call B i the boundary of Ω i and B = ∪B i denotes the locus of multi-material junctions including surface patches, edges and corners.

The Delaunay refinement meshing algorithm presented in the next section samples a set of points E ∈ R 3 and builds the Delaunay triangulation of E restricted to Ω. The algorithm outputs Del(E)|Ω=∪ i∈J,i =0 Del(E)|Ω i where Del(E)|Ω i is the set of tetrahedra whose circumcentres are contained in Ω i . In other words, each tetrahedron is labelled according to the material in which its circumcentre lies. We call boundary facets the facets incident to two tetrahedra with different labels. These boundary facets form a watertight non-manifold surface mesh that approximates surface patches where two material meet.

Delaunay refinement algorithm:

The algorithm starts by sampling a small initial set of points E on ∪B i . Three points per connected component of ∪B i are sufficient. Next it calculates the Delaunay triangulation Del(E) and its restrictions Del(E)|Ω i and the boundary fecets. This initial approximation is then refined until it meets the following user-given quality criteria for boundary facets and tetrahedra:

criteria for boundary facets: minimum angle α; maximum edge length l; maximum distance between a facet and the surface patch d;

criteria for tetrahedra: ratio between tetrahedron cirumradius and shortest edge length β; maximum edge length L.

Thus, the mesh refinement criteria are given by the 5-uplet (α, l, d, β, L). A bad element is an element that does not fulfil criteria. Bad facets are removed from the mesh by inserting their surface centres. The surface centre of a boundary facet is the point of intersection between its dual Voronoi edge and a surface patch.

Bad tetrahedra are removed from the mesh by inserting their circumcentres. The algorithm inserts refinement points one by one and maintains the current set E, Del(E), Del(E)|Ω and boundary facets. The refinement procedure is iterated until there is no bad element left.

After the refinement, degenerated tetrahedra with small dihedral angles (slivers) are removed from the mesh using a sliver exudation algorithm [START_REF] Cheng | Sliver exudation[END_REF].

It is proven in [START_REF] Rineau | Meshing 3d domains bounded by piecewise smooth surfaces[END_REF] that for appropriate choices of refinement criteria, the algorithm terminates. It delivers surface and volume meshes which form a good approximation of the image partition as soon as E is a "sufficiently dense" sample of its boundaries and volumes. However, 0-and 1-junctions are not handled explicitly and they are poorly reconstructed in the output mesh. As shown on Fig. 2(1) the 1-junctions are zigzagging and the 0-junctions are not preserved.

Feature preserving extension

In order to constrain the Delaunay refinement algorithm to mesh properly 0and 1-junctions, firstly we need to extract these junctions from the input image.

Multi-material junction extraction:

Here, we extend the image function F : Z 3 → J into a function F : R 3 → J using the the concept of continuous analog, borrowed from digital geometry and topology [START_REF] Latecki | 3d well-composed pictures[END_REF][START_REF] Françon | Topological 3d-manifolds : a statistical study of the cells[END_REF]. Following this concept, for any point p ∈ R 3 , F (p) = F (p i ), where p i is the point of Z 3 closest to p. As before, this function F defines a partition of the domain to be meshed Ω = ∪ i =0 Ω i but now Ω i = F -1 (i), i ∈ J is a set of cubic voxels with the same label. As before, B = ∪B i denotes the multi-material junctions which are composed of:

-2-junctions S (surface patches composed of voxel faces) which correspond to the intersection of exactly 2 materials;

-1-junctions L (composed of voxel edges) which are defined at the intersection of exactly 3 or 4 materials;

-0-junctions P (defined by voxel vertices) which correspond to the intersection of 4 or more materials (at maximum 8).

As it has been stressed before, our multi-material junction extraction algorithm delivers only 0-and 1-junctions because the Delaunay refinement algorithm handles surface patches well. The result is a 1D cellular complex composed of edges {L i } and their end points {P i }. Fig. 2(2) shows the 1D complex obtained for the multi-material sphere which is composed of five edges and two corners.

Protecting multi-material junctions: It is well known that neighbourhoods of edges and corners are regions of potential problems for Delaunay refinement algorithm. First, as we have already seen, the usual Delaunay refinement does not reconstruct these sharp features accurately. Secondly, if we constrain these edges to appear in the mesh and if the surface patches incident to them make small dihedral angles, the usual Delaunay refinement may not terminate. However, Cheng et al. [START_REF] Cheng | Delaunay refinement for piecewise smooth complexes[END_REF] have shown that if the edges are protected with protecting balls the Delaunay refinement terminates.

In this work, we protect 0-and 1-junctions with balls before launching the mesh refinement. We first keep all corners in {P i } and then we sample points on edges {L i } according to some user-specified density (see Fig. 2(3)). This distance d between two sampled points should be at most the maximum edge length parameter for facets l. We protect each sampled point p ∈ L i with a ball b = (p, r) where r = 2/3 * d (see Fig. 2(4)). The protecting balls have to satisfy the following properties:

each edge L i is completely recovered by the protecting balls of its samples any two adjacent balls on a given edge L i overlap significantly without containing each other's centres any two balls on different edges L i and L j do not intersect no three balls have a common intersection After the sampling and protection step, we use the previous Delaunay refinement algorithm as follows: Each protecting ball b = (p, r) is turned into a weighted point (p, r) and inserted into the initial set of points E. The Delaunay triangulation is turned into a weighted Delaunay triangulation where the Euclidean distance is replaced by the weighted distance. The weighted distance from a point x ∈ R 3 to a weighted point (p, r) is defined as ||x -p|| 2 -r 2 . All the other points inserted during the refinement are considered as points of weight zero.

The protecting balls and the weighted Delaunay triangulation guarantee two important properties. First, the segment between two adjacent points on any protected edge L i remains connected with restricted Delaunay edges (see Fig. 2(5)). Secondly, since the algorithm will never try to insert a refinement point into the union of protecting ball, its termination is guaranteed (see [START_REF] Cheng | Delaunay refinement for piecewise smooth complexes[END_REF] for more detail).

In practice, when a multi-material 3D image is the input, the algorithm outputs high-quality tetrahedral meshes of different materials which are consistent with each other. In particular, 1-junctions are properly reconstructed with edges whose vertices lie on these junctions (see Fig. 2(5)).

Results and Conclusion

The Delaunay refinement algorithm and its feature preserving extension have been implemented upon robust primitives to compute the Delaunay triangulation provided by the CGAL library [START_REF]CGAL: Computational Geometry Algorithms Library 15[END_REF]. We have tested our meshing algorithm on synthetic labelled images and on segmented medical images provided by IRCAD [15]. Figure 3 shows the meshes generated from two labelled liver datasets by the Delaunay refinement strategy with and without the feature preserving extension. Figure 3(a) displays the mesh of a liver adjacent to a right kidney and the 1-junction produced at the intersection of these two objects and the background. In this case, the 1-junction is a simple closed curve which has been protected with balls of radius 6mm. Figure 3(b) shows the mesh of a liver which has been cut into 4 anatomical regions. There are 8 1-junctions and 4 0-junctions produced at the intersection of these anatomical regions which have been protected with balls of radius 3mm.

Table 1 lists the quantitative results for these two liver images and the multimaterial sphere on Fig. 2. The refinement criteria for Delaunay refinement are given as the 5-uplet (α, l, d, β, L) defined in section 2. Note that our edge extraction and protection algorithm takes few seconds and does not penalize the Delaunay refinement which also has a reasonable computation time. A typical liver image (512×512×112) segmented into 4 different materials is meshed with target edge length of 10mm in less than half a minute.

In conclusion, we have proposed a feature preserving Delaunay refinement meshing strategy to generate conforming 3D meshes from labelled images. These meshes are targeted towards applications in the finite element methods which require conforming multi-material junctions to avoid instabilities and errors during the simulation. 1. Quantitative results and parameters for three different 3D images. The α in the refinement criteria is given in degree and l, d and L are given in mm. The four last raws give the computation times of different algorithm steps in seconds.

Fig. 1 .

 1 Fig. 1. (a) A set of points in the plane and its Voronoi diagram. (b) The dual Delaunay triangulation. (c) The Delaunay triangulation restricted to the blue curve is plotted with a black line. (d) The Delaunay triangulation restricted to the yellow region is composed of triangles whose circumcentres are inside the region.

Fig. 2 .

 2 Fig. 2. (1) Delaunay refinement 3D mesh. (2) Multimaterial junctions: five 1-junctions and two 0-junctions. (3) Sampled points on junctions. (4) Protecting balls. (5) Edge preserving Delaunay refinement 3D mesh. (6) A cut of the tetrahedral mesh. (7) Dihedral angles distribution.

Fig. 3 .

 3 Fig. 3. Meshes generated from labelled liver images: (a) A liver adjacent to a right kidney and a zoom on their edge. (b) A liver segmented into 4 anatomical regions and a zoom on one of the corners. The first raw shows meshes obtained with the usual Delaunay refinement. The second raw shows meshes resulting from our feature preserving extension and histograms of their dihedral angles distributions.

⋆ This research was supported by the FOCUS K3D Coordination Action, EU Contract ICT-2007.4.2 contract number 214993


Des Commande

Electriques Systemes

Jing Dai

Phulpin Yannick

Ernst Damien°

APPRENTISSAGE PAR RENFORCEMENT APPLIQUE A LA

Keywords: Apprentissage par renforcement, Systèmes électriques, Réseaux, Commande

Cet article propose une revue de littérature concernant les applications de l'apprentissage par renforcement à la commande des systèmes électriques. L'apprentissage par renforcement a pour caractéristique principale de résoudre des problèmes de commande optimale à partir de la seule observation des trajectoires du système. Il présente l'intérêt de ne pas requérir de connaissance à priori sur la dynamique du système à commander et convient ainsi aux problèmes de commande des systèmes complexes. Dans un premier temps, l'article détaille les caractéristiques des problèmes auxquels l'apprentissage par renforcement s'applique, puis cette technique est décrite. Ensuite, deux exemples classiques d'application aux systèmes électriques sont présentés.

Dans un contexte global de mutation des systèmes électriques, la commande de leurs différents éléments représente un enjeu de taille. En effet, il est d'autant plus difficile de déterminer des lois de commande performantes et robustes que les systèmes électriques sont des systèmes complexes : ils sont difficiles à modéliser du fait du grand nombre d'éléments interconnectés qui ont un comportement généralement non-linéaire et parfois discontinu, et ils sont sujets à des variations soudaines [START_REF] Damien° | Agent-based control systems: Why are they suited to engineering complex systems?[END_REF]. Les enjeux techniques associés aux systèmes électriques ont rapidement requis la mise en oeuvre de schémas de commande afin de s'assurer de l'alimentation permanente des charges [START_REF] Bouneau | Les Réseaux Electriques au Coeur de la Civilisation Industrielle[END_REF]. Ceux-ci ont généralement été synthétisés de manière empirique avant de s'orienter vers des schémas de commande basés sur modèles physiques. Or la modélisation des éléments d'un réseau implique une simplification qui peut nuire, dans le cas d'un système complexe, à la performance du système. Par exemple, pour modéliser un dispositif muni d'électronique de puissance, il est courant d'utiliser un modèle moyen de ses convertisseurs au risque de négliger certaines discontinuités qui pourraient avoir un impact sur le système [START_REF] Usman Iftikhar | A control strategy to stabilize PWM DC-DC converters with input filters using state-feedback and pole-placement[END_REF]. Il est donc nécessaire que les lois de commande soient suffisamment robustes face aux erreurs introduites lors de la modélisation.

Alors que l'interconnexion progressive des systèmes électriques et la diversification des éléments qui y sont connectés atteignent un stade qui pourrait mettre en cause les modes de commande de ces systèmes [START_REF] Bialek | Why has it happen again ? Comparison between the UCTE blackout in 2006 and the blackouts of 2003[END_REF], cet article propose de s'interroger sur le potentiel de nouveaux outils de commande basés sur une modélisation du système indépendante des niveaux physiques. Cette technique nommée apprentissage par renforcement (on utilisera dans cet article l'abréviation RL pour reinforcement learning) a pour but d'optimiser itérativement les lois de commande du système en vue de maximiser un indice de performance cumulée à long terme [START_REF] Sutton R | Reinforcement Learning: An Introduction[END_REF]. Cela revient à apprendre certaines caractéristiques macroscopiques du système en interagissant avec celui-ci, puis prendre des décisions en fonction de son état actuel. L'apprentissage par renforcement a déjà été appliqué avec succès aux systèmes électriques [START_REF] Glavic | Power systems stability control: reinforcement learning framework[END_REF][START_REF] Imathias | A reinforcement learning approach to automatic generation control[END_REF][START_REF] Glavic | Learning versus model predictive control: a comparison on a power system problem[END_REF] ainsi que dans d'autres domaines tels que par exemple la robotique [START_REF] Hafner | Neural reinforcement learning controllers for a real robot application[END_REF], la médecine [START_REF] Murphy | Optimal dynamic treatment regimes[END_REF] ou encore les télécommunications [START_REF] Singh | Reinforcement learning for dynamic channel allocation in cellular telephone systems[END_REF]. Dans cet article, nous allons donner un aperçu général des bénéfices potentiels de son application aux systèmes électriques.

L'article est organisé comme suit. Dans un premier temps, nous allons formaliser certains types de problèmes qui peuvent être traités par apprentissage par renforcement. Puis, le principe de fonctionnement de cette méthode sera présenté. Ensuite, deux exemples classiques d'application de RL à la commande des systèmes électriques seront détaillés. Enfin, la conclusion fournira quelques commentaires sur la performance de cette approche et sur les nouvelles applications envisagées. ) , (

Problèmes de commande optimale pour des systèmes à temps discret

1 t t t u x f x = + . (1)
A tout instant t , la performance du système est représentée par une récompense immédiate t r , qui peut être déterminée comme suit:

) , (

t t t u x r ρ = . ( 2
)
Si l'on considère un état de départ 0

x et une séquence d'actions de commande ) ,..., , (

1 1 0 - = T u u u u
sur un horizon de temps T , on peut effectuer une somme pondérée des indices de performances du système de sorte à déterminer une performance cumulée:

∑ - = = 1 0 0 ) ( T t t t u T r x J γ , (3)
où γ est le facteur de dévaluation qui permet de prendre en compte les récompenses à plus ou moins loin long terme.

Dans ce contexte, la stratégie de commande à mettre en place doit mener à une séquence de d'actions de commande optimale

) ,..., , ( * 1 * 1 * 0 * - = T u u u u telle que: ) ( max 0 * x J u u T u ∈ . (4)

Description générale de l'approche RL

L'approche RL est dite « agent-based ». Elle suppose en fait qu'un agent intelligent, qui ignore les fonctions f et ρ , est capable d'observer l'état du système t x et la valeur de l'indice de performance t r et détermine la valeur de t u à tout instant t .

On peut identifier deux grandes familles de techniques en RL: celles qui apprennent un modèle et puis utilisent ce modèle pour en déduire une loi de commande (quasi-)optimale et celles qui déterminent une loi de commande (quasi-) optimale sans passer par l'apprentissage d'un modèle. Dans cet article, nous nous intéressons aux techniques d'apprentissage par renforcement qui ne nécessitent pas de devoir apprendre un modèle. Souvent, ces techniques reposent sur le calcul d'une fonction de valeur (nommée fonction V ) qui dépend de l'état initial du système. Elle représente la performance cumulée maximale que l'on peut obtenir si le système évolue à partir de cet état initial en étant soumis à une séquence d'actions de commande optimale. Alternativement, on peut aussi définir cette fonction de valeur pour chaque paire état-action ) , ( u x (nommée fonction Q dans ce cas) qui représente la performance cumulée maximale que l'on peut obtenir quand on applique cette action à partir de cet état initial et que le système reçoit une commande optimale par la suite. L'agent intelligent cherche à estimer cette fonction de valeur en interagissant avec le système. Après une période d'entraînement, on considère qu'il en a fait une bonne estimation et il peut alors choisir, pour un état donné, l'action dont l'espérance de performance cumulée est la plus grande. Il existe différents algorithmes pour estimer la fonction de valeur (ou la fonction Q ) sans estimer de modèle. Parmi ceux-ci on peut citer les algorithmes basés sur le concept de différence temporelle (e.g., SARSA [START_REF] Sutton R | Reinforcement Learning: An Introduction[END_REF] et Q-learning [START_REF] Watkins | Learning From Delayed Rewards[END_REF][START_REF] Watkins | Q-learning[END_REF]) ou encore les algorithmes de la classe fitted-Q iteration qui sont basés sur l'algorithme d'itération sur les valeurs [START_REF] Ernst | Tree-based batch mode reinforcement learning[END_REF].

Exemples d'application

Certains problèmes classiques en commande des systèmes électriques ont été formalisés comme des problèmes de commande optimale à temps discret. Cette section présente deux types d'applications : en temps-réel, et en mode off-line. Avec l'approche RL off-line (Figure 2), l'agent est soumis à un ensemble de scénarii afin d'apprendre un certain nombre de caractéristiques du système. Il peut ensuite extraire une loi de commande à appliquer au système ou comparer les résultats obtenus avec différentes lois de commande génériques. Ainsi, dans [START_REF] Glavic | Power systems stability control: reinforcement learning framework[END_REF], un contrôleur de frein résistif est conçu pour améliorer la stabilité transitoire d'un réseau à dix noeuds. Un autre exemple est la commande d'un TCSC dans un simple système à un générateur et une charge dans [START_REF] Glavic | Learning versus model predictive control: a comparison on a power system problem[END_REF].

Les deux sections suivantes détaillent les applications à la commande d'un frein résistif et d'un TCSC présentées en [START_REF] Glavic | Power systems stability control: reinforcement learning framework[END_REF] et [START_REF] Glavic | Learning versus model predictive control: a comparison on a power system problem[END_REF].

Conception d'un contrôleur dynamique de frein

Figure 3. Système électrique à dix noeuds et deux régions [START_REF] Glavic | Power systems stability control: reinforcement learning framework[END_REF] Le système utilisé pour cette application compte deux régions comportant chacune deux générateurs et une charge (Figure 3). Suite à un défaut franc triphasé dans le système, on peut activer le frein résistif (RB) au noeud 6 afin d'éviter la perte de synchronisme entre les deux zones. La loi de commande à synthétiser doit donc déterminer à chaque instant si le frein résistif doit être activé.

Les générateurs sont modélisés par un modèle détaillé, avec une excitation à courant continu, un régulateur automatique de tension et un régulateur de vitesse, alors que les charges sont modélisées comme un courant constant et une impédance constante. Pour accélérer la résolution du problème, on réduit le modèle initial à 60 dimensions à un modèle à deux variables d'états, à savoir l'angle ( t δ ) et la vitesse ( t ω ) relatifs entre les deux zones, qui fournissent l'information nécessaire tant pour décider des actions de commande que pour mesurer la performance. La fonction de récompense est définie comme suit en fonction de la stabilité du système

   < - < ⋅ - - = rad if 1000 rad if ) , ( π δ π δ ω t t t t t t u c u x r (5) où } 1 , 0 { ∈ t u
indique si le frein est activé à l'instant t et c détermine le degré auquel on pénalise l'activation du frein. La phase d'apprentissage consiste en différents scenarii, où le système est soumis après 10 s de régime statique à un défaut franc triphasé au noeud 10 dont la durée est déterminée aléatoirement entre 250 et 350 ms. Le système entre ensuite en régime transitoire jusqu'à ce qu'une instabilité soit détectée ou que 60 s se soient écoulées. 1000 scénarii sont générés pour l'apprentissage, dont 163 instables. Pendant l'apprentissage, on adopte un facteur d'avidité ( ε ) de 0.1, c'est-à-dire, l'agent applique avec une probabilité de 90% une action « optimale » basée sur sa connaissance déjà obtenue, ou essaie une action au hasard pour explorer.

Modèle de simulation

Le résultat des simulations montre qu'après un apprentissage de 1000 scénarii, on a obtenu une commande structurée sur toute l'espace d'état. La police de commande ainsi obtenue permet au système de subir sans perte de stabilité un défaut franc d'une durée de 350 ms, alors que sans le frein, le défaut ne peut être plus long que 215 ms avant que le système perde le synchronisme. La robustesse de ce mode de commande est aussi testée pour un défaut franc se trouvant au noeud 7, pour lequel on arrive à augmenter cette durée maximale du défaut de 141 ms, sans frein, à 252 ms.

Apprentissage on-line pour commander un TCSC

Le deuxième exemple porte sur la commande d'un TCSC pour amortir l'oscillation de puissance électrique. Il s'appuie également sur le modèle de système électrique représenté en Figure 3, où un TCSC est placé entre les deux zones. Les paramètres de l'AVR des générateurs sont modifiés pour que le système soit initialement amorti négativement.

Contrairement au premier exemple, où on dispose d'un modèle de simulation pour exercer l'agent, on adopte dans cet exemple le mode on-line, où l'agent commande le système tout en apprenant de nouvelles trajectoires. Pour ce faire, les grandeurs utilisées par l'agent doivent être définies à partir de mesures en temps réel. Pour concevoir une police de commande locale, il faut aussi choisir une grandeur mesurable proche de l'emplacement du TCSC. Ainsi, la puissance ( e P ) transférée dans la ligne à laquelle le TCSC est connecté est supposée mesurée. A travers cette grandeur uniquement, le système est partiellement observable. Pour compenser ce problème, on définit un pseudo-état qui contient les observations et les actions prises à certains instants précédents. A l'occurrence, ce pseudo-état à instant t est défini comme les puissances injectées aux instants t , Les simulations avec une charge constante montrent qu'au bout de 10 heures après la mise en oeuvre de l'agent, il arrive à déduire une loi de commande qui enlève l'oscillation initialement présente dans le système non compensé. Les petites fluctuations restantes sont dues à la discrétisation. La loi de commande a aussi été testée avec une charge périodique, dont le résultat montre que la police est convient également aux conditions stochastiques.

Conclusion

Dans cet article, nous avons mis en évidence le potentiel d'application de l'apprentissage par renforcement dans la commande de systèmes électriques en nous appuyant sur deux exemples pratiques. Pour ces deux applications possédant un nombre relativement faible de variables d'états, des algorithmes d'apprentissage par renforcement assez simples se sont avérés performants En revanche, pour des problèmes impliquant plusieurs centaines ou milliers de variables d'états, comme c'est souvent le cas pour un grand système électrique, il faudra appliquer des algorithmes plus sophistiqués de sorte à décomposer le problème et/ou réduire l'espace d'état. Les approches de RL hiérarchique, l'agrégation d'état, etc. nous semblent particulièrement prometteuses à cet égard. Cette perspective s'annonce comme un défi scientifique, car la recherche dans le domaine de RL s'applique le plus souvent à des problèmes dont la solution peut-être trouvée en grande partie en se basant sur l'intuition humaine alors que ce n'est souvent pas le cas lorsque l'on traite des problèmes de commande liés aux grands réseaux électriques.

Figure 1 .

 1 Figure 1.Commande RL temps-réel [6] Agent

Figure 2 .

 2 Figure 2. Commande RL off-line [6]

  Le contrôle RL s'applique typiquement à des processus de décision markoviens. Dans cet article, nous nous concentrons sur les problèmes déterministes, où les équations qui régissent la dynamique n'impliquent pas de variables aléatoires. A tout instant t , le système est représenté par un

	état t x . Une action t u est alors appliquée et le système évolue vers l'état 1 + t x à l'instant	1 t . Cette +
	transition peut s'exprimer sous la forme de l'équation suivante :

.

  Quant à la variable de commande, elle est définie comme la réactance du TCSC, qui prend 5 valeurs discrètes entre sa zéro et sa capacité maximale. La fonction de récompense dépend de l'état de stabilité du système, et est défini comme suit :

	t	-	1	et	t	-	2	, ainsi que les actions prises à instants	t	-	1	et	t	-	2
								r	(	x	,	u	)	=	    	--	-1000 e P	e P	if if	e e P P	> ≤	MW MW 250 250
	où e P représente la valeur correspondante en régime permanent, qui est estimée comme la moyenne
	au cours de 60 dernières secondes.


R Gaglione Ab

C Adloff

M Chefdeville

C Drancourt

G Vouters

R Gaglione
email: gaglione@lapp.in2p3.fr

DIRAC v2: a DIgital Readout Asic for hadronic Calorimeter

• Linear fit: F (q) = 1/g • q + b g : gain b : pedestal Input charge is injected with a GPIB controlled pulse generator delivering a voltage pulse to on-chip 1 pC test capacitor through -20 dB attenuator. All data are collected to PC thanks to Labview software, and analyzed offline with a ROOT/C++ framework.

C. Results

The characterisation of DIRAC v1 has been described in details in [START_REF] Gaglione | DIRAC: a Digital Readout Asic for hAdronic Calorimeter[END_REF]. DIRAC v2 brings some improvements to these results: Table 3 gives results of a gaussian fit for gain and pedestal distribution for the five prototypes. These values are good enough to avoid any channel to channel ASIC calibration in the calorimeter.

The linearity is within +1/-3% on the 20-200 fC range.

The noise, extract from s-curve, is the width from 100% efficiency to 0% efficiency. At 5σ, the noise is less than 5 fC.

The minimum threshold is less than 10 fC which corresponds to half of the most probable signal from minimum ionising particles in MICROMEGAS detectors developped at LAPP. Moreover, a power-on time less than 3 µs has been measured. To obtain this result, efficiency and inflexion point of the s-curve have been observed in function of the power-on time.

IV. ASIC EMBEDDED IN MICROMEGAS CHAMBER

To minimize shower leakage and minimize HCAL diameter, the thickness of the active medium must be thinner than 8 mm. In that respect, the Bulk MICROMEGAS is an attractive option as the fabrication process allows a PCB with front end ASICs soldered on one side, and anode pads patterned on the other side to be equipped with a MICROMEGAS mesh. This is crucial for the construction of a real scale DHCAL for which large areas should be instrumented and dead zones minimized to insure a good hermeticity of the HCAL.

A MICROMEGAS detector consists of a gas volume separated in a drift and an amplification region by a thin mesh. An industrial technology, called bulk [START_REF] Giomataris | MICROMEGAS in a bulk[END_REF] has been chosen. The drift region is defined by a 3 mm thick resin frame manufactured by stereolithography. This frame also provides gas inlet and outlet. The drift electrode (cathode) is made of a 5 µm thick copper foil and a 75 µm Kapton insulator, glued together on a 2 mm thick steel plate, which is the MICROMEGAS chamber lid 1 . The amplification electrode consists of a woven mesh of stainless steel wires (18 µm diameter, 56 µm pitch) maintained by insulating pillars patterned by photolithography (400 µm diameter) at precisely 128 µm of the anodes. This technology has been chosen for its performances (especially near 100% efficiency for MIP), its robustness [START_REF] Baron | Large bulk-micromegas detectors for TPC applications in HEP[END_REF][7] and its ease of industrialisation in a PCB workshop (big amount of detectors and large areas are expected in the future). A cut view of the detector is presented Figure 6. The first tests are made with an X-ray source ( 55 Fe) thanks to a small hole in the lid of the chamber. The energy resolution is measured and the gain of the detector vs high voltage is checked (Figure 7). The pedestal is at 5 ADC counts, the photopeak at about 770 (σ=63). This gives an energy resolution σ E /E of 8.5% at 5.9 keV. A typical gain is 10 4 for a -420 V mesh voltage. This chamber has been tested in a 200 GeV pion beam at the CERN/SPS [START_REF] Gaglione | A MICROMEGAS chamber with embedded DIRAC ASIC for hadronic calorimeter[END_REF]. A drift cathode voltage of 460 V and a mesh voltage of 410 V have been used. Thresholds have been set to 24, 40 and 80 DAC code (respectively to 19, 32 and 64 fC). Figure 8 shows the beam profile in hit counts.

0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1
The measured hit multiplicity (mean number of pad hit for each trigger) is 1.10. This is in very good agreement with previous measurements performed with analog readout prototypes of same chamber geometry [START_REF] Adloff | Large surface MicroMegas with embedded front-end electronics for a digital hadronic calorimeter[END_REF] [START_REF] Adloff | MICROMEGAS chambers for hadronic calorimetry at a future linear collider[END_REF].

V. FUTURE IMPROVEMENT

Recent physics simulation may indicate that the lowest threshold for a DHCAL should be around 1 MIP-MPV. However, a 97% efficiency for the detector invloves a minimum threshold of 1.3 fC. Thus, to perform further R&D on the micromegas detector, a new preamplifier is needed, with improved gain, improved bandwidth, and improved noise, and without rising the power consumption too much. An improved design, presented Figure 9 has started. The difference with the first version are a gain boost stage, a cascoded current source (I2) and a voltage follower at the output. With I1=200 µA, I2=20 µA, I3=I4=10 µA, the preliminary simulation results give a gain of 108 dB, a bandwidth of 8 kHz, and a gain-bandwidth product of 2 GHz. The phase margin is 72 • and the minimum phase (in the bandwidth) of 51 • . With no increase in the bias current, the rms noise is 2.2 mV with C det =60 pF. This value will be improved with increase of I1.

VI. CONCLUSION

The construction of a bulk MICROMEGAS chamber with embedded ASIC has been demonstrated by producing and test-ing a first prototype equipped with a DIRAC v1 chip. The second version of DIRAC ASIC is currently under characterisation. Further measurements of detection efficiency and hit multiplicity are foressen to assess in more details the performance of DIRAC based MICROMEGAS chambers. For that purpose, four chambers of small size (8×8 cm 2 ) are well suited and are currently under development. These measurements will be performed with beam at CERN.In parralel, the design of medium area PCB (32×48 cm 2 ) has began to build a 1 m 2 MI-CROMEGAS chamber.

Figure 5 :

 5 Figure 5: Example of s-curve

Figure 6 :

 6 photoresist pillars steel mesh (325 LPI) 5 µm drift cathode insulator

Figure 7 :

 7 Figure 7: Detector characterisation

Figure 8 :

 8 Figure 8: Beam profile

Figure 9 :

 9 Figure 9: Preamplifier schematic

Table 3 :

 3 Prototype dispersion summary

	Chip ID		1	2	3	4	5
	Gain (fC/DACU)	mean sigma 0.03 0.03 0.02 0.02 0.02 1.1 1.0 1.1 1.0 1.1
	Pedestal (fC)	mean sigma	6.2 2.0	4.0 1.6	6.7 1.8	6.9 1.6	5.6 1.7

In a DHCAL, this cover will be a part of the calorimeter absorber.

VII. ACKNOWLEDGMENTS

DIRAC v1 preamplifier has been designed by H. Mathez, acquisition board by C. Girerd and acquisition sofware by C. Combaret. The mask and the mesh lamination have been performed at CERN by R. De Oliveira and his TS/DEM group. Chamber design, assembly, handcrafting and tests have been conducted at LAPP by the LC-Detector group. Special thanks are addressed to F. Peltier for his involvement in the detector assembly.

VIII. REFERENCES


Developmental exploration in the cultural evolution of lexical conventions

Pierre-Yves Oudeyer and Frédéric Delaunay INRIA Bordeaux Sud-Ouest The objective of this poster is to show that developmental mechanisms can impact importantly the efficiency of cultural evolution dynamics in the formation of shared lexicons. Thus, this poster tries to gather two threads of research: semiotic dynamics and developmental sciences.

On the one hand, many models of language formation and self-organization were developed in the last decade, under the general theoretical umbrella of semiotic dynamics [START_REF] Steels | Evolving grounded communication for robots[END_REF]. One of the best studied model is the naming game [START_REF] Kaplan | Simple models of distributed coordination[END_REF], in which a population of agents builds a shared lexicon, associating words and meanings, through cultural evolution and selforganization. In these simulations, agents interact in a peer-to-peer manner, negotiating each time the word that shall be associated to a randomly chosen meaning. Experiments have shown that simple feedback mechanisms lead to the self-organization of a globally shared set of associations [START_REF] Steels | Evolving grounded communication for robots[END_REF][START_REF] Kaplan | Simple models of distributed coordination[END_REF].

On the other hand, recent years have also seen the multiplication of models showing that a developmental approach to learning can be very efficient in real-world spaces. The general idea is based on the gradual control of the complexity of the task or skill to be learnt, "starting simple" and progressively becoming more complicated.This can be realized through the control of the number of degrees of freedom of the motor apparatus, the sensitivity of sensors, or the complexity of the learning situations, which are progressively and actively increased [START_REF] Berthouze | Motor skill acquisition under environmental perturbations: On the necessity of alternate freezing and freeing of degrees of freedom[END_REF][START_REF] Elman | Learning and development in neural networks: The importance of starting small[END_REF][START_REF] Oudeyer | Intrinsic Motivation Systems for Autonomous Mental Development[END_REF].

In this poster, we propose to show that the introduction of active mechanisms of complexity control at the level of individuals in naming game experiments allows to drastically improve the speed of convergence of the global population to a shared lexicon. A related coupling was presented in [START_REF] Steels | Scaffolding language emergence using the autotelic principle[END_REF], but it concerned the evolution of grammatical forms and was combined with other new complex mechanisms, making the study of the specific impact of complexity control not directly addressed.

The "standard" naming game

In the naming game [START_REF] Kaplan | Simple models of distributed coordination[END_REF], a population of 𝑁 agents tries to negotiate a lexicon, associating for each agent each meaning 𝑚 𝑖 ∈ 𝑀 to a single word 𝑤 𝑗 ∈ 𝑊, avoiding both synonymy and homonymy.

The set 𝑀 of meanings and the set 𝑊 of words are finite and predefined, represented by discrete symbols, with 𝑊 ≥ 𝑀 . Initially, each agent starts with an empty lexicon, which grows through peer-to-peer interaction. In an interaction, a speaker and a hearer are randomly chosen. The speaker chooses randomly a meaning among those that are possible, and then looks for the word which is most strongly associated to this meaning in its internal memory. If there is no word already associated to it, then it chooses randomly a word among those that are not used yet in another association. Then, it utters the word and the hearer finds the meaning in its own memory which is most closely associated to it, and shows it to the speaker. If this is the same meaning as the one initially chosen by the speaker, then the interaction is a success, and both agents reinforce the association, and weaken all associations involving only the word or only the meaning used in the interaction. If the interaction is not a success, the speaker tells the hearer what meaning he intended and the hearer decreases the score of the association he used, and increases the score of the association proposed by the speaker. After a certain number of interactions, [START_REF] Steels | Evolving grounded communication for robots[END_REF] and [START_REF] Kaplan | Simple models of distributed coordination[END_REF] showed that a globally shared lexicon was formed.

Controlling complexity in the naming game

In the standard version of the naming game, as meanings are chosen randomly across the set of all possible meanings by the speakers, all meanings and many words are quickly introduced in the population. The consequence is that when 𝑀 is large, this leads to a massive competition among associations right from the few first dozens of interactions: the complexity of the task grows nearly to its maximum in a very short time.

We propose to introduce a mechanism, local to each agent, in order to permit the regulation of this growth of complexity. A mechanism which we experimented consists in having speakers choose actively the meanings they will talk about instead of choosing them randomly. This choice of meaning depends on the subjective level of success in communication that each agent currently measures: a given agent decides to talk about a meaning it has never talked about before if and only if the mean of the best scores of all associations involving each already used meaning is over a predefined threshold (90 percent), i.e. when they have enough success in interaction with others when talking about the meanings they already talked about. Otherwise, the speaker chooses randomly a meaning he has already used. The consequence is that the number of meanings, whose association with a word is negotiated in the population, gradually and actively increases instead of being maximal right from the start.

We have conducted systematic experiments to investigate the impact of such an active policy for complexity control. Results show that the speed of convergence is one order of magnitude faster when a developmental mechanism is used as opposed to the standard version of the naming game. For example, figure 1 shows comparisons of the speeds of convergence for both strategies in various experiments where the number of agents = the number of available words = the number of available meanings = N, where N is varied from 50 to 300. These curves show that the active strategy is not only faster, but that the algorithmic complexity changes (first approximations show that it shifts from 𝑂(𝑁 2 log 𝑁 ) to 𝑂(𝑁𝑙𝑜𝑔(𝑁))). Figure 2 shows the evolution of the mean number of meanings and words introduced in the population at a given time both for the standard and developmental version of the naming game: this shows that complexity increases more gradually in the developmental case. When total convergence is reached, its value is 1. We used here the value 0.9, which is quasi-convergence, because it allowed the simulation to be fast enough to obtain statistically significant results for the random strategy for N =|M|=|W| = 300 (each simulation already takes several hours on a standard PC).

Figure 2 With the active choice of meaning, the growth of the number of meanings and words is dynamically controlled.

Figure 1

 1 Figure 1 Comparison of the speed of convergence on a shared lexicon in population of agents with the standard naming game (random choice of meaning) and with the developmental naming game (active choice of meaning). The theoretical success is a measure described in (Kaplan, 2005) which allows us to monitor how far agents in the population are from globally sharing the same non-ambiguous lexicon.When total convergence is reached, its value is 1. We used here the value 0.9, which is quasi-convergence, because it allowed the simulation to be fast enough to obtain statistically significant results for the random strategy for N =|M|=|W| = 300 (each simulation already takes several hours on a standard PC).