La navegación de robots móviles en entornos de interior constituye un reto de investigación en el campo de la robótica. Las soluciones que se pueden encontrar son de una gran diversidad. Esta diversidad se justifica por las diferencias en recursos de sensado, localización, computacionales y de comunicaciones que poseen los robots para los que se plantea la solución. Este trabajo se plantea en un entorno de trabajo prestablecido y con una serie de restricciones anteriores al inicio de este trabajo. Se trata de un robot autónomo controlado mediante una FPGA y con posibilidad de localización mediante un sistema de ultrasonidos. Este robot es capaz de realizar un mapa en formato de rejilla. Es sobre este paradigma de rejilla que funciona el algoritmo desarrollado en este trabajo. Junto a esta restricción en el diseño del mapa, se ha incluido una condición extra, la restricción de recursos que implica el uso de la FPGA. Esta limitación se traduce en una menor capacidad de cómputo y capacidad de memoria (en comparación a trabajos existentes que utilizan un ordenador para resolver la navegación). El estado del arte plantea dos alternativas para la resolución de este problema, el uso de algoritmos de navegación sobre grafos (Dijkstra y A) y los algoritmos de navegación orientados a sortear obstáculos locales (Distbug). Frente a estas dos aproximaciones se plantea el nuevo algoritmo desarrollado en este trabajo: HCTNav. Este algoritmo se ha desarrollado con el objetivo de reducir el tamaño de memoria requerido por Dijkstra y a obtener una solución con menor distancia recorrida en comparación con Distbug. Para llevar a cabo la implementación del algoritmo ha sido necesario un desarrollo de un entorno de trabajo adecuado. El inicio de este trabajo consistió en la implementación de un entorno de simulación donde poder aplicar y probar el algoritmo desarrollado. Este entorno fue desarrollado con una interfaz gráfica que ha permitido la depuración y redefinición del algoritmo HCTNav. El algoritmo ha sido implementado en ANSI C junto a versiones de los algoritmos antes mencionados: Dijkstra, A y Distbug. Esta implementación ha permitido la comparación del comportamiento de todos estos algoritmos. La elección del lenguaje ha sido condicionada por el lenguaje que es capaz de interpretar el microprocesador embebido en la FPGA. Las pruebas se han realizado sobre un banco de treinta mapas desarrollados por distintos integrantes del grupo de investigación. Estos mapas de tienen unas dimensiones reducidas (15 columnas y 10 filas). Además, se ha utilizado un subconjunto de estos mapas para crear un test de mapas ampliados. Esta ampliación ha sido automática siguiendo dos líneas, el escalado y la replicación. Este set de mapas contiene versiones ampliadas en factores: 2, 4, 8, 16 y 32. Los resultados obtenidos muestran que el tiempo de ejecución del algoritmo HCTNav es equivalente al tiempo de ejecución de Dijkstra o A*. Siendo del orden de nanosegundos para las versiones pequeñas de los mapas y del orden de un segundo para las versiones ampliadas con un factor de 32. En ambos casos, estos tiempos son despreciables en comparación con el tiempo de desplazamiento del robot (decenas de segundos). En la comparación de recursos de memoria, HCTNav requiere la mitad de memoria en el caso de los mapas pequeños. En el caso de los mapas con máxima ampliación, HCTNav requiere diez veces menos memoria que sus competidores. En cuanto a la mejora del camino óptimo, HCTNav obtiene de media caminos con una longitud significativamente menor que los resultados que obtiene Distbug.

La navegación de robots móviles en entornos de interior constituye un reto de investigación en el campo de la robótica. Las soluciones que se pueden encontrar son de una gran diversidad. Esta diversidad se justifica por las diferencias en recursos de sensado, localización, computacionales y de comunicaciones que poseen los robots para los que se plantea la solución. Este trabajo se plantea en un entorno de trabajo prestablecido y con una serie de restricciones anteriores al inicio de este trabajo. Se trata de un robot autónomo controlado mediante una FPGA y con posibilidad de localización mediante un sistema de ultrasonidos. Este robot es capaz de realizar un mapa en formato de rejilla. Es sobre este paradigma de rejilla que funciona el algoritmo desarrollado en este trabajo. Junto a esta restricción en el diseño del mapa, se ha incluido una condición extra, la restricción de recursos que implica el uso de la FPGA. Esta limitación se traduce en una menor capacidad de cómputo y capacidad de memoria (en comparación a trabajos existentes que utilizan un ordenador para resolver la navegación). El estado del arte plantea dos alternativas para la resolución de este problema, el uso de algoritmos de navegación sobre grafos (Dijkstra y A*) y los algoritmos de navegación orientados a sortear obstáculos locales (Distbug). Frente a estas dos aproximaciones se plantea el nuevo algoritmo desarrollado en este trabajo: HCTNav. Este algoritmo se ha desarrollado con el objetivo de reducir el tamaño de memoria requerido por Dijkstra y a obtener una solución con menor distancia recorrida en comparación con Distbug. Para llevar a cabo la implementación del algoritmo ha sido necesario un desarrollo de un entorno de trabajo adecuado. El inicio de este trabajo consistió en la implementación de un entorno de simulación donde poder aplicar y probar el algoritmo desarrollado. Este entorno fue desarrollado con una interfaz gráfica que ha permitido la depuración y redefinición del algoritmo HCTNav. El algoritmo ha sido implementado en ANSI C junto a versiones de los algoritmos antes mencionados: Dijkstra, A* y Distbug. Esta implementación ha permitido la comparación del comportamiento de todos estos algoritmos. La elección del lenguaje ha sido condicionada por el lenguaje que es capaz de interpretar el microprocesador embebido en la FPGA. Las pruebas se han realizado sobre un banco de treinta mapas desarrollados por distintos integrantes del grupo de investigación. Estos mapas de tienen unas dimensiones reducidas (15 columnas y 10 filas). Además, se ha utilizado un subconjunto de estos mapas para crear un test de mapas ampliados. Esta ampliación ha sido automática siguiendo dos líneas, el escalado y la replicación. Este set de mapas contiene versiones ampliadas en factores: 2, 4, 8, 16 y 32. Los resultados obtenidos muestran que el tiempo de ejecución del algoritmo HCTNav es equivalente al tiempo de ejecución de Dijkstra o A*. Siendo del orden de nanosegundos para las versiones pequeñas de los mapas y del orden de un segundo para las versiones ampliadas con un factor de 32. En ambos casos, estos tiempos son despreciables en comparación con el tiempo de desplazamiento del robot (decenas de segundos). En la comparación de recursos de memoria, HCTNav requiere la mitad de memoria en el caso de los mapas pequeños. En el caso de los mapas con máxima ampliación, HCTNav requiere diez veces menos memoria que sus competidores. En cuanto a la mejora del camino óptimo, HCTNav obtiene de media caminos con una longitud significativamente menor que los resultados que obtiene Distbug.