Philippe Wenger Cuspidal

Philippe Wenger

Cuspidal Robots

Introduction

Preliminaries

This chapter deals with the so-called cuspidal robots. It is focused on serial, open-chain robots. For these robots, the geometric model can be defined by an input map f, such that X = f (q), where q is the vector of joint variables (the inputs), which are all actuated. Vector X contains the coordinates of the end-effector pose (the outputs). The robots are assumed non-redundant, namely, the number of joint variables (n) is equal to the number of coordinates (m) that describe the end-effector pose (n = m). The configuration space of these robots can be restricted to their joint space, which is fully defined by the actuated joints. As a consequence, the only singularities are defined by the input singularities. Unless specified, the word singularity will stand for input singularity in this chapter. Figure 1 shows a 3-R robot (made of three revolute joints). The input variables are the three joint coordinates θ 1 , θ 2 and θ 3 . The output variables are defined by the three Cartesian coordinates x, y and z of a reference point P fixed on the last link. For this robot, n = m = 3 and its joint space is a 3-Torus if the joints are unlimited (a 3-D box if they are limited). Generically, the singularities form a set of surfaces in the joint space. These surfaces divide the joint space into a set of singularity-free connected regions called aspects, as defined by [START_REF] Borrel | A study of manipulator inverse geometric solutions with application to trajectory planning and workspace determination[END_REF]. As it will be shown further, a cuspidal robot is a robot that can move from one of its inverse geometric solution to another without encountering a singularity. This feature was discovered quite recently and has then been fascinating a lot of researchers. Before this discovery, it was thought that any robot should necessarily cross a singularity during a change of solution, like, e.g., when an anthropomorphic robot (a Puma type robot) switches from the elbow up to the elbow down configuration by passing through the fully outstretched (or folded) singular configuration (see section 2.1). A brief history of cuspidal robots is presented next.

Brief history of cuspidal robots

In 1986, a mathematical proof was provided in order to confirm the well-established belief that any non-redundant serial robot should cross a singularity when moving from one solution to another [START_REF] Borrel | A study of manipulator inverse geometric solutions with application to trajectory planning and workspace determination[END_REF]. This proof was based on the implicit function theorem and some topological arguments. The proof was in fact incorrect but at that time nobody noticed it as it was just confirming a fact that everybody had admitted before. The very first mention of a singularity-free change of solution dates back to 1988, in a talk by V. Parenti-Castelli and C. Innocenti (University of Bologna, Italy) presented during the first conference on Advances in Robot Kinematics that took place in Ljubljana [START_REF] Parenti | Position analysis of robot manipulators : Regions and sub-regions[END_REF]. For two different types of 6-R (revolute-jointed) robots, the authors were able to build a singularity-free path joining two inverse solutions. It was such a big challenging of a well-established fact that nobody trusted them at that time. In a separated work conducted in Stanford University, J. W. Burdick showed in its PhD thesis several 3-R robots also able to move from one solution to another without encountering a singularity [START_REF] Burdick | Kinematic analysis and design of redundant manipulators[END_REF]. These results were not published outside the PhD thesis. Nothing appeared during the next four years before this behavior was then formalized in 1992 by [START_REF] Wenger | A new general formalism for the kinematic analysis of all nonredundant manipulators[END_REF]. It was clearly shown in this work why even a simple 3-R robot can move from one of its solution to another without meeting a singularity. It was not easy to understand why the proof given in [START_REF] Borrel | A study of manipulator inverse geometric solutions with application to trajectory planning and workspace determination[END_REF]) was incorrect as it seemed mathematically sound. The main problem was that the proof resorted to a hypothesis that turned out to be not true in all robots. The detailed explanation is a bit more tricky and is not reported there. The belief that a change of solution should necessarily be singular was so strongly rooted in people's mind that it took several years before the research community started to accept the existence of cuspidal robots. The word cuspidal was defined after 1995 when it was shown that the existence of a cusp point in the singularity locus of the robot indicates that this robot can change its posture without encountering a singularity by encircling this cusp point [START_REF] Omri | How to recognize simply a nonsingular posture changing 3-dof manipulator[END_REF], see sections 2.4 and 4.2.

Questions of interest

When the research community started to admit the truth in the second part of the 90s, it was faced with a lot of questions, such as:

-How can a non-singular change of solution be accomplished for a given robot? -What are the consequences on path-planning? -Is this ability possible only for specific robots or is it more general? -Given a new robot, how to know if it will have this ability? -Is it possible to set some conditions for a robot to have this ability? -Is it possible to enumerate all the cuspidal robots?

The first two issues are very important for control, while the others are very important for the designer. As it will be shown further, a change in geometric parameters of a non-cuspidal robot may render it cuspidal. Interestingly, this fact can be illustrated with the story of the IRB 6300C robot launched by ABB in 1996. This new manipulator was specially designed for the car industry to minimize the swept volume. The only difference from the Puma was the permutation of the first two link axes, resulting in a manipulator with all its joint axes orthogonal. Commercialization of the IRB 6400C was stopped one year later. Informal interviews with robot customers at that time revealed difficulties in planning offline trajectories using Robotic-CAD systems for this robot. In fact it was shown later that the IRB 6400C robot turns out to be cuspidal.

Chapter outline

In the rest of this chapter, the singular and non-singular changes of posture are analyzed in details. Next the feasibility of trajectories in cuspidal robots are investigated and the maximal regions of feasible paths in the workspace are defined. The identification, enumeration and classification of 3-dof (degree-of-freedom) cuspidal robots and non-cuspidal robots are then addressed. Eventually, the case of 6-dof robots and parallel robots are discussed.

Postures

Definition

A posture is associated with one solution to the inverse geometric problem of a robot. This word refers to the way a given robot places its links in space to reach a given frame. For usual industrial robots, a posture can be easily identified geometrically. For example, it is well known that an anthropomorphic robot shown in Figure 2, has at most eight distinct inverse geometric solutions, which are associated with eight postures. These postures can be identified geometrically by the configuration of the elbow (up or down), the shoulder (right or left) and the wrist (flip or no flip). The total number of combinations amount to 2 3 = 8 distinct postures. Figure 3 shows four of the eight postures obtained in the flip configuration of the wrist. It is well known that the only way for this robot to switch from any of its posture to another is to cross a singular configuration.

Postures and aspects case 1 : non-cuspidal robots

The aspects are the largest singularity-free connected regions of the joint space [START_REF] Borrel | A study of manipulator inverse geometric solutions with application to trajectory planning and workspace determination[END_REF]. They are bounded by the singularity surfaces (or hyper-surfaces for a robot with more than 3 joints) and by the joint limits when they exist. Additional boundaries may occur in the presence of obstacles [START_REF] Omri | Kinematic Analysis of Robot Manipulators[END_REF]. Before cuspidal robots were discovered, one posture was thought to be uniquely associated with one aspect. Indeed, since the robot was thought to cross necessarily a singularity when moving from one posture to another, there could not be more than one posture in each of its aspects. This is true for most usual industrial robots like the anthropomorphic robot and the SCARA robot shown in Figure 3 and Figure 4, respectively. The SCARA robot is a well-known industrial robot (Figure 4). This 4-dof robot can produce three translations in space and one rotation about a vertical axis. This motion is known as the Schönflies motion, first studied by the German mathematician Arthur-Moritz Schönflies . This motion is suitable for pick-and-place tasks. The deter- minant of the Jacobian matrix det(J) vanishes whenever sin(θ 2 ) = 0, where θ 2 is the second revolute joint variable. Accordingly, a singularity occurs whenever θ 2 = 0 or θ 2 = π, namely, when the arm is fully extended or fully folded. This robot has two aspects defined by θ 2 > 0 and θ 2 < 0, respectively. Moreover, the inverse geometric model of this robot admits two solutions, associated with the two postures elbow up and elbow down, respectively. Fig. 5, left, shows the two aspects in (θ 1 , θ 2 ). The other joint variables can be ignored since they do not play any role in the singularities and aspects. The robot is assumed to have joint limits and its joint space is thus a square in (θ 1 , θ 2 ). Figure 5, right, shows the aspects projected in the workspace and the robot depicted in an elbow down posture. There is only one inverse geometric solution in each aspect; namely, a posture is associated with one aspect.

Postures and aspects case 1 : cuspidal robots

A cuspidal robot has more than one inverse geometric solution in at least one of its aspects. In other words, it can move from one posture to another without meeting a singularity. The 3-R robot with mutually orthogonal joint axes shown in fig. 1 turns out to be cuspidal because this robot has two aspects and four inverse geometric solutions, two in each aspect. The determinant of the Jacobian matrix J of this robot can be written as:

det(J) = (d 3 + c 3 d 4 )(c 2 (s 3 d 3 -c 3 r 2 ) + s 3 d 2 ) (1)
where c i = cos(θ i ) and s i = sin(θ i ), i = 2, 3. The geometric parameters d 2 , d 3 , d 4 and r 2 , shown in Figure 1, are the Modified Denavit-Hartenberg as defined in [START_REF] Khalil | A new geometric notation for open and closed loop robots[END_REF]. It can be noticed that the first joint variable θ 1 does not appear in this determinant. This is always the case in any serial robot whose first joint is revolute since in this case the singularities do not depend on θ 1 . The singularity surfaces of our robot, which are the zero sets of det(J) = 0, can then be plotted in (θ 1 , θ 2 ) where they appear as curves. The first factor may vanish only when d 3 < d 4 , namely when the last link is longer than the second link. If it is not the case, the singularity curves are defined by the zeros of the second factor only. Figure 6 (left) shows the singularity curves obtained when d 2 = 1, d 3 = 2, d 4 = 1.5 and r 2 = 1 and for unlimited joints. Note that since the robot is assumed to have no joint limits, its joint space has the structure of a Torus and the singularity curves are defined on the Torus T (θ 2 , θ 3 ). For more simplicity, a plane picture of the joint space is shown in fig. 6 and the reader may retrieve the topology of T (θ 2 , θ 3 ) by identifying the opposite sides of the square. Having this important notice in mind, it is easy to see that the singularities form two closed curves S 1 and S 2 and define only two aspects. The singularities can be also plotted in the workspace. For our 3-R robot, the workspace is of dimension 3 but it is sufficient to plot a planar cross section passing through the first joint axis because we know that the singularities do no depend on θ 1 . The workspace can then be plotted in the plane (ρ, z), where ρ = x 2 + y 2 (Figure 6, right). The outside boundary of the workspace W S 2 is the image of S 2 while the internal boundary W S 1 is the image of S 1 . The internal boundary is made of four lines that merge at four cusp points. This internal boundary separates two regions: the inner region and the outer region. It can be verified that the robot has four inverse geometric solutions in the inner region but it has only two solutions in the outer region. We solve the inverse geometric model at a point P (ρ = 2.5, z = 0.5) in the inner region. The four solutions are (in radians): q (1) = [-1.8, -2.8, 1.9] t , q (2) = [-0.9, -0.7, 2.5] t , q (3) = [-2.9, -3, -0.2] t and q (4) = [0.2, 0.3, 1.9] t . It is apparent from fig. 7 that q (2) and q (3) lie in the same aspect A 1 . It is then possible to link q (2) and q (3) by a non-singular path as shown in Figure 7. Keeping in mind that the opposite sides of the square should be identified, one can see that q (1) and q (4) also lie in one single aspect (A 2 ). Contrary to their non-cuspidal counterparts, the anthromorphic robot and the SCARA robot, the postures of this 3-R cuspidal robot are difficult to identify geometrically, as shown in Figure 8.

Non-singular change of posture vs singular change of posture

The question of how a cuspidal robot can move from one of its postures to another without encountering a singularity is of primary interest and has puzzled the research community for several years. People thought that the robot should meet a special transitory state between the two postures during a change of posture. If it is not a singularity, what kind of transitory state should it be? In fact no special transitory state is met during a non-singular change of posture and this change is accomplished quite smoothly. To better understand this behavior, it might be helpful to refer to the mappings from a surface onto a plane as formalized by Whitney in 1955. Whitney showed that only two types of stable singularities may occur when a surface is projected onto a plane: the fold and the cusp [START_REF] Whitney | On singularities of mappings of euclidean spaces 1. mappings of the plane into the plane[END_REF]. A fold arises when the surface is simply folded like in Figure 9, left. Its projection onto a plane defines a simple line. A cusp arises when the surface is folded twice as in Figure 9, right. The projection onto a plane gives rise to two fold lines that merge at a cusp point. Now, the non-singular change of posture Figure 9. A fold (left) and a cusp (right). Adapted from [START_REF] Gibson | Kinematics from the singular viewpoint[END_REF]. can be interpreted by considering that the doubly-folded surface shown on the right of Figure 9 is the configuration space F (ρ, z, t) = 0 of a cuspidal robot, where ρ and z are the output variables and t is associated to one of the joint variables. The projection onto the plane corresponds to the workspace of the robot. The two red lines merge at a cusp point and define a region where the robot admits three solutions t 1 , t 2 and t 3 , each one being associated with on one of the three layers of the doubly-folded configuration space surface. Figure 10 shows a path connecting two solutions t 1 and t 3 (from layer 1 to layer 3) at a given point (ρ, z) of this 3-solution region. This path goes smoothly between the solutions and no special transitory configuration is met. Moreover, it turns out that the path goes around the cusp, a fact that will prove of primary importance for the characterization of cuspidal robots. One should be aware that if the projection of the path onto the plane does cross the two red line segments, the path itself never meets the corresponding folds of the configuration space and it is really singularity-free. Coming back to our cuspidal 3-R robot, the non-singular posture changing path shown in Figure 7 is now projected in the workspace cross section (Figure 11). Like in Figure 10, the path encircles a cusp point. The same remark as above also holds here: no singularity is met even if two segments of the inner boundary are crossed. The shape of the configuration space of the robot is a bit more complicated than the one illustrated in Figure 10. It is easier to cut it along its folds and to show separately its restrictions to the aspects. Figure 12 shows the configuration space restricted to the aspect A 1 (above) and aspect A 2 (below). To get the complete configuration space, these two parts should be glued together along their common edges. In fact the complete configuration space folds along these edges. The fact that there are four inverse geometric solutions in the inner region and only two in the outer region is in accordance with the number of layers of the configuration space in these regions. The non- This path goes smoothly from one layer to another like in Figure 10 by going around a cusp point. Note that in P there are two more solutions in aspect A 2 and a non-singular posture changing path between these two solutions will have to encompass one of the two opposite cusp points. A singular posture changing path can also be defined in P . In the configuration space, such a path should go from one layer of an aspect to a layer of another aspect by moving on a fold. The splitted model of the configuration space shown in Figure 12 does not make it possible to show this path on the same image. Starting from P in aspect A 1 , the path will have to go towards one of the edges. Once on the edge, the path is in fact on the fold that enables it to enter the second aspect A 2 and a singularity is encountered, where two inverse geometric solutions merge. Physically, the robot behaves like if it was bouncing back against a workspace boundary (think of the SCARA robot that has to bounce back in the fully outstretched configuration when it moves from the elbow up to the elbow down posture). 3 Path feasibility

Showing an example

Another important feature of cuspidal robots is their inability to track certain prescribed paths in their workspace, even in the absence of joint limits or obstacles. Let us consider the straight line path shown in red in Figure 13. The arrow indicates the direction of motion. The robot is unable to track this path. The reason is that the robot will have to stop on the second crossed boundary line. Indeed, Figure 12 shows that an edge will be always met, should the robot start from aspect A 1 or A 2 . Since when arriving on an edge the robot has no other choice than bouncing back, it cannot track the path further. Note that the path is also infeasible in the reverse direction. In usual non-cuspidal robots met in industrial robotic sites, path infeasibility is usually due to a physical obstruction such as a joint limit or a collision. The above example shows that a path can be infeasible even if the robot has not joint limits and if there are no collisions. The following section proposes a way of defining the regions of feasible paths in the workspace for cuspidal robots.

Regions of feasible paths for non-cuspidal robots

The question of whether a prescribed path in the workspace can be fully tracked or not is of primary interest for many robotic applications such as process tasks. Think of an arc-welding task in which the soldering torch attached to the robot end-effector must realize a continuous welding seam. The welding seam must be fully realized in one step at a constant velocity. This is the reason why P. Borrel introduced the notion of aspects (see section 2.2) when he started to work of the design of a Robotic CAD interface with CATIA for robots offline programming [START_REF] Borrel | A study of manipulator inverse geometric solutions with application to trajectory planning and workspace determination[END_REF] in 1986. For a non-cuspidal robot, there is only one posture in each aspect. This means that the kinematic map is one-to-one from each aspect onto the workspace. In other words, the aspects are the largest uniqueness domains of the joint space for a non-cuspidal robot. This property is useful to analyze the feasibility of paths. Indeed, since the kinematic map is oneto-one on each aspect, the pre-image of any connected set lying in the image of an aspect in the workspace defines a connected set in this aspect. This means that any continuous path lying in the image of an aspect is the image of a continuous path in the joint space. In other words, any path in the image of an aspect is feasible by the robot. This means that the images of the aspects are the (maximal) regions of feasible paths in the workspace for a non-cuspidal robot. In a robotic CAD system, it is this very convenient to determine the regions of feasible paths in the workspace since the user will then know where to define the prescribed paths during the off-line programming of a robot. Referring to Figure 5, this SCARA robot has two regions of feasible paths in the workspace that overlap. Suppose that this SCARA robot is used to cut L-shape plates. The robot tool must be able to follow the contour of the shape continuously. Figure 14 shows the two regions of feasible paths along with a suitable and a non-suitable placement of the plates in the workspace. The one that is fully included in the image of an aspect (above) is suitable while the other (below) is not. For a cuspidal robot, the aspects do not define uniqueness domains any more. Accordingly, the regions of feasible paths are not the images of the aspects in the workspace. New uniqueness domains must be defined.

Characteristic surfaces

Since the singular surfaces in the joint space do not separate all the inverse geometric solutions, new separating surfaces should exist. The set obtained by calculating the non-singular inverse geometric solutions for all points on an internal boundary forms a set of non-singular surfaces in each aspect. These surfaces are called the characteristic surfaces [START_REF] Wenger | A new general formalism for the kinematic analysis of all nonredundant manipulators[END_REF]. A set of characteristic surfaces is associated with one aspect and they separate the inverse geometric solutions in each aspect, as shown further. A general definition of the characteristic surfaces can be set as follows, which stands for any non-redundant manipulator. Let A * i be the boundary of aspect A i . The characteristic surfaces {CS i } associated with A i are:

{CS i } = f -1 (f (A * i )) ∩ A i (2)
where f (A * i ) is the image of A * i under the forward kinematic map and

f -1 (f (A * i )) = {q/f (q) ∈ f (A * i )}.
Note that since an aspect is defined as an open set, A i does not contain its boundary i.e. A * i ∩ A i = ∅ thus {CS i } might be empty (note that if this is the case for all its aspects, the robot is not cuspidal). Since the general definition of the characteristic surfaces is not algebraic in nature, it is difficult to derive an algebraic expression of {CS i } that would be easy to handle. It should be thus calculated numerically. For the cuspidal robot of Figure 1 i can be defined as

{CS i } = f -1 (W S i ) ∩ A i , where f -1 (W S i ) = {q/f (q) ∈ W S i }. Since W S 1 = BS 1 ∩ BS 2 ∩ BS 3 ∩ BS 4 (Figure 15 above), we can write f -1 (W S 1 ) = f -1 (BS 1 ) ∪ f -1 (BS 2 ) ∪ f -1 (BS 3 ) ∪ f -1 (BS 4 ). Each set f -1 (BS j ) has two components CS 1,j = f -1 (BS j ) ∩ A 1 and CS 2,j = f -1 (BS j ) ∩ A 2 in
A 1 and A 2 , respectively. Thus, the two sets of characteristic surfaces can be written as 15 below). Any two adjacent segments of a set of characteristic surfaces meet at a preimage of a cusp point. This preimage is either a singular configuration or a non-singular one. When the preimage is singular, the segments meet tangentially to a singular surface, whereas a non-singular preimage of a cusp point forms a cusp in an aspect. For example, the segments CS 1,1 and CS 1,2 meet tangentially to the singularity surface S 1 at the singular preimage of the cusp point that links BS 1 and BS 2 in the workspace. The remaining non-singular preimage of this cusp point connects the segments CS 2,1 and CS 2,2 and forms a cusp in aspect A 2 (Figure 15 below).

{CS 1 } = CS 1,1 ∪ CS 1,2 ∪ CS 1,3 ∪ CS 1,4 and {CS 2 } = CS 2,1 ∪ CS 2,2 ∪ CS 2,3 ∪ CS 2,4 respectively (Figure

Uniqueness domains and regions of feasible paths for cuspidal robots

The characteristic surfaces induce a partition of each aspect into smaller sets Ra ij . Also, the internal boundaries induce a partition of the workspace into regions and each such region is associated with several sets Ra ij . For the cuspidal robot at hand, the inner region is associated with the four sets Ra 11 , Ra 12 , Ra 21 and Ra 22 (in gray in Figure 16). The first two, Ra 11 and Ra 12 , are in A 1 , while Ra 21 and Ra 22 are in A 2 . The outer region is associated with the two sets Ra 13 and Ra 23 that belong to A 1 and A 2 , respectively. The sets Ra ij are used to determine the maximal uniqueness domains. First, it can be proved that the sets Ra ij are uniqueness domains [START_REF] Wenger | Uniqueness domains and regions of feasible paths for cuspidal manipulators[END_REF]. Second, there exist larger uniqueness domains in the joint space. In effect, Figure 16 shows that each aspect is made of three sets Ra ij , two of them being associated with the same region in the workspace. If one removes one of these two sets and its boundary from the aspect, the remaining domain is a uniqueness domain [START_REF] Wenger | Uniqueness domains and regions of feasible paths for cuspidal manipulators[END_REF]. Thus, there is still a unique and Qu 4 = A 2 -C(Ra 21 ) are still uniqueness domains. In addition, these uniqueness domains are maximal [START_REF] Wenger | Uniqueness domains and regions of feasible paths for cuspidal manipulators[END_REF]. Figure 17 depicts the four uniqueness domains Qu 1 , Qu 2 , Qu 3 and Qu 4 . The uniqueness domains can be determined numerically. A simple numerical method can be found in Figure 17. The four uniqueness domains for the robot of Figure 1. [START_REF] Wenger | Uniqueness domains and regions of feasible paths for cuspidal manipulators[END_REF]) and will not be reported here. Now that we have determined the (maximal) uniqueness domains, it is then possible to obtain the (maximal) regions of feasible paths in the workspace for a cuspidal robot. These regions are the images in the workspace of the uniqueness domains. Figure 18 shows the four regions W f i = f (Qu i ), i = 1, , 4 of feasible paths for the cuspidal robot at hand. The internal segments that appear in each region indicate sets of points that do not belong to this region and, in turn, segments that the manipulator cannot cross. In fact, each region of feasible paths is the image of an aspect minus one or several segments of the internal boundary surface. This is because the maximal uniqueness domains are defined from the aspects by removing one set Ra ij together with its boundary. By doing so, one removes a part of the boundary surface in the Cartesian space. Note that the four regions W f i define regions where any arbitrary path is feasible but they do not feature the full model of feasible paths. In effect, it is always possible to define a feasible path that undergoes a non-singular change of posture in aspect A 1 (resp. in aspect A 2 ). In this case, the path would start in W f 1 (resp. in W f 3 ) and stop in W f 2 (resp. in W f 4 ). In fact, the full model of feasible paths is obtained when W f 1 and W f 2 (resp. W f 3 and W f 4 ) are properly glued together. To better visualize this fact, the reader is invited to come back to Figure 12, which precisely shows the full model of feasible paths.

Note : the above definitions and formula stand for any non-redundant robot, with or without joint limits. In [START_REF] Wenger | Uniqueness domains and regions of feasible paths for cuspidal manipulators[END_REF], a cuspidal 3-R robot with joint limits has been analyzed with this theory. It is even possible to include the influence of collisions (self-collisions or collisions with the environment) in the calculus, as reported in [START_REF] Wenger | Modeling kinematic properties of type-2 regional manipulators using octrees[END_REF]. Practically, however, it is difficult to handle robots with more than 3 joints.

Identification, enumeration and classification of cuspidal and non-cuspidal robots

Simplifying geometric conditions

Because of the more complex behavior of a cuspidal robot and because of the difficulty in modeling its kinematic properties, industrial robots should be preferably non-cuspidal. Thus, before designing an innovative kinematic architecture, robot manufacturers should have guidelines and design rules to help them. Why a manipulator with a given geometry is cuspidal on noncuspidal has long been a very intriguing question. It is worth noting that this question remains not completely solved. One of the pioneer contributors to this problem was J. Burdick, who observed that under simplifying geometric conditions such as intersecting or parallel joint axes, a 3-R manipulator was non-cuspidal [START_REF] Burdick | A classification of 3R regional manipulator singularities and geometries[END_REF]. Other simplifying conditions were exhibited later [START_REF] Wenger | Design of cuspidal and noncuspidal manipulators[END_REF] as a direct consequence of the condition recalled in next section. Finally, the following seven geometric conditions were found to define non-cuspidal 3R manipulators:

1. first two joint axes are parallel; 2. last two joint axes are parallel; 3. first two joint axes intersect; 4. last two joint axes intersect; 5. first two joint axes are orthogonal and all joint offsets vanish; 6. the joint axes are mutually orthogonal and the first joint offset vanishes; 7. the joint axes are mutually orthogonal and

d 2 4 > d 2 3 (1 + ( r2 d2-d3 ) 2
). These conditions also hold for 6-R manipulators with a spherical wrist because the singularity conditions for the wrist and the regional structure Figure 18. The four maximal regions of feasible paths for the robot of Figure 1. can be decoupled. It is worth noting that conditions 2. and 3. are encountered in most industrial 6-R manipulators. However, the last three conditions are unusual.

A design methodology taking into account the aforementioned geometric conditions was proposed by [START_REF] Wenger | Some guidelines for the kinematic design of new manipulators[END_REF].

Identification of cuspidal robots and classification

The identification of cuspidal robots is one of the most important issues to solve. When a new robot is designed or even when an existing robot is modified, it is necessary to know if the resulting robot will be cuspidal or not before using it. The first important result in the identification of cuspidal robots was found in 1995: the existence of a point in the workspace where three inverse geometric solutions coincide indicates that the robot is cuspidal (El [START_REF] Omri | How to recognize simply a nonsingular posture changing 3-dof manipulator[END_REF]. The formal mathematical proof is not detailed here, it relates on the facts reported in section 2.4. A point with three coincident inverse geometric solutions can be identified in a planar cross-section of the workspace as a cusp point (hence the word cuspidal robot). Moreover, the existence of a point with three coincident solutions can be verified using the univariate polynomial derived to solve the inverse geometric model. For a 3-R manipulator, the existence of cusps can be determined from its fourth-degree inverse kinematic polynomial P (t) = at 4 + bt 3 + ct 2 + dt + e in t = tan( θ32 ) whose coefficients are function of the geometric parameters and of the variables R = x 2 + y 2 and Z = z 2 (see [START_REF] Kholi | Workspace analysis of mechanical manipulators using polynomial discriminant[END_REF] for more details on the derivation and properties of this polynomial). The condition for P (t) to have three equal roots can be set as follows:

   P (t, d 2 , d 3 , d 4 , α 2 , α 3 , r 2 , R, Z) = 0 ∂P ∂t (t, d 2 , d 3 , d 4 , α 2 , α 3 , r 2 , R, Z) = 0 ∂ 2 P ∂t 2 (t, d 2 , d 3 , d 4 , α 2 , α 3 , r 2 , R, Z) = 0 (3)
where d 2 , d 3 , d 4 , r 2 , α 2 , and α 3 are the geometric parameters of the robot. If at least one solution to this system exists, this means that the robot is cuspidal. More interestingly, one can try to derive a condition on the geometric parameters for the above system to have (real) solutions. This is very challenging but by doing so, a condition for a 3-R robot to be cuspidal could be found. One needs to eliminate the three variables t, R and Z. This task is not tractable in the general case but fortunately it becomes feasible (although still complex) once the angle values α 2 and α 3 are assigned to 90 • , i.e. in the particular case of orthogonal manipulators. We can go even further by looking for the conditions under which the number of real solutions changes. By doing so, one will obtain a set of bifurcation surfaces in the parameter space of orthogonal 3-R manipulators where the number of cusp points changes. Accordingly, such bifurcating surfaces can be regarded as sets of transition robots that divide the parameter space into domains where all robots have the same number of cusp points. The algebra involved in system (3) is too complex to be handled by commercial computer algebra tools. [START_REF] Corvez | Using computer algebra tools to classify serial manipulators[END_REF] resorted to sophisticated computer algebra tools to solve system (3) by normalizing with d 2 = 1 (without loss of generality) and first considering the more particular case r 3 = 0 (no offset along the last joint axis like the robot shown in fig. 1). They used Groebner Bases and Cylindrical Algebraic Decomposition [START_REF] Lazard | Solving parametric polynomial systems[END_REF], [START_REF] Collins | Quantifier elimination for real closed fields by cylindrical algebraic decomposition[END_REF] to find the equations of the bifurcating surfaces and the number of domains generated by these surfaces. A kinematic interpretation of this theoretical work was conducted by [START_REF] Baili | Classification of one family of 3R positioning manipulators[END_REF]: the authors analyzed global kinematic properties of one representative manipulator in each domain. Finally, only five different cases were found to exist and the true bifurcating surfaces were shown to take on the following explicit form [START_REF] Baili | Classification of one family of 3R positioning manipulators[END_REF]:

C 1 : d 4 = 1 2 (d 3 2 + r 2 2 - (d 3 2 + r 2 2 ) 2 -(d 3 2 -r 2 2 ) AB ) (4)
C 2 : d 4 = d 3 1 -d 3 B and d 3 < 1 (5) C 3 : d 4 = d 3 d 3 -1 B and d 3 > 1 (6) C 4 : d 4 = d 3 1 -d 3 B and d 3 < 1 (7)
where:

A = (d 3 + 1) 2 + r 2 2 and B = (d 3 -1) 2 + r 2 2 (8)
These four surfaces divide the parameter space into five domains with 0, 2 or 4 cusps. Figure 19 shows the plots of the surfaces in a section (d 3 , d 4 ) of the parameter space for r 2 = 1. The separating surfaces, which appear as curves there, are labelled with C i in accordance with the labels in equations ( 4) to (8). Plotting sections for different values of r 2 changes the size of each region but the general pattern does not change and the number of cells remains the same. There are two domains of non-cuspidal manipulators (domains 1 and 5), two domains of cuspidal manipulators with four cusps (domains 2 and 4) and one domain of cuspidal manipulators with two cusps. Figure 20 shows the cross sections of the workspace and the singular curves in the joint space, for one representative robot in each domain of the partition. The number of inverse geometric solutions in each region of the workspace is indicated. Figure 20 shows that robots in domain 1 have only two inverse geometric solutions. Also, they have a void in their workspace and they are non-cuspidal. In fact, it can be shown that all other robots have 4 inverse geometric solutions. The other non-cuspidal robots are in domain 5. They have a region with 4 inverse geometric solutions and no void. It is interesting to note that robots in domain 5 were in fact already identified in [START_REF] Wenger | Design of cuspidal and noncuspidal manipulators[END_REF], they correspond to the case 7 enumerated in section 4.1.

Figure 19. The four bifurcating surfaces and the five domains in the parameter space (section r 2 = 1).

The partition of the parameter space and the equations of the bifurcating surfaces allow us to define an explicit necessary and sufficient condition for an orthogonal manipulator with no offset along its last joint axis to be cuspidal. Indeed, Figure 19 shows that a manipulator is cuspidal if and only if it belongs to domains 2, 3 or 4. Thus, an orthogonal manipulator with no offset along its last joint axis is non-cuspidal if and only if:

             d 4 > 1 2 d 2 3 + r 2 2 - (d 2 3 +r 2 2 ) 2 -d 2 2 (d 2 3 -r 2 2 ) √ (d3+d2) 2 +r 2 2 √ (d3-d2) 2 +r 2 2 and d 3 > d 2 or d 3 < d 2 and d 4 < d3 d2-d3 (d 3 -d 2 ) 2 + r 2 2 (9)
It is worthnoting that this necessary and sufficient condition on the geometric parameters is not straighforward and not intuitive at all.

Case r3 = 0: the case of non-zero offset along the last joint axis has also been studied. The number of parameters to handle is 4 instead of 3 and the bifurcating surface equations get much more complicated: the equation of one of the bifurcating surfaces is a 12 th -degree polynomial in the square of the geometric parameters and contains 536 monomials! Because of this complexity, it is difficult to derive an algebraic condition like (9) for a robot to be cuspidal . Figure 21 shows a section of the parameter space at r 2 = 0.3 and r 3 = 0.8. Numerals indicate the numbers of cusps in the domains. It turns out that a robot with non-zero joint offset along its last joint axis may have up to 8 cusps. Such a robot is shown in Figure 22.

Note1 : the existence of a cusp point is a sufficient condition for a robot to be cuspidal but it is not necessary in general. The reason is that the presence of a cusp point provides a way of defining a non-singular change of posture in a local way (the encircling path can be made as close as possible to the cusp point). In theory, there could exist a more global way of defining a non-singular change of posture. Figure 23 shows a workspace pattern that could enable a non-singular change of posture in the absence of any cusp point. This global non-singular change of posture can be interpreted using a comparison with a figure-eight race track where the crossroads is realized with a bridge, i.e. there are two levels at the crossroads. Each level is associated with a posture. Starting from the crossroads on the bridge (level 1), the track is followed until the crossroads at the same horizontal position but under the bridge is reached (level 0). In fact, it turns out that the existence of a cusp point is a necessary and sufficient condition for a 3-R orthogonal robot to be cuspial and consequently the pattern shown in Figure 23 cannot exist for these robots. This can be shown by verifying that for one arbitrary robot in each domain of the parameter space associated with no cusp, there is only one inverse geometric solution in each aspect. It is likeable that this result still stands for general 3-R robots (without orthogonal joint axes). On the other hand, a planar parallel cuspidal robot was shown in [START_REF] Coste | Non-singular change of assembly mode without any cusp[END_REF] to feature a joint space pattern as in Figure 23 (see section 5.2).

Note2 : 3-dof robots with one prismatic joint can be classified in a similar way. In fact, the equations will be simpler and such robots are more likely to be non-cuspidal because their inverse geometric model can be often solved in a cascade of two quadratics [START_REF] Pieper | The Kinematics of Manipulators Under Computer Control[END_REF]. Note that any 3-dof robot with more than one prismatic joint is always non-cuspidal because its inverse geometric model admits two solutions at most (only one for a 3-P robot) [START_REF] Pieper | The Kinematics of Manipulators Under Computer Control[END_REF].

5 Higher-degree-of-freedom robots and parallel robots

6-dof serial robots

The results pertaining to 3-R robots also hold for 6-R robots with a spherical wrist (i.e, with their last three joint axes intersecting at a common point) because the singularity analysis of the wrist can then be decoupled from that of the regional structure. In section 1.3, we reported the story of the IRB 6400C robot. This robot, shown in Figure 24, has a spherical wrist and its regional structure is an orthogonal 3R robot that can be shown to be cuspidal. Note that the main objective of this new robot design was to save space along the assembly lines and this is why its first joint axis is horizontal instead of vertical [START_REF] Hemmingson | New Robot Improves Cost-Efficiency of Spot Welding[END_REF]. This was a good idea but at the time the engineers of ABB designed their new robot, the classification results were not published. It would be interesting to attempt a new design, keeping the orthogonal architecture with its first axis horizontal but tuning the length parameters in order that the robot falls in one of the interesting classes of non-cuspidal orthogonal robots described by Zein et al. (2006a). On the other hand, there is no general result about the enumeration of cuspidal 6-dof manipulators with non-spherical wrist. One of the reasons is the difficulty in analyzing the singularities of general 6-R robots, which depend on four joint variables instead of two in 3-R robots. We think that 6-R manipulators are very likely to be cuspidal, even if the simplifying geometric conditions listed in section 4.1 are satisfied. This is because the inverse kinematics of most 6-dof manipulators with nonspherical wrist is a polynomial of degree higher than 4, which is more likely to admit triple roots. Further research work is required before stating more definitive results but several examples of simple 6-R cuspidal robots with non-spherical wrist exist. One of these robots is the GMF P150 shown in Figure 25 used in the automotive industry for car painting (a similar version exists by COMAU). This robot is close to a PUMA robot, the only difference being the presence of a wrist offset. El Omri showed that without taking account the joint limits, this robot has 16 inverse kinematic solutions and only two aspects [START_REF] Omri | Kinematic Analysis of Robot Manipulators[END_REF]. Thus, it is cuspidal. Another example is the ROBOX painting robot studied by [START_REF] Zoppi | Effective backward kinematics for an industrial 6R robot[END_REF] (see Figure 26). The kinematic architecture is very close to the GFM P150 but the wrist offset is not along the same wrist axis. This cuspidal robot has also 16 inverse kinematic solutions and only two aspects.

If the classification of 6-dof cuspidal and non-cuspidal robots is far from being simple, it is possible to enumerate a set of non-cuspidal robots, namely, those whose inverse geometric polynomial can be solved with quadratics or linear equations in cascade. Such robots were enumerated by [START_REF] Mavroidis | Structural parameters which reduce the number of manipulator configurations[END_REF].

Parallel robots

A parallel robot may change its assembly-mode without encountering an output singularity. As first observed in 1998, a parallel robot may be cuspidal in the sense that it may change its assembly-mode (an assembly mode is associated with a solution to the direct geometric problem) without crossing an output singularity [START_REF] Innocenti | Singularity-free evolution from one configuration to another in serial and fully-parallel manipulators[END_REF], [START_REF] Wenger | Workspace and assembly-modes in fully parallel manipulators: A descriptive study[END_REF]. As shown by [START_REF] Mcaree | An explanation of never-special assembly changing motions for 3-3 parallel manipulators[END_REF] and explained in details by [START_REF] Zein | Non-singular assembly-mode changing motions for 3-RPR parallel manipulators[END_REF], if a parallel robot has 3 coincident assembly modes, thus defining a cusp point in a section of its joint space (not in the workspace this time), then this robot is cuspidal. A non-singular change of assembly-mode can then be accomplished by encircling a cusp point in a section of the joint space (McAree and Daniel, 1999), [START_REF] Zein | Non-singular assembly-mode changing motions for 3-RPR parallel manipulators[END_REF]. Figure 27 shows the singularity curves and a non-singular assembly-mode changing path in a section ρ 1 = 17 of the joint space for the 3-RPR robot (the underlined letter refers to the actuated joint) analyzed in [START_REF] Innocenti | Singularity-free evolution from one configuration to another in serial and fully-parallel manipulators[END_REF] and [START_REF] Mcaree | An explanation of never-special assembly changing motions for 3-3 parallel manipulators[END_REF].

Figure 27. A non-singular assembly-mode changing path encircling a cusp point in a section of the joint space for a 3-RPR planar parallel robot.

Because the kinematic equations of a parallel manipulator are very complex, it seems very difficult to derive general geometric conditions for a parallel robot to be cuspidal. However, some results are available for planar parallel robots. One of these results claims that to be cuspidal, a 3-RPR robot parallel planar robot should not have similar platform and base trian-gles [START_REF] Mcaree | An explanation of never-special assembly changing motions for 3-3 parallel manipulators[END_REF], [START_REF] Kong | Determination of the uniqueness domains of 3-RPR planar parallel manipulators with similar platforms[END_REF] but this is false if the legs are RRR instead of RPR [START_REF] Wenger | Uniqueness domains and regions of feasible paths for cuspidal manipulators[END_REF]. Another interesting result claims that a generic 3-RPR robot has always two aspects [START_REF] Husty | Non-singular assembly mode change in 3-RPR parallel manipulators[END_REF], [START_REF] Coste | A simple proof that generic 3-RPR manipulators have two aspects[END_REF]. Since such robots have up to six assembly-modes, this shows that they have more than one assembly-mode in one of their aspects, which thus allows them to accomplish non-singular assembly-mode motions. The last interesting result is a proof that a planar parallel robot can be cuspidal while there are no cusp points at all [START_REF] Coste | Non-singular change of assembly mode without any cusp[END_REF], see Note1 in section 4.2 and Figure 23. More details on cuspidal planar parallel robots can be found in (Zein et al., 2006b), [START_REF] Zein | Singular curves in the joint space and cusp points of 3-RPR parallel manipulators[END_REF] and [START_REF] Zein | Non-singular assembly-mode changing motions for 3-RPR parallel manipulators[END_REF].

Quite few results exist for 6-dof parallel robots. Out of the octahedral Gough-Stewart platform studied by [START_REF] Mcaree | An explanation of never-special assembly changing motions for 3-3 parallel manipulators[END_REF] and J.P. Merlet who showed the existence of non-singular assembly-mode changing motions for this robot, the only other available result, to the author's knowledge, was published in [START_REF] Caro | Non-singular assembly mode changing trajectories of a 6-dof parallel robot[END_REF]. In this paper, a non-singular assembly-mode changing path was generated for a 6-dof 3-PPPS parallel robot.

If the interest of designing a cuspidal serial robot is questionable, a parallel robot that is cuspidal is interesting since the robot can thus move in a larger part of its workspace without crossing any output singularity [START_REF] Wenger | Uniqueness domains and regions of feasible paths for cuspidal manipulators[END_REF], [START_REF] Zein | Non-singular assembly-mode changing motions for 3-RPR parallel manipulators[END_REF].

Conclusions

The results presented in this chapter can be summarized as follows. Cuspidal robots, which were first discovered in 1988, have multiple inverse geometric solutions that are not separated by a singular surface. In the joint space, additional surfaces, called the characteristic surfaces, divide the aspects and separate the solutions. These surfaces are used to define new uniqueness domains and regions of feasible paths in the workspace. The definitions are general and stand for any serial, non-redundant robot with or without joint limits. For 3-dof robots, it is possible to calculate and plot these characteristic surfaces, uniqueness domains and regions of feasible paths. If the first joint is revolute and unlimited, 2-dimensional plots are sufficient. Because there is no simple algebraic definition, these sets must be calculated numerically.

A 3-R robot is non-cuspidal as soon as its first two or last two joint axes are parallel or intersect, or if the three joint axes are mutually orthogonal and the first joint offset is equal to zero. But an orthogonal manipulator with its last joint offset equal to zero may be cuspidal.

A robot is cuspidal if there is at least one point where three inverse geometric solutions coincide. For 3-dof robots, such points appear as cusp points in a cross section of the workspace. In general, the existence of a cusp point is only sufficient for a robot to be cuspidal but for the particular case of 3-R orthogonal robots, this condition is also necessary. The full partition of the parameter space of 3-R orthogonal robots is possible. Bifurcating surfaces divide the parameter space into domains where all robots have the same number of cusp points.

For 3-R orthogonal robots with no joint offset along their last joint axis, it is possible to derive an explicit DH-parameter based necessary and sufficient condition for a robot to be cuspidal. For general 3-R orthogonal manipulators, the classification is much more complex and does not lend itself to explicit conditions.

Little research work has been conducted on 6-R cuspidal robots. It appears that 6-R robots with non-spherical wrist are very likely to be cuspidal, even if two joint axes intersect or are parallel. However, there is still much work to do before having definitive geometric conditions for general 6-R robots. Resorting to some transversality theorems used by singularity theorists would help going further, providing that we remain in the generic case [START_REF] Pai | Genericity and singularities of robot manipulators[END_REF], [START_REF] Donelan | Singular phenomena in kinematics[END_REF], [START_REF] Donelan | Singularities of regional manipulators revisited[END_REF]. So the first step would be to enumerate all 6-R generic robots.

Finally, the issue of classifying cuspidal and non-cuspidal parallel robots is still much more difficult and remains open. As shown in [START_REF] Coste | Non-singular change of assembly mode without any cusp[END_REF], a parallel robot may be cuspidal without having any cusp, so that we lack a necessary and sufficient condition for the classification of parallel robots.

Figure 1 .

 1 Figure 1. A serial robot with three revolute joints.

Figure 2 .

 2 Figure 2. An anthropomorphic robot.

Figure 3 .

 3 Figure 3. Four postures for the anthropomorphic robot, from left to right: (elbow up, shoulder left), (elbow up, shoulder right), (elbow down, shoulder right), (elbow down, shoulder left).

Figure 4 .

 4 Figure 4. A SCARA robot.

Figure 5 .

 5 Figure 5. Aspects of the SCARA robot in the joint space (left) and workspace (right).

Figure 6 .

 6 Figure 6. Singularity curves for the 3-R cuspidal robot shown in fig. 1 (left) and its projection in the workspace (right).

Figure 7 .

 7 Figure 7. Two solutions in each aspect and a non-singular path joining two solution in A 1 .

Figure 8 .

 8 Figure 8. The four postures of the 3-R cuspidal robot at point P .

Figure 10 .

 10 Figure 10. A non-singular path joining two distinct solutions.

Figure 11 .

 11 Figure 11. Non-singular posture changing path in the workspace.

Figure 12 .

 12 Figure 12. The splitted configuration space cut along its folds and shown in the two aspects. A non-singular posture changing path is shown in aspect A1 (above).

Figure 13 .

 13 Figure 13. An infeasible path for the cuspidal robot.

Figure 14 .

 14 Figure 14. Use of the aspects for cutting trajectories for a non-cuspidal robot.

  studied in Figures 6-8, the set of characteristic surfaces {CS i } associated with A *

Figure 15 .

 15 Figure 15. The characteristic surfaces (below) of the cuspidal robot of fig. 1 and correspondence with the segments of the internal boundary in the workspace (above).

Figure 16 .

 16 Figure 16. The characteristic surfaces divide the aspects into smaller sets.

Figure 20 .

 20 Figure 20. Workspace topologies in each domain.

Figure 21 .

 21 Figure 21. Partition of the parameter space for 3-R robots with joint offsets, section at r 2 = 0.3, r 3 = 0.8.

Figure 22 .

 22 Figure 22. A 3-R orthogonal robot with 8 cusps (d 2 = 1, d 3 = 0.91, d 4 = 0.94, r 2 = 0.3, r 3 = 0.9).

Figure 23 .

 23 Figure 23. A workspace pattern that would allow a non-singular posture changing path in the absence of cusps.

Figure 24 .

 24 Figure 24. The IRB 6400C robot.

Figure 25 .

 25 Figure 25. The GMF P150 robot.

Figure 26 .

 26 Figure 26. The ROBOX robot.


Katia Lupinetti

Franca Giannini

Marina Monti

Jean-Philippe Pernot

Automatic extraction of assembly component relationships for assembly model retrieval

come   L'archive ouverte pluridisciplinaire

In this context, starting from assemblies stored in STEP format without information on kinematic relationships and constraints, this paper addresses the way the assembly component relationships can be extracted to better support the assembly retrieval. The idea is to exploit interface relationships through a dedicated geometric reasoning. In particular, we propose a framework for the global/partial retrieval of assembly models according to different user requirements at different levels of details.

The extracted data are then encoded in a multi-level assembly descriptor called Enriched Assembly Model (EAM) that is organized in four main levels: statistics, structure, interface and shape. This paper focuses on the interface layer, in particular on the automatic computation of different types of relationships that exist between assembly components.

The interface layer represents the motions of a part with respect to another one. It encodes knowledge starting from part contacts and then rising to equivalent joint using four levels namely the contact, joint, synthesis and mechanism levels. The lowest level encodes all the faces involved in the contact between two parts and their corresponding degree of freedom (DOF). Here, contacts can be considered as constraints that limit the DOF according the involved geometric entities, i.e. points, curves or surfaces. The joint level, i.e. the second one, characterizes the resulting movement between two parts considering all their contacts. Then, the synthesis level groups support parts. In this layer, the collection of parts that form bearings, couplings, shaft or pattern of screws are considered as a unique mechanism for allowing a precise movement. The highest level corresponds to the assembly mechanism, i.e. the DOF of a part considering all the linked parts in the assembly. In this paper, the two lowest levels are described: contact and joint.

Once the information extracted and stored within the socalled EAM, the assembly model retrieval can start. The use of a multi-level descriptor advantageously enables the detection of similarities according to various aspects. For instance, Fig. 1 shows two translation joints (i.e. same functionality) defined in two different ways involving different surfaces in contact. The two models are different both at the shape and at the contact levels but similar at the kinematic one. The proposed multi-level descriptor allows to capture and distinguish these configurations and can be very helpful when considering the retrieval of similar assembly models with respect to specific criteria (e.g. type of surfaces in contact). The rest of the paper is organized as follows. Section 2 provides an overview of the works related to the characterization and extraction of assembly relationships with a particular focus on those techniques designed for assembly retrieval purposes. In section 3, the proposed Enriched Assembly Model (EAM) descriptor is introduced, while in section 4 the technical background and the reasoning techniques to extract the assembly relationships are introduced. Some results are presented in section 5 and section 6 ends the paper providing conclusions and highlighting future works.

Related work

Several works exist for the extraction of assembly contacts in different application domains. In the assembly retrieval field, Chen et al. [START_REF] Chen | A flexible assembly retrieval approach for model reuse[END_REF] used Degree Of Freedom (DOF), kinematic pair and geometric mating to enrich their assembly descriptor. However, they are able to extract all this information for some kinematic-pairs while other complicated kinematic-pairs have to be labeled manually. Yang et al. [START_REF] Yang | Virtual assembly technologies based on constraint and DOF analysis[END_REF] proposed a simulation system for assembly process based on the constraint recognitions, confirmations and navigation. Constraint detection is handled in the recognition phase, while the other phases compute some transformation matrices to move the assembly components in virtual systems. The recognition phase detects six types of constraints considering geometric information of the involved elements and it is based on the equivalence between them and the DOF. However it requires user intervention to track the position and the orientation of the components.

An automatic method to extract kinematic information from assembly models is developed by Park and Oh [START_REF] Park | Kinetic Model Extraction from a Geometric Model[END_REF]. They assert that most of the assembly geometric models have just revolute and prismatic joints. Their procedure is divided in three main steps. First, it identifies the regions of contact using the collision detection of boxes and parallel computation to improve the speed of calculation. Focusing on revolute joints, the second step aims to identify the contact surface of the cylinder shape and the creation of the center axis. Last step decides the type of joint using collision detection. Even though their approach identifies joints automatically, the proposed scenario it too restricted. Swain et al. [START_REF] Swain | Extended liaison as an interface between product and process model in assembly[END_REF] have defined an extended liaison to integrate the information between the product model and the assembly process. This structure is able to identify the assembly process of riveting, welding, scree fastening, bolt fastening and gluing. The proposed procedure is able to extract the liaison details automatically from assembly models, but its main limit is the complexity of the algorithm.

For finite element analysis, Shahwan et al. [START_REF] Shahwan | Qualitative behavioral reasoning from components' interfaces to components' functions for DMU adaption to FE analyses[END_REF] described a qualitative reasoning process to detect component interfaces from assembly models. Their method is based on the definition of conventional and functional interfaces. Unfortunately, the geometric information intrinsically contained and available in the assembly model are not sufficient for the reasoning process and additional data formalized in other structures as ad-hoc ontologies are required. [START_REF] Kim | Mereotopological assembly joint information representation for collaborative product design[END_REF] presented ontology based reasoning techniques for representing and differentiating assembly joints that are similar from geometric and topological point of view. They gave definitions and theorems for characterizing assembly joints in mereotopological representation (a formal ontology that combines mereological and topological concepts) requiring various data as fastener attribute, screw/nut head and body; but it is not mentioned how this information are obtained from the assembly model.

Enriched assembly model

When looking for an existing assembly in a database, and depending on the objectives of the retrieval, a designer may be interested in different assembly characteristics. Thus, to support assembly retrieval with different search keys at different LOD, we define a multi-level assembly descriptor, the so-called Enriched Assembly Model (EAM). The EAM has four information layers: statistics, structure, interface and shape (Fig. 2). The statistics layer contains values that roughly characterize and discern assembly models. Number of subassemblies, number of principal parts, number of fasteners, number of thin parts and number of patterns of a specific type (e.g. linear, rotational or reflective patterns) are attributes associated to the entire assembly as well as to each subassembly. On the other hand, for matching purpose, the parts in the assembly can be filtered according to the percentage of a specific type of surface or the number of maximal faces of a specific type of surface. Then, the number of a specific joint type or the number of elements in contact for a specific contact type is considered to differentiate the type of joint present in an assembly model.

The structural layer encodes the hierarchical assembly structure as specified at the design stage. In this organization, the structure is represented as a tree where the root corresponds to the entire assembly model, the intermediate nodes are associated with the sub-assemblies and the leaves characterize the parts. Attributes to specify parts arrangement (regular patterns of repeated parts) are attached to the entire assembly and its sub-assemblies [START_REF] Lupinetti | Regular patterns of repeated elements in CAD assembly models retrieval[END_REF].

The interface layer is the main focus of this paper and it specifies the relationships among the parts in the assembly. It is divided in four levels. The lowest level, i.e. the contacts level, encodes all the faces involved in the contact between two parts and the degree of freedom between those faces. Joint level describes the motion(s) resulting from several contacts between two parts, while synthesis level gathers together collection of parts that belong to the same functionality group. The highest level, i.e. the mechanism level, characterizes the overall motion of a part when considering all the associated joints.

The shape layer categorizes the shape of an assembly and its constitutive parts using several dedicated descriptors. Using several shape descriptors helps answering different assembly retrieval scenario, which can consider different shape characteristics.

A complete EAM, i.e. with the four layers, is computed only for the models stored in the databases on which the search has to be performed. However, for what concerns the query, only those layers involved in the retrieval are computed and exploited, thus reducing the complexity of the system.

Interface layer

The interface layer aims at describing the relationships between two parts of an assembly model. Starting from the contacts involved between parts and then reasoning on the relative DOF, the relative motion of a part with respect to another one can be characterized. To formalize this knowledge, four levels are defined: contact, joint, synthesis and mechanism levels. The contacts level encodes all the faces involved in the contact between two parts and the degree of freedom between those faces. Joint level describes the motion(s) resulting from several contacts between two parts. Since the motion of a component in the assembly might be realized through different technologies (e.g. bearings, coupling and drive shaft), an additional level is introduced, the synthesis one. In this level, the parts which belong to the same equipment are grouped together thus creating a higher level of details. A further level is defined, the mechanism level, to define the overall motion of a part respect to the entire model. Fig. 3 shows an example of the structure of the interface layer. An assembly model is illustrated in Fig. 3(a problem, solving it by the exploitation of a probabilistic technique matching [START_REF] Bomze | Annealed replication: a new heuristic for the maximum clique problem[END_REF].

Some results are illustrated in Fig. 5. The first model used as query for the retrieval is a landing gear and the query requests models similar at the joint level. While the second model is a flange and, in this case, the requests is for models similar at the contact level. The retrieved models are very similar at local level, while the global similarity is represented by a rough measure. Two models are locally similar if a portion of the query model is present in the compared model. In both the examples, the last retrieved models are indeed locally similar. The structure of the hydraulic cylinder (last retrieved model for the first example) has the same movement (rotations) of the tires in the query, while the radial pistons (last retrieved model for the second example) have the same contacts given by the patterns of screws and bolts as in the flange model.

The rate for the ranking is the ratio between the number of matched parts and the number of parts in the query models. This value is not accurate -because it considers only a parameter -but it is an index of the global percentage of the query in the retrieved models. With this meaning, some retrieved landing gears have a low global measure, but it is due to some additional components for which the models diverge. In this sense, the models are rather different at the joint level but should be more similar at a higher level of detail. Fig. 5. Similar models at the joint level and at contact level

Conclusion and future works

The information concerning the relationships between the components of an assembly model are crucial in several domains. However, for different reasons, those information are not always available. Tools for their automatic computation are important but it is not an easy task and some existing tools often require major user interactions. .

Starting from the basic contacts between two parts, we define a first class of equivalence able to describe the motion between the involved parts. The simple results of the landing gears show the importance of additional levels for the equivalence. In that frame, other landing gears have the same final motion but involving additional components, thus the global measure is low (in some cases it is less then 0.50). To retrieve them with a higher score, fasteners and auxiliary parts should be neglected considering only the final motion between the main parts. This objective is addressed by the other levels of equivalence, the synthesis and the mechanism ones which have not been detailed in this paper. In this way, the landing gears designed with different components will be retrieved with a higher measure at the mechanism level and lower measure at the joint level.

Ongoing activities aim to improve the rules for the computation of the DOF of the contacts and for the identification of their equivalence concerning also the aspect ratio of the contact portions. For instance, a cylindrical contact with L >> r (where L and r are the cylinder length and radius respectively) could rotate along its axis, but it allows small rotations along other directions also. Another upgrading concerns the ability of recognizing if the kinematic system defined by two parts is isostatic or hyper-static. This kind of information is useful in simulation systems.

Fig. 1 .

 1 Fig. 1. (a) Translation by cylindrical faces; (b) Translation by planar face

  ) while Fig. 3(b) illustrates the four levels of the interface layer. The first row of Fig. 3(b) depicts the contacts through a graph structure, where the nodes identify the parts and the arcs represent the type of contacts. The portions of contacts, highlighted in red on Fig. 3(a), are formed by two planar and one cylindrical face, while the other junctions in the assembly involve only a cylindrical contact. For this reason, the graph representing the contact level has several arcs between some pairs of nodes. The second row of Fig. 3(b) corresponds to the joint level and represents the equivalent motion between two parts, thus the arc between nodes B and C supports an attribute value that indicates the rotation between the two corresponding parts of the assembly. The bar C and D are secondary parts and are inserted in the model to limit the final overall motion of B with respect to E, thus in the graph in the

Fig. 2 .

 2 Fig. 2. Enriched assembly model layer