[EN] The efficiency of free-collision motion planning results very sensible on robot and obstacle modelling
technique selected. In this way, many works have been oriented to define models with proper
throughput to speed up the collision detection proccess. This dissertation presents a new approach to
the problem, whose complexity is reduced notably by means of using enveloping models of real
objects, allowing security regions or distances. This objective is reached by means of the definition of
a spherical model, composed of infinite spheres, generated from the application of linear or
polynomial equations to a reduced number of control spheres, giving the so-called poly-spheres and
spheroids respectively. These models, with evident simplicity, present a high modelling power, adapt
easily to the requirements need in collision-detection and path planning applications for robotics
systems.
In order to represent a complete multi-robot cell, an extended hierarchical structure has been defined,
in form of an AND-OR graph, with different degrees of accuracy, according to the different
approximation model used. In order to generate automatically this structure, a procedure has been
developed to compute the minimum volume enveloping spherical model in an off-line process with
two levels based on Downhill Simplex method and Hough transform. This procedure can be greatly
speed up by using clustering techniques to obtain appropiate initial conditions, allowing an on-line
use. With a hierarchical structure computed in such a way, a fast procedure for collision detection in a
multi-robot cell is introduced, based on several algorithms for distance computation including polyspheres
and spheroids. This methodology presents a fast and anticipativa response, in the sense that
every movement of a system has been validated before its execution, implying that not necessarily
must be done in an off-line simulation.
The use of spherical models, in addition to their fast distance computation, results suitable for the
definition of artificial potential fields allowing a path planning in robotics systems with up to six
degrees of freedom, including three for translation and three for rotation. The definition of these new
potential fields and the study of new planning techniques based on classical optimisation methods
allow their application straight forward in Cartesian space, with all their advantages.
Last but not least, with the help of some systems for robot programming, simulation and control, the
correctness of these contributions have been validated in a set of prototype applications, covering
from robot-obstacle and multi-robot collision detection, to motion planning for a robot-arm or an
auto-guided vehicle. / [ES] La eficiencia de la planificación de movimientos libres de colisión resulta muy sensible al modelado
de los robots y obstáculos que se consideren, por lo que, frente al modelado tradicional con politopos,
muchos trabajos en robótica han estado orientados a la definición de unos modelos que presenten
buenas prestaciones de cara a acelerar el proceso de detección de colisiones. En esta Tesis se presenta
una nueva perspectiva del problema, cuya complejidad queda reducida notablemente al utilizar
envolventes de los objetos reales, lo que permite definir zonas o distancias de seguridad. Para ello se
han definido unos modelos esféricos, compuestos de infinitas esferas generadas a partir de la
aplicación de unas relaciones lineales o polinómicas a un número reducido de esferas de control,
dando lugar a las llamadas poli-esferas y esferoides respectivamente. Estos modelos, de sencillez
clara, presentan una potencia de modelado elevada, adaptándose fácilmente a los requisitos necesarios
en las aplicaciones de detección de colisiones y planificación de movimientos en sistemas
robotizados.
Para la representación de una célula multi-robot completa, se ha definido una estructura jerárquica
extendida, en forma de grafo AND-OR, con diferentes grados de precisión, mediante diferentes
modelos de aproximación. De cara a generar automáticamente esta estructura, se ha desarrollado un
procedimiento para generar el modelo esférico envolvente de mínimo volumen en un proceso off-line
con dos niveles, basados en el método de minimización Downhill Simplex y en la transformada de
Hough. Este procedimiento se acelera enormemente al utilizar técnicas de agrupamiento para obtener
condiciones iniciales apropiadas, permitiendo su uso on-line. Con una estructura jerárquica generada
de esta forma, se introduce un procedimiento rápido de detección de colisiones aplicable a una célula
multi-robot, basado en algoritmos básicos de cálculo de distancias que pueden considerar poli-esferas
y esferoides. Esta metodología presenta una respuesta rápida y anticipativa, entendiendo por tal que
todo movimiento de cualquier sistema ha sido validado antes de su ejecución, por lo que no
necesariamente debe realizarse en una simulación off-line.
La utilización de modelos esféricos, así como el rápido cálculo de distancias entre ellos, resulta idónea
para la definición de campos potenciales artificiales que permitan una planificación de movimientos
en sistemas robotizados con hasta seis grados de libertad, incluyendo tres de traslación y tres de
rotación. La definición de estos nuevos campos potenciales y el estudio de nuevas técnicas de
planificación basados en métodos clásicos de optimización permiten su aplicación directamente en el
espacio cartesiano, con las claras ventajas que esto conlleva.
Finalmente, con la ayuda de varios sistemas de programación, simulación y control de robots, se ha
demostrado la validez de estas aportaciones en una serie de aplicaciones prototipo que van desde la
detección de colisiones de un robot con un obstáculo o entre sistemas multi-robot, a la planificación
de movimientos de un brazo-robot o un vehículo autoguiado. / Mellado Arteche, M. (1996). Modelado, detección de colisiones y planificación de movimientos en sistemas robotizados mediante volúmenes esféricos [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/56621
| Identifer | oai:union.ndltd.org:upv.es/oai:riunet.upv.es:10251/56621 |
| Date | 28 October 2015 |
| Creators | Mellado Arteche, Martín |
| Contributors | Tornero Montserrat, Josep, Universitat Politècnica de València. Departamento de Informática de Sistemas y Computadores - Departament d'Informàtica de Sistemes i Computadors |
| Publisher | Universitat Politècnica de València |
| Source Sets | Universitat Politècnica de València |
| Language | Spanish |
| Detected Language | Spanish |
| Type | info:eu-repo/semantics/doctoralThesis |
| Source | Riunet |
| Rights | http://rightsstatements.org/vocab/InC/1.0/, info:eu-repo/semantics/openAccess |
Page generated in 0.0025 seconds