Pierre Andry

Arnaud Blanchard

Philippe Gaussier

Using the rhythm of non-verbal human-robot interaction as a signal for learning

Keywords: Human-robot-interaction, Autonomous robotics, Self-supervised learning, artificial neural networks, rhythm detection and prediction

published or not. The documents may come

Using the rhythm of non-verbal human-robot interaction

as a signal for learning

I. INTRODUCTION

U NDERSTANDING non-verbal communication is crucial for building really adaptive and interactive robots. Young infants, even at pre-verbal stages take turn, naturally switch roles and maintain bi-directional interaction without the use of explicit codes or declarative "procedures" [START_REF]The Imitative Mind: Development, Evolution and Brain Bases[END_REF]. Among the implicit but important signals of interaction, synchrony and rhythm appear to be fundamental mechanisms in early communication among humans [START_REF] Nadel | Experiencing contigency and agency : first step toward self-understanding ?[END_REF], [START_REF] Rochat | Five levels of self-awareness as they unfold early in life[END_REF].

Our long term goal is to understand the emergence of turn taking or role switching between a human and a robot (or even between two robots). Understanding what the good dynamical properties of turn taking are would be an important progress towards maintaining for free robust and long lasting interaction (without explicit programming or explicit signals). It could lead to the learning of long and complex sequences of behaviors. Moreover, this work is linked to the fundamental question of how a "natural" interaction can emerge from few basic principles [START_REF] Kuriyama | Acquisition of human-robot interaction rules via imitation and response observation[END_REF]. Taking inspiration from numerous studies in developmental psychology on how newborns and young preverbal infants react in interpersonal relations (see next section for a review), this work focuses on the role of rhythm in human-robot face to face interaction. Our main goal in this ETIS, CNRS UMR 8051, University Cergy-Pontoise, ENSEA, 6avenue du ponceau, F-95000

Institut Universitaire de France (IUF)

paper is to show that an implicit signal such as the rhythm of the interaction can be used to build internal rewards and enhance the learning of an interacting robot. To do so, we propose a simple methodology illustrating how many good associations can be learned thanks to the conjunction of a rhythm detector with different reinforcement learning rules: is a robot detecting cadence changes able to improve its responses and converge toward a satisfying interaction with a caregiver ? We present an artificial Neural Network (NN) control architecture inspired from properties of the hippocampus and cerebellum. This model allows on-line learning and the prediction of the rhythm of the sensorimotor flow of the robot. As a result, the robot is able, from its own dynamics, to detect changes in the interaction rhythm, that is to say changes in the cadence of the gesture production of the human-robot system. The architecture uses the rhythm prediction to compute an internal reward reinforcing the robot's set of sensorimotor associations. Therefore, a stable and rhythmic interaction should indicate that the robot's behavior is correct (generating internal positive rewards, strengthening sensorimotor rules, and allowing to respond correctly). On the other hand, an interaction full of breaks (the time for the caregiver to express his disagreement or even to interrupt the interaction) should lead the robot to change its motor responses due to the internal negative reward and converge toward new ones corresponding to the human's expectancies. Rhythm prediction plays the role of a control mechanism allowing the building of an internal reward, which is used to guide the learning of sensorimotor associations. Finally we will discuss the importance of the learning rule coupled to the rhythm prediction mechanisms and highlight how rule properties can affect the quality of the interaction, and the learning of the task.

II. INTERDISCIPLINARY MOTIVATION

In the last decade, an important effort has been made to make robots more attractive to human beings. For instance, a major focus of interest has been put on the expressiveness and the appearance of robots [START_REF]Regulation and entrainment for human-robot interaction[END_REF], [START_REF] Kozima | Can a robot empathize with people?[END_REF], [START_REF] Masahiro | On the uncanny valley[END_REF] . Targeting the facilitation of human-machine communication, theses approaches have neglected the importance of the dynamics when two agents interact. In our opinion, intuitive communication (verbal or not) refers to the ability to "take turn" and to respond coherently to the stimulations of others without needing the presence of an expert. In summary, it means being able to detect the crucial signals of the interaction and use them to adapt one's dynamics to the other's behavior. Obviously, such an issue questions the sense of "self" and "others", and the position of such notions in the frame of building an interactive robot. In the present work, we do not want to define an a priori boundary between the robot and the external world. We follow a bottomup approach, testing how the combination of a few low-level mechanisms can allow the emergence of cooperative behaviors without any notion of self. From an epigenetic perspective this combination of low-level mechanisms can then appear as an interesting hypothesis in the discussion of the emergence of self and agency in artificial and natural systems. Among these bootstrapping mechanisms, we will emphasize novelty detection (and more precisely rhythm detection) as a way of building an internal reward structuring the learning of any interacting agent. In developmental robotics, a lot of research focus on how artificial systems can detect novelty in their surrounding environment in order to learn and generalize new skills, i.e. how robots can, autonomously, develop and ground their own learning experience [START_REF] Lungarella | Modelling embodied cognition in humans with artifacts[END_REF]. The notion of environment itself plays a crucial role, with numerous researches focusing on the embodiment or the surrounding physical environment while a few deal with the adaptation to the social environment of the robot. One of the seminal works concerns the role of prediction in the building of the relationships between the environment and the robot. In [START_REF] Tani | Learning to perceive the world as articulated: an approach for hierarchical learning in sensory-motor systems[END_REF], the authors showed how multiple internal predictors playing the role of experts can help a mobile robot segment the outside world according to the confidence and the scale of the prediction of each expert. The segmentation of the external world in different categories (and therefore the convergence of the experts predictions) is made on-line, while the robot is exploring the environment. Another good example of an active exploration and learning of the physical environment can be given by the humanoid robots Cog and Obrero. In [START_REF] Fitzpatrick | First contact: an active vision approach to segmentation[END_REF], Cog produces random arm movement to roll and push small objects, and use the induced optical movement to discriminate the objects from the background (see also [START_REF] Torres-Jara | Tapping into touch[END_REF] for the same experiment using sound with the robot Obrero). This is used to visually segment the objects and to learn some of their properties (roll vs non-roll, etc.). These experiments are examples in which the robot's progress is directly linked to its activity and the changes it induces. Also in the frame of the exploration of the physical surrounding environment, authors have proposed to introduce the notion of intrinsic motivation in artificial systems [START_REF] Barto | Intrinsically motivated learning of hierarchical collections of skills[END_REF], [START_REF] Oudeyer | Intelligent adaptive curiosity: a source of self-development[END_REF]. They propose that self-motivated experiments of a prediction-based controller allow the robot to discover and split its physical environment into a finite number of states. The different areas of interest are segmented and labeled according to the consequence of the experiments on the learning progress of the robot [START_REF] Oudeyer | Intrinsic motivation systems for autonomous mental development[END_REF]. This mechanism allows the robot to seek the situations where novelty will be the most "interesting" by providing the maximal learning progress (fully predictable and totally un-predictable situations progressively becoming repellers). Such an "artificial curiosity" is a good example of how the building of an internal reward value can drive the development of the robot in its physical environment. Finally, in preliminary experiments Pitti et al. [START_REF] Pitti | Synchronization : Adaptive mechanism linking internal and external dynamics[END_REF] have started to link internal dynamics with the dynamics of a human manipulating the robot. They highlight how synchronization allows to integrate sensing and acting in an embodied robot, and then facilitates the learning of simple sensorimotor patterns. The authors show that the synchronization between input (sensing) and output (action) is a necessary condition for information transmission between the different parts of the architecture and therefore for learning new patterns. Reviewing these studies, one important question we may ask is: can the same principles of novelty detection and intrinsic motivation be applied to a social environment, for example in the case of an autonomous robot exchanging with a caregiver? The first works started to show that behaviors such as imitation could allow autonomous robots to get for free some adaptation to the physical environment thanks to simple "social" behaviors [START_REF] Dautenhahn | Getting to know each other -artificial social intelligence for autonomous robots[END_REF]. Following this idea, we have started to consider low level imitation (imitation of meaningless gestures) as a proto-communicational behavior obtained as an emergent property of a simple perception-action homeostat based on perception ambiguity [START_REF] Gaussier | From perceptionaction loops to imitation processes: a bottom-up approach of learning by imitation[END_REF], [START_REF] Andry | Learning and communication in imitation: An autonomous robot perspective[END_REF]. Tending to balance vision and proprioception (direct motor feedback) the controller acts to correct errors induced by an elementary visual system (unexpected movement detection). An imitative behavior emerges without notion or detection of the experimenter. Based on the same principles, [START_REF] Blanchard | From imprinting to adaptation : Building a history of affective interaction[END_REF] highlights how a system naturally looking for the initial equilibrium of its first perceptions (based on the imprinting paradigm) can alternate an exploration of the physical environment and a return to the caregiver for learning grounding. More recently, researches have started to investigate the stability of human-robot faceto-face interactions, using synchrony and anti-synchrony as a link between stable internal dynamics and bi-directional phase locking with the caregiver [START_REF] Prepin | Human-machine interaction as a model of machine-machine interaction : how to make machines interact as humans do[END_REF], [START_REF] Kuriyama | Acquisition of human-robot interaction rules via imitation and response observation[END_REF], [START_REF] Blanchard | Designing a turn-taking mechanism as a balance between familiarity and novelty[END_REF], [START_REF] Revel | Emergence of structured interactions: From a theoretical model to pragmatic robotics[END_REF]. According to developmental psychology, the ability to synchronize, to detect the synchrony, and the sensitivity to the timing appear to play an important role in early communication among infants from birth on. Works have shown that babies are endowed with key sensorimotor skills exploited during interpersonal relations [START_REF] Rochat | Five levels of self-awareness as they unfold early in life[END_REF]. For example, the young infants show sensitiveness to timing with the ability to imitate, exchange and preserve the temporality and rhythm of sequences of sounds during bi-directional interaction with their mother [START_REF] Trevarthen | The social foundations of language and thought[END_REF]. Neonates (between 2 and 48 hours after birth) are able to anticipate the causality between two events, and also to express a negative expression if the second event does not follow the first one [START_REF] Gewirtz | Handbook of socialization theory and research[END_REF], [START_REF] Blass | Classical conditioning in newborn human 2-48 hours of age[END_REF] . Gergely and Watson have unified these findings in a model of contingency detection (DCM) extending the notion of causality to the social events [START_REF] Gergely | Early social-emotional development: Contingency perception and the social biofeedback model[END_REF]. According to the DCM model, infants are able to discriminate the causality provoked by their own actions (direct feedback inducing a perfect synchrony with their own motor production) for example when seeing and/or feeling the movement of their own body, from the contingencies of social interactions (due to the regular but non perfect synchrony between the emission of the stimulus by the baby and the response of the caregiver). From this point, contingency detection have turn to be one of the key mechanism of the development of self and social cognition [START_REF] Hiraki | Detecting contingency: A key to understanding development of self and social cognition[END_REF]. In the same line, Prince et Al. are interested in understanding the development of infant skills with a model of contingencies detection based on the inter-modal perception of audio-visual synchrony [START_REF] Prince | Taking synchrony seriously: A perceptuallevel model of infant synchrony detection[END_REF]. An extended verson of this lowlevel model is also tested by Rolf et al. in order to bind words or sounds with the vision of object [START_REF] Rolf | Attention via synchrony. making use of multi-modal cues in social learning[END_REF]. In parallel, a lot of studies have been aimed at studying how infants detect changes in the other's responses during face-toface interactions. Since 1978, the still-face paradigm, introduced by Tronick et al has been widely used and studied (see [START_REF] Nadel | Twomonth-old infants of depressed mothers show mild, delayed and persistent change in emotional state after non-contingent interaction[END_REF] for a review) especially during pre-verbal interactions. A still-face consists in the production of a neutral, still-face of the caregiver after a few minutes of interaction. Interestingly, this sudden break of the response and the timing of the interaction induce a fall of the infant's positive responses. The same responses where also measured with the more accurate Double Video paradigm allowing to shift the timing of the interaction using a dual display and recording system [START_REF] Nadel | Experiencing contigency and agency : first step toward self-understanding ?[END_REF]. In this second paradigm, the content of the caregiver's responses remains the same as in a normal interaction, but a more or less long decay can be introduced in the display of the mother's responses. Using this dispositive during natural, bi-directional mother-babies interactions, Nadel and Prepin [START_REF] Nadel | Experiencing contigency and agency : first step toward self-understanding ?[END_REF] highlight the importance of the timing of the response and show how synchrony and rhythm are fundamental parameters of preverbal communication. Breaking the timing results in violating the infant's expectations, and produces a strong increasing of negative responses.

Consequently, in the frame of a face-to-face human-robot interaction composed of simple gestures (for example an imitation game), our working hypothesis will be the following:

• a constant rhythm should naturally emerge if the interaction goes well (that is to say, if the robot's responses correspond to the human's expectancies).

• Conversely, if the robot produces the wrong behavior or the wrong responses, we suppose that the human may introduce more breaks in the interaction, for example to take the time to restart the game, manifest his disagreement(even if the robot is not able to process any signal concerning this dissatisfaction), or simply withdrawing the interaction. Therefore, we will present in the next section our model for rhythm learning and prediction, and the internal reward extraction mechanism based on the rhythm detection.

III. MODEL

Our model is an artificial Neural Network divided in two main parts (Fig. 1). The first part (the Rhythm detection and prediction layer in Fig. 1, up) learns on-line and very quickly (one-shoot learning) the rhythm of the Input-Output activity and computes a reward value R according to the accuracy of the rhythm prediction. The second part (the sensorimotor learning layer in Fig. 1, bottom) is a reinforcement learning mechanism allowing to change the Input-Output associations according to R values updated during the interaction.

A. Rhythm detection and prediction

The role of this network is to learn and predict the timing of the changing sensory-motor events. The network is inspired by the functions of two brain structures involved in memory and timing learning: the cerebellum and the hippocampus (see [START_REF] Banquet | Cognitive Science Perspectives on Personality and Emotion[END_REF] for the neurobiological model we have proposed). It processes the sum of information from the sensorimotor pathway (integrating vision processing and the link between vision and motor output, see section III-B), stimulated each time the human makes a gesture in front of the robot. Consequently, the robot can have information about the whole dynamics of the interactions by monitoring only the flow of its own sensorimotor activity, without having any notion of the other. A single S neuron is summing the activities coming from the sensorimotor pathway. When S is connected to the Input vector, the result is an activity representing the total intensity of the human stimulations. In all the experiments, Input responses are the result of a competition applied to the visual detection. Therefore, S gives the undifferentiated activity of the successive inputs activated. The core of the timing prediction is composed of three groups of neurons (Fig. 1

Act TB j (t) = m 0 m j • exp - ((t -τ ) -m j ) 2 2 • σ j ( 1
)
where j is the number of the cell of T B, m j and σ j are the time constant and the standard deviation associated to the jth cell. τ is the instant of the activation of T B by one T D spike. One P O cell learns the association between T B cells states (the time trace of the previous Input stimulation) and the new T D activation (the detection of the current Input stimulation).

W TB(j) PO =    Act TB j j (Act TB j ) 2 if Act TD = 0 unmodified otherwise (2)
The potential of P O is the sum of the information coming from T D and the delayed activity in T B.

P ot P O = j W T B(j) po • Act T B j (3)
Act P O = f P O P ot P O (4)
f P O = exp x 2 2 • σ 2 (5)
After one learning (at least the presentation of two Input stimulations), T B cells activation leads to the growing activity of P O until a maximum corresponding to the stimuli period (Fig. 2). The learning is done on-line, meaning that repetitive activations of the different units of Input will lead to repetitive predictions of the timing of the next input by P O. The prediction itself is not linked to a particular Input unit, but only to the precise timing at which the next Input unit should be observed. At last, comparing P O and T D activities gives the success value of the rhythm predictor. This comparison is used to build the reward R for sensorimotor associations learning:

R(t) = P O(t) -α • T D(t) (6)
with P O(t) the value of the activity of P O in [0, 1.5] at the instant t, T D(t) the value of the activity of T D in [0, 1], t the instant of T D spike, and α = 0.75 in all experiments. The value of R(t) is calculated when T D spikes, on the basis of P O state at time t . For example, let us suppose that Input is activated with a period t ref . P O learns to predict the timing with a maximal activity at t ref , and the value of R(t) is maximal while the frequency of Input activation stays unchanged. If, for some reason, the input frequency is changed to a period t new , then the shape of P O ("bell" curve) will induce a decrease of R(t) proportional to the shift between t new and t ref (see Fig. 3). If t new is too different from the previous t ref , a negative reward is produced (rhythm break detection) at the first occurrence of the new T D spikes. After the emission of the negative reward, t new will be learned by P O (on-line learning), being the new reference of the interaction rhythm and the new period predicted. Letting P O learn on-line the period allows to obtain a system which suits to the changes of timing (see Fig. 4), without negative reward if the frequency is slowly changing and sliding during the interaction. Moreover, eq. 1 and 2 allow a one shot learning of the timing between two stimulations. It means that the rhythm is learned once the human and the robot have exchanged two gestures (approximately 3 to 5 seconds of interaction, depending on the human intrinsic period of interaction t ref ). In the frame of a human robot interaction, the rhythms can not be learned faster. During the interaction, the rhythm prediction is constantly updated according to the flow of the Input/Output information, at each new gesture. Of course, the rhythm prediction can be updated or progressively modified to take into account past value (averaging with a sliding window).

Such properties are welcome in the frame of a real humanrobot interaction where the rhythm can slowly vary without negative impact until a strong break arises. When a negative reward is emitted (case of a strong rhythm break), P O is temporally inhibited until the next T D activation. This modulation of P O prevents the learning of the duration of the rhythm break itself and having two consecutive negative rewards. One of the main interests of this NN algorithm is that P O prediction respects the Weber-Fechner law [START_REF] Banquet | Cognitive Science Perspectives on Personality and Emotion[END_REF]: the standard deviation of P O activity is inversely proportional to the period of the timing learned. This property is particularly appropriated to the detection of various human-robot interaction rhythms, where for example a delay of 100ms must not have the same consequence if it happens in a interaction that is carried at 0.5 Hz vs 5Hz . The global shape of the reinforcement is In the above experiments, the number of cells j was tested between 10 and 30 according to the precision of P O needed (j does not affect the global shape of P O activity but the resolution of the curve). m j defines the center of each curve on the time course since the activation of the battery (at a relative time τ ). It is important to maintain an overlap of the activity of each cell of T B, otherwise a strict separation would result in noisy and erroneous predictions (in this case the maximum of P O would not correspond to the learned timing). Practically, the value of m j is proportional to j multiplied by a constant, and shifts the center of each curve along the time course. To ensure the overlap of multiples cells and the production of a "bell" curve of P O, σ j is also linked to j. More precisely, σ j is inversely proportional to the value of j • m j • constant. This ensures that the first cells of T B have high standard deviation, resulting in a "thin" curve, while the last cells have a smaller deviation, resulting in larger curves. This variation of thickness of T B curves induce the variation of thickness of the P O curve at the origin of the Weber-Fechner property (see Fig. 2).

B. Sensorimotor Learning

The Input-Output link (Fig. 1, bottom) is the sensorimotor pathway of the architecture. Input processes visual information from the CCD camera. The visual space of the robot is split into different areas stimulated by the gestures of the human. For seek of simplicity, the actions of the human are filtered by a color detector, and the human is asked to handle a pink ball (see Fig. 5). Output triggers the robot's motor response. The activation of one Output neuron induces the movement of the robot's effector toward a region of the working space. The number of Input and Output neurons is the same, and the division of the working space is the same on each layer. For example, Input first neuron is activated when the upper right area of the visual space of the robot is stimulated, and the trigger of the first Output neuron will induce the robot to raise the right arm upside.

In the frame of our experiments, Input and output are competitive layers forcing the activation of a sole Input-Output association at a time. Both groups also have activity thresholds, allowing the robot to be still (no motor command) if no relevant input is provided (no significant visual activity). From these properties, we obtain an elementary but reliable basis for a non-verbal human robot interaction. Each time the human caregiver makes a move (stimulating Input neurons) the robot will trigger a motor response. Input-Output links are initially random, and in the frame of our experiments, the robot will have to discover and learn the right Input-Output associations corresponding to the caregiver expectancies. Therefore, finding the good responses corresponds to discovering the right sensorimotor associations among the possible ones. To do so, a learning rule using reward R computed by the Rhythm detection and prediction Layer (section III-A) is introduced.

The rule learning Input-Output associations is directly inspired from the Associative Search Element (ASE) from Barto, Sutton and Anderson [START_REF] Barto | Neuronlike adaptive elements that can solve difficult control problems[END_REF]. ASE uses a "generate and test" search process in order to find the correct outputs. To simplify the equations, the letters I and O stands for Input and Output groups.

O i = H( j W ij * I j + noise) (7)
With H the Heaviside function and noise the amount of additional random noise. At the beginning of the experiment the W ij have the same value and the noise value is driving the selection of O i neurons. It ensures the initial exploration of the search space before any learning. When an output is tested, the correction of the weight is made according to the variation of R(t) and O i (t -1):

∆W ij (t) = α • ∆R(t) • ∆O i (t -1) • O i (t -1) • I j (t -1) (8)
with ∆x(t) = x(t)x(t -1) and W ij the weight between Input j and Output j updated at time t. For the Input I j activated at t -1, the network tests the output O i at t -1 and obtain the reward R at t. This learning rule results in a modification of the Input-Output link according to the variations of R(t) and Output(t), Fig. 6. Therefore, constant on-line updates of the rhythm prediction produce a new R value at each interaction step (that is to say at each new human-robot exchange of gesture), and to change the Input-output weights accordingly. Doing so, it is important to notice that the convergence time is strongly dependent of the interaction cadency, the value of R being updated at each exchange according to each new rhythm prediction.

I i (t) ∆O i (t -1) ∆R(t) ∆W ij (t) 0 . . 0 . 0 . 0 . . 0 0 1 ր ր ր 1 ր ց ց

IV. EXPERIMENTS

In this section, we describe three kind of experiments: 1) A simple human-machine interaction based on keysound associations. The experimenter has to teach the computer to associate sounds with keystrokes. In this experiment, the human is expert, and the goal is to demonstrate the convergence of the model with a growing number of Input-Output associations 2) A human-robot interaction with a Sony Aibo robot, testing gestures-gestures associations. The human has to teach the robot to respond with the right gesture among 4 possible ones, according to 4 human gestures. In this experiment we tested expert and non-expert users in the frame of very limited instructions. 3) A human-robot interaction with a small humanoid Aldebaran Robotics Nao robot. The subjects are involved in the same gesture experiment as experiment 2, and we also tested two groups of subjects, experts vs nonexperts. Taking into account the results of experiment 2, we propose to enhance the learning rule to take into account a delayed reinforcement and we introduce a confidence value to enhance the stability of the robot's associations testing. In all the experiments, we have defined expert and non-expert subjects as follow:

• An expert user is a subject that knows that the rhythm of the interaction has an effect on the robot learning. It concerns people from the lab aware of this research, and also peoples naive to robotics that are instructed before the experiment that they can change the timing of the interaction or break the rhythm in order to change the robot's behavior.

• A non-expert user is a subject that is not aware of the robot's functioning, and that has for only instruction the one given to each experiment, without additional information.

A. Human-machine interaction: the sound experiment

In order to test the feasibility of our model, we have established a human-computer interaction setup.

1) Setup: The setup is designed as a game where the expert must teach the computer to produce a given note when he hits a given key. As presented in section III, the architecture must learn to associate key strokes with sounds, through the interaction (see Fig. 7). Fig. 7. Principle of the human-computer interaction. The user (U ) pushes a keyboard key and expects a given note in response. From t 1 to t 4 the machine (M ) responds correctly, so the user continues the interaction and tests new keys. At t 6 the note emitted is incorrect, and the user interrupt shortly the interaction (or at least change noticeably the timing) to restart the interaction, or for example express his disagree before going on.

2) Results:

We have tested the network with sizes of Input and Output groups going from 2 neurons to 10 neurons. In all tests, the number of neurons in Input and Output is equal, meaning that the search rule had to discover the right set of n associations in a set of n 2 possible associations. Figure 8 shows the average time for discovering the right set of associations according to n (Fig. 8, up) and the progress of the on-line learning during one experiment, with n = 10 (Fig. 8, bottom).

The system succeeded in learning the set of correct associations. Obviously, we see in Figure 8, up that the convergence time of the architecture is strongly linked to the combinatory of the exploration space before discovering the right associations. For example the experiment presented in Figure 8, bottom took approximately 7min of interactions before fully converging. The network is running permanently, but it is important to notice that the learning rule can only be triggered after each update of the interaction cycle. Therefore, the time taken to converge is not a limitation of the algorithm, but a limitation imposed by the user's cadence taking the time to interact every 2 or 3 seconds in the frame of such a keyboard-human game. If we take for example the sequence of 10 elements, it means that the interaction has to go through the test of the 100 possible input-output associations. With an interaction cycle of 3 s, this gives us a "theoretical" total interaction duration of 300 seconds, without taking into account the additional time taken to break the interaction. Our algorithm converges in a mean time of 445 seconds of intereaction.

The choice of this first test (under the form of a humancomputer interaction using sounds, for seek of simplicity) allows the human to quickly and intuitively react to the sound emitted by the computer. With such a simple setup, all the tests where done with an expert user, that is to say a user confident with the interface, and who knows that he can use the rhythm to control the learning. The objective of this experiment was to show that the convergence of a classical reinforcement rule was possible when combined with a neural network rhythm predictor learning on-line, even with a large amount of possible sensorimotor associations (here, up to 100 associations). "Large " must be here understood as an important set of associations to be explored in a limited time of interaction. In all the experiments, the first association have always been the most difficult to discover. While none of the responses of the system are those expected by the user, it is difficult to establish a default rhythm of interaction. Conversely, once a first association is discovered and learned, the user tends to use it to support the exchanges, installing a default rate with the system before testing the new keys, and so on.

B. First Human-robot experiment

1) setup: For this experiment, we have used a Sony Aibo robot. The robot was seated on a table in front of the human (see Fig. 9 for an illustration). The robot controlled four degrees of freedom (the elbow and the shoulder of each arm), and the head was still. The control architecture was implemented with four different actions: raising the left foreleg, raising the right foreleg, lowering the left foreleg or lowering the right foreleg. The task was a "mirror action" game where the robot has to learn to make the same action as the human. The robot must produce the same action, on the same side, as the actions done by the human (human and robot being faceto-face). During the game, the robot has to explore its motor repertory when stimulated by the human, and discover and reinforce the mirror gestures of the human's ones. Consequently the robot had to discover the 4 associations corresponding to the imitative actions among 16 possible ones.

2) Instructions: The subjects where told to "teach the robot to do the same action". To illustrate the instructions, a little program was run to show the 4 possible actions of the robot using the two upper legs. No additional instruction was given to the subject (if the robot is able to process speech, face, etc...). Such a setup was done to easily engage the human to lead the interaction, and also to give as less as possible cues about the functioning of the robot, especially for nonexpert users. The human proposes a gesture and wait for the robot's response, but he has no access to any special interface indicating to the robot if the response was good or bad. At the end of the experiment, we questioned the subject about the quality of the interaction, the teaching procedure they used, and if they could understand how the robot was learning.

3) results: experts: For all expert subjects, the learning of the 4 Input-Output associations was completed in a mean time of 4min of interactions. Figure 10 shows the result of one experiment conducted with an expert according to the setup described in the previous section. The correct learning of the 4 associations took approximately 3 minutes1 . As in the sound experiment, the experts found the first association the most difficult one to teach because they have no basis to trigger a constant rhythm and therefore no basis to control the reinforcement. Most of the experts, and especially the experts naive to robotics (but instructed to use the timing to change the robots learning) also felt the robot's action choices as inconsistent during the experiment. The interaction was found to be "disturbing", or "unstable", because of the robot changing randomly the exploration of the sensorimotor associations. This behavior of the robot is directly linked to the noise parameter added to the activity of O i . If this variable is fundamental in the exploration of the search space by the algorithm, the corresponding robot's behavior is felt as inconsistent by the experimenter, changing from time to time the action, "for no reason". This situation particularly happens at the beginning of the experiment, when |R| is too week to induce strong changes of the W ij letting the noise value decide the winning output.

4) results: non-experts: None of the 5 non-expert subjects succeeded to teach the robot the 4 Input-Output. The best score was the teaching of 2 associations (population mean score: 1.4 taught association), with a mean interaction time of 5.2 minutes. When questioned, none of the subjects detected that the timing of the exchanges played a role in the learning of the robot. When combining data record (mainly the robot's inputs) and responses of the subject to an interview about the quality of the interaction, we can formulate the following comments:

• As for the expert subjects, the non-experts felt the robot behavior as inconsistent, changing randomly the actions. A more "stable" behavior in the responses of the robot would have helped the subject to take the time to work on a given sensorimotor association, testing it iteratively and giving more chance to install an interaction rhythm.

• There is a strong overlap between the duration of actions and reaction of the non-experts whatever this duration is For all experiments, we recorded the delays and durations (from the robot's perceptions) of the actions responsible for the reward attribution. On the left side ares values of delays and durations corresponding to negative rewards vs the positive ones on the right. Mean delay and duration for negative rewards are 3.2s and 1.7s vs 6.1s and 2.3s for the positive rewards. Similar distributions where found for each of the 5 non-experts.

linked to a positive or a negative reward (Fig. 11). In this experiment, the variance and overlap for each category shows that there is no obvious distinction between the timing of successful actions and incorrect ones. We can explain the variance of positive actions as follow: cadences are not always the same, and the period of a constant satisfying interaction can slide during the experiment. This effect is taken into account by our algorithm that adapts to small successive variations of the rhythm. We can explain the variance of negative actions as follow: when observing the experiment and the inputs of the robot (reflecting the timing of the subject's actions) non-expert users often carry-on the interaction at a constant rhythm when the robot is wrong, waiting two or three wrong actions to make a strong break. This explains that the duration of negative actions and reactions overlaps with the positive ones. Such information allows us to think that if an algorithm using immediate reinforcement is suited for experts (they immediately break the rhythm after a wrong answer) it may not be the case in the frame of nonexpert users, waiting a mean of 2 or 3 wrong responses before breaking the interaction. In this case, our algorithm should also take into account the delayed rewards, for example to distribute the effect of a negative reward on the 2 or 3 past associations.

• Finally, and more generally it is important to mention that experiments lasting more than 4min were found to be tiring by the non-experts. We did not conduct an intensive research on how to identify precisely the time during which a human could accept to interact with such a setup. The number of variables is too important (it would require a strong analysis of the experimental condition) and such a study is out of the scope of our competences (the human being in the loop, it would require a psychological study about the human acceptance of interaction with such artificial systems). Nevertheless, these naive but recurrent observations of tired or bored reactions after 4 or 5 minutes of interaction let us suggest that it is a limit for studying a "one shoot" interaction with our autonomous robots (being given the entertainment level of our robots).

C. Second Human-robot experiment

To investigate the limitations of the first set of robotic experiments, we tested a second learning rule, in order to (1) take into account a delayed reward, for example if the break of the rhythm does not only concern the precedent Input-Output association and (2) to give to the robot the possibility to maintain the associations longer in order to test more strongly if a rule must be learned or unlearned.

1) The PCR rule: The Probabilistic Conditioning Rule (PCR) [START_REF] Gaussier | Living in a partially structured environment: How to bypass the limitation of classical reinforcement techniques[END_REF] was proposed to allow mobiles robots to learn the correct set of perception-action associations when receiving delayed reward. A typical task solved by PCR was to allow a mobile robot to learn the right actions to do (go ahead, turn left or turn right) in order to escape from a maze. Each branch of the maze was recognized by the robot using vision (the recognition of the places being the inputs of the learning network), and the robot received negative rewards each time it bumped into a wall, and a unique positive reward when escaping from the maze. The rule was designed with the following properties:

• the robot must be able to test a given number of hypothesis during a given amount of time before deciding to learn or not (for example always turning left when sensing a wall close to the front sensors).

• the robot can manage delayed reward, thanks to a memory of the associations that where selected since the last reward (for example rewarding the robot only at the exit of the maze). Whereas this learning rule was initially designed to solve tasks of mobile robotics with external motivations, we found interesting that its properties should fit with some of the issues of our first robotic application.

In order to be able to reward past associations, P CR uses a correlation X over a sliding window τ in order to keep a short term memory of the activated inputs (I i ) , outputs (O j ), and associations (IO ij ) with:

X j [t + 1] = τ X j [t] + X j [t] τ + 1 (9)
In order to be able to test a given association longer, a confidence value (p ij ) is introduced. This value represents how the corresponding association is trusted by the architecture. A high value of p ij indicate that the corresponding association between I i and O j should not be changed. Otherwise a weak value of p ij indicate that the association must be changed because not rewarding. Consequently, R is used to change the confidence value of associations:

if |∆R(t)| > ξ then the confidence value p ij is updated:

∆p ij = (ǫ + α * ∆R) * C ij * f B (W ij ) -λ * p ij (10)
p ij [t + 1] = H(p ij [t] + ∆p ij [t]) (11)
With R(t) the global reinforcement signal from P O, ǫ the learning speed, α the reinforcement factor, λ a forget factor, ξ the reward threshold.

f B = -1 if W ij = 0, 1 otherwise.
Moreover, C ij is the STM memory of the past associations calculated with eq. 9 and:

C ij = IO ij I i O j (12)
At each iteration, the confidence of each association is tested. If a random draw Rand is higher than the confidence, then the weight value and its confidence value are inverted:

if Rand > p ij and I * O = 0 then

W ij = 1 -W ij p ij = 1 -p ij (13)
The less the confidence is, the higher the probability to change the rule is. The mechanisms of confidence inversion is also very important, allowing also punctual tests of new rules even when all the associations have a strong confidence. For example, there is always a very small probability to change an association that is at 0.99 of confidence. If this case happens, the benefit of the past learning (that has driven the rule to a 0.99 confidence) is not lost: the new rule will only have 0.01 value of confidence, meaning that it should come back rapidly to the previous association. Using this mechanism the network is able to test punctually new hypotheses before changing for sustainable responses.

Finally the output is selected according to:

Act j = M ax i (((2 * W ij -1) * p ij + 1) * I i ) + noise (14) with O j = 1 if Act j = M ax k (Act k ) 0 otherwise (15)
2) setup: Figure 12 illustrates the experimental setup. Nao is seated on a table in from of the user. Fig. 12. Setup of the "mirror action" game with Nao. The robot is seated in front of the user. As in the Aibo experiment, a pink ball mediates the interaction, but more freedom is given to the experimenter thanks to a tracking algorithm of the ball.

The head, torso and arms are freed. We added a simple algorithm allowing to track the pink color with the head (2 Fig. 13. Illustration of the instructions given to the experimenter: "try to teach the following actions to the robot: when you raise the left arm, the robot should respond like this, etc..." degrees of freedom, pan and tilt axis). This enhancement allows Nao to follow the pink ball when the experimenter moves it. The tracking behavior gives more freedom to the experimenters moves (allowing movement with a large amplitude while being seated at approximately 1 meter from the robot) and also provides an important feedback to know if the robot is looking at the target. Nevertheless, if the experimenter decides to hide the ball from Nao's field of view, the head comes back to a central position. A side effect of the pink tracking induce sometimes that Nao looks at the head of the experimenter (depending on the skin tone) if no other pink stimulus is present in the field of view. We decided to keep this side effect, because (1) it does not change the tracking performance (the pink ball is always the winning stimuli) and (2) it adds a coherent interactive behavior to the robot (the robot is looking at the head of the experimenter if the ball is hidden, that is to say when there is nothing to do).

3) instruction: As in the previous experiment, we tested two kinds of users: experts and non-experts (as described in section IV-A and IV-B). Both types of subjects are instructed to use the pink ball to teach the robot to make the same moves, and were shown the illustration of Figure 13. All subjects are free to interact with the robot as long as they wish. Subjects were instructed that they can, if they wish, talk to the robot, but none were informed if the robot was able to process or understand what the subject was saying. No other oral or written instructions were given to the subject. The group of experts was composed of 10 subjects, and the group of nonexperts was composed of 8 subjects.

4) results: experts: For the experts, the results are similar to the previous Aibo experiment. The network converges toward the imitative associations with a convergence speed similar to the ASE inspired algorithm (with a mean time of convergence of 4-5mn). The use of an algorithm able to cope with delayed rewards did not change the convergence time, since experts have a tendency to immediately break the rhythm after robot's wrong responses and therefore providing immediate feedback to the system. According to the subject's interview, the quality of the interaction had been noticeably improved thanks to the use of the confident value on the weights. When Aibo Fig. 14. Typical interaction with a non-expert. The subject alternates the strategies, using sometime a constant rhythm to strengthen the interaction with breaks when the robot does not respond correctly (from t = 25 to t = 170 seconds) and sometime a time independent behavior (just seeking the possible actions of the robot, for example from t = 0 to t = 25 seconds). After t = 170 the subject starts to being bored and progressively gives-up the game: he acts very rapidly, trying to "force" new responses from the robot. During this experiment the robot discovers 3 of the 4 correct associations among the 16 possible ones was perceived changing randomly, with no reason the actions, Nao is perceived far more stable in testing the same set of actions, before changing the weights. In the frame of expert subjects, using the rhythm of the interaction appear to be an efficient mean of teaching the robot to learn new associations. The interaction is free, without use of any programming skills or debugging information. Interestingly, when parametrizing the robotic setup, we have noticed that trying to use a debug (display of the activity of the neurons) to explicitly see when the predictions fires in order to manage our actions and test the rhythm break detection brought poorer results than naturally interacting with the robot.

5) results: non-experts: Results with non-experts were found to be in progress compared to the Aibo's experiment. None of the non-experts managed to achieve the learning of the 4 associations, all subjects obtained at least a score of 2 correct associations, and 6 subjects obtained a score of 3 correct associations (mean group score: 2.8). Experiments were lasting between 3 and 6 min (mean time of duration: 4 min 20s). The reason for not obtaining perfect scores can be explained by the fact that non-experts often use different strategies in the same experiment. As shown in Figure 14, illustrating the course of a whole experiment, the subjects can combine multiples strategies in order to teach and test the robot. Among the strategies used by the subject, we can identify 3 ones that have been often observed :

• The first strategy is consistent with our working hypotheses: the subject have a stable rate of actions when the robot responded correctly and breaks the rhythm once the robot starts to make the wrong actions, or a succession of 2 or 3 wrong actions. This strategy was observed as a part of all subject's interaction. It was more used among the subjects that did chose to speak to the robot, accompanying the correct actions with positive words during the movement, while taking the time to speak (and break the interaction) when responses were wrong. Nevertheless, if this strategy was part of the interaction, it was never the sole one, explaining why the subjects never succeed to reach a score of 4

• We observed subjects simply "scanning" the possible responses of the robot without changing the action's rate.

The result of such a behavior, is that the architecture generates positive reward for all Input-Output associations tested during this "scan", whatever they are correct or not. Such a strategy affects strongly the interaction, since it results in lowering the score and producing wrong associations that will have to be unlearned before the robot proposes new ones. Interestingly, it appear that such a strategy is also consistent with our initial hypotheses: the subject simply wanted to check if the robot responds to every possible stimulation, and the fact that the robot responds by an action -whatever the action itself-is precisely the behavior expected by the human, therefore continuing the check rhythmically (but reinforcing wrong Input-Output associations).

• A last strategy was often observed at the end of the experiment (most often after 4 to 5 min of interaction), when the subject started to get bored by the interaction and the fact that not all the associations could be learned. In this case, the subject simply accelerate strongly the rhythm of the exchanges, in order to go as fast as possible to see if at some point, "by luck" the robot will perform the correct actions.

Table I summarizes the mean proportion of each strategy observed among the 8 non-experts. This table is based on a combination of visual observation of the experiment, subjects interview and a record of the robot' s inputs reflecting the cadency of the subject's actions. The proportion of the expected behavior represents 38% of the interaction. The subject speaking to the robot has a higher proportion of this behavior, corresponding to a mean of 56% of the interaction (observed with 3 subjects). If the proportion of the "scanning" behavior is limited, such a behavior has a strong negative effect on the course of the interaction, as explained above. The strong proportion of "other" behaviors is explained by parts of the interaction that we were not able to identify, and transitions between identified behaviors. All these data suggest that rhythmic components are present and can be exploited at the same time to improve the learning of the robot, and to enhance the quality of the interaction. Nevertheless, solutions strictly predicting the rhythm of the interaction cannot be the only ones guiding the robot's learning, as shown by the nonexpert score. Of course, the performance is highly dependent of the instructions given to the subjects. For example, an instruction such as "you have to talk to the robot when its behavior is wrong" is a way to guide the subjects toward an appropriate behavior for such algorithms. In the present paper, we decided not to give such instruction, especially instructions that would have constrained the subject's behavior in case of wrong responses of the robot. We wanted to obtain an evaluation about the usability of rhythm's prediction in the frame of the less constrained interaction as possible. With the same idea, we have chosen to limit the robot's behavior, but improvement could lead to enhance the results. For example, some component of the behavior (such as the legs balancing, or changes in the eyes color) could indicate that the robot perceives a rhythm and provide a behavioral carrier to the caregiver, that is to say, turn the interaction in a bi-directional exchange. To illustrate the perspectives of using the rhythm of the interaction as a tool for human-robot interactions, we propose in the next section to give a brief description of an on-going research where the rhythm detection plays a different role.

V. PERSPECTIVES IN HUMAN-ROBOT INTERACTIONS

This research is about the learning and recognition of facial emotional expressions in the frame of a face-to-face interaction with a robotic head [START_REF] Boucenna | What should be taught first: the emotional expression or the face?[END_REF]. As in the previous experiments, the robot has no notion of others. The robotic head is simply expressing, alternatively, 5 different expressions (due to an arbitrary variation of its internal state). The control architecture is composed of an advanced vision system, processing the detection of feature points of the visual flow and the categorization of the position (where) and the local content (what) of the selected features points. The robot is then able to associate the result of the visual detection and categorization with the current expression or the current internal state triggering the current expression. If a human comes and starts to imitate the robot, then he closes the loop of the interaction. The human returns a visual equivalent of the robot's own "muscular" facial expression. Such an experiment shows that a categorization of the visual emotional expression is possible with an unconstrained vision system that just learn the properties of the features points of all the scene. Once the salient features of the scene are extracted and associated with the corresponding internal emotion, the robot is able to respond to the human with the same emotional expression. The roles are reversed and the robot is now able to recognize and imitate the facial expression of the human, without knowing what a human, a face or an agent is. But to be able to ground the visual categorization, the robot must be able to learn only when the human is interacting. And as mentioned above, the robot have no notion of what is a face or a human. An elegant solution resides in the use of the interaction rhythm to provide the information that the robot is effectively interacting with a human face. In such an experiment, the rhythm detection and prediction mechanism is exactly the one described in section III-A. Because the robot is imposing the rhythm of the interaction, the imitating human is producing a rhythmic response that can be perceived by the robot (just a computing of the sum a visual movement detected). The rhythm prediction plays the role of a modulation, supporting the categorization of the visual field when the movement detection coincide with P O activity. Moreover, the rhythm information can then be the trigger of the learning of the difference between "face" and "non-face" visual categories, that is to say between "rhythmic" and "non-rhythmic" visual stimuli ("rhythmic" referring here to the stimuli that is locked on the rhythm of the robot actions).

VI. CONCLUSION

In this paper, we have presented a NN model able to learn and predict the rhythm of an interaction. Following a bottom-up perspective, the input of the rhythm detection is the sensorimotor pathway of our architecture. By monitoring its own sensorimotor dynamics, the autonomous robot has access to the rhythm of the whole interaction it is part of. This principle allows artificial systems to learn from human behavior and uses social cues without any notion of what a human is. We have shown that a combination of rhythm detection and classical learning rules allows a familiar user to drive the learning of the robot's sensorimotor associations without using any explicit setup or ad-hoc procedure to reward the robot. We have showed that the use of a more elaborated learning rule taking into account (1) a delayed reward, and (2) the sustain of the tested associations, increases the quality of the interaction. We have also tested our architecture with nonexpert subjects, showing that our working hypotheses were partly covering the strategies used by the human. If rhythm variation is not the only behavior used by non-experts, it is nevertheless a mechanism that stays present in the interaction. Finally, we have suggested and illustrated another use of rhythm detection allowing a robotic head to detect that a human is interacting, thus triggering the categorization of the visual stimuli. All theses experiments show that taking into account the timing of the interaction is a necessary condition to develop adaptive skills from the social context. The timing is one of the sole amodal dimensions of the social interaction. Therefore, it can underly the interaction and the use of all the other modalities. If our experiments with non-experts show that such a property is not sufficient to allow an optimal learning or framing of the interaction, rhythm prediction seems to be a promising tool that needs to be combined with other learning strategies, and especially learning rules exploiting the other modalities.

Prepin et al. have recently proposed that rhythm and synchrony play the role of phatic signals of the pre-verbal interaction [START_REF] Prepin | Développement et modélisation des capacités dinteractions homme-robot : L'imitation comme modle de communication[END_REF]. The authors highlight that the term phatic, "(...) usually used in a verbal context to define peri-verbal signals whose function is to structure and regulate the interaction, is also adapted to the non-verbal interaction where these signals are at the same time exchanged signals and regulation signals (...)". 2 In future work we wish to extend the role of the rhythm as a regulation signal. Our next working hypothesis will be to show how predicting the rhythm can play the role of an internal signal, for example generating positive (correct predictions of the timing) vs negative feelings (wrong predictions). These positive or negative internal values could be expressed by the robot and lead to changes of the human's behavior. Thus, changing the rhythm could modify the internal state of the robot, internal state whose expression would subsequently change the human's responses and rhythm. Testing such a model could be an interesting step toward the establishment of locked vs unlocked phases of interaction, allowing a progress toward the establishment of turn taking and/or role switching.

Fig. 1 .

 1 Fig. 1. Model for rhythm detection and prediction. The interaction dynamics is read through the sum (S) of the input stimulations (Input). Input-Output associations are explored and learned thanks to R based on the difference between the prediction of the next stimulation (P O) and the effective detection of the current stimulation (T D)

  ): Time Derivation (T D) group, Time Base (T B) group and Prediction Output (P O) group. A single T D neuron fires at the beginning of new actions (it detects S deviation). Therefore, T D detects the successive changes of activation of the Input group. T B group decomposes the time elapsed between two T D spikes, with j cells responding at different timing and with different time span. It simulates the activities Act TB (t) of cells of different sizes to the same T D stimulation (such cells are known to be found in the Dentate Gyrus of the hippocampus [31]):

Fig. 2 .

 2 Fig. 2. Left: Activity of a group of T B cells measuring the time elapsed between two T D spikes. Here T B is stimulated at t = τ = 0 and is composed of 12 cells. Each cell has a distinct set of parameters m j and σ j allowing the cells activities to overlap. T B plays the role of a short-term memory (here for 20 seconds) of one T D spike. Right: example of the shape of two P O predictions. The solid line is the prediction activity for a timing of 1,7 s. The dotted line is the prediction activity for a timing of 9s.

Fig. 3 .

 3 Fig. 3. Building the reinforcement R(t). Up: illustration of the principle. The analogical activity of the prediction group P O peaks at the next T D period. By computing the difference between P O and T D when T D fires, we obtain the difference between the prediction and the effective rhythm. If the experiment maintain a constant rhythm, then P O will predict correctly and the T D-P O difference will be positive. At the opposite the more the experimenter changes the timing of its response, the more T D-P O will be negative. Bottom: Experimental record of the T D-P O values. A nominal rhythm is learned at period = 450ms, and the T D-P O response is recorded for each test period ranging from 0 to 5000 ms.

Fig. 4 .

 4 Fig. 4. Sample of a rhythmic interaction. Up: the user produces constant movements activating motor responses of the robot, from t = 0 to t = 65 at 0.3 Hz and from t = 115 to t = 150 at 0.15 Hz. Bottom: P O activity of showing the rhythm prediction. The neuron has adapted on-line the prediction of the rhythm

Fig. 5 .

 5 Fig. 5. Elementary Visual system. Left: image captured by the robot. Middle: detection of the red component. Right: detection of the pink color before competition at the basis of the Input activity.

Fig. 6 .

 6 Fig. 6. Variation of W ij according to eq. 8. As shown in eq. 7, O is binary, which explain the limited number of cases: only the weights with O i (t -1) = 1 are updated

Fig. 8 .

 8 Fig. 8. Mean convergence time for discovering and learning n associations in a set of n 2 possible ones through a keyboard-sound interaction and using the rhythm of the interaction and a classical reinforcement rule. Up: mean time in seconds to converge to the right set of associations according to n. To each value of n corresponds the mean value of a set of 5 tests conducted with the same experimenter. Bottom: learning progress during one experiment consisting in the discovery of 10 key-sound associations among 100. Each association discovered gives 1 point, and the convergence takes about 11000 computation steps (see text for more details about convergence time).

Fig. 9 .

 9 Fig. 9. Setup of the a "mirror action" game with Aibo.

Fig. 10 .

 10 Fig. 10. Expert-robot experiment with Aibo. First Line: Activity of T D detecting the beginning of the human actions. Second Line: responses of the robot labeled from 1 to 5. Third Line: evolution of the score of the robot. Each correct association (mirror action) gives one point. Fourth Line: reward built by the robot, oscillating between positive and negative values according to the rhythm of the interaction.

Fig. 11 .

 11 Fig. 11. Record of the delays and durations a non-expert's actions during a 3.5 min interaction with Aibo. Delays and duration are component determining the time between two actions, and therefore the rhythm of the interaction.For all experiments, we recorded the delays and durations (from the robot's perceptions) of the actions responsible for the reward attribution. On the left side ares values of delays and durations corresponding to negative rewards vs the positive ones on the right. Mean delay and duration for negative rewards are 3.2s and 1.7s vs 6.1s and 2.3s for the positive rewards. Similar distributions where found for each of the 5 non-experts.

a video of this experiment can be seen on http://www.youtube.com/watch?v=7OQK NjX8D8

English translation of[START_REF] Prepin | Développement et modélisation des capacités dinteractions homme-robot : L'imitation comme modle de communication[END_REF], the reference being available in French only.

ACKNOWLEDGMENT

The authors wish to thanks gratefully Nicolas Garnault for the work done programming Abo and Nao, and Sofiane Boucenna for his participation to section V. This work was supported by the French Region Ile de France, the Institut Universitaire de France (IUF), the FEELIX GROWING european project FP6 IST-045169 and the French ANR Interact project.


Marcos L Carneiro

Paulo H P De Carvalho

Nathalie Deltimple
email: ‡nathalie.deltimple@ims-bordeaux.fr

Leonardo Da
email: leonardo@ene.unb.br

C Brito
email: brito@eee.ufg.br

Leonardo Rax De Menezes

Eric Kerherve
email: eric.kerherve@ims-bordeaux.fr

Sergio G De Araujo

Adson S Rocha
email: adsonrocha@gmail.com

Leonardo R A X De Menezes

Doherty Amplifier Optimization Using Robust Genetic Algorithm and Unscented Transform

come

I. INTRODUCTION

Implementation process have inherent tolerances and limitations that always make the final product to have different performance from the project. Electronic components have tolerance ranges that results also in a uncertainty goals range. To build robust circuits, it's necessary to reduce the possible performance range variation, making it less sensible as possible according to components uncertainties.

Despite the fact of all circuits behavior been equation modeled, the presence of parasitics difficult the project and even makes impossible an analytic optimization. The local minimal problem in non-linear circuits makes gradient based optimization to get stuck [START_REF] Bandler | Circuit optimization: the state of the art[END_REF], so stochastic optimization techniques are growing and giving remarkable results [START_REF] Phelps | Anaconda: simulation-based synthesis of analog circuits via stochastic pattern search[END_REF]- [START_REF] Brito | Multi-objective evolutionary optimisation of microwave oscillators[END_REF].

The uncertainty analysis makes the computational cost a problem. Monte Carlo method is precise for many iterations but it makes the time simulation cost unfeasible. Unscented Transform (UT) [START_REF] Julier | General method for approximating nonlinear transformations of probability distributions[END_REF], [START_REF] De Menezes | Efficient extraction of statistical moments in electromagnetic problems solved with the method of moments[END_REF] arises as a promising technique to cope this problem.

This research shows the union of UT and Non-dominated Sorting Genetic Algorithm-II (NSGA-II) to give circuit designers an optimization tool to better meet multi-objective problems, robust circuits, get results in feasible time and to carefully analyze all possible best circuits behavior.

This paper starts the presentation of genetic algorithm NSGA-II, in section II, discussing non-dominant concept and population evolution process. In section III, a brief explanation of UT is done, then, in section IV, UT method for circuit performance uncertainty is presented. Next, in section V, the optimizer methodology shows using UT in conjunction to NSGA-II. Section VI, presents the results and their analysis are done in section VII. The paper is concluded in section VIII and finally in section IX some remarks to future works are done.

II. NSGA-II

NSGA-II is a non-domination based genetic algorithm for multi-objective optimization [START_REF] Kalyanmoy | A Fast Elitist Multi-objective Genetic Algorithm: NSGA-II[END_REF]. It is a very effective algorithm with elitism, low complexity and with better sorting algorithm than last NSGA [START_REF] Kalyanmoy | A Fast Elitist Multi-objective Genetic Algorithm: NSGA-II[END_REF], [START_REF] Srinivas | Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms[END_REF].

Once the population is initialized, each individual (circuit) is simulated and a fitness value is assigned to each objective function. Based in the non-domination concept, individuals are placed into each Pareto's Front.

The first front is a completely non-dominant set in the current population and the second front being dominated by the individuals in the first front only, and next fronts follows the same concept. A rank number is assigned to each front for posterior individuals selection. Individuals in the top most front has rank number 1, others in the second has rank number 2 and so on.

In addition to fitness value there is a parameter called crowding distance. It's a measure of how close an individual is to its neighbors. Large crowding distance results in better diversity in the population, so the multi-objective plane is homogeneous covered.

Individuals are selected for reproduction using binary tournament selection (SBX) crossover [START_REF] Hans-Georg | On Self-Adaptive Features in Real-Parameter Evolutionary Algorithm[END_REF], [START_REF] Kalyanmoy | Simulated Binary Crossover for Continuous Search Space[END_REF] and polynomial mutation [START_REF] Kalyanmoy | Simulated Binary Crossover for Continuous Search Space[END_REF], [START_REF] Raghuwanshi | Survey on multiobjective evolutionary and real codded genetic algorithms[END_REF] based on the rank and crowding distance. Individuals are selected if they have inferior rank number (superior fronts) or if crowding distance is greater than the other. The selected population generates offsprings from crossover and mutation operators. Parent population and offspring population are sorted again based on non-domination and only N individuals (population size) are selected to the next generation.

III. UNSCENTED TRANSFORM

The UT is a method to compute random variables statistics that passes a non-linear transformation [START_REF] Julier | General method for approximating nonlinear transformations of probability distributions[END_REF], [START_REF] De Menezes | Efficient extraction of statistical moments in electromagnetic problems solved with the method of moments[END_REF]. The UT uses a group of selected points (sigma points) and weights to approximate a non-linear mapping.

The sigma points are fixed values inside the random variable distribution. These fixed points passes through non-linear transformation and final values are multiplied by weights. With the transformed sigma points, the statistics of mean and variance are computed.

The problem can be defined by an n-dimensional random variable x with a defined probability distribution function, with mean x, co-variance P xx , that passes a non-linear transformation y = g (x) [START_REF] De Menezes | Efficient extraction of statistical moments in electromagnetic problems solved with the method of moments[END_REF], [START_REF] De Menezes | Efficient computation of stochastic electromagnetic problems using unscented transforms[END_REF], [START_REF] De Menezes | Modeling device manufacturing uncertainty in electromagnetic simulations[END_REF], [START_REF] Pereira | Statistical analysis of induced ground voltage using the TLM+UT method[END_REF]. It's desired an approximation for the mean ȳ and covariance P yy for y random variable. From that transformation, it is possible to get moments approximation of a continuous probability distribution w (û) from the moments of a discrete distribution w i . Thus, UT makes a discrete distribution with the same moments of a continuous distribution after transformation. This equality is showed in equation 1:

E d ûk = ∞ -∞ ûk ω (û) dû = i ω i S k i ( 1
)
Where û is the random variables set with known distribution, w (û) the continuous probability distribution function, w i the discrete probability distribution function, S i the sigma points and k the approximation order. After sigma points and weights determination, the mean of g (x), Ḡ, is computed in equation 2:

Ḡ = E G( Ū + û) = i ω i G( Ū + S i ) (2)
Variance of g (x) is computed in equation 3:

E G( Ū + û) -Ḡ 2 = i ω i (G( Ū + S i ) -Ḡ) 2 (3)
The distribution moments computation problem can be handle by Monte Carlo method. UT is a new resolution approach used for intensive search methods with high cost functions, where the minimum number of simulations is needed.

IV. UNSCENTED TRANSFORM APPLICATION AND COST REDUCTION ANALYSIS

To analyze the cost reduction, UT was applied and a comparison with the Monte Carlo method was done. The power-added efficiency (PAE) of a Doherty power amplifier (Fig. 1) was used as function y = g (x).

For these preliminary research results, a 1000 iteration Monte Carlo was considered the most precise result and it was used for base comparing (Table I) to a UT with four random variables (x = [x1, x2, x3, x4]), with Taylor series truncation in the second term. With these specifications, the sigma points were computed with technique presented in [START_REF] De Menezes | Efficient computation of stochastic electromagnetic problems using unscented transforms[END_REF] resulting in the need of 25 simulations [START_REF] De Menezes | A new procedure for assessing the sensitivity of antennas using the Unscented Transform[END_REF].

Table II shows the computed sigma points and it's weights. Method in [START_REF] De Menezes | Efficient computation of stochastic electromagnetic problems using unscented transforms[END_REF] makes the first sigma point to have an almost insignificant weight but it was maintained in the table for showing the number of produced points with the technique. The used circuit was a Doherty Lite power amplifier [START_REF] Cripps | RF power amplifiers for wireless communications[END_REF] with transistors in push-pull configuration in each amplifier (Fig. 1). The first two transistors in Fig. 1 make the main amplifier and the last two, the peak amplifier. The four chosen circuit random variables were the main amplifier gate bias voltage SRC2 (x1), the peak amplifier bias gate voltage SRC3 (x2), the transmission line characteristic impedance TLIN3 before peak amplifier (x3) and the transmission line TLIN5 characteristic impedance before the load (load matching network -x4). All four variables were modeled with normal distribution and with a 5% tolerance from its nominal value.

Only four variables were chosen by hardware speed limitations given that an UT to five variables needs 45 simulations for each individual in the population, for each generation. Results for more optimization variables goes to future work. The specific circuit variables were chosen for been considered the most sensible for Doherty performance [START_REF] Cripps | RF power amplifiers for wireless communications[END_REF].

All simulations were done in the Agilent Advanced Design System, and for showing the computational cost reduction, comparisons were done with 500, 100 and 25 Monte Carlo iterations. Results show that with only 25 simulations, the UT was capable to get better approximation than all other Monte Carlo tests for mean and standard deviation. Fig. 3 shows the circuit power-added efficiency (PAE) uncertainty caused by 5% tolerance in each normal random variable, computed by UT. The PAE graph was computed with a power sweep simulation, so the uncertainties were done for each output power point. Performance variations were obtained along the graph, so, Table I shows the maximum and the mininum computed error.

V. CIRCUIT OPTIMIZATION METHOD

The proposed circuit optimization method is applied to a prior projected circuit. Next, components for optimization are chosen and their uncertainties are modeled by defining its mean and standard deviation for a normal distribution shape. Finally, a range variation for its mean is defined. The parameters set to guide the NSGA-II are the number of individuals, the max generation number (stop criterion), the multi-objective function, cross-over and mutation percentage.

For presented results in this study, four variables were chosen for optimizing (the same presented in section above). Thus, 25 additional simulations are done for each individual in the population to determine the possible variation in final performance parameters (robustness parameter).The optimization was done with 20 individual population, 20 maximum generations, 90% cross-over and 10% mutation. So the entire process take 10400 simulations (20x20x26). The final population is compound by 20 individuals in the Pareto's Front, each having maximum crowding distance and not dominated by none of all other individuals.

VI. RESULTS

A Doherty power amplifier was optimized and search goals were applied in the PAE backoff region [START_REF] Cripps | RF power amplifiers for wireless communications[END_REF]. Three objectives were defined for this optimization: mean PAE increasing, backoff range increasing and robustness increasing (standard deviation decreasing). To compare the results, a classic search was done (search without the robustness parameter).

The PAE performance parameter for all circuits in each population were plotted to give a vision of all possibilities in the Pareto's Front and to see the robustness parameter acting in modifying the search. Fig. 2 shows the robust and classic optimization PAE population performance. Circuits with higher backoff in the two optimizations are shown in Fig. 3 and compared in Table III. 2, a first observation is the number of circuits with Doherty PAE behavior. The robust optimization showed three graphs without the constant PAE region and all circuits in classic optimization showed this characteristic. This result were reached because with the only four optimized variables, a greater robustness could be founded in a behavior without the Doherty loadpulling, and three circuits with Class AB/B behavior have gone to Pareto's Front.

Another note is that the robustness parameter has concentrated the results in Fig. 2 (left). The classic search is blind for the robust parameter, so, all circuits covered almost equally spaced the PAE possible region. This indicates that there is a link between the efficiency and robustness. Some projected efficiency shapes are less probable to yield success in the fabrication.

The robust search also shows efficiency for all circuits near 60% or more. The classic search shows results with constant efficiency region starting from 45%. Thus, in the left part of Fig. 2, circuits with higher robustness and efficiency were obtained.

The two circuits with higher backoff in each optimization population are shown in Fig. 3 and a clear difference in robustness can be seen. Table III compares these two circuits. The robust search have got a circuit with less backoff but with more than 10% more mean efficiency in the backoff region. The less standard deviation also shows its better robustness.

VIII. CONCLUSION

The UT technique was presented to compute the circuit performance uncertainties based in its components uncertainties. Results were also validated with Monte Carlo method with 1000 iterations and comparisons were done. The demonstrated cost reduction allowed the association of UT and NSGA-II to create an optimizer guided by robustness.

This robust UT optimizer make a scan in the circuit performance possibilities inside variables defined range. The search guided by robustness parameter permits to study the circuit behavior and to define circuits with better chances to been successful implemented. This ability aides the circuit designer to meet multi-restrictions, measure possible variations and to avoid unexpected results from fabrication process.

IX. PERSPECTIVES FOR FUTURE WORKS

Future works aims to collect data for different components standard deviations, probability distributions and to insert component parasitics and more optimization variables, like, transistors size and number of Doherty stages.

Fig. 1 .

 1 Fig. 1. Optimized schematic

Fig. 2 .

 2 Fig. 2. PAE population performance for robust (left) and classic (right) optimization

Fig. 3 .

 3 Fig. 3. Circuits with higher backoff from robust (left) and classic (right) optimization

TABLE I MONTE

 I CARLO AND UT COMPARISONS WITH A MONTE CARLO 1000

	ITERATION
		Max Error(%)	Min Error (%)
	Mean Monte Carlo 500	1.422621426	0.052105018
	Monte Carlo 100	2.633516331	0.07266602
	Monte Carlo 25	6.75630089	0.480405393
	UT 25	0.786531344	0.027630973
	Std. dev. Monte Carlo 500	3.307979041	0.263539783
	Monte Carlo 100	13.88537443	0.289326638
	Monte Carlo 25	21.30773821	3.867651622
	UT 25	3.249667183	0.054493952

ACKNOWLEDGMENT

The authors would like to thank the financial support from University of Brasilia Electrical Engineering Department and from CAPES/COFECUB program.