Tesis Doctorado
Resolutión de systemes d equatións de distance avec incertitudes.
Autor
Grandón, Carlos
Institución
Resumen
In this thesis we are interested in a particular class of problems which frequently
appear in robotics (and many other areas as chemistry, molecular biology, Computer-Aided
Design (CAD), and aeronautics). They are systems of distance equations
with uncertainties.
Uncertain values mean values which are not exactly determined but are bounded
by well-known limits. These values are represented as intervais, and frequently
come from measurements. In a model, these values appear as existentially quantified
parameters.
Solving such a problem with uncertainties means to find a set of solutions
taking into account these inaccuracies in order to obtain certified answers (in the
way that no solution is lost).
The aim of the works contained in this thesis is to solve systems of distance
equations with uncertainties in their parameters as accurately as possible, combining
techniques from Constraint Programming and Interval Analysis communities.
A common approximation for the solutions for these types of problems is to
replace parameters with interval values by real numbers, and to solve the problem
without considering the inaccuracies. We show that this approximation is not
convenient, especially when certified solutions are required (for example for safely
reasons for a Surgical Robot).
In a first phase, we propose a special Branch and Prune algorithm with conditional
bisection which is able to compute a rough approximation of each continuum
of solutions for a given problem.
A rough approximation (a box) is not enough in all the cases, thus a sharp
approximation (a set of boxes) describing continuous solution sets is often required.
We show that this approximation must consider an inne- bor te.st in order to
detect large parts of the search space containing only solutions to the problem.
Using inner box tests not only reduces the number of generated boxes but also
provides more information about the geometry of the solutions set. We propose
and compare various inner box tests for distance equations with uncertainties.
When a single solution point belonging to a continuum of solutions is given,
an inner box around this point and totally included within the continuum of
solutions may be very interesting for tolerance issues. For this reason we propose
a strategy for building such a box based on theoretical results of Modal Interval
Analysis combined with a well-known technique of Constraint Programming called projection.
Finaily, the developed techniques are illustrated on a real problern of Robotics
in which we solve the direct kinematics of a special class of parallel robot. PFCHA-Becas Docteur en Sciences 186p. PFCHA-Becas TERMINADA