Publication: Aceleración de algoritmos de localización para robots móviles en 3D mediante CUDA®
Loading...
Identifiers
Publication date
2014-11
Defense date
2014-11-21
Authors
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Impact
Export
Abstract
La localización de un robot es uno de los problemas a los que se enfrenta actualmente la robótica moderna. El algoritmo desarrollado en la Universidad Carlos III, llamado RELF-3D, intenta resolver este problema, centrándose en hacerlo cuando no hay conocimiento acerca de la posición de partida. El robot MANFRED-V2 está programado con él para encontrar su posición haciendo comparaciones con un mapa precargado de uno de los edificios del campus. Mide las distancias a las diferentes paredes que hay en su posición actual con varios escáneres láser, a continuación, se ejecuta el algoritmo RELF-3D. Este algoritmo se basa en la adaptación genética, creando poblaciones aleatorias que representan posiciones dentro del mapa y haciendo que evolucionen a una solución óptima.
Sin embargo, el algoritmo necesita hacer varios cálculos para calcular las distancias, evaluar sus errores y por lo tanto se requiere una gran cantidad de tiempo.
Este proyecto ha sido propuesto para encontrar una manera de resolver este problema. El objetivo es llegar a un tiempo de cálculo aceptable utilizando la computación paralela. Por lo tanto un lenguaje de programación debe ser elegido. La decisión fue utilizar las bibliotecas CUDA® de NVIDIA ™ para el lenguaje C, debido a su proximidad con el lenguaje C original y la disponibilidad de las arquitecturas CUDA® en la casi totalidad de las GPUs de esta compañía por un precio razonable.
El resultado obtenido superará expectativas del lector debido a la cantidad de tiempo ahorrado mediante el uso de suficientes hilos paralelos para resolver todas las posibles distancias medidas al mismo tiempo.
Varias propuestas para desarrollos futuros del algoritmo RELF-3D se hacen después de las conclusiones, así como algunas proposiciones de mejora del hardware.
Locating a robot is one of the main problems faced nowadays by modern robotics. The algorithm developed in the Carlos III University called RELF-3D tries to solve this problem, focusing on doing it when there is no knowledge about the starting position. The robot MANFRED-V2 is programmed with it to find its position by making comparisons with a preloaded map of one of the buildings of the campus. The laser scan is used to measure distances to the walls, and then the algorithm RELF-3D is executed. This algorithm is based on adaptive genetics, creating randomized populations that represent positions within the map and evolving them to an optimal solution. However, the algorithm needs to make several computations to calculate the distances, evaluate its errors and hence a lot of time is required. This project has been proposed to find out a way to solve this problem. The goal is to reach an acceptable computational time using parallel computing. Therefore a programming language must be chosen. The decision was to use the CUDA® libraries from NVIDIA™ for the C language, because of its proximity to the original C language and the availability of the CUDA® architectures in almost all of this company GPUs for a reasonable price. The result obtained will surpass the reader’s expectative because of the amount of time saved by using enough parallel threads to solve all the possible distances measured at the same time. A few proposals for future developments of the RELF-3D algorithm are made after the conclusions, as well as some hardware improvements.
Locating a robot is one of the main problems faced nowadays by modern robotics. The algorithm developed in the Carlos III University called RELF-3D tries to solve this problem, focusing on doing it when there is no knowledge about the starting position. The robot MANFRED-V2 is programmed with it to find its position by making comparisons with a preloaded map of one of the buildings of the campus. The laser scan is used to measure distances to the walls, and then the algorithm RELF-3D is executed. This algorithm is based on adaptive genetics, creating randomized populations that represent positions within the map and evolving them to an optimal solution. However, the algorithm needs to make several computations to calculate the distances, evaluate its errors and hence a lot of time is required. This project has been proposed to find out a way to solve this problem. The goal is to reach an acceptable computational time using parallel computing. Therefore a programming language must be chosen. The decision was to use the CUDA® libraries from NVIDIA™ for the C language, because of its proximity to the original C language and the availability of the CUDA® architectures in almost all of this company GPUs for a reasonable price. The result obtained will surpass the reader’s expectative because of the amount of time saved by using enough parallel threads to solve all the possible distances measured at the same time. A few proposals for future developments of the RELF-3D algorithm are made after the conclusions, as well as some hardware improvements.
Description
Keywords
Algoritmos genéticos, Robótica, Visión artificial, Localización RELF-3D, Evolución diferencial, Computer Unified Device Architecture (CUDA)