Stéphane Caro

Damien Chablat

Alexandre Goldsztejn

Daisuke Ishii

Christophe Jermann

A Branch and Prune Algorithm for the Computation of Generalized Aspects of Parallel Robots

Keywords: Numerical constraints, parallel robots, singularities, generalized aspects

établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Mechanical manipulators, commonly called robots, are widely used in the industry to automatize various tasks. They are mechanical assemblies of rigid links connected by mobile joints. Some joints are actuated and they allow commanding the robot operating link, called its end-effector (or platform). One key characteristic of a robot is its reachable workspace, informally defined as the set of poses its end-effector can reach. Indeed, its size defines the scope of operational trajectories the robot can perform. The workspace can be computed from the set of possible command inputs using the kinematic model of the robot, a system of equations relating the commands and the pose coordinates. The size of this system is often referred to as the degrees of freedom (DOF) of the robot.

Robots comply with either a serial or a parallel (or possibly a hybrid) assembly, whether its links are connected in series or in parallel. Parallel robots [START_REF] Kong | Type Synthesis of Parallel Mechanisms[END_REF][START_REF] Merlet | Parallel robots[END_REF] present several advantages with respect to serial ones: They are naturally stiffer, leading to better accuracy with larger loads, and allow high speed motions. These advantages are contrasted by a more complicated design that yields difficulties for the computation and the analysis of their workspace. First, one pose of the robot's end-effector may be reached by several actuated joint commands (which correspond to different working modes), and conversely one input command may lead to several poses of its end-effector (which correspond to different assembly modes). Second, parallel robots generally have parallel singularities [START_REF] Amine | Singularity conditions of 3T1R parallel manipulators with identical limb structures[END_REF], i.e., specific configurations where they become uncontrollable and can even be damaged.

One central issue in designing parallel robots is to compute its nonsingular workspace, together with the corresponding commands, so that the robot can be safely operated. This amounts to computing the connected components of the set of nonsingular configurations, called generalized aspect in [START_REF] Chablat | Working Modes and Aspects in Fully Parallel Manipulators[END_REF]. This computation must be certified in terms of non-singularity and connectivity in order to guarantee safe operations. Few frameworks provide such certifications, among which algebraic computations and interval analysis. Algebraic methods are in general too expensive and apply only for polynomial systems. Still, the cylindrical algebraic decomposition was used in [START_REF] Chablat | Uniqueness domains and non singular assembly mode changing trajectories[END_REF] with a connectivity analysis limited to robots with 2 DOFs. Though generalized aspects are mathematical objects that cannot, in general, be computed exactly using numerical methods, interval analysis allows the rigorous computation of some approximation. It was used in [START_REF] Merlet | A formal-numerical approach for robust in-workspace singularity detection[END_REF] for robots having a single solution to their inverse kinematic problem; Though limited, this method can still tackle important classes of robots like the Stewart platform. A quad-tree with certification of nonsingularity was built in [START_REF] Chablat | Joint space and workspace analysis of a two-dof closed-chain manipulator[END_REF] for some planar robots with 2 DOFs; This method can be extended to higher dimensional robots, but it requires the a priori separation of working modes by adhoc inequalities, and is not certified with respect to connectivity. Finally, the two works [START_REF] Jaulin | Path planning using intervals and graphs[END_REF][START_REF] Delanoue | Guaranteeing the Homotopy Type of a Set Defined by Non-Linear Inequalities[END_REF] propose algorithms based on interval analysis to analyze the connectivity of set defined by inequalities constraints, but cannot be extended to equality constraints. In particular, the developments presented in the present paper somehow extend the interval-based path planning method proposed in [START_REF] Jaulin | Path planning using intervals and graphs[END_REF] for sets defined by inequality constraints only, to manifolds defined by equality, disequality and inequality constraints.

In this paper we propose a branch and prune algorithm incorporating the certification of the solutions and of their connectivity. This allows a fully automated and certified computation of what we call connected sets of nonsingular configurations (CSNCs), i.e., certified approximations of generalized aspects, from the model of arbitrary parallel robots, including robots with multiple solutions to their direct and inverse kinematic problems, without requiring any a priori study to separate their working modes. Though the proposed method does not allow counting the number of CSNCs rigorously, it constructs inner approximations of the nonsingular workspace that allow commanding parallel robots safely. Although less important in practice, a more accurate and costly connectivity analysis is also proposed, which enables separating non connected CSNCs, hence providing a lower-bound on the exact number of generalized aspects. The algorithm is applicable to robots with an arbitrary number of DOF, although the complexity of the computations currently restricts its application to robots with three DOFs. It is also very flexible as it can naturally take into account additional constraints such as, e.g., arm collisions, obstacle avoidance or joint limits. It is thus the first method able to handle such a large class of robots for the problem of computing connected sets of nonsingular configurations. Its main limitation is its performances, due to the combinatorial explosion of the number of computed boxes with the dimension of the problem and the prescribed computational precision. As a consequence, we have applied it to planar robots only at the moment.

A motivating example is presented in Section 2 followed by some preliminaries about numerical constraint programming and robotics in Section 3. The proposed algorithm for certified singularity free connected components computation is presented in Section 4. Finally, experiments on planar robots with 2 and 3 degrees of freedom are presented in Section 5.

Notations

Boldface letters denote vectors. Thus f (x) = 0 denotes a system of equations f on a vector of variables x: f 1 (x 1 , . . . , x n ) = 0, . . . , f k (x 1 , . . . , x n ) = 0. The Jacobian matrix of f (x) with respect to the subset x ′ of the variables x is denoted F x ′ (x). Interval variables are denoted using bracketed symbols, e.g.,

[x] = [x, x] := {x ∈ R | x ≤ x ≤ x}. Hence, [x] is an interval vector (box) and [A] = ([a ij ]
) is an interval matrix. IR denotes the set of intervals and IR n the set of n-dimensional boxes. For an interval [x], we denote wid[x] := xx its width, int[x] := {x ∈ R | x < x < x} its interior, and mid[x] := (x + x)/2 its midpoint. These notations are extended to interval vectors.

Motivating Example

Description. Consider the simple PRRP2 planar robot depicted in Figure 1 (left), which involves two prismatic joints (gray rectangles) sliding along two perpendicular directions. These prismatic joints are connected through three rigid bars (black lines) linked by two revolute joints (circles) that allow free rotations between the rigid bars. The lengths of the prismatic joints are respectively denoted by x and q, the end-effector pose x being along the horizontal direction and the command q corresponding to the height along the vertical direction. Figure 1 (left) shows one generic configuration of the robot. Note that there is another symmetric (negative) pose x associated to the same command q, which is typical of parallel robots. From this configuration, every (vertical) change in q induces a unique corresponding (horizontal) change in x, hence this configuration is nonsingular. Figure 1 (right) shows two singular configurations. In the plain green pose (where the robot's main rigid bar is horizontal), increasing or decreasing the command q both entails a decrease of x. In the dashed red pose (where the robot's main rigid bar is vertical), increasing or decreasing the command q entails a vertical motion of the end-effector which is impossible due to the robot architecture, hence a potential damage to the robot. The green configuration amounts to a serial singularity, which restricts the robot mobility without damaging it; the red configuration is a parallel singularity, which may damage the robot.

Kinematic model. The coordinates of the revolute joints are respectively (a, q) and (x, b), where a and b are architecture parameters corresponding to the lengths of the two horizontal and vertical small rigid bars. Then the main oblique rigid bar enforces the distance between these two points to be equal to its length l, a third architecture parameter. Hence, the kinematic model of this robot is defined as follows:

(x -a) 2 + (q -b) 2 = l 2 .
(

) 1
The solution set of this model, the circle of center (a, b) and radius l, is depicted in Figure 2 (left). The direct kinematic problem consists in computing x knowing q, leading to two solutions a ± l

2 -(q -b) 2 if q ∈ [b -l, b + l], no solution otherwise.
Similarly, the inverse kinematic problem consists in computing q knowing x, leading to two solutions b± l 2 -(xa) 2 provided that x ∈ [a-l, a+l], no solution otherwise. It is noteworthy that this simple robot is representative of the general case since parallel robots can have several solutions to both their direct and inverse kinematic problems.

It is also typical regarding its singularities: It has two serial singularities where the solution set has a vertical tangent (leftmost and rightmost green points in left hand side graphic of Figure 2), and two parallel singularities where the solution set has a horizontal tangent (topmost and bottommost red points in the left hand side graphic of Figure 2). These four singularities split the solution set into four singularity free connected components (quarters of circle), i.e., this robot has four generalized aspects. We can determine the nonsingular workspace of the robot by projecting each aspect onto the x component (the thick lines above and under the paving in Figure 2 (right)). Certified approximation of Generalized Aspects. This paper uses numerical constraint programming in order to compute, with full certification, subsets of the different aspects, called connected sets of nonsingular configurations (CSNC) in the following. The standard branch and prune algorithm is adapted in such a way that solving the robot kinematic model together with non-singularity constraints leads to the enclosure depicted in the right hand side graphic of Figure 2. Each solution box is certifiably crossed by a single aspect which covers the whole box projection on the x subspace, and each pair of neighbor solution boxes are certified to share a common solution. Therefore, the connected components A 1 , A 2 , A 3 , A 4 of the computed boxes shown in the right hand side graphic of Figure 2 allow separating the four aspects, and provide, by projection, inner approximations of the nonsingular workspace of this robot.

a b l x q x q A 2 A 4 A 3 A 1

Preliminaries

Numerical Constraint Programming

Numerical constraint solving inherits principles and methods from discrete constraint solving [START_REF] Montanari | Networks of constraints: Fundamentals properties and applications to picture processing[END_REF] and interval analysis [START_REF] Moore | Interval Analysis[END_REF]. Indeed, as their variable domains are continuous subsets of R, it is impossible to enumerate the possible assignments and numeric constraint solvers thus resorts to interval computations. As a result, we use a so-called interval extension [f ] :

IR n → IR of each function f : R n → R involved in a constraint, such that ∀[a] ∈ IR n , ∀a ∈ [a], f (a) ∈ [f ]([a]).

Numerical Constraint Satisfaction Problems

A numerical constraint satisfaction problem (NCSP) is defined as a triple v, [v], c that consists of

• a vector of variables v = (v 1 , . . . , v n ), • an initial domain, in the form of a box [v] = ([v 1 ], . . . , [v n ]) ∈ IR n , and • a constraint c(v) := (f (v) = 0 ∧ g(v) ≥ 0), f : R n → R e and g : R n → R i ,
i.e., a conjunction of e equations and i inequalities.

A solution of a NCSP is an assignment of its variables v ∈ [v] that satisfies its constraints. The solution set Σ of an NCSP is the region within its initial domain that satisfies its constraints, i.e., Σ(

[v]) := {v ∈ [v] | c(v)}.

The Branch and Prune Algorithm

The branch and prune algorithm [START_REF] Van Hentenryck | Solving polynomial systems using a branch and prune approach[END_REF] is the standard complete solving method for NCSPs. It takes a problem as an input and outputs two sets of boxes, called respectively the undecided boxes (stored inside U ) and solution boxes (stored inside S). It interleaves a refutation phase, called prune, that eliminates inconsistent assignments within a box, and an exploration phase, called branch, that divides a box into several subboxes to be searched recursively, until a prescribed precision ǫ is reached. Algorithm 1 shows a generic description of this scheme. It involves four subroutines: Extract (extraction of the next box to be processed), Prune c (reduction of the domains based on refutation of assignments that cannot satisfy a subset of constraint c), Prove c (certification that a box contains some solutions of the constraint c, the specific semantic being problem dependent), and Branch (division of the processed box into sub-boxes to be further processed). Each of them has to be instantiated depending on the problem to be solved. The procedure Prune c obviously depends on the type of constraint in the problem, as well as on other characteristics of the problem. The procedures Extract and Branch allow defining the search strategy (e.g., breadth-first, depth-first, etc.), which may be tuned differently with respect to the problem. The procedure Prove c actually defines the aim of the branch and prune. A box for which Prove c succeeds is called a solution box: Being a solution box can take different meaning depending on the considered problem and the question asked. For instance, if the question is to find the real solutions of a well-constrained system of equations, then it will generally implement a solution existence (and often uniqueness) theorem, e.g., Miranda, Brouwer or interval Newton [START_REF] Neumaier | Interval Methods for Systems of Equations[END_REF], that guarantees that the solution box contains a (unique) real solution; on the other hand, if the question is to compute the solution set of a conjunction of inequality constraints, then it will usually implement a universal solution test, which guarantees that every real assignment in the solution box is a solution of the NCSP.

Parallel Robots, Singularities and Generalized Aspects

As illustrated in Section 2, the kinematic model of a parallel robot can be expressed as a system of equations relating its end-effector pose x and its commands q: f (x, q) = 0.

(

A solution (x, q) is called a configuration, and the solution set Σ is called the configuration manifold and lies within the configuration space (also called the posecommand product space). The subspace restricted to the pose parameters x (resp. command parameters q) is known as the workspace (resp. joint-space). The projection Σ x (resp. Σ q ) of the solution set Σ is called the robot reachable workspace (resp. reachable joint-space). In this paper, we restrict to the most typical architectures which satisfy dim x = dim q = dim f = n, i.e., neither over-nor under-actuated manipulators. Then, by the implicit function theorem, this system of equations defines a local bijection between x and q provided the Jacobian matrices F x (x, q) and F q (x, q) are Algorithm 1 Branch and prune

Input: NCSP v, [v], c , precision ǫ > 0 Output: pair of sets of boxes (U , S) 1: L ← {[v]}, S ← ∅ and U ← ∅ 2: while L = ∅ do 3: [v] ← Extract(L) 4: [v] ← Prune c ([v]) 5: if [v] = ∅ then 6: if Prove c ([v]) then 7: S ← S ∪ {[v]} 8: else if wid[v] > ǫ then 9: L ← L ∪ Branch([v]) 10: else 11: U ← U ∪ {[v]} 12:
end if

13:
end if 14: end while 15: return (U , S) non-singular. The configurations (x, q) that do not satisfy these regularity conditions are called singularities, respectively parallel or serial whether F x (x, q) or F q (x, q) is singular. These algebraic singularity characterizations correspond to the horizontal and vertical tangents of the kinematic manifold described in Section 2.

A key issue in robotics is to control a robot while avoiding singularities, in particular because reaching a parallel singularity can dramatically damage a robot. This leads to the definition of generalized aspects [START_REF] Chablat | Working Modes and Aspects in Fully Parallel Manipulators[END_REF] as maximal sets of nonsingular configurations (x, q) that can all be connected within Σ without crossing any singularity. More formally, the set of nonsingular configurations of the robot is

Σ * := {(x, q) ∈ R n × R n | f (x, q) = 0, det F x (x, q) = 0, det F q (x, q) = 0}. (3)
This corresponds, e.g., to the four quarters of circle in the left hand side graphic of Figure 2, where the four singularities (green and red points) are removed. As illustrated by this diagram, Σ * is generally made of several connected components 3 . Formally, the generalized aspects of the robots are defined to be the connected components of (3).

For a given generalized aspect A, its projection A x is a maximal singularity-free region in the robot reachable workspace. Knowing these regions allows roboticists to safely plan robot motions: Any two poses in A x are connected by at least one singularity-free path. In addition, the study of aspects provides important information about robot characteristics, e.g., if (x, q) and (x, q ′ ) exist in an aspect A and q = q ′ , i.e., two different commands yield the same pose, then the robot is said to be cuspidal [START_REF] Wenger | Cuspidal and noncuspidal robot manipulators[END_REF]. Cuspidal robots can change assembly mode without crossing singularities, yielding an extra flexibility in their usage. Finally, the computation of aspects allows roboticists to make informed choices when designing a robot for a given task.

Description of the Method

The proposed method for the generalized aspect computation relies on solving the following NCSP whose solutions are the nonsingular configurations of the robot:

(x, q) , ([x], [q]) , f (x, q) = 0 ∧ det F x (x, q) = 0 ∧ det F q (x, q) = 0 . (4) Let Σ([x],
[q]) be the solution set of this NCSP. Our method computes a set of boxes partly covering this solution set. This set of boxes is partitioned into subsets that represent fully certified approximations of the aspects of the considered robot, in terms of both solution existence and connectedness within the solution set. The computed boxes have to satisfy the specific properties stated in Subsection 4.1. The corresponding branch and prune instantiation is described in Subsection 4.2. Finally, the connections between the output boxes have to be certified as described in Subsection 4.3, and the connected component analysis is described in Subsection 4.4.

From the NCSP Model to the Generalized Aspects Computation

We aim at computing a (finite) set of boxes S ⊆ IR n × IR n together with (undirected) links N , i.e. 2-subsets of S, satisfying the following three properties:

(P 1 ) ∀([x], [q]) ∈ S, ∀x ∈ [x], ∃ a unique q ∈ [q], f (x, q) = 0; (P 2 ) ∀([x], [q]) ∈ S, ∀x ∈ [x], ∀q ∈ [q], det F x (x, q) = 0 ∧ det F q (x, q) = 0; (P 3 ) ∀ ([x], [q]), ([x ′ ], [q ′ ]) ∈ N , ∃(x, q) ∈ ([x], [q]) ∩ ([x ′ ], [q ′ ]), f (x, q) = 0. Property (P 1 ) allows defining in each ([x], [q]) ∈ S a function κ ([x],[q]) : [x] → [q]
that associates the unique command q = κ ([x],[q]) (x) with a given position x (i.e., the solution of the inverse kinematic problem locally defined inside ([x], [q])).

Property (P 2 ) proves there is no singularity in the box. Furthermore, it allows applying the Implicit Function Theorem to prove that κ ([x],[q]) is differentiable (and hence continuous) inside [x]. Therefore, for a given box ([x], [q]) ∈ S, the solution set restricted to this box

Σ([x], [q]) = x, κ ([x],[q]) (x) : x ∈ [x] (5)
is proved to be connected and singularity free, and is thus a subset of one generalized aspect. These two properties entail in particular that

Σ * ∩ ([x], [q]
) is a connected manifold, hence a subset of a single aspect, and that [x] is included inside the reachable workspace. They are satisfied by the motivating example output shown in Figure 2 (right). Remark that given a box ([x], [q]) ∈ S and a position x ∈ [x], the corresponding command κ ([x],[q]) (x) is easily computed using Newton iterations applied to the system f (x, •) = 0 with initial iterate q ∈ [q] (e.g., q = mid[q]).

Property (P 3 ) basically entails that Σ([x], [q]) and Σ([x ′ ], [q ′ ]) are connected, and are thus subsets of the same aspect. Finally, assuming S k ⊆ S to be a connected component of the undirected graph (S, N ), the solution set

([x],[q])∈S k Σ([x], [q]) (6)
is fully certified to belong to one single generalized aspect. Hence the final output of the process will be several sets of boxes S k , each of them being certified to enclose one connected set of nonsingular configurations (CSNC). As mentioned previously, certified approximations of CSNCs are of central importance for practical robot design and usage purposes.

Instantiaton of the Branch and Prune Algorithm

The main specificity of the proposed branch and prune algorithm lies within the solution test used in the Prove c function, which must ensure the desired properties. The pruning and branching steps use standard operators and can be tuned appropriately depending on the considered robot. Details are provided below.

Solution Test

The Prove c function of Algorithm 1 has to return true only when properties (P 1 ) and (P 2 ) are verified. The former is related to proving the existence of solution and is performed using a parametric Newton operator as described in the following paragraph. The latter requires checking the regularity of some interval matrices as described in the next paragraph.

Existence proof. The standard way to prove that a box ([x], [q]) satisfies Property (P 1 ) is to use a parametric interval Newton existence test [START_REF] Goldsztejn | A Branch and Prune Algorithm for the Approximation of Non-Linear AE-Solution Sets[END_REF][START_REF] Goldsztejn | Sensitivity analysis using a fixed point interval iteration[END_REF][START_REF] Goldsztejn | Inner approximation of the range of vector-valued functions[END_REF]. Using the Hansen-Sengupta [START_REF] Neumaier | Interval Methods for Systems of Equations[END_REF] version of the interval Newton, the following sequence is computed

[q 0 ] := [q], . . . , [q k+1 ] := [H]([q k ]) ∩ [q k ] (7)
where [H] is the Hansen-Sengupta operator applied to the system f ([x], q) = 0, which depends only on the variables q and hence is a square system of equations with interval parameters. As soon as

∅ = [q k+1 ] ⊆ int[q k ] is verified, the interval Newton operators properties entails ∀x ∈ [x], ∃q ∈ [q], f (x, q) = 0, (8)
hence the box ([x], [q k+1 ]) is proved to satisfy Property (P 1 ). However, because Algorithm 1 has to bisect the domain [q] for insuring convergence by separating the different commands associated to the same pose, 4 this test fails in practice in most situations.

This issue was overcome in [START_REF] Goldsztejn | Inner approximation of the range of vector-valued functions[END_REF], in the restricted context of constraints of the form x = f (q), by computing [q k+1 ] := [H]([q k ]) in [START_REF] Merlet | A formal-numerical approach for robust in-workspace singularity detection[END_REF], i.e., removing the intersection with [q k ], in order to allow inflating and shifting [q k-1 ] if necessary. 5 As a result, the Hansen-Sengupta operator acts as a rigorous local search routine allowing the sequence to converge towards the aimed solution set. An inflation factor τ has also to be applied before the Hansen-Sengupta operator so as to ease the strict inclusion test after each iteration. Hence, the computation of [q k+1 ] is as follows:

[q k ] := mid[q k ] + τ ([q k ] -mid[q k ]) and [q k+1 ] := [H]([q k ]). (9)
Then the condition ∅ = [q k+1 ] ⊆ int[q k ] also implies Property (P 1 ) and is likely to succeed as soon as

([x], [q]
) is small enough and close enough to some nonsingular solution, which eventually happens thanks to the bisection process. A typical value for the inflation factor is τ = 1.01, which would have to be more accurately tuned for badly conditioned problems, but it is not the case of usual robots.

Regularity test. In order to satisfy the regularity constraints in Property (P 2 ), the interval evaluation of each Jacobian F x and F q over the box ([x], [q]) has to be regular.

Testing the regularity of interval matrices is NP-hard, so sufficient conditions are usually used instead. Here, we use the strong regularity of a square interval matrix [A], which consists in checking that C[A] is strongly diagonally dominant, where C is usually chosen as an approximate inverse of the midpoint of [A] (see [START_REF] Neumaier | Interval Methods for Systems of Equations[END_REF]).

Pruning

The considered constraints are of two types: A system of n equalities, and two disequalities. Since the latter generally does not allows any pruning in the context of numerical CSPs, only the former is considered for pruning. In our context, the Prune c function is implemented as a standard AC3-like fixed-point propagation of contracting operators that enforces local consistencies, like the Hull [START_REF] Benhamou | Revising hull and box consistency[END_REF][START_REF] Lhomme | Consistency Techniques for Numeric CSPs[END_REF] or the Box consistencies [START_REF] Benhamou | Revising hull and box consistency[END_REF][START_REF] Goldsztejn | Box Consistency through Adaptive Shaving[END_REF], which allows an inexpensive refutation non-solution. Moreover, a stronger consistency can be achieved using some interval-Newton based operator. Those operators readily apply to square systems of equations, but have to be adapted to under constrained systems of equations. This is detailed in Subsection 4.2.1, since those operators also allow proving the existence of solutions.

Search Strategy

The standard search strategy for NCSPs applies appropriately in our context: We use a deep first search strategy within the Extract function, which is adequate and avoids the risk of filling up the memory (unlike a breadth-first search or largest-first search approach). The Branch function typically selects a variable in a round-robin manner (i.e., all domains are selected cyclically) and splits the corresponding interval at its midpoint (i.e., a domain is split into two halves).

Computing and Certifying Links

The computation of N , i.e., the links that satisfy Property (P 3 ), is done in two steps:

1. Maintain the neighborhood graph (R, M), where R = L ∪ S ∪ U is the set of all boxes produced by the algorithm, defined as the graph between the boxes in R which share at least a common point; 2. Compute the certified neighborhood graph (S, N ), where N ⊆ M ∩ 2 S is the set of links between certified boxes that satisfy Property (P 3 );

N is generally a strict subset of M∩2 S : Indeed, two certified boxes with nonempty intersection may still contain different components of Σ * . Note that, (R, M) and (S, N ) somehow play similar roles as G ± in [START_REF] Jaulin | Path planning using intervals and graphs[END_REF].

Maintaining the Neighborhood Graph

Two boxes ([x], [q]) and ([x ′ ], [q ′ ]) are neighbors if and only if they share at least one common point, i.e., ([x], [q]) ∩ ([x ′ ], [q ′ ]) = ∅. The neighborhood links M are maintained during the branch and prune computation: After the current box has been pruned (line 4 of Algorithm 1), its neighbors are updated accordingly (it may have lost some neighbors); also, the boxes produced when splitting the current box (line 9 of Algorithm 1) inherit from (some of) the neighbors of the current box, and are neighbors to one another. One delicate point in managing neighborhood comes from the fact that some pose or command parameters are often angles whose domains are restricted to a single period, e.g., [-π, π]; the periodicity of these parameters has to be taken into account: Boxes are neighbors when they share a common point modulo 2π on their periodic dimensions.

Certifying Connectivity Between Neighbors

The links M ∩ 2 S between certified boxes have to be checked to satisfy (P 3 ): It may happen that two neighbor boxes share no common point satisfying the kinematic relation f = 0, e.g., if they each cover a portion of two disjoint, but close, aspects. Asserting neighborhood Property (P 3 ) requires again a certification procedure: For any pair of neighbor certified boxes

([x], [q]), ([x ′ ], [q ′ ]) ∈ M ∩ 2 S , we verify ∃q ∈ ([q]∩[q ′ ]), f (mid([x]∩[x ′ ]), q) = 0, (10)
which implies Σ([x], [q]) ∩ Σ([x ′ ], [q ′ ]) = ∅.
Since the union of two connected sets that have a nonempty intersection is also connected, this proves that Σ([x], [q]) and Σ([x ′ ], [q ′ ]) belong to the same aspect. Using the certification procedure described in Section 4.2 allows proving Equation [START_REF] Delanoue | Guaranteeing the Homotopy Type of a Set Defined by Non-Linear Inequalities[END_REF]. Finally, N is defined as the subset of M ∩ 2 S of pairs that satisfy [START_REF] Delanoue | Guaranteeing the Homotopy Type of a Set Defined by Non-Linear Inequalities[END_REF], and obviously satisfy obvious satisfy Property (P 1 ), Property (P 2 ) and Property (P 3 ).

Connected Components Computation

We present two ways to compute connected sets of nonsingular configurations (CSNCs) from the graphs (R, M) and (S, N ).

Simple CSNCs Construction

The first simply consists in computing the connected components (S i , N i ) of the graph (S, N ), using a standard algorithm for the graph connected component computation (e.g., [START_REF] Hopcroft | Algorithm 447: efficient algorithms for graph manipulation[END_REF]). This leads to a partition of S into S i , each S i covering a single aspect of the considered robot. However, there is no certified information about the disconnectedness of the different components: The major portion of a large aspect should be covered with a single CSNC, but the instability of the proving process close to singular regions implies that many small "spurious" CSNCs should appear at the boundaries. Together with the fact very small aspects may not be covered by certified boxes, this is the reason why the number of computed CSNCs is not related to the exact number of aspects of a robot.

For practical considerations, the spurious CSNCs can be eliminated using a measure of their size: All computed CSNCs are ordered by decreasing number of constituting boxes; The largest ratio, in number of constituting boxes, between two consecutive CSNCs in this order is computed, and used as a separation between relevant and spurious components. Though heuristic, we show in Section 5 that this filtering process allows retrieving the most significant CSNCs which in fact correspond to the exact aspects of the robots for which they are known.

CSNCs Construction and Separation

The second approach is more complex, but provides more information in term of connectedness: The main computed CSNCs can be proved to be actually separated either because they have different determinant signs, or because they are disconnected within (R, M). However, it can happen that some generalized aspects may not be separable numerically using these conditions, as illustrated by the following example.

Example. Consider the manifold Σ

* := {x ∈ R 3 : x 2 1 + x 2 2 + x 2 3 = 1, x 1 x 2 = 0}.
It is made of 4 connected components, as illustrated on the left hand side graphic of Fig-ure 3. However, these four components, although connected, are infinitely close to each other, making their separation impossible using some box classification with respect to the sign of x 1 x 2 . Note that this situation is not generic: By slightly perturbing the separating equation to, e.g., Σ * := {x ∈ R 3 : x 2 1 + x 2 2 + x 2 3 = 1, x 1 x 2 = 0.01}, which is depicted on the right hand side of Figure 3, we obtain three connected components which can be separated using the sign of x 1 x 2 -0.01.

The undecidable status illustrated by the previous example is actually generic for some robots: As soon as one of the determinants det F x (x, q) or det F q (x, q) can be formally factored (e.g., when one of these Jacobians are diagonal, in which case the its determinant is the product of its diagonal entries), some aspects may turn out to be non separable using only the signs of these determinants. In order to overcome this difficulty, exploiting the structure of the determinants is mandatory: When possible, we factor the product det F x (x, q) det F q (x, q) to d 1 (x, q) • • • d p (x, q) and, instead of recording the sign of both det F x ([x], [q]) and det F q ([x], [q]) for each box, we record the sign of each d i ([x], [q]).

For each possible s = (s 1 , . . . , s p ) ∈ {-1, 1} p , we define (R s , M s ) ⊆ (R, M) as the subgraphs of (R, M) whose boxes satisfy sup s i d i ([x], [q]) ≥ 0, i.e., R s contains boxes whose interval evaluations d i ([x], [q]) have signs compatible with s. Then, we compute the connected components (R s i , M s i ), i ∈ {1, . . . , I s }, of each (R s , M s ). Finally, we compute the connected components of (R s i ∩ S, M s i ∩ N ), the subgraph of (R s i , M s i ) containing only certified boxes and links, and denote them (S s ij , N s ij ), j ∈ {1, . . . , J s,i } with J s,i ≥ 0 (J s,i could be equal to zero if (R s i , M s i ) contains no certified box or link).

Obviously, boxes in two different (R s i , M s i ) and (R s ′ i ′ , M s ′ i ′ ) cannot contain solutions that belong to the same aspect. Therefore,

s∈{-1,1} p card{i ∈ {1, . . . I s } : J s,i > 0} (11)
is a lower bound of the number of aspect. On the other hand, as mentioned in the previous subsection, we expect (S s ij , N s ij ) to contain numerous spurious CSNCs due to the instability of the proving process close to singular regions. The same heuristic filtering can thus be used to isolate the largest CSNCs of practical interest.

Experiments

We present experiments on four planar robots with respectively 2 and 3 degrees of freedom, yielding respectively a configuration manifold of dimension 2 or 3 embedded in a configuration space of dimension 4 or 6. Although these dimensions seem somehow low, some of them represent real challenges for methods that certify admissibility and connectivity.

Implementation

We have implemented the proposed method described in Section 4 using the Realpaver library [START_REF] Granvilliers | Algorithm 852: Realpaver: an interval solver using constraint satisfaction techniques[END_REF] in C++, specializing the classes for the different routines in the branch and prune algorithm. Given a NCSP that models a robot and a prescribed precision ǫ, the implementation outputs certified boxes grouped by certified connected components as explained in Section 4. Hence we can count not only the number of output boxes but also the number of certified connected set of nonsingular configurations (CSNCs) that can be extracted from them. The experiments were run using a 3.4GHz Intel Xeon processor with 16GB of RAM. Robot RPRPR (resp. RRRRR) is represented in Figure 4(a) (resp. Figure 4(b)). It has two arms, each connecting an anchor point (A, B) to its end-effector (P ), each composed of a revolute joint, a prismatic (resp. revolute) joint and again a revolute joint in sequence. The end-effector P lies at the shared extremal revolute joint and is described as a 2D point (x 1 , x 2 ) ∈ [-20, 20] 2 . The prismatic (resp. initial revolute) joint in each arm is actuated, allowing to vary the arms lengths (resp. angles). The arm lengths (resp. angles) are considered to be the command (q 1 , q 2 ) ∈ [2, 6]× [START_REF] Amine | Singularity conditions of 3T1R parallel manipulators with identical limb structures[END_REF][START_REF] Jaulin | Path planning using intervals and graphs[END_REF] (resp. [-π, π] 2 ) of the robot. Using the architecture parameters defined in [START_REF] Chablat | Domaines d'unicité et parcourabilité pour les manipulateurs pleinement parallèles[END_REF] (resp. [START_REF] Chablat | Working Modes and Aspects in Fully Parallel Manipulators[END_REF]), their kinematic equations are respectively

Robot Models

x 2 1 + x 2 2 -q 2 1 = 0, (x 1 -9) 2 + x 2 2 -q 2 2
= 0, and (x 1 -8 cos q 1 ) 2 + (x 2 -8 sin q 1 ) 2 -25 = 0, (x 1 -9 -5 cos q 2 ) 2 + (x 2 -5 sin q 2 ) 2 -64 = 0. Robot 3-RPR (resp. 3-RRR) is represented in Figure 4(c) (resp. Figure 4(d)). It has three arms, each connecting an anchor point (A 1 , A 2 , A 3 ) to its end-effector (P ), each composed of a revolute joint, a prismatic (resp. revolute) joint and again a revolute joint in sequence. The end-effector is a triangular platform whose vertices are attached to the extremal revolute joints of the arms. The pose parameters (x 1 , x 2 , x 3 ) represent the coordinates (x 1 , x 2 ) ∈ [-50, 50] 2 of one vertex of the platform, and the angle x 3 ∈ [-π, π] between its basis and the horizontal axis. The prismatic (resp. initial revolute) joint in each arm is actuated, allowing to vary the arm lengths (resp. angles). The arm lengths (resp. angles) are considered to be the command (q 1 , q 2 , q 3 ) ∈ [10, 32] 3 (resp [-π, π] 3 ) of the robot. Using the architecture parameters defined in [START_REF] Coste | A simple proof that generic 3-RPR manipulators have two aspects[END_REF] (resp. [START_REF] Chablat | Domaines d'unicité et parcourabilité pour les manipulateurs pleinement parallèles[END_REF]), their kinematic equations are:

x 2 1 + x 2 2 -q 2 1 = 0, (x 1 + 17 cos x 3 -15.9) 2 + (x 2 + 17 sin x 3 ) 2 -q 2 2 = 0, (x 1 + 20.8 cos(x 3 + 0.8822)) 2 + (x 2 + 20.8 sin(x 3 + 0.8822) -10) 2 -q 2 3 = 0,
and, respectively (x 1 -10 -10 cos q 1 ) 2 + (x 2 -10 -10 sin q 1 ) 2 -100 = 0, (x 1 + 10 cos x 3 -10 -10 cos q 2 ) 2 + (x 2 + 10 sin x 3 -10 -10 sin q 2 ) 2 -100 = 0, (x 1 + 10 √ 2 cos(x 3 + π/4) -10 cos q 3 ) 2 + (x 2 + 10 √ 2 sin(x 3 + π/4) -10 -10 sin q 3 ) 2 -100 = 0.

Due to the computational complexity of our method, we have added the extra constraint x 3 = 0 to the latter model of robot 3-RRR, i.e., fixing the orientation of its platform. This constraint virtually reduces the dimension of the problem to 5 instead of 6, making it tractable in reasonable time with our method. Results below integrate this additional constraint and we denote this modified robot 3-RRR* in the following.

History and Applications of the Four Planar Parallel Robots under Study

We can find many studies on the four planar parallel robots under study and some practical applications in the literature. The RPRPR robot, also called bipod robot, is used in the so-called hexapod machine tools, which are the most widespread [START_REF] Zou | Kinematic analysis of a biglide parallel grinder[END_REF], and in the famous Gough-Stewart platforms, commonly met in flight-simulators [START_REF] Du Plessis | Design and optimum operation of a reconfigurable planar gough-stewart machining platform[END_REF]. The bipod robot is also used in the design of the Micromat Hexa industrial machine developed at the IWU in Chemnitz and in the design of the CMW300 industrial robot developed by the Compagnie Mécanique des Vosges in France [START_REF] Wenger | Comparative study of serial and parallel mechanism topologies for machine tool[END_REF].

The RRRRR robot, usually called five-bar mechanism, has often been used in research papers as an illustrative example due to its simplicity and interesting kinematic properties similar to those of spatial robots, namely : (i) several working and assembly modes [START_REF] Chablat | Working Modes and Aspects in Fully Parallel Manipulators[END_REF] ; (ii) error analysis and assembly conditions [START_REF] Binaud | Kinematic sensitivity of robotic manipulators to joint clearances[END_REF][START_REF] Wu | Error modeling and experimental validation of a planar 3-PPR parallel manipulator with joint clearances[END_REF]; (iii) generalized aspects [START_REF] Caro | Non-singular assembly mode changing trajectories of a 6-DOF parallel robot[END_REF]; (iv) trajectory planning [START_REF] Barnard | Trajectory generation for high speed pick and place robots[END_REF]. There exist some prototypes of the RRRRR robot such as the Dexterous Twin-Arm Robot (DexTAR) developed by Prof. Bonev and his team [START_REF] Joubair | Kinematic calibration of a five-bar planar parallel robot using all working modes[END_REF].

A reference book on kinematics, static analysis and stiffness of 3-DOF planar parallel robots composed of revolute and/or prismatic joints was published by Duffy [START_REF] Duffy | Statics and Kinematics with Applications to Robotics[END_REF]. There have been various studies of these robots. 3-RPR planar parallel robots have been extensively studied [START_REF] Merlet | Parallel robots[END_REF]: synthesis, kinematic and singularity analysis, workspace analysis. 3-RRR planar parallel robots have also been studied in [START_REF] Hunt | Structural kinematics of in parallel actuated robot arms[END_REF][START_REF] Gosselin | Kinematic analysis optimization and programming of parallel robotic manipulators[END_REF][START_REF] Husty | On the workspace of planar three-legged platforms[END_REF]. Some prototypes based on the architecture of the 3-RRR planar parallel robot have been developed such as the NaVARo that has eight actuation modes thanks to three transmissions with two clutches and additional parallelogram linkages [START_REF] Rakotomanga | Performance of a planar parallel mechanism with variable actuation[END_REF].

Computation of CSNCs

Table 1 provides some figures on our computations. Its columns represent the different robots we consider. Line "# aspects" provides the theoretically established number of aspects of each robot provided in [START_REF] Chablat | Domaines d'unicité et parcourabilité pour les manipulateurs pleinement parallèles[END_REF][START_REF] Chablat | Working Modes and Aspects in Fully Parallel Manipulators[END_REF][START_REF] Coste | A simple proof that generic 3-RPR manipulators have two aspects[END_REF] (this value is unknown for the 3-RRR* robot). Line "precision" gives the prescribed precision ǫ used in the computation. Lines "# boxes" and "# CSNCs" give respectively the number of boxes and the number of connected sets of nonsingular configurations returned by our method. Line "time" gives the overall computational time in seconds of the method, including the connected components computation with connectivity certification. Note that, this timing does not contain the time taken for filtering out the spurious CSNCs.

Despite the quite coarse precisions we have used, the number of output boxes can be very large, due to the dimension of the search space we are paving. The number of CSNCs is much smaller, but still does not match the theoretically known number of aspects (except for the PRRP which is very simple), implying numerous disjoint CSNCs do in fact belong to the same aspect. As expained in Section 4.4, this is due to the numerical instability of the kinematic equations of the robots in the vicinity of the aspect boundaries, which are singularities of the robot. Indeed, in these regions, the numerical certification process cannot operate homogeneously, resulting in disconnected subsets of certified boxes, separated either by non-certified boxes or by non-certified links.

These spurious CSNCs have no practical use in robotics because they represent only very small, hence negligible, regions of the reachable workspace, moreover too close to singularities to safely operate within. For practical considerations, we can thus filter them out as explained in Section 4.4.1. Applying this heuristic, practical, post-process, the number of obtained CSNCs, reported at Line "# CSNCs filtered " in Table 1, reaches the theoretically known number of aspects in the cases of the robots we considered. Line "# boxes filtered " in Table 1 shows the total number of boxes after the filtering heuristic. Figure 5 illustrates the number of boxes of the CSNCs retained after filtering (the dashed lines represent the computed heuristic thresholds), as well as the number of boxes of the largest spurious (and filtered) CSNC right after the dashed line. Line "# CSNCs separated " gives the lower bounds of the number of aspects, which are computed by the method described in Section 4.4.2. These results seem to indicate that our assumption is correct for the considered robots, i.e., that the major part of each aspect is indeed covered with a single large CSNC. The retained CSNCs projected onto the x subspace are depicted in Figures 6 and7. 6They graphically correspond to the aspects of the robots for which they are theoretically known (e.g., see [START_REF] Chablat | Domaines d'unicité et parcourabilité pour les manipulateurs pleinement parallèles[END_REF][START_REF] Chablat | Joint space and workspace analysis of a two-dof closed-chain manipulator[END_REF][START_REF] Chablat | Working Modes and Aspects in Fully Parallel Manipulators[END_REF][START_REF] Coste | A simple proof that generic 3-RPR manipulators have two aspects[END_REF]). Note that the red boxes, that enclose the singularity curves, seem to cross the aspects due to the projection onto the workspace, while they of course do not cross in the configuration space where the boxes have been computed and proved to certify Property (P 2 ).

The computation requires quickly growing time and space with respect to the prescribed precision ǫ, since this parameter controls the explosion of the number of spurious components, hence boxes, at the boundaries of the aspects. We thus need to tweak it for an efficient and reliable aspect determination. For the first three robots, the precision ǫ = 0.1 gave precise enough results to compute precisely CSNCs corresponding to the known aspects after filtering out the spurious components. For 3-RPR, we had to use the coarser precision ǫ = 0.3 to avoid getting out of memory. Still, it was sufficient to compute precise CSNCs approximating the two known aspects of this robot. In the computation of 3-RRR*, the threshold between the regular and the spurious components is not as clear as for the other robots, even though we improved the precision up to ǫ = 0.008. Nevertheless, only the largest CSNCs have a practical usage in the context of robotics, hence deciding whether these very small CSNCs are really spurious is not critical. According to our filtering criterion, we selected the 25 largest ones that are depicted in Figure 7.

Handling Additional Constraints

In the process of robot design, various properties should be verified in addition to the aspect identification. In our framework, such properties can be handled by simply adding constraints to the robots models, which is an intrinsic strength of NCSPs based method with respect to other methods, e.g., based on formal computations. In the following, we investigate the impact of three recurrent issues in robotics: Self collisions between different robot links, joint limits, and collision with obstacles inside the workspace. We use the RRRRR robot as an illustrative example.

The considered additional constraints are inequality constraints: More precisely, they can be formulated as conjunctions and/or disjunctions of inequalities. Therefore, they are involved in both pruning and proving, and solution boxes will be proved to fully satisfy these additional constraints in addition to properties (P 1 ), (P 2 ) and (P 3 ) defined in page 8. Note that due to the additional constraints expressions, a trivial contractor is used, which simply uses interval evaluations to check if a box contains no solution.

Arm Collisions

First we show how to avoid collisions between arms of the RRRRR robot. The required additional constraint consists of enforcing no collision of any pair of links. For an arbitrary pair of links (T, U ) and (V, W ), where T , U , V and W are their respective endpoints, their non intersection is mathematically expressed as:

∀λ ∈ [0, 1], ∀µ ∈ [0, 1], λ T + (1 -λ)U = µ V + (1 -µ)W.
One such constraint must be imposed for each pair of links in the robot. Inner and outer tests for such a constraint are easily derived. Link collisions happen in full-dimensional regions of the workspace. Indeed, when two links intersect at a given pose, they also intersect at neighbor poses (except when intersecting at their extremities). Hence, link collisions constraints define colliding regions, which must be removed from the computed CSNCs. Figure 8 illustrates these facts. Figure 8(a) presents one of the CSNCs we have previously obtained for the RRRRR robot (see Figure 7(b)). Figure 8(b) then shows how this component is reduced when considering link collisions, and presents two poses to explain this reduction. Pose P 1 induces no link collision and thus remains within the collision-free CSNC. Pose P 2 previously belonged to the CSNC but does not belong to the collision-free CSNC as it induces a link collision. The two full-dimensional regions corresponding to collision and collision-free configurations have to be separated by a boundary, which corresponds to tangential collisions. They are depicted in blue in contrast with the red boundaries that represent singularities of the robot. Note that like singularities, some of the collision boundaries overlap with the collision-free components due to the projection in the 2D workspace of the paving computed in the 4D configuration space.

Results are depicted in Figure 9. We set the precision to 0.01 for a better visualization of the collision boundaries, although a cruder precision is sufficient to obtain the collision-free CSNCs. As in the previous experiment, we obtain ten CSNCs that are collision free. They correspond to collision-free subregions of the ten CSNCs obtained previously. Note that some of the previously obtained components remain unaffected by the additional constraint, i.e., they were already collision-free. As in Figure 8, blue boxes in each figure represent collision boundaries where the end point of a link comes to touch another link.

Joint Limits

In the second experiment, we compute the CSNCs while considering the joint limits, which are inherent in real mechanisms. Limits of the range of actuated joints are easily enforced by setting their corresponding domains. Instead, we consider joint limits of non-actuated joints. In the RRRRR robot, it consists in limiting the angle between the links (A ′ P ) and (P B ′ ), inside the interval [θ, θ]. This is equivalent to the conjunction of the two following two-sided inequality constraints:

θ ≤ cos -1 u | v u v ≤ θ, θ ≤ sin -1 u ⊥ | v u ⊥ v ≤ θ,
where u = P -A ′ , v = P -B ′ and u ⊥ = (-u 2 , u 1 ), and • | • is the scalar product.

As in the link collisions, this constraint will remove some regions from the computed CSNCs. Figure 8(c) presents the joint-limited CSNCs of the RRRRR robot resulting from the original CSNC depicted in Figure 8(a) when the angle at the endeffector P is limited to [-π/2, π/2]. It also presents two poses: Pose P 1 is consistent with the joint limit and thus remains within the original joint-limited CSNC. Pose P 2 did belong to the original CSNC but it does not belong to the computed joint-limited CSNC since, at this pose, the joint limit is not respected. Blue boxes represent joint limit boundaries where the limited joint angle becomes π/2 or -π/2.

The other joint-limited CSNCs are depicted in Figure 10. We have twelve jointlimited CSNCs where the first and sixth original CSNCs in Figure 7(b) have been split in two by the joint limit constraint.

Collision with Obstacles

The third experiment takes into account the collision of robot links with an obstacle in the workspace. We assume a circular obstacle centered at point C with radius R. For each link (T, U ) of the robot, collision-freeness is described by the constraint dist 2 (C, (T, U )) ≥ R 2 where

dist 2 (C, (T, U )) :=      C -T |C -T if U -T |C -T < 0 C -U |C -U if T -U |C -U < 0 C -T |C -T -U -T |C-T 2 U -T |U -T otherwise.
Again, the obstacle avoidance constraint yields collision regions and collision-free regions within the aspects. Figure 8(d) presents the three collision-free CSNCs of the RRRRR robot resulting from the CSNC depicted in Figure 8(a) when a circular obstacle (in black) located at C = (4.5, 0) with radius R = 1 is to be avoided. It also presents two poses: Pose P 1 induces no collision with the obstacle and thus remains within the collision-free CSNC. Pose P 2 did belong to the original CSNC but it does not belong to the collision-free CSNCs since, at this pose, a link overlaps with the obstacle. Again, blue boxes represent the boundaries between collision-free and collision regions.

The other collision-free CSNCs are depicted in Figure 11. We have twenty six collision-free CSNCs where the first, second, third, sixth, seventh and eighth original CSNCs in Figure 7(b) are split into three, four, four, three, four and four parts respectively.

Conclusion

The computation of aspects, i.e., connected components of nonsingular configurations, is a critical task in the design and analysis of parallel robots. The proposed algorithm uses numerical constraint programming to fully certify this computation. It is worth noting that this is the first algorithm that automatically handles such a large class of kinematic models with fully certifying the configurations existence, non-singularity and connectivity: The only restriction of the algorithm is its computational complexity, which is exponential with respect to the number of degrees of freedom of the robot.

The presented experiments have reported the sharp approximations of aspects for some realistic models: Large connected sets of nonsingular configurations, particularly suitable for path planning, have been computed for well-known planar robots with two and three degrees of freedom, the number of which matches the exact number of aspects. The more challenging 3-RRR planar parallel robot, whose number of aspects is still an open question, remains out of reach because of the complexity of the computation, though we have obtained some promising results for a given orientation of its moving-platform. Tackling this robot, as well as more complex and spatial ones, will certainly require the definition of stronger, dedicated, operators, and probably a change of computing paradigm, e.g., using parallelepipeds [START_REF] Goldsztejn | A new framework for sharp and efficient resolution of NCSP with manifolds of solutions[END_REF] instead of boxes. Finally, although experiments have shown that the proposed method computes approximations of all aspects of well-known robots, it cannot be used for rigorously counting the aspects, a challenge we will address in the future on the basis of this method.

Figure 1 :

 1 Figure 1: The PRRP in a generic pose (left) and in singular poses (right).

Figure 2 :

 2 Figure 2: The PRRP kinematic model solutions set (left) and the computed paving (right).

Figure 3 :

 3 Figure 3: Singular singularity

Figure 4 :

 4 Figure 4: Considered robot architectures.

3 Figure 6 :

 36 Figure 6: Computed 3D workspace of of 3-RPR (after filtering). First figure shows the undecided boxes that cover the surface of the workspace. Second and third figures show the computed CSNCs corresponding to the two aspects.

Figure 7 :

 7 Figure 7: Projections into the 2D workspace of the computed CSNCs (after filtering). Green boxes are certified; red and black boxes are undecided (i.e., do not satisfy Properties (P 1 ) and (P 2 ), respectively).

Figure 8 :

 8 Figure 8: Aspect decomposition of RRRRR with respect to various additional constraints.

Figure 9 :

 9 Figure 9: Computed CSNCs of RRRRR taking into account link collisions.

Figure 10 :

 10 Figure 10: Computed CSNCs of RRRRR with a limited angle.

Figure 11 :

 11 Figure 11: Computed CSNCs of RRRRR with a circular obstacle.

Table 1 :

 1 Experimental results.

		PRRP RPRPR RRRRR	3-RPR	3-RRR*
	# aspects	4	2	10	2	unknown
	precision	0.1	0.1	0.1	0.3	0.008
	# boxes	38	2 176	69 612	13 564 854 11 870 068
	# boxes filtered	28	1 444	53 062	5 833 951	5 841 193
	# CSNCs	4	4	1 767	44 220	56 269
	# CSNCs filtered	4	2	10	2	25
	# CSNCs separated	4	2	10	2	25
	time (in sec.)	0.003	0.36	38	12 700	10 700

  Number of boxes in each connected component. Each bar corresponding to a CSNC shows the number of contained boxes (ordered largest first). The rightmost bar in each histogram corresponds to the largest CSNC that is filtered out with our heuristic.

	3 330 212	2 448 359	799	483 764	427 933	373 826	360 196	358 962	357 270	317 598	304 441	300 518	286 084	240 678	234 711	232 231	225 870	218 964	180 055	174 007	134 497	132 794	110 754	101 391	95 446	65 097	17 818	3799	446
	1 2 3	1 2 3 4 5 6 7 8 9 1011121314151617181920212223242526
	(c) 3-RPR										(d) 3-RRR*
	Figure 5:

In robotics, manipulators are typically named according to the sequence of joints they are made of, e.g., P stands for prismatic joint and R stands for revolute joint, actuated joints being underlined.

The connected components[START_REF] Munkres | Topology[END_REF] of a set are its subsets that are connected and maximal with respect to inclusion. They define a unique partition of the set. Since the Jacobian of f is full rank at nonsingular configurations, Σ * is a manifold. In that case, connectedness is equivalent to path-connectedness (see[START_REF] Lee | Introduction to Topological Manifolds[END_REF]), which matches the requirement for path planning.

In[START_REF] Goldsztejn | A Branch and Prune Algorithm for the Approximation of Non-Linear AE-Solution Sets[END_REF], only problems where the system has one unique solution for each parameter value were tackled, hence without bisecting variable domains and using directly the parametric existence test[START_REF] Merlet | A formal-numerical approach for robust in-workspace singularity detection[END_REF].

This interval-Newton driven inflation technique is used in global optimization to prove feasibility of approximate feasible points. It is, for instance, implemented by the Intlab[START_REF] Rump | INTLAB -INTerval LABoratory[END_REF] function verifynlss. It was also used in[START_REF] Goldsztejn | Sensitivity analysis using a fixed point interval iteration[END_REF] in the context of sensitivity analysis, and in[START_REF] Ishii | Interval-based projection method for underconstrained numerical systems[END_REF] within a numerical constraint based method dedicated to the projection of a manifold.

Figures are available at http://www.ueda.info.waseda.ac.jp/ ˜ishii/pub/aspects/.

Acknowledgments. This work was partially funded by the French agency ANR project SIROPA (PSIROB06 174445) and JSPS (KAKENHI 23-3810). The computer used for the experiments was supported by Prof. Kazunori Ueda (Waseda University, Tokyo).


Johann Stan
email: johann.stan@univ-st-etienne.fr

Fabrice Muhlenbach
email: fabrice.muhlenbach@univ-st-etienne.fr

Christine Largeron
email: christine.largeron@univ-st-etienne.fr

Recommender Systems using Social Network Analysis: Challenges and Future Trends

Keywords: Recommendation systems, Information filtering, Collaborative filtering, Content-based filtering

Recommender System (RS): Special type of information filtering system that provides a prediction that assists the user in evaluating items from a large collection that the user is likely to find interesting or useful.

Status update (micropost): Short message, shared in an online social platform, expressing an activity, state of mind or opinion.

Folksonomy: Whole set of tags that constitutes an unstructured collaborative knowledge classification scheme in a social tagging system.

Definition

Recommender systems (RSs) are software tools and techniques dedicated to generate meaningful suggestions about new items (products and services) for particular customers (the users of the RS). These recommendations will help the users to make decisions in multiple contexts, such as what items to buy, what music to listen to, what online news to read [19], or, in the social network domain, which user to connect to or which users to consider as a trustful adviser.

Overview

Main Components of a Web 2.0 Social Network A social network can be defined as a set of entities interconnected and it is usually represented as a graph where the entities are described by nodes and their relationships by links. It should be noticed that this concept is not limited to the case of online social networks such as Facebook, LinkedIn, MySpace or Twitter, the main focus of our work.

A common characteristic of these networks, and more specifically modern online social networks, is that they are composed of (i) users (with a user profile, activities and connections) and (ii) social objects representing the intermediations, e.g. topics of user interactions, shared videos, photos.

The user profile generally includes static personal information, such as the name, email and address, as well as more dynamic information about the interests and information needs of the user. The role of the user profile is essential in online communities.

Generally user profiles are different from one application to another, as users present themselves differently, based on the targeted population of the given application (which are sometimes very specific). Another dimension of users is represented by the activities they perform in the social platform. This includes content sharing, media uploading and content description (such as photo tagging). Finally, the third dimension of users is represented by the social connections they establish with others in the network. Users in these online networks are generally connected to different communities, belonging to different social spheres (e.g., friends, family, coworkers).

Another important user characteristic is related to trust. Indeed, the different applications on social content sites allow users to be closer to their communities and to be aware of peer activities and opinions. This brings new dimensions to trust and allows users to have higher confidence in the recommendations, suggestions and sentiment of friends.

Shared social objects influence interactions between users. An object in this context has a concrete and perceptible, physical and/or numeric, manifestation. Some objects are the source of conversational interactions and keepers of collective attention.

They constitute a conversation support. In our actual digital context objects are mainly multimedia ones as articles (Wordpress, Wikipedia), videos (Youtube, Dailymotion), pictures (Flickr, Picasa) or specific status updates shared by users.

In such systems, users can employ different types of annotations to describe social objects: structured annotations (in this case, the terms employed in the annotation are regulated by a common domain vocabulary that must be used by the members of the system), semi-structured annotations (these annotation are generally freely selected keywords without a vocabulary in the background, and a collection of these annotations is called a folksonomy). The last category of such annotations is unstructured, which is the most frequently used in social platforms, and therefore we describe it in more detail. This can be found in the majority of social networks and microblogging systems and primarily consists of free texts in the form of short messages describing a resource, a finding, an impression, a feeling, a recent activity, mood or future plan. A common practice is either to express an opinion about the resource (e.g., web page) or to provide its short summary for the community.

The limitations of this kind of content sharing from the viewpoint of information retrieval and knowledge management are similar to that of social tagging, as users have complete freedom in the formulation of these messages. More concretely, it is difficult to extract interesting topics or named entities from such messages, given the fact that there is an ambiguous, frequently changing underlying vocabulary.

Recommender Systems and Social Platforms: the Mutual Benefits

Nowadays, the wide use of Internet around the world allows a lot of people to connect. This explosion of the Web 2.0 (blogs, wikis, content sharing sites, social networks, etc.)

gives rise to a growing need for RSs based on social and information network mining methods. For such systems, the underlying social structure, also called social network or virtual community, can be leveraged.

The substantial growth of the social web poses both challenges and new opportunities for research in RSs. The main reason for this is the fact that the social web transforms information consumers into active contributors, allowing them to share their status, comment or rate web content. Finding relevant and interesting content at the right time and in the right context is challenging for existing recommender approaches.

At the same time, the major added value of social platforms is to encourage interaction between users. Each interaction can be extracted and used as an input for the RS, as it helps to better understand the user interests and information needs. Also, the structure of the underlying social network in a social platform can contribute to generate recommendations that are more trusted by users (e.g., by considering the social distance in the recommendation process, as generally we trust more recommendations from closer connections). Therefore, we can conclude that the social web provides a huge opportunity for improving RSs (Fig. 1).

Fig. 1. Reciprocal contributions made by recommender systems to social networks

On the other hand, RSs can clearly help to improve user participation in social systems, as they can recommend new friends or interesting content. Thus, the user will be more motivated to keep on-going participation in the social platform, because the more content he/she shares, the more relevant connections the system can recommend, having a precise profile about him/her. Using this connection between social platforms and RSs, new scenarios can be defined for advanced applications, such as people recommendation or various content recommendations (e.g., tags for photo annotation).

Introduction and State of the Art Social Network Analysis

Social network analysis and social mining can be very useful in this context where RSs can take benefit from social networks and conversely, where the formation and evolution of the network can be affected by the recommendations. In order to illustrate this point, we can mention three well known tasks in social network analysis and social network mining:

•

The first one is the identification of key actors which play a particular role or which have a particular position in the network. Different indicators, such as the centrality or the prestige were initially introduced mainly in order to highlight the "most important" actors in the network [START_REF] Wasserman | Social Network Analysis: Methods and Applications[END_REF]. With the appearance of online social networking, these measures were recently revisited to detect actors called, depending on the authors, mediators, ambassadors or experts. Among the actors who have received a lot of attention appears notably the influencer who can be defined as an actor who has the ability to influence the behaviour or opinions of the other members in the social network [START_REF] Anagnostopoulos | Influence and correlation in social networks[END_REF]. The identification of the influencers can be seen as an optimization problem better known as "influence maximization" (or "spread maximization") that is NP-complete but approximated solutions can be determined thanks to greedy algorithms like "Cost-Effective Lazy Forward" (CELF ) algorithm or its extensions Newgreedy, Mixedgreedy or Celf++ [12; 4].

•

Another well known problem in the context of social networks is that of community detection. This problem has mainly been studied in the literature in the case where the community structure is described by a partition of the network actors where each actor belongs to one community [20; 13] and among the core methods we can mention those that optimize a quality function to evaluate the goodness of a given partition, like the modularity, the ratio cut, the min-max cut, or the normalized cut, the hierarchical techniques like divisive algorithms based on the minimum cut, spectral methods or Markov Clustering algorithm and its extensions. However, in real networks, an actor can often belong to several groups and these overlapping communities can be detected using for example the clique percolation algorithm implemented in CFinder or OSLOM (Order Statistics Local Optimization Method). Other recent works have attempted to detect communities, taking into account the profile of the users and their relationships [START_REF] Combe | Getting clusters from structure data and attribute data[END_REF]. These methods can be applied to determine groups of users with similar characteristics or the same interests and consequently, they can be integrated in neighbourhood-based collaborative systems.

•

The evolution of the network is another challenge. Indeed, in many networks, the structure of the network, in other word the actors as well as their relationships, changes quickly over time. The identification of evolving communities or their detection over time is also a subject of recent research which can be integrated in systems to improve recommendations but the dynamic analysis of the network is also related to the link prediction problem which aims to determine the appearance of new links or the deletion of links in the network [18; 15; 5; 8].

It is obvious that link prediction can be useful for people recommendation and, conversely, recommendation approaches can allow to predict the evolution of the network. This temporal dimension is notably important in the context of mobile applications in which moving actors are interacting with each other.

Recommender Systems

The field of social network analysis is a complex and rapidly changing area. To understand the mutual contributions of social networks in recommender systems (and vice versa), it is necessary to clarify the basic principles of these systems.

RSs are dedicated to the help of the users when they must make a decision, taking as basis the fact that in ordinary life people often make decisions based on the recommendation of others. At work, employers count on recommendation letters when they want to recruit new employees; with friends, we talk about books that we loved to read, music or movies that we liked, purchases that have given us satisfaction, or products that disappointed us; and more generally, we trust reviews of specialists before seeing a TV show, an art exhibit, or purchasing an item. This behaviour is based both on the belief that our friends have similar tastes to ours, and on the trust that we can provide to the expert opinion. The recommendations provided by automated systems are trying to mimic those two principles, depending on the available information, and they are supplied to the users in the form of a prediction or a list of items.

The information used for the recommendation process can be extracted from the content available from the users and the items, or it can be inferred from the explicit ratings when the users are asked to rate the items. Depending on the way of how the information is used, the RS is considered to be a content-based, a collaborative filtering or a hybrid (where both information, collaborative and content-based, are used) RS [START_REF] Adomavicius | Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions[END_REF].

Whatever approach is used, the key elements of an RS are (i) the users, (ii) the items, and (iii) the transactions. The users of an RS, which may have very diverse goals and characteristics, are both those who benefit from the system and those who supply it with information. Items are the objects (products or services) that are recommended, and they may be characterized by their complexity and their value or utility for a given user. Transactions are the recorded interactions between a user and the RS, especially the relation between a user and a given item, which can be an explicit feedback, e.g., the rating of a user for a selected item.

In the content-based approach, which has its roots in information retrieval and information filtering research, an item is recommended to a user based upon a description of the item and a profile of the user interests [START_REF]Recommender Systems Handbook[END_REF]. This family of RSs has some advantages (user independence, transparency, easy recommendation of new items) but also some drawbacks: content analysis is limited and the system suffers from overspecialization that leads to homophily (a person is only recommended by people who think like he or she).

In the collaborative filtering approach, an item is recommended to a given user by following another way: the collaborative filtering methods produce user specific recommendations of items based on patterns of ratings without need for exogenous information about either items or users [START_REF]Recommender Systems Handbook[END_REF]. The preferences of the users are explicit:

the users are asked to rate the items (e.g., in terms of l-5 star scale or "I like" / "I don't like"). This approach needs only a set of ratings of users on sets of items: a list of n users, a list of m items and a rating r x,t indicates the rating of user x on the item t. In a typical collaborative filtering scenario, it is very rare (if not impractical) for a user x to rate all the m items, so the R matrix of all ratings users × items is sparse.

To result in recommendation, the collaborative filtering can be either neighbourhoodbased (memory-based) or model-based [17; 19]. The model-based approaches try to propose a model able to predict the unknown rating of a user x for an item t by discovering the underlying preference class of users and the category class of the items.

In neighbourhood-based collaborative filtering, the rating matrix R is directly used to predict ratings for new items, either when the neighbourhood derives from a similarity between the users (for user-based systems), or when the neighbourhood derives from a similarity between the items (for item-based systems), e.g., two items are considered as neighbours if several users have rated these items in a similar way. In most cases, the similarity estimated between users or items in these approaches are Pearson correlation or vector cosine-based similarity.

The efficiency of an RS is measured in terms of relevance of the recommendations and forecast accuracy, in particular seeking to narrow the difference between the predicted ratings made by the system and the real ratings made by the users.

Moreover, the system has to be a good filtering system and not present to users uninteresting items, while not missing interesting items (e.g., in the case of commercial RS, for increasing the number of items sold). It is important to propose to the users items that might be hard to find without a precise recommendation. Many systems suffers from novelty discovery, i.e. they fail to find serendipitious items. All these properties will increase the user satisfaction and the fidelity to the use of the system.

The latest trends in RS domain seek to take into account how human beings function with their peers, especially in their interpersonal behaviors, which brings it closer to the field of social network analysis. Some users try to find credible recommenders so they can follow them, it is thus interesting to investigate the most influential members. It is also important to develop a method to better understand each user of the system and improve the understanging of their profiles, to identify what they like and dislike, or are expecting from the system. The RS must seek to enable individual mechanisms that users can work together, because some users like to contribute to the system with their ratings and express their opinions and beliefs or can be happy to help the others by contributing with information. However, it should be cautious as there are malicious users who seek to influence others in the system just to promote or penalize certain items. A detailed overview of these properties is presented in the different chapters of the collective book edited by Ricci et al [START_REF]Recommender Systems Handbook[END_REF].

Social Search Systems

Frameworks that specifically target recommendation services based on user profiles are mostly in the category of people recommendation and question answering systems.

Such systems explore either the topology of the network or the content of the exchanges between communities and peers. The main difference to content-based social search is the fact that the result of a recommendation is not a document, but another user or group of users. In this way, the person can interact directly with the recommended user, which provides a more secure and trusted environment for the communication process. Also, such people-to-people interactions are more interesting for the service provider, as they can contribute to the growth of the social platform, which is generally measured by the number of users and connections between them.

Guy et al [START_REF] Guy | Do you know?: recommending people to invite into your social network[END_REF] present a people recommendation strategy specially adapted for the enterprise ecosystem. The recommendation engine uses information from an organization Intranet for computing similarity scores between employees. Such information include: (i) paper or patent co-authorship, (ii) commenting of each others' blogs or profiles, (iii) mutual connection in other social networks, internal to the organization.

Based on an aggregated score computed for each relationship, people are recommended to be added in an employee internal messenger system. For each recommendation, an explanation is generated, considered an important component of such systems [START_REF] Herlocker | Explaining collaborative filtering recommendations[END_REF]. A limitation of this approach can be considered the fact that the recommendation only uses statistical information to infer the social proximity between users. More concretely, the content of interactions and exchanges is not taken into account to measure the similarity of interests or information needs. We also mention here the fact that most people recommendation strategies in popular social networks, such as Facebook or Orkut, are also based on this statistical similarity schema.

Lin et al [START_REF] Lin | Smallblue: Social network analysis for expertise search and collective intelligence[END_REF] also target the issue of expertise location in the enterprise environment. The proposed system, SmallBlue [START_REF] Lin | Smallblue: Social network analysis for expertise search and collective intelligence[END_REF], similarly to Guy et al [START_REF] Guy | Do you know?: recommending people to invite into your social network[END_REF], employs data mining and statistical data analysis techniques to extract profile information for employees. More specifically, the system uses company email as a source of information.

Keywords are extracted from each email and a bag-of-words based profile is constructed for employees. An innovative feature of the system is the social explanation of people recommendations, by displaying the social path that connects the user to the recommended person on a specific topic.

Hannon et al [START_REF] Hannon | Recommending twitter users to follow using content and collaborative filtering approaches[END_REF] go beyond the previous approach and build a recommendation strategy using the content of interactions (e.g., status updates) as input. Designed for recommending people to follow in Twitter, the Twittomender system allows users to expand their network by connecting to people that they do not know directly, but with whom they share similar interests. Each user in the system is represented by a vector, comprised of terms extracted from their shared messages. A kind of social expansion of this basic profile is performed, by taking into account messages shared by people connected to the user. This is based on the observation that connected people share close interest. The computation of profile similarities is achieved by the traditional tfidf weighting schema in information retrieval and cosine similarity. The Twittomender system is original and different from existing collaborative filtering approaches, as it takes into account the structure of the underlying social network to better approximate the interests of the user. It is however a considerable limitation in the system that no disambiguation or semantic expansion of profile terms are considered. More concretely, the user profile is composed of keywords that might have multiple meanings and this could be a considerable drawback for the relevance of recommendations.

A new generation of social search engines is represented by so-called Question Answering Systems. The main difference to the previous approaches is the fact that in this case the system builds a user profile from some kind of user activity (content production or consumption) and uses it to match them with a question formulated by another user.

Aardvark [START_REF] Horowitz | The anatomy of a large-scale social search engine[END_REF] is certainly the most promising social search engine. Aardvark introduced several innovations in the field of social search. First of all, it is the first system that models the users based on their generated content. For this reason, users provide topics of interest to the system when they subscribe. Then, a crawler extracts further topics from the user's profiles and status updates in social platforms to expand the initially entered profile items. The extraction of topics from social updates is achieved by linear classifiers, such as Support Vector Machines and probabilistic classifiers. Aardvark is not built on top of existing social platforms and lacks a global approach for conceptualizing user profiles.

In another recent social search engine, CQA [START_REF] Li | Routing questions to appropriate answerers in community question answering services[END_REF], the objective is similar to that of Aardvark : route a question to the right person in a community of answerers. In their paper, Li and King [START_REF] Li | Routing questions to appropriate answerers in community question answering services[END_REF] introduce two important dimensions for such systems: (i) the consideration of the answerer availability and (ii) the question of the quality of answers.

The quality of answers is estimated by taking into account statistical information about the length of the answer, the time the user took to send it and the feedback of other users. In the case of availability, the system monitors the user logins and performs a prediction of whether the user will be available at a specific time and date in the future.

We can finally conclude that in current social search systems that offer a people recommendation service, the issue of recommendation explanation is still not well tackled (which is also strongly related to privacy management). Also, few frameworks benefit from semantic web technologies on a data storage or data enrichment level.

Another possibility to build an RS is to leverage the content shared by users in the social network. More specifically, we consider the content productions of users in order to better understand their interests and information needs and more concretely, build expertise profiles. In such way, the recommender engine is able to recommend people that have similar or complementary interests. From a conceptual viewpoint, such a recommender engine is composed of two parts: (i) the identification of semantic data (e.g., entities extracted from status updates) that will compose the profile and

(ii) the scoring of said semantic data (measuring the user expertise).

We consider X the domain of all n users involved in the social platform. T x represents the set of items correlated with user x, i.e., T x = t|W eight(t, x) > 0. Therefore, user x and item t are correlated when W eight(t, x) > 0, W eight being the weight of the item in the profile.

An item in the user profile can be represented by a keyword or a concept. The main difference is that concepts have URIs, that provide them the exact semantic meaning. Generally, such URIs can be retrieved from so called semantic knowledge graphs, such as DBPedia. Each profile item is an entity (keyword, named entity) extracted from at least one content production of the user and connected to at least one semantic concept present in at least one semantic knowledge base. The main arguments for this choice is that this kind of representation is richer and less ambiguous than a keyword-based or item-based model. It provides an adequate grounding for the representation of coarse to fine-grained user interests. A semantic knowledge base provides further formal, computer-processable meaning on the concepts (who is coaching a team, an actor filmography, financial data on a stock), and makes it available for the system to take advantage of knowledge base-originated semantic concepts that are more precise, and reduce the effect of the ambiguity caused by simple keyword terms.

Normally in a conversation, we depend essentially on the context of the conversation to disambiguate a word. Similarly, in order to associate keywords or entities in a social update to the right concept in Linked Data, contextual cues are necessary to allow restricting the semantic field of the social update. In traditional documents, generally there are sufficient contextual cues to overcome such ambiguous situations, where the meaning of a term is not straightforward.

In the case of social platforms, the short nature of posts requires to find these cues elsewhere, so we may consider two main additional sources of contextual cues:

•

The first contextual cue is user-related, which consists in building incrementally a vocabulary from all social updates of the user. The assumption behind this first additional context is that there is a probability that the user previously shared some content in a related semantic field (e.g., a user who posted about "Apple" might have shared before about other Apple products, such as the "iPhone").

•

The second additional contextual cue is community-related. On social platforms users are members of different communities, which influence each other in terms of interests. Users participate in a group or a community because they are interested in what community members say and as a consequence of this participation, users have intention of using commonly known keywords to make his/her contents easily understandable by the community. This second contextual cue is used only if the user-related one is not yet available or not sufficiently rich (e.g., user has shared few messages, but has lots of friend connections). More specifically, it is a solution for the so-called cold-start situation and consists of aggregating the most recent messages of friends connected to the user and constructing a vocabulary from the content of these messages.

After the construction of the vector containing also such items that represent the context of the keyword, several similarity measures can be used to compare it with the description of candidate concepts in the knowledge base, and the best matching concept selected. A further, optional step is to leverage the semantic neighborhood of the concept to better describe the user expertise (e.g., include more general concept into the profile). This could be interesting in case of profile extracted from status updates, as such messages are short and therefore we have little available information about the user information needs or interests.

Future Directions/Open Questions

As seen in the previous section, over the last two decades, some major advances have been achieved in the area of RSs using techniques of social network analysis and mining.

In this section we present some current challenges and open questions, that we think, will be a major preoccupation for scientific communities, but also the industry in the upcoming years. We will consider two practical future directions and list the corresponding open challenges that need to be considered.

Recommender Systems in the Enterprise

Nowadays, more and more companies show increasing interest towards the integration of RSs in the Intranet in order to further improve communications and internal knowledge management. Several reasons push companies to invest in such infrastructures:

• it can improve social interactions between employees (e.g., a people recommender in the enterprise may help in finding the best expert for a specific problem [START_REF] Joly | Contextual recommendation of social updates, a tag-based framework[END_REF], which may reduce costs and increase efficiency);

• it can provide new means for the dynamic composition of teams for a specific project, as the expertise of employees can be easily retrieved. Also, internal documents, videos can be recommended for a project or learning;

• such a system may provide specific tools for employees in order to keep motivation and a good atmosphere in the company, e.g. associating specific tags to colleagues, such as expertise tags and specific badges, when being an active contributor in providing help to colleagues or other scenarios;

• with such a system, an implicit internal social network can be built, that links employees with similar interests and activities. This can help the company in improving its organization and also optimize human resources management (changing dynamically teams, etc.).

The deployment of an RS in a company faces several challenges and its design depends on several criteria, such as the type of activity the company performs or the degree of sensibility of the information they share. A first challenge, but also, the most important, is what kind of internal content to use as input for the RS. Company emails are a rich source for learning more about each employee expertise and interests, but there may privacy and security concerns. Another, more acceptable source for such an RS may be represented by content employees share on internal or web-based social networks, such as Twitter [START_REF] Stan | Semantic user interaction profiles for better people recommendation[END_REF] or Yammer. Such content is shorter and generally does not contain confidential information. Furthermore, the content of web-pages employees read may also represent and additional source for such systems for the construction of the expertise profiles [START_REF] Joly | Contextual recommendation of social updates, a tag-based framework[END_REF].

Amongst the challenges for building such a system, the most important are technical and related to human-computer interaction (HCI). More concretely, technical challenges include the implementation of content extraction tools from internal mail servers, the microblogging platforms and web browsers. All the extracted content must be aggregated and stored in a secure database. Challenges related to HCI include the design of user interfaces that allow users to control what content to share with the system (e.g., there may be e-mails for private usage).

An important issue when designing RSs is to generate an explanation for each recommendation. Such explanations could be useful as they increase trust. They can be of several types: (i) the explanation of the social path between the two users, i.e.

by showing part of the social graph and the paths in the employee social network that connect them or (ii) a semantic explanation, that includes areas of expertise of the recommended employee. According to the social distance, such areas of expertise may be shown with different levels of granularity, by using hierarchical paths of concepts in semantic knowledge bases, such as DBPedia (e.g., expert in Twitter is more specific than expert in microblogging platforms).

In a nutshell, the following questions should be considered for building a successful RS specifically targeted to an enterprise:

• How to extract the named entities from short, unstructured messages, status updates? In other words, how to transform each social interaction that occurs in the company or that employees share into useful knowledge for the RS;

• How to combine structural and semantic analysis for recommendation ranking;

• What are the next generation privacy protection mechanisms that would allow an easy adoption of such a system in a company;

• How to generate useful and meaningful explanations for a recommendation;

• How to make good recommendations without violating privacy concerns;

The use of such RSs in an enterprise may be useful also for generating a profile for the entire company, e.g., by aggregating all individual user profiles. Such a profile may be useful for the next generation enterprise social networks, where each node in the network is a company. Such a network could facilitate collaboration between companies, e.g., by finding the best company for a collaborative European project.

Recommendation in Mobile Social Networks: a Multi-Agent Approach

A second scenario for RSs concerns mobility and ubiquity, as more and more users have smartphones, capable of sensing context. The most widely used context in such a scenario is the user location, which may significantly improve recommendation (other context data may include available networks (Wifi, Bluetooth) or other physical data).

By integrating location in an RS, a preliminary filtering of items can be performed, by selecting only a subset that is in a well-defined perimeter. Such items may include other users with similar interests (e.g., looking for people who like similar artists in a given location), as well as restaurants, cinema or other services the city provides.

The deployment of such an RS faces several challenges, depending on its design. A first important design principle which needs to be fixedearly is whether the system is centralized or decentralized. Clearly, a centralized system would face important performance and scalability issues. A decentralized system is more interesting, as a local server can be associated to each location in the city, which could support this recommendation service.

A further step towards decentralization can be considered, by integrating multiagent principles to the RS, i.e., to design and implement a customizable approach where different autonomous decision-making entities (agents) have to communicate, exchange knowledge and cooperate in order to achieve individual and/or collective objectives. It allows the creation of different communities, with different possible functions and modes of exchanges. Such an approach aims to meet several challenges, such as decentralization of the community management, personalized automatic management and discovery of communities, and flexibility so that any agent can create its own community. In addition, it should cover all levels of abstractions (agent, environment and organization) that are required for the development of sophisticated multi-agent system. In this design, each smartphone is equipped with an agent, capable of exchanging knowledge with other agents, using the local server associated to a given location in the city.

Using a multi-agent approach for an RS in mobility, agents can act as a personal assistant on the behalf of each user, present in a given location. The agent perceives knowledge from the communities of individual interests and acts upon the communities to meet their goals. Thus, agents can bring the appropriate people having common goals or interests together share their knowledge with each other at ease.

Other scientific challenges for such advanced RSs include the traditional coldstart problem, i.e., how to provide recommendations to users with little information about their profile, or how to recommend items with few ratings. Also, an important general challenge is how to make recommendation users trust, i.e., how to provide users an easy way for giving feedback on recommendations. With regards to trust, recent works try to integrate the notion of distrust, i.e., how to deal with users or items that cannot be trusted?

Cross-References