Member, IEEE Marc Gouttefarde
email: marc.gouttefarde@lirmm.fr

Member, IEEE David Daney
email: david.daney@sophia.inria.fr

Member, IEEE Jean-Pierre Merlet

Interval-Analysis-Based Determination of the Wrench-Feasible Workspace of Parallel

Keywords: Cable-driven robots, workspace determination, wrench-feasibility, interval analysis

published or not. The documents may come

I. INTRODUCTION

P ARALLEL cable-driven robots consist essentially of a mobile platform connected in parallel to actuated reels by cables as illustrated in Fig. 1. The actuation of each cable allows the control of the platform motion and/or wrenches. These parallel robots have several interesting properties such as a potentially very large reachable workspace since large lengths of cables can be used, low mass of the mobile parts of the robot and low visual intrusion. Therefore, they are good candidates for many applications, a few examples of which are B Cable Fig. 1. A parallel cable-driven robot.

high-speed manipulation [START_REF] Kawamura | High-speed manipulation by using parallel wire-driven robots[END_REF], [START_REF] Dekker | Design and testing of an ultra-high-speed cable robot[END_REF], haptic interfaces [START_REF] Ishii | A 3D spatial interface device using tensed strings[END_REF], automated construction systems [START_REF] Williams | Contour-crafting-cartesiancable robot system concepts: Workspace and stiffness comparisons[END_REF] and locomotion interfaces [START_REF] Perreault | Cable-driven parallel mechanisms: Application to a locomotion interface[END_REF]. However, various factors may limit the workspace of parallel cable-driven robots among which the inability of the cables to push on the mobile platform is an important and challenging one. This fundamental issue has been the subject of several studies especially in recent years. The works presented in [START_REF] Kurtz | Dexterity measure for tendon actuated parallel mechanisms[END_REF]- [START_REF] Williams Ii | Planar cable-direct-driven robots: Design for wrench exertion[END_REF] are among the first ones to tackle this issue, and have been followed by several others. Cable interferences may also limit the workspace of parallel cable-driven robots. Cable collisions are generally avoided, e.g. [START_REF] Maeda | On design of a redundant wire-driven parallel robot WARP manipulator[END_REF], even if some authors suggest to permit collisions between the cables so as to obtain a larger workspace [START_REF] Wischnitzer | Wire-driven parallel robot: Permitting collisions between wires[END_REF]. The present paper does not deal with collision issues. An interval analysis based method that can be used to check if cable interferences occur is presented in [START_REF] Merlet | Legs interference checking of parallel robots over a given workspace or trajectory[END_REF].

The consequences of the unilateral nature of cable actuation on the shape and size of the usable workspace of parallel cabledriven robots are usually examined by means of wrench feasibility. In general terms, a pose (position and orientation) of the mobile platform is said to be wrench feasible if any wrench of a given required set of wrenches can be applied to the mobile platform by pulling it with the cables (no cable has to push), possibly with a range of allowed tension values, that is a minimal (always nonnegative) and a maximal admissible value for the tension in each cable [START_REF] Ebert-Uphoff | On the connections between cable-driven robots, parallel manipulators and grasping[END_REF], [START_REF] Bosscher | Wrench-feasible workspace generation for cable-driven robots[END_REF]. The problem is then to determine the set of wrench feasible poses, i.e., the so-called wrench-feasible workspace (WFW). Two particular instances of the WFW deserve their own names: the static (equilibrium) workspace and the force-closure (FC) workspace, the latter being also known as the wrench-closure workspace-note that the terminology is far from being unified. The static workspace is the set of poses of the mobile platform for which the cables can balance the weight of both the platform and the payload with tension forces only. It is of particular interest for cable suspended robots such as the ROBOCRANE [START_REF] Albus | The NIST ROBOCRANE[END_REF] which rely on gravity to keep the cables taut. The static workspace is a WFW whose required set of wrenches is reduced to a single wrench corresponding to the platform and payload weight. The force-closure workspace, whose name derives from an analogy with force-closure grasps of robotic hands [START_REF] Ebert-Uphoff | On the connections between cable-driven robots, parallel manipulators and grasping[END_REF], is the set of poses at which the platform can be fully constrained by the cables. The FC workspace is thus the very special case of a WFW whose required set of wrenches is the whole space of wrenches and the only constraint on the cable tensions is non-negativity.

Recently, "geometric methods" aiming at delineating the workspace boundary have been proposed in the case of the static [START_REF] Fattah | On the design of cable-suspended planar parallel robots[END_REF], so-called dynamic [START_REF] Barrette | Determination of the dynamic workspace of cable-driven planar parallel mechanisms[END_REF] and FC [START_REF] Gouttefarde | Analysis of the wrench-closure workspace of planar parallel cable-driven mechanisms[END_REF] workspaces of planar robots. Not without difficulties, they have also been applied to the static and FC workspaces of six-DOF robots [START_REF] Stump | Workspaces of cable-actuated parallel manipulators[END_REF]. However, except for these particular instances of the WFW, geometric methods are not currently available probably due the number and complexity of the equations describing the WFW boundary [START_REF] Bosscher | Wrench-feasible workspace generation for cable-driven robots[END_REF]. Furthermore, because they aim at visualizing the boundary, these methods are limited to 3D workspaces. For six-DOF robots, only a partial picture of the workspace is thus obtained since at least three out of the six pose variables must be fixed, e.g., when determining a constant-orientation workspace.

Therefore, the WFW is commonly determined by considering a grid of mobile platform poses, each pose of the grid being tested for wrench feasibility. The grid provides a discretization of the search space. In such a basic discretization method, the only tool needed is a test that determines if a given pose is wrench feasible. Classic methods of constrained optimization can usually be used to test wrench feasibility of a given pose. But, since feasibility rather than optimality is of interest, this does not necessarily yield very efficient tests. Therefore, more efficient approaches have been proposed. In the case of the FC workspace, references [START_REF] Roberts | On the inverse kinematics, statics, and fault tolerance of cable-suspended robots[END_REF], [START_REF] Stump | Workspaces of cable-actuated parallel manipulators[END_REF]- [START_REF] Diao | A method of verifying force-closure condition for general cable manipulators with seven cables[END_REF] present specific tests which are based on characterizations of FC already known in grasping by robotic hands [START_REF] Murray | A Mathematical Introduction to Robotic Manipulation[END_REF]. Related works can be found in [START_REF] Behzadipour | Design of reduced DOF parallel cable-based robots[END_REF], [START_REF] Hassan | Optimization of actuator forces in cablebased parallel manipulators using convex analysis[END_REF]. Only a few works, however, deals with the general case of the WFW, i.e., with minimal and maximal admissible cable tensions. In fact, tests that determine if a given pose belongs to the WFW are discussed in [START_REF] Bosscher | Wrench-feasible workspace generation for cable-driven robots[END_REF], [START_REF] Krut | Force performance indexes for parallel mechanisms with actuation redundancy, especially for parallel wire-driven manipulators[END_REF], [START_REF] Pham | Tension analysis of cable-driven parallel mechanisms[END_REF], some of them focusing on a specific required wrench set geometry. The method proposed in [START_REF] Bouchard | On the ability of a cabledriven robot to generate a prescribed set of wrenches[END_REF] is a valuable one since it enables to test wrench feasibility of a given pose for a great variety of required wrench set geometries.

A discretization method is quite straightforward to implement but it does not truly solve the problem of determining the WFW. In fact, out of the infinitely many poses of the discretized search space, only finitely many of them-those of the discretization grid-are tested for wrench feasibility. Hence, all the poses of the grid may be wrench feasible while the search space does not fully lie in the WFW because some poses which are not wrench feasible may be missed. Note that this issue is not unlikely to happen since the WFW has usually a non-convex geometry and can contains holes or consists of several disconnected components [START_REF] Gouttefarde | Analysis of the wrench-closure workspace of planar parallel cable-driven mechanisms[END_REF]. In this sense, the result provided by a discretization can never be guaranteed, i.e., one can never know if this result can be trusted. In practice, a discretization should yield good results as soon as the discretization grid is fine enough. However, especially for six-DOF robots, the grid is to remain relatively coarse since otherwise the number of its poses is rapidly too large for all of them to be tested in a realistic amount of time. This implies a strong trade-off between accuracy (number of poses in the grid) and computation time. For instance, in the case of a 6D space of poses (a 6-DOF robot), when the discretization of each axis of the search space contains 10 points, provided that the discretization grid is defined as the Cartesian product of these discretizations, which is generally the case, the total number of poses to be tested is 10 6 , a million. With 25 points per axis, the total number of poses is greater that two billion and 100 points per axis leads to 10 12 poses, such that testing all of them is too expensive.

The present paper proposes an alternative to discretization with the aim of addressing the aforementioned drawbacks. This alternative consists of numerical methods, mainly based on interval analysis, providing guaranteed WFW determinations in reasonable computation times. It is applicable to any n-DOF parallel robot driven by n or more than n cables and consists mainly in a test able to find boxes of poses fully inside the WFW and a complementary test that can detect boxes fully outside the WFW. The determination is said to be guaranteed in the sense that, besides taking into account rounding errors, wrench feasibility of each of the infinitely many poses of a search space is explored. Possibly, the method yields sets of poses for which no conclusion could be drawn at the current algorithm resolution. The proposed approach is notably based on a theorem due to Rohn [START_REF] Fiedler | Linear Optimization Problems with Inexact Data[END_REF], which allows us to conclude on the feasibility of some infinitely many linear systems of equations by testing the feasibility of (only) finitely many of them (Section IV). It is also based on consistency techniques applied to continuous domains (Section V). Additionally, the proposed approach is able to deal with uncertainties on the geometric design parameters (in the form of small uncertainty boxes) in reasonable computation times, as long as these uncertainties remain small. Some of the numerical tools proposed here have been introduced in a previous paper of the authors [START_REF] Gouttefarde | Wrench-feasible workspace of parallel cable-driven mechanisms[END_REF]. Besides, to the best of our knowledge, the only other work introducing interval analysis as a tool to compute the WFW is [START_REF] Bruckmann | Continuous workspace analysis, synthesis and optimization of wire robots[END_REF]. Compared to [START_REF] Bruckmann | Continuous workspace analysis, synthesis and optimization of wire robots[END_REF], the contributions of the present paper are:

• The use of Rohn's Theorem (Section IV) to test if a box of poses is fully included in the WFW. This avoids both time consuming bisections in the cable tension and mobile platform wrench spaces and the needs of considering permutations of the wrench matrix columns. • A means of testing whether a box of poses lies fully outside the WFW (Section V).

• A means of mitigating the effects of the so-called wrap-ping effect (Section VII), thereby improving computation time. These three points lead to interval analysis based determinations of the WFW having reasonable computation times.

The paper is organized as follows. The WFW is defined in Section II. Section III introduces interval evaluation of the wrench matrix of a parallel cable robot. Then, in Section IV, a detailed description of the main problem to be solved-testing the feasibility of infinitely many linear systems-is proposed. A sufficient condition for a box of poses to be fully inside the WFW is also introduced together with a means to test this condition. A sufficient condition for a box of poses to be fully outside the WFW and a means to test it are presented in Section V. In Section VI, the tests of Sections IV and V are used within usual branch-and-prune algorithms in order to determine the WFW. Then, in order to significantly improve efficiency, Section VII shows how to work with a wrench matrix without denominators. Finally, examples are provided in Section VIII and Section IX concludes the paper.

II. WRENCH-FEASIBLE WORKSPACE DEFINITION

Let us consider an n-DOF parallel robot whose mobile platform is driven by m cables with m ≥ n-generally n = 3 or n = 6-together with a fixed frame (O, x, y, z) and a mobile frame (P , x ′ , y ′ , z ′ ), the latter being attached at the platform reference point P as shown in Fig. 2. The point of the fixed base from which cable i extends is denoted A i whereas B i denotes the point of the platform at which cable i is attached. If the projections of --→ OA i , --→ P B i and --→ OP in the base frame are denoted a i , b i and p, respectively, the vector directed along cable i from B i to A i is l i = a ib ip. The corresponding unit vector is d i = l i /ρ i , where ρ i denotes the length of cable i. The pose of the mobile platform is defined by the position vector p and by the orientation of the mobile frame with respect to the base frame.

The relationship between the tensions in the cables and the wrench f -combination of a force and a moment-applied by the cables at the platform reference point P is [START_REF] Roberts | On the inverse kinematics, statics, and fault tolerance of cable-suspended robots[END_REF], [START_REF] Hiller | Design, analysis and realization of tendon-based parallel manipulators[END_REF]

Wτ = f (1)
where τ = (τ 1 , . . . , τ m ) T is the vector of cable tensions and W is the n × m pose dependent wrench matrix whose columns are denoted w i , W = (w 1 , . . . , w m ). Thus, the wrench applied at P by cable i is τ i w i . In the case of six-DOF robots, the wrench w i is

w i = d i b i × d i 6×1 (2)
where × denotes the cross product. Note that W = -J -T where J -1 is the so-called inverse Jacobian matrix [START_REF] Merlet | Parallel Robots[END_REF] whose line vectors are normalized Plücker coordinates of the cable lines. Let the required wrench set [f ] be the set of wrenches that the cables must apply at reference point P and let [τ ] be the m-dimensional box of allowed cable tensions. Usually, the box [τ ] is defined as

[τ ] = {τ | τ i ∈ [τ imin , τ imax ], 1 ≤ i ≤ m} (3) O x y z B i A i P x ′ y ′ z ′ ρ i cable i platform p b i a i d i Fig. 2. Notations.
where, for each i, τ imin and τ imax are two positive scalars such that τ imin < τ imax . A maximum tension τ imax is necessary in order to take into account the maximum torque of each actuator or the maximum tension that a cable can withstand. The minimum tension τ imin ≥ 0 allows one to ensure that none of the cables will be slack, a situation that may cause control problems.

In order to deal with the influence on the workspace of the unilateral nature of the forces applied by the cables, the WFW is of particular interest. It is is defined as follows [START_REF] Bosscher | Wrench-feasible workspace generation for cable-driven robots[END_REF].

Definition (WFW) The WFW is the set of mobile platform poses that are wrench feasible, i.e., for which, for any wrench f in [f ], there exists a vector of cable tensions τ in [τ ] such that Wτ = f . Determining the WFW is useful since it allows to take into account both the requirement of nonnegative cable tensions and that of maximum admissible cable tensions. Additionally, at a wrench feasible pose, provided that [f ] contains a neighborhood of the origin, the wrench matrix W has full rank. Generally, the WFW is thus a singularity free workspace.

III. INTERVAL WRENCH MATRIX

A. Interval Evaluation, Interval Vectors and Interval Matrices

This subsection provides a brief overview of interval analysis as used in the paper. More details can be found in [START_REF] Moore | Methods and Applications of Interval Analysis[END_REF]- [START_REF] Hansen | Global Optimization Using Interval Analysis[END_REF].

An interval [x] is a bounded set of real numbers defined by

[x] = [x, x] = {x ∈ R | x ≤ x ≤ x} (4)
where (x, x) ∈ R 2 and x ≤ x. The reals x and x are the lower and upper bound of the interval [x], respectively. A fundamental feature of interval analysis is the interval evaluation of a function. Let us consider a real-valued function f (x). The classic rules of addition, multiplication, etc. of real numbers can be extended to intervals yielding an interval arithmetic [START_REF] Moore | Methods and Applications of Interval Analysis[END_REF]. Moreover, by properly rounding the endpoints of computed intervals, rounding errors can be taken into account. Based on these basic operations and on the interval evaluation of basic algebraic and transcendental functions such as x 2 , sin and cos, almost any real function f (x) can be evaluated for an interval

[x] yielding an interval [f ] which encloses the image of [x] under f (denoted f ([x]), i.e., f ([x]) = {f (x) | x ∈ [x]} ⊆ [f ]. (5)
The converse inclusion does not hold in general and [f ] overestimates f ([x]) introducing pessimism in the evaluation. There exists several means to improve the interval evaluation of a function such as the use of the derivative of the function or of its Taylor series expansion, e.g. [START_REF] Moore | Methods and Applications of Interval Analysis[END_REF], [START_REF] Hansen | Global Optimization Using Interval Analysis[END_REF].

An n-dimensional interval vector

[x] = ([x 1 ], . . . , [x n ]) T is a set of vectors x = (x 1 , . . . , x n ) T such that, for each i, x i belongs to the interval [x i ].
For instance, the set of allowed cable tensions [τ ] defined in (3) is an interval vector. Considered as a set of points of R n , an interval vector is a box shaped set. A real-valued function f (x) of several variables can be interval evaluated yielding an interval

[f ] that contains the image f ([x]) of the interval vector [x] = ([x 1 ], . . . , [x n ]) T under f , i.e. f ([x]) = {f (x) | x i ∈ [x i ], 1 ≤ i ≤ n} ⊆ [f ]. (6)
Finally, an interval matrix [A] is a two-dimensional rectangular array of intervals. We will denote [A ij ] the interval located at the ith line and jth column of

[A]. An interval ma- trix is a continuous set of matrices and the notation A ∈ [A] is understood component-wise, i.e., by definition, A ∈ [A] if each real entry A ij of matrix A belongs to the corresponding interval [A ij ] of [A].

By means of interval arithmetic, the multiplication of an interval matrix [A] by an interval vector [x] yields an interval vector [b] = [A][x] such that

∀ A ∈ [A], ∀ x ∈ [x], Ax ∈ [b]. (7)
In the sense of ( 7), [b] is a box enclosure of the set

{Ax | A ∈ [A] and x ∈ [x]} (8)
which generally is not a box. Hence, there usually exist vectors b ∈ [b] which do not belong to this set, i.e., such that

∀ A ∈ [A], ∀ x ∈ [x], b = Ax. (9)

B. Interval Evaluation of the Wrench Matrix

Let the n-dimensional vector x denote the pose of the mobile platform. For instance, in the case of a 6-DOF robot, x can be the six-dimensional vector (p T , ψ T ) T where p defines the position of the platform and the three components of vector ψ are Euler angles defining its orientation.

Consider a box of mobile platform poses. This box is an n-dimensional interval vector, which we denote by [x]. Each component w ij of the wrench matrix W is pose dependent. Such a dependency is denoted by w ij = w ij (x). Referring to the preceding section, each w ij can be interval evaluated for the interval vector

∀ x ∈ [x], W(x) ∈ [W]. (10)
A 3 =(2.0,2.5) In [START_REF] Roberts | On the inverse kinematics, statics, and fault tolerance of cable-suspended robots[END_REF], W(x) stands for the wrench matrix obtained for the pose x. In words, for each and every pose x ∈ [x], the wrench matrix W obtained for x belongs to [W]. The interval matrix [W] is referred to as the interval wrench matrix. Let us note here that (10) must be verified for the results presented in Section IV-A and V-A to hold. The interval wrench matrix can be thought of as a box in R nm which encloses the set

A 1 = y P (x, y) (1
{W(x) | x ∈ [x]} (11)
of the infinitely many wrench matrices corresponding to the poses x lying in [x]. The set [START_REF] Takeda | A transmission index for in-parallel wiredriven mechanisms[END_REF] has an unknown complex shape since each component w ij of W is a nonlinear function of x. Consequently, the interval wrench matrix "overestimates" [START_REF] Takeda | A transmission index for in-parallel wiredriven mechanisms[END_REF] and it is important to note that there exist matrices

W O ∈ [W] which are not wrench matrices, i.e., ∀ x ∈ [x], W O = W(x)
. This is known as the wrapping effect [START_REF] Jaulin | Applied Interval Analysis[END_REF] which refers to the loss of the dependency relationships between the w ij at the time of the determination of [W]. In the sequel, the notation

[W] = [W]([x]) means that [W]
is the interval matrix obtained by interval evaluating each component of W for the box [x]. Hence, it verifies [START_REF] Roberts | On the inverse kinematics, statics, and fault tolerance of cable-suspended robots[END_REF]. In the pseudocodes presented in Section VI, this computation is denoted Compute_WrenchMatrix([x]). Note that the wrench matrix W is also a function of the geometric design parameters a i and b i defined in Section II. Let us collect all these design parameters in a vector u, e.g.

u = (a 1x , a 1y , a 1z , . . . , b mx , b my , b mz ). If in addition to a box [x], a box [u] of design parameters is given, the wrench matrix W can be interval evaluated for [x] and [u] yielding an interval wrench matrix [W] such that ∀ x ∈ [x], ∀ u ∈ [u], W(x, u) ∈ [W].
For instance, let us consider a simple point-mass two-DOF robot driven by three cables as shown in Fig. 3. The wrench matrix of this robot is the 2 × 3 matrix W = (d 1 , d 2 , d 3 ) where d i is the two-dimensional unit vector directed along cable i from P to A i . For the box of poses Finally, note that, for instance, although the matrix -1 1.5 0 -0.5 0 1.6 [START_REF] Williams Ii | Planar cable-direct-driven robots: Design for wrench exertion[END_REF] belongs to [W], it does not correspond to any wrench matrix obtained for x in [x].

IV. BOXES FULLY INCLUDED IN THE WFW

A. Feasibility of Interval Linear Systems

In this paper, the WFW considered are such that the required wrench set has the shape of a box in R n and, thus, can be identified with an n-dimensional interval vector [f ].

In order to compute the WFW by means of branch-andprune algorithms (Section VI), one of the main problem consists in verifying whether a given box (interval vector) of poses [x] is fully included in this workspace. According to the definition of the WFW, this problem amounts to testing if

∀ x ∈ [x], ∀ f ∈ [f ], ∃ τ ∈ [τ ] such that Wτ = f . ( 14
)
In words, [START_REF] Maeda | On design of a redundant wire-driven parallel robot WARP manipulator[END_REF] reads that for any pose x in [x] and for any wrench f in [f ] to be exerted by the cables on the mobile platform, there exists cable tensions τ in the allowed set [τ ] that can generate f , i.e., such that Wτ = f . Let x ∈ [x] be a pose of the mobile platform and W the corresponding wrench matrix. For a given wrench f ∈ [f ], the system of linear equations Wτ = f is said to be feasible if it admits a solution τ in [τ ]. Then, since there are infinitely many poses x in [x] and infinitely many wrenches f in [f ], verifying whether [START_REF] Maeda | On design of a redundant wire-driven parallel robot WARP manipulator[END_REF] is true amounts to verifying the feasibility of infinitely many linear systems Wτ = f . In other words, it requires the feasibility of all the individual systems belonging to the following continuous family of linear systems

{Wτ = f | x ∈ [x], f ∈ [f ]} . ( 15
)
To solve this difficult problem, one can rely on interval analysis tools that allow to deal with a so-called system of interval linear equations [START_REF] Neumaier | Interval Methods for Systems of Equations[END_REF], [START_REF] Hansen | Global Optimization Using Interval Analysis[END_REF], denoted

[W]τ = [f ] (16)
which, following [START_REF] Fiedler | Linear Optimization Problems with Inexact Data[END_REF], is said to be strongly feasible when

∀ W ∈ [W], ∀ f ∈ [f ], ∃ τ ∈ [τ ] such that Wτ = f . ( 17
)
In fact, let us consider a given box of poses [x] and the associated wrench matrix

[W] = [W]([x]
). According to [START_REF] Roberts | On the inverse kinematics, statics, and fault tolerance of cable-suspended robots[END_REF], [START_REF] Ebert-Uphoff | On the connections between cable-driven robots, parallel manipulators and grasping[END_REF] implies [START_REF] Maeda | On design of a redundant wire-driven parallel robot WARP manipulator[END_REF]. Hence, the strong feasibility (17) of the system of interval linear equations ( 16) is a sufficient condition for the box [x] to be fully included in the WFW. Nevertheless, since the interval wrench matrix [W] is only an enclosure and not an exact description of the set (11), ( 17) is sufficient but not necessary for [x] to be fully inside the WFW.

A theorem, due to Rohn, providing a necessary and sufficient condition for [START_REF] Ebert-Uphoff | On the connections between cable-driven robots, parallel manipulators and grasping[END_REF] to be true is presented in Section IV-C. This theorem applies to the case m ≥ n of n-DOF parallel robots driven by n or more than n cables. In the particular case m = n (as many cables as DOF), note that well-known tools of interval analysis dealing with square systems of interval linear equations [START_REF] Neumaier | Interval Methods for Systems of Equations[END_REF], [START_REF] Hansen | Global Optimization Using Interval Analysis[END_REF] can also be applied.

B. A Set of Vertex Matrices and Vertex Vectors

Before introducing Rohn's Theorem in the next subsection, a set of "vertex" matrices of an interval matrix has to be defined. Let [A] be an n×m interval matrix whose components are the intervals

[A ij ] = [A ij , A ij ]
and let Y n be the set of ndimensional vectors y whose components y i are equal either to 1 or to -1. We associate with each of the 2 n vectors y ∈ Y n the matrix A y whose components are

A y ij = A ij + (A ij -A ij )(1 -y i )/2. ( 18
)
Note that the ith component y i of y defines completely the ith line of A y , e.g., when

y i = -
Let us also define the set of "vertex" vectors of an interval vector [b] as the set of the 2 n vectors b y , y in Y n , whose components are defined by

b y i = b i + (b i -b i )(1 + y i )/2. ( 20
)
where the interval

[b i , b i ] is the ith component of [b]. Geo-

C. A Useful Theorem

The system of interval linear equations ( 16) is a shorthand notation for the set of linear systems

{Wτ = f | W ∈ [W] and f ∈ [f ]} . (21)
The following theorem states that the infinitely many systems belonging to [START_REF] Gouttefarde | Analysis of the wrench-closure workspace of planar parallel cable-driven mechanisms[END_REF] are all feasible, i.e., [START_REF] Ebert-Uphoff | On the connections between cable-driven robots, parallel manipulators and grasping[END_REF] is true, if and only if finitely many of them are feasible.

Theorem 1 (Rohn) The system of interval linear equations

[W]τ = [f ] is strongly feasible if and only if the 2 n systems of linear equations W y τ = f y , y ∈ Y n , are all feasible.
The necessary condition is trivial whereas the reader interested in the proof of the sufficient condition is referred to [START_REF] Fiedler | Linear Optimization Problems with Inexact Data[END_REF] (Chapter 2). Since strong feasibility ( 17) is a sufficient condition for a box [x] to lie within the WFW, this very useful theorem allows us to conclude that [x] is fully inside the WFW whenever each of the 2 n (classic) linear systems W y τ = f y , y ∈ Y n , is feasible. W y and f y are the vertex matrix of [W] and the vertex vector of [f ] defined by [START_REF] Bosscher | Wrench-feasible workspace generation for cable-driven robots[END_REF] and [START_REF] Barrette | Determination of the dynamic workspace of cable-driven planar parallel mechanisms[END_REF], respectively.

Note that the feasibility of a system W y τ = f y is a wellknown problem in linear programming (LP). For example, it can be tested by means of the simplex method applied to the general LP problem [START_REF]Linear Programming[END_REF] (chapter 8)

min c T τ s.t. W y τ = f y and τ ∈ [τ ] (22)
for which any linear form c, e.g. the trivial linear form c = 0, can be considered since only the feasibility of the problem is to be determined. Alternatively, one can also rely on the methods presented in [START_REF] Bosscher | Wrench-feasible workspace generation for cable-driven robots[END_REF], [START_REF] Krut | Force performance indexes for parallel mechanisms with actuation redundancy, especially for parallel wire-driven manipulators[END_REF]- [START_REF] Bouchard | On the ability of a cabledriven robot to generate a prescribed set of wrenches[END_REF]. Note that the method introduced in [START_REF] Neumaier | Safe bounds in linear and mixedinteger linear programming[END_REF] allows one to keep the numerical guarantee of interval analysis (the simplex method being highly sensitive to rounding errors).

In brief, by means of Theorem 1, a procedure denoted Feasible([W], [f ], [τ ]) can be written. This procedure returns true if the necessary and sufficient condition stated in Theorem 1 is true and it returns unknown otherwise. When Feasible() returns true, it thus ensures that the box of poses [x] for which [W] has been calculated is fully included in the WFW. Feasible() consists in testing the feasibility of at most 2 n linear systems Wτ = f .

V. BOXES FULLY OUTSIDE THE WFW

A means of testing whether a given box of poses [x] lies fully outside the WFW is a valuable tool. Indeed, when Feasible() returns true, the box [x] at hand is guaranteed to be fully included in the WFW. But, when Feasible() returns unknown nothing is known about the location of [x] with respect to the WFW since Feasible() is based on condition [START_REF] Ebert-Uphoff | On the connections between cable-driven robots, parallel manipulators and grasping[END_REF], the latter being only a sufficient condition for [x] to be fully inside the WFW.

A. A Sufficient Condition

By definition, a pose x of the mobile platform of an n-DOF parallel robot driven by m cables belongs to the WFW if

∀ f ∈ [f ], ∃ τ ∈ [τ ] such that Wτ = f . (23)
A direct consequence of the convexity of [f ] and of the set

F = {f | f = Wτ , τ ∈ [τ ]
}-the available net wrench set [START_REF] Bosscher | Wrench-feasible workspace generation for cable-driven robots[END_REF]is the equivalence between [START_REF] Gallina | Manipulability of a planar wire driven haptic device[END_REF] and the following condition

∀ f y ∈ {f y }, ∃ τ ∈ [τ ] such that Wτ = f y (24)
in which, using the notations of Section IV-B, {f y } denotes the set of vertices of the box [f ]. A proof of this equivalence can be found in [START_REF] Bosscher | Wrench-feasible workspace generation for cable-driven robots[END_REF] in the case τ imin = 0.

A single pose x lies outside the WFW if and only if (24) is false. Hence, a box of poses [x] is fully outside the WFW if and only if [START_REF] Voglewede | Application of the antipodal grasp Theorem to cable-driven robots[END_REF] is false for any x ∈ [x], that is, if and only if

∀ x ∈ [x], ∃ f y ∈ {f y } such that ∀ τ ∈ [τ ], Wτ = f y . (25)
In words, [x] is fully outside the WFW if and only if, for any pose x in [x], there exists at least one vertex f y of the required wrench set [f ] which cannot be generated by the cables with tensions in [τ ]. Equation ( 25) is a necessary and sufficient condition for a box of poses [x] to be fully outside the WFW but it appears to be difficult to test it. Instead, we propose to consider the following condition

∃ f y ∈ {f y } such that ∀ W ∈ [W], ∀ τ ∈ [τ ], Wτ = f y (26) where [W] = [W]([x]
). Since the implication ( 26) ⇒ (25) holds, ( 26) is a sufficient condition for a box [x] to be fully outside the WFW. The converse implication is generally not true so that this condition is not necessary. The implication (26) ⇒ (25) is a consequence of (10) and of the fact that in [START_REF] Pham | Force-closure workspace analysis of cable-driven parallel mechanisms[END_REF] the wrench f y which cannot be generated with admissible tensions τ depends upon the pose x considered in [x] whereas, in [START_REF] Ferraresi | A new methodology for the determination of the workspace of six-DOF redundant parallel structures actuated by nine wires[END_REF], f y does not depend on x, i.e., it cannot be generated with admissible cable tensions whatever W ∈ [W] and thus whatever x ∈ [x]. In this sense, [START_REF] Ferraresi | A new methodology for the determination of the workspace of six-DOF redundant parallel structures actuated by nine wires[END_REF] is stronger than [START_REF] Pham | Force-closure workspace analysis of cable-driven parallel mechanisms[END_REF].

B. A Test Based on Consistency

For a given interval wrench matrix [W], (26) can be tested as follows: the vertices f y of [f ] are considered in turn and, for each f y , we check if the system of interval linear equations [W]τ = f y is inconsistent, that is, whether or not

∀ W ∈ [W], ∀ τ ∈ [τ ], Wτ = f y . ( 27
)
To this end, one can rely on so-called consistency techniques applied to continuous domains [START_REF] Hansen | Global Optimization Using Interval Analysis[END_REF], [START_REF] Lhomme | Consistency techniques for numeric CSPs[END_REF], [START_REF] Collavizza | Comparing partial consistencies[END_REF]. These numerical techniques do not aim at solving the system of equations but rather at narrowing down the size of the box [τ ] such that no solution is lost. Two examples are hull consistency and 3B-consistency which can be found in [START_REF] Merlet | An Algorithms Library of Interval Analysis for Equation Systems[END_REF], for example. Due to space limitations, details on consistency techniques applied to continuous domains are not provided in this paper. The important point for the problem at hand is that applying a consistency technique to the system [W]τ = f y with variables τ and associated domain [τ ] yields a new box [τ ] ′ such that, on the one hand, [τ ] ′ ⊆ [τ ] and, on the other hand, if

∃ W ∈ [W], ∃ τ ∈ [τ ] such that Wτ = f y (28) then τ ∈ [τ ] ′ , i.e.,

VI. DETERMINATION OF THE WFW: BRANCH-AND-PRUNE ALGORITHMS

This section presents examples of pseudocodes that illustrate how the previously introduced procedures Feasible() and Out() can be used to determine the WFW by means of n-dimensional boxes, to test if a given prescribed workspace is fully included in the WFW and to obtain the total orientation WFW. These pseudocodes are essentially branch-and-prune algorithms.

A. Determination of the WFW

The algorithm shown in Fig. 4 manages a list L of pose boxes [x] initialized with the search box B. The current box [x] is found to be either fully inside the WFW (line 5), or fully outside the WFW (line 7), or else [x] is bisected (line 11) as long as it is not too small according to the threshold ǫ. In the latter case, the two resulting smaller boxes are put back in the list L so that each becomes the current box at a later time during the execution of the algorithm.

This algorithm outputs the lists L in , L out and L neg . The properties of the procedure Feasible() (resp. Out()) ensure that all the boxes of L in (resp. L out ) are fully included in the WFW (resp. fully outside). The boxes of L neg are of two types.

• A box [x] of the first type is a box too small to be bisected and containing a part of the WFW boundary.

• A box [x]
of the second type is too small to be bisected but does not contain any WFW boundary pose: it is either fully inside or else fully outside the WFW but not detected as such at line 5 or 7. Such boxes exist because the procedures Feasible() and Out() are based on conditions which are only sufficient (Sections IV and V). This is a negative consequence of the wrapping effect, which necessarily comes along with the computation of [W] (Section III-B), and of the fact that the problem of finding boxes fully outside the WFW has been relaxed so as to obtain the procedure Out() (condition ( 26) is stronger than [START_REF] Pham | Force-closure workspace analysis of cable-driven parallel mechanisms[END_REF], see Section V).

Due to the existence of boxes [x] of the second type, L neg provides a "thick" representation of the WFW boundary.

The accuracy of the algorithm, i.e. the size of the boxes of L neg , can be adjusted by means of the threshold ǫ. Obviously, the smaller is ǫ the higher the computation time.

The WFW boundary is always contained within L neg , i.e., the boxes of L neg provides a conservative approximation of the WFW boundary. Indeed, consider a pose x of B which lies on the WFW boundary and let us show that x belongs necessarily to L neg . Assume to the contrary that x belongs only to boxes of L in and/or of L out . The WFW being a closed set, x ∈ WFW and thus x cannot belong to L out . Hence, x belongs solely to boxes of L in . Then, either x is an interior point of a (unique) box of L in or x lies on the common boundary of several boxes of L in . But, in both cases, there exists a neighborhood of x lying in the union of the boxes of L in containing x and consequently fully included in the WFW. Then, x lies in the WFW interior in contradiction with the fact that it is on the WFW boundary. In conclusion, a pose x of B lying on the WFW boundary belongs neither to L in nor to L out and thus necessarily belongs to (a box of) L neg . This shows that the part of the WFW boundary lying in the search box B is necessarily contained in boxes of L neg .

Finally, note that the structure of the algorithm shown in Fig. 4-as well as those of the algorithms described in the two following subsections-makes it well adapted to parallel computing.

Input: B, [f ], [τ ], ǫ Output: Lin, Lout, Lneg 1. L ← B % Initialize list L with the search box B 2. while L = {∅} do 3. [x] ← Extract(L) 4. [W] = Compute_WrenchMatrix([x]) 5. if Feasible([W], [f ], [τ ]) then 6. Lin ← [x] % [x] ⊆ WFW 7. else if Out([W], {fy}, [τ ]) then 8. Lout ← [x] % [x] ∩ WFW = {∅} 9.
else % Both Feasible() and Out() returned unknown

L ← Bisect([x])

12.

else % [x] is too small to be bisected 13.

Lneg ← [x]

14.

end if 15. end if 16. end while Fig. 4. A branch-and-prune algorithm to determine the WFW.

Input: W, [f ], [τ ], L, ǫ Output: L 1. if L = {∅} then 2.
L ← W % Initialize list L with the box workspace W 3. end if 4. while L = {∅} do 5.

[x] ← Extract(L)

6.

[W] = Compute_WrenchMatrix([x])

7. if Out([W], {fy}, [τ ]) then 8. return false 9. else if Feasible([W], [f ], [τ ]) then 10. continue % [x] ⊆ WFW 11. else 12. if Size([x]) > ǫ then 13.

L ← Bisect([x])

14.

else % [x] is too small to be bisected 15.

L ← [x]

B. Test of a Box Workspace W

Fig. 5 shows the pseudocode of an algorithm using the same ingredients as those of Fig. 4 in order to test whether or not a given prescribed workspace W (a big box) is fully included in the WFW. When this algorithm returns true, it ensures that W is fully included in the WFW since all of the infinitely many poses of W have been checked for wrench feasibility. When false is returned, a part of W lies completely outside the WFW (line 8). Finally, when the state unknown is returned at line 16, the algorithm is not able to conclude-W may be fully inside the WFW. In this latter case, the algorithm can be executed again with a smaller threshold ǫ and with the final list L of the previous execution as an input.

C. Total Orientation WFW

For parallel cable-driven robots having both translational and rotational DOF, the total orientation WFW is defined as the set of positions p of the reference point P such that the [p] ← Extract(L)

4.

[x] = ([p], [ψ])

5. state = FullyInside([x],[f ],[τ ],ǫori) 6.
if state = true then

L ← Bisect([p])

13.

else % [p] is too small to be bisected 14.

Lneg ← [p]

15.

end if 16. end if 17. end while Fig. 6. A basic algorithm to determine the total orientation WFW. mobile platform pose x = (p, ψ) belongs to the WFW for any orientation ψ taken in a given set of orientations [ψ]which, in this paper, is a box. The total orientation WFW is of interest because it can be visualized. Indeed, it is a subset of the Cartesian space of the robot (the space of the positions of the reference point P ).

The pseudocode shown in Fig. 6 is a basic algorithm that computes the total orientation WFW by means of a set of position boxes [p]. The output list L in contains these latter boxes whereas L out contains boxes covering the exterior of the total orientation WFW. The output list L neg contains the boxes [p] for which the algorithm cannot conclude. The important fact about L neg is that it always contains the boundary of the total orientation WFW since the procedures Feasible() and Out()-which are used in FullyInside()-never return true when applied to a box containing a part of the WFW boundary. The procedure FullyInside() called at line 5 is a slight modification of the algorithm shown in Fig. 5 in which the bisection (line 13 in Fig. 5) is only applied to the orientation part of the current box [x] with associated threshold ǫ ori . FullyInside() returns true if [x] is fully included in the WFW, false if a part of [x] is found to be outside the WFW and unknown otherwise.

D. On the Effect of the Bisections

In the algorithms presented in Fig. 4 to 6, the repeated bisections progressively reduce the size of the boxes [x] (or [p]), stored in the list L, for which the procedures Feasible() and Out() (or FullyInside()) cannot conclude. Ultimately, the current box [x] would be reduced to a single pose x and the interval wrench matrix [W] = [W]([x]) would consequently be reduced to the wrench matrix W obtained for x. According to the definition of the WFW stated in Section II, for such a unique pose x and associated wrench matrix W, (17) (resp. [START_REF] Ferraresi | A new methodology for the determination of the workspace of six-DOF redundant parallel structures actuated by nine wires[END_REF]) is necessary and sufficient for x to belong to the WFW (resp. to be outside the WFW), whereas it is only sufficient in the case of a non-degenerate box [x]. This characteristic of ( 17) and ( 26) is a key property that makes the branch-andprune algorithms presented in this section work well.

In order to emphasize this important point, consider for instance the condition [START_REF] Ebert-Uphoff | On the connections between cable-driven robots, parallel manipulators and grasping[END_REF]. For a box [x] which is fully included in the WFW, [START_REF] Ebert-Uphoff | On the connections between cable-driven robots, parallel manipulators and grasping[END_REF] may not be verified because the enclosure [W] overestimates the set of wrench matrices [START_REF] Takeda | A transmission index for in-parallel wiredriven mechanisms[END_REF], i.e., because of the wrapping effect. After the bisection of [x] which yields two smaller boxes, say [x] 1 and [x] 2 , the overestimations involved in the computations of the interval wrench matrices

[W] 1 = [W] 1 ([x] 1 ) and [W] 2 = [W] 2 ([x] 2 )
are somehow lesser and the condition [START_REF] Ebert-Uphoff | On the connections between cable-driven robots, parallel manipulators and grasping[END_REF] has more chance of being true for both [x] 1 and [x] 2 than for their parent box

[x].
Finally, note that the strategy used for choosing the bisected variable can play an important role as an appropriate choice may avoid a large number of bisections. In the present work, only basic strategies have been tested such as the roundrobin strategy in which variables are bisected alternately. Other strategies may turn out to be useful, e.g., the maximum smear heuristic [START_REF] Kearfott | Rigorous Global Search: Continuous Problems[END_REF].

VII. IMPROVEMENT OF EFFICIENCY

The algorithms presented in the previous section are basic. In order to improve their efficiency, many tricks can be employed. For instance, in the algorithm shown in Fig. 5, one can first verify if one of the vertices of the prescribed workspace W is outside the WFW. Indeed, in this case, it is useless to explore the whole workspace W with a branchand-prune algorithm. Besides, the efficiency of the proposed methods can also be improved by modifying equation ( 1) with which we work from the outset. The gain in efficiency is substantial enough to deserve a discussion which is the purpose of the present section.

A. Wrench Matrix Without Denominators

The computation time of the algorithms presented in Section VI is highly dependent upon the quality of the enclosure of the set (11) by the interval wrench matrix [W]. Sharper enclosures lead to a lower number of bisections and thus to a lower computation time. To this end, this section presents modifications of the problem which allows us to work with a matrix W * whose symbolic expression is simpler than that of W. Indeed, due to the so-called dependence problem [START_REF] Jaulin | Applied Interval Analysis[END_REF]- [START_REF] Hansen | Global Optimization Using Interval Analysis[END_REF], the quality of the interval evaluation of an expression depends highly on the number of occurrences of each variable for which the expression is evaluated. The fewer occurrences, the better is the interval evaluation. Hence, it is worth working with a matrix W * whose components w * ij have symbolic expressions containing less occurrences of the pose variables than those of W. A good candidate for W * is the matrix obtained from the wrench matrix W by removing the denominators appearing in each of its elements, i.e.

W * = WD (29)
where D = diag(ρ 1 , . . . , ρ m ) is an m × m diagonal matrix with the cable lengths ρ i on its diagonal. In the case of six-DOF robots, the column vectors of W * are given by

w * j = l j b j × l j 6×1 . ( 30
)
Compared to (2), [START_REF] Hassan | Optimization of actuator forces in cablebased parallel manipulators using convex analysis[END_REF] involves l i instead of d i = l i /ρ i such that the denominators ρ i have been removed. Since ρ i is a function of the pose variables x, the expressions of the components of W * contain less occurrences of the pose variables than those of W. For a given box of poses [x], the quality of the interval evaluation of W * , [W * ] = [W * ]([x]), is thereby much better than that of W, i.e. the wrapping effect is reduced.

B. Modification of the Sufficient Conditions

So as to work with W * instead of W, the sufficient condition [START_REF] Ebert-Uphoff | On the connections between cable-driven robots, parallel manipulators and grasping[END_REF] for a box of poses [x] to be fully included in the WFW must be modified as follows

∀ W * ∈ [W * ], ∀ f ∈ [f ], ∃ τ * ∈ [τ * ] such that W * τ * = f (31
) with the interval vector [τ * ] defined by

[τ * ] = τ * | τ * i ∈ [τ imin /ρ i , τ imax /ρ i ], ∀ 1 ≤ i ≤ m (32
) where ρ i and ρ i are, respectively, the lower and upper bounds of the interval evaluation

[ρ i ] of ρ i for the box [x] ([ρ i ] = [ρ i ]([x]) = [ρ i , ρ i ]
) whereas τ imin and τ imax are defined in [START_REF] Ishii | A 3D spatial interface device using tensed strings[END_REF]. In [START_REF] Krut | Force performance indexes for parallel mechanisms with actuation redundancy, especially for parallel wire-driven manipulators[END_REF], the interval matrix [W * ] corresponds to the interval evaluation of W * for the box [x]. We shall note that the modified set of allowed cable tensions [τ * ] is properly defined only if

τ imin /ρ i ≤ τ imax /ρ i (33)
Thus, the problem can be modified only if [START_REF] Bouchard | On the ability of a cabledriven robot to generate a prescribed set of wrenches[END_REF] is verified for all i. The fact that (31) is a sufficient condition for [x] to be fully included in the WFW is proved in the appendix. Finally, in order to work with W * instead of W, the sufficient condition (26) for a box [x] to be fully outside the WFW is to be modified as follows

∃ f y ∈ {f y } | ∀ W * ∈ [W * ], ∀ τ * ∈ [τ * ], W * τ * = f y (34) where [W * ] = [W * ]([x]) and [τ * ] is defined by [τ * ] = τ * | τ * i ∈ [τ imin /ρ i , τ imax /ρ i ], ∀ 1 ≤ i ≤ m (35) with [ρ i , ρ i ] = [ρ i ]([x]
). The proof of the fact that ( 34) is a sufficient condition for [x] to be fully outside the WFW resembles that of [START_REF] Krut | Force performance indexes for parallel mechanisms with actuation redundancy, especially for parallel wire-driven manipulators[END_REF] and is therefore left to the reader. Note that the box [τ * ] defined in [START_REF] Gouttefarde | Wrench-feasible workspace of parallel cable-driven mechanisms[END_REF] is not the same as the one defined in [START_REF] Pham | Tension analysis of cable-driven parallel mechanisms[END_REF]. Note also that, contrary to [START_REF] Pham | Tension analysis of cable-driven parallel mechanisms[END_REF], no condition such as (33) must be fulfilled for [START_REF] Gouttefarde | Wrench-feasible workspace of parallel cable-driven mechanisms[END_REF] to have a meaning (provided that ρ i = 0). Hence, one can (and should) always use [START_REF] Fiedler | Linear Optimization Problems with Inexact Data[END_REF] in place of [START_REF] Ferraresi | A new methodology for the determination of the workspace of six-DOF redundant parallel structures actuated by nine wires[END_REF].

VIII. EXAMPLES

Our implementation in C++ uses the interval arithmetic of the BIAS/Profil C++ library, the simplex method of the GNU Linear Programming Kit (GLPK) and the hull consistency procedure of ALIAS [START_REF] Merlet | An Algorithms Library of Interval Analysis for Equation Systems[END_REF]. The computation times have been obtained on a DELL XPS laptop (Core 2 Duo CPU T7500, 2.20 GHz).

A. 3-DOF Planar Robots

Let us consider the 3-DOF planar robot driven by four cables shown in Fig. 7 (left) in its reference orientation. The actuated reels fixed to the base are located at the vertices of a square of side length 1 m. The mobile platform is a rectangle of length l p and height h p . We let l p and h p be negative in order to consider robots with crossed cables. For instance, the robot obtained for l p = 0.2 m and h p = -0.2 m is shown in Fig. 8 T (m,m,rad) is found not to be fully included in the WFW in less than 1 s for h p = 0.2, h p = 0.1 and h p = 0 (m). For h p = -0.1 and h p = -0.2 (m), this box is found to be fully inside the WFW in 2 s.

B. A 6-DOF Robot

The 6-DOF parallel cable-driven robot considered is shown in Fig. 9 in its reference orientation. Its base frame is a cube of edge length 1 m. Its mobile platform, a regular tetrahedron of I Base frame I Uncertainty box edge length l, is driven by eight cables. Let us also consider the WFW defined by τ min =1 N, τ max =540 N for each cable and The computation times of our implementation of the pseudocode of Fig. 5 that determines whether W is fully included in the WFW are shown in Table I for various values of l and s. Table II shows examples of computation times necessary to test the poses of a discretization of W for various values of the number of points used to discretize each axis. The results are consistent as all the poses of the various discretization grids are found to lie in the WFW. Comparing these results with those of Table I shows that, in this example, the interval analysis based method (computation time of 47 s) is more efficient than a discretization with at least 6 points per axis which is a remarkable result since the infinitely many poses of W have been verified to be wrench feasible while only finitely many of them are checked by a discretization. is an example in which the wrapping effect has a negative impact on the efficiency since most of the boxes in L neg do not contain any boundary pose of the total orientation WFW (boxes referred to as being of the "second type" in Section VI-A).

© W I Cable A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8

C. Including Uncertainties

Let us consider again the WFW, the prescribed workspace W and the 6-DOF parallel cable robot of Section VIII-B (for l = 0.2 m). Let us assume that each a i and each b i , which define the geometry of the robot (see Fig. 2), are not exactly known. Instead, the end point of each of these vectors is only known to lie in a small box. Such an uncertainty box is illustrated in Fig. 9 in the case of a 7 . In Section III-B, a vector u collecting all the geometric design parameters has been defined. The uncertainties on a i and b i yields a (small) box [u] of uncertain design parameters.

The procedures of Section VI can easily be modified so as to handle such boxes [u]. For instance, in the algorithm of Fig. 5, at line 6, it suffices to compute the interval wrench matrix [W] by interval evaluating W for the current box [x] and for

[u]. Note that, since ∀ x ∈ [x], ∀ u ∈ [u], W(x, u) ∈ [W],
when Feasible() (resp. Out()) returns true, it means that for all u in [u], the box of poses [x] is fully included in the WFW (resp. fully outside). In other words, [x] is guaranteed to be fully included in the WFW (resp. fully outside) for any value of the geometric design parameters in their respective uncertainty boxes.

For example, for uncertainty boxes of edge lengths 0.002 m, 0.004 m and 0.006 m, a modified version of the algorithm of Fig. 5 shows that W is fully included in the WFW in 128 s, 297 s and 1095 s, respectively. For larger uncertainty boxes, because bisections in the high-dimensional space of geometric design parameters would be required (u has dimension 48 for a 6-DOF robot with 8 cables), the computation time can be very high. Note however that, even for small uncertainty boxes for which the method proposed in this paper is able to conclude, a discretization of each uncertainty box (even very coarse), besides providing no guarantee on the result validity, leads to prohibitive computation times due the dimension of u.

IX. CONCLUSION

An interval analysis based approach to the WFW determination of n-DOF parallel robots driven by n or more than n cables has been proposed. The WFW considered is such that the required wrench set is a box. The main novelty of our approach is to provide two tests. The first one enables to find boxes guaranteed to be fully inside the WFW whereas the second one enables to detect boxes guaranteed to be fully outside the WFW. The paper has then discussed the use of these two tests within standard branch-and-prune algorithms. Moreover, the use of a wrench matrix without denominators has been proposed as a means of reducing the so-called wrapping effect thereby significantly improving computation time.

The distinctive characteristic of our approach is that none of the infinitely many poses of the search space is disregarded. The results are thus always of better quality since full-dimensional sets of poses (here boxes) are returned, in comparison to a discrete finite set of individual poses in the case of a discretization. Let us also point out that testing all the poses of a fine enough discretization grid always leads to a computation time higher than the one of the approach proposed in this paper. Besides, our approach turns out to be particularly suited to test whether a given prescribed workspace is fully included in the WFW, a problem for which it offers competitive computation times. Hence, it is a valuable tool for the dimensional synthesis framework introduced in [START_REF] Hao | Multi-criteria optimal design of parallel manipulators based on interval analysis[END_REF]. Additionally, it has been briefly illustrated how the proposed approach can deal with small uncertainties on the geometric design parameters of a parallel cable robot. A drawback of the proposed approach is that its computation time can hardly be predicted.

The approach to the WFW determination proposed in this paper may also return boxes of poses for which no conclusion could be drawn (at the current algorithm resolution). The set of these boxes has the important property of always containing the part of the WFW boundary included in the search space thereby providing a conservative approximation of this boundary. Note however that, among these boxes, some of them are either fully inside or else fully outside the WFW but not detected as such due to the wrapping effect. In this paper, we have proposed and shown how to work with a wrench matrix without denominators so as to reduce this effect. Further improving efficiency by mitigating the negative consequences of the wrapping effect remains an important research issue and is part of our future works.

APPENDIX

where ρ i is the length of cable i for the pose x at hand. Now, since τ * is in [τ * ], for each of its component τ * i we can write τ imin /ρ i ≤ τ * i ≤ τ imax /ρ i .

Moreover, by definition of ρ i and ρ i , for each i we have 0 ≤ ρ i ≤ ρ i ≤ ρ i which, assuming ρ i > 0 (i.e., ρ i = 0), implies 1 ≤ ρ i /ρ i and ρ i /ρ i ≤ 1 [START_REF] Merlet | Parallel Robots[END_REF] and consequently τ imin ≤ (τ imin ρ i )/ρ i and (τ imax ρ i )/ρ i ≤ τ imax [START_REF] Moore | Methods and Applications of Interval Analysis[END_REF] since τ imax ≥ τ imin ≥ 0. Multiplying both inequalities of (37) by ρ i , according to [START_REF] Moore | Methods and Applications of Interval Analysis[END_REF] and since τ i = ρ i τ * i , we obtain

τ imin ≤ τ i ≤ τ imax . (40)
In other words, τ is in [τ ], the system Wτ = f is feasible and, consequently, x belongs to the WFW. Since this reasoning is valid for any pose x in [x], (31) is a sufficient condition for [x] to be fully included in the WFW.

  [x] yielding an interval [w ij ]. According to (6), [w ij ] satisfies the following property: for all poses x in [x], w ij (x) belongs to [w ij ]. Therefore, the n × m interval matrix [W] whose components are the intervals [w ij ] has the following fundamental property

2 Fig. 3 .

 23 Fig. 3. A point-mass cable-driven robot and its box workspace [x].

  [x] = ([1.5, 2.5], [0.4, 1.8]) T , each component of each d i is interval evaluated yielding the following [W] [-2.986, -0.239] [0.344, 2.334] [-0.715, 0.715] [-2.886, -0.0239] [-1.734, 0.134] [0.324, 3.0] . (12) It can be verified that for any position x of P lying in [x], the associated wrench matrix W lies within [W].

  metrically, the set of vectors b y is the set of vertices of the n-dimensional box [b].

10 .

 10 if Size([x]) > ǫ then 11.

Fig. 5 .

 5 Fig. 5. Testing a prescribed workspace W for full inclusion in the WFW.

  Input: B, [ψ], [f ], [τ ],ǫpos, ǫori Output: Lin, Lout, Lneg 1. L ← B % Initialize list L with the search box B 2. while L = {∅} do 3.

7 .

 7 Lin ← [p] % [p] ⊆ total orientation WFW 8. else if state = false then 9. Lout ← [p] % [p] ∩ (total orientation WFW) = {∅} 10. else % state = unknown 11.if Size([p]) > ǫpos then 12.

Fig. 7 .Fig. 8 .

 78 Fig. 7. A 3-DOF planar parallel cable-driven robot (left) and its constantorientation WFW (right) for orientation φ = π/4 and geometric parameters lp = 0.2 m, hp = -0.2 m (crossed cables)-computation time of 2 s (right figure).

  together with its total orientation WFW obtained by the algorithm of Section VI-C for the set of orientations [-π/5, π/5]. The WFW is defined here by τ min =1 N and τ max =50 N for each cable and [f ]=[[-10, 10], [-10, 10], [-0.5, 0.5]] T (N,N,N.m). A constant-orientation WFW obtained with the algorithm of Section VI-A is shown in the right subfigure of Fig. 7. Using the pseudocode of Section VI-B, for l p = 0.2 m, the box of poses [x]=[[-0.2, 0.2], [-0.2, 0.2], [-π/5, π/5]]

Fig. 9 .

 9 Fig. 9. A six-DOF parallel robot driven by eight cables.

  [f ]=[[-10, 10],[-10, 10],[-10, 10], [-0.5, 0.5], [-0.5, 0.5], [-0.5, 0.5]] T (forces in N, moments in N.m) together with a prescribed workspace W. The position components of W form a cube of edge length s whose center coincides with that of the base frame whereas its orientation part is a box of three Euler angles φ, θ and ψ (XYZ convention) such that φ ∈ [-π/12, π/12], θ ∈ [-π/12, π/12] and ψ = 0 (rad). W is thus a five-dimensional workspace.

Fig. 10 shows

 10 the total orientation WFW obtained by the algorithm of Section VI-C for the set of orientations φ ∈ [-π/12, π/12], θ ∈ [-π/12, π/12] and ψ = 0 (rad). For clarity, only the boxes of L in are shown. The considered search space (box B) is the whole base frame cube. The corresponding computation time is 1567 s. Despite this computation time value, the total volume of the boxes in L neg -0.6 m 3 for a search space volume of 1 m 3 -remains quite large. This

Fig. 10 .

 10 Fig. 10. Total orientation workspace computation for ǫpos = ǫ ori = 0.05 and l = 0.2 m (L in , Lout and Lneg total volumes are equal to 0.22 m 3 , 0.18 m 3 and 0.6 m 3 , respectively).

  Proof of (31): let x be any pose lying in the box[x]. According to (31), for each f ∈ [f ] there exists a τ * in [τ * ] such that W * τ * = f where W * = W * (x). If W = W(x)is the wrench matrix associated with the pose x, according to (29), we have W * = WD. Then, W * τ * = f implies that Wτ = f with τ := Dτ * = (ρ 1 τ * 1 , . . . , ρ m τ * m ) T

  1 the components of the ith line of A y are equal to the upper bounds A ij of the corresponding interval components of the ith line of [A]. The 2 n matrices A y are called vertex matrices since, as the interval matrix [A] can be thought of as a box embedded in R nm , the A y corresponds to some (but not all) of the vertices of this box. For instance, with y = (1, -1) T ∈ Y 2 , the vertex matrix W y of the interval matrix [W] defined in (12) is equal to

	-2.986 0.344 -0.715 -0.0239 0.134 3.0	.

TABLE II EXECUTION

 II TIME FOR VARIOUS DISCRETIZATIONS OF W (FOR l = 0.2 AND s = 0.4) WHERE p i DENOTES THE NUMBER OF POINTS IN THE DISCRETIZATION OF EACH AXIS OF W AND p THE TOTAL NUMBER OF POINTS (POSES) IN THE DISCRETIZATION GRID, p = p 5 i .

		p i = 4	p i = 6	p i = 8	p i = 10
		p = 1024	p = 7776	p = 32768	p = 100 000
	Computation
	time	11 s	84 s	352 s	1077 s
	A 8	¨¨B L in A 6	r r A 8 r	A 6

This work was supported in part by the French National Research Agency (ANR) under grant 2009-SEGI-018-01 and 2009-SEGI-018-02 and in part by the Région Languedoc-Roussillon under grant 115217. Marc Gouttefarde is with the Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier (LIRMM)