Tesis para optar al grado de Magíster en Ciencias, Mención Computación / La detección de colisiones ha sido un tópico de extenso estudio en computación gráfica y geometría computacional. Sus campos de aplicación incluyen la robótica, biología computacional, juegos, y simulaciones en cirugía, física y biología. Un entorno real complejo para la detección de colisiones corresponde a imágenes biomédicas y astronómicas: imágenes en series de tiempo, de gran tamaño, a veces con gran cantidad de objetos, que se mueven y se deforman, y que pueden aparecer o desaparecer de la escena, o experimentar autocolisiones, aspectos que pueden hacer la detección de colisiones un trabajo demasiado lento de calcular sin las estrategias apropiadas. Este trabajo realiza un contraste entre dos enfoques de detección de colisiones de fase amplia en 2D+tiempo: usando los métodos estáticos sweep and prune directo, que funcionan cuadro a cuadro, y el método sweep and prune incremental, que mantiene las estructuras a lo largo de la simulación, contra el enfoque cinético del algoritmo sweep and prune cinético. Ambos enfoques fueron probados en simulaciones de objetos con movimiento rectilíneo en direcciones aleatorias. La comparación se hizo siguiendo los lineamientos de experimentación en algoritmos establecidos por Moret [26] respecto a qué parámetros es pertinente medir, las diez sugerencias de Johnson [22] para realizar un experimento con algoritmos y las sugerencias de Sanders [31] para mostrar los resultados en forma de gráficos. Los resultados muestran que el uso del algoritmo sweep and prune cinético es un orden de magnitud más rápido que los algoritmos sweep and prune estáticos en simulaciones que involucran una distribución aleatoria de objetos en movimiento, sin importar la densidad de objetos en la simulación. También se estudia el efecto de colisiones múltiples dentro de las simulaciones, un suceso que no fue investigado por Coming & Staad [11]. Esto permite hacer sugerencias sobre las instancias en las que un algoritmo es más apropiado que otro.

[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 no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/56621