Publication: Algoritmos de planificación de robots usando fast marching
Loading...
Identifiers
Publication date
2011
Defense date
2011-02-10
Authors
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Impact
Export
Abstract
El objeto de este proyecto es conseguir que el robot LEGO NXT Mindstorm siga lo más fielmente posible una ruta que le es planificada mediante un algoritmo planificador (ya desarrollado por el Departamento de Sistemas y Automática de la Universidad Carlos III) basado en la metodología Fast Marching (marcha rápida) Para el seguimiento de la ruta por el robot vamos a necesitar por una parte un software desarrollado mediante la aplicación informática Matlab (2007b) y un sistema de relocalización mediante el cual podemos conocer con una gran precisión donde se encuentra el robot dentro del mapa que hemos cargado. El sistema de relocalización se basa en el uso del algoritmo “Differential Evolution” ya implementado en un proyecto anterior. Se trata de una especie de algoritmo genético mejorado, se parte de una población inicial en la que se introduce una perturbación (diferencia de dos vectores) y dicha perturbación se suma a un tercer vector para obtener un vector de prueba. Cada uno de los vectores correspondientes a los puntos de la población inicial, competirá con el vector de prueba que tenga su mismo índice pasando a la siguiente generación los individuos más aptos. Por cada una de las sucesivas generaciones se repetirá el proceso de introducción de perturbación, crear vector de prueba y el proceso de competición o selección de los individuos que habrán de pasar a la siguiente generación. Cuando el algoritmo ha convergido totalmente (tras el paso de sucesivas generaciones) obtenemos la solución con mejor valor de la función de Fitness o función de salud. La función del algoritmo “Differential Evolution” es obtener la mejor función de salud (Fitness) o minimizar la función de coste (Cost). En lo referente a este proyecto, el algoritmo “Differential evolution” se encarga de minimizar la diferencia entre los vectores V0 y V1, siendo V0 el vector que contiene las mediciones realizadas por el sensor de ultrasonidos del entorno que rodea al robot y V1 el vector que contiene las medidas estimadas que se obtendrían si el robot se encontrara donde nosotros creemos que está. El cuadrado de la diferencia entre V0 y V1 se denomina error cuadrático. El sistema de relocalización nos permite hacer las correcciones necesarias en la ruta para que solventando el inconveniente de la acumulación de errores en un seguimiento de ruta odométrico se llegue hasta el punto de destino convenido. __________________________________________________________________________________________________
The purpose of this proyect Is to make the LEGO NXT Mindstorm robot follow as closely as possible a route that is planned by a scheduler algorithm (already developed by the Department of Systems and Automation, at Carlos III University in Madrid) based on the Fast Marching method (quick start). In order for the robot to monitor the route, we will need the following. On the one hand, we will need software developed using the Matlab IT (information Technology) application (2007b). On the other hand, we will need a relocation system to achieve the maximum precision about it’s location in the map. The relocation system is based on the use of the algorithm “Differential Evolution”. This has been already implemented in a previous draft. It is a kind of improved genetic algorithm. It starts from an initial population in which a disturbance (difference between two vectors) is introduced. This disturbance is added to a third vector in order to get a test vector. Each one of the vectors corresponding to the initial population points will compete with the test vector with the same index. The most skilled individuals will move into the next generation. When the algorithm has completely converged (after the passage of consecutive generations) we can get the best value solution of the fitness function (or health function). The function of the algorithm “Differential Evolution” is to get the best health function (Fitness) or to minimize the cost function (cost). With regard to this proyect, the algorithm “Differential Evolution” makes sure the minimization of the difference between vectors V0 and V1. Vector V0 contains the measurements of the robot environment, taken by the ultrasonic sensor. Vector V1 contains the estimated measurements if the robot were located where we think it is. The difference between V0 and V1 squared is called the quadratic error. The relocation system allows us to make the necessary corrections to the route so that it is possible to get to the agreed point of destination by solving the problem of error accumulation in an odometric route tracking.
The purpose of this proyect Is to make the LEGO NXT Mindstorm robot follow as closely as possible a route that is planned by a scheduler algorithm (already developed by the Department of Systems and Automation, at Carlos III University in Madrid) based on the Fast Marching method (quick start). In order for the robot to monitor the route, we will need the following. On the one hand, we will need software developed using the Matlab IT (information Technology) application (2007b). On the other hand, we will need a relocation system to achieve the maximum precision about it’s location in the map. The relocation system is based on the use of the algorithm “Differential Evolution”. This has been already implemented in a previous draft. It is a kind of improved genetic algorithm. It starts from an initial population in which a disturbance (difference between two vectors) is introduced. This disturbance is added to a third vector in order to get a test vector. Each one of the vectors corresponding to the initial population points will compete with the test vector with the same index. The most skilled individuals will move into the next generation. When the algorithm has completely converged (after the passage of consecutive generations) we can get the best value solution of the fitness function (or health function). The function of the algorithm “Differential Evolution” is to get the best health function (Fitness) or to minimize the cost function (cost). With regard to this proyect, the algorithm “Differential Evolution” makes sure the minimization of the difference between vectors V0 and V1. Vector V0 contains the measurements of the robot environment, taken by the ultrasonic sensor. Vector V1 contains the estimated measurements if the robot were located where we think it is. The difference between V0 and V1 squared is called the quadratic error. The relocation system allows us to make the necessary corrections to the route so that it is possible to get to the agreed point of destination by solving the problem of error accumulation in an odometric route tracking.
Description
Keywords
Robótica, Algoritmos genéticos, Robots móviles