Samuel Martin

Irinel-Constantin Morȃrescu

Dragan Nešić

New cut-balance conditions in networks of clusters

Keywords: Multiagent systems, consensus, structured networks

Existing results in the literature guarantee that the state of multi-agent systems interacting over networks that satisfy the cut-balance assumption asymptotically converges to a constant vector. Furthermore, when the network is persistently connected the agents reach a common value called consensus. Many real large-scale networks are obtained by sparsely connecting subnetworks of densely connected agents. In this context, our objective is to provide new cut-balance assumptions that are adapted to networks of clusters. They are useful for consensus and agreement in clusters in situations when network topology is such that clusters are given or can be easily identified. In this case our new cut-balance assumptions can be checked by realizing a smaller number of operations.

Introduction

The multi-agent framework is widely used to model the dynamics of large numbers of interconnected systems. The most studied problem in this context is the consensus or synchronization of all agents in the network. The convergence to consensus is typically characterized by conditions that depend on the communication graph between agents. Basic results concern fixed undirected topologies but notable advances towards directed and time varying topologies have been provided in [START_REF] Jadbabaie | Coordination of groups of mobile autonomous agents using nearest neighbor rules[END_REF][START_REF] Moreau | Stability of multiagent systems with time-dependent communication links[END_REF][START_REF] Ren | Consensus seeking in multiagent systems under dynamically changing interaction topologies[END_REF][START_REF] Hendrickx | Convergence of typesymmetric and cut-balanced consensus seeking systems[END_REF] for discrete time dynamics and [START_REF] Olfati-Saber | Consensus problems in networks of agents with switching topology and time-delays[END_REF][START_REF] Ren | Consensus seeking in multiagent systems under dynamically changing interaction topologies[END_REF][START_REF] Hendrickx | Convergence of typesymmetric and cut-balanced consensus seeking systems[END_REF][START_REF] Martin | Continuous-time consensus under persistent connectivity and slow divergence of reciprocal interaction weights[END_REF][START_REF] Martin | Continuous-time consensus under non-instantaneous reciprocity[END_REF] for continuous time algorithms. In [START_REF] Hendrickx | Convergence of typesymmetric and cut-balanced consensus seeking systems[END_REF], the authors introduced the assumption of cut-balance communication which is a general form of communication reciprocity among the agents. Under the cut-balance assumption, convergence is ensured, and consensus may occur in groups or globally. The cut-balance assumption was extended in [START_REF] Martin | Continuous-time consensus under persistent connectivity and slow divergence of reciprocal interaction weights[END_REF] where This paper was not presented at any IFAC meeting. Corresponding author I.-C. Morȃrescu. This work was supported by the ANR project COMPACS-"Computation Aware Control Systems", ANR-13-BS03-004 and by the Australian Research Council under the Discovery Project DP1094326.

Email addresses: samuel.martin@univ-lorraine.fr (Samuel Martin), constantin.morarescu@univ-lorraine.fr (Irinel-Constantin Morȃrescu), dnesic@unimelb.edu.au (Dragan Nešić).

the authors also provided a convergence rate when global consensus takes place. One drawback of the cut-balance assumption is that it is a global assumption which may be hard to verify when not ensured by design. A direction to search for a local assumption is to split the agents into clusters. It is reported in the literature that large scale networks often consist of sparsely interconnected clusters of densely coupled agents [START_REF] Chow | Time scale modeling of sparse dynamic networks[END_REF][START_REF] Bıyık | Area aggregation and time-scale modeling for sparse nonlinear networks[END_REF][START_REF] Morȃrescu | Coordination in networks of linear impulsive agents[END_REF]. Different algorithms have been developed to detect the clusters in such networks [START_REF] Newman | Finding and evaluating community structure in networks[END_REF][START_REF] Blondel | Fast unfolding of communites in large networks[END_REF][START_REF] Morȃrescu | Opinion dynamics with decaying confidence: Application to community detection in graphs[END_REF]. In the sequel we take advantage of the partition of network in clusters to state new conditions for consensus. Consequently, the contribution of the present study is that, under stronger assumptions on the interaction graph, we provide a new assumption on reciprocity of communication which can be verified in a local manner. Therefore, we provide conditions for consensus that can be checked by performing a reduced number of operations. Notation. The following notation will be used throughout the paper. The set of nonnegative integers, real and nonnegative real numbers are denoted by N, R and R + , respectively. A non trivial subset S of a set C, denoted as S C, is a non-empty set with S C.

Problem formulation

Let N {1, . . . , n} be a set of n agents. By abuse of notation we denote both the agent and its index by the same symbol i ∈ N . Each agent is characterized by a scalar state x i ∈ Preprint submitted to Automatica 2 November 2016 R, ∀i ∈ N that evolves according to the following model

ẋi (t) = n j=1 a ij (t)(x j (t) -x i (t)), ∀i ∈ N (1)
where a ij (t) ≥ 0 are measurable functions of time representing the communication weights/interaction strength. Let x(t) = (x 1 (t), . . . , x n (t)) ∈ R n be the overall state of the network collecting the states of all the agents. It is noteworthy that x(t), t ∈ R + is uniquely defined by an initial state x(0) and dynamics (1). Indeed, there exists a unique differentiable function of time x : R + → R n whose components satisfy equation ( 1) for all t ∈ R + . We call it the trajectory of the overall system. We say the trajectory asymptotically reaches a consensus when there exists a common agreement value α ∈ R such that

lim t→+∞ x i (t) = α, ∀i ∈ N .
In the sequel, agents are assumed to be partitioned in m nonempty clusters: C 1 , C 2 , . . . , C m ⊂ N , that are assumed to be given or can be easily identified. For instance clusters may correspond to groups of agents which are spatially close while different clusters are spatially distant. Let us introduce the following supplementary notation: M {1, . . . , m} and n i denotes the cardinality of cluster C i . Without loss of generality, we permute the agents' labels according to the cluster partition so that when j ∈ C i and j ∈ C i+1 , j < j .

Definition 1 A directed path of length p in a given di- rected graph G = (V, F) is a union of directed edges p k=1 (i k , j k ) such that i k+1 = j k , ∀k ∈ {1, . . . , p -1}.
The node j is connected with node i in a directed graph G = (V, F) if there exists at least a directed path in G from i to j (i.e. i 1 = i and j p = j).

For two subsets of nodes A, B ⊂ N , the sum of communication weights from B to A is denoted as

w A ← B (t) = i∈A,j∈B a ij (t).
The cut-balance assumption in [START_REF] Hendrickx | Convergence of typesymmetric and cut-balanced consensus seeking systems[END_REF]) can be formulated as follows.

Hypothesis 1 There exists a constant K ≥ 1 such that for all non trivial subsets S N

w S ← (N \S) (t) ≤ K • w (N \S) ← S (t), ∀t ≥ 0.
(2)

This basically means that if a group of agents influences the remaining ones, the former group is also influenced by the remaining ones by at least a proportional amount. A comparison between the cut-balance condition and other types of communication such as existence of a spanning tree has been carried out in [START_REF] Hendrickx | Convergence of typesymmetric and cut-balanced consensus seeking systems[END_REF][START_REF] Martin | Continuous-time consensus under persistent connectivity and slow divergence of reciprocal interaction weights[END_REF]. Let us recall here the first part of Theorem 1 in [START_REF] Hendrickx | Convergence of typesymmetric and cut-balanced consensus seeking systems[END_REF]. First, we define the graph of persistent communication.

Definition 2 A persistent edge associated with system (1) is a couple (j, i) ∈ N × N such that ∞ 0 a ij (t)dt = +∞. The graph of persistent communication associated to system (1) is the graph G = (N , E) gathering all agents and including only the persistent edges, i.e.,

E = {(j, i) ∈ N × N | ∞ 0 a ij (t)dt = +∞}.
Theorem 1 Suppose that Hypothesis 1 is satisfied for all time t ≥ 0. Then, the trajectory of system (1) converges. Then, there is a directed path from i to j in the graph of persistent communication G if and only if there is also a directed path from j to i, and there holds in that case lim t→∞ x i (t) = lim t→∞ x j (t).

Notice that Hypothesis 1 is a global assumption which may be hard to verify when not ensured by design. The objective of this work is to propose new assumptions that can be verified locally and provides similar guaranties for the particular case of graphs partitioned in clusters. Let us introduce here the main hypotheses of this work.

Assumption 1 (Intra-cluster reciprocity) There exists a constant K I ≥ 1 such that for any cluster k ∈ M and for all non trivial subsets S C k ,

w S ← (C k \S) (t) ≤ K I • w (C k \S) ← S (t), ∀t ≥ 0.
Assumption 2 (Inter-cluster reciprocity) There exists a constant K E ≥ 1 such that for all non trivial subset S M,

k∈S w C k ← (N \C k ) (t) ≤ K E • k∈S w (N \C k ) ← C k (t), ∀t ≥ 0.
Assumptions 1 and 2 correspond to Hypothesis 1 within each cluster and between clusters, respectively. In Assumption 2 the equivalent cut-balance assumption is formulated in the case where each cluster is considered as a node and the communication between clusters is weighted by the sum of agent-wise communication weights. It is necessary that K I ≥ 1 and K E ≥ 1 and the equality corresponds to symmetric communications. The next assumption ensures that the total communication weight which a cluster C k receives cannot exceed a proportion of the weight received by any non trivial subset of C k from the rest of C k .

Assumption 3 (Clustered communication)

There exists a constant ρ > 0 such that for each cluster k ∈ {1, . . . , m} and for all non trivial subsets S C k ,

w C k ← (N \C k ) (t) ≤ ρ • w S ← (C k \S) (t), ∀t ≥ 0.
Remark 1 The purpose of Assumption 3 is to prevent cases where two subsets of a cluster are more connected to the outside than to each other. To understand the importance of Assumption 3, we have the two following facts :

• Assumption 3 is not necessarily satisfied when Assumptions 1 and 2 hold. • Assumptions 1 and 2 without Assumption 3 are not sufficient to obtain the global cut-balance Hypothesis 1.

A counter-example illustrated by Figure 1 allows to prove these facts : consider the 4-agent system with communications described by a 12 (t) = a 21 (t) = a 34 (t) = a 43 (t) = 1 and a 13 (t) = a 42 (t) = t. All these weights form persistent edges. The other weights are assumed to be uniformly 0. The only non-trivial partition in clusters satisfying Assumptions 1 and 2 is C 1 = {1, 2} and C 2 = {3, 4} with K I = 1 = K E . For this partition, Assumption 3 clearly fails for instance taking S = {1}. Moreover, the global cut-balance Hypothesis 1 also fails for instance taking S := {1, 2, 4} (see Figure 1 for an illustration). The relation (2) in Hypothesis 1 holds only if K ≥ t, ∀t ≥ 0 i.e., K = ∞, which is not feasible.

Asymptotic behavior: Consensus and Clustering

In this section, we suppose that we deal with a network partitioned in clusters satisfying the communication pattern introduced by Assumptions 1, 2 and 3. Our main result can be stated as follows.

Proposition 1 Under Assumptions 1, 2 and 3, the communication weights satisfy Hypothesis 1 with reciprocity constant K = (K I + ρ + K E max(ρ, 1)).

Notice that the global cut-balance Hypothesis 1 does not guarantee the existance of a non-trivial partition into clusters for which Assumptions 1, 2 and 3 are all satisfied. For a counter-example, consider the 3-node unidirectional circle graph with constant weights such that a 12 (t) = a 23 (t) = a 31 (t) = 1 and the other weights are uniformly 0. The global cut-balanced condition is satisfied but no non-trivial partition into clusters satisfies Assumption 1.

PROOF. Let S be some non trivial subset of N . Denote, for k ∈ {1, . . . , m}, S k = S ∩ C k . Set S k may either be empty, equal to C k or a non trivial subset of C k . We introduce

E ∅ = {k ∈ {1, . . . , m} | S k = ∅}, E eq = {k ∈ {1, . . . , m} | S k = C k }, E = {k ∈ {1, . . . , m} | S k C k }.
We have

w S ← (N \S) (t) = m k=1 w S k ← (N \S) (t) = k∈Eeq w S k ← (N \S) (t) + m k∈E w S k ← (N \S) (t).
Denote W eq (t) and W (t) the terms in the right-hand side above. First, quantity W (t) can be rewritten as

W (t) = k∈E w S k ← (C k \S k ) (t) + k∈E w S k ← N \(C k ∪S) (t).
Set S k being non-empty, the first term can be upper bounded using Assumption 1. Set (C k \ S k ) being non-empty either, the second term can be upper bounded using Assumption 3. This yields

W (t) ≤ k∈E K I w (C k \S k ) ← S k (t) + k∈E ρw (C k \S k ) ← S k (t) = (K I + ρ) k∈E w (C k \S k ) ← S k (t).
Secondly, using the definition of E eq we rewrite the quantity W eq as

W eq (t) = k∈Eeq w C k ← (N \S) (t) ≤ k∈Eeq h∈M\Eeq w C k ← C h (t),
where the last inequality comes from (N \ S) ⊆ N \ ∪ k∈Eeq C k , so that Assumption 2 applies and gives

W eq (t) ≤ K E h∈M\Eeq k∈Eeq w C h ← C k (t) ≤ K E   h∈E ∅ k∈Eeq w C h ← C k (t) + h∈E k∈Eeq w C h ← C k (t)   .
The first term in the bracket can be bounded by h∈E ∅ w C h ← S and for the second term we use E ∩ E eq = ∅ to get,

h∈E k∈Eeq w C h ← C k (t) ≤ h∈E w C k ← (N \C h ) (t). Since for k ∈ E , (C k \ S k ) is a non trivial subset of C k , we apply Assumption 3 to obtain h∈E k∈Eeq w C h ← C k (t) ≤ ρ h∈E w (C h \S h ) ← S h (t) ≤ ρ h∈E w (C h \S h ) ← S (t).
Consequently,

W eq (t) ≤ K E max(ρ, 1) k∈E ∪E ∅ w (C k \S k ) ← S (t). Since w S ← (N \S) (t) = W (t) + W eq (t), it holds w S ← (N \S) (t) ≤ (K I + ρ + K E max(ρ, 1))w (N \S) ← S (t).
In the cases where the clusters are already given, checking Proposition 1 requires a smaller number of operations. Precisely, in the general case, the cut-balance assumption requires to loop over 2 n sets S and for each S to sum over O(n 2 ) terms. On the other hand Assumptions 1 and 3 require at most max k∈{1,...,m} n k 2 n k such sets with a sum over O(n 2 k ) terms and Assumption 2 requires a loop over 2 m sets and sum over O(m 2 ) terms. From Theorem 1, we have the following corollary.

Corollary 1 Suppose that Assumptions 1, 2 and 3 are satisfied. Then, the trajectory of system (1) converges. Let G = (N , E) be the graph of persistent communication (see Definition 2). Then,

• there is a directed path from i to j in G if and only if there is also a directed path from j to i, and there holds in that case lim t→∞ x i (t) = lim t→∞ x j (t),

• if a persistent edge exists between two clusters C k , C h , k = h ∈ M, then lim t→∞ x i (t) = lim t→∞ x j (t), ∀i, j ∈ C k ∪ C h .
PROOF. The first item of the corollary is implied by Theorem 1 and Proposition 1. For the second, notice that if there exists a persistent edge (j, i) linking two clusters i.e., with i ∈ C k , j ∈ C h and k = h, Assumption 3 implies that the persistent edges internal to cluster C k form a strongly connected graph, and by the reciprocity Assumption 2, there also exist persistent edges from cluster C k to C h , so that the persistent edges internal to cluster C h also form a strongly connected graph. As a conclusion, all pairs of nodes in C k ∪ C h are linked by a path of persistent edges and the first bullet point applies.

When any two agents belonging to a cluster C k , k ∈ M are connected by a persistent directed path, the first item of Corollary 1 guarantees that a local agreement is reached in C k . If the local agreements α k , α h ∈ R are reached in clusters C k , C h , k = h ∈ M, respectively, and a persistent link exists between the two clusters, the second item of Corollary 1 implies α k = α h . In other words we provide a flexible characterization of the asymptotic behavior describing agreement in: clusters, groups of clusters or overall network.

Conclusion

In this note we investigated consensus in network structured in clusters. Our main assumptions guaranteeing consensus in this framework are adaptations of the global cut-balance assumption. We believe that the conditions we propose are better adapted to the clustered communications case because they are local and consequently their verification requires a smaller number of operations.

Fig. 1 .

 1 Fig. 1. Illustration of the importance of Assumption 3. Continuous blue and red lines represents the clusters C1 and C2 as in Remark 1. Bold unidirectional arrows correspond to the stronger communication weights with value t while dashed bidirectional arrows correspond to the weaker communcation weights with value 1. The dotted-dashed green line corresponds to a particular set S which makes the cut-balance Hypothesis 1 fail.


S ¸erban Sabȃu

Irinel-Constantin Morȃrescu
email: constantin.morarescu@univ-lorraine.fr

Lucian Bus
email: lucian@busoniu.net

Ali Jadbabaie
email: jadbabai@mit.edu.

Decoupled-Dynamics Distributed Control for Strings of Nonlinear Autonomous Agents

We introduce a novel distributed control architecture for a class of nonlinear dynamical agents moving in the "string" formation, while guaranteeing trajectory tracking and collision avoidance. Each autonomous agent uses information and relative measurements only with respect to its predecessor in the string. The performance of the scheme is entirely scalable with respect to the number of agents in formation. The scalability is a consequence of the "decoupling" of a certain bounded approximation of the closed-loop equations, entailing that individual, local analyses of the closed-loops stability at each agent will in turn guarantee the aggregated stability of the entire formation. An efficient, practical method for compensating communications induced delays is also presented.

I. INTRODUCTION

The distributed control of autonomous agents moving in the "string" (or "line") formation, also know as platooning is a fifty years old problem, going back to the work [START_REF] Levine | On the Optimal Error Regulation of a String of Moving Vehicles[END_REF] of Levine & Athans on intelligent highway systems. Since no existing control solution was deemed satisfactory from an applications standpoint, consistent research efforts are still being invested for developing practical platooning control schemes. The difficulty of the problem stems from the notorious lack of scalability of networks of dynamical agents, which causes the performance of existing control schemes to depend not only on the number of vehicles in formation but on the vehicle's position in formation, as well [START_REF] Middleton | String Stability in Classes of Linear Time Invariant Formation Control with Limited Communication Range[END_REF]. Platooning may also be seen as a particular instance of flocking for multi-agent systems. The flocking problem has been intensively studied in the last decade for agents with linear [START_REF] Tanner | Stable Flocking of mobile agents, part I: fixed topology[END_REF], [START_REF] Tanner | Stable Flocking of mobile agents, part II: dynamic topology[END_REF], [START_REF] Olfati-Saber | Flocking for Multi-Agent Dynamic Systems: Algorithms and Theory[END_REF], [START_REF] Martin | Multi-agent flocking under general communication rule[END_REF] or nonlinear [START_REF] Zhou | Flocking of multi-agent dynamical systems based on pseudo-leader mechanism[END_REF], [START_REF] Su | Adaptive secondorder consensus of networked mobile agents with nonlinear dynamics[END_REF] dynamics. Generally speaking, two important features characterize the flocking behavior of autonomous agents: cohesion of the formation and collision avoidance. In multi-agent systems they are implemented as connectivity/topology preservation [START_REF] Bullo | Distributed Control of Robotic Networks[END_REF], [START_REF] Zavlanos | Distributed connectivity control of mobile networks[END_REF], [START_REF] Fiacchini | Convex conditions on decentralized control for graph topology preservation[END_REF], [START_REF] Bus ¸oniu | Topology-preserving flocking of nonlinear agents using optimistic planning[END_REF] and collision avoidance [START_REF] Tanner | Stable Flocking of mobile agents, part I: fixed topology[END_REF], [START_REF] Tanner | Stable Flocking of mobile agents, part II: dynamic topology[END_REF], [START_REF] Zhou | Flocking of multi-agent dynamical systems based on pseudo-leader mechanism[END_REF], respectively.

Just as for platooning applications (and more generally, in distance based formation control) the regulated measures are the relative (interspacing) distances between consecutive agents, for several other meaningful applications in networks of dynamical agents, the regulated signals in trajectory tracking or synchronization problems represent relative measurements such as relative velocities (with respect to neighboring agents), local clocks offsets or phase differences between (neighboring) coupled oscillators. In this paper, we present preliminary results on a class of novel distributed control policies where the relative measurements (with respect to the neighboring agents) are used by the local sub-controllers in conjunction with the knowledge of the control actions of the sub-controllers at the neighboring agents. It turns out that the performance of the resulted distributed control schemes considerably outperforms the distributed architectures based solely on relative measurements.

The problem considered in this paper can be rephrased as a multi-agent flocking problem with collision avoidance. The literature on this topic is very rich and considers both directed or undirected, fixed or time-varying interconnection graphs. The objective of the control scheme is to achieve the synchronization of the trajectories of all agents in the formation with the trajectory of the leader agent. Such trajectory tracking must be achieved while ensuring zero (steady-state) errors of the regulated measures (in our case the relative speed between two consecutive agents) and while avoiding collisions, i.e. performing the needed longitudinal steering (brake/throttle) maneuvers that guarantee the avoidance of collision with the preceding vehicle.

A. Contributions of this Paper

The approach taken here is based on the use of Artificial Potential Functions [START_REF] Tanner | Stable Flocking of mobile agents, part I: fixed topology[END_REF], [START_REF] Zhou | Flocking of multi-agent dynamical systems based on pseudo-leader mechanism[END_REF].When compared to the state-ofthe-art, our results represent a consistent extension of existing methods [START_REF] Tanner | Stable Flocking of mobile agents, part I: fixed topology[END_REF], [START_REF] Zhou | Flocking of multi-agent dynamical systems based on pseudo-leader mechanism[END_REF], from at least three perspectives. Firstly, it guarantees stability, velocity matching (trajectory tracking) and collision avoidance even for directed topologies, as illustrated by the distributed control scheme reported here. Secondly, it achieves complete scalability with respect to the number of agents in formation [START_REF] Zhou | Flocking of multi-agent dynamical systems based on pseudo-leader mechanism[END_REF] and also with respect to the connectivity of the inter-agents communications graph. Finally, a practical adaptation of the distributed controller is able to completely compensate the wireless communications induced time delays.

By comparison, the main result in [START_REF] Zhou | Flocking of multi-agent dynamical systems based on pseudo-leader mechanism[END_REF] imposes that all the minor matrices of the weighted Laplacian matrix associated with the interconnection graph are positive definite and lower bounded by a certain constant. This basically requires the maximization of the eigenvalues of the weighted Laplacian matrix, which can be interpreted as the maximization of the number of interconnections in the underlined graph (see [START_REF] Godsil | Algebraic Graph Theory[END_REF]) together with the maximization of its diagonal elements (see Geršgorin disk theorem [START_REF] Horn | Matrix Analysis[END_REF]). It is worth noting that the first requirement involves the transmission of the exact state of the leader to many agents in the formation, while the second requirement represents high local control gains.

The most interesting feature of our proposed scheme is the fact that it achieves complete scalability with respect to the number of vehicles in the string. Such scalability features come as a consequence of the complete "decoupling" of a certain bounded approximation of the closed-loop equations, such that by performing solely individual, local analyses of the stability at each agent, will in turn guarantee the stability of the aggregated formation.

B. Paper Organization

The paper is organized as follows: in Section II we introduce the general framework and we formulate the platooning control problem. Section III provides a preliminary description of the novel distributed control architecture introduced in this work along with a first glimpse at the closed-loop dynamics "decoupling" featured by the control scheme. Section IV contains the main result as it delineates the guarantees for stability, velocity matching and collision avoidance. Finally, Section V outlines a practical delays compensation mechanism while Section VI provides an illustrative numerical example, worked out on a simplified dynamical model for road vehicles.

II. GENERAL FRAMEWORK AND PROBLEM STATEMENT A. Preliminaries

Definition 2.1: The σ-norm of a vector x is defined as

x σ def = 1 σ 1 + x 2 2 -1 (1)
with σ is a positive constant. This is a class K ∞ function of x 2 2 and is differentiable everywhere. Definition 2.2: A set Ω is said to be forward invariant with respect to an equation, if any solution x(t) of the equation satisfies:

x(0) ∈ Ω =⇒ x(t) ∈ Ω, ∀t > 0.
Definition 2.3: Artificial Potential Function (APF). The function V k,k-1 (•) is a differentiable, nonnegative, radially unbounded function of z σ satisfying the following properties:

(i) V k,k-1 ( z σ ) → ∞ as ( z σ ) → 0, (ii) V k,k-1 ( z σ
) has a unique minimum, which is attained at z σ = δ k , with δ k being a positive constant.

B. The Problem: Trajectory Tracking of the String Formation

We consider a homogeneous group of n agents (e.g. autonomous road vehicles) moving along the same (positive) direction of a roadway, with the origin at the starting point of the leader. The dynamical model for the agents, relating the control signal u k (t) of the k-th vehicle to its position y k (t) on the roadway, is given by

ẏk (t) = v k (t), vk (t) = f (v k (t)) + u k (t) ; (2a) y k (0) = - k j=0 j , v k (0) = 0. (2b)
where v k (t) is the instantaneous speed of the k-th agent, u k (t) is its command signal and k is the initial interspacing distance between the k-th agent and its predecessor in the string. Throughout the sequel we will use the notation

y k = G k u k (3)
to denote (especially for the graphical representations) the input-output operator G k of the dynamical system from (2a), with the initial conditions (2b). Assumption 2.4: The index "0" is reserved for the leader vehicle, the first vehicle in the string, for which we assume that there is no controller on board and consequently the command signal u 0 (t) will represent a reference signal for the entire formation.

In the rest of the paper we often forget the time argument of the involved variables. It is worth noting that when the argument is missing it has to be thought as t. Let us further define

z k def = y k-1 -y k , z v k def = v k-1 -v k for 1 ≤ k ≤ n, (4)
to be the interspacing and relative velocity error signals respectively (with respect to the predecessor in the string). By differentiating the first equation in ( 4) it follows that żk (t) = z v k (t), therefore implying that constant interspacing errors (in steady state) are equivalent with zero relative velocity errors and also allowing to write the following time evolution for the relative velocity error of the k-th vehicle

żv k = f (v k-1 ) -f (v k ) + u k-1 -u k .
(5)

III. A NOVEL DISTRIBUTED CONTROL ARCHITECTURE

The inherent difficulty in platooning control is rooted in the nested nature of the interdependencies between the regulated signals. Specifically, the regulated errors (e.g. interspacing errors or relative velocity errors) at the k-th agent depend on the regulated errors of its predecessor (the (k-1)th agent) and so on, such that by a recursive argumentgoing through all the predecessors of the k-th agent -they ultimately depend on the trajectory of the leader vehicle, which represents the reference for the entire formation.

We introduce a novel control architecture featuring a certain beneficial "decoupling" properties of the closed-loop dynamics that avoid the pitfalls of the aforementioned nested interdependencies. The distributed control policies rely only on information locally available to each vehicle. For the scope of this paper, we consider non-linear controllers built on the so-called Artificial Potential Functions (APF), in particular we will look at control laws of the type Definition 7] with β k being a proportional gain to be designed for supplemental performance requirements. With the notation from (4), the control policy (6) for the k-th vehicle becomes

u k = u k-1 +β k (v k-1 -v k )-∇ y k V k,k-1 ( y k-1 -y k σ ) (6) with k ≥ 1, where each of the V k,k-1 (•) functions is an Artificial Potential Function [2,
u k = u k-1 + β k z v k -∇ y k V k,k-1 ( z k σ ) (7)
and it can further be written as the sum of the following two components: firstly, the control signal u k-1 of the preceding vehicle, which is received onboard the k-th vehicle via wireless communications (e.g. digital radio). Secondly, the local component, which we denote with

u k def = β k z v k -∇ y k V k,k-1 ( z k σ ) (8)
and which is based on the measurements (4) which are locally available to the k-th vehicle, as they can be acquired via onboard LIDAR sensors. Thus, the k-th control law reads:

u k = u k-1 + u k .
The control policy (6) entails a highly beneficial "decoupling" feature of the closed-loop dynamics at each agent, as we simply illustrate next. Firstly, note that by plugging ( 6) into ( 5) we obtain the following closed-loop error equations at the k-th agent:

żv k = f (v k-1 ) -f (v k ) -β k z v k + ∇ y k V k,k-1 ( z k σ ). (9)
The following result will be instrumental in the sequel. Consider the following Lyapunov candidate functions:

L k z k (t), z v k (t) def = 1 2 V k,k-1 ( z k (t) σ )+ +z v k (t)z v k (t) , with 1 ≤ k ≤ n. (10)
Lemma 3.1: The differential of the Lyapunov candidate function L k (•, •) introduced in (10) along the trajectories of (2) and ( 6) is given by

d dt L k (z k (t), z v k (t)) = z v k (t) f v k-1 (t) -f v k (t) -β k z v k (t)z v k (t) , (11)
and does not depend on the choice of the APFs V k,k-1 (•).

IV. DECOUPLING CONTROL DESIGN

As we will show in this section, in the proposed method the control actions of each agent are based exclusively on receiving information from its predecessor. While the control gains are strictly related to the reactivity of the system (i.e. faster systems needs higher controller gains) our scheme does not require making the leader's information (instantaneous speed or acceleration) available to other agents in the string (the virtual leaders from [START_REF] Zhou | Flocking of multi-agent dynamical systems based on pseudo-leader mechanism[END_REF]). Our directed communications scheme, necessitates a minimal information exchange and sensing radius for all agents (each agent performs measurements and receives information only with respect to its predecessor).

The following result is the main result of this Section, as it delineates a "decoupling" property of the closed-loop dynamics, achieved by the (6) type control policy along with velocity matching and collision avoidance. Due to space limitations we do not provide proofs in this paper. [START_REF] Martin | Multi-agent flocking under general communication rule[END_REF] then for all type (6) control laws with that β k > α the following hold: (A) Given the Lyapunov function L k introduced in (10), local to the k-th agent, the sub-level sets

(v 2 -v 1 ) f (v 2 ) -f (v 1 ) ≤ α v 2 -v 1 2 2 , ∀ v 1 , v 2
Ω k c def = {(z k , z v k )|L k ≤ c,
= 2L k (z k (0), z v k (0)) there exists η c such that y k -y k-1 2 > η c , ∀t ≥ 0.
Therefore, a pre-specified safety distance can be imposed by the initial conditions. Proposition 4.2: Given L k (•, •) as introduced in (10), the string formation's steady-state configuration is attained at the minimum of the following formation-level Lyapunov function:

L(z(t), z v (t)) def = 1 2 n k=1 L k (z k (t), z v k (t)) (13)
which coincides component-wise with the minima of the Lyapunov functions [START_REF] Godsil | Algebraic Graph Theory[END_REF] local to the k-th agent. Furthermore, the level sets of L given by Ω c def = {(z, z v )|L ≤ c, with c > 0} are compact and they represent forward invariant sets for the closed-loop dynamics of the entire formation, as given in (2) and ( 6) with 1 ≤ k ≤ n. Consequently, velocity matching and vehicles' collision avoidance are achieved, without the need for inserting exact leader information in the formation (the "virtual leaders" from [START_REF] Zhou | Flocking of multi-agent dynamical systems based on pseudo-leader mechanism[END_REF]) while maintaining a safe interspacing distance.

V. DELAY COMPENSATION MECHANISM

The difficulties caused for networked systems by the communications induced delays and time jittering have been a topic of intensive study for decades. For platooning practical applications it has been argued in [START_REF] Peters | Leader tracking in homogeneous vehicle platoons with broadcast delays[END_REF] that the (low latency) time delays induced by the wireless communications, even if assumed time-invariant and homogeneous1 , irremediably alter the performance of the control scheme. The cause of this this phenomenon is the well understood fact that the delays propagate through the closed-loops towards the back of the platoon and furthermore they accumulate in a manner depending on the number of vehicles in formation, ultimately leading to string instability [START_REF] Peters | Leader tracking in homogeneous vehicle platoons with broadcast delays[END_REF]. For the case of linear dynamical agents, the very recent results from [START_REF] Sabau | Optimal distributed control for platooning via sparse coprime factorizations[END_REF] provide a functional scheme for compensating the effect of the communications delays by employing GPS time based synchronization mechanisms. However, the aforementioned method [5, Section VI] of essentially "incorporating" the synchronization delay in the model of the plant cannot be adapted to nonlinear dynamical models. In this section we introduce a practical method for adapting the distributed controller of Section IV to be able to compensate the communications delays, while essentially preserving all the performance features from the delay free case.

A. An Adaptation of Time-Headways for Velocity Matching Classical results in platooning control [START_REF] Chien | Automatic Vehicle Following[END_REF], [START_REF] Klinge | Time headway requirements for string stability of homogeneous linear unidirectionally connected systems[END_REF], [START_REF] Swaroop | A comparison of spacing and headway control laws for automatically controlled vehicles[END_REF] proved that a considerable improvement of performance can be obtained by adequately modifying the regulated interspacing distance (for each vehicle k) z k = y k-1 -y k such as to include a factor -h ẏk (t) proportional with the speed of the current vehicle. The resulted interspacing policies (dubbed time headways) become z k = y k-1 (t) -y k (t) -h ẏk (t) and provide a spacing in time rather than distance (between two consecutive vehicles). Up until the recent distributed scheme introduced in [5] -for linear dynamical agents and linear controllers, string stability could only be achieved via the use of time headways policies [START_REF] Middleton | String Stability in Classes of Linear Time Invariant Formation Control with Limited Communication Range[END_REF]. Furthermore, relatively large values of the time headway h > 0 were necessary in order to guarantee both string stability and the improvement of disturbances attenuation at mid and high frequency 2 . The generally adopted value for highway platooning (which became standardized at some point) is h = 1 second. The main drawback of such large time headways is that they drastically impair the tightness of the formation, reducing the traffic throughput and any potential fuel savings achievable by the air drag reduction.

We introduce next a novel method for delays compensation that combines the GPS time based synchronization mechanism from [5, Section VI] with an adaptation of the time headways to the velocity matching objective of our distributed controller from Section IV. Firstly, let us revamp as follows the definitions (4) of the interspacing distances z k and of the regulated relative speeds z v k respectively at the k-th vehicle:

z k (t) def = y k-1 (t -θ) -y k (t -θ) -θ ẏk (t -θ), (14)
z v k (t) def = v k-1 (t -θ) -v k (t -θ) -θ vk (t -θ), 1 ≤ k ≤ n,
where the positive constant θ > 0 will be taken to be equal with the communications delay and will be considered to be the same for all vehicles in formation 3 . It can be seen that the signals defined in ( 14) are merely θ delayed version of (4), with an additional θ time headway added to the expression of the interspacing errors z k . The fact that in ( 14) at the current moment in time t, we regulate the measurements taken at moment (t-θ) is a limitation imposed by the communications delay (which are relatively very small, though) and it entails some loss in performance which was to be expected. The inclusion of the θ time headway results in a slightly more conservative policy, since it induces slightly larger 4 interspacing distances as the speed increases. The same conservative effect (of the θ time headway) occurs with respect to the regulated relative speeds z v k (t) during the transient regime when the acceleration vk is sizable.

Remark 5.1: For all practical applications related to platooning, the value of θ will be taken to be equal to a worst case scenario value of the latency of the wireless communication systems, which is about 2×10 -2 seconds for digital radio systems such as WiFi, Bluetooth or Zigbee. Furthermore, the GPS time based synchronization mechanism described in [5, Section VI] used in conjunction with time stamping protocols at the transmission of the predecessor's control signal u k-1 is able to emulate and implement time invariant and heterogeneous communications time delays through the entire formation.

B. Analysis

Next, note that by performing a Taylor series expansion it follows that

y k (t) = y k (t -θ) + θ ẏk (t -θ) + O(θ 2 ), v k (t) = v k (t -θ) + θ vk (t -θ) + O(θ 2 ), (15)
therefore an O(θ 2 ) approximation of the measurements from ( 14) is given by

z k (t) def = y k-1 (t -θ) -y k (t), z v k (t) def = v k-1 (t -θ) -v k (t) for 1 ≤ k ≤ n. (16)
We assume the following initial conditions

y k (t) = - k j=0 j , v k (t) = 0, ∀t ∈ (-θ, 0].
Remark 5.2: Writing the Taylor series expansion with an integral rest, we obtain the following equivalent expression for ( 16)

z k (t) = y k-1 (t -θ) -y k (t -θ) - t t-θ ẏk (τ )dτ, z v k (t) = v k-1 (t -θ) -v k (t -θ) - t t-θ vk (τ )dτ (17)
and so it becomes apparent that the signals introduced in ( 16) can be measured on board the k-th vehicle via (17), using only onboard ranging sensors 5 and high accuracy longitudinal speedometers in conjunction with a mere integrator. Specifically, the first term in (17) consists of the θ-delayed measurement of the interspacing distance minus the integration of the absolute speed (measurable on board) over a θ-length interval. The second term in (17) consists of the θ-delayed measurement of the relative speed 6 minus the (v k (t) -v k (t -θ)) term, comprised of absolute speeds measurable onboard. Finally, the entire history on the interval [(t -θ), t] of the ranging sensors ( 17) must be stored in a memory buffer, in order to be used by the distributed controller we will introduce next.

Given the values of θ that appear in practice (see Remark 5.1) and given the worst case scenario of breaking decelerations |ÿ k (t)| that could occur during highway traffic, it follows from (15) that the signals from [START_REF] Su | Adaptive secondorder consensus of networked mobile agents with nonlinear dynamics[END_REF] are such an accurate approximation of [START_REF] Fiacchini | Convex conditions on decentralized control for graph topology preservation[END_REF], that the order of the approximation falls way below the tolerated measurement errors of the most performant ranging sensors. That is to say that choosing between two controllers that regulate either the ( 14) signals or the [START_REF] Su | Adaptive secondorder consensus of networked mobile agents with nonlinear dynamics[END_REF] signals respectively, has considerably less influence on the resulted scheme than the measurement noise of an highly accurate LIDAR. Consequently, we can choose to regulate [START_REF] Su | Adaptive secondorder consensus of networked mobile agents with nonlinear dynamics[END_REF]. Considering the definition of z k and z v k as in ( 16), we will prove that the distributed control policies given next are able to entirely compensate the communication induced delays:

u k (t) =u k-1 (t -θ) + β k z v k (t) + ∇ y k V k,k-1 ( z k (t) σ ) u k (t) =0, ∀t ∈ (-θ, 0] (18
) Remark 5.3: Note that for the real time implementation of type [START_REF] Bullo | Distributed Control of Robotic Networks[END_REF] control policies onboard the k-th vehicle, two pieces of information are needed: (i) the command signal of the predecessor, received on board a with θdelay, via wireless communications and (ii), the ( 16) sensor measurements z k , z v k which are on board measurable (according to the considerations of Remark 5.2). A GPS time-base synchronization of these two pieces of information may be performed as in [5, Section VI] in order to ensure time invariant, point-wise delays of value exactly θ, homogenously throughout the entire formation.

With this controller at hand we obtain the following closed-loop error equations at the k-th agent:

żv k (t) = f (v k-1 (t -θ)) -f (v k (t)) -β k z v k (t) + ∇ y k V k,k-1 ( z k (t) σ ). (19)
We will use the Lyapunov function defined in [START_REF] Godsil | Algebraic Graph Theory[END_REF] keeping in mind that the definitions of z k (t), z v k (t) are in accordance to [START_REF] Su | Adaptive secondorder consensus of networked mobile agents with nonlinear dynamics[END_REF]. Consequently, the time delays adaptation for the main result of Section IV reads:

Theorem 5.4: If the function f (•) from (2a) satisfies the global Lipshitz-like condition [START_REF] Martin | Multi-agent flocking under general communication rule[END_REF] then for all type (18) control laws with that β k > α the following hold: (A) The differential of the Lyapunov candidate function L k (•, •) introduced in (10) along the trajectories of (2) and ( 18) is given by (C) The controller [START_REF] Bullo | Distributed Control of Robotic Networks[END_REF] guarantees velocity matching and a lower bound on the absolute values of the interspacing distance z k (t). Furthermore, considering c = 2L k (z k (0), z v k (0)) there exists η c such that

d dt L k (z k (t), z v k (t)) = z v k (t) f v k-1 (t -θ) -f v k (t) -β k z v k (t)z v k (t) , (20)
z k (t) 2 > η c , ∀t ≥ 0.
Therefore, a pre-specified safety distance can be imposed by the initial conditions.

Remark 5.5: The scheme proposed above is able to regulate v k-1 (t -θ) -v k (t) in the presence of communications delays. Therefore, as far as the leader's velocity profile is slowly varying relatively to the order of magnitude of the communications delays, the scheme does regulate an accurate approximation of v k-1 (t) -v k (t). Nevertheless, oscillations of the leader's velocity at a frequency that is of the same order of magnitude with the θ time delay cannot be efficiently compensated and the accordion effect will appear. These assumptions are very well satisfied in the platooning setting, but they may not be valid for other applications. The conclusion is in line with the well known fact that for the validity of the control scheme it is always necessary that the time delays that propagate through the controller are smaller than those propagating through the given plant.

VI. A NUMERICAL EXAMPLE

In this section we illustrate the distributed controller introduced earlier for the case dynamical agents [START_REF] Zhou | Flocking of multi-agent dynamical systems based on pseudo-leader mechanism[END_REF], where the function f (•) taken to be a quadratic form f (v) = -γg -v 2 , in accordance with the dynamical model of road vehicles from [22, (1)/pp. 1]. Here, γ = 0.011 is the tyre rolling resistance coefficient, g = 9.81m/s 2 the gravitational acceleration, and = 0.463 kg/m the air drag constant. The dynamics (2) become

ẏk = v k (21a) vk = -γg -v 2 k + η R w k (21b)
with η = 1.8 being the gear ratio and R = 0.5 being the wheel radius. The command signal ω k is the engine's torque, and its linear transformation

η R ω k corresponds to the input u k in (2). Note that f (•) in (21) satisfies the global Lipschitz-like condition [2, Assumption 1] (v 2 - v 1 ) f (v 2 ) -f (v 1 ) ≤ α v 2 -v 1 2 2 , for any two vectors v 1 , v 2 in the domain of f (•).
The control law is designed using APFs (Definition 2.3) of the following form [2, Fig. 1

/ pp.197] V k,k-1 ( z k σ ) = η R ln( z k σ ) 2 + 100 z k 2 σ ( 22
)
and an empirically tuned gain β = 25 η R . The reference signal for the entire formation will be the control control of the leader vehicle, namely u 0 (t).

We look at a speed profile of the leader consisting of two smoothed rectangular pulses. The vehicles start at relatively small separations, of about 2 m. The plots for the delay free case, using the baseline controller from Section IV are shown in Figure 1. The controller will cause an initial increase in the interspacing distances, at the expense of delaying velocity matching. Once a sufficient interspacing distance has been achieved (in this case, around 5 m, related to the minimum of the APFs), the velocities are brought together. If we consider a time delay of θ = 0.02 s (which is the common nominal value for wireless communications) and we apply the delay compensation mechanism from Section V, then Figure 2 below exhibits practically the same wave forms as Figure 1, hence the effects of the delays are entirely compensated by the controller. Finally, to illustrate the point made by Remark 5.5, we look at the situation when the leader's velocity profile is a fast-varying sine while considering a large time delay θ = 0.5 s, comparable to the period of the sine reference. The examination of Figure 3 below, shows that velocity agreement cannot be achieved, and there is an "accordion" effect in the positions (undamped oscillations). However, even in this challenging situation the controller manages to avoid collisions.

Theorem 4 . 1 :

 41 If the function f (•) from (2a) satisfies the global Lipshitz-like condition [2,Assumption 1]

  withc > 0} of L k are compact and they represent forward invariant sets for the local closed-loop dynamics (9) of the k-th vehicle. (B) The controller (6) guarantees velocity matching and collision avoidance. Furthermore, considering c

  and does not depend on the choice of the APFs V k,k-1 (•). (B) Given the Lyapunov function L k introduced in (10), local to the k-th agent, the sub-level sets Ω k c def = {(z k , z v k )|L k ≤ c, withc > 0} of L k are compact and they represent forward invariant sets for the local closed-loop dynamics (19) of the k-th vehicle.

Fig. 1 .

 1 Fig. 1. Trajectories of vehicles -the delay free case

Fig. 2 .

 2 Fig. 2. Trajectories of vehicles with a typical θ = 0.02 s. time delay

Fig. 3 .

 3 Fig. 3. Trajectories with a fast varying leader reference and large time delay.

For digital radio wireless systems such as WiFi, Bluetooth or Zigbee, the corresponding time-delays have low latencies but they are time-varying, taking values around a nominal delay of about

ms.

It's worth mentioning that the control scheme proposed in[START_REF] Sabau | Optimal distributed control for platooning via sparse coprime factorizations[END_REF] achieves without time headways the same disturbances attenuation at low and mid frequency as the attenuation achievable with the use of time headways.

See also Remark 5.1 in the following paragraph

The effect is directly proportional with the value of θ which is very small in practice.

Preferably very low latency LIDAR sensors, which are already affordable and widely available commercially

The relative speed with respect to the preceding vehicle, which is also measurable onboard.


K Abidi
email: kabidi@esi.dz

M A Menacer

Kamel Smaïli
email: kamel.smaili@loria.fr

CALYOU: A Comparable Spoken Algerian Corpus Harvested from YouTube

Keywords: Algerian dialect, Word2Vec, Comparable corpora, Soundex

This paper addresses the issue of comparability of comments extracted from Youtube. The comments concern spoken Algerian that could be either local Arabic, Modern Standard Arabic or French. This diversity of expression gives rise to a huge number of problems concerning the data processing. In this article, several methods of alignment will be proposed and tested. The method which permits to best align is Word2Vecbased approach that will be used iteratively. This recurrent call of Word2Vec allows us improve significantly the results of comparability. In fact, a dictionary-based approach leads to a Recall of 4, while our approach allows one to get a Recall of 33 at rank 1. Thanks to this approach, we built from Youtube CALYOU, a Comparable Corpus of the spoken Algerian.

Introduction

Nowadays, to develop speech recognition systems for vernacular languages, is a real challenge for the community. Contrary to classical natural language, vernacular languages are by definition used daily in the communication but are rarely written. To develop a speech recognition system or machine translation for this kind of language, we need to collect data. The best way to get this type of data is to harvest them from social networks. In this work, we are interested by the spoken Algerian. One needs to know that in Algeria people speak their mother tongue, which is a special Arabic dialect, but could speak the official language, which is Modern Standard Arabic (MSA), and also French. Nevertheless, what makes the issue more challenging is that people can mix in the same sentence the three previous languages. Extracting data from Youtube is not new, Salama et al. in [START_REF] Salama | Youdacc: the youtube dialectal arabic comment corpus[END_REF] extracted several dialects from this social network in order to constitute a dataset of several dialects. In [START_REF] Abdul-Mageed | yes we can?": Subjectivity annotation and tagging for the health domain[END_REF], the authors used Youtube in order to build a Lexicon for the sentiment Analysis. A similar work has been done by [START_REF] Uryupina | Sentube: A corpus for sentiment analysis on youtube social media[END_REF]. In [START_REF] Siersdorfer | How useful are your comments?: analyzing and predicting youtube comments and comment ratings[END_REF], the authors studied the influence of the sentiment existing in comments of Youtube. Our objective in this work is to collect from Youtube Algerian comments and to align those that are close to each other. To do that, we crawled 22000 videos by using 250 queries related to Algerian topics, such as: Bouteflika, Sellal, Messaoudi, Samira Tv, Aliouet, etc. Aligning comments will produce a comparable corpus we called CALYOU (Comparable spoken ALgerian extracted from YOUtube). This corpus could be used in several topics such as: adapting a MSA language model to Algerian dialect, to extract parallel dialectal phrases, which may be included in translation tables, etc. This paper is organized as follows: In Section 2, we present related works concerning the extraction of comparable corpora.

Then, we give an overview on languages spoken in Algeria and their difficulties, in Section 3. We describe the collected corpus in Section 4. Several experiments and results are described in Section 5. Finally, we conclude and present some future works.

Related works

The comparability topic is widely used in the community and several articles have been published. When documents are collected, one needs to measure the closeness between different articles. The automatic acquisition of comparable corpora can be accomplished by using similarity measures. These measures consist to quantify and capture the different comparability levels. Several related work proposed efficient measures to align and evaluate the quality of extracted comparable documents. Li and Gaussier in [START_REF] Li | Improving corpus comparability for bilingual lexicon extraction from comparable corpora[END_REF] defined the degree of comparability between two corpora as the expectation of finding, for each word of the source corpus, its translation in the target one. They use this definition to propose a measure that estimates the comparability of two parallel corpora to which noise have been added. They showed that the comparability degree decreased proportionally with the added noise. A similar approach proposed by Etchegoyhen et al. in [START_REF] Etchegoyhen | Set-theoretic alignment for comparable corpora[END_REF] termed STACC, is based on expanded lexical sets and Jaccard similarity coefficient. The idea is to get rid of a manual bilingual dictionary. The bilingual dictionary is built on a large parallel corpus by using Giza ++ [START_REF] Och | A systematic comparison of various statistical alignment models[END_REF]. Since, it is independent from languages, the approach has been evaluated on a large dataset of ten languages. Huang et al. in [START_REF] Huang | Mining large-scale comparable corpora from chinese-english news collections[END_REF] describe a method based on techniques inspired from Cross Lingual Information Retrieval. With the translation of the keywords of the source documents, they retrieve the target documents that contain these translated words. Then, the mapping between source and target documents is achieved in accordance to a similarity value. A method based on word embedding has been proposed by Vulic et al in [START_REF] Vulic | Monolingual and cross-lingual information retrieval models based on (bilingual) word embeddings[END_REF]. The model has the possibility to learn bilingual word embeddings from already comparable corpora. The crucial idea in this work is the fact that the method allows to share the cross-lingual embedding space. Works on comparable corpus containing Arabic are not as popular as those used for English or French, we can mention those proposed in [START_REF] Munteanu | Improving machine translation performance by exploiting non-parallel corpora[END_REF], [START_REF] Abdul-Rauf | On the use of comparable corpora to improve SMT performance[END_REF], [START_REF] Saad | Cross-lingual semantic similarity measure for comparable articles[END_REF]. In this last work, different comparability measures based on bilingual dictionaries or on numerical methods such as Latent Semantic Indexing (LSI) have been proposed. At the best of our knowledge, there is no work consisting of aligning corpora of the Algerian spoken language in its all forms: writing in MSA, in French and in dialect. Add to that, all the issues related to the way of writing the dialect: Latin script or Arabic script. Also, due to the missing of dictionaries and corpora, no standardization of writing words is available. Concerning resources, except PADIC [START_REF] Meftouh | Machine translation experiments on PADIC: A parallel arabic dialect corpus[END_REF] a multilingual parallel corpus, which contains 6 dialects including two from Algeria, there is no substantial known data.

The spoken Algerian

People in Algeria speak mainly Algerian dialect, but this one could be mixed to Modern Standard Arabic and even French. Algerian dialect is informal language, not used in official speech, it includes an important portion of borrowed words, especially from French, Turkish and Berber. Vocabulary of Algerian dialect includes verbs, nouns, pronouns and particles. Most of this vocabulary is from MSA. Moreover, there is significant variation in the vocalization in most cases, and omission of some letters in other cases (mainly the Hamza) 1 . As presented before, in this paper we are interested by the comments of Algerian videos. We have to mention that there is no rule in the way of writing the comments and this constitutes a real challenge for the community. Because no standardization exists, people write sometimes Algerian dialect by using Latin script (LS), called also Arabizi that is an alphabet to communicate over Internet. This obviously constitutes a serious issue because Arabic NLP tools could not be used. Unfortunately, French NLP tools cannot be used either since the written words in LS are not in French. In the following, we give an example of a post related to an Algerian video: w jma3atkom t3ayeb f bouteflika aw rah khirmanek b alf khatra. That should be written with Arabic script (AS) such as: and means: And you are making fun of Bouteflika when he is a thousand times better than you. One can remark that people use some codification for specific Arabic letters that do not exist in LS. This is the case of that is written 3, that is written 9, as 5 and other codes that are not officially unfortunately adopted by everyone. Algerian dialect could be written by using AS, but some words are not Arabic, they are in general adapted from French such as:

that means its place. The sound / p / does not exist in Arabic, but in Algerian dialect it is used as it is and sometimes it is replaced by / b /. In addition to the Algerian mother tongue, people may express their opinions in French, while some propose their comments in Modern Standard Arabic. This diversity of the different ways to write comments show the large panel of writing the spoken language that make the processing very challenging.

Corpus

To build CALYOU, we harvested data from Youtube by using the Google's API2 that allows users to search for videos that match specific criteria and retrieve all information and comments of those videos. To harvest, we chose few keywords to form queries in order to retrieve videos concerning national news, Algerian celebrity, football, etc. Table 1 shows some statistics of the collected data, where |C| is the number of comments before and after preprocessing, |W | is the number of words and |V | is the vocabulary size.

We can mention that after the cleaning process, the corpus has been reduced by around 20% and the vocabulary by around 10%.

Measuring the comparability

Our objective is to make comparable Algerian dialect, French and Arabic comments to create CALYOU. What we propose, is not only, to produce comparable French and dialect comments, but also to align dialect comments written in LS with those written in AS.

To this end, we need to measure the comparability of comments, that is why we used classical approaches and proposed new ones adapted to the Algerian dialect.

The methods are evaluated on a test corpus composed of comparable comments built by hand. The performance are given in terms of the classical Recall (R@1, R@5 and R@10), well known in Information Retrieval, are given in Table 3 and will be detailed for each approach in the next sections.

Dictionary-based method

In a first experiment, we used a dictionary-based method proposed by Li and Gaussier (LG) [START_REF] Li | Improving corpus comparability for bilingual lexicon extraction from comparable corpora[END_REF]. The comparability measure can be defined as the maximum score between a comment written in LS and all the comments written AS. We mention that even if the comment is written in LS, that does not mean necessarily that it is a French comment. It could be a dialectal comment written in LS as explained in Section 3.

The size and the quality of dictionary may heavily affect the result of comparability measure. For LG, we used the Open Multilingual WordNet (OMW) 3 that contains 55373 pairs of Arabic and French words.

LG method achieves bad results: 4 at Recall 1 (see Table 3), this was expectable since the dictionary is composed by MSA words and not by Algerian Arabic words. In our best of knowledge, there is no available large Algerian -French dictionary, that is why we used the mentioned dictionary because even if the comments are in Arabic dialect, they contain words in MSA.

Indexing words by their sounds

Since dialect is a spoken language, people may write the same word in different manners, while keeping the same pronunciation. That is why, we decided to improve the last method by indexing the words by their pronunciation or more exactly by their representative sounds. For that, we used Soundex [START_REF] Aqeel | On the development of name search techniques for arabic[END_REF], a phonetic algorithm for indexing by sound. Words are encoded by taking advantage of their phonetic form. The encoding is done in both comments in LS and AS. All the words in the LS that do not exist in the bilingual dictionary are encoded by Soundex. The underlying hypothesis is that we might consider them such as dialectal words or proper names. Then all the words of the comment written in Arabic are encoded by Soundex. If two strings from respectively LS, AS comments have the same code, we can conclude that, one is the transliteration of the other. Soundex proposes to replace each letter by the index of a group of characters. Each group is constituted by the graphemes corresponding to the similar class of sounds (see Table 2). We obviously adapted the original corresponding's table in order to match the graphemes of Youtube comments and Arabic sounds. The characters of Group 0, are ignored unless they appear in the first position of a word. Encoding consists in keeping the first character without any change and the following are encoded in accordance to Table 2. Any word will be represented by a letter followed by three digits. For example, encoding the dialect word , will give two codes (Figure 1) corresponding to the possible transliterations: Houma and 7ouma.

Table 2: Corresponding's table for transliteration

English character Index

Arabic character

A E H I O U W Y 0 B P F 1 C S K G J Q X Z 2 D T 3 L 4 M N 5 R 6

Houma 7ouma

Soundex ArSoundex H500 7500 H500, 7500 For the previous example will be encoded by " 500", then is transliterated by 7 or H. Consequently, the words , Houma and 7ouma match. Therefore, the process of comparability will provide better results. In fact, we combined LG and Soundex in the process of comparability. The results are given in Table 3 (Line 2). Introducing Soundex allows to improve the results from 4 to 11 at Recall 1. This is obviously not enough but, henceforth the use of the sound representation of words is necessary.

A Word2Vec-based method

The free style of writing in the comments of Youtube gives rise to some problems when words should be matched. In fact, the same word in the Algerian spoken could be written in several ways such as in Table 4. The word kho, which means brother, could be written in various manners in addition to similar words such as hbibna. The word frr is also a way to express the meaning of the word kho; it is derived from the French word frère of which the vowels have been discarded. Because we work on Table 4: An Example of different ways to write the word kho khoya khoo khouya khou khyo khooo hbibna frr dialects and there is no dictionary, which could provide all the forms related to one lexical entry, we decided to use Word2Vec to retrieve the different forms of a word. To find the correlated words for each entry of an Algerian lexical dialect, we opted for a continuous bag of words (CBOW) method [START_REF] Mikolov | Efficient estimation of word representations in vector space[END_REF] with a sliding window of 150. This size has been fixed after several tests. This large number is due to the fact that all the comments concerning the same video have been concatenated into one document. CBOW allows us to build for each word, a list of its correlated words, the idea is to have for each word all its various forms.

Table 5 shows the words that are related to kho with the corresponding distances. We can remark that the majority of those words of Table 4 do exist in the list provided by word2Vec. In addition to these words, others are proposed that will be helpful for the comparability. We used these lists of words provided

SC(CLS, CAS) = w∈C LS σ(w, CAS) + w∈C AS σ(w, CLS) |CLS| + |CAS| (1)
where CLS (respectively CAS) is Latin Script (respectively Arabic script) of Algerian video comments. σ is a function, which increases the value of the comparability, if any word provided by CBOW does exist in the target comment.

σ(w, C) = 1 if ∃m/m ∈ CBOW (w) ∧ m ∈ C 0 else (2)
The comparability measure SCw2v can be defined as the maximum score between a Latin script comment CLS with every comment written in Arabic script C i AS for 1 ≤ i ≤ NC AS . Where NC AS is the number of comments written in Arabic script.

change du traditionnel original, j'ai essayé votre recette j'ai vraiment beaucoup aimé, W2V

w 1 → x 1 1 . . . x n 1 w 2 → x 1 2 . . .
SCw2v(CLS) = max 1≤i≤N C AS Score(CLS, C i AS ) (3)
The results of comparability are better than what we obtain with Li and Gaussier combined with Soundex. In fact, in this method we take into account the variability of writing the dialect in the comments of Youtube videos. The results jumped from 11 at Recall 1 to 24, this is a significant result but is not enough. By combining the comparability based on CBOW with Soundex, we noticed a small improvement of 4% at rank 1 and 6% at rank 5 (see Table 3 Line 4) .

Iterating Word2Vec for improving the comparability

In order to improve the comparability of comments, we decided to iterate the process of Word2Vec. The underlying idea is to improve, at each step, the quality of comparability of the comments. In fact, since the results of comparability have been improved by using Word2Vec, we decided to retrain the system with better comparable documents achieved by this method.That means, after getting comparable comments by using Word2Vec, these documents are put back into the training corpus. Then, we calculate again for each word in Latin script its corresponding and correlated words written in Arabic script. The justification of this process is that at the initial step, the CBOW method runs on articles composed of bulk comments, but of the same topic. Theses comments are not gathered in order to assure good performance to CBOW. When we align them, we hope that by injecting them into the training process, we will get a better training corpus. This iterative process is repeated until the measure of comparability stops increasing as illustrated in Figure 2.

This process has been iterated several times until the Recall 1 stops increasing. In fact, this process improves the quality of comparability that reaches 33 at Recall 1 and 54 at Recall 10. This improvement is significant in comparison to all the other experiments achieved before. In Table 6, we present some examples of comments aligned by our approach. For each comment in Latin script, the corresponding target comment retrieved by the iterative Word2Vec is given. One can notice that, in the first example of Table 6, the French comment is not well written. As presented before, people write sometimes as they want without any respect of the lin-guistic rules. We can notice in theses examples that the retrieved comments are close to the source comments. Let us focus on the fact that sometimes the dialect is written in Latin script but the sentence is not in French, such as in the third example of Table 6. Our approach permits to find the best comment written in Arabic associated to this dialect comment written in Latin script.

Conclusions

In this article, we addressed the difficult issue of matching comments from Youtube for a vernacular language for which no writing rules do exist. It concerns the spoken Algerian for which people express their opinions in Youtube in local Arabic dialect, Modern Standard Arabic and French. Sometimes, in the same comment the three languages may be mixed. This particularity is specific to the spoken Algerian that leads to more difficulties in the treatments of the corresponding texts. We tested a classical dictionary-based method to match comments; this approach totally collapsed by achieving a Recall of 4! Because, people write with Latin script and Arabic script, the use of phonetic representation has been considered in order to find the transliterations of words written in two completely different scripts. The use of a phonetic algorithm (Soundex) allowed to reach an absolute improvement of 7 points. This improvement is relevant, in comparison to the initial score of Li and Gaussier that is very poor. Then, we used a Word2Vecbased approach to find a list of words that could be correlated to a lexical entry. This method permitted to find a list of variations of the same word. Then this has been exploited for the matching process of comparability. The results jumped again and outperformed the baseline method. We proposed then an approach that iterates the process of collecting the list of words by Word2Vec in order to improve at each step the quality of the training corpus. The results achieved are very relevant since the corresponding method outperforms the approach LG and Soundex by 22 points. This approach allowed us to build CA-LYOU: A comparable spoken Algerian corpus extracted from YouTube. The performance we get (33 at Recall 1) may be considered as weak and we have to improve it in a future work. But, different experiments in the literature, on comparable corpora for natural language and not for dialects, have been done, but they have not reached much better results [START_REF] Saad | Extracting comparable articles from wikipedia and measuring their comparabilities[END_REF] than what we get on much more difficult data.

Figure 1 :

 1 Figure 1: Encoding dialect word

Table 1 :

 1 The collected Youtube Algerian Dialect Corpus

		Raw corpus Cleaned Corpus
	|C|	1.1M	853K
	|W |	16M	12.7M
	|V |	97K	88K

Table 3 :

 3 Comparability results

		R@1 R@5 R@10
	LG	4	12	19
	LG + Sound	11	27	40
	SCw2v	23	42	51
	SCw2v + Sound	24	45	52
	Iterative SCw2v + Sound	33	48	54

Table 5 :

 5 The closest words of kho in accordance to CBOW method

	khoya video khoo	khouya rak	khou
	0.59	0.53	0.52	0.51	0.47 0.46
	khooo ta3	hbibna			frr
	0.45	0.44	0.44	0.41	0.38 0.37
	by Word2Vec to better estimate the comparability between two
	comments. The comparability between a comment in LS with a
	comment in AS is estimated as follows:

Table 6 :

 6 Example of comparable comments aligned by using the iterative Word2Vec principle Source j'ai trop aimé la tenu c mon style Translation I like too much your outfit, this is my style Target Translation I like them too much, I like this style Source Deradji reste avec le sport Translation Deradji continue taking care of sport Target: Translation Mr derradji you are expert in Sport, please continue in sport and we will continue appreciating you Source radja meziane vraiment cette chanson djat thebel be la voix dialek w rabi yerhem kamel messaoudi Translation Raja Meziane this song is wonderful with your voice, may God bless the soul of Kamel Messaoudi Target Translation Beautiful Lyrics especially with your voice, may God bless the soul of Kamel Messaoudi

The Hamza is a letter in the Arabic alphabet, representing the glottal stop.

[START_REF] Abdul-Mageed | yes we can?": Subjectivity annotation and tagging for the health domain[END_REF] Available at: https://developers.google.com/Youtube

Available at : http://compling.hss.ntu.edu.sg/omw/