Polynomial Continuation in the Design
of Deployable Structures
Andrew Viquerat
King’s College
Department of Engineering
University of Cambridge
A thesis submitted for the degree of
Doctor of Philosophy
October 2011
For my parents, David and Maureen.
i
Acknowledgements
Most of all, I would like to thank my supervisor, Dr Simon Guest for his
ability to immediately identify the core issues in any problem and to see
new and exciting directions for research with ease, his willingness to hear
out any and all of my ideas, no matter how implausible, and his painstaking
attention to detail. My advisor, Dr Keith Seffen also deserves thanks for
being a wonderful source of, and check-point for ideas.
I would like to thank the University of Cambridge, King’s College Cam-
bridge, and in particular, the King’s College graduate community for provid-
ing a ready-made family away from home.
The Advanced Structures research group has provided a rich and diverse
source of inspiration over the past three years. In particular I would like
to thank Mark Schenk, Alex MacDonald, Richard Silveira, Richard Persaud,
Mohammad-reza Golabchi and Arnaud Bonin.
I am very grateful for the financial support provided by King’s College, the
Cambridge Commonwealth Trust, and the University of Sydney Travelling
Scholarships.
ii
Declaration
This dissertation is the result of my own work and includes nothing which
is the outcome of work done in collaboration except where specifically indi-
cated in the text. The research described in this dissertation was carried out in
the Department of Engineering at the University of Cambridge between Oc-
tober 2008 and September 2011. This dissertation has not been previously
submitted, in part or in whole, to any university or institution for any degree,
diploma, or other qualification. This dissertation is presented in 186 pages,
and contains fewer than 150 images, and fewer than 65000 words including
all appendices and bibliography.
iii
Abstract
Polynomial continuation, a branch of numerical continuation, has been ap-
plied to several primary problems in kinematic geometry. The objective of
the research presented in this document was to explore the possible exten-
sions of the application of polynomial continuation, especially in the field
of deployable structure design. The power of polynomial continuation as a
design tool lies in its ability to find all solutions of a system of polynomial
equations (even positive dimensional solution sets). A linkage design prob-
lem posed in polynomial form can be made to yield every possible feasible
outcome, many of which may never otherwise have been found.
Methods of polynomial continuation based design are illustrated here by way
of various examples. In particular, the types of deployable structures which
form planar rings, or frames, in their deployed configurations are used as
design cases. Polynomial continuation is shown to be a powerful component
of an equation-based design process.
A polyhedral homotopy method, particularly suited to solving problems in
kinematics, was synthesised from several researchers’ published continua-
tion techniques, and augmented with modern, freely available mathematical
computing algorithms. Special adaptations were made in the areas of level-
k subface identification, lifting value balancing, and path-following. Tech-
niques of forming closure/compatibility equations by direct use of symmetry,
or by use of transfer matrices to enforce loop closure, were developed as ap-
propriate for each example.
The geometry of a plane symmetric (rectangular) 6R foldable frame was ex-
amined and classified in terms of Denavit-Hartenberg Parameters. Its design
parameters were then grouped into feasible and non-feasible regions, before
continuation was used as a design tool; generating the design parameters
required to build a foldable frame which meets certain configurational spec-
ifications.
iv
Two further deployable ring/frame classes were then used as design cases:
(a) rings which form (planar) regular polygons when deployed, and (b) rings
which are doubly plane symmetric and planar when deployed. The governing
equations used in the continuation design process are based on symmetry
compatibility and transfer matrices respectively.
Finally, the 6, 7 and 8-link versions of N-loops were subjected to a witness
set analysis, illustrating the way in which continuation can reveal the nature
of the mobility of an unknown linkage.
Key features of the results are that polynomial continuation was able to pro-
vide complete sets of feasible options to a number of practical design prob-
lems, and also to reveal the nature of the mobility of a real overconstrained
linkage.
General Keywords: 6R Linkage, Deployable ring, Deployable structures,
Numerical continuation, Overconstrained mechanism, Polyhedral homotopy,
Polynomial continuation.
Library of Congress Keywords: Continuation methods, Equations (Nu-
merical solutions), Foldable structures, Homotopy theory, Kinematics.
CUED Library Keywords: Deployable structures, Kinematic geometry,
Linkages, Polynomial continuation.
v
Contents
Contents vi
Nomenclature xi
1 Introduction 1
1.1 Deployable Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Design Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Standard Kinematic Synthesis Techniques . . . . . . . . . . . . . 6
1.2.2 Perfect Planar Mechanisms . . . . . . . . . . . . . . . . . . . . . 8
1.2.3 Optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.4 Direct Solution of Closure/Compatibility Equations . . . . . . . . 9
1.3 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2 Polynomial Continuation 18
2.1 Polynomial Continuation Basics . . . . . . . . . . . . . . . . . . . . . . 18
2.1.1 The Degree of a System of Polynomial Equations . . . . . . . . . 18
2.1.2 Types of Solutions of Polynomial Equations . . . . . . . . . . . . 19
2.1.3 The ‘Circle’ Problem . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Predictor-Corrector Method (Path Following) . . . . . . . . . . . . . . . 24
2.2.1 Step Size Control . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.2 Path Follower Control Parameters . . . . . . . . . . . . . . . . . 27
2.3 Homogenisation and Be´zout Numbers . . . . . . . . . . . . . . . . . . . 30
2.3.1 Multi-Homogeneous Start Systems . . . . . . . . . . . . . . . . 32
2.3.2 The Homotopy . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.4 Polyhedral Homotopy Method . . . . . . . . . . . . . . . . . . . . . . . 34
2.4.1 A Simplex Minimisation Method . . . . . . . . . . . . . . . . . 40
2.4.2 A More Intuitive Method . . . . . . . . . . . . . . . . . . . . . . 45
2.4.3 Optimising the Lifting Values to Improve Numerical Stability . . 47
vi
2.5 Witness Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.5.1 Monodromy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.6 Solution to a Hinge Closure Problem . . . . . . . . . . . . . . . . . . . . 53
3 Plane Symmetric Bricard 6R Foldable Frames 56
3.1 Frame Geometry and Definitions . . . . . . . . . . . . . . . . . . . . . . 57
3.2 Expression in Terms of Denavit-Hartenberg Parameters . . . . . . . . . . 62
3.3 Examination of Mobility using a Cascade of Homotopies . . . . . . . . . 65
3.4 Finding a Feasible Region of Design Parameters . . . . . . . . . . . . . . 70
3.5 A Two-Variable Compatibility Equation . . . . . . . . . . . . . . . . . . 73
3.6 Using a Polyhedral Homotopy to Design the Plane Symmetric Bricard
6R Foldable Frame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.6.1 Examples of Solution Runs . . . . . . . . . . . . . . . . . . . . . 80
3.7 Deployment of the 6R Foldable Frame . . . . . . . . . . . . . . . . . . . 83
3.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4 Regular-Polygonal Foldable Rings 85
4.1 Existing Designs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.1.1 A Hoop-Column Antenna . . . . . . . . . . . . . . . . . . . . . 86
4.1.2 A Spoked Wheel to Deploy Large Surfaces . . . . . . . . . . . . 86
4.2 Ring Geometry and Compatibility Equations . . . . . . . . . . . . . . . . 89
4.2.1 Original Derivation of Ring Geometry Based on Triangular Cross-
Sectioned Bars . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.2.2 Expression of the Hinge Vectors in Local Bar Coordinates . . . . 92
4.2.3 Constructing the Two Compatibility Equations . . . . . . . . . . 94
4.3 Using the Compatibility Equations to Design the Ring . . . . . . . . . . . 96
4.3.1 Using the Original Form of the Compatibility Equations . . . . . 97
4.3.2 Using {φ , θ} to Specify Bar Orientation . . . . . . . . . . . . . 101
4.3.3 Using {θ , ψ} to Specify Bar Orientation . . . . . . . . . . . . . 104
4.4 Simulating the Ring’s Motion . . . . . . . . . . . . . . . . . . . . . . . . 108
4.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5 Doubly Symmetric 8-Bar Foldable Rings 112
5.1 Arbitrarily Positioned Vertices . . . . . . . . . . . . . . . . . . . . . . . 113
5.1.1 A Loop Closure Equation . . . . . . . . . . . . . . . . . . . . . 114
5.1.2 Constraint Equations and Design Variables . . . . . . . . . . . . 116
5.1.3 Continuation Results . . . . . . . . . . . . . . . . . . . . . . . . 120
vii
5.2 Rectangular 8-Bar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
5.2.1 Continuation Results . . . . . . . . . . . . . . . . . . . . . . . . 128
5.3 Deployment of 8-Bar Rings . . . . . . . . . . . . . . . . . . . . . . . . . 132
5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6 Mobility of 6,7 & 8-Link N-Loops 135
6.1 ‘Tangle’ N-Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.2 6-Link N-Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
6.3 Solution Structure of 6-Loop Equations . . . . . . . . . . . . . . . . . . 140
6.3.1 Solutions of Dimension 1 . . . . . . . . . . . . . . . . . . . . . 140
6.3.2 Solutions of Dimension 0 . . . . . . . . . . . . . . . . . . . . . 141
6.4 7 & 8-Loops and Their Mobility . . . . . . . . . . . . . . . . . . . . . . 141
6.4.1 The Degree of the 8-Loop’s Mobility . . . . . . . . . . . . . . . 142
6.4.2 The Degree of the 7-Loop’s Mobility . . . . . . . . . . . . . . . 144
6.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
7 Conclusions 148
Glossary 155
References 156
A Feasibility Charts for Plane-Symmetric 6-Bar Linkage 166
B Software Guide 175
B.1 Using Software to Find Dimension-Zero Solutions of a System of Poly-
nomial Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
B.2 Using Software to Find Higher Dimensional Solutions of a System of
Polynomial Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
viii
Nomenclature
Roman Symbols
aij 1) Denavit-Hartenberg bar length (i, j = 1, . . . , 6)
2) element j of polynomial support i
d witness set dimension
f polynomial target system
g polynomial start system
h homotopy
hi hinge vector i
J Jacobian matrix
K small displacement matrix of a closed loop
ki multiplicity of equation structure i
L intersecting complex hyperplane
Li single axis rotation matrix (i = 1, 2, 3)
li length of bar i
mi dim(Qi)
M,Mi pure translation matrix
N number of bars in loop
n number of variables or equations in system of polynomials
nx normal vector to plane (x = l, r)
ix
pi hinge or point location
Q loop closure/compatibility equation
Qi convex hull of equation i’s support
R rotation matrix
r number of distinct polynomial structures present in system
Ri Denavit-Hartenberg hinge extension (i, j = 1, . . . , 6)
t continuation parameter
Tij transfer matrix from coordinates i to coordinates j
wi lifting function for equation i
zi extra variables in homotopy cascade system
Greek Symbols
αi 1) 6-bar hinge tilt angle (i = 1, 2)
2) Reg.-polygon cross-section internal angles (i = 1, 2, 3)
αij Denavit-Hartenberg hinge angle (i, j = 1, . . . , 6)
αx hinge tilt angle (x = a, b, c)
βi 6-bar hinge tilt angle (i = 1, 2)
δxY offset distance (x = a, b, c)
γ 6-bar design parameter
λ 1) number of spatial degrees of freedom
2) random complex number
φ general roll angle
φij N-loop hinge twist between link i and j
φx hinge opening angle (x = a, b, c)
ψ general yaw angle
x
σ singular value
θ general pitch angle
θij 6-bar hinge angle (i, j = 1, . . . , 6)
Superscripts
6-bar hinge tilt projection onto Y Z plane
L geometric part of transfer matrix
Subscripts
B transfer matrix equation
g geometric part of transfer matrix
l left
R rotation matrix equation
r right
s 1) stowed location
2) ‘state’ part of matrix
xi
1. Introduction
1.1 Deployable Structures
The term Deployable Structure (Gantes, 2001; Guest, 1994; Pellegrino, 2001) is used to
describe a device which has at least two distinct states. A simple example is an um-
brella. An umbrella has two distinct states (open and closed), and displays one of the
most common design requirements of deployable structures in general, which is that in
its inoperative state it is much more compact. The umbrella design in Figure 1.1 is a
mechanism which consists of a single revolute/slider joint, and a number of planar sub-
mechanisms (arranged radially), each with two bars connected by revolute joints. In
deploying an umbrella, one introduces strain energy into the covering fabric, and then
contains this energy by using a simple spring loaded catch. The energy gradient of the
deployment process ensures that this state is stable. A number of typical requirements of
Figure 1.1: Umbrella: The most familiar deployable structure? (Licensed under the GFDL by
the author)
a deployable structure are illustrated in this simple example. These include:
1
1.1 Deployable Structures
• structure has at least two distinct states;
– stowed
– deployed
• structure is typically more compact and robust in the stowed state;
• structure occupies a larger volume in the deployed state. This is usually the state in
which the deployable structure is operational, although it might be more fragile;
• a smooth deployment path exists between the two states;
• the deployed state is stable (meaning the deployed shape does not need to be ac-
tively maintained);
• the structure’s deployment is reliable and, sometimes, repeatable. This points to a
need for simplicity in design.
Deployable structures have been used by engineers to solve problems in a variety of
situations. Deployable structures have even been found to arise in nature (De Focatiis &
Guest, 2002). Some of the most interesting applications are to be found in satellite design,
in which deployable booms, masts, antennae, radars and solar arrays are commonplace.
These deployable structures are launched in the stowed state, when volume minimisation
requirements are of the greatest importance. Once in orbit, the structures can be deployed.
The reliability of this deployment phase is of critical importance. Reliability can be
increased by keeping a design as simple as possible, and also often by restricting any
mechanisms involved to those with a single degree of freedom (SDOF). It is for this
reason that a number of the linkages addressed in this document are SDOF.
Not all deployable structures are mechanisms in the traditional sense of the word.
Some categories of structures are:
Telescopic Structures These are often used to deploy masts, antennae, or other devices
of circular cross-section. They can be deployed using internal cables, threads, or
even controlled gas expansion. See Figure 1.2.
Pantographic Structures A simple pantograph is a planar, scissor-like linkage whose
motion is strictly linear. Pantographs of this type are often found attached to shav-
ing mirrors in bathrooms. The basic linkage can be modified to form mechanisms
such as the Hoberman Sphere and expandable “blob” structures (Jensen & Pel-
legrino, 2002, 2005), and extended into three dimensions to form pantographic
2
1.1 Deployable Structures
Latches
Nuts
Motor
Figure 1.2: Telescopic Mast (reproduced from Pellegrino (1995)).
rings, or masts such as that shown in Figure 1.3. Further examples of pantographic
structures can be found in Pellegrino & You (1993); You & Pellegrino (1997a,b).
Similar base-level mechanisms called double chains have also been used to create
mobile, closed loop structures (Mao et al., 2009).
Figure 1.3: Pantographic mast developed by You.
Bistable Structures A common example of a bistable structure is a carpenter’s tape
3
1.1 Deployable Structures
measure. Strips of metal, composite or plastic can be pre-stressed in such a way
that the strip is stable when rolled up, and also when stretched out straight. A
similar structure can be constructed without pre-stress by making use of composite
material properties (an idea commercialised by a company called RolaTube, which
makes masts using this concept). An example is shown in Figure 1.4. The dynam-
ics of strips which use their own internal energy to deploy have been the topic of a
good deal of research (Seffen & Pellegrino, 1999).
Figure 1.4: A bistable tube design. These are long thin strips which are stable both in a coiled
and deployed state. (a) STEM, (b) bi-STEM, and (c) interlocking bi-STEM. The
Storable Tubular Extendible MemberTM is produced by Northrop Grumman and has
been used in space applications for over 30 years.
Inflatable Structures As the name suggests, inflatable structures (Fang et al., 2004) are
devices which in the stowed (deflated) state are thin membranes which can be easily
and compactly stored, and can be inflated to fill a larger volume, and even take on
some structural rigidity. A simple example is a balloon (Figure 1.5). A slightly
more complicated example is JPL’s inflatable SAR frame, shown in Figure 1.6.
Sometimes inflatable structures are chemically rigidized once fully deployed.
Folding Frames and Rings This type of deployable structure is the primary feature of
this document. The inflating structure in Figure 1.6 is technically a Frame, but
cannot be said to be folding. Folding frames have been a focus of the Advanced
Structures Laboratory at Cambridge for some time, and numerous versions have
been produced there. A folding frame or Ring is typically stowed with some or all
4
1.1 Deployable Structures
Figure 1.5: NASA’s Echo II Balloon (which was rigidized when inflated).
Figure 1.6: JPL’s inflatable SAR frame. The flexible patch array and the inflatable booms are
shown rolled up in the stowed state on the left.
bars parallel, and deployed to form a rigid supporting structure for a membrane.
Frames or rings are closed loops, and are linkages which may have any number
of kinematic degrees of freedom, although single degree of freedom closed loops
are of particular interest. Some linkages are mobile, not because they are mecha-
nisms in the true sense, but because they possess a Geometric Degree of Freedom
(Chen et al., 2004; Gan & Pellegrino, 2003; You, 2007). A subset of linkages with
a geometric degree of freedom are known as Overconstrained Mechanisms (Cui
& Dai, 2011; Mavroidis & Roth, 1994). An overconstrained mechanism has a de-
gree of freedom or a mobility which arises because of some quirk of symmetry,
or other special geometric property (see Section 3.2); it has a higher mobility than
5
1.2 Design Techniques
that predicted by the Chebychev-Gru¨bler-Kutzbach criterion. An example of the
deployment of such an overconstrained mechanism is given in Figure 1.7. De-
ployable frames have been proposed for use in space applications (Chen & You,
2006a,b) (in particular panel and antenna deployment (Pellegrino et al., 2000)).
Figure 1.7: A single degree of freedom, 6-bar foldable ring deploying, from Gan & Pellegrino
(2006).
The study of deployable structures spans a broad range of disciplines, and incorpo-
rates a variety of structures, however, the focus of this document is in the area of folding
rings and frames.
1.2 Design Techniques
Both mechanism simulation and design are addressed in the chapters which follow. This
section outlines some of the many techniques used to date to synthesise and design de-
ployable structures.
1.2.1 Standard Kinematic Synthesis Techniques
The design of mechanisms was originally an inherently creative task. Designers would
use a trial and error approach until a satisfactory linkage or mechanism was found. The
need for reliable linkages which could perform a prescribed function with some accuracy
increased with the onset of the industrial revolution. For some time the most sought after
linkage was a planar, straight-line linkage, which could be used to guide machinery along
6
1.2 Design Techniques
a linear path. James Watt developed a linkage (sometimes known as Watt’s linkage, or
the parallel linkage) in 1784, the central point of which traces out what is very nearly a
straight line over a limited range of motion. Watt used this linkage to constrain the motion
of his steam driven pistons, preventing them from binding with their cylinders. The Watt
linkage is still used today in the suspension of some cars. Other linkages capable of
approximating straight line motion soon appeared. Examples are the Chebyshev linkage,
the Hoekens linkage (which converts rotational motion into approximate straight-line
motion), and the Evans linkage (Bryant & Sangwin, 2008). In 1853, the Sarrus linkage
was invented. The Sarrus linkage is a spatial linkage which converts circular motion
(over a limited range) into linear motion. If manufactured very carefully, the top of
the linkage traces out a perfectly straight line. It was not until several years after the
invention of Watt’s linkage that the first planar perfect straight-line linkage appeared.
The Peaucellier-Lipkin linkage (Demaine & O’Rourke, 2007), was invented in 1864 (and
again in 1871 independently), essentially by accident. Hart’s linkage, another perfect
straight-line mechanism, was invented in 1875, and requires only five links, compared to
the Peaucellier-Lipkin’s seven.
Not all linkages are required to follow a straight line. Sometimes linkages which ap-
proximate a prescribed curve are required. Given some basic specifications about desired
mobility, it may be possible to methodically determine the types of mechanisms able to
perform the desired task (Freudenstein & Maki, 1979; Read & Wilson, 1998), but it is
almost always impossible to synthesise the exact geometry from any kind of recipe. This
said, very simple mechanisms can be designed in such a way that a point on the mecha-
nism, or a coupler link, can be made to closely follow a given algebraic curve. An atlas
of 4-bar linkages was given in Hrones & Nelson (1951), which allowed the designer to
manipulate an existing planar 4-bar design in such a way that it more closely followed a
desired curve.
In the 20th century, the procedure for kinematic synthesis became more formalised
(Hartenberg & Denavit, 1964). The three standard stages of mechanism design are type,
number and dimensional synthesis. In type synthesis, one identifies the mechanical
component best suited to producing the type of motion required. In number synthe-
sis, the number of degrees of freedom is determined. In dimensional synthesis, the exact
lengths/angles/sizes of the mechanism components are determined. Dimensional synthe-
sis forms the primary topic of this document.
Until fairly recently, accurate simulation of the motion of all but the most elementary
mechanisms was very difficult. The curves traced out by even the simplest linkages can
still be very complicated. The simulation and design of more complicated linkages has
7
1.2 Design Techniques
become possible only with the arrival of computer based numerical analysis and simula-
tion. Prior to that, linkage synthesis involved a combination of intuition, experimentation,
and luck.
1.2.2 Perfect Planar Mechanisms
Knowing that it is possible to construct linkages capable of tracing out a perfectly straight
line, one might also wonder if it is possible to design linkages capable of tracing out more
complicated, algebraic curves. Kempe’s Universality Theorem (Hopcroft et al., 1984;
Kempe, 1877) states that it is possible to construct a planar mechanism such that one of
the mechanism’s vertices traces out a specified parametric curve, no matter how high the
degree of the curve. The design of such mechanisms can even be automated (Gao et al.,
2001). Kempe’s Universality Theorem can also be generalised to higher dimensions
(Abbott & Barton, 2004). The linkages which are generated by such automated processes
tend towards impracticality, with even the most simple curves requiring a great number
of links. In general, the number of links required to trace an algebraic plane curve of
degree n is O(n4).
1.2.3 Optimisation
Optimisation techniques lend themselves to the task of refining an already established
solution concept, rather than top level design. In linkage design, that might mean that
the number of links, the types of joints, and the connectivity (the way in which the links
are connected to one another) have already been decided. An optimisation step could be
included to adjust the lengths of the links, the location of the linkage anchors or perhaps
the dimensions of the bars to be used, to more closely match the design constraints.
Essentially all optimisation techniques require the specification of an objective func-
tion, which is then maximised or minimised, subject to certain constraints. Some ex-
amples of features which one might include in an objective function when designing
linkages, with particular reference to deployable structures, are:
• proximity of a coupler link to a series of prescribed points (sometimes referred to as
Precision Points) at the position of greatest proximity throughout the range of the
linkage’s motion. This is known as point-path synthesis, and examples are given in
figures 1.8(a) and 1.8(b);
• maximum volume of space required during deployment;
8
1.2 Design Techniques
• maximum stretch in a membrane mounted to a folding frame during deployment;
• maximum velocity of certain joints during deployment;
• magnitude of the smallest singular value in a linkage during deployment (this might
be useful in designing a bifurcation-free mechanism).
Some of the most powerful optimisation methods require computation of the gradi-
ents of the objective function with respect to the various design variables. Examples of
numerical gradient-based methods are line searches, the Newton-Raphson method, and
non-linear least squares (Angeles et al., 1988). Sometimes, if enough care is taken, gra-
dients can be obtained analytically, making optimisation more precise (Sancibrian et al.,
2004). If gradients are not readily available, one might use a quasi-Newton method (Ge
et al., 1999), trust regions, pattern searches (Krishnamurty & Turcic (1992) uses a Hooke-
Jeeves approach to linkage design), or more exotic approaches such as an ant-gradient
search (Diab & Smaili, 2008), or a technique known as simulated annealing (Martı´nez-
Alfaro, 2007).
The optimisation methods mentioned above vary in the extent to which they rely on a
high quality start point in design variable space. The numerical gradient-based techniques
are perhaps the most sensitive to the choice of start point, but have the advantage of
performing very well when in proximity to a minimum or maximum of the objective
function. All optimisation methods require a point at which to begin the search for a local
minimum/maximum of the objective function, which complicates the task of a linkage
designer. In using optimisation, a designer will initially have to rely on his or her intuition
to find a feasible start point in design variable space close enough to the optimum design
to allow the optimiser to converge.
Figures 1.8(a) and 1.8(b) illustrate an example in which the dimensions of a 4-bar
planar mechanism are adjusted to match a set of precision points as closely as possible
(a collaborative optimisation architecture (Braun & Kroo, 1995) was used to generate the
examples shown).
1.2.4 Direct Solution of Closure/Compatibility Equations
A further approach to mechanism design involves first expressing a kinematic problem
as a series of Closure Equations or Compatibility Equations (which ensure the proper
formation and motion of the mechanism), as well as a collection of Constraint Equations
which specify something about the way in which the linkage should behave. The op-
timisation methods of Section 1.2.3 are typically used in situations in which there are
9
1.2 Design Techniques
(a) Initial 4-bar configuration showing vertex
locus.
(b) Final 4-bar configuration showing vertex
locus.
Figure 1.8: An example of the optimisation of a 4-bar planar linkage to closely match a set of
precision points. The lengths of the bars have been adjusted using an optimiser.
a greater number of constraints and design targets than design variables. The coupler
curve-fitting example of Figures 1.8(a) and 1.8(b) illustrates a situation in which there
are a great many more design targets (precision points) than there are design variables
(bar lengths). An optimiser will approximate the design targets within operational limits,
while obeying any constraints which have been specified. In trying to directly solve a
system of equations which specify a certain design problem, one generally aims to work
with a square system; that is, a system in which there are as many equations (constraints)
as variables. That is not to say that one need always deal with a strictly square system, as
under-determined systems can provide very interesting curves and manifolds in solution
space which reveal a lot about the nature of a problem.
More often than not (especially in kinematics) a square system of closure, compat-
ibility and constraint equations will have more than a single solution. In fact, a feature
which makes the direct solution of closure/compatibility equations such an attractive ap-
proach to mechanism or linkage design is that sometimes a number of different designs
will satisfy the same requirements. Using an ad hoc or optimisation method will most
likely only locate a single solution to a kinematic problem (if any is found at all).
An example of the way in which a design procedure might flow is given below:
1. select design requirements (such as choosing a number of precision points);
2. select an appropriate type of mechanism and set the number of links and their
connectivity;
3. determine which dimensions/angles are to be used as design variables;
4. construct a system of equations which describes the motion of the mechanism;
10
1.2 Design Techniques
5. solve these equations for the design variables.
The final step in the procedure above involves the solution of a set of non-linear equations
(general solution methods for these kinds of equations are covered in Hoffmann & Ver-
meer (1995); Nielsen (1997)). The approach described above does require an educated
guess about the type of mechanism required to perform the task, the number of links, and
the connectivity of the links (note, however, that Emiris & Moroz (2011) uses the direct
solution of non-linear compatibility equations to enumerate all possible connectivities for
a given linkage type, negating the need to pre-specify a connectivity).
Symbolic and Eigenvalue Techniques
A large number of non-linear equations which arise in kinematics can be converted to
polynomial form. Once a system of non-linear equations is in polynomial form, some
standard solution techniques can be applied. Such methods include the use of Gro¨bner
Bases to solve equations exactly, using substitution to reduce a system of polynomials
to a single equation (Lee & Liang, 1988) (which could then be solved as an eigenvalue
problem (Chtcherba & Kapur, 2004)), and Galois Theory (Owen, 1991).
Method of Resultants
One particularly powerful technique involves the use of resultants. A good background
on the use of resultants as they apply to kinematics is given in Nielsen (1997), while the
mathematics (resultants of the Sylvester type) are covered in Chtcherba & Kapur (2004)
and Sturmfels & Zelevinsky (1994). Applications of result based methods to kinemat-
ics and structural problems are given in Emiris (1994); Emiris & Mourrain (1996), and
more famously in Lee & Liang (1988). At their core, resultant techniques are formalised
strategies for performing elimination. Slightly different approaches exist for reducing
systems of multivariate polynomials, but all involve the construction of a matrix system
equivalent to the original polynomials, and the evaluation of a determinant which reduces
the number of variables involved. While very powerful in the treatment of small systems,
the method of resultants is difficult to formalise for all sizes and types of polynomial
systems, which leads to an insufficient degree of automation for a generally applicable
method.
Polynomial Continuation
Of key interest in this document is a method called Numerical Continuation, and in par-
ticular, Polynomial Continuation (Allgower & Georg, 2003; Zulehner, 1988). Continua-
11
1.2 Design Techniques
tion is a numerical technique in which the solutions of a system of polynomial equations
are found by way of a second, similar system of equations whose solutions are already
known. By incrementally transforming the system whose solutions are known into the
original ‘target’ system, the unknown solutions can be found. Numerical continuation
methods can be applied to a variety of equation families, but polynomials have certain
properties which allow for the simplification of the continuation procedure. In particu-
lar, it is possible to construct very tight bounds on the number of solutions which may
theoretically arise in a given set of equations. The solutions of a system of polynomial
equations with real coefficients are a mixture of solutions at infinity, complex conjugate
pairs and real solutions (Erdos & Grunwald, 1939). It is the real solutions which are
typically of greatest interest in linkage design (Luo & Dai, 2007; Wampler et al., 1990)
because they describe the physically realisable linkages. Note that there is no way of
predicting how many of the solutions of a system of polynomials will fall into each of
these categories (at infinity, complex or real) before the continuation process has been
completed. Polynomial continuation has been applied to a variety of kinematic problems
in the past (Soeseno, 1990; Verschelde, 2011), and constitutes the principal topic of in-
vestigation for a number of researchers. Typically, applications involve the solution of
inverse kinematics (Chablat & Angeles, 2003).
Some of the major examples of the use of polynomial continuation in the solving of
problems in kinematics are:
Computing camera motion from a sequence of images An inverse kinematics problem
explored in the Ph.D. thesis Emiris (1994).
Predicting molecule structure An exercise in “finding energetically favourable config-
urations”1 in which the shape of a molecule is determined mathematically (Emiris,
1994; Emiris & Mourrain, 1996).
Stewart platform kinematics Sometimes called a left hand problem, a Stewart platform
is a parallel manipulator in which a static base plate is attached to a mobile top plate
by six rods of variable length. The problem of finding the orientation and position
of the top plate, or the lengths of the rods as a function of the top plate’s orientation
and position is a classic problem in non-linear equation solving. Stewart platforms
have featured in a number of analyses based on continuation methods (Emiris,
1994; Raghavan & Roth, 1993; Sommese et al., 2002a).
Number of assembly modes of a linkage It is possible to enumerate all the possible
1from Emiris & Mourrain (1996)
12
1.2 Design Techniques
connectivities of a linkage, given a number of links and a number of nodes (Emiris
& Moroz, 2011).
Inverse kinematics of general 6R manipulators Another classic problem in inverse kine-
matics frequently adressed using continuation. A typical task is to establish all
possible linkage configurations given a manipulator end location and orientation
(Manocha & Canny, 1994; Raghavan & Roth, 1993; Wampler & Morgan, 1993).
Planar 4-bar point-path synthesis This was mentioned briefly in section 1.2.3 and will
be addressed in the form of an example below. 4-bar point-path synthesis was an
early ‘demonstrator’ problem in polynomial continuation which has been consid-
ered by a number of authors (Morgan & Wampler, 1990; Subbian, 1990; Subbian
& Flugrad, 1991; Wampler et al., 1992).
Spatial body-guidance problem Sometimes called a Burmester problem, the body-guidance
problem involves the use of inverse kinematics to design a linkage based on a se-
quence of pre-specified body locations and orientations (Sommese et al., 2002a;
Wampler et al., 1990).
For an example of polynomial continuation as applied to a problem in kinematics,
return now to the point-path synthesis for a planar 4-bar linkage. It is not specified that
the coupler link need follow a particular continuous curve, but only that it pass through
a collection of precision points at various stages in its range of motion. In Section 1.2.1
it was described how a curve approximating a desired path could be generated using an
atlas of 4-bar designs. In Section 1.2.2 it was stated that a linkage following a given alge-
braic curve could always be found, but that the linkage would most likely be intractably
complex. In Section 1.2.3, a precision point example involving a large number of preci-
sion points and a reasonably good start point in the design space was used to illustrate
linkage optimisation. In the current point-path synthesis it is required that the coupler
link of the 4-bar linkage to be designed must pass precisely through each of the precision
points. In order for this to be possible, a square system must be constructed; so only as
many precision points as there are design variables may be specified. Figures 1.9(a) to
1.9(c) show three different solutions arising from the specification of five precision points
(requiring the use of five independent design variables in the form of bar lengths). The
only pre-specifications for the linkage are that it must be a planar 4-bar, and that the cou-
pler link must be opposite the anchored link. Note that the order in which the precision
points are hit cannot be stipulated. The length and orientation of the anchored link are
also pre-specified in this example for simplicity.
13
1.2 Design Techniques
4-bar point-path synthesis is a classic application of continuation to the design of
mechanisms. The solutions shown are, in fact, not the only solutions to this particular set
of precision points, but they illustrate the way in which several different designs can sat-
isfy the same requirements. Interestingly, the number of solutions arising from the spec-
ification of any number of precision points in planar 4-bar mechanism design is always
a multiple of three; every mechanism appears together with its two Roberts’ cognates.
This example highlights the difference between an optimisation approach (Figures 1.8(a)
and 1.8(b)), and a direct solution approach. No start point (initial design) was required
to generate the solutions, and a designer using this technique will be presented with a
number of solutions to the specified problem, some of which he or she will possibly not
have conceived. Planar 4-bar design problems of this nature permit a maximum of nine
design variables (four bar lengths, two coupler side lengths, two translational parameters
and one rotation) for exact solution. This means that it is possible to solve exactly for
nine precision points (Wampler et al., 1992).
A more comprehensive introduction to polynomial continuation is given in Chapter
2.
14
1.2 Design Techniques
(a) 4-bar mechanism showing vertex
locus, Example 1.
(b) 4-bar mechanism showing vertex
locus, Example 2. Note that solution is
degenerate.
(c) 4-bar mechanism showing vertex locus, Example 3.
Figure 1.9: Examples of 4-bar linkages arising from the direct solution of their loop closure
equations. The same set of precision points produced all of the examples shown.
15
1.3 Chapter Summary
1.3 Chapter Summary
Chapter 2: Introduction to Polynomial Continuation A branch of numerical contin-
uation known as polynomial continuation has been applied to numerous problems
in kinematics and linkage design for over twenty years. Polynomial continuation
is a broadly applicable mathematical tool, however, the majority of the applica-
tions found in this and proceeding chapters will concern only the application of
polynomial continuation to linkage design problems.
This chapter provides a background in the basics of continuation, including: speci-
fication of homotopies; path-following and predictor-corrector methods; homogeni-
sation and Be´zout numbers, and the generation of multihomogeneous start systems;
Polyhedral Homotopy methods, including the calculation of mixed volumes, opti-
mising lifting values and the creation of minimum volume start systems; witness
sets and the reduction of systems of polynomials into their irreducible components.
At the end of the chapter, an illustrative example, in the form of a hinge design
problem, is presented.
Chapter 3: 6R Plane Symmetric Frames The plane symmetric 6R foldable frame is
identified as a case of the plane symmetric Bricard linkage in terms of Denavit-
Hartenberg Parameters; the nature of its single degree of freedom is examined in
detail by determining the exact structure of the system of equations governing its
movement; a range of design parameters for building feasible mechanisms is de-
termined numerically; and polynomial continuation is used to design frames with
certain specified desirable properties.
Chapter 4: Regular-Polygonal Foldable Rings A regular-polygonal deployable ring is
designed using polynomial continuation. When deployed, the ring forms a regular
polygon with an even number of sides, and when stowed, forms a close packed
bundle of parallel bars. The ring’s motion is characterised using a pair of compat-
ibility equations, and these equations are used to design rings whose deployment
occurs in a prescribed manner. Various combinations of design variables are used
to design the ring from different perspectives, illustrating the versatile way in which
continuation can be used to solve real linkage problems.
Chapter 5: Doubly Symmetric 8-Bar Foldable Rings This is, in some ways, a gener-
alisation of the design case in Chapter 4. The requirement for the deployed ring
to be a regular polygon is relaxed. Rings with a double plane symmetry when de-
ployed are required, for volume minimisation purposes, to fold up into a bundle
16
1.3 Chapter Summary
when stowed. Rather than a pair of compatibility equations, a matrix equation,
based on a transfer matrix closure equation approach, is used to design rings which
satisfy certain design specifications. In a further departure from Chapter 4, the ma-
jority of these specifications take the form of a precisely regulated stowed shape,
rather than a particular deployment path.
Chapter 6: Mobility of N-Loops Chapter 3 includes an example of how Witness Sets
can be used to understand the structure of the closure or compatibility equations
defining the kinematics of a linkage. In this chapter, an extended example of a
similar nature is given, with a greater emphasis on the implications of the structure
of the equations for the mobility of the linkage.
N-loops, made up of closed loops of 90◦ arc shaped links are studied, with par-
ticular reference to the 6, 7 and 8-link variants. The 6-link variant was found to
have the most interesting closure equation structure, with direct implications for
the linkage’s mobility. The degree of the irreducible components governing the
mobility of the 7 and 8-link variants were determined.
17
2. Polynomial Continuation
Polynomial continuation is used extensively throughout this thesis. A handful of soft-
ware packages are available for research purposes; most notably PHCpack (Guan & Ver-
schelde, 2008; Verschelde, 1999), HOM4PS-2.0 (Lee et al., 2008) and HOMPACK (Wat-
son et al., 1987). For maximum versatility, all software used in this thesis was written
entirely by the author in Matlab, using a variety of literature sources as the basis of the
underlying algorithm.
2.1 Polynomial Continuation Basics
A branch of Numerical Continuation known as Polynomial Continuation has been ap-
plied to various problems in linkage design over a period of more than two decades.
Polynomial continuation is a method of finding the roots of a system of polynomials.
2.1.1 The Degree of a System of Polynomial Equations
Just as a polynomial equation has a degree, so too does a system of polynomials. Equation
2.1 is a 4th degree polynomial in x, y and z. The degree, or order, of the whole equation
is determined by the term in the equation which has the highest degree.
x2yz + 2y2 − 5z = 0 (2.1)
The system of Equation 2.2 has degree 8, which is simply the product of the degrees of
the constituent equations. According to the fundamental theorem of algebra, Equation
2.2 has at most eight solutions.
x2yz + 2y2 − 5z = 0
3xy + z − 2 = 0
2x− y + z = 0
(2.2)
18
2.1 Polynomial Continuation Basics
Methods to solve systems like 2.2 symbolically are available. Software packages such
as Matlab, Maple and Mathematica can be used to solve simple systems exactly, but
these packages falter when the degree of a system becomes too large. In addition, not
all systems of polynomials can be solved symbolically, as discussed in Section 2.2 of
Lamure & Michelucci (1996).
2.1.2 Types of Solutions of Polynomial Equations
There are a number of ways to classify the types of solutions which arise in polynomial
systems. Firstly, a solution may be contained within the finite plane, or it may be a
Solution at Infinity. Within this, solutions may be further categorised as:
• Geometrically Isolated;
• Positive Dimensional (continuous solution set which arises when a solution is not
geometrically isolated, could be overlapping lines etc.);
• non-singular (determinate of Jacobian of system = 0).
Note that being non-singular implies a solution is geometrically isolated, but being ge-
ometrically isolated does not imply non-singular. A graphical representation of this is
given in Figure 2.1. (in computational analysis, Singular Solutions present greater numer-
Space of Singular SolutionsSpace of Non-Singular
Solutions
Positive-
Dimensional
Solutions
Geometically isolated
Solutions
Figure 2.1: Polynomial solution/root types.
19
2.1 Polynomial Continuation Basics
ical difficulties than non-singular, and end games, which deal specifically with singular
solutions, have become an area of study unto themselves (Leykin et al., 2000)).
Some simple examples of polynomial systems, each of which illustrates one of the
solution types mentioned above, have been placed in Table 2.1. Each system has degree
2. In the first example, the line and the parabola clearly intersect at two geometrically iso-
lated locations. Both solutions are non-singular. The second example illustrates a single
(geometrically isolated, non-singular) solution in the finite plane. The second solution is
said to be at infinity. The third example illustrates a geometrically isolated, but singular
solution. It is said to be a solution with a multiplicity of 2. No examples of Positive
Dimensional solution sets have been given, but one could be created by multiplying any
of the second equations in Table 2.1 by a factor of x2− y: a second overlapping parabola
with a continuum of solutions along its entire length would be introduced. More will be
said about positive dimensional solution sets later in the chapter.
To understand better what is meant by a solution at infinity, consider the following
system:
f(x, y) =
x2 + y2 − 7
x2 + y2 − 14y + 30
=
0
0
(2.3)
Next, consider what happens when x → X/p and y → Y/p, and all denominators are
cleared:
f(X, Y, p) =
X2 + Y 2 − 7p2
X2 + Y 2 − 14Y p+ 30p2
=
0
0
and send p → 0. What is left is called the Homogenised version of f , sometimes abbre-
viated as f 0.
f 0(X, Y ) =
X2 + Y 2
X2 + Y 2
=
0
0
The solutions of f 0 are called the ‘solutions at infinity.’ Note that any scalar multiple
of the solutions at infinity will also be a solution to f 0. Conventionally, one searches for
solutions of the form {1, Y } or {0, Y }. In this case, the solutions at infinity are at {1,±i}.
The additional two solutions to this 4th degree problem are at {±0.1237, 2.6429}.
Not all systems have solutions at infinity, sometimes despite first appearances. Con-
sider:
f(x, y) =
3xy − 2x2 + 2y − 7
x2 + y2 − 4x+ 2
=
0
0
with
f 0(X, Y ) =
3XY − 2X2
X2 + Y 2
=
0
0
20
2.1 Polynomial Continuation Basics
1)
x2 − y = 0
y − 1 = 0
Two non-singular
solutions in the finite
plane.
2)
x2 − y = 0
x− 1 = 0
One solution at ∞.
One non-singular in
finite plane.
3)
x2 − y = 0
y = 0
One singular solu-
tion in finite plane with
multiplicity 2.
Table 2.1: Simple polynomial systems.
21
2.1 Polynomial Continuation Basics
which has only the four finite solutions {−0.7001 ± 0.8908i,−1.0218 ∓ 2.3539i} and
{1.6232± 0.8837i, 1.6372± 0.2039i}.
2.1.3 The ‘Circle’ Problem
The examples discussed above can easily be solved algebraically. To describe how con-
tinuation works, consider the following motivational problem: find the equation of a
circle which passes through three prescribed points. This centuries old problem can be
solved geometrically, algebraically (somewhat laborious) or via numerical optimisation
if a reasonable initial guess is available. The general form of the equation describing a
circle is given by 2.4.
(x− a)2 + (y − b)2 = r2 (2.4)
This is depicted in Figure 2.2. Once the three points pj , have been specified, the problem
p1
p3
p2
(a,b)
r
Figure 2.2: Problem description: circle.
can be written as in Equation 2.5.
f(a, b, r) =
(p1x − a)2 + (p1y − b)2 − r2
(p2x − a)2 + (p2y − b)2 − r2
(p3x − a)2 + (p3y − b)2 − r2
= 0 (2.5)
22
2.1 Polynomial Continuation Basics
This is a degree-8 system. For now, rather than trying to solve the equations directly,
consider instead the system given in Equation 2.6.
g(a, b, r) =
a2 − 1
b2 − 1
r2 − (a+ 3b)
= 0 (2.6)
This is also a degree-8 system in the same variables. g has no physical significance,
and was chosen only for its simple solution structure. The solutions to Equation 2.6 can
immediately be read off, and are placed in the columns of: ab
r
=
1 1 1 1 −1 −1 −1 −11 −1 1 −1 1 −1 1 −1
2 i
√
2 −2 −i√2 √2 i2 −√2 −i2
(2.7)
Let g(a, b, r) be known as the Start System, and f(a, b, r) as the Target System. It is
possible to use knowledge of the solution structure of one system of polynomial equations
to determine the solutions of another. A new function, known as a Homotopy (Zulehner,
1988) is defined. A homotopy is given in its simplest form in Equation 2.8.
h(a, b, r) = (1− t)g(a, b, r) + tf(a, b, r) (2.8)
As the Homotopy Parameter t is incrementally varied from 0 to 1, h transforms slowly
from g into f . Starting at t = 0 with the known solutions of g, h is solved numerically
for a, b and r at intervals between t = 0 and t = 1. At present, there are two main
approaches taken to the tracking of solutions from t = 0 to t = 1 via Equation 2.8.
The first of these is known as the Predictor-Corrector method, and the second as the
Simplicial method (Allgower & Georg, 1980). Only the predictor-corrector method will
be discussed here in detail. Coding methods for the predictor-corrector approach are well
documented (Morgan, 1987; Wampler et al., 1990). Note also that continuation methods
can involve more than a single continuation parameter (Henderson, 2004), although only
the single case is considered here.
As a practical example, assume that the intention is to solve Equation 2.5 with the
(rather uninteresting) points p1 = {−1, 1}, p2 = {1, 1} and p3 = {1,−1}, which define
three corners of a square. Commonsense suggests that the solution will be a circle of
radius
√
2 centred at the origin. Running a continuation script (using Equation 2.6 as the
23
2.2 Predictor-Corrector Method (Path Following)
start system and 2.7 as the start solutions) yields the following results: ab
r
=
∞ ∞ ∞ ∞ ∞ 0 ∞ 0∞ ∞ ∞ ∞ ∞ 0 ∞ 0
∞ ∞ ∞ ∞ ∞ √2 ∞ −√2
The problem is seen to have six solutions at infinity. The remaining two are both finite,
geometrically isolated non-singular solutions. Only one is physically realisable, with a
negative radius being meaningless. In the continuation process, six of the paths from the
finite start solutions have diverged to infinity, while two have tracked to finite, geometri-
cally isolated points.
Polynomial continuation presents itself as an appealing tool in kinematics because it
finds not just one, but all of the solutions to a given system (whether they are physically
realisable or not). Numerical methods, such as the Newton Raphson Method are reliable,
but only when the starting estimate lies within an attraction region of a desirable solution.
2.2 Predictor-Corrector Method (Path Following)
Once the f(x) (target) and g(x) (start) systems (which combine to give h(x, t)) have
been constructed, small increments can be made in the arguments of h to produce:
h(x+∆x, t+∆t) = h(x, t) + Jx∆x+ Jt∆t+ · · ·
where Jx and Jt are the Jacobians of h with respect to x and t respectively. Since it is
assumed that h equates to zero at all points between t = 0 and t = 1, the above can be
solved as in Equation 2.9, which is known as the predictor step.
∆x = −J−1x Jt∆t (2.9)
If t undergoes an incremental increase, the solutions to h can be refined by repetitively
applying Equation 2.10, which is known as the corrector step.
∆x = −J−1x h(x, t) (2.10)
A graphical representation of this approach is given in Figure 2.3.
Both the predictor and corrector steps described above can be improved: the total
length of the predictor step can be controlled, and the corrector step can be forced to be
24
2.2 Predictor-Corrector Method (Path Following)
x
t
t = 0
g(x)
t = 1
f(x)
Predict
Correct
Figure 2.3: Standard path tracking.
perpendicular to the predictor step. Firstly, construct a new vector z =
xT t
T . From
before:
dx
dt
= −J−1x Jt
The z vector is updated during the path-following process using Equation 2.11:
z1 = z0 +
dx
dt 1
dxdt 1 · step (2.11)
where the size of the step can be varied. Once the predictor step has been performed,
the correction can then be forced to occur along a line perpendicular to the predictor
vector; the idea being that the distance to the path should be shorter in the majority of
cases. The corrector step is made by repeatedly solving Equation 2.12, which ensures the
orthogonality of the predictor and subsequent corrector steps.
Jx Jt
(z0 − z1)T
[zk+1 − zk] = −
h(z, t)
0
(2.12)
A representation of the tangential prediction/orthogonal correction method is given in
25
2.2 Predictor-Corrector Method (Path Following)
Figure 2.4.
Predict
Correct
x
t
t = 0
g(x)
t = 1
f(x)
Figure 2.4: Tangential path tracking.
In practice, a correction process using a fixed value of t is usually sufficient. The
method used to generate the results contained in this document is a combination of a
predictor step based on Equation 2.11, and a corrector step based on Equation 2.10.
2.2.1 Step Size Control
How far to progress along the solution path with the next prediction is a key issue in
efficient programming. If the step size is too small then each path will take too long to
trace. If the step size is too big, then the corrector may fail to re-converge to the path.
The method employed to control the step size is as follows:
1. provide an initial step size;
2. if the correction term after a certain number of iterations is small enough, then
count the step as a success;
3. if a certain number of consecutive successful steps have been taken, increase the
step size;
4. if the last step was considered a failure, decrease the step size;
26
2.2 Predictor-Corrector Method (Path Following)
5. ensure that the step size lies within the upper and lower allowable universal bounds.
The choice of the initial step size is very important, and dictates how likely the path
follower is to experience a failure at the start.
2.2.2 Path Follower Control Parameters
The path following process as implemented in the Matlab code used throughout this
document can be represented as a flow chart, included as Figure 2.5. The flow chart
illustrates a number of step size controls used in path following, most of which were
synthesised from other authors’ publications on the topic. The combination of step size
controls constitutes a unique path following algorithm, suited to the types of polynomials
which arise in the study of the kinematics of deployable structures.
A number of numerical parameters can be used to define the way in which the predictor-
corrector path follower of Figure 2.5 operates. These scalars can be used to manipulate
the trade-off between accuracy and speed in computation. A list of the parameters and
their functions is provided.
Initial step size User defined figure (usually 10−4) which sets the magnitude of the first
predictor step in the process. Too big a step could result in a path jump (failed
re-convergence) before the iteration process has even begun.
Maximum number of steps Simply sets an upper limit on the number of prediction
steps before a path following process is considered to have failed.
Minimum step size A lower limit on allowed step size. Often encountered when at-
tempting to follow solutions to infinity. Should typically be greater than machine
precision.
Maximum step size Step size is allowed to grow to a maximum of this magnitude. This
limit is typically reached in the mid stages of path following t = 0.2− 0.8, and to
a large extent dictates the speed of the overall process. Path jumps can easily occur
if this number is set too large.
Minimum successful iterations This parameter sets the number of prediction-correction
steps which must occur without incident before the step size can be increased with
confidence. It is typically in the range 4 to 6.
Allowable predictor vector direction change This parameter constitutes one of the main
defences against path jumps. It sets the minimum allowable inner product between
27
2.2 Predictor-Corrector Method (Path Following)
Select a start solution
Set t = 0 and choose
a step size
Have there
been N successful
steps?
Double
step
size
Compute predictor step ƚ zƚ xƚ t
Halve
step
size
No
Yes
Is this the
first iteration?
Update:
xxŸƚ x
ttŸƚ t
Store
wƚ z
Fix t and run
corrector step
Quit
(Failure)
Max steps
exceeded or
min step size
reached?
Was correction
sufficient and within
bounds?
Has t over-
stepped t = 1?
Is ǻt too small?
Isǻz sufficiently
similar to w?
Has t over-
stepped too many
times?
Yes
Yes
No Yes
No
No
YesNo
NoYes
YesNo
Quit
(Success)
Yes No
Figure 2.5: Flowchart describing the predictor-corrector method used in path following.
28
2.2 Predictor-Corrector Method (Path Following)
the current predictor vector and the previous one. Simply, each step in the path
following process must roughly be in the same direction as the last. A big change
in predictor direction is often a good indication that a path jump has occurred. The
value is typically between 0.95 and 0.99. Regions of paths with high curvature will
cause the step size to decrease, allowing the curve to be traced more accurately.
Minimum convergence requirement The set value for the magnitude of the corrector
step at which the convergence loop is terminated.
Minimum function magnitude The value of the 2-norm of the homotopy output re-
quired after the corrector step before a new corrector step is allowed. It is usually
around 10−6. This criterion is often the first to catch solutions on their way to
infinity.
Continuation parameter overstep allowance This integer specifies the number of times
t should exceed 1 before a target system solution is declared to have been found.
Each time t does exceed 1, the path follower returns to the previous point on the
path found between 0 and 1 and the step size is halved. In this way the path follower
converges slowly on t = 1. A value of 10 is usually sufficient for this parameter.
Allowable convergence stretch The correction phase should not shift the solution by a
distance significantly greater than the magnitude of the step size for the predictor
stage. If it does, then it is very likely that a path jump has occurred. This parameter
is applied as a multiplication factor of the current step size, and if the corrector
step shifts the solution by more than this amount then the entire predictor-corrector
iteration is considered to be a failure. A value of 2 is usually effective.
Minimum t component As a path begins to diverge to infinity, the amount by which
the continuation parameter (t) increases with each iteration becomes a smaller and
smaller fraction of the amount by which the solution variables themselves increase.
This parameter sets the minimum allowable size of this fraction, usually around
10−6 to 10−5.
Multi-precision flag Simply a 0 or 1 which specifies whether the program should be
enabled to make use of multiple precision capabilities in undertaking particularly
troublesome convergence loops. For almost all purposes, standard machine preci-
sion is sufficient, and the flag is set to 0 (off).
Output type flag Another flag with value 0 or 1. A 1 (on) requests that the path follower
29
2.3 Homogenisation and Be´zout Numbers
return every point encountered on the path in the form of a matrix. Can be very
heavy on memory usage.
2.3 Homogenisation and Be´zout Numbers
A simple example of homogenisation has already been seen in the discussion of solutions
at infinity above. In homogenising a system of equations the hope is that some, or all,
of the solutions at infinity can be removed. Homogenising a system of equations can
remove solutions at infinity, reducing the number of paths unnecessarily tracked, but it
does result in the introduction of new homogeneous variables (denoted as p previously).
The addition of the new homogeneous variables also requires the addition of some new
equations if the system as a whole is to be kept square.
The Be´zout Number (Wampler et al., 1990) of a system of polynomial equations can
loosely be described as the number of solutions left to be found following homogenisation
(after some solutions at infinity have been removed). Each type of solution has its own
associated Be´zout number. Non-singular, geometrically isolated solutions have a Be´zout
number of 1, but singular solutions may have higher Be´zout numbers, which correspond
to the multiplicity of the solution at that point. Summing the Be´zout numbers for all the
solutions to be found in a particular system gives the total Be´zout number for the system.
Prior to the development of polyhedral methods, n-homogenisation was used extensively
in the study of kinematic equations (Dhingra et al., 1994).
Consider again the system of three equations given in Equation 2.2. As a system
with degree 8, it is expected that eight solutions will be present, counting those which
may be at infinity and multiplicities. As an alternative to homogenising the system in
the way outlined previously (known as 1-homogenising), the variables can be placed into
homogeneous groups, and the system n-homogenised. Consider forming two homoge-
neous groups from the set {x, y, z}: {x} and {y, z}. Let k be the number of variables
in each group, so in this case: k1 = 1 and k2 = 2. With each homogeneous group is
associated a new homogeneous variable, say p and q respectively for this example. In the
original equations, set x → X/p and y → Y/q, z → Z/q. Either p or q independently
going to zero is enough to define a solution at infinity. What becomes of interest now,
is not the degree of the original equations in all the variables, but rather in each group.
The 2-homogenisation described here has the homogeneous structure given in Table 2.2.
The Be´zout Number for the 2-homogenised system is slightly more difficult to calculate.
Mathematically, it is the coefficient of the term
m
j=1 α
kj
j in Equation 2.13 (see Wampler
30
2.3 Homogenisation and Be´zout Numbers
Degree Group 1 Group 2
Equation 1 2 2
Equation 2 1 1
Equation 3 1 1
Table 2.2: Homogeneous structure of Equation 2.2.
et al. (1990)):
n
l=1
m
j=1
djlαj
(2.13)
where n is the number of equations, m is the number of groups and djl is the degree
of the lth equation with respect to the jth group. The variable α is a ‘place-holder’
for the original terms of the equations. In this example, the coefficient is 6, which is
marginally smaller than the original system’s 8. The benefit of n-homogenisation is that it
can exclude many solutions at infinity from the outset, reducing the number of paths to be
followed. Often the number of paths to be followed can be halved or more, depending on
the homogeneous grouping used. Here, the modest reduction from eight to six solutions
still affords some computational benefit. Once the 2-homogenisation has been performed,
and a multi-homogeneous start system with six solutions constructed, six paths can be
found to trace to the solutions of Equation 2.2: xy
z
=
−3.1164 2.5444 0.3002 −0.6143 −0.1140 ∞0.5070 0.8211 1.3682 −0.9152 2.6927 ∞
6.7398 −4.2678 0.7677 0.3134 2.9206 ∞
To confirm that there are in fact five finite solutions, note that (one of the ways in which)
Equation 2.2 can be written following elimination is:
57y5 − 255y4 + 260y3 + 120y2 − 256y + 80 = 0
which clearly has five solutions. The solutions of this Univariate polynomial can be found
as the eigenvalues of the companion matrix (Sommese & Wampler, 2005):
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
−8057 25657 −12057 −26057 25557
31
2.3 Homogenisation and Be´zout Numbers
which match those solutions found using continuation.
Homogenisation introduces an extra computational complication in the form of addi-
tional equations to account for the homogeneous variables. An equation of the form:
cj0yj0 + . . .+ cjkjyjkj − 1 = 0 (j = 1 : m) (2.14)
(where y are the elements of the particular group and c are complex coefficients chosen
at random (Wampler et al., 1990)) introduced for each homogeneous group works well.
It is then possible to solve for the homogeneous variables for each group at the end of the
calculations. A homogeneous variable of value zero corresponds to a solution at infinity.
Recall the example of Equation 2.3, in which two solutions at infinity were discovered at
(1,±i). A tracking of the four start points of the 1-homogenised version of 2.3 leads to
four finite solutions, of which two would have homogeneous variables equal to zero, and
would also be a scalar multiple of (1,±i).
2.3.1 Multi-Homogeneous Start Systems
To effectively implement the Polynomial Continuation method, it is necessary to be able
to automate the generation of appropriate start systems. The homogeneous structure of
a start system must be the same as that of the target system, and it must have the same
number of solutions.
Return once more to the simple polynomial system of Equation 2.2, which has the
homogeneous structure given in Table 2.2. A general start system can be constructed
which consists of linear factors only, making solution straightforward. The example at
hand would have a start system of the form given in Equation 2.15.
g(x, y, z) =
(x− α1)(x− α2)(y + τ1z − β1)(y + τ2z − β2)
(x− α3)(y + τ3z − β3)
(x− α4)(y + τ4z − β4)
= 0 (2.15)
The coefficients α, τ and β are chosen at random. The more uncorrelated the coefficients,
the better. The Be´zout Number for a system with this homogeneous structure is known
to be six, so there must be six finite solutions to this start system. It is easy to find the
roots of an equation corresponding to variables which alone constitute a particular group
(group of size one). In the notation used in Equation 2.15 they are simply α1,α2, . . ..
To find the roots corresponding to the members of a group containing k > 1 members,
k equations are required. In this case, group 2 has two members, so to find x, y pairs
32
2.3 Homogenisation and Be´zout Numbers
requires a 2×2 matrix inversion. Explicitly, the solutions to 2.15 are: xy
z
=
α1
1 τ3
1 τ4
−1
β3
β4
xy
z
=
α3
1 τ1
1 τ4
−1
β1
β4
xy
z
=
α4
1 τ1
1 τ3
−1
β1
β3
xy
z
=
α2
1 τ3
1 τ4
−1
β3
β4
xy
z
=
α3
1 τ2
1 τ4
−1
β2
β4
xy
z
=
α4
1 τ2
1 τ3
−1
β2
β3
These solutions are all unique.
Before solutions can be found, it is necessary to construct a ‘Solution Map’ (method
synthesized by the author), which describes which equations are to be used to calculate
the value of a particular variable. The solution map for the case above is given in Table
2.3. If the degree of a particular equation with respect to a homogeneous group is greater
Solution Num: 1 2 3 4 5 6
x Equation 1 2 3 1 2 3
Multiplicity 1 1 1 2 1 1
y Equation 2 1 1 2 1 1
Multiplicity 1 1 1 1 2 2
z Equation 3 3 2 3 3 2
Multiplicity 1 1 1 1 1 1
Table 2.3: Solution map for a degree-8 system of equations (Equation 2.15).
than one, then the corresponding equation in the start system will contain more than one
factor consisting of the elements of that group. Looking at Table 2.2, it can be seen that
Equation 2.2 has degree two in both group 1 and group 2. ‘Multiplicity’ in Table 2.3 refers
to the particular occurrence of a group within the start system equation. Since groups 1
and 2 each appear in two factors in the first equation of the start system in Equation 2.15,
equation 1 can be accompanied by multiplicities of 1 and 2.
2.3.2 The Homotopy
While the definition of a homotopy given in Equation 2.8 is sufficient for most applica-
tions, it is not necessarily as numerically stable as some others which could be used. Take
33
2.4 Polyhedral Homotopy Method
for example, the case that f = −g, for which the value t = 1/2 yields nothing at all. In
practice, a homotopy of the form given in Equation 2.16 is used for most applications.
h(a, b, r) = exp (iθ)(1− t)g(a, b, r) + tf(a, b, r) (2.16)
Here, θ is a randomly chosen number. This reduces the probability of numerical difficul-
ties arising in the homotopy effectively to zero.
If the only difference between the systems g and f is the value of the (complex)
coefficients of the Monomials, a simple and very efficient form of continuation known
as Coefficient-Parameter Continuation (Morgan & Sommese, 1989) can be used to map
from one system to the other.
2.4 Polyhedral Homotopy Method
There are several ways of constructing start systems and homotopies, each with their own
advantages and disadvantages. One’s goal should always be to decrease the number of
solution paths to be followed by pre-identifying and eliminating those which will diverge
towards infinity. Often, the most efficient methods for small systems are not particularly
generalisable, and the complexity of the start system and its construction outweighs the
benefits to be gained by a reduction in path count for larger systems.
Ideally, one would construct a start system with a monomial structure as similar as
possible to that of the target system. A start system constructed using linear terms via
n-homogenisation will usually closely approximate the target structure, but almost in-
variably contains extra terms. An outline is provided in this section of a method which
has been in development since the mid 1990’s, and which arguably constitutes the best
generalisable system for constructing start systems and homotopies. The exact method
presented here is adapted from one contained in the article Li (1999), and described later
in more detail in Li (2003). The reader is referred to these sources for more information.
In Bernstein (1975), it was shown than an upper bound for the number of roots of
a system of Laurent polynomials (note that the indices do not need to be ≥ 0 for this
to work) is provided by computing something known as the Mixed Volume. The mixed
volume refers to a special way of combining the Convex Polytopes of the Supports of
each equation. Support refers to the set of indices which appear in a given polynomial.
For example, in:
P (x1, x2, x3) = 3x
2
1x2x
3
3 + 1.4x2x
2
3 − 6x31 + 4.3x22 + 1.2x2 − 3.2x3 + 7
34
2.4 Polyhedral Homotopy Method
in the variables {x1, x2, x3}, the support is:
Supp =
2
1
3
,
0
1
2
,
3
0
0
,
0
2
0
,
0
1
0
,
0
0
1
,
0
0
0
Notice that so far the coefficients of the equation have not featured. Imagine now that each
element of the support defines a point in n dimensional space, where n is the dimension
of the solution vectors, so each equation’s support defines a collection of points. To make
use of the results of Bernstein (1975) (often simply referred to as Bernstein’s Theorem),
one need only consider the convex hull of the collection of points formed by each support.
Returning to the example above, the convex hull is:
conv(Supp) = Q =
2
1
3
,
0
1
2
,
3
0
0
,
0
2
0
,
0
0
1
,
0
0
0
which defines a convex polytope. Two or more polytopes can be combined using a
Minkowski Sum, defined in Equation 2.17 (see Sommese & Wampler (2005), p139 and
Konaxis (2010), p18).
Q1 +Q2 = {q1 + q2 | q1 ∈ Q1, q2 ∈ Q2} (2.17)
Next, the definition of volume used here is simply that which follows geometrically.
vol(Q) =
1
n!
det [a1 − a0, . . . , an − a0] (2.18)
Here, Q is a simplex with n+1 vertices, labelled a0, . . . , an. The mixed volume (Lee &
Li, 2007) of a system of polytopes is defined in Equation 2.19 (where Cni represents the
combinations of n things taken i at a time).
M(Q1, . . . , Qn) = coeff (λ1 . . .λn, vol(λ1Q1 + . . .+ λnQn))
=
n
i=1
(−1)n−ivol
j∈Cni
Qj
(2.19)
Bernstein’s theorem states that the root count of a polynomial system with supports
Supp1, . . . , Suppn on (C)
n \0 is equal to the mixed volume of its supports as defined
in Equation 2.19.
35
2.4 Polyhedral Homotopy Method
To get a better handle on the concept of a mixed volume, consider the polynomial
system given in Equation 2.20.
p1 = ax
3y + bxy2 + cy + 1 = 0
p2 = dxy
3 + ex+ 1 = 0
(2.20)
Here we have:
Q1 =
3
1
,
1
2
,
0
1
,
0
0
Q2 =
1
3
,
1
0
,
0
0
Q1 +Q2 =
4
4
,
4
1
,
2
5
,
1
4
,
0
1
,
1
0
,
0
0
A graphical representation of the situation is given in Figure 2.6. Directly applying Equa-
3
2
1
0 1 2 3 4
4
3
2
1
0 1 2 3
Q1
4
3
2
1
0 1 2 3 4
5
Q2 Q1+Q2
Figure 2.6: Graphical representation of mixed volume of equation 2.20.
tion 2.19 shows that this system has a mixed volume of 10. Note at this point that the
Be´zout number for this system is 16, while the 2-homogeneous Be´zout number is 11.
Already it can be seen that a polyhedral homotopy will produce the smallest number of
paths to be followed. Looking at the graphical representation of Q1 + Q2, it is possible
to see two greyed areas, each sharing a single edge with each of Q1 and Q2. These areas
are known as mixed cells, mixed subdivisions or n-subfaces. Their areas (or volumes in
higher dimensions) can be combined to give the mixed volume. In this case, the smaller
36
2.4 Polyhedral Homotopy Method
area has an area of 1, and the larger, 9, which combine to 10. Each of these mixed cells
is said to generate a number of start solutions equal to its volume. In most cases, the way
in which the polyhedra may be arranged in order to produce mixed cells is not unique,
although the mixed volume will not vary. When a valid subdivision is being sought com-
putationally, a technique to ensure that one is found is to actually introduce a n + 1th
dimension to the problem. This process is referred to as lifting, and the exact manner
in which it is applied has been the subject of quite some research in its own right. Par-
ticularly efficient methods of generating a lifting are available if the polynomials being
investigated are symmetric (Verschelde & Gatermann, 1995), but only the general lifting
case will be presented below (symmetric polynomials do not frequently arise in the types
of kinematic systems considered here). Briefly: the process involves taking each vertex
of each Qi, aij say, and using it as the argument of a random (real valued) Lifting Func-
tion, unique to each support. Denoting these random functions as ωi for i = 1, . . . , n,
then each support is lifted by one dimension such that:
Q¯i =
conv(a¯ij) | a¯ij =
aij
ωi(aij)
i = 1, . . . , n
aij ∈ Qi
(2.21)
Each Q¯i can be used to form the Minkowski sum Q¯i + . . . + Q¯n, which itself defines a
convex polytope. The edges of the lower hull of this new polytope can be projected onto
the original n dimensions, forming a valid subdivision, from which the mixed cells can
be identified.
As a further example, consider once more the system of Equation 2.2. Recall that this
system has a total degree (or 1-homogeneous Be´zout number) of 8, and a 2-homogeneous
Be´zout number of 6, with a 2-homogeneous start system tracking to the five finite solu-
tions of the target system, and one at infinity. As it happens, Equation 2.2 has a mixed
volume of 5, illustrating the way in which polyhedral methods can narrow down the
number of start solutions to the absolute upper bound.
The theorem of Bernstein (1975) was applied directly to the solution of polynomial
systems via continuation in Huber & Sturmfels (1995). There are several methods avail-
able to construct polyhedral homotopies. At the core of each method is a search for a valid
subdivision which can be used to identify the mixed cells. The most intuitive method is
simply to take every single combination of polyhedra edges, and test each one for valid-
ity. This is very reliable, and works for small systems, but quickly becomes impractical
in systems of dimension greater than 3 or 4, or with equations with a great many terms.
An outline of the method given in Li (1999) and Li (2003) is given below. First,
use a contracted notation in which xa = xa11 x
a2
2 . . . x
an
n . Each polynomial can then be
37
2.4 Polyhedral Homotopy Method
represented as:
pi(x) =
aij∈Qi
cijx
aij i = 1, . . . , n (2.22)
To increase numerical reliability, it is usually better to solve for the solutions of a system
with the same support structure, but with random complex coefficients first, and then
perform a Coefficient Homotopy from this system to the original target. In light of this,
let us deal instead with:
pi(x) =
aij∈Qi
cijx
aij i = 1, . . . , n (2.23)
where cij are random complex coefficients. Next, introduce the continuation parameter,
t, by multiplying each term by tωi(aij). Notice that at t = 1, hi(x)|t=1 = pi(x).
hi(x) =
aij∈Qi
cijx
aij tωi(aij) (2.24)
Now, a change of variable is performed, and in the process an unknown set of real num-
bers α = (α1, . . . ,αn) is introduced. Set:
xi = yit
αi i = 1, . . . , n
which transforms Equation 2.24 into:
hi(y) =
aij∈Qi
cijy
aij taij ,α+ωi(aij) (2.25)
Finally, the continuation parameter is altered once more by introducing a further un-
known, the real scalar βi. Each equation is multiplied through by t−βi .
h∗i (y) =
aij∈Qi
cijy
aij taij ,α+ωi(aij)−βi (2.26)
The unknown βi must be chosen to satisfy a very special set of criteria. In particular, if
each Qi has mi elements, and j = 1, . . . ,mi, then from each Qi, it can be shown that
there must exist a pair of elements {ai, ai } such that:
ai,α+ ωi(ai) = ai ,α+ ωi(ai ) = βi
ai,α+ ωi(ai) ≤ aij,α+ ωi(aij) ∀aij ∈ Qi\ {ai, ai }
(2.27)
38
2.4 Polyhedral Homotopy Method
Using the criteria of 2.27, Equation 2.26 can be rewritten as in Equation 2.28, which
represents the final form of the polyhedral homotopy.
h∗i (y) =
aij∈{ai,ai }
cijy
aij +
aij∈Qi\{ai,ai }
cijy
aij taij ,α+ωi(aij)−βi (2.28)
It is most probable that more than one set of {α, βi} unknowns will be found which
satisfy the constraints of Equation 2.27. At this stage an analogy can be made with the
geometry of the problem, as each of these sets of {α, βi} unknowns corresponds to a
mixed cell.
It can be seen that when t = 1, Equation 2.28 is equivalent to Equation 2.23; the
original random-coefficient system of polynomials. When t = 0, only the first two terms
of each of the n equations remain. There will be as many versions of Equation 2.28 as
there are mixed cells (or {α, βi} sets). Each of these n× 2 binomial systems which arise
at t = 0 can be solved using a relatively straightforward process to produce a number of
solutions equal to the volume of the corresponding mixed cell. The solutions of each of
these subdivisions can then be traced using a predictor-corrector path follower from t = 0
to t = 1, after which all the solutions of the random-coefficient system of polynomials
will be known. These solutions can then be traced in a second continuation process, using
a standard coefficient homotopy, to find all the solutions of the system with the original
coefficients. A short summary of the process is given:
1. construct a system of polynomials with the same structure as the target system, but
with random complex coefficients;
2. ensure that each support contains the origin (each equation has a constant term),
for the greatest generality;
3. use a series of n lifting functions to add an n+ 1th dimension;
4. use this lifting to determine all sets of {α, βi} (and their corresponding pairs of
vertices) which satisfy the constraints of Equation 2.27;
5. set t = 0 and determine all the solutions to each of the binomial systems arising
from Equation 2.28;
6. use continuation to trace each of these solutions to those of Equation 2.23;
7. trace all of these solutions to those of the original Equation 2.22 using a coefficient
homotopy.
39
2.4 Polyhedral Homotopy Method
Up till now, the method of completing step 4 in the list above has not been addressed,
although it is possibly the most labour intensive stage in the process. The primary goal
in this step is to find all the vertices of the convex polytope defined by the lifted indices
of each equation. Two methods are given below.
2.4.1 A Simplex Minimisation Method
If a system of n polynomial equations has only r < n distinct supports, then it is possible
to take advantage of this fact to speed up the solving of Equation 2.27. Generally, one
considers the case of r = n first, but for compactness, only the general case of 1 ≤ r ≤ n
will be presented here. A polynomial system with r < n distinct supports is said to have
Semi-Mixed Supports, while if they are all unique, to have Mixed Supports. An example
of a system with semi-mixed supports is given in Section 3.6. Define the multiplicity
of each type of support as ki, where
r
i=1 ki = n, and 1 ≤ l ≤ ki. Equation 2.28
requires a slight modification to the form of Equation 2.30. The definition in Equation
2.27 also needs to be slightly modified to allow larger groupings than pairs to satisfy its
requirements (Equation 2.29).
Ci = {aij| aij,α+ ωij = βi} i = 1, . . . , r
βi ≤ aij,α+ ωi(aij) ∀aij ∈ Qi\Ci
(2.29)
h∗il(y) =
aij∈Ci
cijly
aij +
aij∈Qi\Ci
cijly
aij taij ,α+ωi(aij)−βi (2.30)
Each of the r sets Ci contains ki + 1 elements. In the case that each equation’s support is
unique, and r = n, then Ci reduces to the {ai, ai } pairs described above.
Finding Level-k Subfaces
Following the method of Li (2003), the first task is to find all points which lie on the
boundary of the polyhedron:
βi ≤ aij,α+ ωi(aij)
40
2.4 Polyhedral Homotopy Method
This can be rewritten in matrix form as:
1 −ai1,1 . . . −ai1,n
1 −ai2,1 . . . −ai2,n
...
...
...
1 −aimi,1 . . . −aimi,n
βi
α1
...
αn
≤
ωi(ai1)
ωi(ai2)
...
ωi(aimi)
or Aν ≤ b
(2.31)
Equation 2.31 defines a polyhedron in n+1 dimensions. At each vertex of the polyhedron,
at least n + 1 of the inequalities will be active (become equalities). If more than n + 1
of the inequalities are active at a vertex, the vertex is said to be degenerate. It is likely
that some of the inequalities will never become active, and cannot be used to define any
vertex (these lie inside the convex polytope defined by the lifted support). To determine
which inequalities can be used to form vertices, one must solve what is usually known
as a phase 1 problem to find an initial vertex of 2.31, and use the simplex minimisation
method to attempt to reach a vertex at which each inequality becomes active.
1. Construct a set of integers, U1 = {1, . . . ,mi} representing each of the inequalities
in Equation 2.31;
2. solve a phase 1 problem to find an initial vertex where at least n+1 of the inequal-
ities are active;
3. construct a new set on integers, V1, representing these active inequalities, and set
U1 = U1\V1;
4. take an element off the top of U1, say number j;
5. remove j from U1: U1 = U1\j;
6. solve the problem:
Minimise− βi + aij,1α1 + . . .+ aij,nαn
s.t.
Aν ≤ b
w.r.t. (βi,α1, . . . ,αn)
The objective of this minimisation is simply the jth row of A. Note that in a prac-
tical implementation of this method, A should be row reduced to form an upper
41
2.4 Polyhedral Homotopy Method
triangle of zeros, and columns of zeros if it is rank deficient. During the minimisa-
tion process, various vertices will be encountered on the way to the target vertex.
Each of these vertices will be defined by a set of active inequalities, which should
be added to V . If the minimum value of the objective at a vertex is −ωi(aij), then
j should be added to V1;
7. set U1 = U1\V1. If U1 is not empty, return to step 4. If U1 is empty, then exit; V1 is
the set of all possible active inequalities.
A vertex is defined by n+ 1 active inequalities. An edge of the polyhedron is defined by
n inequalities, and the simplex method works by moving from a vertex, along one of the
edges which forms this initial vertex, to another at which the function objective is smaller.
If a degenerate vertex (one with more than n+ 1 active constraints) is encountered, then
all possible combinations of n constraints, defining edges intersecting the vertex, must
be considered. Each must be tested as a potential feasible exit direction from the current
vertex. The treatment of degenerate vertices significantly slows the simplex minimisation
process, but lifting functions which are sufficiently random tend to lead to polyhedra
with non-degenerate vertices. Each vertex encountered during the simplex minimisation
process has a new set of active inequalities which can immediately be added to V1 and
removed from U1, meaning that each element of the initial U1 does not need to be sought
sequentially and independently (one of the great advantages of the simplex method).
The next stage involves finding pairs of inequalities which appear together. The pro-
cess is quite similar.
1. Construct a set of pairs U2 = {{j1, j2} | {j1, j2} = comb(V1, 2)};
2. use a non-degenerate vertex encountered in the previous process as a start vertex;
3. remove all the pairs of inequalities which appear at this start vertex from U2, and
use them to define V2;
4. take a pair {j1, j2} from the top of U2;
5. remove {j1, j2} from U2: U2 = U2\ {j1, j2};
6. solve the problem:
Minimise− 2βi + (aij1,1 + aij2,1)α1 + . . .+ (aij1,n + aij2,n)αn
s.t.
Aν ≤ b
w.r.t. (βi,α1, . . . ,αn)
42
2.4 Polyhedral Homotopy Method
Again, remove any pairs of inequalities encountered at vertices during minimisa-
tion from U2 and append them to V2. If the minimum value of the objective is
−ωi(aij1)− ωi(aij2), then add {j1, j2} to V2;
7. set U2 = U2\V2. If U2 is not empty, return to step 4. If U2 is empty, then exit; V2 is
the set of all possible pairs of active inequalities.
If the equation in question has a multiplicity of one (ki = 1), then stop here. If ki = 2,
then repeat the process above, this time looking for all possible combinations of three
active constraints, given that each of the three elements must already have appeared in a
pair with each of the other two elements in V2. This can be pursued to the point of finding
all possible combinations of ki + 1 active constraints. It is much faster to undertake this
iterative process in finding all the combinations of ki + 1 active constraints than it is to
set Uki+1 with
mi
ki+1
elements and search for them directly.
mi
ki+1
can be a very large
number!
So far, the r supports have been only been considered individually. Equation 2.29
defines a polyhedron which encompasses all of the supports. At this stage, it is known
which combinations of ki+1 elements from each of the r supports could possibly satisfy
2.29. Each of the r supports has yielded what is known as a level-k subface, and these
k-subfaces need to be fitted together in a way which satisfies Equation 2.29, forming a
level-r subface. Most combinations will not meet this requirement. It is, however, likely
that more than one combination of elements for each support will work, resulting in more
than one level-r subface (and hence more than one value of α). One could simply try
all the combinations of ki + 1 support elements (level-k subfaces) for each support in an
attempt to satisfy Equation 2.29, but in most cases this would be quite slow. Instead, a
further simplex minimisation step is employed to extend the level-k subface for the first
support. Each level-r subface will correspond to a particular value of α and β. It cannot
be known beforehand how many of these subfaces there will be. What is known is that
each r-subface will define a volume:
det (V (α)) =
a11 − a10
...
a1k1 − a10
...
ar1 − ar0
...
arkr − ar0
(2.32)
43
2.4 Polyhedral Homotopy Method
(note the r sets of ki + 1 elements arranged into n pairs, forming a binomial start system
as in Equation 2.28). The sum of each of the volumes det(V (α)) is equal to the mixed
volume for the entire system.
Extending the Level-k Subfaces
Once level-k subfaces have been found for each support using Equation 2.31, attention
is now turned to the subfaces generated by the first support. In practice, it is likely that
quite a number of pairs (or sets of k1 + 1 elements) will have been found which satisfy
2.31, each representing a level-k subface.
Assume that the elements C1 =
a10, . . . , a
1k1
form one of the level-k subfaces for
the first support. There is now a larger simplex:
a1j − a10,α ≤ ω1(a10)− ω1(a1j) ∀a1j ∈ Q1\C1
β2 − a2j,α ≤ ω2(a2j) ∀a2j ∈ Q2
(2.33)
which can be written in a matrix form as:
0 a11,1 − a10,1 . . . a11,n − a10,n
...
...
...
0 a1m1,1 − a10,1 . . . a1m1,n − a10,n
1 −a21,1 . . . −a21,n
...
...
...
1 −a2m2,1 . . . −a2m2,n
β2
α1
...
αn
≤
ω1(a10)− ω1(a11)
...
ω1(a10)− ω1(a1m1)
ω2(a21)
...
ω2(a2m2)
The sequence of k1 equations:
a11 − a10,α = ω1(a10)− ω1(a11)
...
a1k1 − a10,α
= ω1(a
10)− ω1(a1k1)
can be used to reduce the dimensionality of the problem by k1. This means that α now
only has n− k1 elements.
Once again, the aim is to locate all the vertices of the simplex defined by 2.33. This
time, one seeks to find pairs (or sets of k2 + 1) of active inequalities in the second set of
equations (pertaining to the second support). If the number of active inequalities never
exceeds k2 + 1 in this section, then it is said that C1, the level-k subface for the first
support, cannot be extended. Recall that there will most likely be more than one version
44
2.4 Polyhedral Homotopy Method
of C1 to test in such a way. If one particular version of C1 is extendible, then that C1+C2
combination is recorded. One then seeks to extend thisC1+C2 subface by searching for a
compatible C3 using a similar simplex to Equation 2.33. Once a set of C1+C2+ . . .+Cr
level-r subfaces has been found which satisfy Equation 2.29, then their corresponding α’s
and β’s can be computed, and their volumes recorded using 2.32.
It is worth noting that the task of finding the level-k subfaces for each support can be
quite time consuming. Often it is better to find the level-k subface for the first support
only, and then progress immediately to extending the subface using the other supports (in
their entirety). The reason this is often faster is that the simplex method’s speed depends
heavily on the dimension of the problem. Since with each step of the subface extension
process, it is possible to reduce the dimensionality of the problem by the sum of the
previous ki’s, it can be beneficial to find the level-k subface for the first support only, and
leave the other supports untreated. This leads to an important operational note for using
the simplex minimisation method: always sort the equations and their supports from first
to last in order of increasing complexity. In other words, place the equation/support
with the fewest terms/elements first, and that with the greatest number last. In this way,
by the time the subface extension process reaches the final support (with the greatest
number of inequalities to scan), the dimensionality has been greatly reduced.
At the end of the subface extension process, it is possible to form a binomial system
from Equation 2.30 with t = 0 for each of the level-r subfaces. Each r-subface generates
det(V (α)) solutions at t = 0, which can be traced to t = 1: the solutions of the final
form of the random complex coefficient target system of polynomials.
2.4.2 A More Intuitive Method
The method of solving 2.29 given in Section 2.4.1 can be very fast when implemented,
even on quite large systems. It is, however, very intricate to code. It also requires a sim-
plex minimisation code which, although commonly available ‘off the shelf,’ will most
likely have to be written from first principles to give access to all of the parts of the pro-
cess which make the overall method so efficient. If one has access to a widely available
package known as Qhull (implemented in Matlab as convhulln.m) which calculates
the convex hull of groups of points in n dimensions, then it is possible to find the level-
r subfaces of a system of equations quite easily. The following ‘bootstrap’ algorithm
was developed specifically for use in solving the systems which appear in the following
chapters.
Assume again that there are n equations with r distinct supports of multiplicity ki for
45
2.4 Polyhedral Homotopy Method
i = 1, . . . , r with
r
i=1 ki = n and 1 ≤ l ≤ ki. Consider the definition of Q¯i as given
in Equation 2.21, as well as the Minkowski sum of hulls as given in Equation 2.17. Also
assume again that each of the r supports contains the origin. The process is as follows:
1. lift each of the r supports using random lifting functions ωi, and construct the Q¯i’s;
2. construct the complete Minkowski sum of these hulls Q¯tot = Q¯1 + Q¯2 + . . .+ Q¯r.
This is an iterative process, and is straightforward to implement. One can either
recompute the convex hull at each step, or once at the end (meaning Qhull is only
called once in the entire process). The time taken by each approach varies based on
the type of problem. Either way, at the end it is important that the total Minkowski
sum be a convex polytope.
3. Once the vertices of each facet of the convex polytope Q¯tot have been found, ex-
press the polytope in terms of a system of inequalities Bx ≤ c. This can be
achieved as follows:
(a) find a location inside Q¯tot, say q¯;
(b) shift Q¯tot by distance q¯ so that Q¯tot now contains the origin;
(c) let M be a (n + 1 × n + 1) matrix whose rows represent the points at each
vertex of a facet of Q¯tot. Each row of B is calculated by inverting the vertices
M−1e where e is a (n+ 1× 1) column vector of 1’s;
(d) c is then simply calculated as c = 1+Bq¯.
4. the rows of B are the outward pointing normals of each of the polyhedron’s facets;
5. identify the lower hull simply by looking for all normals with a negative ‘ω’ com-
ponent;
6. normalise each of the rows of B by its ω component, producing a list of inner
normals to the polyhedron;
7. identify which of the facets of the lower hull correspond to the original supports,
and which correspond to mixed cells. This is achieved by taking a row of B, say b,
and forming the product:
βi = q¯ij, b q¯ij ∈ Q¯i
If there is an i for which βi is different for every j, then b is an inner normal to a
support, and not a mixed cell.
46
2.4 Polyhedral Homotopy Method
8. the remaining rows of B are now of the form bp = {αp, 1}, where p refers to a
particular mixed cell. Each row bp will have ki + 1 values of j which generate
identical values of βi = q¯ij, bp in each support i. The identification of the mixed
cells is complete.
Note that if a facet has more vertices than there are dimensions, Qhull will divide the
facet up into smaller subfacets. Imagine the square base of a four-sided pyramid in three
dimensions; QHull will divide the square base up into two equal triangles, and output six
distinct facets. An unmentioned, but important part of the process above, is to re-combine
these divided facets to capture the true number of vertices. Mixed cells usually have more
vertices than there are dimensions.
2.4.3 Optimising the Lifting Values to Improve Numerical Stability
Tracking the solution paths which arise using the polyhedral method involves implement-
ing Equation 2.28 numerically. The power to which the continuation parameter t is raised
has a great impact on the numerical stability of the path following process. If the expo-
nent (aij,α+ωi(aij)−βi term) is too small, then tracking precision will be lost where t
is close to 0. Similarly, if the exponent is too large, then tracking precision will be lost as
t→ 1. Dynamic Lifting (Mizutani et al., 2007; Verschelde et al., 1996) is one technique
which can be applied to try to keep these exponents in a reasonable range, but is not
practical beyond a certain mixed volume. Another technique which involves balancing
the lifting values (Gao et al., 2000) tries to make the best of a pre-existing subdivision
which was most likely calculated using a random lifting. In Gao et al. (2000), a constant
multiple is applied to all of the existing lifting values to ensure no exponents are smaller
than a certain threshold value. A form of optimisation is then applied to the lifting val-
ues with the goal of reducing the magnitude of the largest exponents while preserving
the structure of the subdivision. A slight variation on this was performed here. First, a
constant multiple was applied to the entire lifting set to bring the largest exponent within
a certain upper bound. Next, a form of optimisation was applied to the smallest expo-
nents to raise them to a sufficient height. The following simple line-search based lifting
value optimiser was written specifically for use in solving the systems which appear in
the following chapters.
Imagine that for a particular set of equations, and a particular set of random lifting
values, the subdivision is found to consist of S level-r subfaces. For each of the r equation
supports, S pairs (or ki + 1 sets) of support terms are formed. Some of these support
terms will appear in more than one of the pairs. Form a collection of these terms for each
47
2.5 Witness Sets
equation as:
Φi =
S
s=1
{ai, ai }s i = 1, . . . , r
The objective function to be minimised can then be written as:
Obj =
r
i=1
S
s=1
aij∈Qi\Φi
− log (aij,αs+ ωi(aij)− βis) (2.34)
The variables used in the optimisation are the heights:
ωij = {ωi(aij)|aij ∈ Φi}
The effect of the logarithm is to heavily penalise exponents of t which are too close to
zero. Using a simple gradient-based line search method is usually sufficient, as it leads to
a convergence within a reasonable number of iterations. To increase numerical accuracy
close to zero, the complex step method was used in computing gradients (Martins et al.,
2003; Ridout, 2009). Those exponents which are close to zero are pushed upwards in the
process. The magnitude of the smallest exponent can usually be expected to at least triple
using this method. It was discovered that a minimum exponent value of 0.35 sufficed for
numerical stability. A lesser sensitivity to large exponent values was observed. Anything
up to an exponent value of 20 was observed to cause little or no numerical instability.
2.5 Witness Sets
Sometimes the solutions to a system of polynomial equations are not all geometrically
isolated (see fig. 2.1). Take the example:
f(x) =
(x21 + x
2
2 − 1)(3x21 + x2)
(x21 + x
2
2 − 1)(x1 − x2)
= 0 (2.35)
Clearly, there is a trivial solution at {0, 0}, as well as a Zero Dimensional Solution at
{−1/3,−1/3}. Systems of polynomial equations can have positive dimensional solu-
tions as well. The ‘dimension’ can be thought of as the number of parameters it would
take to describe the line or surface of solutions in polynomial form. The example above
has a solution set of dimension 1, which is a curve. In this case, it is simply the unit
circle. The maximum dimension of any solution set is d = n− 1, where n is the number
of variables (Verschelde, 2009). A direct application of polynomial continuation to this
48
2.5 Witness Sets
problem will produce a number of singular and non-singular solutions, since all positive
dimensional solutions are singular, and the continuation process will identify some points
on the unit circle. Without prior intuition about where the solutions to this problem might
fall, and of what type they might be, this blind application of continuation would not
reveal much about the structure of the equations. Any singular solution found cannot be
guaranteed to belong to a positive dimensional set, nor can it be determined what the di-
mension of that set might be, nor which other solutions might share that set. One further
problem with this approach is that the Newton’s method endgames used to locate solu-
tions at the end of a continuation run do not work particularly well on singular solutions
(convergence is less reliable, and limited to a linear rather than quadratic rate).
A good approach for determining the structure of a system of polynomial equations,
as well as finding the solutions themselves, is to append a number of intersecting com-
plex hyperplanes to the original problem (Sommese & Verschelde, 2000; Verschelde,
2009). Each new hyperplane brings with it a new variable. The number of hyperplanes
required is equal to the dimension of the solution set being examined. A 1D solution set,
as in the example above, would require the addition of a single hyperplane, and a single
new variable. In general, the modified equations look like:
f (x, z) =
f1(x) +
d
j=1 λ1,jzj
...
fn(x) +
d
j=1 λn,jzj
a1 + a1,1x1 + · · ·+ a1,nxn + z1
...
ad + ad,1x1 + · · ·+ ad,nxn + zd
(2.36)
where d is the dimension of the solution set being scanned. The z terms are the intro-
duced variables, and the as and λs are random complex numbers. These hyperplanes
will intersect the positive dimensional solution set, and define a number of non-singular
solutions on it. The number of these solutions corresponds to the degree of the positive
dimensional solution set. Positive dimensional solutions are identified by looking for
solutions to 2.36 with z = 0. These solutions are said to form a Witness Set.
Once the solutions with z = 0 have been identified, they are put aside and labelled
as the witness set for the dimension d. If d ≥ 1, then the number of hyperplanes still
included in the problem can be reduced to gain access to lower dimension witness sets.
This process is generally referred to as a Cascade of Homotopies. The cascade process
is repeated for each value of d until d = 0 is reached. At each stage of the process, all
49
2.5 Witness Sets
solutions with z = 0 are labelled as witness sets for that particular level (value of d).
The leftover solutions at the end are the zero-dimensional solutions which would have
been identified using a direct application of continuation. To reduce the dimensionality,
an homotopy of the form in Equation 2.37 is constructed and tracked from t = 0→ 1.
h(x, z) =
f1(x) +
d−1
j=1 λ1,jzj + (1− t)λ1,dzd
...
fn(x) +
d−1
j=1 λn,jzj + (1− t)λn,dzd
a1 + a1,1x1 + · · ·+ a1,nxn + z1
...
(1− t)(ad + ad,1x1 + · · ·+ ad,nxn) + zd
(2.37)
During this process, the dth intersecting hyperplane and the dth z variable are removed
from the system of equations.
There are two points worthy of note at this stage:
1. Not all solutions with z = 0 are necessarily members of a witness set of the dimen-
sion currently under investigation. It is possible that such a solution actually lies on
a higher dimensional solution set. If all higher dimension witness sets have already
been identified, it is possible to determine if a point is actually a member of one of
these higher sets using a membership test. This is why, when no prior information
about a system of equations is available, it is prudent to begin with d = n− 1. An
indication that a point is actually a member of a higher dimensional solution set is
that the point is singular.
2. Members of a witness set for a particular dimension are not necessarily members
of the same Irreducible Component. This could be the case if there are two or more
separate curves/manifolds in the solution space at the same dimensionality. It is
possible to determine which elements of a witness set are members of the same
irreducible component using a process called Monodromy (Sommese & Wampler,
2005), discussed in Section 2.5.1.
An illustration of what a membership test involves is given in Figure 2.7. In this illus-
tration, a single hyperplane L intersects two irreducible components at a total of five
locations. Assume that these five points constitute the entire witness set for this dimen-
sion. The point x has been located as part of the cascade process, in a lower dimension.
To determine if point x is actually a member of the witness set just described, plane L is
translated such that it passes through x. If x was a member of the witness set (and hence
50
2.5 Witness Sets
lay on one of the two irreducible components pictured), then one of the five witness set
points would be tracked to the exact location of x as the intersecting plane was moved.
x
L
Lx
x
Plane in 1D, illustrating
a witness set with 5 members
in 2 irreducible components.
Want to test if x is a
member of witness set.
Shift L to Lx, a plane
passing through x.
x is not a member of
this witness set.
Figure 2.7: Illustration of membership test for a single point.
By way of an example, the decomposition of equation system 2.35 will be described
in detail (a more involved example is given on p2028 of Sommese et al. (2001a)). Since
only two variables are involved, start with d = n− 1 = 1. This involves the introduction
of a single new variable z, and a single intersecting plane. With the introduction of the
new variable, the system in terms of {x1, x2, z} has a mixed volume of 12. Solving this
system shows that four of the solutions go to infinity, six have z = 0 and two have z = 0.
It can immediately be said that the witness set of dimension 1 has two members. This
is not surprising, as the unit circle is a second order curve in one parameter. The six
remaining solutions are then subjected to a dimension reduction homotopy, or cascade
(Equation 2.37), which brings d to zero. This second homotopy shows that one solution
goes to infinity, while five remain finite. Applying a membership test to these five re-
maining points shows that three actually lie on the unit circle, leaving the expected two
solutions {0, 0} and {−1/3,−1/3}. This is illustrated graphically in Figure 2.8.
2.5.1 Monodromy
Should a system of polynomial equations possess a positive dimensional solution set,
then the solution of this system, augmented with an intersecting complex hyperplane
(as in Equation 2.36), will consist of a number of witness points. In the case of Figure
2.7, five witness set points, lying on two irreducible components, are shown. Initially, it
51
2.5 Witness Sets
12 initial solutions 4 paths to infinity
2 solutions with z = 0
6 remaining solutions
1D witness set
1 path to infinity
5 remaining solutions Filter stage 3 filtered out
2 0D solutions
Cascade step
Use 1D witness
set to perform
membership tests
Figure 2.8: Reduction process for system of polynomial equations (Equation 2.35).
will not be known how many irreducible components are present, nor how many witness
points lie on each. One way of determining which points lie on which irreducible compo-
nent is to sample the irreducible components at a sufficient number of locations (perhaps
by incrementally moving intersecting hyperplanes and tracking individual points) to con-
struct a polynomial of the same degree as the irreducible component. This polynomial
can then be used to directly test membership of other points (Sommese et al., 2001a).
Another way to determine the finer structure of a system of equations is to employ a
process known as monodromy (Sommese et al., 2001b). This involves tracking witness
points from one intersecting plane to another random plane, before permuting the mem-
bers of each irreducible component by changing the complex coefficient often introduced
to a linear homotopy to increase numerical accuracy in solution tracking (essentially the
factor θ in Equation 2.16). These permuted solutions are then tracked back to the original
intersecting plane. Members of the same irreducible component will permute amongst
themselves only, which allows these components to be identified. If these witness points
happen to be singular (if they have multiplicity > 1), they are more difficult to track
along their irreducible components. Methods do exist for treating singular points of this
type (Sommese et al., 2002b), but these will not be covered here as no such points were
discovered in the kinematic equations considered.
52
2.6 Solution to a Hinge Closure Problem
2.6 Solution to a Hinge Closure Problem
To illustrate the applicability of polynomial continuation to a simple mechanical prob-
lem, a planar 4-bar mechanism will be examined. This mechanism must be able to fold
completely flat, with all of its bars collinear (a condition which requires that the sum of
the lengths of two adjacent sides must be equal to the sum of the lengths of the other two
sides). The layout is shown in Figures 2.9(a) and 2.9(b). This mechanism is actually a
special type of ‘hinge’ which is symmetric about CD (a concept proposed by the author
and Dr Simon Guest for connecting adjacent SAR panels in an articulated fashion fol-
lowing a visit to EADS Astrium in Portsmouth). The ends of two panels can be attached
to the AB links, allowing the two panels to be parallel but separated by a distance of
2p when in the configuration pictured in Figure 2.9(a), and collinear when the hinge is
folded flat. The hinge provides a way of attaching one panel to another while keeping the
active surface (which faces inwards in the closed configuration) free from attachments. It
can be shown that the only constraints necessary for operation are:
AC + CD = AB +BD
AC ≤ AE
(2.38)
The use of the second of Equations 2.38 can be avoided through careful choice of the
parameter q (pictured). The aim of the design procedure is to specify p and l based on
the required geometry, choose a value for q, and then solve for the lengths CD and BD.
There are two unknowns in this problem, and as things stand, only one equation. In
addition to AC +CD = AB +BD, equations can be written which relate to the lengths
AC,BD and CD. These are:
AC2 = (x0 − CD)2 + p2
BD2 = x20 + (p+ l)
2
CD = x0 + q
The complete set of equations is given in 2.39.
AC + CD − l −BD = 0
AC2 − (x0 − CD)2 − p2 = 0
BD2 − x20 − (p+ l)2 = 0
CD − x0 − q = 0
(2.39)
53
2.6 Solution to a Hinge Closure Problem
x
B
A
D/E C
(x0,p+l)
(x0,p)
(x0+q,0)
Plane of symmetry
Panel #1
Panel #2
y
(a) Initial layout of hinge.
Panel #1
x
B
A
D C
Plane of symmetry
Panel #2
y
E
(b) Hinge during operation. Notice that joint E is a
combination slider/revolute.
Figure 2.9: Hinge design for continuation analysis.
This system has a total degree of four. It is good practice to remove any linear equations,
if possible, by substitution. After the first and last equations of 2.39 have been removed,
what is left is:
(BD + l − q − x0)2 − (q2 + p2) = 0
BD2 − x20 − (p+ l)2 = 0
(2.40)
which is written in terms of the unknowns BD and x0. These equations still have a total
degree of four, and also a mixed volume of four. Introducing a standard set of parameters
which are known to work:
q = 0.2
p = 0.2
l = 0.3
gives the two finite solutions:
BD
x0
=
−0.5179
−0.1351
,
0.7751
0.5922
Clearly the first solution is not physically realisable, but the second is. The remaining two
solutions are at infinity. It is easy to see why the solution structure is as it is by looking
at the curves representing Equations 2.40. This is shown in Figure 2.10. The two finite
solutions are clearly visible, with the other two off at infinity.
54
2.6 Solution to a Hinge Closure Problem
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
-2.5
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
2.5
x0
BD
Solution 1
Solution 2
Equation 2
Equation 1
Figure 2.10: Solution paths for simple hinge design showing two solution locations.
While this example is simple, it demonstrates that the method of Polynomial Contin-
uation can reduce the complexity of finding solutions to kinematic problems.
55
3. Plane Symmetric Bricard 6R
Foldable Frames
In this chapter, a particular form of plane symmetric 6-bar folding linkage will be exam-
ined in some detail. Several different types of foldable frames, which in their deployed
configurations form (often regular) polygons, have appeared in literature in the past 40
years. An early example appears in Crawford et al. (1975), in which an even number of
bars are linked together in such a way that they can be folded into a tight bundle, and un-
folded to form a regular polygon (in the 6-bar case of this, a three-fold symmetric linkage
results (Chen et al., 2004), while in the 4-bar case, a Bennett linkage is formed (Chen
& You, 2006a,b)). 4-bar foldable frames have also been extensively examined recently
(Chen, 2003; Chen & You, 2006a; Gan & Pellegrino, 2003). In Pellegrino et al. (2000),
a new family of 6-bar foldable frames was proposed. A two-fold symmetric member of
this family has been proposed as a support for a solar blanket, and its kinematics ex-
amined numerically (Gan & Pellegrino, 2005, 2006). Recently, this two-fold symmetric
6R foldable frame was identified as a special line and plane symmetric Bricard linkage
(Chen & You, 2009). This particular variant does, however, suffer from problems with
bifurcations (although certain designs avoid this). If one of the two planes of symmetry
is removed, a mobile 6R frame which experiences fewer problems with bifurcations re-
mains. An example is shown in Figure 3.1. The kinematics of this singly symmetric 6R
foldable ring were studied recently in Hutt (2007).
This chapter seeks to extend the results of the previous work by: first identifying the
frame as a plane symmetric Bricard linkage (Bricard, 1897); examining the nature of
its mobility using a cascade of homotopies (Sommese & Verschelde, 2000) to identify
positive dimensional solution sets; determining a range of design parameters for building
feasible mechanisms; deriving a closed form expression for the linkage’s kinematics; and
finally employing polynomial continuation in an attempt to design a family of singly
symmetric 6R foldable rings with certain desirable practical properties.
Sections 3.2-3.4 contain some analysis which is not directly applicable to the design
56
3.1 Frame Geometry and Definitions
Figure 3.1: Folding process for a linkage with parameters α1 = π/4,α2 = −π/4 and γ = π/2.
Each bar is shown as a twisted prismatic bar with square cross-section.
of linkages using continuation, but which nonetheless adds some important breadth of un-
derstanding of the plane symmetric 6R foldable frame. It is hoped that these sections will
allow for a more informed interpretation of the results on the design process in Section
3.6. This kind of extended analysis will be omitted from the following chapters.
3.1 Frame Geometry and Definitions
A representation of the general plane symmetric Bricard linkage is given in figure 3.2. In
this chapter, a special class of this linkage, which can be constructed using straight links
forming a rectangle when deployed, is considered. The two-fold symmetric ring of Chen
& You (2009) has two different bar lengths (l1 and l2), and the bars are all tilted from the
vertical by a single angle µ. Square cross-sectioned, prismatic (i.e. untwisted) bars were
used. By contrast, the 6R linkage considered in this chapter has all six bar lengths the
same (l), and four separate bar tilt angles (α1,α2, β1 and β2), introducing a requirement
that, if the bars have a square cross-section, some of the bars must be twisted in order to
match the prescribed tilt angles at each end. The deployed linkage is a rectangular frame
of breadth twice its height. A simplified diagram of the deployed linkage with all design
parameters labelled is given in Figure 3.3, while a representation of the physical linkage
is given in Figure 3.4, in which the twists in the bars are clearly visible. While a square
cross-section is not required to construct the linkage, it does aid in visualising the bar
twist.
57
3.1 Frame Geometry and Definitions
h6
h1
h2
h3
h5
h4
D
D
D
a61
a12
a23
R1
R2
Figure 3.2: Plane symmetric Bricard linkage (case illustrated is from linkage with
α1 = π/4,α2 = −π/4 and γ = π/2).
Because the linkage has only a single degree of freedom, its opening and closing
(deployment/stowing) can be driven using any one of its six hinges. The plane symmetry
means that the motion of two of the six hinges (referred to here as θ61 and θ12) will be
exactly replicated (in hinges θ45 and θ34 respectively). To track how the linkage moves
from its deployed to stowed position, one can plot the hinge angle of one of these two
hinges against the other. The relationship between the angle of opening of each of these
two hinges is not simple, but can be found algebraically (see Section 3.5).
In linkage design, one adjusts a collection of design variables (lengths, angles, thick-
nesses etc.) such that the linkage moves in a way which is as close as possible to a desired
pattern. This closeness can be specified in a number of ways. It might be that a certain
part of the linkage must trace out a given curve in space during its unfolding. It might
be that a part of the linkage never exceeds a given velocity, or that a joint never subtends
more than a given angle. In the design of the plane-symmetric 6-bar linkage, one appro-
priate design criterion which suggests itself is the specification of a special relationship
between θ61 and θ12 during the deployment phase. In a way, this is like specifying Preci-
sion Points, but in angle space. In the current chapter, three design variables (identified
later) are used to specify the linkage. In order to construct a square system of equations
58
3.1 Frame Geometry and Definitions
Y
X
Z
h1
(ș
61
)
45
º
Pl
an
e
of
sy
m
m
et
ry
Pr
oj
ec
tio
n
of
h
1
on
to
Y
Z
pl
an
e
h2
(ș
12
)
h3
(ș
23
)
h4
(ș
34
)
h5
(ș
45
)
h6
(ș
56
)
1
2
3
4
5
6
ȕ1
ȕ2
Į1
Į2
Į
1
p1
p2
p3
p4
p5
p6
i
B
ar
n
um
be
r
pi
H
in
ge
p
os
iti
on
m
ar
ke
r
hi
(ș
ji)
H
in
ge
v
ec
to
r (
w
ith
h
in
ge
a
ng
le
)
Įi
H
in
ge
d
es
ig
n
pa
ra
m
et
er
#
1
Į
i
Pr
oj
ec
tio
n
of
h
in
ge
d
es
ig
n
pa
ra
m
et
er
#
1
on
to
Y
Z
pl
an
e
ȕi
H
in
ge
d
es
ig
n
pa
ra
m
et
er
#
2
Figure 3.3: Design variables of the singly-symmetric 6R linkage with plane of symmetry
shown. The global axes are indicated in the centre of bar 1. This is a special subset
of the Bricard plane symmetric case in which all the hinges lie in the same plane in
the ‘deployed’ configuration.
59
3.1 Frame Geometry and Definitions
one can specify three {θ61, θ12} pairs, and use these to form three closure equations to
solve. In this way, three precision points can be used to guide the linkage from the stowed
to the deployed position along a desirable path. This will be covered in more detail in
Section 3.6.
h1
h2
h3
h4
h5
h6
Figure 3.4: Example of singly-symmetric 6R foldable linkage with visible bar twist for
α1 = π/4,α2 = −π/4 and γ = π/2. Notice that even the offsets in the hinge
locations caused by the finite thickness of the bars does not cause the linkage to
behave significantly differently.
There are six hinges (labelled h1 − h6), each with a single rotational degree of free-
dom, connecting the bars in a closed loop. The plane of symmetry is preserved through
the folding motion. This plane is parallel to the XZ plane in the fully deployed/open
configuration, shown in Figure 3.3. The plane contains the points p6 and p3 (pi are posi-
tion vectors), and the vectors h6 and h3, which are inclined to the Z axis by angles β1 and
β2 respectively. Also when deployed, hinges h1 and h2 lie in planes rotated from the Y Z
plane by 45◦ about the Z axis. The angles these hinges form to the horizontal can be spec-
ified in two important ways. When constructing physical models of the plane-symmetric
6-bar, the most intuitive form is obtained by taking the projection of the hinges onto the
Y Z plane, and considering the angle formed between that projection and the XY plane,
labelled here as α1 and α2. This projection is shown in Figure 3.3. This definition of
hinge inclination to the vertical is more intuitive as it specifies the tilt angle that a square
cross-sectioned bar would need to form with the horizontal before cuts at 45◦ are made.
However, future mathematical results are simplified by directly taking the angle between
the XY plane and the hinge vectors, written as α1 and α2 here. Relationships between
60
3.1 Frame Geometry and Definitions
the two α definitions can be constructed as:
tanα =
1√
2
tanα
⇒ sinα = sinα
√
sin2 α + 2 cos2 α
⇒ sin2 α = sin
2 α
1 + cos2 α
cos2 α =
2 cos2 α
1 + cos2 α
At present, there are four angular parameters (either {α1,α2, β1, β2} or {α1,α2, β1, β2})
which define the linkage. In order for all the bars to be parallel when fully stowed, the
hinge vectors h6 and h3 must also be parallel in the fully folded configuration since they
must be perpendicular to both the normal to the plane of symmetry, and the ends of the
bars to which they are attached. In general, h6 and h3 will not be parallel when folded
for a given choice of β1 and β2. The parallel condition can be enforced by specifying a
simple linear relationship:
β1 = 2α
1 − γ
β2 = π − 2α2 + γ
(3.1)
where an extra variable, γ, has been introduced to replace β1 and β2. Also note that
it is the (projected) α1 and α2 definitions which have been used here. Three variables
({α1,α2, γ} or equivalently {α1,α2, γ}) remain to specify the linkage.
It can be shown that hinges 1 and 2 have maximum opening angles, as described in
Equation 3.2.
θ61max = π − 2 tan−1
tan α1
2 + tan2 α1
= π − cos−1(cos2 α1)
θ12max = π − 2 tan−1
tan α2
2 + tan2 α2
= π − cos−1(cos2 α2)
(3.2)
At these maximum angles, bars 6 and 2 are both colinear with bar 1, indicating full
folding of the linkage. These definitions will be useful for simulation purposes later.
61
3.2 Expression in Terms of Denavit-Hartenberg Parameters
3.2 Expression in Terms of Denavit-Hartenberg Param-
eters
A good rule of thumb for determining the number of degrees of freedom (DOF) in a
mechanism, known as the Kutzbach Criterion, is given in Equation 3.3 (to be found in
Freudenstein & Maki (1979)).
F = λ(l − j − 1) +
j
i=1
fi (3.3)
Here, F is the number of degrees of freedom, l is the number of links present, j is the
number of binary joints, fi is the number of degrees of freedom in the ith joint (eg. 3 for
ball joint, 1 for hinge) and λ is the number of spatial degrees of freedom available to the
mechanism (3 for planar mechanisms, and 6 for 3D). A joint connecting n > 2 links is
counted as (n− 1) binary joints. Equation 3.3 is only a general indication of the degrees
of freedom a mechanism is likely to possess, as it often happens that a mechanism may
in fact have a greater number of degrees of freedom because of certain special geometric
properties. Phillips (1984) states this as “All geometric specialities, whether consciously
introduced by the designer or occurring accidentally, give rise to special extra mobilities
Ms: these always increase the apparent mobility Ma of mechanism, never decrease it.”
These geometric properties are very difficult to generalise, and will not be addressed in
detail here. For further reading on this topic, see both Phillips (1984) and Phillips (1990),
which form an extended work dealing primarily with the identification and classification
of these geometric degrees of freedom studied from a screw theory perspective.
A blind application of Equation 3.3 indicates that the minimum number of links re-
quired to be arranged in a loop using single DOF joints for a positive mobility to arise
is seven. In general, this is true, and seven bars arranged to form a loop using hinges
will produce a linkage with a mobility of one. Several loops possessing fewer bars but
with positive mobility due to special geometric properties have been identified. The Ben-
nett Linkage is a mobile 4-bar loop (Chen & You, 2005). The Bennett Linkage can be
used to generate a 5-bar loop known as the Goldberg 5R linkage (Chen, 2003). There
are several known mobile 6-bar loops, which can be synthesised in a number of ways
(including combining Goldberg linkages (Chen & You, 2007)). Other forms of foldable
6-bar linkages have been discovered more recently (Baker, 2005, 2006; Chen & You,
2008). Arguably the most famous of the 6-bar linkages are the Bricard Linkages (Baker,
1980), of which there are six subtypes, being the general Line Symmetric case, the gen-
62
3.2 Expression in Terms of Denavit-Hartenberg Parameters
eral plane-symmetric case, the trihedral case, the line-symmetric octahedral case, the
plane-symmetric octahedral case and the doubly collapsible octahedral case. The 6-bar
linkage of this chapter happens to be the plane-symmetric Bricard case. A representa-
tion of this case, with the Denavit-Hartenberg parameters labelled, is given in Figure 3.2.
The linkage is symmetric about the plane passing through hinges 6 and 3. The defining
parameters are:
a61 = a65 , a12 = a54 , a23 = a43
α61 + α65 = α12 + α54 = α23 + α43 = π
R6 = R3 = 0 , R1 = R5 , R2 = R4
(3.4)
It is possible to derive a relationship between the design variables α1, α2, β1 and β2
of the singly symmetric 6R foldable ring, and the Denavit-Hartenberg parameters. This
is achieved by solving a series of simple linear equations which arise from the linkage’s
geometry. Start with the link between hinges 6 and 1. The Bricard linkage joints must
lie on a line which passes through pi(0) and is parallel to hˆi(0), where the notation (0)
represents positions and vectors in the deployed configuration, and hˆ represents a unit
vector:
p6 = p6(0) + tl6hˆ6(0)
p1 = p1(0) + tl1hˆ1(0)
Here, tl6 and tl1 are unknown scaling factors. It is apparent that R6 = 0, but also that a61
is non-zero. a61 is perpendicular to both hˆ6(0) and hˆ1(0), so define a new vector of unit
length as:
a61 = hˆ6(0)× hˆ1(0)
The length of a61 is unknown, so a third scaling factor, ta61, is introduced. The governing
equation is given in 3.5.
p6 + ta61a
61 = p1
⇒p6(0) + tl6hˆ6(0) + ta61a61 = p1(0) + tl1hˆ1(0)
(3.5)
This can easily be solved to give tl6, tl1 and ta61, and hence p6, p1 and a61 = |ta61a61|.
Moving on to the next link (between hinges 1 and 2), define:
p2 = p2(0) + tl2hˆ2(0)
as well as:
a12 = hˆ1(0)× hˆ2(0)
63
3.2 Expression in Terms of Denavit-Hartenberg Parameters
Since R1 is non-zero, introduce the unknown tR1 to the governing Equation 3.6.
p1 + tR1hˆ1(0) = p2 + ta12a
12
⇒p1 + tR1hˆ1(0) = p2(0) + tl2hˆ2(0) + ta12a12
(3.6)
From this tl2, tR1 and ta12 can be found, which in turn gives p2, R1 = tR1 and a12 =
|ta12a12|.
Finally, consider the link between hinges 2 and 3 by defining:
p3 = p3(0) + tl3hˆ3(0)
as well as:
a23 = hˆ2(0)× hˆ3(0)
and Equation 3.7.
p2 + tR2hˆ2(0) = p3 + ta23a
23
⇒p2 + tR2hˆ2(0) = p3(0) + tl3hˆ3(0) + ta23a23
(3.7)
From this tl3, tR2 and ta23 can be found, which in turn gives p3, R2 = tR2 and a23 =
|ta23a23|.
The important parameters are:
a61
l
=
1− 4 cos
2 (α1)
2
√
2 sin (2α1) sin (2β1) + (3 cos (2α1)− 1) cos (2β1) + cos (2α1) + 5
a12
l
= 2
sin2 (α1 − α2)
2 cos (2α1) + 4 sin
2 (α1) cos (2α2) + 6
a23
l
=
1− 4 cos
2 (α2)
−2√2 sin (2α2) sin (2β2) + (3 cos (2α2)− 1) cos (2β2) + cos (2α2) + 5
and
R1
l
=
√
2
4 cos (α1)
2
√
2 sin (2α1) sin (2β1) + (3 cos (2α1)− 1) cos (2β1) + cos (2α1) + 5
. . .
−2 (cos (α1) + sin (α1) sin (α2) cos (α2))
cos (2α1) + 2 sin2 (α1) cos (2α2) + 3
R2
l
=
√
2 sec (α2) .
− 4 cos
2 (α2)
−2√2 sin (2α2) sin (2β2) + (3 cos (2α2)− 1) cos (2β2) + cos (2α2) + 5
. . .
+
sin (2α1) sin (2α2) + 4 cos (2α2) + 4 sin2 (α2) cos (2α1) + 8
2 cos (2α1) + 4 sin2 (α1) cos (2α2) + 6
− 1
64
3.3 Examination of Mobility using a Cascade of Homotopies
The twist angles can be simply determined as:
α61 = cos
−1
hˆ6(0), hˆ1(0)
α12 = cos
−1
hˆ1(0), hˆ2(0)
α23 = cos
−1
hˆ2(0), hˆ3(0)
As a numerical example, consider the case of α1 = π/4,α2 = −π/4, and β1 = β2 =
0 (γ = π/2). This can be written in terms of Denavit-Hartenberg parameters for the plane
symmetric case:
a61
l
=
1√
2
a12
l
=
2
3
a23
l
=
1√
2
R1
l
=
2
3
R2
l
= −2
3
α61 =
π
4
α12 =
2π
3
α23 =
3π
4
Figure 3.2 represents this case. A real model with the same parameters is shown during
its folding process in Figure 3.6.
3.3 Examination of Mobility using a Cascade of Homo-
topies
It is possible to construct a set of loop closure equations by defining coordinate systems
attached to each link and then deriving the transfer matrices which describe the transfor-
mation from one coordinate system to the next. This method is illustrated in Chen & You
(2009) and Gan & Pellegrino (2006), where it is used to simulate the motion of closed
loop linkages, and to study their bifurcations. A transfer matrix is typically 4 × 4, and
consists of a 3 × 3 rotation matrix, say R, and a 3 × 1 translation vector, say v. These
parts are arranged as:
T =
R v
0 0 0 1
If a coordinate system is attached to the end of a link in a linkage, then a transfer matrix
can be used to rotate and translate it to the location of the coordinate system attached to
an adjacent link in a single operation. Repeating this operation around a linkage which is
also a closed loop will eventually lead back to the original link. Mathematically, this can
be expressed as:
F = T61T56T45T34T23T12 − I = 0
65
3.3 Examination of Mobility using a Cascade of Homotopies
where Tab defines the transfer between the coordinate system attached to link a to that
attached to b. The coordinate system at each joint is aligned so that the z-axis is aligned
with the hinge axis. Before each translation, the x-axis is rotated such that it points along
the current bar towards the next joint. As there are single degree of freedom connections
between the links, each transfer matrix can be separated into a part which deals only with
rotation about the z-axis, L3, and a part which relates to the unchanging geometry of the
link, TLab (which shifts the coordinate system from the closest end of one hinge to the
closest end of the next), and Tab = TLabL3(θab). The equations above then become:
F = TL61L3(θ61)T
L
56L3(θ56)T
L
45L3(θ45)T
L
34L3(θ34)T
L
23L3(θ23)T
L
12L3(θ12)− I = 0 (3.8)
Explicitly, the transfer matrices for each of the six links of the plane symmetric 6R fold-
able frame are:
TL12 = L1(β2)ML3(π/4)L1(α2 − π/2)
TL23 = L1(π/2− α2)L3(π/4)ML1(−β2)
TL34 = L1(π/2− α1)L3(π/4)ML3(π/4)L1(α2 − π/2)
TL45 = L1(−β1)ML3(π/4)L1(α1 − π/2)
TL56 = L1(π/2− α1)L3(π/4)M(π/4)L1(β1)
TL61 = L1(π/2− α2)L3(π/4)ML3(π/4)L1(α1 − π/2)
(3.9)
where L1 is a rotation about the x-axis, andM defines a translation of length l along each
link:
M =
1 0 0 −l
0 1 0 0
0 0 1 0
0 0 0 1
The single off-diagonal entry in matrix M has a negative sign because the effect of ap-
plyingM to a point in space is to rewrite that point as a location in the basis of the new,
translated coordinate system. Shifting a coordinate system in the positive x-direction
requires the inclusion of a negative term in the (1, 4) location of matrix M . The matrix
Equation 3.8 can be separated into six individual equations which together ensure loop
closure. As in Gan & Pellegrino (2006), the strictly upper triangular part of this ma-
trix equation provides the six independent scalar equations necessary to form a square
66
3.3 Examination of Mobility using a Cascade of Homotopies
system:
F(θ12, θ23, θ34, θ45, θ56, θ61) =
F1,2
F1,3
F1,4
F2,3
F2,4
F3,4
= 0 (3.10)
Once the loop closure equations have been formed, the motion of the linkage can be sim-
ulated using a type of predictor-corrector approach detailed in Gan & Pellegrino (2006)
and Chen & You (2009). One particularly useful by-product of this method is a matrix
whose singular values can be used to examine the linkage’s mobility at each point of the
unfolding process.
The plane-symmetric 6-bar ring can be described as an Overconstrained Mechanism,
or as possessing a geometric degree of freedom. This implies that it does not satisfy the
Kutzbach Criterion (Freudenstein & Maki, 1979), which must be due to some special
feature of the linkage’s geometry, in this case its symmetry. It is possible to determine
mathematically if a linkage is likely to possess a geometric degree of freedom, and if
so, of what degree, and in how many disconnected sets, by using the method of witness
sets described in Sommese et al. (2001a), Sommese & Verschelde (2000) and introduced
in Section 2.5. The method can be used to find curves of solutions through the solution
space.
The loop closure equation can be simplified by assuming that hinge angles reflected
in the plane of symmetry will be equal, as:
θ12 = θ34
θ45 = θ61
Finally, the maximum degree of the resulting polynomial closure equations can be re-
duced by rearrangement into the form of Equation 3.11.
F =L3(θ61)TL34L3(θ12)T
L
23L3(θ12)T
L
12 − . . .
(TL45)
−1L3(−θ56)(TL56)−1L3(−θ61)(TL61)−1L3(−θ12) = 0
(3.11)
which is written in terms of the four remaining unknowns {θ12, θ23, θ56, θ61}. Equation
3.11 can be written in pure polynomial form by replacing the trigonometric functions
of the four unknowns with new variables by setting cos(θij) = Cij and sin(θij) = Sij .
Four elements from the strictly upper triangular part of Equation 3.11 can be chosen, and
67
3.3 Examination of Mobility using a Cascade of Homotopies
augmented with standard trigonometric identities relating the new variables, to construct
a system of equations of the form:
C212 + S
2
12 − 1
C223 + S
2
23 − 1
C256 + S
2
56 − 1
C261 + S
2
61 − 1
F 1,2
F 1,3
F 2,3
F 3,4
= 0 (3.12)
Equation 3.12 defines a relationship between each of the hinge angles. It is a system
of polynomial equations in which the coefficients are written in terms of the 6-bar design
parameters α1,α2, β1, β2 and the bar length l. It has a Mixed Volume (Gao & Li, 2003) of
176, which means there is a tight upper bound of 176 on the number of finite solutions.
If this is, in fact, an over-constrained mechanism, then it can be expected that positive
dimensional solution sets will be present. A positive dimensional solution set is a contin-
uum of solutions which may exist on a line, plane, or higher dimensional manifold. Often,
more than one curve or manifold of solutions will be present in a system of equations. If
these curves do not intersect one-another at any point, they are known as Irreducible Com-
ponents. The appearance of positive dimensional solution sets in the closure equations
of a linkage is a sign that the linkage may actually be mobile. The dimensionality of the
solution set corresponds to the degree of freedom of the linkage. For example, if a one-
dimensional solution set is found, then it is possible that the linkage will be mobile with
a single degree of freedom. Since Equation 3.12 contains four unknowns, it is possible
that there could be as high as a n− 1 = 3-dimensional solution set. It is known a priori,
however, that no three or two-dimensional solution sets are present. After introducing a
single, random complex intersecting hyperplane into the equations (increasing the mixed
volume to 400), and solving the resulting system using standard continuation methods, it
was discovered that Equation 3.12 has a one-dimensional solution set whose witness set
contains 28 elements. This first step also generated a further 246 solutions which do not
lie on a one-dimensional curve of solutions. To determine which of these extra solutions
are actually zero-dimensional geometrically isolated points, a cascade step is required
(Sommese & Verschelde, 2000). The cascade involves gradually removing the intersect-
ing plane, introduced earlier, from the equations by way of a new homotopy. Using this
method a zero-dimensional solution set, also with 28 members, was found. The mem-
68
3.3 Examination of Mobility using a Cascade of Homotopies
bers of the witness set were all found to belong to the same irreducible component which
must, therefore, represent the single mobile path known to exist in the real linkage (an
algebraic curve of degree 28 in the solution space). The cascade process is represented in
Figure 3.5.
400 initial solutions 126 paths to infinity
28 solutions with z = 0
246 remaining solutions
1D witness set
174 path to infinity
72 remaining solutions Filter stage 44 filtered out
28 0D solutions
Cascade step
Use 1D witness
set to perform
membership tests
Figure 3.5: Homotopy cascade used to determine 1D and 0D witness sets for 6R linkage.
It has been shown that the plane-symmetric 6-bar linkage has a single irreducible
component in dimension-1, which has 28 members when the closure equations are posed
as above. Since it is known that this linkage has a single geometric degree of freedom, it
can be stated that this irreducible component of degree 28 is responsible for its mobility.
The fact that a linkage’s closure equations contain a positive dimensional solution set
does not, in general, prove that a linkage will actually possess any mobility, but suggests
that it may be possible. To prove that a linkage does have a degree of freedom would
require showing that there is at least one irreducible component in purely real space, and
that at least part of this component lies in a feasible region of the linkage’s parameters.
Figure 3.6: The folding of a wooden model with α1 = π/4, α2 = −π/4, and hence
α1 = tan−1(1/
√
2), α2 = − tan−1(1/
√
2).
69
3.4 Finding a Feasible Region of Design Parameters
3.4 Finding a Feasible Region of Design Parameters
Only certain combinations of the three design parameters {α1,α2, γ} (as described in
Section 3.1) will lead to a linkage which behaves in a way which is likely to be desirable.
The most fundamental of the requirements of a linkage of the type under consideration
(plane symmetric Bricard foldable frame) are:
• linkage does not bifurcate at any point;
• linkage unfolds continuously and smoothly from closed to open configuration;
• hinge angles are allowed to lie only in the range spanned by the same hinge’s angle
when deployed, and the angle when stowed;
• no two bars intersect during the unfolding process.
The satisfaction of the first three points ensures the satisfaction of the fourth, and so
this fourth point is not considered here. At present it is not clear why this automatic
satisfaction of the fourth point occurs in practice.
Since there are only three design variables, one can be held constant, and a 2-dimensional
plot constructed depicting a feasible space in terms of the other two. Holding γ constant,
a set of feasibility contour lines can be plotted, as in Figure 3.7. The γ dependence of the
feasible region is indicated in Figure 3.8.
Points of note about these feasibility graphs are:
• there is always a plane of symmetry defined by α1 = α2;
• the range of values permissible for α1 and α2 is [−π/2, π/2] (outside this range
proper linkage closure does not occur);
• the range of values permissible for γ is (−π, π];
• plots for the range γ ∈ (−π, 0] can be obtained by using γ = γ0 − π, where γ0 is
in the range (0, π].
The loop closure equations (Equation 3.10) were used as the basis of construction
for each of the contour lines in Figure 3.7. Many combinations of design variables will
lead to a linkage which becomes singular somewhere in its range of movement. These
combinations are marked as regular dashed lines. Some of the dashed lines represent
singularities which occur outside the standard stowed-deployed range of motion (often
a configuration the linkage could only reach if it passed through itself), but they are in-
cluded for completeness. Singularities in the closure equations are of interest primarily
70
3.4 Finding a Feasible Region of Design Parameters
0 /8 /4 3/8 /2
-/2
-3/8
-/4
-/8
0
/8
Į1
Į2
Feasible region based on
singularity limits.
Feasible region based on
singularity, and hinge
directional limits.
Singularity contour.
Chart plane of symmetry.
Boundary of region for
ZKLFKș12 opens with
VDPHVLJQDVș61.
Boundary of region for
which ș23 always has the
same sign.
Figure 3.7: Feasibility map for γ = 5π/8.
0 /8 /4 3/8
/2
-/2-3/8
-/4-/8
0/8
/43/8
/2
/8
/4
3/8
/2
5/8
3/4
7/8
ȖSingularity Free Region
Į2
Į1
Figure 3.8: Variance of singularity free region with γ.
71
3.4 Finding a Feasible Region of Design Parameters
because they indicate that a bifurcation could occur at the point at which the linkage
suddenly gains an extra degree of freedom. The singularity contours of key interest are
those which mark a boundary between linkage designs which move continuously from
stowed to deployed, and those which do not. If the combination of variables which pro-
duce a linkage which becomes singular right at the perimeter of this range can be deter-
mined, then a region of design variable space which produces feasible linkages can be
bounded. Because of the highly singular nature of the loop closure equations at a bifurca-
tion/singularity point (Gosselin & Angeles, 1990), standard predictor-corrector methods
were not suitable for following the singular paths through the design parameter space.
Instead, a method which involved a (variable size) predictor step based on the previous
step, and a subsequent unconstrained minimisation was used. The objective function has
the form:
F = σ5 + |F|
where σ5 is the fifth singular value of the Jacobian of the loop closure equations (zero at
a singularity), and |F| is the norm of the closure equations themselves (Equation 3.10).
Note that it is possible to find the linkage’s singular values by constructing:
K
∆θ12
∆θ23
∆θ34
∆θ45
∆θ56
∆θ61
=
∆x
∆y
∆z
∆θx
∆θy
∆θz
where
K =
p1 × h1 p2 × h2 p3 × h3 p4 × h4 p5 × h5 p6 × h6
h1 h2 h3 h4 h5 h6
The singular values of K can be used in just the same way as those of the Jacobian of
Equation 3.10. Here, [∆x,∆y,∆z,∆θx,∆θy,∆θz]T is the resultant twist of the Bricard
6R plane symmetric linkage.
The other contour lines, defining the boundaries of design for linkages with mono-
directional hinges, were found using path followers which use a predictor step in the
direction of the null space of the Jacobian at the previous point, and a corrector based
simply on Newton’s method.
A more extensive collection of feasibility graphs is included as an appendix.
72
3.5 A Two-Variable Compatibility Equation
3.5 A Two-Variable Compatibility Equation
A loop closure equation based on each of the linkage’s six hinge angles was derived in
Section 3.3. In this section, a similar equation is derived, but only in terms of two of the
hinge angles. This equation will be referred to as a Compatibility Equation, as it ensures
the compatibility of each half of the ring at the plane of symmetry. The derivation of
the compatibility equation is based on the assumption that the linkage is always symmet-
ric about the plane defined by hinges h6 and h3. A compact way of representing this
symmetry is:
Q = [(p6 − p3)× h6] · h3 = 0 (3.13)
This equation can be written entirely in terms of the variable hinge angles θ61 and θ12 (as
well as the fixed design parameters α1,α2 and γ). If one of the hinge angles, say θ61, is
nominated as the driving, or input angle, then Equation 3.13 can be used to find θ12 in
terms of θ61. The other four hinge angles can then be found.
If the bar lengths are labelled simply as l, then the hinge locations in the deployed
configuration can be written as:
p1(0) =
−
l
2
0
0
p2(0) =
l
2
0
0
p6(0) =
−
l
2
l
0
p3(0) =
l
2
l
0
where the midpoint of p1 and p2 has been taken as the origin. Furthermore, hinge unit
vectors can be determined:
hˆ6(0) =
sin β10
cos β1
hˆ3(0) =
sin β20
cos β2
Finally, the alternate hinge angle definitions α1 and α2 can be used to define:
hˆ1 =
−
1√
2
cosα1
− 1√
2
cosα1
sinα1
hˆ2 =
1√
2
cosα2
− 1√
2
cosα2
sinα2
In the following it is critical that h1 and h2 be expressed as unit vectors. The alternative
definitions α1 and α2 have been used here because they allow h1 and h2 to be expressed
as unit vectors in the current axes without the use of a normalising factor dependent
on α1 or α2. This greatly simplifies the process of solving the compatibility equations
73
3.5 A Two-Variable Compatibility Equation
later on.
If the locations of hinges 1 and 2 (p1 and p2) are held fixed in space, then the locations
of hinges 6 and 3 (p6 and p3) can be found by rotating their locations in the deployed
configuration about hinge vectors hˆ1 and hˆ2. To rotate a vector v about a (unit) axis w
by an angle θ:
v = (v ·w)w + (v − (v ·w)w) cos θ + v ×w sin θ (3.14)
If the axis w passes through a point p, and the substitution u = v − p is made, then:
v = (u ·w)w + (u− (u ·w)w) cos θ + u×w sin θ + p (3.15)
Applying Equation 3.15 to the current problem for p1 and p2 gives:
p6 = (u1 · hˆ1)hˆ1 + (u1 − (u1 · hˆ1)hˆ1) cos θ61 + u1 × hˆ1 sin θ61 + p1(0)
p3 = (u2 · hˆ2)hˆ2 + (u2 − (u2 · hˆ2)hˆ2) cos θ12 + u2 × hˆ2 sin θ12 + p2(0)
(3.16)
where u1 = p6(0)−p1(0) and u2 = p3(0)−p2(0). Also introduced are the hinge angles
θ61 and θ12 which each start at zero, and indicate how much hinges 1 and 2 have ‘opened’
during the process of linkage folding. Hinge vectors h6 and h3 also change during the
folding/unfolding process. Applying Equation 3.14 to the problem of finding the hinge
orientations gives:
hˆ6 = (hˆ6(0) · hˆ1)hˆ1 + (hˆ6(0)− (hˆ6(0) · hˆ1)hˆ1) cos θ61 + hˆ6(0)× hˆ1 sin θ61
hˆ3 = (hˆ3(0) · hˆ2)hˆ2 + (hˆ3(0)− (hˆ3(0) · hˆ2)hˆ2) cos θ12 + hˆ3(0)× hˆ2 sin θ12
(3.17)
Using Equation 3.1, is is possible to re-write the definitions for hˆ6 and hˆ3 as:
hˆ6(0) =
2 sinα
1 cosα
1 cos γ − sin γ(cos2 α1 − sin2 α1)
0
cos γ(cos2 α1 − sin2 α1) + 2 sinα1 cosα1 sin γ
hˆ3(0) =
2 sinα
2 cosα
2 cos γ − sin γ(cos2 α2 − sin2 α2)
0
cos γ(sin2 α2 − cos2 α2)− 2 sinα2 cosα2 sin γ
74
3.5 A Two-Variable Compatibility Equation
Now to be consistent, these definitions need to be re-written in terms of α1 and α2.
hˆ6(0) =
2
√
2 sinα1 cosα1 cos γ − sin γ(cos2 α1 − 2 sin2 α1)
0
cos γ(cos2 α1 − 2 sin2 α1) + 2
√
2 sinα1 cosα1 sin γ
/ 1 + sin2 α1
hˆ3(0) =
2
√
2 sinα2 cosα2 cos γ − sin γ(cos2 α2 − 2 sin2 α2)
0
cos γ(2 sin2 α2 − cos2 α2)− 2
√
2 sinα2 cosα2 sin γ
/ 1 + sin2 α2
(3.18)
If Equation 3.18 is substituted into 3.17, and then combined with 3.16 in the compat-
ibility equation (3.13), the final form is achieved. Worthy of note is that the (1 + sin2 α)
terms in the denominator of 3.18 can be multiplied out, leaving a pure polynomial form
of the compatibility equation.
It is also possible to use Equation 3.13 to simulate the motion of the loop. Assume
that the bar connecting hinges 1 and 2 is fixed in space (i.e. the plane of symmetry
moves). Since the position of hinge 6 is being rotated about hˆ1, Equation 3.17 can be
used to decompose h6:
a6 = (hˆ6(0) · hˆ1)hˆ1
b6 = (hˆ6(0)− (hˆ6(0) · hˆ1)hˆ1)
c6 = hˆ6(0)× hˆ1
and thus
hˆ6 = a6 + b6 cos θ61 + c6 sin θ61
hˆ3 = a3 + b3 cos θ12 + c3 sin θ12
The positions of the hinges can also be parameterised as:
q6 = (u1 · hˆ1)hˆ1 + p1(0)
r6 = (u1 − (u1 · hˆ1)hˆ1)
s6 = u1 × hˆ1
leading to:
p6 = q6 + r6 cos θ61 + s6 sin θ61
p3 = q3 + r3 cos θ12 + s3 sin θ12
Substituting these forms into Equation 3.13, and collecting trigonometric terms leads to:
η0 + η1 cos θ12 + η2 sin θ12 + η3 sin θ12 cos θ12 + η4 cos
2 θ12 + η5 sin
2 θ12 = 0 (3.19)
75
3.5 A Two-Variable Compatibility Equation
where ηi can be expressed explicitly in terms of θ61 as well as a6,b6 . . .q6, r6 . . . . The
process can just as easily be reversed to write Equation 3.19 in terms of θ61 with a4,b4 . . .q4, r4 . . .
found by choosing a value of θ12. It can be shown that in fact:
η3 = 0
η4 = η5
If:
l =
η1η2 ± (η0 + η4)
η21 + η
2
2 − (η0 + η4)2
(η0 − η2 + η4)(η0 + η2 + η4)
then Equation 3.19 has the solution:
θ12 = sin
−1(
l√
1 + l2
) (3.20)
Equation 3.20 can be used to find the positions and orientations of hinges 6 and 3. Using
this information, it is possible to reflect in the plane defined by hinges 6 and 3 to find the
positions and orientations of hinges 4 and 5. Hinge angles θ56 and θ23 can be found easily
in terms of the angles between the plane of symmetry and the bars connecting hinges 1
and 6, and 2 and 3. An example of how the hinge angles θ61 and θ12 vary with respect to
one-another during deployment is given in Figure 3.9.
0 /4 /2 3/4
0
/4
/2
3/4
5/4
3/2
ș61
Max. ș61 angle
Max. ș12 angle Fully stowed configuration
Fully deployed configuration
ș12
Figure 3.9: Angle evolution during the deployment of a linkage with parameters α1 = π/4,
α2 = −π/4 and γ = π/2, derived from equation 3.20.
76
3.6 Using a Polyhedral Homotopy to Design the Plane Symmetric Bricard 6R
Foldable Frame
It is also possible to simulate the motion of closed loops numerically (Chen & You,
2009; Gan & Pellegrino, 2006), although this will not be discussed here. One advan-
tage of simulating the motion of linkages numerically is that this can provide more ready
access to information about likely bifurcations (Gan & Pellegrino, 2005; Kumar & Pel-
legrino, 2000) using singular value decomposition (other techniques, such as catastrophe
theory (Lengyel & You, 2004), can also be useful in the identification of bifurcation
points).
3.6 Using a Polyhedral Homotopy to Design the Plane
Symmetric Bricard 6R Foldable Frame
Once an expression for the compatibility equation in terms of α1, α2 and γ has been
obtained, Equation 3.13 can be written as a pure polynomial in terms of new variables
(as in Section 3.3) replacing the set of sines and cosines {Cα1 , Sα1 , Cα2 , Sα2 , Cγ, Sγ}.
The polynomial itself is quite long, and in its fully expanded form consists of 389 dis-
tinct terms, prohibiting any manual manipulation, and making its explicit representa-
tion difficult. The equation can be formed as a black-box function, with inputs x =
{Cα1 , Sα1 , Cα2 , Sα2 , Cγ, Sγ}, and extra parameters {θ61, θ12, l}. The compatibility equa-
tion can be written as:
Q (x, θ61, θ12, l) = 0
If the function evaluates to zero, then the equation is satisfied.
The compatibility equation for the plane symmetric rectangular 6-bar linkage has
been derived in terms of three variables, α1, α2 and γ. All three are angles, and are
considered to be the only design variables for the linkages for the purposes of this section.
Because of the nature of Equation 3.1, it is implicit that the linkage will start as a
rectangular structure with length twice its width, and then fold into a compact configura-
tion in which all the bars are parallel. This is arguably the most desirable characteristic
of the linkage should one intend to use it as a deployable structure. However, one might
like to exercise greater control over the way in which the linkage opens and folds. This
might be desirable in order to minimise the stretch on a flexible sheet attached to the link-
age, or perhaps to confine the dimensions of the linkage to a particular three dimensional
envelope during its opening. The complexity of the equations involved in describing the
motion of the linkage means that only numerical optimisation techniques lend themselves
to any attempt to modify the linkage’s parameters of motion. It is possible, however, to
‘guide’ the linkage on its way from deployed to stowed and vice versa. Since the linkage
77
3.6 Using a Polyhedral Homotopy to Design the Plane Symmetric Bricard 6R
Foldable Frame
has only a single degree of freedom, the specification of the angle between any two ad-
jacent bars is sufficient to completely describe the state of the linkage. It is not possible,
in general, to specify exactly what any of the other angles in the linkage should be at the
same time, as this over-determines the system. One can, however, specify the values of
more than one hinge angle in the linkage during the opening and closing process at a dis-
crete number of positions. For each of these positions, one of the design variables must
be freed up in order to keep the system determined. Since there are only three design
variables, a maximum of three discrete positions may be specified on the linkage’s path.
An appropriate way to specify positions along the opening and closing path is to use
the hinge angles θ61 and θ12 in matched pairs {θ61i, θ12i} for i = 1, 2, 3 to establish a
set of angular precision points through which the linkage must pass. Note that it is not
possible to specify the order in which the precision points are encountered during an
opening/closing run. It is also not possible to determine whether the linkage will self-
intersect during opening/closing. This can only be investigated using simulation.
In choosing to consider the sines and cosines of the variables instead of the variables
themselves, it has become necessary to introduce a set of equations to compensate for
the increase in the number of polynomial variables. This can be achieved in a number of
ways, but a simple way is given in Equation 3.21, preserving polynomial form.
C2α1 + S
2
α1 − 1 = 0
C2α2 + S
2
α2 − 1 = 0
C2γ + S
2
γ − 1 = 0
(3.21)
Design problems can now be solved using the compatibility equation. The particular
type of problem considered here involves using pre-specified parameter sets {θ61i , θ12i}
and then solving for a {Cα1 , Sα1 , Cα2 , Sα2 , Cγ, Sγ} set which satisfies the equations. The
full equation set is given in Equation 3.22.
F =
Q (x, θ611, θ121, l)
Q (x, θ612, θ122, l)
Q (x, θ613, θ123, l)
C2α1 + S
2
α1 − 1
C2α2 + S
2
α2 − 1
C2γ + S
2
γ − 1
= 0 (3.22)
Equation 3.22 is all that is required to form a polyhedral homotopy of the form de-
78
3.6 Using a Polyhedral Homotopy to Design the Plane Symmetric Bricard 6R
Foldable Frame
scribed in Section 2.4. It is a system of polynomial equations in six variables. Each of the
first three equations of 3.22 contains the same set of 389 monomials, which means they
have an identical support with 389 elements. Mathematica can be used to analyse the full
equations and arrange the supports into matrix form. The mixed volume of the supports
is 2352, meaning that the system has at most this many solutions. It is worth noting that
if the variables are placed into homogeneous groups [{Cα1 , Sα1} , {Cα2 , Sα2} , {Cγ, Sγ}],
the system has a Be´zout number of 2400. The proximity of the Be´zout number and the
mixed volume is due to the breadth of monomials present in the first three equations of
the target system. It was found that, in this case, the polyhedral homotopy method ex-
hibited greater numerical stability than multi-homogenisation methods. Because of this,
a polyhedral homotopy was used to solve the system.
Since the system of equations in 3.22 contains more than one equation with the same
structure, that is, equations with the same polynomial structure but different coefficients,
special polyhedral methods were used to simplify the process of constructing a start sys-
tem for solving the target problem. The system is said to have Semi-Mixed Supports
(systems in which every support is unique are said to have Mixed Supports). The first
three equations, representing the compatibility equation but with different coefficients,
are treated as a single equation, but with multiplicity three. The convex hull of the sup-
port of the first three equations (Q1) contains only 102 elements; a significant reduction
on 389. It is these 102 which are dealt with directly when forming the polyhedral ho-
motopy. In the notation of Li (2003), the target equations of 3.22 have n = 6 with
r = 4 : k1 = 3, k2 = 1, k3 = 1, k4 = 1. That is to say, the system is written in terms
of six unknowns, and there are six equations, but the first three have the same polyno-
mial structure, leaving four distinct polynomial types. Also, dim(Q1) = m1 = 102 ,
dim(Q2) = m2 = 3 , dim(Q3) = m3 = 3 and dim(Q4) = m4 = 3. Recall that in
practice, it is better to order the system of supports in terms of size from smallest to
largest. Q1, being the largest support, was placed last when forming the polyhedral ho-
motopy. Computing a binomial start system for the 6-bar linkage can take half an hour
on a 3.16GHz Intel processor with the ordering of Equation 3.22, but only 8 seconds after
the re-ordering.
Using continuation to follow the 2352 start solutions from the binomial start system
to the random coefficient version of the target system results in a full complement of non-
singular finite solutions to track to the real coefficient system. This second continuation
process leaves only ∼500 non-singular finite solutions. These are the solutions of key
interest.
79
3.6 Using a Polyhedral Homotopy to Design the Plane Symmetric Bricard 6R
Foldable Frame
3.6.1 Examples of Solution Runs
Some examples for essentially randomly chosen precision points are given below. In
each of the continuation runs below, the number of non-singular finite solutions was in
the region of 500. What is of interest is how many of those solutions are real. In each of
the following examples, the number of real solutions is given, along with the number of
these which were found to be geometrically meaningful and distinct.
In the first example in Table 3.1, only one solution progresses smoothly from de-
ployed to stowed (this is common), and in this case it has the design parameters:
α1 = −π/4
α2 = π/4
γ = −π/2
This result is not particularly surprising as the precision points were taken from a simu-
lation of a linkage with these design variables.
In Table 3.1, Example #2, four real solutions appeared again, however, this time none
were found to move smoothly from the deployed to stowed configurations.
The marked precision points of the example in Table 3.1, Example # 3, produced
seven distinct real solutions, although again, only one moves along a smooth path from
open to closed. It has the design variables:
α1 = −1.358
α2 = 0.5871
γ = −2.421
The results for the precision points specified in Table 3.1, Example # 4 also show no
practically desirable solutions. This example differs from the others in that the search
was for a set of hinge angles not monotonically increasing in θ12 with respect to θ61. It is
possible that no smooth solutions can be found for such a case.
It is important to remember that the theory of polynomial continuation guarantees
that all solutions satisfying the precision point constraints will be found. The solution
sets given here for these particular examples can be said with confidence to be complete.
80
3.6 Using a Polyhedral Homotopy to Design the Plane Symmetric Bricard 6R
Foldable Frame
Summary of Triple Precision Point Examples
Ex
am
pl
e
#
1
θ pairs
θ61
θ12
=
0.787
0.512
,
2.49
1.04
,
3.02
1.19
No. of real solutions found 40
No. of indep. real solutions 4
0 /4 /2 3/4 5/4 3/2 7/4 2
0
/4
/2
3/4
5/4
3/2
7/4
2
ș pair precision points
Only solution which progresses
unhindered from deployed
to stowed configuration
ș61 (radians)
ș1
2 (
ra
di
an
s)
X Fully stowed
configuration
Ex
am
pl
e
#
2
θ pairs
θ61
θ12
=
0.571
0.370
,
2.35
0.826
,
3.36
1.39
No. of real solutions found 32
No. of indep. real solutions 4
0 /4 /2 3/4 5/4 3/2 7/4 2
0
/4
/2
3/4
5/4
3/2
7/4
2
ș61 (radians)
ș1
2 (
ra
di
an
s)
...Continued on next page
81
3.6 Using a Polyhedral Homotopy to Design the Plane Symmetric Bricard 6R
Foldable Frame
– continued from previous page
Ex
am
pl
e
#
3
θ pairs
θ61
θ12
=
1
0.5
,
2
1
,
3
1.5
No. of real solutions found 44
No. of indep. real solutions 7
0 /4 /2 3/4 5/4 3/2 7/4 2
0
/4
/2
3/4
5/4
3/2
7/4
2
ș1
2 (
ra
di
an
s)
ș61 (radians)
X
Ex
am
pl
e
#
4
θ pairs
θ61
θ12
=
1
0.5
,
2
1.2
,
3
0.7
No. of real solutions found 28
No. of indep. real solutions 3
0 /4 /2 3/4 5/4 3/2 7/4 2
0
/4
/2
3/4
5/4
3/2
7/4
2
ș1
2 (
ra
di
an
s)
ș61 (radians)
Table 3.1: Angle paths for triple precision point examples. Each curve in each example
represents a different linkage design. The θ pair precision points are marked, as is the
location at which a feasible design is fully stowed. Note that the combination of θ61
and θ12 for which a linkage is said to be stowed will be different for each design. In
the examples presented, at most one design was found to actually reach the stowed
configuration.
82
3.7 Deployment of the 6R Foldable Frame
3.7 Deployment of the 6R Foldable Frame
The deployment mechanisms for most feasible designs of the plane symmetric 6R fold-
able frame are likely to be quite simple. The linkage has only a single degree of freedom,
and it is possible that the entire deployment could be driven by applying a torque at a sin-
gle hinge. More likely some redundancy will be included, in the form of spring loaded,
damped hinges installed at more than one location around the frame. For example, driv-
ing hinges 1,2,4 and 5 would, in most cases, lead to very reliable deployment. Including
this redundancy would result in some additional stresses being introduced into the frame
during deployment, and also in the deployed configuration. In this situation an issue
for consideration would be the avoidance of excessive distortion of the deployed frame’s
shape. Damping would also need to be sufficient to negate unwanted impulses being ap-
plied to any device to which the frame is attached, as well as any vibration produced as
bars lock into their deployed positions.
Figure 3.9 shows an example of the relationship between angles θ61 and θ12 during
deployment. Table 3.1 also contains a number of examples. In every case of a feasible
frame design encountered to date, θ12 is a monotonic function of θ61, and vice versa (note
that in Table 3.1, Example #4, the only case in which the θ pairs were not monotonically
increasing, no feasible designs were found). This suggests that in most cases, applying
a constant torque to hinges 1 and 2 (and 4 and 5) is sufficient to drive a frame from the
stowed to deployed configurations.
3.8 Conclusion
The mobility of the singly symmetric 6R foldable ring over-constrained mechanism has
been shown to manifest itself in the linkage’s closure equations as a single irreducible
component in the one-dimensional solution set. A set of ‘feasibility maps’ showing the
regions in parameter space in which the 6R foldable ring exhibits desirable characteris-
tics has been produced. Also, a method of designing such rings by specifying angular
precision points has been demonstrated. It is hoped that these techniques, together, will
provide a useful and practical way of designing singly symmetric 6R foldable rings.
More work needs to be done in examining exactly what happens to a membrane at-
tached to the frame during deployment. A particularly fragile membrane could tear (most
likely near the corner hinges) if overextended, or become too crumpled in the stowed con-
figuration. The exact method of deployment is also an area which has been neglected to
date. Which of the hinges need to be driven, and how a sufficient torque could be applied
83
3.8 Conclusion
at those hinges, are issues which require much more thought and, most likely, experimen-
tation.
In considering the design of a practical folding frame, one would also need to consider
the dynamics of the deployment; the rigidity of the frame both during deployment, and
when fully deployed; the moments necessary to deploy the frame at each hinge location;
the velocities of each of the hinges during deployment; and the volume of the region of
space required in order for the frame to deploy uninterrupted. For space applications, the
stiffness and vibration characteristics are particularly important, especially given that a
deployable structure is likely to constitute a large portion of the satellite/spacecraft, and
could affect its dynamics significantly.
84
4. Regular-Polygonal Foldable Rings
The type of linkage considered in this chapter is a cyclic and equilateral ring (that is, it
displays rotational symmetry about a line passing through the centre of the ring), gen-
erally referred to as a regular polygon. Its purpose is most likely to be the provision of
a frame upon which to stretch a membrane, such as a flexible solar array, or a radar. It
could also be used to support a reflecting antenna (as analysed in Tibert (2002)); and in
such a circumstance might be referred to as a hoop-column antenna (see Figure 4.5).
Much like the precision points specified as part of the point-path synthesis described
in Section 1.2.4, and the internal mechanism angle relationships prescribed in Section
3.6, the design of deployable folding rings in this chapter uses a set of angular ‘precision
points’ to attempt to steer the linkage along a certain path during its deployment. The pre-
scribed precision points in this chapter are not internal angles, but rather are orientation,
or Euler, angles used to describe the attitude of the bars of the ring as the ring deploys.
This type of angle specification is a powerful tool, in that it allows a designer to select
the exact shape of the ring at a limited number of positions during deployment. This pro-
cess involves solving some sometimes quite large systems of equations for several design
variables at a time. It is possible that a number of different ring designs could satisfy
the constraints set by the designer; a situation which manifests itself in the appearance
of multiple solutions to the afore-mentioned equations. In general, it cannot be known
a priori how many, if any, solutions exist to a given problem, but the use of numerical
continuation can guarantee that every one of these solutions will be found.
4.1 Existing Designs
Two similar structures: a deployable ring antenna designed by the Harris corporation in
the early 1980’s, and a large deployable spoked wheel designed by Astro Research cor-
poration in the mid 1970’s, provide good examples of how deployable rings can be used
to solve volume minimisation problems, especially in space applications. Both Harris,
and Astro Research prepared their designs as part of contracting work for NASA. Both
85
4.1 Existing Designs
designs also provide good insight into the ways in which such frames can be deployed
and held rigid in the deployed configuration.
4.1.1 A Hoop-Column Antenna
The hoop-column antenna design, proposed and constructed by Harris, illustrates one
of the primary uses of deployable rings; a framework for a large antenna. Because dish
antennas require a reflective mesh surface with a specific shape, a deployable antenna will
consist not only of a central column and circumferential hoop (the element of primary
interest in this chapter), but also a pretensioning mechanism (usually attached to the
underside of the mesh), in this case called surface shaping cords.
Most sources detailing the development of deployable rings, or hoop-column anten-
nas, suggest some form of column/cable-release mechanism to generate controllable, sta-
ble deployment. Quite often, the central column is a telescopic or deployable mast itself.
An early concept of how such a structure might deploy is shown in Figure 4.1, while a
top view of a later 15 metre hoop-column design is shown in Figure 4.2. This particular
model was constructed as a proof of concept for a later design to measure 100 metres
in diameter. This design is interesting as, during deployment, it seems all joints are
constrained to lie in a cylindrical manifold of slowly increasing radius (see Figure 4.3).
Extra controllability is achieved by a complicated combination of pulley systems between
joints, and active and passive hinges.
4.1.2 A Spoked Wheel to Deploy Large Surfaces
Deployable rings can also be used to support membranes which do not require any curva-
ture. This includes flexible solar arrays, and phased array antennas. Two similar designs
for deployable solar arrays were proposed, first in a conference (Crawford et al., 1974),
and then in a report (Crawford et al., 1975). Both designs form a rigid regular polyhedron
when fully deployed, upon which a flexible solar array could be mounted. When stowed,
both designs fold into a compact bundle. The so called ‘two-hinge’ design receives most
attention in the body of the text of the report, but a basic description of the dynamics of
a variant in which each bar is joined to its neighbour using only a single hinge is given
in the appendix. In the two-hinge case, adjacent bars are connected to one another by an
intermediate block with one hinge at each end, leading to the ‘two-hinge’ description. A
representation of the two hinge design is shown in Figure 4.4.
The one-hinge version poses a more complex design problem, as compatibility con-
straints are tighter when only one hinge is used to join each of the bars in the ring. Only
86
4.1 Existing Designs
Figure 4.1: A deployable hoop-column concept, developed by the Harris Corporation. Notice
how the bars making up the outer ring structure are stored vertically, but rotate into
the horizontal plane before deploying, staying in the horizontal plane the whole
time. Reproduced from Tibert (2002).
Figure 4.2: Top view of a 15 metre hoop-column design, from Harris-Corporation (1986).
87
4.1 Existing Designs
Figure 4.3: Deployment process of a hoop-column ring, from Harris-Corporation (1986).
Figure 4.4: A representation of the two hinge spoked wheel design (from Crawford et al.
(1975)).
an even number of bars is permitted, say N . N is quite often greater than seven, in-
dicating that several degrees of freedom will be present in the ring. In Crawford et al.
(1975) it was proposed that the deployment be controlled by use of a number of cables,
or ‘spokes’, to constrain these extra degrees of freedom. A real ring whose deployment
88
4.2 Ring Geometry and Compatibility Equations
is controlled by a system of cables is shown in figure 4.5. The deployment of a 10-bar
Figure 4.5: A deployable antenna (courtesy of the Toshiba Corporation and Sergio Pellegrino)
of the type suggested by Crawford et al. This is the two-hinge version of the
deployable ring.
single-hinge deployable ring is shown in Figure 4.6.
Because any deployable ring with more than seven bars will have more than one
degree of freedom, it is necessary to control the deployment using some additional mech-
anism. Figure 4.7 shows a fully deployed 8-bar deployable ring supported by a spoked
wheel structure. The same ring, partially deployed, is shown in Figure 4.8.
4.2 Ring Geometry and Compatibility Equations
For the remainder of the chapter, the focus will be on single hinge (orNR, whereN is the
number of elements of the ring) versions of deployable rings, much like those presented in
the second example of Section 4.1. Because of its simplicity, the single hinge ring has the
potential to exhibit greater reliability. It also presents a more interesting design problem
89
4.2 Ring Geometry and Compatibility Equations
Figure 4.6: The deployment of a 10-bar single-hinge ring (from Crawford et al. (1975)). The
multiple degrees of freedom are not apparent here as the deployment has been
carefully controlled, and the linkage supported by the table underneath.
Figure 4.7: A fully deployed 8-bar deployable ring (from Crawford et al. (1974)). The ring is
held rigid by the spoked wheel structure to which it is attached.
as the number of design variables is quite limited, naturally steering the search for designs
in the direction of more elegant solutions. It is possible, however, that the versatility of
the deployable ring will be limited by the restriction toNR linkages only, with these types
90
4.2 Ring Geometry and Compatibility Equations
Figure 4.8: A partially deployed 8-bar deployable ring (from Crawford et al. (1974)). The solar
cell gores visible here unravel from the rim segments as the ring undergoes
deployment. The source document contains a calculation of the tension arising in
the gore as a result of deployment.
lending themselves more to the support of flat membranes than to contoured surfaces.
4.2.1 Original Derivation of Ring Geometry Based on Triangular
Cross-Sectioned Bars
The single-hingeNR version of the regular-polygonal deployable ring can be designed in
quite an elegant manner by making the bar cross-section an isosceles triangle. In Figure
4.6, the bars are observed to fit very closely together in the first image because the angle
marked α1 is set to be:
α1 =
360◦
N
More detailed geometry is given in Figure 4.9. Once the angle α1 has been set, the other
two internal angles can be found as:
α2 = 90
◦ − α1
2
The ends of each of the bars are cut at an angle of 180◦/N so that they fit together in the
deployed position. It can be shown that, at the end faces of each bar, the double internal
91
4.2 Ring Geometry and Compatibility Equations
N
Figure 4.9: Geometry of single-hinge NR foldable ring with triangular cross-sectioned bars
(from Gan & Pellegrino (2006)).
angles are:
α3 = tan
−1
cos2(α1/2)
sin(α1/2)
The hinges are mounted on the inside and outside upper faces of the ring alternatively.
The aim of the subsequent sections is to present a more comprehensive process for
design, based on the assumption that the cross section of the bars is either circular, or
irrelevant. The particularly neat and compact stowed configuration of the triangular cross-
sectioned bar design is sacrificed for greater control over the deployment path.
4.2.2 Expression of the Hinge Vectors in Local Bar Coordinates
A top view of the one-hinge regular-polygonal deployable ring (sometimes referred to
as a Hedgepeth Ring) is given in Figure 4.10. The highlighted bar also has its hinges
shown as hl on the left and hr on the right, where the subscripts l and r denote ‘left’
and ‘right’ respectively. To understand the motion of the entire ring, one need only focus
on any individual bar, referred to as the ‘design’ bar from now on. This bar can then
be reflected N − 1 times about the indicated planes of symmetry to obtain the rest of
the ring. It is necessary that the hinge vectors of this design bar (and hence those of
all the other bars) remain in the planes shown during deployment. A front view of the
highlighted (design) bar is shown in Figure 4.11. The hinges are fixed to the end of each
bar. An obvious question is: is it always possible to find a bar orientation such that the
hinges at the ends of the bar lie exactly in each of the two planes shown in Figure 4.11,
and if this is possible, how many different orientations which achieve this are there? It
92
4.2 Ring Geometry and Compatibility Equations
(2S/N)
Y
X
hl
hr
Figure 4.10: Top view of regular-polygonal foldable ring (in mid-deployment) with N = 10.
Global coordinates are indicated.
XY
Z
(2S/N)
hl
hr
Figure 4.11: Front view of individual bar in regular-polygonal ring with global coordinates
indicated.
is not immediately clear that there are not an infinite number of orientations. The benefit
of using polynomial continuation in this design problem is that it can be guaranteed that
every one of the possible solutions will be found (including positive dimensional sets
93
4.2 Ring Geometry and Compatibility Equations
indicating that there are an infinite number), so they can be enumerated with confidence.
The next stage is to determine an appropriate set of design variables. Attention is
restricted to the highlighted bar shown in Figures 4.10 and 4.11. The first parameter one
might consider is the bar length, but this can be neglected without any loss of generality.
To allow for maximum generality, the hinges attached to each end of the design bar may
have any orientation with respect to the local coordinates of the bar. Figure 4.12 shows
how the hinge vectors are defined in the local coordinates of the bar. Each hinge is
z
hl
hr
Il
Tl Tr
Ir
y
x
Figure 4.12: Regular-polygonal ring bar shown in local coordinates with hinge definitions.
assigned a ‘longitude’ φ, and a ‘lattitude’ θ. Using l and r again to denote the left and
right hand ends of the bar; the four design variables are {φl, θl,φr, θr}. The left and right
hinges can thus be constructed as unit vectors (in local coordinates attached to the bar):
hl =
cos(θl)sin(θl) sin(φl)
− sin(θl) cos(φl)
hr =
cos(θr)sin(θr) sin(φr)
− sin(θr) cos(φr)
(4.1)
4.2.3 Constructing the Two Compatibility Equations
In this section, a system of equations is derived which constrains each link to remain
within its own segment, and also requires its orientation to be such that the hinge vectors
94
4.2 Ring Geometry and Compatibility Equations
attached to each end of the link always lie within the two partitioning planes of symmetry.
In this way, such a system enforces the rotational symmetry of the complete ring. In
practice, these constraints would be administered by a carefully controlled system of
cables, or other such mechanism. The term compatibility is used because the purpose of
the equation is to enforce certain constraints at planes of symmetry, which then ensures
that each link is compatible with the next (across the plane of symmetry).
As the ring is deployed, each bar undergoes a rotation. Define a rotation matrix R in
terms of the standard single-axis rotation matrices:
L1 =
1 0 00 cos(φ) − sin(φ)
0 sin(φ) cos(φ)
L2 =
cos(θ) 0 sin(θ)0 1 0
− sin(θ) 0 cos(θ)
L3 =
cos(ψ) − sin(ψ) 0sin(ψ) cos(ψ) 0
0 0 1
R = (L1L2L3)
T
If the bar undergoes a rotation R, then so do the hinge vectors at each of its ends. Now
assume that the two planes shown in Figure 4.11 have normal vectors nl on the left and
nr on the right. It is now possible to write the two governing equations for the motion of
the bar (based on the fact that each hinge must remain in its respective plane) as:
Rhl , nl = 0
Rhr , nr = 0
(4.2)
Together, these equations form the compatibility equations for the ring. As depicted, the
plane normals will have the form:
nl =
cos(
π
N )
− sin( πN )
0
nr =
cos(
π
N )
sin( πN )
0
in global coordinates.
The two relationships in Equation 4.2 are written in terms of three variables; a roll
95
4.3 Using the Compatibility Equations to Design the Ring
(φ), a pitch (θ) and a yaw (ψ).
4.3 Using the Compatibility Equations to Design the Ring
The goal in this section is to arrive at a reliable design method for a deployable folding
ring. Some design criteria which might naturally arise are:
• ring folds into a compact bundle with all bars parallel;
• ring opens out into a regular polygon with number of sides equal to the number of
bars (such that it might support a circular sheet of photovoltaic cells, radar patches
etc.);
• the orientation of the bars during deployment is pre-specified at several points;
• the bars do not self intersect during deployment.
All but the last of these points can be addressed using continuation to design the ring.
The basic details of the mechanism layout (number of bars, connectivity etc.) have es-
sentially been set by choosing to focus on one-hinge regular-polygonal deployable rings
only. Next, some features of the mechanism which can be varied to alter the kinematics
(the design variables) need to be identified (in this case the four hinge orientation an-
gles {φl, θl,φr, θr}). Following this, the most appropriate way to use continuation in the
design process must be chosen. In this chapter, it was decided to specify a number of
link attitudes (equal to the number of design variables) at various stages in the ring’s de-
ployment. A set of compatibility equations describing the linkage in the desired attitudes
was then constructed, and solved for the design variables which are required to force the
mechanism to attain these positions. The outline of the process is:
1. determine geometric constraints on bars/links in the ring (eg: planes of symmetry);
2. identify the plausible design variables;
3. derive the compatibility equation(s);
4. find the polyhedral structure of the compatibility equation(s), and establish a start
system with the same structure for use in continuation;
5. determine appropriate inputs to the compatibility equations to achieve the required
design criteria.
96
4.3 Using the Compatibility Equations to Design the Ring
The compatibility equations (4.2) are written in terms of φ, θ and ψ, as well as the four
design variables φl, θl, φr and θr. In this case there are two fundamental compatibility
equations, three input (orientation) angles and four design variables. There are a number
of approaches which may be taken to using the compatibility equations. The main guiding
principle is that four independent equations must be formed in order to solve for all four
of the design variables. Three different methods will be explored in this section:
1. use the two compatibility equations in their current form, and use two sets of input
angles to form two pairs of the compatibility equations, resulting in the required
four equations;
2. combine the two compatibility equations into one by eliminating the ψ input angle.
This allows for four sets of the remaining inputs {θ,φ} to be used to generate the
required four versions of the reduced single compatibility equation;
3. combine the two compatibility equations into one by eliminating the φ input angle.
A mixture of {θ,φ} and {θ,ψ} type reduced compatibility equations is used to
design the ring.
4.3.1 Using the Original Form of the Compatibility Equations
It is possible to choose two sets of orientation (Euler) angles {φ1, θ1,ψ1} and {φ2, θ2,ψ2},
and then use polynomial continuation to arrive at a set of design variables which describe
a bar/ring systemwhich will pass through the prescribed orientations at some point during
the ring’s deployment. This process is similar, in a way, to that applied to the point-path
synthesis problem described in Section 1.2.4, except that in this case, sets of pre-specified
bar orientations take the place of precision points. It is also similar to the internal-angle
precision point example of Section 3.6, except that the angular precision points in this
chapter are specified in global coordinates.
As is common when using continuation, the sines and cosines of the design variable
angles are used instead of the angles themselves. This doubles the number of unknowns,
and requires the addition of equations of the form C2x + S2x − 1 = 0. The full set of
97
4.3 Using the Compatibility Equations to Design the Ring
equations is given below.
F =
R(φ1, θ1,ψ1)hl(Cφl , Sφl , Cθl , Sθl , Cφr , Sφr , Cθr , Sθr) , nl(N)
R(φ2, θ2,ψ2)hl(Cφl , Sφl , Cθl , Sθl , Cφr , Sφr , Cθr , Sθr) , nl(N)
R(φ1, θ1,ψ1)hr(Cφl , Sφl , Cθl , Sθl , Cφr , Sφr , Cθr , Sθr) , nr(N)
R(φ2, θ2,ψ2)hr(Cφl , Sφl , Cθl , Sθl , Cφr , Sφr , Cθr , Sθr) , nr(N)
C2φl + S
2
φl
− 1
C2θl + S
2
θl
− 1
C2φr + S
2
φr − 1
C2θr + S
2
θr − 1
= 0
This system has a total degree of 28 = 256 in the eight unknowns. However, it has a
mixed volume of only 16.
Without knowing any more about the system, it is now possible to design a ring
which will fold up into a tight bundle, and deploy into the shape of a regular polygon,
as in Figure 4.13. There are two critical phases to the deployment; fully deployed and
1
2
4
3
Figure 4.13: Deployment/stowing sequence of a 10-sided regular-polygonal ring (hinge vectors
of design bar shown).
fully stowed (depicted as positions 1 and 4 in Figure 4.13). At each of these phases, the
‘design’ bar (which then gets reflected several times to form the rest of the ring) has a
particular attitude. When it is deployed, it has a pitch (θ) of 0◦, and a yaw (ψ) of 0◦. The
roll (φ) is irrelevant. When the bar is stowed, it has a pitch of 90◦, and both roll and yaw
98
4.3 Using the Compatibility Equations to Design the Ring
are irrelevant. As an example, choose the following set of angles (in radians): φ1θ1
ψ1
=
00
0
;
φ2θ2
ψ2
=
π
2
π
2
0
(4.3)
This set gives sixteen real solutions, which all reduce to the same hinge vectors. One
solution is:
φl
θl
φr
θr
=
−18◦
−84.3◦
−162◦
−95.7◦
⇒ hl =
0.09990.3075
0.9463
, hr =
−0.09990.3075
−0.9463
Notice the obvious symmetry in the hinge vectors here, with the magnitude of each com-
ponent being equal left and right, and only the sign changing. As it happens, these are
the same hinge vectors which arise using the design method described in Section 4.2.1.
Since this is the only solution to appear in the continuation process, it can be said that the
isosceles triangle based design is the only one which satisfies these particular deployed
and stowed configuration requirements. The attitude of the design bar during closure is
shown in Figure 4.14, while a sequence of the ring moving from the deployed to stowed
configuration is given in Figure 4.15.
It is, of course, possible to choose other sets of input angles, but the set described
above illustrates how continuation can be used quite simply to design a practical ring. As
a further example, consider the set of input target angles: φ1θ1
ψ1
=
0.50.2
0.25
;
φ2θ2
ψ2
=
0.91.3
0.7
(4.4)
The angular progression for the ring designed with these inputs is shown in Figure 4.16.
Notice that the ring never reaches the fully stowed (θ = π/2) nor fully deployed (θ = 0)
configurations. This example provides a good insight into the nature of the design prob-
lem. When using a similar angle/orientation-based design approach in Section 3.6, the
rectangular shape of the deployed linkage was implicit in the compatibility equation,
that is: setting the driven angle θ61 to zero results in a system for which θ12 = 0 (the
dependent angle) is always a solution. Bar pitch (θ) is usually used as the driven input in
this chapter. Setting θ = 0 does not guarantee that the yaw angle, ψ, will also be zero,
99
4.3 Using the Compatibility Equations to Design the Ring
S S S S
S
S
T (rad)
I a
nd
\
(r
ad
)
I targets
\ targets
I
\
Fu
lly
D
ep
lo
ye
d
Fu
lly
S
to
w
ed
Figure 4.14: Example of a ring design using the original compatibility equations (N = 10), and
the angle targets given in Equation 4.3.
Figure 4.15: First example of a fully feasible ring moving from deployed to stowed positions
(clockwise from bottom left). This is identical to the ring which would result from
the design methods of Section 4.2.1. It is based on the targets of Equation 4.3, and
its angular progression is shown in Figure 4.14.
and since θ = ψ = 0 is a necessary condition for the regular-polygonal foldable ring to
be fully deployed, such a relationship must be specified explicitly as part of the design
process. This is why the targets of Equation 4.3 produce a feasible ring design, while
100
4.3 Using the Compatibility Equations to Design the Ring
S S S S
S
S
S
S
T (rad)
I a
nd
\
(r
ad
)
I targets
\ targets
I
\
Figure 4.16: Second example of a ring design using the original compatibility equations
(N = 10), and the angle targets given in Equation 4.4.
those of Equation 4.4 do not.
4.3.2 Using {φ , θ} to Specify Bar Orientation
Sometimes, it is beneficial to reduce the description of the motion of a deployable struc-
ture to a single compatibility equation, as this reduces the amount of information which
must be specified a priori in a design using continuation. In this section, it is shown that
only two of the three input angles need be specified to define a target point, leaving the
third free. To combine the two compatibility equations into one, one of the three vari-
ables; φ, θ or ψ must be eliminated. Although the design of a feasible deployable ring
using the methods described here must involve the explicit specification of the deployed
state constraint θ = ψ = 0, it is nonetheless interesting to observe what happens when
the dependence on ψ is removed altogether.
Assume that Cx = cos(x) and Sx = sin(x). The equations in 4.2 can be written as:
ml1 ml2
mr1 mr2
Cψ
Sψ
=
0
0
101
4.3 Using the Compatibility Equations to Design the Ring
where:
ml1 ml2
mr1 mr2
= M(φ, θ,φl, θl,φr, θr)
For this system to have a solution, then
f˜ ≡ det (M) = ml1mr2 −ml2mr1 = 0 (4.5)
(this particular elimination technique was taken from Crawford et al. (1975)). Equation
4.5 is a single compatibility equation for the system, and is written completely in terms
of the angular inputs φ and θ, as well as the design variables {φl, θl,φr, θr}. The equation
has 9 terms. This equation can be used to define a necessary relationship between φ and
θ at a point in the bar’s motion, without specifying anything about the third angular input,
ψ.
Once again, eight equations form the continuation target set. Four sets of pairs of
input angles can be selected: {φi, θi} i = 1, . . . , 4. These sets form the target system as:
F =
f˜ ({φ1, θ1} , {Cφl , Sφl , Cθl , Sθl , Cφr , Sφr , Cθr , Sθr})
f˜ ({φ2, θ2} , {Cφl , Sφl , Cθl , Sθl , Cφr , Sφr , Cθr , Sθr})
f˜ ({φ3, θ3} , {Cφl , Sφl , Cθl , Sθl , Cφr , Sφr , Cθr , Sθr})
f˜ ({φ4, θ4} , {Cφl , Sφl , Cθl , Sθl , Cφr , Sφr , Cθr , Sθr})
C2φl + S
2
φl
− 1
C2θl + S
2
θl
− 1
C2φr + S
2
φr − 1
C2θr + S
2
θr − 1
= 0
This system has a total degree of 44.24 = 4096, but a mixed volume of only 96, indicating
that the vast majority of the solutions are at infinity. Typically, all 96 solutions of the
target system are non-singular and geometrically isolated.
As an example, consider the target angles (again in radians):
φ1
θ1
=
0.05
0.1
;
φ2
θ2
=
0.1
0.3
;
φ3
θ3
=
0.3
0.7
;
φ4
θ4
=
0.5
1.2
(4.6)
which produces the result shown in Figure 4.17. Notice that in this case there are two
separate φ paths which hit all of the input angle targets, although neither design could be
said to be feasible.
102
4.3 Using the Compatibility Equations to Design the Ring
S S S S
S
S
S
S
T (rad)
I a
nd
\
(r
ad
)
I targets
I (design #1)
I (design #2)
\ (design #1)
\ (design #2)
Figure 4.17: Example of system designed with four {φ, θ} specifications (N = 10), and the
angle targets given in Equation 4.6.
Next, alter the target angles slightly to include one target pair at θ = π/2:
φ1
θ1
=
0.05
0.1
;
φ2
θ2
=
0.1
0.3
;
φ3
θ3
=
0.3
0.7
;
φ4
θ4
=
0.5
π
2
(4.7)
with the result shown in Figure 4.18. In this case there are actually four separate φ paths
which hit the first three targets, but then none hit the fourth at θ = π/2. This illustrates
an interesting feature. It happens that:
∂f˜
∂φ
θ=π2
= 0
This means that the specification of any value of φ is irrelevant when θ = π/2 as the
equation exhibits no sensitivity to φ. Any value of φ4 in the example above will produce
the same results as those shown in Figure 4.18. The benefit of still including an equation
with a target pair at θ = π/2 is that it encourages real solution paths which travel all the
way from θ = 0 to θ = π/2, producing a ring which can be fully stowed. If it is not
required that a ring be fully stowable, then a target at θ = π/2 is not necessary.
Because the reduction from two compatibility equations to one involved the elimi-
nation of the yaw orientation (ψ) in this section, all control over this variable was relin-
103
4.3 Using the Compatibility Equations to Design the Ring
S S S S
S
S
S
S
T (rad)
I a
nd
\
(r
ad
)
I targets
I (design #1)
I (design #2)
I (design #3)
I (design #4)
\ (design #1)
\ (design #2)
\ (design #3)
\ (design #4)
Figure 4.18: Second example of system designed with four {φ, θ} specifications (N = 10), and
the angle targets given in Equation 4.7.
quished. Using the remaining two variables, it was possible to generate a number of ring
designs which satisfied the four {φ, θ} precision points, and even to ensure that some
of these designs would stow properly by specifying a precision point at θ = π/2, but
none were found to deploy to the proper shape. To ensure both proper deployment and
closure, as well as specifying a number of angular precision points between these two
configurations, the system of equations used in this section needs to be modified slightly.
4.3.3 Using {θ , ψ} to Specify Bar Orientation
In this section, the two original compatibility equations are combined by way of the
elimination of the variable φ. The power of this reduction is that it allows the yaw angle
to be specified at a particular pitch angle. This is particularly useful for ensuring that the
ring forms a regular polygon when fully deployed by enforcing a zero yaw angle at zero
pitch (fully deployed). The elimination of the angle φ from the governing Equations 4.2 is
a little more involved than the elimination of ψ, but demonstrates nicely the way in which
new unknowns can be introduced to pose a compatibility equation in pure polynomial
form.
104
4.3 Using the Compatibility Equations to Design the Ring
Start with the left hinge constraint, and condense its notation as follows:
Rhl , nl = wl0 + wl1Cφ + wl2Sφ = 0
The wli terms represent combinations of trigonometric functions of the input angles θ and
ψ, and the design variables. The explicit expressions are omitted for brevity. Next, make
the substitution Cφ = m and Sφ =
√
1−m2, which after rearranging gives:
(w2l1 + w
2
l2)m
2 + 2wl0wl1m+ w
2
l0 − w2l2 = ζ2m2 + ζ1m+ ζ0 = 0
where
ζ2 = w
2
l1 + w
2
l2
ζ1 = 2wl0wl1
ζ0 = w
2
l0 − w2l2
Similar treatment of the equation for the right hinge leads to a second quadratic in m of
the form:
ξ2m
2 + ξ1m+ ξ0 = 0
Solving each quadratic form and equating the results in:
−ζ1 ±
ζ21 − 4ζ0ζ2
2ζ2
=
−ξ1 ±
ξ21 − 4ξ0ξ2
2ξ2
(4.8)
At this stage, introduce the new unknowns:
Γ2 = ζ21 − 4ζ0ζ2
Ω2 = ξ21 − 4ξ0ξ2
If these new variables are substituted into Equation 4.8, then the compatibility equation
system can be written as:
f˘ ≡ ξ2 (Γ− ζ1)− ζ2 (Ω− ξ1) = 0
and
Γ2 − ζ21 + 4ζ0ζ2 = 0
Ω2 − ξ21 + 4ξ0ξ2 = 0
which are all pure polynomials written completely in terms of the angular inputs ψ and
θ, as well as the design variables {φl, θl,φr, θr}.
105
4.3 Using the Compatibility Equations to Design the Ring
Clearly it is going to be more computationally expensive to specify design precision
points in terms of {θ,ψ} pairs than {φ, θ} pairs, as the number of design variables, and
hence equations, will increase by two for each pair. As a compromise, a system of target
equations which are a combination of the {φ, θ} and {θ,ψ} based compatibility equations
will be used:
F =
f˜ ({φ1, θ1} , {Cφl , Sφl , Cθl , Sθl , Cφr , Sφr , Cθr , Sθr})
f˜ ({φ2, θ2} , {Cφl , Sφl , Cθl , Sθl , Cφr , Sφr , Cθr , Sθr})
f˜ ({φ3, θ3} , {Cφl , Sφl , Cθl , Sθl , Cφr , Sφr , Cθr , Sθr})
f˘ ({ψ1, θ4} , {Cφl , Sφl , Cθl , Sθl , Cφr , Sφr , Cθr , Sθr})
Γ2 − ζ21 + 4ζ0ζ2
Ω2 − ξ21 + 4ξ0ξ2
C2φl + S
2
φl
− 1
C2θl + S
2
θl
− 1
C2φr + S
2
φr − 1
C2θr + S
2
θr − 1
= 0
This system has an impressive total degree of 43.7.8.8.24 = 458752, but a mixed volume
of only 768. Using this system, it is possible to specify what the yaw angle should be at
one particular pitch angle, as well as what the roll should be at a further three pitches.
This gives a very large degree of control over the motion of the ring.
As an example, consider the target angles:
φ1
θ1
=
3π
16
3π
8
;
φ2
θ2
=
π
8
π
4
;
φ3
θ3
=
π
16
π
8
;
ψ1
θ4
=
0
0
(4.9)
This generates the paths shown in Figure 4.19. One of the two separate designs shown
here which hit the various targets, actually gets quite close to full closure at θ = π/2
by chance, but just fails to achieve full closure. Notice, however, that the ψ paths pass
through ψ = 0 at full deployment, which is very likely to be a desirable design criterion
for the ring. To actually ensure full closure, one of the target equations needs to specify
θ = π/2, as in:
φ1
θ1
=
−
π
2
;
φ2
θ2
=
0.5
π
3
;
φ3
θ3
=
0.25
π
6
;
ψ1
θ4
=
0
0
(4.10)
which results in the two separate ring designs shown in Figure 4.20. While both designs
106
4.3 Using the Compatibility Equations to Design the Ring
S S S SS
S
S
S
S
S
T (rad)
I a
nd
\
(r
ad
)
I targets
\ targets
I (design #1)
I (design #2)
\ (design #1)
\ (design #2)
Figure 4.19: Example of system designed with three {φ, θ} specifications and one {θ,ψ}
(N = 10), and the angle targets given in Equation 4.9.
reach a fully stowed position with θ = π/2, only one of the two designs starts with ψ = 0
in the deployed position (labelled as design # 1), so only one completely satisfies the
design requirements. This feasible design is represented in a sequence showing the ring
moving from the deployed to stowed position in Figure 4.21. The ring represented in
Figure 4.21 has the hinge vectors:
φl
θl
φr
θr
=
136.78◦
−96.80◦
172.78◦
−94.64◦
⇒ hl =
−0.1184−0.6800
−0.7236
, hr =
−0.0809−0.1253
−0.9888
Once again, the value of φ1 specified is irrelevant since f˜ is completely insensitive to
φ when θ = π/2. In this case, what has been designed is a completely functional ring
which has all bars parallel in its fully stowed state, and forms a regular polygon when
deployed.
107
4.4 Simulating the Ring’s Motion
S S S SS
S
S
S
S
S
T (rad)
I a
nd
\
(r
ad
)
I targets
\ targets
I (design #1)
I (design #2)
\ (design #1)
\ (design #2)
Figure 4.20: Second example of system designed with three {φ, θ} specifications and one
{θ,ψ} (N = 10), and the angle targets given in Equation 4.10.
Figure 4.21: Feasible ring design for target set of Equation 4.10. Its angular progression is
labelled as design # 1 in Figure 4.20.
4.4 Simulating the Ring’s Motion
A number of ways of specifying bar attitudes during deployment (neglecting {φ,ψ} pair
specification for now) have been established. It is now necessary to be able to simulate
the motion of the bar (and hence the entire ring) accurately in order to verify any results
108
4.4 Simulating the Ring’s Motion
which might be obtained using a polynomial continuation design approach. Any one of
the three rotation angles {φ, θ,ψ} could be chosen as an input, with the other two being
solved by way of the two Equations 4.2. Selecting the pitch angle θ as the input happens
to simplify the simulation process.
The two equations in 4.2 can be written as:
(al + blCφ + clSφ)Cψ + (dl + elCφ + flSφ)Sψ = 0
(ar + brCφ + crSφ)Cψ + (dr + erCφ + frSφ)Sψ = 0
where specifically:
al = CθCθlCδ
bl = CφlSθSθlCδ − SθlSφlSδ
cl = SθSθlSφlCδ + CφlSθlSδ
dl = CθCθlSδ
el = SθlSφlCδ + CφlSθSθlSδ
fl = −CφlSθlCδ + SθSθlSφlSδ
ar = CθCθrCδ
br = CφrSθSθrCδ + SθrSφrSδ
cr = SθSθrSφrCδ − CφrSθrSδ
dr = −CθCθrSδ
er = SθrSφrCδ − CφrSθSθrSδ
fr = −CφrSθrCδ − SθSθrSφrSδ
This can be written in matrix form as:
al + blCφ + clSφ dl + elCφ + flSφ
ar + brCφ + crSφ dr + erCφ + frSφ
Cψ
Sψ
=
0
0
(4.11)
Again, the determinant of the matrix above must be zero in order for a solution to exist.
The determinant of the matrix can be written as:
η0 + η1Cφ + η2Sφ + η3C
2
φ + η4S
2
φ + η5CφSφ = 0 (4.12)
109
4.5 Conclusions
where specifically:
η0 = aldr − ardl
η1 = −dlbr + drbl − arel + aler
η2 = −crdl + cldr − arfl + alfr
η3 = bler − brel
η4 = clfr − crfl
η5 = cler − crel + blfr − brfl
Once again, use the substitution Cφ = m and Sφ =
√
1−m2 in Equation 4.12 to get:
−(η2 + η5m)
√
1−m2 = (η3 − η4)m2 + η1m+ η0 + η4
Square both sides of this equation, and rearrange into the form:
k4m
4 + k3m
3 + k2m
2 + k1m+ k0 = 0 (4.13)
where specifically:
k4 = (η3 − η4)2 + η25
k3 = 2η1(η3 − η4) + 2η2η5
k2 = η
2
1 + η
2
2 + 2(η0 + η4)(η3 − η4)− η25
k1 = 2η0η1 + 2η1η4 + 2η2η5
k0 = (η0 + η4)
2 − η22
Equation 4.13 is a standard quartic equation in m, and closed form expressions exist
for each of its four solutions. Since ki = f (θ , φl , θl , φr , θr) for i = 0, . . . , 4, it is
possible to specify a value of θ as the input, then solve for m = cos(φ). Once φ has
been found, ψ can be determined using Equation 4.11. The complete orientation vector
[φ, θ,ψ]T can be found in this way.
4.5 Conclusions
Polynomial continuation has been shown to be a reliable method of designing deploy-
able spatial rings to meet certain geometric criteria. Fundamentally, the design process
involves the construction of relevant compatibility equations for the basic configuration
of the ring, and then solving these equations for the design variables required to allow the
110
4.5 Conclusions
ring to exhibit the desired kinematic properties. Solving these compatibility equations
by standard numerical techniques is unlikely to reveal a real solution, let alone the full
complement of solutions. By using continuation it is possible to guarantee that every
satisfactory combination of design variables has been found.
A mathematical description of the motion of the foldable ring was obtained by fo-
cussing on an individual bar of the ring, and applying rotation matrices to this bar (in the
Euler angles φ, θ and ψ) to derive an expression for the bar’s attitude. The problem then
became one of finding the mathematical relationships which would ensure that each end
of the bar just touched the two closest N/2 dividing planes of symmetry, and that the
hinges attached to each of these ends lay within these planes. Only one bar need ever
be considered, as this individual bar is simply reflected N − 1 times around a loop to
construct the rest of the ring. Two fundamental compatibility equations were found, and
it was shown that these equations could be used directly to design the ring. It was also
shown that the two compatibility equations could be combined via the elimination of one
of the three input angles. Two different combinations ({φ, θ} and {θ,ψ}) of input angle
based compatibility equation were demonstrated, as well as a target system constructed
using combinations of these compatibility equations. It was found that in order to design
a feasible ring, it is necessary to specify the relationship θ = ψ = 0 (full deployment), as
well as θ = π/2 with φ,ψ free (bars parallel when stowed), all within the same system of
equations. Target systems based on different combinations of compatibility equations are
possible, but the mixed volume of these systems can become quite large. For example, a
target system based on two {φ, θ}, and two {θ,ψ} equations (two f˜ and two f˘ equations)
has a mixed volume of 3840 in twelve unknowns, which is a considerable, although not
impossible, computational problem.
Finally, it was shown that it is possible to simulate the motion of a regular-polygonal
foldable ring by way of closed form relationships between the orientation angles of the
ring’s bars. The pitch angle, θ, is the best candidate for the input angle, and φ and ψ can
be found explicitly using standard formulae for the solution of quartic polynomials.
111
5. Doubly Symmetric 8-Bar Foldable
Rings
In Crawford et al. (1975) a type of deployable ring, or loop, was proposed which can
be stored as a collection of parallel bars in a bundle, and deployed to form a regular
polygon upon which can be stretched a radar, reflector, solar panel or other flexible sheet.
Two different types were proposed; one in which each bar is connected to the next by
two hinges attached to a small hub containing a gearing mechanism to keep the rate of
deployment of each of the two hinges the same, and a second type in which only a single
hinge is used to connect each pair of bars. The number of bars is always even, and for
number of bars n ≥ 8 a great number of degrees of freedom can be present. The design
of the single-hinge type was considered in detail in Chapter 4.
In this chapter, the design of a similar type of loop is considered, except that the
requirement for the deployed shape to be a regular polygon is removed. This was done
in an attempt to explore the versatility of deployable frames of this type; meaning, those
which are stored with their bars parallel to a central axis, and deploy to form a planar
loop, orthogonal to a central axis. To constrain the difficulty of the design problem, two
perpendicular planes of symmetry were introduced, with their intersection defining the
central axis. The two-fold plane symmetry means that the number of bars will always
be a multiple of four. A representation of a typical folding process is given in Figure
5.1. Only the 8-bar case is examined here in detail, with the 4-bar case being a Bennett
linkage, and the 12-bar and above cases forming a good area for further research. Two
different variants of the 8-bar are considered; being one in which the vertices of the loop
in the deployed configuration are positioned arbitrarily, and another in which the vertices
are constrained to lie on a rectangle.
112
5.1 Arbitrarily Positioned Vertices
Figure 5.1: A doubly-symmetric 8-bar loop undergoing folding (clockwise from bottom left).
5.1 Arbitrarily Positioned Vertices
The design parameters for this ring are shown in Figures 5.2 and 5.3, the latter being a
top view showing the locations of the vertices in XY coordinates (capitalisation denot-
ing global coordinates). Single hinges, each with a single rotational degree of freedom,
connect each bar to the next. The only constraints placed on the positioning of the ver-
tices are that hinge a must lie on the X axis, meaning Ya = 0, and hinge c must lie on
the Y axis, meaning Xc = 0. This leaves four initial positional parameters for the loop,
{Xa, Xb, Yb, Yc}.
In Chapter 4, the motion of regular-polygonal foldable loops was defined and sim-
ulated by way of two compatibility equations. Each of these equations was derived by
imposing the constraint that the hinges at the end of each bar must lie within two static
planes. This kind of constraint would not work for the doubly symmetric ring. In this
section, the defining equations for a doubly symmetric 8-bar foldable ring are derived
by using a series of transfer matrices, similar to those used in Section 3.3 (to define the
closure of the 6-bar rings), and also in Gan & Pellegrino (2006). The entire loop can
be designed by focusing on the first XY plane quadrant (as shown in Figure 5.3), and
reflecting the result in the XZ and Y Z planes to generate the rest of the ring. Setting
the locations of the vertices (a, b and c) automatically defines the bar lengths l1 and l2, as
well as the angles γa, γb and γc. The parameters αa,αb,αc and β, and the hinge rotations
φa,φb and φc remain to be determined. The lengths can be found simply by:
l1 = b− a l2 = c− b
113
5.1 Arbitrarily Positioned Vertices
Z
Y
X
Įa
Įb
Įc
Hinge a
Hinge b
Hinge c
l2
l1
l1
l1
l1
l2
l2
l2
Figure 5.2: The doubly symmetric 8-bar foldable loop in the deployed configuration. Hinge
inclinations to the vertical are shown. The two perpendicular planes of symmetry are
shown bounding the first XY quadrant. Bar lengths l1 and l2 are also labelled.
5.1.1 A Loop Closure Equation
In order to construct the defining loop closure equation for the linkage, first establish
some rotation matrices:
L2(θ) =
cos(θ) 0 sin(θ)0 1 0
− sin(θ) 0 cos(θ)
L3(ψ) =
cos(ψ) − sin(ψ) 0sin(ψ) cos(ψ) 0
0 0 1
L2B(θ) =
cos(θ) 0 sin(θ) 0
0 1 0 0
− sin(θ) 0 cos(θ) 0
0 0 0 1
L3B(ψ) =
cos(ψ) − sin(ψ) 0 0
sin(ψ) cos(ψ) 0 0
0 0 1 0
0 0 0 1
114
5.1 Arbitrarily Positioned Vertices
Y
X
Ȗa
Ȗb
Ȗc
ȕ
Hinge a
Hinge b
Hinge c
{Xa,Ya}
{Xb,Yb}
{Xc,Yc}
Figure 5.3: The doubly symmetric 8-bar foldable loop in the deployed configuration. Hinge
XY plane locations are shown.
and some pure translation matrices:
M1 =
1 0 0 0
0 1 0 l1
0 0 1 0
0 0 0 1
M2 =
1 0 0 0
0 1 0 l2
0 0 1 0
0 0 0 1
Now imagine a local coordinate system attached to hinge a, with its local x and z axes
lying in the globalXZ plane in the deployed configuration (though local and global axes
are not necessarily aligned). To express a location at hinge c in the frame attached to
hinge a, the following matrix transformation can be used:
LB = L3B(φa)L2B(−αa)L3B(γa)M1L3B(β)L2B(αb)L3B(φb)L2B(−αb)
. . . L3B(γb − β)M2L3B(γc)L2B(αc)L3B(φc)
(5.1)
In this process, the local y axis is kept aligned with each bar during a translation step, and
the local z axis is kept aligned with each hinge vector during a rotation about that hinge.
115
5.1 Arbitrarily Positioned Vertices
A rotation only version of Equation 5.1 is useful, and is given in Equation 5.2.
LR = L3(φa)L2(−αa)L3(γa)L3(β)L2(αb)L3(φb)L2(−αb)
. . . L3(γb − β)L3(γc)L2(αc)L3(φc)
(5.2)
To maintain the two-fold symmetry of the ring, it is necessary to ensure that hinge vec-
tors at a and c lie in each of the planes indicated in Figure 5.2 at all times. One way of
enforcing this condition is to stipulate that the local y axes (at a and c) must be perpen-
dicular to one another at all times (since the hinge vectors at a and c are defined as being
coincident with the z axis of the local coordinate system at each end). This forces both
the x and z axes of the local coordinate system attached to c to lie in the same plane from
the deployed to stowed position. In this way, the global Y axis is defined by the local y
axis at a, while the global X axis is defined by the (negative of the) local y axis at c.
The global Z can be found simply asX × Y . The governing equation for the system can
be given in the form of Equation 5.3, which is expressed in terms of the local coordinates
at a.
LR
01
0
,
01
0
= 0 (5.3)
While this is not a ‘closure’ equation in the truest sense of the word, the use of transfer
matrices in its derivation is sufficiently reminiscent of the loop closure techniques of
Section 3.3 for the name to be loosely applied.
At present, the hinge b vector is initially specified using two parameters; αb and β. In
the design of a loop which is capable of folding up into a tight bundle, hinge b must be
able to rotate such that bars 1 (length l1) and 2 (length l2) are parallel and coincident. It
can be shown that for this to occur, it is necessary that β = γb/2. Using this, β can be
removed from the preceding equations, to give:
LB = L3B(φa)L2B(−αa)L3B(γa)M1L3B(γb/2)L2B(αb)L3B(φb)L2B(−αb)
. . . L3B(γb/2)M2L3B(γc)L2B(αc)L3B(φc)
LR = L3(φa)L2(−αa)L3(γa)L3(γb/2)L2(αb)L3(φb)L2(−αb)
. . . L3(γb/2)L3(γc)L2(αc)L3(φc)
5.1.2 Constraint Equations and Design Variables
At this stage it is appropriate to begin to enumerate the design variables, and to consider
some constraints which might be imposed on the system. It is necessary that the number
116
5.1 Arbitrarily Positioned Vertices
of each of these be equal to form a square system of polynomial equations. The parame-
ters γa, γb, γc, l1 and l2 are all determined directly by the location of the three hinges a, b
and c in the fully deployed configuration in the XY plane. The remaining unknowns are
the three hinge inclinations αa,αb and αc, which will serve as the design variables in the
continuation design process. Some thought can now be given to what characteristics a
practical foldable 8-bar loop should possess.
• Deployed shape:
– deployed shape is directly specified by setting vertex locations in 1st quadrant;
– it is considered likely that the deployed shape will be a Convex Polygon for
most purposes, so only shapes of this type will be studied here.
• Folding motion of loop:
– to avoid bar collisions, each hinge must remain entirely within its own quad-
rant at all times;
– hinge b should follow as simple a path as possible from deployed to stowed to
minimise stress on any flexible sheet which might be attached to the frame;
– since the linkage has, by its nature, multiple degrees of freedom, some of the
hinges will have to be specially driven/guided;
– the relationship between, and control of, these driven hinges should be as
simple as possible.
• Stowed shape:
– it is likely that any practical 8-bar loop of this type will not be required to fold
into as tightly packed a bundle as possible, i.e. with bars stowed perfectly
parallel;
– some space should be left in the centre of the stowed linkage to accommodate
a central deployment assistance mechanism, or a packed flexible sheet;
– a top view of a stowed linkage is given in Figure 5.4, showing the dimensions
of the internal space.
In Section 3.6, a plane symmetric 6R foldable frame was designed using numerical
continuation. This was accomplished by defining sets of matched internal angles which
acted as ‘precision points’ at various stages throughout the linkage’s deployment. In
Section 4.3, angles were again used to specify precision points, except that rather than
117
5.1 Arbitrarily Positioned Vertices
Y
X
Hinge a
Hinge b
Hinge c
įbYįbXįcY
įaX
Figure 5.4: Top view of 8-bar linkage in stowed configuration.
internal angles, Euler angles were used to directly prescribe bar orientations in global
coordinates. In a departure from the precision point design methods of previous chapters,
the doubly symmetric 8-bar foldable ring in this chapter will be designed by way of exact
specification of the linkage’s stowed shape. Constraint equations will be written in terms
of distances rather than angles (although the design variables themselves will again be
angles). By choosing to focus only on the stowed shape one relinquishes all control
over the deployment path. Choice of deployment path is relegated to the second, more
subjective stage of the continuation design process in which once chooses designs from
amongst the continuation derived results.
To achieve the stowed configuration shown in Figure 5.4, it is necessary to introduce
three further unknowns in the form of the hinge angles in the stowed position, φas, φbs
and φcs. This makes a total of six unknowns; {φas,φbs,φcs,αa,αb,αc}. At present,
there are no constraint equations, and one closure equation in the form of Equation 5.3.
118
5.1 Arbitrarily Positioned Vertices
Construct the following transfer matrix definitions:
a)
LB1 = L3B(−φcs)L2B(−αc)L3B(−γc)M−12 L3B(−γb/2)L2B(αb)L3B(−φbs)
. . . L2B(−αb)L3B(−γb/2)M−11
b) LB2 = L3B(φas)L2B(−αa)L3B(γa)M1
c) LB3 = L3B(−φcs)L2B(−αc)L3B(−γc)M−12
d)
LB4 = L3B(φas)L2B(−αa)L3B(γa)M1L3B(γb/2)L2B(αb)L3B(φbs)L2B(−αb)
. . . L3B(γb/2)M2
e)
LR = L3(φas)L2(−αa)L3(γa)L3(γb/2)L2(αb)L3(φbs)L2(−αb)L3(γb/2)L3(γc)
. . . L2(αc)L3(φcs)
and from this, a set of constraint equations can be formed, as in Equation 5.4.
a)
LB1
0
0
0
1
,
0
1
0
0
+ δaX = 0
b)
LB2
0
0
0
1
,
0
1
0
0
− δbY = 0
c)
Yb
Xb
LB3
0
0
0
1
,
0
1
0
0
+ δbY = 0
d)
LB4
0
0
0
1
,
0
1
0
0
− δcY = 0
e)
LR
01
0
,
01
0
= 0
(5.4)
Equation 5.4a is expressed in the coordinates of the local axes attached to hinge c, and
sets the distance hinge a should sit away from the origin in theX direction in the stowed
119
5.1 Arbitrarily Positioned Vertices
configuration. Equation 5.4b is expressed in the coordinates of the local axes attached
to hinge a, and sets the distance hinge b should sit away from the X axis when stowed.
Equation 5.4c is in local hinge c coordinates, and sets the distance hinge b sits away from
the Y axis when stowed. The Yb/Xb factor included here ensures that the position of
hinge b in the deployed and stowed configurations, and the origin, are collinear. The
inclusion of the Yb/Xb factor also means that the offset δbX does not need to be specified
explicitly. Equation 5.4d is in local hinge a coordinates, and sets the offset of hinge c
from the X axis when stowed. Equation 5.4e is, of course, the definition equation of 5.3,
but is included again here for completeness.
The four constraint and single closure equations given above are sufficient to specify
a foldable linkage with several desirable characteristics. These five equations, together
with the six design variables {φas,φbs,φcs,αa,αb,αc}, form an under-determined system
which could be used to design a family of linkage designs. As an alternative, an additional
constraint is introduced which simply has the form:
φc = φa
Stipulating that the hinge angles at a and c must be the same at all times may have
some practical advantages. If these hinges were, say, identical spring loaded hinges with
enough damping to cause them to expand at the same rate, the linkage would behave as
though it had a single degree of freedom, and expand to be rigid. The four hinge b’s could
be left free to rotate. This new equality reduces the number of design variables to five,
resulting in a square system of equations.
The form of Equation 5.4c, along with the constraint φc = φa, has an interesting
consequence in terms of the motion of hinge b during deployment. It is the equiva-
lent, mathematically, to including a further constraint equation requiring the projection
of hinge b onto the XY plane to remain on the same line (formed by the hinge b lo-
cation when deployed, and the origin) at all times during deployment (hinge b expands
radially away from the centre during deployment). This equivalence can be observed by
actually constructing such a constraint equation, and noting that its gradient with respect
to {φa/c,φb,αa,αb,αc} is always spanned by any four of the five rows of the Jacobian
formed by the other five equations.
5.1.3 Continuation Results
Equation set 5.4 forms the basis of the equations used in the continuation process. As
usual, trigonometric terms are replaced with new variables, doubling the number of un-
120
5.1 Arbitrarily Positioned Vertices
knowns. The unknowns are now {Cφas , Sφas , Cφbs , Sφbs , Cαa , Sαa , Cαb , Sαb , Cαc , Sαc}.
Five new equations of the form:
C2φas + S
2
φas − 1
C2φbs + S
2
φbs
− 1
C2αa + S
2
αa − 1
C2αb + S
2
αb
− 1
C2αc + S
2
αc − 1
= 0
are appended to the set of five in 5.4. The vertex locations, such as those in Table 5.1,
are used to generate the coefficients for equation set 5.4, which is now a system of pure
polynomials in terms of the ten unknowns. This system of ten equations in ten unknowns
has a total degree of 22400, but a mixed volume of only 512. The system can then be
solved using the polyhedral homotopy methods of Chapter 2.
A polynomial system with the same structure as 5.4, but with random complex coef-
ficients, can be solved first and then used as the start system for each real valued design
problem of the same type. Because polyhedral homotopy methods provide such a tight
upper bound on the number of solutions to a system, the start system with random com-
plex coefficients will have only finite solutions, the number of which is exactly equal to
the mixed volume of the system. Any real valued system will only ever have the same
number, or fewer solutions. To solve a real (or possibly another complex) valued system,
one can construct a coefficient homotopy from the initial complex valued start system
to the real or complex target. Constructing a coefficient homotopy from one real target
system to another will not guarantee that all solutions will be found.
After using polyhedral homotopy methods to construct a random complex coefficient
start system with structure identical to Equations 5.4, some design cases were examined
using a coefficient homotopy. The results are discussed below.
Design Case # 1
To test the design method, some random vertex locations were selected, with the proviso
that the deployed linkage be a convex polygon with l1 ≈ l2, and vertices approximating
a regular polygon for the first case. The initial parameters for this first example are given
in Table 5.1. The particular value of the δbY offset was chosen in this case because it
causes hinge b to be situated a distance of 0.15 units radially from the Z axis (the same
distance as hinges a and c). This system yielded surprisingly few geometrically isolated
solutions. Four distinct real designs were found, with their deployment paths shown in
121
5.1 Arbitrarily Positioned Vertices
Parameter Value
Hinge a location {1,0}
Hinge b location {0.7,0.8}
Hinge c location {0,1.1}
δaX 0.15
δbY 0.1129
δcY 0.15
Table 5.1: Initial parameters for 8-bar design example # 1.
Figure 5.5. Only one of the finite, real solutions (labelled as design # 1) was found not
S S S
S
S
S
S
Ib
I a
,
I c
Design #1
Design #2
Design #3
Design #4
Stowed Positions
Deployed Position
Figure 5.5: Internal angles for doubly symmetric 8-bar foldable ring, example # 1. All
simulations were started at the ring stowed locations. Only design # 1 was found to
progress satisfactorily from the stowed to deployed configuration.
only to satisfy the constraints, but to operate in a totally satisfactory manner. This entails
all hinges opening smoothly from stowed to deployed, and all hinges staying within their
quadrant at all times during deployment. Some designs are degenerate, and do not have
uninterrupted paths from the stowed to the deployed configurations (such as designs #2
and #4), while others can move continuously from stowed to deployed, but have to self-
intersect in order to do so. As expected, the vertical projection of hinge b onto the XY
plane followed the line described by Y = Yb/Xb.X , with only the height above this plane
varying. A summary of the details about the single feasible design found is given in Table
122
5.1 Arbitrarily Positioned Vertices
5.2, along with a detail of the deployment path.
Although design # 1 does meet almost all the design criteria laid out earlier in the
chapter, it is not quite ideal. This design was chosen over the other possible three because
it deploys in a relatively straightforward manner, without any of the hinges crossing the
X or Y axes during deployment. This said, hinge c comes quite close (to within a dis-
tance of 0.1 units) of the X axis during deployment, meaning the design would probably
be rejected in practice. To find a truly acceptable design with these deployed vertex loca-
tions, the relationship φc = φa would need to be relaxed, or at least modified. A flowchart
of the linkage’s folding from the deployed to stowed position is given in Figure 5.6.
Figure 5.6: Folding of 8-bar example # 1, design # 1; clockwise from bottom left. Notice how
close the c hinges come to one another in the second to last image.
123
5.1 Arbitrarily Positioned Vertices
Solution Structure
No. of real solutions found 32
No. of geom. distinguishable solutions 4
Geometry of Solution
αa -1.2238 rad
αb 1.0641 rad
αc -1.2686 rad
Deployed Loop Stowed Loop
Angle Progression Plot
S S S S S
S
S
Ib
I a
,
I c
Stowed
Deployed
Table 5.2: Data for 8-bar foldable ring, example # 1, design # 1.
124
5.1 Arbitrarily Positioned Vertices
Design Case # 2
For this example, vertex locations were chosen such that lengths l1 and l2 were signifi-
cantly different from one another. This was to test the feasibility of the design procedure
for loops which differ appreciably from a regular polyhedron. The initial parameters are
given in Table 5.3. Again, four different real solutions were found, and their deployment
Parameter Value
Hinge a location {1,0}
Hinge b location {0.8,0.4}
Hinge c location {0,0.8}
δaX 0.15
δbY 0.06708
δcY 0.15
Table 5.3: Initial parameters for 8-bar design example # 2.
paths are shown in Figure 5.7. Once again also, only a single feasible solution was found
S S S S S
S
S
S
S
Ib
I a
,
I c
Design #1
Design #2
Design #3
Design #4
Stowed Positions
Deployed Position
Figure 5.7: Internal angles for doubly symmetric 8-bar foldable ring, example # 2. All
simulations were started at the ring stowed locations. Only design # 4 was found to
progress satisfactorily from the stowed to deployed configuration.
(labelled as design # 4), the details of which are given in Table 5.4. Hinge c was found
125
5.1 Arbitrarily Positioned Vertices
not to venture too close to the X axis during deployment in this case, and a quite satis-
factory linkage could most likely be constructed using the parameters listed here. The
deployment is shown in Figure 5.8.
Figure 5.8: Folding of 8-bar example # 2, design # 4; clockwise from bottom left. In this case,
the c hinges remain a safe distance away from one another during
folding/deployment.
126
5.1 Arbitrarily Positioned Vertices
Solution Structure
No. of real solutions found 32
No. of geom. distinguishable solutions 4
Geometry of Solution
αa 0.1400 rad
αb -2.2821 rad
αc -0.1400 rad
Deployed Loop Stowed Loop
Angle Progression Plot
S S S S
S
S
Ib
I a
,
I c
Deployed
Stowed
Table 5.4: Data for 8-bar foldable ring, example # 2, design # 4.
127
5.2 Rectangular 8-Bar
5.2 Rectangular 8-Bar
One particularly interesting subset of the 8-bar foldable loop is the one for which:
γa = 0
γb = π/2
γc = 0
This describes a linkage which is rectangular in the deployed configuration. The extra
degree of freedom present in the 8-bar rectangular linkage (as opposed to the 6-bar ver-
sion, see Chapter 3) may allow for extra design constraints to be considered. A greater
range of aspect ratios can also be achieved without the self intersection problems which
can arise with the 6-bar rectangular linkage.
A rectangular linkage can be designed using polynomial continuation in much the
same way as a linkage with arbitrarily positioned vertices. The only difference is that
the new special values of the γ angles cause Equation 5.4b to become equivalent to
5.4c. This reduces the total number of equations to four. There are still five unknowns
({φas/cs,φbs,αa,αb,αc}), however, which means a new relationship needs to be intro-
duced to square up the system. It is also possible, of course, that this under-determined
system could be used to find a family of ring designs lying along the curve of solutions
to the four equations in five unknowns. This will not be attempted here. Rather, a simple
yet practically desirable new relationship between the unknowns will be sought.
5.2.1 Continuation Results
To overcome the lack of constraint equations, a new relationship of the form φbs = ±2φas
was introduced. The rationale behind this is that the hinge angles φa and φc actually only
constitute ‘half’ angles, in that they span the angle from one bar to a central plane of
symmetry. In the construction of a physical model, a hinge which opened to twice that
value would be required to link one bar to the next. It was hypothesised that if hinge
b could be set to open to twice the value of the two (equal) half-angles of hinges a and
c, then perhaps only a single type of hinge, designed to open only as far as a certain
fixed angle, would be required to construct the entire loop. This reduced 4 × 4 system
of polynomials has a mixed volume of only 96. An illustrative example of the design
process for a rectangular 8-bar linkage is given below.
128
5.2 Rectangular 8-Bar
Design Case # 3
The initial design parameters for a rectangular loop are given in Table 5.5.
Parameter Value
Hinge a location {1.1,0}
Hinge b location {1.1,0.7}
Hinge c location {0,0.7}
δaX 0.1
δbY 0.0537
δcY 0.1
Table 5.5: Initial parameters for 8-bar design example # 3.
This time, only sixteen real solutions were found, but again, four of them were ge-
ometrically distinct. The four deployment paths are shown in Figure 5.9. Note that, on
this occasion, the deployed configuration was used as the start point for all the simula-
tions depicted. Two of the rings were found to have their deployed and stowed locations
S S S S
S
S
S
S
Ib
I a
,
I c
Design #1
Design #2
Design #3
Design #4
Stowed Positions
Deployed Position
Figure 5.9: Internal angles for doubly symmetric 8-bar foldable ring, example # 3. All
simulations were started at the ring deployed locations. Only design # 1 was found
to progress satisfactorily from the deployed to stowed configuration.
connected by an uninterrupted deployment path. Of these, only one (design # 1) behaves
129
5.2 Rectangular 8-Bar
entirely satisfactorily. The details of its design are given in Table 5.6. What is immedi-
ately apparent is that φbs = ±2φas, since when deployed, both angles are zero, and when
stowed:
φas = 1.4500 rad
φbs = −3.3832 rad
cos(φbs) = cos(2φas)
sin(φbs) = sin(2φas)
This is not surprising, as the specification φbs = 2φas has the equivalent effect on the
equations of setting:
cos(φbs) = cos
2(φas)− sin2(φas)
sin(φbs) = 2 sin(φas) cos(φas)
As it happens, no feasible solutions satisfying φbs = ±2φas were found for this rectangu-
lar linkage. The best result, this considered, is shown in Table 5.6. The folding process is
shown in Figure 5.10. It is possible that a rectangular frame with a different aspect ratio
might be deployable with φbs = ±2φas, but none has been found to date.
Figure 5.10: Folding of 8-bar example # 3, design # 1; clockwise from bottom left. In this case,
the c hinges remain a safe distance away from one another during
folding/deployment.
130
5.2 Rectangular 8-Bar
Solution Structure
No. of real solutions found 16
No. of geom. distinguishable solutions 4
Geometry of Solution
αa -1.0613 rad
αb -1.7585 rad
αc -0.8795 rad
Deployed Loop Stowed Loop
Angle Progression Plot
S S S S
S
S
Ib
I a
,
I c
Stowed
Deployed
Table 5.6: Data for 8-bar foldable ring, example # 3, design # 1.
131
5.3 Deployment of 8-Bar Rings
5.3 Deployment of 8-Bar Rings
Rather than use a 4, 5 or 6-bar linkage, a designer might choose to use an 8-bar linkage as
the basis of a deployable ring because of the greater range of deployed shapes possible,
and because of the greater control which can be exercised over the way in which the
frame deploys. However, some extra complications need to considered. Many deployable
frames based on 4, 5 or 6-bar linkages have only a single degree of freedom, and hence
have pre-determined deployment paths which can often be easily followed simply by
applying sufficient moments at one or more of the hinges (Laloi, 1999; Pellegrino et al.,
2000). By their nature, 8-bar spatial linkages (arranged in a loop) will have at least two
degrees of freedom. It is important that the extra benefit derived from the increased
versatility in shape outweigh the increase in complexity of the deployment system. The
double symmetry of the frames considered in this chapter means that hinge b is replicated
four times around the loop, while hinges a and c are replicated twice each. If (as was the
case in all examples given above), hinge angles φa and φc are set to be equal, then this
leaves two distinct hinge angles present in the loop. At this stage, the best method of
deploying a doubly symmetric 8-bar frame is unknown, although it is possible that a set
of four identical, damped, spring-loaded hinges attached to either hinges b or a, c might
suffice.
The charts displaying angles φa,φc vs. φb provide some valuable information about
the deployability of a given 8-bar design. If hinge b is to be the driven hinge, then φb
needs to be a monotonic function of φa,φc, and if a, c is to be the driven hinge, then
φa,φc must be a monotonic function of φb over the deployment range.
Consider the case of example #1, design # 1. Looking at the angular progression at the
bottom of Table 5.2, it can be seen that the linkage would not fully deploy if hinges a and c
were designated as the driven hinges (φa, φc do not increase/decrease monotonically). In
fact, the same problem would be encountered with hinge b selected as the driven hinge.
This design could clearly not be deployed with passive actuators such as springs, or if
it was, it could not be guaranteed that the deployment would follow anything like the
prescribed deployment path.
Next consider example # 2, design # 4, whose deployment path is shown at the bottom
of Table 5.4. Notice that this time, φa, φc do increase/decrease monotonically, meaning
that spring loaded hinges could, most likely, be used to deploy the ring without causing
it to deviate from its prescribed deployment path.
Finally, consider example # 3, design # 1, whose deployment path is shown at the
bottom of Table 5.6. This time φb increases/decreases monotonically with φa, φc, but the
132
5.4 Conclusion
converse is not true. Hinge b presents itself as the only candidate for a driven hinge.
5.4 Conclusion
The deployable rings in Chapter 4 are regular polygons in their deployed state. The study
of the doubly symmetric foldable rings in this chapter was intended as an extension by
way of an exploration into the design of foldable rings which form non-regular polygons
in their deployed state. It is conceivable that not all deployable membranes might require
a regular polygon shaped frame (approximating a circle). The aim of this chapter was
also to illustrate a different way of specifying design constraints in the process of linkage
design using polynomial continuation. An 8-bar version of the doubly symmetric foldable
ring was used for this purpose. As an alternative to the use of angular precision points
to specify the way in which a ring deploys, a series of dimensions, prescribing an exact
stowed shape, was introduced in the form of constraint equations. The deployed shape
was directly specified in all cases, and the exact dimensions of the stowed ring were used
to generate the coefficients for the polynomials (whose monomials were written in terms
of the unknown design variables).
Two different deployed shapes, whose vertices were essentially randomly located (but
still forming a convex polygon), were used as design examples. Each yielded four dis-
tinct real solutions, but only one which could be considered feasible in that (a) no self-
intersection was observed, and (b) a single connected path existed between the deployed
and stowed configurations. A rectangular deployed shape was also considered, and a
simplified version of the compatibility/constraint equation system introduced. The rect-
angular design was also found to yield four distinct real solutions, and a single feasible
design.
The three design examples included in this chapter together constitute a compelling
case for the use of polynomial continuation in the linkage design process. In each case
more than one set of design parameters (solutions) were found to satisfy the imposed
constraints, leaving the designer with a number of valid options. Different criteria can
be used to select which of the feasible solutions best fits the design objective. In this case,
the design priority which guided the solution selection was avoidance of self intersection
during deployment. Choosing among the solutions determined via the continuation pro-
cess, is to some extent a matter of personal judgement. Once a designer has determined
which features a linkage absolutely must possess, and has found, via continuation, all the
combinations of design parameters which will satisfy those constraints, he/she is free to
exercise his/her discretion in selecting the best.
133
5.4 Conclusion
Issues concerning the deployment of 8-bar doubly symmetric foldable frames were
discussed, with particular reference to the three design cases considered earlier. Deploy-
ment of such rings using passive actuators may not be possible in situations in which
deployment paths require hinge angles which do not vary monotonically.
134
6. Mobility of 6,7 & 8-Link N-Loops
This chapter marks a slight departure from the theme of preceding chapters. The focus in
this final chapter is not the development of polynomial continuation-based design tools as
applicable to practical foldable rings, but rather the use of continuation to gain a greater
understanding, at a theoretical level, of the closure equations of mobile loops. This topic
was introduced briefly in Chapter 3, Section 3.3, but is covered here in more detail.
The examples used in this chapter are a specific type of closed loop called N-loops
(where N is the number of links present). Some quite simple examples of these loops
exhibit some interesting characteristics from the point of view of mobility. These charac-
teristics can be explored in a very hands-on way by using a commercially available type
of toy whose components resemble those of N-loops when connected in a ring (see next
section). As a kind of shorthand, the ‘N’ in N-loops will occasionally be replaced by a
numeral.
In this chapter, polynomial continuation is used to probe the nature of the equations
describing N-loops. In the first instance, the 6-link N-loop is examined, yielding arguably
the most interesting results. The existence of both rigid and mobile conformations is
suggested by the structure of the 6-loop’s closure equations, enabling a mathematical
understanding of the linkage’s mobility. 7 and 8-loops are then examined, focussing only
on the positive dimensional solutions which are known to exist in their closure equations.
6.1 ‘Tangle’ N-Loops
The toy, ‘Tangle Creations,’ is “a series of 90◦ curves, connected and able to pivot at
each joint.”1 More specifically, it is a collection of quarter arcs, with each piece able
to connect to another end-to-end, allowing a single (longitudinal) rotational degree of
freedom between them. The links can be connected end-to-end to form a closed loop. The
most simple example of such a closed loop consists of four individual pieces connected to
form a rigid circle. A basic application of the Kutzbach criterion (Equation 3.3) suggests
1https://www.tanglecreations.com
135
6.2 6-Link N-Loops
that a closed loop of links requires at least seven elements (in the spatial case) in order
to display any mobility (seven links connected in a loop using seven single degree of
freedom joints). A reasonable question is: given that other forms of mobile 6-bar linkages
exist, is it possible to construct a mobile loop of Tangle pieces using only six, or fewer,
elements? As it happens, there are two different ways in which six Tangle pieces can
be connected together into a loop. One of the conformations is rigid, as predicted by
the Kutzbach criterion, while the other possesses a geometric degree of freedom, and is
mobile.
Recently, a version of the Gru¨bler criterion was used to count the kinematic degrees
of freedom in N-loops (Guest & Fowler, 2010). Porta et al. (2007) produced a com-
plete map of the conformation space for similar (molecular) loops by manipulating dis-
tance constraints into Cayley-Menger determinants, and then finding their roots using
numerical techniques. In this chapter the mobility of N-loops is considered again, but
the problem of finding and predicting mobilities which might occur is approached from
a different, and entirely numerical, perspective. Each link is assumed to be identical, and
the key dimensions of each link can be set to unity without loss of generality (in prepa-
ration for numerical analysis). At its core, the analysis involves the solution of a system
of closure equations for the linkage. The unknowns are the twist angles between each
of the links, necessary to ensure loop closure. Two main categories of solutions can be
expected; geometrically isolated (sometimes called zero-dimensional) points, and posi-
tive dimensional solutions sets. Positive dimensional solutions indicate that a continuum
of solutions which satisfy the closure equations exists, which perhaps also indicates an
internal mobility in the physical linkage. The structure of the closure equations for the
6-link Tangle loop is of particular interest because the loop is known to possess a certain
amount of mobility, depending on the exact conformation.
6.2 6-Link N-Loops
A Tangle piece is quite simple to describe geometrically. Figure 6.1 shows a Tangle piece
in plan view. Each element is connected socket 1 to socket 2 in a loop. Closed linkages
of this nature can be described succinctly using an arrangement of transfer matrices. A
transfer matrix is used to move between coordinate systems attached to each of the links
(both a rotation and a translation); see Sections 3.3 and 5.1.1, as well as Chen & You
(2009); Gan & Pellegrino (2006). Position vectors are augmented with a 1: [x, y, z, 1]T .
Transfer matrices of this nature can be expressed as a combination of geometric and
‘state’ components. One way of expressing the rotation between one link and the next
136
6.2 6-Link N-Loops
l
l
x
y
Socket 1
Socket 2
Figure 6.1: Tangle piece in plan view.
about the x-axis is a simple rotation matrix:
Ts =
1 0 0 0
0 Cφ Sφ 0
0 −Sφ Cφ 0
0 0 0 1
This is the ‘state’ part of the matrix, and can be applied in local coordinates at socket
1 (Figure 6.1) to describe a rotation between the current link and the next. The angle
φ determines the magnitude and sign of the rotation. The geometric part of the transfer
matrix is fixed, and performs a rotation of 90◦ about the z-axis, as well as two translations
of magnitude l.
Tg =
0 1 0 −l
−1 0 0 l
0 0 1 0
0 0 0 1
The two parts can be combined to form the complete transfer matrix:
T = TgTs =
0 Cφ Sφ −l
−1 0 0 l
0 −Sφ Cφ 0
0 0 0 1
(6.1)
137
6.2 6-Link N-Loops
A loop closure equation can be written as:
F = T61T56T45T34T23T12 − I = 0
which is in terms of the six rotations {φ12,φ23,φ34,φ45,φ56,φ61}. In the solution of the
closure equations, no prior assumptions about how the loop is to be formed need be made.
The strictly upper triangular part of F provides six independent equations, which can be
used to form a square system.
F1,2
F1,3
F1,4
F2,3
F2,4
F3,4
= 0
The (real part of the) solution space of these equations is equivalent to the Conforma-
tional Space of the Tangle linkage. Quite often, the vast majority of solutions to an
unhomogenised system of polynomial equations are solutions at infinity. Before apply-
ing continuation, there is no way to determine which of the start system’s solutions will
track to solutions at infinity in the target system. One way to reduce the number of paths
which diverge to infinity is to reduce the degree, or order, of the target (and hence also the
start) system. This can be achieved by way of elimination (Univariate polynomials have
only solutions in the finite plane), but in this case a reduction in degree can be achieved
simply by dividing the closure equation, placing three terms on each side:
F = T34T23T12 − (T61T56T45)−1 = 0
The maximum degree of each term in F is now three. The final step in constructing a
system of equations appropriate for use with continuation is to express each equation in
terms of the sines and cosines of the rotation angles, rather than the angles themselves.
This doubles the number of unknowns, and the number of equations. The new variables
are assigned asCφij = cos(φij) and Sφij = sin(φij). The final system is given in Equation
138
6.2 6-Link N-Loops
6.2.
F 1,2
F 1,3
F 1,4
F 2,3
F 2,4
F 3,4
C2φ12 + S
2
φ12 − 1
C2φ23 + S
2
φ23 − 1
C2φ34 + S
2
φ34 − 1
C2φ45 + S
2
φ45 − 1
C2φ56 + S
2
φ56 − 1
C2φ61 + S
2
φ61 − 1
= 0 (6.2)
This system has a total degree of 486 × 26 = 31104, but a mixed volume of only 1472.
The system could be solved directly using polyhedral methods, locating all the zero-
dimensional solutions, but this would not reveal much about the structure of the equations
except, perhaps, for hints of the existence of higher dimensional solution sets in the form
of patterns of singular solutions.
(a) 6-Loop Mobile Conformation. (b) 6-Loop Rigid Conformation.
Figure 6.2: The two (mobile and rigid) 6-loops (from Guest & Fowler (2010)).
One method of probing the structure of a system of polynomial equations, and in
particular, identifying higher dimensional solution sets, is the method of Witness Sets.
This method was introduced in Section 2.5, and used in Section 3.3 to gain a greater
139
6.3 Solution Structure of 6-Loop Equations
understanding of the mobility of the plane symmetric 6R foldable ring. The construction
of witness sets by a cascade of homotopies is a top-down process; starting with a search
for elements on the highest possible dimensional set, and working downwards. To take
the most general approach would involve introducing n − 1 = 11 hyperplanes and new
variables, and implementing 11 cascade homotopies, one after the other. This would
result in an initial system in 23 unknowns; a formidable computational task. Instead,
some a posteriori knowledge is used to rule out the existence of solutions of dimension 2
or greater, since none are observed in practice, and no unusual singular solutions appear
during the search for 1 and 0 dimensional sets. This being the case, a single hyperplane
and a single extra unknown are appended to system 6.2. This has no affect on the total
degree of the system, but does raise the mixed volume to 4352. While 4352 is a large
number of solution paths to track, the task is not an impossible one.
6.3 Solution Structure of 6-Loop Equations
The first step in solving the combined system of Equation 6.2 and the extra hyperplane
is to construct and solve a random complex coefficient system with the same polynomial
structure. This provides a start system with the full complement of 4352 equations which
can be reused in the solution of different target systems. The next step is to use the random
complex coefficient start system to solve the target system directly using a coefficient
homotopy. Equation 6.2 is written in terms of the twelve original unknowns, as well as a
length parameter l. Without loss of generality, this length can be set to 1.
6.3.1 Solutions of Dimension 1
Using a start systemwith the full complement of 4352 equations to solve the target system
for the dimension 1 case leads to 2206 finite solutions. Of these, twelve satisfy the
condition z = 0, where z is the new introduced variable which only becomes zero when
a solution of dimensionality > 0 has been found. This immediately suggests that it
might be possible to construct a closed loop linkage of six Tangle pieces which has some
internal mobility. Looking more closely at the solutions, in can be observed that each
satisfies the relationship xi = xi+3 i = 1, . . . , 6 (addition modulo 6). This suggests some
relevance to the rotational symmetry which the mobile form of the six element N-loop is
known to actually possess. So far it can only be stated that the full witness set consists of
twelve members. It also needs to be determined if these twelve solutions form part of the
same irreducible component, or whether there are a number of separate components. This
140
6.4 7 & 8-Loops and Their Mobility
is achieved by using a method called Monodromy (see Section 2.5.1). In this case, all
twelve solutions were observed to permute amongst themselves during the monodromy
process, meaning that only a single positive dimensional solution set (dimension 1) exists,
and that it has degree 12.
Table 6.1 provides a list of some of the (real) points which lie on the continuum of
solutions of degree 12 (and dimension 1). Figure 6.2(a) illustrates a real model of a
mobile 6-loop.
Point # 1 2 3 4 5 6
φ12 0 −π2 π2 0 π2 −π2
φ23
π
2 0 −π2 −π2 0 π2
φ34 −π2 π2 0 π2 −π2 0
φ45 0 −π2 π2 0 π2 -π2
φ56
π
2 0 −π2 −π2 0 π2
φ61 −π2 π2 0 π2 -π2 0
Table 6.1: A selection of points on the 6-bar N-loop 1-dimensional irreducible component. Each
of these points is observable as a real configuration of the 6-bar N-loop (as well as the
continuum of solutions between each point).
6.3.2 Solutions of Dimension 0
Once the full witness set for the solutions of dimension 1 has been found, a cascade ho-
motopy can be used to reduce the dimension of the remaining 2194 solutions. In this
process, 1994 of these solutions diverged to infinity. This left 200 solutions in the twelve
original unknowns. Of these 200 solutions, 32 were identified as being members of the
1-dimensional irreducible component, and hence removed. This left 168 true zero di-
mensional (geometrically isolated) solutions. The vast majority of these 168 are complex
and/or non-physical singular. In fact, only two non-singular real solutions remain, and
these are given in Table 6.2. Up to rotational symmetry, these two solutions represent the
one rigid conformation observed to exist in the 6-link N-loop. Figure 6.2(b) illustrates a
real model of a rigid 6-loop. A graphical representation of the cascade process is given
in Figure 6.3.
6.4 7 & 8-Loops and Their Mobility
While it may have been unexpected that the 6-loop should have a mobile conformation,
it comes as no surprise that the 7 and 8-loops are both mobile. A direct application of
141
6.4 7 & 8-Loops and Their Mobility
Solution # 1 2
φ12
π
2 −π2
φ23 −π2 π2
φ34
π
2 −π2
φ45 −π2 π2
φ56
π
2 −π2
φ61 −π2 π2
Table 6.2: The two non-singular real zero-dimensional solutions to the 6-loop equations. These
two solutions describe the only observed rigid conformation of the 6-loop, up to
rotational symmetry.
4352 initial solutions 2146 paths to infinity
12 solutions with z = 0
2194 remaining solutions
1D witness set
1994 path to infinity
200 remaining solutions Filter stage 32 filtered out
168 0D solutions
Cascade step
Use 1D witness
set to perform
membership tests
Figure 6.3: Reduction process for 6-Loop closure equations (Equation 6.2).
the Kutzbach criterion suggests that the 8-loop should possess two degrees of freedom,
and the 7-link, one. This is indeed the case. Neither the 7 nor 8-loop is known to possess
a rigid conformation, removing the need to perform a full homotopy cascade on each of
the loops’ closure equations to fully examine their nature. Something, however, can be
said about the positive dimensional solution sets which are present in each loop’s closure
equations, and which give rise to their mobility.
6.4.1 The Degree of the 8-Loop’s Mobility
To construct a set of closure equations for the 8-loop, a similar set of transfer matrices to
those in Section 6.2 are used, with the addition of two extra transfer matrices to account
142
6.4 7 & 8-Loops and Their Mobility
for the two extra links:
F = T81T78T67T56T45T34T23T12 − I = 0
⇒ F = T45T34T23T12 − (T81T78T67T56)−1 = 0
Once again, only the upper six off-diagonal entries contribute:
F 1,2
F 1,3
F 1,4
F 2,3
F 2,4
F 3,4
= 0
This leaves a system in eight unknowns and six equations. The under-determined nature
of the system immediately suggests that mobility could be present, and that there will be
(in general) two degrees of freedom in the loop’s motion. Two intersecting hyperplanes
are added, resulting in a determined system. To calculate the degree of the positive di-
mensional solution sets present, it is necessary to enumerate the locations in which the
hyperplanes are intersected by the solution paths, while accounting for any multiplicities
(although the use of complex coefficients in the random intersecting hyperplanes gener-
ally obviates the need to consider multiplicities). Only one intersection point on each
irreducible component is required to generate all the others. By using monodromy to
expand the sets representative of each irreducible component, it is possible to generate
the full witness set. The process may begin with any subset of intersection points which
contains at least one member on each component.
It has been suggested1 that the 8-loop may possess two ‘lobes’ of feasible configura-
tion sets, connected only by their closures at the point at which the 8-loop forms a double
circular ring. This raises questions about whether there may be two separate irreducible
components in the dimension-2 solution set, with one representing each of the ‘lobes’.
To test this, two configurations, each thought to exist in different solution lobes, were
generated. A ‘crown’ configuration, in which the twist angle between each link differs
from the next only in sign, was used for this purpose. An illustration of the crown is given
in Figure 6.4. The ‘right way up’ crown is given by:
φi(i+1) = ± arccos(1−
√
2) ≈ ±114◦ i = 1, . . . , 8
1via a personal communication, R. Connelly.
143
6.4 7 & 8-Loops and Their Mobility
Figure 6.4: Crown configuration of the 8-loop (from Guest & Fowler (2010)).
and the ‘upside down crown’ is given by:
φi(i+1) = ∓ arccos(1−
√
2) ≈ ∓114◦ i = 1, . . . , 8
For each of these configurations, two complex-valued hyperplanes which passed through
these (real) points were found, and the process of monodromy employed to generate full
sets representing the irreducible components associated with each. Both the ‘right way
up’ and the ‘upside down’ irreducible components were found to contain 48 points, and
a quick mapping from one set to the other revealed that they were in fact the same set. It
is postulated, therefore, that a single dimension-2 irreducible component (of degree 48),
is responsible for all the mobility of the 8-loop.
6.4.2 The Degree of the 7-Loop’s Mobility
If seven Tangle pieces are connected in a loop, then without any prior knowledge it could
be assumed that some mobility, most likely a single degree of freedom, will be present. In
fact, two separate single degree of freedom conformations exist. One is dubbed the ‘boat’
conformation, and appears in Figure 6.5(a). The other, named the ‘chair’ conformation,
appears in Figure 6.5(b).
One obvious question which arises is: do the two observed mobile conformations
lie on the same irreducible component, or do they form two distinct parts of the one-
144
6.4 7 & 8-Loops and Their Mobility
(a) 7-loop boat conformation. (b) 7-loop chair conformation.
Figure 6.5: 7-loop examples (from Guest & Fowler (2010)).
dimensional solution set? Once again, a set of closure equations of the form
F = T71T67T56T45T34T23T12 − I = 0
⇒ F = T34T23T12 − (T71T67T56T45)−1 = 0
is constructed, and this time a single random complex coefficient intersecting hyperplane
is added. Both the chair and boat conformations at some point in their motion satisfy the
relationships
φ12 = 0
φ23 = −φ71
φ34 = −φ67
φ45 = −φ56
This point can be used as a seed to generate the rest of the intersection points on the
irreducible component using monodromy. Specifically, for the boat conformation, the
145
6.5 Conclusions
initial angles are:
φ12 = 0
φ23 = cos
−1
19
√
2− 27
16
√
2− 22
≈ 102◦
φ34 = − cos−1
1
7
(9− 4√2)
≈ −46◦
φ45 = − cos−1
1− 1√
2
≈ −73◦
while for the chair, the initial angles are:
φ12 = 0
φ23 = cos
−1
19
√
2− 27
16
√
2− 22
≈ 102◦
φ34 = − cos−1
−
1
7
(9− 4√2)
≈ −134◦
φ45 = cos
−1
1− 1√
2
≈ 73◦
These symmetry points were found to generate witness sets with 112 elements each for
both the boat and chair forms. Further analysis revealed that each of these sets mapped
onto the other, and hence that both real conformations lie on the same irreducible com-
ponent of degree 112. This indicates that the two conformations are connected in
complex space, but not in real, since it is not possible to transform a real 7-loop from
the boat to the chair form without disconnecting the links. The degree of this component
is quite large, and indicates the high complexity of the motion of the 7-loop.
6.5 Conclusions
It was possible to use polynomial continuation (applied to the closure equations of the
6-link N-loop) to identify features of the closure equations which are responsible for
the 6-loop’s unusual mobility properties. The closure equations for the 6-link N-loop
was found to have a dimension-1 solution set of degree 12, which is responsible for its
mobility when connected in the mobile conformation. The closure equations were also
found to have a dimension-zero solution set with 168 solutions, only two of which are
real. These two real solutions represent the same rigid conformation up to rotational
146
6.5 Conclusions
symmetry.
Monodromy was used to identify a single (dimension-2) irreducible component of
degree 48 which is responsible for the mobility of the 8-link N-loop. This process was
also used to identify a single (dimension-1) irreducible component responsible for the
7-link N-loop’s mobility in both the ‘chair’ and ‘boat’ forms.
147
7. Conclusions
The usefulness and versatility of numerical continuation, and in particular polynomial
continuation, in the design of deployable rings and frames has been illustrated by way of
a number of case studies.
On a more fundamental level, the design of deployable rings has been approached
from the viewpoint that an in-depth understanding of the closure/compatibility equations
used to mathematically describe the behaviour of the underlying linkage is of critical
importance. Often, more than one equation structure can be used to model linkage be-
haviour, with some some structures being more appropriate than others, depending on the
exact case (compare the symmetry based compatibility equations used in Chapter 4 to the
transfer matrix based loop closure equations used in Chapter 5 to model a quite similar
style of ring). If one is to attempt the design of a linkage by direct solution of a system
of defining equations, in particular using polynomial continuation, careful consideration
must be given to the type of closure/compatibility equations used. For example, in Chap-
ter 3, a transfer matrix based closure equation was found to be useful for understanding
the mobility of the 6-link plane symmetric foldable ring, but a more simple compatibility
equation based only on two of the ring’s six hinge angles was found to be more appro-
priate for designing the ring using continuation because it was written in terms of fewer
variables and could be used to define the ring’s shape at a greater number of positions
during deployment. Ideally, the closure/compatibility equations will be arranged in such
a way that the mixed volume of the complete system of design equations is minimised (in
Chapter 6, the total degree of the closure equations was reduced by splitting the transfer
matrices across two terms). A fundamental understanding of the defining equations is
also necessary when it comes to introducing design parameters in the form of constraint
equations. One can optimise the continuation based design process by constructing con-
straint equations involving only those design variables which are absolutely necessary,
and which can be arranged in such a way as to minimise the mixed volume of the design
equations.
In addition to illustrating how polynomial continuation can be used in the design
148
process of deployable rings, it has also been shown that variations on the continuation
method (in the form of cascades of homotopies, and monodromy processes) can be used
to get a real understanding of the mathematical nature of a deployable linkage’s mobility.
In Chapter 6 it was shown that closure equations could be used (without the construction
of a real 6-link N-loop) to reveal the existence of two different types of conformation;
one mobile and one rigid. This method has the potential to reveal conformations which
had not previously been considered in a linkage, and can also be used to determine with
absolute certainty that no other conformations, besides those already known, exist.
Polynomial continuation has applications, not only in kinematics, but also in geom-
etry, chemistry, and many other technical fields. Chapter 2 provides an introduction to
polynomial equations, and how they arise in the study of geometry and kinematics. The
types of solutions which arise are examined, and categorised. The concepts of start and
target systems are introduced, and the path-following techniques used in numerical con-
tinuation are described in some detail. Two main methods of reducing the number of so-
lution paths to follow are considered. The first is multi-homogenisation, and techniques
for using this method are presented, along with an automated method of generating start
systems. The second is the polyhedral homotopy method, and again, a practical guide
to its use as a solver is given. Readers wishing to learn more about the mathematical
basis of the polyhedral method will find Li (1999) and Huber & Sturmfels (1995) to be
useful sources. The depth of content in Chapter 2 is thought to be sufficient for a basic
understanding of the processes involved in using polynomial continuation in the design
of deployable linkages.
Chapter 3 focuses on a type of plane symmetric 6-bar linkage which has been pro-
posed as a reliable, single degree of freedom deployable frame/ring for space applica-
tions. The rectangular version of the linkage, with width twice its length, has three to
four design parameters (depending on whether the new variable γ is introduced or not)
pertaining to the exact orientation of the hinges joining each of the bars. The linkage is
a Bricard plane symmetric case, and its Denavit-Hartenberg parameters can be written in
terms of the four angular design parameters of the 6-bar foldable ring. The three design
parameter version of the ring was subjected to a design process using polynomial contin-
uation by way of a simple compatibility equation for the loop. Further work required on
this topic includes; an extensive study of possible deployment mechanisms, focusing on
reliability; an analysis of the stretch in a membrane attached to the frame as it deploys
(could be a critical design factor if the attached membrane is particularly fragile); and
an analysis of the stiffness and vibration properties of the frame. Stiffness and vibration
properties are of particular importance in space applications.
149
The subject of Chapter 4 is a particular type of deployable ring with N bars, and rota-
tional symmetry of order N/2. An inventory of existing deployable rings with rotational
symmetry is given, of which the type of ring first proposed in Crawford et al. (1975) (in
particular the variant in which only one hinge is used to attach each bar to the next in
a loop) is identified as the main focus for the rest of the chapter. The majority of the
chapter is concerned with a continuation-based design process, much like that in Chapter
3. Again, a compatibility equation (making use of the symmetry of the ring to simplify
expressions) is used to design the ring by means of a series of angular precision points,
except that this time, the angles are global bar orientations rather than internal hinge an-
gles. A greater variety of design options is also presented, with various combinations of
the design variables used to illustrate the range of controls a designer can bring to bear
on the problem. A method of simulation of the ring’s motion based on the compatibility
equations is also provided. Future work on this topic could include a scan of the feasible
space of the design variables (as in Section 3.4), as well as an examination of deployment
techniques. The multiple degrees of freedom present in rings of the type presented in this
chapter make reliable deployment a more challenging problem.
In Chapter 5, the focus is again on deployable rings, except that in this case consid-
eration is given to rings whose deployed shape is not necessarily a regular polygon. For
computational simplicity, the number of bars is restricted to eight. By way of contrast
with the two preceding chapters, a system of transfer equations is used as the basis of
the polynomial continuation design process. Symmetry is still used to limit the size of
the expressions. Also different is the way in which constraints are placed on the system.
Rather than a series of angular precision points, a series of distance-based constraints is
used to specify the stowed shape of the ring precisely. This illustrates the usefulness of
continuation in designing a deployable structure to meet strict practical requirements.
Finally, Chapter 6 presents a slightly less practical, but nonetheless interesting, ap-
plication of polynomial continuation to the field of linkage design. Continuation can be
used to enumerate the possible configurations for a linkage, once a connectivity has ac-
tually been specified. This analysis is performed on the 6-link variant of the N-loop. The
equation structures of the 7 and 8-link versions of the N-loop are scanned for positive
dimensional solution sets, and witness sets are generated for the irreducible components
responsible for the loops’ mobility.
The power of polynomial continuation as a design tool has been illustrated by way
of several examples. Continuation allows a linkage (or deployable structure) designer to
break the design process down into two key stages. First, he/she decides which features
are essential for the linkage’s purpose. These features can be represented as mathemati-
150
cal constraints, which are applied during the continuation process to yield a collection of
design options, all of which meet these constraints. If the linkage closure/compatibility
equations, and the constraint equations have been posed correctly, then the use of contin-
uation guarantees that every possible design option satisfying the imposed constraints
will be found. In the second stage of the process the designer can confidently exercise
his/her judgement in deciding which of the feasible options best suits the application
under consideration (see sections 5.1 and 5.2). Continuation reduces uncertainty, and al-
lows a designer to be at once objective and subjective in deriving the best solution to the
problem at hand.
151
Glossary
Be´zout Number A measure of the number of solutions of a system of polynomial equa-
tions based on an n-Homogenised version of those equations (includes multiplic-
ities). It is less than or equal to the total degree, but greater than or equal to the
Mixed Volume. 30
Cascade of Homotopies A series of homotopies used in the process of finding Witness
Set members at various dimensionalities. 49
Closure Equation An equation, or set of equations, which is used to ensure that a link-
age is connected in a loop. 9
Coefficient Homotopy A form of Homotopy in which only the coefficients of a system
of polynomial equations are functions of the Homotopy Parameter. 38
Compatibility Equation An equation, or set of equations, which is used to ensure that
one or more parts of a linkage are connected in a way which is physically realisable
and compatible. 9, 73
Conformational Space The space of feasible assemblies of a linkage. Often used to
describe assemblies of molecules. 138
Constraint Equation An equation, or set of equations, which is used to enforce design
constraints or realisable limits mathematically. 9
Convex Polygon A two-dimensional version of a convex polytope. 117
Convex Polytope Otherwise known as a convex polyhedron; it is an n dimensional shape
whose vertices define a convex set of points. 34
Denavit-Hartenberg A minimal line (four parameter) representation in robotics first
proposed by Denavit and Hartenberg. 16, 63
152
Glossary
Deployable Structure A structure capable of a large change in size, usually with a
smaller stowed configuration, and a larger deployed configuration. 1
Frame A linkage which has a rigid configuration which defines a particular shape. It is
often used as a mount for membranes. 4
Geometric Degree of Freedom A mobility or degree of freedom not accounted for by
the Kutzbach Criterion. It usually arises in a linkage as a result of some special
symmetry, or conformation. 5, 154
Geometrically Isolated A solution to a system of equations which has no other solutions
in the immediate vicinity. 19
Homogenised A homogeneous polynomial has monomials which all have the same total
degree. A polynomial can be homogenised via the addition of new homogeneous
variables. 20, 152
Homotopy For functions g and f : X → Y , a homotopy is a “family of continuous
functions h(t) : X → Y for t ∈ [0, 1]”1 such that h(0) = g and h(1) = f and the
map t → h(t) is continuous from [0, 1]. 23, 152–154
Homotopy Parameter The homotopy parameter is the variable t → h(t) which drives
the Homotopy. 23, 152
Irreducible Component A connected continuum of solutions existing at a given dimen-
sion in solution space. 50, 68, 154
Lifting Function A function applied to each of the elements of the supports of a system
of polynomial equations to lift the supports up a dimension. 37
Line Symmetric In two dimensions is usually used to refer to a reflection across a line
(2D version of plane symmetry). In three dimensions can be used to refer to a
rotational symmetry about a line, or axis. 62
Minkowski Sum The result of adding every element of one set to every element of an-
other. 35
Mixed Supports A collection of Supports for a system of equations, each support being
unique. 40, 79
1http://en.wikipedia.org/wiki/Homotopy
153
Glossary
Mixed Volume The combined area/volume of all the level-r subfaces for a subdivision
of a set of lifted supports. Practically, it provides an upper bound on the number of
solutions to a given system of polynomial equations. 34, 68, 152, 154
Monodromy Literally means to “move around singly”, and pertains to the movement
of various objects around a singularity. The process is used here to check the
membership of Irreducible Components. 50, 141
Monomial A product of powers of the variables of a system of equations. Sometimes
also used to refer to the individual terms of a polynomials (products of powers of
variables and their coefficients). 34
Numerical Continuation Amathematical technique for finding solutions of a system of
equations. Solutions of a known system of equations are tracked numerically into
those of the unknown system. 11, 18, 154, 155
Overconstrained Mechanism A subset of linkages with a Geometric Degree of Free-
dom. 5, 67
Polyhedral Homotopy A form of Homotopy which is based on a lifted support subdi-
vision. It is used to find a full complement of solutions to a system of polynomial
equations, with a number of start solutions equal to the Mixed Volume. 16
Polynomial Continuation The same as Numerical Continuation, applied specifically to
polynomial systems. 11, 18
Positive Dimensional A positive dimensional solution set is a continuum of non-geometrically
isolated solutions which exists on a line, or manifold in the solution space. 19, 20
Precision Point A point, either in physical space, or in the design parameter space of a
linkage, which acts as a design target for the linkage. 8, 58
Ring A closed loop deployable linkage. 4
Semi-Mixed Supports A collection of Supports for a system of equations with some,
but not all of the supports being unique. 40, 79
Singular Solution A solution of a system of equations which defines a location at which
the system’s Jacobian is indeterminate. 19
154
Glossary
Solution at Infinity A solution of a non-homogeneous system of polynomial equations
which does not exist in the finite plane. 19
Start System In Numerical Continuation, a start system forms the start point for a ho-
motopy. It is usually a system of equations with a similar structure as the Target
System, but with known solutions. 23
Support A representation (as a set of vectors) of the powers of each of the variables in
each of the monomials in a polynomial equation. 34, 153, 154
Target System In Numerical Continuation, a target system forms the end point for a
homotopy. It is usually a system of equations with unknown solutions. 23, 155
Univariate A univariate polynomial is written in terms of a single variable only. 31, 138
Witness Set A witness set is a collection of points on a positive dimensional solution
set of a particular dimension. A full witness set contains as many elements as the
degree of the positive dimensional solution set. 17, 49, 139, 152
Zero Dimensional Solution Another way of saying that a solution is geometrically iso-
lated. 48
155
References
ABBOTT, T. & BARTON, R. (2004). Generalizations of Kempe’s universality theorem.
Manuscript. 8
ALLGOWER, E.L. & GEORG, K. (1980). Simplicial and continuation methods for ap-
proximating fixed points and solutions to systems of equations. SIAM Review, 22, 28–
85. 23
ALLGOWER, E.L. & GEORG, K. (2003). Introduction to Numerical Continuation Meth-
ods. Society for Industrial and Applied Mathematics (SIAM). 11
ANGELES, J., ALIVIZATOS, A. & AKHRAS, R. (1988). An unconstrained nonlinear
least-square method of optimization of RRRR planar path generators. Mechanism and
Machine Theory, 23, 343–353. 9
BAKER, J. (1980). An analysis of the Bricard linkages.Mechanism and Machine Theory,
15, 267–286. 62
BAKER, J.E. (2005). A curious new family of overconstrained six-bars. ASME Journal
of Mechanical Design, 127, 602–606. 62
BAKER, J.E. (2006). On generating a class of foldable six-bar spatial linkages. ASME
Journal of Mechanical Design, 128, 374–784. 62
BERNSTEIN, D.N. (1975). The number of roots of a system of equations. Functional
Analysis and its Applications, 9, 183–185. 34, 35, 37
BRAUN, R.D. & KROO, I.M. (1995). Development and application of the collaborative
optimization architecture in a multidisciplinary design environment. Tech. rep., NASA
Langley (NASA-95-iciam.rdb ). 9
BRICARD, R. (1897). Me´moire sur la the´orie de l‘octae`dre articule´. Journal de
mathe´matiques pures et applique´es, 3, 113–148. 56
156
REFERENCES
BRYANT, J. & SANGWIN, C. (2008). How Round Is Your Circle?. Princeton University
Press. 7
CHABLAT, D. & ANGELES, J. (2003). The computation of all 4R serial spherical wrists
with an isotropic architecture. Journal of Mechanical Design, 125, 275–280. 12
CHEN, Y. (2003). Design of Structural Mechanisms. Ph.D. thesis, University of Oxford.
56, 62
CHEN, Y. & YOU, Z. (2005). Mobile assemblies based on the Bennett linkage. Proceed-
ings of The Royal Society London A, 461, 1229–1245. 62
CHEN, Y. & YOU, Z. (2006a). Square deployable frames for space applications. part 1:
theory. Journal of Aerospace Engineering, 220, 347–354. 6, 56
CHEN, Y. & YOU, Z. (2006b). Square deployable frames for space applications. part 2:
realization. Journal of Aerospace Engineering, 221, 37–45. 6, 56
CHEN, Y. & YOU, Z. (2007). Spatial 6R linkages based on the combination of two
Goldberg 5R linkages.Mechanism and Machine Theory, 42, 1484–1498. 62
CHEN, Y. & YOU, Z. (2008). An extended Myard linkage and its derived 6R linkages.
Journal of Mechanical Design, 130, 052301,1–052301,8. 62
CHEN, Y. & YOU, Z. (2009). Two-fold symmetrical 6R foldable frame and its bifurca-
tions. International Journal of Solids and Structures, 46, 4504–4514. 56, 57, 65, 67,
77, 136
CHEN, Y., YOU, Z. & TARNAI, T. (2004). Threefold-symmetric Bricard linkages for
deployable structures. International Journal of Solids and Structures, 42, 2287–2301.
5, 56
CHTCHERBA, A.D. & KAPUR, D. (2004). Constructing Sylvester-type resultant ma-
trices using the Dixon formulation. Journal of Symbolic Computation, 38, 777–814.
11
CRAWFORD, R.F., HEDGEPETH, J.M. & PREISWERK, P.R. (1974). Spoked wheels to
deploy large surfaces in space: weight estimates for solar arrays. In Canadian Aero-
nautics and Space Institute and American Institute of Aeronautics and Astronautics,
Joint Meeting, Toronto, Canada; United States.. 86, 90, 91
157
REFERENCES
CRAWFORD, R.F., HEDGEPETH, J.M. & PREISWERK, P.R. (1975). Spoked wheels to
deploy large surfaces in space-weight estimates for solar arrays. Tech. Rep. NASA-
CR-2347; ARC-R-1004, NASA. 56, 86, 88, 90, 102, 112, 150
CUI, L. & DAI, J. (2011). Axis constraint analysis and its resultant 6R double-centered
overconstrained mechanisms. Journal of Mechanisms and Robotics, 3. 5
DE FOCATIIS, D.S.A. & GUEST, S.D. (2002). Depolyable membranes designed from
folding tree leaves. Philosophical Transactions of The Royal Society A, 360, 227–238.
2
DEMAINE, E.D. & O’ROURKE, J. (2007). Geometric Folding Algorithms. Linkages,
Origami, Polyhedra.. Cambridge University Press. 7
DHINGRA, A.K., CHENG, J.C. & KOHLI, D. (1994). Synthesis of six-link, slider-crank
and four-link mechanisms for function, path and motion generation using homotopy
with m-homogenization. Journal of Mechanical Design (ASME), 116, 1122–1131. 30
DIAB, N. & SMAILI, A. (2008). Optimum exact/approximate point synthesis of planar
mechanisms. Mechanism and Machine Theory, 43, 1610–1624. 9
EMIRIS, I.Z. (1994). Sparse Elimination and Applications in Kinematics. Ph.D. thesis,
University of California at Berkeley. 11, 12
EMIRIS, I.Z. & MOROZ, G. (2011). The assembly modes of rigid 11-bar linkages. In
International Federation for the Promotion of Mechanism and Machine Science. 11,
13
EMIRIS, I.Z. & MOURRAIN, B. (1996). Polynomial system solving and the case of the
six-atom molecule. Tech. Rep. 3075, INRIA. 11, 12
ERDOS, P. & GRUNWALD, T. (1939). On polynomials with only real roots. The Annals
of Mathematics, 40, 537–548. 12
FANG, H., LOU, M., HUANG, J., QUIJANO, U. & PELAEZ, G. (2004). Development of
a 7-meter inflatable reflectarray antenna. In 45th AIAA/ASME/ASCE/AHS/ASC Struc-
tures, Structural Dynamics & Materials Conference, Palm Springs, CA., USA.. 4
FREUDENSTEIN, F. & MAKI, E.R. (1979). The creation of mechanisms according to
kinematic structure and function. Environment and Planning B, 6, 375–391. 7, 62, 67
158
REFERENCES
GAN, W.W. & PELLEGRINO, S. (2003). Closed-loop deployable structures. In 44th
AIAA/ASME/ASCE/AHS Structures, Structural Dynamics, and Materials Conference.
5, 56
GAN, W.W. & PELLEGRINO, S. (2005). Kinematic bifurcations of closed-loop deploy-
able frames. In Proceedings of the 5th International Conference on Computation of
Shell and Spatial Structures. 56, 77
GAN, W.W. & PELLEGRINO, S. (2006). Numerical approach to the kinematic analysis
of deployable structures forming a closed loop. Journal of Mechanical Engineering
Science, 220, 1045–1056. 6, 56, 65, 66, 67, 77, 92, 113, 136
GANTES, C.J. (2001).Deployable Structures: Analysis and Design. Southampton : WIT
Press. 1
GAO, T. & LI, T.Y. (2003). Mixed volume computation for semi-mixed systems. Dis-
crete and Computational Geometry, 29, 257–277. 68
GAO, T., LI, T.Y., VERSCHELDE, J. & WU, M. (2000). Balancing the lifting values to
improve the numerical stability of polyhedral homotopy continuation methods. Applied
Mathematics and Computation, 114, 233–247. 47
GAO, X.S., ZHU, C.C., CHOU, S.C. & GE, J.X. (2001). Automated generation of
Kempe linkages for algebraic curves and surfaces. Mechanism and Machine Theory,
36, 1019–1033. 8
GE, J.X., CHOU, S.C. & GAO, X.S. (1999). Geometric constraint satisfaction using
optimization methods. Computer-Aided Design, 31, 867–879. 9
GOSSELIN, C. & ANGELES, J. (1990). Singularity analysis of closed kinematic chains.
IEEE Transactions on Robotics and Automation, 6, 281–290. 72
GUAN, Y. & VERSCHELDE, J. (2008). Software for Algebraic Geometry, vol. 148.
Springer New York. 18
GUEST, S.D. (1994). Deployable Structures: Concepts and Analysis. Ph.D. thesis, Uni-
versity of Cambridge. 1
GUEST, S.D. & FOWLER, P.W. (2010). Mobility of ‘N-Loops’: bodies cyclically con-
nected by intersecting revolute hinges. Proceedings of The Royal Society A, 466, 63–
77. 136, 139, 144, 145
159
REFERENCES
HARRIS-CORPORATION (1986). Development of the 15 meter diameter hoop column
antenna. Tech. rep., NASA Langley Research Center. 87, 88
HARTENBERG, R. & DENAVIT, J. (1964). Kinematic Synthesis of Linkages. McGraw-
Hill Book Company. 7
HENDERSON, M.E. (2004). Multiparameter continuation methods. http:
//www.research.ibm.com/people/h/henderson/Continuation/
ContinuationMethods.html. 23
HOFFMANN, C. & VERMEER, P.J. (1995). Geometric constraint solving in R2 and R3.
In World Scientific, Singapore. 11
HOPCROFT, J., JOSEPH, D. & WHITESIDES, S. (1984). Movement problems for 2-
dimensional linkages. SIAM Journal on Computing, 13, 610–629. 8
HRONES, J.A. & NELSON, G.L. (1951). Analysis of the four-bar linkage; its application
to the synthesis of mechanisms. The Technology Press, The Massachusetts Institute of
Technology. 7
HUBER, B. & STURMFELS, B. (1995). A polyhedral method for solving sparse polyno-
mial systems. Mathematics of Computing, 64, 1541–1555. 37, 149
HUTT, T. (2007). Deployable rings. Tech. rep., University of Cambridge. 56
JENSEN, F. & PELLEGRINO, S. (2002). Expandable structures formed by hinged plates.
In Fifth International Conference on Space Structures. 2
JENSEN, F. & PELLEGRINO, S. (2005). Expandable “blob” structures. Journal of the
International Association for Shell and Spatial Structures, 46, 151–158. 2
KEMPE, A.B. (1877). How to draw a straight line; a lecture on linkages. MacMillan and
Co. (Now available online through Project Gutenberg). 8
KONAXIS, C. (2010). Algebraic Algorithms for Polynomial System Solving and Applica-
tions. Ph.D. thesis, National and Kapodistrian University of Athens. 35
KRISHNAMURTY, S. & TURCIC, D.A. (1992). Optimal synthesis of mechanisms using
nonlinear goal programming techniques. Mechanism and Machine Theory, 27, 599–
612. 9
KUMAR, P. & PELLEGRINO, S. (2000). Computation of kinematic paths and bifurcation
points. International Journal of Solids and Structures, 37, 7003–7027. 77
160
REFERENCES
LALOI, N. (1999). Analytical and experimental study of a new type of hinges. Tech. rep.,
Deployable Structures Laboratory, Dept. of Engineering, University of Cambridge.
132
LAMURE, H. & MICHELUCCI, D. (1996). Solving geometric constraints by homotopy.
IEEE Transactions on Visualization and Computer Graphics, 2, 28–34. 19
LEE, H.Y. & LIANG, C.G. (1988). Displacement analysis of the general spatial 7-link
7R mechanism. Mechanism and Machine Theory, 23, 219–226. 11
LEE, T.L. & LI, T.Y. (2007). Mixed volume computation, a revisit. 35
LEE, T.L., LI, T.Y. & TSAI, C.H. (2008). HOM4PS-2.0: a software package for solving
polynomial systems by the polyhedral homotopy continuation method. Computing, 83,
109–133. 18
LENGYEL, A. & YOU, Z. (2004). Bifurcations of SDOF mechanisms using catastrophe
theory. International Journal of Solids and Structures, 41, 559–568. 77
LEYKIN, A., VERSCHELDE, J. & ZHAO, A. (2000). Evaluation of Jacobian matrices for
Newton’s method with deflation to approximate isolated singular solutions of polyno-
mial systems. 20
LI, T.Y. (1999). Solving polynomial systems by polyhedral homotopies. Taiwanese Jour-
nal of Mathematics, 3, 251–279. 34, 37, 149
LI, T.Y. (2003). Handbook of Numerical Analysis, vol. XI, chap. Numerical Solution of
Polynomial Systems by Homotopy Continuation Methods, 209–304. North-Holland.
34, 37, 40, 79
LUO, Z. & DAI, J. (2007). Patterned bootstrap: A new method that gives efficiency
for some precision position synthesis problems. Journal of Mechanical Design, 129,
173–183. 12
MANOCHA, D. & CANNY, J.F. (1994). Efficient inverse kinematics for general 6R ma-
nipulators. IEEE Transactions on Robotics and Automation, 10, 648–657. 13
MAO, D., LUO, Y. & YOU, Z. (2009). Planar closed loop double chain linkages.Mech-
anism and Machine Theory, 44, 850–859. 3
161
REFERENCES
MARTI´NEZ-ALFARO, H. (2007). Advances in Metaheuristics for Hard Optimization,
chap. Four-Bar Mechanism Synthesis for n Desired Path Points Using Simulated An-
nealing, 23–37. Springer Berlin Heidelberg. 9
MARTINS, J.R.R.A., STURDZA, P. & ALONSO, J.J. (2003). The complex-step deriva-
tive approximation. ACM Transactions on Mathematical Software, 29, 245–262. 48
MAVROIDIS, C. & ROTH, B. (1994). Analysis and synthesis of overconstrained mech-
anisms. In Proceeding of the 1994 ASME Design Technical Conference, Minneapolis,
MI, September, 115–133. 5
MIZUTANI, T., TAKEDA, A. & KOJIMA, M. (2007). Dynamic enumeration of all mixed
cells. Discrete and Computational Geometry, 37, 351–367. 47
MORGAN, A. (1987). Solving Polynomial Systems Using Continuation for Engineering
and Scientific Problems. Prentice-Hall, inc. 23
MORGAN, A. & WAMPLER, C. (1990). Solving a planar four-bar design problem using
continuation. Journal of Mechanical Design, 112, 544–550. 13
MORGAN, A.P. & SOMMESE, A.J. (1989). Coefficient-parameter polynomial continua-
tion. Applied Mathematics and Computation, 29, 123–160. 34
NIELSEN, J. (1997). Solving Sets of Nonlinear Equations for the Design and Analysis of
Mechanical Systems. Ph.D. thesis, Dept. Of Mechanical Engineering, Leland Stanford
Junior University. 11
OWEN, J.C. (1991). Algebraic solution for geometry from dimensional constraints. In
ACM Symposium on Solid and Physical Modeling. 11
PELLEGRINO, S. (1995). Large retractable appendages in spacecraft. Journal of Space-
craft and Rockets, 32, 1006–1014. 3
PELLEGRINO, S., ed. (2001). Deployable Structures. Springer-Verlag Wien New York.
1
PELLEGRINO, S. & YOU, Z. (1993). Foldable ring structures. In G. Parke & C. Howard,
eds., Space Structures 4: The Fourth International Conference on Space Structures,
vol. 1. 3
162
REFERENCES
PELLEGRINO, S., GREEN, C., GUEST, S.D. & WATT, A. (2000). SAR advanced de-
ployable structure. Tech. rep., University of Cambridge Department of Engineering. 6,
56, 132
PHILLIPS, J. (1984). Freedom in Machinery, vol. 1. Cambridge University Press. 62
PHILLIPS, J. (1990). Freedom in Machinery, vol. 2. Cambridge University Press. 62
PORTA, J., ROS, L., THOMAS, F., CORCHO, F., CANTO´, J. & PE´REZ, J. (2007). Com-
plete maps of molecular-loop conformational spaces. Journal of Computational Chem-
istry, 28, 2170–2189. 136
RAGHAVAN, M. & ROTH, B. (1993). Inverse kinematics of the general 6R manipulator
and related linkages. Journal of Mechanical Design, 115, 502–508. 12, 13
READ, R.C. & WILSON, R.J. (1998). An Atlas of Graphs. Oxford University Press. 7
RIDOUT, M.S. (2009). Statistical applications of the complex-step method of numerical
differentiation. The American Statistician, 63, 66–74. 48
SANCIBRIAN, R., VIADERO, F., GARCI´A, P. & FERNA´NDEZ, A. (2004). Gradient-
based optimization of path synthesis problems in planar mechanisms. Mechanism and
Machine Theory, 39, 839–856. 9
SEFFEN, K.A. & PELLEGRINO, S. (1999). Deployment dynamics of tape springs. Pro-
ceedings of The Royal Society London A, 455, 1003–1048. 4
SOESENO, J. (1990). Applications of Homotopy to Kinematic Synthesis and Analysis.
Master’s thesis, University of Wisconsin-Milwaukee. 12
SOMMESE, A.J. & VERSCHELDE, J. (2000). Numerical homotopies to compute generic
points on positive dimensional algebraic sets. Journal of Complexity, 16, 572–602. 49,
56, 67, 68
SOMMESE, A.J. & WAMPLER, C.W. (2005). The Numerical Solution of Systems of
Polynomials Arising in Engineering and Science. World Scientific. 31, 35, 50
SOMMESE, A.J., VERSCHELDE, J. & WAMPLER, C.W. (2001a). Numerical decompo-
sition of the solution sets of polynomial systems into irreducible components. SIAM
Journal of Numerical Analysis, 38, 2022–2046. 51, 52, 67
163
REFERENCES
SOMMESE, A.J., VERSCHELDE, J. & WAMPLER, C.W. (2001b). Using monodromy
to decompose solution sets of polynomial systems into irreducible components. In
C. Ciliberto, F. Hirzebruch, R. Miranda & M. Teicher, eds., Application of Algebraic
Geometry to Coding Theory, Physics and Computation, 297–315, NATO, Kluwer Aca-
demic Publishers. 52
SOMMESE, A.J., VERSCHELDE, J. & WAMPLER, C.W. (2002a). Advances in poly-
nomial continuation for solving problems in kinematics. In Proceedings of DETC’02,
ASME Design Engineering Technical Conferences. 12, 13
SOMMESE, A.J., VERSCHELDE, J. & WAMPLER, C.W. (2002b). Algebraic Geome-
try, chap. A method for tracking singular paths with application to the numerical irre-
ducible decomposition, 329–345. de Gruyter. 52
STURMFELS, B. & ZELEVINSKY, A. (1994). Multigraded resultants of Sylvester type.
Journal of Algebra, 163, 115–127. 11
SUBBIAN, T. (1990).Use of ContinuationMethods for Kinematic Synthesis and Analysis.
Ph.D. thesis, Iowa State University, Ames, IA. 13
SUBBIAN, T. & FLUGRAD, D.R. (1991). Four-bar path generation synthesis by a con-
tinuation method. Journal of Mechanical Design, 113, 63–69. 13
TIBERT, G. (2002). Deployable Tensegrity Structures for Space Applications. Ph.D. the-
sis, Royal Institute of Technology, Department of Mechanics, Stockholm. 85, 87
VERSCHELDE, J. (1999). Algorithm 795: PHCpack: a general-purpose solver for poly-
nomial systems by homotopy continuation. ACM Transactions on Mathematical Soft-
ware (TOMS), 25, 251–276. 18
VERSCHELDE, J. (2009). Witness sets. Lecture, UIC Dept. of Math, Stat and CS. 48, 49
VERSCHELDE, J. (2011). Database of polynomial systems. http://www.math.
uic.edu/˜jan/. 12
VERSCHELDE, J. & GATERMANN, K. (1995). Symmetric Newton polytopes for solving
sparse polynomial systems. Advances in Applied Mathematics, 16, 95–127. 37
VERSCHELDE, J., GATERMANN, K. & COOLS, R. (1996). Mixed volume computation
by dynamic lifting applied to polynomial system solving. Discrete and Computational
Geometry, 16, 69–112. 47
164
REFERENCES
WAMPLER, C.W. & MORGAN, A.P. (1993). Solving the kinematics of general 6R ma-
nipulators using polynomial continuation. Institute of Mathematics and its Applica-
tions Conference Series, 41, 57. 13
WAMPLER, C.W., MORGAN, A.P. & SOMMESE, A.J. (1990). Numerical continuation
methods for solving polynomial systems arising in kinematics. Journal of Mechanical
Design, 112, 59–68. 12, 13, 23, 30, 32
WAMPLER, C.W., MORGAN, A.P. & SOMMESE, A.J. (1992). Complete solution of
the nine-point path synthesis problem for four-bar linkages. Journal of Mechanical
Design, 114, 153–159. 13, 14
WATSON, L.T., BILLUPS, S.C. & MORGAN, A.P. (1987). Algorithm 652: HOMPACK:
a suite of codes for globally convergent homotopy algorithms. ACM Transactions on
Mathematical Software (TOMS), 13, 281–310. 18
YOU, Z. (2007). Motion structures extend their reach.Materials Today, 10, 52–57. 5
YOU, Z. & PELLEGRINO, S. (1997a). Cable-stiffened pantographic deployable struc-
tures part 2: Mesh reflector. AIAA Journal, 35, 1348–1355. 3
YOU, Z. & PELLEGRINO, S. (1997b). Foldable bar structures. International Journal of
Solids and Structures, 34, 1825–1847. 3
ZULEHNER, W. (1988). A simple homotopy method for determining all isolated solu-
tions to polynomial systems.Mathematics of Computation, 50, 167–177. 11, 23
165
A. Feasibility Charts for
Plane-Symmetric 6-Bar Linkage
Feasible region based on
singularity limits.
Feasible region based on
singularity, and hinge
directional limits.
Singularity contour.
Chart plane of symmetry.
Boundary of region for
ZKLFKș12 opens with
VDPHVLJQDVș61.
Boundary of region for
which ș23 always has the
same sign.
Figure A.1: Key to feasibility charts for plane-symmetric 6-bar linkage
166
0 S/8 S/4 3S/8 S/2
-S/2
-3S/8
-S/4
-S/8
0
Į1
Į2
Figure A.2: Feasibility chart for γ = π/8
167
0 S/8 S/4 3S/8 S/2
-S/2
-3S/8
-S/4
-S/8
0
Į1
Į2
Figure A.3: Feasibility chart for γ = π/4
168
0 S/8 S/4 3S/8 S/2
-S/2
-3S/8
-S/4
-S/8
0
Į1
Į2
Figure A.4: Feasibility chart for γ = 3π/8
169
0 S/8 S/4 3S/8 S/2
-S/2
-3S/8
-S/4
-S/8
0
Į1
Į2
Figure A.5: Feasibility chart for γ = π/2
170
0 S/8 S/4 3S/8 S/2
-S/2
-3S/8
-S/4
-S/8
0
S/8
Į2
Į1
Figure A.6: Feasibility chart for γ = 5π/8
171
0 S/8 S/4 3S/8 S/2
-S/2
-3S/8
-S/4
-S/8
0
S/8
S/4
Į2
Į1
Figure A.7: Feasibility chart for γ = 3π/4
172
0 S/8 S/4 3S/8 S/2
-S/2
-3S/8
-S/4
-S/8
0
S/8
S/4
3S/8
Į2
Į1
Figure A.8: Feasibility chart for γ = 7π/8
173
0 S/8 S/4 3S/8 S/2
-S/2
-3S/8
-S/4
-S/8
0
S/8
S/4
3S/8
S/2
Į1
Į2
Figure A.9: Feasibility chart for γ = π
174
B. Software Guide
The polyhedral homotopy software was written entirely in Matlab. Matlab provides a
flexible programming environment, and an extensive library of functions.
B.1 Using Software to Find Dimension-Zero Solutions of
a System of Polynomial Equations
The first step in using any of the software utilised in solving nearly all of the problems
included in this document is to express the terms of the equations in a compact, and
immediately useful notation. As an example, consider equation system 2.2. This system
consists of three equations in three unknowns, and is therefore the kind of square system
one would expect to have a number of dimension-zero, geometrically isolated solutions.
The support and coefficient list for the system must be expressed in matrix format, which
in this case looks like:
i) Support:
0 0 0
2 1 1
0 2 0
0 0 1
Coefficients:
0
1
2
−5
ii) Support:
0 0 01 1 0
0 0 1
Coefficients:
−23
1
iii) Support:
0 0 0
1 0 0
0 1 0
0 0 1
Coefficients:
0
2
−1
1
where i, ii and iii represent each of the three equations. Each row represents a term of
the equation, and each column represents a variable. Note that a constant term (all zero
row) has been included in each support. The support arrays are arranged into a structure
called S (with .support extension), while the target system coefficients are arranged
into a structure called TargStruc (with .coeff extension). These two structures are
the only inputs required to fully solve the target system of polynomial equations.
Quite often, target systems contain hundreds of monomials, and the supports and
target coefficients can only be reliably organised into arrays via an automated process.
175
B.1 Using Software to Find Dimension-Zero Solutions of a System of Polynomial
Equations
The Mathematica commands Coefficient and CoefficientList were found to be quite
useful in identifying the monomials of target systems, and extracting the coefficients
themselves.
The following is a step-by-step practical guide to the solving of a square system of
polynomial equations.
1. Determine the supports for each equation, and the coefficients of the target system.
This can be done manually, or by some automated process. The results must be
exported to the Matlab file SupportConstruction.m.
• In the case of Equation 2.2, the first support would be entered as:
>> S(1).support = [0,0,0;2,1,1;0,2,0;0,0,1]
while the target coefficients for the first equation are entered as:
>> TargStruc(1).coeff = [0;1;2;-5]
and similarly for the subsequent equations.
• Semi-mixed supports are handled by including the multiplicity of each sup-
port type in the SuppRep vector. For example, a system of five equations in
which the first two supports are identical would be entered as:
>> SuppRep = [2;1;1;1]
• Running SupportConstruction.m loads S, TargStruc and SuppRep to the
workspace.
• TargStruc must be saved as a data file, for example:
>> save TargProblemEg1 TargStruc
2. Lifting values must now be applied to the supports, and a valid subdivision deter-
mined. This is performed by running the function:
>> [SUpdated,KSub,yMat,maxheight,minheight] = ...
PolyStartSimplexMixed(S,SuppRep)
• maxheight gives the largest power of t to appear in Equation 2.28, while
minheight gives the smallest. Both should lie in a range of approximately
0.35 - 8 for numerical stability.
• If the t-powers lie outside the desirable range, the heights can be shifted as
a group via a simple multiplication of all the lifting values, or the spread of
values can be decreased by running:
>> [SUpdated,KSub] = LiftingOpt(SUpdated,KSub,SuppRep)
as many times as necessary (which operates on the lifting values).
• Following an optimisation run, the values of yMat need to be recalculated
using:
>> yMat = yMatCalc(SUpdated,SuppRep,KSub)
• Finally, the data structures must be saved in a file, for example:
>> save StartHomotProblemEg1 SUpdated SuppRep KSub yMat
3. The homotopy of Equation 2.28 must now be carried out, and this is done by run-
ning the function:
176
B.1 Using Software to Find Dimension-Zero Solutions of a System of Polynomial
Equations
>> [XFinalMat,xmatbigMat,tmatMat,FailStats, ...
ReplaceSolLocations] = PolyDriverExacGrad(runsubs,OldFailStats)
• Before running this function, PolyDriverExactGrad.m must be edited to
ensure that it loads the data for the correct start system. In the example under
consideration, StartHomotProblemEg1.mat should be loaded.
• The input runsubs tells the solver which of the subfaces listed in KSub to run.
To generate a complete start system, all subfaces must be run.
• The output, XFinalMat, contains a list of solutions to a start system which
can be used to find the full set of solutions to any target system with the
same polynomial structure. All its solutions should be finite, and the number
of solutions will be equal to the mixed volume of the system (because its
coefficients were randomly chosen complex numbers).
• Before using the start system whose solutions are listed in XFinalMat, the
matrix should be renamed:
>> xStart = XFinalMat
and saved in a new data file:
>> save PolyStartProblemEg1 xStart
4. To solve the target problem, run the function:
>> [xmatout,xmatoutact,xmatbig,Jacobvec,tmat, ...
FailStats] = CoeffDriverExactGrad(runsols)
• Before running this function, CoeffDriverExactGrad.m must be edited to
ensure that it loads the data for the correct start, and target systems. In the ex-
ample under consideration, StartHomotProblemEg1.mat should be loaded
for the start system information, PolyStartProblemEg1.mat for the start
system solutions and TargProblemEg1.mat for the target coefficients.
• The input runsols tells the solver which of the start solutions to pass to the
path follower. Generally, one wishes to run all the start solutions.
• The output, xmatout, contains the solutions to the target system. Paths which
were found to diverge, or fail in some other way appear simply as a column
of NaNs.
177
B.1 Using Software to Find Dimension-Zero Solutions of a System of Polynomial
Equations
Main Data Structures
Structure/Function Sub-Elements Purpose
S .support → Support in array form for each equation
SUpdated .support
.k
.w
.coeff
→
→
→
→
Support in array form for each equation
Number of terms in support
Lifting value for each term
Random complex coefficients
TargStruc .coeff → Coefficients for target system
SuppRep - → Vector containing equation multiplicities
KSub .subfaces
.alpha
.betavec
→
→
→
Support pairs for each subface
α vector for each subface
β values for each subface
yMat .startsols → Solutions to binomial start system
xStart - → All solutions to homotopy in Equation 2.28
xmatout - → All solutions to target system
178
B.1 Using Software to Find Dimension-Zero Solutions of a System of Polynomial
Equations
Polyhedral Homotopy Function List
Function Action Inputs Outputs
SupportConstruction.m A script into which information
about the target polynomial’s
support and coefficients can be
entered.
- S
TargStruc
SuppRep
PolyStartSimplexMixed.m Function assigns random lifting
to each support member, and
computes a valid subdivision.
The α and β vectors of Section
2.4 are computed, as well as the
initial solutions based on each of
the support base pairs.
S
SuppRep
SUpdated
KSub
yMat
LiftingOpt.m Modifies SupRepp and KSub
by implementing the method of
Section 2.4.3 to increase the
hight of the smallest t-power,
and thus increase the numeri-
cal reliability of the following
stages.
SUpdated
KSub
SuppRep
SUpdated
KSub
yMatCalc.m Called by
PolyStartSimplexMixed.m
to compute the solutions to the
t-independent support pairs.
Needs to be called again follow-
ing a lifting value modification,
usually after an application of
LiftingOpt.m.
SUpdated
KSub
SuppRep
yMat
PolyDriverExacGrad.m Implements the homotopy of
Equation 2.28.
SUpdated
KSub
yMat
SuppRep
xStart
StandardPFPolyhedralExa-
ct.m
Is called directly by
PolyDriverExacGrad.m,
and performs the base level path
following for each of the initial
solutions in yMat.
SUpdated
KSub
yMat
SuppRep
xStart
179
B.1 Using Software to Find Dimension-Zero Solutions of a System of Polynomial
Equations
Coefficient Homotopy Function List
Function Action Inputs Outputs
CoeffDriverExactGrad.m Performs a coefficient homo-
topy, converting the random
complex coefficient start system
(whose solutions were computed
by PolyDriverExacGrad.m)
into the target system with the
same polynomial structure,
and coefficients specified in
SupportConstruction.m.
SUpdated
SuppRep
xStart
TargStruc
xmatout
StandardPFCoeffExact.m Standard path following
function called directly by
CoeffDriverExactGrad.m.
SUpdated
SuppRep
xStart
TargStruc
xmatout
180
B.2 Using Software to Find Higher Dimensional Solutions of a System of
Polynomial Equations
B.2 Using Software to Find Higher Dimensional Solu-
tions of a System of Polynomial Equations
The suite of functions written to examine the structure of systems of polynomial equa-
tions makes use of many of the same components as the functions in Section B.1. How-
ever, they were written to be used in a slightly more automated way, with the user specify-
ing the names of some data files in the first instance (within the function SuppComp Step 1.m),
and then simply running a series of other function in a specified order.
The following is a step-by-step practical guide to the solving of a square system of
polynomial equations, which one suspects of having positive dimensional solution sets.
1. Construct the target system function, and name it TargFun.m. This will look like:
>> F = TargFun(x,ExtParams)
• The input should be a column vector containing the n variables;
• The output should be a column vector containing the evaluated polynomials.
2. The function SuppComp Step 1.m loads the target system information into the
workspace. Run this as:
>> [S,SuppRep,HyperCoeff0,FileNames] = SuppComp Step 1(d)
• First, manually enter the support data into the function’s script. This is done
in the same way as the dimension-zero case.
• No target system coefficients need be specified, as an external target function
is used.
• All the data files used in the following process must be named in this function
file. The names are stored in a structure called FileNames, passed to all
subsequent functions.
• The vector SuppRep must be a column of ones. No shorthand for mixed
supports is permitted in the witness set construction process.
• The only explicit input to SuppComp Step 1.m is the parameter d, which
specifies how many new variables/complex hyperplanes should be appended
to the target system. This is the top dimension to be searched. Setting d = 0
reduces the problem to a search for zero dimensional solutions, as in Section
B.1.
3. Next, run the subdivision finder. This looks like:
>> [SUpdated,KSub,yMat,maxheight,minheight] = ...
PolyStartSimplexMixed Step 2(S,SuppRep,FileNames)
This behaves in just the same way as its 0D counterpart, except that the start system
data files are automatically saved using the names specified in SuppComp Step 1.m.
4. The lifting value optimiser:
>> [SUpdated,KSub] = LiftingOpt Step 3(SUpdated,KSub,SuppRep)
also behaves much like its 0D counterpart.
181
B.2 Using Software to Find Higher Dimensional Solutions of a System of
Polynomial Equations
• Once a lifting value optimisation has been performed, the solutions in yMat
will have to be recalculated by running:
>> yMat = yMatCalc(S,SuppRep,KSub)
then re-saving the start polynomial data using:
>> save(FileNames.StartSys,’SUpdated’,’SuppRep’,’KSub’, ...
’yMat’)
5. The top level augmented start system can be completely solved by running:
>> [XFinalMat,xmatbigMat,tmatMat,FailStats, ...
ReplaceSolLocations] = DriverPolyhedral Step 4(runsubs, ...
FileNames,OldFailStats)
• Once again, runsubs specifies the subfaces to be run.
• XFinalMat contains the solutions to the augmented (top level) start system.
The solutions are automatically saved in a data file for use in solving the target
system later.
6. To solve the top level augmented target system, run:
>> [xmatout,xmatoutact,xmatbig,Jacobvec,tmat, ...
FailStats] = DriverCoeff Step 5(runsols,FileNames)
• The output, xmatout, contains the solutions to the top level target system
(augmented with d random complex hyperplanes and d new variables, z. This
output is automatically saved using the name specified in SuppComp Step 1.m.
• Solutions which form part of the witness set for dimension d can already be
recognised by their z variables being zero.
7. Next, run:
>> [nonsols,highersols,Wout] = WitFilt Step ia(xmatout,[], ...
FileNames)
• This function automatically checks for solutions of dimension d, and places
them in the structure Wout(1).set.
• Any other finite solutions are returned in the matrix nonsols.
8. The next step is to use a cascade process to reduce the dimension of the target
system. This is performed by running:
>> [xmatout,xmatoutact,xmatbig,Jacobvec,tmat, ...
FailStats] = DriverDimReducer Step ib(nonsols,FileNames)
• The points in nonsols are fed into a path follower which reduces the target
system to a dimension of d− 1.
• The output, which over-writes the previous xmatout, contains the solutions
to this dimension d− 1 system.
• Elements of the witness set for d − 1 are identifiable by having zero z com-
ponents.
182
B.2 Using Software to Find Higher Dimensional Solutions of a System of
Polynomial Equations
9. The function WitFilt Step ia.m is run again, except this time it acts as a filter
stage, searching for solutions to the d − 1 dimension equations which are actually
members of the dimension d witness set:
>> [nonsols,highersols,Wout] = WitFilt Step ia(xmatout, ...
Wout,FileNames)
• The structure Wout is used to provide the witness set points to perform the
filter step.
• The new-found elements of the witness set of dimension d− 1 are appended
to the witness set structure as Wout(2).set.
10. Functions WitFilt Step ia.m and DriverDimReducer Step ib are run alterna-
tively until dimension zero is reached. Wout will contain d+ 1 sub-elements at the
end.
183
B.2 Using Software to Find Higher Dimensional Solutions of a System of
Polynomial Equations
Main Data Structures
Structure/Function Sub-Elements Purpose
S .support → Support in array form for each equation
FileNames .RandCoeffs
.StartSys
.PolySys
.Output
→
→
→
→
Name of file containing random hyperplane
coefficients
Name of file containing SUpdated, KSub
and SuppRep
Name of file containing xStart
Name of file containing xmatout
SuppRep - → Vector containing equation multiplicities
SUpdated .support
.k
.w
.coeff
→
→
→
→
Support in array form for each equation
Number of terms in support
Lifting value for each term
Random complex coefficients
KSub .subfaces
.alpha
.betavec
→
→
→
Support pairs for each subface
α vector for each subface
β values for each subface
yMat .startsols → Solutions to binomial start system
xStart - → All solutions to homotopy in Equation 2.28
xmatout - → All solutions to initial augmented target sys-
tem, or the result of a dimension reducing cas-
cade step
nonsols - → Those results of a homotopy run which are de-
termined not to lie on the dimension currently
being examined (z = 0). These results are
passed on to the cascade step
Wout .set → Structure built up over cascade process con-
taining all solutions found to exist at each di-
mension examined
184
B.2 Using Software to Find Higher Dimensional Solutions of a System of
Polynomial Equations
Witness Set Construction Function List
Function Action Inputs Outputs
SuppComp Step 1.m The supports for the target equa-
tions are entered directly into
the file, as well as the multi-
plicity for each support. The
user specifies a dimension (d)
at which to begin the search for
witness points, and the function
appends an appropriate number
of intersecting complex hyper-
planes and new variables (as per
Equation 2.36).
d S
SuppRep
PolyStartSimplexMixed St-
ep 2.m
Function assigns random lifting
to each support member, and
computes a valid subdivision.
The α and β vectors of Section
2.4 are computed, as well as the
initial solutions based on each of
the support base pairs.
S
SuppRep
FileNames
SUpdated
KSub
yMat
LiftingOpt Step 3.m Modifies SupRepp and KSub
by implementing the method of
Section 2.4.3 to increase the
hight of the smallest t-power,
and thus increase the numeri-
cal reliability of the following
stages.
SUpdated
KSub
SuppRep
SUpdated
KSub
yMatCalc.m Called by
PolyStartSimplexMixed
Step 2.m to compute the so-
lutions to the t-independent
support pairs. Needs to be
called again following a
lifting value modification,
usually after an application of
LiftingOpt Step 3.m.
SUpdated
KSub
SuppRep
yMat
DriverPolyhedral Step 4.m Implements the homotopy of
Equation 2.28.
SUpdated
KSub
yMat
SuppRep
FileNames
xStart
StandardPFPolyhedralExa-
ct.m
Is called directly by
DriverPolyhedral Step 4.m
and performs the base level path
following for each of the initial
solutions in yMat.
SUpdated
KSub
yMat
SuppRep
xStart
...Continued on next page
185
B.2 Using Software to Find Higher Dimensional Solutions of a System of
Polynomial Equations
– continued from previous page
Function Action Inputs Outputs
DriverCoeff Step 5.m Solves the homotopy system of
Equation 2.36.
SUpdated
SuppRep
xStart
FileNames
xmatout
StandardPFCoeff.m Standard path following
function called directly by
DriverCoeff Step 5.m.
SUpdated
SuppRep
xStart
xmatout
TargFun.m A function called directly by
StandardPFCoeff.m. It con-
tains the ‘black-box’ version
of the original target equations.
The user must manually insert
the target system into this func-
tion. Unlike the dimension-zero
process, gradients are taken by a
finite difference method.
- -
WitFilt Step ia.m If this is the top dimension run,
the function simply identifies so-
lutions with z = 0, places them
in Wout and puts the rest in
nonsols. On subsequent calls,
the function checks each solu-
tion for membership of higher
dimensional solution sets using
existing members of Wout, and
removes them if necessary.
xmatout
Wout
FileNames
nonsols
Wout
DriverDimReducer Step ib-
.m
Implements the homotopy
of Equation 2.37 to reduce
the dimension by one. This
function is called in a suc-
cessive iteration process with
WitFilt Step ia.m until
dimension zero is reached.
nonsols
FileNames
xmatout
DriverCoeff Monodromy.m Takes a particular dimension’s
witness set (or a component
thereof) and maps it onto a
new hyperplane, before mapping
back to the original hyperplane.
The output can be checked
for permutations (which indicate
membership of the same irre-
ducible component).
Wout.set
FileNames
xmatout
186