Algoritmos de navegación

Se define navegación como la metodología (o arte) que permite guiar el curso de un robot móvil a través de un entorno con obstáculos. Existen diversos métodos o algoritmos, pero todos ellos poseen en común el afán por llevar el robot a su destino de forma segura y práctica dependiendo de la finalidad última del robot.

¿La navegación en robots móviles?

Las tareas involucradas en la navegación de un robot móvil son: la percepción del entorno a través de sus sensores, de modo que le permita crear una abstracción el mundo; la planificación de una trayectoria libre de obstáculos, para alcanzar el punto destino seleccionado; y el guiado del vehículo a través de la referencia construida.

En consecuencia con lo anterior, el robot móvil debe poseer una arquitectura que coordine los distintos elementos de a bordo (sistema sensorial, control de movimiento y operación) de forma correcta y eficaz para la realización de una misión. El diseño de esta arquitectura depende mucho de su aplicación en articular, pero un esquema básico de los principales módulos que la componen y la interacción que existe entre los mismos es el presentado en la figura 1.

Figura 1. Esquema básico de la arquitectura necesaria en un robot móvil para realizar una misión.

Esquemas de navegación en robots móviles: Realizar una tarea de navegación para un robot móvil significa recorrer un camino que lo conduzca desde una posición inicial hasta otra final, pasando por ciertas posiciones intermedias o submetas. El problema de la navegación se divide en las siguientes cuatro etapas:

Percepción del mundo: Mediante el uso de sensores externos, creación de un mapa o modelo del entorno donde se desarrollará la tarea de navegación.
Planificación de la ruta: Crea una secuencia ordenada de objetivos o submetas que deben ser alcanzadas por el vehículo. Esta secuencia se calcula utilizando el modelo o mapa de entorno, la descripción de la tarea que debe realizar y algún tipo de procedimiento estratégico.
Generación del camino: En primer lugar define una función continua que interpola la secuencia de objetivos construida por el planificador. Posteriormente procede a la discretización de la misma a fin de generar el camino.
Seguimiento del camino: Efectúa el desplazamiento del vehículo, según el camino generado mediante el adecuado control de los actuadores del vehículo.

¿Que es un algoritmo?

Un algoritmo es un método eficaz para resolver un problema expresado como una secuencia finita de instrucciones. Los algoritmos son utilizados para el cálculo, procesamiento de datos, y muchos otros campos. Cada algoritmo es una lista de instrucciones bien definidas para completar una tarea. A partir de un estado inicial, las instrucciones que describen un cálculo que procede a través de una serie bien definida de estados sucesivos, con el tiempo terminan en un estado final que termina

Algunos Algoritmos de navegación en robots móviles

Primero miremos la planeación mediante los grafos de visibilidad: Los grafos de visibilidad proporcionan un enfoque geométrico útil para resolver el problema de la planificación. Se supone un entorno bidimensional en el cual los obstáculos se muestran mediante polígonos. Para la generación del grafo este método introduce el concepto de visibilidad, según el cual define dos puntos del entorno como visibles si y solo si se pueden unir mediante una línea que no intercepte ningún obstáculo. Así, si se considera como nodos del grafo de visibilidad la posición inicial, la final y todos los vértices de los obstáculos del entorno, el grafo resulta de la unión mediante arcos de todos aquellos nodos que sean visibles. Ya teniendo el grafo se procede a aplicar algoritmos como los que se muestran a continuación.

El algoritmo de Dijkstra

El algoritmo de Dijkstra es un algoritmo de navegación utilizado en los campos de la robótica, consiste en encontrar el camino más corto, desde un punto de referencia local hasta una meta definida, consiste en tomar el mencionado punto de referencia y vértices aleatorios hasta la meta e ir calculando la distancia hasta cada uno de los vértices e irse recorriéndolos de forma tal de lograr el camino mas corto hasta la meta.

Teniendo una figura o grafo dirigida(o) con N nodos no aislados, sea x el nodo inicial, un vector D de tamaño N guardará al final del algoritmo las distancias desde x al resto de los nodos.

Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.
Sea a = x (tomamos a como nodo actual).
Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos vi.
Si la distancia desde x hasta vi guardada en D es mayor que la distancia desde x hasta a sumada a la distancia desde a hasta vi; esta se sustituye con la segunda nombrada, esto es: si (Di > Da + d(a, vi)) entonces Di = Da + d(a, vi)
Marcamos como completo el nodo a.
Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenando los valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.

Así teniendo a D completamente lleno

Figura 2. Algoritmo de Dijkstra en funcionamiento

El algoritmo de Prim

Aplicado a la robótica y a los algoritmos de navegación el algoritmo de Prim, es un algoritmo que forma recorrer un camino por medio de lo que se conoce en la teoría de grafos como un árbol, un árbol no es mas que la condición que tienen dos vértices (o puntos) mediante un solo camino, asi el objetivo del algoritmo de navegación es llegar al punto que se llama meta por medio del árbol mas pequeño posible, o sea que sus ramas( o uniones entre vértices) tengan la minima distancia posible.
El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik.

Figura 3. Objetivo del algoritmo de Prim