Fermín León, Leonardo Javier
CASTELLANOS GÓMEZ, JOSÉ ÁNGEL (dir.)
Universidad de Zaragoza,
2018
Abstract: Aplicando análisis provenientes de la teoría de grafos, la teoría espectral de grafos, la exploración de grafos en línea, generamos un sistema de SLAM activo que incluye la planificación de rutas bajo incertidumbre, extracción de grafos topológicos de entornos y SLAM activo \'optimo.
En la planificación de trayectorias bajo incertidumbre, incluimos el análisis de la probabilidad de asociación correcta de datos. Reconociendo la naturaleza estocástica de la incertidumbre, demostramos que planificar para minimizar su valor esperado es más fiable que los actuales algoritmos de planificación de trayectorias con incertidumbre.
Considerando el entorno como un conjunto de regiones convexas conectadas podemos tratar la exploración robótica como una exploración de grafos en línea. Se garantiza una cobertura total si el robot visita cada región. La mayoría de los métodos para segmentar el entorno están basados en píxeles y no garantizan que las regiones resultantes sean convexas, además pocos son algoritmos incrementales. En base a esto, modificamos un algoritmo basado en contornos en el que el entorno se representa como un conjunto de polígonos que debe segmentarse en un conjunto de polígonos pseudo convexos. El resultado es un algoritmo de segmentación que produjo regiones pseudo-convexas, robustas al ruido, estables y que obtienen un gran rendimiento en los conjuntos de datos de pruebas.
La calidad de un algoritmo se puede medir en términos de cuan cercano al óptimo está su rendimiento. Con esta motivación definimos la esencia de la tarea de exploración en SLAM activo donde las únicas variables son la distancia recorrida y la calidad de la reconstrucción. Restringiendo el dominio al grafo que representa el entorno y probando la relación entre la matriz asociada a la exploración y la asociada al grafo subyacente, podemos calcular la ruta de exploración óptima.
A diferencia de la mayoría de la literatura en SLAM activo, proponemos que la heurística para la exploración de grafos consiste en atravesar cada arco una vez. Demostramos que el tipo de grafos resultantes tiene un gran rendimiento con respecto a la trayectoria \'optima, con resultados superiores al 97 \% del \'optimo en algunas medidas de calidad.
El algoritmo de SLAM activo TIGRE integra el algoritmo de extracción de grafos propuesto con nuestra versión del algoritmo de exploración incremental que atraviesa cada arco una vez. Nuestro algoritmo se basa en una modificación del algoritmo clásico de Tarry para la búsqueda en laberintos que logra el l\'imite inferior en la aproximación para un algoritmo incremental. Probamos nuestro sistema incremental en un escenario de exploración típico y demostramos que logra un rendimiento similar a los métodos fuera de línea y también demostramos que incluso el método \'optimo que visita todos los nodos calculado fuera de línea tiene un peor rendimiento que el nuestro.
Abstract (other lang.):
En la planificación de trayectorias bajo incertidumbre, incluimos el análisis de la probabilidad de asociación correcta de datos. Reconociendo la naturaleza estocástica de la incertidumbre, demostramos que planificar para minimizar su valor esperado es más fiable que los actuales algoritmos de planificación de trayectorias con incertidumbre.
Considerando el entorno como un conjunto de regiones convexas conectadas podemos tratar la exploración robótica como una exploración de grafos en línea. Se garantiza una cobertura total si el robot visita cada región. La mayoría de los métodos para segmentar el entorno están basados en píxeles y no garantizan que las regiones resultantes sean convexas, además pocos son algoritmos incrementales. En base a esto, modificamos un algoritmo basado en contornos en el que el entorno se representa como un conjunto de polígonos que debe segmentarse en un conjunto de polígonos pseudo convexos. El resultado es un algoritmo de segmentación que produjo regiones pseudo-convexas, robustas al ruido, estables y que obtienen un gran rendimiento en los conjuntos de datos de pruebas.
La calidad de un algoritmo se puede medir en términos de cuan cercano al óptimo está su rendimiento. Con esta motivación definimos la esencia de la tarea de exploración en SLAM activo donde las únicas variables son la distancia recorrida y la calidad de la reconstrucción. Restringiendo el dominio al grafo que representa el entorno y probando la relación entre la matriz asociada a la exploración y la asociada al grafo subyacente, podemos calcular la ruta de exploración óptima.
A diferencia de la mayoría de la literatura en SLAM activo, proponemos que la heurística para la exploración de grafos consiste en atravesar cada arco una vez. Demostramos que el tipo de grafos resultantes tiene un gran rendimiento con respecto a la trayectoria \'optima, con resultados superiores al 97 \% del \'optimo en algunas medidas de calidad.
El algoritmo de SLAM activo TIGRE integra el algoritmo de extracción de grafos propuesto con nuestra versión del algoritmo de exploración incremental que atraviesa cada arco una vez. Nuestro algoritmo se basa en una modificación del algoritmo clásico de Tarry para la búsqueda en laberintos que logra el l\'imite inferior en la aproximación para un algoritmo incremental. Probamos nuestro sistema incremental en un escenario de exploración típico y demostramos que logra un rendimiento similar a los métodos fuera de línea y también demostramos que incluso el método \'optimo que visita todos los nodos calculado fuera de línea tiene un peor rendimiento que el nuestro.
Abstract (other lang.):
Pal. clave: robótica
Titulación: Programa de Doctorado en Ingeniería de Sistemas e Informática
Plan(es): Plan 512
Department: Informática e Ingeniería de Sistemas
Nota: Presentado: 09 07 2018
Nota: Tesis-Univ. Zaragoza, Informática e Ingeniería de Sistemas, 2018
-
Permalink:
Visitas y descargas
Record created 2018-10-16, last modified 2021-05-20
