The kinematics, dynamics, and control of a unicycle moving without slipping on a plane has been extensively studied in the literature of nonholonomic mechanical systems. However, since planar motion can be seen as a limiting case of the motion on a sphere, we focus our analysis on the more general spherical case. This paper introduces a novel approach to path planning for a unicycle rolling on a sphere while satisfying the non-slipping constraint. Our method is based on a simple yet effective idea: first, we model the system as a linear time-varying dynamic system. Then, leveraging the fact that certain such systems can be integrated under specific algebraic conditions, we derive a closed-form expression for the control variables. This formulation includes three free parameters, which can be tuned to generate a path connecting any two configurations of the unicycle. Notably, our approach requires no prior knowledge of nonholonomic system analysis, making it accessible to a broader audience.

It is well known that the singularities of a Gough-Stewart platform arise when the determinant of the Plücker coordinates of the robot leg lines vanish. The direct expansion of this determinant in terms of the configuration of the moving platform leads to an intimidating algebraic expression which is difficult to organize in a manner that facilitates extracting geometric conditions for singularities to occur. The use of Grassmann-Cayley algebra has permitted expressing this determinant as a bracket polynomial which is easier to manipulate symbolically. Each monomial in this polynomial is the product of three brackets, 4×4 determinants involving the homogeneous coordinates of four leg attachments. In this paper, we show how to derive, using elementary linear algebra arguments, bracket polynomials where all brackets can be interpreted as reciprocal products between lines. Contrarily to what one might expect, these new bracket polynomials are simpler in general than those previously obtained using Grassmann-Cayley algebra.

No proper norm exists to measure the distance between two object poses essentially because a general pose is defined by a rotation and a translation, and thus, it involves magnitudes with different units. As a means to solve this dimensional-inhomogeneity problem, the concept ofcharacteristic lengthhas been put forward in the area of kinematics. The idea consists of scaling translations according to this characteristic length and then approximating the corresponding displacement defining the object pose in${\mathbb {R}}^3$by a rotation in${\mathbb {R}}^4$, for which a norm exists. This article sheds new light on this kind of approximations which permits simplifying optimization problem whose cost functions involve translations and rotations simultaneously. A good example of this kind of problems is the pointcloud registration problem in which the optimal rotation and translation between two sets of corresponding 3-D point data, so that they are aligned/registered, have to be found. As a result, a simple closed-form formula for solving this problem is presented which is shown to be an attractive alternative to the previous approaches.

The problem of restoring the orthonormality of a noisy rotation matrix by finding its nearest correct rotation matrix arises in many areas of robotics, computer graphics, and computer vision. When the Frobenius norm is taken as the measure of closeness, the solution is usually computed using the singular value decomposition (SVD). A closed-form formula exists but, as it involves the roots of a polynomial of third degree, it is assumed to be too complicated and numerically ill-conditioned. In this article, we show how, by carefully using some algebraic recipes scattered in the literature, it is possible to derive a simple and yet numerically stable formula for most practical applications. Moreover, by relying on a result that permits obtaining the quaternion corresponding to the sought optimal rotation matrix, we present another closed-form formula that provides a good approximation to the optimal one using only the elementary algebraic operations of addition, subtraction, multiplication, and division. These two closed-form formulas are compared with respect to the SVD in terms of accuracy and computational cost.

The forward kinematics of the Gough-Stewart platform, and their simplified versions in which some leg endpoints coalesce, has been typically solved using variable elimination methods. In this paper, we cast doubts on whether this is the easiest way to solve the problem. We will see how the indirect approach in which the length of some extra virtual legs is first computed leads to important simplifications. In particular, we provide a procedure to solve 30 out of 34 possible topologies for a Gough-Stewart platform without variable elimination.

This paper presents a first attempt at a unified kinematics analysis of all serial and parallel solvable robots, that is, robots whose position analysis can be carried out without relying on numerical methods. The efforts herein are focused on finding a unified formulation for all quartically-solvable robots, as all other solvable robots can be seen as particular cases of them. The first part is centered on the quest for the most general quartically-solvable parallel and serial robots. As a result, representatives of both classes are selected. Then, using Distance Geometry, it is shown how solving the forward kinematics of the parallel representative is equivalent to solve the inverse kinematics of the serial representative, thus providing a unified formulation. Finally, it is shown that the position and singularity analysis of these robots reduces to the analysis of the relative position of two coplanar ellipses.

Distance Bound Smoothing (DBS) is a basic operation originally developed in Computational Chemistry to determine point configurations that are within certain pairwise ranges of distances. This operation consist in the iterative application of filtering processes that reduce the given ranges using triangular and tetrangular inequalities. Standard DBS has a limited range of applications because it does not take into account constraints on the orientations of simplices (triangles or tetrahedra, depending on the dimension of the problem). This paper discusses an extension of DBS that permits incorporating these constraints. This paves the way for the application of DBS techniques to a broad range of problems in Robotics.

Dual quaternions give a neat and succinct way to encapsulate both translations and rotations into a unified representation that can easily be concatenated and interpolated. Unfortunately, the combination of quaternions and dual numbers seems quite abstract and somewhat arbitrary when approached for the first time. Actually, the use of quaternions or dual numbers separately is already seen as a break in mainstream robot kinematics, which is based on homogeneous transformations. This paper shows how dual quaternions arise in a natural way when approximating 3-D homogeneous transformations by 4-D rotation matrices. This results in a seamless presentation of rigid-body transformations based on matrices and dual quaternions, which permits building intuition about the use of quaternions and their generalizations.

A double banana is defined as the bar-and-joint assembly of two bipyramids joined by their apexes. Clearly, the bar lengths of this kind of assembly are not independent as we cannot assign arbitrary values to them. This dependency can be algebraically expressed as a closure condition fully expressed in terms of bar lengths. This paper is devoted to its derivation and to show how its use simplifies the position analysis of many well-known serial and parallel robots thus providing a unifying treatment to apparently disparate problems. This approach permits deriving the univariate polynomials, needed for the closed-form solution of these position analysis problems, without relying on trigonometric substitutions or difficult variable eliminations.

This paper deals with the motion planning problem for parallel orienting platforms with one non-holonomic joint and two prismatic actuators which can maneuver to reach any three-degree-of-freedom pose of the moving platform. Since any system with two inputs and up to four generalized coordinates can always be transformed into chained form, this path planning problem can be solved using well-established procedures. Nevertheless, the use of these procedures requires a good understanding of Lie algebraic methods whose technicalities have proven a challenge to many practitioners who are not familiar with them. As an alternative, we show how by (a) properly locating the actuators, and (b) representing the platform orientation using Euler parameters, the studied path planning problem admits a closed-form solution whose derivation requires no other tools than ordinary linear algebra.

The real roots of the univariate polynomial closure condition of a planar parallel robot determine the solutions of its forward kinematics. This paper shows how the univariate polynomials of all fully parallel planar robots can be derived directly from that of the widely known 3-RPR robot by simply formulating these polynomials in terms of distances and oriented areas. This is a relevant result because it avoids the case-by-case treatment that requires different sets of variable eliminations to obtain the univariate polynomial of each fully parallel planar robot.

In most practical implementations of the Gough-Stewart platform, the octahedral form is either taken as it stands or is approximated. The kinematics of this particular instance of the Gough-Stewart platform, commonly known as the octahedral manipulator, has been thoughtfully studied. It is well-known, for example, that its forward kinematics can be solved by computing the roots of an octic polynomial and its singularities have a simple geometric interpretation in terms of the intersection of four planes in a single point. In this paper, using a distance-based formulation, it is shown how these properties can be derived without relying neither on variable eliminations nor trigonometric substitutions. Moreover, thanks to this formulation, a family of platforms kinematically equivalent to the octahedral manipulator is obtained. Herein, two Gough-Stewart parallel platforms are said to be kinematically equivalent if there is a one-to-one correspondence between their squared leg lengths for the same configuration of their moving platforms with respect to their bases. If this condition is satisfied, it can be shown that both platforms have the same assembly modes and their singularities, in the configuration space of the moving platform, are located in the same place.

The algebraic characterization of the singularities of a Stewart platform is usually presented as a 6×6 determinant, whose rows correspond to the line coordinates of its legs, equated to zero. This expression can be rewritten in a more amenable way, which is known as the pure condition, as sums and products of 4×4 determinants, whose rows correspond to the point coordinates of the leg attachments. Researchers usually rely on one of these two expressions to find the geometric conditions associated with the singularities of a particular Stewart platform. Although both are equivalent, it is advantageous to use either line or point coordinates, depending on the platform topology. In this context, an equivalent expression involving only plane coordinates, i.e., a dual expression to that using point coordinates, seems to be missing. This paper is devoted to its derivation and to show how its use is advantageous in many practical cases, mainly because of its surprising simplicity: It only involves the addition of 4×4 determinants whose rows are plane coordinates defined by sets of three attachments.

Two-dimensional slices of robot singularity loci contain, in general, cusps. This kind of points are important because their presence indicates the possibility of planning assembly-changing motions that do not meet any singularity. The critical points where the number of cusps changes, as the slice is swept, permit one to decompose a singularity locus into domains where the obtained slices share common topological properties. In this paper, it is shown how Catastrophe Theory provides a solid framework to classify these critical points up to certain types of equivalence giving precise local models to describe them. It is also shown how only three possible types of these critical points exist for generic robots. The presented results are exemplified on a serial 3R robot.

The standard forward-kinematics analysis of 3-RPR planar parallel robots boils down to computation of the roots of a sextic polynomial. There are many different ways to obtain this polynomial, but most of them include exceptions for which the formulation is not valid. Unfortunately, near these exceptions, the corresponding polynomial exhibits numerical instabilities. In this paper, we provide a way around this inconvenience by translating the forward-kinematics problem to be solved into an equivalent problem fully stated in terms of distances. Using constructive geometric arguments, an alternative sextic - which is not linked to a particular reference frame - is straightforwardly obtained with the need for neither variable eliminations nor tangent-half-angle substitutions. The presented formulation is valid, with no modification, for any planar 3-RPR parallel robot, including the special architectures and configurations - which ultimately lead to numerical instabilities - that cannot be directly handled by previous formulations.

A 5-SPU robot with collinear universal joints is well suited to handle an axisymmetric tool, since it has five controllable degrees of freedom, and the remaining one is a free rotation around the tool. The kinematics of such a robot also having coplanar spherical joints has previously been studied as a rigid subassembly of a Stewart-Gough platform, which has been denoted a line-plane component. Here, we investigate how to move the leg attachments in the base and the platform without altering the robot's singularity locus. By introducing the so-called 3-D space of leg attachments, we prove that there are only three general topologies for the singularity locus corresponding to the families of quartically, cubically, and quadratically solvable 5-SPU robots. The members of the last family have only four assembly modes, which are obtained by solving two quadratic equations. Two practical features of these quadratically solvable robots are the large manipulability within each connected component and the fact that, for a fixed orientation of the tool, the singularity locus reduces to a plane.

This paper introduces a class of reconfigurable parallel robots consisting of a fixed base and a moving platform connected by serial chains having RRPS (Revolute-Revolute-Prismatic-Spherical) topology. Only the prismatic joint is actuated and the first revolute joint in the chain can be locked or released online. The introduction of these lockable joints allow the prismatic actuators to maneuver to approximate 6-DoF motions for the moving platform. An algorithm for generating these maneuvers is first described. Then, a motion planner, based on the generation of a Probabilistic RoadMap (PRM) whose nodes are connected using the described maneuvers, is presented. The generated trajectories avoid singularities and possible collisions between legs.

A 5-SPU robot with collinear universal joints is well suited to handling an axisymmetric tool, since it has 5 controllable DoFs and the remaining one is a free rotation around the tool. The kinematics of such a robot having also coplanar spherical joints has previously been studied as a rigid subassembly of a Stewart-Gough platform, it being denoted a line-plane component. It was shown that this component has 8 assembly modes corresponding to the roots of a bi-quartic polynomial. Here we identify a whole family of these 5-SPU robots having only 4 assembly modes, which are obtained by solving two quadratic equations. This family is defined by a simple proportionality constraint relating the coordinates of the base and platform attachments. A geometric interpretation of the architectural singularities of this type of robots in terms of conics is provided, which facilitates their avoidance at the design stage. Parallel singularities obey also a neat geometric structure, which permits deriving a cell decomposition of configuration space. Two practical features of these quadratically-solvable robots are the large maneuverability within each connected component and the fact that, for a fixed orientation of the tool, the singularity locus reduces to a plane.

A pentapod is usually defined as a 5-degree-of-freedom fully-parallel manipulator with an axial spindle as moving platform. This kind of manipulators have revealed as an interesting alternative to serial robots handling axisymmetric tools. Their particular geometry permits that, in one tool axis, inclination angles of up to 90 degrees are possible thus overcoming the orientation limits of the classical Stewart platform.

When the attachments of five legs in a Stewart platform are collinear on one side and coplanar on the other, the platform is said to contain a line-plane subassembly. This paper is devoted to the kinematics analysis of this subassembly paying particular attention to the problem of moving the aforementioned attachments without altering the singularity locus of the platform. It is shown how this is always possible provided that some cross-ratios between lines -defined by points in the plane- are kept equal to other cross-ratios between points in the line. This result leads to two simple motion rules upon which complex changes in the location of the attachments can be performed. These rules have interesting practical consequences as they permit a designer to optimize aspects of a parallel robot containing the analyzed subassembly, such as its manipulability in a given region, without altering its singularity locus.

There are only three 6-SPS parallel manipulators with triangular base and platform, i.e., the octahedral, the flagged, and the partially flagged, which are studied in this paper. The forward kinematics of the octahedral manipulator is algebraically intricate, while those of the other two can be solved by three trilaterations. As an additional nice feature, the flagged manipulator is the only parallel platform for which a cell decomposition of its singularity locus has been derived. Here, we prove that the partially flagged manipulator also admits a well-behaved decomposition, technically called a stratification, some of whose strata are not topological cells, however. Remarkably, the adjacency diagram of the 5-D and 6-D strata (which shows what 5-D strata are contained in the closure of a 6-D one) is the same as for the flagged manipulator. The availability of such a decomposition permits devising a redundant 7-SPS manipulator, combining two partially flagged ones, which admits a control strategy that completely avoids singularities. Simulation results support these claims.

This paper presents a new method to isolate all configurations that a multiloop linkage can adopt. The problem is tackled by means of formulation and resolution techniques that fit particularly well together. The adopted formulation yields a system of simple equations (only containing linear, bilinear, and quadratic monomials, and trivial trigonometric terms for the helical pair only) whose structure is later exploited by a branch-and-prune method based on linear relaxations. The method is general, as it can be applied to linkages with single or multiple loops with arbitrary topology, involving lower pairs of any kind, and complete, as all possible solutions get accurately bounded, irrespective of whether the linkage is rigid or mobile.

Any set of two legs in a Gough–Stewart platform sharing an attachment is defined as a$\Delta$component. This component links a point in the platform (base) to a line in the base (platform). Thus, if the two legs, which are involved in a$\Delta$component, are rearranged without altering the location of the line and the point in their base and platform local reference frames, the singularity locus of the Gough–Stewart platform remains the same, provided that no architectural singularities are introduced. Such leg rearrangements are defined as$\Delta$-transforms, and they can be applied sequentially and simultaneously. Although it may seem counterintuitive at first glance, the rearrangement of legs using simultaneous$\Delta$-transforms does not necessarily lead to leg configurations containing a$\Delta$component. As a consequence, the application of$\Delta$-transforms reveals itself as a simple, yet powerful, technique for the kinematic analysis of large families of Gough–Stewart platforms. It is also shown that these transforms shed new light on the characterization of architectural singularities and their associated self-motions.

Many different robotic in-parallel structures have been conceived as six-component force sensors. In general, they perform well for most applications but, when accuracy is a must, two main limitations arise. First, in most designs, the legs are connected to the base and the platform through ball- and-socket joints. Although the dry friction in each of these joints can be individually neglected, the integrated effect of twelve such elements becomes noticeable. Second, dynamical measurements might not be very accurate because the natural resonance frequency of the used structures is quite low even for relatively small dimensions. This dynamical response can be obviously modified with a proper mechanical design, but this increases the complexity of the sensor. This paper discusses the design and implementation of a touch pad based on a 6-axis force sensor and shows how the above limitations degrade its behavior. Moreover, it is shown how using a tensegrity structure both problems could be alleviated because ball-and- socket joints can be substituted by point contacts and the resonance frequency of the structure can be controlled by adjusting the static tensions of the tendons.

Flagged manipulators are of interest because they are the only Stewart-Gough platforms for which a cell decomposition of their singularity loci is available. Here we show that the known family of such manipulators can be enlarged if one allows robot designs that, for some particular parameter values, become architecturally singular. Along this line, the most general 6-6 flagged manipulator is derived by applying a singularity-preserving transformation that leaves the relative position between two lines invariant. This transformation opens up the possibility of an "equal cross ratios" architectural singularity, which is shown to appear clearly in the factorization of the Jacobian determinant. From the 6-6 flagged manipulator, all the extended family of (possibly architecturally-singular) flagged manipulators is derived.

Wire-based tracking devices are an affordable alternative to costly tracking devices. They consist of a fixed base and a platform, attached to the moving object, connected by six wires whose tension is maintained along the tracked trajectory. One important shortcoming of these devices is that they are forced to operate in reduced workspaces so as to avoid singular configurations. Singularities can be eliminated by adding more wires, but this causes more wire interferences, and a higher force exerted on the moving object by the measuring device itself. This paper shows how, by introducing a rotating base, the number of wires can be reduced to three, and singularities can be avoided by using an active sensing strategy. This also permits reducing wire interference problems and the pulling force exerted by the device.

This paper introduces box approximations as a new tool for path planning of closed-loop linkages. Box approximations are finite collections of rectangloids that tightly envelop the robot's free space at a desired resolution. They play a similar role to that of approximate cell decompositions for open-chain robots - they capture the free-space connectivity in a multi-resolutive fashion and yield rectangloid channels enclosing collision-free paths - but have the additional property of enforcing the satisfaction of loop closure constraints frequently arising in articulated linkages. We present an efficient technique to compute such approximations and show how resolution-complete path planners can be devised using them. To the authors' knowledge, this is the first space-decomposition approach to closed-loop linkage path planning proposed in the literature.

The conditions for a parallel manipulator to be flagged can be simply expressed in terms of linear dependencies between the coordinates of its leg attachments, both on the base and on the platform. These dependencies permit to describe the manipulator singularities in terms of incidences between two flags (hence, the name ldquoflaggedrdquo). Although these linear dependencies might look, at first glance, too restrictive, in this paper, the family of flagged manipulators is shown to contain large subfamilies of six-legged and three-legged manipulators. The main interest of flagged parallel manipulators is that their singularity loci admit a well-behaved decomposition with a unique topology irrespective of the metrics of each particular design. In this paper, this topology is formally derived and all the cells, in the configuration space of the platform, of dimension 6 (nonsingular) and dimension 5 (singular), together with their adjacencies, are worked out in detail.

Flagged in-parallel manipulators are attractive because their singularity loci admit a well-behaved decomposition, with a unique topology irrespective of the metrics of each particular design. In this paper, this topology is formally derived and all the cells, in the configuration space of the platform, of dimension 6 (non-singular) and dimension 5 (singular), together with their adjacencies, are worked out in detail. This characterization of the singularity loci is useful to come up with designs which admit control strategies free of singularities. In particular, it is shown that by adding an extra leg to any flagged manipulator, the resulting 7-leg structure admits a control strategy (by appropriately choosing which leg remains passive) that completely avoids singularities

This paper presents a numerical method able to compute all possible configurations of a planar linkage. The procedure is applicable to rigid linkages (i.e., those that can only adopt a finite number of isolated configurations) and to mobile ones (i.e., those that have internal degrees of freedom). The method is based on the fact that this analysis always reduces to finding the roots of a polynomial system of linear, quadratic, and hyperbolic equations, which is here tackled with a new strategy exploiting its structure. The method is conceptually simple, geometric in nature, and easy to implement, yet it provides solutions of the desired accuracy in short computation times. Experiments are included which show its performance on the double butterfly linkage, for which an accurate an complete discretization of its configuration space is obtained

Some in-parallel robots, such as the 3-2-1 and the 3/2 manipulators, have attracted attention because their forward kinematics can be solved by three consecutive trilaterations. In this paper, we identify a class of these robots, which we call flagged manipulators, whose singularity loci admit a well-behaved decomposition, i.e., a stratification, derived from that of the flag manifold. Two remarkable properties must be highlighted. First, the decomposition has the same topology for all members in the class, irrespective of the metric details of each particular robot instance. Thus, we provide explicitly all the singular strata and their connectivity, which apply to all flagged manipulators without any tailoring. Second, the strata can be easily characterized geometrically, because it is possible to assign local coordinates to each stratum (in the configuration space of the manipulator) that correspond to uncoupled rotations and/or translations in the workspace.

The inverse/direct kinematics of trilaterable serial/parallel manipulators can be stated as a system of distance constraints whose set of solutions can be determined using a sequence of trilaterations, possibly involving points at infinity. It is possible to decide whether a mechanism is trilaterable by relying only on its topology. Based on this fact, we here enumerate all trilaterable serial and in-parallel robots with six degrees of freedom. The relevance of the obtained family of manipulators is established when it is shown to contain the best-known commercial serial robots. As a result of this analysis, we come up with a general method to solve the inverse/direct kinematics of a wide family of manipulators.

Given some geometric elements such as points and lines in R/sup 3/, subject to a set of pairwise distance constraints, the problem tackled in this paper is that of finding all possible configurations of these elements that satisfy the constraints. Many problems in robotics (such as the position analysis of serial and parallel manipulators) and CAD/CAM (such as the interactive placement of objects) can be formulated in this way. The strategy herein proposed consists of looking for some of the a priori unknown distances, whose derivation permits solving the problem rather trivially. Finding these distances relies on a branch-and-prune technique, which iteratively eliminates from the space of distances entire regions which cannot contain any solution. This elimination is accomplished by applying redundant necessary conditions derived from the theory of distance geometry. The experimental results qualify this approach as a promising one.

This paper deals with the problem of estimating the pose of a moving rigid body by measuring the length of six wires attached to it. Since wires can be seen as extensible legs, this problem is equivalent to that of solving the forward kinematics of a six-degree-of-freedom parallel manipulator. Among all possible locations for the attachments on the moving object, the "3-2-1" configuration is shown to exhibit a large number of favorable properties. The performance analysis of this particular configuration is addressed by finding analytic expressions for the estimated pose covariance matrix and the expected value of the pose estimation error, or bias error, which has been omitted in the previous analysis of wire-based tracking devices. This analysis takes advantage of a formulation for trilateration based on Cayley-Menger determinants, which is mathematically more tractable compared to previous ones, because all terms involved are determinants with geometric meaning. This accommodates a more thorough investigation of the properties of the device.

Locating a robot from its distances, or range measurements, to three other known points or stations is a common operation, known as trilateration. This problem has been traditionally solved either by algebraic or numerical methods. An approach that avoids the direct algebrization of the problem is proposed here. Using constructive geometric arguments, a coordinate-free formula containing a small number of Cayley-Menger determinants is derived. This formulation accommodates a more thorough investigation of the effects caused by all possible sources of error, including round-off errors, for the first time in this context. New formulas for the variance and bias of the unknown robot location estimation, due to station location and range measurements errors, are derived and analyzed. They are proved to be more tractable compared with previous ones, because all their terms have geometric meaning, allowing a simple analysis of their asymptotic behavior near singularities.

Most geometric constraint problems can be reduced to give coordinates to a set of points from a subset of their pairwise distances. By exploiting this fact, this paper presents an algorithm that solves geometric constraint systems by iteratively reducing and expanding the dimension of the problem. In general, these projection/backprojection iterations permit tightening the ranges for the possible solutions but, if at a given point no progress is made, the algorithm bisects the search space and proceeds recursively for both subproblems. This branch-and-prune strategy is shown to converge to all solutions.

An image can be seen as an element of a vector space so that it can be expressed in terms of a series expansion of any nonnecessarily orthogonal base of this space. This paper shows how a matrix-based formulation of this fact permits deriving a new reconstruction method of an image from its geometric moments where the basis functions used in the reconstruction and those used to obtain the moments do not necessarily define the same subspace. This permits introducing constraints relative to the bandwidth or the spatial resolution of the image to be reconstructed. Moreover, it is shown that, by exploiting the algebraic properties of the involved matrices as well as the properties of computer arithmetic, accurate solutions to this problem in spite of its ill-conditioning can be obtained.

Given a set of affine varieties in R/sup 3/, i.e. planes, lines, and points, the problem tackled in this paper is that of finding all possible configurations for these varieties that satisfy a set of pairwise euclidean distances between them. Many problems in robotics - such as the forward kinematics of patroller manipulators or the contact formation problem between polyhedral models - can be formulated in this way. We propose herein a strategy that consists in finding some distances, that are unknown a priori, and whose derivation permits solving the problem rather trivially. Finding these distances relies on a branch-and-prune technique that iteratively eliminates from the space of distances entire regions which cannot contain any solution. The elimination is accomplished by applying redundant necessary conditions derived from the theory of Cayley-Menger determinants. The experimental results obtained qualify this approach as a promising one.

This paper deals with the problem of estimating the pose of a rigid moving object by measuring the length of six wires attached to it. Among all possible locations for the attachments on the moving object, the "3-2-1" configuration exhibits the highest number of favorable properties. A closed-form coordinate-free solution to the forward kinematics of this particular configuration is given in terms of Cayley-Menger determinants. The proposed formulation is mathematically more tractable compared to previous ones because all terms are determinants with geometric meaning. This accommodates a more thorough investigation of the properties of the device and leads to formulas whose numerical conditioning is independent from the chosen reference frames.

An analytic formulation of the statics and the instantaneous kinematics of robot manipulators based on Grassmann-Cayley algebra is presented. The notions of twist, wrench, twist space and wrench space are mathematically represented by the concept of extensors of this algebra and the reciprocity relation between twist and wrench spaces of partially constrained rigid bodies is reflected by its inherent duality. Kinestatic analysis of manipulators implies the computation of sums and intersections of the twist and wrench spaces of the composing chains which are carried out by means of the join and meet operators of this algebra when the linear subspaces involved in the kinestatic analysis of manipulators are represented by extensors. The importance of Grassmann-Cayley algebra in kinestatics is that it has an explicit formula for the meet operator that gives analytical expressions of the twist and wrench space of robot manipulators with arbitrary topology.

Presents an algorithm for correcting incorrect line drawings-incorrect projections of a polyhedral scene. Such incorrect drawings arise, e.g., when an image of a polyhedral world is taken, the edges and vertices are extracted, and a drawing is synthesized. Along the way, the true positions of the vertices in the 2D projection are perturbed due to digitization errors and the preprocessing. As most available algorithms for interpreting line drawings are "superstrict," they judge these noisy inputs as incorrect and fail to reconstruct a three-dimensional scene from them. The presented method overcomes this problem by moving the positions of all vertices until a very close correct drawing is found. The closeness criterion is to minimize the sum of squared distances from each vertex in the input drawing to its corrected position. With this tool, any superstrict method for line drawing interpretation is now practical, as it can be applied to the corrected version of the input drawing.

Local moments have attracted attention as local features in applications such as edge detection and texture segmentation. The main reason for this is that they are inherently integral-based features, so that their use reduces the effect of uncorrelated noise. The computation of local moments, when viewed as a neighborhood operation, can be interpreted as a convolution of the image with a set of masks. Nevertheless, moments computed inside overlapping windows are not independent and convolution does not take this fact into account. By introducing a matrix formulation and the concept of accumulation moments, this paper presents an algorithm which is computationally much more efficient than convolving and yet as simple.

Presents an ellipsoidal calculus based solely on two basic operations: propagation and fusion. Propagation refers to the problem of obtaining an ellipsoid that must satisfy an affine relation with another ellipsoid, and fusion to that of computing the ellipsoid that tightly bounds the intersection of two given ellipsoids. These two operations supersede the Minkowski sum and difference, affine transformation and intersection tight bounding of ellipsoids on which other ellipsoidal calculi are based. Actually, a Minkowski operation can be seen as a fusion followed by a propagation and an affine transformation as a particular case of propagation. Moreover, the presented formulation is numerically stable in the sense that it is immune to degeneracies of the involved ellipsoids and/or affine relations. Examples arising when manipulating uncertain geometric information in the context of the spatial interpretation of line drawings are extensively used as a testbed for the presented calculus.

Solving the direct kinematics of parallel spherical mechanisms with l legs is basically solving systems of l-1 second-order multinomials. This paper presents a recurrent expression for the control points of these multinomials when expressed in the Bernstein form. This result allows one to propose a technique for solving the direct kinematics of these mechanisms that takes advantage of the sub-division and convex hull properties of polynomials in the Bernstein form. Contrary to other numerical approaches, the one presented here is clearly less involved and, although it can be classified within the same category as interval-based techniques, it does not require any interval arithmetic computation.

This paper presents a new algorithm for correcting incorrect projections of a polyhedral scene. Such projections arise in applications where an image of a polyhedral world is taken and its edges and vertices are extracted. Along the way, the true positions of the vertices in the 2D projection are perturbed due to digitization errors and the preprocessing. As most available algorithms for reconstructing polyhedral scenes from projections are "superstrict", they judge these noisy inputs as incorrect and fail to obtain a 3D scene from them. The method presented overcomes this problem by moving the positions of all vertices until a very close correct projection is found. With this tool, any superstrict method for reconstructing scenes from projections is now practical, as it can be applied to the corrected projection.

Some thinning algorithms for 3D objects, or generalizations of existing ones for 2D, have been proposed in recent years. The paper presents a simple and very fast algorithm compared to most of them, and still it has theoretically favorable properties. It provides a connected surface skeleton that allows shapes to be reconstructed with bounded error. In addition, it is also very attractive because it allows discrete skeletons to be obtained directly from volumes in many representations without converting them to a voxel-based representation. Our algorithm is a generalization of the one presented by Cardoner et al. (1997) for 2D objects. It is based on the application of directional erosions, while retaining those voxels that introduce disconnection.

Using structural geometry, Whiteley (1991) showed that a line drawing is a correct projection of a spherical polyhedron if and only if it has a cross-section compatible with it. We extend the class of drawings to which this test applies, including those of polyhedral disks. Our proof is constructive, showing how to derive all spatial interpretations; it relies on elementary synthetic geometric arguments, and, as a by-product, it yields a simpler and shorter proof of Whiteley's result. Moreover, important properties of line drawings are visually derived as corollaries: realizability is independent of the adopted projection, it is an invariant projective property, and for trihedral drawings it can be checked with a pencil and an unmarked ruler alone.

Given two sculptured objects, described by a collection of rational Bezier patches, we propose an algorithm that provides the distance between them if the objects are not intersecting, or a measure of penetration otherwise. The algorithm extends the upper-lower bound subdivision approach to the computation of the nearest points by considering the relative orientations between the subdivided patches. All required geometric constructions can be described as rational Bezier patches so that their control points can be precomputed from those of the original patches. Additional operations have been designed to exhibit linear complexity with the total number of involved control points.

This paper studies the statics and the instantaneous kinematics of a rigid body constrained to keep an arbitrary number of surface-surface contacts with a rigid static environment during its motion. These properties are analyzed under the frictionless assumption by modelling each contact with a kinematic chain that instantaneously gives the same motion freedom as the contact itself and by studying the resulting parallel chain using the Grassmann-Cayley algebra. With this algebra twists and wrenches can be expressed by means of extensors and operated using the join and meet operators. Moreover, the duality inherent in this algebra is used to reflect the reciprocity condition between possible twists and admissible wrenches between partially constrained rigid bodies.

We present a simple local geometric characterization of the configuration space of two polyhedra in contact that provides a representation of all infinitesimal motions that separate them. The polyhedra considered are general in the sense that they possibly have non-convex faces and arbitrary number of holes. The approach presented has two main advantages over former ones: 1) it only relies on the classical basic contacts between polyhedra, i.e. the vertex-face and edge-edge contacts; and 2) it does not require the focal decomposition of non-convexities into convex parts.

An improved universal parallel recurrent neural network canonical architecture, named a recurrent trainable neural network (RTNN), suited for state-space systems identification, and an improved dynamic backpropagation method of its learning, are proposed. The proposed RTNN is studied with various representative examples and the results of its learning are compared with other results given in the literature. For a complex nonlinear plants identification, a fuzzy-rule-based system and a fuzzy-neural multimodel, are used. The fuzzy-neural multimodel is applied to a mechanical system with friction identification.

Proves that the realizability of a line drawing without occluding segments can be verified by checking the concurrence of groups of three lines to a single point. These lines are either those supporting segments in the drawing or new ones added during the test itself. Although this result was essentially already established by Whiteley , the presented approach uses the concept of delta-star reductions to obtain all possible spatial realizations and consistent edge-labellings (convex or concave) of a given drawing. As opposed to well-known algebraic approaches, which require a Waltz filtering preprocessing step before proceeding to the global geometric test the approach presented is based on geometrically interpretable projective conditions which allows an easy localization of the source of eventual inconsistencies.

In this paper we present a new algehrwic analysis of the closure equation obtained for arbitrary single loop spatial kinematic chains, which allows us to design an eficient interval method for solving their inverse kinematics.The solution of a kinematic equation can be factored into a solution of both its rotational and its translational components.We have obtained general and simple expressions for these equations and their derivatives that are used to perform Newton cuts.A branch and prune strategy is used to get a set of boxes as small as desired containing the solutions.If the kinematic chain is redundant, this approach can also provide a discretized version of the solution set.The mathematics of the proposed approach are quite simple and much more intuitive than continuation or ehmination methods.Yet it seems to open a promising jield for further developments.

Image compression techniques have been recently used not only for reducing storage requirements, but also computational costs when processing images on low cost computers. This approach might be also of interest for processing large engineering drawings, where feature extraction techniques must be intensively applied for their segmentation into regions of interest for subsequent analysis. This paper explores this alternative using a simple run-length compression, leading to excellent results. Although this approach is not new and can be classified within the decomposition paradigm used since the early stages of line drawing image processing, the developed formalism allows directional morphological set transformations to be performed, on a low cost personal computer, faster than on costly parallel computers for the same, but uncompressed, images. This good performance is proved in two different applications: the generation of homotopic skeletons through thinning processes, and the extraction of linear features through serializing multiangle parallelism operations.

The computation of linear moment matrices, whose elements are defined as zeroth order integration values of an image, was recently introduced as a tool to reduce the computational cost required to obtain the geometric moments of an image. The main relevance of these matrices is twofold: on one hand, they can be efficiently obtained by means of accumulation filters, which only require additions; on the other one, their relation to geometric moments, as well as to discrete Fourier spectrum coefficients, allows the exchange and interpretation of many results from different areas of image processing and pattern recognition. Taking into account the relevance of these matrices, a new recursive property that allows their efficient computation in sliding-window processes is presented here. First, a scalar recursive updating rule is formulated. It relates the value of each element of a linear moment matrix to those calculated in the previous location of the sliding-window. Then, this result is reformulated to obtain an explicit matrix formula. The obtained recursive updating rule has a straightforward application in many different fields involving sliding window processes in order to efficiently obtain local features related to geometric moments and discrete Fourier spectrum coefficients.

This paper investigates the partition of the configuration space induced by basic contacts between polyhedra, using their combinatorial interpretation in terms of oriented matroids. It is shown that solving motion planning problems using this cellular decomposition can be analytically expressed in terms of invariants, without explicit use of artificial coordinate frames. One of the main aims of this paper is to draw the attention of the reader to some results from the theory of matroids which are directly applicable to path planning, and many other geometric problems arising in robotics. In particular, the relevance of the concept of mutation in the context of collision-free path planning is highlighted. Moreover, it is proved that the set of mutations contains the walls of a given cell in configuration space, and that this set, as one moves from one cell to a neighbour one, can be updated in linear time with the number of vertices. This provides a simple way to detect a large amount of redundant constraints from purely combinatorial considerations, without relying on the manipulation of algebraic equations.

Exact interference checking between two arbitrary polyhedra is known to have O(mn) complexity, where m and n are the number of edges in the two polyhedra. This is just a worst-case bound that still leaves plenty of room for algorithm improvement in practice. The algorithm presented herein has been developed so as to: 1. Minimize the number of operations that each pairing of edges entails. We prove that this factor is 4.5 for multiplications and 8.5 for additions. 2. Avoid the construction of auxiliary geometric entities. The standard approach is to decompose the nonconvex polyhedra (or their faces) into convex entities and then check for interference in this convex setting. This entails the construction of many fictitious edges and faces, which indirectly contribute to the growth of the complexity. 3. Permit the straightforward application of prunning strategies to most practical situations, so that the worst-case bound above is reached only when truly needed. 4 Allow the derivation of both directional and undirectional distance bounds between the polyhedra, which prove extremely useful for collision avoidance and local path planning. The simplicity and homogeneity of the algorithm has led to a quick implementation, which has been proven to be robust and fast. Some performance measurements are reported.>

The author investigates the global sets of solutions for single loop inverse kinematic problems containing only independent rotational and translational degrees of freedom, providing a rational and compact method to obtain these sets. The proposed methodology relies on a deep understanding of spherical redundant mechanisms, shedding light on the basic algebraic structure underlying inverse kinematic problems associated with single loop kinematic chains. This methodology consists of finding the inverse kinematic solution to the n-bar mechanism. It is shown that one can model any kinematic loop equation as the loop equation derived from this mechanism after taking as many bars as needed and constraining some of the resulting degrees of freedom. The solution of any kinematic equation can be factored into a solution of both its rotational and translational components. While the solution of the former can be obtained quite easily, the later leads, in general, to inextricable formulae. Some important relationships between the two components are obtained, which make it simpler to obtain the solution to the translational component once the solution to the rotational one has been found.>

The authors treat two different problems in the analysis of assemblies, and algorithms are described for each. The first problem is the selection of consistent sets of part feature relationships, and it corresponds to a search over possible configurations of parts that are consistent with feature set mappings. The second problem is the evaluation of the kinematic consistency of an assembly that has been defined by consistent feature sets. These two problems are linked together as two of the steps required in a search for all correct assembly configurations of a given set of parts. Several of the other necessary steps related to part interference, path feasibility, and workcell device kinematics are referred to but not analyzed. The proposed search algorithm is based on a constraint posting strategy, i.e. rather than generating and testing all specific alternatives, chunks of the search space are progressively removed from consideration by constraints that rule them out until one satisfactory alternative is found.>

An alternative approach for the propagation of uncertain geometric information, based on the ideas presented by J.R. Deller (IEEE ASSP Magazine, vol.6, p.4-20, Oct. 1989) and extended to deal with graphs of geometric constraints, is presented. This method avoids the independency assumption of the probabilistic approach. In this approach, when new sensory data are acquired, a set of strips is obtained, propagated, and fused to obtain the updated ellipsoids associated with each feature, Then, the hypothesis about the location of the involved geometric features can be easily updated. Inconsistencies are easily detected, resulting in fast rejection of erroneous data.>

A system for the automatic synthesis of assembly configuration is presented. It consists of the propagation, combination, and satisfaction of three types of constraints: shape-matching constraints, constraints on the degrees of freedom, and nonintersection constraints. Given a high-level description of an assembly and the models of the workpieces, the system determines which parts of the workpieces should be mated and produces a set of homogeneous-coordinate transformations defining the relative position and orientation of each workpiece in the final assembly. This system can be seen as a previous step towards a practical and efficient assembly planner.>

When a set of constraints is imposed on the degrees of freedom between several rigid bodies, finding the configuration or configurations that satisfy all these constraints is a matter of special interest. The problem is not new and has been discussed, not only in kinematics, but also more recently in the design of object-level robot programming languages. In this last domain, several languages have been developed, from different points of view, that are able to partially solve the problem. A more general method is derived than those previously proposed that were based on the symbolic manipulation of chains of matrix products, using the theory of continuous groups.>