Navegación global utilizando grafo de visibilidad
From Robotica
PFC de Alejandro López Romero.
- Codigo
- Memoria (PDF)
- Transparencias
- Video1, Video2
Trabajando con el simulador del robot Pioneer, partimos de un mapa del mundo en el que se moverá el robot, expresado en forma de segmentos rectos. El robot debe ser capaz de planificar una ruta hacia un punto dado en el mapa, para ello construirá y utilizará un grafo de visibilidad de ese entorno. El método desarrollado de construcción consiste en dos fases :
- Agrandar los segmentos de obstáculo a una distancia mayor que el radio del robot para evitar colisionar con las paredes. En la figura se muestran estas paredes u obstáculos como segmentos rojos y la zona de seguridad que los rodea de color rosa.
- Se unen entre sí todos los vértices de la zona de seguridad siempre y cuando el segmento creado no atraviese ningún segmento de obstáculo o de seguridad. Los segmentos generados (en verde en la figura) serán los posibles caminos por los que pueda moverse el Pioneer libremente sin chocar. Es el llamado grafo de visibilidad simple.
Se integra una mejora a este último método teniendo en cuenta que los puntos de intersección entre los segmentos de seguridad pueden ser nodos válidos del grafo. Añadiendo esta condición ampliamos el alcance del anterior método y generamos el grafo de visibilidad mejorado.
Una tercera opción incluida en el sistema es generar los nodos del grafo aleatoriamente sobre los límites del mapa. Esto nos da por una parte una distribución homogénea de nodos y cierta velocidad en la ejecución del algoritmo. Por otro lado no nos garantiza una planificación óptima de la ruta ya que a veces se realizarán desvios y giros teóricamente innecesarios.
La utilización del grafo generado permite trazar una ruta entre la posición actual del robot y un destino cualquiera. Esta ruta se calcula por el momento mediante dos algoritmos : Dijkstra y A* ( A estrella ). El primero calcula todos los caminos posibles desde el robot al resto de los nodos, eligiendo finalmente la ruta que pase por el nodo más cercano a la meta. El algoritmo A* obtiene exclusivamente la ruta desde el origen hasta la meta, y lo hace de manera más rápida que Dijkstra, aunque no garantiza el camino mínimo ya que contiene una componente heurística. Este algoritmo es uno de los más utilizados en el encaminamiento de routers en las redes de datos y videojuegos.
