Claude Touzet
email: claude.touzet@iuspim.u-3mrs.fr

Neural reinforcement learning for behaviour synthesis

Keywords: Neural Q-learning, reinforcement learning, obstacle avoidance behaviour, self-organising map, autonomous robotics

We present the results of a research aimed at improving the Q-learning method through the use of artificial neural networks. Neural implementations are interesting due to their generalisation ability. Two implementations are proposed: one with a competitive multilayer perceptron and the other with a self-organising map. Results obtained on a task of learning an obstacle avoidance behaviour for the mobile miniature robot Khepera show that this last implementation is very effective, learning more than 40 times faster than the basic Q-learning implementation. These neural implementations are also compared with several Q-learning enhancements, like the Q-learning with Hamming distance, Q-learning with statistical clustering and Dyna-Q.

INTRODUCTION

In this paper, we present the results of research aimed at improving reinforcement learning through the use of artificial neural network implementations. Reinforcement learning proposes the synthesis of robot behaviours with the help of reinforcement functions. A reinforcement function uses a measure of the robot's performance to guide the learning. It is no longer necessary to write an algorithm generating the corresponding behaviours, something particularly interesting when such algorithms are not available (too complex, too expensive, etc.). Moreover, the synthesised behaviour integrates the local performance (i.e., the heterogeneity ) of the sensors, the motors, the noise of the environment, etc.

Reinforcement learning applications imply the mapping of situations to actions in huge situation-action space. On the other hand, the duration of the learning phase must be as short as possible to reduce engineering costs of development. Therefore, generalisation is of major importance in the process. Neural network generalisation, as shown by connectionist industrial developments, is very attractive. In this paper, we review neural implementations of Q-learning and also propose two new implementations.

In section 1, the real mobile robot Khepera and the environment of our experiments are described. This section also presents the reinforcement learning function used for the synthesis of an obstacle avoidance behaviour. The following section 2 reviews the Qlearning method, certainly the most used reinforcement learning method. Section 3 points out the credit assignment problem of the Q-learning method and briefly describes several enhancements. Section 4 introduces the first neural network implementation of the Qlearning, pointing out its advantages and limitations. Section 5 presents our proposal for a multilayer perceptron implementation of Q-learning. In section 6, a second neural network implementation is proposed using a self-organising map. Comparisons between the different implementations of Q-learning are presented in section 7. Results are discussed in section 8. Concluding remarks are given in section 9.

THE MINIATURE MOBILE ROBOT KHEPERA

Khepera is a miniature mobile robot [START_REF] Mondada | Mobile Robot Miniaturisation: A Tool for Investigation in Control Algorithms[END_REF] having a diameter of 6 cm and a weight of 86 g (figure 1). Two continuously independently controllable wheels allow the robot to move around. Eight infra-red sensors help the robot to perceive its environment. Their detection range is between 5 and 2 cm. Sensor data are real values between 0.0 (nothing in front) and 1.0 (obstacle nearby), each coded in 10 bits. All the measurements depend significantly on various factors like the distance from the obstacle, the colour, the reflectance, the vertical position, etc. The heterogeneity between sensors is important (figure 2) and reflects the sensor manufacturing process. The computational power of the robot is equivalent to a M68331. Energy autonomy is thirty minutes. Figure 2. Maximum value of the sensor response associated to a small obstacle (a pen) rotating around the robot at a constant distance of 2 cm. The sensor value is drawn as a line segment starting at the sensor location and oriented to the obstacle. The length of the segment represents the measured sensor value (the grey circle represents a value of 1.0 which is only achieved by sensor 4 and 8). The obstacle right in front of sensor 4 generates a response value of 1.0, but the same obstacle in front of sensor 5 generates a response value of 0.4. Sensor 4 is then two times more effective than sensor 5.

Task, environment and indicator

Task

The task Khepera has to perform is to move forward when possible and avoid obstacles. Two behaviours are involved. One, with a higher priority, moves forward. A second proposes avoidance actions. The first behaviour is so simple, i.e., move forward when nothing is detected by the sensors, that it is of no interest here. However, the second behaviour involves knowing how much to turn and in which direction so as to avoid the obstacles. Our goal in dealing with this particular task is not to solve a problem for which solutions were proposed years ago [START_REF] Walter | An Imitation of Life[END_REF], but to work with a problem just complex enough to be not trivial, but also simple enough to allow a good understanding of the implications of neural implementations. The Braitenberg vehicle [START_REF] Braitenberg | Vehicles: Experiments in synthetic psychology[END_REF] described in the commercial package of Khepera will serve us as a benchmark for our experiments. The avoidance algorithm used is described in figure 3.

Let I be the sensor vector, I = {i 1 , i 2 , i 3 , i 4 , i 5 , i 6 , i 7 , i 8 }, let A be the speed vector, A = {a l , a r } a r = c 1 . i 1 + c 2 . i 2 + c 3 . i 3 + 10 a l = c 3 . i 4 + c 2 . i 5 + c 1 . i 6 + 10 where c 1 , c 2 and c 3 are negative constants. We choose for these constants the value given by the commercial package: c 1 = -17, c 2 = -11, c 3 = -7

Figure 3. The obstacle avoidance used by the Braitenberg vehicle that will serve as benchmark for our experiments.

Environment

The environment is an arena the size of a sheet of A4 paper. Obstacles are film cans or whatever is suitable (lipsticks, erasers, etc.). Obstacles are put in the arena at the beginning of the experiment (figure 4). Figure 5 shows a trace of the Braitenberg avoidance behaviour of Khepera in the arena.

Indicator of the task

The distance to the obstacles (G(t)) measures the correspondence of the robot's behaviour with the target behaviour. For each obstacle encountered by the robot during the experiment only one value is memorised which is the shortest distance. G(t ) = DO(t ) / t ; where DO(t ) is the sum of the shortest distances from the beginning of the experiment (the higher the sensor value, the shorter the distance to the obstacle). The graph is averaged over seven runs, the mean and standard deviation1 are displayed. This graph will help us evaluate the training procedures proposed in the following material. The results reported are averaged over 7 runs. The robot comes really near to the obstacles (sensor value approximately equal to 1.0).

Reinforcement function

The robot receives the following reinforcement signals during the learning phase: +1 if it is avoiding, or -1 if a collision occurs, or 0 otherwise. The robot is avoiding when the present sum of sensor values is smaller than the last one, the difference been greater than 0.10. A collision occurs when the sum of the six front sensor values is greater than 2.90 or the sum of the two back sensor values is greater than 1.95. Threshold values like (0.10, 2.90, 1.95) have been determined after extensive experiments. In front of a wall (e.g., the boundary of the arena) a collision corresponds to a distance less than 2 cm. This distance value of 2 cm. is inferred from the sensor performance (fig. 2). It does not necessary mean that the robot touched the wall.

The same absolute value is used for positive and negative reinforcement signals, despite the fact that a collision may be considered much more important than an avoidance action. In the literature, many authors attach more importance to negative rewards, sometimes as much as 100 times more effect on the learning rule. However, we consider the reinforcement function as a qualitative criterion and we do not want to introduce qualitative bias through weighting of the rewards (bias are nevertheless unavoidable: a bias is introduce by any choice of the threshold values).

Q-LEARNING

Reinforcement Learning

Reinforcement learning is the learning of a mapping from situations to actions so as to maximise a scalar reward or reinforcement signal [START_REF] Kaelbling | Learning in embedded systems[END_REF]. A robot learns a given behaviour by being told how well or how badly it is performing as it acts in each given situation.

As feedback, it receives a single information item from the world. By successive trials and/or errors, the robot determines a mapping function which is adapted through the learning phase. For this purpose, numerous reinforcement learning algorithms are available (e.g., TD(λ), AHC [START_REF] Holland | Extending the adaptive heuristic critic and Q-learning: from facts to implications[END_REF]), among which the Q-learning method is certainly the most used.

Q-learning

Reinforcement learning synthesises a mapping function between situations and actions by maximising a reinforcement signal. Q-learning [START_REF] Watkins | Learning from Delayed Rewards[END_REF] algorithms store the expected reinforcement value associated with each situation-action pair, usually in a look-up table. Three different functions (figure 7) are involved: memorisation, exploration and updating [START_REF] Sehad | Reinforcement Learning and Neural Reinforcement Learning[END_REF]. Figure 8 describes the Q-learning algorithm. Figure 7. Q-learning method functional decomposition. In response to the present situation, an action is proposed by the robot memory. This action is the one that has the best probability of reward. However, this proposition may be modified by the evaluation function to allow an extensive exploration of the situation-action space. After the execution of the action by the robot in the real world, a reinforcement function provides a reinforcement value. This value, here a simple qualitative criterion (+1, -1 or 0), is used by the updating algorithm to adjust the reward value (Q) associated with the situationaction pair. The learning is incremental, because the acquisition of the examples is carried out in real situations.

1. Initialisation of the robot memory: for all situation-action pairs, the associated Q value is 0 (i.e., Q (i , a )= 0). 2. Repeat : a -Let i be a world situation. b -The evaluation function select the action a to performed: a = argMax (a ) (Q (i , a' )) where a' represent any possible action in situation i .

The exploration process modify the selected action to explore the situation-action space:

a* = a + ∆a ∆a is usually a randomly selected with a Gaussian distribution N (0, σ), σ usually decreases as the learning proceed. c -The robot executes the action a in the world. Let r be the reward (r can be null) associated with the execution of the action a in the world. d -Update the robot memory:

Q t+1 (i , a ) = Q t (i , a ) + ß(r + γ . Max (Q t (i' , a' )) -Q t (i , a )).
eq. 1

where i' is the new situation after having carried out the action a in situation i , a'' is any action which is possible from state i' and 0 < ß, γ < 1.

Figure 8. A general algorithm for the Q-learning method.

A look-up table implementation of Q-learning was used with the miniature robot Khepera to generate an obstacle avoidance behaviour. In all our experiments, ß = 0.9 and γ = 0.5.

For practical reasons, each sensor value is coded as 1 bit (the threshold is 0.2). If the measured value is below the threshold then the sensor bit value is 0, otherwise it is 1.

Therefore, the total number of possible situations is restricted to 2 8 (i.e., 256). For the same practical reasons, the total number of actions is reduced to 5 different speeds per motor, reducing the total number of possible actions to 25. Figure 9 gives the size of the look-up table for all the possible coding.

1 bit 2 bits 3 bits 4 bits 5 bits 6 bits 7 bits 8 bits 9 bits 10 bits Size 6400 1.6 10 6 4. proportion of moves executed by the obstacle avoidance module that received positive reinforcements since the beginning of the experiment. Graphs are averaged over 5 runs, standard deviation is also reported.

A trace of the behaviour of the miniature mobile robot Khepera after learning is given in figure 12. The trajectory appears not as smooth as with the Braitenberg vehicle. One of the reasons is certainly the 1 bit coding per sensor (where the Braitenberg vehicle uses 10 bits).

Star t

Figure 12. Trace of the Q-learning avoidance behaviour of Khepera after 4000 learning iterations. There are 70 iterations. It is the same environment as fig. 5.

Determining the number of learning iterations required is a difficult task. To this end, we use an indicator: the total number of non-null Q values in the look-up table (figure 13). In our case, we choose 4000 learning iterations, i.e., 2/3 of the maximum number of situation-action pairs that can be experienced. It must be reported that, even after 4000 learning iterations, the synthesised behaviour is not perfect. Figure 14 displays the graph of Lafter learning, there are still negative reinforcements experienced, but much less than what a pure random behaviour displays.

Moreover, the Braitenberg implementation also experiences negative reinforcements.

CREDIT-ASSIGNMENT PROBLEM

Any difficulty in the use of Q-learning is the result of a situation space being so large that, combined with all possible actions, an exhaustive exploration of all situation-action pairs is impossible, as is also an exhaustive memorisation. For example, in the case of the mobile robot Khepera, the total number of possible situations is ((2) 10 ) 8 , not far from 10 24 . Even if the number of possible speeds per wheel is reduced to 25, the size of the situation-action space is 3 10 25 . Working with a real robot implies mechanical constraints: in this case, an action takes approximately 200 ms to be performed. In one minute, a maximum of 300 actions can be executed. Therefore, there is an incredibly small number of explored situation-action pairs versus unknown situation-action pairs. This problem is called the structural credit-assignment problem. A solution to this problem is the generalisation process: the use of experienced situation-action pairs to induce ways of dealing with new unknown situations.

Several improvements emphasising generalisation have been proposed. Mahadevan et al. uses Hamming distance to generalise between similar situations; the same authors also use clusters to generalise across similar situation-action sets. Sutton proposes the Dyna-Q model to speed up propagation through time of the Q values. [START_REF] Mahadevan | Automatic Programming of Behavior-based Robots using Reinforcement Learning[END_REF] The main idea of this refinement is to compute a Hamming distance between the world situation i and similar situations in order to apply the updating function on all of them. Only one action is carried out, but many similar situations are updated using the same reinforcement value. The Hamming distance between any two situations is simply the number of bits that are different between them. Bits can be of different weights (i.e., weighted Hamming distance). Two situations are distinct if the Hamming distance between them is greater than a fixed threshold (figure 15). This generalisation method is limited to syntactic criteria: it is dependent on the coding of the situations. In this example, the world situation is i 3 , the executed action is a 6 , the threshold value for the Hamming distance is 1.

Q-Learning with weighted Hamming distance

a 1 i i 1 a a 2 a 3 a 4 a 5 a 6 i 2 i 3 i 4 i 5
Q (i 3 , a 6 ) is updated, but also Q (i 2 , a 6 ) and Q (i 4 , a 6 ).
Experiments with Khepera have been carried out using a Hamming distance of 1 (figures 16 and 17). As one can see, the performance is not high (but worse with a Hamming distance of 2). The look-up table used is the same as in the previous section. However, learning is sped up through the use of the Hamming generalisation process. Therefore, the total number of learning iterations has been reduced to 2000, i.e., three times (figure 18) the proportion of non-null Q values in the look-up table (fig. 13). It must be pointed out that the generalisation process used here may conduct to invalid actions. For example, when a forwards action is positively rewarded, the generalisation process also rewards the same forwards action in front of small obstacle (only 1 or 2 sensors activated). and2 (H2). These percentages are between three (H1) and eight (H2) times the maximum value obtained for classical Qlearning. Some of these values conduct to invalid actions.

Q-Learning with statistical clustering

Mahadevan et al. [START_REF] Mahadevan | Automatic Programming of Behavior-based Robots using Reinforcement Learning[END_REF] propose an other generalisation method less dependent on the coding of the situations: statistical clustering. Here, each action is associated with a set of situations giving information concerning the usefulness of performing the action in a particular class of situations. Clusters are sets of "similar" situation instances that use a given similarity metric. All situations that appear in the same cluster are updated together (figure 19). Here again, generalisation is limited to syntactic criteria.

a 1 i i 1 a a 2 a 3 a 4 a 5 a 6 i 2 i 3 i 4 i 5 i 6 Cluster c 2 associated with a 2 Q Figure 19
. Generalisation using statistical clustering. If one of the situations of the cluster c 2 is the world situation and a 2 as been carried out then all Q values of the cluster c 2 are updated. In this example, the world situation is i 3 and the action carried out is

a 2 , then Q (a 2 , i 3 ) is updated together with Q (a 2 , i 1 ) ,Q (a 2 , i 2 ) and Q (a 2 , i 5 ) .
Our implementation of the statistical clustering generalisation process on the learning of an obstacle avoidance for Khepera is the following:

-Each forwards action associated with situations involving less obstacles than the resent situation is a cluster (a Hamming distance of 1 is used), -Each backwards action associated with situations with no obstacles behind is a cluster (a Hamming distance of 1 is used), -It is not legitimate to have cluster associated with rotational actions.

Results are displayed in figures 20 and 21. It seems that clustering is not better, even worse, than the Hamming generalisation in our case. The proportion of non-null Q values is 17.1% after 2000 learning iterations.

Dyna-Q

It may be difficult to rerun the same sequence of situation-action pairs so as to back propagate delayed rewards (equation 1 in figure 8). As a result, Sutton [START_REF] Sutton | Reinforcement Learning Architectures for Animats[END_REF] imagined adding a model of the world in which situation-action pairs are randomly carried out again (figure 22). The reinforcement function is modified in order to deal with the modelled world. In this case, only situation-action pairs previously seen (in the real world) will lead to a non-zero reinforcement reward. The returned reward r' is the same as in the real world. When the experience is performed in the real world, the exploration process is the same as described earlier in section 2.2. Otherwise (i.e., for an experience in the modelled world) the exploration function is a random selection of actions. Figure 22. Dyna architecture: the world model is used as a direct replacement for the world. In addition to the usual functioning, learning steps are also run using the model in place of the world, using predicted outcomes rather than actual ones. For each real experience with the world, many hypothetical experiences (randomly) generated by the world model can also be processed and learned from. The cumulative effect of these hypothetical experiences is that the policy approaches the optimal policy given the current model.

Comparisons

Experiments on the learning of an obstacle avoidance behaviour for the mobile robot Khepera show that these three methods speed up the learning (figure 25). Our criterion for having learnt is no more collision occur (estimated subjectively by the experimenter), together with a minimum number of positive rewards (e.g., the behaviour that consists in stopping far from any obstacle is good at experiencing no collision, but not with reference to the minimum of positive rewards). The minimum positive rewards requested is chosen by the experimenter.

The performances after learning are not perfect. This comes from the fact that a unique bit is used to code each sensor value (with a threshold at 0.2). This is certainly not precise enough. However, it is impossible to use all the bits available per sensor [START_REF] Sutton | Reinforcement Learning Architectures for Animats[END_REF]. The generalisation is limited to syntactic criterion (Hamming and clustering). There is no specific generalisation with the Dyna-Q implementation, just help in the propagation of the reward signals.

AHC [START_REF] Holland | Extending the adaptive heuristic critic and Q-learning: from facts to implications[END_REF] is very similar to Q-learning. The major difference is that AHC builds two functions (one for evaluating the interest of the situation, one for proposing an action in a situation) where Q-learning builds only one function (evaluation and policy in the same time). We think that the results reported here should also apply to the AHC method, but the necessary experiments were not conducted. The memory size is the proportion of non-null Qvalues in the look-up table (size 6400).

NEURAL Q-LEARNING

The first neural network implementation of reinforcement learning occurred at the beginning of the eighties [START_REF] Barto | Neuronlike adaptive elements that can solve difficult learning control problems[END_REF]. Neural Q-learning implementations were proposed in the nineties [START_REF] Barto | Pattern Recognizing Stochastic Learning Automata[END_REF]. Neural implementation seems to offer many advantages: quality of the generalisation and limited memory requirement for storing the knowledge. The memorisation function uses the weight set of the neural network. The memory size required by the system to store the knowledge is defined, a priori, by the number of connections in the network. It is independent of the number of explored situation-action pairs.

Ideal implementation

The ideal neural implementation will provide, in a given situation, the best action to undertake and its associated Q value (figure 26). This action should be the best available action in the situation, but how can we be sure of that? The direct implementation of the ideal neural network implementation of Q-learning with a multilayer backpropagation network implicates several drawbacks. The updating function (figure 27) is a weight modification algorithm, here the well-known gradient error backpropagation algorithm [START_REF] Rumelhart | Learning internal representations by error propagation[END_REF]. An error signal on the output neurones must therefore be defined for each output neurone. How can a quantitative error signal be defined when the only available information is of qualitative nature? The definition of this error is restricted to simple cases where only two actions are possible. For example, one of the first applications used to demonstrate the power of the neural implementation of Qlearning was the inverse pendulum with only two actions (moving the cart left or right).

In this case, it is easy to deduce from the reinforcement signal the desired output value. If the reinforcement signal received is positive (+1) then the output provided by the neural network is the desired one. If the reinforcement signal received is negative (-1) then the desired output is the inverse of the output proposed by the network. For applications involving many possible actions, like mobile robotics (e.g., Khepera allows 400 different actions), dealing with negative rewards is more difficult and requires modifications of the ideal implementation.

QCON

Lin [START_REF] Lin | Reinforcement Learning for Robots Using Neural Networks[END_REF] proposes the QCON model: a multilayer perceptron implementation of the Qlearning algorithm the characteristic of which is to have only one output neurone. There are as many QCON networks as there are actions (figure 28). It is impossible to generalise across actions.

Q value of action a 1 Situation Q value of action a n Situation . . . Each network is associated with a unique action and the output is considered as the Q value associated with the situation-action pair. There are as many QCON networks as there are actions. Generalisation across situation-action pairs is impossible. Learning concerns only one network per iteration.

Unmapping in multilayer backpropagation neural networks

Generalising across actions implies an implementation architecture composed of only one network so as to be able to use every reinforcement signal to update the network. Moreover, generalising across actions implies that the output layer codes actions and not Q values. Since the neural model is still a multilayer perceptron with a backpropagation learning algorithm, an error must be defined on the output layer. There is no problem when the reinforcement signal is positive, the proposed action is the desired one. But, with negative reinforcements, how can a desired action be chosen? At least, even if it is not possible to find the right situation-action association, a mechanism must be built that will unmap the wrong situation-action association proposed by the network.

The first idea that comes to mind when the number of possible actions increases is to learn the inverse mapping [START_REF] Barto | Pattern Recognizing Stochastic Learning Automata[END_REF]. The problem then is to determine among all those left which action is the most in opposition. Because the output of the network is numerical, we can change the sign of the output values. However, this is a harmful way of unlearning. Nobody knows what has been deleted. Representation on a neural network is distributed, so it is not possible to delete only one association (or situation-action pair)

without interfering with the rest of the learned knowledge. Moreover, a negative reinforcement does not always mean that the error is important, and to learn the inverse action can be defective. With the same goal in mind, Ackley [START_REF] Ackley | Interactions Between Learning and Evolution[END_REF] proposes the use of the complement of the generated output. Results are completely dependent on the nature of the application and are not satisfactory. We propose in the next section an action decomposition mechanism that allows unmapping without destroying the memory of the network.

Modifying the reinforcement function

Since problem of unmapping only arises with negative reinforcement signals, it may be an interesting solution to modify the reinforcement function. However, it is impossible to learn, in the general case, using only positive rewards. Know-how, on the contrary, tells us that it is frequently simpler to refine reinforcement functions with negative reinforcements.

A COMPETITIVE MULTILAYER PERCEPTRON FOR THE IMPLEMENTATION OF THE Q-LEARNING

As opposed to the implementations seen in section 2 and 3, neural reinforcement restricts learned knowledge. The ideal neural network implementation (section 4) has the great advantages of enormously reducing the memory requirements. However, the executed situation-action pairs are not explicitly stored, nor is the associated Q value. Only the most important feature of Q-learning is conserved: to be able to propose the action with the best reward potential for a given world situation. The more realistic QCON proposal does not take full advantage of a neural implementation. As many networks as the number of actions are necessary, greatly limiting generalisation.

We propose a neural implementation model that is intermediate to the ideal implementation model and QCON (it allows us to generalise between actions, but the associated Qvalue is not stored explicitly):

Step 1: Actions are grouped together in sets of agonist-antagonist actions. This can be done through a decomposition mechanism starting with complex actions and ending with the elementary actions as shown in figure 29.

Robot move

Right motor move

Left motor move

Right motor move forward Right motor move backward

Left motor move forward Left motor move backward Figure 29. Example of decomposition into elementary agonist-antagonist action sets: from the complex action 'robot move' to the elementary sets of actions, like 'right motor move forward'.

Step 2: These sets of elementary actions are coded on the output layer of the unique multilayer perceptron. One output neurone is used for each elementary action set (for the example given in figure 29, there are four output neurones). Into the set, the action to perform is coded by the output value of the neurone. In the example of the mobile robot Khepera, we use ten speeds per motor. Each neurone output varies from -1 to +1 which correspond respectively to speed 0 and speed 9. We chose a uniform distribution for the other values. It is extremely important for the generalisation process to respect continuity in the coding of the action set (order preserving coding). Therefore, speed 0 must be coded by a value less different from speed 1 than speed 9 (respectively -1 , -0.8 and +1).

Step 3: Having two neurones per motor (one for forward speeds and the other for backward speeds), the system has to decide which actions will be executed. We choose to interpret the neurone output value as a certainty value of the neural network in its proposition. Interpreting the network output values as certainty values is a common practice in connectionism, in particular in the domain of fuzzy reasoning [START_REF] Touzet | Application of Connectionist Models to Fuzzy Inference Systems[END_REF]. A competition between the two 'agonist-antagonist' neurones allows us to select the actions to undertake (figure 30). It is important to note that the fastest speed is always selected, either forwards or backwards. For example, it is extremely unlikely that a stop action will be selected. The following assumption is made: a non-null motor speed always allows us to avoid the obstacle.

Step 4: If the reinforcement signal received after carrying out the action is positive, then the desired output is the executed action (figure 30) and backpropagation can occur.

Step 5: If the reinforcement signal received after carrying the action is negative, then the value of each agonist-antagonist pair is exchanged. The desired output is the counterpart value of the executed action (figure 30) and backpropagation can occur. This method allows us to limit the size of the error, which depends on the certainty of the network. The color represents the activity value of the neuron. The darker the color, the higher the value Figure 30. Through competition between the neurones in each pair, the neurone of maximum value is selected. The exploration process can modify the proposal so to explore the situation-action space. If the reinforcement signal is positive then the error is equal to the value added by the exploration process. There is no error for the other neurone of the pair. If the reinforcement signal is negative then values of each pair of neurones are exchanged.

The five steps of this method for a competitive multilayer neural network implementation of Q-learning are summarised in figure 31. 1. Random initialisation of the network weights.

Repeat :

a.

Let i be an input situation for the neural network, and (o 1 , o 2 ) the outputs computed by propagation of activities. The action a to perform is given by competition : a = o winner + ∆o, where ∆o comes from the exploratory process as described in 2. Experiments with the competitive multilayer perceptron implementation of Q-learning on the synthesis of an obstacle avoidance behaviour for the miniature mobile robot Khepera are displayed in figures 32 and 33. The multilayer perceptron has only one hidden layer of 4 neurones, an output layer of 4 neurones and 8 input neurones. All input neurones are connected to the hidden and output neurones. There is a threshold connection on each hidden neurone. The total number of connections is 84.

SELF-ORGANISING MAP Q-LEARNING

Experiments reported in the previous section show that the competitive multilayer perceptron implementation learns faster than the other reviewed implementations: generalisation is better. We think that this is due to the localised coding on the output layer: one output neurone for each action set; and also to the competition between output neurones. Therefore, we chose to investigate the implementation of Q-learning with a neural network model that is completely dedicated to these two points: the self-organising map (also known as the Kohonen map) [START_REF] Kohonen | Self-Organisation and Associative Memory[END_REF]. We call this self-organising map implementation of the Q-learning Q-KOHON. There are other competitive neural network models which have the same properties: ART [START_REF] Carpenter | The ART of adaptive pattern recognition by a self-organizing neural network[END_REF], CMAC [START_REF] Albus | A new approach to manipulator control: the Cerebellar Model Articulation Controller (CMAC)[END_REF], etc.

Self-organising map

Structure

There is only one layer of neurones. Each neurone is connected to the inputs. A neighbourhood is defined for each neurone. The neighbourhood size depends on the application. In this paper, we use four neighbours per neurone.

Learning

Coding on a self-organising map is localised. Each neurone represents a particular class (or cluster) of the inputs (figure 34). Competition occurs between all the neurones of the map. During the learning phase, the neurones of the self-organising map approximate the probability density function of the inputs. The learning algorithm is presented in figure 35.

Repeat

For each example E of the learning base, E = {x,y}

For each neurone i of the SOM, d(i)= |x -w x,i | + |y -w y,i | (equation 2)

Select the closest neurone: j = argMin (i) (d(i)) Modify the weights of j using a learning coefficient 0<λ<1: w j,x (t+1) = w j,x (t) + λ.(x -w j,x (t)), w j,y (t+1) = w j,y (t) + λ.(y -w j,y (t))

Modify the weights of the neighbours of j with a learning coefficient µ using the same rule (usually 0<µ<λ)

Figure 34. Self-organising map learning algorithm.

Learning projects the N dimensional space represented by the training data on the M dimensional space of the self-organising map (usually two dimensions). This projection respects the relative distribution of the training data. The neighbourhoods allow us to generate a "continuous" mapping of the N dimensions space on the self-organising map.

Close N dimensional data are close in the M dimensions of the self-organising map.

Learning base (input) (input) (input) ...

(input 1 , ..., input n )

Figure 35 Self-organising map model. During the learning phase, the network weights are tuned so as to reduce the difference between the input to the network and the selected neurone.

Q-KOHON

During the learning phase, the neurones of the self-organising map approximate the probability density function of the inputs. The inputs are situation, action and the associated Q value (figure 36). The learning phase associates with each neurone of the map a situation-action pair plus its Q-value. It is a method of state grouping involving syntactic similarity and locality [START_REF] Mc Callum | Using transitional proximity for faster reinforcement learning[END_REF]. The number of neurones equals the number of stored associations. The neighbourhood property of the Kohonen map allows it to generalise across similar situation-action pairs. The Q-KOHON uses the self-organising map as an associative memory. This associative memory stored triplets. Part of a triplet is used to probe the self-organising map in search of the corresponding information. Here, situation and Qvalue are used to find the action: the best action to undertake in a world situation is given by the neurone that has the minimal distance to the input situation and to a Q value of value +1 (figure 37 a). To this end, equation 2 in the self-organising map learning algorithm (figure 34) has been changed to:

d(i)= |world_situation -W situation, i | + |1 -W Qvalue,i | The selected

Training:

The learning base is built incrementally (as for the competitive multilayer implementation). Each action of the Khepera robot is a learning example: the number of learning iterations is the total number of experiments (actions carried out in real world situations). The learning algorithm updates the Q value weight (using equation 1) and, also, the situation and action weights. The neurone corresponding to the situation and the action effectively performed is selected. The distance used is different from the search process of the most rewarding action. It includes the situation and action vectors, but nothing concerning the Q value. The equation 2 is modified in the following manner:

d(i)= |world_situation -W situation,i | + |1 -W action,i |
Together with the selected neurone, the four neighbours are also updated. The learning coefficient is 0.9 for the selected neurone and 0.5 for the neighbourhood. During the learning, the influence on the neighbours decreases proportionally to the inverse of the number of iterations. Results are given in figures 38 and 39. 100 iterations are sufficient to learn a correct behaviour. There are sixteen neurones in the map (176 connections (11 x 16)). The weights are randomly initialised around 0.5 for sensors and 0.0 for motors. Qvalues are initialised to 0.0. The inputs are of three kinds: a situation vector, an action vector and a Q value. The first eight inputs correspond to the eight sensors. In this neural implementation, the ten coding bits of each sensor are used. The ninth and tenth inputs correspond to the left and right motor commands respectively. The eleventh input corresponds to the Q value. The results reported are averaged over 5 runs. Studying the network weights, we can interpret the learned behaviour. Figure 42 presents for each neurone its eight weights linked to the situation input after 100 learning iterations. These weights only depend on the explored situations and represent for each neurone the prototype situation associated. For example the diagram for the neurone number one (N1 above left) shows that N1 is associated with a situation presenting an obstacle on the right side, principally coded by sensor 6, but also to a lesser level by sensors 5 and 7. This obstacle must be very near (about 2 cm), since the value corresponding to sensor 6 is equal to 1. This obstacle is large enough to be detected by sensors 5 and 7, and to a lesser extent by sensors 4 and 8. One should recall the heterogeneity of the sensors (figure 2) when looking at the prototype of each class of situations, particularly evident in N11 with the less effective sensor 5. All kinds of situations encountered during the learning are represented here. Due to the topological constraints of the maps, neighbouring neurones are associated with similar situations: similar sensors involved (shape of the obstacle) and similar values (distance to the obstacle). Figure 42. Visualisation of the eight weights linked to the situation input for each neurone of the map after 100 learning iterations in a task of obstacle avoidance behaviour synthesis. The higher the value of the sensor, the more sensitive the corresponding neurone to an obstacle. These diagrams represent the sixteen shapes of obstacles used for the classification. Each class is associated with an appropriate action.

The properties of the self-organising map allow us to predict that, if a correct behaviour is learned (i.e., only positive rewards are experienced), then all neurones will code positive Q values. Figure 43 presents the evolution of the weights corresponding to the Q value during the learning phase for all neurones. For N2, the curve shows that the Q value of the associated situation-action pair starts initially at 0.0, decreases to -0.5 and after 100 iterations, increases to 0.65. Initialisation puts all values to 0.0. The Q values become positive for all neurones: the actions undertaken in the encountered situations are correct. Figure 44 displays the mean of the Q values of all the neurones during the learning phase: the global performance of the robot is increasing, i.e., something rewarding is learned. In conclusion, we note that, unlike the multilayer perceptron implementation, the interpretation of the weights is possible. Moreover, if a correct behaviour is learned (i.e., only positive or null reinforcement values are experienced), then all neurones will code positive Q values. This last fact results in the optimisation of the stored knowledge.

COMPARISONS

DISCUSSION

Results obtained demonstrate that the neural generalisation allows us to speed up the Qlearning method. Starting from the QCON architecture, we have investigated the competitive multilayer perceptron implementation and the self-organising map implementation. The corresponding increase in performance seems to come from a localised coding on the output neurones and competition between the neurones.

Therefore, other neural network models, like the ART (Adaptive Resonance Theory) network [START_REF] Carpenter | The ART of adaptive pattern recognition by a self-organizing neural network[END_REF] which displays a partly-localised coding and general competition between the neurones, or the RBF (Radial Basis Function) network which enhances localised coding and general competition between the neurones, should be investigated. However, the unique property of neighbourhood of the Kohonen map, which influences the generalisation process through the continuity of the coding, may be very important for the quality of the results. In this case, we may have found with this implementation the 'ultimate' Q-learning implementation.

Reinforcement functions are usually hand-tuned and emerge after lots of experiments. The reinforcement learning algorithm task is to improve the cumulative reward over time.

Despite a good learning phase (i.e., only positive Q values for all neurones of the selforganising map) the obtained behaviour does not always exhibit the expected behaviour.

In our experiments, the learned behaviours show a large distribution of covered distances. Figure 47 displays four curves corresponding to four different experiments. A behaviour may exhibit a predilection for moving forward, or for moving backward, or for small movements, or for change in its policy during the experiment. There is also another behaviour, perhaps the most rewarding considering our reinforcement function describes in 1.2. It is: move forward to an obstacle, stop before the sum of the sensor values is above the threshold (2,90) and then move backward, and do it all again. This sequence of actions maximises rewards, but it is something different from the expected obstacle avoidance behaviour. changes its policy at the end of the learning phase (here 200 iterations).

Temporal credit-assignment problem

This result about the covered distances of several different experiments shows that having an effective Q-learning implementation is not sufficient to solve an application. In our particular case, the synthesised behaviour is a reactive behaviour. It does not integrate sequences of actions. A solution would be to change the reinforcement function to allow the taking into account of sequences of actions. Equation 1 (fig. 8) will then be used to solve the temporal credit assignment problem. However, its efficiency is strictly limited to short sequences of actions. The Q-learning implementation needs a concept of historical states to deal with large sequences of actions. Temporal self-organising map and recurrent neural networks [START_REF] Touzet | The Connectionist Sequential Machine: a General Model of Sequential Networks[END_REF] appear to be good candidates to this end.

The description of the reinforcement function is of tremendous importance and research must be done for the design of reinforcement functions. We have started some work in this direction and proposed to add to the learning system an external module containing generic forbidden sequences of actions [START_REF] Touzet | Improving Reinforcement Learning of Obstacle Avoidance Behavior with Forbidden Sequences of Actions[END_REF]. Experiments with the mobile robot Khepera demonstrate that it is possible to constrain the synthesised behaviours to forward avoidance behaviours.

The environment of our experiments is stationary; that is, the probabilities of making state transition, or receiving specific reinforcement signals, do not change over time. One may decide that this assumption makes our experiments trivial in that, after all, operation in non-stationary environments is one of the motivations for building learning systems [START_REF] Kaelbling | Reinforcement Learning: A Survey[END_REF]. In fact, the methods described here are effective in slowly varying non-stationary environments, in particular if learning does not stop and if there is always a probabilistic action selection function.

As expressed in section 1.1, obstacle avoidance in nothing else than a simple, pedagogical task for mobile robotics, aimed at allowing comparisons between reinforcement learning implementations. It is very difficult to achieve a solution with tabula rasa learning techniques (i.e., pure reinforcement learning). Bias must be incorporated to allow effective learning solutions, like: shaping, local reinforcement signals, imitation, problem decomposition, reflexes, etc.

Shaping: start with very simple tasks, then increase the difficulty. This method is particularly useful with supervised learning approaches [START_REF] Dorigo | Robot Shaping: developping autonomous agents through learning[END_REF].

Local reinforcement signals: whenever possible, give local reinforcement signals, rewarding local actions (not far from immediate reinforcement signals) [START_REF] Mataric | Reward function for accelerated learning[END_REF].

Imitation: learn by watching an other agent. The problem is to get the first agent to perform the task. Today, this first agent must be human controlled in a task of obstacle avoidance [START_REF] Lin | Self-improving reactive agents based on reinforcement learning, planning and teaching[END_REF].

Problem decomposition: decompose complex behaviour into a collection of simpler ones, and provide useful reinforcement signals for each one. This decomposition technique is used in almost all successful robotics reinforcement learning experiments [START_REF] Colombetti | Behavior Analysis and Training -A Methodology for Behavior Engineering[END_REF].

Reflexes: [START_REF] Del R. Millàn | Rapid, Safe and Incremental Learning of Navigation Strategies[END_REF] provide the robot with a set of reflexes, i.e., initial knowledge that will allow a better exploration of the search space (figure 48). This initial knowledge can be ameliorated through learning. Learning from Basic Reflexes. This method utilises a set of basic reflexes every time its connectionist controller fails to generalise correctly its previous experience to the current situation, i.e., the evaluation function does not find an input neurone matching the current situation. The connectionist controller associates the selected reflex with the situation in one step. The sensory situation is represented by a new unit of the network and the selected reflex, or situation-action pair, is coded into the network weights. This new association is tuned subsequently through reinforcement learning. The neural network gets control more often as the robot explores the environment.

CONCLUSION

In this paper, we have presented the results of research aimed at improving reinforcement learning through the use of neural network implementations. The same real robot, environment and reinforcement function are used for all the experiments described in the paper. After a brief description of the Q-learning method, we have pointed out the need for generalisation. Several enhancements, including the Hamming distance, statistical clustering and Dyna-Q were briefly described. The results obtained with these implementations are interesting, but still insufficient at least in our experiment of learning an obstacle avoidance behaviour for the miniature mobile robot Khepera. Therefore, we have studied neural network implementations of Q-learning for their generalisation properties and limited computer memory requirements. An ideal neural implementation is proposed. It helps to understand the current limitations of the today implementations, like QCON (a multilayer perceptron implementation of Q-learning). A competitive multilayer perceptron implementation is then proposed that allows better generalisation. This increase in performance seems to be the result of a localised coding on the output neurones and competition between neurones. A second neural implementation that takes full advantage of these two attributes is then proposed using a self-organising map.

Results obtained on a task of learning an obstacle avoidance behaviour for the miniature mobile robot Khepera show that this last implementation is very effective.

It is our opinion that with a self-organising map implementation, Q-learning is no more a research area but a tool at the disposition of the engineer to develop applications in autonomous robotics. However, as discussed in section 8, there is still research to conduct in the Q-learning domain. In particular, the design of reinforcement functions is probably the most difficult part in the development of a reinforcement learning application. To deal with more complicated behaviour synthesis than the reactive behaviour chosen here, it is necessary to develop new Q-learning implementations. A concept of historical states is needed to deal with large sequences of actions. Temporal self-organising map and recurrent neural networks appear to be promising candidates to this end.

Figure 1 .

 1 Figure 1. The miniature mobile robot Khepera.

Figure 4 .Figure 5 .

 45 Figure 4. One of the environments of our experiments with the miniature robot Khepera in the centre. Obstacle are put in the arena at the beginning of each experiment.

Figure 6 .

 6 Figure 6. Distance to the obstacles measured during a Braitenberg avoidance behaviour.

Figure 10 .Figure 11 .

 1011 Figure 10. Distance to the obstacles measured after 4000 learning iterations with classical Q-learning. The results reported are averaged over 5 runs, standard deviation is also reported. Distances to obstacles are greater than Braitenberg's implementation (fig. 6): learning is interesting.

Figure 14 .

 14 Figure 14. Negative reinforcements experienced with a classical Q-learning implementation after 4000 learning iterations, a random exploration behaviour and a Braitenberg implementation. Graphs are averaged over 5 runs, standard deviation is also reported.

Figure 15 .

 15 Figure 15. Generalisation using Hamming distance in black. In this example, the world situation is i 3 , the executed action is a 6 , the threshold value for the Hamming distance is 1. Q (i 3 , a 6 ) is updated, but also Q (i 2 , a 6 ) and Q (i 4 , a 6 ).

Figure 16 .Figure 17 .

 1617 Figure 16. Q-learning with Hamming distance ( of 1): distance to the obstacles measured after 2000 learning steps. The results reported are averaged over 6 runs.

Figure 20 Figure 21 .

 2021 Figure 20. Q-learning with statistical clustering : distance to the obstacles measured after 2000 learning steps. The results reported are averaged over 5 runs. As shown by the standard deviation graph, the synthesised behaviours are very different in their performances.

Figure 23 .Figure 24 .

 2324 Figure 23. DYNA Q-learning: distance to the obstacles measured after 1000 learning iterations. The results reported are averaged over 5 runs.

Figure 25 .

 25 Figure 25. Comparison of several different implementations of Q-learning in terms of learning time, number of learning iterations and memory size. The learning time is the time in seconds needed to synthesise an obstacle avoidance behaviour. It reflects the number of real world experiments required. The number of learning iterations is the number of updates of the look-up table (after real world or modelled world experiments).

Figure 26 .

 26 Figure 26. Ideal neural Q-learning model providing for an input situation the best action to undertake and its associated Q value.

Figure 27 .

 27 Figure 27. The direct implementation of the ideal neural network implementation of Qlearning with a multilayer backpropagation network.

Figure 28 .

 28 Figure 28. The QCON model: only one output neurone per multilayer neural network.Each network is associated with a unique action and the output is considered as the Q value associated with the situation-action pair. There are as many QCON networks as

  2 and o winner = Max. (o 1 , o 2 ). b. Execute the action a in the world. c. Let r be the reinforcement signal associated with the execution of a in . The weights are updated by an algorithm which minimises the output error. It is necessary to determine a desired output value d for each output neurone, depending on r . If r = 0 then there is no modification. If r = +1 then d select = a . Only weights connected to the selected neurone are modified. If r = -1 then d 1 = o 2 and d 2 = o 1 (exchange of values). All weights are modified.

Figure 31 .

 31 Figure 31. Learning algorithm for a competitive multilayer neural network implementation of the Q-learning.

Figure 32 .Figure 33 .

 3233 Figure 32. Competitive multilayer neural network implementation of Q-learning: distance to the obstacles measured after 500 learning iterations. The results reported are averaged over 5 runs.

Figure 36 .

 36 Figure 36. The self-organising map implementation of Q-learning.

Figure 37 .

 37 Figure 37. Selection of the best action to perform in the world situation. The Kohonen map is used as an associative memory: information is probed with part of it. a/ The world situation and a Q value of +1 are given as inputs. b/ The answer is a selected neurone which weights give situation, Q value and the associated action.

  Figure 38. Q-KOHON : distance to the obstacles measured after 100 learning iterations.The results reported are averaged over 5 runs.

Figure 39 .

 39 Figure 39. Effectiveness of Q-KOHON (100 learning iterations plus 276 test iterations):proportion of moves executed by the obstacle avoidance module that received positive and negative reinforcements since the beginning of the experiment. Graphs are averaged over 5 runs, standard deviation is also reported.

Figure 41 .

 41 Figure 41. Performance traces (76 iterations) of the robot with Q-KOHON after learning.

5 Figure 43 .Figure 44 .

 54344 Figure 43. Evolution of the Q value associated with each neurone (or class of situationaction represented by a neurone). The Q values, starting from 0.0, converge to positive values for all neurones, demonstrating that the learned behaviour is rewarding. There are 100 learning iterations, but the learning does not completely stop after 100 (λ = µ = 0.001). After 500 iterations, only situation-action pairs giving positive rewards are stored in the map. The number of iterations in the figure as to be multiplied by 10.

Figure 45 Figure 45 .Figure 46 .

 454546 Figure45presents the learning time, number of learning iterations and memory size of the two artificial neural network Q-learning implementations studied previously. A comparison with the other implementations of Q-learning has been done. Results displayed in figure46show that the self-organising map Q-learning implementation requires less memory and learns faster than all the others (by a factor of 40). The Q-KOHON implementation has also the best behaviour after learning, i.e., less negative reinforcements received than all the other implementations (fig.39).

Figure 47 .

 47 Figure 47. Distances covered by Khepera during four different experiments of learning an obstacle avoidance behaviour. Behaviour (a) displays a predilection for moving forward , (b) prefers moving backward, (c) prefers small forward movements, (d)

  Figure48. Learning from Basic Reflexes. This method utilises a set of basic reflexes every time its connectionist controller fails to generalise correctly its previous experience

  Figure 18. Proportion of non null Q values in the look-up table in function of the number of learning iterations for a Hamming distance of 1 (H1)

	Nb. it.	1000 H1 1500 H1 2000 H1	1000 H2 1500 H2	2000 H2
	%	30.8	32.5	32.5	80.8	80.8	82.5
	statistical clustering

Therefore, a modification of the Hamming generalisation process has been introduced:

  The same look-up table is used as in the classical Q-learning implementation. This implementation needs fewer actions carried out in the real world, but the number of learning iterations is increased. The proportion of non-null Qvalues in the look-up table is 19.4% after 1000 learning iterations and 26.7% after 2000 learning iterations.

There are ten hypothetical experiences for each real world action (the maximum possible number is 25: the number of possible actions). The ten hypothetical actions are randomly selected using a uniform probability. The results obtained with Khepera for an obstacle avoidance behaviour synthesis are given in figures 23 and 24.

The standard deviation is computer as: sqrt ((sumX[i] -mean)^2 / N)

1 Acknowledgements

We thank all the K-Team members (LAMI-EPFL, Switzerland) for their interest in this research and the use of one of the first Khepera robots.


S Hadj-Said
email: souad.hadj-said@renault.com

G Colin

A Ketfi-Cherif
email: ahmed.ketfi-cherif@renault.com

Y Chamaillard
email: yann.chamaillard@univ-orleans.fr

Convex Optimization for Energy Management of Parallel Hybrid Electric Vehicles

Keywords: Energy Management Strategy, Hybrid Electric Vehicles (HEV), Convex optimization, Pontryagin's Maximum Principle (PMP), Engine On/Off

This paper presents a comparison between two optimization methods for the energy management of a parallel hybrid electric powertrain: convex programming and Pontryagin's Minimum Principle (PMP). The objective of this comparison is to validate the analytical solution by comparing the results with the ones obtained on the original model with Dynamic Programming (DP). Therefore, before its application, some necessary approximations and convexification were made on the original nonlinear and non-convex model. The validation of the simplified model was also carried out. In this paper, two cases are studied. In the first case, the supervisory control considers only the torque split between the Internal Combustion Engine (ICE) and the Electric Machine. In the second case, a binary decision ICE On/Off is included in the optimization problem. In order to solve the problem of the binary decision, which makes the problem non-convex, a analytical solution based on PMP is then proposed. The results show that the analytical solution is close to the optimal solution given by DP.

INTRODUCTION

The transport sector accounts for 26% of global energy consumption [START_REF] Badin | Hybrid Vehicles[END_REF]. This is the reason why, in recent years, extensive research has been undertaken in order to reduce energy consumption and pollution caused by transportation. In this paper, we focus on one of the solutions for achieving a near-term reduction of energy consumption proposed by the automotive industry, which is the use of Hybrid Electric Vehicles (HEVs). HEVs consist of at least two power sources, an internal combustion engine and one or more electric motors, as well as an energy buffer, typically a battery. This means that an energy management solution must be found between power sources in the vehicle that minimizes fuel consumption. In simulation, optimal off-line approaches are interesting for design and component sizing purposes and real-time control strategy design. There are many approaches to design an optimal energy management strategy: deterministic Dynamic Programming (DP) [START_REF] Pérez | Optimization of power management in an hybrid electric vehicle using dynamic programming[END_REF][START_REF] Debert | Energy management of a high efficiency hybrid electric automatic transmission[END_REF], stochastic DP [START_REF] Johannesson | Assessing the potential of predictive control for hybrid vehicle powertrains using stochastic dynamic programming[END_REF], and Pontryagin's Maximum Principle [START_REF] Serrao | Ecms as a realization of pontryagin's minimum principle for hev control[END_REF][START_REF] Kim | Optimal control of hybrid electric vehicles based on pontryagin's minimum principle[END_REF]. While being a globally optimal energy management, dynamic programming is computationally expensive, which limits its application to low-order systems (typically two states). As far as PMP method is concerned, its inconvenient is the sensitivity of the solution towards the boundary conditions [START_REF] Serrao | A comparative analysis of energy management strategies for hybrid electric vehicles[END_REF].

Recently, convex optimization [START_REF] Boyd | Convex Optimization[END_REF][START_REF] Grant | Cvx: Matlab software for disciplined convex programming[END_REF] has attracted attention in the research field of energy management for HEVs. It is seen as an alternative method for the optimization of the power flows in HEVs due to its advantages, the most important of which is that it is computationally more efficient than DP or PMP. In [START_REF] Murgovski | Engine on/off control for dimensioning hybrid electric powertrains via convex optimization[END_REF][START_REF] Murgovski | Component sizing of a plug-in hybrid electric powertrain via convex optimization[END_REF], convex optimization was employed to dimension the HEV powertrain especially the battery, whereas [START_REF] Hu | Energy efficiency analysis of a series plug-in hybrid electric bus with different energy management strategies and battery sizes[END_REF] used it for energy efficiency analysis. In this study, we are interested in minimizing fuel consumption via convex optimization, with the use of a engine On/Off functionality to stop and start the engine during the driving cycle. This functionality enables a further fuel consumption reduction. Unfortunately, a binary variable for controlling the engine On/Off state cannot be included in a convex formulation as the set of integer numbers is not convex. To solve this kind of optimization problems, also known as a mixed integer problem, [START_REF] Murgovski | Component sizing of a plug-in hybrid electric powertrain via convex optimization[END_REF] proposed that integer and binary variables should be decided a priori by heuristics. In [START_REF] Elbert | Engine on/off control for the energy management of a serial hybrid electric bus via convex optimization[END_REF], the optimal engine On/Off strategy is computed analytically using the PMP approach for a serial hybrid electric bus. In [START_REF] Nüesch | Convex optimization for the energy management of hybrid electric vehicles considering engine start and gearshift costs[END_REF], the engine On/Off and gearshift strategies are given by a combination of DP and PMP. This paper is organized as follows. In section 2, the vehicle model is presented. In section 3, convex modeling and optimization are proposed for a first study case where the engine is running during the driving cycle which is presented so that the optimization problem considers only the torque split of a parallel electric hybrid powertrain. In section 4, a second case is studied where the engine On/Off decision is added to the optimization problem.

Here, the PMP approach on the convex model is applied to find analytically the global optimal engine state and the optimal torque split. Then, the optimal torque split is also determined by a convex solver. In section 5, simulation results obtained in the two study cases are compared to the results obtained by DP. The purpose of this comparison is to establish the performances of the simplified model and the analytical solution for real-time energy management strategies. In this section, the HEV model, often presented as quasistatic, is given. Fig. 1 illustrates the configuration of the powertrain architecture considered , which consists of a battery, an electric motor, an internal combustion engine delivering power to the wheels via a transmission block and a clutch e on , which couples or decouples the engine with the rest of the powertrain. The vehicle dynamics is governed by the following equations:

Battery

F wheel (t) = m vec v(t) + F res (t)[N ] (1) T 0 (t) = F wheel (t).R wheel [N m] (2) ω 0 (t) = v(t)/R wheel [rad/s]
(3) where F wheel is the force at the wheels, F res (t) = F tires + F aero (t) the resistive force which includes the aerodynamic force (F aero (t) = 0.5.ρ.Scx.v 2 (t)) and the tire resistance (F tires )(here assumed constant), m vec [kg] the total vehicle mass and R wheel [m] the wheel radius.

Transmission

Transmission between the wheels and the crankshaft is given by the following static model:

ω dem (t) = ω 0 (t)r Gear (4) T dem (t) = T 0 (t)/(η Gear r Gear ) if T 0 (t) ≥ 0 (T 0 (t)η Gear )/r Gear if T 0 (t) ≤ 0 (5)
P dem (t) = T dem (t)ω dem (t) = T e (t)ω e (t) + e on (t)T i (t)ω i (t) (6) where T 0 , ω 0 , T dem , ω dem , T e , ω e , T i , ω i are torque and speed of respectively the wheel, the crankshaft, the electric motor and the internal combustion engine. e on stands for the binary engine On/Off control, e on (t) = {0, 1} where e on = 1 means that the engine is activated.

Battery

The battery is modeled as a simple resistive circuit [START_REF] Badin | Hybrid Vehicles[END_REF][START_REF] Murgovski | Component sizing of a plug-in hybrid electric powertrain via convex optimization[END_REF] and the battery power is given by:

P batt (t) = OCV (SoE)i batt (t) -R batt (SoE)i 2 batt (t)[w] (7) P batt (t) = P e (t) + P aux (8)
The State of Energy (SoE) of the battery is defined as:

ṠoE(t) = - OCV (SoE)i batt (t) E max (9)
where E max [J] is the maximal battery energy. The current i batt [A] and SoE are limited by:

i battmin ≤ i batt (t) ≤ i battmax (10) SoE min ≤ SoE(t) ≤ SoE max . ( 11
)

Engine

The engine model consists of the fuel power consumed by the engine to deliver mechanical power:

P f uel (t) = e on (t)H f ṁf (T i (t), ω i (t)) (12
) where ṁf (T i (t), ω i (t))[g/s] is the fuel consumption map of the engine and H f [J/g] the fuel lower heating value.

The engine torque T i is limited by a function of the engine speed ω i :

T imin (ω i (t)) ≤ T i (t) ≤ T imax (ω i (t)) (13)
If the gear ratio is given, the engine speed is directly obtained from ω dem and it is not decided by the optimization.

ω i (t) = ω dem (t) (14)

Electric Motor (EM)

The electric motor model expresses the electric power produced by EM which includes the mechanical power delivered and the losses obtained from the specific power loss of the EM loss(T e (t), ω e (t)). So, the electric power (P e ) produced by the EM has the following expression: P e (t) = T e (t)ω e (t) + loss(T e (t), ω e (t)) (15) Here also, the EM speed is obtained from ω dem .

ω e (t) = ω dem (t) (16) The EM torque is limited by torque limits depending on the EM speed:

T emin (ω e (t)) ≤ T e (t) ≤ T emax (ω e (t)) (17)

CONVEX OPTIMIZATION WITHOUT ENGINE ON/OFF STRATEGY

As can be seen from [START_REF] Elbert | Engine on/off control for the energy management of a serial hybrid electric bus via convex optimization[END_REF]; [START_REF] Nüesch | Convex optimization for the energy management of hybrid electric vehicles considering engine start and gearshift costs[END_REF]; [START_REF] Yuan | Comparative study of dynamic programming and pontryagins minimum principle on energy management for a parallel hybrid electric vehicle[END_REF], there are many approaches to the energy management problem in HEVs. These different methods focus on the same objective and try to solve a common problem, i.e. a problem of optimization under constraints. In this section, the application of convex optimization to the HEV energy management problem is presented. In the following, e on = 1. P c is the continuous optimization problem given by:

P c :        min u∈U J(x(t), u(t)) ẋ = f (x(t), u(t)) C e (x(t), u(t)) = 0 C i (x(t), u(t)) ≤ 0 (18)
where the state is x = SoE, the control input is u = T e , C e are the equality constraints and C i are the inequality constraints. The goal of this paper is to minimize fuel consumption under constraints. Therefore, the objective function J c has to be reformulated as follows:

J(x(t), u(t)) = t f t0 P f uel (t)e on (t)dt (19)
In the following, the time-discretized optimization problem is solved by a convex solver. For a chosen sampling time t, and by applying the Euler formula, the optimization problem is rewritten as follows:

P d :        min u∈U J d (x(k), u(k)) x(k + 1) = t.f (x(k), u(k)) + x(k) C e (x(k), u(k)) = 0 C i (x(k), u(k)) ≤ 0 (20)
and:

J d (x(k), u(k)) = N k=0 P f uel (k)e on (k) (21)
Compared to a general constrained optimization problem, the convex optimization problem has three requirements:

• the cost function (21) must be convex;

• the inequality constraint functions C i (x(k), u(k)) must be convex; • the equality constraint functions C e (x(k), u(k)) must be affine.

Section 3.1 describes the necessary approximations for a reformulation of the original problem into a convex optimization problem.

Convex modeling

In order to apply convex programming, the nonlinear vehicle model has to be approximated by a convex model, see [START_REF] Boyd | Convex Optimization[END_REF].

Battery model To preserve the problem convexity, the following two assumptions are made [START_REF] Badin | Hybrid Vehicles[END_REF][START_REF] Murgovski | Component sizing of a plug-in hybrid electric powertrain via convex optimization[END_REF]. Firstly, the open circuit voltage (OCV ) and the resistance on the battery R batt are considered constant. This should be checked after optimization. Secondly, equation ( 7) is relaxed with inequality.

OCV (SoE) = OCV (22) R batt (SoE) = R batt (23) P batt (t) ≤ OCV i batt (t) -R batt i batt 2 (t) ( 24
)
Engine model Here, equation ( 12) is approximated by a second order polynomial with speed dependent coefficients. Pfuel (t) = a 0 (ω i (t)) + a 1 (ω i (t))T i (t) + a 2 (ω i (t))T i 2 (t) (25) where the coefficients a 0 , a 1 and a 2 are found by least squares for a number of grid points of ω i . Fig. 2 is the representation of an example of the original and the approximated engine models. The maximum relative error (RE f uel ) of the fuel power approximation was calculated using the expression RE f uel (t) = max ωi ( P f uel (ωi(t))-Pfuel (ωi(t))

P f uel (ωi(t))

). Fig. 2 shows that the approximated engine model is sufficiently representative of the original engine model. 15) is relaxed with inequality and approximated by a second order polynomial with speed dependent coefficients.

P e (t) ≥ b 0 (ω e (t))+b 1 (ω e (t))T e (t)+b 2 (ω e (t))T e 2 (t) = Pe (t) (26) where the coefficients b 0 , b 1 and b 2 are found by least squares for a number of grid points of ω e . Fig. 3 is the representation of an example of the original and the approximated EM models. The relative error (RE e ) of the electrical power approximation was calculated using the expression RE e (t) = max ωe ( Pe(ωe(t))-Pe(ωe(t))

Pe(ωe(t))

). Fig. 3 shows that the approximated EM model is sufficiently representative of the original EM model. As for RE f uel , RE e is due to the interpolation between two speeds (e.g between 2500 rpm and 3000 rpm).

Convex problem resolution

The original problem, after approximations, is rewritten as a convex problem and can be solved by a convex solver. Moreover, according to the PMP, minimizing ( 19) is equivalent to minimizing the Hamiltonian function which is calculated from ( 9) and ( 12), as follows:

(t) = P batt (t) + R batt i batt 2 (t).
Here, it is assumed that the battery losses are neglected(R batt i batt 2 (t) ≈ 0), therefore, OCV i batt (t) ≈ P batt (t). Thus, by replacing P batt (t) by ( 8), P f (t) by ( 25) and P e (t) in ( 8) by ( 26), the Hamiltonian ( 27) becomes:

H(t, u(t)) = a 0 (t) + a 1 (t)T i (t) + a 2 (t)T i 2 (t) + s(t)(b 0 (t) + b 1 (t)T e (t)+b 2 (t)T e 2 (t)+P aux (t))
Therefore, H is minimum when ∂H ∂Te = 0, so that:

T * e (t) = 2a 2 (t)T dem (t) + a 1 (t) -s * (t)b 1 (t) 2(a 2 (t) + s * (t)b 2 (t)) (28)
Finally, in order to calculate the optimal torque split, the optimal equivalence factor s * must be found so that the desired final state is reached. Here, s * is determined by dichotomy.

Afterwards, a convex solver is used to solve the convex problem and its results are compared to the results of PMP. The optimization problem is presented to the solver as follows

                                             min N k=1
Pfuel (k)e on (k)

s.t. T dem (k) = T e (k) + e on (k)T i (k) P e (k) ≥ b 0 (ω e (k)) + b 1 (ω e (k))T e (k) + b 2 (ω e (k))T e 2 (k) P batt (k) ≤ OCV i batt (k) -R batt i batt 2 (k) T emin (ω e (k)) ≤ T e (k) ≤ T emax (ω e (k)) T imin (ω i (t)) ≤ T i (k) ≤ T imax (ω i (t)) SoE min ≤ SoE(k) ≤ SoE max i battmin ≤ i batt (k) ≤ i battmax P batt (k) = P e (k) + P aux SoE(k + 1) = SoE(k) -∆t OCV i batt (k)/E max SoE(1) = SoE(N ) = 50% (29)
Then, ( 29) is rewritten in a matrix form. The quadratic functions are expressed in the following form: X T AX + cX + d, whereas the affine functions are formulated as: eX + l. X(4N × 1) is the optimization variable, such that:

X =    T i T e SoE i batt    T i = [T i (1)T i (2)...T i (N )] T (N × 1) T e = [T e (1)T e (2)...T e (N )] T (N × 1) SoE = [SoE(1)SoE(2)...SoE(N )] T (N × 1) i batt = [i batt (1)i batt (2)...i batt (N )] T (N × 1)
Finally, the convex problem ( 29) can be solved using the solvers available in [START_REF] Grant | Cvx: Matlab software for disciplined convex programming[END_REF], such as SeDuMi [START_REF] Labit | Sedumi interface 1.02: a tool for solving lmi problems with sedumi[END_REF], or SDPT3 [START_REF] Toh | On the implementation and usage of sdpt3-a matlab software package for semidefinite-quadratic-linear programming[END_REF].

OPTIMIZATION WITH ENGINE ON/OFF STRATEGY

In this section, the engine On/Off functionality is considered in the optimization problem (P ) (e on = {0, 1}). As given in section 2, the binary variable e on is present in ( 6) and ( 12). Since e on makes the problem (P ) nonconvex, it cannot be included as a decision variable for the solver. Therefore, this decision must precede the resolution of the convex problem by the solver. In the following, the PMP is used to find the globally optimal engine state and the optimal torque split. Then, the optimal engine On/Off decision is introduced a priori to the solver which calculates the globally optimal torque split.

The Hamiltonian (27) can be analyzed for two cases: engine On H On and engine Off H Of f , where:

H = H On , for e on = 1 H Of f , for e on = 0 with H On = a 0 (t) + a 1 (t)T i (t) + a 2 (t)T i 2 (t) + s(t)(b 0 (t) + b 1 (t)T e (t) + b 2 (t)T e 2 (t) + P aux (t)) H Of f = s(t)(b 0 (t) + b 1 (t)T e (t) + b 2 (t)T e 2 (
t) + P aux (t)) In the case "On", H On is minimum for (28), whereas in the case "Off", e on = 0, H Of f is minimum when

T * ,Of f e (t) = T dem (t) (30
) since T i (t) = 0 and (6) have to be satisfied. The condition of optimality, minimizing the Hamiltonian, to switch on the engine is:

H On (T * ,On e ) ≤ H Of f (T * ,Of f e ) (31
) By inserting ( 28) and ( 30) in ( 31), the conditions on the requested torque become:

T dem (t) ≤ T 1 lim (t) (32) T dem (t) ≥ T 2 lim (t) (33)
Where

T 1,2 lim (t) = a1(t)-s * (t)b1(t)∓ √ a0(t)(a2(t)+s * (t)b2(t)) 2s * (t)b2(t)
. From ( 32) and (33), the torque threshold is a function of the optimal equivalence factor and the model parameters (a 0 (t), a 1 (t), a 2 (t) and b 0 (t), b 1 (t), b 2 (t)). The optimal engine On/Off decision is given by e on * (t) = 1, if T dem (t) ≤ T 1 lim (t) or T dem (t) ≥ T 2 lim (t) 0, else Fig. 4 shows the optimization On/Off process. Firstly, the optimal engine state e * on and the optimal EM torque T * e P M P are calculated by finding a first s * by dichotomy. As the control could be singular [START_REF] Delprat | Hybrid vehicle optimal control: Linear interpolation and singular control[END_REF], a second parameter t s was introduced to switch for another value of s * in order to converge to the desired final SoE. t s permits to switch between two values of s * (e.g. s * 1 and s * 2 in Fig. 5). The existence of t s is demonstrated by the fact that (34) is continuous, SoE t f (t s = t 0 ) > 50% and SoE t f (t s = t f ) < 50%. The expression of SoE t f (t s ) is given by:

SoE t f (t s ) = - ts t0 ṠoE(t)dt| s=s * 1 - t f ts ṠoE(t)dt| s=s * 2
(34) Secondly, the optimal EM torque T * e CV X is also found by a convex solver for the predefined command e on . To ensure optimality in the solution given by convex programming, the equivalence factor s out must be optimal. In [START_REF] Murgovski | Engine on/off control for dimensioning hybrid electric powertrains via convex optimization[END_REF], it was shown that the necessary condition for a globally optimal solution is: s in ≡ s out .

RESULTS

In this section, the evaluation of the convex method is presented by comparing its results to DP results. In order to ensure the robustness of the control (torque split and/or engine state) obtained from the simplified model, the latter was applied on the original model. For each method, it is assumed that the driving cycle is given. The minimum, maximum and initial value of the SoE is 25%, 85% and 50%, respectively.

Tables 1 and2 summarize the results obtained in terms of fuel consumption (FC) and computation time for four cycles: NEDC, ARTEMIS urban, road and highway. For the convex method, the fuel consumption value was obtained by applying the strategy on the original vehicle model. From tables 1 and 2, convex optimization finds almost the same fuel consumption as the one found by DP. These results prove that the solution based on the simplified model is very close to the globally optimal solution. In addition, the CPU time of the analytical method is lower than the one of DP and almost the same as convex programming. Fig. 6 and Fig. 7 show that the strategies provide a similar SoE trajectory.

CONCLUSION

In this paper, convex optimization is presented and applied to calculate the energy management strategy for a parallel HEV. The results of the comparison show that the convex method, which is based on simplified models, provides an optimal solution close to the global optimum given by DP. This leads to the validation of the approximated models and encourages their use for embedded optimal control. Moreover, the convex strategy presents two other attractive advantages. The first one is its low computation time compared to DP which will be even more interesting when the optimization problem has more than one state variable. The second one is that it does not require discretization of the continuous control and state variables which introduces errors in the solutions. In addition, the PMP analytical method has two more important From the results of optimization with the engine On/Off strategy presented in section 5, two important conclusions can be drawn: first, the engine On/Off functionality allows a significant reduction in fuel consumption. Secondly, the analytical method is very efficient, since its solution is very close to the globally optimal solution given by DP.

  Fig. 1. Parallel HEV powertrain model with engine On/Off clutch

Fig. 2 .

 2 Fig. 2. The original and the approximated fuel power model for representative engine speeds (top) and the maximum relative error resulting from this approximation (bottom) for NEDC cycle speeds

  Fig. 3. The original and the approximated electric power model for representative EM speeds (top) and the maximum relative error resulting from this approximation (bottom) for NEDC cycle speeds

Fig. 5 .

 5 Fig. 5. Discontinuities in the dependence of the final SoE of a constant equivalence factor s *

Fig. 6 .Fig. 7 .

 67 Fig. 6. Comparison of the SoE trajectory obtained by DP and convex optimization for ARTEMIS highway cycle without engine On/Off strategy

  SoE(t), u(t) = [T e (t) e on (t)] T , s is the Lagrange multiplier and OCV i batt

	3. The original and the approximated electric power
	model for representative EM speeds (top) and the
	maximum relative error resulting from this approx-
	imation (bottom) for NEDC cycle speeds
	H(x(t), u(t)) = P f (T e (t), t)e on (t) + s(t)	OCV i batt (T e (t), t) E max
		(27)
	Where x(t) =

Table 1 .

 1 Fuel consumption and time computation results without engine On/Off strategy

	Cycle	Strategy	CPU	FC
			time [s]	[L/100km]
		CVX	6	4.69
	NEDC	DP	18	4.69
		PMP CO	4	4.69
		CVX	7	6.75
	ARTEMIS road	DP	17	6.75
		PMP CO	6	6.75
		CVX	5	10.16
	ARTEMIS highway	DP	17	10.16
		PMP CO	6	10.16
	Cycle	Strategy	CPU	FC
			time [s]	[L/100km]
	NEDC	PMP/CVX	13	2.39
		DP	28	2.38
		PMP CO	10	2.39
	ARTEMIS road	PMP/CVX	13	3.84
		DP	26	3.83
		PMP CO	8	3.84
	ARTEMIS highway	PMP/CVX	12	6.38
		DP	27	6.34
		PMP CO	7	6.38
	Table 2. Fuel consumption and time computa-
	tion results with engine On/Off strategy


Claude Touzet

Why Neurons are Not the Right Level of Abstraction for Implementing Cognition

The cortex accounts for 70% of the brain volume. The human cortex is made of micro-columns, arrangements of 110 cortical neurons (Mountcastle), grouped in by the thousand in so-called macro-colums (or columns) which belong to the same functional unit as exemplified by Nobel laureates Hubel and Wiesel with the orientation columns of the primary visual cortex. The cortical column activity does not exhibit the limitations of single neurons: activation can be sustained for very long periods (sec.) instead of been transient and subject to fatigue. Therefore, the cortical column has been proposed as the building block of cognition by several researchers, but to not effect -since explanations about how the cognition works at the column level were missing. Thanks to the Theory of neuronal Cognition, it is no more the case.

The cortex functionality is cut into small areas: the cortical maps. Today, about 80 cortical maps are known in the primary and secondary cortex [START_REF] Silver | Topographic maps in human frontal and parietal cortex[END_REF]. These maps form a hierarchical organization. A cortical map is a functional structure encompassing several thousands of cortical columns. The function of such maps (also known as Kohonen maps) is to build topographic (i.e., organized and localized) representations of the input stimulii (events). This organization is such that similar inputs activate either the same cortical column or neighboring columns. Also, the more frequent the stimulus, the greater the number of cortical columns involved. Each map acts as a novelty detector and a filter. Events are reported as patterns of activations on various maps, each map specialized in a specific "dimension". Spatial and temporal coordinates of events are linked to activations within the hippocampus and define de facto the episodic memory.

Learning is achieved at neuronal level using the famous Hebb's law: "Neurons active in the same time frame window reinforce their connections". This rule does not respect "causality". This, plus the fact that there is at least as much feed-back connections as there are feed-forward ones, explain why a high level cortical activation generates a low level cortical pattern of activations -the same one that would trigger this high level activity. Therefore, our opinion is that the true building block of the cognition is a set of feed-forward and feed-back connections between at least two maps, each map a novelty detector.

Due to the fact that the real world is mostly continuous (the shorter the time interval, the smaller the variations) and because the neighboring situations (events) are represented close to each others on the cortical maps, then it is possible to actually "see" and understand activation trajectories (on a map) as representing the various situations encountered (in the real life). It is also straightforward to make a prediction about the coming next situation: the next (column) in line with the current trajectory, and to suppress the transmission to higher levels if successful (in predicting) -therefore reserving higher level maps (such as the ones involved in language) to the processing of the very few events that are non-ordinary (i.e., extraordinary) for the subject. Exterogenous attention is therefore automatically build by to the processing of extraordinary inputs. Endogenous attention is achieved by the mere activation of high level representation, which automatically pre-activates low level localizations (columns) through feed-back connections.

A behavior (i.e., acting) is a sequence of actions related to the achievement of a goal. Any goal can be seen as a situation (to reach). Since situations are associated to columns on maps, a successful behavior is a trajectory on the map that hosts the goal situation, starting from the current situation and ending at the goal situation. The associated actions to perform in order to move from one situation to the next one (closer to the goal) are given by a second map which codes for variations between situations and associated actions [START_REF] Touzet | Modeling and Simulation of Elementary Robot Behaviors using Associative Memories[END_REF]. There is no difference implied by the level of abstraction: a mobile robot avoiding obstacles using as a goal a "situation clear of any obstacle" is similar to a person writing a scientific publication using as a goal its "memorization of readers having understood and learned". As evidenced by V. Braitenberg (e.g., its vehicles experiment), anthropomorphism promptly converts to "love", "hatred", "humor", etc. sequences of actions automatically and very simply defined, such as by a few specific goal situations.

Other typically human cognitive abilities are also better understood through the functioning of a hierarchical structure of cortical maps, such as intelligence and consciousness [START_REF] Touzet | Consciousness, Intelligence, Free-will: the answers from the Theory of neuronal Cognition[END_REF], intrinsic motivation [START_REF] Touzet | The Illusion of Joy[END_REF] or reading [START_REF] Dufau | Developmental Perspective on Visual Word Recognition: New Evidence and a Self-Organizing Model[END_REF].