Práctica 4: Navegación Global

Published in

PRÁCTICAS ROBÓTICA MÓVIL

5 min readJan 8, 2021

Descripción

La intención de esta práctica es conseguir que un taxi navegue por el mapa de un punto a otro utilizando un algoritmo de navegación global.

Haremos uso del algoritmo Gradient Path Planning (GPP).
El funcionamiento principal será planificar la ruta e intentar seguir lo mejor posible. Para planificar la ruta primero hará uso del algoritmo para crear un mapa el cual irá avanzando con forma de onda e ira asignando valores mayores según vaya aumentando. Después calculara la ruta por objetivos siguiendo los valores menores y seguirá esta.

Como actuadores tendremos las ruedas del robot las cuales se podrán mover de forma linear y angular para avanzar y girar la aspiradora.
Como sensores disponemos de un sensor de posición que nos dirá la posición x e y del robot en el mapa y también su orientación respecto a este.

Diferenciaré el software en 4 partes para poder explicar todo de una forma mas precisa.

Lo primero que hay que hacer es crear un mapa el cual empieza a crearse desde el destino y finalizará al llegar a la posición inicial del coche. Para ello iremos creando el mapa avanzando en forma de onda.
La forma de avanzar seguirá una mecánica muy sencilla: Posición inicial 0, me muevo hacia arriba, izquierda, derecha y abajo y aumento +1 su valor. Después me muevo hacia sus cuatro diagonales y aumento +1.4 su valor. Con esto he hecho que la posición inicial se haya movido hacia sus 8 direcciones, es decir, que el padre ha tenido 8 hijos.
Hecho esto haremos que cada hijo tenga otros 8 hijos en los que tendrán el valor del padre +1 o +1.4 en función de la dirección a la que se mueva. Así conseguiremos expandirnos en forma de onda por todo el mapa.
Para no repetir lugares o que estas tengan un valor mas pequeño (esto sirve para que la ruta sea mas pequeña), compararemos el valor que tiene dicho hijo y haremos que este cambie su valor y se expanda si su valor es mayor al que le vamos a introducir.
Para que no se expanda por los obstáculos, tendremos un array donde se contemplan dichos obstáculos y las rutas. Entonces si el valor es 255, es ruta y si el valor es 0, es obstáculo.
Si hemos seguido todos estos pasos habremos generado un mapa tal que así:

Está parte no es realmente necesaria ya que en el mapa que hemos generado ya tenemos los obstáculos reflejados con un 0 pero con esta penalización lo que haremos es conseguir que el coche no vaya cerca de las paredes y así evitaremos posibles choques.
Para realizar esta penalización es que cada pared refleje un valor (+174 / +168 / +162) en función de lo alejada que este la casilla ( 1 / 2 / 3).
Para ello tendremos que coger nuestro mapa de obstáculos, generarle la penalización y sumar el mapa de obstáculos con penalización a nuestro mapa. Con ello conseguiremos que las casillas cercanas a los obstáculos tengan mayor valor (mas intensidad en la imagen).
También para no repetir penalización iremos comparando sus valores y podremos el mayor. Si una ha sido penalizada con +162 y ahora se quiere penalizar con +174 se usará la nueva penalización (valor sin penalizar + penalización). Si es en caso contrario se mantendrá la que hay.

Tendremos que calcular la ruta desde el coche hasta el destino y la idea principal es ir avanzando casilla a casilla siguiendo la ruta de menor valor.
Para hacer esto iremos mirando la posición actual del robot y observaremos las 8 casillas que le rodean. Estas casillas nos dirán el valor que hemos ido calculando cuando íbamos creando el mapa haciendo una onda.
Teniendo esos 8 valores, nos quedaremos con la casilla que menor valor tenga y avanzaremos a ella. Haremos esto hasta que el valor del menor sea 0, que corresponde con la casilla destino y reflejaremos en el mapa la ruta ideal a seguir.

Una vez hemos completado los pasos anteriores, ejecutaremos nuestro código dándole a Play Code y el coche empezara avanzar.
Para ello seguirá la misma lógica que para el calculo de la ruta pero en este caso en vez de mirar solo a sus 8 vecinos mirara +10 casillas, es decir, mirara a su vecino izquierdo, al izquierdo del izquierdo… y así hasta 10 veces.
Con esto lo que conseguiremos es que calcule un objetivo lejano e intente ir hacia el en vez de calcular el objetivo final.
Ademas no siempre cogerá su casilla final sino que de esas 10 casillas escogerá la de menor valor y la pondrá como objetivo.
Una vez sabe cual es tendremos que convertir este objetivo de absoluto a relativo ya que el absoluto es el objetivo en el mundo pero nosotros nos estamos moviendo por el mapa local del coche.
Para calcular el objetivo relativo tendremos que hacer la diferencia del objetivo y el coche y pasaremos a hacer la transformación.
Por ultimo se le fija una velocidad (en mi caso 4) y hacemos que el coche gire usando su Y relativa.

Este algoritmo (GPP) es bastante bueno para poder realizar una buena navegación global aunque tarda bastante en poder calcular una ruta.