Andrea Cherubini
email: cherubini@dis.uniroma1.it

F Giannone

L Iocchi
email: iocchi@dis.uniroma1.it

Layered Learning

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

In order for robots to be useful for many real-world applications, they must be able to adapt to novel and changing environments. For this purpose, a popular research field is the annual RoboCup soccer competition 1 . In this domain, many factors, such as the speed of individual robots, the effectiveness of kicks, and the choice of the appropriate attacking strategy, determine the success of a team. The robot should be able to respond to changes in its surroundings by adapting both its low-level skills (e.g., the walking style) and the higher-level skills (e.g., the behaviour) which depend on them.

Firstly, creating effective motion for walking and kicking the ball is a challenging task, since there is a large number of parameters to be set, and since successful motions strongly depend on many factors, including: playing surface, robot hardware, and game situation. In recent years, machine learning techniques have been used to find optimal parameter sets. Secondly, in Robocup matches, the correct choice of the best behaviours required to accomplish a certain task (e.g., to score a goal) is fundamental for success. Machine learning techniques have been used in this field as well, in order to adapt the behaviours to the given game situation. In fact, machine learning generates solutions with little human interaction, and explores the search space of possible solutions in a systematic way, whereas humans are often biased towards exploring a small part of the space. An analysis of the methods used to learn optimal motion parameters and optimal behaviours, and comparisons with the approach presented in this paper, are reported in Section 2.

Following up on these works, we have analyzed different learning techniques for a AIBO soccer robot. In particular, we have considered a layered-like learning approach [START_REF] Stone | Layered learning[END_REF] that is suitable with the large dimensions of the search space we are considering. Besides, we have compared three different methods in the different layers: genetic algorithm (GA), Nelder-Mead (NM), and policy gradient (PG). Finally, we have studied how to use a 3D simulator for speeding up robot learning. The results of our experimental work can be summarized as follows: 1) layered learning is very effective in the complex scenario considered in this paper; 2) using a 3D simulator can actually speed up the learning process on real robots; 3) the learned low-level parameters are strongly related to the desired behavior. We have successfully experimented the presented learning methodology in preparation of RoboCup 2006, showing a notable improvement of performance of the basic behaviours of the robots in our team.

Related Work

Robot learning is a growing area of research at the intersection of robotics and machine learning. It has been used both at low level, for sensing and control issues, and at high level, for cognitive and behavior issues. We include in the first class -parameter learning -all problems where learning is aimed at finetuning of the parameters used by the low level algorithms. In the second classbehavior learning -we consider problems where learning is aimed at finding the optimal composition of simple behaviors for accomplishing a certain task.

In the first class of problems, one of the primary application areas is robot motion control, in all cases where the complete mathematical model is not known, and traditional optimization methods cannot be used. Gait optimization for legged robots is one of such fields. A Genetic Algorithm has been used for optimization of the vector of quadruped walk parameters, as shown in [START_REF] Chalup | Machine learning with AIBO robots in the Four-Legged League of Robocup[END_REF]. Algorithms based on an evolutionary approach achieved four-legged walks of high quality avoiding the need for gradient approximation [START_REF] Chernova | An evolutionary approach to gait learning for fourlegged robots[END_REF][START_REF] Rofer | Evolutionary gait-optimization using a fitness function based on proprioception[END_REF]. Kohl and Stone, from the University of Texas at Austin [START_REF] Kohl | Machine learning for fast quadrupedal locomotion[END_REF], empirically compared four different machine algorithms for quadruped walk optimization. Parameter learning has proved very effective for improving other motion control tasks, such as robot grasping. This task is achieved in [START_REF] Fidelman | The chin pinch: A case study in skill learning on a legged robot[END_REF] by applying the layered learning paradigm [START_REF] Stone | Layered learning[END_REF]: grasping parameters rely on previously learned walk parameters. Another interesting application area for parameter learning is robot vision. Bredeche and others [START_REF] Bredeche | Perceptual learning and abstraction in machine learning: an application to autonomous robots. Systems, Man and Cybernetics[END_REF], for instance, have shown the interest of using biologically inspired perceptual learning mechanisms to improve object identification in real-world environments. Researchers also proved the utility of behavior learning for improving some high level robot tasks, i.e. navigation, exploration, path-planning. Genetic Programming (GP, [START_REF] Koza | Genetic Programming: on the programming of computers by means of natural selection[END_REF]) and Reinforcement Learning (RL) are often used for learning behaviors at the cognitive layer. The adaptation mechanism of GP is similar to that of GAs, except that it is based on symbolic, rather than bit string, representation. In [START_REF] Del R. Millan | Rapid, safe, and incremental learning of navigation strategies[END_REF], RL is efficiently used for concept and rule acquisition in high level navigation in an unknown environment. Behavior learning is also a popular method for solving complex problems in multi-robot systems [START_REF] Martinson | Learning to role-switch in multi-robot systems[END_REF].

To our knowledge, the aforementioned classes of learning (parameter and behaviour learning) have rarely been joined in a single framework. In [START_REF] Arsenio | Developmental learning on a humanoid robot[END_REF], this possibility has been explored: cognitive capabilities are developmentally created, starting from abilities for detecting, segmenting and recognizing objects up to task execution. In such approach, learning can be accelerated by increasing the complexity of the environment while the robot develops [START_REF] Nagai | A developmental approach accelerates learning of joint attention[END_REF]. Moreover, experimental comparisons of different learning methodologies have been rarely addressed. In this work, we focus our attention on the definition of a learning task in which behavior learning and parameter learning are integrated and present an experimental evaluation of a layered learning approach using three different learning techniques: Genetic Algorithm, Policy Gradient and Nelder-Mead Simplex Method.

Problem definition

In this paper we consider learning a complex task as a composition of different behaviors. More specifically, we consider situations in which a task T can be accomplished by applying different strategies, where each strategy is a composition of different behaviors. Each behavior B is characterized by a set of parameters Θ B = {θ 1 , ..., θ k B }. Notice that a behavior can be present in different strategies and possibly requires the definition of different parameters depending on the situation in which it is used. The learning problem is thus twofold: from one hand, behavior learning is needed to select the best strategy, i.e., the best composition of basic behaviors; from the other hand, each behavior needs a fine tuning of each parameter. In the next section we present a learning methodology that integrates behavior and parameter learning for a complex robot task.

To make this problem more clear we will present the application example in which we have tested our method. Consider a robot playing soccer within the RoboCup Four-Legged league competitions. One of the main tasks to be accomplished is to approach the ball and kick it to the opponent goal. This is a complex task that requires the integration of different behaviors in different ways. Many strategies can be defined to accomplish this task, but a winning strategy is difficult to identify since it depends on many factors: position of the robot and of the ball in the field, position of the other robots, etc. Besides, each behavior has several parameters to be tuned: walking gait parameters, kick parameters, etc. Also, these values should depend on the situation at hand: for example, we may prefer a fast but imprecise walk when the robot is far from the ball and an opponent robot is closer, while a slower but precise walk may be better when the robot is close to the ball and no other robots are around. Learning such a complex task requires to define a strategy (as a combination of behaviors) and tune the parameters of the behaviors involved in such a strategy.

System description

As aleady mentioned, we focus on learning the attacking task for a soccer robot in the Four-Legged League, i.e. learning to approach the ball and kick it to the opponent goal in the 'best' way. In the rest of this Section, we will describe our task learning approach, by focusing on: the description of the system (behaviors and parameters of the attacking robot), the definition of learning approach, and the algorithms used for optimization of the robot performance.

Behaviors

For learning the attacking task, a set of six behaviors B P = {B 1 , . . . , B 6 } have been considered. These behaviors (see Figure 1) can be classified in three subsets:

-Ball approaching behaviors: B 1 : fast ball approach (the path length is minimized by an omnidirectional walk), B 2 : aligning ball approach (while the robot approaches the ball, its heading is concurrently oriented towards the opponent goal) -Ball carrying behaviors (aimed at grasping the ball with the robot chin, and orienting the robot heading towards the opponent goal): B 3 : rotational ball carrying (alignment is achieved by pure rotation), B 4 : rototranslational ball carrying (alignment is achieved by a rototranslational movement towards the goal)

-Ball kicking behaviors (realized by direct kinematics control of the 15 joint positions): B 5 : head straight kick (the robot 'dives' on the ball and hits it with the head), B 6 : head spanning kick (the robot 'dives' on the ball and hits it with varying head pan).

A strategy is a combination of such behaviors. In this paper we consider only a simple form of behavior composition: chaining. Thus we consider strategies as sequences of behaviors. For example, {B 1 ; B 4 ; B 5 } is a possible strategy for the attacking task.

Parameters

Each behavior B is characterized by a set of parameters Θ B .

Speed and stability of the ball approach are mainly characterized by the walking gait parameters, which define the kinematic characteristics of the walk. The eleven walking gait parameters Θ W G = {θ W G,1 , . . . , θ W G,11 } are: the relative positions of the locus center for fore/hind feet as (x, y, z) offsets (6 parameters), the height of the steps performed by the fore/hind legs (2 parameters), the step duration (1 parameter), and the maximum amplitude of the locus base for forward and lateral motions (2 parameters).

Walking gait parameters have little influence on the quality of ball carrying, which relies mainly on the way the robot slows down and eventually stops near the ball (i.e. on the ball carrying parameters). The four ball carrying parameters Θ BC = {θ BC,1 , . . . , θ BC,4 }, which control the transition from approaching the ball to grasping it, are: the ball distance at which linear translational slowing down begins, the distance at which the robot stops translating, and similarly the relative robot-ball angle at which linear rotational slowing down begins, and the angle at which it terminates. These parameters also influence the quality of ball control in attacking strategies with no ball carrying (e.g., strategy {B 1 ; B 5 }).

The robot kicks are generated by a sequence of fixed joint positions, related to a timing information, stating for how long the joint values must be kept (i.e. the kick 'speed'). The nine ball kicking parameters Θ BK = {θ BK,1 , ..., θ BK,9 } are: the front legs initial and final angular positions (6 parameters), the robot head tilt initial and final angular positions (2 parameters) and the kick speed (1 parameter).

Learning to attack

Here, we present the optimization problem that must be solved in order to improve the attacker performance, based on the above system characteristics. As aforementioned, we present a learning approach that allows for the concurrent search of optimal behaviors and optimal parameters. The first issue deserves some clarification. We represent the attacker strategy P i with a string of three integers, instead of symbolic expressions. We use the coding function:

c : P i → {φ 1 φ 2 φ 3 } ∈ Z 3 i = 1, . . . , 12
such that: φ 1 indicates the ball approaching behaviour used in strategy P i (1 for B 1 , or 2 for B 2 ), φ 2 the ball carrying behaviour (1 for B 3 , 2 for B 4 , 0 for no ball carrying), and φ 3 the ball kicking behaviour (1 for B 5 , 2 for B 6 ). For example, the strategy {B 1 ; B 4 ; B 5 } is coded with the string {122}.

With this approach, the search for the optimal composition of simple behaviors amounts to a parameter optimization problem in the discrete set S φ ⊂ Z 3 .

In practice, since we consider parameter and behavior learning together, a candidate solution of the optimization problem is:

X = [θW G,1 . . . θW G,11 θBC,1 . . . θBC,4 θBK,1 . . . θBK,9 φ1 φ2 φ3] T ∈ R 24 × S φ
The very large dimensions of the search space, and the system characteristics, suggest the use of the layered learning paradigm [START_REF] Stone | Layered learning[END_REF] for optimizing this problem. In fact, given a hierarchical task decomposition, layered learning allows for learning at each level of the hierarchy, with learning at each level directly affecting learning at the next higher level. The incremental learning approach that we use is inspired by the layered learning paradigm; however, in contrast with classic layered learning, we utilize the same learning method for each layer of the hierarchy. Specifically, we can decompose optimization of the attacker task in the following four optimization subtasks (layers):

-L 1 : find X 1,opt = [θ W G,1 . . . θ W G,11 ] T opt ∈ R 11 for 'best' walk; -L 2 : find X 2,opt = [θ BC,1 . . . θ BC,4 ] T opt ∈ R 4 for 'best' ball carrying, given X 1,opt found by L 1 ; -L 3 : find X 3,opt = [θ BK,1 . . . θ BK,9 ] T opt ∈ R 9
for 'best' ball kicking, given X 1,opt and X 2,opt found by L 2 and by L 3 ; -L 4 : find X 4,opt = [φ 1 . . . φ 3 ] T opt ∈ Z 3 for 'best' attacking strategy, given X 1,opt , X 2,opt , and X 3,opt , found by the three previous layers.

We note k i the dimension of X i at each level L i (k 1 = 11, k 2 = 4, k 3 = 9, k 4 = 3). The solution can be obtained as:

X opt = [X 1,opt X 2,opt X 3,opt X 4,opt ] T
Irrespective of whether we use incremental learning or not, the appropriate choice of the objective function for optimization is fundamental. The function for evaluating the quality of an attacking performance, must take into account: the quality (speed and precision) of the robot motion for approaching the ball, the quality of ball carrying, and the quality (power and precision) of the kick. Hence, we adopt the following objective function:

F (X) = k W G f W G (X) + k BC f BC (X) + k BK f BK (X)
where k W G , k BC , k BK are positive weights indicating the significance desired for each of the three aspects in the learning process, and f W G , f BC , f BK indicate respectively the quality of the walking gait, of ball carrying, and of ball kicking. These functions are derived with heuristics on the robot and ball positions at various stages of the attacking task.

Learning techniques

Our objective is to maximize F (X) in a space of dimension k. This is not trivial, since F (X) is 'black box', and although it can be computed on the real system as well as in the simulated environment, analytical computation of its derivatives is impossible, and all the parameters are box-constrained due to the physical characteristics of the system (we note : ∆ j the range size for each θ j ). Hence, conventional derivative-based optimization methods (e.g. Gradient or Newton methods) cannot be utilized, and convergence analysis of a method is impossible. The selected approach must handle non differentiable search space, have high convergence rate, and be resistent to noise in F (X). A variety of algorithms possess these characteristics. In particular, we will focus on three different machine learning algorithms: Genetic Algorithms, Nelder-Mead Simplex Method, and Policy Gradient. Characteristics of the three methods are briefly presented below.

Genetic algorithms have shown very interesting results in many low level problems [START_REF] Back | Optimization by means of genetic algorithms[END_REF]. A population of q parameter sets (individuals) is used to find a solution for the optimization problem. To evolve a new population from the tested one, the q e best individuals are preserved (elitism) and the remaining individuals are generated by applying crossover (q c individuals) and mutation (q m individuals) operators.

The Nelder-Mead simplex algorithm is a very popular direct search method for multidimensional unconstrained minimization [START_REF] Lagarias | Convergence properties of the Nelder Mead simplex algorithm in low dimensions[END_REF]. In a search space of dimension k, a simplex of v = k + 1 vertices is tested, and subsequently moved through the search space via four possible geometrical transformations: reflection, expansion, contraction, and shrinkage. From an initial parameter set 0 X, the other l X vertices (l = 1, . . . , k) of the first simplex are generated as: l X = 0 X + [0, . . . , ±ζ l , . . . , 0] T .

The Policy Gradient algorithm has been successfully used for robot learning [START_REF] Kohl | Machine learning for fast quadrupedal locomotion[END_REF]. From an initial parameter set 0 X, p randomly generated policies m X (m = 1, . . . , p), near 0 X, are evaluated, such that: m X = 0 X + [ρ 1 , . . . , ρ k ] T , and each ρ j is chosen randomly in the set {+ j , 0,j }. Each m X is grouped into one of three sets for each j: S + ,j , S 0,j or S -,j depending whether its j th parameter was obtained by adding + j , 0 orj . After evaluating the objective function at each m X, average scores F+ ,j , F0,j , and F-,j are computed for S + ,j , S 0,j and S -,j , respectively. These scores are used to construct an estimate of the gradient, which is then normalized, multiplied by a scalar step-size η and added to 0 X, to begin the next iteration.

Experimental results

In this section we report the experimental results that we obtained by applying the proposed learning methodology in the described robot soccer scenario. More specifically, we comment on three results: 1) the effectiveness of the incremental approach; 2) the comparison among the three learning methods implemented: Genetic Algorithms, Nelder-Mead, and Policy Gradient; 3) the effectiveness of using a 3D simulator for speeding up the learning process.

We have executed the incremental learning approach presented in the previous section, but without considering the fourth layer L 4 , since this would require additional input to the system. In fact, selecting the best strategy depends on other variables, such as the position of the robot and of the ball with respect to the target goal, the position of other robots in the field, etc. For layer L 4 it is necessary to learn a function that maps the current situation with a suitable strategy for that situation. This aspect needs to be further investigated and it is thus beyond the scope of the present paper.

In practice, we applied incremental learning, focused on layers L 1 to L 3 , for optimizing the strategy P 1 = {B 1 , B 5 }, i.e., the robot approaches the ball as fast as possible, and kicks it forward, without grasping it, with fixed head pan. Learning this task has been initially developed and configured within the 3D AIBO simulator [START_REF] Zaratti | A 3D simulator of multiple legged robots based on USARSim[END_REF] embedded in USARSim (Urban Search and Rescue Simulator), before experimentation on the real robot. In fact, one of the objectives of this work is to show that the learning configurations tuned in the simulated environment can be successfully ported for learning on the real robot.

Here, we briefly outline the configurations of the three learning algorithms. For the genetic algorithm, we chose: q = 10, q e = 1, q c = 6, q m = 3. Selection of individuals from the original population is based on the popular roulette wheel scheme, and mutation is obtained by altering the j th parameter with an offset chosen randomly in the set [-0.2 j , +0.2 ∆ j ]. For the Nelder-Mead algorithm, at each layer L i : v = k i + 1, and ζ l = ±0.2 ∆ j , with the sign of ζ l chosen randomly. For the policy gradient, we use for the three layers: p 1 = 8, p 2 = 4, p 3 = 6, j = 0.1 ∆ j , η = 3.

The same initial parameter set 0 X is used for starting each learning technique. Since there is significant noise in each experiment, each set of parameters is evaluated three times, and the resulting fitness evaluated for that set, is computed by averaging over the three experiments. For each layer, and each learning technique, we terminate learning after a number of evaluations equal to: 10k i has been performed (e.g. for L 1 , 110 evaluations, i.e., 330 experiments). We choose to use the same amount of learning time, since this is usually a given specification in learning problems. The results of the incremental learning algorithm are shown in Fig. 2(a), where the best fitness value found by the learning algorithms is plotted over the number of evaluations. A similar plot is shown in Fig. 2(b), where we ran the same number of evaluations by learning all 24 parameters at the same time Comparison between the two plots confirms the qualitative properties of the incremental approach: for instance, for the GA, the final fitness obtained by the incremental approach is 34% higher than that obtained by learning all parameters together, and the slope of the interpolating line is greater (0.97 versus 0.60) in Fig. 2(a) than in Fig. 2(b). Nelder-Mead slightly outperforms Genetic Algorithm and Policy Gradient.

Other experiments were carried out to show how the optimal low-level parameters are strongly related to the desired behavior. To emphasize this aspect, we used the same learning configuration used for optimizing strategy P 1 = {B 1 , B 5 }, to optimize strategy P 2 = {B 1 , B 3 , B 5 } (the robot approaches the ball as fast as possible, rotates while grasping it, and kicks it forward with fixed head pan). This experiment was carried out with the genetic algorithm, in USARSim: starting from the optimal walking gait parameters X 1,opt learned for the previous strategy, we proceeded with the other two levels to derive X 2,opt and X 3,opt . Comparison between the optima learned for P 1 and P 2 showed major differences. In fact, for P 1 , the optimal parameters are: The differences are reasonable: for P 2 , the robot must slow down farther away from the ball (parameters θ BC,1 and θ BC,2 are different in the two cases) and the head movement for kicking the ball (which in P 2 has been grasped) is different and depends on parameters θ BK,7 and θ BK,8 . After having configured the algorithm for learning strategy P 1 in the 3D simulated environment, we ported it on the real robot. The initial parameter set for each technique is the set derived at the end of simulator optimization. This time, for each layer, and each learning technique, we terminate learning after a number of evaluations equal to 5 k i has been performed. The results of the incremental learning algorithm are shown in Fig. 3(a), where the best fitness value is plotted over the number of evaluations. On AIBO, policy gradient slightly outperforms the two other approaches.

To emphasize how the use of a 3D simulator speeds up the learning process on real robots, we ran another experiment where the GA was used to learn L 1 for the same strategy P 1 , starting from a random population, different from the one derived at the end of USARSim optimization. The results of this experiment are shown in Fig. 3(b), where the fitness of GA walking gait learning starting from different populations are plotted: the figure clearly shows the advantage of the simulator for deriving the GA initial population.

Conclusions

In this paper we presented a layered-like approach for learning optimal parameters, and strategy selection. We compared three different methods in the different layers: genetic algorithm, Nelder-Mead, and policy gradient. Moreover, we showed how the use of a 3D simulator speeds up robot learning.

The proposed learning methodology has been applied to the soccer attacking task. It has been implemented in USARSim and extensively experimented in laboratory on AIBO, showing a notable improvement in the performance of the robot basic behaviours. The main results of the experiments are: the utility of the layered approach for this complex scenario, and the effectiveness of the 3D simulator for configuring the learning algorithms before porting on the robot.

Incremental learning has been executed without considering the strategy selection layer. In fact, this depends on the 'game situation' (e.g., positions of robot and ball with respect to the goal). Learning a function that maps the game situation with a suitable strategy will be the object of further work.

Fig. 1 .

 1 Fig. 1. The six behaviours that can be used in the attacking task.

Fig. 2 .

 2 Fig. 2. Fitness values at each evaluation during USARSim training (solid lines: GA in blue, NM in green and PG in red) and linear interpolations (dashed lines): (a) incremental learning, (b) learning all parameters.

Fig. 3 .

 3 Fig. 3. Fitness values during AIBO training: (a) incremental learning (solid lines: GA in blue, NM in green, PG in red) with start point derived from USARSim, and linear interpolations (dashed lines), (b) comparing GA for L1: with initial population derived from USARSim (solid blue line), and with random initial population (solid black line), and linear interpolations (dashed lines).

X 2 ,

 2 opt = [148 5 50 6] T X 3,opt = [21 44 969 1611 30 0 -684 -350 26] T whereas for P 2 , the optimal parameters are: X 2,opt = [300 100 100 7] T X 3,opt = [19 71 908 1654 10 0 -879 -247 17] T

In this work, we focus on AIBO robots and RoboCup Four-Legged league (see www.tzi.de/4legged/)


A Cherubini
email: cherubini@dis.uniroma1.it

F Giannone

L Iocchi
email: iocchi@dis.uniroma1.it

P F Palamara

An extended policy gradient algorithm for robot task learning

In real-world robotic applications, many factors, both at low-level (e.g., vision and motion control parameters) and at high-level (e.g., the behaviors) determine the quality of the robot performance. Thus, for many tasks, robots require fine tuning of the parameters, in the implementation of behaviors and basic control actions, as well as in strategic decisional processes. In recent years, machine learning techniques have been used to find optimal parameter sets for different behaviors. However, a drawback of learning techniques is time consumption: in practical applications, methods designed for physical robots must be effective with small amounts of data. In this paper, we present a method for concurrent learning of best strategy and optimal parameters, by extending the policy gradient reinforcement learning algorithm. The results of our experimental work in a simulated environment and on a real robot show a very high convergence rate.

I. INTRODUCTION

In order for robots to be useful for real-world applications, they must adapt to novel and changing environments. In most domains, the robot should be able to respond to changes in its surroundings by adapting both its low-level skills (e.g., vision or motion control parameters) and the higher-level skills (e.g., the behaviors) which depend on them.

Recently, machine learning techniques have been used in many robotic applications, both for finding optimal parameter sets of specific behaviors and for determining the best choice of behaviors required to accomplish a task in a given situation. In fact, machine learning approaches generate solutions with little human interaction, and explore the search space of possible solutions in a systematic way, whereas humans are often biased towards exploring a small part of the space.

Despite this growing interest, considerable work remains, due to the difficulties associated with machine learning in the real world. Compared to other machine learning scenarios such as classification or action learning in simulation, learning on physical robots presents several formidable challenges. In particular, learning methods designed for physical robots must be effective with small amounts of data, and should converge in short time. Indeed, it is often prohibitively difficult to generate large amounts of data due to the maintenance required on robots, such as battery changes, hardware repairs, and, usually, constant human supervision. Thus, learning methods designed for physical robots must be effective with small amounts of data. Other practical issues that make robot learning extremely challenging are the time and material constraints: to be of practical use for robotics, the learning algorithms must converge in a relatively small number of training epochs [START_REF] Chalup | Machine learning with AIBO robots in the four-legged league of robocup[END_REF].

Following up on all these considerations, and on our previous work [START_REF] Cherubini | Layered learning for a soccer legged robot helped with a 3D simulator[END_REF], we have developed an extended version of the policy gradient learning technique introduced in [START_REF] Kohl | Policy gradient reinforcement learning for fast quadrupedal locomotion[END_REF]. In [START_REF] Cherubini | Layered learning for a soccer legged robot helped with a 3D simulator[END_REF], we have shown the effectiveness of the incremental learning approach in complex robot learning scenarios. We have also studied how to use a 3D simulator for speeding up robot learning. Finally, we have shown that the learned lowlevel parameters are strongly related to the desired behavior. Consequently, the extended policy gradient algorithm that we propose in this work must learn the best strategy (i.e., composition of simple behaviors), and correspondingly the best parameters for accomplishing a given task. Our approach guarantees faster training than the classic policy gradient [START_REF] Kohl | Policy gradient reinforcement learning for fast quadrupedal locomotion[END_REF], by exploiting additional information on the system properties, such as the contiguities between strategies, and the relevance of the behavior parameters.

The method has been tested in the application example of an attacker robot in the RoboCup Four-Legged League. However, in our opinion, the algorithm is flexible, and can be extended in order to optimize tasks different from soccer attack on robot platforms different from Sony AIBO.

II. RELATED WORK

Robot learning is a growing area of research at the intersection of robotics and machine learning. It is used both at low level, for sensing and control issues, and at high level, for cognitive and behavior issues. We include in the first class -parameter learning -all problems where learning is aimed at fine-tuning of the parameters used by the low level algorithms, and in the second class -behavior learning -problems where learning aims at finding the optimal composition of behaviors for accomplishing a task.

In the first class of problems, one of the primary application areas is robot motion control, in all cases where the complete mathematical model is not known, and traditional optimization methods cannot be used. Gait optimization for legged robots is one of such fields [START_REF] Chalup | Machine learning with AIBO robots in the four-legged league of robocup[END_REF]. Parameter learning has proved very effective for improving other motion control tasks, such as robot grasping. In [START_REF] Fidelman | The chin pinch: A case study in skill learning on a legged robot[END_REF], this is achieved by applying the layered learning paradigm [START_REF] Stone | Layered learning[END_REF]: grasping parameters rely on previously learned walk parameters. Another interesting application area for parameter learning is robot vision. In [START_REF] Bredeche | Perceptual learning and abstraction in machine learning: an application to autonomous robots[END_REF], for instance, biologically inspired perceptual learning mechanisms are used to improve object identification in real-world environments.

On the other hand, researchers have proved the utility of behavior learning for improving high level robot tasks, e.g. navigation, exploration, path-planning. In the behavioral decomposition approach, the desired behavior is broken down into a set of simpler behaviors, which are activated or suppressed through a coordination mechanism. The structure of the simpler behavioral modules can emerge from a learning process, instead of being pre-designed. Nolfi [START_REF] Nolfi | Evolutionary robotics: Exploiting the full power of selforganization[END_REF] showed how a good evolutionary approach can produce simpler and more robust solutions, than those designed by hand. The robot can evolve by adapting its behaviors to various constraints on the environment, on the desired task, and on the user satisfaction. Genetic Programming (GP, [START_REF] Koza | Genetic Programming: on the programming of computers by means of natural selection[END_REF]) and Reinforcement Learning (RL, [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]) are useful tools for learning behaviors at the cognitive layer. The adaptation mechanism of GP is similar to that of Genetic Algorithms, except that it is based on symbolic, rather than bit string, representation.

To our knowledge, the aforementioned classes of learning (parameter and behavior learning) have rarely been joined in a single framework. One reason is the long time required to solve the optimization problem in the large search space including both parameters and behaviors. Here, we present a fast method based on the policy gradient reinforcement learning technique [START_REF] Sutton | Policy gradient methods for reinforcement learning with function approximation[END_REF] useful in all cases where behavior and parameter learning should be integrated for optimal task execution. Our method can be considered an extended version of the policy gradient technique introduced in [START_REF] Kohl | Policy gradient reinforcement learning for fast quadrupedal locomotion[END_REF], which takes into account behavior similarities and parameter relevance during the learning process, to speed up convergence. Experimental comparison between the policy gradient from [START_REF] Kohl | Policy gradient reinforcement learning for fast quadrupedal locomotion[END_REF] and the extended version that we propose is carried out in this work, based on an incremental learning approach.

III. PROBLEM DEFINITION

In this paper we consider learning a complex task as a composition of different behaviors. More specifically, we consider situations in which a task T can be accomplished by applying different strategies, where each strategy is a composition of different behaviors. Each behavior B is characterized by a set of parameters Θ B = {θ 1 , ..., θ k B }. Notice that a behavior can be present in different strategies and possibly requires the definition of different parameters depending on the situation in which it is used.

The learning problem is thus twofold: behavior learning is needed to select the best strategy (i.e., the best composition of basic behaviors) and meanwhile each behavior requires fine tuning of each parameter. As in any robot learning problem, the proposed algorithm should minimize time consumption, which is often related to 'hardware consumption' in real robot applications. Hence, the algorithm must converge to the best solution after few iterations.

The learning problem we are interested in is the following. Given a set S of different strategies for accomplishing a certain task T , we want to learn the best choice of the strategy, as well as the parameters Θ B that ensure the best performance on the execution of the best strategy. Two main difficulties arise when dealing with this problem: 1) the choice of an optimal strategy, 2) an optimization problem in the behavior parameters space.

In general, the choice about which strategy must be selected to perform a task is not easy. This is firstly due to the fact that in complex scenarios, the winning strategy depends on the context (i.e., the current situation of the environment around the robot). Secondly, some strategies can perform similarly in a given context: this similarity (contiguity) can be used to speed up the learning process. Thirdly, a coarse initial design of the learning algorithm can lead to overestimation of the search space dimensions. In particular, this occurs when parameters which have little relevance on the performance are learned. Based on these considerations, we will show that the speed of a robot task learning algorithm can be improved by: 1) detecting and exploiting similarities between learned strategies, and 2) updating the search space dimensions, by removing irrelevant parameters during learning.

Furthermore, in the optimization of behavior parameters, the optimization function is not known ('black box') and analytical computation of its derivatives is impossible. Besides, the parameters are box-constrained due to the physical characteristics of the system. Hence, conventional derivativebased optimization methods (e.g., Gradient or Newton methods) cannot be utilized The selected approach must handle non differentiable search space, have high convergence rate and be resistent to noise.

CLASSIC POLICY GRADIENT INPUT: S, v X 0 , N iter OUTPUT: S v * , v * X * 1 initialize parameter set for all strategies: v X ← v X 0 2 for each strategy v = 1 to N str 3 v X * = classic policy gradient ( v X 0 , N iter ) 4 endfor 5 v * ← arg max v F ( v X * ) 6 return (S v * , v * X * ) 7 END
Many algorithms possess these characteristics. In particular, we will utilize the Policy Gradient learning algorithm, which has been successfully used for robot learning [START_REF] Kohl | Policy gradient reinforcement learning for fast quadrupedal locomotion[END_REF], [START_REF] Cherubini | Layered learning for a soccer legged robot helped with a 3D simulator[END_REF].

In the next section we present a general learning methodology that integrates behavior and parameter learning for executing a complex robot task in a small amount of experiments. The approach is based on an extension of the policy gradient algorithm that allows for significantly increased convergence rate for complex robot tasks.

IV. COMPLEX TASK LEARNING

The method for task learning proposed in this paper aims at determining at the same time the best strategy and the optimal parameters to be used in the behaviors used in such a strategy. We will refer in the following to a set of N str different strategies for accomplishing the task T : S= {S 1 , . . . , S Nstr }. Each strategy is characterized by a set of behaviors, for which we want to optimize the characteristic parameters. Let v X ∈ R n be a representation of the parameters used by behaviors in the strategy S v . Although, in general, different strategies have different parameter spaces, we will assume that the parameters of the behaviors for all the strategies can be represented as a vector in R n . Furthermore, we will denote with F the fitness function used to evaluate strategies and parameters and thus with F ( v X) the evaluation of the parameters X within the strategy S v .

The objective of the leaning process is to learn the best choice of the strategy S v * , along with the optimal parameters v * X * that ensure the best performance on the execution of that strategy, i.e., that maximize F ( v X). To achieve this goal, we first present a straightforward application of policy gradient approach, and then describe a novel extended method that substantially increases convergence rate. The first method simply consists of solving N str independent optimization problems (one for each strategy) in R n , and choose the pair S v * , v * X * that returns the highest fitness value for task T .

A. Classic policy gradient method

The policy gradient algorithm [START_REF] Kohl | Policy gradient reinforcement learning for fast quadrupedal locomotion[END_REF] estimates the gradient of the objective function in the parameter space and follows it towards a local optimum. The parameter optimization approach starts from an initial parameter set X 0 and proceeds to estimate the partial derivative of F (X 0 ) with respect to each parameter. From the initial set X 0 , p randomly generated policies m X (m = 1, . . . , p), near X 0 , are evaluated, such that: m X = X 0 + [ρ 1 , . . . , ρ k ] T , and each ρ j is chosen randomly in the set {j , 0, + j }. Each m X is grouped into one of three sets for each j: G -,j , G 0,j or G + ,j depending whether its j th parameter was obtained by addingj , 0 or + j . After evaluating the objective function at each m X, average scores F-,j , F0,j , and F+ ,j are computed for G + ,j , G 0,j and G -,j , respectively. These scores are used to construct an estimate of the gradient, which is then normalized, multiplied by a scalar step-size η and added to X 0 , to begin the next iteration i (i = 1, . . . , N iter ). Pseudocode for learning the best strategy S v * and the corresponding best parameters v * X * for a given task T , using the policy gradient method, is shown in Fig. 1. The function classic policy gradient ( v X 0 , N iter ), summarizes the algorithm described in [START_REF] Kohl | Policy gradient reinforcement learning for fast quadrupedal locomotion[END_REF].

B. Extended policy gradient method

Although effective, the method described above does not exploit two important factors of this learning process: similarities between strategies and relevance of parameters.

In this section, we present an extension of the method, which additionally takes into account: contiguities between strategies, and relevance of parameters within each strategy, to fasten the learning process. Let us define, at every iteration step ī = 0, the following metrics:

• Contiguity between strategies S v and S w :

C ī(v, w) = 1 d( v X ī, w X ī) + 1
where:

d( v X ī, w X ī) = k j=1 v X ī j -w X ī j 2
is the euclidean distance between v X ī and w X ī. We also note v P i the set ('cluster') containing all points w X i which are 'near' v X i . • Relevance of parameter j for a given strategy v: it is the norm of the weighted average of the j th gradient component:

R ī(v, j) = ī i=1 λ ī-i v X i j ī i=1 λ ī-i
where 0 < λ < 1 is a forgetting factor that operates as a weight diminishing for the more remote data. Small values of the relevance imply that the estimated gradient varies 'slightly' along the j th component during the learning process: hence, we assume that the corresponding parameter has little relevance on the system performance. We denote with v J i ⊆ {1, . . . , v k i } the subset of relevant parameters (i.e., parameters j with 'high' R i (v, j)) for learning strategy v at iteration i. v J i is updated at each iteration step i during the learning process, depending on the values of R i (v, j). The extended algorithm is shown in Fig. 2. This algorithm has a similar structure than the one described in the previous section, but it contains two major improvements. Firstly, for each strategy, the subset v J i is updated, and at each iteration, policies are generated by perturbing only relevant parameters; hence, the size of the search space is reduced, and the algorithm convergence is faster. Secondly, for contiguous strategies, points reached at each learning iteration and belonging to v P i are evaluated, and the best point is chosen as the initial point for the next iteration for each of the contiguous strategies.

EXTENDED POLICY GRADIENT INPUT: S, v X 0 , N iter OUTPUT: S v * , v * X * 1 initialize for all v: v X ← v X 0 , v J 0 ≡ {1, . . . , v k 0 } 2 for each iteration i = 1 to N iter 3 for each strategy v = 1 to N str 4 generate v m X i perturbations of v X i-1 on v J i-1 5 evaluate F ( v X i ) at all p policies v m X i for task T 6 v J i ← ∅ 7
for each parameter j ∈ v J i-1 8 evaluate F-,j , F0,j , and F+ ,j 9

if F0,j > F-,j and F0,j > F+ ,j

10 v X i j ← 0 11 else 12 v X i j ← F+ ,j -F-,j 13 endif 14 evaluate R i (v, j) 15 if R i (v, j) > T r (T r a given threshold) 16 v J i ← v J i ∪ j 17 endif 18 endfor %parameters 19 v X i ← η × v X i | v X i | 20 v X i ← v X i-1 + v X i 21 endfor %strategies 22 for each strategy v = 1 to N str 23 for each strategy w = 1 to N str 24 evaluate C i (v, w) 25 if C i (v, w) > T c (T c a given threshold) 26 v P i ← v P i ∪ w X i 27 endif 28
endfor %strategies w 29 evaluate F (X) at all X ∈ v P i 30 v X i ← arg max

X∈ v P i F (X) 31 endfor %strategies v 32 endfor %iterations 33 for each strategy v = 1 to N str 34 v X * ← arg max i F ( v X i ) 35 endfor %strategies v 36 v * ← arg max v F ( v X * ) 37 return (S v * , v * X * ) 38 END

V. SOCCER ROBOT APPLICATION

Concurrent behavior and parameter learning is useful in many complex high dimensional systems. Here we present a detailed example on which the proposed method has been applied and experimented (results are commented in Section VI). We consider a robot playing soccer within the RoboCup Four-Legged league competitions. One of the main tasks to be accomplished in this scenario is to approach the ball and kick it to the opponent goal. This is a complex task that requires the integration of different behaviors in different ways. Many strategies can be defined to accomplish this task, but a winning strategy is difficult to identify since it depends on many factors: position of the robot and of the ball in the field, position of the other robots, etc. Besides, each behavior has several parameters to be tuned: walking gait parameters, kick parameters, etc. Also, these values should depend on the situation at hand: for example, we may prefer a fast but imprecise walk when the robot is far from the ball and an opponent robot is closer, while a slower but precise walk may be better when the robot is close to the ball and no other robots are around. Learning such a complex task requires to define a strategy (as a combination of behaviors) and tune the parameters of the behaviors involved in the strategy.

Learning the attacking task for a soccer robot consists in learning to approach the ball and kick it to the opponent goal in the 'best' way. In the rest of this section, we will describe our task learning process, by describing behaviors and parameters of the attacking robot and some implementation details of the proposed algorithm.

A. Behaviors

For learning the attacking task, a set of seven behaviors B P = {B 1 , . . . , B 7 } has been considered. These behaviors (see [START_REF] Cherubini | Layered learning for a soccer legged robot helped with a 3D simulator[END_REF] for further details) can be classified in three subsets:

• Ball approaching behaviors:

-B 1 : fast ball approach -the path length is minimized by an omnidirectional walk; -B 2 : aligning ball approach -while the robot approaches the ball, its heading is concurrently oriented towards the opponent goal; • Ball controlling behaviors:

-B 3 : rotational ball carrying -the robot grasps the ball with its chin, and subsequently orients its heading towards the opponent goal; -B 4 : gradual ball reaching -the robot gradually decreases its translational and rotational velocities in order to reach the ball without knocking it; • Ball kicking behaviors:

-B 5 : head straight kick -the robot 'dives' on the ball and hits it with the head -the head pan angle is kept null during this kick; -B 6 : head spanning kick -the robot 'dives' on the ball and hits it with varying head pan: the kick is more powerful but less precise than B 5 ; -B 7 : lateral head kick -the robot hits the ball laterally with a varying head pan angle. A strategy is a combination of such behaviors. In this paper we consider only a simple form of behavior composition: chaining between a ball approaching, a ball controlling, and a ball kicking behavior. Thus we consider strategies as sequences of three behaviors. For example, {B 1 ; B 3 ; B 5 } is a possible strategy for the attacking task.

B. Parameters

Each behavior B is characterized by a set of parameters Θ B . The parameters are box-constrained due to the physical characteristics of the system, and we note ∆ j the range size for each θ j .

Speed and stability of the ball approach are mainly characterized by the walking gait parameters, which define the kinematic characteristics of the walk. The trot gait is used, with a half-ellipsoidal locus shape for foot motion, and contact between the base of the locus and the ground generates body motion. The gait is characterized by the eleven walking gait parameters:

Θ W G = {θ W G,1 , . . . , θ W G,11 }.
Walking gait parameters have little influence on the quality of ball control, which relies mainly on the way the robot slows down and stops near the ball (i.e. on the ball controlling parameters). We use translational and rotational slowing down velocities that are respectively proportional to the ball distance and to the relative robot-ball angle.

Thus, ball control is influenced by the four parameters: Θ BC = {θ BC,1 , . . . , θ BC,4 }.

The robot kicks are generated by a sequence of fixed joint positions (for AIBO's 15 joints), at three stages of the kick, related to a timing information, stating for how long the joint values must be kept (i.e. the kick 'speed'). Motion of the back leg joints is fixed (since it has little influence on the kick quality), whereas motion of the head and front legs should be learned. Hence, twenty three ball kicking parameters Θ BK = {θ BK,1 , ..., θ BK,23 } are used.

The behaviors are not influenced by all of the parameters: in practice, each behavior is characterized by a subset of such parameters. For instance, the ball distance at which the robot stops translating (θ BC,2 ), may be fundamental for behavior B 4 and irrelevant for B 3 . In particular, we are interested in learning the seven sets of parameters Θ B :

Θ B1 ⊆ Θ W G Θ B2 ⊆ Θ W G Θ B3 ⊆ Θ BC Θ B4 ⊆ Θ BC Θ B5 ⊆ Θ BK Θ B6 ⊆ Θ BK Θ B7 ⊆ Θ BK

C. Learning configuration

The learning process consists in chosing the best strategy and optimizing the parameter sets: Θ W G , Θ BC , and Θ BK . These sets are represented as a vector:

X = [θW G,1. . .θW G,11θBC,1. . .θBC,4θBK,1. . .θBK,23] T ∈ R 38
that also represents a candidate solution of the optimization problem. As already mentioned, these sets might include parameters which are irrelevant for the strategy, and the learning algorithm will deal with them.

The very large dimensions of the search space, and the system characteristics, suggest the use of the layered learning paradigm [START_REF] Stone | Layered learning[END_REF] for optimizing this problem. In fact, given a hierarchical task decomposition, layered learning allows for learning at each level of the hierarchy, with learning at each level directly affecting learning at the next higher level. The incremental learning approach that we use is inspired by the layered learning paradigm; however, in contrast with classic layered learning, we utilize the same learning method for each layer of the hierarchy. Specifically, we decompose optimization of the strategy parameters in the following three optimization subtasks (layers):

•

L 1 : find X 1,opt = [θ W G,1 . . . θ W G,11 ] T opt ∈ R 11 for 'best' walk; • L 2 : find X 2,opt = [θ BC,1 . . . θ BC,4 ] T opt ∈ R 4 for 'best' ball control, given X 1,opt found by L 1 ; • L 3 : find X 3,opt = [θ BK,1 . . . θ BK,23 ] T opt ∈ R 23 for 'best' kicking, given X 1,opt and X 2,opt found by L 1 and L 2 .
The solution of the attacker strategy optimization problem can then be obtained as:

X opt = [X 1,opt X 2,opt X 3,opt ] T
The appropriate choice of the objective function for optimization is fundamental. The function for evaluating the quality of an attacking strategy -the fitness function -must take into account: the quality (speed and precision) of the robot motion for approaching the ball, the quality of ball control, and the quality (power and precision) of the kick. Hence, we adopt the following objective function:

F (X) = K W G f W G (X) + K BC f BC (X) + K BK f BK (X)
where f W G , f BC , f BK indicate respectively the quality of the ball approaching, ball controlling, and ball kicking behavior used. These functions are derived with heuristics on the robot and ball positions at various stages of the attacking strategy execution. The functions are derived identically for behaviors in the same subset (e.g., f BC is derived in the same way for B 3 and B 4 ). K W G , K BC , and K BK are positive weights indicating the significance desired for each of the three aspects in the learning process. F (X) is thus identical (i.e., same functions f W G , f BC and f BK and same weights) for all the strategies used to execute the attacking task.

VI. EXPERIMENTAL RESULTS

In this section, we report the experimental results obtained by applying the two proposed policy gradient methods for task learning in the described robot soccer scenario. We take advantage of two results from our previous work [START_REF] Cherubini | Layered learning for a soccer legged robot helped with a 3D simulator[END_REF]: the utility of using a 3D simulator for speeding up the learning process, and the effectiveness of the incremental approach for robot task learning. The major contribution of the experiments is the comparison between the classic and extended policy gradient methods presented in Section IV.

The objective of the learning algorithms is to find the most suitable strategy S v * and the corresponding optimal parameters v * X * for a given task. In practice, we focus on the following task T : ball 50 cm in front of robot, and direction from ball to goal orthogonal to the robot sagittal axis, with the goal on the right of the robot. The five strategies chosen to achieve the task are:

S1 = {B1 B3 B5} S2 = {B1 B3 B6} S3 = {B1 B4 B7} S4 = {B2 B4 B5} S5 = {B2 B4 B6}
The performance of these strategies can be compared, since the objective function is the same for all the strategies. Learning this task is initially implemented with the 3D AIBO simulator [START_REF] Zaratti | A 3D simulator of multiple legged robots based on USARSim[END_REF] embedded in USARSim1 before experimentation on the real robot. In fact, in [START_REF] Cherubini | Layered learning for a soccer legged robot helped with a 3D simulator[END_REF], we have shown that the learning configurations tuned in the simulated environment can be successfully ported on the real robot.

We utilize the incremental learning approach presented in the previous section. For the 3 layers, we choose the policy gradient configuration: j = 0.1 ∆ j , η = 3. In the classic version, the number of policies p at the 3 layers is set to: p 1 = 8, p 2 = 4, p 3 = 16. Instead, in the extended version, since the number of parameters decreases during the learning process (depending on their relevance), p is set to two thirds of the number of parameters to be learned. The same initial parameter set 0 X is used for starting learning on each strategy v. Since there is significant noise in the experiments, each set of parameters is evaluated twice, and the resulting fitness evaluated for that set, is computed by averaging over the two experiments. In USARSim, since 'hardware consumption' is not an issue, for each layer, we compare the learning algorithms after 10 k i evaluations have been performed (e.g. for L 3 , 240 evaluations, i.e., 480 experiments). Comparison between extended and classic policy gradient has been carried out at layer L 3 . For the first two layers, classic policy gradient learning has been used to derive X 1,opt and X 2,opt . The results of incremental learning at L 1 and L 2 are shown in Fig. 3, where the best fitness value found by classic policy gradient is plotted over the number of evaluations, for each of the 5 strategies.

Afterwards, we proceed by learning layer L 3 with the classic and extended policy gradient. To emphasize the capability of the extended version to filter out irrelevant parameters, we add a 24 th irrelevant parameter θ BK,24 (which is not used by the robot for kicking the ball) to the set Θ BK . The results of learning L 3 with the classic policy gradient are shown in Fig. 3. The extended policy gradient is initially experimented by considering solely parameter relevance. We use: T r = 0.03 and λ = 0.8. At the end of the learning process, for all five strategies, approximately 50% of the parameters are filtered out (e.g., 11 parameters for S 1 , 13 parameters for S 4 ). For all strategies, θ BK,24 is filtered out during the learning process. The fitness values during learning with parameter reduction are shown in Fig. 4: for all strategies, the final fitness outperforms the fitness obtained with the classic algorithm. The best improvements are for strategies S 2 (the fitness increases by 18%) and S 5 (14%). For strategy S 2 (which prevails in the experiments), the gradient component and relevance of parameters: θ BK,3 , θ BK,13 and θ BK,24 are plotted in Fig. 5. Note that, as expected, θ BK,24 is filtered out In the next experiment, strategy contiguity is also utilized in the extended algorithm, along with parameter relevance; we set T c = 0.002. For all strategies, the final fitness (plotted in Fig. 6) outperforms the fitnesses obtained with the classic algorithm and with the extended version that considers only parameter relevance. The best improvements are for strategies S 3 (the fitness increases by 35% with respect to classic policy gradient) and S 5 (21%). During the learning process, the algorithm takes advantage of the contiguities between strategies S 1 , S 2 and S 3 and also between strategies S 1 , S 4 and S 5 . With this complete version of the extended policy gradient, strategy S 4 prevails.

Finally, both algorithms are ported on the real robot, for comparison at learning X 3,opt with fixed: X 1,opt , X 2,opt . The strategies that performed better in USARSim (S 2 and S 4 ) are used. For each strategy, three experiments are carried out. Firstly, classic policy gradient is applied for learning all 24 parameters (dotted curves in Fig. 7). Then (dashed curves), classic policy gradient is applied for learning only the relevant parameters (12 parameters in S 2 , 13 in S 4 ) derived in the simulated experiments. Finally (solid curves), the extended policy gradient is used, by reducing the parameter set initialized with the relevant parameters derived in USARSim. The initial parameter sets are the final sets obtained from USARSim training. Each set of parameters is evaluated twice, and the resulting fitness is obtained by averaging. This time, we terminate learning after 120 evaluations have been performed. For both strategies, the utility of reducing the parameter set in the simulated environment before porting on the real robot is visible by comparison of the dotted and dashed curves in Fig. 7. Further improvement, as expected, is obtained by reducing the parameter set throughout the learning process (solid curves). At the end of the experiments, 10 parameters are preserved for S 2 , 9 for S 4 . Hence, 2 parameters for S 2 and 4 for S 4 have not required further adjustment on the real robot after USARSim training.

VII. CONCLUSIONS

In this paper, we presented a method for concurrent learning of best strategy and optimal parameters, by extending the policy gradient reinforcement learning algorithm. The proposed method guarantees fast convergence by exploiting information on the system properties, while learning. In particular, the contiguities between strategies, and the pa- The proposed learning technique has been applied to the soccer attacking task. It has been implemented in USARSim and extensively experimented in laboratory on AIBO, showing a notable improvement in the learned robot performance with respect to robot performance learned with classic policy gradient. Firstly, our technique outperforms classic policy gradient when the comparison is carried out over the same number of evaluations. Moreover, the convergence rate of our technique is higher than that of classic policy gradient: the same fitness value (e.g., in USARSim, 400) is attained much earlier (145 evaluations in advance). These results are fundamental in robot applications, where hardware consumption is a major issue. Development of a robot task learning algorithm that identifies the system major characteristics during training could be the object of further work.

Fig. 1 .

 1 Fig. 1. Pseudocode for classic policy gradient task learning.

Fig. 2 .

 2 Fig. 2. Pseudocode for extended policy gradient task learning.

Fig. 3 .

 3 Fig. 3. The best fitness values obtained from each evaluation during USARSim training with classic policy gradient at layers: L 1 (strategies S 1 , S 2 and S 3 in black, S 4 and S 5 in grey), L 2 (strategies S 1 , S 2 in red, S 3 in green, S 4 and S 5 in blue) and L 3 : S 1 (orange), S 2 (red), S 3 (green) S 4 (blue) and S 5 (cyan).

Fig. 4 .

 4 Fig. 4. The fitness values obtained during USARSim training with extended policy gradient (considering parameter relevance) at L 3 : S 1 (pink), S 2 (red), S 3 (green) S 4 (cyan) and S 5 (blue).

Fig. 5 .

 5 Fig. 5. Evolution of gradient component (dashed line) and relevance (continuous line) of: θ BK,3 (green), θ BK,13 (red) and θ BK,24 (blue) during USARSim training of S 2 at L 3 : circles indicate the evaluation step where the parameter becomes irrelevant (the black line indicates Tr).

Fig. 6 .

 6 Fig. 6. The fitness values obtained during USARSim training with extended policy gradient (considering parameter relevance and strategy contiguity) at L 3 : S 1 (pink), S 2 (red), S 3 (green) S 4 (cyan) and S 5 (blue)

Fig. 7 .

 7 Fig. 7. Fitnesses during AIBO training with start point derived from USARSim training: S 2 in red, S 4 in blue.

http://usarsim.sourceforge.net

ACKNOWLEDGMENT

The authors thank Maria Sciannelli for her support in the USARSim experiments.


A Cherubini
email: cherubini@dis.uniroma1.it

G Oriolo
email: oriolo@dis.uniroma1.it

F Macrì

F Aloise
email: f.aloise@hsantalucia.it

F Babiloni
email: fabio.babiloni@uniroma1.it

F Cincotti
email: f.cincotti@hsantalucia.it

D Mattia
email: d.mattia@hsantalucia.it

Development of a multimode navigation system for an assistive robotics project

Assistive technology is an emerging area where robotic devices can be used to strengthen the residual abilities of individuals with motor disabilities or to help them achieve independence in the activities of daily living. This paper deals with a project aimed at designing a system that provides remote control of home-installed appliances, including the Sony AIBO, a commercial mobile robot. The development of the project is described by focusing on the design of the robot navigation system. Single step, semi-autonomous and autonomous operating modes have been realized to provide different levels of interaction with AIBO. Automatic collision avoidance is integrated in all cases. The performance of the navigation system is shown by experiments. Moreover, the system underwent clinical validation, in order to obtain a definitive assessment through patient feedback.

I. INTRODUCTION

The development of service robots for healthcare and assistance to elderly or disabled persons is an active area of research and development. Several projects have been undertaken in this field, ranging from navigation aids for the visually impaired [START_REF] Bousbia-Salah | A navigation system for blind pedestrians[END_REF] to robots for assisting individuals with motor disabilities [START_REF] Caselli | Toward a mobile manipulator service robot for human assistance[END_REF]. Many assistive robotics projects aim at increasing the quality of the user life in his/her house.

In this field, it is important to design versatile systems, which can assist the patient in certain tasks, e.g., managing home appliances, carrying objects, or monitoring the environment [START_REF] Harmo | Needs and solutions: home automation and service robots for the elderly and disabled[END_REF]. These systems should fulfill basic requirements with respect to safety, cost and user friendliness. In particular, it should be possible to collect signals for controlling devices or robots in an 'intelligent home' from different sources depending on the patient residual abilities. Recently, electroencephalographic brain signals [START_REF] Belic | Identification of human gripping-force control from electro-encephalographic signals by artificial neural networks[END_REF], and implanted Brain Computer Interfaces [START_REF] Hochberg | Neuronal ensemble control of prosthetic devices by a human with tetraplegia[END_REF] have been used. The systems should be validated by experiments on potential users [START_REF] Wada | Psychological and social effects of one year robot assisted activity on elderly people at a health service facility for the aged[END_REF]. Another typical use of robotic technologies in this context is directed to partial recovery of the patient mobility. Semi-autonomous navigation systems for wheelchairs [START_REF] Gomi | Developing intelligent wheelchairs for the handicapped[END_REF] are an example. These systems adapt to various levels of disability by offering different autonomy levels [START_REF] Fioretti | A navigation system for increasing the authonomy and the security of powered wheelchairs[END_REF], [START_REF] Kitagawa | Semiautonomous obstacle avoidance of omnidirectional wheelchair by joystick impedance control[END_REF].

In this paper, we present the basic algorithms developed for a robot navigation system and their application in the ASPICE (Assistive System for Patient's Increase of Communication, ambient control and mobility in absence of muscular Effort) project [START_REF] Cincotti | Brain-operated assistive devices: the ASPICE project[END_REF]. One central feature of the ASPICE system is the possibility for the user to remotely control the motion of a mobile robot (a Sony AIBO) with a reduced set of commands. Depending on the residual abilities of the user, as well as on the desired task, it is possible to choose between different operating modes. Automatic obstacle avoidance is integrated in the system to guarantee safe, collision-free motion in cluttered environments.

The paper is organized as follows. In Sect. II the architecture of the ASPICE system is briefly illustrated. In Sect. III, the main features of the AIBO robot are described. Section IV presents the primitives developed for the robot framework, at perception and motion levels. The robot navigation modes that we implemented, on the basis of the ASPICE requirements, are outlined in Sect. V. Experiments are reported in Sect. VI. Other issues not covered in the previous sections are mentioned in the conclusion.

II. THE ASPICE PROJECT

The ASPICE project received in 2004 a renewable twoyear funding grant from TELETHON, an italian medical research charity foundation. The project involves three partners, among which the Clinical Neurophysiopathology Laboratory of the Fondazione Santa Lucia IRCCS and the Robotics Lab of the University of Rome "La Sapienza".

ASPICE is aimed at developing a technological aid allowing neuromotor-disabled users to improve or recover their mobility and communication in the surrounding environment. The project is addressed towards those patients in which the residual muscular strength is low and practical obstacles or security concerns do not allow a displacement from bed [START_REF] Cincotti | Brain-operated assistive devices: the ASPICE project[END_REF]. Hence, the major requirements are: adaptability to different levels of disability, low cost, and robustness to the setting. Depending on the user requirements, the assistive device will be a program running on a common low-power PC, on a palmtop, or on a powerful workstation.

The ASPICE architecture, with input and output devices, is shown in Fig. 1. Some key elements of the system are:

• various input devices for easy access to the Control Unit: standard input devices (mouse, eye tracker, voice recognition) and a Brain-Computer Interface (BCI); • the Control Unit, which receives signals from the input devices via a Graphic User Interface (GUI) and converts them in commands that drive the output devices (the domotic appliances or a mobile robot); • the mobile robot;

• a number of domotic appliances, which must comply with the patient's need for ambient control: TV, fan, lights, video camera, telephone, personal computer; • visual feedback (either through the fixed video camera or through the robot vision system) to provide the user with an increased sense of presence in the environment.

The Control Unit contains drivers for all output devices; in some cases, existing drivers are utilized, whereas in other cases (e.g., the mobile robot) the driver has been designed "ad hoc" for the system. The BCI detects the activation patterns of the brain, and whenever the user induces a voluntary modification of these patterns, it is able to translate it into an action associated to the user will. The BCI used in ASPICE is based on variations of the EEG rhythmic activity; the signals are captured by means of an electrode cap, and processed by a dedicated software package. All signals between the input devices and the Control Unit, and between the latter and the output devices (including visual feedback) are transmitted over a wireless connection.

In assistive robotics projects, a major requirement is the user friendliness of the robotic platform. Although in recent years users are becoming more acquainted with technology, characteristics such as low cost, safety, and low request for maintenance are still fundamental needs of any biomedical robotic application. In particular, clinicians have often emphasized the importance of working with a friendly-looking robot, in order to limit the psychological impact on patients. In our case, these considerations led to the choice of the doglike robot Sony AIBO ERS-7 for inclusion in the system. Besides, studies on improvement of quality of life, among elderly, using AIBO, have given good results [START_REF] Kanamori | Pilot study on improvement of quality of life among elderly using a pet-type robot[END_REF].

AIBO should be driven around the user home with a small set of commands. It should also assist the patient in visually monitoring the environment and communicating with the caregiver. Partial autonomy should be implemented in order to avoid collisions with obstacles and AIBO should be able to charge its battery when needed without user intervention.

As aforementioned, an objective of the ASPICE project is compatibility with a variety of users and their level of disability. In this spirit, three navigation modes have been developed: Single step, Semi-autonomous and Autonomous mode. The user is expected to choose single step navigation to retain complete control of the robot; e.g., for fine motion in cluttered areas. In semi-autonomous navigation, the user specifies the main direction of motion, leaving to the robot the task of avoiding obstacles. Finally, in the autonomous mode, a target point in the environment is assigned by the user, and the robot travels to the target; this is useful for quickly reaching important locations. This mode is expected to be particularly useful for severely impaired patients, which are unable to send frequent commands. All three navigation modes must contain some level of obstacle avoidance. Each navigation mode is associated to a GUI in the ASPICE Control Unit. The GUIs are shown in Fig. 2. By selecting the corresponding button from the single step GUI, the user can control the step direction. From the semiautonomous mode GUI, the user can select one of six directions -the same of single step mode -or stop the robot. Instead, in the autonomous navigation GUI, each button corresponds to a destination in the user apartment (here, the living room, the bedroom, the bathroom, and the kitchen).

III. THE ROBOT PLATFORM: AIBO

The platform used in this work is a quadruped robot, Sony AIBO ERS-7 (see Fig. 3). AIBO is a low-cost robot, widely used for research purposes. The robot is equipped with 20 actuated joints, a CMOS camera, two distance sensors (on the head and on the chest), an accelerometer, a stereo microphone, a MIDI speaker, a set of leds and pression sensors. A wireless card enables remote control. AIBO's real-time operating system APERIOS runs a specialized layer called OPEN-R, a cross-development environment based on C++. The robot behavior is programmed by loading all executable and configuration files on a memory stick which is read by the on-board processor. In spite of the above features, the AIBO robot presents many limitations. The most severe are the following:

• the closed hardware prevents the addition of sensors and/or actuators; • since Sony does not release the driver code, we had to realize from scratch an ad hoc driver for this work; • the head distance sensor and the CMOS camera move in accordance, making it impossible for the distance sensor to detect obstacles in directions other than the one pointed by the camera; a tradeoff between moving the head for video feedback and moving it for obstacle detection/avoidance had to be reached; • the chest sensor is constrained to the robot body and peculiarly oriented, thus limiting its effective utility; • vibrational and slipping effects during the quadruped gait cycle make odometric reconstruction very inaccurate in the long run; • the variable attitude of AIBO during its gait precludes the use of an external sensory system (e.g., based on infrared triangulation with a detector placed on the robot) for solving the localization problem.

IV. PRIMITIVES

In order to utilize AIBO, specific primitives have been developed and integrated in the driver framework. These have been designed to fulfill the robot driver requirements: obstacle detection/avoidance, motion control, and path planning.

Let us define the reference frames which will be used:

• the robot frame (Fig. 4) with origin fixed at the robot center projection on the ground, x axis in the forward direction, y axis pointing the left side of the robot, and z axis in the vertical direction; • the image frame (Fig. 5) with origin fixed at the top left corner of the image, horizontal i x axis pointing right, and i y axis pointing downward;

A. Perception primitives

The main features that the robot should perceive are the obstacles that it should avoid and the landmarks that it needs for localization and path planning purposes. We chose to use the robot range sensors to detect obstacles, and the camera to recognize visual landmarks. We use a local two-dimensional occupancy grid (OG) to represent the detected obstacles, built by the occupancy grid generator. The visual landmarks that we use are straight white lines (SWL) and coded squares (CS) placed on the floor. Thus, a straight white line extractor (SWLE) and a coded square extractor (CSE) have been developed. Moreover, the visual landmarks (VL) should be located in sequential scenes. This task is accomplished by a visual landmark tracker (VLT). 1) Occupancy grid generator: The robot should be able to recover robust and useful spatial descriptions of its surrounding obstacles, using sensory information. These descriptions should be used for short-term planning in the environment.

To do this, we used a tesselated two-dimensional representation of spatial information called the occupancy grid, which in the past years proved to be extremely efficient for performing path planning and obstacle avoidance in unknown and unstructured environments [START_REF] Elfes | Using occupancy grids for mobile robot perception and navigation[END_REF].

In our approach, the two range finders (head and chest) are used to detect obstacles, although the chest sensor, due to its limited range and particular orientation (see Fig. 3), can only detect close obstacles and therefore is not used to compute the OG. Thus, only the head sensor is utilized to build the local OG by moving the head pan joint along a sinusoidal profile spanning an angular width of 90 • . While the origin of the occupancy grid is always on the head pan axis, and its longitudinal extent is limited by the range of the head distance sensor (1 m), its orientation (i.e., the direction of its bisectrix) is the same as the direction of motion (v x v y ) (see Fig. 4a). Obviously, due to the joint limit, it is impossible to build occupancy grids for backward motions. The grid may be built with the robot either stationary or in motion. In the second case, the head pan movement is synchronized with the gait cycle, and odometric data (reconstructed through the leg joint encoders) are used to build a consistent map. When the pan cycle is complete, a cell in the grid is considered to be occupied if there is a sensor reading indicating an obstacle inside that cell.

2) Straight white line extractor: A requirement of the robot driver is straight white line extraction. In order to be independent from color classification, the straight white lines are detected by search only on the luminance signal I i x, i y . Line edges are searched among pixels with a strong gradient of luminance ∇I, as explained in [START_REF] Cherubini | A vision-based path planner/follower for an assistive robotics project[END_REF].

The SWLE returns the coordinates of the n j pixels belonging to each straight white line SW L j among the N SW L lines extracted on the image frame (Fig. 5):

[ i x r i y r ] T SW L,j r = 1, . . . , n j j = 1, . . . , N SW L
3) Coded square extractor: Along with the SWL, we have used as visual landmarks a set of white coded squares laid on the ground. The identity and orientation of each square is uniquely identified through a black dots code. We arranged from 1 to 7 black dots on the border of the squares, in order to generate 15 configurations (see Fig. 6) which uniquely define the landmark identity (defined by its label: ID) and orientation. Edges of squares are searched as in the SWLE. More details on the CSE algorithm are given in [START_REF] Cherubini | A vision-based path planner/follower for an assistive robotics project[END_REF]. The CSE returns, for each of the N CS detected coded squares: the image coordinates of the square center o and of the centers of the n dots black dots (Fig. 5):

[ i x o i y o ] T CS,l [ i x m i y m ] T CS,l l = 1, . . . , N CS m = 1, . . . , n dots n dots = 1, . . . , 7
4) Visual landmark tracker: The SWLE and CSE only take into account information from the current image, and give no long-term knowledge. Thus, consistent landmarks must be obtained by comparing the extracted landmarks over consecutive images. This is done by projecting the characteristic points of each extracted VL from the image frame [ i x i y] T V L to the robot frame [x y z] T V L . Such mapping is not one-to-one, and can only determine, given the camera intrinsic parameters, the projecting ray corresponding to each point [ i x i y] T V L [START_REF] Corke | Visual control of robots: high performance visual servoing[END_REF]. However, in our application, since all the VLs are on the ground plane, the problem can be solved in closed form, as in [START_REF] Rofer | Robocup 2005 german team technical report[END_REF]. The VLT algorithm returns the characteristics of the VLs (shown in Fig. 4b and Fig. 4c), validated in a sufficient number of consecutive frames:

[b α] T SW L,j j = 1, . . . , N SW L ID l γ l [x o y o 0] T CS,l l = 1, . . . , N CS

B. Motion primitives

From a kinematic viewpoint, AIBO can be considered an omnidirectional robot: three velocities (forward v x , lateral v y , and angular v θ around the robot center, positive for CCW rotation) can be independently specified (Fig. 4a). Whenever the robot velocities are specified in workspace coordinates as V = [V x V y ] T (e.g., when they are imposed by a user command), they must be mapped to the configuration space. To perform this conversion, we have used two strategies. The first (omnidirectional translational motion), consists of simply setting

[v x v y v θ ] T = [V x V y 0]
T . Instead, the second (nonholonomic-like motion), consists in setting:

v x = V x v y = 0 v θ = ATAN2(V y , V x ) (1)
The advantages of each strategy will be illustrated later. Basic motion primitives for controlling the robot legs in order to obtain the desired motion

[v x v y v θ ]
T are based on the quadruped parameterized walk [START_REF] Hengts | Omnidirectional motion for quadruped robots[END_REF], which is widely used in the four-legged robot community, and which we will not discuss in detail. Velocity commands computed by the motion primitives are scaled if any of them exceeds the physical limits of the actuators. We also developed two vision-based motion primitives: the landmark approacher (LA), and the straight line follower (SLF), which use visual information returned by the perception primitives to guide the robot. In practice, the robot actuators are driven by a visual servoing scheme. Since the VLT returns the position of the visual landmarks relative to the robot, position-based visual servo control turns out to offer a better solution than image-based servoing. The two vision-based motion primitives are explained below.

1) Landmark approacher: When the robot finds a landmark, it should approach it, in order to get a better perception, which can be useful for localization purposes. It is a posture stabilization task with reference configuration defined by the position and orientation of the landmark. Since no smooth time-invariant feedback can solve this problem for a nonholonomic mobile robot [START_REF] Canudas De Wit | Theory of Robot Control[END_REF], and path minimization on the other hand is desired, omnidirectional motion is used. The walk that drives the robot implements a proportional closed-loop control strategy for reducing the robot relative distance and orientation with respect to the landmark. This is done by setting:

v x = κ T x V L v y = κ T y V L v θ = κ R θ V L For SWL approaching, [x y θ] T V L = [b sin α b cos α -α] T . Similarly, for CS approaching, [x y θ] T V L = [x o y o -γ] T .
In both cases, κ T and κ R are positive given gains.

2) Straight line follower:

This primitive should solve the path following problem for the SWLs. We adopted a nonholonomic model for the robot, in order to obtain a more "natural-looking" walk. Both linear and non-linear smooth state-feedback control solutions are possible. AIBO is modeled here as a unicycle robot, with velocities [v x v y =0 v θ ] T , and the task can be achieved by using only one control variable, namely v θ . Linear feedback control can be realized by tangent linearization of ḃ and α, in the neighborhood of (b = 0, α = 0). This gives a second order linear system which is controllable, and thus asymptotically stabilizable by linear feedback on v ϑ , if v x = v f > 0 is fixed. A stabilizing linear feedback is of the form:

v ϑ = (k 2 b -k 3 α) v f
with an appropriate choice of positive gains k 2 and k 3 .

V. ROBOT NAVIGATION MODES

All three navigation modes are based on the algorithms presented in Sect. IV. The Single step mode and the Semiautonomous mode utilize only the occupancy grid generator. The first sequentially uses the OG and implements motion control, whereas, in the latter, OG generation and motion control are executed simultaneously. The Autonomous mode utilizes all the primitives presented in Sect. IV.

A. Single step mode

With single step motion, the robot can be driven, with a fixed step size, in any six directions (forward, backward, lateral left/right, CW and CCW rotations). Before performing the motion command, the robot generates the appropriate OG (oriented along the intention of motion) from its stationary position and verifies whether the step can be performed without colliding with obstacles. Depending on the result of the collision check, the robot decides whether or not to step in the desired direction. Note that, since no OG can be built for backward or rotational motions, the corresponding step commands should be used with care.

B. Semi-autonomous mode

With semi-autonomous motion, the user specifies general directions of motion, which the robot should track as closely as possible. Instead of executing a single step, the robot walks continuously in the specified direction until it receives a new command (either a new direction or a stop). If the specified direction is forward or lateral1 (i.e., the user desired direction of motion in the workspace is V des = [V des,x 0] T or V des = [0 V des,y ] T ), autonomous obstacle avoidance is obtained by the use of potential fields. The algorithm used in this case is explained below.

The OG is generated as the robot moves, and then used to compute the robot velocities. Our algorithm uses vortex and repulsive fields to build the velocity field. For each occupied cell on the OG, c = [x c y c ] T , with x c and y c cell coordinates in the robot frame (see Fig. 4a), define the repulsive potential [START_REF] Khatib | Real-time obstacle avoidance for manipulators and mobile robots[END_REF] as:

U r ( c , η) =    K r 1 c - 1 η 2 if c ≤ η 0 else
where c is the distance of the cell from the robot center, η the radius of influence of U r , and K r a given gain. Repulsive and vortex [START_REF] De Luca | Local incremental planning for nonholonomic mobile robots[END_REF] fields induced by each cell are obtained respectively as gradient and rotor of the potential:

f r c =     ∂U r ( c , η r ) ∂x c ∂U r ( c , η r ) ∂y c     f v c =     ± ∂U r ( c , η v ) ∂y c ∓ ∂U r ( c , η v ) ∂x c    
Note the different radii of influence η r and η v of repulsive and vortex fields. By choosing η v > η r , we obtain velocity fields that are essentially vortices at large distances, and become increasingly repulsive at close range. The signs of f v c,x and f v c,y depend on the position of the occupied cell with respect to the robot sagittal plane: a cell in the right (left) half of the grid will induce a CW (CCW) vortex. The fields generated by all the occupied grid cells are then superimposed with the desired workspace velocity in order to obtain the total velocity field:

V = c f r c + c f v c + V des
This velocity must be mapped to the configuration space velocities either with the omnidirectional translational motion conversion or by enforcing nonholonomic-like motion (1). The first is consistent with the objective of maintaining as much as possible the robot orientation specified by the user. Instead, with the second kind of conversion, the orientation of the robot is always tangent to the path; the grid provides more effective collision avoidance since the direction of its angle bisector coincides with the x axis (because v y is null).

C. Autonomous mode

For the autonomous navigation mode (ANM), we designed a physical roadmap (Fig. 6) to reach and connect all relevant destinations in the experimental arena, and utilized a more sophisticated visual servoing scheme. The roadmap is formed by streets and crossings, all realized in white adesive tape laid on the ground. The perception primitives are used to identify streets (straight white lines) and crossings (coded squares) while the motion primitives are used to drive the robot. When approaching a landmark or following a street, the robot concurrently implements landmark fixation, in order to keep the landmark centered in the image plane. This is done by solving the inverse kinematics problem for the head joints.

The autonomous behavior is represented by a Petri Nets framework. The ANM Plan uses the following actions (note that at all times during the actions, the perception primitives are executed for searching and updating perceived data):

• Seek streets: The robot seeks streets in the environment, while avoiding collisions. Motion directions are predefined: AIBO alternates forward and rotation steps. • Approach the nearest street: When it perceives some streets with the SWLE, and tracks them with the VLT, the robot uses the LA to walk towards the nearest.

• Follow the street: When the robot is sufficiently close to the street, it implements the linear SLF for walking on the street, until at least one crossing is detected. • Plan the path to destination: When a crossing is detected with the CSE, and tracked with the VLT, the robot has univocally identified its ID and orientation. This information, along with the CS positions in the robot frame, and with the map, identifies the robot pose (position and orientation). The robot then uses a Dijkstra-based graph search [START_REF] Dijkstra | A note on two problems in connection with graphs[END_REF] to find the shortest path to the destination. Depending on the result of the graph search, the robot will approach and follow another street (repeat the corresponding actions in the plan), or stop if the crossing corresponds to the desired destination. The ANM Plan repeats the above actions until the destination is reached. Transitions that start or terminate the actions represent events (e.g., Street seen, or Crossing near) which are triggered by conditions on sensed information (e.g., distance from a line). The plan must also deal with action failures. For instance, whenever the robot loses visual contact with a street it was approaching, the system aborts the current action and moves to the state where the street is not seen, and so on, until the robot reaches the street again.

VI. EXPERIMENTS

Here, we show the results of two experiments performed with the robot driver: the first is a comparison between the navigation modes, while the second is autonomous battery charging. We also discuss the ASPICE clinical validation and its results on the quality of life of users.

In the first experiment (Fig. 7), the user is expected to drive the robot from a start to a goal point (noted respectively "S" and "G" on the image). The task is repeated 5 times for each of the three navigation modes (single step, semiautonomous, and autonomous) and results are averaged. The robot is driven by selecting commands on the ASPICE GUIs; a mouse is used as input device. In semi-autonomous navigation, omnidirectional translational motion is used for mapping desired user velocities to the configuration space. Comparison between the modes is based on execution time and user intervention (i.e., number of times the user had to intervene by clicking on the GUI for updating the commands). As expected, results (see Table I) confirm the qualitative properties expected for each mode. Note how the best choice depends not only on user's preference and ability but also on the specific task (e.g., position of the start and goal points in the environment, presence and position of obstacles).

In a second experiment, autonomous battery charging is tested. This behavior is also present in the Sony Driver, but since Sony does not release the code of its driver, we had to realize it ad hoc for this project. This experiment not only fulfills an ASPICE requirement, but also provides an additional testbed for the ANM. In fact, the AIBO Charging Station is placed near a marked crossing on the roadmap, and as soon as the battery level is low, the robot autonomously moves to the station. The experiment is illustrated in Fig. 8. The robot position at consecutive time frames is shown while it approaches the roadmap, follows the street up to the battery charger crossing, detects it, and makes a turn in order to reach the charging station on the basis of the plan.

Other experiments, as well as simulations with Webots (a mobile robot simulation environment developed by Cyberbotics) were performed in the Robotics Lab of the University of Rome to test the navigation system, before starting the clinical validation on actual patients. The system was also tested by using the BCI (Brain Computer Interface) to drive the robot. The two experiments in Fig. 7 and8 as well as a BCI-driven experiment are shown in the video clip attachment to this paper. Other video clips are available at: http://www.dis.uniroma1.it/∼labrob/research/ASPICE.html.

At this stage of the project, the system has been implemented and is available at the Fondazione Santa Lucia in Rome for validation with patients [START_REF] Cincotti | Non invasive braincomputer interface systems: towards their application as assistive technology[END_REF]. All domotic appliances used in ASPICE have been installed in the experimental apartment of the hospital. A portable computer runs the Control Unit program, and several input devices are available to cope with as many categories of users as possible. The subjects have been admitted to a neurorehabilitation program, and the whole procedure underwent the approval of the local ethical committee. Then, for two weekly sessions over 4 weeks, the patient and her/his caregivers have been practising with the ASPICE system. The experiments have been carried out with eight subjects suffering from Spinal Muscular Atrophy type II and six subjects suffering from Duchenne Muscular Dystrophy. Data on user satisfaction, increase of independence, and reduction of caregiver workload, have been collected, structured in questionnaires. All of the patients were able to master the system and control AIBO within 5 sessions. Four of them interacted with the system via BCI. Most patients experienced (as they reported in the questionnaire) 'the possibility to interact with the environment by myself'. The average grade given by the patients to their 'personal satisfaction in utilizing the robot' was 3.04 on a 5-point scale. This is a very promising result, considering that the users were originally more accustomed to using and controlling the 'traditional' ASPICE appliances rather than the mobile robot.

VII. CONCLUSIONS AND FUTURE WORK

The ASPICE project is a work in progress. After 24 months, the objective of developing a multimode navigation system for AIBO based on few simple primitives has been achieved. In particular, three navigation modes have been devised to provide the user with different levels of interaction and control of the mobile robot. These operating modes have been integrated in the ASPICE system, and have been tested by patients in a neurorehabilitation program. We expect that the results of the clinical validation will be fundamental for further advancement and adaptation of the ASPICE system.

Other aspects which were addressed during the development of the system have not been treated here. For example, the video feedback from the robot camera to the Control Unit is necessary for assisting the user in driving the robot, and for increasing his sense of presence within the environment. Each image frame acquired by the robot camera undergoes an on-board JPEG compression before being streamed over a wireless connection to the ASPICE Control Unit. A GUI for head control has also been developed to allow the user to move the robot head and point the camera in any desired direction. Another feature of the system is a GUI for vocal requests, which improves the communication of the patient with the caregiver. When the robot receives a vocal request (e.g., 'I am thirsty' or 'Please come'), it travels to a designated destination (where the caregiver is) and plays the corresponding prerecorded audio file with its speakers. Another issue that deserved attention is AIBO's walking gait, which was designed on the basis of patient feedback; for example, a typical request was to reduce the noise caused by leg contact with the ground.

Fig. 1 .

 1 Fig. 1. The ASPICE architecture.

Fig. 2 .

 2 Fig. 2. ASPICE navigation GUIs: single step (top), semi-autonomous (center) and autonomous (bottom) modes. In each GUI, the home button brings back to the ASPICE main GUI.

Fig. 3 .

 3 Fig. 3. The Sony AIBO ERS-7 used in the ASPICE Project.

Fig. 4 .

 4 Fig. 4. Relevant variables utilized in: (a) occupancy grid generation, (b) straight white line tracking, and (c) coded square tracking.

Fig. 5 .

 5 Fig. 5. Extracting edges (yellow), for SWL (left) and CS (right) detection. The detected CS center is marked in red, and dot centers in cyan.

Fig. 6 .

 6 Fig. 6. The roadmap used in autonomous navigation mode. The ID labels of each CS are indicated. Note that crossings appear larger than they are.

Fig. 7 .

 7 Fig. 7. Experiment with the ASPICE navigation modes: the user drives the robot from point S to point G using the single step (above), semiautonomous (center) and autonomous (below) modes. execution time (sec) user intervention (clicks) single step 107 11 semi-autonomous 83 5 autonomous 90 1

Fig. 8 .

 8 Fig. 8. Two phases of the battery charging experiment.

TABLE I COMPARISON

 I BETWEEN THE THREE ASPICE NAVIGATION MODES.

As for the single step mode, no obstacle avoidance can be performed when executing backward or rotational motions.

This work has been partially supported by the Italian Telethon Foundation Grant GUP03562.