arXiv:1204.5580v1 [cs.RO] 25 Apr 2012  Cusp Points in the Parameter Space of Degenerate 3-RP R Planar Parallel Manipulators  Montserrat Manubens  Institut de Rob ` otica i Inform ` atica Industrial, CSIC - UPC, Llorens i Artigas, 4-6, 08028 Barcelona, Spain mmanuben@iri.upc.edu  Guillaume Moroz  INRIA Nancy-Grand Est, 615, rue du jardin botanique, 54600, Villers-l ` es-Nancy, France guillaume.moroz@inria.fr  Damien Chablat  Institut de Recherche en Communications et Cybern  ́ etique de Nantes, UMR CNRS n 6597, 1 rue de la No  ̈ e, 44321 Nantes, France damien.chablat@irccyn.ec-nantes.fr  Philippe Wenger  Institut de Recherche en Communications et Cybern  ́ etique de Nantes, UMR CNRS n 6597, 1 rue de la No  ̈ e, 44321 Nantes, France philippe.wenger@irccyn.ec-nantes.fr  Fabrice Rouillier  INRIA Paris-Rocquencourt, Universit  ́ e Pierre et Marie Curie Paris VI 4, place Jussieu, F-75005 Paris, France fabrice.rouillier@inria.fr  This paper investigates the conditions in the design param- eter space for the existence and distribution of the cusp lo- cus for planar parallel manipulators. Cusp points make pos- sible non-singular assembly-mode changing motion, which increases the maximum singularity-free workspace. An ac- curate algorithm for the determination is proposed amend- ing some imprecisions done by previous existing algorithms. This is combined with methods of Cylindric Algebraic De- composition, Gr ̈ obner bases and Discriminant Varieties in order to partition the parameter space into cells with con- stant number of cusp points. These algorithms will allow us to classify a family of degenerate 3-RP R manipulators.  Keywords: kinematics, parallel manipulator, singulari- ties, cusp, discriminant variety, cylindric algebraic decom- position, degenerate 3-RP R, symbolic computation.  1   Introduction  In the past, singularities were believed to physically sep- arate the different assembly modes, meaning that for fixed joint values one could not find a path going from one assem- bly mode to another without crossing a singular configura- tion.   So the interest relied on considering the widest con- nected non-singular domain, called   aspect .   Innocenti and Parenti-Castelli pointed out in [1] that non-singular changes of assembly mode are possible, and McAree and Daniel showed in [2] that such changes are possible when triple roots of the Forward Kinematic Problem (FKP) exist. In [3] Zein, Wenger and Chablat showed that for the case of 3-RP R manipulators a non-singular change of assembly mode can be accomplished by encircling a cusp point, and Husty re- cently proved in [4] that the generic 3-RP R parallel manipu- lators without joint limits always have 2 aspects. From the algebraic point of view, the locus of cusp points can be described by means of symbolic equations. In order to avoid long symbolic-algebraic manipulations, these equations are usually solved by numerical approximation at an early stage, which may lead to small deviations that can be propagated along the process. However, there exist effi- cient symbolic-algebraic techniques that may leave the use of numerical methods to the last step. In particular, we will apply   Gr ̈ obner bases   [5] in order to adopt a more suitable equivalent system defining the same solution points. Lazard and Rouillier introduced the mathematical no- tion of   Discriminant Variety   (DV) [6], which is a variety of codimension 1 in the chosen parameter space whose com-
plement satisfies the property that over each connected com- ponent the given system has a constant number of solutions. The complement of this DV will be partitioned into cells by a  Cylindric Algebraic Decomposition   [7], also known as CAD. This paper is intended to illustrate both the performance of the new algorithm for the determination of the locus of cusp points and its combination with the forementioned al- gebraic techniques in the analysis of existence conditions and distribution along a 2-dimensional parameter space. Al- though the method can be applied to more general manip- ulators (see [8]), such performance will be exemplified on a family of degenerate 3-RP R manipulators, detailed in Sec- tion 2. The algorithm for the cusp point determination, which is one of the main contributions of the paper, is given in Sec- tion 3, where it is compared to other previous algorithms. Section 4 outlines some of the exploited algebraic objects such as the DV. In Section 5 the previous procedures are combined with the CAD to partition a 2-dimensional space with regard to the associated number of cusp points, which leads us to analyze a complete family of degenerate 3-RP R manipulators that depend on one geometric parameter. This section also illustrates some applications of the presented strategy to robot design. The paper concludes in Section 6.  2   A class of degenerate 3-RP R  Let us describe the family of manipulators on which the strategies presented along the paper will be exemplified. A general 3-RP R manipulator is a 3-degrees-of-freedom pla- nar parallel mechanism that has two platforms connected by three RP R rods, with the prismatic joints being actuated and the revolute ones being passive. Without loss of generality we can assume the absolute reference frame to be such that the base points of the leg rods are   A 1   = ( 0 ,   0 ) ,   A 2   = ( A 2 x ,   0 )  with   A 2 x   >   0, and   A 3   = ( A 3 x ,   A 3 y ) . If   B 1 ,   B 2   and   B 3   are the corresponding points on the moving platform, then the geo- metric parameters associated to this manipulator are the val- ues   A 2 x ,   A 3 x ,   A 3 y , the lengths   d 1   =   ‖ B 1 B 2 ‖ ,   d 3   =   ‖ B 1 B 3 ‖ , and the angle   β   =   ̂   B 2 B 1 B 3 .   The input-space is then formed by  ρ ρ ρ   = ( ρ 1 ,   ρ 2 ,   ρ 3 )   ∈   R 3 , where   ρ i   ≥   0 are the leg rod lengths, and the output-space is formed by the poses of the moving platform   x   = ( x ,   y ,   α ) , where   B 1   = ( x ,   y )   and   α   is the angle of vector   B 2   −   B 1   relative to   A 2   −   A 1 .   We define   ( s α ,   c α ) ,  ( s β ,   c β )   and   ( s α + β ,   c α + β )   to denote the sines and cosines of  α ,   β , and   ( α   +   β ) , respectively. Then the forward kinematics of a general 3-RP R manipulator is defined by the system of equations  x 2   +   y 2   −   ρ 2 1   =   0  ( x   +   d 1   c α   −   A 2 x ) 2   + ( y   +   d 1   s α ) 2   −   ρ 2 2   =   0  ( x   +   d 3   c α + β   −   A 3 x ) 2   + ( y   +   d 3   s α + β   −   A 3 y ) 2   −   ρ 2 3   =   0 .  (1) For these manipulators, Hunt showed that the FKP ad- mits at most 6 assembly modes [9], and several authors [10, 11] proved independently that the system associated to the FKP can be reduced to a polynomial of degree 6.   The 3- RP R manipulators for which the degree of this characteris-  PSfrag replacements  A 1   A 2  A 3  B 1  B 2  B 3  α β ρ 1  ρ 2  ρ 3  d 1  d 3  x y  Fig. 1.   Example of degenerate 3-RP R.  tic polynomial decreases are known as   analytic   or   degener- ate   [12,13], because the Cramer system in Gosselin’s method degenerates. In this paper we will focus on a class of degen- erate 3-RP R manipulators whose base and moving platforms are congruent triangles, with the moving triangle being re- flected with respect to the base one, as that of Fig. 1. This class of manipulators was first studied by Wenger, Chablat and Zein in [14].   Their mathematical description requires the addition to the initial Eqn. (1) of the following geometric constraints:  d 1   =   A 2 x  cos ( β ) =   A 3 x / d 3  sin ( β ) =   − A 3 y / d 3 .  (2) Therefore, the system of equations defining this family of de- generate 3-RP R manipulators, formed by Eqns. (1) and (2), will be denoted as  F ( ρ ρ ρ ,   x ) =   0 .  Generically, we will refer to this system by   F .   Whenever concrete values for the geometric parameters are considered, these will be specified. Finally, the notation   | ( ρ ρ ρ , x )   will stand for the evaluation on real values   ( ρ ρ ρ ,   x ) .  3   Cusp locus determination  In this section we describe the cuspidal locus and an- alyze the usual methods for their determination. After that we propose a more accurate approach and compare it to the previous ones in a simple example. Let us assume that a specific manipulator, whose geo- metric parameters have been set into   F , has been designated. Then, we denote the associated   configuration space   by  C   ( F ) =   { ( ρ ρ ρ ,   x )   ∈   R 6   :   F | ( ρ ρ ρ , x )   =   0 } .  The Jacobian matrix of   F   with respect to the output vari- ables is denoted as   J x ( F ) =  (   ∂ F  ∂ x  ∂ F  ∂ y  ∂ F  ∂α  )  .   The configura-
tions where its determinant is zero are called   parallel singu- lar configurations , or   type 2 singularities . On these configu- rations the manipulator shows a loss of control. The   parallel singular locus   of our manipulator is a 2-dimensional space that can be described (see [15]) as  Σ ( F ) =   { ( ρ ρ ρ ,   x )   ∈   C   ( F )   :   J x ( F ) | ( ρ ρ ρ , x )   is rank deficient } .  For simplicity, we will refer to this set as the   singular locus . With this setting we now define the   cuspidal locus   as  κ ( F ) =   { ( ρ ρ ρ ,   x )   ∈   C   ( F )   :   ρ ρ ρ   root of exact multiplicity 3 of   F } ,  i.e. the triple roots of the FKP. Observe that   κ ( F )   ⊂   Σ ( F ) , since the Jacobian   J x ( F )   is rank deficient on the roots of mul- tiplicity three of   F . It is known that in the proximity of cusp points a non-singular change of assembly mode can be made. Figure 2 shows a cusp point   κ   and a non-singular path con- necting two different assembly modes ( p 1   and   p 3 ). We shall note, however, that both the singular and the cusp locus are quite difficult to visualize in the 6-dimensional   ( ρ ρ ρ ,   x ) -space. So for mechanisms with at most one inverse kinematics so- lution, as is the case for the 3-RP R, we will actually project them onto the input-space instead.  3.1   Usual methods for the cusp computation  Let us revise the two main algorithms that have been more commonly used in the determination of the locus of cusp points for a given manipulator. The following method, introduced by Wenger and Chablat in [13], and anallytically derived in [16], has been used for the degenerate 3-RP R ma- nipulators.   It was inspired on an approach developed by Hern ́ andez et al in [17] for other robots.  Algorithm 1   by Wenger and Chablat [13]  1. Reduce   F   (by successive resultants) to a single equation  g ( t ) =   0, with   t   =   tan ( α / 2 )   and coefficients in   ρ ρ ρ . 2. Equations of triple roots of   g G   =   { g   =   0 ,   ∂ g  ∂ t   =   0 ,   ∂ 2   g  ∂ t 2   =   0 } . 3. Equations of strictly triple roots of   g G   =   G   ∪ {   ∂ 3 g  ∂ t 3   6   =   0 } . 4.    ̃ G   =   Eliminate   t   from   G   and solve the remaining system for real values of   ρ ρ ρ . 5. Solve    ̃ G .  This strategy reduces the problem to the computation of the strictly triple roots of one single univariate polynomial   g . However, the constraint added in step 3 makes the computa- tion quite hard, and thus this step is often removed. Another commonly used method, described by McAree and Daniel in [2], makes use of the series expansion of   F .  PSfrag replacements   p 1  p 2  p 3  κ π ρ ( p i )  π ρ ( κ )  Fig. 2.   Cusp point   κ   as a triple root of the FKP and non-singular path linking upper and lower solutions of the FKP.  Algorithm 2   by McAree and Daniel [2]  1. Series expansion of   F  ∆ F   =   ∂ F  ∂ x   ∆ x   +   ∂ F  ∂ ρ ρ ρ   ∆ ρ ρ ρ   +   1  2   ∆ x T  (   ∂ 2 F  ∂ x 2  )  ∆ x   +   ∆ x T  (   ∂ 2   F  ∂ x ∂ ρ ρ ρ  )  ∆ ρ ρ ρ +  1  2   ∆ ρ ρ ρ T  (   ∂ 2   F  ∂ ρ ρ ρ 2  )  ∆ ρ ρ ρ   +   . . .  2. Compute configurations where 1st and 2nd order con- straints are rank deficient, i.e. solve  v T  (  u   ∂ 2 F  ∂ x 2  )  v   =   0, where   v   is a unit vector in right kernel of   ∂ F  ∂ x   , and   u   is a unit vector that spans left kernel.  This second strategy reduces the problem to the resolu- tion of some quadratic equations, but it also requires to find the unit vectors   u   and   v , which may hinder the computation. These algorithms are commonly used in the cusp locus determination. However, both have drawbacks related to the non-cuspidality of some resulting points:  •   Since the polynomial   g   obtained by Algorithm 1 is the result of several projections, some of the obtained points may correspond to the projection of complex (not real) solutions, as we will see later on.  •   Step 3 usually needs to be removed from Algorithm 1 in order to avoid slow-processing.  •   Algorithm 2 does not constrain the multiplicity of the solutions to be exactly 3, so it may obtain higher multi- plicity ones. Regardless of that, in [3] it is shown that ad- ditional spurious solutions may be produced for generic 3-RP R manipulators. Therefore, both methods can only provide sufficient condi- tions for the cuspidal locus but not always necessary ones.  3.2   Improved method  Despite the fact that the formulation of the cusp locus is quite simple, the associated system of equations usually contains many equations in many unknowns, whose resolu- tion can take long computations and even lead to abnormal termination for not too complex examples. So the methods described previously were introduced as simple, though not accurate, alternatives to the symbolic resolution. However, we can now get over some of these difficulties with current powerful symbolic algebra tools that fix the deficiencies of the algorithms detailed above.
The approach that we propose is an evolution of   [18] by Moroz et al., inspired on the results of [19].   The main difference of the proposed method compared to that of [18] is the introduction of the   saturation   operator to remove the quadruple roots.  Algorithm 3   Proposed method  1. Equations of double roots of   F   w.r.t.   ρ ρ ρ  D F   =   F   ∪ { det ( J x ( F )) =   0 }  2. Equations of triple roots of   F   w.r.t.   ρ ρ ρ  T F   =   D F   ∪ { det ( m )   :   m   maximal minors of   J x ( D F   ) }  3. Equations of quadruple roots of   F   w.r.t.   ρ ρ ρ  Q F   =   T F   ∪ { det ( m )   :   m   maximal minors of   J x ( T F   ) }  4. Saturate   T F   by   Q F  C F   =   sat ( T F   ,   Q F   )  5. Solve   C F   for real values of   ( ρ ρ ρ ,   x )  Given the system defining the mechanism   F , it computes iteratively the equations   T F   and   Q F   of triple and quadruple roots   ρ ρ ρ   of   F , respectively. Then, we use saturation. Given two polynomial systems   S 1   and   S 2 , sat ( S 1 ,   S 2 )   is an algebraic operator that returns a polynomial system whose solution set is the closure of the solutions of the first system after remov- ing those of the second one. If   V   ( S i )   denotes the solution set of   S i , it is satisfied that  V   ( sat ( S 1 ,   S 2 )) =   V   ( S 1 )   \   V   ( S 2 ) .   (3) In general, the saturation ensures that all roots of   S 2   are re- moved. However, in specific cases, some points can remain due to property of Eqn. (3) for which we can only obtain  V   ( S 1 )   \   V   ( S 2 )   instead of   V   ( S 1 )   \ V   ( S 2 ) , which can differ by a null-measure set that can easily be removed afterwards. Fur- ther details on the saturation and its geometric interpretation can be found in [5]. Although we are only interested in real (feasible) solu- tions, we shall note that the polynomial system obtained after saturating has real coefficients and thus its solution set could contain some complex (not real) roots. For this reason we need to solve the final cusp system   C F   in the real field. This is done by using the   RootFinding   Maple package. With Algorithm 3 the previous drawbacks are amended:  •   When computing the saturation of   T F   by   Q F   , the points of multiplicity 4 or higher are removed, and so we can guarantee that only the cusp locus is obtained.  •   By solving   C F   for   ( ρ ρ ρ ,   x ) , instead projecting onto the   ρ ρ ρ - space, we avoid having biased points produced by the projection of complex (not real) solutions.  •   Furthermore, solving   C F   in the real field ensures that no other spurious complex solutions are considered.  3.3   Case study comparison  Let us now compare the performance of both Algo- rithm 1 without step 3 and the proposed Algorithm 3 on a simple case of degenerate 3-RP R in order to contrast their results.   However, let us clarify that both the formulation and the proposed algorithm apply to other more general ma- nipulators (see [8]). We set the geometric parameter values  A 2 x   =   1,   A 3 x   =   0,   A 3 y   =   1,   β   =   − π / 2,   d 1   =   1, and   d 3   =   1. The characteristic polynomial for Algorithm 1 is  g ( t ) = ( ρ 2 3   − ρ 2 1 ) t 3   +( ρ 2 2   − ρ 2 1   − 4 ) t 2   +( ρ 2 3   − ρ 2 1   − 4 ) t   + ρ 2 2   − ρ 2 1  After eliminating   t   from   G   we get    ̃ G   =   { P 1 ,   P 2 ,   P 3 }   as follows  ρ 4 2   +   ρ 4 3   −   2   ρ 2 2   ρ 2 3   +   6   ρ 2 1   −   3   ρ 2 2   −   3   ρ 2 3   −   12   =   0 2   ρ 4 1   +   2   ρ 4 3   −   4   ρ 2 1   ρ 2 3   +   4   ρ 2 1   +   3   ρ 2 2   −   7   ρ 2 3   −   16   =   0  ρ 4 3   +   ρ 2 1   ρ 2 2   −   ρ 2 1   ρ 2 3   −   ρ 2 2   ρ 2 3   +   3   ρ 2 1   +   ρ 2 2   −   4   ρ 2 3   −   6   =   0 .  (4) Observe that these equations are not independent. Indeed,   P 2  is a combination of the other two:  P 2   = ( ρ 2 1   −   ρ 2 3   +   1 )  3   P 1   + ( ρ 2 3   −   ρ 2 2   +   6 )  3   P 3 .  Additionally, there are solutions of    ̃ G   that do not correspond to the real cusp locus. For instance, if we set   ρ 1   =   1 / 3, the system    ̃ G | ρ 1 = 1 / 3   has two solutions with both   ρ 2   and   ρ 3   pos- itive.   But the FKP evaluated on these two solutions only has complex solutions   ( x ,   y ,   α ) . So, for   ρ 1   =   1 / 3 the c-space  C   ( F )   has no cusp points, though Algorithm 1 obtained two mistaken candidates. We now test Algorithm 3 on the same example.   The equations of the cusp locus   C F   are: 6   c α   +   ρ 2 2   −   ρ 2 3   =   0 2   s 2  α   +   s α   −   1   =   0 2   c 2  α   −   s α   −   1   =   0 2   c α   s α   −   c α   =   0 3   c α   +   3   s α   +   ρ 2 1   −   ρ 2 3   +   1   =   0 3   c α   +   3   s α   +   x 2   +   y 2   −   ρ 2 3   +   1   =   0 2   x s α   +   2   y s α   −   4   s α   −   x   −   y   +   2   =   0 2   s α   ρ 2 3   −   3   c α   −   6   s α   −   4   x y   −   x   −   y   =   0 2   x c α   +   2   y s α   +   c α   −   3   s α   −   2   x   +   1   =   0 2   y c α   +   2   y s α   +   c α   −   s α   −   x   +   y   +   1   =   0 4   y s α   −   s α   +   2   ( c α   −   1 )   ρ 2 3   +   4   y 2   −   3   y   +   x   +   1   =   0 2   s α   ( 2   y 2   −   4   y   −   1 )   −   3   c α   −   4   x y   −   2   y 2   +   3   y  − x   +   ρ 2 3   −   2   =   0 6   s α   ( 2   y   +   1 ) +   12   c α   −   8   y 2   x   +   8   y 3   +   12   x y  + x   −   3   y   +   2   x   ρ 2 3   −   6   y   ρ 2 3   −   6   ρ 2 3   +   8   =   0 18   s α   ( 18   y   −   1 ) +   36   c α   +   32   y 4   +   20   y 2   +   44   x y  + 13   x   −   47   y   +   4   ρ 4 3   −   8   ρ 2 3   y x   −   32   y 2   ρ 2 3  − 6   x   ρ 2 3   −   6   y   ρ 2 3   −   32   ρ 2 3   +   40   =   0 .  (5)
PSfrag replacements  ρ 2  ρ 3  Fig. 3.   Singular curve for   ρ 1   =   1  3   on   ( ρ 2 ,   ρ 3 )  Here if we try to solve   C F   | ρ 1 = 1 / 3 , we get no real solutions. Figure 3 shows a section in the   ( ρ 2 ,   ρ 3 ) -plane of the singular locus of   F   for   ρ 1   =   1  3   . As can be observed, there is no cusp point in this plot. This phenomenon is not casual. Actually, the value 1 / 3 for   ρ 1   has not been randomly picked as we will see in next section. In fact, Algorithm 3 describes the cusp locus more accurately than Algorithm 1, in general.  4   Discussion on the joint space  We now extend our improved method to partition a pa- rameter space with regard to the associated cusp locus. So, we want to discuss the solutions of a parametric system. Among the numerous possible ways of solving paramet- ric systems, we focus on the use of Discriminant Varieties (DV) [6] for two main reasons: it provides a formal decom- position of the parameter space through an exactly known algebraic variety (no approximation), and it has been suc- cessfully used in similar problems [20]. Let us consider a general parametric polynomial system  F   =   { p 1 ( v ) =   0 , . . . ,   p m ( v ) =   0 ,   q 1 ( v )   >   0 , . . . ,   q l   ( v )   >   0 } ,  where   p 1 , . . . ,   p m ,   q 1 , . . . ,   q l   are polynomials with rational co- efficients depending on   v   = ( U 1 , . . . , U d   ,   X 1 , . . . ,   X n )   with   X i  being unknowns and   U i   parameters. For instance, the system describing the cuspidal configurations our manipulator   C F   is parametric if some of the geometric parameters are initially left free in   F . The DV associated to system   F   is described by a polynomial equation. This DV partitions the parameter space into several regions such that over each open region delimited by the DV the number of real solutions of   F   is constant. Prior to defining the DV associated to   F   , we need to specify a solver of 0-dimensional systems that will be used as a black box.  4.1   Basic black-boxes  Let us describe the global solver for 0-dimensional sys- tems that will be used as a black box in the general algorithm. We mainly use exact computations, namely formal elimina- tion of variables (resultants, Gr ̈ obner bases) and resolution of 0-dimensional systems, including univariate polynomials. We   first   compute   a   Gr ̈ obner   basis   of   the   ideal  〈 p 1 , . . . ,   p m 〉   for any ordering, which will help us detect if the system has or has not finitely many complex solutions. If yes, then compute a so called Rational Univariate Represen- tation (RUR) of   〈 p 1 , . . . ,   p m 〉   (see [21]), which is an equiva- lent system of the form  {   f   ( T   ) =   0 ,   X 1   =   g 1 ( T   )  g ( T   )   , . . . ,   X n   =   g n ( T   )  g ( T   )   } , where   T   is   a   new   variable   independent   of   X 1 , . . . ,   X n , equipped with a so called   separating element   (injective on the solutions of the system)   u   ∈   Q [ X 1 , . . . ,   X n ]   and such that :  V   ( p 1 , . . . ,   p m )   u  − →   V   (   f   )   u − 1  − − →   V   ( p 1 , . . . ,   p m ) ( x 1 , . . . ,   x n )   7   →   β   =   u ( x 1 , . . . ,   x n )   7   →  (   g 1 ( β )  g ( β )   , . . . ,   g n ( β )  g ( β )  )  defines a bijection between the (real) roots of the system and the (real) roots of the univariate polynomial   f   . We then solve   f   =   0, computing so called isolating in- tervals for its real roots, i.e. non-overlapping intervals with rational bounds that contain a unique real root of   f   (see [22]). Finally, interval arithmetic is used in order to get isolating boxes of the real roots of the system (non-overlapping prod- ucts of intervals with rational bounds containing a unique real root of the system), by studying the RUR over the iso- lating intervals of   f   . In practice, we use the function   RootFinding[Isolate]  from Maple software, which performs exactly the compu- tations described above.  4.2   Discriminant varieties  Consider now the constructible set  S   =   { v   ∈   C n   :   p 1 ( v ) =   0 , . . . ,   p m ( v ) =   0 ,  q 1 ( v )   6   =   0 , . . . ,   q l   ( v )   6   =   0 } , and let us assume that for almost all the parameter values this   S   is a finite set of points. Then, a discriminant variety of  S   with respect to   ( U 1 , . . . , U d   )   is a variety   V   ⊂   C d   such that over each connected open set   U   not intersecting   V   ( U   ∩ V   =  / 0 ),   S   defines an analytic covering. In particular, the number of points of   S   over any point of   U   is constant. Discriminant varieties can be computed using basic and well-known tools from computer algebra such as Gr ̈ obner bases [6].   A full package is available in Maple software through the   RootFinding[Parametric]   package, which pro- vides us with a polynomial   DV   ( S ; U 1 , . . . , U d   )   whose associ- ated discriminant variety is   V   .  4.3   Case study comparison  Let us consider again the degenerate 3-RP R with the same geometric parameter values as those specified in sec- tion 3.3, i.e.   A 2 x   =   1,   A 3 x   =   0,   A 3 y   =   1,   β   =   − π / 2,   d 1   =   1, and   d 3   =   1, and consider the systems    ̃ G   (Eqn. 4), and   C F  (Eqn. 5), obtained by Algorithm 1 without step 3 and by Al- gorithm 3, respectively. We will regard as a parameter one of the leg lengths   ρ 1   of the manipulator. The discriminant
DV  ̃ G  DV C F  0 cusps   2 cusps   3 cusps  ρ 1  0,0 cusps 0,0 cusps  r 1   =  √ 2 √ 27 − 10  2   ,   2 cusps  r 2   =  √ 2  4   ,   2 cusps  r 3   =   √ 2,  3 cusps  r 3   =   √ 2,  5 cusps  0 cusps   4 cusps   6 cusps  Fig. 4.   Comparison of both discussions on   ρ 1  variety will provide us with a polynomial in   ρ 1   whose roots will delimit some open intervals such that for whatever value of   ρ 1   within one interval, the number of cusp points of   F | ρ 1  will be the same. We compute the DV for each system with respect to   ρ 1 , and analyze the results. In the first case, we get the polynomial   DV   (    ̃ G ;   ρ 1 ) =  ρ 1   ( ρ 2 1   −   2 ) ( 2 ρ 4 1   +   10 ρ 2 1   −   1 ) , whose roots describing the dis- criminant variety are  r 0   =   0,   r 1   =  √ 2 √ 27 − 10  2   and   r 3   =   √ 2. Since the number of cusp points is kept constant between two consecutive roots, we can compute the associated number of cusps by picking one single value of   ρ 1   inside each open interval and solve    ̃ G | ρ 1   . In this case we obtain  •   0 cusp configurations for   ρ 1   ∈   ] 0 ,   r 1 [ ,  •   2 cusp configurations for   ρ 1   ∈   ] r 1 ,   r 3 [ , and  •   3 for   ρ 1   ∈   ] r 3 ,   ∞ [ . Substituting   ρ 1   =   r i   into    ̃ G   we obtain the number of cusps on the borders of the intervals.  •   0 cusps on   ρ 1   =   0,  •   2 cusps on   ρ 1   =   r 1 , and  •   3 on   ρ 1   =   r 3 . In the second case, a similar analysis for   C F   gives  DV   ( C F   ;   ρ 1 ) =   ρ 1   ( ρ 2 1   −   2 ) ( 8 ρ 2 1   −   1 ) ( 2 ρ 4 1   +   10 ρ 2 1   −   1 ) ,  which has one more root than   DV   (    ̃ G ;   ρ 1 )  r 0   =   0,   r 1   =  √ 2 √ 27 − 10  2   ,   r 2   =  √ 2  4   and   r 3   =   √ 2. The intervals and the numbers of cusps for   C F   differ a bit from those obtained for    ̃ G :  •   0 cusps for   ρ 1   ∈   ] 0 ,   r 1 [ ,  •   0 cusps for   ρ 1   ∈   ] r 1 ,   r 2 [ ,  •   4 cusps for   ρ 1   ∈   ] r 2 ,   r 3 [ ,  •   6 cusps for   ρ 1   ∈   ] r 3 ,   ∞ [ .  •   0 cusps on   ρ 1   =   0,  •   0 cusps on   ρ 1   =   r 1 ,  •   2 cusps on   ρ 1   =   r 2 ,  •   5 cusps on   ρ 1   =   r 3 . The results obtained in both cases are compared in Fig. 4.   We can observe that the first two intervals do not exactly coincide, and that for the second system the obtained numbers of cusps appear doubled for all intervals (compared to those obtained for the first system). Both phenomena can be explained as a consequence of the projection map used to compute the system    ̃ G . Let us remind the reader that    ̃ G   is obtained after several reductions of the initial system, each of which applying also a projection on the   ρ ρ ρ -space. For this, there can be complex configurations of the manipulator that project onto real roots   ρ ρ ρ   of    ̃ G . This is the case for the values of   ρ 1   ∈ ] r 1 ,   r 2 [ . The same can be done for any other parameter and the same phenomena can be observed.  5   Higher-dimensional discussion by means of a CAD  By construction we know that over any connected open region not intersecting the DV the system has a constant number of real roots, for whatever chosen parameters. But if we want to discuss larger parameter spaces, then the open regions will no longer be as simple as 1-dimensional inter- vals.   So the goal of this section is to provide an accurate description of the regions with constant number of solutions. For this we will use the Cylindric Algebraic Decomposition (CAD) [7, 23].  5.1   The complementary of a discriminant variety  Let   P d   ⊂   Q [ U 1 , . . . , U d   ]   be the set of polynomials de- scribing the DV. Then for each   i   =   d   −   1 , . . .,   0, we introduce a new set of polynomials   P i   ⊂   Q [ U 1 , . . . , U d − i ]   defined by a backward recursion:  •   P d   = the polynomials defining the DV,  •   P i   =   {   DV   ( p ; U i ) , LeadingCoefficient ( p , U i ) , Resultant ( p ,   q , U i ) ,   p ,   q   ∈   P i + 1   }  Each   P i   has an associated algebraic variety of dimension at most   i   −   1,   V i   =   V   ( ∏ p ∈ P i   p ) .   The   V i   are used to recur- sively define a finite union of simply connected open subsets  ∪ n i  k = 1 U i , k   ⊂   R i   of dimension   i   such that   V i   ∩   U i , k   =   / 0 . Before defining the sets   U i , k , we introduce some nota- tion: for a univariate polynomial   p   with   n   real roots, root ( p ,   l ) =      − ∞   if   l   ≤   0 ,  the   l th   real root of   p   if 1   ≤   l   ≤   n ,  + ∞   if   l   >   n   .  Moreover, if   p   is a   n -variate polynomial, and   v   is a   ( n   −   1 ) - tuple, then   p v   denotes the univariate polynomial where the first   n   −   1 variables have been replaced by   v . The recursive process defining the   U i , k   is the following:  •   For   i   =   1, let   p 1   =   ∏ p ∈ P 1   p . Taking all   U 1 , k   =]   root ( p 1 ,   k ) ; root ( p 1 ,   k   +   1 )[   for   k   =  0 , . . . ,   n , where   n   is the number of real roots of   p 1 , one gets a partition of   R   that fits the above definition. More- over, one can arbitrarily chose one rational point   u 1 , k   in each open interval   U 1 , k .  •   Then, for   i   =   2 , . . . ,   d , let   p i   =   ∏ p ∈ P i   p . The regions   U i , k   and the points   u i , k   are of the form:  U i , k   = { ( v 1 , ...,   v i − 1 ,   v i )   |   v   : = ( v 1 , ...,   v i − 1 )   ∈   U i − 1 ,   j ,  v i   ∈ ]   root ( p v  i   ,   l ) ,   root ( p v  i   ,   l   +   1 )[ }  u i , k   = ( β 1 , ...,   β i − 1 ,   β i ) ,   with {   ( β 1 , ...,   β i − 1 ) =   u i − 1 ,   j  β i   ∈ ]   root ( p u i − 1 ,   j  i   ,   l ) ,   root ( p u i − 1 ,   j  i   ,   l   +   1 )[   ,
PSfrag replacements  ρ 1  d 1  Fig. 5.   Plot of the DV of   C F   with respect to   ( ρ 1 ,   d 1 )  where   j ,   l   are fixed integers. With this recursive procedure we get a full description of the complementary of the DV for the system to be solved: the cells   U d , k   and a test point   u d , k   ∈   U d , k   (with rational co- ordinates). The number of solutions associated to each open cell   U d , k   is obtained by solving the given system restricted to  u d , k   using a 0-dimensional solver. Both the cell decomposi- tion and the test points can be obtained by the Maple function  RootFinding[Parametric][CellDecomposition] .  5.2   Open CAD for a class of degenerate 3-RP R  Let us see the performance of this CAD on a 2- dimensional discussion. We consider now a family of degen- erate 3-RP R manipulators with   A 2 x   =   1,   A 3 x   =   0,   A 3 y   =   1,  β   =   − π / 2, and   d 3   =   1, and regard as parameters both   ρ 1   and  d 1 , constrained by   d 1   ≥   0. Now, the system   C F   describing the cusp locus associated to this family of manipulators has 18 polynomials, its DV is plot in Fig. 5, and the polynomial  DV   ( C F   ;   ρ 1 ,   d 1 )   factors as follows:  d 1   ρ 1   ( d 2 1   +   1 ) ( − 4   ρ 6 1   −   12   ρ 4 1   +   27   ρ 2 1   d 2 1   +   15   ρ 2 1   −   4 ) ( 4   ρ 6 1   +   12   ρ 4 1   d 2 1   −   15   ρ 2 1   d 4 1   +   4   d 6 1   −   27   ρ 2 1   d 2 1   ) ( 256   ρ 6 1   d 2 1   +   81   ρ 2 1   d 6 1   −   288   ρ 4 1   d 4 1   +   256   ρ 6 1   −   576   ρ 4 1   d 2 1  +   51   ρ 2 1   d 4 1   −   16   d 4 1   −   288   ρ 4 1   +   51   ρ 2 1   d 2 1   +   81   ρ 2 1 ) .  The complement of this DV produces 90 cells with as- sociated numbers of cusps varying among 0, 2, 4 and 6, as shown in Fig. 6, where black vertical lines delimit intersec- tion points of the DV. Let us notice that although all cells must be considered disconnected, it is apparent that cells are naturally grouped with regard to their number of cusps. Additionally, cells with different number of cusps are exclu- sively separated by curves of the discriminant variety. Fur- thermore, this distribution is consistent with that obtained for  d 1   =   1 in Section 4.3, as can be seen in Fig. 7.   However, here the section is divided into many more smaller intervals whose borders we cannot apriori ensure to be associated to a specific number of cusp points. In fact, let us also observe that the cells with 2 cusp points (in blue) degenerate into one  PSfrag replacements  ρ 1  d 1  0 cusps 2 cusps 4 cusps 6 cusps  Fig. 6.   Cell Decomposition for   ( ρ 1 ,   d 1 )  PSfrag replacements  ρ 1  d 1  Fig. 7.   Zoom in of the cell decomposition for   ( ρ 1 ,   d 1 ) . Line   d 1   =   1  in white.  single point for   d 1   =   1. So we could claim that the case with  d 1   =   1 is a very special degenerate 3-RP R manipulator.  5.3   Study of the cusp points on the borders of the CAD  At this point we can only certify the number of cusp points in the open cells. This excludes the cell borders. The union of all these borders consists of the DV plus the delim- itation of intersection points of the DV. However, by defini- tion, changes in the number of solutions can only happen on the DV. So, we just need to analyze the DV. We could try executing a further iteration of the CAD on the DV, but the system to be solved turns out to be too com- plex and we cannot obtain any results after long computa- tions. It is clear that not all points on the DV will correspond to the same number of solutions. But we can expect the num- ber of solutions to be preserved along the DV between two consecutive auto-intersection points of the DV. And although it has not yet been proven, many tests have been run on sev- eral examples with random points on the DV and all the re- sults confirm what the following conjecture infers.  Conjecture 1.   Given a polynomial system   F , let   V   be the DV of   F   w.r.t two parameters   U 1 , U 2 , and let   A   be the set of its auto-intersection points. Then, the number of solutions of  F   is constant on each connected component of   V   \   A . The following algorithm analyzes the to study the num- bers of solutions on the DV based on the previous conjecture.
0   cusps  4   cusps  1   cusps  5   cusps  2   cusps  6   cusps  3   cusps  ρ 1  d 1  PSfrag replacements  ρ 1  d 1  (a)   (b)  Fig. 8.   Distribution of cusp points on   DV   ( C F   ;   ρ 1 ,   d 1 )   (a), and zoom in view on   [ 0 ,   1 . 5 ]   ×   [ 0 ,   1 . 5 ]   (b).  Algorithm 4   Number of solutions of   F   on the DV  V   =   variety of   DV   ( F ; U 1 , U 2 )  A   =   { auto-intsersection points of   V   }  for   each connected component   U i   of   V   \   A   do  p i   =   random point on   U i  Compute the number of solutions on   U i   as the number of solutions of   F | p i  end for for   each point   q   ∈   A   do  Compute the number of solutions of   F | q  end for  5.4   Complete analysis and applications  From the results exposed in the previous subsections and by joining all the different pieces together we obtain a com- plete partition of the 2-dimensional parameter space. The execution of Algorithm 4 on   DV   ( C F   ;   ρ 1 ,   d 1 )   pro- vides the distribution of cusp points shown in Fig. 8.   The integral picture of the 2-dimensional distribution is given in Fig. 9. It is interesting to notice that there is a continuity on the transitions between cells having the same number of cusp points, since their common border inherits that same number of cusp points. Observe also that this distribution has been obtained thanks to the DV associated to the chosen parameters   d 1   and  ρ 1 , which depends exclusively on these two parameters. In particular,   DV   ( C F   ;   ρ 1 ,   d 1 )   does not depend on   ρ 2   nor   ρ 3 . This tends to be erroneously interpreted as: “ if we pick a   ( ρ 1 ,   d 1 ) -point with associated number of cusps k, then whatever the values   ρ 2   and   ρ 3   may take, C F   | ( ρ 1 , ρ 2 , ρ 3 , d 1 )   has k solutions ”. Instead, it should be read as follows: “ if we pick a   ( ρ 1 ,   d 1 ) -point with associated number of cusps k and fix these values then, among the reachable configura- tions there are k cuspidal ones, i.e.   C F   | ( ρ 1 , d 1 )   has k solu- tions ”. However, the number of associated cusp points does establish a maximum of cuspidal configurations for any val-  PSfrag replacements  ρ 1  d 1  Fig. 9.   Complete analysis of the cusp points for   ( ρ 1 ,   d 1 )  ues   ρ 2   and   ρ 3 . For example, in yellow regions we can have a maximum of 4 cuspidal configurations, but depending on the values of   ρ 2   or   ρ 3   there can even be none. In particular, for the red regions there are 0 cusp points for all possible values  ρ 2   and   ρ 3 . Some applications can be derived which may be inter- esting from the designer’s point of view:  •   It can be helpful in deciding the most suitable architec- ture of the mechanism. Let us assume that we want to design a 3-RP R manipulator with some given geometric constraints such that for a specific task one of the legs has to be blocked to a fixed length   ρ 1 , but the job re- quires a large singularity-free workspace. Therefore, we may be interested in finding a range   ∆ d 1   of parameter values for which the manipulator is cuspidal.  •   It can also be useful for deciding the most suitable ranges of leg lenghts for each possible architecture, given a specific task. For instance, let us assume that the job is set for a non-cuspidal manipulator with parameter values   A 2 x   =   1,   A 3 x   =   0,   A 3 y   =   1,   β   =   − π / 2, and   d 3   =   1, but it requires the largest possible range of the leg length  ρ 1 . Then, the value   d 1   can be optimized with this crite- rion. Figure 10 details both the optimal valule   d 1   and the largest possible range   ∆ρ 1   for our problem. Let us just notice that in both cases the obtained ranges can be of varied topology (open, closed, semi-closed, open and closed, connected, or even a union of these types). This is due to the combination of both the CAD and the study of the cusp locus on the DV.  6   Conclusions  This paper has introduced both an efficient method for the computation of the cuspidal configurations of a mecha- nism, and a reliable algorithm that partitions a given param- eter space into open regions with constant number of associ- ated cusp points. The first one is based on a symbolic-algebraic approach able to describe the roots of exact multiplicity 3 and a cer- tified numerical algorithm that isolates among them the real
PSfrag replacements  ρ 1  d 1  ∆ρ 1  Fig. 10.   Optimal   d 1   and   ∆ρ 1   for non-cuspidal degenerate 3-RP R.  (i.e. not complex) ones. This symbolic-numeric approach is more efficient than other previously existing methods, which mainly relied on the approximation of roots of multiplicity at least 3 after reducing the initial system to a simpler one and projecting it onto the   ρ ρ ρ -space. This new method is combined with some algebraic tools such as the discriminant variety (DV) and the cylin- dric algebraic decomposition (CAD) in order to analyze a 2- dimensional parameter space with respect to the associated number of cusp points.   This second algorithm provides a partition of the parameter space into cells with constant num- ber of cusp points, which is certified for whatever values are picked inside each open cell but not on their borders. Cell borders are further analyzed by Algorithm 4 based on Con- jecture 1, which still remains unproved. Both algorithms have been applied to the analysis and distribution of the cusp locus for a family of degenerate 3- RP R manipulators, and some applications to robot design are also derived. This does not mean that the two given algo- rithms are specially designed for this type of 3-RP R mecha- nisms. Indeed, they are suitable for more general examples since they do not rely on any ad-hoc formulation. Neverthe- less for some examples the obtention of results within rea- sonable time may not be feasible yet, since there is an im- portant symbolic-algebraic part, and thus the more complex the initial system is the harder it will be to compute a parti- tion on the parameter space.  Acknowledgements  The authors would like to acknowledge the financial support of this research by ANR Project SiRoPa. The first and second authors have been supported for this research by two postdoctoral contracts at the Institut de Recherche en Communications et Cybern ́ etique de Nantes under the spon- sorship of the same project.  References  [1] Innocenti,   C.,   and   Parenti-Castelli,   V.,   1998. “Singularity-free   evolution   from   one   configuration to another in serial and fully-parallel manipulators”.  ASME J. Mechanical Design,   120 (1), pp. 73–79. [2] McAree, P. R., and Daniel, R. W., 1999. “An explana- tion of never-special assembly changing motions for 3- 3 parallel manipulators”.   I. J. Robotic Research,   18 (6), pp. 556–574. [3] Zein, M., Wenger, P., and Chablat, D., 2007. “Singu- lar curves in the joint space and cusp points of 3-RPR parallel manipulators”.   Robotica,   25 (6), pp. 717–724. [4] Husty, M. L., 2009.   “Non-singular assembly mode change in 3-RPR parallel manipulators”.   In Proceed- ings of the 5th International Workshop on Computa- tional Kinematics, Springer, pp. 51–60. [5] Kreuzer, M., and Robbiano, L., 2000.   Computational commutative algebra 1 . Springer. [6] Lazard, D., and Rouillier, F., 2007. “Solving parametric polynomial systems”.   J. Symbolic Computation,   42 (6), pp. 636–667. [7] Collins, G. E., 1975.   Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition . Springer. [8] Chablat,   D.,   Moroz,   G.,   and   Wenger,   P.,   2011. “Uniqueness domains and non singular assembly mode changing trajectories”.   In Proceedings of the 2011 IEEE International Conference on Robotics and Au- tomation (ICRA), pp. 3946–3951. [9] Hunt, K., 1983.   “Structural kinematics of in-parallel actuated robot arms”.   J. Mechanisms, Transmissions and Automation in Design,   105 , pp. 705–712. [10] Gosselin, C., Sefrioui, J., and Richard, M., 1992. “So- lutions polynomiales au probl` eme de la cin ́ ematique di- recte des manipulateurs parall` eles plans ` a trois degr ́ es de libert ́ e”.   Mechanism and Machine Theory,   27 (2), pp. 107–119. [11] Pennock, G., and Kassner, D., 1990. “Kinematic anal- ysis of a planar eight-bar linkage:   application to a platform-type robot”.   In ASME Proc. of the 21st Bi- ennial Mechanisms Conf., pp. 37–43. [12] Kong, X., and Gosselin, C., 2001. “Forward displace- ment analysis of third-class analytic 3-RPR planar par- allel manipulators”.   Mechanism and Machine Theory,  36 , pp. 1009–1018. [13] Wenger, P., and Chablat, D., 2009. “Kinematic analysis of a class of analytic planar 3-RPR parallel manipula- tors”. In Proceedings of the 5th International Workshop on Computational Kinematics, pp. 43–50. [14] Wenger, P., Chablat, D., and Zein, M., 2007. “Degen- eracy study of the forward kinematics of planar 3-RPR parallel manipulators”.   ASME J. Mechanical Design,  129(12) , pp. 1265–1268. [15] Gosselin, C., and Angeles, J., 1990. “Singularity analy- sis of closed-loop kinematic chains”.   IEEE J. Robotics and Automation,   6 (3), pp. 281–290. [16] Ur ́ ızar, M., Petuya, V., Altuzarra, O., and Hern ́ andez, A., 2011. “On the cuspidality of the analytic 3-RPR”.
In IFToMM 13th World Congress in Mechanism and Machine Science. [17] Hern ́ andez, A., Altuzarra, O., Petuya, V., and Macho, E., 2009. “Defining conditions for nonsingular transi- tions between assembly modes”.   IEEE Transactions on Robotics,   25 , pp. 1438–1447. [18] Moroz, G., Rouillier, F., Chablat, D., and Wenger, P., 2010. “On the determination of cusp points of 3-RPR parallel manipulators”.   Mechanism and Machine The- ory,   45 . [19] Moroz, G., 2008.   “Sur la d ́ ecomposition r ́ eelle et alg ́ ebrique des syst` emes d ́ ependant de param` etres”. PhD thesis, Universit ́ e Paris 6, France. [20] Corvez, S., and Rouillier, F., 2002.   “Using computer algebra tools to classify serial manipulators”. In Auto- mated Deduction in Geometry, pp. 31–43. [21] Rouillier, F., 1999. “Solving zero-dimensional systems through the rational univariate representation”.   J. Ap- plicable Algebra in Engineering, Communication and Computing,   9 (5), pp. 433–461. [22] Rouillier, F., and Zimmermann, P., 2003. “Efficient iso- lation of polynomial real roots”.   J. Computational and Applied Mathematics,   162 (1), pp. 33–50. [23] Dolzmann, A., Seidl, A., and Sturm, T., 2004.   “Effi- cient projection orders for CAD”. In Proceedings of the 2004 International Symposium on Symbolic and Alge- braic Computation, pp. 111–118.