Precedents

The KRD group has been investigating the general motion analysis problem for more than two decades. Several techniques have been developed so far, before obtaining the current mature solution implemented in the Cuik Suite toolbox.

Here there is a review of previous research by the group, and solvers preceeding the Cuik Suite.

[Previous research]    [Preceeding solvers]    [References]

Previous research
From 1985 to 1995 (Group Theory, Interval Propagation, and the n-bar formalism)

The first group publications related to the problem date back to the PhD. Thesis of Federico Thomas, who proposed a solution method based on Group Theory [Thomas 1988a, Thomas 1988b]. During the period from 1988 to 1991, this work was extended to compute all solutions constrained to lie within given ranges of the robot's degrees of freedom. The results for planar, spherical and triangulable mechanisms appeared in the PhD. thesis of Enric Celaya [Celaya 1992a] and subsequent publications [Celaya 2002, Celaya et al. 2007, , Celaya et al. 2012]. These techniques were applied to the analysis and synthesis of mechanisms with several loops [Celaya 1994], to redundant manipulators [Celaya 1993], and to positioning objects from the on-line definition of body-environment contact constraints [Celaya 1992b, Rodriguez 2008], extending previous related developments [Thomas 1988c, Thomas 1991, Thomas 1992a]. Finally, a formulation based on representing loops as n-bar mechanisms was also investigated, which allows a factorization strategy for solving the kinematic loop-closure equations [Thomas 1992b, Thomas 1993, Thomas 1994].

A n-bar mechanism.

From 1996 to 1999 (General Interval Techniques)

Within the project "Spatial Constraint Analysis and its Application to Mechanical Design and the Simulation of Robotic Tasks" (TIC96-0721-C02-01), the group showed that general methods based on interval techniques are robust and easy to implement when applied to the position analysis problem. These methods do not require any symbolic manipulation of the input polynomials, which is an advantage over elimination techniques. In this sense, during the elaboration of his PhD. thesis, Albert Castellet developed a novel technique that combined the Interval Newton method [Castellet 1998b] with additional necessary conditions that speed up its convergence [Castellet 1994, Castellet 1997a, Castellet 1997b, Castellet 1998a, Castellet 1998b, Castellet 1999].

Kinematic structure of the Standford manipulator.

From 2000 to 2005 (Bernstein Subdivision)

The subdivision property of Bernstein polynomials was later on exploited, defining an alternative algorithm that has the same convergence rate as the Hansen method, but avoids computing derivatives of the input equations [Bombín 2000, Bombín 2001]. This yields a remarkably simple algorithm when the input equations are all multilinear. Since any set of kinematic constraints can be expressed by means of such equations plus a given number of circle equations, the group proposed a propagation scheme that uses one equation at a time to prune portions of the search space containing no solution [Porta 2002, Porta 2004]. This approximation combined the success of using only necessary conditions with the simplicity of a multilinear formulation. It also showed that the use of redundant equations allows isolating small-enough regions containing all solutions, without resorting to a global test. Continuing this progression, the group later combined Bernstein subdivision with a new formulation for the problem, based on inter-point distances of the robot only [Porta 2004, Porta 2005a]. This coordinate-free formulation (derived from the theory of Distance Geometry) yields much simpler equations and allows the identification of closed-form solutions in many cases [Porta 2005b]. This algorithm was later on optimized, by integrating the pruning effect of all equations into a single global test, based on linear programming [Porta 2007b]. The algorithm was parallelized and tested in the Marenostrum grid computer of the Barcelona Supercomputing Center. This has allowed obtaining, for the first time, complete maps of the solution space of several biomolecules, in a series of experiments jointly prepared with the Molecular Engineering Group at UPC [Porta 2007b].

The conformational space of the cyclooctane. The Marenostrum supercomputer.

From 2005 to 2011 (Linear Relaxations)

Within the projects A Trajectory Planner for Robotic Systems of Arbitrary Topology" (DPI2004-07358), and Analysis and Motion Planning of Complex Robotic Systems (DPI2007-60858) the group proposed a completely different approach to the position analysis problem. A new formulation has been obtained which yields easier-to-solve equations, involving linear, quadratic and bilinear terms only. Such simple-form equations allow a direct derivation of convex bounds for the solution space. The use of such bounds, in combination with an iterative linear programming technique, gives rise to a quite efficient solver. For instance, it allows solving the general 6R and Stewart Platform manipulators in a few seconds on a Desktop PC, and the derivation of one- or two-dimensional conformational maps of many molecules in reasonable computation times. Main related papers are [Creemers 2006, Porta 2006, Porta 2007a, Porta et al. 2009, Rosales et al. 2011a]. In parallel, work on the distance-based approach to the problem continued. In this sense, the group has obtained a new technique to solve the associated distance matrix completion problem, based on projections and backprojections of the point set [Thomas 2004a, Thomas 2004b, Porta 2005c].

A grasp synthesis problem.

From 2011 until present (Higher-dimensional Continuation and Randomization)

Withing the current project An Extension of Branch-and-Prune Techniques for Motion Analysis and Synthesis of Complex Robotic Systems (DPI2010-18449) we extended the software implementing higher-dimensional continuation tools and randomization in order to address problems such as the synthesis of robots [Simo-Serra et al. 2011, Simo-Serra et at. 2012] the singularity analysis [Bohigas et al. 2011, Bohigas et al. 2012b, Bohigas et al. 2012c, Bohigas et al. 2013a, Bohigas et al. 2012e], the grasp planning [Rosales et al. 2011b, Rosales et al. 2012], the path planning under loop closure constraints, [Porta et al. 2011, Jaillet 2011a, Bohigas et al. 2012a, Bohigas et al. 2012d, Porta et al. 2012, Jaillet 2012, Jaillet 2013, Bohigas et al. 2013b], or the analysis of the conformational space of bio-molecules [Jaillet et al. 2011b, Porta 2013].

The PR2 service robot.

Preceeding solvers
CUIK-0

This solver (1997) implements the techniques developed in Albert Castellet's Ph.D. thesis, and it is among the first interval-based position analysis solvers in the literature. It was successfully applied to the inverse kinematics of several 6R and 7R serial manipulators and, some years later, it was used by Josep M. Porta to confront the SLAM problem [Porta 2005d]. Main publications are: [Castellet 1998a], [Castellet 1998b].

Function bounds using the interval derivative (left) or the slope (right).

CUIK-I

This solver (2002) uses a polytope-based technique instead of a interval-based one. In this approach, a mechanism is described as a set of matrix equations in homogeneous coordinates. The use of homogeneous matrices makes this solver ideal to be implemented using the special processors included in the PC graphic cards or in the game consoles. We applied this solver to the inverse kinematics of robots with isolated solutions or with one-dimensional solution manifolds. Main papers are: [Porta 2002].

The trapeziod-segment clipping.

CUIK-II

This solver (2003-2005) also employs polytope bounds of the solution space, but these are derived from the (more involved) theory of Bernstein subdivision. The solver, in fact, solves the general distance matrix completion problem: find all embeddings of a set of points that are pairwise constrained by fixed, known distances. The formulation based on points and distances allows detecting many cases which are solvable in closed form. It easily shows that most industrial robots, e.g., can be solved by resorting to trilateration only [Porta 2005b]. It also allows tackling molecular conformation problems in a natural way, since distance constraints obtained from nuclear magnetic resonance can be taken into account as limited ranges for the variables. Main papers are: [Bombín 2000], [Bombín 2001], [Porta 2007b].

Convex hull and sub-division for a planar curbe.

CUIK-III

This solver (2004) is geometric in nature. It is based on successive projections and back-projections of a set of points constrained by pairwise distances. The method is simple and elegant, and provides good results in reasonable time, but still deserves further research to make it of practical use (execution time should be reduced and the quality of output increased). Research on this solver is still on progress. Main papers are: [Thomas 2004a], [Thomas 2004b], [Porta 2005c].

Projection of a distance constraint on an axis.

The Cuik Suite

This is the solver the group has been developing since 2005. It was initially developed for planar linkages, but was later generalized to spatial ones. The solver is based on linear relaxations - convex polytope bounds of the solution space and it also incorporates higher-dimensional continuation techniques. This is the most efficient solver developed so far by the group, both in terms of convergence speed, quality of the output, and range of applications it can deal with. Main papers are: [Creemers 2006], [Porta 2006], [Porta 2007a], [Porta et al. 2009], [Jaillet et al. 2011], [Porta et al. 2011], [Rosales et al. 2011a], [Rosales et al. 2011b], [Bohigas et al. 2012a], [Bohigas et al. 2012b], [Bohigas et al. 2012c], [Jaillet 2012], [Bohigas et al. 2013b], [Jaillet 2013], [Porta 2013].

Charts locally parametrizing a manifold.

References

[Bohigas 2011] O. Bohigas, L. Ros, and M. Manubens, "A unified method for computing position and orientation workspaces of general Stewart platforms," ASME International Design Engineering Technical Conference, pp. 959-968, 2011

[Bohigas 2012a] O. Bohigas, Michael E. Henderson, L. Ros, and J.M. Porta, "A singularity-free path planner for closed-chain manipulators," IEEE International Conference on Robotics and Automation, pp. 2128-2134, 2012.

[Bohigas 2012b] O. Bohigas, D. Zlatanov, L. Ros, M. Manubens, and J.M. Porta, "Numerical computation of manipulator singularities," IEEE International Conference on Robotics and Automation, pp. 1351-1358, 2012.

[Bohigas 2012c] O. Bohigas, M. Manubens, and L. Ros, "A complete method for workspace boundary determination on general structure manipulators," IEEE Transactions on Robotics, 28(5):993-1006, 2012.

[Bohigas 2012d] O. Bohigas, M. Manubens, and L. Ros, "Planning singularity-free force-feasible paths on the Stewart platform," International Symposium on Advances in Robot Kinematics, pp. 245-252, 2012

[Bohigas 2012e] O. Bohigas, D. Zlatanov, M. Manubens, and L. Ros, "On the numerical classification of the singularities of robot manipulators," ASME International Design Engineering Technical Conference, 2012

[Bohigas 2013a] O. Bohigas, M. Manubens, and L. Ros, "A linear relaxation method for computing workspace slices of the Stewart platform," Journal of Mechanisms and Robotics, 5(1):011005, 2013.

[Bohigas 2013b] O. Bohigas, M. Manubens, and L. Ros, "Navigating the wrench-feasible C-space of cable-driven hexapods," International Conference on Cable-Driven Parallel Robots, pp. 53-68, 2012.

[Bombín 2000] C. Bombín, L. Ros, and F. Thomas, "A concise Bézier clipping technique for solving inverse kinematics problems," in Advances in Robot Kinematics, J. Lenarcic y M.M. Stanisic (editors). Kluwer Academic Publishers, 2000.

[Bombín 2001] C. Bombín, L. Ros, and F. Thomas, "On the computation of the direct kinematics of parallel spherical mechanisms using Bernstein polynomials," Proceedings of the IEEE International Conference on Robotics and Automation, pp. 3332-3337 Seoul, South Korea, 2001.

[Castellet 1994] A. Castellet and F. Thomas, "Characterization of self-motion manifolds using Morse theory," 2nd PROMotion Workshop on Motion Planning, L'Escala, 10-13 October, 1994.

[Castellet 1997a] A. Castellet and F. Thomas, "Towards an efficient interval method for solving inverse kinematic problems," Proceedings of the IEEE International Conference on Robotics and Automation, Vol. IV, pp. 3615-3620, April 22-28, Alburqurque, New Mexico, 1997.

[Castellet 1997b] A. Castellet and F. Thomas, "Using interval methods for solving inverse kinematic problems," Proceedings of the NATO Advanced Study Institute on Computational Methods in Mechanisms, Vol. II, pp. 135-145, junio 16-28, Varna, Bulgaria, 1997.

[Castellet 1998a] A. Castellet and F. Thomas, "An algorithm for the solution of inverse kinematics problems based on an interval method," in Advances in Robot Kinematics, M. Husty and J. Lenarcic, Eds. Kluwer Academic Publishers, pp. 393-403, 1998.

[Castellet 1998b] A. Castellet, "Solving Inverse Kinematic Problems Using an Interval Method," PhD. thesis. Technical University of Catalonia, 1998.

[Castellet 1999] A. Castellet and F. Thomas, "The Self-Motion Manifold of the Orthogonal Spherical Mechanism," Mechanisms and Machine Theory, Vol. 34, No. 1, pp. 59-88, January 1999.

[Celaya 1992a] E. Celaya, "Geometric reasoning for the determination of the position of objects linked by spatial relationships," PhD thesis, Technical University of Catalonia, October 1992.

[Celaya 1992b] E. Celaya, "LMF: A program for positioning objects using geometric relationships," in Applications of Artificial Intelligence in Engineering VII, D.E. Grierson et al. (editors), pp. 873-881, Computational Mechanics Publications, Southampton, and Elsevier Applied Science, London, 1992.

[Celaya 1993] E. Celaya and C. Torras, "On Finding the Set of Inverse Kinematic Solutions for Redundant Manipulators," in Computational Kinematics, J. Angeles, G. Hommel and P. Kovács (editores), pp. 85-94, Kluwer Academic Publishers, 1993.

[Celaya 1994] E. Celaya, E. and C. Torras, "Solving multi-loop linkages with limited-range joints," Mechanism and Machine Theory, Vol. 29, No. 3, pp. 373-391, abril 1994. Pergamon Press.

[Celaya 2002] E. Celaya, "Interval propagation for solving parallel spherical mechanisms," In: Advances in Robot Kinematics, J. Lenarcic and F. Thomas ed., Kluwer Academic Publishers, 2002, pp. 415-422.

[Celaya 2007] E. Celaya, T. Creemers, and L. Ros, "Exact Interval Propagation for the Efficient Solution of Planar Linkages," World Congress in Mechanism and Machine Science (IFToMM), pp. 1-7, 2007

[Celaya 2012] E. Celaya, T. Creemers, and L. Ros, "Exact interval propagation for the efficient solution of position analysis problems on planar linkages," Mechanism and Machine Theory, 54: 116-131, 2012.

[Creemers 2006] T. Creemers, J.M. Porta, L. Ros, and F. Thomas, "Fast Multiresolutive Approximations of Planar Linkage Configuration Spaces," IEEE International Conference on Robotics and Automation, pp. 1511-1517, 2006.

[Jaillet 2011a] L. Jaillet and J.M. Porta, "Path planning with loop closure constraints using an atlas-based RRT," 15th International Symposium on Robotics Research, 2011.

[Jaillet 2011b] L. Jaillet, F. Corcho, J.J. Pérez, and J. Cortés, "Randomized tree construction algorithm to explore energy landscapes," Journal of Computational Chemistry, 32(16):3464-3474, 2011.

[Jaillet 2012] L. Jaillet and J.M. Porta, "Asymptotically-optimal path planning on manifolds," Robotics: Science and Systems Conference, 2012.

[Jaillet 2013] L. Jaillet and J.M. Porta, "Path planning under kinematic constraints by rapidly exploring manifolds," IEEE Transactions on Robotics, 29(1): 105-117, 2013.

[Porta 2002] J.M. Porta, L. Ros, F. Thomas, and C. Torras, "Solving Multi-Loop Linkages by Iterating 2D Clippings," in Advances in Robot Kinematics, J. Lenarcic and F. Thomas (Eds.), pp. 255-265, Kluwer Academic Publishers.

[Porta 2003] J.M. Porta, L. Ros, F. Thomas, and C. Torras, "A Branch-and-Prune Algorithm for Solving Systems of Distance Constraints," Proceedings of the IEEE International Conference on Robotics and Automation, May 12-17, Taipei, Taiwan, 2003.

[Porta 2004] J.M. Porta, L. Ros, and F. Thomas, "Isolating Self-Motion Manifolds on a Playstation," In Advances in Robot Kinematics. C. Galletti y J. Lenarcic (editors), pp. 123-132. Kluwer Academic Publishers, 2004.

[Porta 2005a] J.M. Porta, F. Thomas, L. Ros, and C. Torras, "A Branch-and-Prune Solver for Distance Constraints," IEEE Transactions on Robotics, Vol. 21, No. 2, pp. 176-187, 2005.

[Porta 2005b] J.M. Porta, L. Ros, and F. Thomas, "On the Trilaterable Six-Degree-of-Freedom Parallel and Serial Manipulators," Proceedings of the IEEE International Conference on Robotics and Automation, April 18-22, Barcelona, 2005.

[Porta 2005c] J. M. Porta, L. Ros, and F. Thomas, "Inverse Kinematics by Distance Matrix Completion," in Proc. International Workshop on Computational Kinematics (Cassino, Italy) 2005.

[Porta 2005d] J.M. Porta, "CuikSlam: A Kinematic-based approach to SLAM," IEEE International Conference on Robotics and Automation, pp. 2436-2442, 2005.

[Porta 2006] J. M. Porta, L. Ros, and F. Thomas, "Multi-loop Position Analysis via Iterated Linear Programming," in Proc. Robotics: Science and Systems II (Philadelphia, USA) 2006.

[Porta 2007a] J.M. Porta, L. Ros, T. Creemers, and F. Thomas, "Box Approximations of Planar Linkage Configuration Spaces," ASME Journal of Mechanical Design, Vol. 127, pp. 397-405, 2007.

[Porta 2007b] J.M. Porta, L. Ros, F. Thomas, F. Corcho, J. Cantó, and J.J. Pérez, "Complete Maps of Molecular Loop Confomational Spaces," Journal of Computational Chemistry, 28(13):2170-2189, 2007.

[Porta 2009] J.M. Porta, L. Ros, and F. Thomas, "A linear relaxation technique for the position analysis of multiloop linkages," IEEE Transactions on Robotics, 25(2):225-239, 2009.

[Porta 2011] J.M. Porta and L. Jaillet, "Path planning on manifolds using randomized higher-dimensional continuation," Ninth International Workshop on the Algorithmic Foundations of Robotics, 2010.

[Porta 2012] J.M. Porta, L. Jaillet, and O. Bohigas, "Randomized path planning on manifolds based on higher-dimensional continuation," The International Journal of Robotics Research , 31(2):201-215, 2012.

[Porta 2013] J.M. Porta and L. Jaillet, "Exploring the energy landscapes of flexible molecular loops using higher-dimensional continuation," Journal of Computational Chemistry, 34(3):234-244, 2013.

[Rodriguez 2008] A. Rodríguez, L. Basañez, and E. Celaya, "A relational positioning methodology for robot task specification and execution," IEEE Transactions on Robotics, 24(3):600-611, 2008.

[Rosales 2011a] C. Rosales, L. Ros, J.M. Porta, and R. Suárez, "Synthesizing grasp configurations with specified contact regions," The International Journal of Robotics Research , 30(4):431-443, 2011.

[Rosales 2011b] C. Rosales, J.M. Porta, and L. Ros. "Global optimization of robotic grasps," VII Robotics: Science and Systems Conference, 2011.

[Rosales 2012] C. Rosales, C. Rosales, R. Suárez, M. Gabiccini, and A. Bicchi, "On the synthesis of feasible and prehensile robotic grasps," IEEE International Conference on Robotics and Automation, pp. 550-556, 2012.

[Simo-Serra 2011] E. Simo-Serra, F. Moreno-Noguer, and A. Perez. "Design of non-anthropomorphic robotic hands for anthropomorphic tasks," ASME International Design Engineering Technical Conference, pp. 377-386, 2011

[Simo-Serra 2012] E. Simo-Serra, A. Perez, H. Moon, and N. Robson. "Kinematic synthesis of multi-fingered robotic hands for finite and infinitesimal tasks," International Symposium on Advances in Robot Kinematics, pp. 173-180, 2012

[Thomas 1988a] F. Thomas, "Planificación de tareas de ensamblado basada en análisis de restricciones," PhD.thesis, Technical University of Catalonia, 1988.

[Thomas 1988b] F. Thomas and C. Torras, "Group theoretic approach to the computation of symbolic part relations", IEEE Journal of Robotics and Automation, Vol. 4, No. 6, pp. 622-634, 1988.

[Thomas 1988c] F. Thomas and C. Torras, "Constraint-Based Inference of Assembly Configurations," Proceedings of the 1988 IEEE International Conference on Robotics and Automation, Vol. II, pp. 1304-1307, April 1988, Philadelphia, USA.

[Thomas 1991] F. Thomas, "Graphs of Kinematic Constraints," Chapter 4 in Computer-Aided Mechanical Assembly Planning, L.S. Homem de Mello and S. Lee (Eds.), pp. 81-111, Kluwer Academic Publishers, 1991.

[Thomas 1992a] F. Thomas and C. Torras, "Inferring feasible assemblies from spatial constraints", IEEE Transactions on Robotics and Automation, Vol. 8, No. 2, pp. 228-239, 1992.

[Thomas 1992b] F. Thomas, "On the n-bar mechanism, or how to find global solutions to redundant single loop spatial kinematic chains", Proceedings of the IEEE International Conference on Robotics and Automation, Vol. I, pp. 403-408, Niza, Francia, 1992.

[Thomas 1993] F. Thomas, "The Self-Motion Manifold of the N-bar Mechanism," in Computational Kinematics, J. Angeles (Editor), pp. 95-107, Kluwer Academic Publishers, 1993.

[Thomas 1994] F. Thomas and C. Torras, "Positional Inverse Kinematic Problems in Rⁿ x T^m Solved in T^2(n+m)", in Advances in Robot Kinematics and Computational Geometry, A.J. Lenarcic y B.B. Ravani (Eds.), pp. 291-300, Kluwer Academic Publishers, 1994.

[Thomas 2004a] F. Thomas, J. M. Porta, and L. Ros, "Distance Constraints Solved Geometrically." In: Advances in Robot Kinematics, C. Galletti and J. Lenarcic eds., Kluwer Academic Publishers, 2004, pp. 31-40.

[Thomas 2004b] F. Thomas, "Solving Geometric Constraints by Iterative Projections and Backprojections," in Proc. IEEE International Conference on Robotics and Automation (New Orleans, USA) 2004, pp. 1789-1795.