KINEMATIC SYNTHESIS USING TREETOPOLOGIES
Edgar Simo-Serraa , Alba Perez-Graciab,∗aInstitut de Robotica i Informatica Industrial (CSIC-UPC), Llorens i Artigas 4-6, 08028
Barcelona, Spainb
Department of Mechanical Engineering, Idaho State University, Pocatello, Idaho 83209,
USA

Abstract
This paper presents a methodology for the description and finite-position dimensional synthesis of articulated systems with multiple end-effectors. The
articulated system is represented as a rooted tree graph. Graph and dimensional synthesis theories are applied to determine when exact finite-position
synthesis can be performed on the tree structures by considering the motion
for all the possible subgraphs. Several examples of tree topologies are presented and synthesized. This theory has an immediate application on thedesign of novel multi-fingered hands.
Keywords: kinematic synthesis, graph theory, tree articulated systems
1. Introduction
Kinematic synthesis theory, in which an articulated system is designed
to meet certain motion specifications, has been applied to open and closed
linkages. In the dimensional synthesis problem, a given topology for an articulated system is dimensioned in order for its workspace to fit a giventask. Finite-position dimensional synthesis of planar linkages was developed
early, see [1, 2, 3, 4]. Dimensional synthesis of spatial articulated systems
has targeted mostly serial chains. The first methods used [5, 6], based on∗

Corresponding author. Phone number 001 208 2825655
Email addresses: esimo@iri.upc.edu (Edgar Simo-Serra), perealba@isu.edu (Alba Perez-Gracia)

Preprint submitted to Mechanism and Machine Theory

November 22, 2013

geometric constraints and vector loop equations, were successful for synthesizing simple systems. More recently, methods based on robot kinematic
equations [7, 8] allowed to formulate design equations for more complex systems, still limiting the application to serial chains, and with limitations inthe solution process [9]. Some examples of dimensional synthesis applied toparallel robots can be found in [10, 11, 12].
Type or structural synthesis [13, 14] includes a systematic classificationof the linkage type in the synthesis process, which is based on graph theory
in many cases. Graph theory has been used for a long time in the analysis
and type synthesis of linkages, see early research by Woo [15], Huang andSoni [16], Manolescu [17], Freudenstein and Maki [18], and more recently
Tsai [19], Mruthyunjaya [20], and Lu, Mao et al. [21], [22]. Additionally,
Chuang and Lee [23] have used structural synthesis for the design of finger
mechanisms.
The analysis of articulated systems with a tree structure has also generated some research. Selig [24] mentions tree-structured mechanisms andmodels them as rooted trees following [25]. His work includes basic definitions and the application to kinematic and dynamic analysis. Chen et al.
[26] perform the analysis of tree-type geometries for applications in modular robots. Song and Amato [27] apply the analysis of tree-like articulated
systems to folding. Jain [28] uses tree graphs for the dynamic analysis ofmulti-body systems; tree-systems also appear describing dynamic systems in
Garcia de Jalon [29]. Tree articulated systems and their graph representation
are also studied in [30] for the analysis and control of mechanical systems,
where they are named forking linkages. Tischler et al. [31, 32] apply graphtheory for the structural synthesis of kinematic chains with applications torobot hands. However, no applications or methodology exist, to the knowledge of the authors, for the dimensional synthesis of articulated systems witha tree structure.
Even though little literature is devoted to these systems when compared to their serial or parallel counterparts, tree articulated systems arewidely used in robotic multi-fingered hands. Locomotive structures for mobile robots could also be modeled as tree-like systems. For this research, thekinematic design of multi-fingered robotic grippers is the primary application.
The advantage of having a methodology for the dimensional synthesis ofa set of fingers lies in the possibility of defining simultaneous manipulationand grasping actions for the whole hand. Aside from underactuated robotic
2

hands (see [33] for a review and [34] for recent results), which present little
dexterity, the design of robotic hands has been performed from an anthropomorphic point of view. See recent reviews of different applications in [35, 36].
In addition to this, modular fingers have been designed that able to perform
certain grasping actions and are later integrated in a hand [37]. The development of a theory for the use of dimensional kinematic synthesis on tree
topologies aims to create a tool for new designs that can be applied, forinstance, in many areas of human-robot interaction.
This paper focuses on developing a general methodology for the finiteposition dimensional synthesis problem, in particular exact dimensional synthesis, applied to articulated systems with a tree structure. A tree-structured
articulated system has a base (a grounded link), some common joints, andmultiple end-effectors, each one of them corresponding to a separate branch.
The input data of the synthesis algorithm is a finite set of rigid-body
positions for each of the multiple end-effectors and a selected tree topology,
which is modeled using rooted tree graphs as explained in Section 2. After thesubstitution of kinematic chains, a compact rooted graph is obtained. Thisgraph must be checked for solvability. In case of obtaining a non-solvablegraph, an equivalent graph must be found. These two steps are developed in
Sections 4 and 5.
For the resulting solvable rooted tree graph, the forward kinematics equations of relative displacements for each serial chain are computed using dual
quaternions. The theory is introduced in Section 3. The synthesis of spatial serial chains for up to five degrees of freedom using this technique wasdeveloped in [38]. In this case, each serial chain corresponds to one branch,including the common joints. The dependency among the different serial
chains allows the extension of the exact synthesis to articulated systems witha high number of degrees of freedom, and to tasks defined by a high numberof positions. The extension of the kinematic synthesis to tree topologies ispresented in Sections 6 and 7, and the matrix representation can be foundin Section 8.
Each serial chain yields a set of equations and all the sets are solved
simultaneously. Due to the high dimension and degree of the obtained systemof equations, a numerical solver is required. As a last step, the solution isused to dimension the substituted kinematic chains.
Three examples are included in Section 9. The first one is a possible
application to a multi-fingered robotic hand, for which numerical solutions
have been found [39]. The second example is a simple PR-(R,P) tree struc3

ture, which can be solved analytically and is used to illustrate the process.
The last example includes a numerical task for an RR-(RR,R,R) topology,
and one of the multiple solutions obtained is presented. For ease of comprehension, an overview of the nomenclature used in this paper is presented inTable 1.
The development of a dimensional synthesis method for tree articulated
systems is a first step towards a new design tool for multi-fingered robotic
hands. The non-anthropomorphic hands obtained, which can perform humantasks if so designed, could be used for specific robotics applications, and inparticular for human-robot interaction or cooperative tasks.
Table 1: Nomenclature used in this paper
SymbolDescriptions

A vector.

[M ]A matrix.

â

A dual number.

Q̂

A dual quaternion.

S

Plucker coordinates of a line; also a screw.

∗$

Smallest subalgebra of se(3) containing all the possible infinitesimal mechanical liaison between two rigid bodies.

$

An ordered screw surface.

L

Linkage locus space.

2. Rooted Tree Graph Representation
Articulated systems with a tree topology can be modeled using graphtheory. This allows for a compact representation of the structure, the identification of key paths in the system, and the realization of some operations
that help simplify the synthesis process.
The use of graphs in order to represent mechanisms was proposed by
Crossley [40]. Tsai’s methodology [19] is followed in this paper. It consistsof identifying the joints with the edges and the links with the vertices of thegraph. The different types of joints (revolute, prismatic, spherical, etc.) are4

indicated using their common abbreviation (R, P, S, etc.) on the edges of
the graph. See for instance Figure 1.
For their use in the kinematic synthesis process, the mechanisms are to be
represented always as rooted graphs, the root vertex being fixed with respect
to the reference system.
R

R

R

R

Figure 1: Graph representation of a 4R serial manipulator. The circle indicates the root vertex and the square indicates the end-effector.
A rooted connected graph representing a kinematic structure shall bedenoted as G(V, E), with a set of v vertices V and a set of e edges E connecting the vertices. The vertices represent the rigid bodies and the edges
represent the joints connecting adjacent bodies. Besides the root vertex, anumber of vertices will be given the special characteristic of being considered
end-effectors.
A graph representing a 4R manipulator can be seen in Fig. 1. The fouredges correspond to the four revolute joints. The root vertex is marked witha circle around the vertex and the end-effector is indicated with a squaremark.
In tree topologies, a vertex can be connected to several edges defining
several branches. The degree of a vertex is the number of edges that areconnected to it, which in this case would be equivalent to the number ofjoints connected to it. Notice that a tree articulated system will always havelinks that are ternary or above; those can be identified in the graph as avertex spanning several edges.
2.1. Contraction
After constructing the initial graph representation of a linkage, the next
step is to contract the graph. The graph is contracted so that each edge
represents the set of joints of a kinematic serial chain instead of an individual
kinematic joint.
The 4R manipulator seen in Fig. 1 would be contracted to a single edge
representing the serial revolute joints connecting the root vertex and the end5

effector. Contraction removes all vertices with a degree of 2; notice that all
vertices with a degree of 1 that are not the root vertex are end-effectors.
2.2. Setting the Root NodeThe special characteristic of the root node is that it indicates that therigid body associated with it is immobile in the reference system. Essentially
it marks the fixed reference system. However, the root node can be set at anyother end-effector by performing a transformation. Consider the positions Pi
as rigid transformations associated to the end-effector i where i = 1 is theroot node, then the inversion of the root from i = 1 to i = j isP∗i = P−1
j Pi ,(1)

where P∗i would be the new end-effector positions relative to the new root j.
Changing the root node can be useful for solving particular systems, as
will be shown in the examples.
2.3. Rooted Graphs for Tree Topologies
Let T (V, E) be a contracted rooted tree graph, with a set of v vertices V
and a set of e edges E, obtained from a rooted connected graph G(Vr , Er ). It
is assumed that there are no loops in the contracted rooted tree graph. For
synthesis purposes, loops can be substituted with equivalent serial chains in aprocess called reduction, which is explained in Section 5. Then the following
relations exist:
1. e = v − 1
2. Between any two vertices i and j where i 6= j there exists only onepath.
3. The only vertices with a degree of 1 will be either the graph root or an
end-effector.
4. There are no vertices of degree 2.
3. Forward Kinematics for Tree Topologies
The forward kinematics for a serial kinematic chain can be written using
the representation-agnostic exponential map [41],6Q̂(θ̂) =

n
Y

e

θ̂i
S
2 i

!
ĝ

(2)

i=1

where θ̂i = θi + di are the joint parameters written as a dual number,with θi and di being the rotation about and displacement along the screw
axis respectively; ĝ is the transformation from the fixed frame to the endeffector at a reference configuration; and Si is the ith joint axis at a reference
configuration.
The term ĝ can be eliminated by considering the forward kinematics ofrelative displacements with respect to this reference configuration, measured
from the fixed frame,Q̂(∆θ̂) =

n
Y

∆θ̂i

e 2 Si ,(3)

i=1

where ∆θ̂ = θ − θ0 + (d − d0 ), with θ0 and d0 being the values of the joint
parameters at the reference configuration.
For a linkage with a tree topology, a set of forward kinematics equations
can be written for each of the branches, considering the common joints in allof them,Q̂i (∆θ̂) =

ki
Y

e

j=1

|

ni
Y

∆θ̂j
Sj
2

e

∆θ̂i,jSi,j2,

i = 1, . . . , b(4)

j=ki +1{z

common}|{z

branch}where the number of common joints for a given branch i is indicated by ki ,and the number of end-effectors, or branches, is indicated by b. Each branchor serial chain has a total of ni joints, including the common joints sharedwith other branches.
4. Linkage Locus Space
For the most general case of a tree topology, where the joint axes canbe arbitrarily positioned in space, it is important to define the minimum
7subgroup of the special Euclidean group SE(3) able to contain the full motionof each end-effector. In the rest of this article, SE(3) will denote the special
Euclidean group and se(3) will denote its corresponding Lie algebra.
For a given serial chain with n joint axes Si , the workspace of relative
motion can be defined as
(
W =

w

n
Y

e

∆θ̂i
2

)
Si − w = 0,

∀θ̂

.

(5)

i=1

However, for performing synthesis, an extended version of the workspaceneeds to be considered; the potential workspace of a generic mechanism topology, as opposed to the particular workspace of a specific mechanism. In orderto define where the generic mechanism topology lies, the Linkage Locus Spaceis defined.
Let $J be the screw system corresponding to a given joint or set of joints
J, and let $∗J be the smallest subalgebra of se(3) containing all the possible
infinitesimal mechanical liaisons [42] between two rigid bodies of a serial
chain connected by that joint or set of joints. In general, this is calculated
for consecutive rigid bodies separated by a joint. However, in the case of
having constraints defined by relationships between joint parameters for two
or more consecutive rigid bodies in a serial chain, this cannot be calculated
as the mechanical liaison of individual joints.
For example $∗P would be the smallest subalgebra that contains all possible
infinitesimal mechanical liaisons of the form,
SP = λ (0; s) ,(6)which in this case would be $∗P = R3 . Consider the helicoidal joint, which
has the form
SH = λ (s; r × s + hs) .

(7)

The smallest subalgebra containing its generic version is $∗H = se(3).
Special relationships can also be considered using explicit calculation. As
an example, consider the case of a revolute joint followed by a cylindric joint
forming an RC chain, where both joints have the same rotation axis with
opposite angles. The coordinates of each joint would be
8SR = θ (s; rR × s)
SC = −θ (s; rC × s) + d (0; s) ,(8)with θ and d being the joint parameters. When considering all the displacements generated by the RC subchain,

∆θ̂R
∆θ̂C
WRC = w e 2 SR e 2 SC − w = 0,


∀θ̂ ,

(9)

which expand to the form
SRC = (0; θ(rR × s − rC × s) + ds) ,(10)

the smallest subalgebra of se(3) containing all possible screws of the form
SRC in this case would be R3 .
Considering the entire chain, it is possible to define the Linkage Locus
Space L as the smallest subalgebra of se(3) corresponding to the smallest
subgroup containing the generic workspace S for the given topology,
(
S=

w

n
Y

e

∆θ̂i
2

)
Si − w = 0, ∀θ̂, ∀S ∈ $∗
i

i

(11)

i=1

This can be calculated directly by finding the smallest subalgebra that
contains S or, given all the subalgebras of all the joints of the serial chain,by using the closure of subalgebras
L = $∗1

$∗2

···

$∗n

(12)

Proof. Firstly w can be expanded by using the well-known Campbell-BakerHausdorf series,

9

n
Y
∆θ̂i
log(w) = log( e 2 Si )
i=1

=

∆θ̂2
∆θ̂n
∆θ̂1
S1 +
S2 + · · · +
Sn +
2
2
2

1
(∆θ̂1 ∆θ̂2 [S1 , S2 ] + ∆θ̂1 ∆θ̂3 [S1 , S3 ] + · · · )+81(∆θ̂12 ∆θ̂2 [S1 , [S1 , S2 ]]+96∆θ̂1 ∆θ̂22 [S1 , [S1 , S3 ]] + · · · ) + · · ·(13)The closure of subalgebras from Eqn. (12) is a vector subspace containing
all the finite Lie products of the form,
L =< S1 S2 · · · Sn [S1 , S2 ] · · · [S1 , [S1 , S2 ]] · · · >(14)

It is straightforward to see that a linear combination of elements from
Eqn. (14) can be found for each element of log(w) in the form of,(∆θ̂1 ∆θ̂2∆θ̂n ∆θ̂1 ∆θ̂2 ∆θ̂1 ∆θ̂3
···
···)
2
2
2
8
8

(15)

From this it can be deduced that,log(w) ∈ L,∀w ∈ S(16)

and thus,log(S) ≤ L,

(17)

proving that log(S) is closed under the Lie bracket and is therefore asubalgebra of se(3). For simplicity let us take two arbitrary elements oflog(S) in the form of,1
X = X1 + X2 + · · · + Xn + [X1 , X2 ] + · · ·
2
10

(18)

The Lie bracket of two elements, which denoted as X and X ∗ respectively,
can be expanded as,
1[X1 + X2 + · · · + Xn + [X1 , X2 ] + · · · ,2
1
X1∗ + X2∗ + · · · + Xn∗ + [X1∗ , X2∗ ] + · · · ] =2∗∗[X1 , X1 ] + [X1 , X2 ] + · · · + [X2 , X1∗ ] + · · · +1([[X1 , X2 ], X1∗ ] + [[X1 , X2 ], X2∗ ] + · · · ) + · · ·2(19)

where each element in the summation belongs to L.
The subalgebras $∗i are also contained in log(S). As L is the smallest
subalgebra containing all $∗i , log(S) ≤ L, and log(S) contains all $∗i , it canbe established that,

log

n
Y

!
$∗i

e

= log(S) = L = $∗1

$∗2

···

$∗n

(20)

i=1

Therefore, in order to calculate dim(S), it is possible to calculate insteaddim(L) by means of iteratively adding successive higher order Lie brackets
for each subalgebra $∗i , until all the Lie brackets are linear products of thepreviously found Lie brackets.
As shown in the next section, the expressions developed here can be used
to define the dimension of the space in which all possible tasks for mechanismsof a given topology can be found. This is important for both being able todefine a task that is feasible for a given topology and also being able todetermine when exact synthesis can be performed.
5. Reduced Tree Topology for Exact Synthesis
The main objective of reduction is to find an equivalent tree graph for
performing exact dimensional kinematic synthesis. At the end of the process,the remaining serial chains or edges must have a finite number of solutions
for dimensional synthesis, while keeping the motion constraints of the original mechanism. An example of a complex graph representing a kinematic11

SarrusLinkage

R

R

R
R

P

R

R
R

R

R
PR
P

Figure 2: Reduction of a complex kinematic structure with a Sarrus linkage
to a tree graph.
structure being contracted and reduced to a rooted tree graph can be seenin Fig. 2.
In the case of open-loop chains, the mobility of the loops can be calculatedusing the well-known Chebyshev-Kutzbach-Grübler (CKG) equation:
F = λ(n − j − 1) +

j
X

fi

(21)

i=1

where F is the number of degrees of freedom of the mechanism, λ = dim(W )[10] is the number of allowed degrees-of-freedom of the space in which theend-effector moves, n is the number of links, j is the number of joints, andfi indicates the degrees of freedom of joint i.
However, this mobility does not take into account the actual structure of
the workspace. With a mobility of 4 the workspace could be redundantly defined, as would be the case of four prismatic joints. Therefore the dimensionof the linkage locus space must also be taken into account.
The number of redundant degrees-of-freedom r of a serial mechanism may
be calculated by

r=

j
X

fk − dim(L),

k=1

12

(22)

where fk denotes the number of degrees of freedom of joint k.
If r > 0 the mechanism is considered to have redundant degrees-offreedom. For a given relative transformation there will be an entire subspaceof joint parameters that will perform the transformation. These mechanisms
are not suitable for exact dimensional synthesis, as there will be a subspaceof solutions and not a finite number of solutions.
Chains without redundant degrees of freedom, able to move anywhere in
the Linkage Locus space L, may have subspaces of solutions too. The degrees
of freedom can be represented as the ordered screw surface $ of a mechanism
topology as:$ = [ $1 $2 · · · $n ]= $1 ⊕ $2 ⊕ · · · ⊕ $n ,(23)

where $i is the Lie subalgebra of joint i.
In order for the kinematic synthesis to have a finite number of solutions
the kinematic chain must comply withdim($) < dim(L).

(24)

The combined condition that the serial chains must comply with to beable to perform exact kinematic synthesis becomes,jX

fk = dim($) < dim(L).

(25)

k=1

Additionally, SE(3) is formed by SO(3) o R3 , R3 being a normal subgroup. The Lie bracket of any vector from the subspace of se(3) with any
vector of R3 belongs to R3 . In order to perform exact kinematic synthesis,
R3 must not be a subspace of the ordered screw surface,
6 ∃ s | (s; s0 ) ∈ $, ∀s0(26)Kinematic serial chains that either fully determine the Linkage Locus
space L or have redundant degrees of freedom must be substituted by other13

chains that preserve L while having a finite number of kinematic synthesis
solutions. This can be seen as solving a more constrained problem in orderto obtain intermediate positions, which are then used to solve the original
problem, albeit it will not have a finite number of solutions.
The process of substituting serial chains that are not suitable for exact
dimensional synthesis is not straightforward when there are many constraints
applied to the kinematic chain. For non-complex cases such as the 4P serial
chain it is simple to see that it must be substituted for the 2P serial chain,
which shares the L = R3 Linkage Locus space with no redundant degrees of
freedom.
5.1. Parallel Mechanism Equivalence
To be able to convert the graph to a tree graph the loops must be replacedwith their non-loop equivalents. Refer to the study of the mobility of singleloop kinematic chains done by Rico and Ravani [42] for a more in depth studyof types of kinematic loops.
Single kinematic loops can be split into two paths, corresponding to theclockwise and counterclockwise directions between two rigid bodies. In orderto study the mobility, the intersection of the subalgebras corresponding toboth paths must be analyzed. Depending on the class of the loops, different
steps must be taken to substitute the loop for a non-loop equivalent.
Trivial kinematic loops are the simplest class to handle. In this case theintersection is either the clockwise or counterclockwise path of the loop. A
path yielding the intersection is called the dominant path; the other path isto be removed, as the restrictions imposed by the dominant path are in fact
what are determining the workspace of the mechanism.
Exceptional kinematic loops have an intersection of subalgebras that is
not trivial and is not equal to neither path. The exceptional kinematic chain
loop can be substituted for the subalgebra corresponding to the intersection
which may not always have a simple equivalence. Fanghella and Galletti [43]find many equivalences of intersections using group theory, and Rico and
Ravani [42] do the same using Lie algebras. However, finding the equivalent
open kinematic chain is not always a simple task, depending on the mobility
class of the loop.
Kinematic chains with partitioned mobility can be removed from thegraph, that is, the edge representing the chain can be removed and bothvertices merged into a single one, as they do not have relative motion.

14

The remaining cases, which correspond to paradoxical kinematic chainsof classes 1 and 2, must be handled on a case-to-case basis, as there is no
general solution.
This process is to be repeated until there are no loops in the graph and it
becomes a tree graph. The equivalent serial chains also need to comply withthe serial chain requirements from Eqn. (25).
The reduction of a Sarrus linkage to an equivalent prismatic joint [44]can be seen in Fig. 2. The Sarrus linkage is formed by two 3R branches witha set of constraints that give it the same workspace as a single prismatic
joint. The problem can then be solved considering the Sarrus linkage to bea prismatic joint. Afterwards the motion of the prismatic joint can be used
to generate a Sarrus linkage.
6. Kinematic Synthesis
In this paper, the focus is on the exact dimensional kinematic synthesis
for a finite set of positions. Dimensional kinematic synthesis seeks to findthe location and orientation of all joint axes in order for each of the endeffectors to perform a given set of displacements. In this section, an overview
of the process for serial chains is presented, and in the next chapter it shallbe extended to tree topologies.
6.1. Design Equations
Using the relative forward kinematics from Eqn. (3), the design equations
for a serial kinematic chain to reach m finite positions areP̂1j =

n
Y

∆θ̂

j
i

e 2 Si ,j = 2, . . . , m,

(27)

i=1

where j = 1 is considered the reference configuration, and P̂1j = P̂j P̂1−1 .
This creates a set of design equations that can be solved in order to reachthe set of relative displacements P̂1j . Therefore the output of solving thedesign equations for a given task are the joint axes in the reference position
and the relative displacements of the joints to each of the remaining m − 1
positions.
In addition to the design equations, different equations can be included,
for example relationships between joint axes would be considered as additional constraints c. Furthermore, the design equations can be modified tohandle velocities and accelerations as done in [45].
156.2. The Synthesis Task
To be able to create the synthesis design equations from Eqn. (27), thenumber of variables and equations in the system must be accounted for. Twotypes of variables are considered: structural and joint parameters. Joint
parameters are those variables parameterizing the motion about the joints
and depend on the number of end-effector poses. Structural parameters
define the location of the joints and depend only on the number and typesof the joints. The total number of variables nx will benx = (m − 1)nj + ns ,(28)

where m is the number of task positions, nj = dim($) is the number of joint
variables, and ns is the number of structural parameters.
The complete set of equations includes design equations and constraints.
The design equations come from Eqn. (27) and depend on the number of
end-effector positions, while here it is assumed that constraints do not. The
total number of independent equations nf will be,nf = (m − 1)d + c(29)

where d = dim(L) and c is the number of constraints.
For the system to have a finite number of solutions, nx = nf must be
imposed for the task. From there the number of absolute positions needed
can be obtained,m=ns − c+ 1,
d − nj(30)

where all the equations are assumed to be independent.
This leaves he number of structural parameters ns to be calculated. While
this may seem like a simple task, it is not always straightforward. Generally
any unconstrained screw joint as the one in Eqn. (7) will have 7 parameters:h ∈ R, s ∈ R3 , and s0 ∈ R3 with two constraints s · s = 1 and s · s0 = 0, totaling 5 independent parameters. An unconstrained general revolute joint
has 4 parameters as h = 0. An unconstrained general prismatic joint has
2 parameters as they can be represented by lines at infinity with the form
(0; s) with s · s = 1.
16

Table 2: Design parameters for different serial chains
Linkage

nj

ns

d

m

mR

mT

L

P

1

2

3

2

1

2

R3

R

1

4

6

1 45

2

3

SE(3)
SE(3)

H

1

5

6

2

2

3 12

C

2

4

6

2

2

5

SE(3)

T

2

5

6

2 41

5

6

SE(3)

E

3

2

6

1 23

2

∞

SE(3)

S

3

3

6

2

∞

∞

SE(3)

PP

2

2

3

3

1

3

R3

RP

2

6

6

2 12

2

7

SE(3)

RR

2

8

6

3

5

9

SE(3)

PPR

3

6

6

3

2

∞

SE(3)

PRP

3

8

6

3 32

2

∞

SE(3)

5

∞

SE(3)

∞

∞

SE(3)

PRR

3

10

6

4 31

RRR

3

12

6

5

17

Table 2 shows various sets of kinematic chains. The constraints are considered implicitly as part of the structural parameters ns . Different combinations of joints and constraints can modify the number of parameters. A
striking example would be that two general prismatic joints PP have a totalof 2 parameters and not 4 as expected. This happens whenever two prismatic joints are consecutive in a kinematic serial chain, as their directions of
motion span a plane.
There is no general rule for calculating the number of structural parameters ns . However, the design equations Eqn. (27) can always be expanded
and checked for variable dependencies.
6.3. Task Degeneration
The m design equations obtained using Eqn. (30) are not necessarily
independent. In fact it is possible for the system of equations to degenerate
into two subsystems where one is overdetermined and the other has an infinite
number of solutions.
The special Euclidean group SE(3) can be seen as the semi-direct productof two subgroups, SE(3) = SO(3) o R3 . The same technique used to obtain
Eqn. (30) can be restricted to the subgroup SO(3) in order to determine thenumber of rotations needed for the change of orientation of the system. The
number of variables nR
x becomes,
RRRnR
x = (m − 1)nj + ns

(31)

where mR is the number of orientations, nR
j the number of joints with aRrevolute component, and ns the number of structural parameters for therotations.
The number of independent equations corresponding to rotations, nR
f , canbe defined byRRRnR
f = (m − 1)d + c ,(32)

where dR = dim(L ∩ so(3)) and cR is the number of constraints affecting therotational parameters in the design equations.
Hence, it is possible to define the number of independent orientationsRm needed to fully define the rotational component of design equations byRmaking nR
x = nf ,
18

R
nR
s −c
m = R
+1
d − nRj
R(33)

If mR ∈ Q+ there will be a limit on the number of independent orientations in the screw system that can be defined. If mR < m, the orientation of
the positions in the task can no longer be fully arbitrary, and m − mR orientations will be dependent on the arbitrary mR rotations. It is important toRremark that this only can happen when nR
j < d .
A similar counting can be done for the translational component of SE(3).
However, R3 is a normal subgroup of SE(3) and thus the equations can not
be decoupled. Following the same process as Eqn. (30) and Eqn. (33),mT =ns − c+ 1,dT − nj(34)

where dT = dim(L ∩ R3 ).
As can be seen from Eqn. (34), the translational part depends on all theparameters and variables while only providing dT independent equations.
A serial mechanism will be solvable using only translational information if
mT ∈ Q+ , which can only happen in systems with one or two single degreeof-freedom joints.
As a consequence, systems where mR < m and mT 6∈ Q+ will not be solvable for arbitrary positions. The positions need to be generated taking into
account the limitations of the mechanism in SO(3) to have a finite numberof solutions.
6.4. Defining Tasks
When defining a task three different scenarios with m ∈ Q+ can be identified depending on the topology of the mechanism to be synthesized.
1. When mR ≥ m and m ∈ Q+ the kinematic chain is fully solvable form arbitrary spatial positions. Additionally if mT ∈ Q+ , the kinematic
chain can be solved for only point locations without considering orientations.
2. When mR < m and m, mR , mT ∈ Q+ the kinematic chain can still besolved for arbitrary spatial positions. However, only mR positions may
R R
contain arbitrary rotations. An additional mT = dm−dd m positions
with only arbitrary translational component will have to be defined.
19

3. When mR < m with m, mR ∈ Q+ , and mT 6∈ Q+ the rotational component will be solvable for the mechanism. However, the translationalpart will not have a finite number of solutions. This type of topology can not be used to perform exact kinematic synthesis for arbitrary
positions. It is still possible to solve for finite solutions if the task
is generated within L in such a way that the rotational part is not
overdetermined, yet still possible to obtain the joint parameters foreach position.
7. Tree Kinematic Synthesis
Once a contracted tree graph representing a kinematic structure is obtained, rigid-body guidance for a finite number of task positions can be performed. For this, it is necessary to calculate the number of positions needed
for all the end-effectors to fully determine the kinematic structure and thus
to have a finite number of solutions.
As with serial kinematic chains, constraints are assigned to all vertices,degrees of freedom to all end-effector vertices, and joint variables and structural parameters to all edges. In the case of the degrees of freedom and joint
variables, which depend on the number of relative positions (m − 1), only thecoefficient multiplying (m − 1) will be represented. This will allow the usageof matrices to simplify the equations. The constraints are design parameters
and thus are known.
7.1. Design Equations
The design equations for tree systems are stated as in Eqn. (27), applying
them to all branches at the same time. This can be written as

i
=
P̂1k

ki
Y

e

∆θ̂jk
2

j=1

|

ni
Y

Sj

e

k
∆θ̂i,j2

Si,jj=ki +1{z

common}|{z

branchi = 1, . . . , b
k = 2, . . . , m,

(35)

}

where the number of common joints is indicated by ki and the number of
end-effectors, or branches, is indicated by b.
The definition of the task for the design equations is similar to what isdone in the previous section. Due to having multiple end-effectors, tasks
become sets of displacements. In the case of tree topologies more care must20

be taken to avoid task degeneration. This is explained in detail in the next
section.
7.2. Solving Substitutions
If the tree structure has had substitutions of parallel or serial kinematic
chains, once the reduced rooted tree graph has been solved, the substitutions can be undone and the solution used to create constraints allowing thesubstituted chain to be solved.
The substituted serial chains has both rigid bodies on either side determined, for each position. It is then possible to consider one of the rigid
bodies a reference and consider the other rigid body as the end-effector of
the chain with a motion equivalent to the relative motion between both rigid
bodies. However, as the substitution was done to obtain a finite number ofsolutions, there will be subspaces of solutions. Equation (27) can be applied
to perform the synthesis of the subspace.
In the case of substituted parallel chains, each branch can be treated as aseparate individual serial chain and can be solved using the same procedureused for the substituted serial chains.
8. Matrix Representation
This section covers the usage of some matrices associated to the tree
topologies. These are used for testing for degeneration in the solvability ofthe exact synthesis problem.
For a tree mechanism with v vertices, e edges and b branches, the e × b
reduced end-effector path matrix [T̃ ] is constructed by calculating the e ×(v − 1) path matrix [T ] and eliminating all columns that do not correspondto an end-effector. The path matrix is defined as,vertex j
t1,1 t1,2 · · · t1,v−1[T ] = t2,1 t2,2 · · · t2,v−1  ..
.. . .
.. 
 .
.
.
. 
te,1 te,2 · · · te,v−1
where,

21edge i(36)
1 if edge i lies on the path originating at the root,
ti,j =and terminating at the vertex j
0 otherwise.

(37)

The (v − 1) × e reduced incidence matrix [B̃] can be constructed as,

b1,1
 b2,1[B̃] =  ..
 .

edge jb1,2 · · ·b2,2 · · ·
..
..
.
.


b1,e
b2,e .. . vertex i(38)

bv−1,1 bv−1,2 · · · bv−1,ewhere,(
1 if vertex i is connected to edge jb̃i,j =
0 otherwise.

(39)

The matrix representation of the graph can be used to work with anddefine the conditions for exact kinematic synthesis. For this purpose, vectorsthat represent the number of joint degrees-of-freedom and structural parameters for the edges and the number of degrees-of-freedom and constraints of
the nodes shall be defined.
8.1. Task Sizing using Matrices
In order to be able to perform exact kinematic synthesis, the global systemof equations obtained using Eqn.(35) must be solvable. This in turn defines
the maximum number of positions that can be required, as it is done withsimple serial chains. Notice that we require the same number of positions
m for each end-effector. However, for exact synthesis of tree topologies, thecriterion is necessary but not sufficient due to the existence of subgraphs,
which will be discussed in the next subsection.
The number of unknowns for each edge are arranged into two e×1 vectors,
denoted as Dej for joint degrees-of-freedom and Des for structural parameters,
so that the total number of unknowns is22

nx = (m − 1)Dej + Des

T

E,

(40)

where E is a vector of ones for the edges in the graph considered.
The number of node equations is obtained using b × 1 vectors, denotedas Dnee for the end-effector degrees-of-freedom and Dnc for the constraints oneach branch,nf = ((m − 1)Dnee + Dnc )T B.

(41)

In this equation, we can take B as a b × 1 vector of ones corresponding tobranches, or end-effectors. Another option, if we want to keep the informationof what constraint is associated to what vertex, is to take B as the vector
for the vertices in the graph considered, not counting the root vertex. In
this case we need to modify vectors Dnee , adding zeros in those vertices thatare not end-effectors, and Dnc , which will associate constraints to specificbranches.
In order for the system to have a finite number of solutions, nf = nx must
be imposed, from which the number positions m needed for exact synthesis
can be obtained,m=(Des )T E − (Dnc )T B
+1
(Dnee )T B − (Dej )T E

(42)

where the system will be unsolvable if m 6∈ Q+ . However, this criteria is
necessary, but not sufficient for the system to be solvable.
Additionally, as seen in Section 6.3 for serial chains, care must be takenwith the subgroups SO(3) and R3 of SE(3). This can be done by defining
the number of positions needed for the rotational part mR of the mechanism
as,

mR =

nR T
T
(DeR
s ) E − (Dc ) B
+1
eR T
T
(DnR
ee ) B − (Dj ) E(43)where the supraindex R denotes the restriction to the number of equations orvariables that affect the SO(3) component of the design equations (27) only.
23

The criteria is then exactly the same as defined for serial chains in Section 6.4, although translation-only tasks have not been covered as they areof little or no interest for tree topologies due to the limitation of only one or
two joints per serial chain.
8.2. Subgraphs
It is sometimes possible to find proper subgraphs within the tree graphrepresenting a kinematic structure that is solvable separately. These subgraphs will generally need a different amount of end-effector positions to besolved for, and will always end up having a smaller equation system size when
performing exact kinematic synthesis. However, if subgraphs exist within thesystem, not all end-effectors will necessarily need the same number of positions. This is because, for a given number of positions as calculated by
Eqn. (42), it may so happen that a subgraph becomes overdetermined.
An interesting consequence of this phenomenon is that it only allows for
simultaneous solution of tree kinematic structures where all chains from theroot to end-effector have more or equal mobility than needed to reach theentire linkage locus space L of the end-effector. If any kinematic chain hasless mobility than needed to reach the entire linkage locus space L of the endeffector, it will always form a subgraph that is solvable separately. Figure 3
presents an example of a graph with solvable subgraphs.
Hence a sufficient, but not necessary condition for the system to be solvable is that it must have no proper solvable subgraphs, that is, subgraphsthat comply with m ∈ Q+ using Eqn. (42). In order to check for this condition, all possible proper subgraphs must be tested. This can be expressedusing the reduced path matrix,ee

Ei = [T̃ ]B̃i
ee

(44)
[>0]

where B̃i is a b × 1 vector representing the end-effectors considered for agiven subgraph i. The Iverson bracket [> 0] is used to denote that elementsof E vector should be either be 1 if > 0 or 0 otherwise. There are 2b − 2
possible subgraphs for any given rooted tree graph representing a reduced
kinematic structure, excluding both the full graph and the null graph.
Given Ei corresponding to the edges in a subgraph, the Bi nodes in thesubgraph can be calculated by,

24

G1

RP
PR

RR

G2

Figure 3: Both branches with fewer than dim(L) = 6 joints form subgraphs
G1 and G2 that are solvable separately.

Bi = [B̃]Ei

(45)
[>0]

This criteria is sufficient, but not necessary. While it does always generate
the smallest system size for performing exact synthesis, it increases the number of end-effector positions needed. A more lax criteria can be used instead,in which cases where the subgraphs are separately solvable are considered.
For each subgraph i, Eqn. (42) can be used to calculate the number of
positions needed for exact synthesis of the subgraph,mi =(Des )T Ei − (Dnc )T Bi+ 1,(Dnee )T Bi − (Dej )T Ei

(46)

ee

where again we could use B̃i instead of Bi if we lump together all theconstraints for each given branch.
A necessary and sufficient criteria for determining the solvability of agraph is, given the number of positions m needed for exact synthesis of thesubgraph, for all proper subgraphs i in the graphm ≤ mi , if mi ∈ Q+

(47)

Additionally, as in the general case, SO(3) and R3 must be consideredseparately. Given a number of rotational components of the m positions,denoted as mR , the following additional criteria are obtained:25

R+
mR ≤ mRi , if mi ∈ Q(48)

where mR
i are the number of frames needed to solve only the rotation partfor subgraph i of the mechanism.
If these criteria are not met, then the subgraph i where either m > mior mR > mRi becomes overdetermined, while other kinematic chains become
underdetermined by the overall set of positions m. The system of equations
for exact kinematic synthesis is no longer guaranteed to have any solutions
when the same number of task positions is defined for each end-effector. In
this case, the system will not be solvable.
Finally, it must be noted that checking a single rooted tree graph is notenough. In order to ensure that the mechanism is solvable, all the endeffectors must be set as the root node and all the subgraphs from theserooted tree graphs must be analyzed. This means that in general, in orderto establish if a topology is solvable, all the b(2b − 2) subgraphs arising fromall the different possible root node arrangements must be checked.
8.3. Solvable Tree Graph
Definition Let T be a contracted tree graph representing a kinematic structure and S be the set of subgraphs of all possible rooted tree graphs arisingfrom setting each end-effector of T as the root of the graph. T will be calledsolvable for a finite number of independent positions if,
1. m ∈ Q+
2. m ≤ mi , ∀mi ∈ Q+ , i ∈ S
R+
3. mR ≤ mR
i , ∀mi ∈ Q , i ∈ S
The advantage of solving a tree with subgraphs is that the workspace canbe defined by a smaller number of positions of all end-effectors at the sametime. However, the dimension of the equation system will always be larger
than solving the smallest subgraph first and using the results to solve othersubgraphs and eventually the entire graph.
9. Examples
In this section three different examples that focus on different parts of thedimensional synthesis are presented. For the notation of contracted rooted
26

V4

V3
4R
E2

E3 4R
V2

3R
V1

E1
5R E6

5R

V5

E4
5R
E5
V6

V7

Figure 4: Rooted tree graph of an anthropomorphic hand model.
kinematic trees, hyphens will be used to indicate serial links and parenthesis
to indicate parallel links.
The first example is a 3R-(4R,4R,5R,5R,5R) manipulator, representing
a human hand, where the focus is on using the matrix approach presented
to determine the independently solvable subgraphs of the mechanism. The
second example is a more simple RP-(R,P) mechanism where the focus is on
solving the dimensional synthesis problem algebraically using the techniqueof changing the root node in order to make it a more tractable problem. The
last example is a 2R-(2R,R,R) manipulator which would be of a complexity
between the other two examples, for which numeric results of a solution arepresented.
9.1. Anthropomorphic Hand Model Subgraphs
Previously presented work performed kinematic synthesis on an anthropomorphic hand model with 5 fingers and a total of 26 revolute joints [39]and it is the first mention of dimensional kinematic synthesis applied to tree
topologies. The anthropomorphic hand model will be revisited using the newtools presented in this paper for dimensional synthesis.
The anthropomorphic hand model is organized as a 3R-(4R,4R,5R,5R,5R)
tree, where the wrist is considered to have 3 revolute joints which are common
to the five fingers. The index and middle fingers have 4 revolute joints, while
the third finger, fourth finger and thumb have 5 revolute joints. This gives a
total of 26 revolute joints. There are not any constraints besides the implicit
constraints of the joints.
The contraction of the individual joints in this case is trivial as there
are no closed loops and all serial chains are formed by revolute joints. The
27

contracted graph can be seen in Fig. 4 and has all the edges and vertices
labeled. It is also easy to see that in this case there is no edge with 6 ormore revolute joints, which is a necessary, but not a sufficient condition forthe structure to be solvable if there are no additional constraints.
As the system is formed entirely by revolute joints, it is straightforward
to assign the 6 × 1 vectors associated with the joint degrees-of-freedom Dej
and the structural parameters Des ,T
Dej = 3 4 4 5 5 5TDes = 12 16 16 20 20 20 ,(49)

as revolute joints have 4 structural parameters associated to them.
The same can be done with the vertices, which are 5×1 vectors associatedto the end-effector degrees-of-freedom Dnee and constraints Dnc ,T
Dnee = 6 6 6 6 6T
Dnc = 0 0 0 0 0(50)

Notice that in this case all end-effectors have a linkage locus space L = se(3)and no additional constraints.
The number of positions needed for the entire system to perform exact
kinematic synthesis can be now be computed. This is done by using Eqn. (42)with all the edges and branches,E= 1 1 1 1 1 1
B= 1 1 1 1 1
26 · 4 − 0m=+ 1 = 27
6 · 5 − 26

(51)

Additionally the rotational components must also be checked by calculating the system that interacts with SO(3),

28


DeR
j = 3

6
DeR
=
s

DnR
ee = 3

DnR
c = 0

T
4 4 5 5 5
8 8 10 10 10T
3 3 3 3
T
0 0 0 0

T

(52)

Now by using Eqn. (43) the number of rotation positions mR needed,considering only the rotational component, can computed as,mR =26 · 2 − 0
41+1=−
3 · 5 − 26
11

(53)

6∈ Q+ it can be seen that the system
With m = 27 ∈ Q+ and mR = −41
11meets another necessary, but not sufficient condition of solvability. For it
to be solvable all the subgraphs must comply with Eqn. (47). This can bedone by first determining the reduced path matrix [T̃ ] and reduced incidence
matrix [B̃]. The path matrix consists on the edges that lie on the path to agiven node. This is relative to the root node, which for this example is V1 .
The reduced path matrix can be written as,
V3

V4

V5

V6

V7

1

E2
 1
E3  0[T̃ ] =
E4  0
E5  0
E6
0

1
0
1
0
0
0

1
0
0
1
0
0

1
0
0
0
1
0


1
0 

0 

0 

0 
1

E1



(54)

where it can be seen that there are no columns for either V1 or V2 as they
are not end-effectors and have been eliminated.
The reduced incidence matrix [B̃] is,

29

E1

E2

E3

E4

E5

E6

1

V3
 0
V4  0[B̃] =
V5  0
V6  0
V7
0

1
1
0
0
0
0

1
0
1
0
0
0

1
0
0
1
0
0

1
0
0
0
1
0


1
0 

0 

0 

0 
1

V2



(55)

where it can be seen that there is no first row for the root vertex V1 .
Now the end-effectors must be iterated on using Eqn. (44) to construct theedges leading to the end-effectors and Eqn. (45). There are in general 2b − 2
possible proper subgraphs given a root node. However, in this case there aresymmetries as many branches are the same leading to many equivalent subgraphs. For single branches they can be studied using the single serial chain
equation from Eqn. (30) and in this case it is easy to see that all branches
need a negative number positions. Therefore none of these subgraphs are
solvable systems.
Next the two branches with 4 revolute joints (index and middle finger)
are considered,TeeB̃6 = 1 1 0 0 0(56)

The system has the following edges,ee

E6 = [T̃ ]B̃6


T
= 2 1 1 0 0 0
[>0]
[>0]

T
= 1 1 1 0 0 0(57)

and the following vertices,T
B6 = [B̃]E6 = 1 1 1 1 0 0 0(58)

It can also be seen graphically in Fig. 4 that this system has indeed
only the edges E1 , E2 , E3 and vertices V1 , V2 , V3 , V4 . The value m6 can becalculated by Eqn. (46),30

Table 3: All solvable subgraphs of the anthropomorphic hand model
Subgraphbrmnf = nx

3R-(4R,4R,5R,5R,5R)

5

26

27

780

3R-(4R,5R,5R,5R)

4

22

45

1056

3R-(4R,4R,5R,5R)

4

21

29

672

3R-(4R,5R,5R)

3

17

69

1224

3R-(4R,4R,5R)

3

16

33

576

3R-(4R,4R)

2

11

45

528

m6 =

4 · 11 − 0+ 1 = 456 · 2 − 11(59)

Furthermore mR
6 can be calculated as,
m6 =2 · 11 − 0
17+1=−
3 · 2 − 11
5

(60)

+
With mR
6 6∈ Q and m6 = 45 ≥ m = 27 this subgraph is solvable. This
process has to be continued for all the possible subgraphs of this rooted tree
graph and other rooted tree graphs arising from setting the root to the otherend-effectors {V3 , V4 , V5 , V6 , V7 }. However, for this mechanism, there exists
no separately solvable subgraph that is not already a subgraph of the original
rooted tree graph. If all these possible subgraphs meet the criteria it can besaid that the graph is solvable.
After analyzing all the possible subgraphs, the results seen in Table 3
can be obtained. From this it can be seen that all the possible subgraphs
were found in [39] and that the entire system is solvable. It is also important to note that all the end-effectors have L = se(3) and L ∩ so(3) = so(3).
Therefore all m positions defined in the task can have arbitrary orientationand location. This is generally true for all unconstrained pure revolute joint
systems that are solvable.
Now that the task specifications have been defined for the mechanism,
synthesis can be performed for a specific task, consisting of m spatial positions, by solving the design equations from Eqn. (35). In our previous work

31

R
PR

P

Figure 5: Rooted tree graph of the RP-(R,P) mechanism.
[39, 45] a numerical optimization scheme has been employed, based on a
genetic algorithm and a Levenberg-Marquadt minimization, which has been
proven to be successful at finding operative solutions.
9.2. Algebraic PR-(R,P)
The PR-(R,P) consists of two common joints: one prismatic and one
revolute, which fork into two branches, one being a revolute joint and theother a prismatic joint as seen in Fig. 5. In this case, there are two subgraphs
corresponding to a PRR mechanism and a PRP mechanism. To decrease
the global equation system size, either subgraph can be solved individuallyand then the results can be used to solve the remaining joint. However, thisrequires more task positions for the first branch solved than for the remaining
joint. Heterogeneous numbers of positions for each end-effector are generally
not desired.
From Eqn.(42) the number of positions needed for all possible chains canbe counted as shown in Table 2. The PRR chain needs m = 3 positions,the PRP chain needs m = 3 21 positions and the entire system needs m = 2 21
positions. Notice that the entire system needs fewer positions than either
branch.
It can be seen, using Eqn. (43), that the PRR chain needs mR = 5 positions, the PRP chain needs mR = 2 position and the entire system would alsoneed mR = 2 positions. In the case of the PRP chain, the exact synthesis
is limited by mR to only two positions with a rotational component. Therefore when defining the task, some additional positions without orientation
information will have to be added.
In order to make sure the system is still solvable, the limit of translations mT must also be checked for all subgraphs. For the PRR and PRP
chain mT = ∞ is obtained, while for the entire system mT = 7 is obtained.
This indicates that only the entire system is solvable for only translations
32

Table 4: Solvability of the different subgraphs of the PR-(R,P) mechanism
Subgraph

m

mR

mT

Comments

PR-(R,P)

2 12

2

7

Full system, rotational and translational components solvable

PRR

3

5

∞

Full system and rotational component solvable

PRP

3 12

2

∞

Only rotational component solvable mR < m
and mT 6∈ Q+

and additionally that the PRP subgraph is only solvable using rotational
components. The results of the solvability are summed up in Table 4.
Being a simple mechanism it can also be solved algebraically. Consider
the kinematic chain from one end-effector to another. This can be thoughtof as changing the root node to one of the end effectors and then solving a
subgraph. The initial forward kinematics of both branches can be written
as,ŜPc (dc )ŜRc (θc )ŜR (θ)=

P̂P RRŜPc (dc )ŜRc (θc ) ŜP (d)|{z} | {z }=P̂P RP| {z }

commonbranch(61)

pose

By considering the kinematic chain from one end-effector to another thecommon joints can be eliminated leading to the following kinematic chain:ŜP (d)−1 ŜR (θ) = P̂P−1RP P̂P RR(62)

where ŜP (d)−1 is equivalent to ŜP (−d). This is analogous to making theend-effector at the end of the P edge the root of the system and solving thesubgraph formed by the PR branch in the new tree graph.
This can be solved algebraically and gives a single solution. Given thesolution, the position of the rigid body connecting the common branches canbe solved as a serial chain,
ŜPc (dc )ŜRc (θc ) = P̂P RP ŜP (−d)
33

(63)

which also has a single solution. Furthermore the entire system has a single
solution.
Therefore the problem can be treated as two separate PR chains andsolved individually. The number of positions each PR chain needs is m = 2 12
and is coincidentally the same as the number of positions needed for theentire system. The solution process is the same as in [46].
Having m = 2 12 6∈ N+ , fully arbitrary positions cannot be defined. WithmR = 2 and mT = 7, the translation of three positions and the orientationof two of them can be defined in order to perform kinematic synthesis. If
more than 2 orientations are defined, the rotational component of the system
becomes overdetermined. The positions can be defined as,P̂12 = P̂P−1RP P̂P RR
P̂13 = P̂P−1RP P̂P RR

12
13

0
w0
= sw
12 + b12 + (s12 + b12 )
0
w0
= sw
12 + b12 + (s13 + b13 )(64)

where it can be seen that they share the same orientation.
Using the real part, the rotation axis of the R joint, g, and the rotation
angle about it, θ, can be computed as,

g=

b12
,
kb12 ktan θ =

kb1i k,sw
1i

i = 2, 3(65)

The dual part can then be used to solve for the moment of the line defining
the R joint, g0 , and for the direction of the P joint, h,
g0 = b01i −

d1i
θ1i
θ1i
(cos h + sin g × h),222

i = 2, 3(66)

by imposing khk = 1 and
sw0
sw0
12
13
=
d12
θ12
d13
θ13
sin
sin
2
2
2
2

(67)

This characterizes the RP joint formed by the two end-effector edges.
Knowing the slide and direction of the P joint, d1i and h, the relative transformation from the end-effector of the P joint to the vertex between the PR
34

E3
R6
R2
R3

R1

E2

R5
R4

E1

Figure 6: Rooted tree graph of the RR-(RR,R,R) mechanism. In order tomore easily identify the individual joints, this graph is displayed without
being compacted.
chain and the P joint can be calculated to obtain two new relative transformations,c
Ŝ12= P̂P RP ŜP (−d)
cŜ13= P̂P RP ŜP (−d)

12
13

c
0c
w0c
= swc
12 + b12 + (s12 + b12 )
c
0c
w0c
= swc
12 + b12 + (s13 + b13 )(68)

The procedure follows as before where the new system is determined byusing Eqn. (65) and Eqn. (66), and thus obtaining all the joint variables andstructural parameters of the system.
The entire system yields a single unique solution. The method for solving
the RP-(R,P) kinematic structure is not general as not all kinematic structures can be split into two non-overlapping substructures that can be solved
with the same number of task positions. However, this example shows anovel methodology that can be used on many structures.
9.3. Numeric RR-(RR,R,R)
The RR-(RR,R,R) can be thought of as a very simple hand model. The
graph of the mechanism can be seen in Fig. 6. It has two revolute joints
in the wrist (R1 and R2 ), two fingers with a single revolute joint each forholding objects (R5 and R6 ) and a thumb with two revolute joints in orderto perform more dexterous object manipulation (R3 and R4 ).
As with any other tree, the first step is to identify all the subgraphsand determine if it is possible to perform exact dimensional synthesis on themechanism. For the sake of brevity this is not analyzed in depth for this35

Table 5: Input task positions for the 2R-(2R,R,R) mechanism given as dual
quaternions
Frame
E1

E2

E3

P̂

1

0.368 − 0.737i − 0.446j − 0.350k + (0.174i + 3.098j − 0.493k + 3.635)

2

0.113 + 0.835i + 0.402j + 0.359k + (6.005i − 6.954j − 4.810k − 4.340)

30.759 − 0.638i − 0.109j − 0.073k + (−0.023i + 4.115j + 2.019k + 0.764)

1

0.070 + 0.621i + 0.665j + 0.409k + (2.076i − 0.232j − 2.086k − 4.013)

20.967 − 0.027i − 0.191j − 0.165k + (1.306i + 1.974j + 1.998k + 0.769)

3

0.998 + 0.002i + 0.063j + 0.014k + (−0.169i + 1.106j − 0.325k − 0.065)

1

0.356 + 0.392i + 0.678j + 0.510k + (−4.285i + 4.559j − 1.975k − 1.126)

2

0.975 − 0.005i − 0.214j − 0.065k + (0.811i + 0.932j + 0.588k + 0.248)

3

0.614 + 0.619i + 0.487j + 0.054k + (0.129i + 0.586j − 3.281k − 0.307)

mechanism, although it can be seen that it is indeed solvable for m = 3
positions.
Consider a randomly generated task consisting of three positions for each
end-effector, as shown in Table 5. Equation (35) is then solved numerically using a global optimization algorithm based on the fusion of a Genetic
Algorithm and Levenberg-Marquadt local optimizer [39]. Many different solutions are obtained, making it necessary to establish some criteria to chosethe desired solution.
The numerical results for one of the solutions are shown in Table 6, including screw axes and inverse kinematics for the defined task. See an example
of implementation of the presented solution in Fig. 7.
10. Conclusions
This paper presents a methodology for the finite-position dimensional
synthesis of articulated systems with a tree structure. The design process isbased on existing techniques for the dimensional synthesis of spatial serial
chains; however, in the design of tree-like topologies specific issues appear
that are explored and solved for the first time in this work.
The method is based on representing the tree as a rooted graph andperforming reduction operations in order to simplify the initial topology.
36

Table 6: An example solution for the RR-(RR,R,R) mechanism. The joints
are described using the Plücker coordinates in the reference frame
s

s0

∆θ2

∆θ3

R1

(0.856, 0.376, 0.354)(−3.292, 3.415, 4.339)

0.383

4.142

R2

(−0.497, −0.473, −0.728)(−1.510, −8.052, 6.262)

1.000

1.883

R3

(−0.870, −0.355, 0.341)(−26.900, 51.540, −15.030)

0.532

0.290

R4

(−0.300, −0.705, −0.642)(8.196, 0.882, −4.798)

6.401

1.226

R5

(−0.505, −0.698, −0.508)(−6.383, 1.045, 4.905)

2.842

5.358

R6

(0.155, 0.772, 0.616)(0.055, 1.364, −1.724)−2.194

3.167

The forward kinematics equations for each of the serial chains forming thetree articulated system are stated and equated to a set of task positions, fromwhich conditions for the solvability of the whole tree and individual subgraphs
or branches of the tree are derived. The inclusion of tree articulated systems
among possible candidate topologies for the design process allows to extend
dimensional synthesis to systems with a high number of degrees-of-freedom
and more complex motion tasks.
This methodology’s main application is the design of novel multi-fingered
hands for human-robot interaction, where a non-anthropomorphic hand could
be used to perform tasks in cooperation with humans. The method is currently limited to the exact finite-position synthesis and hence it does notaccount for performance issues derived from the pass from a finite set of positions to a continuous trajectory, such as the existence of self-intersections
or singularities while performing the task. The addition of conditions forthese and other performance requirements, as well as for grasping, is to beconsidered in future work.
Acknowledgements
This work is supported by the National Science Foundation under Grant
No. 1208385. The content is solely the author’s responsibility.

37

Figure 7: Two views of a possible implementation for the selected solution.
References[1] R. Hartenberg, J. Denavit, Kinematic Synthesis of Linkages, McGrawHill, 1964.
[2] B. Roth, Finite position theory applied to mechanism synthesis, Journalof Applied Mechanics 34 (1967) 599–605.
[3] G. N. Sandor, A. G. Erdman, Advanced Mechanism Design: Analysis
and Synthesis, Vol. 2, Prentice-Hall, Englewood Cliffs, NJ, 1984.
[4] C. Suh, C. Radcliffe, Kinematics and Mechanisms Design, John Wiley,
1978.
[5] P. Chen, B. Roth, Design equations for finitely and infinitesimally separated position synthesis of binary link and combined link chains, ASME
Journal of Engineering for Industry 91 (1967) 209–219.
[6] G. Sandor, K. Bishopp, On a general method of spatial kinematic synthesis by means of a stretch-rotation tensor’, Journal of Engineering for
Industry 91 (1969) 115–122.
38

[7] E. Lee, C. Mavroidis, Geometric design of 3r manipulators for reachingfour end-effector spatial poses, The International Journal of Robotics
Research 23(3) (2004) 247–254.
[8] J. M. McCarthy, G. Soh, Geometric Design of Linkages, Springer-Verlag,
New York, second edition, 2010.
[9] M. L. Husty, M. Pfurner, H.-P. Schrocker, K. Brunnthaler, Algebraic
methods in mechanism analysis and synthesis, Robotica 25 (2007) 661–
675.
[10] J. Angeles, Spatial Kinematic Chains. Analysis, Synthesis, Optimization, Springer-Verlag, New York, 1982.
[11] J. Merlet, D. Daney, Dimensional synthesis of parallel robots with aguaranteed given accuracy over a specific worskpace, in: Proc. of the2005 International Conference on Robotics and Automation, Barcelona,
Spain, pp. 942–947.
[12] H. Su, J. M. McCarthy, L. T. Watson, Generalized linear product homotopy algorithms and the computation of reachable surfaces, ASME
Journal of Computers and Information Science and Engineering 4(3)(2004) 226–235.
[13] G. Gogu, Structural Synthesis of Parallel Robots. Part 1: Methodology,
Springer, first edition, 2007.
[14] J. M. Herve, The lie group of rigid body displacements, a fundamental
tool for mechanism design, Mechanism and Machine Theory 34 (1999)
717–730.
[15] L. Woo, Type synthesis of plane linkages, ASME Journal of Engineering
for Industry (1967) 159–172.
[16] M. Huang, A. Soni, Application of linear and nonlinear graphs in structural synthesis of kinematic chains, Journal of Engineering for Industry(1973) 525–532.
[17] N. Manolescu, A method based on baranov trusses and using graphtheory to find the set of plane jointed kinematic chains and mechanisms,
Mechanisms and Machine Theory 8 (1977) 3–22.
39

[18] F. Freudenstein, E. R. Maki, The creation of mechanisms according tokinematic structure and function, Journal of Environment and Planning
6 (1979) 375–391.
[19] L. W. Tsai, Mechanism Design: Enumeration of Kinematic Structures
According to Function, CRC Press, Boca Raton, 2001.
[20] T. Mruthyunjaya, Kinematic structure of mechanisms revisited, Mechanism and Machine Theory 38 (2003) 279–320.
[21] Y. Lu, e. a. Mao, B.Y., Derivation of valid contracted graphs from simpler contracted graphs for type synthesis of closed mechanisms, Mechanism and Machine Theory 52(3) (2012) 206–218.
[22] Y. Lu, e. a. Mao, B.Y., Analysis and determination of associated linkage,
redundant constraint, and degree of freedom of closed mechanisms withredundant constraints and/or passive degree of freedom, ASME Journalof Mechanical Design 134(5) (2012).
[23] C. Chuang, J. Lee, Topological synthesis of underactuated passively
adaptive finger mechanisms, in: Proc. of the 13th World Congress in
Mechanism and Machine Science, Guanajuato, Mexico.
[24] J. M. Selig, Geometric Fundamentals of Robotics (Monographs in Computer Science), SpringerVerlag, 2004.
[25] N. Biggs, Discrete Mathematics, 1985.
[26] I. Chen, G. Yang, I. Kang, Numerical inverse kinematics for modular
reconfigurable robtos, Journal of Robotic Systems 16(4) (1999) 213–225.
[27] G. Song, N. Amato, A motion-planning approach to folding: from paper
craft to protein folding, IEEE Transactions on Robotics and Automation
20(1) (2004) 60–71.
[28] A. Jain, Graph-theory roots of spatial operators for kinematics anddynamics, in: Proc. of the 2010 International Conference on Robotics
and Automation, Anchorage, Alaska, USA, pp. 2745–2750.
[29] J. Garcia de Jalon, E. Bayo, Kinematic and Dynamic Simulation ofMultibody Systems: The Real-Time challenge, Springer-Verlag, 1994.
40

[30] S. Stramigioli, Modeling and IPC control of interactive mechanical systems - A coordinate-free approach, volume LNCIS 266, Springer, 2001.
[31] C. Tischler, A. Samuel, K. Hunt, Kinematic chains for robot hands - 1.
orderly number synthesis, Mechanism and Machine Theory 30(8) (1995)
1193–1215.
[32] C. Tischler, A. Samuel, K. Hunt, Kinematic chains for robot hands ii:
Kinematic constraints, classification, connectivity and actuation, Mechanism and Machine Theory 30(8) (1995) 1217–1239.
[33] L. Briglen, T. Laliberte, C. Gosselin, Underactuated Robotic Hands,
Springer, 2008.
[34] A. Ciocarlie, P. Allen, Data-driven optimization for underactuatedrobotic hands, in: Proc. of the 2010 International Conference on
Robotics and Automation, Anchorage, Alaska, USA, pp. 1292–1299.
[35] J. Belter, A. Dollar, Performance characteristics of anthropomorphic
prosthetic hands, in: Proceedings of the 2011 IEEE International Conference on Rehabilitation Robotics, pp. 921–927.
[36] L. Biagiotti, F. Lotti, C. Melchiorri, G. Vassura, How Far is the Human
Hand? A Review of Anthropomorphic Robotic End-effectors. Internalreport, Technical Report, Universita di Bologna, 2004.
[37] J. Dai, D. Wang, Geometric analysis and synthesis of the metamorphic
robotic hand, ASME Journal of Mechanical Design 129 (2007) 1191–
1197.
[38] A. Perez Gracia, J. M. McCarthy, The kinematic synthesis of spatialserial chains using clifford algebra exponentials, Proceedings of the Institution of Mechanical Engineers, Part C, Journal of Mechanical Engineering Science 220(7) (2006) 953–968.
[39] E. Simo-Serra, F. Moreno-Noguer, A. Perez-Gracia, Design of NonAnthropomorphic Robotic Hands for Anthropomorphic Tasks, in: Proc.
of the 2011 ASME International Design Engineering Technical Conferences, Washington D.C., USA.

41

[40] F. R. E. Crossley, A cotribution to grubler’s theory in the number
synthesis of plane mechanisms, Transactions of the ASME Journal ofEngineering for Industry (1964) 1–8.
[41] R. M. Murray, Z. Li, S. S. Sastry, A Mathematical Introduction to
Robotic Manipulation, CRC Press, Inc., Boca Raton, FL, 1994.
[42] J. M. Rico, J. Gallardo, B. Ravani, Lie algebra and the mobility ofkinematic chains, Journal of Robotic Systems 20 (2003) 477–499.
[43] P. Fanghella, C. Galletti, Metric relations and displacement groups inmechanism and robot kinematics, Journal of Mechanical Design 117(1995) 470–478.
[44] J. M. Rico, B. Ravani, On calculating the degrees of freedom or mobilityof overconstrained linkages: Single-loop exceptional linkages, Journal of
Mechanical Design 129 (2007) 301–311.
[45] E. Simo-Serra, A. Perez-Gracia, H. Moon, N. Robson, Design of Multifingered Robotic Hands for Finite and Infinitesimal Tasks using Kinematic Synthesis, in: J. Lenarcic, M. Husty (Eds.), Recent Advances in
Robot Kinematics, Springer, 2012.
[46] A. Perez-Gracia, Synthesis of spatial rprp closed linkages for a given
screw system, ASME Journal of Mechanisms and Robotics 3(2) (2011).

42