APLICACIÓN DE LA PLANIFICACIÓN ABSTRACTA EN LOS SISTEMAS DE ROBOTS AUTÓNOMOS

1.     Introducción

Los robots móviles autónomos se han estado desarrollando con el objetivo de llevar a cabo tareas complejas en diferentes ambientes, tanto en hábitats humanos como lugares menos amigables, tales como planetas distantes y regiones bajo el agua. 

Para entornos interiores, se proyecta la posibilidad de crear robots móviles autónomos que lleven a cabo tareas solicitadas por los residentes de un edificio o los trabajadores de una planta, tales como: la entrega de correo, guiar visitantes, ir a buscar café, recoger una impresión, o simplemente entregar un mensaje u objeto de un lugar a otro.

En este trabajo se presenta una primera aproximación a la situación planteada donde se centrará la atención en la planificación de tareas, como el nivel superior de abstracción del sistema. Esta abstracción se hace necesaria dado que el uso de planes de muy bajo nivel implicaría ejecutar varios cientos de pasos para resolver cierto problema de navegación donde el espacio de planes de esta magnitud sería tan grande que aun las técnicas de planificación más sofisticadas probablemente no llegarían a una solución en una cantidad razonable de tiempo.

Se presenta a continuación la arquitectura del sistema que integra una capa de planificación de tareas, una capa de planificación de movimientos y por último el ejecutor, que para este caso es un robot lego NXT.

A grandes rasgos el funcionamiento se resume en 4 pasos:

·         El usuario ingresa la descripción del mundo accediendo a la interfaz gráfica
      El usuario especifica los objetivos que debe llevar a cabo el robot

·         El programa genera los archivos Domain.PDDL y Problem.PDDL

·         El planificador arroja una solución, para cumplir los objetivos minimizando la distancia recorrida

·         El programa captura dicha solución y se comunica con la aplicación AppCells para que esta se encargue de ejecutar cada uno de los pasos planteados en el plan.

2.     Descripción del mundo

Se implemento una sección en la que el usuario pueda describir el entorno en el cual trabajará el robot, para ello se consideraron tres aspectos principales:


La inclusión de las áreas.
La inclusión de puntos de conexión entre áreas
La inclusión de los obstáculos al interior de las áreas. 

Un área queda completamente determinada especificando:

• el punto del extremo superior izquierdo y el extremo inferior derecho, en un plano coordenado (x,y)

Para la especificación de los puntos de conexión entre áreas se requiere de:

• la dupla de áreas conectadas
• la ubicación del punto de conexión, en el mismo plano coordenado (x,y)

 

La inclusión de los obstáculos hace parte de la última etapa, donde se hace necesario especificar:

• El área donde está ubicado
• Los nodos, es decir puntos (x,y) que determinan el obstáculo.

3.Creación del Domain.PDDL y  Problem.PDDL

A esta instancia el robot tiene conocimiento del entorno de trabajo pero aún no se asignan las tareas para empezar un proceso de planificación.

El estandar para llevar a cabo dicho procedimiento es dividir la información en dos archivos que recibe el planificador LPG  como entradas, que consisten de un dominio y un problema, en el dominio se establece el conjunto de estados y el conjunto de acciones, por lo que es estático, es decir, no varía con un problema u otro.

Por otro lado el problema hace referencia a un caso específico y en él está contenida toda la información correspondiente al estado inicial y el estado final.

Con el fin de ilustrar la aplicabilidad de la planificación de tareas a un problema de navegación cotidiano se presenta un mapa que puede corresponder a la distribución de un espacio de trabajo, posteriormente la especificación del dominio y el problema  representarán dicho espacio.

Suponga un espacio distribuido como el de la figura, en él se encuentran 6 áreas, con conexiones definidas solo entre algunas de ellas, además de la inclusión de obstáculos en las áreas 1, 3, 5 y 6.

El proceso de composición del dominio no requiere mayores esfuerzos, se definirán los tipos de objetos que se pueden crear que son: sitio y robot, las funciones recorrido, para almacenar la distancia recorrida por el robot y la función distancia, para almacenar el costo del viaje de un área a otra.

Se crearán además predicados para denotar la ubicación actual del robot, marcar un área como visitada y puntualizar  la existencia de una conexión entre áreas. Por último se creará la acción viajar, que le permitirá al robot desplazarse, siempre y cuando se cumplan la restricciones planteadas.

Usando la sintaxis PDDL el archivo Domain tiene la siguiente forma.

Por otro lado la composición del Problem se convierte en la traducción de la información ingresada por el usuario a la sintaxis PDDL, se puede notar que se crearon 6 objetos de tipo sitio y un objeto de tipo robot.

Se procede a definir los términos en los que se encuentra el estado inicial, definiendo: ubicación inicial, conexiones entre áreas y distancia entre las mismas.

Consecuentemente son agregadas las condiciones del estado final, es decir los objetivos, que consisten para este caso en visitar las 6 áreas definidas y por último se establece una métrica, la cual tiene la finalidad de determinar la calidad de un plan respecto a la minimización del recorrido.

Usando la sintaxis PDDL el archivo Problem tiene la forma expuesta en el siguiente codigo

5.     Proceso de planificación Abstracta

El problema descrito anteriormente solo contiene seis salas dado que por cuestiones de espacio tener un problema más grande supone un archivo muy extenso para presentar en este artículo, en la práctica, la utilidad de este proceso muestra sus bondades con una situación de quince áreas o más, donde no es siquiera apreciable una solución observando un mapa o la descripción del mundo.

La ejecución del planificador bajo el Domain y Problem descrito anteriormente presenta una solución como se muestra en la siguiente imagen:

6.     Proceso de planificación de movimientos

Para la ejecución del plan se procede a leer el archivo generado por el planificador, extrayendo la información necesaria para componer un archivo .txt que sea interpretable por la aplicación appcells.

El archivo generado deberá estar compuesto por:

è El punto inicial y el punto final

è Dos puntos que determinan la margen del entorno de trabajo

è Cantidad de obstáculos

è Nodos por cada obstáculo

è Nodos del obstáculo

Como se muestra en la siguiente imagen:  

AppCells comprenderá cada uno de estos archivos como una instrucción y procederá a encontrar la ruta al interior de la sala que le permita viajar del punto inicial al punto final evitando los obstáculos, en la siguiente imagen se presenta el mapa generado, incluidos los obstáculos y los puntos inicial y final.

El programa para cumplir el objetivo, tal y como se plantea en el dibujo es enviado al robot lego NXT usando el protocolo Bluetooth.

Para este propósito, el procedimiento fue crear un “NXT Project” y el main se corre como : “LeJOS NXT program”.

7.     Conclusiones

Los resultados de la planificación para estos entornos ha resultado ser satisfactoria en el sentido de que siempre retornará una solución si esta existe, y el proceso asegura entregar la mejor de ellas para la ejecución.

Dado que el proceso de planificación será ejecutado por un computador y luego son enviadas  instrucciones específicas al robot, el costo computacional puede elevarse conforme crezcan las dimensiones del problema disponiendo solo de las capacidades del computador, que para estas aplicaciones es bastante aceptable.

Aunque la planificación abstracta propone un modelo muy ideal, el planificador de movimientos AppCells debe lidiar con aspectos del entorno que afectan el desempeño, estos son debidamente tomados en consideración por un módulo de corrección de errores, pero su exactitud absoluta no se puede asegurar, por lo que asignarle al robot un plan extenso, supone acumulación de errores y una diferencia considerable entre la trayectoria teórica y la real.

Los avances en el campo de la visión artificial serian de gran utilidad en un sistema autónomo como el que aquí se expone, dado que puede dotar al robot de una visualización del entorno en tiempo real, haciéndolo tolerante a ambientes dinámicos.

Escrito por: Andrés Felipe Gutiérrez Salazar. Grupo SINTELWEB. Universidad Nacional de Colombia Sede Medellín.

Generación de Trayectorias con Mapas de Visibilidad y Comparación entre los Algoritmos genético y Dijkstra en la Búsqueda de la Ruta Óptima

Pruebas de Descomposición Exacta y Adaptativa para la Navegación de Robots Móviles

Se implementó, con ayuda de Jeferson David Ossa, las técnicas de descomposición de celdas exacta y adaptativa (o aproximada) [1][2][3][4][5], para planificación de movimientos en la navegación de robots móviles, que consideran un mundo cerrado, estático y conocido. La siguiente es la arquitectura propuesta.

Los planificadores suelen considerar al robot como un punto, lo cual es irreal. Una de las soluciones (aunque no es exacta), es agrandar todos los obstáculos con respecto al radio del robot.

Teniendo a un robot móvil tipo diferencial con las siguientes dimensiones:

En las pruebas realizadas se compararon las dos técnicas implementadas en dos diferentes escenarios (uno de ellos se puede apreciar en la siguiente figura).

Adicionalmente, en cada escenario, se realizaron dos pruebas distintas, una en la que el robot pudiera pasar exactamente (según la implementación) a través del espacio que dejaban los dos obstáculos entre sí, y otra donde el robot, a pesar de que sí pudiera pasar con cierta configuración, le tocara dar una vuelta alrededor de algún obstáculo.  Así pues, se hicieron cuatro pruebas para cada uno de los dos algoritmos. Las secuencias de puntos generadas por los planificadores se pueden apreciar a continuación.

Escenario 1. Descomposición adaptativa con trayectoria ineficiente

Escenario 1. Descomposición adaptativa con trayectoria eficiente

Escenario 2. Descomposición adaptativa con trayectoria ineficiente

Escenario 2. Descomposición adaptativa con trayectoria eficiente 

Escenario 1. Descomposición exacta con trayectoria ineficiente

Escenario1. Descomposición exacta con trayectoria eficiente

Escenerio 2. Descomposición exacta con trayectoria ineficiente

Escenario 2. Descomposición exacta con trayectoria eficiente

A continuación, se puede apreciar un video de algunas de estas pruebas, las cuales, en promedio, arrojaron un error del 3,4% como se ve en la siguiente tabla.

[1]     Jean-Claude Latombe, Robot Motion Planning. Kluwer Academic Publishers, 1991.

[2]     H. Choset, et al., Principles of Robot Motion: Theory, Algorithms, and Implementations. Boston: MIT Press, 2005.

[3]     S. LaValle, Planning Algorithms. Cambridge: Cambridge University Press, 2006.

[4]     Roland Siegwart, Illah R. Nourbakhsh, Introduction to Autonomous Mobile Robots. The MIT Press, 2004.

[5]     Robin R. Murphy, Introduction to AI Robotics. Massachussetts: The MIT Press 2000.

Arquitectura Subsumption

Creación y Aplicación de la Arquitectura Subsumption Orientada a Comportamientos, para controlar un robot Lego NXT bajo el ambiente Java-LeJOS

 

Algunas Arquitecturas Orientadas a comportamientos:

Basada en esquemas:

Permite que cada elemento pueda ser instanciado o finalizado en cualquier momento, de acuerdo con la tarea a realizar y el estado del entorno, lo que dota a la arquitectura con una capacidad importante. Cada comportamiento es implementado como un conjunto de esquemas. Ver mas...

Redes de  activación:

En esta arquitectura, un agente es visto como un conjunto de competencias (comportamientos) módulos, y la selección de acciones se modela como una propiedad emergente de una dinámica de activación / inhibición entre estos módulos. El método de coordinación es competitivo, un solo módulo puede estar activo en cualquier momento. Ver mas...

Distribuida para navegación móvil:

Incluye un modulo de coordinación basado en votación. Cada comportamiento arroja un número de votos a favor o en contra de un conjunto predefinido de acciones. Los comportamientos tienen un peso asignado. La acción con más votos se selecciona y los actuadores se ajustan convenientemente. Cada grado de libertad (es decir, de giro y velocidad) tiene su propio árbitro, lo que aumenta la modularidad. Ver mas...

Acerca de la Arquitectura Subsumption: 

Rodney Brooks desarrolló la arquitectura Subsumption. La arquitectura Subsumption se presentó en 1986 en el documento "A Robust Layered Control System for a Mobile Robot”. La idea era conectar directamente la percepción y la acción, descartando los modelos internos. El controlador debe ser descompuesto de forma simultánea y asíncrona en capas orientados a tareas, capas que trabajan en distintos objetivos (caminar, evitar los obstáculos, etc.).

Componentes de la Arquitectura Subsumption:

• Comportamientos o capas: Para implementar un algoritmo de control para un robot usando la arquitectura subsumption, se debe descomponer o separar en módulos cada una de las diferentes tareas, objetivos o incluso sensores en comportamientos diferentes. Cada uno de estos comportamientos, debe tener una condición de inicio, algo que se debe satisfacer para determinar el instante en el cual dicho comportamiento tome el control del robot, también se debe definir alguna acción a ejecutar en cuanto el robot termina de ejecutar el comportamiento, esta acción deberá ser lo más corta posible, generalmente se utiliza para cambiar el estado de algún indicador, por último se debe definir la acción a ejecutar en el momento en que el comportamiento toma el control del robot. Adicionalmente a esto, se debe pensar en la importancia o relevancia de cada comportamiento con respecto a los demás, permitiendo saber cuáles comportamientos predominan sobre los otros y cuáles no.
• Árbitro: Este componente, es el encargado de iniciar la ejecución de los comportamientos y  de dar el control del robot a cierto comportamiento en el momento en que la condición de inicio indicada en un este se cumpla. En caso de que dos o más comportamientos cumplan sus condiciones de inicio en un instante dado, solo el comportamiento de mayor importancia será el que tome el control.

 Saber mas...

Acerca de Java-LeJOS:

LeJOS es un entorno de desarrollo basado en Java, que permite programar robots Lego NXT bajo el firmware LeJOS, con gran facilidad . Saber mas...

 La Arquitectura Subsumption en Java-LeJOS:

Java-LeJOS ofrece la librería Subsumption que hace parte del paquete lejos.robotics.subsumption. Dicho paquete contiene la clase Arbitrator y la interfaz Behavior, útiles para la gestión de los comportamientos y la creación de estos con cada uno de sus componentes  respectivamente.

  

La interfaz Behavior:

Esta interfaz, es la cual nos va a permitir crear cada uno de los módulos que representarán los diferentes comportamientos que componen nuestro algoritmo de control. Esta interfaz está compuesta por tres métodos abstractos que nos permitirán definir todas las características de un comportamiento. Estos son:

• boolean takeControl(): Este método retorna un valor de tipo booleano, de acuerdo al valor de verdad de este, el comportamiento toma el control. Es decir en el momento en que tome un valor verdadero, el árbitro le sede el control del robot a este comportamiento, siempre y cuando no exista otro comportamiento de prioridad mayor que cumpla también su condición de inicio.
• void action(): El código contenido en este método, es el que será ejecutado en cuanto el comportamiento tome el control del robot, representa la tarea a ejecutar por el robot en ese momento, en cuanto la ejecución del código termina, el método retorna.
• void suppress(): Este método debe ser lo más corto posible, es ejecutado en cuanto el método action() termina su ejecución, es usado generalmente para establecer el valor de alguna variable de control del propio comportamiento o de otros, por ejemplo una “flag”.

Para crear un comportamiento solo basta con implementar la interfaz Behavior y los métodos abstractos.

Ilustración 1 Creación de un comportamiento en Java-LeJOS

En cuanto se tengan creadas las clases correspondientes a cada comportamiento, se deben crear las instancias correspondientes, y posteriormente un arreglo de comportamientos ordenados según su importancia, siendo el de menor índice el menos importante.

Ilustración 2 Instanciación de comportamientos en Java-LeJOS

 Saber mas...

La Clase Arbitrator: 

La clase Arbitrator es encargada de gestionar los comportamientos según su importancia y dar el control a cada uno en cuanto se cumplan las condiciones de inicio. Esta clase posee un único método:

• Public void start(): Este método comienza el ciclo de gestión de los comportamientos, hasta que el programa termine en la ejecución de algún comportamiento o todos los comportamientos estén inactivos.

La clase Arbitrator posee dos constructores, para poder instanciar y dar inicio a la ejecución, ambos reciben como argumento el arreglo de comportamientos ordenado según su relevancia:

Ilustración 3 Constructor Clase Arbitrator

El segundo constructor recibe un argumento adicional:

Ilustración 4 Constructor Clase Arbitrator con dos argumentos

Si el valor del segundo argumento es verdadero, el árbitro finalizará su ejecución en el momento en que no exista algún comportamiento activo. Si se enviara este argumento con valor falso, sería idéntico a utilizar el primer constructor.

Saber mas... 

Implementación en un ejemplo real: 

Este algoritmo es un evasor de obstaculos, consiste en hacer que el robot este avanzando constantemente hacia adelante hasta encontrar un obstaculo, en ese momento girará a la izquierda y seguira avanzando hasta encontrar otro. Mientras el boton escape no sea presionado.

Ilustración 5 Implementación de un ejemplo real.

Videos:

A continuación pondré dos videos con la implementación de este algoritmo linealmente y con la arquitectura Subsumption.


Implementación con Arquitectura Subsumption 

Implementación Lineal

Se puede apreciar una diferencia notable en los tiempos que le lleva al robot llegar al final en cada video, sin embargo esta diferencia no tiene nada que ver con la implementacion del algoritmo, sino a factores externos a esto como son friccion, impresicion en los giros, etc.

En la siguiente grafica, se muestran cinco eventos en los que se tomaron los tiempos de cada algoritmo, los tiempos son bastante dispersos, sin embargo el promedio de estos tiempos es muy cercano:

Arquitectura Subsumption VS Algoritmo Lineal:
 

Conclusiones:

• La arquitectura Subsumption orientada a comportamientos, es una muy buena práctica al momento de programar robots, permitiendo generar buen código, comprensible y modular.
• Implementar un algoritmo controlador en arquitectura Subsumption, abre las puertas a múltiples posibilidades al momento de programar, sin embargo no ofrece mayores cambios en eficiencia con respecto a un algoritmo implementado linealmente.
• En el momento de programar un robot, lo ideal es hacerlo desde un comienzo con una arquitectura orientada a comportamientos y no realizar una implementación lineal para ser transformada luego en dicha arquitectura.
• Al implementar algoritmos en la arquitectura subsumption, es muy posible que no se obtengan mejoras a nivel de eficiencia, sin embargo es importante pensar si esta implementación permitiría llegar a un desempeño más eficaz del robot, permitiendo llevar a cabo tareas que antes no era posible.
• Implementar un algoritmo con la arquitectura Subsumption, permitirá a futuro aumentar la cantidad de comportamientos existentes con gran facilidad, pudiendo así mejorar el alcance y desempeño del robot o incluso eliminar comportamientos que ya no sean útiles.
• Al tener la posibilidad de tener múltiples comportamientos, se podría pensar en la posibilidad de tener un repositorio de comportamientos, que puedan ser utilizados por el robot, dadas ciertas condiciones.

   

Escrito por: Juan David Meza Gonzalez. Grupo SINTELWEB. Universidad Nacional de Colombia Sede Medellín.