Distance Geometry in Active Structures

Abstract

Distance constraints are an emerging formulation that offers intuitive geometrical interpretation of otherwise complex problems. The formulation can be applied in problems such as position and singularity analysis and path planning of mechanisms and structures. This paper reviews the recent advances in distance geometry, providing a unified view of these apparently disparate problems. This survey reviews algebraic and numerical techniques, and is, to the best of our knowledge, the first attempt to summarize the different approaches relating to distance-based formulations.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Introduction

A structure can be seen as a complex multibody system (see Fig. 1). While rigid structures have been widely used in construction, passive mobile structures are commonly used, for instance, as shock absorbers. The advent of automation, however, opened the possibility for building active structures [1], i.e., structures which can actively vary their geometry as needed. Such structures are mechanisms, since their motions are typically achieved by means of actuated elements such as revolute joints or variable-length bars. Due to their shape versatility, variable geometry structures have myriad potential applications including robot arms [2], hyper-redundant manipulators [3], flight simulators [4], payload vibration reduction systems [5], the manipulation of large payloads [6], morphing wings [7], space applications [8], and civil engineering structures [9].

The design of novel variable geometry structures rely on having a complete characterization of their valid configurations. Such configurations are defined by a system of equations encoding the assembly, task, or contact constraints intervening in the problem, and the goal is to analyze the motion capabilities by studying the solutions and properties of such system. The equations can be encoded with different formulations, and the analysis can be significantly simplified if the right formulation is chosen.

Fig. 1

Structures are typically composed by interconnected rigid bodies and they can have different types of mobility. a A fixed bridge is an example of rigid structure. b The shock absorbers of a bike are passive mobile structures. c Retractable roofs are active structures

The dominant formulation is based on homogeneous transforms using the parameters proposed by Denavit and Hartenberg  [10]. This formulation encodes the relative relation between the reference frames associated with the bodies connected by a given joint. Althouth the motion simulation using such parameters is straightforward, the motion analysis using them is challenging, because the resulting equations typically involve complex trigonometric expressions.

Over the past few years, several works have shown that deviating from this classical approach and formalizing the motion analysis problems using distance constraints can be very advantageous. Distance constraints provide intuitive geometric insights on aspects of the motion analysis problem which are difficult to discern otherwise. Moreover, these geometric insights allow the derivation of solutions common to a group of problems that must otherwise be treated on a case-by-case basis [11,12,13].

In some mechanisms, the configuration space is composed of isolated points. This is what happens, for example, when solving the position analysis problem of serial or parallel manipulators. In other situations, the valid configurations form a variety, and the problem is to analyze relevant subsets of this variety. This is the case when analyzing the singularity loci. In systems in which the dimension of the variety is very high, global analysis of the configuration space is unfeasible, and the main problem is to find collision and/or singularity free paths connecting any two given configurations. Next, we review the existing distance geometry approaches to these three fundamental problems.

Position Analysis

The position analysis problem consists in computing all the valid configurations of a constrained multibody system. This problem appears, for instance, in the inverse kinematic of serial manipulators [14], as illustrated in Fig. 2. It also appears when solving the forward kinematics of parallel structures [15], when planning the motion of deployable structures [16], in robot grasping [17], in constraint-based object positioning [18], or in simultaneous localization and map-building [19]. The problem appears in other domains as well, such as in the dynamical simulation of multibody systems [20], in parametric computer-aided design (CAD) [21], or in the conformational analysis of biomolecules [22].

Fig. 2

The inverse kinematic problem of a serial robot consists in finding the robot configurations that position the end effector in a given pose. For the manipulator in the figure, this problem has eight different solutions. Four of them are shown here

Traditional approaches translate the original geometric problem into a system of kinematic equations derived from the independent kinematic loops in the problem. Existing techniques for solving such systems of equations can be classified into algebraic and numerical methods. The use of independent loop equations has seldom been questioned, yet the resulting expressions are not particularly well suited for either the algebraic or numerical methods: first, because arbitrary reference frames have to be included, and second, because all formulas involve translations and rotations simultaneously, thus leading to complex trigonometric equations. The distance-based formulation offers an alternative that avoids these two problems and has been shown to provide novel insights in both algebraic and numerical methods.

Algebraic Methods

Algebraic methods use variable elimination to reduce the initial system to a univariate polynomial whose roots, once back-substituted into other equations, yield all solutions of the original system [23].

Fig. 3

An excavator (left) can be modeled as a planar mechanism (right) with a global rotation about a vertical axis. White and black dots represent movable and fixed revolute joints, respectively

To apply the variable elimination methods to equations resulting from the kinematic loops, the trigonometric expressions must be replaced to obtain a system of polynomial equations. Typically the tangent half-angle substitution is used, but it misses possible roots at $\pm \pi$. Moreover, the resulting expressions are complicated, limiting the scalability of this approach. Some of the successful results obtained with this approach can be attributed to clever manual manipulation of the expressions, which are difficult to generalize [24]. Using a distance-based approach, the original geometric problem is translated into a graph where the nodes are points on the structure and the edges are distance, area, or volume constraints involving these points. Relying on this formulation, Rojas and Thomas [27] proposed a procedure for solving the position analysis of complex planar mechanisms (see Fig. 3). The procedure analyzes the two possible assemblies of a triangle, given the distances between its vertices. This basic problem is elegantly formulated using the so-called bilateration matrices. More complex mechanisms are then analyzed, decomposing them in strips of triangles and chaining bilateration matrices for triangles sharing one edge. This directly produces a scalar algebraic resultant in most cases, which can be transformed into a polynomial by clearing radicals.

Fig. 4

The bilateration problem (left) and the associated notation (right)

Let us review this procedure in more detail. According to the notation in Fig. 4, the objective of the bilateration operation is to determine the location of point $P_k$ given known locations for points $P_i$ and $P_j$. The position vector of the orthogonal projection of $P_k$ onto $\overline{P_iP_j}$ can be expressed as

$$\begin{aligned} \mathbf{p}=\mathbf{p}_i \,\sqrt{\frac{D(i,k)}{D(i,j)}} \, \cos \theta \, \mathbf{p}_{i,j} = \mathbf{p}_i + \frac{D(i,j;i,k)}{D(i,j)}\,\mathbf{p}_{i,j} \end{aligned}$$

(1)

where

$$\begin{aligned} D(i_1, \dots , i_n; j_1, \dots , j_n)= \left| \begin{array}{cccc} 0 &{} 1 &{} \dots &{} 1 \\ 1 &{} s_{i_1,j_1} &{} \dots &{} s_{i_1,j_n} \\ 1 &{} \vdots &{} \ddots &{} \vdots \\ 1 &{} s_{i_n,j_1} &{} \dots &{} s_{i_n,j_n} \end{array}\right| \end{aligned}$$

(2)

is the Cayley-Menger determinant of n points, with $s_{i,j}$ the square of $d_{i,j}$, the distance between $P_i$ and $P_j$, and $D(i_1, \dots , i_n)=D(i_1, \dots , i_n;i_1, \dots , i_n)$ is the Cayley-Menger determinant.

Using $\mathbf{p}$, the position of $P_k$ can be expressed as

$$\begin{aligned} \mathbf{p}_k=\mathbf{p} \pm \frac{\sqrt{D(i,j,k)}}{D(i,j)}\, \mathbf{S} \, \mathbf{p}_{i,j}, \end{aligned}$$

(3)

where $\mathbf{S}=\left( \begin{matrix} 0 &{} -1 \\ 1 &{} 0 \end{matrix}\right)$, and the ± sign accounts for the two mirror-symmetric locations of $P_k$ with respect to the line defined by $\overline{P_iP_j}$. Substituting (1) in (3), we get

$$\begin{aligned} \mathbf{p}_{i,k}=\frac{D(i,j;i,k)}{D(i,j)} \, \mathbf{p}_{i.j} + \frac{D(i,j,k)}{D(i,j)} \,\mathbf{S}\, \mathbf{p}_{i,j}, \end{aligned}$$

(4)

which can be expressed in a more compact form as

$$\begin{aligned} \mathbf{p}_{i,k}=\mathbf{Z}_{i,j,k}\,\mathbf{p}_{i,j} \end{aligned}$$

(5)

where

$$\begin{aligned} \mathbf{Z}_{i,j,k}=\frac{1}{D(i,j)} \left( \begin{matrix} D(i,j;i,k) &{} \pm \sqrt{D(i,j,k)} \\ \pm \sqrt{D(i,j,k)} &{} D(i,j;i,k). \end{matrix} \right) \end{aligned}$$

(6)

Fig. 5

Two triangles sharing one edge

Note that (5) expresses $\mathbf{p}_{i,k}$ as a function of $\mathbf{p}_{i,j}$. When we have a strip of triangles, i.e., a sequence of triangles each sharing one edge with the previous one in the sequence, we can chain the bilateration process, i.e., multiply bilateration matrices, and express a vector in the final triangle as a function of a vector in the initial one. In the same way, we can derive expressions for vectors between points whose relative distance is initially unknown. For instance, in the situation in Fig. 5, we have that

$$\begin{aligned} \mathbf{p}_{j,l}=\mathbf{p}_{i,l}-\mathbf{p}_{i,j} = (\mathbf{Z}_{j,k,l}\,\mathbf{Z}_{i,j,k}\,-\mathbf{I}) \, \mathbf{p}_{i,j}. \end{aligned}$$

(7)

It can then be shown that the squared distance between $P_j$ and $P_l$ is given by

$$\begin{aligned} s_{j,l}=\det (\mathbf{Z}_{j,k,l}\,\mathbf{Z}_{i,j,k}\,-\mathbf{I})\,s_{i,j}, \end{aligned}$$

(8)

which expresses $s_{j,l}$ as a function of known edge lengths.

For larger problems, the same procedure can be applied, identifying strips of triangles with known edge lengths fully covering the mechanism. In most mechanisms with mobility zero, this process typically requires the introduction of unknown distances. Actually, the number of unknown distances to introduce coincides with the coupling number of the mechanism. Thus, the method can be applied to linkages with a coupling number higher than one. In the final expression, one of the distances in the triangle at the end of the strip is expressed as a function of an unknown distance in the first triangle. This expression, therefore, is directly a scalar algebraic equation which can be converted into a polynomial by clearing radicals. This direct procedure for deriving resultant polynomials is much simpler than those in the literature, and makes it possible to solve problems such as that in Fig. 6, which contains six independent kinematic loops, a number that has not been attained with elimination methods [26].

Fig. 6

Some of the valid configurations of a 13-link Watt-Baranov truss. The position analysis of this mechanism using algebraic methods has been shown to be feasible when formulating the problem in terms of distance constraints [25]

For systems with mobility one, we obtain a polynomial depending on two unknown distances which can be used for path tracking: one of the unknowns is fixed, and the system is solved for the remaining variable. The advantage in using a distance formulation in this case is that path-crossing conditions can be readily identified, since they correspond to alignments of particular points in the problem. Thus, the distance-based formulations simplify the path-tracking procedures, as compared with previous approaches [27].

This distance-based algebraic approach can be generalized to 3D using fans of tetrahedra instead of strips of triangles. This enables solving in closed form the position analysis of variable geometry trusses much more complex than those solvable with traditional formulations [28].

Numerical Methods

Although the distance-based algebraic methods have proved quite efficient in fairly non-trivial position analysis problems, this technique explodes in complexity with the size of the problem. Thus, to address larger problems, one must resort to numerical techniques. Several distance-based alternatives are available in the literature.

Trilateration Methods

The position analysis problem can be seen as that of determining all the possible values for the unknown distances in the graph of distance constraints encoding the problem. If the graph is represented in the form of an adjacency matrix, the problem boils down to completing the matrix from the distances initially fixed. Once the matrix is completed, standard linear algebraic methods can be used to give coordinates to the points in the problem [29].

Fig. 7

Trilateration can be used to compute the distance between $P_4$ and $P_5$ from their distances to $P_1$, $P_2$, and $P_3$, which form a fixed triangle. Two solutions are possible, depending on the location of $P_4$ and $P_5$ with respect to the plane defined from points $P_1$, $P_2$, and $P_3$

In some problems, the matrix completion process can be performed in an incremental constructive way. In ${\mathbb E}^3$, if all but one of the relative distances between five points are known, the unknown distance can be readily determined by trilateration. Using the notation in Fig. 7, we have that

$$\begin{aligned} s_{4,5}=\frac{2}{D(1,2,3)}\,\left( D(1,2,3,4;1,2,3,5)\Big |_{s_{4,5}=0} \pm \sqrt{D(1,2,3,4)\,D(1,2,3,5)} \right) , \end{aligned}$$

(9)

where $D(1,2,3,4;1,2,3,5)\Big |_{s_{4,5}=0}$ denotes the corresponding Cayley-Menger bideterminant with $s_{4,5}$ set to 0. Observe that no point coordinates appear in the result, only inter-point distances, and that two solutions are possible, corresponding to the two possible signs for the square root in the expression.

A problem is trilaterable if it is possible to determine a trilateration sequence to compute the initially unknown distances in the problem. This sequence can be readily determined by subgraph matching, i.e., finding parts of the original graph which match with the trilateration subgraph shown in Fig. 7. Porta et al. [11] showed that the inverse/direct kinematics of the most usual serial/parallel robots are trilaterable problems, which greatly simplifies their resolution. Moreover, [30] showed that if the searched subgraph includes six points with only one unknown distance between them, this unknown distance is linear with respect to the rest of the distances, and thus it has only one possible solution. This avoids the generation of distance completions that have to be discarded in a post-processing stage, since they would include tetrahedra with orientations incompatible with the original problem. For greater detail on the role of orientations in distance geometry, see Sect. Bound Smoothing with Orientation Constraints.

Note that the trilateration process is closely related to the algebraic approach described in Sect. Algebraic Methods. The main difference is that in the trilateration, only one new unknown distance appears at each step, whereas in the algebraic method, the first step involves two unknown distances. This is why the former method is purely numerical while the latter generates a symbolic expression in one variable distance.

To the best of our knowledge, the combination of the trilateration step and the procedure to determine a trilateration sequence was first introduced by Porta et al. [11, 30], and was later independently proposed by Lavor et al. [31] in the context of structural biology, but in Cartesian space, i.e., relying on the coordinates of the points and assigning coordinates to the trilaterated point at each step. More recently, the same authors proposed an equivalent algorithm in distance space [32].

Branch-and-Prune Methods

Unfortunately, not all problems admit a trilateration sequence, and thus general solvers must be devised to determine the valid distance matrices from the initially known distances. Porta et al. present alternative general solvers relying on a branch-and-prune technique [33,34,35]. These solvers iteratively eliminate regions of the space of distances where the distance constraints are not satisfied. When the distance space cannot be further reduced, it is split, and the reduction and split procedure is recursively applied to the two resulting sub-spaces. This process can be seen as an extension of the classic bound-smoothing techniques [36], and isolates the valid solutions for the input problem in the form of interval matrices at the desired resolution. Since splitting the search space is trivial, the key operation of the branch-and-prune methods is the procedure used to shrink the boxes in distance space.

Fig. 8

Segment-trapezoid clipping. Left: in this two-variable case, the graph of the multilinear function $f(x_1,x_2)$ in the domain box $\mathcal {B}$ necessarily lies inside the shown tetrahedron $\mathcal {H}$. The vertices of $\mathcal {H}$ are obtained by evaluating f in the corners of $\mathcal {B}$. The projection of $\mathcal {H}$ to a given coordinate planes defines a trapezoid. Right: from the initial range for a variable, we can prune all points for which its trapezoid does not intersect the $f(x_1,x_2)=0$ line

The method presented in [34, 35] introduces variable substitutions to convert the quadratic expression resulting from the Cayley-Menger determinants into multilinear equations. The graph of a multilinear function defined on an axis-aligned box is included in the convex hull of the evaluation of the function in the corners of the domain [37]. The solution of $f(\mathbf{x})=0$ can then be bounded to the intersection of this hull with the plane $f(\mathbf{x})=0$. Since the computation of this intersection can be difficult, the method projects the hull onto each coordinate plane, as depicted in Fig. 8 (left), and intersects each of the resulting trapezoids with the line, as shown in Fig. 8 (right). Typically, these segment-trapezoid clippings reduce the ranges of some variables, giving a smaller box (the black rectangle in Fig. 8) that still bounds the root locations. Although this strategy produces less pruning than the convex hull-plane clipping, it is advantageous in practice due to its lower cost of operation.

A Gough-Stewart platform is a six-degrees-of-freedom structure composed of a moving platform connected to a base by six legs. The pose of the platform is controlled by the leg lengths. Parallel structures are used in many applications, including positioning tools [38], flight simulators [39], or radiotelescopes [40]. After some leg rearrangements (see Sect. Singularity Analysis), the forward kinematic problem of the Gough-Stewart in Fig. 9 can be formulated using two Cayley-Menger determinants [41]

$$\begin{aligned} D(1,3,4,5,6)&=0,\\ D(1,2,4,5,6)&=0, \end{aligned}$$

where $P_1$, $P_2$, and $P_3$ are the points defining the triangle at the base of the structure and $P_4$, $P_5$, and $P_6$ the vertices in the triangle at the moving platform. The branch-and-prune algorithm proposed by Porta et al.  [35] determines the two solutions of this problem typically in less than 0.01 s on a standard desktop computer.

Fig. 9

Left: a hexapod structure. Right: associated distance graph where nodes are points and edges are distance constraints. Solid lines denote distances that are constant independently of the configuration

A variation of the above algorithm, where the box reduction is based on the properties of the Bernstein polynomials, has been used to elucidate the valid conformations of several molecular structures [42]. This method was parallelized and run on the MareNostrum supercomputer¹ to obtain the first complete description of the conformational space of the cyclooctane, which is a two-dimensional variety. To the best of our knowledge, this was the first distance geometry method able to characterize such complex solution spaces.

Distance geometry provides yet another alternative to crop the distance ranges based on the reduction and expansion of the dimension of the problem [43]. This approach is purely geometric, avoiding the algebraization of the problem. Taking the vector from $P_1$ to $P_n$ as a reference, a vector $\mathbf{q}=(\overline{d}_{1,n},\ldots ,\overline{d}_{n,n})$ can be defined where

$$\begin{aligned} \overline{d}_{i,n}=\frac{1}{2 \,d_{1,n}} (d_{i,n}^2+d_{1,n}^2-d_{i,1}^2) \end{aligned}$$

(10)

is the orthogonal projection of the vector from $P_n$ to $P_i$ onto the reference vector. We can also define the orthogonal complement of this projection, which is a matrix $\mathbf{Q}^\perp$ with

$$\begin{aligned} \mathbf{Q}_{i,j}^\perp =d_{i,j}^2-\frac{1}{4\, d_{1,n}^2} (d_{i,n}^2-d_{j,n}^2+d_{j,1}^2-d_{i,1}^2)^2. \end{aligned}$$

(11)

It can be shown that matrix $\mathbf{Q}$, with $Q_{i,j}=s_{i,j}$, is a proper Euclidean distance matrix in $\mathbb R^d$ if and only if $\mathbf{Q}_{i,j}^\perp$ with $i,j=1\ldots n-1$ is a correct Euclidean distance matrix in $\mathbb R^{d-1}$. Thus, the method projects the input distance matrix with interval ranges until the problem becomes one-dimensional, and hence consistency can be enforced using the triangular equality. The eventually reduced ranges are back-projected using the intermediate vectors $\mathbf{q}$ and matrices $\mathbf{Q}^\perp$ to find tighter ranges for the distances in the original problem. The direct evaluation of (10) and (11) using interval arithmetics would be inaccurate due to the well-known overestimations effect of this approach [44]. However, if a function $z=g(\mathbf{x})$ is monotone in an axis-aligned domain $\mathbf{x}=(x_1,\ldots ,x_n)$, with $x_i\in [x_i^l,x_i^u]$, and the derivatives of g are available, its upper bound is $z^u=g(\hat{\mathbf{x}})$, where $\hat{\mathbf{x}}=(\hat{x}_1, \ldots , \hat{x}_n)$ is the vertex of the domain given by

$$\begin{aligned} \hat{x}_i={\left\{ \begin{array}{ll} x_i^l &{} \text {if } \partial g/\partial x_i<0, \\ x_i^u &{} \text {otherwise.} \end{array}\right. } \end{aligned}$$

The lower bound, $z^l$, is in a vertex defined with the opposite criterion. Thus, tight bounds for $\overline{d}_{i,n}$ and $\mathbf{Q}_{i,j}^\perp$ can be obtained by analyzing their respective derivatives. This method has been applied to solve the position analysis of planar and spatial mechanisms with mobility 0 and 1 [43, 45].

Bound Smoothing with Orientation Constraints

One of the major shortcomings of the approaches described in the previous section is their limited capability for encoding orientation constraints. Let us consider the regional part of the wrist-partitioned 6R robot shown in Fig. 10 (left), that is, the first three links and joints that permit locating the wrist center anywhere in the robot’s workspace. Figure 10 (right) shows the formalization of this problem as a graph of distance constraints. In this example, any standard distance constraint solver would generally obtain eight different sets of compatible distances. Nevertheless, it is well known that the inverse kinematics of a 3R robot can only have up to four solutions [46]. This apparent contradiction has a simple explanation: a distance-based technique would not take into account the relative orientations of the tetrahedra defined by the sets of points $\{P_1 , P_2, P_3, P_4\}$ and $\{P_3 , P_4 , P_5 , P_6\}$. The same situation occurs in many other structures.

Fig. 10

Left: the configuration of the regional part of a wrist-partitioned 6R robot is determined by the location of seven points. Right: associated distance graph where nodes stand for points and edges for known distances between the corresponding points. Solid lines represent constant distances, regardless of the location of the end-effector

To address this issue, Rull et al. present a distance-bound smoothing approach that permits the incorporation of orientation constraints in the process of reducing the valid ranges of distances [47]. This approach focuses on planar problems that are formalized with the following constraints:

• For all sets of three points:

  $$\begin{aligned} D(i_1,i_2,i_3)\le 0. \end{aligned}$$

  (12)

• For all sets of four points:

  $$\begin{aligned} D(i_1,i_2,i_3,i_4)=0, \end{aligned}$$

  (13)

  and

  $$\begin{aligned} D(i_1,i_2,i_3;i_1,i_2,i_4) = \left\{ \begin{array}{cl} <0 &{} \text {if }\, \sigma _{i_1,i_2,i_3} \sigma _{i_1,i_2,i_4} >0\\ \ge 0, &{} \text {otherwise} \end{array} \right. \end{aligned}$$

  (14)

  where $\sigma _{i,j,k}$ is defined as negative if points $P_i$, $P_j$, and $P_k$ have to be arranged clockwise, and as positive otherwise.

While the expansion of (12) leads to the triangular inequality involving the distances between $P_{i_1}$, $P_{i_2}$, and $P_{i_3}$, (13) is nothing more than the tetrangular equality involving the six pairwise distances between $P_{i_1}$, $P_{i_2}$, $P_{i_3}$, and $P_{i_4}$.

Note that the whole set of orientation constraints in (14) cannot be fixed arbitrarily. Actually, it is possible to define a basis that determines all other orientations [48].

Fig. 11

Taking triangle $P_1$, $P_2$, and $P_3$ as a reference, the plane is divided into seven regions. If $P_4$ is bound to be in one of these regions, $s_{3,4}$ is monotone with respect to the rest of the squared distances. The boundaries separating the monotonic regions correspond to configurations where there is an alignment of three points

Since an efficient algorithm exists for tightening bounds using triangular constraints [49], it can be safely assumed that they are already satisfied by the initial ranges. Thus, the approach focuses on the analysis of (13) under orientation constraints. The expansion of this equality yields a quadratic expression in any of the involved squared distances. For instance, for the set of points $\{P_1,P_2,P_3,P_4\}$, we have

$$\begin{aligned} s_{3,4} = \frac{\left. D(1,2,4;1,2,3)\right| _{s_{3,4}=0}+\sigma _{1,2,4}\,\sigma _{1,2,3} \sqrt{D(1,2,4)\,D(1,2,3)}}{D(1,2)} \end{aligned}$$

(15)

or alternatively

$$\begin{aligned} s_{3,4} = \frac{\left. D(1,2,4;1,2,3)\right| _{s_{3,4}=0} + 16\,A_3\,A_4}{D(1,2)}, \end{aligned}$$

(16)

where $A_i$ denotes the oriented area of the triangle defined by the ordered set $\{P_1,P_2,P_3,P_4\}\backslash P_i$, since $4 A_i=\sigma _{j,k,l}\,\sqrt{-D(j,k,l)}$.

The range of $s_{3,4}$ can be tightly bounded using the monotonicity analysis presented at the end of Sect. Branch-and-Prune Methods. To apply this method to the function in (16), we need to compute the derivatives of $s_{3,4}$ with respect to $s_{i,j}$. Instead of computing these derivatives from (16), it is more convenient to obtain them from the linearization of (13), which reads as:

$$\begin{aligned} A_1 A_2 \, \delta s_{1,2} -A_1 A_3 \, \delta s_{1,3} +A_1 A_4 \, \delta s_{1,4}&\nonumber \\ +\, A_2 A_3 \, \delta s_{2,3} -A_2 A_4 \, \delta s_{2,4} +A_3 A_4 \, \delta s_{3,4}&=0. \end{aligned}$$

(17)

Then, we have that

$$\begin{aligned} \frac{\partial s_{3,4}}{\partial s_{i,j}} = -1^{i+j}\,\frac{A_i A_j}{A_3 A_4}. \end{aligned}$$

(18)

As long as the sign of the oriented areas of the triangles defined by $P_1, P_2, P_3$, and $P_4$ do not change, $s_{34}$ is monotone. Therefore, in this case, we can readily identify the vertices providing tight bounds for $s_{3,4}$ by controlling the regions where there are orientation sign changes.

Figure 11 shows a partition of the plane in regions where the orientations of the triangles defined by $P_1$, $P_2$, and $P_i$ with $i>3$ are constant, taking the triangle defined by $P_1$, $P_2$, and $P_3$ as a reference. If $P_4$ remains in one of these regions, the bounds for $s_{3,4}$ can be readily determined. For instance, if $P_4$ is in the Rhombus region, the patterns in Fig. 12 identify the vertices of the domain giving a tight range for $s_{3,4}$. We can identify 14 patterns, two for each region, which subsume the seven patterns used by Crippen and Havel [36].

Fig. 12

The two configurations giving the lower (left) and upper (right) bounds for $s_{3,4}$ in the Rhombus region. Solid and dashed lines indicate distances at their lower and upper limits, respectively

When three points can be aligned within the allowed distance ranges, the boundaries separating the monotonic areas must be recursively analyzed. At the end of the process, tight bounds for the variable of interest are obtained.

As an alternative, a geometric approach based on projections and back-projections introduced in [45] can also be extended to take into account orientation constraints. Moreover, this method can operate in 3D problems, whereas the extension to 3D of the method introduced in [47] is not trivial.

Fig. 13

A robot formation. Each robot is equipped with an ultrasound sensor to measure the distances to nearby teammates. The lines in the figure represent the distances actually measured. The orientation of the triangles is given by cameras mounted on the robots. The integration of the distance and orientation constraints permits the determination of tight bounds for the possible location of each robot

The integration of the orientation constraints opens a new range of applications for distance geometry methods, such as the coordination of robot teams, sensor data fusion, and constraint-based robot programming, to name just a few. For instance, Fig. 13 illustrates the application of this method to the mutual localization of a robot team.

Singularity Analysis

The singularity locus of any given mechanism is the set of configurations where mobility or control issues might arise. To prevent malfunctions or even structural damage, singularities must be avoided. Thus, given its relevance, singularity analysis is a major topic of research in mechanics. However, the characterization of singularities has only been achieved for particular mechanism instances or requires the use of complex computational methods [50]. In general, modifications of the mechanism parameters change the singularity locus in unpredictable ways, which hinders the analysis of new structures. Borras and Thomas, however, proposed distance geometry tools to identify singularity-invariant leg rearrangements for parallel structures, i.e., changes in the attachments of the legs to the base or the platform that do not change the singularity locus [51]. This generalizes the singularity analysis of a particular structure to all the other structures that can be defined from it with singularity-invariant leg rearrangements. Moreover, these rearrangements can be used to avoid multiple spherical joints, significantly simplifying the actual construction of the structure [41].

In a parallel structure, the linear and angular velocity of the moving platform, $\mathbf{v}$ and $\mathbf{\Omega }$, respectively, are related to the leg lengths by

$$\begin{aligned} \mathbf{R}_l \left( \begin{array}{c} \dot{l}_1 \\ \vdots \\ \dot{l}_6 \end{array} \right) = \mathbf{J} \left( \begin{array}{c} \mathbf{v} \\ \mathbf{\Omega } \end{array} \right) \end{aligned}$$

(19)

where $\mathbf{R}_l$ is a diagonal matrix with leg lengths $l_1, \ldots , l_6$, and $\mathbf{J}$ is the matrix of non-normalized Plücker coordinates of the six leg lines. The relevant singularities for parallel structures occur when $\det (\mathbf{J})=0$. Now assume that we rearrange the leg attachments and that the squares of the new leg lengths, $d_1, \ldots , d_6$, are related to the previous ones by an affine relation of the form

$$\begin{aligned} \left( \begin{array}{c} d_1^2 \\ \vdots \\ d_6^2 \end{array} \right) = \mathbf{A} \left( \begin{array}{c} l_1^2 \\ \vdots \\ l_6^2 \end{array} \right) + \mathbf{b}. \end{aligned}$$

(20)

Then, as shown by [52], the relation between the change in the leg lengths and the velocity of the platform becomes

$$\begin{aligned} \mathbf{R}_d \left( \begin{array}{c} \dot{d}_1 \\ \vdots \\ \dot{d}_6 \end{array} \right) = \mathbf{A}\,\mathbf{J} \left( \begin{array}{c} v \\ \Omega \end{array} \right) \end{aligned}$$

(21)

and the new singularity condition is $\det (\mathbf{A}\,\mathbf{J})=\det (\mathbf{A}) \det (\mathbf{J})$. If $\det (\mathbf{A})$ is a constant non-null factor, the leg rearrangement has no effect on the singularity locus. If $\det (\mathbf{A})$ is null, then the rearrangement introduces an architectural singularity, i.e., the resulting platform is in a singularity irrespective of its leg lengths.

Fig. 14

Singularity-invariant leg rearrangements. Left: rearrangement along a line connecting two anchor points. Right: rearrangement in a plane defined by three anchor points

A Cayley-Menger determinant can be used to derive the affine relation between the leg lengths before and after the rearrangement. For instance, consider the situation in Fig. 14 (left), where the anchor point $P_1$ is displaced to a new position $P_4$ along the line supported by $P_1$ and $P_2$. Since in this rearrangement the four points remain coplanar, then

$$\begin{aligned} D(1,2,3,4)= \left| \begin{array}{ccccc} 0 &{} 1 &{} 1 &{} 1 &{} 1 \\ 1 &{} 0 &{} (d_{1,4}+d_{2,4})^2 &{} s_{1,3} &{} s_{1,4} \\ 1 &{} (d_{1,4}+d_{2,4})^2 &{} 0 &{} s_{2,3} &{} s_{2,4} \\ 1 &{} s_{1,3} &{} s_{2,3} &{} 0 &{} s_{3,4} \\ 1 &{} s_{1,4} &{} s_{2,4} &{} s_{3,4} &{} 0 \end{array}\right| =0. \end{aligned}$$

(22)

Expanding this determinant, we obtain

$$\begin{aligned} d_{2,4} \,s_{1,3} + d_{1,4}\, s_{2,3} - (d_{1,4}+d_{2,4})\, s_{3,4} - d_{1,4}\, d_{2,4}\, (d_{1,4}+d_{2,4}) = 0 \end{aligned}$$

(23)

which defines an affine relationship between the leg lengths before and after the rearrangement with

$$\begin{aligned} \mathbf{A}=\left( \begin{array}{cccc} \frac{d_{2,4}}{d_{1,4}+d_{2,4}} &{} \frac{d_{1,4}}{d_{1,4}+d_{2,4}} &{} \ldots &{} 0 \\ 0 &{} 1 &{} \ldots &{} 0 \\ \vdots &{} \vdots &{} \ddots &{} \vdots \\ 0 &{} 0 &{} \ldots &{} 1 \end{array} \right) . \end{aligned}$$

(24)

Since $\det (\mathbf{A})=d_{2,4}/(d_{1,4}+d_{2,4})$, the proposed change in the anchor point location is a singularity-invariant leg rearrangement.

Figure 14 (right) shows another possible leg rearrangement, where a leg attachment is moved on the plane defined by the anchor points of three legs. In this case, the conditions to be held is

$$\begin{aligned} D(1,2,3,4,5)=0 \end{aligned}$$

(25)

which can be rewritten to

$$\begin{aligned}&D(1,2,3;2,3,5)\, s_{1,4} - D(1,2,3;1,3,5)\, s_{2,4} \nonumber \\&+D(1,2,3;1,2,5)\, s_{3,4} - D(1,2,3)\, s_{4,5} + C = 0 \end{aligned}$$

(26)

where C is a constant that does not depend on the distances involving $P_4$. This leads to a singularity factor

$$\begin{aligned} \det (\mathbf{A})= \frac{D(1,2,3;2,3,5)}{D(1,2,3)}, \end{aligned}$$

(27)

which is independent of the structure configuration and, thus, defines a singularity-invariant leg rearrangement.

Note that other leg rearrangements are possible. The advantage in using distance geometry in their derivation is that, in general, the singularity factors have a direct geometric interpretation.

Path Planning

For structures with high mobility, the comprehensive description of both their configuration spaces and their singularity loci is unfeasible. Fortunately, in these cases, research efforts usually focus on path planning problems, i.e., problems consisting in determining how to move the structure from an initial to a goal configuration, while avoiding collisions or singularities [53, 54], although this second aspect is less commonly treated in the literature [55].

For tree-like structures, the configuration space is parametric, which greatly simplifies the problem. However, when kinematic loops appear in the problem (see Fig. 15), the configuration space becomes a manifold embedded in the ambient space formed by the joint variables [56]. Actually, kinematic loops appears in many relevant problems, such as complex manipulation problems [57], parallel robot path generation [15], grasp planning [58], and surgery planning [59].

Fig. 15

A two-armed service robot holding a plate. The arms must be in contact with the plate, and the plate must remain horizontal to avoid tilting the coffee mug on it. A loop of kinematic constraints is thus generated

Under the presence of kinematic constraints, standard formulations produce involved configuration spaces. For some families of structures, though, distance constraints produce much simpler representations of the configuration spaces, in which the path planning problem can be easily solved.

Trinkle and Milgram analyze the configuration space of planar chains with revolute joints formalized with joint angle parameters, but also use concepts from distance geometry [60]. Using the notion of long link, they prove that the configuration spaces of such mechanisms are connected if and only if they do not have three long links. Otherwise, their configuration space has two components, and each is toroidal. They then propose a path planning algorithm differentiating between these two cases. When the configuration space has two components, the first task is to discern whether the two configurations to be connected are in the same component. If not, the path planning problem cannot be solved. For configurations in the same component, one link is used to drive the mechanism, while the remaining links comply in a series of accordion moves that can be proven to connect the configurations of interest. The final path is not optimal, but the algorithm is shown to be very efficient for significantly long loops.

Han et al. [61] propose a distance-based formulation for planar closed chains with revolute joints, where a configuration is represented by the set of distances from a point on the base link to the end-points of the rest of links, complemented with a set of triangle orientations. In this parameter space, the loop closure constraints become linear inequalities, and the configuration space becomes practically piecewise convex. The boundaries between the different convex regions of this space are given by particular alignments of points, i.e., changes in the orientation of the triangles. Thus, to connect any two given configurations, one need only identify the boundaries to be crossed and define a piecewise linear path between them.

The approaches by Trinkle and Milgram [60] and by Han et al. [61] can both be generalized to spatial mechanisms with spherical joints. However, no general joints or joint limits can be encoded in these approaches, which hinders their general applicability.

Summary

Distance-based formulations provide new insights into fundamental problems. In the context of algebraic methods, the number of variable eliminations is reduced to the point that, in many cases of practical interest, they are no longer required. Numerical methods also benefit from the use of distance formulations, since trilateration approaches naturally follow from them, and they provide a rich set of tools to reduce the search space in the context of branch-and-prune approaches. Moreover, distance formulations allow one to define singularity-invariant leg rearrangements, which significantly expand the utility of previous singularity characterizations in Gough-Stewart platforms. This enables the construction of active structures with well-characterized singularity loci and without complex mechanical pieces such as double spherical joints. Finally, in many cases, the analysis of the configuration spaces and the associated path planning problems can be certainly simplified when adopting a distance-based formulation.

Despite the extensive history of distance geometry, it has only recently been introduced for the position and motion analysis of structures. Given the success of the cases presented in this survey, we expect that distance-based formulations and their associated tools will soon be recognized as a powerful alternative for addressing the complex geometric problems arising in this discipline. Finally, the distance geometry methods described in this survey are able to solve a wide variety of problems, including trilaterable and non-trilaterable cases, linkages with a coupling number higher than 1, and even flexible graphs. We expect that these methods will find application in domains other than those presented here.