Symmetry breaking has been a hot topic of research in the past years, leading to many theoretical developments as well as strong scaling strategies for dealing with hard applications. Most of the research has however focused on discrete, combinatorial, problems, and only few considered also continuous, numerical, problems. While part of the theory applies in both contexts, numerical problems have specificities that make most of the technical developments inadequate.
In this paper, we present the rlex constraints, partial symmetry-breaking inequalities corresponding to a relaxation of the famous lex constraints extensively studied in the discrete case. They allow (partially) breaking any variable symmetry and can be generated in polynomial time. Contrarily to lex constraints that are impractical in general (due to their overwhelming number) and inappropriate in the continuous context (due to their form), rlex constraints can be efficiently handled natively by numerical constraint solvers. Moreover, we demonstrate their pruning power on continuous domains is almost as strong as that of lex constraints, and they subsume several previous work on breaking specific symmetry classes for continuous problems. Their experimental behavior is assessed on a collection of standard numerical problems and the factors influencing their impact are studied. The results confirm rlex constraints are a dependable counterpart to lex constraints for numerical problems.
Many of the existing molecular simulation tools require the efficient identification of the set of nonbonded interacting atoms. This is necessary, for instance, to compute the energy values or the steric contacts between atoms. Cell linked-lists can be used to determine the pairs of atoms closer than a given cutoff distance in asymptotically optimal time. Despite this long-term optimality, many spurious distances are anyway computed with this method. Therefore, several improvements have been proposed, most of them aiming to refine the volume of influence for each atom. Here, we suggest a different improvement strategy based on avoiding to fill cells with those atoms that are always at a constant distance of a given atom. This technique is particularly effective when large groups of the particles in the simulation behave as rigid bodies as it is the case in simplified models considering only few of the degrees of freedom of the molecule. In these cases, the proposed technique can reduce the number of distance computations by more than one order of magnitude, as compared with the standard cell linked-list technique. The benefits of this technique are obtained without incurring in additional computation costs, because it carries out the same operations as the standard cell linked-list algorithm, although in a different order. Since the focus of the technique is the order of the operations, it might be combined with existing improvements based on bounding the volume of influence for each atom
The calibration of serial manipulators with high
numbers of degrees of freedom by means of machine learning is
a complex and time-consuming task. With the help of a simple
strategy, this complexity can be drastically reduced and the speed
of the learning procedure can be increased: When the robot is
virtually divided into shorter kinematic chains, these subchains
can be learned separately and, hence, much more efficiently
than the complete kinematics. Such decompositions, however,
require either the possibility to capture the poses of all endeffectors
of all subchains at the same time, or they are limited to
robots that fulfill special constraints. In this work, an alternative
decomposition is presented that does not suffer from these
limitations. An offline training algorithm is provided in which
the composite subchains are learned sequentially with dedicated
movements. A second training scheme is provided to train
composite chains simultaneously and online. Both schemes can
be used together with many machine learning algorithms. In the
simulations, an algorithm using Parameterized Self-Organizing
Maps (PSOM) modified for online learning and Gaussian Mixture
Models (GMM) were chosen to show the correctness of the
approach. The experimental results show that, using a two-fold
decomposition, the number of samples required to reach a given
Ulbrich, S.; Ruiz De Angulo, V.; Torras, C.; Asfour, T.; Dillmann, R. IEEE transactions on systems man and cybernetics Part B-Cybernetics Vol. 42, num. 4, p. 1215-1230 DOI: 10.1109/TSMCB.2012.2188507 Date of publication: 2012 Journal article
The kinematics of a robot with many degrees of freedom is a very complex function. Learning this function for a large workspace with a good precision requires a huge number of training samples, i.e., robot movements. In this paper, we introduce the Kinematic Bézier Map (KB-Map), a parameterizable model without the generality of other systems but whose structure readily incorporates some of the geometric constraints of a kinematic function. In this way, the number of training samples required is drastically reduced. Moreover, the simplicity of the model reduces learning to solving a linear least squares problem. Systematic experiments have been carried out showing the excellent interpolation and extrapolation capabilities of KB-Maps and their relatively low sensitivity to noise.
This Technical Report introduces a data structure and an algorithm to efficiently to efficiently determine rigid clusters in a given molecule. This is a relevant problem in Monte Carlo simulations where the actuated DOFs change at each iteration. If the number of actuated DOFs is small, large temporary rigid groups appear during the time spanned by a MCS step. This document also provides a way of calculating the total energy in the molecules taking into account only inter-rigid energy terms. Thus, a large fraction of energy terms are not required to
be computed, namely intra-rigid terms.
Goldsztejn, A.; Jermann, C.; Ruiz De Angulo, V.; Torras, C. International Conference on Principles and Practice of Constraint Programming p. 317-324 DOI: 10.1007/978-3-642-23786-7_25 Presentation's date: 2011 Presentation of work at congresses
Symmetry-breaking constraints in the form of inequalities between variables have been proposed for a few kind of solution symmetries in numeric CSPs. We show that, for the variable symmetries among those, the proposed inequalities are but a specific case of a relaxation of the well-known LEX constraints extensively used for discrete CSPs. We discuss the merits of this relaxation and present experimental evidences of its practical interest.
Ruiz De Angulo, V.; Torras, C. IEEE transactions on systems man and cybernetics Part B-Cybernetics Vol. 38, num. 6, p. 1571-1577 DOI: 10.1109/TSMCB.2008.928232 Date of publication: 2008-01 Journal article
We propose a technique to speed up the learning of the inverse kinematics of a robot manipulator by decomposing it into two or more virtual robot arms. Unlike previous decomposition approaches, this one does not place any requirement on the robot architecture and, thus, it is completely general. Parametrized Self-Organizing Maps (PSOM) are particularly adequate for this type of learning, and permit comparing results obtained directly and through the decomposition. Experimentation shows that time reductions of up to two orders of magnitude are easily attained.
Symmetries in discrete constraint satisfaction problems have been explored and exploited in the last years, but symmetries in continuous constraint problems have not received the same attention. Here we focus on permutations of the variables consisting of one single cycle. We propose a procedure that takes advantage of these symmetries by interacting with a continuous constraint solver without interfering with it. A key concept in this procedure are the classes of symmetric boxes formed by bisecting a n-dimensional cube at the same point in all dimensions at the same time. We analyze these classes and quantify them as a function of the cube dimensionality. Moreover, we propose a simple algorithm to generate the representatives of all these classes for any number of variables at very high rates. A problem example from the chemical ﬁeld and a kinematics solver are used to show the performance of the approach in practice.
Cortés, J.; Simeon, T.; Ruiz De Angulo, V.; Guieysse, D.; Remaud, M.; Remaud-Simeon, M.; Tran, V. Bioinformatics Vol. 21, num. Suppl. 1, p. 116-125 DOI: 10.1093/bioinformatics/bti1017 Date of publication: 2005-06 Journal article