[PDF] Redalyc.Búsqueda de la ruta óptima mediante los algoritmos

View - Download Redalyc.Búsqueda de la ruta óptima mediante los algoritmos

Previous PDF

Next PDF

Scientia Et Technica

ISSN:

0122-1701

scientia@utp.edu.co

Universidad Tecnológica de Pereira

Colombia

Guzmán Luna, Jaime Alberto; Arango Sánchez, Rafael Esteban; Jiménez Pinzón, Leidy Diana

Búsqueda de la ruta óptima mediante los algoritmos: genético y dijkstra utilizando mapas de visibilidad

Scientia Et Technica,

vol. XVII, núm. 51, agosto , 2012 , pp. 107-112

Universidad Tecnológica de Pereira

Pereira, Colombia

Disponible en: http://www.redalyc.org/articulo.oa?id=84923910016

Sistema de Información Científica

Red de Revistas Científicas de América Latina, el Caribe, España y Portugal Proyecto académico sin fines de lucro, desarrollado bajo la iniciativa de acceso abierto

Scientia et Technica Año XVII, No 51, Agosto de 2012. Universidad Tecnológica de Pereira. ISSN 0122-1701 107

Fecha de Recepción: 26 de enero de 2012

Fecha de Aceptación: 28 de Agosto de 2012 Búsqueda de la ruta óptima mediante los algoritmos: genético y dijkstra utilizando mapas de visibilidad Finding path through the algorithms: genetic and dijkstra using maps of visibility. Jaime Alberto Guzmán Luna, Rafael Esteban Arango Sánchez, Leidy Diana Jiménez Pinzón

Escuela de Ingeniería de Sistemas e Informática, Universidad Nacional de Colombia, Medellín, Colombia

jaguzman@unal.edu.co raerangosa@unal.edu.co ldjimenezp@unal.edu.co Resumen - Este artículo presenta el estudio de la generación de trayectorias entre dos puntos y una cantidad cualquiera de obstáculos entre ellos mediante el mapa de visibilidad teniendo en cuenta la geometría del robot, de igual manera en éste se plantea la comparación entre el algoritmo genético y el algoritmo Dijkstra al encontrar la ruta óptima entre las trayectorias ya generadas con el mapa de visibilidad. El algoritmo es implementado en Java, en Java Lejos versión 0.9 se desarrolla un algoritmo que envía al robot los puntos de navegación mediante bluetooth corrigiendo el error de su trayectoria y sus giros mediante el uso de los sensores como el compás, el tacómetro y el concepto de la odometría; las pruebas para obtener los resultados son aplicadas sobre el robot LEGO NXT 2.0. Palabras clave - Mapas de Visibilidad, Algoritmo Genético,

Algoritmo Dijkstra, Java LeJos.

Abstract - This article presents the study of the generation of paths between two points and a quantity any of obstacles between them through the map of visibility using the geometry of the robot, equally in this can find the comparison between the genetic algorithm and the algorithm Dijkstra finding optimal path between the paths already generated with the map of visibility. The algorithm is implemented in Java, in Java LeJos version 0.9 develops an algorithm that sends to the robot the points of navigation through bluetooth correcting the mistake of his path and his drafts through the use of the sensors as the compass, the tachometer and the concept of the odometry; the tests to obtain the results are applied on the robot LEGO NXT 2.0. Key Word - Maps of Visibility, Genetic Algorithm, Algorithm

Dijkstra, Java LeJos.

I. INTRODUCCIÓN

La navegación se define como la metodología que permite guiar el curso de un robot móvil desde un punto inicial

hasta un punto final a través de un entorno que contiene obstáculos mediante la generación de diferentes trayectorias, las

cuales se construyen mediante la unión de tres caminos: uno que conecta el punto inicial con el primer obstáculo, otro que es el que recorre los obstáculos entre si y el último es el que se une desde allí hasta el punto final, el objetivo siempre es llevar a su destino de forma óptima el robot teniendo en cuenta sus dimensiones para dejar de considerarlo como un punto en el espacio y tomarlo como un objeto que tiene unas medidas específicas y ocupa un volumen en el espacio de navegación pero para llevar esto a cabo es importante el estudio de la percepción del mundo, la planificación de la ruta, la generación del camino y el seguimiento del mismo; aspectos que se deben tener en cuenta en el desarrollo del proyecto y aunque son analizados independientemente se relacionan entre sí ya que demuestran continuidad, de allí la importancia de implementar su solución en el orden respectivo[1]. En este artículo se presenta el estudio de la generación de trayectorias, existen diferentes métodos que ya han sido implementados y son eficientes en la planificación de caminos, como por ejemplo, el método de descomposición por celdas o el diagrama de voronoi [2] pero para este proyecto se hará uso del grafo de visibilidad. Para encontrar la ruta óptima a partir de las trayectorias ya existentes se estudian los algoritmos de búsqueda como el algoritmo dijkstra o el algoritmo genético, se presenta la descripción de los algoritmos implementados, se proponen las pruebas para la verificación de los algoritmos y finalmente se presentan las conclusiones del trabajo. Actualmente existen investigaciones que implementan el algoritmo de búsqueda Dijkstra con el diagrama de Voronoi [3], con el mapa de visibilidad [4], con la descomposición por celdas [5] o el algoritmo genético con el mapa de voronoi [6].

II. CONTENIDO

A. Descripción del robot lego NXT. El robot móvil utilizado para realizar las pruebas de navegación es el robot Lego Mindstorms NXT 2.0, puede ser programado en diferentes lenguajes pero para este proyecto se usó Java Lejos. El robot Scientia et Technica Año XVII, No 51, Agosto de 2012. Universidad Tecnológica de Pereira. 108
recibe desde el ordenador y por medio de conexión bluetooth los ángulos y las distancias que debe navegar en el mundo real, estos datos son los generados en la aplicación de java con el nombre de "Plan" y son los resultados arrojados por los algoritmos de búsqueda propuestos para estudiar. Tal como se muestra en la figura 1a, el robot tiene el sensor de compás que le ayuda a minimizar el error en sus giros; dos servomotores, uno para cada llanta haciendo sus movimientos totalmente independientes y el brick, donde se descarga el proyecto de Java Lejos para poner en funcionamiento el robot. En la parte trasera tiene una rueda loca la cual fue construida con una esfera que pertenece al kit de Lego (ver figura 1b), con este mecanismo los movimientos del robot son más fluidos y precisos a comparación de la rueda dequotesdbs_dbs2.pdfusesText_3

[PDF] aliexpress france avis

[PDF] alkyl and aryl halides notes pdf

[PDF] alkyl halides notes pdf

[PDF] all google sites list

[PDF] all html5 tags list with examples pdf

[PDF] all police codes mn

[PDF] all the methods in the interface are internally

[PDF] allan_and_barbara_pease_ _body_language_the_definitive_book.pdf

[PDF] allemand langage familier

[PDF] aller + infinitif exercices

[PDF] aller retour paris ajaccio air france

[PDF] aller retour paris nice avion

[PDF] alliance gradebook pinnacle

[PDF] allocate memory for struct in c

[PDF] alloprof fonction polynomiale du second degré