Cyril Gavoille
email: gavoille@labri.fr.

Quentin Godfroy
email: quentin@godfroy.eu.

Laurent Viennot
email: laurent.viennot@inria.fr.

Node-Disjoint Multipath Spanners and their Relationship with Fault-Tolerant Spanners

Keywords: distributed graph algorithm, spanner, multipath routing

HAL is

Introduction

It is well-known [ADD + 93] that, for each integer k 1, every n-vertex weighted graph G has a subgraph H, called spanner, with O(n 1+1/k ) edges and such that for all pairs u, v of vertices of G, d H (u, v) (2k -1) • d G (u, v). Here d G (u, v) denotes the distance between u and v in G, i.e., the length of a minimum cost path joining u to v. In other words, there is a trade-off between the size of H and its stretch, defined here by the factor 2k -1. Such trade-off has been extensively used in several contexts. For instance, this can be the first step for the design of a Distance Oracle, a compact data structure supporting approximate distance query while using sub-quadratic space [START_REF] Thorup | Approximate distance oracles[END_REF][START_REF] Baswana | Distance oracles for unweighted graphs: Breaking the quadratic barrier with constant additive error[END_REF][START_REF] Baswana | Faster algorithms for approximate distance oracles and all-pairs small stretch paths[END_REF]. It is also a key ingredient for several distributed algorithms to quickly compute a sparse skeleton of a connected graph, namely a connected spanning subgraph with only O(n) edges. This can be done by choosing k = O(log n). The target distributed algorithm can then be run on the remaining skeleton [START_REF] Barenboim | Deterministic distributed vertex coloring in polylogarithmic time[END_REF]. The skeleton construction can be done in O(k) rounds, whereas computing a spanning tree requires diameter rounds in general. We refer the reader to [START_REF] Pettie | Low distortion spanners[END_REF] for an overview on graph spanner constructions.

However, it is also proved in [START_REF] Thorup | Approximate distance oracles[END_REF] that if G is directed, then it may have no sub-digraph H having o(n 2 ) edges and constant stretch, the stretch being defined analogously by the maximum ratio between the one-way distance from u to v in H and the one-way distance from u to v in G. Nevertheless, a size/stretch trade-off exists for the round-trip distance, defined as the sum of a minimum cost of a dipath from u to v, and a minimum cost dipath from v to u (see [START_REF] Cowen | Compact roundtrip routing in directed networks[END_REF][START_REF] Roditty | Roundtrip spanners and roundtrip routing in directed graphs[END_REF]). Similar trade-offs exist if we consider the p-edge-disjoint multipath distance (in undirected graphs) for each p 1, that is the minimum sum of p edge-disjoint paths joining u and v, see [START_REF] Gavoille | Multipath spanners[END_REF].

Trade-offs for non-increasing graph metric

More generally, we are interested in size/stretch trade-offs for graphs (or digraphs) for some non-increasing graph metric. A non-increasing graph metric δ associates with each pair of vertices u, v some non-negative cost that can only decrease when adding edges. In other words, δ G (u, v) δ H (u, v) for all vertices u, v and spanning subgraphs H of G. Moreover, if δ H (u, v) α • δ G (u, v) + β, then we say that H is an (α, β)-spanner and that its stretch (w.r.t. the graph metric δ) is at most (α, β). We simply say that H is an α-spanner if β = 0. The size of a spanner is the number of its edges.

In the previous discussion we saw that every graph or digraph has a spanner H of size o(n 2 ) and with bounded stretch for graph metrics δ such as round-trip, p-edge-disjoint multipath, and the usual graph distance. However, it does not hold for one-way distance. A fundamental task is to determine which graph metrics δ support such size/stretch trade-off. We observe that the three former graph metrics cited above have the triangle inequality property, whereas the one-way metric does not.

This paper deals with the construction of spanners for the vertex-disjoint multipath metric. A pmultipath between u and v is a subgraph composed of the union of p pairwise internally vertex-disjoint paths joining u and v. The cost of a p-multipath between u and v is the sum of the weight of the edges it contains. Given an undirected positively weighted graph G, define δ p G (u, v) as the minimum cost of a pmultipath between u and v if it exists, and ∞ otherwise. A p-multipath s-spanner is a spanner H of G with stretch at most s w.r.t. the graph metric δ p . In other words, for all vertices u, v of

G, δ p H (u, v) s•δ p G (u, v), or δ p H (u, v) α • δ p G (u, v) + β if s = (α, β). It generalizes classical spanners as d G (u, v) = δ p G (u, v) for p = 1.

Motivations

Our interest in the node-disjoint multipath graph metric stems from the need for multipath routing in networks. Using multiple paths between a pair of nodes is an obvious way to aggregate bandwidth. Additionally, a classical approach to quickly overcome link failures consists in pre-computing fail-over paths which are disjoint from primary paths [KKKM07, [START_REF] Pan | Fast Reroute Extensions to RSVP-TE for LSP Tunnels[END_REF][START_REF] Nasipuri | Performance of multipath routing for on-demand protocols in mobile ad hoc networks[END_REF]. Multipath routing can be used for traffic load balancing and for minimizing delays. It has been extensively studied in ad hoc networks for load balancing, fault-tolerance, higher aggregate bandwidth, diversity coding, minimizing energy consumption (see [START_REF] Mueller | Multipath routing in mobile ad hoc networks: Issues and challenges[END_REF] for a quick overview). Considering only a subset of links is a practical concern in link state routing in ad hoc networks [START_REF] Jacquet | Remote spanners: what to know beyond neighbors[END_REF]. This raises the problem of computing spanners for the multipath graph metric, a first step towards constructing compact multipath routing schemes.

Our contributions

Our main contribution is to show that sparse p-multipath spanners of constant stretch do exist for each p 1. Moreover, they can be constructed locally in a constant number of rounds. More precisely, we show that:

1. Every weighted graph with n vertices has a p-multipath kp

• O(1 + p/k) 2k-1 -spanner of size Õ(p 2 • n 1+1/k ),
where k and p are integral parameters 1. Moreover, such a multipath spanner can be constructed distributively in O(k) rounds. 2. For p = k = 2, we improve this construction whose stretch is 18. Our algorithm provides a 2multipath (2, O(W ))-spanner of size O(n 3/2 ) where W is the largest edge weight of the input graph.

Distributed algorithms are given in the classical LOCAL model of computations (cf. [START_REF] Peleg | Distributed Computing: A Locality-Sensitive Approach[END_REF]), a.k.a. the free model [START_REF] Linial | Locality in distributed graphs algorithms[END_REF]. In this model nodes operate in synchronous discrete rounds (nodes are also assumed to wake up simultaneously). At each round, a node can send and/or receive messages of unbounded capacity to/from its neighbors and can perform any amount of local computations. Hence, each round costs one time unit. Also, nodes have unique identifiers that can be used for breaking symmetry. As long as we are concerned with running time (number of rounds) and not with the cost of communication, synchronous and asynchronous message passing models are equivalent.

Overview

Multipath spanners have some flavors of fault-tolerant spanners, notion introduced in [CLPR10] for general graphs. A subgraph H is an r-fault tolerant s-spanner of G if for any set F of at most r 0 faulty vertices, and for any pair u, v of vertices outside

F , d H\F (u, v) s • d G\F (u, v).
At first glance, r-fault tolerant spanners seem related to (r + 1)-multipath spanners. (Note that both notions coincide to usual spanners if r = 0.) This is motivated by the fact that, if for an edge uv of G that is not in H, and if, for each set F of r vertices, u and v are connected in H \ F , then by Menger's Theorem H must contain some p-multipath between u and v. If the connectivity condition fulfills, there is no guarantee however on the cost of the p-multipath in H compared to the optimal one in G. Actually, as presented on Fig. 1, there are 1-fault tolerant s-spanners that are 2-multipath but with arbitrarily large stretch. Nevertheless, a relationship can be established between p-mutlipath spanners and some r-fault tolerant spanners. In fact, we prove in Section 2.4 that every r-fault tolerant s-spanner that is b-hop is a (r + 1)multipath spanner with stretch bounded by a function of b, r and s. Informally, a b-hop spanner H must replace every edge uv of G not in H by a path simultaneously of low cost and composed of at most b edges. We observe that many classical spanner constructions (including the greedy one) do not provide boundedhop spanners, although such spanners exist as proved in Section 2.1. Some variant presented in [START_REF] Chechik | Fault tolerant spanners for general graphs[END_REF] of the Thorup-Zwick constructions [START_REF] Thorup | Approximate distance oracles[END_REF] are also bounded-hop (Section 2.2). Combining these specific spanners with the generic construction of fault tolerant spanners of [START_REF] Dinitz | Fault-tolerant spanners: Better and simpler[END_REF], we show in Section 2.3 how to obtained a LOCAL distributed algorithm for computing a p-mutlipath spanner of bounded stretch. A maybe surprising fact is that the number of rounds is independent of p and n. We stress that the distributed algorithm that we obtain has significantly better running time than the original one presented in [START_REF] Dinitz | Fault-tolerant spanners: Better and simpler[END_REF] that was Ω(p 3 log n).

s u v 1 s/n
For instance for p = 2, our construction can produce a 2-multipath 18-spanner with O(n 3/2 log 3/2 n) edges. For this particular case we improve the general construction in Section 3 with a completely different approach providing a low multiplicative stretch, namely 2, at the cost of an additive term depending of the largest edge weight.

We note that the graph metric δ p does not respect the triangle inequality for p > 1. For p = 2, a cycle from u to w and a cycle from w to v does not imply the existence of a cycle from u to v. The lack of this property introduces many complications for our second result. Basically, there are Ω(n 2 ) pairs u, v of vertices, each one possibly defining a minimum cycle C u,v of cost δ 2 G (u, v). If we want to create a spanner H with o(n 2 ) edges, we cannot keep C u,v for all pairs u, v. Selecting some vertex w as pivot for going from u to v is usually a solution of save edges (in particular at least one between u and v). One pivot can indeed serve for many other pairs. However, without the triangle inequality, C u,w and C w,v do not give any cost guarantee on δ 2 H (u, v).

Main Construction

In this section, we prove the following result:

Theorem 1 Let G be a weighted graph with n vertices, and p, k be integral parameters 1. Then, G has a p-multipath kp • O(1 + p/k) 2k-1 -spanner of size O(kp 2-1/k n 1+1/k log 2-1/k n) that can be constructed w.h.p. by a randomized distributed algorithm in O(k) rounds.

Theorem 1 is proved by combining several constructions presented now.

Spanners with few hops

An s-spanner H of a weighted graph G is b-hop if for every edge uv of G, there is a path in H between u and v composed of at most b edges and of cost at most s • ω(uv) (where ω(uv) denotes the cost of edge uv). An s-hop spanner is simply an s-hop s-spanner.

If G is unweighted (or the edge-cost weights are uniform), the concepts of s-hop spanner and s-spanner coincide. However, not all s-spanners are s-hop. In particular, the (2k -1)-spanners produced by the greedy2 algorithm [ADD + 93] are not.

For instance, consider a weighted cycle of n + 1 vertices and any stretch s such that 1 < s < n. All edges of the cycle have unit weight, but one, say the edge uv, which has weight ω(uv) = n/s. Note that d G (u, v) = ω(uv) > 1. The greedy algorithm adds the n unit cost edges but the edge uv to H because

d H (u, v) = n s • ω(uv) (recall that uv is added only if d H (u, v) > s • d G (u, v)).
Therefore, H is an s-spanner but it is only an n-hop spanner.

However, we have:

Proposition 1 For each integer k 1, every weighted graph with n vertices has a (2k -1)-hop spanner with less than n 1+1/k edges.

Proof. Consider a weighted graph G with edge-cost function ω. We construct the willing spanner H of G thanks to the following algorithm which can be seen as the dual of the classical greedy algorithm, till a variant of Kruskal's algorithm:

(1) Initialize H with V (H) := V (G) and E(H) := ∅;

(2) Visit all the edges of G in non-decreasing order of their weights, and add the edge uv to H only if every path between u and v in H has more than 2k -1 edges.

Consider an edge uv of G. If uv is not in H then there must exist a path P in H from u to v such that P has at most 2k -1 edges. We have d H (u, v) ω(P ). Let e be an edge of P with maximum weight. We can bound ω(P ) (2k -1) • ω(e). Since e has been considered before the edge uv, ω(e) ω(uv). It follows that ω(P ) (2k -1) • ω(uv), and thus

d H (u, v) (2k -1) • ω(uv). Obviously, if uv belongs to H, d H (u, v) = ω(uv) (2k -1) • ω(uv) as well. Therefore, H is (2k -1)-hop.
The fact that H is sparse comes from the fact that there is no cycle of length 2k in H: whenever an edge is added to H, any path linking its endpoints has more than 2k -1 edges, i.e., at least 2k.

We observe that H is simple even if G is not. It has been proved in [START_REF] Alon | The Moore bound for irregular graphs[END_REF] that every simple n-vertex m-edge graph where every cycle is of length at least 2k + 1 (i.e., of girth at least 2k + 1), must verify the Moore bound:

n 1 + d k-1 i=0 (d -1) i > (d -1) k
where d = 2m/n is the average degree of the graph. This implies that m < 1 2 (n 1+1/k + n) < n 1+1/k . Therefore, H is a (2k -1)-hop spanner with at most n 1+1/k edges.

Distributed bounded hop spanners

There are distributed constructions that provide s-hop spanners, at the cost of a small (poly-logarithmic in n) increase of the size of the spanner compared to Proposition 1.

If we restrict our attention to deterministic algorithms, [START_REF] Derbel | On the locality of distributed sparse spanner construction[END_REF] provides for unweighted graphs a (2k -1)-hop spanner of size O(kn 1+1/k ). It runs in 3k -2 rounds without any prior knowledge on the graph, and optimally in k rounds if n is available at each vertex.

Proposition 2 There is a distributed randomized algorithm that, for every weighted graph G with n vertices, computes w.h.p. a (2k -1)-hop spanner of O(kn

1+1/k log 1-1/k n) edges in O(k) rounds.
Proof. The algorithm is a distributed version of the spanner algorithm used in [START_REF] Chechik | Fault tolerant spanners for general graphs[END_REF], which is based on the sampling technique of [START_REF] Thorup | Approximate distance oracles[END_REF]. We make the observation that this algorithm can run in O(k) rounds. Let us briefly recall the construction of [CLPR10, p. 3415].

To each vertex w of G is associated a tree rooted at w spanning the cluster of w, a particular subset of vertices denoted by C(w). The construction of C(w) is a refinement over the one given in [START_REF] Thorup | Approximate distance oracles[END_REF]. The main difference is that the clusters' depth is no more than k edges. The spanner is composed of the union of all such cluster spanning trees. The total number of edges is O(kn 1+1/k log 1-1/k n). It is proved in [START_REF] Chechik | Fault tolerant spanners for general graphs[END_REF] that for every edge uv of G, there is a cluster C(w) containing u and v. The path of the tree from w to one of the end-point has at most k -1 edges and cost (k -1) • ω(uv), and the path from w to the other end-point has at most k edges and cost k • ω(uv). This is therefore a (2k -1)-hop spanner.

The random sampling of [START_REF] Thorup | Approximate distance oracles[END_REF] can be done without any round of communications, each vertex randomly select a level independently of the other vertices. Once the sampling is performed, the clusters and the trees can be constructed in O(k) rounds as their the depth is at most k.

Fault tolerant spanners

The algorithm of [START_REF] Dinitz | Fault-tolerant spanners: Better and simpler[END_REF] for constructing fault tolerant spanners is randomized and generic. It takes as inputs a weighted graph G with n vertices, a parameter r 0, and any algorithm A computing an s-spanner of m(ν) edges for any ν-vertex subgraph of G. With high probability, it constructs for G an r-fault tolerant s-spanner of size O(r 3 • m(2n/r) • log n). It works as follows: Set H := ∅, and repeat independently O(r 3 log n) times:

(1) Compute a set S of vertices built by selecting each vertex with probability 1 -1/(r + 1);

(2)

H := H ∪ A(G \ S).
Then, they show that for every fault set F ⊂ V (G) of size at most r, and every edge uv, there exists with high probability a set S as computed in Step (1) for which u, v / ∈ S and F ⊆ S. As a consequence, routine A(G \ S) provides a path between u and v in G \ S (and thus also in

G \ F ) of cost s • ω(uv). If uv lies on a shortest path of G \ F , then this cost is s • d G\F (u, v).
From their construction, we have: Proposition 3 If A is a distributed algorithm constructing an s-hop spanner in t rounds, then algorithm [START_REF] Dinitz | Fault-tolerant spanners: Better and simpler[END_REF] provides a randomized distributed algorithm that in t rounds constructs w.h.p. an s-hop r-fault tolerant spanner of size O(r 3 • m(2n/r) • log n).

Proof. The resulting spanner H is s-hop since either the edge uv of G is also in H, or a path between u and v approximating ω(uv) exists in some s-hop spanner given by algorithm A. This path has no more than s edges and cost s • ω(uv).

Observe that the algorithm [DK11] consists of running in parallel q = O(r 3 log n) times independent runs of algorithm A on different subgraphs of G, each one using t rounds. Round i of all these q runs can be done into a single round of communication, so that the total number of rounds is bounded by t, not by q.

More precisely, each vertex first selects a q-bit vector, each bit set with probability 1 -1/(r + 1), its jth bit indicating whether it participates to the jth run of A. Then, q instances of algorithm A are run in parallel simultaneously by all the vertices, and whenever the algorithms perform their ith communication round, a single message concatenating the q messages is sent. Upon reception, a vertex expands the q messages and run the jth instance of algorithm A only if the jth bit of its vector is set.

The number of rounds is no more than t.

From fault tolerant to multipath spanner

Theorem 2 Let H be a s-hop (p -1)-fault tolerant spanner of a weighted graph G. Then, H is also a p-multipath ϕ(s, p)-spanner of G where ϕ(s, p) = sp • O(1 + p/s) s and ϕ(3, p) = 9p.

To prove Theorem 2, we need the following intermediate result, assuming that H and G satisfy the statement of Theorem 2.

Lemma 1 Let uv be an edge of G of weight ω(uv) that is not in H. Then, H contains a p-multipath connecting u to v of cost at most ϕ(s, p) • ω(uv) where ϕ(s, p) = sp • O(1 + p/s) s and ϕ(3, p) = 9p.

Proof. From Menger's Theorem, the number of pairwise vertex-disjoint paths between two non-adjacent vertices x and y equals the minimum number of vertices whose removal disconnects x and y. By definition of H, H \ F contains a path P F of at most s edges between u and v for each set F of at most p -1 vertices (excluding u and v). This is because u and v are always connected in G \ F , precisely by a single edge path of cost ω(uv). Consider P H the subgraph of H composed of the union of all such P F paths (so from u to v in H \ F -see Fig. 2 for an example with p = 2 and s = 5).

Vertices u and v are non-adjacent in P H . Thus by Menger's Theorem, P H has to contain a p-multipath between u and v. Ideally, we would like to show that this multipath has low cost. Unfortunately, Menger's Theorem cannot help us in this task.

Let κ s (u, v) be the minimum number of vertices in P H whose deletion destroys all paths of at most s edges between u and v, and let µ s (u, v) denote the maximum number of internally vertex-disjoint paths of at most s edges between u and v. Obviously, κ s (u, v) µ s (u, v), and equality holds by Menger's Theorem if s = n -1. Equality does not hold in general as presented in Fig. 2. However, equality holds if s is the minimum number of edges of a path between u and v, and for s = 2, 3, 4 (cf. [START_REF] László Lovász | Mengerian theorems for paths of bounded length[END_REF]).

v u

Figure 2: A subgraph P H constructed by adding paths between u and v with at most s = 5 edges and with p = 2. Removing any vertex leaves a path of at most 5 edges, so κ 5 (u, v) > 1. However, there aren't two vertex-disjoint paths from u to v of at most 5 edges, so

κ 5 (u, v) > µ 5 (u, v). Observe that µ 6 (u, v) = κ 5 (u, v) = 2.
Since not every path of at most s edges between u and v is destroyed after removing p -1 vertices in P H , we have that κ s (u, v) p. Let us bound the total number of edges in a p-multipath Q of minimum size between u and v in P H . Let r be the least number such that µ r (u, v) p subject to κ s (u, v) p. The total number of edges in Q is therefore no more than pr.

By construction of P H , each edge of P H comes from a path in H \ F of cost ω(P F ) s • d G\F (u, v) s • ω(uv). In particular, each edge of Q has weight at most s • ω(uv). Therefore, the cost of Q is ω(Q) prs • ω(uv).

It has been proved in [START_REF] Pyber | Menger-type theorems with restrictions on path lengths[END_REF] that r can be upper bounded by a function r(s, p) < p+s-2 s-2

+ p+s-3 s-2 = O(1 + p/s)
s for integers s, p, and r(3, p) = 3 since as seen earlier

κ 3 (u, v) = µ 3 (u, v). It follows that H contains a p-multipath Q between u and v of cost ω(Q) sp • O(1 + p/s) s • ω(uv) as claimed.
Proof of Theorem 2. Let x, y be any two vertices of a graph G with edge-cost function ω. We want to show δ p H (x, y) ϕ(s, p) • δ p G (x, y). If δ p G (x, y) = ∞, then we are done. So, assume that δ p G (x, y) = ω(P G ) for some minimum cost p-multipath P G between x and y in G. Note that ω(P G ) = uv∈E(P G ) ω(uv).

We construct a subgraph P H between x and y in H by adding: (1) all the edges of P G that are in H; and (2) for each edge uv of P G that is not in H, the p-multipath Q uv connecting u and v in H as defined by Lemma 1.

The cost of P H is therefore:

ω(P H ) = uv∈E(P H ) ω(uv) =   uv∈E(P G )∩E(H) ω(uv)   +   uv∈E(P G )\E(H) ω(Q uv )   .
By Lemma 1, ω(Q uv ) ϕ(s, p) • ω(uv). It follows that:

ω(P H ) ϕ(s, p) • uv∈E(P G ) ω(uv) = ϕ(s, p) • ω(P G ) = ϕ(s, p) • δ p G (x, y)
as ϕ(s, p) 1 and by definition of P G . Clearly, all edges of P H are in H. Let us show now that P H contains a p-multipath between x and y. We first assume x and y are non-adjacent in P H . By Menger's Theorem applied between x and y in P H , if the removal of every set of at most p -1 vertices in P H does not disconnect x and y, then P H has to contain a p-multipath between x and y.

Let S be any set of less than p -1 faults in G. Since P G is a p-multipath, P G contains at least one path between x and y avoiding S. Let's call this path Q. For each edge uv of Q not in H, Q uv is a p-multipath, so it contains one path avoiding S. Note that Q uv may intersect Q wz for different edges uv and wz of Q. If it is the case then there is a path in Q uv ∪ Q wz from u to z (avoiding v and w), assuming that u, v, w, z are encountered in this order when traversing Q. Overall there must be a path connecting x to y and avoiding S in the subgraph (Q ∩ H) ∪ uv∈Q\H Q uv . By Menger's Theorem, P H contains a p-multipath between x and y.

If x and y are adjacent in P H , then we can subdivide the edge xy into the edges xz and zy by adding a new vertex z. Denote by P H this new subgraph. Clearly, if P H contains a p-multipath between x and y, then P H too: a path using vertex z in P H necessarily uses the edges xz and zy. Now, P H contains a p-multipath by Menger's Theorem applied on P H between x and y that are non-adjacent.

We have therefore constructed a p-multipath between x and y in H of cost at most

ω(P H ) ϕ(s, p) • δ p G (x, y). It follows that δ p H (x, y) ϕ(s, p) • δ p G (x, y) as claimed.
Theorem 1 is proved by applying Theorem 2 to the construction of Proposition 3, which is based on the distributed construction of s-hop spanners given by Proposition 2. Observe that the number of edges of the spanner is bounded by

O(kp 3 • m(2n/p) • log n) = O(kp 2-1/k n 1+1/k log 2-1/k n).

Bi-path Spanners

In this section we concentrate our attention on the case p = 2, i.e., 2-multipath spanners or bi-path spanners for short. Observe that for p = k = 2 the stretch is ϕ(3, 2) = 18 using our first construction (cf. Theorems 1 and 2). We provide in this section the following improvement on the stretch and on the number of edges.

Theorem 3 Every weighted graph with n vertices and maximum edge-weight W has a 2-multipath (2, O(W ))-spanner of size O(n3/2 ) that can be constructed in O(n4 ) time.

While the construction shown earlier was essentially working on edges, the approach taken here is more global. Moreover, this construction essentially yields an additive stretch whereas the previous one is only multiplicative. Note that a 2-multipath between two nodes u and v corresponds to an elementary cycle. We will thus focus on cycles in this section.

An algorithm is presented in Section 3.1. Its running time and the size of the spanner are analyzed in Section 3.2, and the stretch in Section 3.3.

Construction

Classical spanner algorithms combines the use of trees, balls, and clusters. These standard structures are not suitable to the graph metric δ 2 since, for instance, two nodes belonging to a ball centered in a single vertex can be in two different bi-components 3 and therefore be at an infinite cost from each other. We will adapt theses standard notions to structures centered on edges rather than vertices.

Consider a weighted graph G and with an edge uv that is not a cut-edge 4 . Let us denote by G[uv] the bi-component of G containing uv, and by δ 2 H (uv, w) the minimum cost of a cycle in subgraph H passing through the edge uv and vertex w, if it exists and ∞ otherwise.

We define a 2-path spanning tree of root uv as a minimal subgraph T of G such that every vertex w of G[uv] belongs to a cycle of T containing uv. Such definition is motivated by the following important property (see Property 1 in Section 3.3): for all vertices a, b in ,b). This can be seen as a triangle inequality like property.

G[uv]\{u, v}, δ 2 G (a, b) δ 2 T (uv, a)+δ 2 T (uv
If δ 2 T (uv, w) = δ 2 G (uv, w) for every vertex w of G[uv], T is called a shortest 2-path spanning tree. An important point, proved in Lemma 2 in Section 3.2, is that such T always exists and contains O(ν) edges, ν being the number of vertices of G[uv].

In the following we denote by B 2 G (uv, r) = w : δ 2 G (uv, w) r and B G (u, r) = {w : d G (u, w) r} the 2-ball (resp. 1-ball ) of G centered at edge uv (at vertex u) and of radius r. We denote by N G (u) the set of neighbors of u in G. We denote by BFS(u, r) any shortest path spanning tree of root u and of depth r (not counting the edge weights). Finally, we denote by SPST 2 G (uv) any shortest 2-path spanning tree of root uv in G[uv]. The spanner H is constructed with Algorithm 1 from any weighted graph G having n vertices and maximum edge weight W . Essentially, the main loop of the algorithm selects an edge uv from the current graph lying at the center of a dense bi-component, adds the spanner H shortest 2-path spanning tree rooted at uv, and then destroys the neigborhood of uv.

F := G, H := (∅, ∅); while ∃uv ∈ E(G), |B 2 G (uv, 4W ) ∩ (N G (u) ∪ N G (v))| > √ n do H := H ∪ SPST 2 F (uv) ∪ BFS G (u, 2) ∪ BFS G (v, 2); G := G \ (B 2 G (uv, 4W ) ∩ (N G (u) ∪ N G (v))) H := H ∪ G Algorithm 1: Construction of H.

Size analysis

The proof of the spanner's size is done in two steps, thanks to the two next lemmas. First, Lemma 2 shows that the while loop does not add too much edges: a shortest 2-path spanning tree with linear size always exists. It is built upon the algorithm of Suurballe-Tarjan [START_REF] Suurballe | A quick method for finding shortest pairs of disjoint paths[END_REF] for finding shortest pairs of edge-disjoint paths in weighted digraphs.

Lemma 2 For every weighted graph G and for every non cut-edge uv of G, there is a shortest 2-path spanning tree of root uv having O(ν) edges where ν is the number of vertices of G[uv]. It can be computed in time O(n 2 ) where n is the number of vertices of G.

Proof. In the following, we call X = G[uv]. SPST 2 X (uv) will therefore be equal to

SPST 2 G (uv). Let ν = |V (X)| and µ = |E(X)|.
We first show that we can reduce our problem to finding a one-to-all pair of edge-disjoint paths in a directed graph. In other words, let P be a procedure which yields a 2-(edge-disjoint)-tree rooted in a single vertex w in a directed graph X . We show we can derive P which yields SPST 2 X (uv) from P. First, remark that the problem of finding SPST 2 X (uv) is equivalent to finding the same structure but rooted in a single vertex w where the edge uv is replaced by uw, wv, and the weights of each edge uw and wv being equal to half of ω(uv).

We construct X as follows: each undirected edge is replaced by two edges going in opposite direction and of same weight. Then each vertex a is replaced by two vertices a 1 and a 2 where every incoming edge arrives at a 1 and every leaving edge leaves from a 2 . An edge going from a 1 to a 2 is finally added. Fig. 3 shows what happens to edges of X.

Note that ν = |V (X )| = 2 • (ν + 1) and µ = |E(X )| = 2 • (µ + 1) + ν + 1.
The procedure P proceeds as follows:

1. uv is replaced by uw, wv.

2. X is constructed.

3. P is called on X , with the root vertex being w 2 .

4. Every edge of type x 2 → y 1 present in the result of P causes the addition of the edge xy to the result of P .

Two edge-disjoint paths in X are vertex-disjoint in X. Indeed, as they cannot both use an edge of the type x 1 → x 2 they cannot share x 1 or x 2 (except at the extremities) because the only way to leave (resp. arrive) from x 1 (resp. to x 2 ) is to use the edge x 1 → x 2 . So if we have two edge-disjoint paths in X going from w 2 to some x 1 , the reduction back to X will yield two disjoint paths from w to x, and then from the edge uv to x.

The procedure P was devised by Suurballe-Tarjan in [START_REF] Suurballe | A quick method for finding shortest pairs of disjoint paths[END_REF]. While not directly constructing the 2-(directed-edge-disjoint)-tree rooted in a single vertex w it can be extracted from their algorithm. Roughly speaking, the construction results of two shortest-path spanning trees computed with Dijkstra's algorithm. The 2 paths (from the source to every vertex v) are reconstructed via a specific procedure. This latter can be analyzed so that the number of edges used in the 2-(directed-edge-disjoint)-tree is at most 2(ν -1): the structure Suurballe-Tarjan constructed is such that all vertices, but the source, have two parents.

Therefore the number of edges yielded by procedure P is at most 4 • ν, which is O(ν).

Secondly, Lemma 3 shows that the graph G remaining after the while loop has only O(n 3/2 ) edges. For that, G is transformed as an unweighted graph (edge weights are set to one) and we apply Lemma 3 with k = 2. The result we present is actually more general and interesting in its own right. Indeed, it gives an alternative proof of the well-known fact that graphs with no cycles of length 2k have O(n 1+1/k ) edges since B 2 G (uv, 2k) = ∅ in that case.

Lemma 3 Let G be an unweighted graph with n vertices, and k 1 be an integer. If for every edge uv of

G, |B 2 G (uv, 2k) ∩ N G (u)| n 1/k , then G has at most 2 • n 1+1/k edges.
Proof. Consider Algorithm 2 applied to graph G. When the procedure terminates, all the vertices and edges of the graph have been removed. In the following, we count the number of edges removed by each step of the while loop, which in turn allows us to bound the number of total edges of G.

for i := k -1 to 0 do while ∃u, |B G (u, i)| n i/k do G := G \ B G (u, i)
Algorithm 2: Remove 1-balls.

Let X i denote the set of vertices u whose 1-ball B G (u, i) is removed during iteration i of the for loop. Let m(u) be the number of edges erased when removing B G (u, i). Note that as i u∈Xi |B G (u, i)| = n (the procedure removed all the vertices), and that

i |X i | • n i/k n because each 1-ball is larger than n i/k .
At each step, we argue that

m(u) (n 1/k + 1) • |B G (u, i)| + |N G (u, i + 1)|
where N G (u, i + 1) is the set of vertices at exactly i + 1 hops from u.

To this effect, let's consider a shortest path tree T rooted in u and spanning B G (u, i).

The number of edges in T is bounded by

|B G (u, i + 1)|, which can be decomposed in |B G (u, i)| + |N G (u, i + 1)|.
We can also bound the total number of non-tree edges as follows: for any

x ∈ B G (u, i), let's consider B 2 G (xy, 2k) ∩ N G (x)
, where y is the parent of x in T . We know that the number of vertices in this 2-ball is less than

n 1/k because it is a property of G. But |B 2 G (xy, 2k) ∩ N G (x)
| is also at least the number of non-tree edges attached to x: for an edge xz / ∈ T , the paths from z towards the root u and from x towards the root until they reach common vertex are of length at most the radius of B G (u, i), which is i k, and so there is a cycle of length at most 2k using the edges xz and xy. So the total number of non-tree edges is bounded by

n 1/k • |B G (u, i)|.
The termination of the while loop during iteration i + 1 implies

|B G (u, i + 1)| < n i+1 k
or equivalently:

|N G (u, i + 1)| < n i+1 k -|B G (u, i)| Therefore we have m(u) < n 1/k |B G (u, i)| + n 1+i k And so m(G) = u∈∪iXi m(u) < n 1/k i u∈Xi |B G (u, i)| + i |X i | • n i+1 k and as i |X i | • n i/k n, we have |E(G)| 2 • n 1+1/k .
Combining these two lemmas we have:

Lemma 4 Algorithm 1 creates a spanner of size O(n 3/2 ) in time O(n 4 ).

Proof. Each step of the while loop adds O(n) edges from Lemma 2, and as it removes at least √ n vertices from the graph this can continue at most √ n times. In total the while loop adds O(n 3/2 ) edges to H. After the while loop, the graph G is left with every

B 2 G (uv, 4W ) ∩ (N G (u) ∪ N G (v)) smaller than √ n.
If we change all edges weights to 1, it is obvious that every B 2 G (uv, 4)

∩ (N G (u) ∪ N G (v)) is also smaller than √ n. Then as B 2 G (uv, 4) ∩ N G (u) is always smaller than B 2 G (uv, 4) ∩ (N G (u) ∪ N G (v)
) we can apply Lemma 3 for k = 2, and therefore bound the number of edges added in the last step of Algorithm 1.

The total number of edges of H is O(n 3/2 ).

The costly steps of the algorithm are the search of suitable edges and the cost of construction of SPST 2 .

The search of suitable edges is bounded by the number of edges as an edge e which is not suitable can be discarded for the next search: removing edges from the graph cannot improve B 2 G (e, 4W ). Then for starting from one extremity of each edge a breadth first search of depth 3 must be computed, keeping only the vertices whose path in the search encounters the other extremity. The cost of the search is bounded by the number of edges of G. So in the end the search costs at most O(n 4 ).

The cost of building a SPST 2 is bounded by the running time of [START_REF] Suurballe | A quick method for finding shortest pairs of disjoint paths[END_REF], which at worst costs O(n 2 ) (the reduction is essentially in O(m + n)). Since the loop is executed at most √ n times, the total cost is O(n 7/2 ).

So the total running time is O(n 4 ).

Stretch analysis

The proof for the stretch is done as follows: we consider a, b two vertices such that δ 2 F (a, b) = is finite (if it is infinite there is nothing to prove). We need to prove that the spanner construction is such that at the end, δ 2 H (a, b) 2 + O(W ) . To this effect, we define P F = P 1 F ∪ P 2 F as a cycle composed of two disjoint paths (P 1 F and P 2 F ) going from a to b such that its weight sums to δ 2 F (a, b). Proving the stretch amounts to show that there exists a cycle P H = P 1 H ∪ P 2 H joining a and b in the final H, with cost at most 2 + O(W ) . Observe that if the cycle P F has all its edges in H then one candidate for P H is P F and we are done. If not, then there is at least one 2-ball whose deletion provokes actual deletion of edges from P F (that is edges of P F missing in the final H).

In the following, let uv be the root edge of the first 2-ball whose removal deletes edges from P F (that is they are not added in H neither during the while loop nor the last step of the algorithm). Let G i be the graph G just before the removal of B 2 G (uv, 4W ) ∩ (N G (u) ∪ N G (v)) , and G i+1 the one just after. The rest of the discussion is done in G i otherwise noted. The proof is done as follows: we first show in Lemma 5 that any endpoint of a deleted edge (of P F ) belongs to an elementary cycle comprising the edge uv and of cost at most 6W . We then show in Lemma 6 that we can construct cycles using a and/or b passing through the edge uv, effectively bounding δ 2 H (uv, a) and δ 2 H (uv, b) due to the addition of the shortest 2-path spanning tree rooted at uv. Finally we show in Lemma 7 that the union of a cycle passing through uv and a and another one passing through uv and b contains an elementary cycle joining a to b, its cost being at most the sums of the costs of the two original cycles.

Lemma 5 Let e = wt be an edge of (G i \ G i+1 ) \ H. Then in G i both w and t are connected to uv by a cycle of cost at most 6W . Proof. Since e isn't present neither in G i+1 nor H, then at least one of its endpoints is in the vicinity of u or v in G i . W.l.o.g. we can consider t be a neighbour of u in G i . w is then at most two hops from uv in G i . The rest of the discussion is done in G i . We can first eliminate the case where w is a direct neighbor of v, as there is an obvious cycle of 4 hops:

w → t → u → v → w .
Consider now the BFS tree rooted at u that is added to H. As w is at two hops at most from u there is a path u → x → w in this tree (x is defined as the intermediate vertex of this path and may not exist). As e was removed, it means that x is distinct from t. Furthermore, t was removed because it belonged to a B 2 (uv, 4W ), so there is an elementary cycle of at most 4 hops passing through t and the edge uv.

Now we distinguish two cases as illustrated by Fig. 4. If x is distinct (which is especially true when it does not exist) from an intermediate vertex between v and t in the cycle, then we can extract an elementary cycle of at most 6 hops passing through uv and w :

w → x → u → v →→ t → w.
If x is the same as an intermediate vertex between v and t, then the cycle is w

→ t → u → v → x → w.
We now show that we can use this lemma to exhibit cycles going from a to uv and from b to uv.

From the vertices belonging to both B 2 Gi (uv, 6W ) and P F we choose the ones which are the closest from a and b (we know that at least two of them exist because one edge was removed from P F during step i of the loop). There are at maximum four of them (a 1 , a 2 , b 1 , b 2 ), one for each sub-path P i F and each extremity {a, b}. Note that each extremity is connected to the root edge by an elementary cycle of cost at most 6W . Two cases are possible (the placement of the vertices can be seen on Fig. 5, although the paths on it are from the proof of lemma 7):

Case 1: There are only two extremities (then they belong to the same subpath) and their cycles which connect them to uv do not intersect the second subpath (w.l.o.g we can suppose it is a 1 and b 1 ).

Case 2: There are more than two extremities: either some edges of the second path were removed or one Property 1 Let uv be a non cut-edge of G and T be any 2-path spanning tree rooted at uv. Then, for all vertices a, b in G

[uv] \ {u, v}, δ 2 G (a, b) δ 2 T (uv, a) + δ 2 T (uv, b) -ω(uv).
Proof. There is in T a cycle joining a to uv of cost δ 2 T (uv, a), and another one joining b to uv of cost δ 2 T (uv, b). Consider the subgraph P containing only the edges from these two cycles. The cost of P is ω(P ) δ 2 T (uv, a) + δ 2 T (uv, b) -ω(uv) as edge uv is counted twice. It remains to show that P contains an elementary cycle between a and b. Note that since a / ∈ {u, v}, a has in P two vertex-disjoint paths leaving a and excluding edge uv: one is going to u, and one to v. Similarly for vertex b.

W.l.o.g. we can assume that a and b are not adjacent in P . Otherwise we can subdivide edge ab to obtain a new subgraph P . Clearly, if P contains an elementary cycle between a and b, then P too. Consider that one vertex z, outside a and b, is removed in P . From the remark above, in P \ {z}, there must exists a path leaving a and joining some vertex Lemma 8 H is a 2-multipath (2, 24W )-spanner.

Proof. If there is in F a path of cost δ 2 (a, b) such that every edge of it is in H, then there is nothing to prove. If there is some removed edge, then we can identify the loop order i which removed the first edge, and we can associate the graph G i just before the deletion performed in the second step of the loop (so P F still completely exist in G i ). By virtue of Lemma 5 we can identify some root-edge uv and we know that there are some vertices of P F linked to uv by an elementary cycle of length at most 6W . Lemma 7 can then be applied, and so in G i , δ 2 Gi (a, uv) and δ 2 Gi (b, uv) are both bounded by δ 2 Gi (a, b) + 12W . As the loop's first step is to build a shortest 2-path spanning tree rooted in uv we know that in H

Conclusion

We have introduced a natural generalization of spanner, the vertex-disjoint path spanners. We proved that there exists for multipath spanners a size-stretch trade-off similar to classical spanners. We also have presented a O(k) round distributed algorithm to construct p-multipath kp • O(1 + p/k) 2k-1 -spanners of size Õ(p 2 n 1+1/k ), showing that the problem is local : it does not require communication between distant vertices.

Our construction is based on fault tolerant spanner. An interesting question is to know if better construction (in term of stretch) exists as suggested by our alternative construction for p = 2.

The most challenging question is to explicitly construct the p vertex-disjoint paths in the p-multipath spanner. This is probably as hard as constructing efficient routing algorithm from sparse spanner. We stress that there is a significant difference between proving the existence of short routes in a graph (or subgraph), and constructing and explicitly describing such short routes. For instance it is known (see [START_REF] Gavoille | Sparse spanners vs. compact routing[END_REF]) that sparse spanners may exist whereas routing in the spanner can be difficult (in term of space memory and stretch of the routes).

Figure 3 :

 3 Figure 3: Process by which X is transformed into X .

Figure 4 :Figure 5 :

 45 Figure 4: Proof of Lemma 5: a cycle of 6 hops exists between w and uv in G i

  w a ∈ {u, v} \ {z} and one path leaving b and joining some vertex w b ∈ {u, v} \ {z}. If w a = w b , then a and b are connected in P \ {z}. If w a = w b , then edge uv belongs to P \ {z} since in this case z / ∈ {u, v}, and thus a path connected a to b in P \ {z}. By Menger's Theorem, P contains a 2-multipath between a and b.

  δ 2 H (a, uv) δ 2 Gi (a, uv) δ 2 Gi (a, b) + 12Wand the same for b. Property 1 can then be used in the 2-path spanning tree, to bound δ 2 H (a, b):δ 2 H (a, b) δ 2 H (a, uv) + δ 2 H (b, uv) 2 • δ 2 Gi (a, b) + 24WFinally, as in G i P F still exists completely, we have thatδ 2 Gi (a, b) = δ 2 F (a, b), so δ 2 H (a, b) 2 • δ 2 F (a, b) + 24W

  Figure 1: A weighted graph G composed of a cycle of n + 1 vertices plus n -1 extra edges, and a spanner H = G \ {uv}. Edge uv has weight 1, non-cycle edges have weight s, and cycle edges weight s/n so that d H (u, v) = s. Removing any vertex z / ∈ {u, v} implies d G\{z} (u, v) = 1 and d H\{z} (u, v) = 2s(1 -1/n). For other pairs of vertices x, y, d H\{z} (x, y)/d G\{z} (x, y) < 2s. Thus, H is a 1-fault tolerant 2s-spanner.

	However δ 2 H (u, v)/δ 2 G (u, v) sn/s. Thus, H is a 2-multipath spanner with stretch at least n.

For each edge uv in non-decreasing order of their weights, add it to the spanner if d H (u, v) > s • d G (u, v).

A short for 2-vertex-connected components.

A cut-edge is an edge that does not belong to a cycle.

Supported by the European project "EULER", the ANR project "ALADDIN", and the équipe-projet INRIA "CÉPAGE". Member of the "Insitut Universitaire de France". Supported by the european project "EULER", the ANR project "ALADDIN", and the équipe-projet INRIA "CÉPAGE". Supported by the European project "EU-LER", the ANR project "ALADDIN", and the équipe-projet INRIA "GANG".

1 Tilde-O notation is similar to Big-O up to poly-logarithmic factors in n.

Figure 6: The two cases for Q 1 and Q 2 . The big dots represent the paths' unused portions.

of the cycles going from one of the extremities a 1 or b 1 to uv intersects the second path.

We show next that we can bound δ 2 H (uv, a) and δ 2 H (uv, b) with the help of the cycles connecting the endpoints and the path P G . This is done with the two next lemmas.

Lemma 6 For any two vertices joined to the same edge uv by elementary cycles there is a simple path of cost at most the sum of the cycles' costs and passing through the edge uv.

Proof. Let us call w and t the two vertices. We will show there is a simple path going from w to t passing through uv. Let us call Q 1 the elementary cycle joining w to uv and Q 2 the one joining t to uv. If by following Q 1 to reach from w one of the endpoints of uv we do not encounter Q 2 , then the path from w to t is composed of the part of Q 1 , then the edge uv, then the part of Q 2 which reaches t without passing through uv. If it is not possible, then there are intersection points between Q 1 and Q 2 . Let i be the closest intersection point from w. The path we are looking for is therefore w → i using Q 1 then i → uv → t using the part of Q 2 which uses the edge uv (the other part would take us directly to a 2 whithout using uv). This path is simple because Q 2 is an elementary cycle and it cannot cross Q 1 before i because of the way i is chosen. The two cases are shown on figure 6.

Lemma 7 Let a, b be two vertices such that an elementary cycle of cost δ 2 (a, b) has common vertices with some B 2 (uv, 6W ). Then δ 2 (a, uv) and δ 2 (b, uv) are bounded by δ 2 (a, b) + 12W

Proof. The lemma is independent of the graph, but for clarity it will be proved using the graph G i and P F .

Recall that we distinguished two cases depending on whether B 2 Gi (uv, 6W ) intersects only one path of P F (either P 1 F or P 2 F ) or both. Fig. 5 illustrates the proof of the two cases. Lemma 6 allows us to solve the first case : since there are no intersection on the second path, the cycle

and so is δ 2 Gi (uv, b). In the second case there are three or four extremities: a 1 , b 1 , a 2 and b 2 , with possibly a 2 and b 2 being the same vertex. We can apply Lemma 6 twice: once between a 1 and a 2 and another time between b 1 and b 2 . These create a simple cycle from a to uv passing by a 1 and a 2 and another one from b to uv passing by b 1 and b 2 . We know the cycles are simple because the vertices were chosen to be the closest from a or b. Note that a 2 and b 2 can be the same. So δ 2 Gi (a, uv) ω(a → a 1 ) + 12W + ω(a 2 → a) δ 2 (a, b) + 12W and the same for b.


Luis Patino

Hamid Benhadda

Nedra Nefzi

Bernard Boulay

François Bremond

Monique Thonnat

Abnormal behavior detection in video protection systems

In this work we present a system to extract in an unsupervised manner the main activities that can be observed by a camera monitoring a scene on the long-term and with the ultimate aim to discover abnormal events. To allow for semantically interpretable results, the activities are characterised by referring them to contextual elements of the observed scene. By contextual elements, we understand activity areas such as building entrances, people meeting areas, road areas,...etc. The system thus stars in a first step by the unsupervised learning of the main activity areas of the scene. We employ trajectory-based analysis of mobiles in the video to discover the points of entry and exit of mobiles appearing in the scene and ultimately deduce the different areas of activity. In a second step, mobile objects are then characterised in relation to the learned activity areas. Two kind of behaviours can then be defined either 'staying in a given activity zone' or 'transferring from an activity zone to another' or a sequence of the previous two behaviours. In a third step we employ a high-level clustering algorithm to group mobiles according to their behaviours and discover both, frequent/normal behaviours and unusual/abnormal events. We employ soft computing techniques in the first two steps to handle the uncertainty inherently present in low-level trajectory data. The high-level clustering algorithm is based on relational analysis methodology. We have applied our system in two domains, the monitoring of activities in the hall entrance of an underground station and to traffic control by monitoring a bus reserved street lane. We show that our current results are encouraging.

Introduction

Nowadays with the increasingly growing needs of protection of people and personal properties, video surveillance has become a big concern of everyday life. A consequence of these needs has led to the proliferation of cameras almost everywhere. Combining these facts with the ease and cheapness of data collection and storage, the video surveillance systems can collect huge amounts of video data that can be very useful for investigation purposes of events occurrence or for the needs of predictions in order to improve these systems themselves.

Paradoxically, these data become virtually unusable for analysis because of their hugeness, hence the need of intelligent analysis systems able to help the end user by, at least semi-automating the data processing analysis. In this paper, we will use clustering techniques to gather similar behaviours and/or trajectories in the same clusters to help the end user finding more rapidly the most important events of interest.

The remainder of this paper is as follows. In the following section, we give a short overview of the related work. Some preliminary steps for data processing are given in section 3. The methodology for activity extraction is presented in section 4; the experimental results are to be found in section 5. Finally, Section 6 draws the main conclusions and describes some perspectives.

Related Work

Extraction of the activity contained in the video by applying data-mining techniques represents a field that has only started to be addressed. Although the general problem of unsupervised learning has been broadly studied in the last couple of decades, there are only a few systems which apply them in the domain of behaviour analysis. A few systems employ soft computing techniques to characterize video activity patterns [START_REF] Doulamis | A fuzzy video content representation for video summarization and content-based retrieval[END_REF][START_REF] Lee | Activity and Location Recognition Using Wearable Sensors[END_REF] but the methodology to self-discover new activities is still missing. Because of the complexity to tune parameters or to acquire knowledge, most systems limit themselves to object recognition [START_REF] Dalal | Human detection using oriented histograms of flow and appearance[END_REF]. For behaviour recognition, three main categories of learning techniques have been investigated.

• The first class of techniques learns the parameters of a video understanding program. These techniques have been widely used in case of event recognition methods based on neural networks [START_REF] Foresti | Event classification for automatic visualbased surveillance of parking lots[END_REF], Bayesian classifiers and HMMs [START_REF] Lv | Left luggage detection using bayesian inference[END_REF][START_REF] Wilson | Hidden Markov models for modeling and recognizing gesture under variation[END_REF].

• The second class consists in using unsupervised learning techniques to deduce abnormalities from the occurring events [START_REF] Xiang | Video behaviour profiling and abnormality detection without manual labelling[END_REF].

• The third class of methods focuses on learning behaviour based on trajectory analysis. This class is the most popular learning approach due to its effectiveness in detecting normal/abnormal behaviours; for instance, on abnormal trajectory detection on roads [START_REF] Piciarelli | Trajectory clustering and its applications for video surveillance[END_REF][START_REF] Stauffer | Learning patterns of activity using real-time tracking[END_REF] or pedestrian trajectory characterisation [START_REF] Anjum | Single camera calibration for trajectory-based behavior analysis[END_REF]. Hidden Markov Models (HMM) have also been employed to detect different states of pre-defined normal behaviour [START_REF] Bashir | Object Trajectory-Based Activity Classification and Recognition Using Hidden Markov Models[END_REF][START_REF] Porikli | Learning object trajectory patterns by spectral clustering[END_REF]. Our main contribution to the state of the art is to employ trajectory information to automatically learn activity zones and generate from them behaviour/event information. Trajectoty and event information analysed together can make visible important activity patterns difficult to see in the raw data.

Data preprocessing

In order to discover meaningful activity, it is of prime importance to have available detailed information allowing to detect the different possible interactions between mobiles. As our system is based on trajectory analysis, the first step to prepare the data for the activity clustering methodology is to extract tracklets of fairly constant speed allowing to characterise the displacements of the mobile or its stationary state. Describing the detection and tracking algorithm is out of the scope of the paper. Suffices to say background substraction and a Kalman filter-based tracker (KLT) are employed to extract mobile trajectories.

If the dataset is made up of N objects, the trajectory tr j for object O j in this dataset is defined as the set of points [x j (t), y j (t)] corresponding to their position points; x and y are time series vectors whose length is not equal for all objects as the time they spend in the scene is variable. The instantaneous speed for that mobile at point [x j (t), y j (t)] is then v (t) = ẋ (t)

2 + ẏ (t)

2 1 2
. The objective is then to detect those points of changing speed allowing to segment the trajectory into tracklets of fairly constant speed so that the trajectory can be summarised as a series of displacements at constant speed or in stationary state.

The mobile object time series speed vector is analysed in the frame of a multiresolution analysis of a time series function v (k) with a smoothing function, ρ 2 s (k) = ρ (2 s k), to be dilated at different scales s. In this frame, the approximation A of v (k) by ρ is such that A 2 s-1 v is a broader approximation of A 2 s v. By analyzing the time series v at coarse resolutions, it is possible to smooth out small details and select those points associated with important changes.

The speed change points are then employed to segment the original trajectory tr j into a series of i tracklets tk. Each tracklet is defined by two key points, these are the beginning and the end of the tracklet, [x i j (1), y i j (1)] and [x i j (end), y i j (end)]. By globally reindexing all tracklets, let m be the number of total tracklets extracted, we obtain the following tracklet feature vector :

tk m = [x m (1), y m (1), x m (end), y m (end)] (1)

Activity Analysis and Clustering

We understand activity as the interactions occurring between mobile objects themselves and those between mobiles and the environment. We employ trajectorybased analysis of mobiles in the video to discover the points of entry and exit of mobiles appearing in the scene and ultimately deduce the different areas of activity. In a second step, mobile objects are then characterised in relation to the learned activity areas. In a third step we employ a high-level clustering algorithm to group mobiles according principally to their behaviours and discover both, frequent/normal behaviours and unusual/abnormal events. We employ soft computing techniques in the first two steps to handle the uncertainty inherently present in low-level trajectory data. The high-level clustering algorithm is based on relational analysis methodology.

Unsupervised learning of activity areas

Modeling the spatial context of the scene is essential for recognition and interpretation of activity. Because it is not possible to define a-priori all activity zones, manually defined Contextual zones do not suffice to describe all possible situations or evolving actions in the monitored scene. We thus propose to learn the complementary activity zones.

The feature vector defined in equation 1 constitute a set of simple descriptors that have proven experimentally to be enough to describe activities in a large variety of domains (such as traffic monitoring, subway control, monitoring smart environments), mainly because they define where the object is coming from and where it is going to and also with approximative constant speed.

In our system, mobiles starting (or ending up) their displacement at nearby positions are seen to share a common activity area. Finding thus the activity areas on the scene could be seen as an equivalent task of clustering entry/exit tracklet points. Different common clustering algorithms such as k-means, Self Organising Maps, etc... can be used but the drawback is, first, the number of clusters must be known in advance, and second, the spatial morphology of the resulting clusters is always circular, which may not correspond to the real scene topology. In our approach, we propose to find first high resoluted (small in size) entry/exit activity zones, which in a second step could be further regrouped to obtain broader activity zones (following an hierarchical agglomerative algorithm).

Clustering of tracklet entry/exit points For this first step, we employ the well-known clustering Leader algorithm [START_REF] Hartigan | Clustering algorithms[END_REF]. It has the advantage to work on-line without needing to specify the number of clusters in advance. In this method, it is assumed that a threshold T is given. The algorithm constructs a partition of the input space (defining a set of clusters) and a leading representative for each cluster, so that every object in a cluster is within a distance T of the leading object. The threshold T is thus a measure of the diameter of each cluster. The algorithm makes one pass through the dataset, assigning each object to the cluster whose leader is the closest and making a new cluster, and a new leader, for objects that are not close enough to any existing leaders. Defining T is application dependent. In this work we have employed the threshold setting suggested by [START_REF]Incremental learning on trajectory clustering[END_REF].

Let's consider the position of a mobile is L(x,y), its influential zone, Zn, is defined by a radial basis function (RBF) centered at the position L; and the belonginess of a new point p(x,y) to that zone is given by:

Zn(L, p) = φ(L, p) = exp(-p -L 2 T 2 ) (2)
The RBF function has a maximum of 1 when its input is p = L and thus acts as a similarity detector with decreasing values outputted whenever p strides away from L. An object element will be included into a cluster Zn if Zn(L, p) ≥ 0.5, which is a natural choice. The cluster receptive field (hyper-sphere) is controlled by the learnt parameter T Merging tracklet entry/exit zones We find the final activity areas by aggregating similar entry/exit tracklet zones. We look to establish a similarity relation between the different zones defined by the tracklets. On the end, new zones are given by the fulfillment of two relations: 1) zone Zn i overlaps zone Zn j , and 2) zone Zn j does not overlap any a-priori user-defined contextual Zone Zctx q . These relations are defined:

R1 ij : Zone Zn i overlaps Zone Zn j R1 ij = 3 k=1   (x,y)∈(X ik ,Y ik ) Zn j (x, y)   (3)
and

X ik = n (k+1) 3 T cos (θ) + Li(1) o , Y ik = n (k+1) 3 T sin (θ) + Li(2) o with θ = 0, ..., π 8 , ..., 2π
That is, points (x, y) ∈ (X ik , Y ik ) belonging to concentric circles to L i are tested to verify how they fit Zn j in order to calculate the overlap/similarity between Zn i and Zn j . This allows avoiding equity problems with clusters defined on sparse regions (some clusters may be defined with a much larger number of points than others).

R2 iq : Zone Zn i overlaps Zone Zctx q R2 iq = 3 k=1   (x,y)∈(X ik ,Y ik ) Zctx q (x, y)   (4)
It is possible to transform R2 into a new relation, R3, which links Zn i and Zn j if both clusters are related to the same Zone Zctx q through the fulfillment of R2. The relation between Zn i and Zn j is then given by

R3 ij = max q min [R2 iq , R2 qj ] (5)
Remark that R3, the complement to R3 given by R3 = -R3, represents the relation linking Zn i and Zn j if both clusters are not related to any contextual Zone (Zctx q ). R1 and R3 can be aggregated employing a soft computing aggregation operator such as R = R1 ∩ R3 = max 0, R1 + R3 -1 and made transitive with:

R • R (x, y) = max z min [R (x, z) , R (z, y]) (6)
R is now a transitive similarity relation with R indicating the strength of the similarity. If we define a discrimination level α in the closed interval [0,1], an αcut can be defined such that

R α (x, y) = 1 ⇔ R (x, y) α (7)
It is thus implicit that α 1 > α 2 ⇔ R α1 ⊂ R α2 ; thus, the R α form a nested sequence of equivalence relations, or from the classification point of view, R α induces a partition

π α = {Z α i } of X × Y (or X 2 ) such that α 1 > α 2 implies π α1 is a refinement of π α2 .
At this point, the difficulty comes down to select the appropriate α-cut such that π α from R α represents the best partition of the data. This is still a difficult and open issue that we choose to approach by selecting the alpha-values, which induce a significant change from π α k to π α k+1 .

To automatically detect those significant partition changes we choose to study the cluster area and number of clusters induced at each partition π α . We achieve this in the frame of a multiresolution analysis. By analysing induced partitions at coarse resolutions, it is possible to smooth out small details and select the αcut levels associated with important changes. From the monitored scene, it would be useful to distinguish among different information levels: (i) grouped activity on large spaces, (ii) very detailed individual activity, (iii) somewhere meaningful in-between the last two. For this reason, when performing activity zone discovery, we automatically select the three highest change-inducers α-cut levels from the previous analysis. The result is then that we end up with a three levels hierarchy of activity zones.

Behaviour definition

We aim at creating a system for the recognition and interpretation of human activity and behaviour, and extract new information of interest for end-users. Low-level tracking information is thus expected to be transformed into high-level semantic descriptions conveying useful and novel information. In our application, we establish a semantic meaning from the scene model built as decribed in the previous section ( 4.1). The behaviour knowledge can be thus expressed with semantic concepts, instead of using quantitative data, thanks to the learned zones and any user-defined contextual zone. Let us assume, we have in total k = 1, ..., K contextual zones on the scene defined either a-priori, or after the zone learning procedure. Two different kinds of behaviours can then be identified:

• Mobile moving from Zone Zctx k to Zone Zctx k ′ • Mobile Inside Zone Zctx k

High level activity analysis

To perform deep high level activities analysis that are not easy to highlight from the raw video data we will try to exhibit complex and hidden correlations between the mobile objects in the video scenes on one hand and between the mobile objects and contextual objects on the other hand. To reach this goal we will use relational analysis clustering methodology.

Relational analysis clustering methodology

The foundations of relational analysis clustering methodology dates from the former works of Condorcet related to the voting theory in 1785 [START_REF] Condorcet | Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix[END_REF]. The concept underlying these works is based on the "consensus" or "majority" rule, which means that a decision can be considered valid as soon as it is supported by a majority of voters. This methodology is very well adapted to categorical data where the variables measured on the objects of interest can be considered as judges deciding if any two objects of the data are or are not of the same category. This methodology has been formalized for the first time as a linear programming problem P in the late eighties by Marcotorchino F. and Michaud P. [START_REF] Marcotorchino | Optimisation en analyse relationnelle des données[END_REF]. If X is a squared matrix representing the unknown final partition to be discovered and I represents the whole data set, then the mathematical formulation of the problem is :

(P)            max X C(X) x ii = 1 ∀ i ∈ I (reflexivity) x ii ′ -x i ′ i = 0 ∀ (i, i ′ ) ∈ I 2 (symmetry) x ii ′ + x i ′ i ′′ -x ii ′′ ≤ 1 ∀ (i, i ′ , i ′′ ) ∈ I 3 (transitivity) x ii ′ ∈ {0, 1} ∀ (i, i ′ ) ∈ I 2 (binarity)
where C(X) is the Condorcet's criterion defined by the relation:

C(X) = n i=1 n i ′ =1 (s ii ′ -s ii ′ )x ii ′
x ii ′ is the general term of matrix X, defined as:

x ii ′ = 1 if i and i ′ are in the same cluster of the final partition 0 otherwise s ii ′ is the number of variables (or voters) supporting "object i and object i ′ are in the same cluster of the final parition" and s ii ′ is the number of variables (or voters) supporting the opposite decision. Hence to maximise the Condorcet's criterion, two objects i and i ′ are likely to be in the same cluster of the final obtained partition as soon as (s ii ′s ii ′ ) is is strictly positive and are likely to be separated otherwise. More details about relational analysis clustering methodology can be found in [START_REF] Benhadda | L'analyse relationnelle pour la fouille de grandes bases de données[END_REF].

At the end of the process, the obtained clusters will be described by the variables modalities that have participated strongly to their constitution thanks to two indicators named ratioC and ratioD. for a cluster C and a modality j, ratioC(j) is the proportion of objects belonging to the cluster that have the modality j, and ratioD(j) is the proportion of cluster objects having modality j with regard to the whole data set objects having this modality,that is :

ratioC(j) = nj C |C| (8) ratioD(j) = nj C nj (9)
where :

nj C is the number of objects of cluster C having modality j -|C| is the cardinal of cluster C nj is the total number of objects of the whole data set having modality j

Relational analysis clustering applied to video data

There are two main types of concepts to be represented from the video and on which we perform highlevel clustering: mobile objects of the observed scene and video events occurring in the scene. For the off-line analysis of both types of concepts, and with the aim of setting the data in a suitable format to achieve knowledge discovery, this information is characterized by a set of specific features:

1. mobileid: the identifier label of the object 2. start: the time when the object is first seen. 3. end: the time when the object is last seen. 4. duration: the total time the object has been observed. (formated in seconds) 5. dist org dest: the total distance walked from origin to destination. (formated in meters) 6. mean speed: the average of the instantaneous speed calculated at all points of the detected mobile object trajectory. 7. Significant evnt: inferred event for the object considering the learned zones.

Results and Evaluation

The algorithm for unsupervised learning of activity areas (as described in section 4.1) was applied to a one hour-duration video recorded at one entrance hall from the Torino underground system. The final relation R given in equation ( 6), which verifies the transitive closure, is thresholded for different αcut values going from 0 to 0.9 and with a step value of 0.05. The algorithm automatically selects the best αcut value giving a well detailed composition of the activity areas of the scene as mentioned in section 4.1. Figure 1 presents those learned zones corresponding to the analysed video.

As mentioned in section 4.2, we achieve behaviour carachterisation by linking low-level tracking to the learned zones. The whole activity observed from the scene can then be reported following the behaviours inferred from the learned zones. For instance, for the ticket machine area (zone Zn1), the obtained report is given in table 1. Zone Zn1 is actually the second most employed one of all zones just after Zn2, wich corresponds to the main hall area (occupancy of 39.85%; not shown in table 1). Most people going to the vending machines depart from the main hall (Zn2); and all people at the vending machines go to the main hall. People directly going to the vending machines from any of the station entrances do this from entrance zones Zn5 or Zn7. In the last step towards a knowledge discovery task, we have applied the relational analysis process explained before in section 4.3. The input variables are those corresponding to the mobile object semantic table described above also in section 4.3, which in this case for the analysed video contains in total 409 detected objects. Variables are weighted so to favour the formation of as many clusters as Significant events in the table are. The interest of such procedure is to explain through other variables what characterizes each of the Significant events. After application of the relational analysis, 23 activity clusters are obtained; table 2 shows some of the obtained clusters. In this table, for instance, cluster2 corresponds to the activity of people staying in zone Zn1, that is, by the Vending machines zone. It can be observed that people can be described by having a very small displacement (less than 4m) and being almost immobile (speed less than 1.5m/s) for a short period of time ([0-4sec]).This is what characterises people bying tickets. This activity is the second most common activity in the station just after 'at Zone 2', corresponding to people staying in the main hall (cluster1; not shown) . Cluster4 corresponds to people going from the vending machines to the main hall ('Zone1 to Zone2'); as observed in the table, people walks a longer distance ([3.84-7.68m]) at a high walking speed ([2.88-4.32m/s]). The last cluster, Cluster 19 represents a rare activity (only two elements contained in this activity); people going from 'Zone7 to Zone1'. These persons are particulary characterised by the time at which they are detected (no other mobile detected at a nearby time). Thus, this way the relational analysis can help us to group together people having similar behaviour. This is of particular interest to the end-users because the activities in the metro station can be better quantified. We have also applied the proposed approach to another domain, namely, traffic control monitoring and specifically detecting abnormal events on a bus reserved street lane. The interest to work on this dataset is that event groundtruth is available for 45 minutes of video. We applied in this dataset the same processing chain as before, that is, we learned first the activity areas of the scene in an unsupervised manner; then we extracted the behaviour from detected mobile objects by relating them to the learned zones. Finally, we applied again the relational clustering methodology to extract high-level information. Figure 2 shows those learned activity zones of the scene. Zn6, Zn7 and Zn9 correspond to people activity areas, whereas the remainig ones are vehicle activity areas as they overlap the bus lane. Behaviour was then characterised either as staying in a given zone or transferring between two zones. We marked as abnormal those behaviours when transferring between zones was in a south-north direction. Table 3 shows the abnormal behaviours established from the learned zones. When applying the high-level relational analysis methodology, all abnormal events were gathered as expected in a single cluster. In order to test the correctness of the whole processing chain, we compared the abnormal events obtained by our approach with those signaled by the available ground-truth. The results of this comparison can be observed in table 4. The recall measure is fairly high while the precision is acceptable. This is principally because our system has included a relative high amount of false positive detections, which might possibly appear because of detections at the bus lane border, which in the ground-truth were not included.

Conclusions

In this paper we have presented a system to extract from video and in an unsupervised manner the main activities that can be observed from the scene. We have setup a processing chain broadly working on three steps: The system stars in a first step by the unsupervised learning of the main activity areas of the scene. In a second step, mobile objects are then characterised in relation to the learned activity areas: either as 'staying in a given activity zone' or 'transferring from an activity zone to another' or a sequence of the previous two behaviours if the tracking persits long enough. In a third step we employ a high-level relational clustering algorithm to group mobiles according to their behaviours and discover what other characteristics from mobile objects are strongly correlated.

We have applied our algorithm in two domains. First, monitoring of activities in the hall entrance of an underground station and showed what are the most active areas of the scene and how rare/abnormal (going to low occupated activity zones) and frequent activities (e.g. buying tickets) are characterised. In the second application, monitoring a bus reserved street lane, we were able again to learn the topology of the scene and separate normal from abnormal activities.

When comparing with available ground-truth for this application, we obtained a high recall measure while the precision is acceptable but can be improved, which we aim to do in our future work by including a larger series of variables to analyse into the last relational clustering step.

Fig. 1 .

 1 Fig. 1. Left panel: Original underground scene observed by the camera. A1 to A5 correspond to user defined areas delimitating the scene. Right panel: Learned zones. Zn1 to Zn8 correspond to activity areas as discovered with our algorithm.

Fig. 2 .

 2 Fig. 2. Left panel: Top view of the bus lane (marked in red) with the zones learned by our system. The arrow indicates the bus flow. Central and Right panels: Two activity examples with mobiles moving against the normal traffic flow. Red points indicate the mobile departure.

Table 1 .

 1 Activity reporting (not exhaustive) related to the vending machines area.

	Proportion Number of mobiles	Description
	25.92%	106	at Zone 1
	3.91%	16	Zone 1 to Zone 2
	2.20%	9	Zone 2 to Zone 1
	0.49%	2	Zone 7 to Zone 1
	0.24%	1	Zone 5 to Zone 1

Table 2 .

 2 Example of activity clusters obtained after application of the Relational Analysis procedure.

	Cluster 2 ( 106 elements)		Cluster 4 ( 16 elements)		Cluster 19 ( 2 elements)
	modality	ratioC	ratioD	modality	ratioC	ratioD	modality	ratioC	ratioD
	.	.	.	.	.	.	.
	Evnt.atZone1 distorgdest.0-3.84 duration.0-4.2 meanspeed.0-1.44	100 89 75 57	100 32 26 44	Evnt.Zone1toZone2 distorgdest.3.84-7.68 duration.0-4.2 meanspeed.2.88-4.32	100 43 37 37	100 12 2 20	Evnt.Zone7toZone1 Start. 22:16:20 End. 22:16:24.4	100 50 50	100 100 100

Table 3 .

 3 Discovered abnormal events

	Abnormal Event Proportion
	Zn1 to Zn8	34
	Zn1 to Zn5	3
	Zn1 to Zn3	45
	Zn1 to Zn4	5
	Zn1 to Zn2	34
	Zn2 to Zn4	8
	Zn2 to Zn3	12
	Zn4 to Zn3	5
	Zn4 to Zn5	3
	Zn4 to Zn8	10
	Zn3 to Zn5	2
	Zn3 to Zn8	16

Table 4 .

 4 Evaluation measures

	TP	116
	FP	61
	TN	2174
	FN	8
	Precision 0.65
	Recall 0.93


V Padois

J.-Y Fourquet

P Chiron

From robotic arms to mobile manipulation: on coordinated motion schemes

Keywords: mobile manipulation, instantaneous kinematics, nonholonomy, motion generation

The task definition for mobile manipulators is presented. Then, a generic formulation of global instantaneous kinematics is proposed for wheeled mobile manipulators. It is compared with the classical kinematic modelling of robotic arms. In particular, it is shown that many tools of classical manipulation can be re-used in this new framework. Finally, simulation results and experiments are presented and the remaining industrial challenges are mentioned. So, this article provides comprehensive bases for the use of such systems in an industrial context.

Moving products and robots

Mobile manipulation is an activity human perform every day. So, it is very unnatural to separate locomotion and manipulation in human tasks. On the other side, automation has been historically organized by explicitly separating the motion of products and the action of manipulators with fixed basis. The main drawbacks of this kind of organization are due to the inherently bounded workspace of classic robotic arms or automatic machines. Finally, their geometric reachability is extremely limited. So, when dealing with relatively small products (car, electronics, etc.), this paradigm leads to move the products inside a fixed bank of robotic manipulators by any kind of conveyors. At least two cases are not really consistent with this kind of organization:

• operations (painting, stripping, welding, etc.) on large products like ships, planes or cranes need to move the tools around them since moving a plane or a ship requires much space and energy. • More generally, in a context where the products change quickly or need updates or customiza-tion, fixed basis robotic manipulators impose hard constraints on the production cycle, and possibly waste of ressources.

So, it became natural to consider robots that have motion and manipulation capabilities. The most famous are humanoids. Nonetheless, the problems they give rise in terms of complexity, cost or stability, disqualify them for a genuine use in manufacturing or production solutions in the near future. Instead, autonomous wheeled vehicles already are in the factories and some laboratories have worked on the coupling of these wheeled mobile bases with industrial robotic arms. Even more, some cases of industrial use of this wheeled mobile manipulators appeared. These compound systems have some common features:

• Mobile base provides an infinite workspace.

• The combination of both subsystems generally give rise to a global system possessing more actuators than required locally by the task. The objectives of this paper are to clarify what kind of tasks can be defined in weeled mobile manipulation and then how to perform these tasks. First, it is shown how the manipulation task and the environment constraints can be taken into account. Then, the need for coordination and the models underlying each strategy are discussed. The coordinated motion strategy is emphasized together with the models derived from the classic models of wheeled mobile platforms and robotic arms. Finally, experiments and simulation show the effectiveness of the approach. Concluding remarks are devoted to the gap between these laboratory experiments and industrial implementation.

Mobile Manipulation Tasks

A Manipulation Task as it is defined for robotic arms is only related to the motion of the end-effector and to the torque/force exerted on it. It is imposed by the user in the so-called operational space. A point in this space is the location of the end-effector (EE) denoted by the m × 1 vector ξ. It is characterized by a set of operational coordinates that correspond to the value of the position and the orientation of a frame attached to the EE at a particular point of this There are few works devoted to redundant manipulators, and also few redundant industrial manipulators since they are more expensive to build and because the whole organization scheme of production lines did not require them. In mobile manipulation, redundancy is the rule and decomposing the task by considering subsystems may appear as a useful recipe. The first experiments, in laboratory ([1] e.g) and industry, explicitly break down the task into sequences of pieces esssentially devoted to locomotion (motion of the platform) or to manipulation (motion of the arm with platform keeping a fixed location). Of course, this static decomposition does not allow to use all the capabilities of these systems. It is necessary to consider tasks for which all the actuators are used at the same time in order to provide a synchronized motion of the mobile manipulator. Moreover, due to the environment and to the inherent manoeuvering nature of the vehicles, a question arises naturally: is it necessary to impose a path for the vehicle -as equality constraints -to avoid obstacles? Or is it possible to solve the problem by the sole consideration of the inequality constraints the environment and the articular bounds of the arm define? So, even in a synchronized motion of the mobile manipulator, there are two main ways to define the task:

• hierachy: defining a subtask for the platform and then a subtask for the arm, • coordination: defining a main task for the endeffector without explicitly imposing equality constraints on the motion of the platform.

Hierarchy

Here one reference motion is given as equality constraints for the platform. The task for the platform consists in moving its location and the task for the arm is relative to the frame attached to the platform.

Here, it is necessary to have two models: the first one that link actuators of the platform to its location evolution on one side, and the second that link end-effector evolution with respect to the first body of the arm to its actuators. First, remember that nonholonomic platform cannot follow any path by definition. Thus, the first problem is to define a feasible path for the platform, or to define path for which it is ensured that the mobile base will remain in a given neighborhood of it. Then, the arm must adapt its motion. This hierarchical decomposition emphasizes nonholonomic constraints of the platform. In this approach, let us mention the works concerning transverse functions that allow to bound the region the platform traverses [START_REF] Padois | Coordination and partial decoupling in tracking control for wheeled mobile manipulators[END_REF][START_REF] Fruchard | A framework for the control of nonholonomic mobile manipulators[END_REF]. In these works, it can be observed that decomposition and hierarchization does not provide an easy to use solution and is of limited efficiency.

Coordination

On the contrary, it can be assumed that the non feasible directions of the wheeled platform will be compensated at the end-effector level by the degrees of freedom of the arm. Such an approach requires a global modelling and the definition of a main task for the end-effector without explicitly imposing equality constraints on the motion of the platform. In that case, it is necessary to have global models that link the end-effector evolution to all the actuators of the compound system. In this approach, it is supposed that the platform will "follow" the end-effector. So, it is necessary to avoid large of the platform, platform collisions and to insure that tool is never at the boundary of its workspace relative to the base of the arm. All these inequality constraints can be taken into account as secondary tasks the whole redundant system will satisfy. When looking at the global mobile manipulator, the kinematic constraints of the platform may be compensated by an adequate generalized velocity of the arm to realize a prescribed end-effector task. In that case, nonholonomy of the platform is somewhat hidden in the global instantaneous kinematics. This approach is presented in the following sections.

Global Modelling

Recently some contributions concerning modelling and control of generic nonholonomic mobile manipulators ( [START_REF] Tchon | Extended Jacobian Inverse Kinematics Algorithms for Mobile Manipulators[END_REF][START_REF] Bayle | Manipulability of wheeled mobile manipulation: application to motion generation[END_REF]) have been proposed. Based on these proposals, it is now possible to consider modelling and control of mobile manipulators on a unified basis and a comparison can be made with classical manipulation. Manipulation and mobile robotics literature both provide modelling tools to solve this problem. On one hand, kinematics and instantaneous kinematics of robotic arms with a fixed base are now a very classical material. The associated notions of redundancy, singularity, and manipulability [START_REF] Sciavicco | Modelling and control of robot manipulators[END_REF][START_REF] Yoshikawa | Foundations of robotics -Analysis and Control[END_REF] are also parts of the classical background of manipulation. On the other hand, wheeled mobile platforms were properly described and modelled by [START_REF] Campion | Structural Properties and Classification of Kinematic and Dynamic Models of Wheeled Mobile Robots[END_REF]. Though less classical and less used in the robotics community, these notions are of great interest in the case of wheeled mobile manipulators.

For the sake of simplicity, the case of mobile manipulator composed of a mobile platform with two independent driving wheels and a serial manipulator with n b joints is considered. Such a system is depicted on figure 1 in a 3-dimensional version used for our experiments or on figure 2 in the planar version used in simulation. Some kinematic modelling results regarding mobile manipulators based on [START_REF] Bayle | Manipulability of wheeled mobile manipulation: application to motion generation[END_REF][START_REF] Bayle | Kinematic modelling of wheeled mobile manipulators[END_REF][START_REF] Padois | Enchaînements dynamiques de tâches pour des manipulateurs mobiles à roues[END_REF] are sum up first.

Figure 1. H 2 bis: a 3D mobile manipulator.

Mobile manipulator kinematics

The configuration of such a mobile manipulator is completely defined using vector q = [ q b q p ] T where q b = [ q b1 . . . q bn b ] T and q p = [ θ r θ l x Op y Op ϑ ] T respectively represents the arm configuration and the platform configuration (see Fig. 2). Its end-effector location (i. e. location of R EE = (O EE , x EE , y EE , z EE ) in the reference frame R = (O, x, y, z)) can be described using a minimal set of parameters ξ = [ ξ 1 . . . ξ m ] T . ξ is expressed as a non linear function of q. Differentiating it, the relation between ξ and q is given by: ξ = J(q) q (1)

with J(q) a m × n matrix and n = n b + 5.

In addition, the components of q are constrained by the nonholonomy of the platform (i. e. the wheels cannot slip). Then, one can define a vector u = [ u b u p ] of n independent parameters (i. e. taking the nonholonomic constraints into account) such as:

q = T (q)u. (2)
Defining J(q) as:

J(q) = J(q)T (q), (3)
equation ( 1) becomes :

ξ = J(q)u. (4)
Equation ( 4) completely describes the mobile manipulator kinematics.

When m < n, the mobile manipulator is said to be kinematically redundant. This property provides the capability to choose a particular kinematic control vector u among those giving the prescribed endeffector velocity ξ by using the relation:

u = J(q) ξ + (I -J(q) J(q))z, (5)
where J(q) is any generalized inverse of J(q) and z any n × 1 vector.

Access to the kinematic redundancy of the system is given by the second right-hand term of equation ( 5) Figure 2. A planar mobile manipulator. also called the internal motion control term since it does not provide any end-effector motion. Remark that practically, it is sufficient to choose the generalized inverse among the so-called weighted pseudo-inverses [START_REF] Doty | A theory of generalized inverses applied to Robotics[END_REF] for having any interesting behavior. Finally, at kinematic level, global system modelling leads to a model that has the same form as the one used for fixed redundant manipulators 1 . So, the same main control techniques can be used and adapted.

Operational kinematic controllers

Given ξ * and ξ * desired end-effector speed and location to track, and a positive definite weighting matrix W reg , the control vector defined by:

u = J(q) ( ξ * + W reg (ξ * -ξ)) + (I -J(q) J(q))z, (6)
ensures an asymptotic decreasing of e = ξ * -ξ toward 0.

In order to take advantage of the kinematic redundancy of the system, z can be chosen such as to minimize a scalar function P(q), also called potential function. The "gradient descent" local optimization method consists in choosing q such as:

q + W grad ∇P(q) = 0, (7)
where W grad ∈ R n×n is a positive definite weighting matrix and ∇P(q) is the gradient of P(q). This choice ensures an evolution of the system configuration tending to locally minimize P(q). However, q components have to be independent which is not the case for a mobile manipulator. Thus, one have to adapt this method by choosing z as:

z = -T (q) + W grad ∇P(q). ( 8
)
1 When the platform features steering actuated wheels, it can be shown that the model is slightly different but keep its main properties. At dynamic level, many analogies that allow to use known techniques are also obtained by an adequate choice of variables [START_REF] Padois | Enchaînements dynamiques de tâches pour des manipulateurs mobiles à roues[END_REF].

where T (q) + denotes the pseudo-inverse of T (q).

When the task imposes end-effector force, the global model can be used for adapting classic scheme generally used for holonomic arms. For example, hybrid speed / force controller used for the following experiments is a modified version of the well known work presented in [START_REF] Raibert | Hybrid position/force control of manipulators[END_REF].

Once the contact is established, the robot's endeffector cannot independently exert a displacement and a force in the same direction. The control vector is then calculated as the sum of three terms:

u = u s + u f + u r , (9)
with:

u s = J(q) S ξs , (10)
u f = J(q) (I -S) ξf , (11)
u r = (I -J(q) J(q))z.

ξs and ξf are the control vectors whose simple versions are given by:

ξs = ξ * + W regs (ξ * -ξ), (13)
and:

ξf = W reg f (f * -f ), (14)
where W regs and W reg f are two positive definite weighting matrices, and S is a m × m diagonal selection matrix where ones or zeros are placed on the diagonal respectively to indicate whether the component of ξ corresponding to the line in S is velocity or force controlled.

Use of redundancy

Here a set of functions to optimize using internal motion is presented. Many other functions may be used but these ones are relevant according to the presented results.

Manipulability maximization

The manipulability notion was first introduced for manipulators (cf. [START_REF] Yoshikawa | Foundations of robotics -Analysis and Control[END_REF] for a detailed presentation of this notion) but was also extended to mobile manipulators in [START_REF] Bayle | Manipulability of wheeled mobile manipulation: application to motion generation[END_REF]. The different manipulability measures are quantitative indicators representing the ease to instantly move the endeffector in any direction. Maximizing any of these indicators tends to avoid singular configuration of the system and thus to avoid high joints speed. Arm Manipulability measure is also useful for avoiding configurations close to workspace boundary of the arm.

Impact force reduction

During the transition tasks between free space motion and contact motion, it is interesting to re-configure the mobile manipulator using internal motion so as to give it good inertial properties. Results concerning holonomic mobile manipulators are presented in [START_REF] Kang | Utilization of inertial effect in damping-based posture control of mobile manipulator[END_REF]. Using the dynamic model of the global system (i. e. the model establishing the relation between physical effects of motion, actuating torques and contact forces at end-effector level), it can be shown that the magnitude of the impact force is configuration dependent. So, redundancy can be used to provide convergence toward a configuration that minimizes this impact force magnitude.

Collision avoidance

Techniques to avoid obstacles have extensively been studied in the case of mobile robots. However, the problem to solve here depends on the nature of the task to perform. Is the goal to follow an obstacle (like during a writing task on the wall) or to go around an obstacle (like in free space end-effector motion)? Different potential functions have been defined depending on what kind of collision avoidance is expected.

Simulation and experiments

Simulation and experiments have been conducted on two different mobile manipulators :

• The first one is depicted at the figure 2. It has been used in simulation in order to illustrate numerous strategies based on redundancy resolution on the basis of local/reactive potential function. • The second one, H 2 bis, has been used for demonstrating a complex mission realization including free-space and contact tasks.

Simulation framework

The simulator has been developed using Matlab and Simulink. The robot is modeled at kinematic and dynamic level. In particular, load torques due to dynamic effects of motion or due to contact, saturations of the actuators, low level digital PID, noise and inaccuracy of the end-effector force sensor together with its limited bandwidth are taken into account.

Contact between the end-effector and the environment is locally modeled either as a {spring // damper} system (i. e. Kelvin-Voigt visco-elastic model) or as a spring system and the values of the parameters characterizing the contact are unknown or poorly estimated.

Simulation results

Simulation 1: go to the wall among obstacles and follow it applying a normal force

The task to realize consists in two main phases: first, the endeffector motion is imposed along a straight line and the environment may comprise low obstacles the robot will sense as motion progresses; in the second stage, the end-effector must follow a line on the wall and apply a given normal force (see figure 3).

Here the end-effector motion is imposed and the mobile base has to avoid low obstacles reactively. There is only a local information about the location and number of obstacles. The dynamic sequencing scheme switchs automatically between indices: manipulability, obstacle avoidance, inertia, etc. The imposed endeffector motion is made of the two blue straight lines and the path of the middle of the rear axle of the mobile base is depicted in red. ξ is chosen as the endeffector position and u = [ θr θl qb1 qb2 ] T . Once the contact is established, the normal direction is force controlled whereas the tangential direction is velocity controlled.

Simulation 2: interactive joystick

Here, the control scheme is used interactively since the endeffector velocity is imposed in real time. Again, the real-time imposed end-effector motion is in blue whereas the path of the middle of the rear axle of the mobile base is depicted in red (see figure 4). This simulation shows the robustness of the control scheme and the ability to realize totally reactive behaviour with a nonholonomic mobile manipulator. In particu- This mode shows how simple is to control the wheeled mobile manipulator in real time. In particular, use by human operator for cooperative tasks is particularly easy.

Experimental results

The mobile platform is actuated using two independent driving wheels. The manipulator is a 6R serial arm called GT6A. The robot is endowed with localization devices such as ultrasonic sensors, a telemeter and a black and white camera, an odometer system, the manipulator's incremental coders and a 6-axis GIROBO force / torque sensor. Control algorithms are implemented using G en om, a generator of software control modules developed, as well as the robot, in the RIA team of the LAAS laboratory.

The task simulated in 4.2.1 has been tested experimentally and the end-effector has been equipped with a pen so as to visualize the path of the end-effector and the action of the normal force. The figure 5 shows the end of the mission obtained by global coordination of mobile manipulator including a transition phase during which configuration is adapted for impact force minimization.

Concluding remarks

It is shown in this paper that classic control schemes can be revisited for wheeled mobile manipulators by choosing adequate global modelling and coordinated control. At present, the industrial use of these robots is limited by at least two factors, technological and organizational:

• technological: challenges are on real-time precision on geometric measures relative to the location of the robot in the environment. • organizational: a fleet of mobile manipulators will, for example, totally change the rules of production sequencing, of reorganization on small series. All is to be redefined, including PLM software tools!

Figure 3 .Figure 4 .

 34 Figure 3. Go to the wall and follow it

Figure 5 .

 5 Figure 5. Coordinated Writing on a board lar, cusps or manoeuvers are automatically generated.This mode shows how simple is to control the wheeled mobile manipulator in real time. In particular, use by human operator for cooperative tasks is particularly easy.

Acknowledgment: This work is partially supported by the French CNRS Robea program within the project Dynamic sequencing of multi-sensor based tasks for complex motions execution in mobile robotics and the experiments have been performed at LAAS-CNRS in Toulouse, France.

LGP-ENIT is a partner of the Innovative Production Machines and Systems (I PROMS) Network of Excellence funded by the European Commission under the Sixth Framwork Programme (Contract n o FP6-2002-500273-2).