Please use this identifier to cite or link to this item: http://repositorio.yachaytech.edu.ec/handle/123456789/478
Title: Simulation of collision avoidance algorithms in 2D using Voronoi Diagrams
Authors: Pineda Arias, Israel Gustavo
Cuenca Macas, Leduin José
Keywords: Prevención de colisiones
Diagramas de Voronoi
Optimización convexa
Programación cuadrática
Planificación de rutas
Simulación
Collision avoidance
Voronoi Diagrams
Convex optimization
Quadratic programming
Path planning
Simulation
Issue Date: Jan-2022
Publisher: Universidad de Investigación de Tecnología Experimental Yachay
Abstract: El presente trabajo resuelve el problema de prevención de colisiones en una simulación de un sistema centralizado de multiagentes holonómicos en un espacio bidimensional libre de obstáculos estáticos. Para ello, proponemos una implementación de una arquitectura con tres módulos para cubrir las siguientes estrategias: Estrategia de Evaluación de Amenazas (EEA), Estrategia de Planificación de Rutas (EPR) y Estrategia de Seguimiento de Rutas (ESR). Las celdas de Voronoi amortiguadas representan la EEA. Los módulos con la EPR utilizan dos algoritmos: el Algoritmo Geométrico Analítico (AGA) y el algoritmo de Control de Horizontes en Retroceso (CHR) basado en Programación Cuadrática (PC). Finalmente, la EPR controla el seguimiento según magnitudes de distancia fijas en cada iteración. El análisis de los resultados considera el tiempo de ejecución computacional, el número de pasos hasta la convergencia y el cálculo de valores óptimos. Además, estos resultados se comparan con el algoritmo de Prevención de Colisiones Recíproco Óptimo (PCRO). De esta forma, nuestra propuesta aborda y resuelve con éxito el problema de prevención de colisiones, pero requiere más tiempo de ejecución y número de pasos en comparación con el algoritmo de PCRO. Además, el número de pasos del AGA está más cerca del algoritmo de PCRO, produciendo resultados prometedores con una precisión del 95%.
Description: This work solves the Collision Avoidance problem in a simulation of a centralized system of holonomic multi-agents in a two-dimensional space free of static obstacles. For this, we propose an implementation of three modules in an architecture: Threat Assessment Strategy (TAS), Path Planning Strategy (PPS), and Path Tracking Strategy (PTS). The Buffered Voronoi Cells represent the TAS. The PPS modules use two algorithms: the Analytical Geometric Algorithm (AGA) and the Receding Horizons Control (RHC) based on Quadratic Programming (QP) Algorithm. Finally, PTS controls the tracking according to fixed distance magnitudes in each iteration. The analysis of the results considers the computational execution time, the number of steps until convergence, and the calculation of optimal values. Also, these results are compared with the Optimal Reciprocal Collision Avoidance (ORCA) algorithm. In this way, our proposal successfully addresses and solves the collision avoidance problem but takes more execution time and number of steps compared with the ORCA algorithm. Besides, the number of steps of AGA is closer to ORCA, producing promising results with an accuracy of 95%.
URI: http://repositorio.yachaytech.edu.ec/handle/123456789/478
Appears in Collections:Tecnologías de la Información

Files in This Item:
File Description SizeFormat 
ECMC0091.pdf2.08 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.