Daciberg Lima

Gonc ¸alves

AND John Guaschi
email: john.guaschi@unicaen.fr

Miguel Maldonado
email: mmaldonado@matematicas.reduaz.mx

EMBEDDINGS AND THE (VIRTUAL) COHOMOLOGICAL DIMENSION OF THE BRAID AND MAPPING CLASS GROUPS OF SURFACES

Keywords: Mapping class groups, surface braid groups, finite coverings, embeddings, (virtual) cohomological dimension

. Finally, if the genus of N is greater than or equal to 2, we give upper bounds for the virtual cohomological dimension of M CG(N ; k). σ -→ Σ k -→ 1, and if f ∈ Top(S; X) then [f ] ∈ P M CG(S; X) if and only if f fixes X pointwise.

Introduction

Let S be a compact, connected surface, and let X = {x 1 , . . . , x k } be a finite (possibly empty) subset of S of cardinality k ≥ 0. Let Top(S; X) denote the group of homeomorphisms of S for the operation of composition that leave X invariant. If S is orientable, let Top + (S; X) denote the set of elements of Top(S; X) that preserve orientation. Note that Top + (S; X) is a subgroup of Top(S; X) of index two. We define the mapping class group M CG(S; X) of S relative to X by: (1.1) M CG(S; X) = π 0 Top + (S; X) if S is orientable π 0 Top(S; X) if S is non orientable.

If S is orientable (resp. non orientable), the group M CG(S; X) is thus the set of isotopy classes of Top + (S; X) (resp. Top(S; X)), the isotopies being relative to the set X. If f ∈ Top + (S; X) (resp. Top(S; X)) then we let [f ] denote its mapping class in M CG(S; X). Up to isomorphism, M CG(S; X) only depends on the cardinality k of the subset X, and we shall often denote this group by M CG(S; k). If X is empty, then we omit it from the notation, and shall just write Top(S), Top + (S), M CG(S) etc. The mapping class group may also be defined in other categories (PL category, smooth category), the groups obtained being isomorphic [START_REF] Boldsen | Different versions of mapping class groups of surfaces[END_REF]. The mapping class group has been widely studied from different points of view -see [START_REF] Birman | Braids, Links and Mapping Class Groups[END_REF][START_REF] Farb | Some problems on mapping class groups and moduli space, In Problems on mapping class groups and related topics[END_REF][START_REF] Farb | A primer on mapping class groups[END_REF][START_REF] Ivanov | Mapping class groups[END_REF][START_REF] Paris | From braid groups to mapping class groups, In Problems on mapping class groups and related topics[END_REF] for example. If k ∈ N, there is a surjective homomorphism σ : Top(S; X) -→ Σ k defined by f (x i ) = x (σ(f ))(i) for all f ∈ Top(S; X) and i ∈ {1, . . . , k}, where Σ k is the symmetric group on k letters. This homomorphism induces a surjective homomorphism from M CG(S; X) to Σ k that we also denote by σ, and its kernel is called the pure mapping class group of S relative to X, denoted by P M CG(S; X). So we have a short exact sequence:

(1.2)

1 -→ P M CG(S; X) -→ M CG(S; X)

Mapping class groups are closely related to surface braid groups. If k ∈ N, the k th ordered configuration space F k (S) of S is the set of all ordered k-tuples of distinct points of S that we may consider as a subspace of the k-fold product of S with itself. The group Σ k acts freely on F k (S) by permuting coordinates, and the associated quotient is the k th unordered configuration space of S, denoted by D k (S). The fundamental group π 1 D k (S) (resp. π 1 F k (S)), denoted by B k (S) (resp. P k (S)) is the braid group (resp. pure braid group) of S on k strings [START_REF] Fadell | Configuration spaces[END_REF][START_REF] Fox | The braid groups[END_REF], and B k (S) and P k (S) are related by a short exact sequence similar to that of (1.2). It is well known that B k (R 2 ) (resp. P k (R 2 )) is isomorphic to Artin's braid group (resp. Artin's pure braid group) on k strings. If π : S -→ S is a d-fold covering map, where d ∈ N, then for all k ≥ 1, there is a continuous map:

(1.3) ϕ k : D k (S) -→ D kd ( S)
defined by ϕ k (A) = π -1 (A) for all A ∈ D k (S), and the induced homomorphism ϕ k# : B k (S) -→ B kd ( S) on the level of fundamental groups is injective [START_REF] Gonçalves | Surface braid groups and coverings[END_REF]. Taking π : S 2 -→ RP 2 to be the standard 2-fold (universal) covering, where S 2 is the 2-sphere and RP 2 is the real projective plane, this result was then applied in [START_REF] Gonçalves | Surface braid groups and coverings[END_REF] to classify the isomorphism classes of the finite subgroups of B k (RP 2 ), and to show that B k (RP 2 ) and M CG(RP 2 ; k) are linear groups for all k ∈ N.

If g ≥ 0 (resp. g ≥ 1), let S = S g (resp. N = N g ) be a compact, connected orientable (resp. non-orientable) surface of genus g without boundary. In the non-orientable case, g is the number of projective planes in a connected sum decomposition. If g ≥ 1 and k ≥ 0, the orientable double covering π : S g-1 -→ N g induces a homomorphism φ k : M CG(N g ; k) -→ M CG(S g-1 ; 2k), where the 2k-point subset of marked points in S is equal to the inverse image by π of a k-point subset of N . One of the main aims of this paper is to generalise the injectivity result of [START_REF] Gonçalves | Surface braid groups and coverings[END_REF] to this homomorphism. If k = 0 and g ≥ 3, it was shown in [START_REF] Birman | On the homeotopy of a non-orientable surface[END_REF][START_REF] Hope | On the Farrell cohomology of the mapping class group of non-orientable surfaces[END_REF] that there exists an injective homomorphism φ : M CG(N g ) -→ M CG(S g-1 ), and that via φ, M CG(N g ) may be identified with the subgroup of M CG(S g-1 ) that consists of isotopy classes of symmetric homeomorphisms. In Section 3, we show that a similar result holds for all k ≥ 0, namely that the homomorphism φ k induced by π is injective, and that via φ k , M CG(N g ; k) may be identified with the subgroup of M CG(S g-1 ; 2k) that consists of isotopy classes of symmetric homeomorphisms.

Theorem 1.1. Let k, g ∈ N, let N = N g be a compact, connected, non-orientable surface of genus g without boundary, and let S be its orientable double covering. Then the homomorphism φ k : M CG(N ; k) -→ M CG(S; 2k) induced by the covering π : S -→ N is injective. Further, if g ≥ 3 then we have a commutative diagram of the following form:

(1.4) 1 B k (N ) M CG(N ; k) M CG(N ) 1 1 B 2k (S) M CG(S; 2k) M CG(S) 1, ϕ k# τ k φ k φ τ k
where τ k and τ k are the homomorphisms induced by forgetting the markings on the sets of marked points.

Note that in contrast with [START_REF] Birman | On the homeotopy of a non-orientable surface[END_REF], Theorem 1.1 holds for all g ≥ 1, not just for g ≥ 3. As we recall in Remark 2.4, the result of [START_REF] Birman | On the homeotopy of a non-orientable surface[END_REF] does not hold if g = 2. The proof of this exceptional case g = 2 in Theorem 1.1 will turn out to be the most difficult, in part due to the non injectivity of φ : M CG(N 2 ) -→ M CG(S 1 ).

In Section 4, we compute the cohomological dimension of the braid groups of all compact surfaces without boundary different from S 2 and RP 2 , and we give an upper bound for the virtual cohomological dimension of the mapping class group M CG(N g ; k) for all g ≥ 2 and k ≥ 1. Recall that the virtual cohomological dimension vcd(G) of a group G is a generalisation of the cohomological dimension cd(G) of G, and is defined to be the cohomological dimension of any torsion-free finite index subgroup of G [START_REF] Brown | Cohomology of groups[END_REF]. In particular, if G is a braid or mapping class group of finite (virtual) cohomological dimension then the corresponding pure braid or mapping class group has the same (virtual) cohomological dimension. In [START_REF] Gonçalves | Inclusion of configuration spaces in Cartesian products, and the virtual cohomological dimension of the braid groups of S 2 and RP 2[END_REF]Theorem 5], it was shown that if k ≥ 4 (resp. k ≥ 3) then vcd(B k (S 2 )) = k -3 (resp. vcd(B k (RP 2 )) = k -2). These results are generalised in the following theorem, the proof being a little more straightforward due to the fact that the braid groups of S g and N g+1 are torsion free if g ≥ 1.

Theorem 1.2. Let g, k ≥ 1. Then:

cd(B k (S g )) = cd(P k (S g )) = cd(B k (N g+1 )) = cd(P k (N g+1 )) = k + 1.
We then turn our attention to the mapping class groups. If 2g + k > 2, J. Harer proved that [START_REF] Harer | The virtual cohomological dimension of the mapping class group of an orientable surface[END_REF]Theorem 4.1]:

vcd(M CG(S g ; k)) =      4g -5 if k = 0 k -3 if g = 0 and k > 0 4g + k -4 if g, k > 0.
Using the embedding of M CG(N g ) in M CG(S g-1 ) given in [START_REF] Birman | On the homeotopy of a non-orientable surface[END_REF], G. Hope and U. Tillmann showed that if g ≥ 3 then vcd(M CG(N g )) ≤ 4g-9 [START_REF] Hope | On the Farrell cohomology of the mapping class group of non-orientable surfaces[END_REF]Corollary 2.2]. Using [START_REF] Gonçalves | Inclusion of configuration spaces in Cartesian products, and the virtual cohomological dimension of the braid groups of S 2 and RP 2[END_REF]Theorem 5], it was shown in [START_REF] Gonçalves | Inclusion of configuration spaces in Cartesian products, and the virtual cohomological dimension of the braid groups of S 2 and RP 2[END_REF]Corollary 6]

that if k ≥ 4 (resp. k ≥ 3) then vcd(M CG(S 2 ; k)) = k -3 (resp. vcd(M CG(RP 2 ; k)) = k -2).
In the case of S 2 , we thus recover the results of Harer. In the second part of Section 4, we generalise some of these results to non-orientable surfaces with marked points. Proposition 1.3. Let k > 0. The mapping class groups M CG(N g ; k) and P M CG(N g ; k) have the same (finite) virtual cohomological dimension. Further: (a) vcd(M CG(N

2 ; k)) = k. (b) if g ≥ 3 then vcd(M CG(N g ; k)) ≤ 4g + k -8.
This paper is organised as follows. In Section 2, we recall some definitions and results about orientation-true mappings and the orientable double covering of non-orientable surfaces, we describe how we lift an element of Top(N ) to one of Top + (S) in a continuous manner, and we show how this correspondence induces a homomorphism from the mapping class group of a non-orientable surface to that of its orientable double covering (Proposition 2.3). In Section 3, we prove Theorem 1.1 using long exact sequences of fibrations involving the groups that appear in equation (1.1) and the corresponding braid groups [START_REF] Birman | Mapping class groups and their relationship to braid groups[END_REF][START_REF] Scott | Braid groups and the group of homeomorphisms of a surface[END_REF]. In most cases, using [START_REF] Gonçalves | Surface braid groups and coverings[END_REF][START_REF] Hamstrom | Homotopy groups of the space of homeomorphisms on a 2-manifold[END_REF], we obtain commutative diagrams of short exact sequences, and the conclusion is obtained in a straightforward manner. The situation is however much more complicated in the case where N is the Klein bottle and S is the 2-torus T , due partly to the fact that the exact sequences that appear in the associated commutative diagrams are no longer short exact. This case requires a detailed analysis, notably in the case k = 1. In Section 4, we prove Theorem 1.2 and Proposition 1.3. Finally, in an Appendix, we provide presentations of P 2 (T ) and B 2 (T ) that we use in the proof of Theorem 1.1.

Acknowledgements. The first-named author was partially supported by FAPESP-Fundação de Amparo a Pesquisa do Estado de São Paulo, Projeto Temático Topologia Algébrica, Geométrica 2012/24454-8. He and the second-named author would like to thank the 'Réseau Franco-Brésilien en Mathématiques' for financial support for their respective visits to the Laboratoire de Mathématiques Nicolas Oresme UMR CNRS 6139, Université de Caen Normandie, from the 2 nd to the 15 th of September 2016, and to the Instituto de Matemática e Estatística, Universidade de São Paulo, from the 9 th of July to the 1 st of August 2016. The third-named author was supported by the Consejo Nacional de Ciencia y Tecnología to visit the Laboratoire de Mathématiques Nicolas Oresme UMR CNRS 6139, Université de Caen Normandie, from the 1 st of February 2014 to the 31 st of January 2015. During that period, he was also partially supported by the Laboratorio Internacional Solomon Lefschetz (LAISLA).

Orientation-true mappings and the orientable double covering

Let M, N be manifolds with base points x 0 , y 0 , respectively. Following [START_REF] Olum | Mappings of manifolds and the notion of degree[END_REF], a pointed map f : (M, x 0 ) -→ (N, y 0 ) is called orientation true if the induced homomorphism

f * : π 1 (M, x 0 ) -→ π 1 (N, y 0 )
sends orientation-preserving (resp. orientation-reversing) elements to orientation-preserving (resp. orientation-reversing) elements. In other words, the map f is orientation-true if for all α ∈ π 1 (M, x 0 ), either α and f * (α) are both orientation preserving or they are are both orientation reversing. In the case of a branched covering f : M -→ N it follows by [START_REF] Gonçalves | Roots of mappings on nonorientable surfaces and equations in free groups[END_REF]Proposition 1.4] that f is orientation-true. In what follows, we will be interested in the case of maps between surfaces. We will start with the case of non-orientable surfaces.

Lemma 2.1. Every homeomorphism f : N -→ N of a non-orientable surface is orientation true. Consequently, the subgroup of all orientation-preserving loops is invariant with respect to f * . Lemma 2.1 is an obvious consequence of [START_REF] Gonçalves | Roots of mappings on nonorientable surfaces and equations in free groups[END_REF]Proposition 1.4], but we shall give a more direct proof.

Proof of Lemma 2.1. Let x 0 ∈ N be a base point and consider α ∈ π 1 (N, x 0 ), which we represent by a loop h : S 1 -→ N . We fix a local orientation O 1 at x 0 , and we consider the orientation on N induced by f , denoted by O 2 . Moving the orientation O 1 along the path h by a finite sequence of small open sets U i , the images f (U i ) may be used to transport the local orientation O 2 along the path f • h.

Consider the maps h, f • h : S 1 -→ N and the tangent bundle T N of N . Pulling back by these maps, we obtain bundles over S 1 that are homeomorphic, and that are the trivial bundle if the loop is orientation-preserving or the twisted bundle if the loop is orientationreversing.

Let g ≥ 1, and let N g be as defined in the introduction. The unique orientable double covering of N g may be constructed as follows (see [START_REF] Lima | Fundamental Groups and Covering Spaces[END_REF] for example). Let the orientable surface S g-1 be embedded in R 3 in such a way that it is invariant under the reflections with respect to the xy-, yz-and xz-planes. Consider the involution J : S g-1 -→ S g-1 defined by J(x, y, z) = (-x, -y, -z). The orbit space S g-1 / J is homeomorphic to the surface N g , and the associated quotient map π : S g-1 -→ N g is a double covering.

To simplify the notation, from now on, we will drop the subscripts g and g -1 from N and S respectively unless there is risk of confusion, so S will be the orientable double covering of N . As indicated previously, the map π gives rise to a map on the level of configuration spaces that induces an injective homomorphism B k (N ) -→ B 2k (S) of the corresponding braid groups, and this allows us to study the braid groups of a non-orientable surface in terms of those of its orientable double covering [START_REF] Gonçalves | Surface braid groups and coverings[END_REF].

The following result is an immediate consequence of Lemma 2.1 and is basically contained in [21, Key-Lemma 2.1].

Lemma 2.2. Let f : N -→ N be a homeomorphism of a non-orientable surface, and let π : S -→ N be the orientable double covering. Then f admits a lift, and the number of lifts is exactly two.

Proof. Using Lemma 2.1, we know that f # | π 1 (S) (π 1 (S)) ⊂ π 1 (S), where we identify π 1 (S) with a subgroup of π 1 (N ). By basic properties of covering spaces, the map f lifts to a map f : S -→ S, and since S -→ N is a double covering, there are two lifts.

The lifts of f are in one-to-one correspondence with the group J of deck transformations. There is thus a natural way to choose a lift in a continuous manner simply by choosing f to be the lift of degree 1 (the other lift is of degree -1 since J is of degree -1). Let ρ : Top(N ) -→ Top + (S) denote this choice of lift. We may use Lemma 2.2 to compare mapping class groups of orientable and non-orientable surfaces.

Proposition 2.3. Let N be a non-orientable surface, and let S be its orientable double covering. Then there is a homomorphism φ : M CG(N ) -→ M CG(S) such that the following diagram commutes:

(2.1)

Top(N ) ρ / / Top + (S) M CG(N ) φ / / M CG(S).
Further, if the genus of N is greater than or equal to 3 then φ is injective.

Proof. If f, g ∈ Top(N ) are isotopic homeomorphisms then an isotopy between them lifts to an isotopy between the orientation-preserving homeomorphisms ρ(f ) and ρ(g) of S. This proves the first part of the statement. For the second part, suppose that the genus of N is greater than or equal to 3. Let M CG ± (S) denote the extended mapping class group of S consisting of the isotopy classes of all homeomorphisms of S, and let C J be the subgroup of M CG ± (S) defined by:

C J = [f ] ∈ M CG ± (S) f ∈ Top(S)
, and there exists f f such that f (2.1). By Lemma 2.2 and the comment that follows it, f admits exactly two lifts, ρ(f ) and J • ρ(f ), the first (resp. second) preserving (resp. reversing) orientation. Now ρ(f ) • J is an orientation-reversing lift of f , from which we conclude that J

• J = J • f , where f f means that f is isotopic to f . By [4], M CG(N ) ∼ = C J / [J] . Let π : C J -→ C J / [J] denote the quotient map. Let f ∈ Top(N ). Then φ([f ]) = [ρ(f )] by diagram
• ρ(f ) = ρ(f ) • J. Hence [ρ(f )] ∈ C J ∩ M CG(S), and so Im(φ) ⊂ C J ∩ M CG(S). On the other hand, π C J ∩M CG(S) : C J ∩ M CG(S) -→ M CG(N ) is an isomorphism using the proof of [21, Key-Lemma 2.1]. It then follows that π • φ = Id M CG(N ) , in particular φ is injective.
In the case of surfaces with marked points, there is another continuous way to choose a lift. For example, given a finite subset X = {x 1 , . . . , x k } of N , denote its preimage under π by:

X = {x 1 , x 1 , x 2 , x 2 , . . . , x k , x k }, where {x i , x i } = π -1 (x i ) for all 1 ≤ i ≤ k.
Pick a subset of X that contains exactly one element of {x i , x i }, denoted by x i , for all 1 ≤ i ≤ k. If f ∈ Top(N ; X) then the restriction of f to X is a given permutation of X, and if j ∈ {1, . . . , k} is such that f (x 1 ) = x j , we may define f to be the unique lift of f such that f (x 1 ) = x j . The two choices for x j correspond to the two possible lifts of f . Remark 2.4. Suppose that the genus of N is 2, in which case N is the Klein bottle K. If T is the torus, the homomorphism φ : M CG(K) -→ M CG(T ) is not injective, and it may be described as follows. Set [START_REF] Lickorish | On the homeomorphisms of a non-orientable surface[END_REF], and its elements are given by the mapping classes of the following automorphisms:

π 1 (K) = α, β | αβαβ -1 . The group M CG(K) is isomorphic to Z 2 ⊕ Z 2
(2.2) α -→ α β -→ β, α -→ α β -→ αβ, α -→ α β -→ β -1 , α -→ α β -→ αβ -1 .
Let π : T -→ K be the orientable double covering of K and let

π 1 (T ) = a, b | [a, b] , so that π # (a) = α and π # (b) = β 2 .
Given a map f : K -→ K such that the induced homomorphism on the fundamental group is given by f

# (α) = α r , f # (β) = α u β v , if v is
odd, then f lifts to a map from T to T , and there are exactly two lifts. The matrices of the induced homomorphisms of these lifts on π 1 (T ) are ( r 0 0 v ) and ( -r 0 0 v ). Observe that the determinant of one of these two matrices is positive. Identifying M CG(T ) with SL(2, Z), we conclude that φ sends the first (resp. second) two automorphisms of equation (2.2) to the matrix ( 1 0 0 1 ) (resp. to -1 0 0 -1 ). In particular, the second part of Proposition 2.3 does not hold in this case.

Embeddings of mapping class groups

As in all of this paper, the surfaces N and S under consideration are compact and without boundary, and π : S -→ N is the double covering defined in Section 2. If X is a finite k-point subset of N , X = π -1 (X) and f ∈ Top(N ; X), then we define a map ρ k : Top(N, X) -→ Top + (S, X) by ρ k (f ) = ρ(f ), where we consider f to be an element of Top(N ) and ρ is as defined in Section 2. By Proposition 2.3, the map ρ k induces a homomorphism φ k : M CG(N ; X) -→ M CG(S; X) defined by φ k ([f ]) = [ρ k (f )]. On the other hand, the map ψ k : Top(N ) -→ D k (N ) (resp. ψ 2k : Top + (S) -→ D 2k (S)) defined by ψ k (f ) = f (X) for all f ∈ Top(N ) (resp. ψ 2k (h) = h( X) for all h ∈ Top + (S)) is a locally-trivial fibration [START_REF] Birman | Mapping class groups and their relationship to braid groups[END_REF][START_REF] Mccarty | Homeotopy groups[END_REF] whose fibre is Top(N ; k) (resp. Top + (S; 2k)). The long exact sequence in homotopy of these fibrations gives rise to the following exact sequences:

B k (N ) -→ M CG(N ; X) τ k -→ M CG(N ), B k (S) -→ M CG(S; X) τ k -→ M CG(S),
where τ k , τ k are induced by suppressing the markings on X and X respectively [START_REF] Birman | Mapping class groups and their relationship to braid groups[END_REF]. In Theorem 1.1, we will see that the injectivity of φ given by Proposition 2.3 carries over to that of the homomorphism φ k between mapping class groups of marked surfaces and holds for all g ≥ 1, in contrast to the non injectivity in the case g = 2 described in Remark 2.4.

Let S be a compact, connected surface without boundary, let l ∈ N, and let X ⊂ S be a subset of cardinality l. If S is orientable, let:

Top + F (S; l) = {f ∈ Top + (S) | f (x i ) = x i for all i = 1, . . . , l } = {f ∈ Top + (S; X) | [f ] ∈ P M CG(S; l)} and Top + F (S; 2l) = f ∈ Top + (S) f (π -1 (x j )) = π -1 (x j ) for all j = 1, . . . , l , and if S is non orientable, let Top F (S; l) = {f ∈ Top(S) | f (x i ) = x i for all i = 1, . . . , l } = {f ∈ Top(S; X) | [f ] ∈ P M CG(S; l)}.
Observe that if S is orientable (resp. non orientable), Top + F (S; 1) = Top + (S; 1) (resp. Top F (S; 1) = Top(S; 1)). Before giving the proof of Theorem 1.1, we state and prove the following two results. The first part of the following lemma generalises results of [START_REF] Hamstrom | Homotopy properties of the space of homeomorphisms on P 2 and the Klein bottle[END_REF]. Lemma 3.2. (a) Let S be a compact, connected orientable (resp. non-orientable) surface without boundary for which π 1 (Top + (S; 1)), (resp. π 1 (Top(S; 1))) is trivial, and let l ≥ 1. Then π 1 (Top + F (S; l)), (resp. π 1 (Top F (S; l))) is trivial. In particular, π 1 (Top + F (T ; l)) (resp.

π 1 (Top F (K; l))) is trivial for all l ≥ 1. (b) π 1 (Top + F (T ; 2l)) is trivial for all l ≥ 1. Proof.
(a) Assume first that S is orientable. We prove the result by induction on l. If l = 1 then the result holds by the hypothesis, using the fact that Top + F (S; 1) = Top + (S; 1). Suppose by induction that the result holds for some l ≥ 1. The map Top + F (S; l) -→ S \ {x 1 , . . . , x l } given by evaluating an element of Top + F (S; l) at the point x l+1 is a fibration with fibre Top + F (S; l + 1). Taking the long exact sequence in homotopy of this fibration and using the fact that π 2 (S \ {x 1 , . . . , x l }) is trivial, it follows that the homomorphism π 1 (Top + F (S; l + 1)) -→ π 1 (Top + F (S; l)) induced by the inclusion of the fibre in the total space is injective, and since π 1 (Top + F (S; l)) is trivial by the induction hypothesis, π 1 (Top + F (S; l + 1)) is too. This proves the first part of the statement if S is orientable. If S is non orientable, it suffices to replace Top + F (S; l) by Top F (S; l) in the proof of the orientable case. The second part of the statement is a consequence of the first part and [17, Corollary, p. 65] and [START_REF] Hamstrom | Homotopy properties of the space of homeomorphisms on P 2 and the Klein bottle[END_REF]Theorem 4

.1]. (b) Let l ≥ 0. The map Top + F (T ; 2l) -→ D 2 (T \ {x 1 , . . . , x 2l )} that to a homeomorph- ism f ∈ Top + F (T ; 2l) associates the set {f (x 2l+1 ), f (x 2l+2 )} is a fibration whose fibre is Top + F (T ; 2l + 2). If l = 0 then Top + F (T ; 2l) is just Top + (T ).
Taking the long exact sequence in homotopy, and using the fact that D 2 (T \ {x 1 , . . . , x 2l }) is a K(π, 1), we obtain the following exact sequence:

(3.1) 1 -→ π 1 (Top + F (T ; 2l + 2)) ( q 2l+2 ) # -----→ π 1 (Top + F (T ; 2l)) -→ B 2 (T \ {x 1 , . . . , x 2l })
, where the homomorphism ( q 2l+2 ) # is induced by the map q 2l+2 : Top + F (T ; 2l + 2) -→ Top + F (T ; 2l) that forgets the marking on the last two points. If π 1 (Top + F (T ; 2l)) is trivial for some l ≥ 1 then clearly π 1 (Top + F (T ; 2l + 2)) is also trivial. So applying induction on l, it suffices to prove the result for l = 1. It follows from Proposition 3.1 that the map π 1 (Top + F (T )) -→ B 2 (T ) sends π 1 (Top + F (T )) isomorphically onto the centre of B 2 (T ). It follows from exactness of (3.1) that π 1 (Top + F (T ; 2)) is trivial, and this completes the proof of the lemma. Remark 3.3. If S is a surface that satisfies the hypotheses of Lemma 3.2(a) then S is different from the 2-sphere [26, lines 2-3, p. 303] and the real projective plane [18, Theorem 3.1], so S is an Eilenberg Mac Lane space of type K(π, 1).

Proof of Theorem 1.1. Consider the double covering π : S -→ N , fix a k-point subset X of N , and let X = π -1 (X). By the comments preceding the statement of the theorem, we obtain the following commutative diagram of fibrations:

(3.2) Top(N ; X) / / ρ k Top(N ) ψ k / / ρ D k (N ) ϕ k Top + (S; X) / / Top + (S) ψ 2k / / D 2k (S),
where ρ is as defined in Section 2, and ϕ k : D k (N ) -→ D 2k (S) is given by equation (1.3). The left-hand square clearly commutes because ρ k is the restriction of ρ to Top(N ; k). We claim that the right-hand square also commutes. On the one hand, π(

ψ 2k • ρ(f )) = π • ρ(f )( X) = f •π( X) = f (X), using the fact that ρ(f ) is a lift of f , so ψ 2k •ρ(f ) = ρ(f )( X) ⊂ π -1 (f (X)) = ϕ k • ψ k (f ). Conversely, if y ∈ π -1 (f (X)), then there exists x ∈ X such that π(y) = f (x). If x ∈ X is a lift of x then y ∈ {ρ(f )( x), J •ρ(f )( x)} = {ρ(f )( x), ρ(f )(J( x))} ⊂ ρ(f )( X)
, which proves the claim. Let Φ 1 : π 1 Top(N ) -→ π 1 Top + (S) denote the homomorphism induced by ρ on the level of fundamental groups. We now take the long exact sequence in homotopy of the commutative diagram (3.2). The form of the resulting commutative diagram depends on the genus g of N , hence we consider the following three cases.

(a) Suppose that g ≥ 3. Then by [START_REF] Hamstrom | Homotopy groups of the space of homeomorphisms on a 2-manifold[END_REF], π 1 Top(N ) and π 1 Top + (S) are trivial, and we obtain the commutative diagram of (1.4). Since ϕ k# (resp. φ) is injective by [START_REF] Gonçalves | Surface braid groups and coverings[END_REF] (resp. by Proposition 2.3), the injectivity of φ k follows from the 5-Lemma. (b) Suppose that g = 1. Using [START_REF] Gonçalves | Surface braid groups and coverings[END_REF][START_REF] Scott | Braid groups and the group of homeomorphisms of a surface[END_REF], we obtain the following commutative diagram of short exact sequences:

(3.3) 1 Z/2Z π 1 Top(RP 2 ) B k (RP 2 ) M CG(RP 2 ; k) 1 1 Z/2Z π 1 Top + (S 2 ) B 2k (S 2 ) M CG(S 2 ; 2k) 1, Φ 1 ϕ k# φ k
where in both cases, Z/2Z is identified with the subgroup generated by the full-twist braid of the corresponding braid group. Since ϕ k# is injective by [START_REF] Gonçalves | Surface braid groups and coverings[END_REF], so is Φ 1 , and a routine diagram-chasing argument shows that φ k is injective. (c) Finally suppose that g = 2, so that N is the Klein bottle K and S is the torus T . Let k ≥ 1. We claim that Ker(φ k ) ⊂ P M CG(K; k). To prove this, let X = {x 1 , . . . , x k }. Let σ : M CG(K; k) -→ Σ k and σ : M CG(T ; 2k) -→ Σ 2k denote the usual homomorphisms onto the symmetric groups of X and X respectively as described in equation (1.2). From the geometric construction of

ρ k , if 1 ≤ i, j ≤ k and σ([f ])(x i ) = x j then σ([ρ k (f )])(y i ) ∈ π -1 (x j ). If [f ] ∈ Ker(φ k ), where f ∈ Top(K, X), then [ρ k (f )] = φ k ([f ]) = [Id S ]. In particular, σ([ρ k (f )]) = Id S 2k , so for all 1 ≤ i ≤ k, σ([ρ k (f )])(y i ) = y i , and it follows that σ([f ])(x i ) = x i , whence [f ] ∈ P M CG(K; k) as claimed.
It thus suffices to prove that the restriction

φ k P M CG(K;k) of φ k to P M CG(K; k) is injective. Now assume that k ≥ 2. Let p k : F k (K) -→ F k-1 (K) (resp. q k : Top F (K; k) -→ Top F (K; k -1)
) be the map given by forgetting the last coordinate (resp. the marking on the last point). Let D

(2)

2k (T ) = F 2k (T )/ Z 2 × • • • × Z 2 k times , let B (2) 2k (T ) = π 1 D (2) 2k (T ). Let p 2k : D (2) 2k (T ) -→ D (2)
2(k-1) (T ) be the map given by forgetting the last two coordinates, and let q 2k : Top + F (T ; 2k) -→ Top + F (T ; 2(k -1)) be the map defined in the proof of Lemma 3.2(b). Then we have the following commutative diagram whose rows are fibrations:

(3.4) Top + F (T ; 2(k -1)) / / Top + (T ) δ 2(k-1) / / D (2) 2(k-1) (T ) Top + F (T ; 2k) / / q 2k O O Top + (T ) δ 2k / / D (2)
2k (T )

p 2k O O Top F (K; k) / / ρ k |Top F (K;k) O O q k Top(K) ρ O O δ k / / F k (K) ϕ k O O p k Top F (K; k -1) / / ρ k-1|Top F (K;k-1)
Top(K)

ρ δ k-1 / / F k-1 (K) ϕ k-1 Top + F (T ; 2(k -1)) / / Top + (T ) δ 2(k-1) / / D (2)
2(k-1) (T ).

The map

δ k : Top(K) -→ F k (K) (resp. δ 2k : Top + (T ) -→ D (2) 2k (T )) is defined by: δ k (f ) = (f (x 1 ), . . . , f (x k )) (resp. δ 2k ( f ) = f (π -1 (x 1 )), . . . , f (π -1 (x k )) )
for all f ∈ Top(K) (resp. for all f ∈ Top + (T )), and the map ϕ k :

F k (K) -→ D (2) 2k (T ) is defined by ϕ k (v 1 , . . . , v k ) = (π -1 (v 1 ), . . . , π -1 (v k )) for all (v 1 , . . . , v k ) ∈ F k (K).
Note also that the diagram remains commutative if we identify the corresponding terms of the first and last rows. Taking the long exact sequence in homotopy of the diagram (3.4) and applying Lemma 3.2, we obtain the following commutative diagram whose rows are exact:

(3.5)

1 π 1 Top + (T ) B (2) 2(k
-1) (T ) π 0 Top + F (T ; 2(k -1)) M CG(T ) 1 1 π 1 Top + (T ) B (2) 2k (T ) π 0 Top + F (T ; 2k) M CG(T ) 1 1 π 1 Top(K) P k (K) P M CG(K; k) M CG(K) 1 1 π 1 Top(K) P k-1 (K) P M CG(K; k -1) M CG(K) 1 1 π 1 Top + (T ) B (2) 2(k-1) (T ) π 0 Top + F (T ; 2(k -1)) M CG(T ) 1, ( δ 2(k-1) ) # ∂ 2(k-1) τ 2(k-1) ( δ 2k ) # ∂ 2k ( p 2k ) # τ 2k ( q 2k ) # (δ k ) # Φ 1 ∂ k ( φ k ) # (p k ) # τ k (q k ) # ϕ k |PMCG(K;k) ϕ (δ k-1 ) # Φ 1 ∂ k-1 ( φ k-1 ) # τ k-1 ϕ k-1|P M CG(K;k-1) ϕ ( δ 2(k-1) ) # ∂ 2(k-1) τ 2(k-1)
where ∂ 2(k-1) , ∂ 2k , ∂ k and ∂ k-1 are the boundary homomorphisms associated with the corresponding fibrations of (3.4), τ 2(k-1) , τ 2k , τ k-1 and τ k are the restrictions of these homomorphisms to the given groups, ( q 2k ) # and (q k ) # are the maps induced by q 2k and q k respectively on the level of π 0 , and ( δ 2(k-1) ) # , ( δ 2k ) # , (δ k ) # and (δ k-1 ) # are the homomorphisms induced by δ 2(k-1) , δ 2k , δ k and δ k-1 on the level of π 1 . The homomorphism φ is given by Proposition 2.3, and ( ϕ k ) # is the restriction of ϕ k# to P k (K), so is injective by [START_REF] Gonçalves | Surface braid groups and coverings[END_REF]. We remark that π 1 Top(K) ∼ = Z (resp. π 1 Top + (T ) ∼ = Z 2 ), and may be identified with the centre of B k (K) (resp. of B 2k (T )), which in fact lies in P k (K) (resp. in P 2k (T )).

Once more, the diagram (3.5) remains commutative if we identify the corresponding groups of the first and last rows. In particular, the second and third columns yield respectively:

( p 2k ) # • ( ϕ k ) # = ( ϕ k-1 ) # • (p k ) # (3.6) ( q 2k ) # • φ k P M CG(K;k) = φ k-1 P M CG(K;k-1) • (q k ) # . (3.7)
We recall at this point that our aim is to show that the homomorphism

φ k P M CG(K;k) is injective. Note that by diagram (3.5), ( ϕ k ) # • (δ k ) # = ( δ 2k
) # , and it follows from the exactness of (3.5) and the injectivity of ( ϕ k ) # that Φ 1 is also injective. We claim that the restriction

(3.8) ∂ 2k Ker(( p 2k ) # ) : Ker(( p 2k ) # ) -→ Ker(( q 2k ) # ) is an isomorphism. Indeed: (i) it is well defined. Indeed, if x ∈ Ker(( p 2k ) # ) then by the commutative diagram (3.5), ( q 2k ) # • ∂ 2k (x) = ∂ 2(k-1) • ( p 2k ) # (x) = 1, so ∂ 2k (x) ∈ Ker(( q 2k ) # ). (ii) suppose that x ∈ Ker( ∂ 2k Ker(( p 2k ) # ) )
. By exactness of the second row of the diagram (3.5), there exists z ∈ π 1 Top + (T ) such that ( δ 2k ) # (z) = x, and by commutativity of the same diagram, (

δ 2(k-1) ) # (z) = ( p 2k ) # • ( δ 2k ) # (z) = ( p 2k ) # (x) = 1. But ( δ 2(k-1)
) # is injective, so z = 1, whence x = 1. Thus ∂ 2k Ker(( p 2k ) # ) is injective too. (iii) let y ∈ Ker(( q 2k ) # ). Using commutativity and exactness of the second row of the diagram (3.5), we have y ∈ Ker( τ 2k ), so there exists w ∈ B

2k (T ) such that ∂ 2k (w) = y, and thus ( p 2k ) # (w) ∈ Ker( ∂ 2(k-1) ). Hence there exists z ∈ π

1 Top + (T ) such that ( p 2k ) # (w) = ( δ 2(k-1) ) # (z) = ( p 2k ) # • ( δ 2k ) # (z). It follows that w( δ 2k ) # (z -1 ) ∈ Ker(( p 2k ) # )
, and that ∂ 2k (w( δ 2k ) # (z -1 )) = ∂ 2k (w) = y by exactness of the second row of (3.5), which proves that ∂ 2k Ker(( p 2k ) # ) is surjective. In a similar manner, one may show that the restriction

(3.9) ∂ k Ker((p k ) # ) : Ker((p k ) # ) -→ Ker((q k ) # )
is also an isomorphism, and if w ∈ Ker((q k ) # ) then ( q 2k ) # (φ k (w)) = φ k-1 ((q k ) # (w)) = 1 by equation (3.7), and so φ k (w) ∈ Ker(( q 2k ) # ). We thus obtain the following commutative diagram of short exact sequences:

(3.10)

1 / / Ker((q k ) # ) / / φ k Ker((q k ) # ) P M CG(K; k) (q k ) # / / φ k |PMCG(K;k) P M CG(K; k -1) / / φ k-1|P M CG(K;k-1) 1 1 / / Ker(( q 2k ) # ) / / π 0 Top + F (T ; 2k) ( q 2k ) # / / π 0 Top + F (T ; 2(k -1)) / / 1,
the second arrow in each row being inclusion. We claim that φ k Ker((q k ) # ) is injective. This being the case, if φ k-1 P M CG(K;k-1) is injective then φ k P M CG(K;k) is also injective by the commutativity and exactness of the rows of (3.10). By induction on k, to complete the proof in the case g = 2, it will thus suffice to prove that the homomorphism φ 1 : M CG(K; 1) -→ M CG(T ; 2) is injective, which we shall do shortly (note that P M CG(K; 1) = M CG(K; 1), so we may remove the restriction symbol from φ 1 ). We first prove the claim. Let y ∈ Ker((q k ) # ) be such that φ k (y) = 1. From the isomorphism (3.9), there exists a unique x ∈ Ker((p k ) # ) such that ∂ k (x) = y. By (3.6), we have

( p 2k ) # • ( ϕ k ) # (x) = ( ϕ k-1 ) # • (p k ) # (x) = 1, so ( ϕ k ) # (x) ∈ Ker(( p 2k ) # ). On the other hand, ∂ 2k • ( ϕ k ) # (x) = φ k • ∂ k (x) = φ k (y) = 1 by commutativity of the diagram (3.5), hence ( ϕ k ) # (x) ∈ Ker( ∂ 2k
). So ( ϕ k ) # (x) = 1 by the isomorphism (3.8). But ( ϕ k ) # is the restriction of ϕ k# to P k (K), so is injective [START_REF] Gonçalves | Surface braid groups and coverings[END_REF]. Thus x = 1, y = 1, and therefore φ k Ker((q k ) # ) is injective as claimed.

It thus remains to show that the homomorphism φ 1 : M CG(K; 1) -→ M CG(T ; 2) is injective. Suppose that w ∈ Ker(φ 1 ). Taking k = 1, the second and third rows of diagram (3.5) become:

(3.11)

1

/ / Z(P 1 (K))

(δ 1 ) # / / Φ 1 P 1 (K) ∂ 1 / / ϕ 1# M CG(K; 1) τ 1 / / φ 1 M CG(K) Z 2 ⊕Z 2 φ / / 1 1 / / Z(P 2 (T )) ( δ 2 ) # / / B 2 (T ) ∂ 2 / / M CG(T ; 2) τ 2 / / M CG(T ) SL(2,Z) / / 1, Since φ•τ 1 (w) = τ 2 •φ 1 (w) = 1
, we see that τ 1 (w) ∈ Ker(φ), and so by Remark 2.4, τ 1 (w) is either equal to the mapping class of the identity of M CG(K), in which case we say that w is of type one, or is equal to the mapping class of the automorphism α -→ α β -→ αβ, in which case we say that w is of type two. Recall that P 1 (K) = α, β | αβαβ -1 and Z(P 1 (K)) = Z(β 2 ), and every element of P 1 (K) may be written (uniquely) in the form α r β s , where r, s ∈ Z. By the Appendix, B 2 (T ) = x, y, a, b, σ and Z(P 1 (T )) = Z(a) ⊕ Z(b), where the given generators of B 2 (T ) are subject to the relations of Theorem A.2. The group B 2 (T ) contains (3.12)

P 2 (T ) = F 2 (x, y) ⊕ Z(a) ⊕ Z(b)
as an index two subgroup, where F 2 (x, y) is the free group on {x, y}. The homomorphism ϕ 1# is given by ϕ 1# (α) = a -1 x 2 and ϕ 1# (β) = yσ -1 . Using the relations of Theorem A.2, one may check that ϕ 1# (β 2 ) = b. First assume that w ∈ Ker(φ 1 ) is of type one. Then w ∈ Ker(τ 1 ), and by exactness of the first row of (3.11), there exists w ∈ P 1 (K) such that ∂ 1 (w ) = w, and so w = α r β s , where r, s ∈ Z are unique. If w ∈ β 2 then ∂ 1 (w ) = 1 by exactness of the first row of (3.11), and the conclusion clearly holds. So suppose that either s is odd or r = 0. Then (3.13)

ϕ 1# (w ) = (a -1 x 2 ) r (yσ -1 ) s = x 2r a -r b s/2 if s is even x 2r ya -r b (s-1)/2 σ -1 if s is odd, using the fact that Z(B 2 (T )) = a, b . Since ( δ 2 ) # • ϕ 1# (w ) = φ 1 • ∂ 1 (w ) = φ 1 (w) = 1,
by observing the induced permutation of ϕ 1# (w ), we conclude that s must be even, so ϕ 1# (w ) ∈ P 2 (T ), and that ϕ 1# (w ) ∈ a, b by exactness of the second row of (3.11). Using the decomposition (3.12), it follows that r = 0, which yields a contradiction. So if w ∈ Ker(φ 1 ) is of type one then w = 1. Now suppose that w ∈ Ker(φ 1 ) is of type

α β β α h ------→ α β β h(α) = α h(β)
Figure 1. The homeomorphism h of K.

two. Consider the basepoint-preserving homeomorphism h of K illustrated in Figure 1.

Observe that τ 1 ([h]) = τ 1 (w), so by exactness of the first row of (3.11), there exists w ∈ P 1 (K) such that w = [h] ∂ 1 (w ). Let r, s ∈ Z be such that w = α r β s . Now h lifts to an orientation-preserving homeomorphism h ∈ Top + (T, X) that is illustrated in Figure 2, where X = { x 1 , x 2 } is the inverse image of the basepoint of K under π. It follows that h = ρ 1 (h), and hence

[ h] = [ρ 1 (h)] = φ 1 ([h]
). On the other hand, relative to the chosen generators of P 2 (T ), the generator x is represented by the loop c based at x 1 , and a is represented by two loops, namely c and a parallel copy c of c based at x 2 . The loop c represents the element x -1 a of P 2 (T ). Using the definition of ∂ 2 , we must find a homotopy H of T starting at the identity, i.e. H(•, 0) = Id T , for which the evaluation of the homotopy at the points x 1 and x 2 yields the braid x -1 a. Let H be the homotopy obtained by pushing x 2 along the loop c and that satisfies H(•, 1) = h. This homotopy clearly has the desired trace (or evaluation), and so ∂ 2 (x -1 a) = [ h]. Since w ∈ Ker(φ 1 ), we have:

c d d c c x 1 x 2 h ------→ c d d h(c) = c h(d)
1 = φ 1 (w) = φ 1 ([h] ∂ 1 (w )) = [ h] ∂ 2 • ϕ 1# (w ) = ∂ 2 (x -1 aϕ 1# (w )),
by commutativity of the diagram (3.11), where ϕ 1# (w ) is given by equation (3.13).

Once more, by considering the induced permutation of x -1 aϕ 1# (w ), s must be even, and so ∂ 2 (x 2r-1 a -r+1 b s/2 ) = 1, where x 2r-1 a -r+1 b s/2 ∈ P 2 (T ) is in the normal form of equation (3.12). Since r ∈ Z, we thus obtain a contradiction. We conclude that φ 1 M CG(K;1) is injective, and this completes the proof of the theorem.

Cohomological aspects of mapping class groups of punctured surfaces

In this section, we study the (virtual) cohomological dimension of surface braid groups and mapping class groups with marked points, and we prove Theorem 1.2 and Proposition 1.3.

Proof of Theorem 1.2. Let g, k ≥ 1, and let S = S g or N g+1 . Since P k (S) is of (finite) index k! in B k (S), and F k (S) is a finite-dimensional CW-complex and an Eilenberg-Mac Lane space of type K(π, 1) [START_REF] Fadell | Configuration spaces[END_REF], the cohomological dimensions of P k (S) and B k (S) are finite and equal, so it suffices to determine cd(P k (S)). Let us prove by induction on k that cd(P k (S)) = k +1 and that H k+1 (P k (S), Z) = 0. The result is true if k = 1 since then F 1 (S) = S, H 2 (π 1 (S), Z) = 0 and cd(P 1 (S)) = cd(π 1 (S)) = 2. So suppose that the induction hypothesis holds for some k ≥ 1. The Fadell-Neuwirth fibration p : F k+1 (S) -→ F k (S) given by forgetting the last coordinate gives rise to the following short exact sequence of braid groups:

(4.1) 1 -→ N -→ P k+1 (S) p # -→ P k (S) -→ 1,
where N = π 1 (S \ {x 1 , . . . , x k }, x k+1 ), (x 1 , . . . , x k ) being an element of F k (S), and p # is defined geometrically by forgetting the last string. Since S \ {x 1 , . . . , x k } has the homotopy type of a bouquet of circles, H i (S \ {x 1 , . . . , x k }), A) is trivial for all i ≥ 2 and for any choice of local coefficients A, and H 1 (S \ {x 1 , . . . , x k }), Z) = 0, hence cd(N ) = 1. By [6, Chapter VIII], it follows that cd(P k+1 (S)) ≤ cd(P k (S)) + cd(N ) ≤ k + 2. To conclude the proof of the theorem, it remains to show that there exist local coefficients A such that H k+2 (P k+1 (S), A) = 0. We will show that this is the case for A = Z. By the induction hypothesis, we have H k+1 (P k (S), Z) = 0. Consider the Serre spectral sequence with integral coefficients associated to the fibration p. Then we have that:

E p,q 2 = H p P k (S), H q (S \ {x 1 , . . . , x k }) . Since cd(P k (S)) = k + 1 and cd(S \ {x 1 , . . . , x k }) = 1 from above, this spectral sequence has two horizontal lines whose possible non-vanishing terms occur for 0 ≤ p ≤ k + 1 and 0 ≤ q ≤ 1. We claim that the group E k+1,1 2 is non trivial. To see this, first note that H 1 (S \{x 1 , . . . , x k }), Z) is isomorphic to the free Abelian group of rank r, where r = 2g+k-1 if S = S g and r = g + k if S = N g+1 , so r ≥ 2, and hence E k+1,1 2 = H k+1 P k (S), Z r , where we identify Z r with (the dual of) N Ab , the Abelianisation of N . The action of P k (S) on N by conjugation induces an action of P k (S) on N Ab . Let H be the subgroup of N Ab generated by the elements of the form α(x)x, where α ∈ P k (S) and x ∈ N Ab and α(x) represents the action of α on x. Then we obtain a short exact sequence 0 -→ H -→ N Ab -→ N Ab /H -→ 0 of Abelian groups, and the long exact sequence in cohomology applied to P k (S) yields: The last term is zero since cd(P k (S)) = k + 1, and so the map between the remaining two terms is surjective. So to prove that E k+1,1 2 is non trivial, it suffices to show that H k+1 (P k (S), N Ab /H) is non trivial. To do so, we first determine N Ab /H. Suppose first that S = S g , and consider the presentation of P k (S) on N Ab given in [START_REF] Gonçalves | On the structure of surface pure braid groups[END_REF]Corollary 8]. With the notation of that paper, a basis B of N is given by: {ρ k+1,r , τ k+1,r , C i,k+1 | 1 ≤ r ≤ g, 1 ≤ i ≤ k -1} , and a set of coset representatives in P k+1 (S) of a generating set S of P k (S) is given by {ρ m,r , τ m,r , C i,j | 1 ≤ r ≤ g, 1 ≤ i < j ≤ k, 1 ≤ m ≤ k}. Using [12, Table 1 and Theorem 7 or Corollary 8], one sees that the commutators of the elements of S with those of B project to the trivial element of N Ab , with the exception of [ρ m,r , τ k+1,r ] and [τ m,r , ρ k+1,r ] that project to (the coset of) C m,k+1 for all m = 1, . . . , k -1 (we take the opportunity here to correct a couple of small misprints in these results: relation [START_REF] Hamstrom | Homotopy groups of the space of homeomorphisms on a 2-manifold[END_REF] of Theorem 7 should read as in relation (XII n ) of Corollary 8; and in Table 1, in each of the three rows, the first occurrence of j > k should read j < k). Note that we obtain a similar result for m = k, but using the surface relation [12, equation (1)] in P k+1 (S) and taking i = k + 1 yields no new information. It follows that H is the subgroup of N Ab generated by the C m,k+1 , where 1 ≤ m ≤ k -1, and that N Ab /H is the free Abelian group generated by the coset representatives of the ρ k+1,r

Proposition 3 . 1 .

 31 Let k ≥ 1, and consider the homomorphism ψ 2k# : π 1 (Top + (T )) -→ B 2k (T ) induced by the map ψ 2k defined above. Then π 1 (Top + (T )) ∼ = Z 2 , and Im( ψ 2k# ) = Z(B 2k (T )) ⊂ P 2k (T ).Proof. First, by [17, Theorem 2, p. 63]), π 1 (Top + (T )) ∼ = Z 2 . Secondly, taking Top + (T ) to be equipped with Id T as its basepoint, a representative loop of an element γ ∈ π 1 (Top + (T ), Id T ) is a path in Top + (T ) from Id T to itself. It follows from the definition of ψ 2k that ψ 2k# (γ) ∈ P 2k (T ). It remains to show that Im( ψ 2k# ) = Z(B 2k (T )). Since Im( ψ 2k# ) ⊂ P 2k (T ), the homomorphism ψ 2k# coincides with the homomorphism of [3, Theorem 1]. Using the exact sequence of that theorem and [3, Corollary 1.3], we see that Im( ψ 2k# ) = a 1 , b 1 , where a 1 and b 1 are the generators of P 2k (T ) defined in [2, Theorem 5]. But by [29, Proposition 4.2], these two elements generate the centre of B 2k (T ) as required.

Figure 2 .

 2 Figure 2. A lift h to T of the homeomorphism h.

( 4 . 2 )

 42 • • • -→ H k+1 (P k (S), N Ab ) -→ H k+1 (P k (S), N Ab /H) -→ H k+2 (P k (S), H) -→ • • • .

and τ k+1,r , where 1 ≤ r ≤ g. In particular, N Ab /H ∼ = Z 2g . Since the induced action of P k (S) on N Ab /H is trivial, using the induction hypothesis, we conclude that: H k+1 (P k (S), N Ab /H) = H k+1 (P k (S), Z) 2g = 0.

It then follows from (4.2) that E k+1,1 2 = H k+1 (P k (S), N Ab ) = 0. Since E p,q 2 = 0 for all p > k + 1 and q > 1, we have E k+1,1

∞ is non trivial, and hence H k+2 (P k+1 (S), Z) = 0. This proves the result in the orientable case. Now let us turn to the non-orientable case. The idea of the proof is the same as in the orientable case, but the computations for N Ab and H are a little different. We use the presentation of P k (S) given in [START_REF] Gonçalves | Braid groups of non-orientable surfaces and the Fadell-Neuwirth short exact sequence[END_REF]. With the notation of that paper, a basis B of N is given by {ρ k+1,r , B i,k+1 | 1 ≤ r ≤ g, 1 ≤ i ≤ k -1}, and a set of coset representatives in P k+1 (S) of a generating set S of P k (S) is given by {ρ

Using [START_REF] Gonçalves | Braid groups of non-orientable surfaces and the Fadell-Neuwirth short exact sequence[END_REF]Theorem 3], one sees that the commutators of the elements of S with those of B project to the trivial element of N Ab , with the exception of [ρ m,r , ρ k+1,r ] that projects to (the coset of) B -1 m,k+1 for all m = 1, . . . , k -1 and 1 ≤ r ≤ g. We obtain a similar result for m = k, and using the surface relation [13, relation (c), Theorem 3] in P k+1 (S) and taking i = k + 1 implies that the element 2 g l=1 ρ k+1,l also belongs to H using additive notation. It follows that H is the subgroup of N Ab generated by the B m,k+1 , where 1 ≤ m ≤ k -1, and the element 2 g l=1 ρ k+1,l . We conclude that

The argument then goes through as in the orientable case.

The exact sequences given by (1.4) and (3.5)

also allow us to obtain information about the virtual cohomological dimension of M CG(N

From the exact sequence given by the third row of (3.5):

since M CG(K) is finite, P M CG(K; k) has the same vcd as the quotient P k (K)/Z(P k (K)), where π 1 Top(K) ∼ = Z(P k (K)). We now prove the result by induction on k. First, the result is true for k = 1 since P 1 (K)/Z(P 1 (K)) ∼ = Z ⊕ Z 2 . Now suppose that the result holds for some k ≥ 1. Since the projection P k+1 (K) -→ P k (K) maps the centre Z(P k+1 (K)) of P k+1 (K) isomorphically onto the centre Z(P k (K)) of P k (K), we have the following short exact sequence of groups:

and the fact that cd(P k+1 (K)) = k + 2 ≤ 1 + vcd(P k+1 (K)/Z(P k+1 (K)) by Theorem 1.2, we see that vcd(P k+1 (K)/Z(P k+1 (K)) ≥ k + 1, so vcd(P k+1 (K)/Z(P k+1 (K)) = k + 1, and the result follows. (b) Let g ≥ 3. Consider the short exact sequence:

given by equation (1.4). Then by [21, Corollary 2.2] and Theorem 1.2, we have:

as required.

Appendix

In this appendix, we provide presentations of P 2 (T ) and B 2 (T ) that are adapted to our situation. From [7, Section 4], we have:

Theorem A.1. The group P 2 (T ) possesses a presentation with generators B 1,2 , ρ 1,1 , ρ 1,2 , ρ 2,1 and ρ 2,2 subject to the following relations:

If necessary, the generator B 1,2 may be suppressed from the list of generators of P 2 (T ). Using Theorem A.1, we may obtain the following useful relations in P 2 (T ):

, we obtain a new presentation of P 2 (T ) whose generators are B 1,2 , δ 1,1 , τ 1,1 , δ 2,1 and τ 2,1 , that are subject to the following relations: It follows from this presentation that P 2 (T ) is isomorphic to F 2 ⊕ Z ⊕ Z, where {x, y} is a basis of the free group F 2 , and {a, b} is a basis of the free Abelian group Z ⊕ Z. We then obtain the following presentation of B 2 (T ). The generator σ given in the statement of Theorem A.2 is the Artin generator σ 1 . The proof of the theorem is standard, and makes use of the above presentation of P 2 (T ), the short exact sequence:

1 -→ P 2 (T ) -→ B 2 (T ) -→ Z 2 -→ 1, standard results on presentations of group extensions [23, Proposition 1, p. 139], and computations of relations between the given generators by means of geometric arguments.


Valerio Modugno

Ugo Chervet

Giuseppe Oriolo

Serena Ivaldi

Learning soft task priorities for safe control of humanoid robots with constrained stochastic optimization

 we proposed a framework to automatically learn the task priorities using a stochastic optimization algorithm (CMA-ES), maximizing the robot performance for a certain behavior. Here, we learn the task priorities that maximize the robot performance, ensuring that the optimized priorities lead to safe behaviors that never violate any of the robot and problem constraints. We compare three constrained variants of CMA-ES on several benchmarks, among which two are new robotics benchmarks of our design using the KUKA LWR. We retain (1+1)-CMA-ES with covariance constrained adaptation [2] as the best candidate to solve our problems, and we show its effectiveness on two whole-body experiments with the iCub humanoid robot.

I. INTRODUCTION

Fulfilling multiple operational tasks to achieve a complex behavior while satisfying constraints is one of the challenges of whole-body control of redundant manipulators and humanoid robots. For example, let us consider the humanoid iCub (Fig. 1) that must fulfil a "global task" by reaching its hands towards two goal positions behind a wall while avoiding collisions. The global task can be decomposed as a combination of simpler elementary tasks (for example: control the end-effector, control the pose of a particular link, etc.) and constraints that guarantee a condition of feasibility over the generated motions (for example: torque and joint limits, collisions, external forces etc.).

More generally, elementary tasks can include tracking desired trajectories, regulating contact forces, controlling the center of mass for balancing etc. Constraints range from mechanical limitations (e.g., joint and torque limits) to safety specifications (e.g., collision avoidance, limiting the exchange of mechanical forces with the environment) and balance keeping for floating base platforms.

In the literature, this constrained control problem is usually solved with prioritized controllers, where a set of operational tasks are organized according to strict priorities in a hierarchy or "stack" [START_REF] Saab | Dynamic wholebody motion generation under rigid contacts and other unilateral constraints[END_REF], [START_REF] Del Prete | Prioritized motionforce control of constrained fully-actuated robots: Task space inverse dynamics[END_REF], or combined with weighting functions, also known as soft task priorities [START_REF] Salini | Synthesis of complex humanoid whole-body behavior: A focus on sequencing and tasks transitions[END_REF], [START_REF] Liu | Generalized hierarchical control[END_REF]. Constraints are either formulated as high-priority tasks or taken into account *This paper was supported by the EU FP7 project CoDyCo (n.600716) and by the EU H2020 project COMANOID (n.645097). 1 Dipartimento di Ingegneria Informatica, Automatica e Gestionale, Sapienza Universita di Roma, via Ariosto 25, 00185 Roma, Italy. modugno@diag.uniroma1.it 2 Inria, Villers-lès-Nancy, F-54600, France; CNRS, Loria, UMR n.7503 and Université de Lorraine. serena.ivaldi@inria.fr

The authors would like to thank the anonymous reviewers. The humanoid robot iCub performing a bimanual task with several tasks and constraints. In this paper we optimize the task priorities guaranteeing that the global robot behavior is safe: it never violates any of the constraints.

by quadratic programming solvers. The task priorities and their evolution in time are usually defined a priori and frequently manually tuned by experts.

A new line of research is now focused on the automatic optimization of task priorities [START_REF] Modugno | Learning soft task priorities for control of redundant robots[END_REF], [START_REF] Dehio | Multiple task optimization with a mixture of controllers for motion generation[END_REF], [START_REF] Ha | Evolutionary optimization for parameterized wholebody dynamic motor skills[END_REF], [START_REF] Lober | Variance modulated task prioritization in whole-body control[END_REF]. Most of these approaches are based on an iterative policy learning technique that needs many repetitions (rollouts) of the same experiment to find a viable solution. These frameworks poorly address the problem of constraints satisfaction when optimizing the task priorities. For example, in [START_REF] Dehio | Multiple task optimization with a mixture of controllers for motion generation[END_REF], torques are saturated for safety, and joint and velocity limits are introduced as tasks. However, satisfaction of constraints formulated as tasks cannot be ensured, especially in the case of soft tasks prioritization. In [START_REF] Ha | Evolutionary optimization for parameterized wholebody dynamic motor skills[END_REF] the balance constraint is added as an objective to the fitness function, but this is a relaxation of the constraint that does not ensure its satisfaction either. In [START_REF] Modugno | Learning soft task priorities for control of redundant robots[END_REF] we used the Covariance Matrix Adaptation-Evolutionary Strategy (CMA-ES) [START_REF] Hansen | Completely derandomized selfadaptation in evolution strategies[END_REF], a derivative-free stochastic optimization method that solves non-linear, non-differentiable optimization problems, with death penalties to enforce constraint satisfaction on the solutions. This choice was not efficient in terms of searching for the optimum solution, since the exploration could easily get stuck in a constrained region where the fitness landscape was turned into a plateau. Furthermore, many solutions had to be dropped because of constraints violation.

Ensuring that the optimization process yields a safe solution -where safety means not violating any constraintsbecomes mandatory if we want to successfully apply these solutions to a real robot [START_REF] Berkenkamp | Safe controller optimization for quadrotors with Gaussian processes[END_REF].

To approach the safety issue, in this paper we investigate constrained stochastic optimization algorithms, and we focus on three variants of CMA-ES: one with vanilla constraints, one with adaptive constraints [START_REF] Collange | Multidisciplinary optimization in the design of future space launchers[END_REF] and the (1+1)-CMA-ES with covariance constrained adaptation [START_REF] Arnold | A (1+1)-CMA-ES for constrained optimisation[END_REF]. We compare these methods with a baseline constrained optimization algorithm, (the fmincon function in Matlab). To compare the algorithms, we explicitly look for methods that can find good solutions while ensuring zero constraint violations within a reasonable computation time.

There exist standard benchmarks for constrained optimization, consisting in analytic problems with several variables and constraints and known optimal solutions. For example Arnold & Hansen [START_REF] Arnold | A (1+1)-CMA-ES for constrained optimisation[END_REF] tested (1+1)-CMA-ES on seven different problems with a number of variables ranging from 2 to 10, and a number of constraints between 1 to 9. However, in robotics the number of constraints usually grows with the number of degrees of freedom (DOF) of the robot: for example, with a 7-DOF robot, the joint position range (7 ×2) and the torque limits (7×2) already introduce 28 constraints. In humanoids and highly articulated systems, the number of DOF is higher (e.g., 32 DOF for the iCub) and so is the number of constraints. Furthermore, the number of tasks increases with the complexity of the action, especially for bimanual or whole-body movements. It is therefore necessary to design new benchmarks tailored for robotics applications to make a pondered decision about the algorithm that is most suited to solve our problem while ensuring that the constraints are never violated.

The contribution of this paper is twofold: first, we compare the performance of three constrained variants of CMA-ES with fmincon on analytic and robotic benchmarks, the latter (RB1,RB2) being new and designed ad hoc; second, we extend the framework for learning task priorities, which we proposed in [START_REF] Modugno | Learning soft task priorities for control of redundant robots[END_REF], to ensure that the optimized priorities lead to safe behaviours that never violate the constraints. We show the effectiveness of our approach by generating optimized and safe (zero constraints violations) whole-body movements on the humanoid robot iCub.

The paper is organized as follows: Section II outlines the framework for learning task priorities for controlling redundant robots; Section III describes the constrained optimization algorithms retained for the study; Section IV and V illustrate the benchmarks comparison and the experiments with the iCub humanoid robot respectively.

II. MULTITASK CONTROLLER WITH LEARNT PRIORITIES

Our method aims at automatically learning the task priorities (or task weight functions) to maximize the robot performance ensuring that the optimized priorities lead to behaviours that always satisfy the constraints. The global robot movement is evaluated by a fitness function φ that is used as a measure of the ability of the robot to fulfil its mission without violating the constraints. Our proposed method outlined in Fig. 2 extends the framework that was introduced in [START_REF] Modugno | Learning soft task priorities for control of redundant robots[END_REF]. In this section we recall the multi-tasks controller and the structure of the parametrized task weight functions α i , while the optimization procedure is described in Section III, where we analyze some recent extensions of the basic CMA-ES method that deal with constraints.

A. Controller for a single elementary task

Here, we briefly describe the torque controller for the i-th elementary task, which is presented in more detail in [START_REF] Modugno | Learning soft task priorities for control of redundant robots[END_REF]. Following our previous work, we use a regularized closed-form solution of a controller derived from the Unified Framework (UF) [START_REF] Peters | A unifying framework for robot control with redundant DOFs[END_REF]. Let us consider the rigid-body dynamics of a robot with n DOF, i.e.: M(q) q + f(q, q) = u i (q, q) where q, q, q ∈ R n are, respectively, the joints positions, velocities, and accelerations; M(q) ∈ R n×n is the generalized inertia matrix, f(q, q) ∈ R n accounts for Coriolis, centrifugal and gravitational forces; and u i (q, q) ∈ R n is the vector of the commanded torques of the i-th task. Following the UF formulation, the general torque controller

is u i = N -1 2 i (A i M -1 N -1 2 i ) † (b i + A i M -1 f
), where the matrix A i (q, q,t) ∈ R m×n and the vector b i (q, q,t) ∈ R m×1 incorporate the information about the m-dimensional task; N i is a weighting matrix that can be changed to achieve different control strategies; (•) † is the Moore-Penrose pseudoinverse; and the upper script in N -1 / 2 i denotes the inverse of the matrix square root. Controllers derived from UF are sensitive to kinematic singularities, due to the matrix inversion [START_REF] Chiaverini | Redundancy resolution for the human-arm-like manipulator[END_REF]. To overcome this problem, we reformulate the UF controller in a regularized fashion, as classically done at the kinematic level, for instance in [START_REF] Nakamura | Inverse kinematic solutions with singularity robustness for robot manipulator control[END_REF]. The resulting closedform solution of the controller for a single elementary task is then:

u i = N -1 i Mi (Iλ -1 i + Mi N -1 i Mi ) -1 (b i + Mi f) , with Mi = A i M -1
. λ i is a regularizing factor (we refer to [START_REF] Modugno | Learning soft task priorities for control of redundant robots[END_REF] for a more accurate description of the regularization problem leading to this closed-form solution).

B. Controller for multiple elementary tasks with soft task priorities

Each elementary task is modulated by a task priority or task weight function α i (t). To automatically find the optimal n t task priorities {α i (t)} i=1,...,n t , we transform the functional optimization problem into a numerical optimization problem by representing the task priorities with parametrized functional approximators α i (t) → αi ( π π π i ,t), where π π π i is the set of parameters that shape the temporal profile of the i-th task weight function. Following the scheme of Fig. 2, given n t elementary tasks the final controller is given by:

u(q, q,t) = n t ∑ i=1 αi ( π π π i ,t) u i (q, q) . (1)

C. Learning the task priorities

We model the task priorities as a weighted sum of normalized Radial Basis Functions (RBFs):

αi ( π π π i ,t) = S ∑ n r k=1 πik ψ k (µ k , σ k ,t) ∑ n r k=1 ψ k (µ k , σ k ,t) , (2)
where

ψ k (µ k , σ k ,t) = exp -1/2[(t -µ k )/σ k ] 2
, with fixed mean µ k and variance σ k of the basis functions, n r is the number of RBFs and π π π i = ( πi1 , . . . , πin r ) ⊆ R n P is the set of parameters for each task priority. S(•) is a sigmoid function that squashes the output to the range [0, 1]. The elementary task is fully activated when the task priority is equal to 1, otherwise the control action fades out until a full deactivation occurs when the priority goes to 0. The free parameters π π π i of each task weight function (Eq. 2) constitute the current parameters set to optimize: π π π = ( π π π 1 , . . . , π π π n t ). To optimize the free parameters π π π, we introduce two elements, the fitness function φ and the set of inequality and equality constraints g, h:

• the fitness function φ = φ (q t=1,...,T , u t=1,...,T ,t) computes a performance measure of the global task executed by the robot over T time steps with the current parameters π π π. The fitness function can contain different criteria ranging from energy consumption arguments to specific properties of the desired trajectories (e.g. speed and smoothness).

• the constraints g, h determine the admissible controls to be applied to the robot. They can be dependent on the robot structure (e.g. maximum joint torques and joint ranges), on the environment (e.g. obstacles and collisions), on the tasks (e.g. safety limits and couplings), etc. The objective of the next section is to formalize the problem of optimizing the parameters π π π that maximize the fitness φ , ensuring that the constraints g, h are satisfied.

III. CONSTRAINED BLACK-BOX OPTIMIZATION OF TASK

PARAMETERS

Learning the parameters π π π ∈ Π Π Π ⊆ R n P is a constrained optimization problem, as we need to find the optimal parameters π π π • that maximize the objective function J(π π π) : R n P → R (by default, equivalent to the fitness φ ):

π π π • = arg max π π π J(π π π)
under the inequality and equality constraints g, h:

g i (π π π) ≤ 0, i = 1, . . . , n IC ; h j (π π π) = 0, j = 1, . . . , n EC .
Following our approach in [START_REF] Modugno | Learning soft task priorities for control of redundant robots[END_REF], we do not constrain the fitness structure nor its differentiability properties, hence we keep solving the problem with derivative-free methods. In [START_REF] Modugno | Learning soft task priorities for control of redundant robots[END_REF] we used CMA-ES [START_REF] Hansen | Completely derandomized selfadaptation in evolution strategies[END_REF] for the known advantage of having to tune few parameters. To find feasible solutions that satisfy the constraints, we adopted a death penalty approach. This was clearly not efficient; the constant penalty applied to the fitness has a pathological effect on the exploration of the algorithm, possibly causing the search to get stuck in infeasible regions.

In this paper, we adopt a different strategy and look explicitly for variants of CMA-ES that take into account the constraints in the exploration procedure. Our goals are: 1) to improve the efficiency of the optimization procedure exploiting the constraint information, and 2) to guarantee that every solution found by the stochastic optimization process lies in a region of the parameter space that satisfies all the constraints. Interestingly, we are not interested in algorithms that permit constraints relaxation (hence violation) to find a solution: this is typically the case of real-time quadratic solvers (e.g. quadprog and qpOASES).

Among the multitude of constrained black-box optimization algorithms, we focused on three variants of CMA-ES: a vanilla penalty CMA-ES, the CMA-ES with adaptive penalty approach proposed in [START_REF] Collange | Multidisciplinary optimization in the design of future space launchers[END_REF] and the (1+1)-CMA-ES with covariance constrained adaptation proposed in [START_REF] Arnold | A (1+1)-CMA-ES for constrained optimisation[END_REF]. The first is a baseline CMA-ES that applies a penalty to the fitness that is proportional to the constraint violation. The second method is similar in principle, but the penalty weights are changed following a heuristic that depends on the constraint violation The third does not rely on penalties but updates the covariance whenever a constraint is violated, to drive the exploration away from infeasible regions.

In the rest of this section, we outline the three methods explaining their differences with respect to CMA-ES. In the presentation, we will use the following symbols:

• J(•): objective function • n IC : number of inequality constraints g i (•) • n EC : number of equality constraints h i (•) • n C = n IC + n EC : total number of constraints • Π Π Π ⊆ R n P : parameter space • π π π k ∈ Π Π Π: k-th
N ( π π π, Σ Σ Σ): Gaussian distribution with mean π π π and co- variance Σ Σ Σ • σ 2 : step size • l(π π π k ): penalty factor • Ĵ(π π π k ) = J(π π π k ) + l(π π π k ): penalized objective function

A. Stochastic optimization with CMA-ES (no constraints)

A single iteration (called generation) of CMA-ES [10] consists of several steps. A set of K samples π π π k is drawn from a multivariate Gaussian distribution N ( π π π, σ 2 Σ Σ Σ) with a σ 2 step size; for each sample π π π k we perform the evaluation of the objective function J, called fitness. The samples are sorted using a ranking procedure based on the fitness and an update of the Gaussian distribution is performed according to the best K e candidates π π π 1:K e , called elites.

The update step affects the mean, covariance, and step size of the search distribution N ( π π π, σ 2 Σ Σ Σ). The evolution of the mean is influenced by the probability weights P k of each elite CMA-ES without constraints In CMA-ES, premature convergence is avoided by tuning the step size σ 2 . Both σ 2 and Σ Σ Σ are updated by combining the information from the last generation and all the previous ones. For the update of the stepsize σ 2 and more detail about the algorithm, we refer the reader to [START_REF] Hansen | Completely derandomized selfadaptation in evolution strategies[END_REF]. To initialize CMA-ES the user has to specify the exploration rate, a scalar value between [0,1] that controls the starting value of the covariance matrix. Fig. 3 shows the pseudo-code of the algorithm.

function CMA-ES for each gen = 1, . . . , n GENERAT IONS do for each k = 1, . . . , K do π π π k ∼ N ( π π π, σ 2 Σ Σ Σ) samples J k = J(π π π k ) evaluation end for π π π 1:Ke = SORT(π π π k=1:K , J k=1:K ) sorting π π π new = ∑ Ke k=1 P k π π π k with ∑ Ke k=1 P k = 1 Σ Σ Σ new = UPDCOV( π π π new , P k=1:Ke ) σ new = UPDSIGMA(σ ) π π π = π π π new Σ Σ Σ = Σ Σ Σ new σ = σ new end for end function

B. CMA-ES with Vanilla Constraints

The vanilla penalty functions method relies on adding a penalty term to the fitness of a candidate that depends on the constraints violation of the candidate. The method employs a penalized objective function Ĵ(π π π k ) = J(π π π k ) + l(π π π k ) with the penalty factor l(π π π k ) defined as:

l(π π π k ) = ∑ n IC i=1 r i max(0, g i (π π π k )) 2 + ∑ n EC j=1 c j |h j (π π π k )|
where r i and c i are positive constant values. In Fig. 4 we present a pseudo-code for this variant where we refer to the penalization routine with PENALTY(•).

C. CMA-ES with Adaptive Constraints

The previous method is by far the simplest and the most intuitive, as it applies a penalty that depends on the candidate π π π k . However, one may want to make the penalty term variable, for example depending on the exploration path.

Collange et al. [START_REF] Collange | Multidisciplinary optimization in the design of future space launchers[END_REF] proposed a penalty function approach where a set of adaptive weights are tuned to prevent the search process from getting stuck in a local minima of the penalized fitness function Ĵ(•). A penalized objective function Ĵ(π π π k ) is therefore used. The key idea is that the penalty factor l(π π π k ) is built to consider the number of feasible solutions per each generation and the activation of each constraint, determined by a heuristic tuned by a user-defined

ε i . In particular, one assigns l(π π π k ) = ∑ n C i=1 w i [γ + i (π π π k )] 2
, where w i , i = 1, . . . , n C is the set of adaptive weights, and γ + i (•) is the positive part of the so-called ε-normalized constraint values γ i , which are used to identify the active constraints. The ε-normalized constraint values γ i are defined as:

γ i = [g i (π π π k ) + ε i ]/ε i for inequality constraints |h i (π π π k )|/ε i for equality constraints . (3)
The user can tune the definition of the constraint violations and the relaxation of the constraints through the parameters

ε i > 0, i = 1, . . . , n C .
For equality constraints h i (•), a candidate solution π k is labelled "feasible" if 0 ≤ γ i ≤ 1 and "infeasible" otherwise. For inequality constraints g i (•), a candidate solution π k is labelled "feasible" if γ i ≤ 1 and "infeasible" otherwise (Fig. 5). The weights update is driven by the ratio of feasible solutions for all the constraints: only when all the samples satisfy the i-th constraint for n P +2 generations. Once this condition is met, the weight w i related to the i-th constraint is decreased almost surely (in a statistical sense). The adaptation rule for the weight w i after each generation is defined as: w i = w i exp(p targetr f eas i ), where p target is a value that changes at each iteration according to p target = (1/Kn P ) 1/D , where D represents the cardinality of the elements' set that satisfies i = 1, . . . , n C : r f eas i < 1 and K is the number of samples. As a rule of thumb, when r f eas i > p target the weight w i decreases, otherwise it increases. In Fig. 4 we provide a pseudo-code for this variant, where we refer to the weight computation routine as UPDATEWEIGHT(•). For more detail on the method we refer to [START_REF] Collange | Multidisciplinary optimization in the design of future space launchers[END_REF].

This method is more interesting since the penalty factor applied to the objective function changes during the optimization process depending on the number of feasible solutions that do not violate the constraints, considering the relaxation acting on the equality constraints. With respect to the vanilla method, the penalty factor here is not constant over the parameter space and depends on the exploration path in the parameter space. This decreases the possibility of getting stuck in local minima or flat areas of the fitness.

D. (1+1)-CMA-ES with Covariance Constrained Adaptation

The third method, proposed by Arnold et al. [START_REF] Arnold | A (1+1)-CMA-ES for constrained optimisation[END_REF], is an extension of (1+1)-CMA-ES with active covariance adaptation [START_REF] Igel | A computational efficient covariance matrix update and a (1+1)-CMA for evolution strategies[END_REF]. As opposed to the other two methods, here we do not have a penalty factor, i.e., the objective function is unchanged, but there is a different exploration strategy that exploits the constraints information to change the covariance and keep the optimization in a feasible region.

A notable difference with the classical CMA-ES is the fact that there is only one sample per generation (π π π 1 , therefore K = 1), that is generated according to the following rule:

π π π 1 = π π π + σ Dz ( 4
)
where D is the Cholesky factor of the covariance matrix 4. Pseudocode for the three variants of constrained CMA-ES: the first is with vanilla penalty (Section III-B), the second is the adaptive penalties method of [START_REF] Collange | Multidisciplinary optimization in the design of future space launchers[END_REF] (Section III-C) and the third is a (1+1)-CMA-ES with covariance constrained adaptation as in [START_REF] Arnold | A (1+1)-CMA-ES for constrained optimisation[END_REF] (Section III-D).

Σ Σ Σ = D T D
k = 1, . . . , K do π π π k ∼ N (π π π, σ 2 Σ Σ Σ) end for for k = 1, . . . , K do J k = J(π π π k ) if CONSTRVIOLATION(π π π k ) then Ĵk = PENALTY(π π π k , J k ) end if end for π π π 1:Ke = SORT(π π π k=1:K , Ĵk=1:K ) π π π new = ∑ Ke k=1 P k π π π k with ∑ Ke k=1 P k = 1 Σ Σ Σ new = UPDCOV(π π π new , P k=1:Ke ) σ new = UPDSIGMA(σ ) π π π = π π π new Σ Σ Σ = Σ Σ Σ new σ = σ new end for end function CMA-ES with adaptive constraints function CMA-ES for each gen = 1, . . . , n GENERAT IONS do for k = 1, . . . , K do π π π k ∼ N (π π π, σ 2 Σ Σ Σ) end for for k = 1, . . . , K do J k = J(π π π k ) end for [l, r, r] = COLLECTVIOLATION(π π π k , ε ε ε) w new = UPDATEWEIGHT(w, r, r) Ĵk = WEIGHTPENALTY(w new , l) π π π 1:Ke = SORT(π π π k=1:K , Ĵk=1:K ) π π π new = ∑ Ke k=1 P k π π π k with ∑ Ke k=1 P k = 1 Σ Σ Σ new = UPDCOV(π π π new , P k=1:Ke ) σ new = UPDSIGMA(σ ) π π π = π π π new Σ Σ Σ = Σ Σ Σ new σ = σ new end for end function (1+1)-CMA-ES with Cov. Const. Adapt. function (1+1)-CMA-ES π π π = FINDFEASIBLESTARTINGPOINT() for each gen = 1, . . . , n GENERAT IONS do π π π 1 = π π π + σ Dz (Eq.4) if CONSTRVIOLATION(π π π 1 ) then D new = UPCOVCONSTR(); D = D new else J new = J(π π π 1 ) if J new > J then D new = UPCOVSUCC() σ new = UPDSIGMA(σ ) π π π = π π π 1 ; D = D new ; σ = σ new else if J new > J old then D new = UPCOVACTIVE(); D = D new end if end if end for end function Fig.
inequalities equalities feasible infeasible . . Fig. 5. This illustration shows the relation between ε i and γ i for inequality and equality constraints as in Eq. 3. As described in Section III-C, the green and red regions identify the constraint values that are respectively labeled as "feasible" and "infeasible". One may notice that ε i induces a relaxation for the equality constraint: therefore it could be possible to label as feasible a solution that violates the constraint (how much depends on ε). On the contrary, it is noticeable that γ + i in the inequality constraint also includes a boundary region determined by ε i where the constraint is satisfied. candidate outperforms the current best, s and D are updated (UPCOVSUCC in Fig. 4):

s new =(1 -c)s c(2 -c)Dz D new = 1 -c + cov D + 1 -c + cov ||w|| 2   1 + c + cov ||w|| 2 1 -c + cov -1   sw T
where c + cov and c are both factors that control the update rate of s and D respectively, while w = D -1 s. Instead, if the current candidate is feasible but its performance is lower than the predecessors, the Cholesky factor D is actively updated (UPCOVACTIVE in Fig. 4):

D new = 1 + c - cov D + 1 + c - cov ||z|| 2   1 - c - cov ||z|| 2 1 + c - cov -1   Dzz T
where c - cov is again a constant that determines the update rate. In this case s is not updated because the current candidate is not better in terms of fitness.

To handle constraints, the key idea is to update the covariance matrix, by reducing the components of Dz in the direction that is orthogonal to the constraint whenever a constraint is violated, as illustrated in Fig. 6. Each time the j-th constraint is violated, we update the corresponding constraint vector v j ∈ R n P and the matrix D (UPCOVCONSTR in Fig. 4):

v new j = (1 -c c )v j + c c Dz D new = D - β ∑ n C j=1 1 g j (π π π 1 >0) n C ∑ j=1 1 g j (π π π 1 >0) v j w T w T w
where c c and β are constants that tune the update step respectively for v j and D, w j = D -1 v j and 1 g j (π π π 1 >0) is equal to one when g j (π π π 1 ) > 0 and zero otherwise. In summary, the method searches for the optimal solution by testing one sample at the time and accounting for the constraints in the covariance adaptation to stay away from infeasible regions. The algorithm is designed in such a way that the mean of the search distribution is updated only if the fitness improves and the candidate is a feasible solution; these two elements ensure that the solution of the optimization problem always satisfies the constraints. However, unlike the other methods, this requires a feasible 1 starting candidate to work, otherwise the exploration process quickly gets stuck. Hence, this method cannot be started from scratch or random values, but needs the pre-computation of a feasible starting point. This is not an issue, since we can always find a feasible starting point that satisfies all the constraints, even if it does not enable the robot to achieve the global task goal (a quick solution is to set the robot in a feasible posture and keep this position by setting the posture task priority to 1 and the others to 0).

IV. BENCHMARKING THE ALGORITHMS

In this section we test the algorithms described in Section III to decide which one better suits our problem. We compare their performances on five different benchmarks: . . Fig. 6. This illustration shows the effect of the covariance adaptation with constraints, as described in Section III-D. A linear inequality constraint, represented by the vertical thick line, divides the parameter space into a region where the constraint is not violated (light grey) and a region where the constraint is violated (dark grey). The covariance D of the search distribution is updated in such a way that the successor samples will not fall into the region where the constraint is active: the updated covariance D new is directed orthogonally with respect to the constraint.

-g07: n P = 10, n IC = 8, n EC = 0 -g09: n P = 7, n IC = 4, n EC = 0 -HB: n P = 5, n IC = 6, n EC = 3 -RB1: n P = 15, n IC = 32, n EC = 0 -RB2: n P = 15, n IC = 50, n EC = 0 The first three are classical benchmarks for constrained optimization [START_REF] Arnold | A (1+1)-CMA-ES for constrained optimisation[END_REF], that is analytic problems with known optimal solutions; the last two are new benchmarks that we designed ad hoc to evaluate the performance of the algorithms on robotic problems with growing complexity. RB1 is a problem inspired by our previous work [START_REF] Modugno | Learning soft task priorities for control of redundant robots[END_REF] where a KUKA LWR (7DOF) has to reach a goal position with its end-effector behind an obstacle, while satisfying constraints of joint position limits, joint torque limits and obstacle avoidance. RB2 has a similar setting with the addition of a second obstacle to avoid and another set of constraints coming from joint velocity limits. To compare the performance of the algorithms on these benchmarks, we define the following metrics:

• m 1 : distance from the optimal solution, defined as m 1 = π π π •π π π * , where π π π • is the optimal solution (known) and π π π * the best solution found by the constrained optimization algorithm;

• m 2 : constraint violations, defined as

m 2 = ∑ n C i=1 | ê(i, π π π * )|
, where ê(i, π π π) = 1 g i (π π π)>0 g i (π π π) for the inequality constraints and ê(i, π π π) = 1 h i (π π π) =0 h i (π π π) for the equality constraints -basically it sums all the constraints that are violated;

• m 3 : number of steps to converge, or settling time, defined as m 3 = n sc (δ ), the number of steps after which the fitness function reaches a steady state condition, i.e., its value is bounded between ±δ % of the steady state value -here, we set δ = 2.5;

• m 4 : best fitness, defined as m 4 = J(π * ), i.e., the fitness of the best solution found by the constrained optimization algorithm. To provide a baseline, we use the (deterministic) constrained optimization function fmincon in Matlab, using the SQP method. This is a suitable choice because it does not require the gradient of the objective function for non-linear constrained optimization problem with nonlinear constraints.

Since (1+1)-CMA-ES with covariance constrained adaptation (Section III-D) needs a feasible candidate solution as a starting point, in order to make a fair comparison all the algorithms start from the same initial position. We perform 40 repetitions of the optimization process per each test problem for each algorithm with an exploration rate of 0.1 and a 5000 samples to assure the convergence of the methods. Fig. 7 shows the results of the numerical experiments with the five benchmarks. The top row reports on the results for g07, g09 and HB with metrics m 1 , m 2 , m 3 , while the bottom row reports on the results for the robotics benchmarks RB1 and RB2, with metrics m 2 , m 3 , m 4 (m 1 cannot be used in this case because the optimal solution π π π • is not known). We also compared the four algorithms in terms of computational time, and did not find significant differences (for example, the optimal solution for RB2 is found on average in 1.7e+04 s for the CMA-ES variants and 1.9e+04 s for fmincon on a i5 laptop with Matlab).

(1+1)-CMA-ES with covariance constrained adaptation offers the best trade-off between performance and constraints' satisfaction both on the analytic and the robotic benchmarks. It always ensures full satisfaction of the constraints while the other methods sometimes fail. Its settling time is comparable to the other stochastic algorithms, while fmincon converges faster. fmincon could seem more appealing, but on the robotic benchmarks its best fitness is lower and actually quite close to the fitness of the starting point (meaning that the algorithm does not really "explore"). Therefore fmincon does not seem a suitable candidate for solving robotic problems with a lot of constraints.

The different performances of the algorithms in the analytic and robotic benchmarks confirm the benefit gained by designing two new robotics benchmarks RB1,RB2. Overall, considering the zero constraint violations and the capability of finding a good solution, we choose to use (1+1)-CMA-ES with covariance constrained adaptation for our experiments with the iCub robot.

V. ROBOTIC EXPERIMENTS

In this section, we apply (1+1)-CMA-ES with covariance constrained adaptation to our multi-task control framework (Section II). We use it to optimize the task priorities and to obtain a solution that never violates the constraints. In the following, we report on the experiments performed to optimize the whole-body movements of the iCub humanoid robot.

We designed two experiments using the 17 DOF of the upper-body of the robot (arms and torso). In the experimental scenario, a rectangular obstacle similar to a wall, that is as large as the robot's chest and 2 cm thick, is placed about 20 cm in front of the robot.

The first experiment is aimed at reaching a goal Cartesian position behind the wall with one hand. There are three elementary tasks. The first is about reaching the desired Cartesian position p * r = [0.35, -0.15, 0.7] (m) with the right hand frame of the robot. The second task is reaching a desired The top row reports on the results on three standard analytical constrained optimization benchmarks (g07, g09, HB -see [START_REF] Arnold | A (1+1)-CMA-ES for constrained optimisation[END_REF]). The bottom row reports on the results on two robotics benchmarks (RB1, RB2) that we designed ad hoc to evaluate the performance of the algorithms on robotics problems. Cartesian position p * elbr = [0.24, -0.23, 0.7] (m) with the elbow frame. The third task is keeping the initial joint config-uration q * = [0, 45, 0, 0, -20, 30, 0, 0, 45, 0, 0, 0, 30, 0, 0, 0, 0] (deg). In sum, the goal is hidden behind the wall, and to reach it with the hand the robot must bend its elbow around the wall corner; the third task should prevent the robot from moving the right arm and the torso. The task priorities are approximated by RBFs with n r = 5, therefore n P = 5 × 3 = 15. There are n C = n IC = 73 inequality constraints: joint position limits, joint torque limits and distance constraints to avoid collisions between the robot and the obstacle. Precisely, a minimal distance of 3 cm is required between the obstacle and a set of pre-defined collision check points (located at the origin of the frames of right shoulder, elbow, wrist, hand and head). For this experiment we use the following fitness function:

φ = - 1 2
∑ T i p r,i -p * r ε max + ∑ T i u 2 i u max (5)
where φ ∈ [-1, 0], T is the number of control steps (the task duration is 20 s, and we control at 1 ms), p r,i is the right hand frame position at time i, p * r the goal position for the hand frame and ε max = 120 and u max = 3.5 * 10 5 are two scaling factors. The first term of φ penalizes the cumulative distance from the goal, while the second term penalizes the global control effort.

The second experiment complicates the first by adding 2 more tasks. The aim is to reach a Cartesian goal position with both robot hands. Two Cartesian goal tasks for each hand and elbow are set symmetrically with respect to iCub's sagittal plane. A fifth posture task is set as to keep the torso as straight as possible during the movement. .68] (m) • Task 5 : q * = [0, 45, 0, 0, -20, 30, 0, 0, 45, 0, 0, 0, 30, 0, 0, 0, 0] (deg) The task priorities are approximated by RBFs with n r = 5, therefore n P = 5 × 5 = 25. The optimization is carried out under the same constraints as in the first experiment with the addition of the left arm collision checks. This means we have n C = n IC = 77 inequality constraints. The fitness is:

φ = - 1 2
∑ T i p r,i -p * r ε max + ∑ T i p l,i -p * l ε max + ∑ T i u 2 i u max (6)
where p l,i is the left hand frame position at time i, p * l the goal position for the left hand frame.

In all the experiments, we seek the best solutions that do not violate any of the constraints. We employ (1+1)-CMA-ES as described in Section III-D with the exploration rate set to 0.1 (this is the only parameter to tune and this is the default value!).

Fig. 8 shows the median fitness and constraint violation obtained by 25 experiments. The fitness grows nicely (φ = 0 would be the optimum). Most importantly, the constraints are never violated, which is exactly what we wanted to obtain. We also show the task priorities and the joint torques from one of the best solutions; they are both smooth, and it is clear that optimizing the task priorities manually would be very difficult if these solutions were to be achieved. The video attachment shows the robot movements in the two experiments and the activation of the tasks priorities evolving in time.

VI. CONCLUSION AND FUTURE WORK

In this paper we proposed to optimize the task priorities of multi-task controllers by a stochastic constrained optimization algorithm that ensures that the constraints are never violated. We benchmarked four constrained optimization algorithms in robotics applications and found that (1+1)-CMA-ES with covariance constrained adaptation meets our requirements in terms of fitness of the solution and constraint satisfaction. Our framework can be used to generate optimized whole-body movements that always comply with safety requirements, as shown in two bimanual experiments with the iCub. Our current limit is the computation time, therefore the method is suited at this time only for offline synthesis of whole-body behaviors of humanoid robots. Ongoing work is aimed at applying the method for safe trajectory optimization (complementary to task priority optimization) and speeding up the computation.

  Fig. 1.The humanoid robot iCub performing a bimanual task with several tasks and constraints. In this paper we optimize the task priorities guaranteeing that the global robot behavior is safe: it never violates any of the constraints.

Fig. 2 .

 2 Fig. 2.Overview of the proposed method. The controller consists of a weighted combination of elementary tasks, where the weight functions represent the soft task priorities. An outer learning loop enables the optimization of the task weight parameters, taking into account the constraint violations in an explicit way.

Fig. 3 .

 3 Fig. 3. Pseudo-code for the basic CMA-ES without constraints.

< 1 .

 1 for the i-th constraint in the curr. generation n P + 2 generation If all the samples π π π k with k = 1, . . . , K satisfy the i-th constraint, then r f eas i = 1; otherwise r f eas i So r f eas i = 1

  and z is a standard normal distributed vector z ∼ N (0 0 0, I I I). The algorithm stores the information about the successful steps in a search path s ∈ R n P . Each time aCMA-ES with vanilla constraints function CMA-ESfor each gen = 1, . . . , n GENERAT IONS do for

Fig. 7 .

 7 Fig. 7. Performance comparison of the three constrained CMA-ES algorithms and the baseline fmincon algorithm from Matlab using the SQD method.The top row reports on the results on three standard analytical constrained optimization benchmarks (g07, g09, HB -see[START_REF] Arnold | A (1+1)-CMA-ES for constrained optimisation[END_REF]). The bottom row reports on the results on two robotics benchmarks (RB1, RB2) that we designed ad hoc to evaluate the performance of the algorithms on robotics problems.

Fig. 8 .

 8 Fig. 8. Two experiments with the iCub, about reaching a goal behind the wall with one or two hands. A) The robot's movement visualized by the mex model. B) The median constraint violation and fitness optimized by (1+1)-CMA-ES with covariance constrained adaptation (over 25 experiments) the constraints are never violated C-D. The task priorities and joint torques of the best solution. The experiments are also shown in the attached video.

•

  Task 1 : p * r = [0.35, -0.15, 0.68] (m) • Task 2 : p * elbr = [0.21, -0.25, 0.68] (m) • Task 3 : p * l = [0.3, 0.0248, 0.68] (m) • Task 4 : p * elbl = [0.21, 0.1138, 0

  candidate at the current generation • K: total number of candidates for each generation • K e : number of best candidates or elites • π π π 1:K e : best candidates of the current generation •

A candidate solution is feasible if it satisfies all the constraints.