Solving the Inverse Kinematic Robotics Problem: A Comparison Study of
the Denavit-Hartenberg Matrix and Groebner Basis Theory
Except where reference is made to the work of others, the work described in this
dissertation is my own or was done in collaboration with my advisory committee. This
dissertation does not include proprietary or classifled information.
Kimberly Kendricks
Certiflcate of Approval:
Michel Smith
Professor and Chairman
Mathematics and Statistics
Overtoun Jenda, Chair
Professor
Mathematics and Statistics
Richard Zalik
Professor
Mathematics and Statistics
Joe F. Pittman
Interim Dean
Graduate School
Solving the Inverse Kinematic Robotics Problem: A Comparison Study of
the Denavit-Hartenberg Matrix and Groebner Basis Theory
Kimberly Kendricks
A Dissertation
Submitted to
the Graduate Faculty of
Auburn University
in Partial Fulflllment of the
Requirements for the
Degree of
Doctor of Philosophy
Auburn, Alabama
August 4, 2007
Solving the Inverse Kinematic Robotics Problem: A Comparison Study of
the Denavit-Hartenberg Matrix and Groebner Basis Theory
Kimberly Kendricks
Permission is granted to Auburn University to make copies of this dissertation at its
discretion, upon the request of individuals or institutions and at
their expense. The author reserves all publication rights.
Signature of Author
Date of Graduation
iii
Vita
Kimberly D. Kendricks was born on August 27, 1980 in Dayton, Ohio. After completing
high school, she attended the University of Pittsburgh in Pittsburgh, Pennsylvania, where
she received a Dual B.S. in Mathematics and Business. Then, she continued her passion for
mathematics at Auburn University in Auburn, Alabama where she received her Master?s
in Applied Mathematics, and since then, has served as a graduate teaching assistant in the
Department of Mathematics.
iv
Dissertation Abstract
Solving the Inverse Kinematic Robotics Problem: A Comparison Study of
the Denavit-Hartenberg Matrix and Groebner Basis Theory
Kimberly Kendricks
Doctor of Philosophy, August 4, 2007
(M.A., Auburn University, 2006)
(Dual B.S., University of Pittsburgh, 2003/2004)
90 Typed Pages
Directed by Overtoun Jenda
The aim is to analyze two very difierent methods for solving the inverse kinematic
robotics problem. The flrst method, called the Engineering Approach, uses the Denavit-
Hartenberg Matrix, and the second method, called the Mathematician?s Approach, uses
Groebner Basis Theory and MAGMA, a mathematics computer software package. With
each approach, we will solve the inverse kinematics robotics problem for various robot
manipulators. By comparing each method, this paper will demonstrate that Groebner Basis
Theory is more advantageous, and furthermore, more beneflcial to the fleld of mathematics
and robotics engineering.
v
Style manual or journal used Journal of Approximation Theory (together with the style
known as \auphd"). Bibliography follows van Leunen?s A Handbook for Scholars.
Computer software used The document preparation package TEX (speciflcally LATEX)
together with the departmental style-flle auphd.sty.
vi
Table of Contents
List of Figures ix
1 Introduction 1
2 The GMF Robotics A-510 Robot Manipulator 5
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Deflnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 The Inverse Kinematic Robotics Problem 8
3.1 Deflnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 Forward Kinematic Robotics Problem . . . . . . . . . . . . . . . . . . . . . 8
3.3 Inverse Kinematic Robotics Problem . . . . . . . . . . . . . . . . . . . . . . 9
4 The Engineering Approach 11
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2 Homogeneous Coordinates and Matrices . . . . . . . . . . . . . . . . . . . . 11
4.2.1 Deflnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2.2 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.3 Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.3.1 Translational Transformations . . . . . . . . . . . . . . . . . . . . . . 13
4.3.2 Rotational Transformations . . . . . . . . . . . . . . . . . . . . . . . 16
4.4 The Denavit-Hartenberg Matrix . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.4.2 Derivation of the Denavit-Hartenberg Matrix . . . . . . . . . . . . . 19
4.5 A Kinematic Model for the GMF Robotics A510 Robot . . . . . . . . . . . 26
4.6 Solving the Inverse Kinematic Robotics Problem . . . . . . . . . . . . . . . 28
4.6.1 Case Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.7 Summary: Engineering Approach . . . . . . . . . . . . . . . . . . . . . . . . 41
4.7.1 Results for the GMF Robotics A510 Robot . . . . . . . . . . . . . . 41
4.7.2 Di?culties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5 The Mathematician?s Approach 44
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.2 Groebner Basis Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.2.1 Terminology and Notation . . . . . . . . . . . . . . . . . . . . . . . . 45
5.3 Algorithm for Computing a Groebner Basis . . . . . . . . . . . . . . . . . . 46
vii
5.3.1 S-Polynomials and Buchberger?s Algorithm . . . . . . . . . . . . . . 47
5.4 MAGMA: Algebraic Computer Software . . . . . . . . . . . . . . . . . . . . 50
5.5 Solving the Inverse Kinematics Robotics Problem . . . . . . . . . . . . . . . 51
5.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.5.2 Algebraic Model for the GMF Robotics A-510 Robot . . . . . . . . . 51
5.5.3 Calculating A Groebner Basis With MAGMA . . . . . . . . . . . . . 56
5.5.4 Case Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.6 Summary: Mathematician?s Approach . . . . . . . . . . . . . . . . . . . . . 60
6 Method Analysis 62
6.1 GMF Robotics A-510 Robot . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.2 The Jacobian Matrix and Singularities . . . . . . . . . . . . . . . . . . . . . 64
6.2.1 The Jacobian for a Robot Manipulator . . . . . . . . . . . . . . . . . 65
6.2.2 Finding the Jacobian for the GMF Robotics A-510 Robot . . . . . . 67
6.2.3 Singularities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6.2.4 Finding Singularities for the GMF A-510 Robot . . . . . . . . . . . 71
6.3 A Procedure for an Algebraic Model for Robot Manipulators . . . . . . . . 72
7 Conclusion 75
Bibliography 78
Appendices 80
viii
List of Figures
2.1 Robot Manipulator identifying segments and joints. . . . . . . . . . . . . . 6
2.2 GMF A-510 Robot, ref. Hung [8]. . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Axis Motion for GMF A-510 Robot, ref. Hung [8]. . . . . . . . . . . . . . . 7
4.1 Translational Transformation Example . . . . . . . . . . . . . . . . . . . . . 15
4.2 Homogeneous Transformation Matrix I, ref. Klafter [10]. . . . . . . . . . . . 19
4.3 Displaced Reference Frames in the Same Space, ref. Klafter [10]. . . . . . . 21
4.4 Alignment of Reference Frames Example,ref. Klafter [10]. . . . . . . . . . . 22
4.5 Establishing Link Coordinate Reference Frames, ref. Lee [14]. . . . . . . . . 23
4.6 Establishing Link Coordinate Frames for the GMF A-510 Robot, ref. Hung
[8]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.7 Case 1: L1 and L3 are Collinear . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.8 Case 2: A Point Inside a Circle Centered at the Origin of radius r = 740 . . 39
4.9 Case 3: A Point Outside a Circle Centered at the Origin of radius r = 740 . 40
4.10 Summary of Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.11 Summary of Solutions found with Manipulation . . . . . . . . . . . . . . . . 42
5.1 Algebraic Model: Top View of GMF A-510 Robot . . . . . . . . . . . . . . 52
5.2 Algebraic Model: Top View of GMF A-510 Robot L1 = 410 . . . . . . . . . 53
6.1 GMF A-510 Robot, ref. Hung [8] . . . . . . . . . . . . . . . . . . . . . . . . 73
ix
Chapter 1
Introduction
Robots have become an integral part of everyday life. Automobiles, household prod-
ucts, and canned or boxed foods, are all prepared by assembly line robots. In this paper, we
highlight the importance of studying robotic motion to perform these tasks. In particular,
we are concerned with flnding all of the possible movements needed in order to move the
robot hand to a desired location where it may pick up, pull, or push an object. By deter-
mining a robot?s capabilities, we can better classify the robot for speciflc tasks improving
e?ciency and productivity. We call the problem of flnding all possible movements the in-
verse kinematics robotics problem.
The inverse kinematic robotics problem has proved to be of great signiflcance because
the solutions found provide control over the position and orientation of the robot hand.
Studies have shown that the inverse kinematic robotics problem can be solved using matrix
algebra, iterative procedures, or geometric applications. Paul [18] used a matrix algebra
technique called the Denavit-Hartenberg Matrix, preferred by engineers because of its sim-
plicity and repetition, to obtain an inverse kinematic solution for a robot manipulator.
Huang [7], Manseur and Doty [15] have developed iterative procedures to obtain a solution.
These iterative methods require rigorous calculations that do not necessarily converge to
a correct solution. Lastly, Lee [14], Yih and Youm [23] applied a geometric approach to
solving the inverse kinematic robotics problem. The works of these authors are profound,
but it is unclear which method to use. Is one method more e?cient in calculating real
1
solutions in real-time than another? This is debatable, but what is overwhelmingly evident
is the popularity of the Denavit-Hartenberg Matrix.
Derived by authors J. Denavit and R. S. Hartenberg, the Denavit-Hartenberg Matrix
(The Engineering Approach) is the most widely used technique for solving the inverse kine-
matic robotics problem for several reasons. One, speciflc intervals can be formed describing
the angle of rotation or translation of each joint of a robot manipulator. These intervals
deflne the potential movement of each joint. Two, with these intervals of movement, certain
parameters can be used in a matrix to describe the movement of the i?1th joint in terms
of the ith joint. Therefore, each joint can be described by a matrix. Three, the product
of all of these joint matrices describes the flnal position of the robot hand in space. In
summary, the Denavit-Hartenberg Matrix is easy to use and easy to understand. However,
when using this technique, we encounter the following di?culties: the need for additional
methods and algorithms to solve the problem, matrix computations may be too large or
too complex, some solutions cannot be found in real-time, and some solutions are not easily
found.
Given these di?culties, and those associated with other engineering approaches, we
look for an alternate method that can resolve them. Hence, Groebner Basis Theory (The
Mathematician?s Approach). Developed by Bruno Buchberger, an algebraic algorithm can
be applied to a given set of non-zero polynomials, producing a basis set, such that every
polynomial in the original set is a linear combination of those polynomials in the basis set.
By flnding solutions to this basis set, we thereby flnd solutions to the entire set. With the
aid of MAGMA, an algebraic computer software package, we can calculate these solutions
in real-time, and consider cases not as easily solved using the Denavit-Hartenberg Matrix,
2
thereby flnding all possible solutions.
To familiarize the reader with each approach, we begin by solving the inverse kinematic
robotics problem for the GMF Robotics A-510 Robot. By demonstrating each approach on
a robot with a simple construction, we are able to reveal where potential problems in the
Engineering Approach can arise. We then extend our knowledge and apply each approach
to a difierent class of robot manipulators. We will analyze each method and compare their
corresponding solutions. The aim is to present to engineers and mathematicians an appli-
cation of Groebner Basis Theory that can solve the inverse kinematics robotics problem
while resolving the di?culties engineers face using the Denavit-Hartenberg Matrix.
In the past, solving the inverse kinematic robotics problem for various robot manip-
ulators has advanced the fleld of robotics engineering, but this comparative study will
contribute to the advancement of the fleld of mathematics, as well, and more importantly,
continue to satisfy the needs of a growing industry dependent upon robots.
We begin by introducing the GMF Robotics A-510 Robot in Chapter 2, where we dis-
cuss the robot?s speciflcations, deflnitions, and important properties. Next is Chapter 3
which focuses on kinematics. Here, the inverse kinematic robotics problem is explained in
more detail. Chapter 4 is devoted to the Engineering Approach of the Denavit-Hartenberg
Matrix. A derivation of the Denavit-Hartenberg Matrix is given as well as a solution to
the inverse kinematics robotics problem. Chapter 5 is devoted to the Mathematicians? Ap-
proach of Groebner Basis Theory. The algorithm for flnding a Groebner basis is provided
as well as a solution to the inverse kinematic robotics problem. At the end of chapters four
and flve, there is a small summary of the solutions found. It is in Chapter 6 where we
3
extend our knowledge and apply each approach to an entire class of robot manipulators. A
brief conclusion follows summarizing the flndings in this paper.
4
Chapter 2
The GMF Robotics A-510 Robot Manipulator
2.1 Introduction
The GMF Robotics A-510 Robot is manufactured by GMF FANUC Robotics and
is typically used to perform assembly line tasks. The GMF Robotics A-510 Robot that
is used in this study presently sits in the Electrical Engineering Robotics Laboratory at
Auburn University in Auburn, Alabama. This robot came from the General Motors Saturn
Automotive Plant in Tennessee. Various tools such as grippers, welders, and spray guns
can be attached to the robot to perform speciflc tasks. We explore other attributes of the
robot below.
2.2 Deflnitions
Deflnition 1: A robot manipulator consists of links which are connected to one another by
joints.
Deflnition 2: A link is a rigid body in a robot manipulator. A link is also called a segment.
Deflnition 3: There are two types of joints. A revolute joint which is a rotary joint that
allows the rotation of one link about the joint of the preceding link, and a prismatic
joint which is a linear joint that allows translation between joints.
Deflnition 4: A serial link manipulator is a robot manipulator in which links and joints
are arranged in an alternating fashion.
5
Segment
Revolute Joint
Prismatic Joint
Figure 2.1: Robot Manipulator identifying segments and joints.
Deflnition 5: An end efiector is the last joint in a serial link manipulator. The end efiector
is typically called the robot hand since various tools can be attached to the end efiector
to have the robot perform difierent tasks.
Deflnition 6: A degree of freedom represents a joint-link pair.
2.3 Properties
The GMF Robotics A-510 robot has four degrees of freedom. The flrst joint is a
prismatic joint and the second, third, and fourth are revolute joints. The motion of each
joint axis is described in the table below.
? The Z axis has a vertical motion of 300mm.(Prismatic Joint)
? The Theta axis has a horizontal rotation of 300 degrees. (Revolute Joint)
? The U axis has a horizontal rotation of 300 degrees. (Revolute Joint)
? The fi axis (end efiector) has a rotation of 540 degrees. (We are only concerned with
where this joint will be placed in space, so we will not incorporate this axis in future
calculations.)
6
a0 a1 a2 a3 a4
a5 a6 a7 a8 a9
a10 a11 a11 a12
a13 a1 a2 a3 a4
a14 a15 a16 a17 a18 a1 a2 a3 a4
a1 a19 a20 a15 a18 a1 a2 a3 a4
Figure 2.2: GMF A-510 Robot, ref. Hung [8].
Figure 2.3: Axis Motion for GMF A-510 Robot, ref. Hung [8].
7
Chapter 3
The Inverse Kinematic Robotics Problem
3.1 Deflnitions
Deflnition 1: Kinematics is the study of motion, ignoring such factors as mass, gravity,
and torques.
Deflnition 2: A Kinematic Chain is a robot manipulator in which each joint has at most
two links. Moreover, a Kinematic Chain is a serial link manipulator whose flrst link
is connected to the base and whose flnal joint is connected to just one link, leaving
the remaining end open. Thus, in a Kinematic Chain no closed loops can be formed.
There are two types of kinematic problems: The Forward Kinematics Robotics Problem
and The Inverse Kinematics Robotics Problem.
3.2 Forward Kinematic Robotics Problem
The Forward Kinematic Robotics Problem: Given a robot manipulator with speciflc
joint angles, we can flnd the exact position and orientation of the robot hand (end
efiector).
Because of its simplicity, the Forward Kinematic Robotics Problem gains little interest.
8
3.3 Inverse Kinematic Robotics Problem
The Inverse Kinematic Robotics Problem: Given an orientation and position for a
robotic arm, we want to show that by flnding all possible combinations of joint set-
tings, we can place the hand of the robot at this exact point and orientation.
The inverse kinematic robotics problem has been the focus of kinematic analysis for
robot manipulators. In order to determine all possible formations to place the end efiector
of a robot manipulator at a particular point in space, we must compute the movements
associated with each joint variable. In doing so, over the span of several decades, authors
have faced the following di?culties:
? The complexity of the inverse kinematic robotics problem is determined by the geom-
etry of the robot manipulator.
? Some calculations to solving the inverse kinematic problem cannot be computed in
real-time.
? There can be di?culty in flnding all possible solutions.
? There can be di?culty in flnding real solutions.
The GMF Robotics A510 Robot is formed by a set of interconnected rigid bodies called
links and these rigid bodies are connected by prismatic or revolute joints. We are interested
9
in how these bodies move in relation to one another in order to place the robot hand, or
end efiector, at a desired point in space. Hence, our focus on the inverse kinematic robotics
problem.
10
Chapter 4
The Engineering Approach
4.1 Introduction
The Engineering Approach uses the Denavit-Hartenberg Matrix to solve the inverse
kinematic robotics problem. With some examples, we derive the Denavit-Hartenberg Ma-
trix, then use the Denavit-Hartenberg Matrix to flnd a solution to the inverse kinematic
robotics problem for the GMF Robotics A-510 Robot.
4.2 Homogeneous Coordinates and Matrices
4.2.1 Deflnitions
Deflnition 1: Homogeneous Coordinates are an alternate way of representing a three di-
mensional vector, but have the addition of a fourth component called a scaling factor,
and all of the components are multiplied by this scaling factor.
Example: In matrix form, the homogeneous representation of a vector ~v is
2
66
66
66
66
64
x0
y0
z0
s
3
77
77
77
77
75
11
where s is the scaling factor and x0 = sx , y0 = sy and z0 = sz.
4.2.2 Remarks
1. Homogeneous representations are not unique.
2. The null vector is represented as
2
66
66
66
66
64
0
0
0
s
3
77
77
77
77
75
where s is a non-zero real number.
3. A vector is undeflned if all the entries are zero.
4. Vector operations such as the Dot Product and Cross Product have homogeneous
representations.
4.3 Transformations
Transformations are a class of matrix operators that can perform vector operations
resulting in the translation or rotation of a vector. There are two types of transformations:
translational and rotational.
12
4.3.1 Translational Transformations
A Translational Transformation denoted Trans(a,b,c) moves a point deflned by a vector
~x, to a new point deflned by a vector ~y. The location of ~y is given by the vector addition of
~x with a translation vector deflned by (a,b,c), where a,b,c represent the components of the
vector that are added to the components of the vector ~x. In other words, we are moving
a point described by a vector ~x along the diagonal (a,b,c) to a new point described by the
vector ~y. Trans(a,b,c) is deflned as
Trans(a;b;c) =
2
66
66
66
66
64
1 0 0 a
0 1 0 b
0 0 1 c
0 0 0 1
3
77
77
77
77
75
The vector components a,b,c are added to the vector ~x to get the point described by
the vector ~y.
Example: Let P = (2;1) be a point in the xy-plane. We wish to move P along the diagonal
of 30? for a distance of 8 units to a new point P0. What are the coordinates of the
flnal point P0 = (x2;y2)?
Solution: The homogeneous representation of P is,
13
~P =
2
66
66
66
66
64
2
1
0
1
3
77
77
77
77
75
Since we are moving ~P along a 30? diagonal, the unit vector corresponding to this
direction is
~u =
2
66
66
66
66
64
p3
2
1
2
0
1
3
77
77
77
77
75
The vector of length 8 along 30? is
~u0 =
2
66
66
66
66
64
4p3
4
0
1
3
77
77
77
77
75
14
P
P?
2
1
8 units
30
x
y
2
Figure 4.1: Translational Transformation Example
In homogeneous representation, then,
~P0 =
2
66
66
66
66
64
1 0 0 4p3
0 1 0 4
0 0 1 0
0 0 0 1
3
77
77
77
77
75
2
66
66
66
66
64
2
1
0
1
3
77
77
77
77
75
=
2
66
66
66
66
64
2+4p3
5
0
1
3
77
77
77
77
75
So,
P0 = (2+4p3;5)
Note: In the computation of ~P0 the scaling factor is 1.
In summary, a translational transformation describes motion along a line.
15
4.3.2 Rotational Transformations
A Rotational Transformation, denoted Rot(axis, ), moves a point deflned by a vector
to a new position in space by rotating the point by about an axis.
Using homogeneous representation, we have the following rotational transformations:
For rotation about the x-axis,
Rot(x; ) =
2
66
66
66
66
64
1 0 0 0
0 cos ?sin 0
0 sin cos 0
0 0 0 1
3
77
77
77
77
75
For rotation about the y-axis,
Rot(y; ) =
2
66
66
66
66
64
cos 0 sin 0
0 1 0 0
?sin 0 cos 0
0 0 0 1
3
77
77
77
77
75
For rotation about the z-axis,
16
Rot(z; ) =
2
66
66
66
66
64
cos ?sin 0 0
sin cos 0 0
0 0 1 0
0 0 0 1
3
77
77
77
77
75
The angle of rotation can be positive or negative and is deflned by using the right-hand
rule. Rotation is positive if the cross product of two axes is in the positive direction of the
third axis. That is, the cross product of the initial and flnal vectors is in the same direction
as the axis about which the rotation is to be performed. For example, the cross product of
~x?~y = ~z, so positive rotation will occur about the z-axis.
Example:
Let
~P =
2
66
66
66
66
64
2
2
2
1
3
77
77
77
77
75
We wish to rotate ~P, 45? about the z-axis to the point described by the vector ~P0.
What would the homogeneous coordinate for ~P0 be?
Solution:
17
First, we wish to flnd
Rot(z;45) =
2
66
66
66
66
64
cos45 ?sin45 0 0
sin45 cos45 0 0
0 0 1 0
0 0 0 1
3
77
77
77
77
75
Then,
~P0 = Rot(z;45)? ~P =
2
66
66
66
66
64
p2
2
?p2
2 0 0
p2
2
p2
2 0 0
0 0 1 0
0 0 0 1
3
77
77
77
77
75
2
66
66
66
66
64
2
2
2
1
3
77
77
77
77
75
=
2
66
66
66
66
64
0
2p2
2
1
3
77
77
77
77
75
Thus,
~P0 = (0;2p2;2;1)
.
4.4 The Denavit-Hartenberg Matrix
4.4.1 Introduction
To understand the Denavit-Hartenberg Matrix, we must flrst understand how it is de-
rived. The Denavit-Hartenberg Matrix is a special form of a homogeneous transformation
18
Figure 4.2: Homogeneous Transformation Matrix I, ref. Klafter [10].
matrix, a 4 ? 4 matrix having the property of transforming a vector from one coordinate
frame to another by means of a translation or rotation. For a kinematic chain with n-joints
and n ? 1-links, each joint is assigned a frame of reference. We can align each frame of
reference by performing a series of rotations and transformations. Thus, each joint can be
represented by a homogeneous transformation matrix describing the particular rotation or
translation needed to align the i?1th joint with ith joint. The product of these matrices
gives the flnal position of the nth joint. In this case, the nth joint represents the robot hand
(end efiector).
4.4.2 Derivation of the Denavit-Hartenberg Matrix
A homogeneous transformation matrix can be described in two difierent ways. One
way is
For the matrix above,
1. The upper left 3?3 matrix is the Rotation Matrix
2. The 3?1 vector describes the Position vector (or Translation)
3. The 1?3 vector is called the Perspective Transform, and is f0;0;0g.
19
4. The 1?1 vector is the Scaling Factor, and will always be represented as s = 1.
On the other hand, we can also describe the homogeneous transformation matrix as:
2
66
66
66
66
64
nx ox ax px
ny oy ay py
nz oz az pz
0 0 0 1
3
77
77
77
77
75
Figure 4.2 Homogeneous Transformation Matrix II.
The matrix above, also known as the T-Variable Matrix, describes the direction vectors
for the x, y, and z axes of frame 2 in terms of the direction vectors for the x, y, and z axes of
frame 1, where the normal vector ~n represents the x-axis, the orientation vector ~o represents
the y-axis, and the approach vector ~a represents the z-axis.
1. For the flrst column, nx;ny;nz are the components of the unit vector deflning the
x-axis of frame 2 in terms of the three unit vectors of the axes from frame 1.
2. For the second column, ox;oy;oz are the components of the unit vector deflning the
y-axis of frame 2 in terms of the three unit vectors of the axes from frame 1.
3. For the third column, ax;ay;az are the components of the unit vector deflning the
z-axis of frame 2 in terms of the three unit vectors of the axes from frame 1.
4. The fourth column is position of frame 2 with respect to frame 1.
20
Figure 4.3: Displaced Reference Frames in the Same Space, ref. Klafter [10].
[Klafter]
In the above examples, we have looked at vectors in an orthogonal reference frame.
Now, we will consider a space consisting of two or more orthogonal reference frames whose
origins are displaced.
Note: We can use the previous transformation operators to align the displaced refer-
ence frames.
Notation: The symbol Amn represents homogeneous transformation matrices that relate
points in frame n in terms of frame m. In particular, A0n = A01 ?A12 ?A23 ?????
A(n?1)n.
Consider the following flgure.
21
Figure 4.4: Alignment of Reference Frames Example,ref. Klafter [10].
Then,
A03 = A01 ?A12 ?A23 =
2
66
66
66
66
64
?1 0 0 0
0 0 1 0
0 1 0 z
0 0 0 1
3
77
77
77
77
75
2
66
66
66
66
64
0 0 ?1 0
0 1 0 0
1 0 0 y1
0 0 0 1
3
77
77
77
77
75
2
66
66
66
66
64
0 1 0 y2
0 0 1 0
1 0 0 0
0 0 0 1
3
77
77
77
77
75
=
2
66
66
66
66
64
1 0 0 0
0 1 0 y1 +y2
0 0 1 z
0 0 0 1
3
77
77
77
77
75
Deflnition: The Inverse Homogeneous Transformation Matrix of Amn is Anm. Hence, the
inverse of a homogeneous transformation is deflned by (Amn)?1 = Anm. Thus, it
follows that Amn ?Anm = I; the identity matrix.
22
Figure 4.5: Establishing Link Coordinate Reference Frames, ref. Lee [14].
Looking at the above example, the inverse is simply taking the reverse. So, to flnd (A03)?1,
we simply walk backwards from the third reference frame and work our way towards the
zero reference frame.
Similarly, a cartesian coordinate system can be assigned to each joint of a robot manipulator
such that each connected link is assigned a particular coordinate axis. Each link coordinate
frame is determined using the following rules:
1. The zi?1 axis lies along the axis of motion of the ith joint.
2. The xi axis is normal to the zi?1 axis, with it?s positive direction towards the zi axis.
3. The yi axis is chosen so that the three axes form a right-handed system, ref. Lee [14].
There are four parameters associated with each link: ai, the length of the link, fii, the link
twist, di, the linear distance of a prismatic joint, and i, the degree rotation of a revolute
23
joint. Each of these parameters is deflned with respect to two joint axes attached to a
particular link, such that
? i is the joint angle from the xi?1 axis to the xi about the zi?1 axis (using the right-
hand rule)
? di is the distance from the origin of the (i?1)th coordinate frame to the intersection
of the zi?1 axis with the xi axis along the zi?1 axis.
? ai is the distance from the intersection of the zi?1 axis with the xi axis to the origin
of the ith frame along the xi axis.
? fii is the angle from the zi?1 axis to the zi axis about the xi axis.[Lee]
Observe that ai and fii describe the structure of a link whereas di and i describe the
position in regards to neighboring links.
Note: Assignment of reference frames is not unique.
Once the link coordinate frames are established, these four parameters are used in a
transformation matrix to deflne the relationship between consecutive frames. This matrix is
called the Denavit-Hartenberg Matrix (D-H Matrix), a homogeneous transformation matrix
solely deflned by the four link parameters and can be found by a series of translations and
rotations.
Using the link parameters, let Rot(axis, i) denote a rotational transformation about
the given axis i degrees, and let Trans(a,b,c) denote a translational transformation that
24
moves a point deflned by a vector ~x, along the diagonal (a,b,c) to a new point deflned by a
vector ~y. Then, the product of these transformations in this order gives the D-H Matrix:
A(i?1)i = Rot(xi;fii)Trans(ai;0;0)Trans(0;0;di)Rot(zi?1; i)
=
2
66
66
66
66
64
cos i ?cosfii sin i sinfii sin i ai cos i
sin i cosfii cos i ?sinfii cos i ai sin i
0 sinfii cosfii di
0 0 0 1
3
77
77
77
77
75
Note: When solving the inverse kinematic robotics problems, ai and fii are constants
and either di and i are joint variables.
Thus, for an n-degree of freedom manipulator, let P be the matrix which is a function
of all of the joint variables, then,
P = A0n = A01 ?A12 ?A23 ?????A(n?1)n
where each Aij matrix is of the D-H Matrix form.
25
a0 a1
a2 a1
a3 a1
a0 a4
a5
a4
a2 a4
a3 a4
a0 a6
a2 a6
a3 a6
a0 a7
a2 a7
a3 a7
a8
a6
a8
a1
a9 a10 a11 a12 a13 a14 a9
a9 a15 a9
a9 a16 a17 a18 a11 a14 a9
a9 a19 a9
a20 a4
a20 a1
Figure 4.6: Establishing Link Coordinate Frames for the GMF A-510 Robot, ref. Hung [8].
4.5 A Kinematic Model for the GMF Robotics A510 Robot
The GMF Robotics A-510 robot has four degrees of freedom. However, the following
kinematic model focuses on the flrst three joints. The last joint refers to the robot hand
or end efiector. Since we are solving the inverse kinematic robotics problem, we are only
interested in where this fourth joint, the robot hand (end efiector) will be placed in space.
We establish the link coordinate frames in Figure 4.6.
Then describe each joint in terms of the four parameters ai;fii; i; and di. Below is a table
describing the joint parameters of the GMF Robotics A510 Robot.
Table 4.1: Table of A-510 link parameters, ref. Hung [8].
Joint, i type GMF name location ai fii i di
1 rotational Theta waist 0 0 1 980 mm
2 prismatic Z - 410 mm 0 0 d2
3 rotational U elbow 330 mm 0 3 0
26
The information in the table allows us to form the following transformation matrices.
A01 =
2
66
66
66
66
64
cos 1 ?sin 1 0 0
sin 1 cos 1 0 0
0 0 1 0
0 0 0 1
3
77
77
77
77
75
A12 =
2
66
66
66
66
64
1 0 0 410
0 1 0 0
0 0 1 d2
0 0 0 1
3
77
77
77
77
75
A23 =
2
66
66
66
66
64
cos 3 ?sin 3 0 330?cos 3
sin 3 cos 3 0 330?sin 3
0 0 1 0
0 0 0 1
3
77
77
77
77
75
27
4.6 Solving the Inverse Kinematic Robotics Problem
To solve the inverse kinematic robotics problem for the GMF Robotics A510 Robot,
let P = A01?A12?A23 . Using MAPLE, a mathematics computer package, we calculate P.
P=
2
66
66
66
66
4
cos 1 cos 3 ?sin 1 sin 3 ?cos 1 sin 3 ?sin 1 cos 3 0 330cos 1 cos 3 ?330sin 1 sin 3 +410cos 1
sin 1 cos 3 +cos 1 sin 3 cos 1 cos 3 ?sin 1 sin 3 0 330sin 1 cos 3 +330cos 1 sin 3 +410sin 1
0 0 1 980+d2
0 0 0 1
3
77
77
77
77
5
The fourth column represents the flnal position of the end efiector. Using the Matrix Ma-
nipulation Method [8], we set the T-Variable Matrix equal to P, the flnal position matrix,
and get
T ?VariableMatrix =
2
66
66
66
66
64
nx ox ax px
ny oy ay py
nz oz az pz
0 0 0 1
3
77
77
77
77
75
=
2
66
66
66
4
cos 1 cos 3 ?sin 1 sin 3 ?cos 1 sin 3 ?sin 1 cos 3 0 330cos 1 cos 3 ?330sin 1 sin 3 +410cos 1
sin 1 cos 3 +cos 1 sin 3 cos 1 cos 3 ?sin 1 sin 3 0 330sin 1 cos 3 +330cos 1 sin 3 +410sin 1
0 0 1 980+d2
0 0 0 1
3
77
77
77
5
28
We want to flnd d2; 1; and 3 that satisfy those equations in the fourth column representing
px;py; and pz. That is, we want to flnd those joint angles, that will allow the end efiector
to reach the points in space described by
=
2
66
66
66
66
64
330cos 1 cos 3 ?330sin 1 sin 3 +410cos 1
330sin 1 cos 3 +330cos 1 sin 3 +410sin 1
980+d2
1
3
77
77
77
77
75
We multiply each side by A?11 such that
A?11 ?T ?VariableMatrix = A2 ?A3
2
66
66
66
66
4
cos 1 sin 1 0 0
?sin 1 cos 1 0 0
0 0 1 ?980
0 0 0 1
3
77
77
77
77
5
2
66
66
66
66
4
nx ox ax px
ny oy ay py
nz oz az pz
0 0 0 1
3
77
77
77
77
5
=
2
66
66
66
66
4
cos 3 ?sin 3 0 330cos 3 +410
sin 3 cos 3 0 330sin 3
0 0 1 d2
0 0 0 1
3
77
77
77
77
5
29
Simplifying the left-hand side (LHS) further, we have
A?11 ?T ?VariableMatrix
=
2
66
66
66
66
4
nx cos 1 +ny sin 1 ox cos 1 +oy sin 1 ax cos 1 +ay sin 1 px cos 1 +py sin 1
?nx sin 1 +ny cos 1 ?0x sin 1 +oy cos 1 ?ax sin 1 +ay cos 1 ?px sin 1 +py cos 1
nz oz az pz ?980
0 0 0 1
3
77
77
77
77
5
=
2
66
66
66
66
64
cos 3 ?sin 3 0 330cos 3 +410
sin 3 cos 3 0 330sin 3
0 0 1 d2
0 0 0 1
3
77
77
77
77
75
=
A2 ?A3
We then set the elements of each matrix equal to one another. In particular, we have
(4.1) px cos 1 +py sin 1 = 330cos 3 +410
30
(4.2) ?px sin 1 +py cos 1 = 330sin 3
(4.3) d2 = pz ?980
Thus, we have found d2 = pz ?980. So we have found one of the three unknown variables.
However, we still need to flnd 1 and 3.
To flnd 3 , we use (4.1) and (4.2). Observe by squaring both sides of (4.1),
(4.4) (px cos 1 +py sin 1)2 = (330cos 3 +410)2
gives
(4.5) p2x(cos 1)2 +2pxpy cos 1 sin 1 +p2y(sin 1)2 = 3302(cos 3)2 +2?410?330cos 3 +4102
And by squaring both sides of (4.2)
(?px sin 1 +py cos 1)2 = (330sin 3)2
31
gives
(4.6) p2x(sin 1)2 ?2pxpy cos 1 sin 1 +p2y(cos 1)2 = 3302(sin 3)2
Then, by adding (4.5) and (4.6), we get
(4.7) p2x +p2y = 3302 +2?410?330cos 3 +4102
Then,
(4.8) p
2x +p2y ?3302 ?4102
2?410?330 = cos 3 = X3
Now, we shall flnd sin 3. To do so, we substitute for cos 3 in (4.1), and square both sides,
then add (4.6).
p2x(cos 1)2 +2pxpy cos 1 sin 1 +p2y(sin 1)2 = f330(p
2
x +p
2
y ?330
2 ?4102)
2?410?330 +410g
2
+p2x(sin 1)2 ?2pxpy cos 1 sin 1 +p2y(cos 1)2 = 3302(sin 3)2
32
Combining the left-hand sides and right-hand sides respectively, yields
p2x +p2y = f330?(p
2x +p2y ?3302 ?4102)
2?410?330 +410g
2 +3302(sin 3)2
Then,
(4.9) ?
s
p2x +p2y ?f330? (p2x+p2y?3302?4102)(2?410?330) +4102g
330 = sin 3 = Y3
Thus,
(4.10) 3 = tan?1( Y3X
3
); for ??2 ? 3 ? ?2
Now that we have found 3, we look to flnd 1. Using (4.1) and (4.2), we have two equations
in two unknowns
px cos 1 +py sin 1 = 330cos 3 +410
?px sin 1 +py cos 1 = 330sin 3
33
Using elimination, we solve the system of equations to get
(4.11) Y1 = sin 1 = ?py(330X3 +410)+px330Y3?p2
x ?p2y
and
(4.12) X1 = cos 1 = (330X3 +410)px +330Y3pyp2
x +p2y
Thus,
(4.13) 1 = tan?1( Y1X
1
); for ??2 ? 1 ? ?2
So, we have found the joint angles (d2, 1, and 3) that will allow the end efiector to touch
the points (px;py;pz) in space. Hence, the inverse kinematic robotics problem for the GMF
Robotics A-510 Robot is solved.
4.6.1 Case Examples
We verify these results in the following examples:
Note: Since pz determines the height of (px;py), we restrict our focus to (px;py), with the
34
L3= 330L1=410
(Px,Py)
Figure 4.7: Case 1: L1 and L3 are Collinear
understanding that (px;py) can occur at any height pz.
Case 1: When L1 and L3 are Collinear
If L1 = 410 and L3 = 330 are collinear, then 3 = 0?. Thus, for 1 from ?150? ? 1 ? 150?,
we have the following
px = 330cos( 1 +0)+410cos 1 = 740cos 1
py = 330sin( 1 +0)+410sin 1 = 740sin 1
35
Thus, there is one formation to reach the point (px;py).
Case 2: A Point Inside a Circle of Radius r = 740 Centered at the Origin
We wish to flnd (px;py) where 1 = 30? and 3 = 30? by using the Forward Kinematic
Robotics Problem
px = 330cos(60)+410cos(30) = 165+205p3
py = 330sin(60)+410sin(30) = 165p3+205
Using the Inverse Kinematic Robotics Problem, we check these results. Given the flnal
position described by px and py, we wish to flnd 1 and 3. We substitute into the equations
derived in the previous section,
X3 = cos 3 = (165+205
p3)2 +(165p3+205)2 ?3302 ?4102
2?410?330 =
p3
2
36
Y3 = sin 3 = ?
q
(165+205p3)2 +(165p3+205)2 ?(330
p3
2 +410)2
330 = ?
1
2
Thus,
3 = tan?1(
1
2p
3
2
) = 30? for ??2 ? 3 ? ?2
and,
3 = tan?1(
?1
2p
3
2
) = ?30? for ??2 ? 3 ? ?2
To flnd 1, using Y3 = 12, we substitute these values into the equations above to get
Y1 = sin 1 = ?(165
p3+205)(330p3
2 +410)+(165+205
p3)3301
2
?(165+205p3)2 ?(165p3+205)2 =
1
2
X1 = cos 1 = (330
p3
2 +410)(165+205
p3)+3301
2(165
p3+205)
(165+205p3)2 +(165p3+205)2 =
p3
2
37
Thus,
1 = tan?1(
1
2p
3
2
) = 30?
Also, we need to flnd 1 when Y3 = ?12
Y1 = sin 1 = ?(165
p3+205)(330p3
2 +410)+(165+205
p3)330?1
2
?(165+205p3)2 ?(165p3+205)2 = 0:84
X1 = cos 1 = (330
p3
2 +410)(165+205
p3)+330?1
2 (165
p3+205)
(165+205p3)2 +(165p3+205)2 = 0:55
Thus,
1 = tan?1(0:840:55) ? 56:83?
38
L3= 330L1=410
(Px, Py)
Figure 4.8: Case 2: A Point Inside a Circle Centered at the Origin of radius r = 740
Since we solved a quadratic equation for Y3, we found two solutions for 3 and two
corresponding solutions for 1. Hence, there are two joint settings that will place the robot
hand at (px;py) = (165+205p3;165p3+205). They are
3 = 30? 1 = 30?
and
3 = ?30? 1 = 56:83?
Thus, we have found all joint settings that will place the robot hand at (px;py) =
(165+205p3;165p3+205).
39
L3 = 330
L1=410
(Px,Py)
Figure 4.9: Case 3: A Point Outside a Circle Centered at the Origin of radius r = 740
Case 3: A Point Outside a Circle of Radius r = 740 Centered at the Origin
Let (px;py) = (760;760). We need to calculate 1 and 3.
For 3,
X3 = cos 3 = 760
2 +7602 ?3302 ?4102
2?410?330 =
878200
270600 = 3:24538
But this is a contradiction since cos 3 must lie between ?1 and 1.
It is clear that a solution for 3 will not be found. Thus, a solution for 1 will not be
found. Hence, this example supports the fact that only those values that lie in the specifled
domain for each joint variable have the potential to exist as possible solutions.
40
Two Solutions
No Solutions
One Solution
Figure 4.10: Summary of Solutions
4.7 Summary: Engineering Approach
4.7.1 Results for the GMF Robotics A510 Robot
We have found d2, 1, and 3. In particular, we found 1 and 3 in terms of (px;py).
From this representation, however, we are not able to gain enough information about each
(px;py). In fact, we don?t know if (px;py) is a reachable point in space unless we substitute it
into the equations derived for 1 and 3. This could become tedious. From our calculations
of a quadratic equation, the most we can conclude is that there are two angle conflgurations
for each joint, to reach (px;py). It is desired to flnd all (px;py) that are reachable points
within our workspace.
By picking three difierent points in space, we discovered for 1 and 3, such that
??
2 ? 1 ?
?
2 and
??
2 ? 3 ?
?
2, that there are at most none, one, or two formations that
can place the robot hand at a particular point in space. We wish to determine the unique
set of points that will produce no solutions, the unique set of points that will produce one
solution, and the unique set of points that will produce two solutions.
41
Two Solutions
One Solution
One Solution
One Solution
Two Solutions
-150
150
Figure 4.11: Summary of Solutions found with Manipulation
Observe further that since 1 and 3 range from ?150? to 150?, and the equations we
derived for them satisfy ??2 ? 1 ? ?2 and ??2 ? 3 ? ?2, we have not found all possible solu-
tions. We manipulate the equations in our kinematic model to flnd any remaining solutions.
Using (4.1), if we let
3 = cos?1
"
p2x +p2y ?3302 ?4102
2?410?330
#
where 0 ? 3 ? ?, and let 1 range from ?150? to 150?, we discover more solutions. In
fact, by choosing three more test points in this new domain, there are none, one, or two
formations that can place the robot hand at a particular point inside this domain. Since
the geometry of our robot arm corresponds to the symmetry of the unit axis, we have also
found those solutions where ?? ? 3 ? 0
By analyzing the geometry of the robot, and manipulating our kinematic model, we
discovered more solutions that determined new formations. But we were only able to do
so because of the simple geometry of the GMF Robotics A-510 Robot. However, if the
42
geometry of the robot is more complex, solutions are not easily found, and in some cases,
solutions are not found at all. Facing this challenge, we acknowledge other di?culties to
the Engineering Approach.
4.7.2 Di?culties
1. There are instances when no solution can be found due to limitations on the robot
manipulator,
2. Multiple solutions are possible since the robot manipulator can use difierent forma-
tions to place the robot hand at a particular point in space,
3. Careful analysis of the geometry of the robot manipulator forces a close examination
and, in some cases, manipulation of the equations found to solve the inverse kinematic
robotics problem in order to flnd all possible solutions.
4. Some calculations cannot be computed as easily by hand. Hence, the use of MAPLE,
a mathematics computer software.
To resolve these di?culties and other challenges mentioned, we search for an alternate
method{The Mathematician?s Approach.
43
Chapter 5
The Mathematician?s Approach
5.1 Introduction
The Mathematician?s Approach uses Groebner Basis Theory to solve the inverse kine-
matic robotics problem. We begin with background on Groebner Basis Theory. Then, with
an example, show how to develop a Groebner basis. Lastly, we use a Groebner basis to
solve the inverse kinematic robotics problem for the GMF Robotics A-510 Robot.
5.2 Groebner Basis Theory
Groebner Basis Theory allows mathematicians to use a particular algorithm to solve
systems of polynomial equations. More formally, this algorithm, named Buchberger?s algo-
rithm [2], after mathematician Bruno Buchberger, applies computational algebra techniques
to speciflc polynomial ideals, producing a Groebner basis that can be used to flnd solutions
to a set of non-zero polynomials for a given ideal.
For multivariant polynomials, the complexity of computing a Groebner basis does not
depend on the number of polynomials in the set, but rather on the term order. By ordering
a set of polynomials with respect to lexigraphical order, at least one element in the Groebner
basis will be in terms of one variable in the set. This makes calculating a Groebner basis
?nice?, because through back substitution, we can flnd a solution to the rest of the variables
in the set. We illustrate this in the following sections.
44
Groebner Basis Theory is a very popular fleld of study, but mathematicians appreciate
it most for its applications in other areas of mathematics. For example, Robbiano [20] uses
Groebner bases to solve problems in Design Experiments in Statistics. Wang [22] shows
how Groebner bases can be used to prove Geometric problems. Cox, Little, and O?Shea [3]
have devoted a text to Groebner Basis Theory and its applications in Geometry and Graph
Theory. Below, we illustrate an application in robotics.
5.2.1 Terminology and Notation
Terminology:
1. Forafleldk, aMonomial Orderingonk[x1;:::;xn]isanyrelationonthesetofmonomials
xfi;fi 2 Zn?0 such that this relation is a linear ordering, and if fi;fl; 2 Zn?0 such that
fi > fl, then fi+ > fl + . Moreover, this relation is also a well ordering.
2. Lexigraphical order (lex order): Given a monomial ordering, let fi = (fi1;:::;fin) and
fl = (fl1;:::;fln) 2 Nn?0. We say xfi > xfl if fi > fl.
Example: Let f = 7x2yx+5z2y +12xz +3y2z +8 2 k[x;y;z]. Then,
With respect to lex order x > y > z, f = 7x2yz +12xz +3y2z +5yz2 +8
45
Notation:
Let k be any fleld and let k 2 [x1;:::;xn] be ordered with respect to lex order, then
for all f 2 k[x1;:::;xn], with f 6= 0,
f = a1xfi1 +a2xfi2 +:::+arxfir;
where 0 6= ai 2 k[x1;:::;xn] and xfii is ordered such that xfi1 > xfi2 > ::: > xfir.
? The leading power product of f is deflned as lp(f) = xfi1
? The leading coe?cient of f is deflned as lc(f) = a1
? The leading term of f is deflned as lt(f) = a1xfi1
5.3 Algorithm for Computing a Groebner Basis
Introduced in 1965 by Bruno Buchberger, an algorithm can be applied to a non-zero
set of polynomials for a given ideal to produce a Groebner basis for that given ideal. More
formally, we have the following deflnition,
Deflnition: A set of non-zero polynomials G = fg1;:::;gtg contained in an ideal I, is
called a Groebner Basis for I if and only if for all f 2 I such that f 6= 0, there exists
i 2 1;:::;t such that lp(gi) divides the lp(f).
46
5.3.1 S-Polynomials and Buchberger?s Algorithm
TodevelopBuchberger?sAlgorithm, wemustflrstunderstandthenatureofS-polynomials.
In the following examples, let k be any fleld, and let Q denote the Rational Field.
Deflnition: Let 0 6= f, g 2 k[x1;:::;xn]. Let L = lcm(lp(f);lp(g)). The polynomial
S(f;g) = Llt(f) ?f ? Llt(g) ?g
is called the S-polynomial of f and g.
Example: Let f = 2yx?y;g = 3y2 ?x 2 Q[x;y], with lex order y > x. Find S(f;g).
Solution: First, we need to flnd L = lcm(lp(f);lp(g)) = lcm(yx;y2) = y2x. Then,
S(f;g) = y
2x
2yxf ?
y2x
3y2g =
y
2f ?
x
3g
= y2(2yx?y)? x3(3y2 ?x) = ?y
2
2 +
x2
3
Ref. Adams [1]
Thus, an S-polynomial allows for the cancelation of leading terms.
Deflnition: Let G = fg1;:::;gtg be a set of non-zero polynomials in k[x1;:::;xn]. Then
G is a Groebner basis for the ideal I = hg1;:::;gti if and only if for all i 6= j,
S(gi;gj)?!G+0
47
. That is, S(gi;gt) is divided by those fg1;:::;gtg 2 G, such that the remainder is
zero.
Example: Let f1 = yx?x;f2 = ?y +x2 2 Q[x;y]. Using lex order with y > x, compute
a Groebner basis for the ideal.
Solution: First, let F = ff1;f2g we calculate the S-polynomial, S(f1;f2). Then, L =
lcm(lp(f1);lp(f2)) = lcm(xy;y) = xy and
S(f1;f2) = xyxyf1 ? xy?yf2 = xyxy(xy ?x)? xy?y(?y +x2)
xy ?x+x(?y +x2) = xy ?x?xy +x3 = ?x+x3;
with respect to lex order S(f1;f2) = x3?x: Using the above deflnition, to have a Groebner
basis, S(f1;f2) ?!F+= 0; but since S(f1;f2) ?!F+6= 0, we take f3 = x3 ?x and form F0.
That is, F0 = ff1;f2;f3g.So we compute a Groebner basis for F0 by calculating S(f1;f2),
S(f2;f3) and S(f1;f3).
For S(f2;f3),
L = lcm(lp(f2);lp(f3)) = lcm(y;x3) = yx3:
48
S(f2;f3) = yx
3
?y f2 ?
yx3
x3 f3 =
yx3
?y (?y +x
2)? yx3
x3 (x
3 ?x)
yx3 ?x5 ?yx3 +yx = yx?x5
For S(f1;f3),
L = lcm(lp(f1);lp(f3)) = lcm(xy;x3) = yx3:
S(f1;f3) = yx
3
xy f1 ?
yx3
x3 f3 =
yx3
xy (xy ?x)?
yx3
x3 (x
3 ?x)
yx3 ?x3 ?yx3 +yx = yx?x3 = ?x?f2
49
But,
(5.1) S(f2;f3) = yx?x5 = ?(yx?x)+(x3 ?x) = ?yx+x3 = x?f2
and
(5.2) S(f1;f3) = ?x3 +yx = ?x(?y +x2) = ?x?f2
By adding (5.1) and (5.2) we get zero. Thus, S(f2;f3) ?!F0+ = 0 and S(f1;f3) ?!F0+ =
0:
Hence, F0 = ff1;f2;f3g is a Groebner basis for F = ff1;f2g, ref. Adams [1].
With the aid of MAGMA, a mathematical computer software package, we are able to
compute a Groebner basis faster and for larger sets of non-zero polynomials.
5.4 MAGMA: Algebraic Computer Software
MAGMA is an algebraic computer system created to solve problems in Algebra, Ge-
ometry, and Number theory. It operates on Linux based systems, but has recently been
adapted for Windows. Developed in 1993 by the Computational Algebra Group in the
School of Mathematics and Statistics at the University of Sydney, MAGMA has received
50
much praise for its advanced algorithms. Devoted to e?ciency, the developers release new
versions of the software every year.
With the assistance of MAGMA, we are able to calculate Groebner bases faster and,
more importantly, are able to compare various alternatives yielding more accurate results
that could not necessarily be calculated as easily by hand.
5.5 Solving the Inverse Kinematics Robotics Problem
5.5.1 Introduction
The inverse kinematic robotics problem is simply determining all combinations of joint
settings that will place the robot arm at a given point in space. To solve this, we must do
the following:
1. Derive polynomial equations modeling the motion of the robot arm at each joint
setting such that the robot arm can be placed at a given point in space.
2. Determine the proper intervals which allow movement at each joint.
3. Then with these equations, flnd a ?nice? set of solutions that will provide us with
possible movements of each joint.
Hence the use of a Groebner basis!!
5.5.2 Algebraic Model for the GMF Robotics A-510 Robot
We look to model the behavior of the GMF Robotics A-510 Robot using simple poly-
nomial equations. By taking a top-down view of the robot, we can project the movements
51
L3= 330
L1=410
(a-eb-f)
(0,0) (e,f)
Figure 5.1: Algebraic Model: Top View of GMF A-510 Robot
of each joint variable onto the xy-plane. Let the point (a;b) represent where the robot hand
(end efiector) will be placed in space. To solve the inverse kinematic robotics problem,
these polynomial equations need to describe the behavior of 1 and 3 in terms of the point
(a;b).
52
L1=410
(0,0) (e,f)
Figure 5.2: Algebraic Model: Top View of GMF A-510 Robot L1 = 410
Thus,
(a?e;b?f) = (330cos( 1 + 3);330sin( 1 + 3))
for
?150? ? 1 ? 150?
and
?150? ? 3 ? 150?
(e;f) = (410cos 1;410sin 1) for ?150? ? 1 ? 150?
53
.
From the flgures above,
? e = 410cos 1
? f = 410sin 1
? a?e = 330cos( 3 + 1)
? b?f = 330sin( 3 + 1)
By substituting, we get
a = 330cos( 3 + 1)+410cos 1
b = 330sin( 3 + 1)+410sin 1
By using the addition identities of trigonometric functions,
54
a = 330(cos 1 cos 3 ?sin 1 sin 3)+410cos 1
and
b = 330(cos 1 sin 3 +cos 3 sin 1)+410sin 1
Recall the trigonometric identities:
cos2 3 +sin2 3 = 1
and
cos2 1 +sin2 1 = 1
Together, we have a system of four equations in four unknowns.
(5.3) 330(cos 1 cos 3 ?sin 1 sin 3)+410cos 1 ?a = 0
(5.4) 330(cos 1 sin 3 +cos 3 sin 1)+410sin 1 ?b = 0
55
(5.5) cos2 3 +sin2 3 ?1 = 0
(5.6) cos2 1 +sin2 1 ?1 = 0
We use MAGMA to flnd a solution to the system.
5.5.3 Calculating A Groebner Basis With MAGMA
Let ci = cos i and si = sin i.
We have the following MAGMA code:
Q:=RationalField ();
FF < L1;L3;a;b > :=FunctionField(Q,4, ?lex?);
P < c3;s3;c1;s1 > :=PolynomialRing(FF,4);
f1 := L3?(c1 ?c3 ?s1 ?s3)+L1?c1 ?a;
f2 := L3?(c1 ?s3 +c3 ?s1)+L1?s1 ?b;
f3 := c21 +s21 ?1;
f4 := c23 +s23 ?1;
I:=ideal < Pjf1;f2;f3;f4 >;
G:=GroebnerBasis(I);
Note: A Function Field allows some variables to act as coe?cients and also allows for
division. Above, c3;s3;c1;s1 act as variables and L1;L3;a;b act as coe?cients.
56
Using lex order c3 > s3 > c1 > s1, MAGMA produces the following basis:
c3 ? a2+b2?L12?L322?L1?L3
s3 + a2+b2a?L3 ?a2b+b3 + b(L12+L32)2a?L1?L3
c1 + bas1 ? a2+b2+L12?L322a?L3
s21 + a2b+b3+b(L12+L32)L1(a2+b2) s1 + (a2+b2)2+(L12+L32)2?a2(L12+L32)+2b2(L12?L32)4?L12(a2+b2)
So, we have a Groebner basis when L1;L3;a 6= 0 and (a2 + b2) 6= 0. If we substitute
L1 = 410 and L3 = 330, we have the following basis:
c3 ? a2+b2?4102?33022?410?330
s3 + a2+b2a?330 ?a2b+b3 + b(4102+3302)2a?410?330
c1 + bas1 ? a2+b2+4102?33022a?330
s21 + a2b+b3+b(4102+3302)410(a2+b2) s1 + (a2+b2)2+(4102+3302)2?a2(4102+3302)+2b2(4102?3302)4?4102(a2+b2)
Looking at the last element in our basis, we see that it is a quadratic polynomial in
terms of s1. So, we can solve for s1 and determine the values of a and b that will provide
us with solutions for the GMF Robotics A-510 robot.
Notation: Let sij denote solution number j for si or ci, for i = 1;3, j = 1;2.
By examining the discriminant, there will be two real solutions for s1, and for each of s11;
and s12, there will be one corresponding value for c1;s2;c2; found by using back substitu-
tion. Furthermore, we conclude that there are two unique joint settings when
0 ? 4(a
2 +b2)2 +3504640000?2a2 ?27700+2b2 ?59200
1640(a2 +b2) ?
a2b+b3 +592000
242720002
Now we can consider two remaining cases:
57
1. Case 1: a = 0 and b = 0
2. Case 2: a = 0 and b 6= 0
5.5.4 Case Examples
Case 1: a = 0 and b = 0
We have the following MAGMA code:
Q:=RationalField ();
FF < L1;L3 > :=FunctionField(Q,2);
P < c3;s3;c1;s1 > :=PolynomialRing(FF,4, ?lex?);
f1 := L3?(c1 ?c3 ?s1 ?s3)+L1?c1;
f2 := L3?(c1 ?s3 +c3 ?s1)+L1?s1;
f3 := c21 +s21 ?1;
f4 := c23 +s23 ?1;
I:=ideal < Pjf1;f2;f3;f4 >;
G:=GroebnerBasis(I);
The Groebner basis for this case is 1.
Thus, there are no joint settings to place the robot arm at the point (a;b). It is obvious
to see by looking at the geometry of the robot arm.
58
Case 2: a = 0 and b 6= 0
Q:=RationalField ();
FF < L1;L3b > :=FunctionField(Q,2);
P < c3;s3;c1;s1 > :=PolynomialRing(FF,4, ?lex?);
f1 := L3?(c1 ?c3 ?s1 ?s3)+L1?c1;
f2 := L3?(c1 ?s3 +c3 ?s1)+L1?s1 ?b;
f3 := c21 +s21 ?1;
f4 := c23 +s23 ?1;
I:=ideal < Pjf1;f2;f3;f4 >;
G:=GroebnerBasis(I);
The Groebner basis for this case is
c3 + L23+L21?b22L3L1
s3 ? bL3c1
c21 + (L43+L41+b4)?2(L23+L21+b2(L23+L21))4L2
1b2
s1 + L23?L21?b22L1b
So, we have a Groebner basis when L1;L3;b 6= 0. By substituting L1 = 410 and
L3 = 330, we have the following basis:
c3 + 3302+4102?b22?410?330
s3 ? b330c1
c21 + (3304+4104+b4)?2(3302+4102+b2(3302+4102))4?4102b2
s1 + 3302?4102?b22?410b
59
We can immediately solve for s1 and c3. Solving for these aligns each joint link pair.
Note that the third element in the basis is a quadratic polynomial in terms of c1. By solving
for c1, we flnd two solutions c11 and c12, and for each, there is a corresponding value for s3.
This means that we can rotate about 1, given those values of s3 that will keep each joint
link pair aligned. Thus, there is only one unique joint setting to place the robot arm at the
point (a;b) when a = 0 and b 6= 0.
5.6 Summary: Mathematician?s Approach
By analyzing the above, we flnd the following results:
1. There are at most two real solutions (joint conflgurations) when (a;b) satisfles
0 ? 4(a
2 +b2)2 +3504640000?554000a2 +118400b2
1640(a2 +b2) ? (
a2b+b3 +59200
24272000 )
2:
2. From Case 1, no solutions when a = b = 0.
3. From Case 2, one real solution (joint conflguration) when (0;b) satisfles
0 ? b
p
554000?b2 ? 3504640000:
4. Those points (a,b) that do not satisfy any of the above are outside of the robot?s
reachable workspace. These points represent no solutions.
By using Groebner Basis Theory and MAGMA, we have found real solutions (see
above) to the inverse kinematic robotics problem. In fact, we have found all of the possible
formations to place the robot hand at the point (a;b). These solutions are more precise
because we determine the set of points that determine two solutions, the set of points that
60
determine one solution, and the set of points that determines no solution. Thus, the inverse
kinematic robotics problem is solved. We explain our results further in the next chapter.
61
Chapter 6
Method Analysis
6.1 GMF Robotics A-510 Robot
From the Engineering Approach, we have learned that there is the possibility of none,
one, or two solutions. However, when using the Denavit-Hartenberg Matrix, we were only
able to develop an equation that could flnd two solutions for 1 and 3 within the given
domain: ??2 ? 1 ? ?2 and ??2 ? 3 ? ?2. Since 1 and 3 rotated beyond ??2 to ?2, there
was the possibility that more solutions existed. By manipulating the equations found using
the Denavit-Hartenberg Matrix, we expanded our domain for 3 from 0 to ?, allowing 1
to rotate freely. Within this new domain, we found that there are none, one, or two solu-
tions. Since the geometry of the robot corresponds to the symmetry of the unit circle, we
found similar solutions for 3 when ?? ? 3 ? 0. Finding these solutions required a close
examination of the geometry of the robot arm, and manipulation of our kinematic model.
The GMF Robotics A-510 Robot is a ?simple? robot manipulator formed by four de-
grees of freedom. By focusing on the flrst three degrees of freedom, we were able to analyze
the geometry of the robot more easily and manipulate less complicated equations. But
what if we were to attempt the Engineering Approach on a robot arm with six or seven
degrees of freedom? Then, flnding all of the possible solutions can become quite di?cult.
The geometry of the robot arm can be challenging, and manipulating the kinematic model
to flnd more solutions can be very complicated.
62
From the Mathematician?s Approach, we learned that there are at most two real so-
lutions for (px;py). Recall, pz determines the height of (px;py). What makes the Mathe-
matician?s Approach most appealing is that we used one algorithm to determine the set of
points that would produce two solutions, the set of points that would produce one solution,
and the set of points that would produce no solution. This was achieved by incorporat-
ing the geometry of the robot arm in our algebraic model. By doing so, we immediately
acknowledged the proper intervals of movement between each joint. Moreover, by using
simple polynomial equations, no further manipulation of our algebraic model was needed
to achieve our solutions. The difierence in how these solutions are represented is profound,
and the amount of work that is required for each method speaks just as loudly.
What accounts for this difierence is how each approach solves the inverse kinematic
robotics problem. The Engineering Approach flnds 1; 3; and d2 in terms of the point
(x;y), but this approach does not identify which (x;y) will guarantee a solution without
plugging the point (x;y) into each equation as shown in the three case examples, where
as the Mathematician?s Approach flnds only those points (a;b) that are reachable points
within our workspace. (Note that (x;y) and (a;b) are arbitrary points.)
Because the Denavit-Hartenberg Matrix uses trigonometric functions, the solutions are
bounded by certain domains corresponding to each trigonometric function. This is why we
only found none, one, or two solutions when ?150? ? 1 ? 150? and ?? ? 3 ? 0. After
manipulating our kinematic model and analyzing the geometry of the robot arm, more so-
lutions existed when 0 ? 1 ? ? and ??2 ? 3 ? ?2. The Mathematician?s Approach avoids
the trouble of flnding solutions within a limiting domain. By developing an algebraic model
using simple polynomial equations we incorporate the entire unit circle with the assistance
63
of trigonometric identities. There is no need to manipulate the equations in our model to
flnd more solutions. Calculating a Groebner basis with MAGMA flnds all possible solu-
tions. In particular, by using the Algebraic Approach, given (a;b) we can easily discover
the maximum number of formations to place the robot hand at the point (a;b), and more
importantly, we discover all real solutions that produce these formations. Because of these
precise results, it is clear why the Mathematician?s Approach is the more e?cient method.
In the following sections, we introduce the Jacobian Matrix and Singularities, a supple-
mental method to the Denavit-Hartenberg Matrix that determines singular conflgurations
(i.e, one solution). This section is presented to demonstrate the great lengths required by
the Engineering Approach to better determine and classify all solutions.
6.2 The Jacobian Matrix and Singularities
For a robot manipulator, there are two joint conflgurations that require further cal-
culations in order to solve the inverse kinematic problem. These particular conflgurations
occur when:
? joint axes are intersecting
? joint axes are parallel (collinear)
In fact, when establishing link coordinate frames, these particular conflgurations are
exceptions to the rules outlined by Lee (See Section 4.4). We call the points in space associ-
ated with these conflgurations singularities and use the Jacobian Matrix to flnd these points.
64
6.2.1 The Jacobian for a Robot Manipulator
The Jacobian discusses joint velocities and accelerations, but in this comparison study,
we are not interested in either of these, but are concerned with how the Jacobian can be
used to determine when there is one solution.
Deflnition: A Jacobian for a robot manipulator is a matrix of difierentials. This matrix
describes the difierential changes in the location of the end efiector caused by the
difierential changes in joint variables.
Using Cartesian coordinates, the displacement of the end efiector can be described by
a difierential motion vector ~D = [dxdydz?x?y?z]. Similar to our derivation of the Denavit-
Hartenberg matrix, we arrive at ~D by performing certain translational and rotational trans-
formations that describe the change in motion from the n?1thjoint to the nth joint. Also,
recallthattheDenavit-Hartenbergmatrixisaspecialhomogeneousmatrixcomposedofonly
four parameters. Now let ~Dq be a special difierential motion vector that describes the dis-
placement of the end efiector in terms of the joint coordinates. Then, ~Dq = [dq1dq2 :::dqn],
for an n-joint manipulator, where dqn is a difierential rotation and ddn is a difierential
translation at joint n.
Consider a robot manipulator with four joints, then ~D and ~Dq are related by the
following equation:
~D = ~J ? ~Dq:
Using this, we flnd the Jacobian.
65
2
66
66
66
66
64
dx
dy
?x
?y
3
77
77
77
77
75
=
2
66
66
66
66
64
J11 J12 J13 J14
J21 J22 J23 J24
J31 J32 J33 J34
J41 J42 J43 J44
3
77
77
77
77
75
2
66
66
66
66
64
dq1
dq2
dq3
dq4
3
77
77
77
77
75
Thus,
J =
2
66
66
66
66
64
J11 J12 J13 J14
J21 J22 J23 J24
J31 J32 J33 J34
J41 J42 J43 J44
3
77
77
77
77
75
is the Jacobian.
So, the Jacobian establishes the relationship between the Cartesian velocities ~D and
the joint velocities ~Dq. Furthermore, McKerrow,[16] highlights the following:
? dx = J11dq1 + J12dq2 + J13dq3 + J14dq4. But, dx represents the x component of the
difierential motion of the end efiector, so from this equation, we conclude that dx is
also a function of the difierential motion of the joints of the manipulator.
? dy = J21dq1 + J22dq2 + J23dq3 + J24dq4. But, dy represents the y component of the
difierential motion of the end efiector, so from this equation, we conclude that dy is
also a function of the difierential motion of the joints of the manipulator.
? ?x = J31dq1 + J32dq2 + J33dq3 + J34dq4. But ?x is the x component of the angular
motion of the end efiector, so from this equation, we conclude that ?x is a function of
66
the difierential motion of the joints of the manipulator. Similarly, for ?y, we conclude
that ?y is a function of the difierential motion of the joints of the manipulator.
? Jij is the partial derivative with respect to joint j of the xi component of the position
of the end efiector. In this case, x1 = x and x2 = y. So, Jij is the partial derivative
with respect to joint j, where j = 1;2;3;4.
The inverse Jacobian establishes the relationship between the Cartesian velocities of the
end efiector and the joint velocities, and is given by,
~Dq = J?1~D
Properties of the Jacobian
For the Jacobian Matrix,
1. The number of rows is determined by the number of degrees of freedom.(The joint
representing the end efiector is not counted.)
2. The number of columns is determined by the number of joints in the manipulator
3. In some instances, the Jacobian is not a square matrix.
6.2.2 Finding the Jacobian for the GMF Robotics A-510 Robot
We begin by calculating the Forward Kinematic solution by taking P calculated in
Chapter 3, and setting P = T ? VariableMatrix. Then, the flnal position of the end
efiector is described by (px;py;pz). In particular,
67
2
66
66
64
px
py
pz
3
77
77
75 =
2
66
66
64
330cos( 1 + 3)+410cos 1
330sin( 1 + 3)+410sin 1
980+d2
3
77
77
75
Observe that pz represents the height of the flnal position of the end efiector. But px
and py are determined by 1 and 3. If we examine the robot from a top view, by looking
down on the robot, we can project each joint conflguration onto the xy- plane. With this
perspective, we restrict our focus to 1 and 3. So, from the matrix above, we now have the
following representation.
2
64 px
py
3
75 =
2
64 330cos( 1 + 3)+410cos 1
330sin( 1 + 3)+410sin 1
3
75
To calculate the Jacobian, we difierentiate, such that
2
64 dpx
dpy
3
75 = J
2
64 d 1
d 2
3
75
To flnd the matrix J, we need to flnd the partial derivatives,
2
64 dpx
dpy
3
75=
2
64 ?330sin 1 cos 3 ?330cos 1 sin 3 ?410sin 1 ?330cos 1 sin 3 ?330sin 1 cos 3
330cos 1 cos 3 ?330sin 1 sin 3 +410cos 1 ?330sin 1 sin 3 +330cos 1 cos 3
3
75
2
64 d 1
d 2
3
75
Next, we calculate the inverse Jacobian.
68
J?1 =
2
64 J22 ?J12
?J21 J11
3
75
jJj
where
J11 = ?330sin 1 cos 3 ?330cos 1 sin 3 ?410sin 1
J12 = ?330cos 1 sin 3 ?330sin 1 cos 3
J21 = 330cos 1 cos 3 ?330sin 1 sin 3 +410cos 1
J22 = ?330sin 1 sin 3 +330cos 1 cos 3
Then,
jJj = J11J22 ?J12J21
= (?330sin 1 cos 3 ?330cos 1 sin 3 ?410sin 1)(?330sin 1 sin 3 +330cos 1 cos 3)
?(?330cos 1 sin 3 ?330sin 1 cos 3)(330cos 1 cos 3 ?330sin 1 sin 3 +410cos 1)
After several cancelations,
jJj = 330?410sin2 1 sin 3 +330?410cos2 1 sin 3 = 135300sin 3
69
So the inverse Jacobian is deflned when sin 3 6= 0.
In particular,
2
64 d 1
d 2
3
75 = 1
135300sin 3
2
64 J22 ?J12
?J21 J11
3
75
2
64 dpx
dpy
3
75
And the Jacobian for the GMF Robotics A-510 Robot has been found. In the next
section, we explain the signiflcance of the Jacobian in more detail.
6.2.3 Singularities
Deflnition: A singularity is simply a point in space where a singular conflguration results.
There are two types of singularities: a workspace internal singularity and a workspace
boundary singularity.
Deflnition: A workspace internal singularity occurs within the workspace,
Deflnition: A workspace boundary singularity occurs when the manipulator is fully ex-
tended to the outer boundary or fully retracted to the inner boundary of its workspace.
Ref Mckerrow, [16].
In the case where joint axes are parallel, a robot manipulator has lost one or more
degrees of freedom, reducing the robot?s mobility in some directions. The point in space
where this occurs is called a workspace internal singularity or a workspace boundary singu-
larity. The Jacobian helps us determine these singular conflgurations.
70
6.2.4 Finding Singularities for the GMF A-510 Robot
When the determinant of the Jacobian is zero, the robot manipulator has a workspace
singularity. We determine the singularities for the GMF Robotics A-510 Robot.
From the previous section, sin 3 = 0 when 3 is either 0 or ?. But 3 ranges from
?150? ? 3 ? 150?, so ? is not a point within the workspace. However, when 3 = 0, we
get a workspace boundary singularity. We substitute 3 = 0 into J, and get,
2
64 dpx
dpy
3
75 =
2
64 ?330sin 1 ?410sin 1 ?330sin 1
330cos 1 +410cos 1 330cos 1
3
75
2
64 d 1
d 2
3
75
which reduces to,
2
64 dpx
dpy
3
75 =
2
64 ?740sin 1 ?330sin 1
740cos 1 330cos 1
3
75
2
64 d 1
d 2
3
75
Observe that the two column vectors in the above Jacobian matrix are parallel. Thus,
only those points on the boundary, that is, those points on the circle of radius r = 740 cen-
tered at the origin, where 1 can rotate from ?150? ? 1 ? 150?, are workspace boundary
singularities. Moreover, it is at these points where the inverse Jacobian is undeflned. So,
there is one solution (i.e., one conflguration) that can reach these points.
71
6.3 A Procedure for an Algebraic Model for Robot Manipulators
In this section, we look to extend our results to an entire class of robot manipulators
that satisfy the following conditions:
? The robot manipulator has n-degrees of freedom,
? The robot manipulator is a kinematic chain consisting of revolute or prismatic joints,
? The joints of the robot manipulator may be collinear or intersecting, but neither is
required.
Each robot manipulator is difierent. Thus, a difierent algebraic model must be formed.
The challenge of the Mathematician?s Approach is deriving an algebraic model. The al-
gebraic model must describe the behavior of the robot such that the relationship between
neighboring joints is respected. The easiest way to achieve this is to map the movements
of each joint onto a 2D-coordinate plane, then use trigonometric functions and identities to
imitate each joint movement, as well as, the resulting movements that occur from related
joints.
Recall the algebraic model used for the GMF Robotics A-510 Robot. Observe that the
there are three joints, a prismatic joint, and two revolute joints. This prismatic joint simply
moves the other two joints in an up and down motion. Because these two revolute joints
are consecutive, they move up and down together. See the flgure 6.1.
This picture is a side view of the GMF Robotics A-510 robot. Now consider a top/down
view of the robot. With this view, we restrict our focus to each revolute joint. If we project
this perspective onto the xy-plane, we can identify the movements of each joint. The point
(e;f) = (410cos 1;410sin 1) describes the movement of revolute joint 1. The second revo-
lute joint, however, not only describes the movement of joint 2, but also acknowledges those
72
a0 a1 a2 a3 a4
a5 a6 a7 a8 a9
a10 a11 a11 a12
a13 a1 a2 a3 a4
a14 a15 a16 a17 a18 a1 a2 a3 a4
a1 a19 a20 a15 a18 a1 a2 a3 a4
Figure 6.1: GMF A-510 Robot, ref. Hung [8]
movements of joint 2 that are in uenced by the movements of joint 1. The end efiector is
represented by the point (a;b) = (330cos( 1 + 3)+410cos 1;330sin( 1 + 3)+410sin 1),
which encompasses the movements at both joints. Using trigonometry, we are able to rep-
resent the position of the end efiector with simple polynomial equations.
In order to proceed with the Mathematician?s Approach, the equations in the algebraic
model must be polynomial equations. Once these equations have been established, we use
MAGMA to flnd a Groebner basis for these equations. By analyzing the Groebner basis,
we are able to determine each unknown variable, as well as those points that can be reached
by the end efiector.
Given a robot manipulator that satisfles the conditions above, we outline the following
procedure to derive an algebraic model:
73
1. Analyze the geometry of the robot manipulator
2. Isolate particular joint behavior and project the joint movements onto a coordinate
system
3. Represent the joint movements using polynomial equations.
4. Verify that these polynomial equations preserve the movement of each joint and the
relationship between neighboring joints.
By following these steps, we arrive at a system of equations, Hence, for a particular
class of robot manipulators, we have provided a systematic procedure for deriving an al-
gebraic model, and with MAGMA are able to apply Groebner Basis Theory to solve the
inverse kinematic robotics problem.
74
Chapter 7
Conclusion
In this flnal chapter, we discuss the di?culties and challenges associated with the
Engineering Approach, and with each di?culty, illustrate how Groebner Basis Theory solves
the inverse kinematic robotics problem without these di?culties. Guez and Ahmad [5]
summarize the following di?culties for an inverse kinematic solution:
1. To form the Aij matrices, we need to know the forward kinematics of the manipulator.
2. There are situations where the Denavit-Hartenberg matrix will not produce equations
that will flnd all possible solutions. Thus, an alternate method must be used to flnd
all solutions.
3. Every robot manipulator has solutions speciflc to that manipulator. Thus, new algo-
rithms and procedures have to be developed to accommodate each manipulator.
In order to use Groebner Basis Theory, we must create an algebraic model describing
the behavior of the robot manipulator. There is no need to form the Aij matrices. So, we
address how Groebner Basis Theory can resolve the last two di?culties. However, if the
previous conditions for deriving an algebraic model (in Section 6.3) are satisfled, we suggest
using the Mathematician?s Approach when such Aij matrices are not easily formed.
Beginning with the second di?culty, there are several situations when the Denavit-
Hartenberg matrix will not produce equations that will flnd all possible solutions. We
revealed one situation in our calculations for the GMF Robotics A-510 robot. By using the
75
Denavit-Hartenbergmatrix, wesolvedaquadraticequationflndingtwosolutions(conflgurations)
for 1 and 3 within a given domain. However, we did not flnd all solutions. By manipu-
lating the kinematic model, we found more solutions. In addition, by testing three random
points within the robot?s workspace, we saw the possibility of no solutions or one solution.
But we were uncertain of when these particular solutions would occur? Hence, the need
for an alternate method called the Jacobian that could accurately determine when there
would be one solution. Using this supplementary method, we found that when L1 = 410
and L3 = 330 are collinear, there would be one solution for the GMF Robotics A-510 robot.
In addition, we also wish to determine when there are no solutions. Clearly, there are no
solutions for those points that are outside of the reachable workspace.
The Mathematician?s Approach flnds all of those points that can be reached within
the workspace. In fact, by calculating a Groebner basis, we are able to determine which
points within the workspace have two solutions (two conflgurations), which points have one
solution (one conflguration), and which points have no solution. Through the Mathemati-
cian?s Approach, we used one method that uses one algorithm. There is no need to use
a supplementary method or second algorithm. Also, as a result, the number of calcula-
tions required to solve the inverse kinematic robotics problem is greatly reduced. Horn, [6],
acknowledges those di?culties associated with flnding all possible solutions by use of the
Denavit-Hartenberg matrix, arguing that the solutions to the inverse kinematic robotics
problem should be "simple to determine and easy to use." Because the Mathematician?s
Approach accomplishes both desires, we conclude that the Mathematician?s Approach is a
better method for producing equations that will flnd all possible solutions.
76
Lastly, in other situations, the Denavit-Hartenberg matrix must be coupled with other
methods or algorithms to flnd all possible solutions. These methods and algorithms include,
but are not limited to neural networking techniques, iterative algorithms, visual servoing,
euler parameters, etc. In the past, each robot manipulator required its own particular
method given the above mentioned di?culties associated with the Denavit-Hartenberg ma-
trix. With the introduction of the Groebner Basis Theory, we provide an alternate method
that may be used on an entire class of robot manipulators satisfying the conditions in Sec-
tion 6:3. For this exibility, we see that the Mathematician?s Approach is an improved
alternate. With further research we look to show that the Mathematician?s Approach can
be used for other classes of manipulators.
With the conclusions found in this paper, we have demonstrated how the Mathemati-
cian?s Approach of Groebner Basis Theory is an alternate method to solving the inverse
kinematic robotics problem. Moreover, by using Groebner Basis Theory, we used one pro-
cedure, performed less calculations, found real solutions, and established when certain so-
lutions (none, one, two, etc.) would occur. Because of these advantages, we see how
Groebner Basis Theory is more beneflcial than the Denavit-Hartenberg Matrix. Also, be-
cause of these advantages, I wish to expand the applications of Groebner Basis Theory to
many other classes of robot manipulators, solving the inverse kinematic robotics problem
for larger classes of robot manipulators.
77
Bibliography
[1] William Adams, Philippe Loustaunau,"?An Introduction to Groebner bases"? American
Mathematical Society, Vol.3, Providence, Rhode Island, 1994.
[2] Bruno Buchberger, "?Groebner Bases: An Algorithmic Method in Polynomial Ideal
Theory,"? Multidimensional Systems Theory, Reidel Publishing Company, Dodrecht,
1985.
[3] David Cox, John Little, Donal O?Shea, \Ideals, Varieties, and Logarithms: An Intro-
duction to Computational Algebraic Geometry and Commutative Algebra," Springer-
Verlag New York Inc., 1992.
[4] J. Denavit, R. S. Hartenberg, "?A Kinematic Notation for Lower-Pair Mechanisms
Based on Matrices,"? Journal of Applied Mechanics, 1955.
[5] Allon Guez, Ziauddin Ahmad,"?Solution to the Inverse Kinematic Problem in Robotics
by Neural Network,"?Second International Conference of Neural Networks, March 1988.
[6] Berthold K.P. Horn, "?New Notation for Serial Kinematic Chains,"? May 1987.
[7] B. Huang, V. Milenkovic, "?Kinematics of Major Robot Linkages,"? Proceedings of the
13th International Symposium on Industrial Robots,"? April 17-19, Chicago, IL.
[8] John Hung, \Kinematic Model for the GMF Robotics A510 Robot," Department of
Electrical and Computer Engineering, Auburn University, Auburn, Alabama, 2007.
[9] Kimberly D. Kendricks, \Using Groebner Bases to Solve the Inverse Kinematic
Robotics Problem for a Planar Robot Arm," Master?s Project, Department of Mathe-
matics, Auburn University, Auburn, Alabama 2006.
[10] Richard D. Klafter, Thomas A. Chmielewski, Michael Negin, \Robotic Engineering An
Integrated Approach," Prentice Hall, Englewood Clifis, New Jersey, 1989.
[11] Yoram Koren, "?Robotics for Engineers"? McGraw-Hill Book Company, New York,
New York, 1985.
[12] Antti J. Koivo, "?Fundamentals for Control of Robotic Manipulators,"? John Wiley
and Sons, Inc., New York, 1989.
[13] C.S. George Lee, C.G. Liang, "?Displacement Analysis of the General Spatial 7-Link,
7-R Mechanism,"? Journal of Mechanisms and Machine Theory, Vol.23, Issue 3, 1988.
78
[14] C.S. George Lee, "?Robot Arm Kinematics, Dynamics, and Control,"? Tutorial of
Robotics, University of Michigan, Ann Arbor, 1982.
[15] Rachid Manseur, Keith L. Doty, "?A Fast Algorithm for Inverse Kinematic Analysis of
Robot Manipulators,"? The International Journal of Robotics Research, Vol. 7, No.3,
Massachusetts Institute of Technology, 1988.
[16] Phillip John McKerrow, "?Introduction to Robotics,"?Addison-Wesley Publishing Com-
pany, New York, 1991.
[17] R. P. Paul, "?Robot Manipulators: Mathematics, Programming, and Control,"? M.I.T.
Press, 1981.
[18] R. P. Paul, Bruce Shimano, Gordon E. Mayer, "? Kinematic Control Equations for Sim-
ple Manipulators,"? Tutorial on Robotics, IEEE Computer Society Press, Washington,
DC, 1981.
[19] D. L. Pieper, "?The Kinematics of Manipulators Under Computer Control,"? Artiflcial
Intelligence Project Memo No.72, Computer Science Department, Stanford University,
1968.
[20] L. Robbiano, "Groebner Bases and Statistics," Groebner Bases and Applications, Cam-
bridge University Press, 1998.
[21] L.W. Tsai, A.P. Morgan, "?Solving the Inverse Kinematics of the Most General Six,
and Five-Degree-of-Freedom Manipulators by Continuation Methods,"? American So-
ciety for Mechanical Engineers, Design Engineering Techinical Conference, Cambridge,
Mass., 1984.
[22] D. Wang, "Groebner Bases Applied to Geometric Theorem Proving and Discovering,"
Groebner Bases and Applications, Cambridge University Press, 1998.
[23] T.C. Yih, Y.Youm, "?Geometrical Modeling of Lower-Pairs Based on Spherical-Euler
Geometry,"? Trends and Developments in Mechanisms, Machines, and Robotics, Vol.
15-1, 1988.
[24] GMF Robotics A-510 Robot Descriptions Manual
79
Appendix
Matrix Calculations:
A12 ?A23 =
2
66
66
66
66
64
1 0 0 410
0 1 0 0
0 0 1 d2
0 0 0 1
3
77
77
77
77
75
2
66
66
66
66
64
cos 3 ?sin 3 0 330cos 3
sin 3 cos 3 0 330sin 3
0 0 1 0
0 0 0 1
3
77
77
77
77
75
=
2
66
66
66
66
64
cos 3 ?sin 3 0 330cos 3 +410
sin 3 cos 3 0 330sin 3
0 0 1 0
0 0 0 1
3
77
77
77
77
75
A01 ?A?101 =
2
66
66
66
66
64
cos 1 ?sin 1 0 0
sin 1 cos 1 0 0
0 0 1 980
0 0 0 1
3
77
77
77
77
75
2
66
66
66
66
64
cos 1 sin 1 0 0
?sin 1 cos 1 0 0
0 0 1 ?980
0 0 0 1
3
77
77
77
77
75
80
=
2
66
66
66
66
64
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
3
77
77
77
77
75
81