03-10-2012, 04:40 PM
Fast Multiresolutive Approximations of Planar Linkage Configuration Spaces
Fast Multiresolutive Approximations.pdf (Size: 635.42 KB / Downloads: 42)
INTRODUCTION
A planar linkage is a set of rigid bodies, also called links,
pairwise articulated through revolute or slider joints, all lying
in a plane. A linkage configuration is a specification of its
spatial shape, i.e., an assignment of positions and orientations
to all links that respects the kinematic constraints imposed by
all joints. As it is well known, the configuration space of a
linkage—the set of all possible configurations—corresponds
to the solution set of a system of polynomial equations, and
thus forms an algebraic variety. This paper presents a numerical
method able to approximate this variety at any desired
resolution, irrespective of whether it contains a finite number
of isolated points (corresponding to rigid configurations) or
higher-dimensional connected components (corresponding to
finite motions of the linkage).
CONVERGENCE ORDER
The asymptotic performance of a root finding algorithm is
normally evaluated by examining its convergence order. An
algorithm is said to exhibit a convergence of order r if there
exists a constant k ∈ (0, 1), such that
CONCLUSIONS
We have presented a complete method able to give box
approximations of the configuration space of a planar linkage.
The method is universal, in the sense that it can manage
linkages of any number of links, jointed to form kinematic
loops of arbitrary topology. It is also complete, in the sense
that every solution point will be contained in one of the
returned boxes. Moreover, in all experiments done so far the
algorithm was also correct, in the sense that all returned boxes
contained at least one solution point. Although in theory this is
not guaranteed, returning boxes with no solution seems rather
improbable, due to the fact that the linerization of circle and
hyperbolic equations introduce errors smaller than the size of
the considered boxes. Moreover the fact that all equations
are simultaneously taken into account during box reduction
(whether directly or in a linearized form) palliates the so-called
cluster effect, a known problem of bisection-based techniques
of this kind [19], whereby each solution is obtained as a
compact cluster of boxes instead of a single box containing
it. In the experiments performed so far, we never encountered
such spurious output.
A main contribution with respect to previous works is the
method’s ability to deal with configuration spaces of general
structure. This is accomplished by maintaining a collection
of boxes that form a tight envelope of such spaces, which
can be refined to the desired accuracy in a multiresolutive
fashion. Empirical tests show that the method is quadratically
convergent to all roots if these are isolated points, and linearly
convergent to them if these form a one-dimensional connected
components. Although an extensive study should be carried out
to determine how the method’s performance scales with the
complexity of the tackled linkages, on all tested examples it
was at least one order of magnitude faster than existing solvers
applied to the same problems.