Alexander Kolpakov

Deformation of finite-volume hyperbolic Coxeter polyhedra, limiting growth rates and Pisot numbers

Keywords: hyperbolic Coxeter group, Coxeter polyhedron, growth function, Pisot number

est destinée au dépôt

Introduction

Since the work of R. Steinberg [START_REF] Steinberg | Endomorphisms of linear algebraic groups[END_REF], growth series for Coxeter groups are known to be series expansions of certain rational functions. By considering the growth function of a hyperbolic Coxeter group, being a discrete group generated by a finite set S of reflections in hyperplanes of hyperbolic space H n , J.W. Cannon [START_REF] Cannon | The growth of the closed surface groups and compact hyperbolic groups[END_REF][START_REF] Cannon | Growth functions of surface groups[END_REF], P. Wagreich [START_REF] Wagreich | The growth function of a discrete group" in Groups Actions and Vector Fields[END_REF], W. Parry [START_REF] Parry | Growth series of Coxeter groups and Salem numbers[END_REF] and W. Floyd [START_REF] Floyd | Growth of planar Coxeter groups, P.V. numbers, and Salem numbers[END_REF] in the beginning of the 1980's discovered a connection between the real poles of the corresponding growth function and algebraic integers such as Salem numbers and Pisot numbers for n = 2, 3. In particular, there is a kind of geometric convergence for the fundamental domains of cocompact planar hyperbolic Coxeter groups giving a geometric interpretation of the convergence of Salem numbers to Pisot numbers, the behaviour discovered by R. Salem [START_REF] Salem | Power series with integral coefficients[END_REF] much earlier in 1944. This paper provides a generalisation of the result by W. Floyd [START_REF] Floyd | Growth of planar Coxeter groups, P.V. numbers, and Salem numbers[END_REF] to the three-dimensional case (c.f. Theorem 5).

Preliminaries

2.1 Let G be a finitely generated group with generating set S providing the pair (G, S). In the following, we often write G for (G, S) assuming S is fixed. Define the word-norm • : G → N on G with respect to S by g = min {n | g is a product of n elements from S ∪ S -1 }. Denote by a k the number of elements in G of word-norm k, and put a 0 = 1 as usually done for the empty word.

Definition. The growth series of the group G = (G, S) with respect to its generating set S is f (t) := f S (t) = ∞ k=0 a k t k . The series f (t) has positive radius of convergence since a k ≤ (2 |S|) k . The reciprocal of the radius of convergence is called the growth rate τ of G. If G is a Coxeter group with its Coxeter generating set S (c.f. [START_REF] Humphreys | Reflection Groups and Coxeter Groups[END_REF]), then f (t) is a rational function by [START_REF] Bourbaki | Lie groups and Lie algebras[END_REF][START_REF] Steinberg | Endomorphisms of linear algebraic groups[END_REF], called the growth function of G. Let P ⊂ H n , n ≥ 2, be a finite-volume hyperbolic polyhedron all of whose dihedral angles are submultiples of π. Such a polyhedron is called a Coxeter polyhedron and gives rise to a discrete subgroup G = G(P) of Isom(H n ) generated by the set S of reflections in the finitely many bounding hyperplanes of P. We call G = G(P) a hyperbolic Coxeter group. In the following we will study the growth function of G = (G, S) = G(P).

The most important tool in the study of the growth function of a Coxeter group is Steinberg's formula.

Theorem 1 (R. Steinberg, [START_REF] Steinberg | Endomorphisms of linear algebraic groups[END_REF]) Let G be a Coxeter group with generating set S. Then

1 f S (t -1 ) = T ∈F (-1) |T | f T (t) , (1)
where F = {T ⊆ S | the subgroup of G generated by T is finite}.

Consider the group G = G(P) generated by the reflections in the bounding hyperplanes of a hyperbolic Coxeter polyhedron P. Denote by Ω k (P), 0 ≤ k ≤ n -1 the set of all k-dimensional faces of P. Elements in Ω k (P) for k = 0, 1 and n -1 are called vertices, edges and facets (or faces, in case n = 3) of P, respectively. Observe that all finite subgroups of G are stabilisers of elements F ∈ Ω k (P) for some k ≥ 0. By the result of Milnor [START_REF] Milnor | A note on curvature and fundamental group[END_REF], the growth rate of a hyperbolic group is strictly greater than 1. Hence, the growth rate of the reflection group G(P) is τ > 1, if P is compact, and the growth function f S (t) has a pole in (0, 1).

2.2

In the context of growth rates we shall look at particular classes of algebraic integers.

Definition. A Salem number is a real algebraic integer α > 1 such that α -1 is an algebraic conjugate of α and all the other algebraic conjugates lie on the unit circle of the complex plane. Its minimal polynomial over Z is called a Salem polynomial.

Definition. A Pisot-Vijayaraghavan number, or a Pisot number for short, is a real algebraic integer β > 1 such that all the algebraic conjugates of β are in the open unit disc of the complex plane. The corresponding minimal polynomial over Z is called a Pisot polynomial.

Recall that a polynomial P (t) is reciprocal if P (t) = t deg P P (t -1 ) equals P (t), and anti-reciprocal if P (t) equals -P (t). The polynomial P (t) itself is called the reciprocal polynomial of P (t).

The following result is very useful in order to detect Pisot polynomials.

Lemma 1 (W. Floyd, [START_REF] Floyd | Growth of planar Coxeter groups, P.V. numbers, and Salem numbers[END_REF]) Let P (t) be a monic polynomial with integer coefficients such that P (0) = 0, P (1) < 0, and P (t) is not reciprocal. Let P (t) be the reciprocal polynomial for P (t). Suppose that for every sufficiently large integer m, t m P (t)-P (t)

t-1
is a product of cyclotomic polynomials and a Salem polynomial. Then P (t) is a product of cyclotomic polynomials and a Pisot polynomial.

The convergence of Salem numbers to Pisot numbers was first discovered and analysed in [START_REF] Salem | Power series with integral coefficients[END_REF]. A geometrical relation between these algebraic integers comes into view as follows. Growth functions of planar hyperbolic Coxeter groups were calculated explicitly in [8, Section 2]. The main result of [START_REF] Floyd | Growth of planar Coxeter groups, P.V. numbers, and Salem numbers[END_REF] states that the growth rate τ of a cocompact hyperbolic Coxeter group -being a Salem number by [START_REF] Parry | Growth series of Coxeter groups and Salem numbers[END_REF] -converges from below to the growth rate of a finite covolume hyperbolic Coxeter group under a certain deformation process performed on the corresponding fundamental domains. More precisely, one deforms the given compact Coxeter polygon by decreasing one of its angles π/m. This process results in pushing one of its vertices toward the ideal boundary ∂H 2 in such a way that every polygon under this process provides a cocompact hyperbolic Coxeter group. Therefore, a sequence of Salem numbers α m given by the respective growth rates τ m arises. The limiting Coxeter polygon is of finite area having exactly one ideal vertex, and the growth rate τ ∞ of the corresponding Coxeter group equals the limit of β = lim m→∞ α m and is a Pisot number.

2.3

In this work, we study analogous phenomena in the case of spatial hyperbolic Coxeter groups. The next result will play an essential role.

Theorem 2 (W. Parry, [START_REF] Parry | Growth series of Coxeter groups and Salem numbers[END_REF]) Let P ⊂ H 3 be a compact Coxeter polyhedron. The growth function f (t) of G(P) satisfies the identity

1 f (t -1 ) = t -1 t + 1 + v∈Ω 0 (P) g v (t), (2)
where

g v (t) = t(1 -t) 2 (t m 1 -1)(t m 2 -1)(t m 3 -1) (t m 1 +1 -1)(t m 2 +1 -1)(t m 3 +1 -1) (3)
is a function associated with each vertex v ∈ Ω 0 (P); the integers m 1 , m 2 , m 3 are the Coxeter exponents * of the finite Coxeter group Stab(v) (see Table 1). Furthermore, the growth rate τ of G(P) is a Salem number.

Vertex group Stab(v)

Coxeter exponents For further references on the subject, which treat several general and useful aspects for this work, we refer to [START_REF] Chapovalov | The Poincaré series of the hyperbolic Coxeter groups with finite volume of fundamental domains[END_REF] and [START_REF] Kellerhals | On the growth of cocompact hyperbolic Coxeter groups[END_REF].

m 1 m 2 m 3 ∆ 2,2,n , n ≥ 2 1 1 n -1 ∆ 2,3,3 1 2 3 ∆ 2,3,4 1 3 5 ∆ 2,3,5 1 5 9
The following example illustrates some facts mentioned above.

Example. Let D n ⊂ H 3 , n ∈ N , be a hyperbolic dodecahedron with all but one right dihedral angles. The remaining angle along the thickened edge of D n , as shown in Fig. 1, equals π n+2 , n ≥ 0. The initial polyhedron D 0 is known as the Löbell polyhedron L(5) (see [START_REF] Yu | Volumes of hyperbolic Löbell 3-manifolds[END_REF]). As n → ∞, the sequence of polyhedra tends to a right-angled hyperbolic polyhedron D ∞ with precisely one vertex at infinity. Let us compute the growth functions and growth rates of G(D n ), n ≥ 0, and G(D ∞ ).

f n (t) = (1 + t) 3 (1 + t + • • • + t n-1 ) 1 -8t + 8t n+1 -t n+2 , (4)
and similarly

f ∞ (t) = (1 + t) 3 (1 -t)(1 -8t) . ( 5
)
Observe that the function ( 4) is anti-reciprocal, but the function (5) is not. The computation of the growth rates τ n , n ≥ 0, for G(D n ) and of the growth rate τ ∞ for G(D ∞ ) gives

τ 0 ≈ 7.87298 < τ 1 ≈ 7.98453 < • • • < τ ∞ = 8.
Thus, the Salem numbers numbers τ n , n ≥ 0, tend from below to τ ∞ , which is a Pisot number. ♦ Consider a finite-volume polytope P ⊂ H n and a compact face F ∈ Ω n-2 (P) with dihedral angle α F . We always suppose that P is not degenerated (i.e. not contained in a hyperplane). Suppose that there is a sequence of polytopes P(k) ⊂ H n having the same combinatorial type and the same dihedral angles as P = P(1) apart from α F whose counterpart α F (k) tends to 0 as k ր ∞. Suppose that the limiting polytope P ∞ exists and has the same number of facets as P. This means the facet F , which is topologically a codimension two ball, is contracted to a point, which is a vertex at infinity v ∞ ∈ ∂H n of P ∞ . We call this process contraction of the face F to an ideal vertex.

Remark. In the case n = 2, an ideal vertex of a Coxeter polygon P 0 ⊂ H 2 comes from "contraction of a compact vertex" [START_REF] Floyd | Growth of planar Coxeter groups, P.V. numbers, and Salem numbers[END_REF]. This means a vertex F ∈ Ω 0 (P) of some hyperbolic Coxeter polygon P is pulled towards a point at infinity.

In the above deformation process, the existence of the polytopes P(k) in hyperbolic space is of fundamental importance. Let us consider the threedimensional case. Since the angles of hyperbolic finite-volume Coxeter polyhedra are non-obtuse, the theorem by E.M. Andreev [22, p. 112, Theorem 2.8] is applicable in order to conclude about their existence and combinatorial structure.

In order to state Andreev's result, recall that a k-circuit, k ≥ 3, is an ordered sequence of faces F 1 , . . . , F k of a given polyhedron P such that each face is adjacent only to the previous and the following ones, while the last one is adjacent only to the first one, and no three of them share a common vertex.

Theorem 4 (Vinberg, [START_REF] Vinberg | Geometry. II: Spaces of constant curvature[END_REF]) Let P be a combinatorial polyhedron, not a simplex, such that three or four faces meet at every vertex. Enumerate all the faces of P by 1, . . . , |Ω 2 (P)|. Let F i be a face, E ij = F i ∩ F j an edge, and

V ijk = ∩ s∈{i,j,k} F s or V ijkl = ∩ s∈{i,j,k,l} F s a vertex of P. Let α ij ≥ 0 be the weight of the edge E ij .
The following conditions are necessary and sufficient for the polyhedron P to exist in H 3 having the dihedral angles α ij :

(m 0 ) 0 < α ij ≤ π 2 . (m 1 ) If V ijk is a vertex of P, then α ij + α jk + α ki ≥ π, and if V ijkl is a vertex of P, then α ij + α jk + α kl + α li = 2π. (m 2 ) If F i , F j , F k form a 3-circuit, then α ij + α jk + α ki < π. (m 3 ) If F i , F j , F k , F l form a 4-circuit, then α ij + α jk + α kl + α li < 2π.
(m 4 ) If P is a triangular prism with bases F 1 and F 2 , then α 13 + α 14 + α 15 + α 23 + α 24 + α 25 < 3π.

(m 5 ) If among the faces F i , F j , F k , the faces F i and F j , F j and F k are adjacent, F i and F k are not adjacent, but concurrent in a vertex v ∞ , and all three

F i , F j , F k do not meet at v ∞ , then α ij + α jk < π.
3 Coxeter groups acting on hyperbolic three-space

Deformation of finite volume Coxeter polyhedra

Let P ⊂ H 3 be a Coxeter polyhedron of finite volume with at least 5 faces. Suppose that k 1 , k 2 , n, l 1 , l 2 ≥ 2 are integers.

Definition. An edge e ∈ Ω 1 (P) is a ridge of type k 1 , k 2 , n, l 1 , l 2 if e is bounded and has trivalent vertices v, w such that the dihedral angles at the incident edges are arranged counter-clockwise as follows: the dihedral angles along the edges incident to v are π k 1 , π k 2 and π n , the dihedral angle along the edges incident to w are π l 1 , π l 2 and π n . In addition, the faces sharing e are at least quadrangles (see Fig. 2). Since the contraction process deforms only one edge to a point, no new 3-or 4-circuits do appear in P ∞ . Hence, for the existence of P ∞ ⊂ H 3 only condition m 5 of Andreev's theorem remains to be verified. Suppose that condition m 5 is violated and distinguish the following two cases for the polyhedron P leading to P ∞ under contraction of the edge e. 1. P is a triangular prism. There are two choices of the edge e ∈ Ω 1 (P), that undergoes contraction to v ∈ Ω ∞ (P ∞ ), as shown in Fig. 3 on the left and on the right. Since P ∞ is a Coxeter polyhedron, the violation of m 5 implies that the dihedral angles along the edges e 1 and e 2 have to equal π/2. But then, either condition m 2 or m 4 is violated, depending on the position of the edge e. 2. Otherwise, the two possible positions of the edge e in Fig. 4 and Fig. 5. The dihedral angles along the top and bottom edges are right, since m 5 is violated after contraction. 2 Consider the polyhedron P on the right in Fig. 5. As before, we may suppose that the faces I, II, III form a 3-circuit. This circuit violates condition m 2 of Andreev's theorem for P. Thus, the non-existence of P ∞ implies the non-existence of P, and one arrives at a contradiction.

Note. Proposition 1 describes the unique way of ridge contraction. Indeed, there is only one infinite family of distinct spherical Coxeter groups representing Stab(v), where v is a vertex of the ridge e, and this one is ∆ 2,2,n , n ≥ 2. One may compare the above limiting process for hyperbolic Coxeter polyhedra with the limiting process for orientable hyperbolic 3-orbifolds from [START_REF] Dunbar | Volumes of hyperbolic 3orbifolds[END_REF].

Proposition 2 Let P ⊂ H 3 be a Coxeter polyhedron of finite volume with at least one four-valent ideal vertex v ∞ . Then there exists a sequence of finite-volume Coxeter polyhedra P(n) ⊂ H 3 having the same combinatorial type and dihedral angles as P except for a ridge of type 2, 2, n, 2, 2 , with n sufficiently large, giving rise to the vertex v ∞ under contraction.

Proof. Consider the four-valent ideal vertex v ∞ of P and replace v ∞ by an edge e in one of the two ways as shown in Fig. 6 while keeping the remaining combinatorial elements of P unchanged. Let the dihedral angle along e be equal to π n , with n ∈ N sufficiently large. We denote this new polyhedron by P(n). The geometrical meaning of the "edge contraction" -"edge insertion" process is illustrated in Fig. 7. We have to verify the existence of P(n) in H 3 . Conditions m 0 and m 1 of Andreev's theorem are obviously satisfied for P(n). Condition m 5 is also satisfied since n can be taken large enough. Since there are no 4-circuits, the only condition of Andreev's theorem for P(n), which might be yet violated, is m 4 . This case is depicted in Fig. 3 on the left. A similar argument as above leads to a contradiction.

2. Otherwise, we consider the remaining unwanted cases, when either condition m 2 or condition m 3 is violated.

2.1 Case of a 3-circuit. In Fig. 8 and Fig. 9, we illustrate two possibilities to obtain a 3-circuit in P(n) for all n sufficiently large, which violates condition m 2 of Andreev's theorem. The faces of the 3-circuit are indicated by I, II and III. In Fig. 8, the edge e is "parallel" to the circuit, meaning that e belongs to precisely one of the faces I, II or III. In Fig. 9, the edge e is "transversal" to the circuit, meaning that e is the intersection of precisely two of the faces I, II or III. Contracting e back to v ∞ leads to an obstruction for the given polyhedron P to exist, as illustrated Figure 9: Forbidden 3-circuit: the second case. The forbidden circuit going through the ideal vertex is dotted. Face III is at the back of the picture in Fig. 8 and Fig. 9 on the right. The polyhedron P in Fig. 8 has two nongeometric faces, namely I and III, having in common precisely one edge and the vertex v ∞ disjoint from it. The polyhedron P in Fig. 9 violates condition m 5 of Andreev's theorem because of the triple, that consists of the faces I, II and (in Fig. 9 on the right, the face III is at the back of the picture).

2.2 Case of a 4-circuit. First, observe that the sum of dihedral angles along the edges involved in a 4-circuit transversal to the edge e does not exceed 3π 2 + π n , and therefore is less than 2π for all n > 2. This means condition m 3 of Andreev's theorem is always satisfied for n sufficiently large. Note. The statements of Proposition 1 and Proposition 2 are essentially given in [22, p. 238] without proof. In the higher-dimensional case, no codimension two face contraction is possible. Indeed, the contraction process produces a finite-volume polytope P ∞ ⊂ H n , n ≥ 4, whose volume is a limit point for the set of volumes of P(k) ⊂ H n as k → ∞. But, by the theorem of H.-C. Wang [22, Theorem 3.1], the of volumes of Coxeter polytopes in H n is discrete if n ≥ 4.

Limiting growth rates of Coxeter groups acting on H 3

The result of this section is inspired by W. Floyd's work [START_REF] Floyd | Growth of planar Coxeter groups, P.V. numbers, and Salem numbers[END_REF] on planar hyperbolic Coxeter groups. We consider a sequence of compact polyhedra P(n) ⊂ H 3 with a ridge of type 2, 2, n, 2, 2 converging, as n → ∞, to a polyhedron P ∞ with a single four-valent ideal vertex. According to [START_REF] Parry | Growth series of Coxeter groups and Salem numbers[END_REF], all the growth rates of the corresponding reflection groups G(P(n)) are Salem numbers. Our aim is to show that the limiting growth rate is a Pisot number.

The following definition will help us to make the technical proofs more transparent when studying the analytic behaviour of growth functions.

Definition. For a given Coxeter group G with generating set S and growth function

f (t) = f S (t), define F (t) = F S (t) := 1 f S (t -1 )
.

Proposition 3 Let P ∞ ⊂ H 3 be a finite-volume Coxeter polyhedron with at least one four-valent ideal vertex obtained from a sequence of finite-volume Coxeter polyhedra P(n) by contraction of a ridge of type 2, 2, n, 2, 2 as n → ∞. Denote by f n (t) and f ∞ (t) the growth functions of G(P(n)) and G(P ∞ ), respectively. Then

1 f n (t) - 1 f ∞ (t) = t n 1 -t n 1 -t 1 + t 2 .
Moreover, the growth rate τ n of G(P(n)) converges to the growth rate τ ∞ of G(P ∞ ) from below.

Proof. We calculate the difference of F n (t) and F ∞ (t) by means of equation [START_REF] Bourbaki | Lie groups and Lie algebras[END_REF]. In fact, this difference is caused only by the stabilisers of the ridge e ∈ Ω 1 (P(n)) and of its vertices

v i ∈ Ω 0 (P(n)), i = 1, 2. Let [k] := 1 + • • • + t k-1 .
Here Stab(e) ≃ D n , the dihedral group of order 2n, and Stab(v i ) ≃ ∆ 2,2,n . The corresponding growth functions are given by f e (t) = [START_REF] Cannon | The growth of the closed surface groups and compact hyperbolic groups[END_REF][n] and [START_REF] Solomon | The orders of the finite Chevalley groups[END_REF]). Thus

f v i (t) = [2] 2 [n], i = 1, 2 (see
F n (t) -F ∞ (t) = 1 f e (t) - 1 f v 1 (t) - 1 f v 2 (t) = 1 t n -1 t -1 t + 1 2 . ( 6
)
Next, perform the substitution t → t -1 on ( 6) and use the relation between F n (t), F ∞ (t) and their counterparts f n (t) and f ∞ (t) according to the definition above. As a result, we obtain the desired formula, which yields 1 fn(t) -1 f∞(t) > 0 for t ∈ (0, 1). Consider the growth rates τ n and τ ∞ of G(P(n)) and G(P ∞ ). The least positive pole of f n (t) is the least positive zero of 1 fn(t) , and f n (0) = 1. Similar statements hold for f ∞ (t). Hence, by the inequality above and by the definition of growth rate, we obtain τ -1 n > τ -1 ∞ , or τ n < τ ∞ , as claimed. Finally, the convergence τ n → τ ∞ as n → ∞ follows from the convergence 1 fn(t) -1 f∞(t) → 0 on (0, 1), due to the first part of the proof. Note. Given the assumptions of Proposition 3, the volume of P(n) is less than that of P ∞ by Schläfli's volume differential formula [START_REF] Milnor | The Schläfli differential equality[END_REF]. Thus, growth rate and volume are both increasing under contraction of a ridge.

Consider two Coxeter polyhedra P 1 and P 2 in H 3 having the same combinatorial type and dihedral angles except for the respective ridges

H 1 = k 1 , k 2 , n 1 , l 1 , l 2 and H 2 = k 1 , k 2 , n 2 , l 1 , l 2 .
Definition. We say that H 1 ≺ H 2 if and only if n 1 < n 2 .

The following proposition extends Proposition 3 to a more general context. Proposition 4 Let P 1 and P 2 be two compact hyperbolic Coxeter polyhedra having the same combinatorial type and dihedral angles except for an edge of ridge type H 1 and H 2 , respectively. If H 1 ≺ H 2 , then the growth rate of G(P 1 ) is less than the growth rate of G(P 2 ).

Proof. Denote by f 1 (t) and f 2 (t) the growth functions of G(P 1 ) and G(P 2 ), respectively. As before, we will show that 1 f 1 (t) -1 f 2 (t) ≥ 0 on (0, 1). Without loss of generality, we may suppose the ridges H i to be of type k 1 , k 2 , n i , l 1 , l 2 , i = 1, 2, up to a permutation of the sets {k 1 , k 2 }, {l 1 , l 2 } and {{k 1 , k 2 }, {l 1 , l 2 }}. By means of Table 1 showing all the finite triangle reflection groups, all admissible ridge pairs can be determined. We collected them in Tables 2-3 at the last pages of the paper. The rest of the proof, starting with the computation of 1 f 1 (t) -1 f 2 (t) in accordance with Theorem 2, equations ( 2) and ( 3), follows by analogy to Proposition 3.

From now on P(n) always denotes a sequence of compact polyhedra in H 3 having a ridge of type 2, 2, n, 2, 2 , with n sufficiently large, that converges to a polyhedron P ∞ with a single four-valent ideal vertex. The corresponding growth functions for the groups G(P n ) and G(P ∞ ) are denoted by f n (t) and f ∞ (t). As above, we will work with the functions F n (t) and F ∞ (t). By Theorem 3, both f n (t) and F n (t) are anti-reciprocal rational functions.

Consider the denominator of the right-hand side of Steinberg's formula (c.f. Theorem 1). According to [5, Section 5.2.2] and [11, Section 2.1], we introduce the following concept.

Definition. The least common multiple of the polynomials f T (t) , T ∈ F , is called the virgin form of the numerator of f S (t -1 ).

The next result describes the virgin form of the denominator of F ∞ (t).

Proposition 5 Let P ∞ ⊂ H 3 be a polyhedron of finite volume with a single four-valent ideal vertex. Then the function F ∞ (t) related to the Coxeter group G(P ∞ ) is given by

F ∞ (t) = t(t -1)P ∞ (t) Q ∞ (t) , where Q ∞ (t) is a product of cyclotomic polynomials, deg Q ∞ (t) - deg P ∞ (t) = 2
, and P ∞ (0) = 0, P ∞ (1) < 0.

Proof. The denominator of F ∞ (t) in its virgin form is a product of cyclotomic polynomials Φ k (t) with k ≥ 2. By means of the equality F ∞ (1) = χ(G(P ∞ )) = 0 (see [START_REF] Serre | Cohomologie des groupes discrets[END_REF]), the numerator of F ∞ (t) is divisible by t -1. Moreover, by [5, Corollary 5.4.5], the growth function f ∞ (t) for G(P ∞ ) has a simple pole at infinity. This means F ∞ (t) has a simple zero at t = 0, so that the numerator of F ∞ (t) has the form t(t -1)P ∞ (t), where

P ∞ (t) is a polynomial such that P ∞ (0) = 0. The desired equality deg Q ∞ (t) -deg P ∞ (t) = 2 follows from f ∞ (0) = 1.
The main part of the proof is to show that P ∞ (1) < 0. By the above, dF∞ dt (1) = P∞(1) Q∞(1) whose denominator is a product of cyclotomic polynomials Φ k (t) with k ≥ 2 evaluated at t = 1. Hence Q ∞ (1) > 0, and it suffices to prove that dF∞ dt (1) < 0.

More general Coxeter prisms arise by gluing the given ones along their orthogonal bases, if the respective planar angles coincide. Among all triangular Coxeter prisms, we depict in Fig. 14

F n (t) = (t -1)P (t) (t n -1)Q ∞ (t)
,

where Q ∞ (t) is the denominator polynomial associated with the deformed polyhedron P ∞ with a unique four-valent ideal vertex from Proposition 5, and P (t) is a product of cyclotomic polynomials and a Salem polynomial. In addition, P (1) = 0.

Proof. Denote by F in n := {f ω (t) | ω ∈ Ω * (P(n)) such that G(ω) is finite}, and by F in ∞ := {f ω (t) | ω ∈ Ω * (P ∞ ) such that G(ω) is finite} where * ∈ {0, 1, 2}. Let F n (t) = P (t) Q(t)
be given in its virgin form, that means Q(t) is the least common multiple of all polynomials in F in n . For the corresponding function F ∞ (t), Theorem 1 implies that Q ∞ (t) is the least common multiple of all polynomials in F in ∞ .

Denote by e the edge of P(n) undergoing contraction, and let v 1 , v 2 be its vertices. Then the growth function of Stab(e) ∼ = D n is f e (t) = [START_REF] Cannon | The growth of the closed surface groups and compact hyperbolic groups[END_REF][n], and the growth function of

Stab(v i ) ∼ = ∆ 2,2,n is f v i (t) = [2] 2 [n], i = 1, 2.
The sets F in n and F in ∞ differ only by the elements f e (t), f v 1 (t), f v 2 (t). Furthermore, both sets contain the polynomial [2] 2 , since the polyhedra P(n) and P ∞ have pairs of edges with right angles along them and stabilizer D 2 . The comparison of the least common multiples for polynomials in F in n and in F in ∞ shows that

Q(t) = Q ∞ (t) • [n], as claimed.
The assertion P (1) = 0 follows from the fact that F n (1) = 0 while lim t→1 t n -1 t-1 = n. Finally, the polynomial P (t) is a product of cyclotomic polynomials and a Salem polynomial by Theorem 2.

Theorem 5 Let P(n) ⊂ H 3 be a compact Coxeter polyhedron with a ridge e of type 2, 2, n, 2, 2 for sufficiently large n. Denote by P ∞ the polyhedron arising by contraction of the ridge e. Let τ n and τ ∞ be the growth rates of G(P(n)) and G(P ∞ ), respectively. Then τ n < τ ∞ for all n, and τ n → τ ∞ as n → ∞. Furthermore, τ ∞ is a Pisot number.

Proof. The first assertion follows easily from Proposition 3. We prove that τ ∞ is a Pisot number by using some number-theoretical properties of growth rates. Consider the growth functions f n (t) and f ∞ (t) of G(P(n)) and G(P ∞ ), respectively, together with associated functions F n (t) =

1 fn(t -1 )
and F ∞ (t) = 1 f∞(t -1 ) . Then the growth rates τ n and τ ∞ are the least positive zeros in the interval (1, +∞) of the functions F n (t) and F ∞ (t). By using Propositions 3, 5 and 6 in order to represent the numerator and denominator polynomials of F n (t) and F ∞ (t), one easily derives the equation

(t -1)P (t) (t n -1)Q ∞ (t) - t(t -1)P ∞ (t) Q ∞ (t) = 1 t n -1 t -1 t + 1 2 . ( 7
)
For the polynomial P (t), we prove that

P (t) = t n+1 P ∞ (t) -P ∞ (t) (8)
is a solution to [START_REF] Everitt | Right-angled Coxeter polytopes, hyperbolic 6-manifolds, and a problem of Siegel[END_REF], where P ∞ (t) denotes the reciprocal polynomial of P ∞ (t), that is,

P ∞ (t) = t deg P∞(t) P ∞ (t -1 ). Since Q ∞ (t) is a product of cyclotomic polynomials Φ k (t) with k ≥ 2, one has Q ∞ (t) = Q ∞ (t) = t deg Q∞(t) Q ∞ (t -1 ).
Now, replace P (t) in ( 7) by its expression from (8) and simplify each term. This yields

t(t -1)P ∞ (t) Q ∞ (t) - (t -1) P ∞ (t) Q ∞ (t) = t -1 t + 1 2 .
By replacing the reciprocal polynomials and by using the fact of Proposition 5, saying that deg Q ∞ (t) -deg P ∞ (t) = 2, we obtain

t(t -1)P ∞ (t) Q ∞ (t) + t -1 (t -1 -1)P ∞ (t -1 ) Q ∞ (t -1 ) = t -1 t + 1 2 . (9)
The identity for F ∞ (t) as described by Proposition 5 transforms the equa-

tion (9) into F ∞ (t) + F ∞ (t -1 ) = t-1 t+1 2
. Then Proposition 3 provides the equivalent identity F n (t) + F n (t -1 ) = 0, which is true by the anti-reciprocity of F n (t) (see Theorem 3).

As a consequence, the relation P (t) = t n+1 P ∞ (t) -P ∞ (t) holds for n large enough. Since we already know that P (t) is a product of cyclotomic polynomials and a Salem polynomial, Lemma 1 implies that P ∞ (t) is a product of cyclotomic polynomials and a Pisot polynomial. Hence, the growth rate τ ∞ is a Pisot number.

5 Some final remarks

Deforming Löbell polyhedra

The family of Löbell polyhedra L(n), n ≥ 5 is described in [START_REF] Yu | Volumes of hyperbolic Löbell 3-manifolds[END_REF]. Contracting an edge of L( 5), a combinatorial dodecahedron, one obtains the smallest 3dimensional right-angled polyhedron with a single ideal four-valent vertex. Contracting all the vertical edges of L(n) as shown in Fig. 12 one obtains an ideal right-angled polyhedron L ∞ (n), n ≥ 5.

Deforming a Lambert cube

Contracting essential edges of a Lambert cube, one obtains a right-angled polyhedron R. This polyhedron could also be obtained from the Lanner tetrahedron [START_REF] Cannon | Growth functions of surface groups[END_REF][START_REF] Charney | Reciprocity of growth functions of Coxeter groups[END_REF][START_REF] Charney | Reciprocity of growth functions of Coxeter groups[END_REF]] by means of construction described in [START_REF] Potyagailo | On right-angled reflection groups in hyperbolic spaces[END_REF]. The polyhedron R is known to have the minimal number of faces among all the right-angled three-dimensional hyperbolic polyhedra of finite volume [START_REF] Everitt | Right-angled Coxeter polytopes, hyperbolic 6-manifolds, and a problem of Siegel[END_REF].

(1-t)t 2 (1+t 2 +2t 3 -t 4 +2t 5 +t 6 +t 8 ) (1+t) 3 (1-t+t 2 )(1-t+t 2 -t 3 +t 4 )(1+t+t 2 +t 3 +t 4 )

Figure 1 :

 1 Figure 1: The dodecahedron D n ⊂ H 3 , n ≥ 0, with all but one right dihedral angles. The specified angle equals π n+2 By Theorem 2, the growth function of G(D n ), with respect to the generating set S of reflections in the faces of D n , equals

Figure 2 :

 2 Figure 2: A ridge of type k 1 , k 2 , n, l 1 , l 2Note. All the figures Fig.4-10 are drawn according to the following pattern: only significant combinatorial elements are highlighted (certain vertices, edges and faces), and the remaining ones are not specified and overall coloured grey. In each figure, the polyhedron is represented by its projection onto one of its supporting planes, and its dihedral angles of the form π/m are labelled with m.Proposition 1 Let P ⊂ H 3 be a Coxeter polyhedron of finite volume with |Ω 2 (P)| ≥ 5. If P has a ridge e ∈ Ω 1 (P) of type 2, 2, n, 2, 2 , n ≥ 2, then e can be contracted to a four-valent ideal vertex.

Figure 3 :

 3 Figure 3: Two possible positions of the contracted edge e. The forbidden 3-circuit is dotted and forbidden prism bases are encircled by dotted lines During the same deformation, the planes intersecting at e become tangent to a point v ∞ ∈ ∂H 3 at infinity. The point v ∞ is a four-valent ideal vertex with right angles along the incident edges. Denote the resulting polyhedron by P ∞ .Since the contraction process deforms only one edge to a point, no new 3-or 4-circuits do appear in P ∞ . Hence, for the existence of P ∞ ⊂ H 3 only condition m 5 of Andreev's theorem remains to be verified. Suppose that condition m 5 is violated and distinguish the following two cases for the polyhedron P leading to P ∞ under contraction of the edge e. 1. P is a triangular prism. There are two choices of the edge e ∈ Ω 1 (P), that undergoes contraction to v ∈ Ω ∞ (P ∞ ), as shown in Fig.3on the left and on the right. Since P ∞ is a Coxeter polyhedron, the violation of m 5 implies that the dihedral angles along the edges e 1 and e 2 have to equal π/2. But then, either condition m 2 or m 4 is violated, depending on the position of the edge e. 2. Otherwise, the two possible positions of the edge e in Fig.4and Fig.5. The dihedral angles along the top and bottom edges are right, since m 5 is violated after contraction.

Figure 4 :

 4 Figure 4: The first possible position of the contracted edge e. The forbidden 4-circuit is dotted. Face IV is at the back of the picture

Figure 5 :

 5 Figure 5: The second possible position of the contracted edge e. The forbidden 3-circuit is dotted. Face III is at the back of the picture 2.2 Consider the polyhedron P on the right in Fig.5. As before, we may suppose that the faces I, II, III form a 3-circuit. This circuit violates condition m 2 of Andreev's theorem for P. Thus, the non-existence of P ∞ implies the non-existence of P, and one arrives at a contradiction.

Figure 6 :Figure 7 :

 67 Figure 6: Two possible ridges resulting in a four-valent vertex under contraction Suppose that one of the remaining conditions of Andreev's theorem is violated. The inserted edge e of P(n) might appear in a new 3-or 4-circuit not present in P so that several cases are possible. 1. P(n) is a triangular prism. The polyhedron P(n) violating condition m 2 of Andreev's theorem is illustrated in Fig. 3 on the right. Since P(n) is Coxeter, the 3-circuit depicted by the dashed line comprises the three edges in the middle, with dihedral angles π n , π 2 and π 2 along them. Contracting the

Figure 8 :

 8 Figure 8: Forbidden 3-circuit: the first case

Figure 10 :

 10 Figure 10: Forbidden 4-circuit. The forbidden circuit going through the ideal vertex is dotted. Face II is at the back of the picture

Figure 12 :

 12 Figure 12: Löbell polyhedron L(n), n ≥ 5 with one of its perfect matchings marked with thickened edges. Left-and right-hand side edges are identified Note, that contracted edges form a perfect matching of L(n) considered as a three-valent graph. The analogous ideal right-angled polyhedra L ∞ (4) and L ∞ (3) also exist. Observe that L ∞ (3) is a combinatorial octahedron. The growth rate of L ∞ (n), n ≥ 3, belongs to the (2n)-th derived set of Salem numbers by Propositions 2 and 3.

5. 3

 3 Finite volume Coxeter polyhedra with an ideal threevalent vertexConsider the dodecahedron D in Fig.13. It has all but three right dihedral angles. The remaining ones, along the edges incident to a single ideal threevalent vertex, equal π 3 .

Figure 13 :

 13 Figure 13: The dodecahedron D with one ideal three-valent vertex The growth function of the corresponding Coxeter group is given byf (t) = (1 + t) 3 (1 + t + t 2 ) 9t 4 -2t 2 -8t + 1 =: Q(t) (t -1) P (t),

Figure 14 :Figure 15 :Figure 16 :

 141516 Figure 14: Prisms that admit contraction of an edge: the first picture

Table 1

 1

	: Coxeter exponents
	A rational function f (t), that is not a polynomial, is called reciprocal if
	f (t -1 ) = f (t), and anti-reciprocal if f (t -1 ) = -f (t). In the case of growth
	functions for Coxeter groups acting cocompactly on H n , the following result
	holds.
	* for the definition see, e.g. [9, Section 3.16, p. 75]

  Proposition 6 Let P(n) ⊂ H 3 be a compact Coxeter polyhedron with a ridge of type 2, 2, n, 2, 2 for n sufficiently large. Then the function F n (t) related to the group G(P(n)) is given by

	-16 at the last
	pages of the paper only ones having a ridge of type 2, 2, n, 2, 2 . A routine
	computation of their growth functions allows to conclude dFn dt (1) < 0.

  , where the polynomial P (t) has integer coefficients. Its reciprocal P (t) is the minimal polynomial of the corresponding growth rate τ . More precisely, P (t) = 9+9t+7t 2 -t 3 with roots τ ≈ 8.2269405 and ς 1 = ς 2 ≈ -0.6134703+ 0.8471252i. Since ς 1 ς 2 ≈ 1.0939668 > 1, the growth rate τ of the group G(D) is neither a Salem number, nor a Pisot number.

3

(1

+ t + t 2 ) 9t 4 -2t 2 -8t + 1 =: Q(t) (t -1) P (t)

Table 2 :

 2 4 (1-t)(1-t+t 2 )(1+t+t 2 ) (1+t)3 (1+t 2 )(1-t+t 2 -t 3 +t 4 )(1+t+t 2 +t 3 +t 4 ) 2 (1-t)(1+2t 2 +t 3 +2t 4 +t 5 +2t 6 +t 7 +2t 8 +t 10 ) (1+t) 3 (1+2t 2 +3t 4 +3t 6 +3t 8 +2t 10 +t 12 ) (1+t 2 )(1-t+t 2 -t 3 +t 4 ) 2 (1-t)(1+t+t 2 +t 3 +t 4 ) (1+t) 3 (1+t 2 )(1-t+t 2 )(1+t+t 2 ) Table for Proposition 4 Type of H 1 Type of H 2 2 (1-t)(1+t 2 )(1+t 3 +t 6 ) (1+t) 3 (1+3t 2 +5t 4 +6t 6 +6t 8 +5t 10 +3t 12 +t 14 ) 2 (1-t)(1+t 2 )(1+t 3 +t 6 ) (1+t) 3 (1-t+t 2 )(1-t+t 2 -t 3 +t 4 )(1+t+t 2 +t 3 +t 4 )2, 5, 2, 2, 5

	Type of H 1	Type of H 2		1 f 1 (t) -1 f 2 (t) =
	2, 2, n, 2, 2 ,	2, 2, n + 1, 2, 2 ,	t n (1-t) 3 (1-t n )(1-t n+1 )(1+t) 2 ,
	n ≥ 2	n ≥ 2		n ≥ 2
	2, 2, 2, 2, 3	2, 2, 3, 2, 3		t 2 (1-t) (1+t) 3 (1+t 2 )
	2, 2, 3, 2, 3	2, 2, 4, 2, 3	t 3 (1-t) (1+t) 3 (1-t+t 2 )(1+t+t 2 )
	2, 2, 4, 2, 3	2, 2, 5, 2, 3
	2, 2, 2, 2, 4	2, 2, 3, 2, 4	t 2 (1-t)(1+t 2 ) (1+t) 3 (1-t+t 2 )(1+t+t 2 )
	2, 2, 2, 2, 5	2, 2, 3, 2, 5
	2, 3, 2, 2, 3	2, 3, 3, 2, 3	t 2 (1-t) (1+t)(1+t 2 )(1+t+t 2 )
	2, 3, 3, 2, 3	2, 3, 4, 2, 3	t 3 (1-t) (1+t) 3 (1+t 2 )(1-t+t 2 )
	2, 3, 4, 2, 3 (1+t) 3 2, 3, 2, 2, 4 2, 3, 5, 2, 3 2, 3, 3, 2, 4	t 4 (1-t)

t t t t t

Table 3 :

 3 Table for Proposition 4 (continuation)

	Vertex group Stab(v) ∆ 2,2,n , n ≥ 2 ∆ 2,3,3 ∆ 2,3,4 ∆ 2,3,5	Its Coxeter exponents Quantity dgv dt (1) m 1 m 2 m 3 1 1 n -1 -1 8 1 -1 n 1 2 3 -1 8 1 3 5 -5 32 1 5 9 -3 16

Table 4 :

 4 Table for Proposition 5. The column on the right follows from Theorem 2, formula (3)

* for how to read hyperbolic Coxeter diagrams, we refer to[START_REF] Vinberg | Geometry. II: Spaces of constant curvature[END_REF] Ch. 5, §1.3]

* supported by the Schweizerischer Nationalfonds SNF no. 200020-121506/1 and no. 200021-131967/1 1 Acknowledgement. This work is a part of the author's PhD thesis project supervised by Prof. Ruth Kellerhals. The author is grateful to the Fields Institute for their hospitality and support during the fall 2011

Consider a sequence of combinatorially isomorphic compact polyhedra P(n) in H 3 having a ridge of type 2, 2, n, 2, 2 and converging to P ∞ . By Proposition 3,

In order to show dF∞ dt (1) < 0, it is enough to prove that dFn dt (1) < 0 for n large enough. To this end, we consider the following identity which is a consequence of Theorem 2, equations ( 2)-(3):

.

In Table 4 at the last pages, we list all possible values dgv dt (1) depending on the subgroup Stab(v) of G(P(n)). It follows that dgv dt (1) ≤ - 1 16 for every v ∈ Ω 0 (P(n)). Provided |Ω 0 (P(n))| ≥ 10, we obtain the estimate dFn dt (1) ≤ - 1 8 . Consider the remaining cases 5 ≤ |Ω 0 (P(n))| < 10. By the simplicity of the polyhedron P(n), we have that 2|Ω 1 (P(n))| = 3|Ω 0 (P(n))|. Therefore |Ω 0 (P(n))| is an even number. Hence, the only cases consist of |Ω 0 (P(n))| = 8, meaning that P(n) is either a combinatorial cube or a doubly truncated tetrahedron (see Fig. 11), and |Ω 0 (P(n))| = 6, meaning that P(n) is a combinatorial triangular prism. In the former case, not all the vertices of P(n) have their stabilizers isomorphic to ∆ 2,2,2 , since P(n) is a non-Euclidean cube or a non-Euclidean tetrahedron with two ultra-ideal vertices. Then Table 4 provides the desired inequality dFn dt (1) < 0. The latter case requires a more detailed consideration. We use the list of hyperbolic Coxeter triangular prisms given by [10, 21] * . These prisms have one base orthogonal to all adjacent faces.


Javier ; Andres

Luis Gracia
email: luigraca@isa.upv.es

Josep Tornero
email: jtornero@isa.upv.es

Calibration and control of a redundant robotic workcell for milling tasks

Keywords: REDUNDANT WORKCELL, POSTPROCESSING redundant workcell, robot calibration, postprocessing, CNC machining, CAD/CAM

published or not. The documents may come

Introduction

Robotic arms are crucial in many manufacturing processes involving large volumes because of their high flexibility and large working areas [START_REF] Patrick | Shop-floor productivity[END_REF]. These properties are usually enhanced with the use of additional joints carrying the arm or the workpiece and making up what is known as an industrial workcell.

At the Design and Manufacturing Institute of the Universidad Politécnica de Valencia (IDF-UPV), a sculpturing robotic system has been tuned to test milling methods for rapid prototyping on soft materials such as expanded polystyrene (EPS). As shown in Figure 1, an industrial KUKA TM KR15/2 arm with six revolute (6R) joints is mounted on a linear track, and works over a synchronized rotary table platform on which the initial blank of material is set. This provides a wide effective workspace for handling large objects with complex shapes. Because the revolute joints and the linear track joints only allow one degree of freedom (DOF) each, the dimension of the joint space ( ℑ ) is n=8 for this workcell. Other examples of robotic systems for similar applications (such as polishing, arc-welding, spray-glazing, etc.) can be found in [START_REF] Feng-Yun | Development of a robot system for complex surfaces polishing based on CL data[END_REF], [START_REF] Huang | Rapid and flexible prototyping through a dual-robot workcell[END_REF], [START_REF] Bidandaa | Computer-aided-design-based interactive off-line programming of spray-glazing robots[END_REF], and [START_REF] Tsai | Mathematical model for robotic arcwelding off-line programming system[END_REF].

Conventional CNC machining techniques can be adapted from high precision metal cutting to fast milling in EPS with robots. Sophisticated CAD/CAM/ROB integrated manufacturing systems mean that during the machining process less time is invested in successive verifications, adjustments, and data translation.

Leading commercial CAM (computer aided manufacturing) software is prepared for the off-line planning of 5-axis CNC operations [START_REF] De Lacalle | The CAM as the centre of gravity of the five-axis high speed milling of complex parts[END_REF]. For precision and universality, the five parameters captured in a cutting toolpath are the three pose coordinates of the tool centre point (TCP) and the two orientation coordinates of the milling tool (considering the tool symmetrical along its axis of revolution, see Figure 1). Accordingly, at milling works the dimension of the task space ( ) Τ is t=5. This assumes no-uncertainty in tool orientation and positioning for a conventional CNC machine but, in every case, the toolpath must be adapted (postprocessed) to the milling system [START_REF] Lee | Developing a postprocessor for three types of five-axis machine tools[END_REF]She 1997, Nemec and[START_REF] Nemec | Robotic cell for custom finishing operations[END_REF].

Accuracy is crucial in a robot program generated by a CAM system, but accuracy is lessened by a poor adjustment of the workcell, particularly in the kinematic factors related to the additional joints. Offsets and deviations in the assembly of the additional external joints of the workcell reduce accuracy [START_REF] Khalil | Modeling identification and control of robots[END_REF].

This paper exposes the fine-tuning of the redundant workcell shown in Figure 1 for milling tasks. After describing the kinematics of the workcell in Section 2, the calibration of the external joints is tackled in Section 3. Section 4 explains the redundancy resolution scheme (RRS) used to implement the algorithm for continuous path tracking in order to integrate a CAM-robotics postprocessor (Section 5). This postprocessor generates the robot instructions off-line for milling tasks with the correct use of the redundancies. The designed postprocessor is tested in Section 6 with a practical application, namely, the prototyping of an orographic model. Finally, the conclusions to this work are discussed in Section 7.

Kinematic modelling of the redundant workcell

A kinematic model is the mathematical description required to control the posture of the robot chain and the associated pose of the milling tool. When performing a task on the workcell, the table can be regarded as fixed while the other movable end-effector (EE) holds the cutter tool in the Cartesian operational workspace ( Ω ) whose base frame is {B}, see Figure 1. Note that the pose of a rigid body in Ω is defined by six coordinates (three locations and three orientation values) and so dim( Ω )=m=6.

The direct kinematic problem (DKP) at the displacement level is straightforward, mapping from ℑ to Ω . It consists of determining the pose of the EE for a given manipulator posture. The standard Denavit-Hartenberg (DH) model is widely utilized in this context due to its simplicity. It represents the pose of the EE as a 4×4 homogeneous transformation matrix T deduced from four parameters (α i , a i , θ i , d i ) describing the relative position between consecutive links [START_REF] Hartenberg | A kinematic notation for lower pair mechanisms based on matrices[END_REF].

Moreover, the robotic workcell described in Section 1 is redundant as ( ) n t with > Τ ⊆ Ω [START_REF] Patel | Control of redundant robot manipulators: theory and experiments[END_REF], with a degree of kinematic redundancy (r K ) of 3 K r n t = -= . This redundancy appears because of the additional linear track ( L d ) and rotary table ( M θ ), as well as the cutter tool symmetry while spinning along its revolution axis, see Figure 1. In practical use, the redundancy along the milling tool axis means that an additional virtual joint can be considered for the kinematic model, increasing the dimension of ℑ (n=9). With these premises, the full DH model is summarised in Figure 2 and Table 1.

External joint calibration

Robot kinematic calibration consists in identifying the differences between the default geometrical parameters given by the manufacturer and those of the real workcell to achieve the required accuracy see ISO 9283:1998. It is notable that the off-line generation of programs for robotic workcells, as opposed to the traditional on-line teaching methods based on repeatability, has resulted in the emergence of different calibration techniques.

Existing calibration techniques can be broadly classified into closed-loop (or pose-matching) and open-loop (or pose-measuring) approaches [START_REF] Fassi | Calibration of Serial Manipulators: Theory and Applications[END_REF]. The closed-loop methods impose some constraints on the EE and only use the joint position measurements to calibrate the robot. However, it is difficult to move a physically closed kinematic chain from one position to another while maintaining the physical constraints, such as touching a point or a plane with a probe. Hence, it is difficult to gather accurate joint readings [START_REF] Fassi | Calibration of Serial Manipulators: Theory and Applications[END_REF][START_REF] Khalil | Calibration of the geometric parameters of robots without external sensors[END_REF]. The open-loop methods traditionally require expensive and demanding devices to measure the EE pose, such as theodolites [START_REF] Whitney | Industrial robot forward calibration method and results[END_REF], inclinometers, coordinate measuring machines [START_REF] Driels | Full-pose calibration of a robot manipulator using a coordinate measuring machine[END_REF][START_REF] Zhong | Neuroaccuracy compensator for industrial robots[END_REF], sonic and visual sensors (Stone et al. 1986, Driels and[START_REF] Driels | Automated partial pose measurement system for manipulator calibration experiments[END_REF], and laser tracking systems [START_REF] Prenninger | Contactless position and orientation measurement of robot end-effector[END_REF][START_REF] Vincze | A laser tracking system to measure position and orientation of robot end effectors under motion[END_REF]. An alternative open-loop method was developed by [START_REF] Sultan | A technique for the independent-axis calibration of robot manipulators with experimental verification[END_REF] on the basis of independent-axis calibration and using two theodolites as data-acquisition media. However, the closed-architecture control system of commercial KR15/2 robots has encouraged the authors to develop a different procedure.

The KR15/2 manipulator has proven to be accurate, but the workcell assembly made in situ left some misalignments in the additional joints, namely the linear track and the rotary table. Consequently, a simple, fast, and accurate calibration is needed to update the robot controller with the correct robot-specific DH parameter values instead of the default values.

The proposed calibration method combines pose-matching and pose-measuring methods using a set of positions of the terminal point of the robot but avoiding the inconveniences of physical contact with the EE. These points are assumed to be on the same plane. A non-linear least squares (NLSQ) identification model has been derived from the consistency conditions of the planes and is detailed below. The DH parameters associated with the additional external joints will be held in vector β , i.e.

1 1 1 2 [ ] T M L a d d β α θ θ =
, in order to be accurately estimated using the calibration procedure. These parameters relate the base frame {B} with the additional frames linked to the additional external joints P{d L } and R{θ M }, see Figure 2. Nevertheless, the calibration method proposed below can be applied to the complete chain by magnifying the observed parameters. This method is suitable for in-situ calibration in an industrial environment and can be run autonomously.

Sensor used in the calibration

A laser displacement sensor (SICK TM OD100-35P840) is rigidly attached to the robot flange. Due to its reduced size, the laser can be integrated within the same milling-tool holder and, thus, the calibration can be performed for the nominal operating conditions of the robot. The laser has a measuring range of 100 mm with 35 µm in resolution and is assumed to be aligned with the Z-axis of the EE. A coordinate system {LR} is chosen with the origin (TCP) in the laser line and with the X,Y-axis set at a convenient orientation, see Figure 3.

It is cumbersome to use planar methods if the calibration process includes the calibration of the laser itself, since the observability of certain parameters is not possible if the EE is moved in parallel over a plane. Thus, the availability of a fully calibrated laser sensor is assumed prior to the assembly of the new additional joints, i.e. 8

LR

T is assumed to be known. For example, 8 LR T can be computed with the approach proposed by [START_REF] Zhu | Calibration of laser displacement sensor used by industrial robots[END_REF].

In practical terms of industrial calibration, the workspace base frame {B} is set at the centre of the rotary table using a squared pattern and several external measurements made in situ (theoretically, only three points per plane are required), see Figure 4.

Non-contact planar constraint calibration procedure

It has been reported that partial EE pose information is sufficient for complete parameter identification [START_REF] Zhong | A new method for autonomous robot calibration[END_REF]. However, [START_REF] Zhuang | Robot calibration with planar constraints[END_REF] showed that a single-plane constraint does not necessarily guarantee the observability of the unknown kinematic parameters of the robot, as the measurement data is biased towards a particular direction. These authors demonstrated that no less than three planes placed at a number of different orientations could replace a 3D-position measurement system.

We use the laser distance sensor to sweep the three constraint planes ( X Π , Y Π and Z Π ) at an intended constant distance d, see Figure 5. To achieve this, a set of points

( 1,..., ) i M p i np =
is commanded to the controller forming three orthogonal meshes in their respective orthogonal planes. This is performed by setting the required position and orientation of the laser displacement sensor at {B} for each point, with the pattern specified by the robot manufacturer [START_REF] Kuka Corp | KUKA System software (KSS): expert programming (KRC2 / KRC3)[END_REF]:

( , , , , , )
i i i i i i i M M x M y M z M A M B M C p p p p p p p = (1)
where the three first values represent the position, and the three last values represent the roll-pitch-yaw orientation coordinates, respectively.

The calibration procedure capitalises on the restriction imposed by the laser line, being almost perpendicular to each plane, and which is intended to be at the same distance d for all the M p points commanded to the controller. Moreover, we can consider the laser TCP at a distance d from the laser sensor so that each commanded point M p lies on its associated plane. The general equation of a plane Π containing the origin of {B} is 0 ax by cz + + = , where a, b, c correspond to the plane coefficients.

Since the TCP is lying in its corresponding plane, each commanded point

i M p should accomplish that + =0 i i i M x M y M z ap bp cp +
. Moreover, the equations observed for the three pattern planes are, respectively,

0 i M x p = , 0 i M y p =
and 0 i M z p = . Therefore, the commanded points M p have the form:

(0, , , 0, / 2, 0)

X i i i M M y M z p p p π Π = - (2)
( , 0, , 0, 0, / 2)

Y i i i M M x M z p p p π Π = - (3)
( , , 0, 0, 0, 0)

Z i i i M M x M y p p p Π = (4)
A non-linear least squares (NLSQ) identification model has been derived from just the laser readings, without additional external measurements or joint recordings. The objective is to adjust the parameters of a kinematic model function that best fits all the np commanded points, see Figure 6. For each point, this model function has the form:

( , ); 1,..., i i M p f q i np β = = (5)
The mp adjustable model parameters are held in the vector β . In the case studied, The fact that each set is constrained to lie on its corresponding plane leads to the construction of the identification model. Let i S p represent the actual coordinates of the laser TCP in {B} that correspond to the configuration q i acquired for the commanded point ( 1) ( ) ( )

1 1 1 2 [ ] T M L a d d β α θ θ = (mp=6).
β β β + = + ∆ s s s (7)
where s is the iteration number. As Equation ( 6) is applied for a sufficient number np>>mp of commanded points arranged on the three orthogonal planes, the resulting system to identify ( )

β ∆ s is: ( ) ( ) ( ) ( ) β β ∆ = ∆ s s s p W ( 8
)
where W is the observation matrix [START_REF] Khalil | Calibration of the geometric parameters of robots without external sensors[END_REF] of dimension np×mp. The observation matrix is an ordered composition of the Jacobians associated with the corresponding observation at each plane,

( ) ( ) ( ) [ ( ) ( ) ( )] X Y Z s s s T f f f W J J J β β β Π Π Π = .
Consequently, care must be taken in the configuration of p ∆ due to the fact that the measurements taken in each plane must correspond with the significance of each row of W . The npx1 vector of the observed residuals in the three planes is

F o r P e e r R e v i e w O n l y ( ) ( ) ( ) ( ) [ ] X Y Z s s s s T p D D D Π Π Π ∆ = .
The increment β ∆ can then be solved to obtain the least squares error solution:

( ) † ( ) β ∆ = ∆ s s W p (9)
where † W is the left pseudo-inverse of W , namely † 1 ( )

T T W W W W - ≡ .
The geometric parameters β are iteratively updated from the current pose error ( ) ∆ s p using Equations ( 9) and ( 7) until the elements of ( ) β ∆ s become smaller than a prescribed limit. This best-fit solution is saved in the controller. The common sense criterion for convergence is somewhat arbitrary, as for example ( )

( ) (0) 0.001 1,..., β β β ∆ < ∀ = - s j s j j j mp (10)
which is equivalent to specifying that each parameter should be refined to 0.1% precision, i.e. ( )

( ) ( ) (0) ( ) (0)
0.001 0.001

β β β β β β ∞ ∞ - < ⋅ - ≈ ⋅ - s s j j j j j j
, where ( )

β ∞ j
is the asymptotic value of the parameter.

Calibration results

The calibration procedure described in this work has been run on an Intel ® Core Duo PC with Matlab ® 2007c. A total of 108 points have been measured, i.e., a regular mesh of 36 grid points (6x6) was commanded for each plane in Figure 7. Figure 8 shows the behaviour of the proposed calibration algorithm for the studied workcell. The calibration process shows a good convergence. The stop criterion given by Equation ( 10) is met at the 18th iteration and the value achieved for the parameters is To validate the improvement obtained with the calibration procedure, two comparisons are considered. For the first, a total of nv=96 points on the table plane were measured using the laser sensor and varying external joints randomly from 0 to 1000 mm for L d and from 0 to π rad for M θ . Figure 9 shows the performance for this test with and without calibration. After calibration the accuracy of the data clearly iºmproves: the average value is reduced from -3.342 to -0.600 mm; the root mean square (RMS) error is reduced from 5.429 mm to 0.998 mm; and the standard error deviation is reduced from 4.279 to 0.797 mm.

The second comparison consists of the milling of a small workpiece, see Figure 10. Although the motion of the additional joints is not required for this milling task, the operator manually displaces (by means of the control panel of the robot) the linear track 500 mm and rotates the table / 4 π rad at a certain time while the lateral walls of the workpiece are being milled. Note that, after calibration (Figure 10, bottom right) the workpiece is better finished.

Inverse kinematic control of the redundant workcell

The inverse kinematic problem (IKP) is relevant because CAM systems specify the toolpath at the Cartesian workspace Ω , whereas the robot controller works in the joint space ℑ . The IKP can be solved for each pose of the path, although at the displacement level the IKP is cumbersome because an infinite number of solutions exist for redundant manipulators. Instead, an iterative approach at the joint rate level is usually used [START_REF] Whitney | Resolved motion rate control of manipulators and human prostheses[END_REF].

The forward kinematics between the EE velocity t and the joint velocity q & is represented by the linear equation • t J q = & , where J is the mxn Jacobian matrix, which is a non-linear function of the joint angles that can be computed with the geometric procedure outlined by [START_REF] Angeles | Fundamentals of robotic mechanical systems: theory, methods and algorithms[END_REF], among others. For the redundant workcell considered in this work, the Jacobian matrix maps the 9-dimensional vector

] ω = T t v , with T x y z ω ω ω ω   =   and T x y z v v v v   = 
 denoting the linear and angular velocities of the EE reference frame relative to the base frame {B}, respectively. The objective of the IKP at the joint rate level is to obtain the required joint velocities & q to achieve the desired EE velocity t for a given Jacobian matrix J. In the case of redundant robots, for which the Jacobian matrix J is non-square (n>m), the right pseudo-inverse ( )

1 † T T J J JJ - ≡
gives the minimum least-squares solution q & that fulfils the desired EE

velocity t, namely † • q J t = &
. Moreover, an arbitrary vector from the Null Space of J , namely ( ) J ℵ , can be added to achieve a secondary goal: † †

• ( ) = + - & q J t I J J h (11)
where I is the identity matrix of dimension n, † ( ) -I J J is the projection operator on ( ) J ℵ , and h is the performance vector for the secondary task. At this point it is worth mentioning that, as the Jacobian matrix depends on the DH parameters, the workcell calibration is crucial for a proper robot control.

In the redundancy resolution scheme (RRS) given by Equation ( 11), the performance vector h can be considered as a virtual force that attempts to push the configuration of the manipulator away from a critical area in ℑ [START_REF] Nemec | Robotic cell for custom finishing operations[END_REF] as a secondary task. The most widespread method used to select h is the gradient projection method (GPM) [START_REF] Liégeois | Automatic supervisory control of the configuration and behavior of multibody mechanisms[END_REF], which minimises a position-dependent scalar, the performance index p, by means of its gradient vector:

• h k p = -∇ ; with 1 2 ( ) ( ) ( ) , ,..., T n p q p q p q p q q q   ∂ ∂ ∂ ∇ =   ∂ ∂ ∂   (12)
In this work, two performance criteria are combined into vector h:

( ) ( ) ( ) ( ) ref = + = -∇ + = - - + - jnt cond jnt cond jnt cond Ts h h h p p H q q H k q q (13)
where H is the weighting matrix for each criterion, e.g. constant diagonal matrices are considered in this work (0.01) = ≡

jnt cond H H diag . Note that the performance vector jnt h given by performance index jnt p tends to maintain the workcell as close as possible to a reference posture q ref (e.g. the HOME posture 0 q shown in Figure 2) to avoid joint limits [START_REF] Huo | The joint-limits and singularity avoidance in robotic welding[END_REF]. The performance vector cond h given by performance index cond p tends to maintain the workcell as far as possible from ill-conditioned postures [START_REF] López-Cajún | Kinematic Isotropy and the Conditioning Index of Serial Robotic Manipulators[END_REF], i.e. postures with poor kinematic performances. The second performance vector cond h is activated when the value of the condition number k of the Jacobian matrix (e.g. obtained using the Euclidean norm) passes over a preset threshold value, e.g. 0.5. At that instant, the corresponding configuration Ts q is recorded to evaluate at ℑ the distance to the actual posture.

5.

Postprocessor implementation for a redundant workcell

CAM system for toolpath generation

The software NX ® is a digital development system from Siemens TM that integrates the tasks of design (CAD), simulation (CAE), and planning of milling tasks (CAM). NX interacts with the program codes in TCL and C++ that manipulate the path data (event handler) and gives a convenient format to the generated output (definition file), see Siemens Corp. ( 2009) and Figure 11. The treatment of the data has been programmed in Matlab ® code with the aid of the Hemero toolbox [START_REF] Maza | Herramienta MATLAB-Simulink para la simulación y el control de robots manipuladores y móviles[END_REF], whereas the Robomove ® software [START_REF] Qdesign | CAD-CAM off line programming for industrial robots[END_REF]) has been used to visualise the robot postures resulting from the implemented RSS.

Continuous path tracking

Once the CAM system has generated the toolpath as a discrete set of close-enough poses at Ω , the EE of the robot must track this path. A tangent, normal, and binormal unit Frenet-Serret vectors, i.e. {t, n, b}, is associated with every sample point of the trajectory and this indicates the required pose, see Figure 12. This trajectory data is stored as T CAM .

The joint angles of the robot have to be computed along this continuous set of poses of the EE. The IKP can be solved at each sampled pose, although the resolution is cumbersome because an infinite number of solutions exist for redundant manipulators. Instead, an iterative approach can be applied by using J (Angeles 2003):

( ) i i i J q q t ∆ = ∆ , with ( )   ∆ ≡   ∆   T i k k d Q vect Q Q t p (14)
where Q k (i.e., the first three rows and columns of the matrix T introduced in Section 2) is the current rotation matrix from {B} to {EE} (see Figure 1), and Q d is the desired rotation matrix. Both matrices are related by:

• • T d k k d Q Q Q Q Q Q = ∆ → ∆ = (15)
Function ( ) vect Q ∆ represents the axial vector of the 3x3 rotation matrix Q ∆ and is computed as:

32 23 13 31 21 12 1 ( ) 2 Q Q vect Q Q Q Q Q ∆ -∆     ∆ ≡ ∆ -∆     ∆ -∆   (16)
Vector p ∆ is defined as the difference between the prescribed value p d of the Algorithm 1 below is programmed with these premises. It starts from the HOME posture (q 0 , Figure 12) and iteratively uses the kinematic models of the single KR15/2 manipulator (sub-index 6R) and the complete workcell (sub-index Workcell) to evaluate the condition number k and manage the motion of all the joints. Algorithm 1

{ } { } 0 CAM CAM Workcell 1)
(each -point of the trajectory, T ( ))

2) , T

3) , DK( , DH-Workcell)

4) • 5) • ( ) 6) 7) DK( , DH-Workcell) 8) d d T d d q q for i i p Q while q p Q q Q Q Q p p p Q vect Q t p J q ε ← ← ∆ > ⇐ ∆ ⇐ ∆ ⇐ - ∆   ∆ ←   ∆   ⇐ { }
+ F R R R R g R L F R k q q q J q q H J k H q q q q endwhile endfor ← ⇐ ← ← ∆ ⇐ ⇐ ∆
The RRS in the 9 th step of Algorithm 1 is programmed using the Householder reflections. Direct calculation of the pseudo-inverse of the Jacobian † J is avoided to keep the round-off errors as low as possible [START_REF] Arenson | Real-time redundancy-resolution schemes for robotic manipulators[END_REF]. Algorithm 2 below summarises this calculation using Matlab ® code.

Application

The production system described above was implemented to mill an 8x13 meter orographic model of the tail end of a reservoir on the river Mijares (Spain). The design is imported from AUTOCAD ® (widely used in topography) to the NX ® -CAD module to restore the contour lines and interpolate a surface mesh. The quality of the resulting CAD file determines the efficiency of the results obtained in the subsequent steps of the milling process. As shown in Figure 13, the model is made by assembling 120 blocks of 1x1x0.5 meters of expanded polystyrene (EPS). The toolpath generated in NX ® has been simulated with and without the implemented postprocessor in the graphical Robomove ® simulator and starting from the same HOME posture. In Figure 14 it can be seen that the end of the workpiece (red part) cannot be reached without moving the additional joints, i.e. L d and M θ . A better performance is achieved when the toolpath is postprocessed with the proposed RRS, which moves the additional joints to maintain a well-conditioned posture during the machining process.

Conclusions

After introducing the capabilities of an industrial robotic workcell, two necessary requirements for setting up the workcell have been discussed in this paper: the in situ calibration of the robot's external joints; and the management of the redundancies (caused by the additional joints and the symmetry of the cutter tool).

For the calibration task, a novel non-contact planar constraint procedure has been developed on the basis of a planar pattern and a laser displacement sensor and has been successfully validated with two illustrative examples. The proposed calibration method is relatively cheap, can be implemented autonomously in most industrial robots, and is fast enough to be used in situ at regular intervals. Further work must be done to integrate the laser measuring device within the tool holder, in order to bridge the gap between the theoretical and practical applications on the shop-floor.

Moreover, a functional postprocessor has been programmed inside the CAM system for the control of redundancies during milling tasks. A real case-study has been considered to validate the effectiveness of these production systems for the milling of large prototypes using soft materials. The proposed postprocessor is expected to be easily applicable on any industrial robot, and useable for different applications such as welding or painting. The implementation details to adapt CAM modules from machining tasks to welding and painting tasks is a field for further research.

  Figure5. Due to the perpendicular orientation commanded, the distance i D Π measured by the laser device approximates to the respective actual coordinate i at {B} (Figure5). For each plane, the other five coordinates of the reached point i S p are neither known nor approximated by any external measurement. Nevertheless, the error committed in all coordinates is reduced as the mp model parameters are tuned.A residual, i r , can be defined as the difference between the actual observed values i S p and the model predicted values, namely ( approximate each residual to be minimised with the reading , i.e. i i r D Π ≈ . Thus, the identification model relating the deviation of the EE location from the plane Π with the differential error in the geometric parameters ( being the Jacobian matrix of the residual regarding the identifiable parameters. Only the expression corresponding to the residual error r Π in the perpendicular direction of each plane Π is taken into account.In this non-linear system, the derivatives r β Π ∂ ∂ are functions of both the commanded postures and the identifiable parameters, so these gradient equations do not have a closed solution. Instead, the default assembly values are chosen as initial guesses for the mp parameters,(0) [ 2, 803, , 305, 0, ] 7. Thus, while minimising the residuals, the final value of β is refined iteratively by consecutive approximations:

  rates into the EE velocity vector

[

  Figure 15 (right) shows the final orographic model at the Hydraulic Engineering Department (DIHMA) of the Universidad Politécnica de Valencia, and which is used for simulating water courses under various climatic conditions.

Figure 1 .

 1 Figure 1. View of the KUKA TM workcell at the IDF-UPV supplied with two additional joints. The insets show the irrelevant axis of symmetry of the milling tool.

Figure 2 .

 2 Figure 2. Frame assignment for the DH representation of the RP-6R workcell.

Figure 3 .

 3 Figure 3. Laser displacement sensor attached to the robot flange.

Figure 4 .

 4 Figure 4. Squared pattern on the workspace base frame {B}.

Figure 5 .

 5 Figure 5. Three commanded meshes on the three respective planes are shown at the top; the coordinate i S y p approximated by the distance

Figure 6 .

 6 Figure 6. Open-loop procedure proposed for the workcell calibration.

Figure 7 .

 7 Figure 7. Sweeping the reference planes with two configurations of L d and M θ .

Figure 9 .

 9 Figure 9. Validation of the calibration: scattergraph and histogram of the distance measurements D Π to the table surface.

Figure 10 .

 10 Figure 10. Milling of a small workpiece: bottom left, result without calibration; bottom right, result with calibration.

Figure 11 .

 11 Figure 11. Integrated postprocessing in NX ® : the 'definition file' and the 'event handler' adapt the toolpath to the controller's Kuka Robot Language (KRL).

  Figure 12. Highlight of the loop leading from an initial current pose (k) to a desired final pose (k+1), both specified by the Frenet-Serret vectors {t, n, b}.

  Figure 13. The orographic model is produced by assembling 120 blocks of 1x1x0.5 meters of EPS.

Figure 14 .

 14 Figure 14. Toolpath postprocessed without (left) and with (right) the proposed RRS.

  Figure 15. Left, milling process of an EPS block; right, final 1:75 model used for flowing simulation (real dimensions of 8x13 m).

  TCP position vector and its current value p k . The relations amongstQ d , p d , Q k , p k , Q ∆

	and p ∆ are shown in Figure 12.

Table 1 .

 1 Workcell parameters for the standard DH-model.

	Link α i (rad) a i (mm) θ i (rad)	d i (mm)
	1	π/2	803	θ M	-305
	2	π/2	0	0	d L
	3	π/2	300	θ 1	-675
	4	0	650	θ 2	0
	5	π/2	155	θ 3	0
	6	π/2	0	θ 4	-600
	7	π/2	0	θ 5	0
	8	0.3564	0	θ 6	-443.4
	TCP	0	0	θ 7(VJM)	-119.7

& & & & &

URL: http://mc.manuscriptcentral.com/tandf/tcim Email:ijcim@bath.ac.ukInternational Journal of Computer Integrated Manufacturing