Andrea Cherubini
email: cherubini@dis.uniroma1.it

F Giannone

L Iocchi
email: iocchi@dis.uniroma1.it

M Lombardo

G Oriolo
email: oriolo@dis.uniroma1.it

Policy gradient learning for a humanoid soccer robot

Keywords: humanoid robotics, machine learning, motion control PACS: 87.85.St, 87.19.lr

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In order for robots to be useful for real-world applications, they must adapt to novel and changing environments and situations. However, the ability to deploy a fully autonomous robot in an unstructured, dynamic environment over an extended period of time remains an open challenge in the field of robotics. For this purpose, a popular research activity is the annual RoboCup competition, where different kinds of robots compete on standard reference testbeds in soccer, rescue and @home scenarios. Among the RoboCup disciplines, we focus here on humanoid robot soccer, and among the capabilities that a humanoid robot needs for playing soccer, walking is obviously the most important. Consequently, the speed, stability and precision of the walking gait, are crucial factors that determine the success of a team.

At first, gait improvements for legged robots centered around hand-tuning. However, in case of a change of robot hardware and/or of walking surface (e.g., the carpet, or the floor), the motion parameters need to be re-calibrated, and this is a process that can easily take several hundred trials for an expert. One alternative to hand-tuning a parameterized gait, while enabling the robot to adapt to changes in its surroundings, is to use machine learning to automate the search for good parameters. In the past, various machine learning techniques have proved useful in finding control policies for a wide variety of robots, as reported in Section 2. 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.

Learning in the robotic soccer domain has to overcome several challenges, such as a continuous multi-dimensional state space, noisy sensing and actions, multiple agents (including adversaries), and the need to act in real-time. Nevertheless, this approach has been somewhat fruitful: for example, since the inception of the RoboCup legged league in 1998, the speed of the quadruped robots has increased significantly [START_REF] Chalup | Machine Learning with AIBO Robots in the Four-Legged League of RoboCup[END_REF]. In most cases, the knowledge achieved in the Four-Legged League can be transferred to the Humanoid League [START_REF] Laue | Getting Upright: Migrating Concepts and Software from Four-Legged to Humanoid Soccer Robots[END_REF]. Despite this growing interest, considerable work remains to be done, due to the difficulties associated with applying machine learning in the real world. Compared to other machine learning scenarios, such as classification or action learning in simulation, learning on physical robots must be effective with a small amount of data, and should converge in short time [START_REF] Chalup | Machine Learning with AIBO Robots in the Four-Legged League of RoboCup[END_REF]. 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.

Following up on all these considerations, in this article, we present a learning method for humanoid walking gaits based on Policy Gradient [START_REF] Kohl | Policy Gradient Reinforcement Learning for Fast Quadrupedal Locomotion[END_REF]. We focus on learning a specific humanoid robot task (namely, curvilinear biped walking), that requires, at the same time: a relatively small set of parameters, and high precision from a control viewpoint. To learn this task, we compare Policy Gradient with an extension that takes into account parameter relevance [START_REF] Cherubini | An extended policy gradient algorithm for robot task learning[END_REF], showing, through experiments on a 3D simulator, the higher convergence rate of the extended policy gradient method and, through experiments on real robots, the performance of Policy Gradient learning algorithms and the effective use of the results of learning on the simulator. While Policy Gradient learning methods have been compared on a quadruped robot in [START_REF] Cherubini | An extended policy gradient algorithm for robot task learning[END_REF], the main contribution of the present article is the application of these algorithms to biped walking. We have successfully applied the presented learning method in preparation of RoboCup 2008, within the Standard Platform League (twolegged division) using Aldebaran NAO robots 1 .

The remainder of this article is organized as follows. Section 2 surveys existing approaches for generating and optimizing legged gaits. Section 3 presents the static parameterized biped motion control scheme that we used to generate curvilinear trajectories with a humanoid robot. In Section 4, we describe the policy gradient learning algorithms. Section 5 defines the learning scheme applied to curvilinear walking gait, while experimental results are discussed in Section 6. We close with a discussion and possible avenues for future work in Section 7.

Related Work

In this section, we provide a brief survey in the field of legged robot gait learning. In particular, we focus on two aspects: gait generation (in particular, we focus on biped gaits), and gait learning. For each aspect, we first review the existing literature, and then outline the original contribution of our work.

Gait generation

The design of controllers enabling biped robots to walk autonomously on uneven and variable terrains in a robust way, e.g. in daily life, remains a crucial research topic in robotics. Recent works in the field of legged robot gait modeling and control have been surveyed in [START_REF] Kajita | Legged Robots[END_REF][START_REF] Kuo | Choosing Your Steps Carefully[END_REF]. In summary, two main classes of methods have been used for biped gait control: static and dynamic control approaches.

The most commonly used dynamic approaches are based on the zero moment point (ZMP). ZMP refers to the location within the base of support of the center of pressure of the floor reaction force. By controlling this location, the robot may induce forward motion while maintaining dynamic balance. In the dynamic walking pattern used in [START_REF] Kim | System Design and Dynamic Walking of Humanoid Robot KHR-2[END_REF], for instance, ZMP is used during the double support phase to guarantee stability. In [START_REF] Yamaguchi | Development of a bipedal humanoid robot-control method of wholebody cooperative dynamic biped walking[END_REF], ZMP is integrated in a whole body cooperative dynamic biped walking, that includes trunk motion to compensate for the moment generated by the motion of the whole body (lower, as well as upper limbs). For a survey of the history and characteristics of ZMP, the reader is referred to [START_REF] Vukobratovic | Zero-moment point -thirty five years of its life[END_REF].

In static approaches, instead, some a-priori definition of the desired trajectories to follow is used. Standard and ad-hoc control techniques have been developed to cope with model uncertainties, obstacles and disturbances, in order to prevent the robot from falling. The desired (also called reference) trajectories can be either obtained from the capture of human motions, or purely computergenerated. In the second case, the usual approach includes two steps. First, a set of output variables (generally, the 3D coordinates of a few selected points on the robot) with adequate dimension is chosen. Second, after parametrization (e.g., under the form of splines) the desired trajectories of these variables are computed, for every phase of the gait. Computer-generated trajectories have been used in [START_REF] Yamasaki | Acquisition of Humanoid Walking Motion Using Genetic Algorithm -Considering Characteristics of Servo Modules[END_REF][START_REF] Hebbel | Modeling and learning walking gaits of biped robots[END_REF][START_REF] Hu | Locomotion Planning and implementation of Humanoid Robot Robo-Eectus Senior (RESr-1)[END_REF][START_REF] Niehaus | Gait Optimization on a Humanoid Robot using Particle Swarm Optimization[END_REF]. In [START_REF] Sato | Reinforcement Learning for Biped Locomotion[END_REF], the trajectories are designed using Central Pattern Generators, similar to bio-inspired self-oscillating systems.

In this work, we utilize a static parameterized biped gait model to control the legs and arms in order to make NAO track arbitrary curvilinear trajectories. We have decided to adopt a static gait model, since no accurate dynamic model of NAO is available at this time. The trajectories are defined by the requested velocity command (v, ω) ∈ R 2 , with v the forward linear velocity, and ω the angular velocity, as for non-holonomic (e.g., wheeled) robots. Our gait model is similar to the one presented in [START_REF] Hebbel | Modeling and learning walking gaits of biped robots[END_REF]. The model is based on arbitrary parameterized joint trajectories, and does not explicitly consider stability aspects; hence, the gait model performance can be assessed through its practical application. However, in contrast with most of the aforementioned works, which focus uniquely on pure rectilinear walks (with the exceptions of [START_REF] Hebbel | Modeling and learning walking gaits of biped robots[END_REF] and [START_REF] Hu | Locomotion Planning and implementation of Humanoid Robot Robo-Eectus Senior (RESr-1)[END_REF]), the motion control scheme that we propose is valid for generic curves of radius R = v/ω. This includes the particular cases of pure rectilinear (ω null, thus R = ∞) and pure rotational (v null, thus R = 0) walks. With this approach, our walk reproduces a natural-looking human walk. Indeed, the close relationship between the shape of human walking paths in goal-directed movements and the kinematics model of a non-holonomic mobile robot has been shown in [START_REF] Arechavaleta | The nonholonomic nature of human locomotion: a modeling study[END_REF] (humans 'do not walk sideways'). From a comparative analysis, the authors of [START_REF] Arechavaleta | The nonholonomic nature of human locomotion: a modeling study[END_REF] infer that some constraints (mechanical, anatomical...) act on human bodies restricting the way humans track trajectories, and that the trunk can be considered as a kind of steering wheel for the human body. Following up on these considerations, and on the fact that the NAO trunk is not actuated, we utilize the arms to add momentum for rotation, in contrast with the other (rare) curvilinear motion control schemes presented in the literature ( [START_REF] Hebbel | Modeling and learning walking gaits of biped robots[END_REF] and [START_REF] Hu | Locomotion Planning and implementation of Humanoid Robot Robo-Eectus Senior (RESr-1)[END_REF]), which exploit only the lower limbs for rotations.

Gait learning

Robots should be able to respond to changes in the surroundings by adapting both their low-level skills (e.g., vision or motion control parameters) and the higher-level skills (e.g., the behaviors) which depend on them. Such adaptation should occur as autonomously as possible. However, in all cases where the complete analytical model is unknown, this is not trivial. Thus, machine learning techniques have been used in many robotic applications, both for finding optimal parameter sets of specific behaviors (parameter learning), and for de-termining the best choice of behaviors required to accomplish a task (behavior learning), whenever the model cannot provide an optimal solution to such problems. Clearly, one of the primary application areas of parameter learning is robot motion control, since the mathematical model is approximated, and traditional optimization methods cannot be used. In particular, gait optimization for legged soccer robots is not straightforward: creating effective motions is a challenging task, since there are many parameters to be set, and since successful motions strongly depend on many factors, which cannot be modeled with precision: playing surface, robot hardware, and game situation. For these reasons, in recent years, machine learning techniques have been used to find optimal parameter sets for legged gait optimization.

Hexapod robot walk generation has been solved in [START_REF] Parker | Learning gaits for the Stiquito[END_REF], with a Genetic Algorithm. Similar methods have been used for optimization of the vector of quadruped walk parameters, while avoiding the need for gradient approximation in [START_REF] Kim | Automatic gait optimisation for quadruped robots[END_REF][START_REF] Chernova | An evolutionary approach to gait learning for four-legged 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 learning algorithms for quadruped walk optimization, and in [START_REF] Duffert | Reliable and precise gait modeling for a quadruped robot[END_REF], genetic algorithms were extended in order to improve omnidirectional gaits by switching and interpolating between vectors of parameters. A common feature of these approaches is that the robots time themselves walking across a known, fixed distance, thus eliminating the need for human supervision, other than battery changes. 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. Similar approaches have been used for learning on humanoid platforms. Humanoid walk parameters are automatically learned using: various evolutionary strategies in [START_REF] Hebbel | Modeling and learning walking gaits of biped robots[END_REF], a particle swarm approach in [START_REF] Niehaus | Gait Optimization on a Humanoid Robot using Particle Swarm Optimization[END_REF], and Reinforcement Learning (RL) in [START_REF] Peters | Reinforcement Learning for Humanoid Robotics[END_REF]. Sato and others [START_REF] Sato | Reinforcement Learning for Biped Locomotion[END_REF] design a new RL algorithm for central pattern generators, in order to improve biped gait stability. A method for optimally generating stable bipedal walking gaits, based on a Truncated Fourier Series Formulation, with coefficients tuned by a Genetic Algorithm, is presented in [START_REF] Yang | Adjustable Bipedal Gait Generation using Genetic Algorithm Optimized Fourier Series Formulation[END_REF]. Policy gradient RL, and particle swarm optimization are compared in [START_REF] Faber | Stochastic Optimization of Bipedal Walking using Gyro Feedback and Phase Resetting[END_REF] for improving a biped gait. Morimoto and Atkeson [START_REF] Morimoto | Learning Biped Locomotion[END_REF] present a model-based RL algorithm for biped walking, in which the robot learns to appropriately modulate an observed walking pattern. In [START_REF] Yamasaki | Acquisition of Humanoid Walking Motion Using Genetic Algorithm -Considering Characteristics of Servo Modules[END_REF], a method for acquisition of highly energy-efficient walking, based on a two-stage genetic algorithm, is presented: in the first phase, the fitness function consists of a walking distance (longer is better), whereas in the second phase, the fitness function consists of a walking distance (longer) and energy consumption (less). Fundamental soccer skills for a real humanoid robot are improved, by extending standard RL with imitation of a teacher, and reevaluation of past experiences, in [START_REF] Latzke | Imitative reinforcement learning for soccer playing robots[END_REF]. A humanoid robot, able to learn how to interact with the environment, and how to develop its perceptual, motor and communication capabilities, has been designed in the research project RobotCub [START_REF] Sandini | RobotCub: an open framework for research in embodied cognition[END_REF]. Researchers at the University of Padova have developed an interface for teaching new motions to humanoid robots through touching, by directly manipulating the limbs of the robot [START_REF] Dalla Libera | Teaching by touching: an intuitive method for development of humanoid robot motions[END_REF].

Following up on these works and on our previous work on the Sony AIBO [START_REF] Cherubini | An extended policy gradient algorithm for robot task learning[END_REF][START_REF] Cherubini | Layered learning for a soccer legged robot helped with a 3D simulator[END_REF], in this article we propose an original parameter learning approach for improving curvilinear biped walks. 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 layered learning approach [START_REF] Stone | Layered Learning[END_REF], that is suitable with the large dimensions of the search space in complex robot learning scenarios. We have also studied how to use a 3D simulator for speeding up robot learning, and we have shown that the learned low-level parameters are strongly related to the desired behavior. In [START_REF] Cherubini | An extended policy gradient algorithm for robot task learning[END_REF], we have proposed an extension of the policy gradient algorithm introduced in [START_REF] Kohl | Policy Gradient Reinforcement Learning for Fast Quadrupedal Locomotion[END_REF], that has been successfully used to optimize quadruped gait of AIBO robots. Our approach guarantees a higher convergence rate than the standard policy gradient, by exploiting additional information on the system properties, such as the contiguities between strategies, and the relevance of the behavior parameters. As reported in [START_REF] Cherubini | An extended policy gradient algorithm for robot task learning[END_REF], the extended policy gradient has been tested in the application example of an attacker robot in the RoboCup Four-Legged League. Referring to the cited works, the original contribution of this article, from the learning point of view, is the experimental comparison between the policy gradient from [START_REF] Kohl | Policy Gradient Reinforcement Learning for Fast Quadrupedal Locomotion[END_REF], and the extended version introduced in [START_REF] Cherubini | An extended policy gradient algorithm for robot task learning[END_REF], carried out for the first time on a biped platform. Moreover, in contrast with the algorithm presented in [START_REF] Cherubini | An extended policy gradient algorithm for robot task learning[END_REF], in this article we only exploit parameter relevance, and not strategy contiguity, since the article focuses on parameter learning rather than behavior learning.

Motion control

Outline

The robot used in this work is NAO from French manufacturer Aldebaran. It has been selected for the soccer competitions of the RoboCup Standard Platform League. NAO has a total of 21 degrees of freedom, shown in Fig. 1: 2 in the head, 4 in each arm, 1 in the pelvis (H Y P ) and 5 in each leg. We define the reference frame F R (also shown in the figure) with origin in the robot center of mass, X axis in the sagittal plane and pointing forward, Y axis orthogonal to the sagittal plane and pointing to the left side of the robot, and Z axis orthogonal to the ground and pointing upwards. In this work, we assume for simplicity that, throughout the gait, the robot center of mass stays in a fixed position with respect to the robot trunk.

The control software of the robot is based on the OpenRDK software framework2 [START_REF] Farinelli | Design and implementation of modular software for programming mobile robots[END_REF]. In the OpenRDK architecture, the MotionControl module is responsible for implementing all requested velocity commands, which are defined as (v, ω) ∈ R 2 , with v the forward linear velocity along the X axis, and ω the angular velocity around the Z axis (positive counterclockwise). In the rest of this section, we describe the parameterized biped curvilinear gait model used in the MotionControl module. Our gait model (which is inspired by the work presented in [START_REF] Hebbel | Modeling and learning walking gaits of biped robots[END_REF]) has been designed in order to keep the number of parameters (and consequently the search space dimension for parameter optimization) as small as possible. It is based on arbitrary parameterized joint trajectories, and does not explicitly consider stability issues; its soundness has thus been proved in practical applications.

The act of biped walking involves, for each gait cycle (i.e., for each step), both a single support (or swing) phase, and a double support phase. Therefore, two fundamental parameters of the step, are:

• T tot : the total duration of a step, • ss % ∈ ]0, 1[: the ratio between single support duration and total step duration.

In the following, we describe the motion control task by dividing it in four subtasks: the design of the foot trajectories in the X -Z plane, the design of the center of mass trajectory in the lateral direction, the Hip Yaw/Pitch joint control used for making the robot turn, and the arm control.

Foot trajectories in the X -Z plane

Here, we present the foot trajectory design for rectilinear walks (v, 0). We show in the following that generic curvatures can be obtained by combining such trajectories with the appropriate Hip Yaw/Pitch control law necessary for pure rotations (0, ω). Since we focus on rectilinear walks, the foot trajectories belong to the X -Z plane. The legs move in two phases: the phase when the foot (stance foot) is on the ground to push the body forward, and the phase when the foot (swing foot) is in the air to prepare the next step. We design the trajectory of the stance foot in F R as a straight line, and the F R swing trajectory as a semi-elliptical trajectory (see Figure 2). The joint angles required to enable the feet to track the rectilinear and semi-elliptical trajectories shown in Figure 2 are calculated by means of inverse kinematics. Since the trajectories belong to the X -Z plane, the three leg pitch joints (hip, knee and ankle) are sufficient to control each foot during each phase. As illustrated in Figure 2, the foot trajectories depend on the following 5 parameters:

• X tot : the total length of a step, which is related to the requested linear velocity v and to the step duration T tot by equation:

X tot = v T tot (1)
• X sw0 : the F R abscissa of the swinging foot at the beginning of the single support phase, • X ds : the portion of X tot covered during one double stance phase, • Z st : the stance foot altitude in F R , • Z sw : the maximum height from the ground reached by the swinging foot.

Using the leg roll joints to control the center of mass and the robot trunk

In order to guarantee stability during the single support phase, the robot must 'swing' sideways during motion, as is commonly done in static biped gaits [START_REF] Hebbel | Modeling and learning walking gaits of biped robots[END_REF][START_REF] Niehaus | Gait Optimization on a Humanoid Robot using Particle Swarm Optimization[END_REF]. This is done by shifting the center of mass of the robot in the direction of the stance foot, which is still on the ground. A qualitative representation of the desired trajectory for the projection of the center of mass in the X -Y plane during rectilinear walks is shown in Figure 3(a). This trajectory comprises a sinusoid above the stance foot area during single support, and a linear trajectory during double support, which moves the center of mass to the next swinging foot, in order to prepare the next step3 . This trajectory is obtained by moving the stance feet in F R . We have seen that gait stability is also increased by letting the robot trunk roll around the X axis during the gait; this is done using a sinusoidal time law of amplitude K R , which is driven by the stance hip roll joints. We have designed the foot and trunk movements by using the 6 parameters: X tot , X ds , Y ft , Y ss , Y ds , and K R . The first two parameters have been defined in Section 3.2. The four other parameters are:

• Y ft : the distance between the feet during the gait, • Y ss : the maximum F R ordinate of the feet during the single support phase, • Y ds : the maximum F R ordinate of the feet during the double support phase, • K R : the amplitude of the trunk roll sinusoidal law.

Exploiting the NAO Hip Yaw/Pitch joint for turning

In order to implement rotational motions around Z (i.e., in order to realize velocity requests with ω = 0), we utilize the single NAO Hip Yaw/Pitch joint H Y P (see Figure 1). The movement is done by alternatively increasing and decreasing the joint value during consecutive single support phases (see Figure 4), and locking it during the double support phases. The rotational movement is designed directly in the joint space, as opposed to the movements described previously, which were designed in the cartesian space, and then mapped to the joint space via inverse kinematics.

Consider two consecutive steps. During the first swing phase, the Hip Yaw/Pitch joint value is increased smoothly (using a cosinusoidal law) from 0 to a fixed value H Y P M , whereas, during the following step, the yaw pitch joint value is decreased (again, using a cosinusoidal law) to restore parallelism (i.e., H Y P = 0) between the feet. Since the rotation axis of the NAO Hip Yaw-Pitch joint is the bisectrix of the Y and Z axis, the total angular width of a double rotation step driven by the above time laws is H Y P M √ 2 . Thus, H Y P M is related to the requested angular velocity ω and to the step duration T tot by:

H Y P M = -2 √ 2 |ω| T tot (2)
Note that the sign of H Y P M is always negative. The sign of ω is determined by the initial foot swing (e.g., in Figure 4, negative ω is obtained by swinging the right foot first). To countervail the effect of the NAO Hip Yaw-Pitch joint value H Y P (t) on the foot trajectories in the X -Z plane, we subtract, throughout the gait cycle,

H Y P (t) √ 2
from the hip pitch joints calculated with the method described in Sect. 3.2.

Arm control

As the human walk shows, arm movement synchronized with leg movement can improve gait performance. Similarly to leg yaw-pitch control, we have decided to design the arm movement directly in the joint space. We only consider the pitch shoulder joints, and lock the 4 elbow and the 2 shoulder roll joints (see Figure 1). Since conservation of angular momentum implies that for rotating bodies, a decrease in the radius is accompanied by an increase in the angular velocity (e.g., the ice skater spins faster when the arms are drawn in, and slower when the arms are extended), we lock the shoulder and elbow roll joints to the zero positions, and fix the elbow yaw joint to 90 • . We design shoulder pitch movements coupled with the leg movement and symmetric with respect to the vertical downward arm position. Two different arm control laws are designed for pure rectilinear walks and pure rotations, and the linear combination of such laws is used for curvilinear walks. For rectilinear walks, the angular momentum induced by the arms must cancel the undesired momentum around the Y axis generated by leg swinging. We use a sinusoidal time law during the swing phases, and lock the shoulder pitch joint, during the double support phases. The arm corresponding to the swinging leg moves backward and viceversa , as shown in Figure 2. Instead, for pure rotations, the angular momentum induced by the arms should enhance the momentum around Z that is used to rotate. We use sinusoidal time laws during both phases. During the swing phase, the arm movement generates a momentum with the same verse of ω, while during the double support phase, the arms are moved back to prepare the next swing phase (see Figure 4). For all walks, i.e., for all velocity commands (v, ω), the arm is controlled by one parameter: the amplitude K S of the shoulder pitch joint sinusoids.

Policy Gradient Learning

In this article, we experiment learning techniques for improving the generation of walking behaviors, using the motion control scheme described in the previous section. In particular, we focus on Policy Gradient methods, that are recalled in this section. As in any robot learning problem, the applied method should minimize time consumption, which is often related to 'hardware consumption' in real robot applications. Hence, the algorithm must converge to the best solution (or to a good solution) after as few experiments as possible. When experimenting learning techniques for humanoid robots, this issue is even more demanding, since bad walking behaviors can cause the robot to fall to the ground and possibly damage itself.

To overcome this problem, we start from this observation: during the learning process, the relevance of the parameters (i.e., their impact on finding an optimal solution) is not constant. In particular, in many cases, some of the parameters reach good or optimal values after few experiments, while other parameters need many experiments. If we are able to appropriately reduce the search space by removing the directions for which we have already found an optimal value (i.e., the directions that are not relevant anymore for determining the optimal solution), the number of experiments needed could be reduced, without losing the quality of the solution. and it is proved to converge to a local optimum X * if a sufficient number of iterations are performed. In practice, at each iteration of the algorithm, p experiments must be executed to evaluate the fitnesses of the p policies necessary for estimating the gradient X. Hence, the total number of experiments necessary to complete N iter iterations is:

N P G = pN iter = ΛkN iter (3)

Extended policy gradient with parameter relevance

Although effective, the method described above does not consider the variable relevance of parameters during the learning process. Here, we present an extension of the method, which takes into account relevance of parameters to fasten the learning process. The algorithm presented in this section is derived from the one described in [START_REF] Cherubini | An extended policy gradient algorithm for robot task learning[END_REF], by considering only the relevance of the parameters, and not the contiguities among strategies, since strategies are not taken into account in this article.

Let us define the following metric for measuring the relevance of the parameters.

Definition. Relevance of parameter j at iteration ī = 0 is the norm of the weighted average of the j th gradient component of vector X:

R ī(j) = ī i=1 λ ī-i X i j ī i=1 λ ī-i
where 0 < λ < 1 is a forgetting factor, that operates as a weight diminishing for the more remote data.

The above definition of relevance is used to estimate how much the parameter can contribute to find an optimal solution. 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, and that it is not necessary to search in this direction anymore.

The Policy Gradient with Parameter Relevance (PGPR) algorithm is shown in Figure 5. The algorithm is similar to Policy Gradient, with the main difference that policies are computed only on the relevant parameters. More specifically, we denote with J i ⊆ {1, . . . , k} the subset of relevant parameters at iteration i (i.e., parameters j with 'high' R i (j)). After P R start iterations, J i is updated at each step during the learning process, depending on the values of R i (j)

POLICY GRADIENT with PARAMETER RELEVANCE INPUT: X 0 , η, N iter , T r , P R start OUTPUT: X * 1 begin 2 initialize X ← X 0 , J 0 ≡ {1, . . . , k} 3 for each iteration i = 1 to N iter 4 generate p i-1 random policies m X i-1 near X i-1 on J i-1 5 evaluate F (X) at all p i-1 policies m X i-1 6 J i ← ∅ 7 for each parameter j ∈J i-1 8 evaluate F-,j , F0,j , and F+ ,j 9 if F0,j > F-,j and F0,j > F+ ,j 10 (lines 14-16). At each iteration, policies are computed only in the directions given by the relevant parameters, i.e. only by the parameters in J i (line 7). Correspondingly, at each iteration, the number of policies generated is also updated according to the number of relevant parameters: p i = Λ|J i |. An example of application of the algorithm is outlined in Figure 6. The figure presents two cases of parameter search for the drawn 2D fitness functions. In each figure, the light (green) colored dots show the values of X i computed at each step (starting from the leftmost one), while the dark (red) colored dot indicates the solution X * found after a few iterations (N iter = 6 in the figure). The horizontal dotted blue line shows the search direction after one of the parameters (the one corresponding to the vertical axis) is fixed. In the left picture, the advantage of the algorithm is clear: after a few iterations the parameter corresponding to the vertical axis is fixed and the search continues only on the horizontal axis (dotted line), rather than on the entire 2D space. This obviously speeds up convergence and improves the quality of the solution when considering a small number of trials. The right picture shows a case where the algorithm does not behave in an optimal way. Here, after some iterations, the parameter associated to the vertical axis is fixed to a value such that the consequent 1-D search does not guarantee to find the optimal solution. However, even in this case, if we consider only a limited number of experiments, the extended algorithm provides a better solution than the classic algorithm. In fact, during the PGPR learning process, since the number of relevant parameters (i.e., |J i |) is reduced progressively, the number of policies p i = Λ|J i | also diminishes. Hence, the total number of experiments necessary to complete N iter iterations, is:

X i j ← 0 11 else 12 X i j ← F+ ,j -F-,j 13 endif 14 evaluate R i (j) 15 if (R i (j) > T r or i < P R start ) 16 J i ← J i ∪ j 17 endif 18 endfor %parameters 19 X i ← η × X i | X i | 20 X i ← X i-1 + X i
N P GP R = N iter i=0 p i = N iter i=0 Λ |J i | (4)
Thus, if we assume that at least one parameter is considered irrelevant and therefore discarded during the learning process (otherwise, the two algorithms will behave identically) and if we fix the number of iterations N iter of the algorithm (i.e., the number of times the gradient is estimated), it is obvious from equations ( 3) and ( 4) that N P GP R < N P G .

This shows the main characteristic of the proposed PGPR algorithm: although it does not guarantee to reach a local optimum (as in the example on the right in Figure 6), in many cases it requires less experiments to compute the same solution (in other words, it tends to find good solutions as early as possible).

As shown in the next sections, the application of this algorithm is very suitable for robot learning tasks, where experiments are expensive and a non-optimal solution obtained with few experiments is often preferred to an optimal solution that requires a larger number of experiments.

Learning configuration

Parameters

The objective of the learning process is to learn the optimal parameter vector X * that ensures the best performance (i.e., the maximum value of fitness function F (X * )) for any curvilinear walking gait (i.e., for arbitrary veloc-ity requests (v, ω) ∈ R 2 ). The vector X is composed of the following eleven parameters (detailed in Section 3):

• ss % : the ratio between single support duration and total step duration,

• X tot : the total length of a step, • X sw0 : the F R abscissa of the swinging foot at the beginning of the single support phase, • X ds : the portion of X tot covered during a double stance phase, • Z st : the stance foot altitude in F R , • Z sw : the maximum height from the ground reached by the swinging foot, • Y ft : the distance between the feet during the gait.

• Y ss : the maximum F R ordinate of the feet during the single support phase, • Y ds : the maximum F R ordinate of the feet during the double support phase, • K R : the amplitude of the trunk roll sinusoidal law, • K S : the amplitude of the swinging shoulder movement.

Note that in the above list of parameters to be learned, we have not considered T tot and H Y P M since equations ( 1) and [START_REF] Laue | Getting Upright: Migrating Concepts and Software from Four-Legged to Humanoid Soccer Robots[END_REF] show that these parameters are constrained respectively to v and X tot , and to ω and T tot . Moreover, we decided to fix T tot allowing for different velocities, obtained by varying X tot .

Although these parameters allow for a curvilinear walking gait, assigning:

X tot = X ds = 0 X sw0 = Xsw0
where Xsw0 is the X sw0 value that guarantees zero moment around the Y axis (i.e., that the ZMP is the projection of the robot center of mass on the ground), turns the gait into a pure rotational walk.

Moreover, all the parameters are box-constrained by the gait designer, due to the physical characteristics of the system, and we call ∆ j the range size for parameter j. Hence, a candidate solution of the optimization problem for curvilinear walk is:

X = [ss % X tot X sw0 X ds Z st Z sw Y ft Y ss Y ds K R K S ] T ∈ Θ ⊂ R 11 (5)
Subsets of these parameters can then be used for pure rotational walks.

Fitness function

The appropriate choice of the fitness function for optimization is fundamental.

Here, we evaluate the quality of a walking gait by taking into account the speed and the precision of the robot motion with respect to the desired trajectory. Hence, we adopt the following function: where L (X) and P (X) are metrics indicating respectively the length of the path covered in a fixed amount of time, and the precision with respect to the desired trajectory at the end of the experiment, measured for parameter set X. The positive weights λ L and λ P indicate the importance of these two measures. Here, we simply report the derivation of L and P in the case of circular trajectories (i.e., case of finite, non-null R), without considering the cases of pure rotation and pure rectilinear walks. To test parameter set X, we make NAO walk, for a fixed period of time, along a circular trajectory of radius |R| (i.e., we apply a motion request (v, ω) such that v = ωR). Refering to Figure 7, we note e (X) the euclidean distance between NAO's final position and the circumference, and d re (X) the signed distance covered by the robot during the experiment. The sign of d re is positive if NAO walked in the correct verse (i.e., if the average radius during the real walk had the sign of R). Then, the variables introduced in (6), can be computed as:

F (X) = λ L L (X) + λ P P (X) (6)
L (X) = dre(X) v P (X) = 1 -e(X)

|R|

Note that F (X) can become negative for bad parameter sets. Note also that, although this formulation of the fitness function does not take directly into account robot falls, it does reward 'late' falls, with respect to 'early' ones.

Experimental results

The objectives of the experiments reported in this section are: 1) demonstrating that the Policy Gradient algorithm is adequate for learning optimal parameters of the curvilinear walk described in this article; 2) evaluating the approach based on parameter relevance and assessing its advantage when only a limited number of experiments is available. The experiments have been performed both on the Webots 3D simulator and on real NAO robots.

For the experimental evaluation described in this section, we took advantage of a result 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. In [START_REF] Cherubini | Layered learning for a soccer legged robot helped with a 3D simulator[END_REF], we had shown that simulated learning can be used in a layered approach as a starting point for learning on the real robot. Moreover, simulations are in general less biased by noise, and require less resources (both in terms of human operators and in terms of hardware) than real world experiments. On the other hand, running very long runs on the simulation does not guarantee better parameters for the real robot. In fact, we found out that after a certain number of learning iterations we obtained too specialized solutions for the simulator that do not correspond to good solutions for the real robot. Therefore, the length of the experiments in simulation have been maintained limited to 20-25 iterations.

In the following, we will thus present first a set of learning sessions using Webots simulator and then sessions on the real NAO. Simulations provide information about the convergence of the algorithms for a robot learning application, while real world experiments are used to show that learning is effective also on real robots.

In both simulated and real experiments, we have focused on learning the best parameter set with a fixed T tot , so with a variable velocity (thus depending from the step length X tot ), aiming at maximizing (with a combined fitness function) both velocity and precision in executing a curvilinear walk.

Experiments with Webots Simulator

For performing quantitative measures of the proposed learning approaches, we made use of the Webots 3D simulator 4 , that includes an official model of the NAO humanoid robot. The learning task described in the previous section has been performed several times, and we report here some relevant results that highlight the characteristics of the Policy Gradient (PG) and the Policy Gradient with Parameter Relevance (PGPR) algorithms. Referring to the 11 parameters shown in ( 5), we have decided to fix parameters ss%, K S and Y ft to hand tuned values, and learn the remaining parameters (thus, k = 8). The number of policies used to estimate the gradient is set to 16 (i.e. p = Λk, with Λ = 2.

With this configuration, we performed two series of experiments: 1) running several learning sessions starting from the same initial parameter set to evaluate the learning rate of PG vs. PGPR, attenuating the effects of the randomized choices of the algorithms; 2) running different learning session for different initial values to evaluate the different performance of PG vs. PGPR.

Experiments with the same initial value

In the first set of experiments, we have performed many learning sessions starting from the same initial parameter set, in order to reduce the randomness of the results. The main objective of this simulation is to analyze the relevance of parameters, and to compare PG and PGPR in terms of both the number of experiments performed and the quality of the solution.

The experimental procedure is the following:

• choose an initial parameter set that is the same in all runs;

• perform 5 complete learning sessions using PG algorithm for a fixed number of iterations (N iter = 20) and analyze the variance of the results (for the fitness values as well as for the final sets of parameters); • identify the parameters with low relevance during the PG learning process; • start PGPR learning processes starting from intermediate results of the PG learning process and fixing the parameters with low relevance • evaluate the reduction in the number of experiments and the differences in the quality of the solutions between PG and PGPR.

The results of the simulations are summarized below. Further details are given in www.dis.uniroma1.it/∼iocchi/RobotExperiments/HumanoidLearning.

• The fitness increases in a regular way and there is low variance between the 5 simulations (see Figure 8). The learning process allows for an increase of performance from policies with fitness 1.55 ± 0.05 at the first iteration to final results of 2.34 ± 0.06. • Not all the solutions converge towards the same parameter set (see Table 1). In particular, some parameters converge towards the same values (low variance in the final solutions), while others tend to assume different values (high variance). This can be explained by the fact that in the simulator some parameters are less relevant and do not contribute in a significant way to the optimal solution. For example, the height of the foot from the ground Z sw does not affect the quality of the solution since the model of the simulator is not precise enough to take into account uneven floor and frictions between the foot and the ground. • Between iteration 10 and iteration 20 between 3 and 5 parameters are considered not relevant. As shown in Table 2, some of them are different in the 5 simulations and they stabilize at different iterations. In almost all the cases, parameters that in the final set of the PG learning process have high variances (i.e., Z sw , X ds , K r ) have been identified by PGPR as not relevant. This confirms the ability of PGPR algorithm to early detect non-relevant parameters. • Applying PGPR algorithm from iterations where non-relevant parameters have been fixed allows for a decrease in the number of experiments between

Experiments with different initial values

In the second set of experiments we repeat the approach described before, but running different learning processes starting from different initial parameter sets. We started with PG algorithm and when the relevance of a parameter is below the given threshold T r , we split the learning task in two: 1) we continue with PG algorithm; 2) the irrelevant parameter is fixed and learning is pursued with the remaining parameters (we call this run PGPR-1). While running PGPR-1, when the relevance of a parameter is below the threshold, we split again in two learning tasks: 1) we continue with PGPR-1 algorithm; 2) we fix this parameter and start a learning session with the remaining ones (we call this run PGPR-2). And so on, until a fixed number of iterations is reached.

In the following tables, graphs and descriptions we use the terms PG, PGPR-1, PGPR-2, ... to refer respectively to the result of the standard PG algorithm, to the PGPR with 1 parameter fixed, to the PGPR with 2 parameters fixed, Run 1 K r = 0.024 [START_REF] Yamasaki | Acquisition of Humanoid Walking Motion Using Genetic Algorithm -Considering Characteristics of Servo Modules[END_REF] X ds = 0.250 [START_REF] Arechavaleta | The nonholonomic nature of human locomotion: a modeling study[END_REF] X sw0 = 0.285 [START_REF] Arechavaleta | The nonholonomic nature of human locomotion: a modeling study[END_REF] Z sw = 0.002 [START_REF] Parker | Learning gaits for the Stiquito[END_REF] Y ds = 0.056 [START_REF] Kim | Automatic gait optimisation for quadruped robots[END_REF] N P GP R = 266 (-17%)

Run 2

Z sw = 0.005 [START_REF] Sato | Reinforcement Learning for Biped Locomotion[END_REF] X ds = 0.245 [START_REF] Arechavaleta | The nonholonomic nature of human locomotion: a modeling study[END_REF] K r = 0.018 [START_REF] Kohl | Machine learning for fast quadrupedal locomotion[END_REF] Y ss = 0.051 ( 20)

N P GP R = 298 (-7%)

Run 3

X ds = 0.250 [START_REF] Hebbel | Modeling and learning walking gaits of biped robots[END_REF] Z sw = 0.004 [START_REF] Sato | Reinforcement Learning for Biped Locomotion[END_REF] K r = 0.021 [START_REF] Sato | Reinforcement Learning for Biped Locomotion[END_REF] Y ds = 0.054 ( 17)

N P GP R = 272 (-15%) Run 4
Z sw = 0.005 [START_REF] Niehaus | Gait Optimization on a Humanoid Robot using Particle Swarm Optimization[END_REF] K r = 0.027 [START_REF] Sato | Reinforcement Learning for Biped Locomotion[END_REF] X ds = 0.241 [START_REF] Parker | Learning gaits for the Stiquito[END_REF] Z st = 0.159 ( 20)

N P GP R = 286 (-11%)

Run 5

Y ss = 0.049 [START_REF] Sato | Reinforcement Learning for Biped Locomotion[END_REF] X sw0 = 0.274 [START_REF] Kim | Automatic gait optimisation for quadruped robots[END_REF] K r = 0.026 [START_REF] Chernova | An evolutionary approach to gait learning for four-legged robots[END_REF] N P GP R = 298 (-7%) Table 2 Non-relevant parameters: values and iteration in which they have been fixed. etc. Thus, the PG run corresponds to the standard PG algorithm, the PGPR-(n) run (with n being the maximum value reached during the procedure) corresponds to the PGPR algorithm proposed in this article (Figure 5), while the runs PGPR-(i) (1 ≤ i ≤ n -1) represent intermediate processes where only a subset of the irrelevant parameters have been fixed.

This procedure aims at verifying the effectiveness of the choice of fixing nonrelevant parameters at a certain iteration of the PG algorithm. It is important to notice here that after the learning process is split, the two sessions proceed in parallel with different randomized choices. Therefore, it is not possible to directly compare the results of the two sessions independently from the random choices that are taken during them.

Starting from a manually coded initial parameter set 0 X(with a fitness of 1.607 in the first iteration), 14 iterations of PG have been executed on all the parameters, reaching a fitness value of 1.865. Then one parameter has been fixed, because of its low relevance, and the learning process has been split in two: one execution with all the parameters, one execution with one parameter less (PGPR-1). At iteration 18, the values of the fitness were 1.954 for PG and 1.985 for PGPR-1, thus showing a slight increase of performance for PGPR. At this iteration a second parameter was below the relevance threshold and we split the execution again: we continued with PGPR-1 and we started a PGPR-2 session. At iteration 25 we stopped the learning process. The final fitness values for PG, PGPR-1, and PGPR-2 were respectively 1.935, 2.029, and 2.049, while the maximum values reached during all the executions were respectively 2.104, 2.161, and 2.241. Three additional learning processes, starting from different initial policies, have been run in Webots. The maximum fitness values obtained by each execution of the algorithm in the four runs have been summarized in Table 3. The value F 0 in the table reports the fitness function computed at the first iteration, and indicates how good the initial parameter set was. As shown in the table, the initial sets used in the runs have been chosen in order to evaluate the effectiveness of the approach when starting both from good parameters (high values of F 0 ) and from bad ones (low values of F 0 ). The first irrelevant parameter was detected/fixed respectively at iteration 14, 13, 12 and 10 for runs 1 to 4 (values in parenthesis). A second irrelevant parameter was detected only in runs 1 and 4, respectively at iteration 18 and 17. Different final results in the table mostly depend on the initial parameter set and on the randomness of the algorithms.

Initial parameter set

F 0 PG PGPR-1 PGPR-2 1
As shown in the table, the general trend is that, PGPR outperforms PG, and PGPR-(i+1) outperforms PGPR-(i). However, there are also cases in which this is not confirmed (for example, with initial set 4). One reason is certainly the randomness of the algorithm. A second reason is that when starting from an initial set that is far from the optimum, fixing a parameter may be more risky, since it can lead to worse solutions. Moreover, some parameters have been fixed early in the runs that start from lower quality initial policies. This is explained by the fact that when starting from a low fitness solution, some of the parameters contribute in a more significant way to the increase of the fitness (i.e., the derivative of the learning curve is higher), causing the other parameters to be fixed at earlier stages. As already mentioned, some of these choices may not be optimal (see again PGPR-2 in the fourth experiments).

The overall results of the experiments reported in this section are that 1) Policy Gradient methods are effective to improve performance of the walking gait described in this article, 2) PGPR method generally guarantees better solutions with respect to PG, since in most cases where the relevance of a parameter is low, fixing this parameter value allows for speeding up the search toward the optimal solution.

Experiments with the real robot

The main objective of this work is to implement an effective walking gait on the real NAO robot, exploiting the results obtained in simulation. Obviously, since the model of the NAO in the simulator is only approximated, the parameter sets that return best results in simulation do not guarantee the same performance on the real robot. However, simulated tests still help to discard bad values of the parameters, to further limit the parameter ranges and to estimate the directions in which the fitness function tends to increase. Moreover, the implementation of the learning algorithms has been fundamental to improve important aspects of the robot gait, such as stability and precision with respect to the desired trajectory.

One important issue we have considered when moving to experiments on the real robots is the lack of simmetry in the response of the motors. While with the simulator it is possible to consider the same set of parameters for driving both the left and the right leg, with the real robot we needed to split some of the parameters in order to differentiate the control of the left and the right leg. Moreover, we also noticed different behaviors of our four robots with the same parameters; this is again due to the different responses of the motors.

The experiments on the real robot have been performed as follows.

(1) The best solutions obtained in the simulator have been tested on the real robot and we have observed the different behavior of the robot with respect to the simulator. (2) We have chosen a "good" initial set of parameters by visual inspection, evaluating mostly the walk stability. (3) We have considered a rectilinear walk, and have adapted the computation of the fitness function to the real robot, on which we do not have a GPSlike device determining the real position of NAO. In practice, the fitness score is given by a combination of the performed distance and a stability value assigned by an operator that visually supervises the experiment. (4) We then apply the PG algorithm considering only the parameters that have shown to be more relevant during simulated experiments.

The results of two sessions of PG algorithm on two different real robots are reported here. In the first experiment (Nao-34), six iterations of the learning process have increased the fitness of the best policy from 45.75 to 57.00, while in the second experiment (Nao-40) the increase of performance in 3 iterations has been from 55.0 to 64.5. Moreover, we have verified that the parameters learned for the rectilinear walk can be effectively used for curvilinear walk as well. Details on the experiments and videos are available at: www.dis.uniroma1.it/∼iocchi/RobotExperiments/HumanoidLearning.

Conclusions

In this article, we have compared two learning methods for humanoid walking gaits based on Policy Gradient. In contrast with most works in the field of biped gait generation and biped gait learning, we have focused on curvilinear trajectories. We have shown that the PGPR algorithm, by taking into account parameter relevance, allows for better solutions than classic policy gradient, when only a few experiments are available, since it reduces the search space size during learning. The experimental results confirm the effectiveness of our biped motion control scheme, the performance of Policy Gradient reinforcement learning methods, and the higher convergence of the PGPR algorithm with respect to classic PG. In fact, we have applied this learning task to biped walking obtaining, both in a simulated environment and on real robots, notable improvements in the execution of walking gaits, even after a limited number of experiments. These results are fundamental in robot learning applications, where time and hardware consumption is a major issue.

Future work will consist of using PGPR to identify the parameters characterizing pure rectilinear and pure rotational gaits. We also plan to estimate the dynamic model of the NAO robot and to exploit its sensing capabilities in order to develop a ZMP gait controller, whose parameters could also be tuned using PGPR.

Fig. 1 .

 1 Fig. 1. The Aldebaran NAO robot with its 21 degrees of freedom, and reference frame F R (X, Y, Z) (green).

Fig. 2 .

 2 Fig. 2. Right foot trajectory in the X -Z plane, and characteristic parameters. Left to right: right foot swing, double support phase, and start of left foot swing. The right shoulder pitch movement is outlined in orange.

Fig. 3 .

 3 Fig. 3. Characteristic parameters of the leg roll joint control used for moving the center of mass sideways. (a) Top view, with qualitative trajectory of the projection of the center of mass in the X -Y plane (green) and initially right foot (dotted blue) swinging. (b) Rear view during single support (left) and double support (right) phases.

Fig. 4 .

 4 Fig. 4. Bottom view showing how the NAO Hip Yaw/Pitch joint is used for turning at ω < 0 over two steps (the swinging foot is dotted blue). Left to right: double support, right swing, double support, left swing, double support. The verse of the angular momentum induced by shoulder pitch movement is outlined in orange.

Fig. 5 .

 5 Fig. 5. Pseudo-code for Policy Gradient with Parameter Relevance algorithm.

Fig. 6 .

 6 Fig. 6. Examples of application of the PGPR algorithm.

Fig. 7 .

 7 Fig. 7. Relevant variables used to compute the fitness of a parameter set X. The robot center of mass is indicated with a green circle. The ideal and real trajectories are represented respectively by the black and green dashed curves.

Fig. 8 .

 8 Fig. 8. Learning curve for the 5 learning sessions.

  7 and 17 % with respect to PG. The best fitness between PGPR and PG is within ±5%. Final parameter sets [Z st Y ds Y ss Z sw X tot X sw0 X ds K r ] .

	Run	X	F (X)
	1	[0.158 0.059 0.053 0.001 0.168 0.289 0.239 0.026] 2.407
	2	[0.159 0.060 0.053 0.008 0.163 0.310 0.250 0.018] 2.378
	3	[0.161 0.059 0.055 0.006 0.165 0.287 0.243 0.022] 2.402
	4	[0.156 0.062 0.050 0.003 0.154 0.294 0.243 0.030] 2.296
	5	[0.153 0.056 0.051 0.006 0.170 0.267 0.203 0.028] 2.289
	Average	[0.157 0.059 0.053 0.005 0.164 0.289 0.236 0.025] 2.354
	Std.dev.	[0.003 0.002 0.002 0.003 0.006 0.015 0.019 0.005] 0.058
	Std.dev. % [1.8% 3.6% 3.3% 55.9% 3.8% 5.3% 7.9% 18.8%] 2.45%
	Table 1

See www.tzi.de/spl/ for details on the League.

openrdk.sf.net

Sinusoidal trajectories have been chosen here (and elsewhere in our gait model) for their smoothness and energetic efficiency.

www.cyberbotics.com

Unfortunately, this choice cannot be made in an ideal manner, and in practice reducing the search space implies a reduction in the quality of the solution. On the other hand, reducing the search space also involves that with the same number of experiments it is possible to explore the search space more in depth. Consequently, there should be a balance between the number of experiments and the quality of the solution.

In this article, we want to verify that reducing the search space by removing irrelevant parameters during the learning process may lead to an optimal solution after few experiments. In order to verify this statement, we adopt the Policy Gradient learning method, 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] and is suitable for a modification that takes into account the relevance of parameters [START_REF] Cherubini | An extended policy gradient algorithm for robot task learning[END_REF], and apply it to biped curvilinear walk.

In the remainder of this section, we recall the Policy Gradient algorithm and its extension that takes into account relevance of parameters, while in the following section, we describe how these methods have been applied to learning curvilinear humanoid gaits.

Policy gradient

The learning problem considered in this article is formulated as a policy gradient reinforcement learning problem [START_REF] Kohl | Policy Gradient Reinforcement Learning for Fast Quadrupedal Locomotion[END_REF], that considers each possible set of parameter assignments, and defines an open-loop policy that can be executed by the robot. Assuming that the fitness function (or objective function) F (X) is differentiable with respect to each of the parameters, the Policy Gradient (PG) algorithm estimates its gradient in the parameter space X ∈ R k , and follows it toward a local optimum X * .

The parameter optimization approach based on Policy Gradient 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 0 (m = 1, . . . , p), near X 0 , are evaluated. The number of policies p is proportional to the search space dimension: p = Λk. Each of the p policies is generated as: m X 0 = X 0 + [ρ 1 , . . . , ρ k ] T , and each perturbation ρ j is chosen randomly in the set {j , 0, + j }. Each m X 0 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 fitness function at each policy m X 0 , 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 X 0 , which is then normalized, multiplied by a scalar stepsize, noted η, and added to X 0 , to determine X 1 and begin the next iteration (i = 1, . . . , N iter ). The step-size η is fixed to a constant value throughout the learning process.

The algorithm usually terminates after a predefined number of iterations N iter ,


A Cherubini

M Leonetti

L Marchetti

A De Luca

L Iocchi

D Nardi

G Oriolo

M Vendittelli

RoboCup 2008 Standard Platform League -Nao Division

The team for 2008 is composed by two groups from the Computer and System Science Department of Sapienza University: the Artificial Intelligence group and the Robotics group. The main research motivation for participation in RoboCup 2008 Nao division is to study the integration of complex control systems for humanoid locomotion with artificial intelligence techniques that have been typically developed on other mobile robotic platforms.

The members of the SPQR team that have developed the Nao soccer team are: Andrea Cherubini, Luca Marchetti, Matteo Leonetti, Simone Elviretti, Federico Faina, Francesca Giannone, Marcello Lombardo, Marco Manganelli, Pier Francesco Palamara, Diana Nobili, Mauro Sbarigia.

The development for RoboCup 2008 has been mainly divided in three parts: 1) implementation of a robotic software architecture for the Nao robots; 2) humanoid control and locomotion for realizing basic movements that are necessary for a soccer application; 3) artificial intelligence techniques for perception, localization, behavior control, behaviors learning and multi-robot coordination. In this report, we will first present our development framework for RoboCup 2008 and then we describe in more details the AI and humanoid control techniques that have been used on the Nao robots.

Development Framework

During the development of many RoboCup applications (ranging from middlesize, to legged, rescue and @home robots) we have gained a lot of experience and developed a set of reusable modules. Except for the AIBOs, that have a specific platform and operating system, all the other robots and robotic applications have been realized by using a common middleware. In particular, we have developed a Robot Development Kit (RDK), OpenRDK2 (formerly named SPQR-RDK [START_REF] Farinelli | Design and implementation of modular software for programming mobile robots[END_REF]), that is now released as open source.

OpenRDK allows for fast implementation of robotic applications on different platforms and for reuse of software components. It provides middleware tools for managing a set of modular components that interact with each other via a shared repository. Each component is responsible for a basic functionality of the robotic platform (e.g., perception, localization, plan execution, motion control, etc.) and the OpenRDK framework provides all the routines needed for effective interaction among these components: synchronization, information sharing with memory lock mechanisms, remote inspection for debugging, etc.

Modules are loosely connected to each other and can be scheduled independently and with different priorities. The modules interact and communicate with each other using a blackboard-type data repository. Based on an abstraction of the information shared by the modules, OpenRDK allows for an easy interchange among modules with similar functionalities, without modifying or recompiling the code. This is very useful, for example, to evaluate alternative modules or to switch from simulated to real robots and sensors. Moreover, information can be shared among different processes/computers and thus visualized and modified by a remote console at run-time. This is extremely useful for tuning and debugging purposes.

Overall, the use of OpenRDK has notably increased productivity of our research group in the development of Nao soccer application. The porting of OpenRDK on the Nao platforms required only a few modifications and it is completely available for use to other teams as well (see SPQR and OpenRDK web sites for more details).

AI techniques for a Standard Platform Team

The RDK allows for an effective interaction among modules that compose a robotic application. In this section we will briefly present some of the components that are included in Nao 2008 development: color segmentation based on a dynamic and adaptative color space transformation that increases robustness to light variations [START_REF] Iocchi | Robust color segmentation through adaptive color distribution transformation[END_REF]; image processing using a limited number of perceptual pixels that activate object recognition; localization implemented with a particle filter based method [START_REF] Marchetti | A comparative analysis of particle filter based localization methods[END_REF]; behavior control using Petri Net Plan representation language [START_REF] Ziparo | Petri net plans[END_REF]; learning techniques for improving robot performance [START_REF] Cherubini | Layered learning for a soccer legged robot helped with a 3D simulator[END_REF][START_REF] Cherubini | An extended policy gradient algorithm for robot task learning[END_REF]; coordination based on a distributed task assignment [START_REF] Iocchi | Distributed coordination in heterogeneous multi-robot systems[END_REF][START_REF] Farinelli | Assignment of dynamically perceived tasks by token passing in multi-robot systems[END_REF].

Dynamic color segmentation and image processing

In order to improve robustness of color segmentation and to avoid long and tedious calibration processes, we have developed a dynamic color segmentation method [START_REF] Iocchi | Robust color segmentation through adaptive color distribution transformation[END_REF] that is able to provide robust and efficient color segmentation with very few calibration effort (Figure 1).

The method is mainly based on fast analysis of a mono dimensional color space: the H component of the HSV. By analyzing color distribution of the current image, we are able to compute a transformation function that transforms such distribution in another distribution. The resulting distribution provides for efficient color segmentation based on static threshold, but being computed according to the current image is also very robust to illumination changes. Evaluation of the approach shows that the method achieves performance that are comparable with those obtained by manual calibration, being at the same time robust to illumination changes.

Image processing on legged robots usually has to take into consideration limitations in CPU power. For AIBO robots we have developed a hierarchical approach for examining the image pixels: first a set of sentinel pixels that are non-uniformly spread on the image are analyzed; then, for those pixels that activate some condition, a region growing approach is used to analyze adjacent pixels and then these regions are grouped in blobs that are then analyzed for object recognition. This approach provides for similar results with respect to complete scanning of the image, but it significantly reduces the computational time.

Localization

Our approach to localization uses a probabilistic technique based on particle filters. In [START_REF] Marchetti | A comparative analysis of particle filter based localization methods[END_REF] we have compared different solutions based on particle filters, investigating the use of two different strategies: the well known Sample Importance Resampling (SIR) filter, and the Auxiliary Variable Particle filter (APF). As a result of the experiments performed, we have detected situations where one strategy is better than the other as well as hints about the use of sensor resetting, that is common in this kind of implementations.

For the Nao robots, we have integrated in the localization technique information about the game state (or in general about the task state), aiming at choosing the localization strategy and parameter setting that are more suitable for the current situation.

Localization is based on perception of known landmarks: beacons, goal poles, lines and corners, for which different sensor models are used in the particle filter implementation. Moreover we are developing more sophisticated mechanism in proposal selection of Particle Filter algorithm that use the result from a Kalman Filter. The aim of this is to use a more informative distribution rather than approaches from previous years.

Petri Net based behavior control

The behaviors of a complex soccer robot require to be represented by plans with high representation power, in order to express all the capabilities of the robot. In particular, it is important to model the following features: 1) sensing actions implementing if-then-else or while constructs able to determine the robot behavior according to the current situation at run-time; 2) concurrency of actions (e.g., moving the head while going to a position); 3) interrupts (e.g., aborting a go-to-ball action if the robot can not see the ball anymore; 4) action synchronization between two parts of the robot (e.g., head and legs); 5) action synchronization between two or more robots.

In order to represent the above mentioned features, transition graphs are not adequate, since, for example, concurrency and interrupts can not easily be modeled. Therefore, we adopted a formalism, called Petri Nets Plans (PNP), which is enough expressive to describe plans with all the above mentioned features (see [START_REF] Ziparo | Petri net plans[END_REF] for further details).

As a difference with other approaches based on extensions of transition graphs, such as XABSL [START_REF] Röfer | German team robocup[END_REF], we clearly distinguish action specification from action implementation, obtaining a framework which permits easier debugging: first, the semantic is well defined and easily verifiable by automated verification programs; second, we have a high granularity of actions which are grouped by functional properties and physical resources used.

The plan execution module based on PNP formalism has been successfully used in all our robotic applications (Four-Legged soccer, Rescue and @Home), providing a high flexibility and being easy to use, thanks to graphical tools for writing, verifying and debugging plans.

Behavior Learning

Soccer robots, and in particular legged ones, require a fine tune of the parameters specially in the implementation of behaviors and basic control actions and in the strategic decisional processes.

In [START_REF] Cherubini | Layered learning for a soccer legged robot helped with a 3D simulator[END_REF] we have performed experiments on layered learning approaches for learning optimal parameters of basic control routines, behaviors and strategy selection. We compared three different methods in the different layers: genetic algorithm, Nelder-Mead, and policy gradient. Moreover, we studied how to use a 3D simulator for speeding up robot learning. The results of this experimental work on AIBO robots have been not only the realization of improved behaviors, but also a more effective learning methodology that makes use of a simulator. Some preliminary results on learning approaches for humanoid robots are described later in Section 4.3.

Multi-robot coordination

In previous multi-robot applications we have implemented a distributed coordination protocol that allows the robots to assign themselves tasks according to the current situation of the environment. During the last years we have experimented many coordination protocols for dynamic task assignment, using both full broadcast communication [START_REF] Iocchi | Distributed coordination in heterogeneous multi-robot systems[END_REF], and token passing based approaches [START_REF] Cottefoglie | Dynamic token generation for constrained tasks in a multi-robot system[END_REF]. These systems have been demonstrated to work effectively in soccer applications (both in middle-size and in the four-legged leagues).

Moreover, we have addressed another important problem for multi-robot coordination that arises in presence of dynamic and noisy perception. The works in [START_REF] Farinelli | Task assignment with dynamic perception and constrained tasks in a multi-robot system[END_REF][START_REF] Farinelli | Assignment of dynamically perceived tasks by token passing in multi-robot systems[END_REF][START_REF] Farinelli | Dealing with perception errors in multi-robot system coordination[END_REF] show different ways to distributed coordination in presence of dynamic perception of tasks to be accomplished and on noisy and erroneous perception. The main advantage of the proposed solutions with respect to others is in the achievement of optimal results with limited bandwidth communication requirements. This make the approaches effective also in presence of noisy communication with limited bandwidth.

Humanoid locomotion and control

Research on biped locomotion has steadily increased over the last years. Advances in hardware technologies and software architectures allowed the realization of impressive humanoid robots, such as the Honda ASIMO or the Sony SDR-3X, as well as many prototype robots developed in university labs. Biped locomotion is classified in static, dynamic or purely dynamic methods. In our recent research work, we have developed both static and dynamic locomotion approaches. In both cases, the biped locomotion developed is composed by two main phases: the single support phase and the double support phase.

Biped Locomotion based on static walking

For the NAO robot, we have developed a parameterized static walk control scheme. Our scheme consists of planning the trajectories of the feet and barycenter in the robot workspace. The swing and stance feet (during the single support phase) respectively track a semi-elliptical and a linear trajectory. These trajectories are generated by solving the inverse kinematics problem for the 6 pitch joints (which are not actuated during double stance), see Figure 2, left. The robot barycenter (during both single support and double stance), is moved along a trajectory designed so that its projection on the ground stays within the support foot. This trajectory is parallel to the ground plane and is generated by solving the inverse kinematics problem for the 4 roll leg joints (see Figure 2, right). In order to improve the gait stability, reduce noise in the FSR readings, and guarantee a 'human-like' gait, the foot soles are kept parallel to the ground throughout the gait. This constraint reduces from 10 to 6 the number of degrees of freedom utilized for gait generation. Curvilinear gaits are generated by exploiting the ankle yaw joint. This joint tracks a sinusoidal trajectory with amplitude proportional to the desired curvature.

Biped Locomotion based on dynamic walking

A Biped Locomotion Strategy for the AIBO ERS-210 Quadruped Robot has been developed and presented in [START_REF] Zonfrilli | Design and implementation of a biped locomotion strategy for the quadruped robot Sony ERS-210[END_REF] (see Figure 3). Although AIBO has several limitations which make biped locomotion a challenging task, such as passive feet, a high baricenter in the erect posture, and relatively weak actuators, we showed that it is possible to realize a biped gait by properly designing the single and double support phases. This approach is in contrast with most previous works, in which a biped mechanism is built having already in mind a certain control strategy. During the double support phase the robot is controllable, while it is not in the single support phase. This is due to the lack of an actuated foot. In the double support phase there is the transition of the support leg, from right to left or viceversa. Many authors have proposed a control strategy in which the double support phase is assumed to be instantaneous, and the actual biped locomotion is achieved by the single support phase, while we have chosen to fully exploit the double support phase. The main idea on which we rely for the control of the system is to reduce the dynamic of the system, in the single support phase, as that of a passive inverse pendulum, in order to explicitly control the boundary conditions of the pendulum to obtain a desired dynamic evolution. The double support phase is thus exploited in order to achieve the correct take-off conditions for performing the single support phase. During the latter, the mechanism motion is essentially uncontrolled but can be predicted and planned using a simple equivalent mechanical system. Both simulation and experimental results described in [START_REF] Zonfrilli | Design and implementation of a biped locomotion strategy for the quadruped robot Sony ERS-210[END_REF] show the positive outcome of our study.

Learning Techniques for Biped Locomotion

Another approach for humanoid locomotion has been experimented using learning techniques 3 In particular, we have devised and applied a learning method for biped locomotion using genetic algorithms and a new strategy for interleaving learning steps in simulation with learning steps on the real robot. In particular, we use genetic algorithms to explore the parameter space of a fuzzy controller guided by an oscillator that implements a walking behavior for the robot. Preliminary results of our approach show that most of the learning can be done in simulation and the steps on the real robot are used to adjust the learnt fitness function. In contrast with other approaches that use simulated results to refine the model of the virtual robot, we use simulated results only to modify the fitness evaluation function. Such a learning approach has been experimented on the humanoid robot Robovie-M and its virtual model in USARSim [START_REF] Iocchi | Learning biped locomotion using interleaved simulated and real data[END_REF].

1 IntroductionSPQR 1

 11 is the group of the Faculty of Engineering at Sapienza University of Rome in Italy, that is involved in RoboCup competitions since 1998 in different leagues (Middle-size 1998-2002, Four-legged since 2000, Real-rescue-robots 2003-2006, Virtual-rescue since 2006 and @Home in 2006). In RoboCup 2008, SPQR team will participate in the Standard Platform League with Nao humanoid robots and in the Virtual Rescue League.

Figure 1 :

 1 Figure 1: Color segmentation on Nao robots

Figure 2 :

 2 Figure 2: NAO walking: pitch joints (left), roll joints (right).

Figure 3 :

 3 Figure 3: AIBO biped walking.

openrdk.sf.net