Research Project

CUIK++: An Extension of Branch-and-Prune Techniques for Motion Analysis and Synthesis of Complex Robotic Systems

Type

National Project

Start Date

01/01/2011

End Date

31/12/2014

Project Code

DPI2010-18449

Project illustration

Staff

Project Description

Substantial efforts are being made in Robotics to better understand how to efficiently compute, plan, simulate or control the motions of complex multi-body systems. These systems are sets of articulated bodies arising in many robotic devices, like parallel manipulators, multi-fingered hands, or reconfigurable mechanisms, but they appear in other domains too, as mechanic models of locomotive organisms, molecular compounds, or nano-structures.

In the course of two preceding R&D projects (CUIK and CUIK+), we developed a general and efficient technique able to solve the position analysis of these systems. This technique is able to find the whole set of configurations that a multi-body system can adopt, given the constraints imposed by its interconnecting joints. The availability of this technique opens up the possibility of extending it with new methods, to be able to tackle related problems of Robotics that have not been fully solved until now. These are:

  • The robot synthesis problem, which consists in determining how should a robot be designed, so as to include certain desired poses in its workspace.

  • The singularity analysis problem, which entails computing all singular configurations of a robot, including end-effector singularities, which induce dexterity losses, and actuator singularities, which cause controllability issues.

  • The path planning problem, which involves finding a trajectory between robot configurations that avoids collision with the obstacles, and maximizes distance to singularities.

While solutions for these problems exist, they are either too specific (i.e., limited to particular robot architectures), or incomplete (they may fail to converge, even if solutions exist), or computationally too costly to be implemented in practice. Obtaining general complete solutions to these problems is crucial, however, for an accurate design, simulation, and planning of the motions of the increasingly-sophisticated devices of today's Robotics. A paradigmatic example are multifingered hands, which must be properly designed to be able to operate within a prescribed workspace, dexterously manipulating objects, and avoiding singular configurations or collisions with the environment all the time.

A first goal of this project is to provide general and complete algorithms for solving these problems on multi-body systems of general structure, possibly containing closed-kinematic chains. Such a solution is possible, we argue, by complementing previous techniques for position analysis developed by the group, with new techniques for critical set computation, higher-dimensional continuation, and randomized exploration.

A second goal of this project is to implement these algorithms efficiently, and to develop a new software platform able to perform integral motion analysis and synthesis of complex multi-body systems. In order to obtain solutions in practical times even for complex problems, the platform will be enabled to run on multi-processor machines, and to exploit the possibility of distributing the operations on highly-parallel graphical processing units.

Finally, a third goal of the project will be to demonstrate the practical usefulness of the platform, by applying it to specific problems of Robotics and Molecular Modeling that are of interest to industrial partners involved in the project. The platform will be applied to (1) the synthesis of grasps for stable and dexterous manipulation of objects with multifingered hands, and to (2) the motion analysis of constrained peptides with applications to drug design.

For more information visit the Kinematics and Robot Design web page or the Cuik project web page.

Project Publications

Journal Publications

  • O. Bohigas, D. Zlatanov, L. Ros, M. Manubens and J.M. Porta. A general method for the numerical computation of manipulator singularity sets. IEEE Transactions on Robotics, 30(2): 340-351, 2014.

    Open/Close abstract Abstract Info Info pdf PDF
  • J.M. Porta, L. Ros, O. Bohigas, M. Manubens, C. Rosales and L. Jaillet. The CUIK suite: Analyzing the motion closed-chain multibody systems. IEEE Robotics and Automation Magazine, 21(3): 105-114, 2014.

    Open/Close abstract Abstract Info Info pdf PDF
  • 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.

    Open/Close abstract Abstract Info Info pdf PDF
  • C. Rosales, J.M. Porta and L. Ros. Grasp optimization under specific contact constraints. IEEE Transactions on Robotics, 29(3): 746-757, 2013.

    Open/Close abstract Abstract Info Info pdf PDF
  • L. Jaillet and J.M. Porta. Efficient asymptotically-optimal path planning on manifolds. Robotics and Autonomous Systems, 61(8): 797–807, 2013.

    Open/Close abstract Abstract Info Info pdf PDF
  • R. Valencia, M. Morta, J. Andrade-Cetto and J.M. Porta. Planning reliable paths with Pose SLAM. IEEE Transactions on Robotics, 29(4): 1050-1059, 2013.

    Open/Close abstract Abstract Info Info pdf PDF
  • O. Bohigas, M. Manubens and L. Ros. Singularities of non-redundant manipulators: A short account and a method for their computation in the planar case. Mechanism and Machine Theory, 68: 1-17, 2013.

    Open/Close abstract Abstract Info Info pdf PDF
  • O. Bohigas, Michael E. Henderson, L. Ros, M. Manubens and J.M. Porta. Planning singularity-free paths on closed-chain manipulators. IEEE Transactions on Robotics, 29(4): 888-898, 2013.

    Open/Close abstract Abstract Info Info pdf PDF
  • 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.

    Open/Close abstract Abstract Info Info pdf PDF
  • L. Jaillet and J.M. Porta. Path planning under kinematic constraints by rapidly exploring manifolds. IEEE Transactions on Robotics, 29(1): 105-117, 2013.

    Open/Close abstract Abstract Info Info pdf PDF
  • 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.

    Open/Close abstract Abstract Info Info pdf PDF
  • S. Ulbrich, V. Ruiz de Angulo, T. Asfour, C. Torras and R. Dillman. General robot kinematics decomposition without intermediate markers. IEEE Transactions on Neural Networks, 23(4): 620-630, 2012.

    Open/Close abstract Abstract Info Info pdf PDF
  • S. Ulbrich, V. Ruiz de Angulo, C. Torras, T. Asfour and R. Dillman. Kinematic Bézier maps. IEEE Transactions on Systems, Man and Cybernetics: Part B, 42(4): 1215-1230, 2012.

    Open/Close abstract Abstract Info Info pdf PDF
  • 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.

    Open/Close abstract Abstract Info Info pdf PDF
  • G. Sanroma, R. Alquézar Mancho, F. Serratosa i Casanelles and B. Herrera. Smooth point-set registration using neighboring constraints. Pattern Recognition Letters, 33(15): 2029-2037, 2012.

    Open/Close abstract Abstract Info Info pdf PDF
  • V. Ruiz de Angulo, J. Cortés and J.M. Porta. Rigid-CLL: Avoiding constant-distance computations in cell linked-lists algorithms. Journal of Computational Chemistry, 33(3): 294-300, 2012.

    Open/Close abstract Abstract Info Info pdf PDF
  • 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.

    Open/Close abstract Abstract Info Info pdf PDF
  • V. Ila, J.M. Porta and J. Andrade-Cetto. Amortized constant time state estimation in Pose SLAM and hierarchical SLAM using a mixed Kalman-information filter. Robotics and Autonomous Systems, 59(5): 310-318, 2011.

    Open/Close abstract Abstract Info Info pdf PDF
  • 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.

    Open/Close abstract Abstract Info Info pdf PDF

Conference Publications

  • M. Manubens, D. Devaurs, L. Ros and J. Cortés. Motion planning for 6D manipulation with aerial towed-cable systems, IX Robotics: Science and Systems Conference, 2013, Berlin, Germany.

    Open/Close abstract Abstract Info Info pdf PDF
  • L. Ros, J.M. Porta, O. Bohigas, M. Manubens, C. Rosales and L. Jaillet. An open-source toolbox for motion analysis of closed-chain mechanisms, 6th International Workshop on Computational Kinematics, 2013, Barcelona, in Computational Kinematics, Vol 15 of Mechanisms and Machine Science, pp. 147-154, 2014, Springer.

    Open/Close abstract Abstract Info Info pdf PDF
  • J.M. Porta, L. Ros, B. Schulze, A. Sljoka and W. Whiteley. On the symmetric molecular conjectures, 6th International Workshop on Computational Kinematics, 2013, Barcelona, in Computational Kinematics, Vol 15 of Mechanisms and Machine Science, pp. 175-184, 2014, Springer.

    Open/Close abstract Abstract Info Info pdf PDF
  • M. Manubens, D. Devaurs, L. Ros and J. Cortés. A motion planning approach to 6-D manipulation with aerial towed-cable systems, 2013 International Micro Air Vehicle Conference and Flight Competition, 2013, Toulouse, France.

    Open/Close abstract Abstract Info Info pdf PDF
  • M. Manubens, D. Devaurs, J. Cortés and L. Ros. 6-D manipulation with aerial towed-cable system, 2013 RSS Workshop on Aerial Mobile Manipulation, 2013, Berlin, Germany.

    Open/Close abstract Abstract Info Info pdf PDF
  • O. Bohigas, D. Zlatanov, M. Manubens and L. Ros. On the numerical classification of the singularities of robot manipulators, 2012 ASME International Design Engineering Technical Conference, 2012, Chicago, Illinois, USA, pp. 1287-1296.

    Open/Close abstract Abstract Info Info pdf PDF
  • O. Bohigas, Michael E. Henderson, L. Ros and J.M. Porta. A singularity-free path planner for closed-chain manipulators, 2012 IEEE International Conference on Robotics and Automation, 2012, Saint Paul, MN, USA, pp. 2128-2134, IEEE.

    Open/Close abstract Abstract Info Info pdf PDF
  • O. Bohigas, D. Zlatanov, L. Ros, M. Manubens and J.M. Porta. Numerical computation of manipulator singularities, 2012 IEEE International Conference on Robotics and Automation, 2012, Saint Paul, MN, USA, pp. 1351-1358, IEEE.

    Open/Close abstract Abstract Info Info pdf PDF
  • L. Jaillet and J.M. Porta. Asymptotically-optimal path planning on manifolds, VIII Robotics: Science and Systems Conference, 2012, Sydney, Australia, pp. 1-8, MIT Press.

    Open/Close abstract Abstract Info Info pdf PDF
  • O. Bohigas, M. Manubens and L. Ros. Planning singularity-free force-feasible paths on the Stewart platform, 13th International Symposium on Advances in Robot Kinematics, 2012, Innsbruck, in Latest Advances in Robot Kinematics, pp. 245-252, 2012, Springer.

    Open/Close abstract Abstract Info Info pdf PDF
  • O. Bohigas, M. Manubens and L. Ros. Navigating the wrench-feasible C-space of cable-driven hexapods, 1st International Conference on Cable-Driven Parallel Robots, 2012, Stuttgart, in Cable-Driven Parallel Robots, Vol 12 of Mechanisms and Machine Science, pp. 53-68, 2013, Springer.

    Open/Close abstract Abstract Info Info pdf PDF
  • C. Rosales, R. Suárez, M. Gabiccini and A. Bicchi. On the synthesis of feasible and prehensile robotic grasps, 2012 IEEE International Conference on Robotics and Automation, 2012, Saint Paul, MN, USA, pp. 550-556, IEEE.

    Open/Close abstract Abstract Info Info pdf PDF
  • E. Simo-Serra, A. Perez, H. Moon and N. Robson. Kinematic synthesis of multi-fingered robotic hands for finite and infinitesimal tasks, 13th International Symposium on Advances in Robot Kinematics, 2012, Innsbruck, in Latest Advances in Robot Kinematics, pp. 173-180, 2012, Springer.

    Open/Close abstract Abstract Info Info pdf PDF
  • E. Simo-Serra, F. Moreno-Noguer and A. Perez. Design of non-anthropomorphic robotic hands for anthropomorphic tasks, 2011 ASME International Design Engineering Technical Conference, 2011, Washington, DC, USA, pp. 377-386.

    Open/Close abstract Abstract Info Info pdf PDF
  • R. Valencia, J. Andrade-Cetto and J.M. Porta. Path planning in belief space with Pose SLAM, 2011 IEEE International Conference on Robotics and Automation, 2011, Shanghai, China, pp. 78-83, IEEE.

    Open/Close abstract Abstract Info Info pdf PDF
  • C. Rosales, J.M. Porta and L. Ros. Global optimization of robotic grasps, VII Robotics: Science and Systems Conference, 2011, Los Angeles, USA, pp. 1-8, MIT Press.

    Open/Close abstract Abstract Info Info pdf PDF
  • L. Jaillet and J.M. Porta. Path planning with loop closure constraints using an atlas-based RRT, 15th International Symposium on Robotics Research, 2011, Flagstaff, USA, Springer.

    Open/Close abstract Abstract Info Info pdf PDF
  • L. Jaillet, J. Hoffman, J. van den Berg, P. Abbeel, J.M. Porta and K. Goldberg. EG-RRT: Environment-guided random trees for kinodynamic motion planning with uncertainty and obstacles, 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2011, San Francisco, CA, USA, pp. 2646-2652, IEEE Press.

    Open/Close abstract Abstract Info Info pdf PDF
  • A. Goldsztejn, C. Jermann, V. Ruiz de Angulo and C. Torras. Symmetry breaking in numeric constraint problems, 17th International Conference on Principles and Practice of Constraint Programming, 2011, Perugia, Italy, in Principles and Practice of Constraint Programming, Vol 6876 of Lecture Notes in Computer Science, pp. 317-324, 2011, Springer.

    Open/Close abstract Abstract Info Info pdf PDF
  • O. Bohigas, L. Ros and M. Manubens. A unified method for computing position and orientation workspaces of general Stewart platforms, 2011 ASME International Design Engineering Technical Conference, 2011, Washington, DC, USA, pp. 959-968.

    Open/Close abstract Abstract Info Info pdf PDF

Other Publications

  • O. Bohigas, M. Manubens and L. Ros. Singularities of Robot Mechanisms: Numerical Computation and Avoidance Path Planning. Volume 41 of Mechanisms and Machine Science. Springer, 2017.

    Open/Close abstract Abstract Info Info