Amitesh Kumar Singam

Wlodek J Kulesza

Comparative Studies of Unsupervised and Supervised Learning Methods based on Multimedia Applications

Keywords: VQM, NR-VQM, SVM, PCA, SSIM

In the mobile communication field, some of the video applications boosted the interest of robust methods for video quality assessment. Out of all existing methods, We Preferred, No Reference Video Quality Assessment is the one which is most needed in situations where the handiness of reference video is partially available. Our research interest lies in formulating and melding effective features into one model based on human visualizing characteristics. Our work explores comparative study between Supervised and unsupervised learning methods. Therefore, we implemented support vector regression algorithm as NRbased Video Quality Metric(VQM) for quality estimation with simplified input features. We concluded that our proposed model exhibited sparseness even after dimension reduction for objective scores of SSIM quality metric.

I. INTRODUCTION

The usage of consumer video applications in mobile devices has been increased to a large extent. Due to the extremely large competition between service providers and application developers to provide the better quality based on the neediness for the advanced methods to assess the video quality is in great demand now. The Multimedia services like video chatting and live video streaming in mobile or hand-held devices boosted the interest in no-reference objective video quality assessment since the availability of reference video is partially available. One of the main features of video services is quality of service as observed by the end user. For instance, the visual quality within transmission can get degraded while capturing, loading, saving or reproduction and distortions within video buffering might occur at any of these stages. Since humans are considered as true judges of video quality due to end users of the video services. In technical terms, the process of validating of video quality by viewers is referred as subjective video quality assessment. However, subjective experiments are often too time-consuming, inconvenient, costly and moreover it must be done under specific recommendations in order to produce standard results. These facts gave rise to the need of some intelligent ways of predicting quality assessment based on accuracy and it can be performed swiftly and economically.

II. VIDEO QUALITY ASSESSMENT

In our research work, we carefully employed the specifications recommended by ITU-R BT 500-10 as mentioned in [1] and VQEG Hybrid test plan in [2] which is explained briefly in following sections.

III. PROPOSED IDEA

Mainly, the proposed method involves extraction of visual quality relevant bitstream parameters and building of a machine learning based model for quality prediction. These parameters were selected carefully to keep the complexity in control and to get reasonable coding information which can represent the coding distortions. Following is the description of the extracted parameters and the rationale of making a parameter a part of the proposed model.

IV. FEATURE EXTRACTION OF H.264 BITSTREAM DATA

Feature extraction out of encoded video sequence has been processed using JM Reference software Version16.0. The Feature extraction of bit stream data which has been generated as a trace file after encoding process. 1) Bitrate.

2) Frame rate 3) Percentage of inter macroblocks of size16x16. 4) Percentage of inter macroblocks of size 4x4 5) Percentage of inter macroblocks of size 8x8 6) Average quantization parameter. .

V. UNSUPERVISED LEARNING METHOD

Generally when we are dealing with high dimensional data, addition of more features will effect the system or model performance and increase complexity of system, therefore in order to overcome curse of dimensionality factors such as efficiency, classification performance and ease of modeling are to be considered. Efficiency is further classified into measurement, storage and computational costs. Especially in machine learning concept, a finite number of observations in a high-dimensional induced space with each input data having possible number of values, any model required large number of features for training to make sure that they are numerous samples with each permutation of values. Therefore, our main idea is to reduce the dimension of inputs with minimal loss of information. Dimensionality reduction is suitable in visualizing data, noticing a compact representation, and minimizes computational processing. In addition, reducing the number of dimensions can separate the features with significant data from less significant ones which provides further Vision into the nature of the data which may not be discovered otherwise. There are various dimensionality reduction techniques like Partial least squares(PLS), principle component analysis(PCA), singular value decomposition(SVD), kernel principle component analysis(KPCA), factor analysis and hierarchical clustering etc. PLS and PCA has two functions in regression analysis i.e. transforming highly correlated variables to independent variables via linear transformation and dimensionality reduction. In the case of regression, So we preferred to use PCA for dimensionality reduction in our research work.

A. Dimension Reduction a) : Especially in machine learning concept, a finite number of observations in a high-dimensional induced space with each input data having a large number of possible values, any model requires large number of features for training to make sure that they are numerous samples with each permutation of values. Therefore, our main idea is to reduce the dimension of inputs with minimal loss of information. Dimensionality reduction is suitable in visualizing data, noticing a compact representation, and minimizes computational load. In addition, reducing the number of dimensions can separate the features with significant data from less significant ones which provides further vision into the nature of the data which may not be discovered otherwise. There are various dimension reduction techniques like principle component analysis, singular value decomposition, kernel principle component analysis, factor analysis and hierarchical clustering etc. In our research work we deployed PCA for dimensionality reduction

B. Principle Component Analysis

Principle component analysis is a statistical method which uses orthogonal linear transformation technique that projects a set of vectors into a new dimension which has components that are linearly uncorrelated and arranged according to decreasing order of variance. It is assumed that most significant data is found in the first coordinates of the projected space and it contains larger variance. Reducing the dimension of the input vector leads to improvement in the generalization performance.

a) : PCA is used to reduce the dimension of input space for our proposed model. The reduction of dimensions in the input space will reduce the complexity of the system and also decreases the time which is necessary to train the model. The PCA technique can be chosen as the method for preprocessing data and to extract uncorrelated features from the data. b) : Computing PCA, If X is an input vector of m dimensions and In order to reduce the dimensions, we need to eliminate insignificant data from a given input vector.

X = [x 1 ; x 2 ; ::; x m0 ; x m0+1 ; :::::; x m ]

(1)

c) : we have to map the input vector X in other dimension Xnew . By designing a transformation matrix (T) of m rows and m columns and multiplying matrix T with input vector we get Xnew . Therefore expression is given as

Xnew = T: X (2)
X is a zero mean m dimensional random vector.

Xnew is new space dimension.

d) : PCA is a multivariate technique employed for dimensionality reduction of a Input features with high number of correlated variables, Therefore we need to maximize the rate of decrease of variance in order to reduce the dimensionality of input vector. A mathematical model of PCA follows e) : If X is input random vector and q is unit vector of m dimension and According to the property of vector q, Euclidean norm of q is one. k q k= 1 By projecting X on q in a projection space A. we get,

A = XT q (3) Variance E[A 2 ] = qR xx qT (4)
where R xx is the correlation matrix

R xx = E[ X XT ] (5)
let (q) be the variance probe

(q) = qR xx qT (6)
For minimal value of variance

(q + q) = (q) (7)
the eigen values 1 ; 2 ; :::::::::: m and the corresponding orthogonal eigenvectors q1 ; q2 ; ::::::q m of the covariance matrix R are calculated and arranged according to their magnitude 1 2

::::::::::

m Rq j = j qj ( 8
)
where 1 is highest value of all eigen values.

Q = [q 1 ; q2 ; :::::::::::q j ; ::::::::; qm ]

= diagonal[ 1 ; 2 ; :::::::::

: m ] (10)
Q is an orthogonal matrix satisfying

qi T qj = 1; if i = j 0; if i 6 = j (11)
Orthogonal similarity transformation is expressed as

QT R Q = (12)
In expanded form

qj T Rq k = j ; if k = j 0; if k 6 = j (13)
The correlation matrix R is expressed in terms of its eigenvalues and eigenvectors as following

R = m X j=1 j qj [q] j T ( 14
)
(q j ) = j (15) a j = X T qj (16)
for j=1,2,....m (represents analysis) a j =projection of X onto principle directions,

X = m X j=1 a j qj (17)
for j=1,...., m (represents synthesis) Let the eigen values 1 ; 2 ; ::::: l are largest values of correlation matrix R xx and

X = l X j=1 a j qj (18)
X is not exact but approximate solution because of truncation to l terms but the dimension of vector X is preserved. Matrix representation of Encoder and Decoder of PCA are f) :

2 4 x 1 j x m 3 5 ! 2 4 [q 1 ] T j [q l ] T 3 5 ! 2 4 a 1 j a l 3 5 g) : 2 4 a 1 j a l 3 5 ! q1 ql ! 2 4 x1 j xm 3 5 ẽ = X X = m X i=l+1 a j qj (19)
Error is found to be orthogonal to X , since PCA transforms linear input space into an orthogonal space ẽ:x = 0 Total variance of m-components of input data

X m X j=1 j 2 = m X j=1 j (20) Total variance of l -components of X l X j=1 j 2 = l X j=1 j (21)
Total variance of (l-m) components of input data vector in error vector

m X j=l+1 j 2 = m X j=l+1 j (22)
Where l+1 ; l+2 ; :::: m corresponds to small variance. So, the variance of input vectors which are detected by PCA depends on eigen values.

In this section all the equations from 2.8-2.29 are derived h) : i are sorted in descending order and the proportion of variance has been explained by principle components(l) as 1 + 2 + :::::::::: + l 1 + 2 + ::::: + l + ::::: + m If the dimensions are highly correlated, then there will be less number of eigenvectors with large eigenvalues so it has l m dimensions and a large dimension reduction may be obtained. We found such typical cases in image and speech processing tasks where inputs are highly correlated. If dimensions are not correlated, then there will be no gain through PCA.

VI. SUPERVISED LEARNING METHOD

Kernel based learning methods are classified into supervised and unsupervised learning algorithms. Kernel method solves any problem by mapping the input data set into high dimensional feature space via linear or nonlinear mapping which is also referred as kernel trick. In recent years, few powerful kernel based models were proposed such as support vector machines, kernel fisher discriminant and kernel principal component analysis which are used for regression, classification, dimensionality reduction and other jobs. In our research work, we adapted Support Vector Machines(SVM) algorithm for regression analysis.

A. Support vector Machines

Support Vector machine(SVM) is a supervised and powerful learning Based algorithm invented by Vladimir VaDnik [3] and it is commonly used for classification and regression analysis. Its formulation is based on structural risk minimization principle which includes capacity control in order to prevent over-fitting problem of Empirical Risk Minimization principle based learning algorithms like traditional Neural Networks. In our research work, we performed regression analysis where Support Vector Regression exhibits the benefits of machine learning with the capability of learning difficult data patterns by mapping of simplified input features extracted from h.264 bit stream data and regressing with desire or true values in a very effective way. The mechanism of SVM works by mapping of nonlinear input data to high dimensional kernel induce space via nonlinear mapping which leads to solving set of linear equations in kernel space [?]. An insensitive loss function is introduced in SVM which measures the risks and the kernel functions has the flexibility that allows SVM to search a wide variety of hypothesis spaces [4].

B. Regression Analysis

Support Vector Regression model will provide better accuracy for predicting the video quality in no-reference video quality assessment and line up with human visual system. Support Vector Regression is a supervised learning method in which the input data is mapped into high dimensional kernel induced feature space via nonlinear mapping. Thus a nonlinear function is transformed to linear function where regression is performed in high dimensional space. The capacity of the model is controlled by parameters that do not depend on dimension of feature space. In support vector regression, a loss function is introduced called as epsilon that ignores errors situated within the zone of the true value as shown in figure .  a) : The given input data set X is first mapped onto an m-dimensional feature space using nonlinear mapping, and then a linear model is constructed in the m-dimensional feature space. The linear model in the feature space is given by

f (x; !) = m X j=1 ! j g j (x) + b (23)
g j (x); j = 1; :::m is a function of nonlinear transformations, and the term b is the bias. Since by pre-processing the input data it is assumed to have zero mean, therefore bias is dropped.

The epsilon band with slack variables is shown in the below figure.

Slack variables measure the cost of the errors on the training points and epsilon error is zero for all points that are inside the epsilon band. Support vector regression introduces a loss function called "-insensitive. Quality estimation can be measured with the help of the loss function.

L " (y; f (x; !)) = ( 0; if jy f (x; !)j "; jy f (x; !)j "; otherwise.

(24) The empirical risk is defined as

R emp (!) = 1 n n X i=1 L " (y i ; f (x i ; !)) (25)
The linear regression is performed by support vector regression in higher dimension kernel induced feature space using "insensitive loss, also by minimizing tries to reduce complexity of the model. Outside the "-insensitive zone the deviation of training data samples is measured by introducing slack variables ( i ; i for i=1,....,n) slack variables are non-negative which determines upper and lower bound. Therefore support vector regression is formulated for minimization.

min 1 2 jj!j j 2 + C n X i=1 ( i + i ) (26)
s:t 8 > < > :

y i f (x i ; !) " + i f (x i ; !){y i " + i i ; i 0; i=1,....,n.
The optimization can be transformed to the dual problem

f (x) = nsv X i=1 ( i )K(x i ; x)) (27) w:r:t0 i C; 0 i C b) :
where n sv -No of Support Vectors, ; i are lagrangian coefficients of certain samples. Some of them are non zero mean and corresponding samples are support vectors and the kernel function is

K(x; x i ) = m X j=1 g j (x)g j (x i ) (28)
Commonly used kernel functions are: linear kernel function, polynomial kernel function, RBF kernel function. In our proposed model we use RBF as kernel function K(y; y i ) = exp jjy y i j j 2 2 (29)

In this section the equations from 2.41-2.47 are derived. Where is kernel parameter. The generalization performance of support vector regression depends on a good setting of kernel and meta-parameters (C, "). Optimal parameter selection problem is also complicated by the fact that complexity of SVR model depends on all three parameters. SVM treats meta-parameters as user-defined inputs for regression. Selection of kernel type and kernel function parameters depends on application-domain knowledge and also should reflect distribution of input (x) training data. C determines the trade-off between the model complexity and the amount up to which deviations larger than " are tolerated. If C is too large or infinity, then the objective is to minimize the empirical risk, without regard of model complexity part in the optimization formulation . The " Controls " -insensitive zone width, to fit the training data. The value of this parameter will affect the number of support vectors which are used to construct the regression function, if " is large only few support vectors are selected and larger "-values results in more flat estimates. Hence, both C and "values affect complexity of model but in a different way.

VII. TEST METHODOLOGY

We preferred k-fold cross-validation (CV) strategy to train and validate the proposed model and Cross Validation(CV) is a technique which was used for estimating performance of predictive model. generally CV is a re-sampling strategy used to validate the performance of our proposed model by random sub-sampling of the available data. In other words, the original data is subdivided randomly into k folds. In each round of CV (k -1) folds are used for training and the remaining fold is used for validation, this procedure is repeated for k times with each of the k folds should used exactly once for the model validation. Performance estimation of our proposed model is determined by average of results obtained in k folds for k rounds

  [5]. Errors which occur on the validation sets are monitored during training. The validation error generally decreases during the initial phase of training, as does the training set error. a) : Mainly, input features are obtained by extraction of bit steam data at decoder side after transmission of video within the network. Our proposed Model has been trained and tested with input features(X) consists of 6 parameters extracted out of bit-stream data as mentioned in above with respective corresponding Target values of SSIM quality metric.


Marco Cognetti

Daniele De Simone

Federico Patota

Nicola Scianca

Leonardo Lanari

Giuseppe Oriolo

Real-time pursuit-evasion with humanoid robots

I. INTRODUCTION

Research on humanoid robots has flourished in the last decade and their use is currently envisaged in a number of applications. Since many of these involve the simultaneous presence of humans and humanoids in the same environment, it becomes imperative to investigate the safety-related issues arising from their coexistence. For example, the objective of the EU H2020 research project COMANOID 1 is to foster the deployment of humanoid robots in aeronautical shopfloors shared with human co-workers.

One of the most essential safety layers in a robot is arguably detection and avoidance of obstacles, static or dynamic. This is a long-standing problem in robotics since Khatib's pioneering work [START_REF] Khatib | Real-time obstacle avoidance for manipulators and mobile robots[END_REF], and by now the literature includes a number of methods for fixed-base manipulators or mobile robots; e.g., see [START_REF] Yoshida | Reactive robot motion using path replanning and deformation[END_REF], [START_REF] Khansari-Zadeh | A dynamical system approach to realtime obstacle avoidance[END_REF] and the references therein. Recently, researchers have started looking at this issue in the context of safe human-robot coexistence and interaction [START_REF] De Luca | Integrated control for pHRI: Collision avoidance, detection, reaction and collaboration[END_REF], [START_REF] Lacevic | Safety assessment and control of robotic manipulators using danger field[END_REF]. Specific criteria for robot navigation in the presence of humans have been investigated in [START_REF] Kruse | Human-aware robot navigation: A survey[END_REF].

While the fundamental issues are the same, the design of safety layers for humanoids must take into account the distinctive peculiarities of these robotic systems, namely the fact that their base can only be displaced through stepping gaits and that equilibrium must be maintained at all times during motion (see, e.g., [START_REF] Kajita | Introduction to Humanoid Robotics[END_REF]). One of the first works that showcased a humanoid avoiding moving obstacles was [START_REF] Michel | Vision-guided humanoid footstep planning for dynamic environments[END_REF], where real-time vision and replanning were used for autonomous navigation with ASIMO; more recent results are presented in [START_REF] Chestnutt | Navigation and gait planning[END_REF] and, using Model Predictive Control techniques, in [START_REF] Bohorquez | Safe navigation strategies for a biped robot walking in a crowd[END_REF], [START_REF] Naveau | A reactive walking pattern generator based on nonlinear model predictive control[END_REF].

In a previous work [START_REF] Cognetti | Real-time planning and execution of evasive motions for a humanoid robot[END_REF], we have addressed a basic safety problem for humanoids: in particular, a situation was considered where the robot is threatened by a moving obstacle (e.g., a human, or another robot) that enters its safety area headed for collision. Under the assumption that the moving obstacle did not change its direction, we developed and implemented a method by which the humanoid could plan and execute in real time an evasion maneuver. In this paper, we shall remove that assumption, and consider a worst-case scenario where the obstacle is actively trying to reach and collide with the humanoid. This leads us to replace the moving obstacle with another humanoid, and to consider therefore a full-fledged pursuit-evasion problem with humanoids.

Pursuit-evasion is a well-known topic in robotics and has been studied from several perspectives, see [START_REF] Chung | Search and pursuit-evasion in mobile robotics[END_REF] for a recent review. Our viewpoint is to consider a coupled dynamic system consisting of two identical humanoids with equivalent control schemes but different objectives: the pursuer tries to align with the line-of-sight to the evader, whereas the latter attempts to move away from the line-of-sight to the pursuer, e.g., in a direction orthogonal to it.

At the core of the proposed control scheme is a maneuver planning module that implements a sequential procedure. From the desired direction of motion, a corresponding Cartesian trajectory is generated, around which footsteps are placed; from these, a stable trajectory for the humanoid CoM is computed. The whole procedure relies on closed-form expressions, thus making real-time implementation possible and ultimately allowing its use in a replanning framework, where each robot updates its motion plan upon completion of a step to account for the perceived motion of the other.

An interesting outcome of our study is that the pursuer and the evader converge to a circular limit cycle along which they travel at the same speed. This property will be first observed on unicycles, which will be used as template models for Cartesian trajectory generation, and then confirmed on NAO humanoids, both in simulations and experiments.

The paper is organized as follows. In Sect. II, we introduce feedback laws for pursuit-evasion with unicycle robots to be used as template models for real-time trajectory generation. Section III addresses the pursuit-evasion problem with humanoids and describes the control schemes that drive the two robots. In particular, we analyze the maneuver planning modules for both the pursuer and the evader, and discuss their use in a replanning framework. Simulations and experiments are presented in Sect. IV. Possible future work is mentioned in the concluding section. II. PURSUIT-EVASION WITH UNICYCLES Our method for pursuit-evasion with humanoids is based on the use of the unicycle2 as a template model for realtime trajectory generation. We shall therefore discuss first pursuit-evasion with unicycles.

We have two unicycle robots, one of which acts as a pursuer and the other as an evader (see Fig. 1). Each robot performs computations in its own moving frame consisting of the sagittal and the coronal axes, and only uses local information made available by its own sensory system. We make the following assumptions: A1 The evader is not performing any particular task, or it is ready to abort it immediately.

A2

Each robot can determine (and measure the orientation of) the line-of-sight to the other.

A3

There are no obstacles in the workspace. In our framework, both the pursuer and the evader are controlled in pure feedback mode; that is, there is no anticipative action based on an estimate of the other robot's intention of motion. At any instant, the pursuer determines the lineof-sight to the evader, represented by the unit vector n aim , and steers its course so as to align with n aim . The evader determines the line-of-sight to the pursuer, represented3 by -n aim , computes from this an evasion direction n eva , and steers its course so as to align with n eva .

Below, we discuss the two robots separately.

A. Pursuer

The pursuer unicycle is represented by

ẋp = v p cos θ p ẏp = v p sin θ p θp = ω p ,
where (x p , y p , θ p ) is the robot configuration and v p , ω p are its driving and steering velocity inputs. The pursuer moves under the action of the following control law4

v p = v (1) ω p = k (θ aim -θ p ) (2)
where v > 0, k > 0 and θ aim = n aim is the phase angle of n aim . The constant driving velocity v sustains a continued pursuing behavior, while the angular velocity forces the robot to align its sagittal axis with n aim , i.e., with the line-of-sight to the evader. Note that the pursuer directly measures the angular error θ aim -θ p , so that no absolute measurements are actually needed.

B. Evader

The equations of the evader unicycle are ẋe = v e cos θ e ẏe = v e sin θ e θe = ω e , where (x e , y e , θ e ) is the robot configuration and v e , ω e are the driving and steering velocity inputs.

The control law for the evader is structurally the same of the pursuer's:

v e = -v (3
)

ω e = k (θ eva -θ e ). (4)
where 5 θ eva = n eva -π, and n eva is the unit vector representing the chosen direction for evasion. Note the following important points.

• The driving velocity of the evader is chosen to be equal in magnitude to that of the pursuer to consider a fair situation where neither robot has an advantage. However, its sign is opposite because the evader moves backwards in order to keep the pursuer in its field of view. The backward motion is the reason for the presence of a -π offset in the definition of θ eva . • The choice of n eva encodes the chosen evasion strategy.

In [START_REF] Cognetti | Real-time planning and execution of evasive motions for a humanoid robot[END_REF] we have discussed two possibilities, i.e., move back and move aside. In this paper we will consider only the second, which is more effective in confined spaces. With this strategy, the evader moves backwards so as to align with a direction that is orthogonal to the line-of-sight to the pursuer. This corresponds to setting n eva = n ⊥ aim , where n ⊥ aim is the normal unit vector to n aim in the half-plane behind the robot; equivalently, we have A possible modification of the orientation control law for the evader is

θ eva = θ aim -π/2. (5)
ω e = k sign(θ eva -θ e ). (6)
This would lead the evader to perform an evasion maneuver using the maximum possible curvature radius.

C. Simulations

The pursuit-evasion system with unicycles has been simulated in MATLAB. A typical result obtained using (1-2) for the pursuer (red) and [START_REF] Khansari-Zadeh | A dynamical system approach to realtime obstacle avoidance[END_REF][START_REF] De Luca | Integrated control for pHRI: Collision avoidance, detection, reaction and collaboration[END_REF] for the evader (blue) is shown in Fig. 2; the control parameters were chosen as v = 1 m/s, k = 0.5. The first snapshot shows the initial configuration of the two robots. In the second, the pursuer moves towards the evader, while the latter starts the evasion maneuver. The last two snapshots show the robots approaching and settling on a circular limit cycle, along which they travel at the same speed; note that their relative orientation is π/2 (a fact that can easily be proven analytically).

We have also simulated the case in which the evader robot is controlled using the saturated control (6); plots are not shown for brevity. We have found that the robots tend again to a circular limit cycle, whose radius is v/k. For the same values of v and k, this radius is always smaller than the radius of the limit cycle observed in the previous case. Also, the relative orientation between the two robots at steady-state is less than π/2.

An interesting generalization of the move aside evasion strategy is obtained by substituting π/2 in eq. ( 5) with a generic angle α ∈ [0, π/2]. With this choice, simulations run using the proportional control (2) for the evader show that the relative orientation of the two robots at steady-state becomes exactly α. Moreover, the radius monotonically increases as α is decreased, and tends to infinity when α approaches zero. Note that α = 0 corresponds to move back, which can then be seen as a limit case of this generalized evasion strategy.

The above observations suggest that the pursuit-evasion system with unicycles possesses strong asymptotic properties which should be further investigated.

III. PURSUIT-EVASION WITH HUMANOIDS

We now proceed to the problem at the center of this paper, i.e., pursuit-evasion with humanoids. The situation of interest is shown in Fig. 3. There are two humanoid robots, one of which acts as a pursuer and the other as an evader. The pursuer is always aware of the presence of the evader, and steers its course trying to intercept it. The evader detects the pursuer when this enters its safety area, triggering the execution of an evasive maneuver.

We shall make the same assumptions A1-A3 of the unicycle case. Since evasion is now a reaction to intrusions in the safety area, A2 must be reinforced by assuming that the evader can also measure the distance to the pursuer.

There is, however, a more fundamental difference: a pure feedback scheme cannot be used, because in humanoids it is necessary to address the problem of gait generation. The proposed solution is to adopt a replanning approach: each robot computes a motion plan in real time based on its current perception of the other, and updates this plan at a fast rate to adapt to new perceptions. At its core, the real-time planning procedure still uses a feedback-controlled unicycle for Cartesian trajectory generation.

A. Control schemes

The control schemes for the two robots, outlined in Fig. 4, are structurally the same, although their objectives are obviously different. As with unicycles, each robot performs computations in its own moving frame consisting of the sagittal and the coronal axes, and only uses local information made available by its sensory system. Fig. 4. The control schemes for the pursuer (above) and the evader (below), with the corresponding maneuver planning modules exploded (red box). The only difference between the two robots is that the pursuer tries to align with the line-of-sight to the evader, whose direction is n aim ; whereas the evader tries to align with direction neva, which is orthogonal to the line-of-sight to the pursuer (whose direction is -n aim ).

Let us look at the pursuer first. The pursuer detects the evader and measures the corresponding line-of-sight (i.e., the current direction of the evader relative to itself) represented in the following by the unit vector n aim . Based on this information, the robot plans in real time a pursuit maneuver, expressed in terms of a reference motion for its own Center of Mass (CoM). This is obtained through a sequential procedure: (1) a Cartesian pursuit trajectory is generated using a unicycle robot as a template model and an orientation control law aimed at aligning the robot with n aim (2) footsteps are placed around the pursuit trajectory (3) a stable trajectory for the CoM is generated accordingly. Once the CoM plan is ready, it is sent to a kinematic controller for computing appropriate joint motions.

The evader detects the pursuer and measures the corresponding line-of-sight, represented by -n aim . Based on this information, an evasion direction n eva is computed and an evasion maneuver is planned in real time, expressed as a reference motion for the robot CoM. This is done by following the same sequential procedure outlined above, with the only difference that the evasion trajectory is generated by a unicycle robot subject to an orientation control law aimed at aligning the robot with n eva . From this point on, the planning procedure of the evader is an exact replica of that of the pursuer.

In the following, we will describe in some depth the structure of the maneuver planning module for both the evader and the pursuer 6 . In conclusion of this section, we discuss when and how replanning is performed. 6 For brevity, we will not provide details on the structure of the detection and joint motion generation modules; in particular, the latter can use standard pseudoinverse-based kinematic control (see, e.g., [START_REF] Cognetti | Humanoid whole-body planning based on CoM movement primitives[END_REF])

B. Cartesian trajectory generation

For each humanoid, the Cartesian trajectory generation submodule computes a Cartesian reference trajectory using the controlled unicycle models of Sect. II as a template. To allow a unified treatment, we write the control laws (1-2) (pursuer) and (3-4) (evader) as follows

v = ± v (7) ω = k (θ * -θ). ( 8
)
The pursuer is obtained by taking the positive determination of v and θ * = θ aim ; while for the evader one should take the negative determination of v and θ * = θ eva . At the start of each maneuver planning phase, time is reset and the template unicycle is initialized at the origin of the current humanoid frame, with the same orientation; i.e., we let t ini = 0, x ini = y ini = 0 and θ ini = 0. To generate a trajectory in real time, we assume that the angular velocity ( 8) is computed at t ini = 0 (when the orientation error is θ * ini -θ ini = θ * ini ) and then kept constant for the whole planning horizon. Under this premise 7 , the unicycle equations can be easily integrated to obtain a closed-form expression for the Cartesian trajectory:

x(t) = ± v sin k θ * ini t k θ * ini (9) y(t) = ± v 1 -cos k θ * ini t k θ * ini (10) θ(t) = k θ * ini t (11)
for t ≤ t s and

x(t) = x(t s ) ± v(t -t s ) cos θ * ini (12) y(t) = y(t s ) ± v(t -t s ) sin θ * ini (13) θ(t) = θ * ini , (14)
for t > t s , with t s = 1/k. The Cartesian part of this trajectory consists of an arc of circle of radius v/k |θ * ini | (until t s , where the tangent to the arc has exactly the desired orientation θ * ini ), followed by a straight line.

C. Footstep generation

The footstep generation submodule generates a sequence of footsteps around the Cartesian trajectory. The idea is simply to use a constant stepsize ∆ along the trajectory itself. This is realized by sampling (9-10) using a constant time interval ∆t = ∆/v and displacing the samples alternatively to the right and to the left of the trajectory. The orientation of each of these footsteps is that of the tangent to the Cartesian trajectory at the sample point, and is given by the corresponding sample of [START_REF] Naveau | A reactive walking pattern generator based on nonlinear model predictive control[END_REF].

D. CoM trajectory generation

The CoM trajectory generation submodule computes a stable CoM trajectory for the humanoid robot. It receives in input the footstep sequence, from which a reference trajectory for the ZMP is generated by polynomial interpolation. Computation of a stable CoM trajectory associated to the ZMP reference is performed using the same LIP-based method described in [START_REF] Cognetti | Real-time planning and execution of evasive motions for a humanoid robot[END_REF]; see also [START_REF] Lanari | Boundedness issues in planning of locomotion trajectories for biped robots[END_REF] for further details.

Below, we quickly recall the computation of the sagittal coordinate x CoM of the CoM; equivalent formulas for the coronal motion can be easily obtained. Let η = g/z CoM , with z CoM the height of the CoM (assumed to be constant in the LIP model), and denote by x * ZMP the sagittal coordinate of the ZMP reference. We have

x CoM (t) = e -ηt x CoM (0) + x s (t) -e -ηt x u (0) + x u (t) 2 ,
where

x u (t) = η ∞ 0 e -ητ x * ZMP (t + τ )dτ x s (t) = η t 0 e -η(t-τ ) x * ZMP (τ )dτ.
The integrals in x u (t) and x s (t) can be easily computed for polynomial ZMP profiles, ultimately leading to a closed-form computation of x CoM (t).

E. Replanning

Once a robot has planned a (pursuit or evasion) maneuver based on its current perception of the other as explained above, it executes a short portion of it and then recomputes a new plan to adapt to new sensor information.

The maneuver planning procedure makes use of closedform expressions exclusively, and is therefore suitable for real-time implementation. In principle, then, we could perform replanning at the same rate at which visual data is updated. However, we have chosen to allow the robot to compute a new plan only upon completion of a step, and more precisely at the end of each double support phase. The rationale for this is to guarantee that the reference profile for the CoM is updated only when the robot has both feet on the ground, so as to avoid any destabilizing effect.

As soon as the new plan is available, it replaces the remaining part of the previous plan. In practice, this implies that the straight line part [START_REF] Cognetti | Real-time planning and execution of evasive motions for a humanoid robot[END_REF][START_REF] Chung | Search and pursuit-evasion in mobile robotics[END_REF] of the Cartesian trajectory is never actually traveled by a robot, at least as long as the line-of-sight to the other robot keeps changing.

IV. SIMULATIONS AND EXPERIMENTS

The proposed approach was validated using two NAO humanoids. One of them, acting as evader, has a depth camera (ASUS Xtion) mounted on its head. This camera provides also the distance to the closest obstacle, making it possible to detect intrusions into the safety area. The pursuer does not need a measurement of the distance to the evader, and therefore only uses the built-in monocular camera.

For simulations, we have used the V-REP environment. The evader safety area is assumed to have a radius of 0.8 m. Cartesian trajectories for the pursuer and the evader are generated as explained in Sect. III-B, with v = 0.1 m/s and k = 0.2. Footsteps are distributed around these trajectories using ∆ = 0.04 m, a value consistent with the NAO gait capabilities. A ZMP trajectory is computed from the footsteps using single and double support durations of 0.122 s and 0.425 s, respectively. The value of z CoM used for CoM trajectory generation is 0.268 m.

A typical simulation is summarized in Fig. 5 (see the accompanying video for a clip), where each frame contains a side view and a top view for a given time instant. In spite of the adaptations needed for the humanoid case, the results fully confirm the pursuit-evasion behavior observed for the unicycle case: the two robots converge to a circular limit cycle, along which they travel at the same speed with a relative orientation of π/2.

For the experiments, the various control parameters have been set to exactly the same values of the simulations. In spite of the rather limited processing capabilities (each NAO is equipped with an Intel Atom running at 1.6 GHz) we were able to perform all computations on-board; in particular, each call to the maneuver planning module takes less than 10 ms.

Figure 6 shows snapshots taken during an experiment (see the accompanying video for a clip). The expected limit cycle behavior is observed again, although its radius is slightly reduced with respect to the simulation. This is mainly due to the fact that the actual robot speed is less than 0.1 m/s due to significant feet slippage on the smooth floor.

V. CONCLUSIONS

We have considered a pursuit-evasion problem between humanoids. This is an evolution of the setting considered in our previous work [START_REF] Cognetti | Real-time planning and execution of evasive motions for a humanoid robot[END_REF], where a humanoid had to avoid an incoming intruder which was initially headed for collision but did not alter its course to pursue the evader. We have designed control schemes for both the pursuer and the evader. They are structurally identical, although the objectives are different: the pursuer tries to align its direction of motion with the line-of-sight to the evader, whereas the evader tries to move in a direction orthogonal to the line-ofsight to the pursuer.

At the core of the control scheme is a maneuver planning module that implements a sequential procedure. From the desired direction of motion, a corresponding Cartesian trajectory is generated, around which footsteps are placed; from these, a stable trajectory for the humanoid CoM is computed. The whole planning procedure makes use of closed-form expressions, thus making real-time implementation possible, and is repeated upon completion of each step to account for the motion of the other robot.

An interesting outcome of our study is that the pursuer and the evader converge to a circular limit cycle along which they travel at the same speed. This property has been first observed on unicycles, which have been used as template models for Cartesian trajectory generation, and then fully confirmed on NAO humanoids, both in simulations and experiments.

Future work will address several points, among which:

• asymptotic properties of pursuit-evasion with unicycles;

• design and validation of more sophisticated evasion strategies; • how to perform evasion maneuvers in the presence of obstacles in the workspace; • the use of MPC to compute robust, stable trajectories for the robot CoMs [START_REF] Scianca | Intrinsically stable MPC for humanoid gait generation[END_REF].

Fig. 1 .

 1 Fig. 1. Pursuit-evasion with unicycles: geometry of the problem

Fig. 2 .

 2 Fig. 2. Pursuit-evasion with unicycles: simulation under control (1-2) for the pursuer (red) and (3-4) for the evader (blue). Axis ticks are 0.5 m apart.

Fig. 3 .

 3 Fig. 3. Pursuit-Evasion with humanoids. The pursuer enters the safety area of the evader and heads towards it. The latter must plan and execute a fast evasive motion. Each robot must continuously replan its motion on the basis of the other's. Note the moving frame associated to each humanoid.

Fig. 5 .

 5 Fig. 5. Pursuit-evasion with humanoids: snapshots from a simulation. The trajectories of the CoMs are shown in red (pursuer) and blue (evader).

Fig. 6 .

 6 Fig. 6. Pursuit-evasion with humanoids: snapshots from an experiment.

The main rationale for this choice is that biomechanical studies (see, e.g.,[START_REF] Mombaur | From human to humanoid locomotion -an inverse optimal control approach[END_REF]) have shown that the human sagittal axis is almost invariably tangent to the Cartesian path during fast locomotion. The consequence of this approach, which we already adopted successfully in[START_REF] Cognetti | Real-time planning and execution of evasive motions for a humanoid robot[END_REF],[START_REF] Faragasso | Vision-based corridor navigation for humanoid robots[END_REF], is that the generated humanoid gaits will not include lateral steps.

Although the direction of the two lines-of-sight is the same, each robot will obviously obtain and express the corresponding measurement in its own moving frame.

This control law is inspired to the Cartesian regulator described in[START_REF] Siciliano | Robotics. Springer[END_REF] Sect. 11.6.2]. The main difference is that here we want to track a moving target (the evader) while the Cartesian regulator aimed at reaching a fixed point. For this reason, the driving velocity in eq. (1) is constant rather than modulated by the distance to the target.

Do not confuse θe, the orientation of the evader, with θeva, the orientation associated to the evasion direction.

Since we are operating in a fast replanning framework, this is an acceptable assumption.