Establecimiento de tecnologías aplicadas al análisis de las trayectorias de un robot móvil en un espacio con obstáculos

Las investigaciones realizadas en el presente trabajo, fueron hechas a partir del desarrollo de los alumnos y del cuerpo docente en la catedra de Tecnologias de las Redes Neuronales Artificiales, de la Universidad Tecnologica Nacional, Facultad Regional del Neuquen. En el campo de la robótica, se realizan las experiencias en base a ambientes de desarrollo con células de trabajo fijas en sus posiciones para que el robot desarrolle sus tareas, tal es el caso del robot ensamblador o soldador en una planta.

Tan significativos fueron los avances tecnológicos en los diferentes ambientes industriales, que constituyeron una de las razones principales para dotar a los sistemas de robots de una adecuada capacidad de desplazamiento, más allá de las prestaciones que realizaban en sus celdas de trabajo. Es entonces cuando esta disciplina dio en llamarse “robótica móvil” y constituye uno de los mayores desafíos que aborda la comunidad científica, que trabaja dentro del rico y extenso campo de la robótica.

Cabe señalar, que las sucesivas investigaciones desarrolladas intentaron proporcionar a estos sistemas un nivel de autonomía suficiente, que le permitan navegar en su ambiente de operación y reaccionar ante situaciones que no han sido consideradas en su programa¹.

La navegación permite guiar el curso de un robot móvil mediante un entorno en el que se encuentran obstáculos. Se conocen diferentes esquemas para llevar a cabo esta tarea, pero todos ellos tienen el objetivo común de dirigir el vehículo hacia su destino de la manera más segura y eficiente posible. La capacidad de reacción que pueda poseer el robot cuando se encuentra ante situaciones inesperadas, debe constituir su cualidad más distintiva para desenvolverse eficazmente en el entorno donde éste deba operar, lo cual indica el grado de autonomía.

En la primera etapa de este trabajo se presentan los resultados obtenidos mediante la aplicación de técnicas de navegación robótica basadas en redes neuronales con aprendizaje supervisado de tipo Backpropagation, representativo de las características más potentes del paradigma reactivo concerniente a la navegación autónoma de robots ^2,3. Este trabajo se realiza en un marco un poco más amplio considerado una evolución del paradigma reactivo, que se denomina “Aproximación Basada en Comportamientos”⁴. Asi, los comportamientos describen la forma en que se reacciona ante un determinado estado de sensores y donde las actuaciones se determinan de manera más elaborada, realizando cálculos a los efectos de decidir qué acción se debe realizar.

En la segunda etapa de este trabajo se hace uso de los Algoritmos de Búsqueda, los que constituyen una de las tecnologías más importantes de la IA, cuyo objetivo principal consiste en hallar una solución válida dentro del espacio de estados. Entre otras técnicas que se pueden implementar con estos algoritmos se conocen las de búsqueda no informada y búsqueda con información. La primera debe su denominación a que el problema que se pretende resolver no proporciona ninguna información adicional que sirva de soporte para encontrar una solución de forma más rápida. Se muestra un experimento relacionado con la Técnica de búsqueda en profundidad, cuyo objetivo central es encontrar una ruta entre el nodo raíz y el nodo objetivo.

A efectos de estudiar la conducta de un robot, se propone como arquitectura una red neuronal que consta de una capa de entrada, una capa oculta y una capa de salida⁵. De esta manera, se intenta que el robot pueda realizar trayectorias de mayor complejidad que para las que fue entrenado.

Durante el proceso de entrenamiento, el vehículo robótico recibe información del ambiente en el cual navega; la cual es volcada en un mapa sensor – motor, que permite esquematizar tal ambiente con obstáculos definidos, y a través de un software diseñado a tal efecto, se simula su interacción luego de su entrenamiento para evaluar su performance bajo las premisas del paradigma reactivo. Este mapa sensor-motor se traduce en una matriz con la descripción sensorial en cada posición de la grilla, que representa el entorno y los posibles movimientos en respuesta a los estímulos sensados, conforme a las políticas de proximidad y de movimiento⁶.

Considerando el mapa sensor-motor y tras el entrenamiento del robot con la tecnología inteligente de la red neuronal escogida se evalúa el robot para diferentes ambientes de operación. La combinación de rutas definidas para distintas configuraciones, constituyen las diversas conductas de navegación que exhibe el robot⁷.

El paradigma de red utilizado se describe en la figura 1, mientras que las figura 2 y 3 muestran el esquema de la organización del ambiente donde navega el robot, consistente en una grilla cuyas coordenadas (x, y) se encuadran dentro de un eje cartesiano con dos trayectorias diferentes. Este entorno visual brinda la información referida a la localización del robot (proporcionada por las coordenadas X e Y, que en este caso corresponden a 0 según X y a 6 según Y), su orientación (dada por Norte, Sur, Este y Oeste), el ambiente propiamente dicho, con la ubicación de sus obstáculos (casilleros con cruces) y las opciones para entrenar la red, reiniciar el proceso cuando sea necesario y simular los pasos de la trayectoria seguida por el robot. Asimismo, estas últimas dos figuras muestran tanto una trayectoria exitosa y una colisión para el mismo entorno desde otro origen⁸.

En fase de operación, se procede a presentarle al robot otras trayectorias diferentes a las aprendidas para evaluar su performance.

Recordar que las experiencias fueron realizadas en conjunto con el cuerpo docente y alumnos de Redes Neuronales Artificiales de la UTN, FRN.

Figura 1
Arquitectura de red de tipo Backpropagation

Figura 2
Trayectoria exitosa de un robot entrenado con RNA

El uso de grafos de navegación permite trabajar con una abstracción del entorno real y son estos usados en la navegación robótica cuando se conocen previamente las características del ambiente.

El entorno se expresa en una grilla donde los casilleros oscuros representan los obstáculos y los casilleros libres indican el espacio transitable, tal como se observa en la figura 4. En estos espacios libres se colocan nodos o vértices nombrados con letras mayúsculas, como se muestra en la figura 5, para luego trazar las aristas posibles que los conectan, figura 6.

Figura 3
Trayectoria no exitosa partiendo desde un lugar distinto al aprendido

Con la definición de estos elementos, se puede entonces comenzar con la presentación del modelo de algoritmo propuesto.

Figura 4
Entorno propuesto

Figura 5
Distribución de los nodos

Figura 6
Diseño del grafo en el entorno

Es importante señalar que este algoritmo trabaja con cierta información. Es decir, el algoritmo aplicado conocerá cuál es el nodo objetivo al que se desea llegar y también puede guardar información sobre cuáles nodos y aristas se han visitado previamente.

El algoritmo Depth First Search (DFS) o algoritmo de búsqueda en profundidad, es el algoritmo que se analiza. La búsqueda que realiza este algoritmo consiste en el descenso hasta el máximo nivel de profundidad de la rama llegando hasta al nodo más profundo y luego continuar con la siguiente rama. Este algoritmo se inicia en un nodo del grafo, considerado nodo raíz. A partir de ese punto, observa cuáles son los nodos hijo y visita al primero. De este nuevo nodo, ve cuáles son los hijos y visita al primero que encuentra. El proceso sigue hasta hallar a una hoja, es decir, un nodo que no tenga hijos o a uno que esté conectado a nodos que ya se hayan visitado previamente. En ese momento, regresa al nodo padre inmediato y visita al siguiente hijo del nodo. El proceso continuo hasta que se encuentra el nodo objetivo o se han visitado todos los nodos del grafo. Esto puede observarse detenidamente en el diagrama de flujo que se despliega en la figura 7.

Este algoritmo expresado en el pseudocódigo descripto en la figura 8 garantiza encontrar una ruta entre el nodo raíz y el objetivo, siempre y cuando el nodo objetivo exista y esté conectado al grafo.

Desde el punto de vista de la implementación, la búsqueda en profundidad utiliza una pila LIFO (Last In First Out). Una pila LIFO tiene dos operaciones: una para introducir un dato en la pila y otra para extraer un dato de la pila. El dato que se extrae de la pila es el último que se introdujo.

Por todo lo expuesto precedentemente, el ejemplo propuesto tiene como objetivo que el robot parta del nodo A y llegue al nodo R, es decir que encuentre una ruta que pueda seguir. Paro ello es necesario contar con una “pila o stack” que sea capaz de guardar las aristas que faltan por visitar y además, un arreglo en el que se registren los nodos y su nodo padre. Es importante al iniciar este algoritmo, hacer una arista del nodo raíz a sí mismo para poder iniciar y colocarlo en la pila.

Figura 7
Diseño del grafo en el entorno

Figura 8
Pseudocódigo del Algoritmo de Búsqueda en Profundidad

Considerando que el paradigma es netamente reactivo, basado en la filosofía de estímulo-reacción, los resultados obtenidos por la aplicación de la tecnología de las RNA de tipo Backpropagation en función del entorno, del tipo de robot y su interacción, ha evidenciado las diferentes conductas del robot. Las observaciones realizadas para distintas orientaciones, distintos puntos de partidas, entre otras, deja en evidencia que el modelo resulta suficiente para algunos casos y limitada para otros. Asimismo, cuando el mundo adquiere mayor complejidad, o bien, cuando se hace partir al robot desde otro origen muy diferente al punto de origen con el cual se ha entrenado, éste adquiere conductas que le permiten resolver el problema a veces acertadamente y otras terminan en una colisión o en el ingreso a un bucle del que no logra salir.

Si bien el tiempo de ejecución es más rápido, puesto que actúa en función de la información que le proveen los sensores, no siempre resulta esto eficiente, puesto que se ha observado que eventualmente no logra el objetivo, aunque actúe con mayor velocidad.

Los experimentos realizados con el algoritmo de búsqueda garantizan la existencia de una ruta siempre y cuando el nodo objetivo exista y esté conectado al grafo.

El presente trabajo fue exitoso a modo de ejemplo en la catedra ya mencionada. Por lo que podemos decir que, el aspecto pedagógico fue fundamental para su desarrollo.

De acuerdo a las investigaciones y experimentos realizados junto a los alumnos, se puede concluir que el robot se desempeña bien dependiendo del lugar de salida e intentando siempre hallar la trayectoria de entrenamiento.

Cabe señalar que el patrón de entrenamiento ha sido suficiente para algunas trayectorias, aunque en ciertos casos dicho patrón no resulta ser representativo del entorno en el cual opera el robot, ya que la mayoría de las salidas de la red correspondientes al movimiento de los motores del robot, es avanzar y por ese motivo es que choca partiendo desde otras posiciones. O bien, ingresa en un bucle sin poder resolver esa situación, quedando inmóvil.

A efectos de disminuir este problema, se aumenta el número de patrones de entrenamiento utilizando varias trayectorias o más largas, vigilando siempre la convergencia de la red para obtener mayor convergencia para los patrones de entrenamiento y máxima generalización, para las nuevas posibles situaciones.

En síntesis, se asume que el uso de las RNA como técnica de navegación de características reactivas proporciona resultados satisfactorios para ciertas trayectorias en la fase de operación, tanto más en la medida que estas trayectorias presenten mayor similitud con las que desarrolló en la fase de entrenamiento; así es que se tendrá por caso, que el robot buscará girar más para el lado que lo hace en la trayectoria de entrenamiento que para el otro. A medida que las trayectorias que se le proponen al robot son tanto más complejas que la que este entrenó, este paradigma exhibe sus limitaciones haciendo que la red no converja y se produzcan situaciones de colisión o bucles en el ambiente de navegación. En otros términos, se produce una incorrecta generalización de la red neuronal para las nuevas situaciones que debe afrontar el robot, las cuales no se encontraban presentes en las trayectorias de entrenamiento.

La idea que subyace detrás de este objetivo central, es que dichas mejoras puedan verse reflejadas en términos de evitación de obstáculos, velocidad de respuesta, optimización de las trayectorias y logro de los objetivos⁴.

Por todo lo expuesto precedentemente cabe considerar la consiguiente investigación sobre el objetivo de mejorar el desempeño del robot en lo que se refiere a sus conductas de navegación.

Complementando el concepto expresado en el punto anterior, considerar la aplicación de técnicas de razonamiento de alto nivel de tipo deliberativas (aprendizaje automático y planificación autónoma de tareas entre otras) como complemento de las técnicas reactivas; las cuales, si bien son de menor velocidad de reacción que estas, también le permiten al robot afrontar requerimientos de desempeño más complejos.

En este sentido, se propone como futura línea de investigación el análisis de la performance del robot en ambientes estructurados de mayor complejidad como así también su desempeño en ambientes de operación de carácter dinámico, en los cuales los obstáculos pueden cambiar de posición mientras el robot realiza su tarea.

Asimismo, y dado el objetivo planteado por los autores, se considera la aplicación de algoritmos de búsqueda más eficientes como nuevas técnicas para la resolución de este caso de estudio. Esto es posible, pues el robot se desempeña en un ambiente estructurado, es decir invariante en el tiempo. Con lo cual, y bajo estas circunstancias se plantean alternativas como algoritmos de búsqueda con costos, como posibles tópicos de análisis, como así también el abordaje de algoritmos de búsqueda informada, tales como el Algoritmo de Dijstra y el Algoritmo A*.

Las futuras líneas de investigación ya mencionadas, serán implementadas en el siguiente cuatrimestre, por los alumnos Maximiliano Leon y Juan Briones, junto al equipo docente de la facultad.