Publication
A branch-and-prune solver for distance constraints
Journal Article (2005)
Journal
IEEE Transactions on Robotics
Pages
176-187
Volume
21
Number
2
Doc link
http://dx.doi.org/10.1109/TRO.2004.835450
File
Authors
Projects associated
DIST: Design and implementation of efficient parallelizable algorithms with applications to robotics and proteomics
SGR ROBÒTICA: Grup de recerca consolidat - ROBÒTICA
RESOL: Resolución de sistemas de ecuaciones cinemáticas para la simulación de mecanismos, posicionado interactivo de objetos y conformación de moléculas
Abstract
Given some geometric elements such as points and lines in R3, 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.
Categories
robots.
Author keywords
branch-and-prune, Cayley–Menger determinant, direct and inverse kinematics, distance constraint, interval method, kinematic and geometric constraint solving, octahedral manipulator
Scientific reference
J.M. Porta, L. Ros, F. Thomas and C. Torras. A branch-and-prune solver for distance constraints. IEEE Transactions on Robotics, 21(2): 176-187, 2005.
Follow us!