Resumen

En robótica, los Diagramas de Voronoi Generalizados (GVDs) son ampliamente utilizados por robots móviles para representar las topologías espaciales de su entorno. En este trabajo consideramos el problema de construir GVDs en entornos discretos. En la literatura existen varios algoritmos que resuelven este problema, en particular el algoritmo Brushfire y sus versiones mejoradas que poseen un mecanismo de reparación local. Sin embargo, cuando el área a procesar es muy grande o es de alta resolución, el tamaño de las matrices métricas utilizadas por estos algoritmos para calcular los GVDs puede ser prohibitivo. Para resolver este problema, proponemos una mejora de los algoritmos actuales, utilizando quadtrees sin punteros en lugar de matrices métricas para calcular y mantener los GVD. Más allá de la construcción y reconstrucción de una GVD, nuestro algoritmo proporciona además un método para aproximar hojas de ruta en múltiples granularidades a partir de la GVD basada en quadtree. Las pruebas de simulación en escenarios representativos demuestran que, en comparación con los algoritmos actuales, nuestro algoritmo generalmente mejora en un orden de magnitud el coste de memoria cuando el área es superior a 2 10 × 2 10 . También demostramos la utilidad de las hojas de ruta aproximadas para tareas de búsqueda de rutas de grueso a fino.

• Materias:Matemáticas Análisis Matemático Álgebra Ingeniería
• Subjects:mathematics Mathematical Analysis Algebra Engineering
• Palabras claves:gvds, área, algoritmos actuales, matrices métricas, diagramas de voronoi generalizados, tareas de búsqueda de rutas finas, mecanismo de reparación local, gvd, algoritmo, problema
• Keywords:gvds, area, current algorithms, metric matrices, generalized voronoi diagrams, fine pathfinding tasks, local repair mechanism, gvd, algorithm, problem