Figura 1
Como seres humanos gozamos del lujo de tener una computadora con miles de sensores que le permiten navegar e interactuar con el mundo real. El producto de la evolución, ha habilitado nuestras mentes a moldear el mundo a nuestro alrededor basado en la recolección de información por medio de nuestros sentidos. Para nevegar exitosamente podemos hacer altos niveles de desición para la navegación, como por ejemplo, el como ir del punto A al punto B, así como niveles bajos de desición, por ejemplo, como pasar através de una puerta. La capacidad del cerebro para adaptarse se ha hecho posible para gente con cierta capacidad sensorial para navegar através de su entorno. Por ejemplo; la gente evidente puede maniobrar a través de áreas o espacios no familiares con la ayuda de un perro guía. Aún sin todos nuestros sensores , somos capaces de enfrentarnos a entornos familiares y no tan familiares.
Las habilidades de los robots modernos mantienen un fuerte contraste con las habilidades humanas. Los robots tienen muy pocos sensores y mucho menos computadoras sofisticadas; consecuentemente tienen una gran dificultad de adaptarse a los cambios dentro de sus entornos. Los tipos comunes de sensores en los robots incluyen sensores de toque (touch) para detectar coalisiones y sensores sonares para detectar obstáculos a distancia. Algunos robots sofisticados usan Stereo Visio para determinar información con respecto a su medio ambiente, pero esto requiere primeramente resolver el problema de vision por computadora. Por desgracia muchos de los robots experimentan en su entorno con sensores rudimentarios y procesan la información que los sensores proporcionan para tomar desiciones de bajo nivel. Los problemas de la navegación robotica se han intensificado dado a las capacidades de ciertos sensores y al mal funcionamiento o daño durante su operación.
Para entender mejor las limitaciones de los robots, imagine una situación en donde usted se encuentra en una casa desconocida con sólo direcciones indefinidas desde su posición inicial, hasta la cocina, después se coloca un traje de plático que completamente lo aisla del mundo exterior. Dentro del traje, lo único que puede escuchar es un sonido de beep, que sonará más rápido mientras más se acerca a las paredes de la casa u otros obstáculos en el camino. Usted deberá usar el sonido y las direcciones descnocidas para navegar exitosamente hacia la cosina. Las posibilidades son, que después de varios tropiezos alrededor y golpes en las paredes, será capaz de encontrar el camino.
Asi mismo, un exitoso sistema de navegación robotica podra encontrar "el camino hacia la cosina" usando muchos sensores. Idealmente el sistema podra adaptarse a mal funcionamiento de algunos sensores. En efecto los investigadores han desarrollado varios enfoques o aproximaciones para manejar el error en los sensores, inlcuyendo el uso de las redes Bayesian [2], caso de estudio de la resonancia [3, y aprendizaje evolucionario [10]. Este artículo describe como el aprendizaje evolucionario usando simulaciones de robots en sus entornos puede ser efectivo en resolver problemas reales de navegación robotica incluyendo el manejo de errores sensoriales.
Charles Darwin fue el primero en identificar el proceso de selección natural en su trabajo monumental El Origen de las Especies. Ciertas características que gobiernan a un individuo al cambio de la supervivencia son pasadas o heredadas a sus descendientes durante su reproducción. Los individuos con pocas características mueren, haciendo las especies en general más fuertes. Inspirado por este proceso natural de " lucha por sobrevivir", los algoritmos evolucionarios, (EAs) intentan encontrar una solución al problema usando simulación evolutiva por computadora.
Existen dos tipos de Eas de interes particular en este artículo. El primer tipo algoritmos genéticos (GAs), involucran la manipulación de una larga cadena de bits. La cadena de bits representa una solución al problema por resolver; y esta en el programador el determinar el significado de la cadena. El segundo, programación genética, involucra generar árboles de sentencias usados en lenguajes como Lisp y Scheme. Con la programación genética, los programas actuales pueden ser creados y executados.
Generalmente hablando, el proceso usado en el aprendizaje evolucionario empieza con la generación aleatoria de una población de individuos, donde cada individuo es una solución potencial al problema. La población es el conjunto de individuos generados. Cada individuo contine un gen (genome), el contenido producido durante la execución de Eas. En el caso de GAs la larga cadena de bits es el gen.
Después cada individuo en la población es evaluado usando una función conveniente. Una función conveniente (Fitness function) usa un método de probar la calidad de una solución para el respectivo problema. Por ejemplo, si un algoritmo genetico esta diseñado para determinar una simple variable de una función algebraica F(n), la función conveniente podra usar un conjunto de entradas y salidas para determinar que tan cercano esta un individuo a la F(n). En este caso la conveniencia podria ser inversamente proporcional a la suma de las diferencias absolutas entre las salidas esperadas y la salida actual para cada entrada.
Como la conveniencia de un individuo es usada, depende de la implementación del algoritmo evolucionario. Usualmente, una alto valor de conveniencia corresponde a una gran oportunidad de que un individuo sea seleccionado para la reproducción. Existen diferentes métodos para producir la próxima generación, pero más convenientemente , se emplean dos operadore: mutación (mutation) y crianza (breeding). La mutación involucra una alteración aleatoria de uno o más genes en el genome del individuo. La crianza usa una operación de un lado a otro, mejor conocido como crossover, para combinar los componentes de dos padres genome y producir uno o más hijos. Una vez creada la nueva generación, la generación anterior es descartada [1].
Un ciclo de evolución y reproducción es repetido a través de varias generaciones, como se especifica por el programador. El proceso de evolución se suspende después de que el criterio de terminación se ha alcanzado y el resultado de la evolución individual [5]. Para una mejor introducción a GP, consulte [1].
Un resumen de los componentes requeridos para EAs son los siguientes [7]:
Algoritmos evolucionarios han sido implementados para resolver problemas en navegación de robots. En particular, EAs han sido usados para obtener un robot que aprenda como adaptarse a sus capacidades limitadas. Usar GP en esta forma es llamado aprendizaje evolucionario. Como se establecio antes, la navegación de robots es un problema dificíl, y viene a ser más dificíl cuando un robot encuentra una falla en sus sensores, es decir los dispositivos que le informan al robot acerca del ambiente, o sus actuadores, dispositivos que permiten al robot interactuar fisicamente con su ambiente.
Son numerosos los ejemplos de EAs que son aplicados a mobilidad robotica. El proyecto GOLEM ha involucrado robots que producen un novedoso significado de locomoción en simulación, y el cual posteriormente ha sido usado en manofactura asistida por computadora [6]. Miglino, Lund, and Nolfi han involucrado exitosamete comportamientos de navagacion usando smilaciones de alta presición para entranamiento y ellos han aplicado sus resultados al robot mobil miniatura Khepera [8]. Wu, Shultz, and Agah han usado GP para desarrollar comprotamientos en simulación de robots para micro vehiculos aereos distruibuidos [11].
Shultz and Grefenstette han aplicado aprendizaje evolucionario a navegación de robots con una estrategia que ellos llaman Aprendizaje Continuo e Incrustado (CEL, por sus siglas en inglés) [10]. La seguridad de CEL en simulación del robot y su ambiente para involucrar comportamientos de navegacion es similar a otras aplicaciones de apredizaje evolucionario. El trabajo de Shultz and Grefenstette extiende el de Miglino, Lund y Nolfi al habilitar al robot para cambiar dinamicamente su simulacion de su propias capacidades sensoriales en vez de tener una simulacion estática de capacidades sensoriales explicitamente detallada por los desarrolladores [11].
CEL es diferente de otras aplicaciones EA en algunos aspectos. En muchas de las aplicaciones EA, ocurren dos pasos diferentes: un periodo inicial es conducido por correr la EA en un conjunto de entrenamiento, seguido por la ejecución de la mejor solución. Con CEL, los dos pasos son unidos y operan concurrentemente mientras el robot esta desarrollando su tarea. Así, el proceso de aprendizaje es continuo. El sistema tiene dos componentes mayores, el sistema de aprendizaje y el sistema de ejecución. El sistema de aprendizaje constantemente involucra nuevos comportamientos en base a pruebas de conocimientos y evalua estos contra el modelo de simulación. Si el sistema de aprendizaje determina que un nuevo comportamiento será más eficiente que el actual, la base de conocimiento activo es actualizado en el sistema de ejecución. En el sistema de ejecución; la toma de desición usa la base de conocimientos para hacer navegación de desiciones. Un monitor es incluido en el sistema de ejecución para actualizar el modelo de simulación usado por el sistema de aprendizaje. Si se detecta un cambio mayor en la capacidad de un robot por medio del monitor, el sistema de aprendizaje se reiniciara e iniciara con nuevos comportamientos que serán efectivos en términos de las capacidades de los robots. La figura 1 muestra este alcance.
Figura 1
Los componentes claves del modelo son:
Al inicio de la operación, el robot usa un caso base de conjunto de reglas definidas por el programador. Cada caso contiene una acción a ejecutar cuando los sensores del robot reunen los parametros especificos en ese caso. Una típica regla podria ser:
IF range = [10,20] AND front_sonar < 50 AND left_sonar > 20 THEN SET turn = 5 (Strength 0.7)
Escencialmente, el sistema esta basado en estimulo-respuesta donde el robot reacciona a las entradas del sensor basado en tiempo real de un conjunto de reglas. Cuando las condiciones cumplen con la sentencia IF, los actuadores ejecutan movimientos basados en el conjunto de valores de la cláusula THEN. Uno puede pensar en estas reglas como genes de la implementación EA. Un individuo en este caso es un conjunto de reglas y una base de reglas forman la población. Fitness es medible por el cumplimiento de la meta en un cierto tiempo. El tope de 50% de reproducción de individuos, produciendo cada uno un offspringc[10]. El sistema de aprendizaje usa SAMUEL, un programa que involucra reglas para la toma de desiciones usando EA y otra heuristica basada en la competencia.
En el experimento de Schultz y Grefenstette, a un robot se le dio la tarea de navegar por el lado opuesto de un cuarto a través de un pasillo empezando por una pared y más adelante con una dirección de 90 grados a 90 grados con dirección 0 a la pared opuesta. Un ejemplo por supuesto es mostrado en la figura 2.El éxito de la medición del CEL fue el porcentaje en tiempos en donde el robot exitosamente alcanzo la meta sin golpearse en la pared a través del camino.
Figura 2
La tecnología Nomadic Nomad 2000 Robot móvil fue usada en una prueba de aplicación real. El robot es una máquina de movimientos sincronizados de tres ruedas. El monitor en el sistema de ejecución combina la salida de los sensores con información de los actuadores del robot para determinar fallas en los sensores. Si una unidad frontal sonar continuamente tiene como salida el valor de cero como la distancia entre el robot y un obstáculo, pero el robot sigue moviendose hacia adelante, entonces el sensor es marcado con error. En el experimento, la falla del sonar fue simulada al cubir el sensor con material pesado[10].
El conjunto de reglas iniciales usado en el experimento le dio al robot una noción básica de como llegar al otro lado del cuerpo, pero no tomo en cuenta los obstáculos y paredes. El modelo de simulación inicialmente asume que todos los sensores estan trabajando [10].
Sin evolución y toda la funcionalidad de los sensores, el robot fue capaz de navegar exitosamente en un 25% del tiempo. Después de 50 generaciones de evolución el rango de éxito del robot incremento en un 61%. Con tres sensores a lado derecho del robot desahabilidado después de 50 generaciones, el rango de éxito bajo en un 42%, pero incremento más de 50 generaciones en un 63%. La figura 3 muestra la curva de aprendizaje, estos porcentajes son en promedio.
Figura 3. Esta curva de aprendizaje muestra el éxito del robot a la
adaptación de la falla de sensores después de un cierto número de generaciones
que estuvieron involucrados en el sistema de aprendizaje. La línea vertical
punteada en la generación 50 indica la instancia cuando tres de los sensores
frontales fueron desahabilitados. Los resultados son promedios sobre 10 corridas.
El resultado del experimento muestra que el robot usando CEL no sólo puede aprender a como mejorar su habilidad para navegar por si mismo, pero también a re-aprender a como navegar después de sufrir la pérdida algunos sensores. Mientras el resultado no sea terriblemente impresionante, la mejora en la navegación y adaptación al cambio en cuanto a capacidad son claramente mostrado.
EL experimento de Schultz y Grefenstette's mostro que CEL es un alcance viable para producir comportamientos adaptativos en robots autónomos en ciertos dominios. Los robots que sufren alguna falla impredesible en su campo se pueden adaptar a sus nuevas capacidades usando CEL y continuar desempeñando sus tareas. Las investigaciones futuras de CEL incluyen la combinación de las fallas de los sensores y actuadores para determinar que tan exitoso puede ser esta investigación y determinar los limites de adaptabilidad del CEL [10]. Otra investigación es necesaria para mejorar el modelo dinámico de un robot en su entorno.
En ciertos dominios, CEL no podra ser una técnica efectiva. Por ejemplo, manejando en la ciudad, CEL podria ser muy lento para involucrar un comportamiento para esquivar a los peatones. Un sistema que combina razones de alto nivel con comportamiento a respuesta de estimulos de bajo nivel que CEL es capaz de desarrollar quizas más efectivamente en un rango amplio de dominios. Sin embargo, CEL es un paso inicial que promete en el área de desarrollar robots móviles adaptativos que puedan aprender por su propia cuenta.
Agradezco a Alan C. Schultz por permitir discutir su trabajo en Crossroads, usar las figuras originales de su trabajo y por la revisar este artículo. Agradezco también al profesor David Wolfe y a los revisores anónimos que dieron algunas sugerencias para escribir este artículo.
Cory Quammen esta cursando un posgrado en Ciencias Computacionales en Gustavus Adolphus College en St. Peter MH. El planea cursar un doctorado en Ciencias Computacionales especializandose en inteligencia artificial y programación genetica.