Sistema de coordinación multiagente basado en comportamientos aprendidos

UNIVERSIDAD DE MÁLAGA ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DE TELECOMUNICACIÓN Tesis Doctoral SISTEMA DE COORDINACIÓN MULTIAGENTE BASADO EN COMPORTAMIENTOS APRENDIDOS Programa de doctorado: Ingeniería de Telecomunicación Autor: José Manuel Peula Palacios Directora: Dra. Cristina Urdiales García MÁLAGA, 2015 AUTOR: José Manuel Peula Palacios http://orcid.org/0000-0002-3798-5195 EDITA: Publicaciones y Divulgación Científica. Universidad de Málaga Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercialSinObraDerivada 4.0 Internacional: http://creativecommons.org/licenses/by-nc-nd/4.0/legalcode Cualquier parte de esta obra se puede reproducir sin autorización pero con el reconocimiento y atribución de los autores. No se puede hacer uso comercial de la obra y no se puede alterar, transformar o hacer obras derivadas. Esta Tesis Doctoral está depositada en el Repositorio Institucional de la Universidad de Málaga (RIUMA): riuma.uma.es Dª CRISTINA URDIALES GARCÍA, PROFESORA TITULAR DEL DEPARTAMENTO DE TECNOLOGÍA ELECTRÓNICA DE LA UNIVERSIDAD DE MÁLAGA CERTIFICA: Que D. José Manuel Peula Palacios, Ingeniero de Telecomunicación, ha realizado en el Departamento de Tecnología Electrónica de la Universidad de Málaga, bajo mi dirección, el trabajo de investigación correspondiente a su Tesis Doctoral titulada: “SISTEMA DE COORDINACIÓN MULTIAGENTE BASADO EN COMPORTAMIENTOS APRENDIDOS” Revisado el presente trabajo, estimo que puede ser presentado al Tribunal que ha de juzgarlo. Y para que conste a efectos de lo establecido por la normativa de la Universidad de Málaga, AUTORIZO la presentación de esta Tesis en la Universidad de Málaga. Málaga, a 22 de octubre de 2015 Fdo. Cristina Urdiales García Profesora Titular del Departamento de Tecnología Electrónica A los que han estado, a los que est´an y a los que estar´an I II Agradecimientos Dice el refr´an que de bien nac´ıos es ser agradec´ıos. Aunque en general no suelo hacer caso a los refranes, pero creo que la ocasi´on merece hacer una excepci´on. As´ı pues, en primer lugar querr´ıa agradecer a mi familia (papa, mama, Salvi, Chelo, Virgi y Alicia) por estar ah´ı y, aunque no se si en alg´un momento han tenido claro que estaba haciendo ni para qu´e serv´ıa, pero gracias por interesaros y apoyarme. Especialmente querr´ıa agradecer a Chelo por ser tan insistente y tener, a´un m´as ganas que yo, de que acabase la tesis. Por otro lado, querr´ıa mencionar de forma especial y obligatoria a Cristina, a quien debo un m´ultiple agradecimiento por su ayuda con el proyecto fin de carrera, el diploma de estudios avanzados y la presente tesis. Gracias por tus locas y descabelladas ideas que, aunque no siempre llevasen a buen puerto, pero al menos nos ech´abamos unas risas en el intento. Gracias tambi´en por estar siempre ingeniando formas de solucionar los problemas y por apoyarme hasta el final. Igualmente, querr´ıa agradecer a Francisco Sandoval por su constante apoyo, esfuerzo e inter´es para que finalizase la presente tesis. Como no, quiero tambi´en agradecer a todo ese torrente de personas que han estado presentes a lo largo de la realizaci´on de este trabajo aportando sus ideas, criticando, apoyando, dando ´animos, acompa˜nando en las comidas, echando unas risas, etc. Estoy seguro de que este listado no est´a completo, pero a´un as´ı quiero agradecer concretamente a Jose Carlos, Jose Ram´on, Pedro, Richar, Jose Manuel, Juanpe, Antonio Bandera, Rebeca, Raquel, Ra´ul, Ale, Paqui, Antonio Palomino, Cubi, Alejandro, Manolo, Pepe, Cisco, Javi, D´ebora, Yolanda, Miguel, Jesus, Blanquilla, Lydia, Carlos, Joaquin, Inma, Mariluz, Adri, Gerardo, David, Fran, Eu, Cesar, Eva, Bernardo, Eva, Zuma, Jacob, Fuen, Gloria, Juanma, Mario, Laura, Nacho, Edu, Javier, Roberta, Alessia, Ulises, Dar´ıo, Thomas, Dani, Josemi, Berti, Juan Ram´on, Rafa, Carmen, mini-Carmen, Ana Bel´en, Lola,al ´ultimo teleko y a Scott. A todos: ¡Muchas gracias! Tambi´en querr´ıa agradecer al Ministerio de Educaci´on y Ciencia (MEC), al Ministerio de Ciencia e Innovaci´on (MICINN) y a los Fondos FEDER por el III IV AGRADECIMIENTOS apoyo ofrecido a trav´es de los proyectos “Sistema de Navegaci´on Multiagente Cooperativo para Entornos Sanitarios” (TIN2004-07741-C02-01), “Perception and senso-motor learning system for humanoid platforms” (TIN200501359), “Arquitectura de ServicioS Inteligente de SoporTe a Personas con necesidades especiales (ASSIST)” (TEC2006-11689-C01), “Arquitectura de Servicios Inteligente de SoporTe a la Independencia mediante Robots (ASISTIR)” (TEC2008-06734-C02-01) y “Tecnolog´ıa Asistiva para Rehabilitaci´on Colaborativa” (TEC2011-29106-C02-01). De igual manera, querr´ıa agradecer a la Junta de Andaluc´ıa por su ayuda a trav´es los proyectos SIAMA (TIC 249) y SIAD (TIC-3991), a la Uni´on Europea en el VI Programa Marco (FP6-2005-IST-5. STREP no. 045088) por el proyecto “Supported Human Autonomy for Recovery and Enhancement of cognitive and motor abilities using information technologies (SHARE-it)” (Ref.STREP no. 045088) y a Andaluc´ıa Tech. Tambi´en querr´ıa agradecer al grupo KEMLg (Knowledge Engineering and Machine Learning Group) de la Universidad Polit´ecnica de Catalu˜na (UPC), por permitirnos usar su implementaci´on del servidor CBR en la presente tesis as´ı como en otros trabajos. Por ´ultimo, y ya que seguramente haya olvidado mencionar expresamente a alguien en los p´arrafos anteriores pues han sido muchos a˜nos y muchas personas, querr´ıa agradecer de forma gen´erica a todos los que han ayudado o participado de alguna manera en la realizaci´on de esta tesis, as´ı como a todos aquellos que no han molestado, pues mucho ayuda el que poco estorba. Por lo tanto: ¡Muchas gracias a todos! Resumen La rob´otica ha cambiado enormemente desde sus or´ıgenes hasta la actualidad. As´ı pues, se ha pasado de la concepci´on de robots, que pr´acticamente eran aut´omatas que realizaban una simple tarea repetitiva de forma autom´atica pr´acticamente sin interactuar ni obtener ning´un tipo de informaci´on del entorno, a los sistemas actuales con una gran versatilidad y capacidades de interacci´on a nivel t´actil, visual y auditivo. Uno de los grandes avances en la rob´otica, no porque la idea no hubiese surgido hace tiempo, sino porque pr´acticamente hasta hace poco no era factible t´ecnicamente, es la aplicaci´on de la inteligencia artificial y la interacci´on entre distintas entidades. Ambos elementos est´an altamente relacionados, pues no es posible obtener una gran interacci´on ni una interacci´on natural si las entidades que interact´uan no disponen de una cierta inteligencia, capacidad de adaptaci´on y de aprendizaje. En el caso de un robot, las posibles interacciones que puede tener son la interacci´on robot-robot y la interacci´on robot-humano. Ambos tipos de interacci´on son hoy en d´ıa ´areas de trabajo muy activas, pues suponen retos interesantes, complejos y con distintos puntos de vista y posibles soluciones, muchas de ellas v´alidas dependiendo de la situaci´on y problema concreto. La presente tesis se centra en la interacci´on robot-robot, concretamente en la coordinaci´on entre robots, ´area activa desde hace a˜nos y todav´ıa con mucho inter´es. Concretamente, en este trabajo se presenta un sistema de coordinaci´on impl´ıcita multi-agente basado en el aprendizaje de comportamientos mediante aprendizaje por demostraci´on. La coordinaci´on impl´ıcita se basa en que la coordinaci´on surge a partir de la interacci´on entre los distintos agentes del sistema, los cuales act´uan de forma aut´onoma e independiente entre ellos, aunque pudiendo tener conocimiento de la existencia de los dem´as agentes. Este enfoque ha sido utilizado frente a la coordinaci´on expl´ıcita porque encaja m´as f´acilmente en una arquitectura basada en comportamientos, cuyo principio de funcionamiento, de abajo hacia arriba, consiste en el desarrollo de comportamientos simples paV XII ´ INDICE GENERAL 5. Coordinaci´on reactiva basada en aprendizaje 125 5.1. Introducci´on............................125 5.2. Coordinaci´on ...........................127 5.3. CBR aplicado a Coordinaci´on . . . . . . . . . . . . . . . . . . 129 5.4. Coordinaci´on basada en comportamientos reactivos aprendidos 130 5.4.1. Comportamiento coordinado en paralelo . . . . . . . . 131 5.4.2. Localizaci´on basada en marcas ARToolkit . . . . . . . 132 5.4.3. Aprendizaje con varios robots: entrenamiento secuencial133 5.4.4. Funcionamiento del sistema . . . . . . . . . . . . . . . 134 5.4.5. Implementaci´on del sistema . . . . . . . . . . . . . . . 134 5.4.6. Descripci´on del CBR . . . . . . . . . . . . . . . . . . . 137 5.4.6.1. Estructura de la base de casos . . . . . . . . . 137 5.4.6.2. Definici´on del caso . . . . . . . . . . . . . . . 138 5.4.6.3. Descripci´on de la fase de recuperaci´on . . . . 140 5.4.6.4. Descripci´on de la fase de reutilizaci´on . . . . 140 5.4.6.5. Descripci´on de la fase de revisi´on . . . . . . . 140 5.4.6.6. Descripci´on de la fase de retenci´on . . . . . . 141 5.5. Experimentos y resultados . . . . . . . . . . . . . . . . . . . . 141 5.5.1. Entrenamiento secuencial: fase 1 . . . . . . . . . . . . . 142 5.5.2. Entrenamiento secuencial: fase 2 . . . . . . . . . . . . . 143 5.5.3. Navegaci´on coordinada aut´onoma . . . . . . . . . . . . 143 5.5.4. Comportamientos coordinados complejos . . . . . . . . 145 5.5.5. Limitaciones de la localizaci´on basada en ARToolkit . . 146 5.6. Conclusiones............................149 6. Coordinaci´on h´ıbrida basada en aprendizaje 151 6.1. Introducci´on............................151 6.2. Coordinaci´on reactiva: problemas y limitaciones . . . . . . . . 153 6.2.1. Aprendizaje de comportamientos complejos o ambiguos 154 6.2.2. Localizaci´on . . . . . . . . . . . . . . . . . . . . . . . . 155 6.2.3. Entorno de desarrollo . . . . . . . . . . . . . . . . . . . 157 6.2.3.1. Simulador . . . . . . . . . . . . . . . . . . . . 160 6.2.4. Implementaci´on del CBR . . . . . . . . . . . . . . . . . 161 6.2.4.1. LibCBR.....................162 6.2.4.2. Depurador de LibCBR . . . . . . . . . . . . . 164 6.3. Coordinaci´on mediante aprendizaje . . . . . . . . . . . . . . . 166 6.3.1. Descripci´on del comportamiento coordinado . . . . . . 169 6.3.1.1. Comportamientos elementales . . . . . . . . . 170 6.3.1.2. Entrenamiento de los comportamientos . . . . 171 6.3.1.3. Combinaci´on de los comportamientos . . . . . 172 6.3.2. Informaci´on y objetos virtuales . . . . . . . . . . . . . 173 ´ INDICE GENERAL XIII 6.3.3. Funcionamiento del sistema . . . . . . . . . . . . . . . 175 6.3.4. Implementaci´on del sistema . . . . . . . . . . . . . . . 176 6.3.5. Descripci´on del CBR . . . . . . . . . . . . . . . . . . . 180 6.3.5.1. Estructura de la base de casos . . . . . . . . . 180 6.3.5.2. Definici´on del caso CBR . . . . . . . . . . . . 180 6.3.5.3. Descripci´on de la fase de recuperaci´on . . . . 182 6.3.5.4. Descripci´on de la fase de reutilizaci´on . . . . 182 6.3.5.5. Descripci´on de la fase de revisi´on . . . . . . . 182 6.3.5.6. Descripci´on de la fase de retenci´on . . . . . . 183 6.4. Experimentos y resultados . . . . . . . . . . . . . . . . . . . . 183 6.4.1. Entrenamiento de los comportamientos b´asicos . . . . . 184 6.4.2. Capa de selecci´on de comportamientos . . . . . . . . . 186 6.4.3. Navegaci´on coordinada aut´onoma . . . . . . . . . . . . 187 6.5. Conclusiones............................190 7. Conclusiones finales y resultados de la tesis 193 7.1. Introducci´on............................193 7.2. Conclusiones............................193 7.3. Aportaciones de la tesis . . . . . . . . . . . . . . . . . . . . . 196 7.4. Resultados y publicaciones . . . . . . . . . . . . . . . . . . . . 197 7.5. L´ıneasfuturas...........................199 Bibliograf´ıa 201 XIV ´ INDICE GENERAL ´ Indice de figuras 1.1. Representaci´on de Talos. . . . . . . . . . . . . . . . . . . . . . 2 1.2. Pato de Vaucanson, destruido en 1789. . . . . . . . . . . . . . 3 1.3. Brazo industrial PUMA. . . . . . . . . . . . . . . . . . . . . . 5 1.4. Robot aut´onomo Prop-M Rover. . . . . . . . . . . . . . . . . . 7 1.5. Ejemplo de una red neuronal. . . . . . . . . . . . . . . . . . . 9 1.6. Equipo de robots en la Robocup 2004. . . . . . . . . . . . . . 12 2.1. Dos AIBOs ERS-7 compitiendo en la Robocup . . . . . . . . . 22 2.2. Navegaci´on reactiva (a), deliberada (b) e h´ıbrida (c) . . . . . . 24 2.3. Red neuronal y estructura interna de una neurona. . . . . . . 33 3.1. T´ıpico ciclo del CBR . . . . . . . . . . . . . . . . . . . . . . . 48 3.2. Representaci´on de un caso CBR. . . . . . . . . . . . . . . . . . 54 3.3. Representaci´on de una base de casos plana. . . . . . . . . . . . 56 3.4. Aprendizaje por observaci´on. . . . . . . . . . . . . . . . . . . . 63 3.5. Esquema del sistema durante el entrenamiento. . . . . . . . . 66 3.6. Par´ametros de definici´on del caso para b´usqueda de pelota. . . 72 3.7. Estimaci´on de la posici´on del robot a partir de las l´ıneas. . . . 74 3.8. Par´ametros de definici´on del caso para b´usqueda de porter´ıa. . 75 3.9. Efecto de cambios en la inclinaci´on de una l´ınea. . . . . . . . . 77 3.10. Ejemplo de adaptaci´on real. . . . . . . . . . . . . . . . . . . . 78 3.11. Entrenamiento para seguimiento de pelota . . . . . . . . . . . 82 3.12. Pruebas de Navegaci´on con una pelota est´atica. . . . . . . . . 83 3.13. Pruebas de navegaci´on reactiva con una pelota m´ovil. . . . . . 84 3.14. Entrenamiento para b´usqueda de porter´ıa usando CBR . . . . 84 3.15. B´usqueda de porter´ıa reactiva usando CBR sin adaptaci´on . . 85 3.16. Errores buscando b´usqueda de porter´ıa sin adaptaci´on . . . . 86 3.17. B´usqueda de porter´ıa reactiva usando CBR con adaptaci´on . . 87 3.18. Nuevas secuencias de entrenamiento espec´ıficas para esquinas . 87 3.19. Prueba final de b´usqueda de porter´ıa reactiva con adaptaci´on . 88 3.20. Im´agenes reales del comportamiento global (prueba 1). . . . . 89 XV XVI ´ INDICE DE FIGURAS 3.21. Im´agenes reales del comportamiento global (prueba 2). . . . . 90 4.1. Estimaci´on de la posici´on usando triangulaci´on. . . . . . . . . 105 4.2. Visi´on est´ereo y localizaci´on. . . . . . . . . . . . . . . . . . . . 107 4.3. ARToolkit y localizaci´on. . . . . . . . . . . . . . . . . . . . . . 109 4.4. Proceso para detecci´on de balizas. . . . . . . . . . . . . . . . . 112 4.5. Diagrama de bloques del sistema. . . . . . . . . . . . . . . . . 115 4.6. Navegaci´on usando localizaci´on por objetos comunes . . . . . 117 4.7. Diagrama de bloques del sistema. . . . . . . . . . . . . . . . . 119 4.8. Navegaci´on usando localizaci´on con ARToolkit . . . . . . . . . 120 4.9. Pruebas de localizaci´on est´atica. . . . . . . . . . . . . . . . . . 122 5.1. Campo con marcas ARToolkit para localizaci´on. . . . . . . . . 133 5.2. Esquema general del sistema. . . . . . . . . . . . . . . . . . . 135 5.3. Descripci´on del sistema de coordinaci´on. . . . . . . . . . . . . 135 5.4. Par´ametros usados en la definici´on del caso CBR. . . . . . . . 139 5.5. Fase 1 del entrenamiento secuencial. . . . . . . . . . . . . . . . 142 5.6. Fase 2 del entrenamiento secuencial. . . . . . . . . . . . . . . . 143 5.7. Navegaci´on coordinada reactiva basada en aprendizaje. . . . . 144 5.8. Secuencias de entrenamiento para comportamientos complejos. 145 6.1. Balizas de colores y disposici´on en el campo. . . . . . . . . . . 156 6.2. Estructura b´asica DLA. . . . . . . . . . . . . . . . . . . . . . 160 6.3. Simulador 3D Gazebo (a) y Mirage (b). . . . . . . . . . . . . . 161 6.4. Formato CSV del fichero CBR. . . . . . . . . . . . . . . . . . 163 6.5. Representaci´on de los casos en el depurador LibCBR. . . . . . 165 6.6. Operaciones visuales del depurador LibCBR. . . . . . . . . . . 166 6.7. Modelo del sistema y objetos virtuales. . . . . . . . . . . . . . 174 6.8. Esquema general del sistema. . . . . . . . . . . . . . . . . . . 176 6.9. Diagrama de bloques de Cliente AIBO. . . . . . . . . . . . . . 178 6.10. Representaci´on de las variables usadas en los casos CBR. . . . 181 6.11. Entrenamiento de los comportamientos elementales. . . . . . . 185 6.12. Prueba de coordinaci´on con oponente parado. . . . . . . . . . 188 6.13. Prueba de coordinaci´on con oponente en movimiento. . . . . . 189 ´ Indice de tablas 2.1. Caracter´ısticas de las arquitecturas de control. . . . . . . . . . 26 6.1. Entrada de los casos CBR para cada comportamiento. . . . . . 181 XVII XVIII ´ INDICE DE TABLAS ´ Indice de acr´onimos AIBO Robot de Inteligencia Artificial. ANN Redes Neuronales Artificiales. CBR Razonamiento Basado en Casos. CSV Valores Separados por Comas. DLA Arquitectura en Capas Distribu´ıda. DWA M´etodo de Ventana Din´amica. GA Algoritmos Gen´eticos. HSI Hue, Saturation, and Intensity. HSV Hue, Saturation, and Value. IA Inteligencia Artificial. LfD Aprendizaje por Demostraci´on. MAS Sistemas Multi-Agente. MRS Sistemas Multi-Robot. OpenCV Librer´ıa de C´odigo Abierto para Visi´on por Ordenador. PFA M´etodo de Campos Potenciales. Pyro Python para Rob´otica. RA Realidad Aumentada. XIX XX Siglas RBS Sistemas Basados en Reglas. ROS Sistema Operativo Rob´otico. SPA Percibir-Planificar-Actuar. URBI Interfaz Universal para Plataformas Rob´oticas. VFH Histograma de Campo de Vectores. Cap´ıtulo 1 Introducci´on 1.1. Introducci´on En este cap´ıtulo se presenta una introducci´on a la rob´otica, as´ı como su evoluci´on desde sus or´ıgenes hasta la actualidad, finalizando este apartado con los Sistemas Multi-Robot (MRS) (Multi-Robot System en ingl´es). Tras esto, se indicar´an los objetivos de la presente tesis y la estructura del documento. 1.2. La rob´otica Los ´ultimos a˜nos han sido testigo del incre´ıble e inexorable avance de la rob´otica desde sus t´ımidos primeros pasos hasta su situaci´on actual. En sus comienzos, all´a por los a˜nos 20, el concepto de robot, acu˜nado en la obra R.U.R de Karel Capek, no era m´as que un t´ermino perteneciente a la ciencia ficci´on. Sin embargo, en poco menos de 100 a˜nos este concepto ha pasado de ser algo ficticio a una realidad cotidiana, pues la rob´otica ha llegado a invadir incluso los hogares dom´esticos con robots para entretenimiento y ocio como el Robot de Inteligencia Artificial (AIBO) (Artificial Intelligence roBOt en ingl´es), Pleo o Sphero, o con robots aspiradoras como la Roomba, llegando a convertirse estos robots, en algunos casos, casi en un miembro m´as de la familia. Todo esto ha sido posible gracias a los avances en muchas de las ´areas de las que depende la rob´otica, como la visi´on, la Inteligencia Artificial (IA), la electr´onica, etc. En general, uno de los mayores avances ha sido la evoluci´on en la miniaturizaci´on electr´onica, que ha permitido grandes capacidades de c´omputo en dispositivos ligeros y de peque˜no tama˜no, permitiendo a la rob´otica aut´onoma mayores capacidades de c´omputo, autonom´ıa y movilidad. 1 8Introducci´on y obtener informaci´on de Marte. Debido a que los retrasos en las comunicaciones hac´ıan inviable un control remoto seguro, el robot rover (llamado Prop-M Rover) deb´ıa ser capaz de moverse, evitando obst´aculos, y obtener muestras de an´alisis del suelo de forma aut´onoma en un entorno pr´acticamente desconocido. As´ı pues, adem´as de capacidad de captar informaci´on del entorno este robot deb´ıa tener una m´ınima capacidad de IA (apenas surgida hac´ıa 30 a˜nos) para poder reaccionar ante los posibles e imprevisibles obst´aculos del entorno. 1.2.5. Inteligencia Artificial La IA es un elemento b´asico en un robot aut´onomo, ya que determina el grado de autonom´ıa de este, entendiendo por grado de autonom´ıa la capacidad del robot para actuar en situaciones diferentes. Si bien es cierto que este elemento no es estrictamente necesario en un robot aut´onomo, pero si es l´ogico que cuanto m´as desarrollada sea la IA del robot, mayor capacidad de actuaci´on y reacci´on tendr´a ante cambios en el entorno. La IA comenz´o a desarrollarse a principios de la d´ecada de los 40, aproximadamente cuando comenzaron a desarrollarse y extenderse los primeros robots industriales. Los primeros trabajos en este ´area se deben a unas publicaciones de Alan Turing, las cuales no tuvieron gran repercusi´on en aquel momento. Poco despu´es de estas publicaciones, Warren McCulloch y Walter Pitts realizaron estudios sobre el funcionamiento de una red neuronal (Fig. 1.5) y demostraron que la m´aquina de Turing pod´ıa ser implementada en una red finita de neuronas. Tras esto, a finales de los a˜nos 40 Donald Hebb desarroll´o un algoritmo (basado en lo que se conoce como Regla de Hebb) que permit´ıa el aprendizaje de estas redes, cre´andose de esta forma la escuela conexionista, considerada como el origen de lo que se conoce hoy en d´ıa como IA. Tambi´en a mediados de esta ´epoca George P´olya present´o los primeros conceptos sobre heur´ıstica, que con el tiempo se convertir´ıa en un elemento fundamental en la IA. Sin embargo, no fue hasta la d´ecada de los 50 cuando la IA comenz´o a cobrar importancia. As´ı pues, en esta ´epoca Alan Turing planteaba, en un art´ıculo que tuvo una enorme repercusi´on, la pregunta de si una m´aquina pod´ıa pensar, y establec´ıa una prueba para comprobar si una m´aquina era capaz de actuar de forma inteligente o no. Fue pocos a˜nos despu´es, a mediados de los 50, cuando surge el t´ermino IA y se convierte en disciplina en la Conferencia de Computaci´on de Dartmouth. En esta ´epoca, Herbert Simon, Allen Newell y J.C. Shaw desarrollaron el primer lenguaje de procesamiento de informaci´on, el IPL-11, y el primer programa de IA, el GPS de sus siglas en ingl´es General Problem Solver, capaz de demostrar teoremas matem´aticos. La rob´otica 9 Figura 1.5: Ejemplo de red neuronal. Si bien la IA estuvo ligada inicialmente a juegos como el ajedrez y las damas, llegando a su punto ´algido con el desaf´ıo entre Deep Blue y Gary Kasp´arov en 1996, pero fue aplicada a otros campos desde casi sus or´ıgenes. As´ı pues, a finales de los 50 y comienzos de los 60 Frank Rosemblatt invent´o y desarroll´o el perceptron, que es una extensi´on del modelo matem´atico concebido por McCullock y Pitts. Este perceptr´on fue inicialmente aplicado al reconocimiento de patrones visuales. Sin embargo, debido a las limitaciones que presentaba el perceptr´on, las redes neuronales cayeron en el olvido hasta el surgimiento del perceptr´on multicapa. Otra de las ´areas en las que fue aplicada fue en la comprensi´on del lenguaje. Como ejemplos de esta aplicaci´on, estar´ıan el programa llamado SADSAM (Sentence Appraiser and Diagrammer, and Semantic Analyzing Machine), desarrollado por Robert K. Lindsay a comienzos de los 60, que era capaz de extraer conclusiones a partir de oraciones, el sistema SIR (Semantic Information Retrieval), desarrollado por Bertrand Raphael a mediados de los 60, o el programa SCHRDLU, que permit´ıa interrogar y dar ´ordenes a un robot que se mov´ıa dentro de un mundo virtual de bloques, desarrollado por Terry Winograd a finales de los 60. Otra de las ´areas a las que fue aplicada la IA fue a la medicina. As´ı pues, el sistema Dendral, desarrollado a mediados de los 60 por Edward Feigenbaum en la Universidad de Stanford, ten´ıa como objetivo el reconocimiento de mol´eculas org´anicas desconocidas. El desarrollo de este sistema llev´o 10 a˜nos y se considera el primer sistema experto. Como resultado de todos estos avances, entre finales de los 60 y principios de los 70 SRI International desarroll´o el primer robot m´ovil de prop´osito general, Shakey, que era capaz de razonar sobre sus propias acciones, es decir, 10 Introducci´on que en vez de realizar secuencias de acciones establecidas ante una orden determinada, el robot era capaz de analizar el comando recibido y determinar, por s´ı mismo, que secuencia de acciones realizar. Este proyecto fue importante por varios factores. Por un lado aunaba distintas ´areas de investigaci´on, como la rob´otica, visi´on por ordenador, procesamiento de lenguaje natural e IA (como de hecho ocurre en casi todos los robots actuales). Por otro lado, fue el primer proyecto que un´ıa el razonamiento l´ogico con la acci´on f´ısica. Sin embargo, a finales de los a˜nos 60 se public´o el libro “Perceptrons: an introduction to computational geometry” de Marvin Minsky y Seymour Papert en el que mostraban las limitaciones del perceptron. Esta publicaci´on caus´o un abandono (temporal) de las redes neuronales a favor de los sistemas expertos, debido a los buenos resultados obtenidos con el sistema experto Dendral. As´ı, a mediados de los 70, Ted Shortliffe desarroll´o en la Universidad de Stanford el programa MYCIN, una continuaci´on del programa Dendral. Este sistema ten´ıa como objetivo el diagn´ostico de enfermedades infecciosas en la sangre, consiguiendo una tasa de aciertos de aproximadamente el 65 %, lo cual mejoraba las estad´ısticas de la mayor´ıa de los m´edicos no especializados en el diagn´ostico de infecciones bacterianas (frente a los especializados cuya tasa era del 80 %). En esta ´epoca tambi´en comenz´o a surgir la Inteligencia Artificial Distribuida como un campo de la IA y, concretamente, lo que hoy en d´ıa se conocen como Sistemas Multi-Agente (MAS) (Multi-Agent System en ingl´es), cuyo objetivo se centra en la interacci´on entre los agentes que componen el sistema. As´ı pues, este enfoque se basa en unir las capacidades de resoluci´on de los distintos agentes de forma que la interacci´on de todos ellos permita la resoluci´on de problemas m´as complejos, estando la inteligencia del sistema distribuida entre los distintos agentes y la interacci´on entre ellos. Ya en la d´ecada de los 80 se empezaron a comercializar las primeras aplicaciones basadas en sistemas expertos (obviamente para el sector profesional). En esta ´epoca tambi´en se desarrollaron los primeros trabajos en el ´area de la conducci´on aut´onoma. Concretamente, fue el equipo de Ernst Dickmanns de la Universidad de Bundeswehr quien construy´o el primer coche robot capaz de conducir por s´ı mismo (aunque en carreteras vac´ıas por seguridad). En esta ´epoca comienz´o tambi´en el resurgimiento de las de las redes neuronales gracias al algoritmo de retropropagaci´on (descrito por Paul J. Werbos). Durante la d´ecada de los 90 hay grandes avances en todas las ´areas relacionadas con la IA, como en aprendizaje m´aquina (machine learning en ingl´es), razonamiento basado en casos, planificaci´on, visi´on, etc. Un ejemplo de estos avances es el robot Polly, desarrollado por Ian Horswill, el primer robot basado en comportamientos capaz de navegar usando visi´on y operar La rob´otica 11 a una velocidad considerable (1 m/s). Otros hitos importantes fueron los avances en conducci´on aut´onoma, realiz´andose experimentos en carreteras con tr´afico, el ´exito de la m´aquina Deep Blue frente a Gary Kasparov o la primera competici´on de la RoboCup, con 40 equipos de robots y m´as de 5000 espectadores. A partir de esta fecha, y hasta la actualidad, contin´uan los avances en todas las ´areas de la IA, siendo uno de los puntos remarcables la liberaci´on de los sistemas expertos al p´ublico en general, surgiendo por ejemplo los juguetes Furby y AIBO a finales de los a˜nos 90 o la aspiradora aut´onoma iRobot’s Roomba a principios del 2000. Ejemplos de sistemas expertos para todos los p´ublicos m´as recientes ser´ıan la aplicaci´on de Google now de Google, Siri de Apple o Cortana de Microsoft, que reconocen lenguaje natural para responder a preguntas y hacer recomendaciones a los usuarios. 1.2.6. Sistemas Multi-Robot Una vez la rob´otica aut´onoma alcanz´o una madurez considerable se fueron planteando retos m´as y m´as complejos, de forma que se encontraron problemas que eran dif´ıciles de resolver por un ´unico robot, estudi´andose la posibilidad de que varios robots colaborasen entre s´ı para realizar una misma tarea que un ´unico robot no podr´ıa hacer o tardar´ıa m´as que varios robots colaborando en paralelo. As´ı fue como surgi´o, a finales de los 80, los MRS (Multi-Robot System en ingl´es), que no es m´as que un sistema formado por m´ultiples robots aut´onomos individuales que interact´uan entre s´ı para realizar una tarea concreta. De esta forma, los MRS se pueden considerar como una extensi´on de la rob´otica aut´onoma individual, posibilitando la resoluci´on de problemas m´as complejos aunque, a su vez, presentando nuevos retos, ya que los robots que forman el sistema deben ser capaces de coordinarse entre s´ı de forma correcta. Tambi´en hay que tener en cuenta que los MRS presentan una serie de ventajas frente a los sistemas monol´ıticos, ya que son m´as tolerantes a fallos, m´as flexibles y, en general, m´as eficientes al realizar las tareas pues tienen la capacidad de estar en m´ultiples lugares al mismo tiempo, dividiendo las tareas complejas en tareas m´as simples. Los trabajos en coordinaci´on e interacci´on de m´ultiples agentes inteligentes comenzaron en la d´ecada de los 70, pero no fue hasta 10 a˜nos despu´es cuando comenzaron a aplicarse estos trabajos en el ´area de la rob´otica, concretamente en rob´otica cooperativa. As´ı pues, el primer trabajo fue el proyecto CEBOT (Cellular Robotics), desarrollado por T. Fukuda, Y. Kawauchi y H. Asama, que consist´ıa en la construcci´on de sistemas complejos bas´andose en peque˜nos robots que se comunicaban entre ellos e interactuaban para 12 Introducci´on realizar una tarea concreta. Por esta misma ´epoca (finales de los 80 y principios de los 90) surgieron otros trabajos basados en la misma idea, como el proyecto ACTRESS (ACTor-based Robot and Equipments Synthetic System), un sistema rob´otico distribuido formado por m´ultiples robots que pueden comunicarse entre ellos para realizar las tareas encomendadas, o el proyecto GOFER, con un enfoque similar al proyecto ACTREES pero incluyendo la posibilidad de comunicaci´on entre robot y el usuario. Pocos a˜nos despu´es, a mediados de los 90, surgi´o el proyecto ALLIANCE, cuyo objetivo era conseguir una cooperaci´on tolerante a fallos entre robots heterog´eneos, pudiendo reaccionar a cambios en el entorno, errores mec´anicos o eliminaci´on de algunos robots del equipo, por ejemplo. A finales de los 90 surgen los proyectos M+, un sistema distribuido para la cooperaci´on de m´ultiples robots que incluye planificaci´on y reparto de tareas as´ı como mecanismos de cooperaci´on basado en negociaci´on, y Murdoch, un sistema de asignaci´on de tareas para agentes heterog´eneos mediante un sistema de negociaci´on que permite escoger el agente m´as adecuado para cada tarea mediante un esquema suscriptor/publicador en el que cada agente se punt´ua seg´un su adecuaci´on a una tarea. Figura 1.6: Equipo de robots en la Robocup 2004.6 En esta ´epoca tambi´en tuvo lugar la primera RoboCup (Fig. 1.6), un proyecto internacional con distintas categor´ıas, cada una con un enfoque, pero con el objetivo com´un de impulsar y promover la investigaci´on en rob´otica 6Imagen p´ublica extra´ıda de: http://commons.wikimedia.org/wiki/File:Robocup. legged.leauge.2004.nk.jpg.´ Ultima visita: 07-09-2015 Objetivos de la tesis 13 aut´onoma, la IA y los MRS. Las distintas categor´ıas de la RoboCup son RoboCupSoccer (una competici´on de f´utbol con robots aut´onomos impulsando, entre otros, el estudio de los MRS y su coordinaci´on), la RoboCupRescue (cuyo objetivo es crear robots que ayuden en tareas de b´usqueda y rescate de personas), RoboCupJunior (cuyo objetivo es acercar la rob´otica a los m´as j´ovenes) y la RoboCupHome (cuyo objetivo es la realizaci´on de robots asistenciales que ayuden en las tareas diarias). La RoboCup tambi´en sirve como un gran laboratorio para la validaci´on de modelos rob´oticos (individuales y colectivos) tanto a nivel de simulaci´on como a nivel f´ısico. De esta forma, muchos de los trabajos de investigaci´on desarrollados dentro del ´area de la rob´otica est´an contenidos en parte o totalmente dentro de las distintas ´areas que componen la RoboCup. Por ´ultimo, a principios del 2000, se hayan otros trabajos como el proyecto ASyMTRe (Automated Synthesis of Multi-Robot Task Solutions through Software Reconfiguration), un sistema que automatiza la soluci´on de tareas en equipos de robots determinando como y quien realizar´a una tarea concreta, permitiendo afrontar las tareas con equipos de robots distintos de forma que unos robots apoyen a otros en caso de necesidad, o el proyecto Centibots, un ambicioso proyecto de la Universidad de Stanford con el apoyo de DARPA que ten´ıa como objetivo coordinar un gran n´umero de robots (100 robots, repartidos entre 80 Amigobots y 20 Pioneer 2 AT) para realizar la tarea de mapear una zona o ´area de inter´es. Todos estos trabajos e iniciativas, junto con muchos otros, han dando paso, poco a poco, al desarrollo de los MRS, siendo hoy un ´area activa de investigaci´on en la que todav´ıa quedan muchos problemas que resolver. Entre estos problemas, est´an la complejidad que pueden alcanzar estos sistemas, debido a las interacciones entre los robots y a todos los factores a tener en cuenta para no repetir tareas, evitar obstaculizarse mutuamente y, en definitiva, coordinarse correctamente para obtener los beneficios de un sistema distribuido. Otros problemas m´as espec´ıficos son, por ejemplo, la dependencia con el componente central en sistemas coordinados centralizados, que generalmente provoca un cuello de botella y ralentiza la coordinaci´on entre los robots, o las comunicaciones en sistemas con una gran cantidad de robots o en entornos donde ´estas est´an limitadas, lo que dificulta enormemente las posibilidades de coordinaci´on y la interacci´on en estos sistemas. 1.3. Objetivos de la tesis La investigaci´on en el ´area de los MAS y MRS comenz´o hace ya bastantes a˜nos (en la d´ecada de los 70), sin embargo no ha sido hasta hace pocos a˜nos, 14 Introducci´on cuando la rob´otica y la tecnolog´ıa han alcanzado una suficiente madurez, que se ha podido estudiar m´as a fondo y de una forma m´as realista y pr´actica en estos ´ambitos. Los MAS est´an englobados directamente dentro del ´area de la Inteligencia Artificial Distribuida, un campo de la IA, y est´an formados por un conjunto de entidades o agentes aut´onomos que ayudan a resolver un determinado problema [93]. Por lo tanto, desde el punto de vista de la Inteligencia Artificial Distribuida un agente puede ser definido como un elemento, que forma parte de un conjunto m´as grande, que ayuda a resolver un problema que no podr´ıa resolver de forma individual [93]. Como se puede observar, la definici´on de agente es bastante vaga y gen´erica. De hecho, no existe una definici´on formal y precisa de lo que es un agente aut´onomo [123], ya que existe una gran cantidad de agentes distintos y es dif´ıcil dar una definici´on exacta. Sin embargo, existen algunas definiciones de agente algo m´as concretas o, al menos, m´as precisas que la dada anteriormente. As´ı pues, se puede considerar que un agente es cualquier entidad en un entorno que es capaz de percibir dicho entorno y actuar de forma aut´onoma interactuando con ´el [123]. Teniendo en cuenta esta definici´on, un agente podr´ıa ser un programa software, un robot o incluso una persona [141]. De hecho, un MRS puede verse como un caso concreto de MAS [52,152] en el que cada robot puede ser considerado como un agente con la habilidad de solucionar unas tareas locales y coordinarse con sus compa˜neros [152]. As´ı pues, y aunque hay diferencias conceptuales entre ellos, pero s´ı que existe una relaci´on entre los MAS y los MRS, pues ambos requieren una coordinaci´on entre los agentes o robots para que el conjunto del sistema pueda realizar tareas que, individualmente, no son capaces de realizar los elementos que lo componen. El inter´es en los MRS y los MAS rob´oticos estriba en que los sistemas formados por m´ultiples robots ofrecen una serie de ventajas frente a los sistemas rob´oticos individuales [9], como son: mayor robustez, ya que al tratarse de un sistema formado por distintos robots en caso de que un robot fallase los dem´as robots podr´ıan seguir realizando su labor, si bien la tarea global tardar´ıa m´as en realizarse. mayor adaptabilidad, ya que al repartirse las tareas es m´as f´acil adaptarse a cambios en el entorno, pues cada robot s´olo tendr´a que adaptarse a los factores que le afecten directamente seg´un su tarea concreta, mientras que si se tratase de un ´unico robot tendr´ıa que adaptarse a todos los factores que afronta cada uno de los robots por separado. Adem´as, si los distintos robots que forman el sistema est´an especializados en una tarea concreta, es m´as f´acil que se adapten a un problema concreto que un robot adapt´andose a todos los problemas espec´ıficos que surjan. Objetivos de la tesis 15 mayor flexibilidad, en parte relacionado con las dos anteriores, pues en caso de fallo o cambios externos, el sistema es potencialmente m´as flexible pudiendo reasignar las tareas, o bien unificar todos los robots en una ´unica tarea para actuar como un ´unico robot. Es por esto que los MRS se usan en aplicaciones complejas y que requieren robustez o abarcar un gran ´area r´apidamente, como por ejemplo el mapeo de terrenos, ambientes hostiles o peligrosos [42], tareas militares [63, 95], operaciones de rescate [87], etc. Por otro lado, no todo son ventajas, ya que el coste de estos beneficios es el correcto dise˜no de un sistema que, en general, es m´as complejo que el dise˜no de un robot aut´onomo individual, pues es necesaria una correcta coordinaci´on y cooperaci´on entre los distintos elementos del sistema para su correcto funcionamiento. Sin embargo, el problema de la coordinaci´on de los distintos robots de un MRS deriva en otros problemas o decisiones m´as espec´ıficas como son la arquitectura, la heterogeneidad del sistema, la comunicaci´on entre los miembros del equipo, el reparto de tareas entre los robots o el aprendizaje entre otros. Por lo tanto, el desarrollo de un MRS supone una serie de decisiones y especificaciones que afectar´an al desarrollo del sistema final. As´ı pues, en la presente tesis, el objetivo es el desarrollo de un sistema de coordinaci´on multi-agente basado en el aprendizaje de comportamientos. La coordinaci´on entre los agentes es impl´ıcita pues en un MAS una de las caracter´ısticas de los agentes es que son aut´onomos y act´uan por s´ı mismos, sin haber un elemento que centralice las acciones de los distintos agentes. Sin embargo, eso ni impide que los agentes puedan conocer la existencia de los dem´as agentes ni se transmitan entre ellos de forma expl´ıcita informaci´on sobre el entorno y su propio estado. La implementaci´on de los comportamientos se realiza mediante aprendizaje en vez de mediante algoritmos anal´ıticos porque el aprendizaje puede ofrecer una mayor libertad y facilidad a la hora desarrollar comportamientos que no se ajusten f´acilmente a una ecuaci´on anal´ıtica. Concretamente, dentro de las distintas t´ecnicas de aprendizaje se usa Aprendizaje por Demostraci´on (LfD) (Learning from Demonstration en ingl´es) [8, 130] porque es una t´ecnica que asocia una acci´on a un estado y consiste en entrenar un comportamiento espec´ıfico a partir de ejemplos provistos por un usuario supervisor, lo cual permite un entrenamiento sencillo, pues tan s´olo es necesario controlar el robot para que realice el comportamiento que quiere que se aprenda, y adem´as, permite absorber, impl´ıcitamente durante el aprendizaje, distintos factores dif´ıciles de modelar, como imperfecciones en los robots (derivas en el movimiento debido a que los motores no est´an correctamente alineados), errores 16 Introducci´on en los sensores, ruido, etc. As´ı pues, esta t´ecnica de aprendizaje solventa uno de los problemas que supone trabajar con robots: su modelado. Dentro del aprendizaje por demostraci´on se ha seleccionado la t´ecnica de aprendizaje Razonamiento Basado en Casos (CBR) en vez de otras como aprendizaje basado en ´arboles de decisi´on o aprendizaje bayesiano, porque el CBR resulta muy intuitivo y f´acil de comprender y, sobre todo, porque encaja a la perfecci´on con el concepto de comportamiento reactivo, cuyo principio de funcionamiento consiste en acoplar las entradas de los sensores a los actuadores o, expresado de otra forma, asociar una situaci´on a una soluci´on, que es lo que hace el CBR. Por ´ultimo, este sistema ha sido probado con robots AIBO ERS-7 de Sony, conectados mediante WiFi y usando localizaci´on visual mediante marcas artificiales de colores en un entorno similar al de la competici´on rob´otica de f´utbol Robocup. Para ello se han entrenado comportamientos simples, como correr por la banda, ir a porter´ıa o evitar a un oponente, y se han combinado mediante una capa superior que los activa y desactiva seg´un la situaci´on lo requiera. 1.4. Estructura de la tesis La presente tesis est´a dividida en los siguientes cap´ıtulos: Capitulo 2: Arquitectura de control y sistema de navegaci´on. En este cap´ıtulo se presenta un estado del arte de las arquitecturas de control y sistemas de navegaci´on m´as usuales. Tras la presentaci´on de cada una de las opciones disponibles, se seleccionar´a las m´as adecuada al sistema que se desea desarrollar. Concretamente, la arquitectura de control usada ser´a una arquitectura h´ıbrida, formada por una capa de bajo nivel basada en comportamientos aprendidos y una de alto nivel que permite la activaci´on o desactivaci´on de estos. As´ı pues, en los cap´ıtulos 3 y 5 se presentar´a la implementaci´on la capa reactiva para comportamientos individuales y coordinados respectivamente, a la que se a˜nadir´a finalmente una capa de m´as alto nivel (cap´ıtulo 6) que los activa y desactiva para permitir obtener comportamientos emergentes m´as complejos. Capitulo 3: Aprendizaje de comportamientos b´asicos. En este cap´ıtulo se presenta la implementaci´on de comportamientos aprendidos mediante CBR (Case-Based Reasoning en ingl´es). El CBR es una t´ecnica para aprendizaje y adaptaci´on que ayuda a resolver problemas actuales mediante la recuperaci´on y adaptaci´on de experiencias pasadas, y se ha Estructura de la tesis 17 escogido porque encaja a la perfecci´on con el enfoque de navegaci´on basada en comportamientos. Como t´ecnica de aprendizaje se usar´a LfD. Por ´ultimo, en este capitulo se aplica el enfoque propuesto para la creaci´on de comportamientos aprendidos a una prueba de concepto que consiste en el aprendizaje de unos comportamientos simples aplicados a un ´unico robot AIBO. El objetivo en este cap´ıtulo es comprobar la idoneidad del aprendizaje basado en CBR para el aprendizaje de comportamientos que, en posteriores cap´ıtulos, permitir´an la coordinaci´on de varios robots. Capitulo 4: Sistema de localizaci´on. El objetivo final de esta tesis es realizar un sistema coordinado multiagente, para lo cual es necesario tener una referencia de las posiciones de los distintos agentes del sistema, bien de forma relativa entre ellos o de forma absoluta. As´ı pues, en este cap´ıtulo se realiza una breve presentaci´on de las distintas t´ecnicas de localizaci´on disponibles. Dado que el enfoque inicial del sistema ha sido un enfoque reactivo, se tratar´a de usar una t´ecnica de localizaci´on que sea lo m´as reactiva posible, teniendo en cuenta que el hecho de usar una localizaci´on ya implica que el sistema no ser´a totalmente reactivo. Tras realizar distintas pruebas, en este cap´ıtulo se concluye que las opciones m´as viables para el sistema de localizaci´on son el uso de localizaci´on basada en marcas fiduciarias (primera opci´on seleccionada) o localizaci´on basada en marcas visuales artificiales corrigiendo el posicionamiento mediante filtrado (opci´on m´as estable pero menos reactiva que la anterior). Capitulo 5: Coordinaci´on reactiva basada en aprendizaje. Tras presentar el algoritmo de navegaci´on (aprendizaje por demostraci´on basado en CBR) en el cap´ıtulo 3 y la t´ecnica de localizaci´on a usar (localizaci´on basada en marcas fiduciarias) en el cap´ıtulo 4, se propone la aplicaci´on de este mismo enfoque para la creaci´on de comportamientos coordinados mediante aprendizaje. Para ello, en este cap´ıtulo se muestran los resultados de una prueba de concepto basada en este enfoque que permite la coordinaci´on de dos robots mediante el uso de CBR. En estas pruebas preliminares el sistema se basar´a ´unicamente en una capa reactiva y la localizaci´on se basar´a en marcas ARToolkit. Tras los experimentos, en este cap´ıtulo se comprueba la correcta coordinaci´on de los robots mediante comportamientos aprendidos, aunque tambi´en se encuentran algunos problemas e inconvenientes que se solventar´an o minimizar´an en el cap´ıtulo 6. Capitulo 6: Coordinaci´on h´ıbrida basada en aprendizaje. En este ´ulti- 24 Arquitectura de control y sistema de navegaci´on Figura 2.2: Esquemas de navegaci´on reactivo (a), deliberado (b) e h´ıbrido (c). esquema est´a inspirado en la idea de imitar los actos reflejos o reacciones instintivas, que en esta arquitectura se suelen llamar conductas o comportamientos. Esta arquitectura ofrece una forma de determinar las distintas acciones a realizar mediante la combinaci´on de conductas o comportamientos activados seg´un la informaci´on recibida de los sensores, bas´andose en la idea de que la uni´on de comportamientos o conductas de bajo nivel da como resultado un comportamiento o conducta m´as complejo, conocido como comportamiento emergente. As´ı pues, en un esquema de navegaci´on reactiva pura ´unicamente se tiene en cuenta la informaci´on que se obtiene en el instante actual, y no informaci´on obtenida anteriormente. Este esquema, por lo tanto, sigue un enfoque desde abajo hacia arriba, en el sentido de que las acciones surgen de las capas de bajo nivel, generando como resultado una acci´on m´as compleja y de m´as alto nivel que las originales. Dado el esquema de funcionamiento de un esquema reactivo, no es necesario un modelado del entorno, ya que la informaci´on recibida directamente de los sensores se acopla a los actuadores del robot mediante una funci´on de transferencia concreta, que es lo que se conoce como comportamiento. Por lo tanto, en estos esquemas no es posible esta- Arquitectura de control 25 blecer el posicionamiento del robot respecto a un modelo del entorno, ya que no hay. Sin embargo, y debido a su simplicidad, estos esquemas son r´apidos y robustos frente a errores en los sensores y ruido [138]. Adem´as, y por la propia naturaleza de este esquema, se ajusta muy bien a ambientes altamente din´amicos o cambiantes [136]. Por otro lado, el comportamiento emergente resultante puede ser impredecible, no necesariamente eficiente [135] y adem´as no se asegura que se pueda alcanzar el objetivo a pesar de que exista alguna forma de llegar, pues este esquema puede caer en m´ınimos locales al hacer uso ´unicamente de la informaci´on actual [138]. Otro problema a tener en cuenta en este esquema es que no es f´acil establecer la coordinaci´on entre los distintos comportamientos de forma adecuada [147]. Dos de las arquitecturas m´as conocidas dentro de los esquemas reactivos son la arquitectura Subsunci´on y el esquema de motor [88], estando el primero enfocado a la competici´on entre comportamientos y el segundo a la cooperaci´on entre ellos. Navegaci´on h´ıbrida o reactiva-deliberada. Esta arquitectura de control surgi´o posteriormente a las arquitecturas deliberativas y reactivas para solucionar sus debilidades pero aprovechando las ventajas de ambas [147]. As´ı pues, este esquema obtiene la ventaja de la planificaci´on y optimizaci´on de los esquemas deliberados y la capacidad de respuesta ante entornos din´amicos o desconocidos de los esquemas reactivos. Los esquemas h´ıbridos [88, 144] est´an normalmente formados por una capa de bajo nivel reactiva, una capa de alto nivel deliberativa y una de control entre ambos (Fig. 2.2.c). De esta forma, la capa de bajo nivel reactiva permite una r´apida respuesta ante cambios en el entorno mientras que la capa de alto nivel deliberativa ofrece un posicionamiento respecto al entorno o a un modelo de ´este y una soluci´on ´optima para alcanzar el destino [147]. Aunque existen una gran variedad de arquitecturas h´ıbridas, una de las m´as conocidas y usadas es la arquitectura en tres capas o arquitectura 3T (del ingl´es 3 Tier) [135], formada por las 3 capas ya comentadas (deliberada, reactiva y de control), y de la cual derivan muchas de las arquitecturas de control actuales. Como es l´ogico, cuando el entorno de trabajo es un entorno din´amico o no totalmente conocido, las arquitecturas de control m´as adecuadas son las arquitecturas reactivas e h´ıbridas, pues son capaces de adaptarse a estos entornos respondiendo con suficiente velocidad. Sin embargo, y dado que las arquitecturas h´ıbridas ofrecen unas mejores prestaciones en general que las 26 Arquitectura de control y sistema de navegaci´on arquitecturas reactivas (Tabla 2.1), lo m´as usual es el uso de arquitecturas h´ıbridas [88], siendo de hecho usada en una gran variedad de robots y entornos distintos [18,54,56,98,116,135]. Por lo tanto, la arquitectura de navegaci´on usada en el presente trabajo ser´a una arquitectura h´ıbrida. Caracter´ısticas Deliberativo Reactivo H´ıbrido Flexibilidad del sistema Muy malo Muy bueno Muy bueno Tiempo de respuesta Muy malo Muy bueno Bueno Soluci´on ´optima Muy bueno Muy malo Bueno Robustez del sistema Regular Bueno Muy bueno Capacidad de planificaci´on Muy bueno Regular Bueno Tabla 2.1: Caracter´ısticas m´as destacadas de las arquitecturas de control. Concretamente, la arquitectura del sistema se comenzar´a por la definici´on e implementaci´on de la capa reactiva, a˜nadiendo capas de nivel superior seg´un se vayan necesitando para la implementaci´on del sistema. As´ı pues, y aunque la arquitectura del sistema ser´a una arquitectura h´ıbrida, en el presente cap´ıtulo y en los cap´ıtulos 3 y 5 se tratar´a s´olo de la implementaci´on la capa reactiva para comportamientos individuales y coordinados respectivamente. Como ya se ha comentado, la idea principal de los comportamientos reactivos es la de usar comportamientos simples (que acoplan los sensores con los actuadores) de forma que de la interacci´on que tiene lugar entre los distintos comportamientos individuales surja un comportamiento m´as complejo llamado comportamiento emergente [9]. En los pr´oximos apartados se desarrollar´a la implementaci´on de estos comportamientos. 2.4. Sistema de navegaci´on Una vez determinada la arquitectura de control, es necesario determinar como se implementar´a el sistema de navegaci´on. Como ya se ha comentado, el sistema de navegaci´on ser´a inicialmente reactivo, a˜nadi´endose capas de nivel superior seg´un sea necesario. As´ı pues, actualmente s´olo se tratar´a la capa de navegaci´on a nivel reactivo. La navegaci´on rob´otica es un problema que ha sido estudiado desde los or´ıgenes de la rob´otica aut´onoma, existiendo una gran variedad de opciones y enfoques distintos. Sin embargo, todos ellos se pueden englobar en dos grupos generales, que son: la navegaci´on mediante algoritmos anal´ıticos y la navegaci´on mediante aprendizaje. Sistema de navegaci´on 27 El enfoque anal´ıtico tiene su origen en la rob´otica cl´asica y busca una soluci´on gen´erica, predecible y repetible mediante una formulaci´on matem´atica. Este enfoque suele ser m´as sencillo de implementar cuanto m´as conocido y controlado sea el entorno de trabajo. Por su parte, el enfoque basado en aprendizaje busca, por lo general, una soluci´on mediante el entrenamiento a trav´es de un experto o a trav´es de informaci´on disponible del entorno, pudiendo llegar a desarrollar esquemas de navegaci´on m´as flexibles que la navegaci´on basada en algoritmos anal´ıticos, aunque su generalidad y predictibilidad depender´an en gran medida de cu´an exhaustivos sean los entrenamientos o la informaci´on disponible del entorno. A continuaci´on se describen con mayor detalle cada uno de estos paradigmas y las distintas alternativas disponibles dentro de cada uno de ellos. 2.4.1. Navegaci´on anal´ıtica La navegaci´on mediante algoritmos anal´ıticos es la navegaci´on m´as conocida y usual siendo, de hecho, los primeros algoritmos de navegaci´on usados. Este enfoque busca modelar anal´ıticamente, mediante una f´ormula matem´atica, el comportamiento de navegaci´on del robot. As´ı pues, cuanto m´as conocido y controlado sea el entorno de trabajo m´as f´acil ser´a determinar la f´ormula matem´atica para una correcta navegaci´on. La navegaci´on anal´ıtica se caracteriza por buscar una soluci´on gen´erica, para un entorno con unas caracter´ısticas concretas, predecible y repetible. Su inconveniente es que es bastante complejo caracterizar el comportamiento de navegaci´on completo si no se conocen a priori todas las situaciones que se deber´an afrontar o no se conoce perfectamente el entorno de pruebas, que es lo que suele ocurrir en entornos de pruebas reales. Por otro lado, este enfoque suele ser sensible a los par´ametros de configuraci´on del algoritmo, que se deben adaptar y optimizar para situaciones espec´ıficas, siendo su optimizaci´on compleja para situaciones generales. Es por esta misma raz´on que este enfoque es apropiado para entornos con circunstancias particulares, no siendo, en general, flexible cuando se trata con entornos cuya configuraci´on puede cambiar considerablemente, siendo necesario reajustar los par´ametros de configuraci´on del algoritmo para un comportamiento ´optimo. 2.4.1.1. M´etodo de Campos Potenciales La navegaci´on mediante el M´etodo de Campos Potenciales (PFA) [61], Potential Fields Approach en ingl´es, es uno de los esquemas de navegaci´on reactiva m´as conocidos y empleados debido a su sencillez y velocidad. Gracias a su simplicidad este esquema puede ser aplicado en entornos din´amicos no 28 Arquitectura de control y sistema de navegaci´on estructurados permitiendo una velocidad de respuesta r´apida ante obst´aculos inesperados. La navegaci´on mediante PFA considera al robot como una part´ıcula libre cargada que se haya bajo la influencia de un campo potencial, de forma que los obst´aculos tienen la misma carga que el robot y el objetivo una carga de polaridad distinta a la del robot. As´ı pues, los obst´aculos generan un campo de repulsi´on artificial alrededor suyo y el objetivo a alcanzar genera un campo potencial de atracci´on hacia ´el. Debido a la sencillez de este m´etodo, ha sido usado no s´olo en navegaci´on para la evitaci´on de obst´aculos sino tambi´en para tareas como selecci´on de comportamientos [83] o coordinaci´on [149]. Sin embargo, este esquema de navegaci´on tambi´en tiene algunos inconvenientes, como las oscilaciones o la ca´ıda en m´ınimos locales. La ecuaci´on general del PFA es: U(rob) = kat ·dist(rob, dest)2+Xkrep ·1 dist(rob, obs)2(2.1) Determinando las constantes kat ykrep (kat >0, krep <0) la mayor o menor atracci´on o repulsi´on al objetivo o a los obst´aculos respectivamente. As´ı pues, el vector de movimiento del robot (~vR) ser´a igual al gradiente negativo de dicho campo (−∇U(rob)). El PFA es un algoritmo de navegaci´on simple y genera unas trayectorias suaves a la vez que evita las colisiones con los obst´aculos. Sin embargo, tiene una serie de inconvenientes, como son [138]: Sensibilidad a la existencia de m´ınimos locales en el campo potencial. En el caso de que el robot alcance un m´ınimo local es posible que ´este se quede atrapado indefinidamente en ´el. Este problema puede ser resuelto mediante el uso de un esquema de navegaci´on h´ıbrido que evitase los m´ınimos locales. Generaci´on de oscilaciones en las cercan´ıas de obst´aculos. Dificultad o incapacidad para desplazarse por zonas con obst´aculos cercanos entre s´ı, como pasillos estrechos. Dependencia de los par´ametros de configuraci´on con el entorno. Este problema tiene relaci´on con los anteriores, ya que si en el entorno existen zonas estrechas por las que el robot debe pasar la configuraci´on de par´ametros tendr´a que disminuir el rango de seguridad del robot para permitir el acceso a dichas zonas, mientras que si las zonas de paso son suficientemente amplias se puede aumentar el rango de seguridad del robot con los obst´aculos. De esta forma, la configuraci´on de los Sistema de navegaci´on 29 par´ametros origina los anteriores problemas de oscilaciones as´ı como la imposibilidad o dificultad de atravesar obst´aculos cercanos entre s´ı. 2.4.1.2. Histograma de Campo de Vectores La navegaci´on mediante Histograma de Campo de Vectores (VFH) [23], Vector Field Histogram en ingl´es, se basa en la representaci´on estad´ıstica del entorno del robot. Concretamente, lo que hace es representar en un histograma la densidad de obst´aculos del entorno. Esta t´ecnica permite determinar las regiones del entorno donde hay una menor densidad de obst´aculos, de forma que el robot se dirija a estas regiones preferentemente. Este algoritmo fue dise˜nado para ser eficiente, robusto y presta especial atenci´on a la incertidumbre de los sensores y al modelado de los errores. Esto es debido a la representaci´on estad´ıstica de los obst´aculos (mediante un histograma de ocupaci´on de celdas), la cual es especialmente interesante cuando hay errores en los sensores. El funcionamiento del VFH se basa en una representaci´on bidimensional de los obst´aculos, que es transformada en un histograma polar de una dimensi´on a partir de la posici´on actual del robot. Una vez realizado ´esto, se selecciona la direcci´on a seguir como el ´angulo en el que la densidad de obst´aculos sea inferior a un determinado umbral, as´ı como el ´angulo m´as pr´oximo a la direcci´on del destino. Finalmente, se dirige el robot en la direcci´on establecida. Este algoritmo fue mejorado posteriormente [134] (llam´andose VFH+ y posteriormente VFH*) para tener en cuenta en el proceso de navegaci´on el tama˜no del robot, reducir las oscilaciones del m´etodo original, aumentar la eficiencia y evitar m´ınimos locales. Funciona bien y ofrece una buena respuesta temporal, sin embargo tiene varios inconvenientes, como que no es capaz de dirigirse intencionadamente hacia un obst´aculo una vez detectado y que se ralentiza en la presencia de una gran cantidad de obst´aculos. Por otro lado, y como ocurre en general con los esquemas anal´ıticos, es sensible a los par´ametros de configuraci´on. 2.4.1.3. Ventana Din´amica La navegaci´on mediante el M´etodo de Ventana Din´amica (DWA), Dynamic Windows Approach en ingl´es, es una t´ecnica para evitar obst´aculos [38] basada en la din´amica del robot y est´a especialmente dise˜nada para poder tratar con las limitaciones de velocidad y aceleraci´on del robot. Para ello se genera un espacio de b´usqueda de posibles rutas y luego se busca la soluci´on ´optima dentro del espacio de b´usqueda establecido impo- 30 Arquitectura de control y sistema de navegaci´on niendo las restricciones de velocidad y aceleraci´on iniciales. De esta forma se busca la trayectoria ´optima que permite alcanzar la meta de una forma segura y con la m´ınima cantidad posible de obst´aculos dentro del intervalo de tiempo actual. Esta trayectoria se va calculando para cada intervalo de tiempo, de forma que si en un intervalo de tiempo se puede aproximar demasiado a un obst´aculo a la velocidad actual, esta se reduce, por ejemplo. Visto de otro modo, este algoritmo comprueba todas las posibles velocidades que puede alcanzar el robot de una forma segura (sin colisiones) en una determinada ventana temporal, por lo que permite navegar al robot a altas velocidades por el entorno de pruebas. Estas velocidades son optimizadas teniendo en cuenta una serie de funciones relacionadas con la distancia a la meta y a los obst´aculos m´as cercanos. 2.4.1.4. Bandas El´asticas La navegaci´on mediante Bandas El´asticas [105], Elastic Bands en ingl´es, consiste en deformar una trayectoria que permita alcanzar el destino deseado (trayectoria que ser´a calculada por un planificador de caminos) en funci´on de unas fuerzas artificiales que se crean a partir de la distribuci´on de obst´aculos presentes en el entorno. La trayectoria resultante de la deformaci´on de las bandas el´asticas es, por lo general, suave y eficiente, siendo una t´ecnica adecuada para entornos parcialmente conocidos en los que la trayectoria calculada por el planificador previo sea v´alida a largo plazo y no deba ser recalculada constantemente. La principal ventaja de este algoritmo es evitar a los planificadores de alto nivel el c´alculo de una nueva ruta ante peque˜nos cambios en el entorno, aplicando modificaciones a la ruta original en tiempo real. Sin embargo, cuando el entorno de aplicaci´on es desconocido o muy din´amico esta t´ecnica no es adecuada, pues una desviaci´on excesiva de la ruta original puede causar que ´esta se vuelva insegura o no fiable. Otro problema de esta t´ecnica, es la sensibilidad con los par´ametros de configuraci´on, siendo complejo un ajuste ´optimo para circunstancias no predecibles. 2.4.1.5. Diagrama de Proximidad La navegaci´on basada en Diagrama de Proximidad (Nearness Diagram) es, en su concepci´on, muy parecido al VFH, ya que consiste en dividir los 360 grados alrededor del robot en sectores, almacenando cada uno de estos sectores la proximidad de los obst´aculos que contiene. De esta forma se estima la proximidad de los obst´aculos al centro del robot y se calcula el camino libre de obst´aculos m´as cercano a la direcci´on en la que se encuentra el destino. Existen modificaciones de este m´etodo, en las que se indica la proximidad Sistema de navegaci´on 31 de los obst´aculos respecto a la parte exterior del robot, por lo que esta modificaci´on permite su aplicaci´on a robots con distintas formas y tama˜nos m´as f´acilmente que el algoritmo original, estimando de una forma m´as correcta la seguridad durante el recorrido. Su principal ventaja respecto al VFH es que se comporta mejor que ´este en entornos con una gran cantidad de obst´aculos. Su principal problema, es el mismo que ya se ha comentado con los dem´as algoritmos anal´ıticos, y es la necesidad de ajustar adecuadamente los par´ametros de configuraci´on del algoritmo para obtener un resultado ´optimo en cada entorno. 2.4.2. Navegaci´on basada en inteligencia artificial La navegaci´on basada en aprendizaje tienen su origen en la IA y los algoritmos de aprendizaje surgidos de ´esta. El aprendizaje puede ser definido como cualquier cambio en un sistema que permita realizar una tarea mejor la siguiente vez que se realice o que permite realizar una tarea que antes no se pod´ıa hacer [132], pudiendo manifestarse este aprendizaje como conocimiento obtenido por observaci´on o aprendizaje, por ejemplo. Por lo tanto, la navegaci´on basada en aprendizaje intenta solventar algunos de los problemas de la navegaci´on mediante m´etodos anal´ıticos permitiendo el movimiento del robot mediante el conocimiento y la experiencia adquirida por el sistema. As´ı pues, las t´ecnicas basadas en aprendizaje suelen basarse en la capacidad de imitar la percepci´on, aprendizaje y razonamiento humanos para solventar problemas complejos [28]. Sin embargo, y como todas la t´ecnicas, tiene sus ventajas y desventajas. Una de las ventajas de este enfoque es la flexibilidad que ofrece frente a los enfoques anal´ıticos, m´as r´ıgidos al tratar de resolver todas las posibles situaciones que debe afrontar el robot mediante una ecuaci´on anal´ıtica. El m´etodo basado en aprendizaje, por su parte, pretende particularizar la respuesta del sistema seg´un el escenario en el que se encuentre, ofreciendo mayor flexibilidad al permitir aprender comportamientos concretos para cada situaci´on espec´ıfica, lo cual es dif´ıcil conseguir mediante algoritmos anal´ıticos. Por lo tanto, el enfoque basado en aprendizaje ofrece una alternativa a la resoluci´on de problemas complejos mediante la simplificaci´on de dichos problemas particularizando seg´un cada circunstancia espec´ıfica. Por su parte, la desventaja de este tipo de navegaci´on es la falta de generalidad, pues es dif´ıcil conseguir un aprendizaje lo bastante completo como para poder afrontar cualquier situaci´on posible. La forma de solucionar este problema es aumentar el entrenamiento y conocimiento almacenado por el robot para incluir mayor cantidad de situaciones a afrontar. Sin embargo, lo m´as usual es realizar un aprendizaje que permita disponer de distintos com- 32 Arquitectura de control y sistema de navegaci´on portamientos para las situaciones m´as usuales a afrontar, lo que permitir´ıa seleccionar el comportamiento m´as adecuado en cada situaci´on, solventando parcialmente el problema. A continuaci´on se describen algunas de las t´ecnicas de IA m´as usuales basadas o usadas en aprendizaje [28], como son el CBR (Case-Based Reasoning en ingl´es), las Redes Neuronales Artificiales (ANN) (Artificial Neuronal Network en ingl´es) o los Sistemas Basados en Reglas (RBS) (Rule-Based System en ingl´es). 2.4.2.1. Razonamiento basado en reglas Los sistemas basados en reglas (RBS) tuvieron sus or´ıgenes en torno a los a˜nos 70, y se basan en la soluci´on de problemas mediante la representaci´on expl´ıcita del conocimiento a trav´es de un conjunto de reglas heur´ısticas generadas por un experto en el ´area [46], siendo una regla una expresi´on formada por una condici´on y una acci´on a realizar en caso de que se cumpla la condici´on. Los sistemas RBS suelen estar formados por varios m´odulos que almacenan las variables y conjunto de reglas del sistema (base de conocimiento), que comprueban si se cumplen o no las condiciones de las distintas reglas (motor de inferencia), que determinan si las reglas se deben aplicar y en que orden y, por ´ultimo, que ejecutan las acciones asociadas a las reglas. Uno de los problemas de este tipo de sistemas es que las reglas deben estar correctamente definidas para solucionar el problema deseado, por lo que es necesario tener un gran conocimiento de dicho problema y que ´este sea comprensible para poder establecer las reglas correctas [28]. Es por esto que los RBS suelen aplicarse fundamentalmente a problemas bien estructurados que pueden ser descritos con relativa facilidad por un conjunto de reglas deterministas bien definidas, como un sistema de control de tr´afico, sistemas de seguridad o transacciones bancarias. Otro problema de estos sistemas es que no son adecuados cuando existen un elevado n´umero de excepciones o situaciones particulares, ya que en estos casos el n´umero de reglas necesarias para describir dichas situaciones ser´ıa muy elevado lo que har´ıa el sistema muy complejo y dif´ıcil de mantener, pudiendo adem´as degradar su respuesta. Como es obvio, y por esta misma raz´on, estos sistemas no suelen proporcionar soluciones adecuadas cuando se pretenden resolver circunstancias excepcionales e imprevistas no contenidas en el conjunto de reglas del sistema. As´ı pues, es conveniente aplicarlos en entornos donde no haya una gran cantidad situaciones excepcionales o bien restringir o limitar las condiciones del entorno para evitar dichas situaciones. Otras situaciones en las que no son convenientes aplicar los RBS es en sis- Sistema de navegaci´on 33 temas cuyas interacciones son complejas o los procesos que tienen lugar no se entienden completamente. As´ı por ejemplo, los RBS son usados en entornos relativamente cerrados con condiciones espec´ıficas (en los que se pueden aplicar reglas m´as generales), como por ejemplo en la identificaci´on de enfermedades espec´ıficas en animales o cultivos [76,154] o en la identificaci´on de elementos como nombres propios, organizaciones o localizaciones en texto no estructurado [3]. 2.4.2.2. Redes neuronales artificiales Las redes neuronales artificiales (ANN) son unas de las t´ecnicas de IA m´as cl´asicas, y est´an basadas en el funcionamiento de las neuronas biol´ogicas. Las ANN son ampliamente utilizadas y desde su origen han sido aplicadas a una multitud de ´areas como: clasificaci´on de patrones [94], clustering [145], funciones de aproximaci´on [29], predicci´on [128], optimizaci´on o control [13]. Figura 2.3: Red neuronal y estructura interna de una neurona. Las ANN est´an compuestas por una gran cantidad de neuronas interconectadas entre s´ı (Fig. 2.3) siendo la unidad b´asica de procesamiento la neurona. El funcionamiento b´asico de una neurona consiste, simplemente, en realizar una suma ponderada (por los pesos de cada entrada) de los distintos valores de entrada de la neurona, aplicando el valor obtenido a una funci´on de activaci´on para determinar si la neurona est´a activa o no. As´ı pues, para que una ANN funcione, antes es necesario realizar un entrenamiento de ´esta, que permitir´a configurar de forma adecuada los pesos [91] de las distintas entradas de las neuronas que forman la ANN, permitiendo as´ı obtener la respuesta esperada. De esta forma, las ANN son capaces de inducir conocimiento sobre el comportamiento de un sistema a partir de la informaci´on de dicho sistema. 40 Arquitectura de control y sistema de navegaci´on pruebas del sistema. De entre ambas opciones, se ha escogido la arquitectura h´ıbrida pues en general ofrece unas mejores prestaciones que las arquitecturas reactivas. Sin embargo, dado que actualmente no es necesaria ninguna capa de alto nivel, se ha comenzado por la capa reactiva de bajo nivel, a la que se a˜nadir´an posteriormente, seg´un se considere necesario, capas superiores para hibridizar el sistema y permitir respuestas m´as complejas. As´ı pues, actualmente el sistema se puede considerar que es un sistema reactivo, hasta que se le a˜nada alguna capa de nivel superior. Respecto al algoritmo de navegaci´on, si bien la soluci´on m´as cl´asica y usual es utilizar un algoritmo anal´ıtico como PFA o DWA, en el presente caso se ha optado por una implementaci´on basada en aprendizaje. La raz´on es que el aprendizaje permite una mayor libertad a la hora de definir las posibles trayectorias a realizar o las posibles respuestas del sistema. Por contra, tienen problemas como que no ofrecen siempre respuestas seguras (por lo que es conveniente a˜nadir un control de seguridad para detener el robot en caso de peligro) o que la obtenci´on de la informaci´on necesaria para el aprendizaje puede resultar a su vez compleja y tediosa. Sin embargo, se considera que las ventajas que ofrece el uso de una t´ecnica basada en aprendizaje puede ser interesante frente al enfoque cl´asico. As´ı pues, y concretamente dentro de las distintas t´ecnicas de aprendizaje, como pueden ser ANN, RBS o CBR, se ha escogido esta ´ultima, principalmente por su transparencia y posibilidad de depuraci´on y acceso a la informaci´on aprendida, lo que permite, en caso de problemas, determinar o intentar determinar que est´a pasando, porqu´e e incluso tratar de buscar una soluci´on, algo que en el caso de las otras t´ecnicas, m´as opacas en ese sentido, no es f´acil de conseguir. Cap´ıtulo 3 Aprendizaje de comportamientos b´asicos 3.1. Introducci´on El uso de los MRS puede ofrecer ventajas frente al uso de los sistemas rob´oticos individuales. Sin embargo, el uso de los MRS supone tener que resolver los mismos problemas que en robots individuales, m´as una serie de problemas a˜nadidos derivados de la coordinaci´on y cooperaci´on de los robots que forman el sistema. As´ı pues, en primer lugar se solucionar´an los problemas relativos a robots individuales, para pasar posteriormente a los problemas propios de los MRS, como la coordinaci´on. Como ya se ha comentado en el cap´ıtulo 2, los robots usar´an una arquitectura h´ıbrida para navegaci´on. Sin embargo, dado que inicialmente no se realizar´an tareas de alto nivel, en primer lugar se plantear´a ´unicamente el desarrollo de la capa navegaci´on reactiva de los robots, la cual se implementar´a mediante comportamientos aprendidos usando CBR, a˜nadiendo posteriormente capas de alto nivel seg´un se consideren necesarias. As´ı pues, en el presente cap´ıtulo se estudia un m´etodo simple y directo, alternativo al cl´asico m´etodo anal´ıtico, que permite ense˜nar comportamientos a un robot para que se mueva siguiendo unos determinados patrones de navegaci´on de una forma sencilla y c´omoda. La idea b´asica de este m´etodo consiste en relacionar la informaci´on visual que obtiene el robot con los comandos de movimiento que est´a realizando en un instante determinado mediante un comportamiento aprendido. Para ello se usar´a aprendizaje LfD controlando remotamente al robot. Concretamente, el entrenamiento consistir´a en controlar remotamente el robot para que realice unas trayectorias determinadas, que determinar´an el comportamiento 41 42 Aprendizaje de comportamientos b´asicos reactivo. De esta forma, durante el aprendizaje lo que se hace es relacionar directamente los comandos de movimiento enviados al robot con los par´ametros extra´ıdos de la imagen, los cuales est´an asociados a la situaci´on espec´ıfica en la que se ejecutan dichos comandos. Una de las ventajas de este enfoque es que para poder obtener comportamientos con distintas respuestas, tan s´olo es necesario entrenar de nuevo el sistema en el nuevo comportamiento deseado. Otras ventajas son que no es necesario realizar ning´un modelo cinem´atico expl´ıcito del robot y que los errores sistem´aticos y mec´anicos del robot (como por ejemplo que el robot gire m´as a la izquierda que a la derecha) son absorbidos impl´ıcitamente por el entrenamiento [47,102]. Esto es debido a que, cuando el operador controla el robot, impl´ıcitamente absorbe y asimila la estructura y movimientos del robot debido a la capacidad de adaptaci´on innata de las personas. As´ı pues, en primer lugar se presentar´a un breve estado del arte sobre la aplicaci´on del CBR en el ´area de la navegaci´on rob´otica (secci´on 3.2). Tras esto, en la secci´on 3.3 se comenta en m´as detalle el CBR, la t´ecnica seleccionada para realizar el aprendizaje de los comportamientos y, tras esto, se describir´a en profundidad el sistema implementado (secci´on 3.4). Posteriormente se aplicar´a el enfoque propuesto a dos tareas que servir´an de prueba de concepto para comprobar que el sistema propuesto puede ser viable para la implementaci´on de comportamientos reactivos aprendidos y, finalmente, se presentar´an los resultados (secci´on 3.5) y las conclusiones (secci´on 3.6) de dichos experimentos, indicando tanto las ventajas como las desventajas del enfoque seleccionado. 3.2. CBR aplicado a navegaci´on aut´onoma La t´ecnica de aprendizaje seleccionada para implementar los comportamientos aprendidos es el CBR. La raz´on es, por un lado, que esta t´ecnica permite un f´acil acceso a la informaci´on almacenada, lo que permite una depuraci´on y comprensi´on del sistema m´as f´acil que otras t´ecnicas de IA. Por otro lado, el funcionamiento del CBR se basa en almacenar experiencias, descritas mediante pares soluci´on-problema, para utilizarlas posteriormente en la resoluci´on de situaciones concretas. Por lo tanto, el CBR encaja perfectamente con la implementaci´on de un comportamiento reactivo, cuya base de funcionamiento es acoplar la informaci´on de los sensores (que define el problema actual) y a la acci´on o comando de movimiento del robot (que define la soluci´on al problema). Sin embargo, y a pesar del paralelismo que pueda existir entre el planteamiento del CBR y los comportamientos reactivos, el CBR no ha sido usado CBR aplicado a navegaci´on aut´onoma 43 generalmente para la navegaci´on reactiva. De hecho, las tareas relacionadas con la navegaci´on rob´otica en las que se ha usado el CBR han sido generalmente las siguientes: Selecci´on de comportamientos, estrategias de navegaci´on y par´ametros. En esta categor´ıa se muestran trabajos [15, 44, 68–71, 73,106, 114, 115, 125, 131] que usan el CBR para la selecci´on de comportamientos o estrategias de navegaci´on, por lo que se usa para navegaci´on de alto nivel, usando por debajo distintos tipos de algoritmos, desde secuencias de movimiento preestablecidas, hasta algoritmos anal´ıticos como PFA. Tambi´en se engloba en esta categor´ıa los trabajos orientados a la selecci´on de par´ametros para mejorar el algoritmo de navegaci´on usado, en general para que se adapte mejor a las circunstancias concretas. Estos trabajos se engloban en la misma categor´ıa que los de selecci´on de comportamiento pues, en muchos trabajos, estos unen la selecci´on de un comportamiento y sus par´ametros concretos mediante CBR para adaptarlos al entorno. As´ı por ejemplo, [69] propone un esquema que permite seleccionar, mediante CBR, los comportamientos a activar, as´ı como los par´ametros de dichos comportamientos, seg´un la situaci´on en tiempo real. De esta forma, los par´ametros usados por los comportamientos son m´as adecuados que si se usan unos par´ametros fijos. Este trabajo contin´ua el trabajo de [106] a˜nadiendo una representaci´on espacio-temporal del entorno que permite describir mejor las situaciones y obtener mejores respuestas por parte del CBR. Para ello, [69] crea una descripci´on espacial y temporal del entorno, de forma que primero se realiza en el CBR una b´usqueda de los casos m´as similares respecto a las caracter´ısticas espaciales, seleccionando entre ´estos, el que tenga una descripci´on temporal del entorno m´as similar al actual. Este enfoque fue posteriormente mejorado en [71] y [70] permitiendo el aprendizaje de nuevos par´ametros y la optimizaci´on de los casos ya almacenados. Otro trabajo similar, que parte tambi´en de [69], es [68], en el que se presenta un sistema para selecci´on de par´ametros (como la ganancia para dirigirse hacia la meta o evitar un obst´aculo o cuanto se puede aproximar a los obst´aculos) de los comportamientos que controlan la navegaci´on de un robot. Por otro lado, y centr´andose s´olo en la selecci´on de tareas, comportamientos y estrategias, hay otros trabajos como [73], que presenta un algoritmo de navegaci´on en dos fases en el que el CBR es usado para determinar los comportamientos a activar en funci´on de una serie de comandos gen´ericos. Concretamente, en una primera fase se determina, 44 Aprendizaje de comportamientos b´asicos mediante GA, una secuencia de comportamientos gen´ericos para realizar una tarea concreta en una plataforma gen´erica. Posteriormente, en una segunda fase, se aplican sobre una plataforma real estos comportamientos gen´ericos usando el CBR para determinar a que comportamientos concretos, se corresponde en esa plataforma el comportamiento gen´erico a ejecutar, seleccionando y activando los comportamientos en tiempo real. Siguiendo otro enfoque distinto, [125] presenta una arquitectura h´ıbrida aplicable a juegos en tiempo real, compuesta por una capa de alto nivel anal´ıtica, una capa intermedia basada en CBR y una capa reactiva con una serie de comportamientos y acciones en el juego, de forma que el CBR es usado para aprender que acciones son m´as adecuadas dependiendo de la situaci´on concreta del juego. En un enfoque algo m´as similar al presentado aqu´ı, [15,114] presentan un sistema basado en CBR para selecci´on de las acciones o secuencias de acciones de un equipo de robots AIBO en la competici´on Robocup. En este caso el CBR decide, a partir de una base de casos creada manualmente, que acci´on (pasar pelota, esquivar, etc.) deben realizar los robots dependiendo de la situaci´on concreta. Sin embargo, estos trabajos est´an orientados a estrategias de m´as alto nivel que el propuesto en este trabajo. Por otro lado, [115] presenta en un sistema con 4 capas (selecci´on de l´ıder o coordinador, selecci´on de estrategia y roles, asignaci´on de roles y ejecuci´on de estrategia) en el que el CBR se utiliza en la segunda capa para la selecci´on de estrategias y roles de un equipo de robots, consistiendo una estrategia en un plan de acci´on a largo plazo, indicando una serie de roles para los robots y las tareas que deben realizar. Por ´ultimo, [44,131] proponen un sistema basado en CBR para estimar el inter´es de una persona en interactuar con un robot. Concretamente, el CBR funciona como una capa de alto nivel que estima, partiendo de entrenamientos previos, el inter´es potencial de la persona en interactuar, determinando as´ı la estrategia de navegaci´on (basada en campos potenciales) que realizar´a el robot para tratar de interactuar con la persona. Planificaci´on global de caminos. En esta categor´ıa se muestran varios trabajos [24,39,43,49,65] que aplican el CBR a la planificaci´on global de caminos bajo distintas condiciones de partida. As´ı, por ejemplo [24, 39] aplican el CBR a la planificaci´on global de caminos en entornos est´aticos partiendo de un mapa m´etrico conocido CBR aplicado a navegaci´on aut´onoma 45 a priori, donde los casos absorben la estructura del entorno, us´andose en [24] abstracciones que permiten simplificar los casos y mejorar la eficiencia del CBR. Por su parte, [43] aplica el CBR a la planificaci´on global de caminos en entornos din´amicos bas´andose en un mapa topol´ogico del entorno conocido a priori [43]. En este trabajo se trataba de encontrar un camino posible desde un origen a un destino en un mapa real de Pittsburgh a partir de rutas almacenadas, las cuales tendr´ıan en cuenta factores como los patrones de tr´afico o el n´umero de v´ıas. El problema es que en el caso de cambios inesperados en el mapa no es posible descubrir nuevas soluciones a menos que se reorganizase el mapa topol´ogico regularmente [65], lo cual supone un coste computacional elevado. Este problema es debido a la estrecha relaci´on entre la descripci´on del entorno y la localizaci´on del robot. Por otro lado, [65] propone un m´etodo para planificaci´on global de caminos en entornos din´amicos usando el CBR para evitar situaciones donde haya que afrontar obst´aculos, minimizando las posibilidades de colisi´on. Este trabajo soluciona el problema de la continua reorganizaci´on del mapa de [43] para obtener nuevos resultados mediante el uso de un mapa basado en cuadr´ıculas, que permite obtener soluciones nuevas m´as f´acilmente que en un mapa topol´ogico. Sin embargo, este trabajo indica que la navegaci´on global basada en CBR es especialmente ´util cuando hay una gran densidad de obst´aculos, de forma que solo haya pocas soluciones al problema que se desea solucionar. Esto es un problema inherente al CBR pues, ante problemas en los que hay muchas posibles soluciones, es dif´ıcil determinar la soluci´on correcta si no hay suficiente informaci´on sobre el problema. En este caso, al haber pocos obst´aculos hay multitud de posibles caminos y, en principio, todos o una gran cantidad de ellos, son igualmente buenos. Por ´ultimo, [49] aplica tambi´en el CBR a la planificaci´on global de caminos con la idea de reutilizar y adaptar rutas anteriormente v´alidas en vez de encontrar rutas nuevas. La diferencia con los enfoques anteriores es que [49] utiliza un grafo de segmentos del camino en los casos CBR en vez del camino completo, de forma que sea m´as sencilla la b´usqueda, el reconocimiento de la situaci´on y su posible adaptaci´on a nuevas situaciones. En este trabajo, y debido al enfoque utilizado, es necesario un algoritmo anal´ıtico para aquellos casos en los que el CBR no disponga de informaci´on sobre el camino actual para poder alcanzar el destino, o bien para enlazar dos tramos segmentos de camino que no tienen conexi´on. 46 Aprendizaje de comportamientos b´asicos Soporte a la navegaci´on [112]. [112] propone un sistema de ayuda a la navegaci´on para entornos semi-estructurados que ayudar´ıa a determinar situaciones en las que no hay posibles salidas, o que camino es mejor coger bajo determinadas circunstancias. El CBR se acopla a un sistema de navegaci´on (que ya permite la navegaci´on y mapeo del entorno) que detectar´a situaciones peligrosas, conflictivas, sin salida, etc, indic´andolo al sistema de navegaci´on para evitar alcanzar dichas situaciones. Como se puede observar, los trabajos relacionados con navegaci´on basados en CBR utilizan el CBR para gestionar, resolver o mejorar tareas generalmente de alto nivel, estando normalmente las tareas de bajo nivel o bien codificadas mediante secuencias preestablecidas o bien implementados mediante algoritmos anal´ıticos, pero no mediante CBR. De hecho, la literatura que se ha encontrado disponible sobre la aplicaci´on del CBR a tareas de bajo nivel en navegaci´on [136, 137, 139] est´a relacionada con el propio grupo de investigaci´on. En estos trabajos, el CBR se usa con un enfoque como el presentado en el presente trabajo, realizando aprendizaje LfD mediante control remoto asociando movimientos concretos ante situaciones espec´ıficas de forma reactiva a bajo nivel. De hecho, el desarrollo actual parte de la experiencia obtenida en dichos trabajos. Sin embargo, la diferencia entre estos trabajos y el presente es que los trabajos anteriores se basan en una plataforma con ruedas usando sonar y el presente trabajo se basa en una plataforma con extremidades usando visi´on. Por lo tanto, en este cap´ıtulo se comprobar´a si este enfoque para la creaci´on de comportamientos reactivos es aplicable igualmente sobre una plataforma AIBO. 3.3. CBR: Funcionamiento y configuraci´on El paradigma del CBR surgi´o a finales de los a˜nos 70 [121] a partir de los estudios de Roger Schank y Robert Abelson y su idea b´asica es que problemas similares tienen soluciones similares [65]. As´ı pues, el CBR intenta resolver problemas reutilizando y adaptando, si es necesario, experiencias o soluciones aplicadas anteriormente a problemas similares [1]. El primer sistema que puede ser llamado un razonador basado en casos fue CYRUS [2], desarrollado por Janet Kolodner a principio de los a˜nos 80. Este primer sistema era poco m´as que un sistema de pregunta-respuesta con conocimiento sobre varios viajes y reuniones del secretario de estado Cyrus Vance. Sin embargo, y a pesar de su simplicidad, el modelo de memoria desarrollado para esta aplicaci´on sirvi´o de esqueleto para posteriores sistemas basados en CBR, como MEDIATOR, PERSUADER, CHEF o JULIA. CBR: Funcionamiento y configuraci´on 47 Dentro de las t´ecnicas de IA, el CBR es un tipo de sistema experto, ya que su objetivo es tratar de imitar el comportamiento de un experto en alguna materia, ya sea un mec´anico, un abogado o un m´edico. Para que un sistema experto sea capaz de imitar el comportamiento de una persona es necesario que este sistema tenga una capacidad de razonamiento o deducci´on similar a la de la persona (al menos en el ´ambito de aplicaci´on del sistema) o bien disponga de conocimiento suficiente sobre como actuar ante los problemas, imitando la actividad anterior del experto aunque, obviamente, con limitaciones. As´ı pues, el CBR, como sistema experto, necesita disponer de una base de conocimiento para poder actuar. En su caso, y dado que el CBR resuelve problemas en base a soluciones y experiencias anteriores, su base de conocimientos (o base de casos) estar´a formada por experiencias o casos, siendo un caso una porci´on de conocimiento que representa una experiencia o soluci´on asociada al contexto en el que tuvo lugar. Por lo tanto, un caso estar´a formado por par contexto-experiencia o problema-soluci´on, determinando el contexto el ´ambito en el que una soluci´on concreta es aplicable. Por otro lado, el funcionamiento de un sistema CBR puede verse de distintas formas, siendo las m´as usuales expresar su funcionamiento como un modelo de proceso en forma de ciclo o como un modelo estructurado de tareas. Ambos son complementarios entre s´ı, aunque el primero de ellos suele ser m´as usado y ofrece una visi´on general m´as clara del funcionamiento del CBR. Tanto este ciclo de funcionamiento como la base de conocimiento que permite funcionar a un sistema CBR se explican en mayor detalle en los siguientes apartados. 3.3.1. Ciclo del CBR El CBR se puede ver como un ciclo, formado normalmente por 4 procesos, que se ejecuta cada vez que se presenta un nuevo problema al CBR, finalizando el ciclo cuando se obtiene una soluci´on a dicho problema, dependiendo la soluci´on del conocimiento que posea el CBR. Las 4 fases que componen el ciclo normal de un sistema CBR (Fig. 3.1), conocido generalmente como ciclo 4R por el nombre de sus 4 fases, son: recuperar, reutilizar, revisar y retener. Sin embargo, y debido a que existen una gran variedad de sistemas CBR, habr´a sistemas que incluyan estas 4 fases, mientras que habr´a otros que tan s´olo incluyan algunas de ellas. En cualquier caso, y de forma general, cada vez que se presenta al CBR un nuevo problema, este problema debe ser transformado en un caso de entrada (Cin) siguiendo la estructura de par´ametros definida para el CBR en cuesti´on. En general, un caso est´a formado por un par problema-soluci´on, sin embargo, 48 Aprendizaje de comportamientos b´asicos Figura 3.1: T´ıpico ciclo del CBR el caso de entrada (Cin) creado a partir del problema actual estar´a formado ´unicamente por el problema o contexto, estando el campo correspondiente a la soluci´on o experiencia vac´ıo, pues es la respuesta que el CBR debe dar. As´ı pues, y tras la conversi´on del problema en un caso de entrada (Cin), se introducir´a en el ciclo CBR, realiz´andose las siguientes tareas en cada una de sus fases: Recuperar (o Retrieve en ingl´es). En esta fase (Fig. 3.1.a) el CBR busca, en la base de casos, el caso (Crec) o casos cuyo problema del par problema-soluci´on se parezca m´as al problema actual (Cin). Reutilizar (o Reuse ingl´es). En esta fase (Fig. 3.1.b), si el caso recuperado de la base de casos (Crec) es lo suficientemente parecido al caso de entrada (Cin), se aplica como soluci´on al problema actual. Si no es lo suficientemente parecido, el caso recuperado es adaptado, de forma que se pueda aplicar a la situaci´on actual. Revisar (o Revise en ingl´es). En esta fase (Fig. 3.1.c) se comprueba, en caso de que se haya aplicado adaptaci´on al caso recuperado, que la soluci´on propuesta soluciona correctamente el problema. CBR: Funcionamiento y configuraci´on 49 Retener (o Retain en ingl´es). Normalmente, en caso de que se haya aplicado adaptaci´on y la soluci´on propuesta sea correcta, en esta fase (Fig. 3.1.d) se almacena en la base de casos el caso adaptado para su uso en futuras situaciones. De forma general, esta fase contempla la adici´on de casos a la base de casos, tanto si son casos adaptados, como casos generados manualmente. A continuaci´on se explican en profundidad cada una de las fases as´ı como los par´ametros o factores que es importante tener en cuenta en cada una de ellas. Tras la explicaci´on en detalle de las fases, se har´a una recopilaci´on de los par´ametros que permiten describir completamente un sistema CBR, y que ser´an usados a lo largo de este trabajo para detallar las distintas implementaciones del CBR. 3.3.1.1. Recuperar El objetivo de esta fase es encontrar, dentro de la base de casos, el o los casos m´as parecidos al caso que describe la situaci´on o problem´atica actual. Es decir, el objetivo de esta fase es obtener, de la experiencia previamente almacenada en el sistema, la m´as parecida al problema actual. As´ı pues, esta fase comienza por la correcta conversi´on del problema o situaci´on a los par´ametros que describen el problema en forma de caso. Por lo tanto, para una correcta identificaci´on de los casos similares es importante que los par´ametros de descripci´on del problema se ajusten lo m´as posible a ´este. En el proceso de b´usqueda dentro de la base de casos no se est´a buscando un caso que coincida exactamente con el caso actual, sino el m´as parecido. Para ello es necesario utilizar un algoritmo de b´usqueda como pueden ser el de [148] b´usqueda por inducci´on, por prototipos o por vecindad. De entre estas t´ecnicas, la m´as gen´erica y usual es la de b´usqueda por vecindad [65], que consiste en establecer una funci´on de distancia que permite determinar que casos se parecen m´as al actual. Sin embargo, la velocidad de respuesta de esta t´ecnica depende de la cantidad de casos que haya en la base de casos. Las otras t´ecnicas mencionadas solucionan este problema, siendo especialmente ´utiles cuando la descripci´on del problema tiene caracter´ısticas que permiten filtrar los casos a considerar (b´usqueda por inducci´on) o cuando la base de casos es demasiado grande y es necesario acotar la b´usqueda entre un conjunto inicial para acelerar la selecci´on posterior (b´usqueda por prototipos). La desventaja de estas t´ecnicas es la posibilidad de p´erdida de casos en la b´usqueda y el preprocesado que es necesario aplicar a la base de casos. As´ı pues, y considerando la t´ecnica de b´usqueda por vecindad, que es la m´as usual, para su aplicaci´on es necesario utilizar una funci´on de similitud 56 Aprendizaje de comportamientos b´asicos Figura 3.3: Representaci´on de una base de casos plana. base de casos en un sistema CBR, todas ellas se pueden dividir en dos grandes grupos: Estructura plana. En las estructuras planas (Fig. 3.3) los casos se almacenan secuencialmente de forma independiente, sin establecer ninguna relaci´on ni agrupaci´on expl´ıcita entre ellos. Esta estructura es sencilla de implementar, garantiza que en la b´usqueda de casos se devuelve el m´as parecido que exista en la base de casos y la inserci´on de nuevos casos es tan simple como a˜nadirlo al final de la base de casos. Sin embargo, tambi´en tiene algunos inconvenientes, ya que en la b´usqueda se realiza la comparaci´on del caso de entrada con todos los casos de la base, por lo que la velocidad de respuesta en las b´usquedas depender´a de la cantidad de casos que almacene la base de casos. Por esta raz´on, y a pesar de que no requiere ning´un post-procesamiento al a˜nadir nuevos casos, es conveniente aplicar peri´odicamente alg´un algoritmo que permita comprobar que el n´umero de casos de la base de casos no crece en exceso para no reducir el rendimiento del sistema. En definitiva, es una estructura adecuada cuando se puede controlar que el n´umero de casos de la base de casos no crezca en exceso. Estructura jer´arquica. En las estructuras jer´arquicas los casos se organizan en la base de casos de forma jer´arquica formando grupos seg´un su parecido teniendo en cuenta determinados par´ametros. Esta estructura es m´as compleja que la estructura plana, pero a cambio de dicha complejidad, permite realizar b´usquedas mucho m´as r´apidas permitiendo el uso de bases de casos con un elevado n´umero de casos. Para ello, en el proceso de b´usqueda en vez de realizar una b´usqueda exhaustiva como en las estructuras planas, se discriminan los casos (seg´un los grupos a los que pertenezcan) que no se consideran parecidos al de entrada, CBR: Funcionamiento y configuraci´on 57 buscando ´unicamente en los que se consideren similares. Por lo tanto, esta estructura solventa el problema de las estructuras planas, pero a cambio de una serie de problemas, como la mayor complejidad de implementaci´on, la posibilidad de p´erdida de casos significativos debido a la discriminaci´on de casos en la b´usqueda jer´arquica, o la complejidad al a˜nadir nuevos casos, que supone, cada vez que se a˜nada un caso, realizar una reestructuraci´on y reorganizaci´on de la base de casos para que ´esta sea consistente. Algunos ejemplos de estructuras jer´arquicas usados habitualmente son la estructura jer´arquica basada en el modelo de memoria din´amica y la basada en el modelo de categor´ıas y ejemplares. Por lo tanto, las ventajas de las estructuras planas son que siempre devuelven el caso m´as similar al actual (no descartan posibles soluciones debido a agrupaciones o accesos a grupos incorrectas) y que la inserci´on de casos es sencilla y barata en t´erminos computacionales. Sin embargo, la b´usqueda en estas estructuras son m´as lentas que en las jer´arquicas si hay una gran cantidad de casos debido a que las estructuras planas buscan en toda la base de casos. Sin embargo, este problema tiene una f´acil soluci´on manteniendo el n´umero de casos de la base de casos acotado. Las estructuras jer´arquicas, por su parte, son m´as eficientes en las b´usqueda pero la implementaci´on y la inserci´on de casos resulta m´as compleja que en las estructuras planas. Por otro lado, y al igual que las estructuras planas requieren un control del n´umero de casos en la base, las estructuras jer´arquicas requieren un mantenimiento para asegurar la coherencia de los ´ındices y agrupaciones de los casos almacenados. Adem´as, las estructuras jer´arquicas son sensibles a la p´erdida potencial de casos significativos si en la b´usqueda se accede a un grupo de b´usqueda no equivocado. 3.3.3. Par´ametros para descripci´on del CBR En este apartado se resumen, de forma breve, los elementos o par´ametros que son necesarios determinar para describir un sistema CBR as´ı como su funcionamiento. Estos elementos son: Estructura de la base de casos. Hay que determinar si la base de casos tiene una estructura plana o jer´arquica (lo que determinar´a el tama˜no m´aximo aconsejable de ´esta as´ı como su velocidad de b´usqueda) y los algoritmos de indexaci´on y/o agrupaci´on usados en funci´on del tipo de estructura seleccionado. Estructura del caso. La estructura de par´ametros que define un caso es crucial para una correcta b´usqueda posterior de los casos as´ı como de 58 Aprendizaje de comportamientos b´asicos los m´as parecidos. Algoritmo de b´usqueda en la fase recuperaci´on. Los algoritmos de b´usqueda m´as usuales son b´usqueda por inducci´on, por prototipos o por vecindad, dependiendo el uso de uno u otro, sobre todo, de la estructura de la base de casos. Algoritmo de similitud en la fase recuperaci´on. El algoritmo de similitud suele ser una distancia distancia de similitud como la distancia Eucl´ıdea, Tanimoto, Manhattan, etc. En el caso de usar una distancia ponderada, hay que indicar los pesos de cada par´ametro tambi´en. Algoritmo de adaptaci´on en la fase de reutilizaci´on. Los posibles algoritmos de adaptaci´on son: adaptaci´on nula, adaptaci´on estructural y adaptaci´on derivada, siendo necesario en el caso de las dos ´ultima indicar como se realizar´a la adaptaci´on sobre el caso recuperado. Algoritmo de evaluaci´on en la fase de revisi´on. Se indicar´a como se realizar´a la validaci´on de las soluciones adaptadas a los nuevos problemas en caso de que se aplique adaptaci´on. Algoritmo de aprendizaje en la fase de retenci´on. Hay que determinar los tipos de aprendizaje que se usar´an en esta fase para el sistema CBR, siendo las alternativas m´as usuales aprendizaje por observaci´on y por experiencia (positiva y/o negativa). 3.4. Navegaci´on basada en comportamientos aprendidos En este cap´ıtulo se presenta un sistema que permite la navegaci´on reactiva de un robot mediante aprendizaje. Concretamente, el objetivo en este cap´ıtulo es demostrar que se pueden desarrollar distintos comportamientos reactivos que permitan la navegaci´on de un robot mediante aprendizaje, sin necesidad de modificar (o realizando modificaciones m´ınimas) el sistema. As´ı pues, para generar distintos comportamientos tan s´olo ser´ıa necesario entrenar al robot para que realice el comportamiento deseado y determinar los par´ametros que definen tanto la situaci´on actual como su soluci´on. La idea es, por lo tanto, comprobar que el enfoque de navegaci´on basada en comportamientos aprendidos es viable y flexible, de forma que pueda ser usada posteriormente para implementar la navegaci´on coordinada del MRS, que es el objetivo de la presente tesis. Navegaci´on basada en comportamientos aprendidos 59 La arquitectura del sistema es una arquitectura h´ıbrida, aunque este cap´ıtulo se centra ´unicamente en la implementaci´on de la capa de navegaci´on reactiva basada en comportamientos aprendidos, dejando la descripci´on de las capas superiores para pr´oximos cap´ıtulos. La raz´on de usar aprendizaje en vez de un algoritmo anal´ıtico es que el aprendizaje permite una mayor flexibilidad a la hora de definir los comportamientos as´ı como una mayor facilidad de implementaci´on y modificaci´on de ´estos, como se coment´o en el cap´ıtulo 2. Dentro de las distintas t´ecnicas de IA y aprendizaje, se usar´a la t´ecnica de CBR porque su aplicaci´on es inmediata en situaciones en las que se puede obtener informaci´on f´acilmente, permite tener acceso a la base de conocimiento del sistema en cada instante y no requiere un modelado ni un entendimiento profundo del problema. Adem´as, el CBR encaja perfectamente con la idea de los comportamientos reactivos, pues permite acoplar de forma inmediata los sensores (cuya informaci´on definir´ıa el problema del caso) a la acci´on o comando de movimiento del robot (que definir´ıa la soluci´on del caso), ya que los casos del CBR est´an formados precisamente por pares problema-soluci´on. Por otro lado, el aprendizaje se realizar´a mediante aprendizaje por demostraci´on (LfD) [8,130]. Este aprendizaje consiste en realizar un entrenamiento, con el robot controlado remotamente, de forma que el operador s´olo tenga que considerar como quiere mover al robot y hacia donde quiere dirigirlo en funci´on de lo que el robot est´a percibiendo. A trav´es de este entrenamiento, el CBR asocia las acciones del operador (los comandos de movimiento del joystick) a un estado (la informaci´on visual extra´ıda de la imagen actual) de una forma sencilla. La secci´on 3.4.3 describe en m´as detalle el LfD as´ı como sus ventajas. Tras finalizar este entrenamiento, el CBR dispone de informaci´on suficiente para que el robot puede comenzar a funcionar de forma aut´onoma utilizando la informaci´on obtenida durante el entrenamiento. Para comprobar la viabilidad del enfoque, se realizar´an pruebas con un robot AIBO de Sony, cuyo principal sensor de entrada es una c´amara, en un entorno con una pelota rosa y un peque˜no campo de f´utbol. Concretamente, para realizar los experimentos se van a entrenar dos comportamientos como prueba de concepto, que permitir´an estimar la validez del sistema en esta plataforma. En ambas tareas se ha utilizado el mismo programa, cambiando ´unicamente el entrenamiento y la definici´on del caso CBR. De esta forma, se comprueba la versatilidad y flexibilidad del sistema para realizar distintos comportamientos, pues s´olo es necesario redefinir los par´ametros del caso y realizar un entrenamiento para implementar un comportamiento. Dado que es una prueba de concepto, estas dos tareas son usadas simplemente para comprobar la viabilidad del enfoque propuesto. Si 60 Aprendizaje de comportamientos b´asicos bien las tareas a realizar son b´asicas, pero cumplen su objetivo, adem´as de permitir una primera toma de contacto con el sistema de navegaci´on reactiva basado en CBR. Las dos tareas a realizar son, en principio, independientes y no se ejecutar´an de forma simult´anea, sino que, como ya se mostrar´a m´as adelante, se enlazar´an de forma secuencial. Tambi´en hay que tener en cuenta que en estas tareas no se tienen en cuenta la presencia de otros robots en el campo, ya que esto se tendr´a en cuenta en pr´oximos cap´ıtulos (concretamente a partir del cap´ıtulo 5). As´ı pues, la primera de las tareas consiste en la b´usqueda de una pelota de color conocido a priori en un campo de f´utbol, restricci´on que es considera normal al plantearse un problema basado en visi´on [146]. Hay que tener en cuenta tambi´en que, aunque el seguimiento de una pelota es un problema bastante conocido y que ha sido solucionado usando distintas aproximaciones, pasando desde las puramente reactivas hasta la predicci´on usando filtros de Kalman [66, 122], pero el objetivo en s´ı no es otro que, como ya se ha comentado, el de realizar unas pruebas preliminares de navegaci´on reactiva basada en CBR usando para ello un comportamiento sencillo del que poder sacar conclusiones f´acilmente. Por otro lado, la segunda tarea ser´a la b´usqueda de la porter´ıa en un campo de f´utbol mediante detecci´on de l´ıneas en la imagen. La localizaci´on basada en detecci´on de l´ıneas ha sido usada normalmente en el entorno de la Robocup, habitualmente en combinaci´on con balizas de colores y porter´ıas [79,129]. As´ı por ejemplo, algunos m´etodos se basan en el color [53,108,109] para detectar las l´ıneas por medio de un escaneo vertical de la imagen, procesando posteriormente toda esta informaci´on mediante t´ecnicas de Montecarlo para estimar la posici´on del robot y calcular la acci´on a realizar a partir de la posici´on del robot. La principal diferencia del enfoque propuesto con respecto a los m´etodos descritos es que en la navegaci´on reactiva basada en CBR no existe un modelo expl´ıcito del entorno, no obteni´endose la posici´on del robot respecto al campo, sino estim´andose impl´ıcitamente mediante el aprendizaje, devolviendo directamente el comando de movimiento que debe realizar el robot para alcanzar la porter´ıa. En cualquier caso, y al igual que en el ejemplo de la b´usqueda de la pelota, es necesario tener en cuenta que esta tarea es usada simplemente para probar la versatilidad de la propuesta de construcci´on de comportamientos basados en CBR. Como se puede observar, ambas tareas utilizan una definici´on del entorno distinta (en la primera se tienen en cuenta la detecci´on de zonas de color, mientras que en la segunda se usan las l´ıneas detectadas en la imagen). Sin embargo, en ambas se usa el mismo sistema y el mismo enfoque basado en entrenamiento, mostrando la versatilidad del sistema propuesto. Por ´ultimo, Navegaci´on basada en comportamientos aprendidos 61 tras finalizar los entrenamientos y las pruebas, ambas tareas se enlazar´an secuencialmente, de forma que se ejecutar´a primero la tarea de buscar la pelota y, una vez encontrada y capturada, se llevar´a la pelota a la porter´ıa para chutar a gol. Estas tareas, as´ı como las ventajas del aprendizaje por demostraci´on y el esquema global del sistema se desarrollan en m´as detalle en los siguientes apartados. 3.4.1. Comportamiento de b´usqueda de pelota Este comportamiento tiene por objetivo que el robot sea capaz de buscar, tras un entrenamiento adecuado, una pelota de un color conocido a priori (rosa) en un entorno controlado (un campo de f´utbol en el que no existen m´as objetos del mismo color que la pelota), se acerque a ´esta y la capture entre las piernas frontales, deteni´endose el comportamiento cuando se detecte que la pelota ha sido capturada. Para el funcionamiento de este comportamiento el robot deber´a detectar en la imagen el color de la pelota y obtener la posici´on estimada de ´esta respecto al robot. Estos par´ametros formar´an la descripci´on del problema y se detallar´an m´as adelante. Si el robot no detecta en el campo de visi´on ninguna pelota, el robot girar´a hacia su izquierda hasta que la pelota entre en el campo de visi´on. Por ´ultimo, recordar que como el comportamiento funciona a nivel reactivo y no existe ning´un modelado del entorno, tampoco existir´a un posicionamiento global del robot en el entorno, siendo todos los objetos referenciados al propio robot. 3.4.2. Comportamiento de b´usqueda de porter´ıa Este comportamiento tiene por objetivo que el robot sea capaz de buscar la porter´ıa, tras el correspondiente entrenamiento, en un entorno controlado (un campo de f´utbol blanco marcado por l´ıneas negras) utilizando para estimar la posici´on de la porter´ıa las lineas detectadas en la imagen. De esta forma, el robot deber´a dirigirse a la porter´ıa y detenerse delante de ´esta. Si posteriormente el robot detecta que no se haya delante de la porter´ıa, volver´a a moverse hacia ´esta. Para el funcionamiento de este comportamiento el robot deber´a ser capaz de detectar las lineas en la imagen y estimar, de forma impl´ıcita, la posici´on de la porter´ıa respecto al robot a partir de ´estas. Hay que tener en cuenta que como s´olo se usan las lineas del campo de f´utbol, y ´este es sim´etrico, el robot se acercar´a a una porter´ıa pero no sabr´a a cual. Al igual que en el caso de la 62 Aprendizaje de comportamientos b´asicos b´usqueda de pelota, los par´ametros de las l´ıneas formar´an la descripci´on del problema y se detallar´an m´as adelante. En el caso de que el robot no detecte ninguna linea en el campo de visi´on, este se detendr´a por seguridad, ya que podr´ıa tener la cabeza demasiado cerca de un obst´aculo que no le permitiese al robot ver nada y colisionar. Finalmente, y al igual que en el comportamiento anterior, indicar que como el comportamiento funciona a nivel reactivo y no existe ning´un modelado expl´ıcito del entorno, tampoco existir´a un posicionamiento global del robot en el entorno. 3.4.3. Aprendizaje por demostraci´on El aprendizaje por demostraci´on o LfD [8,130] es una t´ecnica de aprendizaje que permite asociar una acci´on a un estado y que consiste en entrenar un comportamiento espec´ıfico a partir de ejemplos provistos por un usuario supervisor. Concretamente, y como ya se ha comentado, el entrenamiento se realiza mediante control remoto del robot a trav´es de un joystick o cualquier otro interfaz que resulte c´omodo al operador. Durante este entrenamiento, el operador ´unicamente tiene que mover al robot seg´un el patr´on que quiera que ´este realice cuando se mueva de forma aut´onoma. As´ı pues, a trav´es del entrenamiento el CBR almacena los comandos de movimiento que realiza el usuario (la acci´on) asoci´andolos a los par´ametros que describen la situaci´on actual (el estado) de una forma sencilla e inmediata. Hay que tener en cuenta que durante los entrenamientos el operador normalmente controla al robot desde su propio punto de vista. Sin embargo, este cambio de punto de vista (pues el robot tiene que moverse desde su propio punto de vista) no es importante siempre y cuando los objetos a tener en cuenta y que conforman el universo del robot est´en en su campo de visi´on. La figura 3.4 muestra un ejemplo de aplicaci´on del LfD y las distintas fases de las que se compone. As´ı pues, la figura 3.4.a muestra el caso en el que el robot a´un no ha sido entrenado y no sabe hacer nada, de forma que al lanzarle la persona la pelota, no sabe que hacer. En la figura 3.4.b se observa como la persona lanza la pelota y controla el robot mediante un joystick para ense˜narle que tiene que hacer cuando vea la pelota. Durante este entrenamiento, los comandos del operador se est´an almacenando tambi´en en el CBR. Finalmente, en la figura 3.4.c se observa como al lanzar el operador la pelota, el robot ya ha aprendido que debe hacer, accediendo a la informaci´on almacenada en el CBR, capturando finalmente la pelota. El uso de este tipo de aprendizaje tiene una serie de ventajas, derivadas la mayor´ıa de ellas de la capacidad innata que tienen las personas para Navegaci´on basada en comportamientos aprendidos 63 Figura 3.4: Aprendizaje por observaci´on: a) El robot no est´a entrenado y no sabe que hacer; b) se entrena al robot para que busque la pelota; c) el robot recuerda como buscar la pelota. adaptarse a distintas situaciones y entornos. As´ı pues, cuando el operador est´a entrenando al robot, este debe asimilar la estructura y movimiento del robot, de forma que el robot aprenda como se mover´ıa una persona si tuviese la misma estructura corporal que el robot. Esta es una idea clave en el enfoque presentado, pues sin esta capacidad de adaptaci´on de los humanos se perder´ıan la mayor´ıa de ventajas del este enfoque. As´ı pues, a partir de esta simple idea, se consiguen las siguientes ventajas [47,102]: La absorci´on de la din´amica y cinem´atica del robot. Esto sucede debido a que cuando el operador maneja el robot est´a asimilando de forma impl´ıcita las caracter´ısticas propias del robot, como su forma de moverse y su velocidad. De esta forma, se evita tener que realizar un modelo cinem´atico del robot. La adaptaci´on del esquema de navegaci´on f´acilmente a otros robots. Esta ventaja deriva del punto anterior ya que, si los par´ametros del caso no son dependientes de la cinem´atica del robot, y dado que ´esta se absorbe durante el entrenamiento por el operador es sencillo adaptar 64 Aprendizaje de comportamientos b´asicos un entrenamiento a otro robot con caracter´ısticas distintas. En cualquier caso, si no fuese factible dicha adaptaci´on, tan s´olo ser´ıa necesario repetir el entrenamiento con el nuevo robot. La absorci´on de los errores en los par´ametros de entrada y de salida. En el caso del robot usado, los par´ametros son extra´ıdos de im´agenes reales capturadas por el robot, por lo que mediante el entrenamiento los errores sistem´aticos de los sensores, como la distorsi´on de barril de la c´amara, u otros errores que se puedan producir debido ruidos en la imagen o movimientos bruscos del robot son absorbidos por el operador impl´ıcitamente ya que las im´agenes reales con las que se realiza el entrenamiento ya incluyen esos errores y distorsiones. Respecto a los par´ametros de salida, en el caso de los robots con extremidades es f´acil que los motores de las extremidades no sean exactamente iguales, lo que hace que el robot pueda tener una deriva hacia un lado, por ejemplo, o que gire m´as en un sentido que en otro. Este tipo de imperfecciones y errores mec´anicos son absorbidos tambi´en de forma impl´ıcita al manejar el robot. La generaci´on comportamientos ad hoc y la mejora de los existentes f´acilmente. Para que el robot realice un comportamiento concreto s´olo es necesario entrenarlo en dicho patr´on de conducta, y en el caso de ampliar uno anterior habr´ıa que realizar un nuevo entrenamiento y a˜nadirlo al ya existente, de una forma sencilla. En este ´ultimo caso habr´ıa que tener especial cuidado si ante una misma situaci´on se realizasen distintos comandos de movimiento, lo que podr´ıa provocar comportamientos indeseados. Evitar el uso de expresiones anal´ıticas para la implementaci´on del comportamiento, pues el propio entrenamiento remoto genera el algoritmo para la navegaci´on del robot. Esto es especialmente interesante cuando se quieren realizar comportamientos que no son f´aciles de implementar anal´ıticamente pero son f´aciles de entrenar. Una f´acil adaptaci´on del comportamiento de navegaci´on a distintas situaciones. Gracias a la capacidad de adaptaci´on del CBR, el sistema podr´ıa, potencialmente, adaptarse de forma sencilla a otras situaciones diferentes a las entrenadas, siempre que ´estas no fuesen muy diferentes y los par´ametros de entrada usados sean los suficientemente gen´ericos. En ´este ´ultimo caso, siempre se puede realizar un nuevo entrenamiento en la nueva situaci´on y a˜nadirlo al entrenamiento anterior. Navegaci´on basada en comportamientos aprendidos 65 3.4.4. Funcionamiento del sistema de navegaci´on El sistema de navegaci´on mediante LfD basado en CBR supone un m´etodo simple y directo para acoplar la informaci´on visual y los comandos de movimiento a enviar al robot, implementando as´ı un comportamiento reactivo aprendido f´acilmente. Sin embargo, para que este sistema funcione de forma aut´onoma es necesaria una informaci´on o experiencia previa. As´ı pues, el sistema de navegaci´on CBR estar´a formado por las siguientes fases: Aprendizaje supervisado. Durante la fase de aprendizaje supervisado o aprendizaje por demostraci´on se realiza el aprendizaje de los distintos patrones de navegaci´on que tendr´a que realizar el robot en funci´on de cada situaci´on concreta. Para ello lo que se hace es controlar de forma remota al robot mientras se almacena en la base de casos del CBR la informaci´on con el comportamiento que se desee entrenar. Como resultado de esta fase se obtendr´a la experiencia inicial o base de casos inicial que utilizar´a el CBR cuando trabaje de forma aut´onoma para obtener soluciones a partir de la experiencia previa (adquirida en esta fase). Navegaci´on aut´onoma. Durante la fase de navegaci´on aut´onoma el robot funcionar´a de forma aut´onoma sin supervisi´on, enviado al CBR informaci´on sobre el entorno y el estado del robot y devolviendo el CBR los comandos de movimiento previamente aprendidos que m´as se adec´uen a la situaci´on actual. 3.4.5. Implementaci´on del sistema de navegaci´on En este apartado se describe la implementaci´on del sistema de navegaci´on basado en comportamientos aprendidos. Como se ha comentado, este sistema est´a formado por dos fases, entrenamiento supervisado y navegaci´on aut´onoma, por lo que se describir´an los bloques que componen el sistema en cada una de ellas. La figura 3.5.a muestra el diagrama de bloques del sistema durante el aprendizaje supervisado. Como se puede observar, el sistema est´a dividido en la aplicaci´on del robot y la aplicaci´on del ordenador, conectadas ambas via WiFi. As´ı pues, la aplicaci´on del robot env´ıa a la del ordenador el estado del robot, as´ı como la imagen capturada por el robot, de forma que la aplicaci´on del ordenador extrae los par´ametros de las im´agenes recibidas y los une con los par´ametros de estado del robot as´ı como con los comandos de movimiento del operador para formar la estructura del caso que se almacenar´a en la base de casos. Simult´aneamente a la creaci´on y almacenamiento de los casos, los 72 Aprendizaje de comportamientos b´asicos que debe alcanzar el robot en cada una de las tareas a aprender. As´ı pues, y dado que ambos comportamientos tienen objetivos distintos, se estudiar´a por separado la parametrizaci´on de entrada cada uno de los comportamientos a aprender: Comportamiento de b´usqueda de pelota. En el caso de la tarea de b´usqueda de la pelota de color conocido (rosa), el destino a alcanzar es la pelota de color rosa. Dado que un sistema reactivo puro no tiene memoria explicita, toda la informaci´on de entrada a usar por el CBR debe estar contenida dentro de la imagen actual. A partir de una imagen se pueden extraer tanto par´ametros cuantitativos como cualitativos [6]. En el caso de los par´ametros cuantitativos, como componentes principales, histogramas, etc´etera, los par´ametros cuantifican la imagen en un conjunto de n´umeros, mientras que los par´ametros cualitativos tratan de encontrar informaci´on significativa en la imagen mediante el an´alisis de su contenido dependiendo de la aplicaci´on a desarrollar. Este ´ultimo enfoque suele dar como resultado un conjunto de caracter´ısticas de inter´es dependientes de la aplicaci´on. Dado que lo que se busca es usar la informaci´on m´ınima que permita describir el problema, y el CBR es dependiente del problema, las t´ecnicas cualitativas resultan m´as interesante para describir el problema presente. Figura 3.6: Par´ametros de definici´on del caso para b´usqueda de pelota. Sin embargo, es importante que el conjunto de caracter´ısticas de la imagen sean representativas, f´aciles de detectar y lo m´as inmune posible a oclusiones y cambios en la iluminaci´on. Dado que la pelota en la imagen se presenta como un ´area de color homog´eneo que crece cuando m´as cerca est´e de la c´amara, se puede usar la posici´on del centroide de dicha ´area en la imagen para determinar la posici´on de la pelota y su tama˜no para determinar su distancia a la c´amara (dado que se conoce su tama˜no real). Para poder conseguir cierta inmunidad contra los cambios Navegaci´on basada en comportamientos aprendidos 73 de iluminaci´on, se puede realizar la detecci´on del color en espacios como HSI o HSV, en los que el canal que indica el color es independiente del que codifica la luminosidad. Es importante tambi´en tener en cuenta las posibles oclusiones de la pelota, por lo que es conveniente a˜nadir un indicador de oclusi´on como par´ametro de entrada. As´ı pues, la figura 3.6 muestra los par´ametros visuales que se tienen en cuenta para la formaci´on del caso de entrada. Sin embargo, hay que tener en cuenta un factor m´as, ya que la cabeza del robot puede no estar alineada con el cuerpo. En ese caso, se puede obtener una imagen en la que, por ejemplo, se vea la pelota enfrente del robot, cuando realmente est´a a la derecha o a la izquierda. As´ı pues, otro par´ametro importante que define la situaci´on del entorno es la orientaci´on de la cabeza, pues define desde que punto de vista se est´a mirando el entorno. Teniendo en cuenta todas estas reflexiones, se llega a la definici´on final del caso para la tarea de detecci´on de pelota, en la que el caso estar´a determinada por la siguiente pareja {P, S}: Case ={{Xball, Yball, XBBball, YBBball, Oball, αhead},{Cf, Cr}} (3.1) Siendo (Xball, Yball) la posici´on de la pelota en la imagen en p´ıxeles, (XBBball, YBBball) el tama˜no de la pelota en ancho y alto en la imagen en p´ıxeles, Oball un indicador de si la pelota est´a ocluida o cortada, αhead la orientaci´on de la cabeza respecto al cuerpo del robot en grados, y CfyCrlos comandos de movimiento frontal y de rotaci´on a enviar al robot normalizados entre -1 y 1. Comportamiento de b´usqueda de porter´ıa. En el caso de la tarea de b´usqueda de la porter´ıa a partir de las l´ıneas detectadas en la imagen, el destino a alcanzar es la porter´ıa. Este comportamiento, al igual que el anterior, es reactivo, por lo que no dispone de ning´un tipo de mapa del entorno y la informaci´on a usar para determinar la posici´on de la porter´ıa debe estar contenida en la imagen capturada. Para la detecci´on de las l´ıneas en la imagen, como ya se ha comentado, el m´etodo m´as usual es la aplicaci´on de la Transformada de Hough, la cual devuelve directamente los par´ametros que definen las l´ıneas detectadas en la imagen. Esta transformada puede aplicarse a cada imagen recibida y, a partir de las l´ıneas que ´esta detecta, realizar de forma instant´anea una estimaci´on de la posici´on del robot y de la porter´ıa en funci´on de 74 Aprendizaje de comportamientos b´asicos las l´ıneas que se est´en visualizando actualmente. As´ı por ejemplo, si se detectan las l´ıneas de la figura 3.7.a, se puede estimar que la posici´on del robot es aproximadamente la indicada, al igual que si se detectan las l´ıneas de la figura 3.7.b la posici´on ser´ıa aproximadamente la indicada en la figura. Hay que tener en cuenta que esta estimaci´on de la posici´on no se realiza de forma explicita, sino que el operador ense˜na al AIBO a estimar su posici´on en el campo de forma impl´ıcita a partir de las l´ıneas detectadas en la imagen. Figura 3.7: Estimaci´on de la posici´on del robot a partir de las l´ıneas. Dado que hay que intentar usar la m´ınima cantidad de par´ametros para la definici´on del caso CBR, para minimizar los posibles errores debido a la detecci´on de las l´ıneas, errores que ocasionan que se detecten m´ultiples l´ıneas derivadas de una ´unica l´ınea que por el movimiento del robot se ha detectado mal, y puesto que en un campo de f´utbol es dif´ıcil ver m´as de 4 l´ıneas simult´aneamente, se ha decidido finalmente usar s´olo las 4 l´ıneas m´as relevantes detectadas en la imagen. As´ı pues, la figura 3.8 muestra los par´ametros que forman el caso de entrada para este entrenamiento. Por ´ultimo, y al igual que en el caso anterior, hay que tener en cuenta el ´angulo de la cabeza, pues de ´este depende el punto de vista desde el que se ve el entorno. As´ı pues, la definici´on final del caso para la tarea de detecci´on de porter´ıa estar´a formada por la siguiente pareja {P, S}: Case ={{ρl1, θl1, ρl2, θl2, ρl3, θl3, ρl4, θl4, αhead},{Cf, Cr}} (3.2) Siendo (ρln, θln) los par´ametros correspondientes a la recta n, αhead la orientaci´on de la cabeza respecto al cuerpo del robot en grados, y Cfy Navegaci´on basada en comportamientos aprendidos 75 Figura 3.8: Par´ametros de definici´on del caso para b´usqueda de porter´ıa. Crlos comandos de movimiento frontal y de rotaci´on a enviar al robot normalizados entre -1 y 1. Hay que tener en cuenta que en el caso de que se detecten menos de cuatro l´ıneas, los campos correspondientes a la l´ıneas no detectadas se rellenan a un valor nulo. Por ´ultimo, en el caso de que no se haya detectado ninguna l´ınea en absoluto, el robot se detiene por seguridad, ya que podr´ıa tener la cabeza demasiado cerca de un obst´aculo que no le permitiese al robot ver nada y colisionar. 3.4.6.3. Descripci´on de la fase de recuperaci´on Para describir la fase de recuperaci´on usada en el CBR es necesario especificar tanto el algoritmo de b´usqueda que usar´a esta fase como la distancia de similitud que se usar´a. Respecto al algoritmo de b´usqueda, se usar´a el algoritmo de b´usqueda por vecindad, pues es un algoritmo muy utilizado cuyo ´unico inconveniente es el tiempo de respuesta si la base de casos crece demasiado, pero como en el caso presente el n´umero de casos se mantendr´a acotado, esto no resultar´a un problema. Por otro lado, la funci´on de distancia para estimar la similitud de los casos que se usar´a es la distancia Manhattan, pues esta distancia permite evaluar las diferencias entre la forma global de los vectores m´as que de los elementos de forma independiente, por lo cual resulta adecuada cuando los elementos del vector a calcular son muy diferentes y no est´an relacionados entre s´ı, como es la situaci´on actual. Adem´as, en la pr´actica se ha comprobado que ha dado buenos resultados. 76 Aprendizaje de comportamientos b´asicos 3.4.6.4. Descripci´on de la fase de reutilizaci´on Para describir la fase de reutilizaci´on usada en el CBR es necesario especificar el algoritmo de adaptaci´on usado. Dado que se han aprendido dos tareas distintas, y en cada una se utiliza una t´ecnica de adaptaci´on distinta, se comentar´a cada una por separado: Comportamiento de b´usqueda de pelota. En el caso de esta tarea, dado que la tarea a desarrollar resulta extremadamente sencilla y en los experimentos, como se ver´a en el apartado 3.5, el aprendizaje por observaci´on ha sido m´as que suficiente, se ha optado por usar una adaptaci´on nula para este comportamiento. Comportamiento de b´usqueda de porter´ıa. En esta tarea, dado que el comportamiento a desarrollar es m´as complejo que el anterior y es dif´ıcil poder tener en cuenta todas las posibles situaciones que el robot pueda enfrentar (ver secci´on 3.5 para m´as detalles), fue necesario a˜nadir un algoritmo que permitiese la adaptaci´on de los casos aprendidos durante el aprendizaje por observaci´on, ya que la otra alternativa era la realizaci´on de un entrenamiento exhaustivo con todas las posibles situaciones que el robot puede afrontar, lo cual resultar´ıa m´as complejo y tedioso. As´ı pues, para poder adaptar un caso es necesario relacionar el caso recuperado a los datos capturados del entorno. En este comportamiento se ha observado que la orientaci´on relativa del robot en el campo (determinada por la componente θde las l´ıneas) tiene una mayor influencia desde el punto de vista del comportamiento que la distancia a la que se encuentra de la meta (determinada principalmente por la componente ρde las l´ıneas). Por tanto, la adaptaci´on debe tener en cuenta el valor de la componente θde las l´ıneas detectadas en la imagen para modificar los comandos de movimiento. La figura 3.9 muestra un ejemplo de como afecta un giro en el robot a la posici´on de una l´ınea en el dominio de Hough. La figura 3.9.a muestra un caso donde el AIBO se dirige hacia la l´ınea formando un ´angulo de 90 grados con su orientaci´on. En la figura 3.9.b se ve el mismo caso pero con un ´angulo menor. La figura 3.9.c muestra la diferencia de ´angulos entre las figuras 3.9.a y b representada en el dominio de Hough. Si el AIBO est´a afrontando la situaci´on en la figura 3.9.b y el caso m´as similar almacenado es el de la figura Fig. 3.9.a, donde el AIBO ten´ıa que seguir hacia delante, para poder alcanzar el mismo resultado el AIBO deber´ıa girar hacia la derecha, dependiendo la magnitud de este giro Navegaci´on basada en comportamientos aprendidos 77 Figura 3.9: Efecto de cambios en la inclinaci´on de una l´ınea en el dominio de Hough. de la diferencia en θentre ambas l´ıneas (figura 3.9.c). Como el comportamiento puede verse afectado por varias l´ıneas simult´aneamente, los casos son adaptados dependiendo de la media de los cambios en la componente θde las l´ıneas detectadas: θAv = Σi(θIN (i)−θCBR(i)) (3.3) Siendo θIN (i) el par´ametro θpara la l´ınea ien la situaci´on actual y θCBR(i) el par´ametro θpara la l´ınea ien la salida del caso recuperado de la base de casos. Si θAv es mayor que un determinado umbral Uadapt (determinado heur´ısticamente), la salida del caso se adapta a˜nadi´endole el factor Fadapt (ecuaci´on 3.4) a la rotaci´on propuesta por el CBR. Sino, se aplicar´a la rotaci´on propuesta por el CBR directamente. Fadapt =k·θAv Uadapt (3.4) Siendo kuna constante para controlar cuanto puede cambiar un caso, de forma que un bajo kproduce una baja adaptaci´on, pero movimientos m´as suaves, mientras que una alta kresulta en una adaptaci´on m´as r´apida pero movimientos m´as bruscos y err´aticos. El valor de kse fij´o heur´ısticamente seg´un la respuesta del comportamiento observada en las pruebas. La figura 3.10 muestra un ejemplo real de adaptaci´on de un caso, en el que el robot hab´ıa aprendido como moverse cuando est´a frente a la porter´ıa (Fig. 3.10.a) mientras que en la situaci´on enfrentada durante la navegaci´on aut´onoma (Fig. 3.10.b) est´a girado hacia la izquierda 78 Aprendizaje de comportamientos b´asicos Figura 3.10: Ejemplo real de adaptaci´on de un caso. (a) Caso almacenado en el CBR. (b) Caso enfrentado durante la navegaci´on aut´onoma (c) Adaptaci´on del caso obtenido del CBR a la situaci´on actual. respecto a la situaci´on almacenada por el CBR. Si el robot se mueve hacia delante, como propone el CBR, el robot acabar´ıa en la banda del campo, pero aplicando adaptaci´on al caso recuperado se consigue modificar el comando de movimiento y que acabe alcanzando la porter´ıa (Fig. 3.10.c). 3.4.6.5. Descripci´on de la fase de revisi´on Para describir la fase de revisi´on usada en el CBR es necesario especificar como se realiza la validaci´on de las soluciones adaptadas y, en general, de las soluciones aportadas por el CBR. As´ı pues, la evaluaci´on o validaci´on de los casos aportados por el CBR se har´a de forma manual mediante observaci´on, por parte de un experto, de la ejecuci´on del sistema en modo aut´onomo, estudiando los ficheros de informaci´on del sistema cuando se vean situaciones an´omalas o extra˜nas para buscar las razones y corregirlas cuando sea posible. Navegaci´on basada en comportamientos aprendidos 79 En cualquier caso, y de forma general, se considerar´a que los casos devueltos por el CBR y la adaptaci´on de los casos son correctas siempre y cuando el robot consiga alcanzar su destino sin necesidad de intervenci´on externa. 3.4.6.6. Descripci´on de la fase de retenci´on Para describir la fase de revisi´on usada en el CBR es necesario especificar los tipos de aprendizajes que se usar´an en el CBR, siendo las alternativas usuales aprendizaje por observaci´on y aprendizaje por experiencia. Obviamente, en ambos comportamientos se usar´a aprendizaje por observaci´on, pues en este aprendizaje [142] es en el que se genera la base de conocimiento que usar´a el CBR cuando se ejecute de forma aut´onoma, es decir, la base de casos inicial del CBR. Concretamente, y como ya se ha comentado, el aprendizaje por observaci´on se realiza mediante control remoto del robot, lo cual permite asociar de forma simple y directa la informaci´on que llega al robot y que describe su entorno con los comandos de movimiento, que son la soluci´on ante dicho entorno para alcanzar su destino. Respecto al aprendizaje por experiencia, ´este se realiza cada vez que una nueva soluci´on es evaluada satisfactoriamente, incorpor´andose as´ı a la base de casos y suponiendo un aprendizaje por experiencia del propio CBR. Es decir, este aprendizaje se realiza cuando el robot est´a navegando de forma aut´onoma, no cuando est´a controlado por el operador a trav´es del joystick, y aprende como resolver nuevas situaciones mediante la adaptaci´on de la experiencia inicial proveniente del operador. As´ı pues, este aprendizaje est´a generado por la incorporaci´on de nuevos casos adaptados a la base de casos por lo que, como se coment´o en la descripci´on de la fase de reutilizaci´on, su utilizaci´on depender´a del comportamiento en cuesti´on y del uso o no de adaptaci´on: Comportamiento de b´usqueda de pelota. En este caso se aplicaba adaptaci´on nula, por lo que no se realizar´a ning´un aprendizaje por experiencia. Comportamiento de b´usqueda de porter´ıa. En este comportamiento, y como ya se coment´o en la secci´on 3.4.6.4, se realiza adaptaci´on de los casos porque s´olo con el aprendizaje por observaci´on no se llega a obtener un comportamiento adecuado del robot. As´ı pues, en este comportamiento s´ı se realiza aprendizaje por experiencia. Sin embargo, conviene destacar que a pesar de la adaptaci´on y el aprendizaje por experiencia, y como se comentar´a en la secci´on 3.5.2, ha sido necesario realizar nuevos entrenamientos espec´ıficos en situaciones 80 Aprendizaje de comportamientos b´asicos concretas (aprendizaje por observaci´on) en las que el sistema no estaba entrenado y la adaptaci´on no era suficiente para solventar la falta de conocimiento. As´ı pues, este comportamiento adem´as de aprendizaje por experiencia ha tenido varias etapas de aprendizaje por observaci´on. 3.5. Experimentos y resultados En esta secci´on se presentan los experimentos realizados para probar el correcto funcionamiento de los comportamientos comentados anteriormente. La plataforma sobre la que se han realizado las pruebas es un robot AIBO ERS7 de Sony y el entorno utilizado para los experimentos es un campo de f´utbol blanco delimitado por l´ıneas negras. Obviamente, el entorno utilizado no se adec´ua a los est´andares del campo en el entorno de la competici´on Robocup, pero el objetivo de estos experimentos no es sino probar que el aprendizaje de comportamientos mediante CBR propuesto es flexible y funcional en un entorno similar al de la Robocup. Durante las pruebas el AIBO no dispone de ning´un modelo del entorno, es decir, no tiene informaci´on a priori sobre el tama˜no de la pelota, las dimensiones del campo ni la posici´on de las l´ıneas. El entrenamiento del robot se ha realizado, como se ha comentado, mediante control remoto usando un joystick. En este apartado se describen los experimentos realizados correspondientes al comportamiento de b´usqueda de pelota, al comportamiento de b´usqueda de porter´ıa y una combinaci´on de ambos comportamientos, en la que el robot primero debe capturar la pelota para, posteriormente, dirigirse hacia la porter´ıa y marcar un gol. Durante los experimentos se recib´ıan las im´agenes a una tasa de unos 15 fotogramas por segundo a una resoluci´on de 216x160 p´ıxeles. Sin embargo, debido que el ordenador usado (Pentium III a 1GHz con 512 MB de RAM) solo era capaz de procesar una de cada 4 im´agenes recibidas, realmente durante los entrenamientos se almacena aproximadamente 4 casos por segundo en la base de casos del CBR. Aunque esta tasa de procesamiento pueda parecer baja, hay que tener en cuenta que la velocidad de movimiento del robot es relativamente baja, con lo que esa tasa de almacenamiento es m´as que suficiente. Antes de pasar a los experimentos, conviene recordar que ´estos no son m´as que una prueba de concepto para comprobar el enfoque propuesto basado en comportamientos aprendidos. As´ı pues, las tareas a realizar no son especialmente complejas y no contemplan, todav´ıa, a otros robots ni obst´aculos en el entorno, lo cual complicar´ıa tanto la definici´on del caso como el entrena- Experimentos y resultados 81 miento. Esto se tendr´a en consideraci´on en pr´oximos cap´ıtulos. 3.5.1. Comportamiento de b´usqueda de pelota Este comportamiento tiene como objetivo que el robot sea capaz de buscar y capturar una pelota situada en cualquier punto del campo de juego. Aunque se trate de un comportamiento muy simple, pero es el comportamiento b´asico con el que se han comenzado a realizar aprendizajes con CBR y es mejor partir de un ejemplo sencillo y f´acilmente comprensible. En los siguientes apartados se detallan las secuencias de entrenamiento realizadas para el aprendizaje por observaci´on de este comportamiento y posteriormente los resultados obtenidos. 3.5.1.1. Entrenamiento del comportamiento Para el aprendizaje por observaci´on se han realizado tres secuencias de entrenamiento distintas, que son suficientes para que este comportamiento se pueda realizar satisfactoriamente. La figura 3.11 muestra las secuencias de entrenamiento realizadas para este comportamiento. En la figura 3.11.a el AIBO est´a orientado hacia la pelota a una determinada distancia y aprende como acercarse a ´esta hasta alcanzarla. En la figura 3.11.b y c la pelota est´a inicialmente situada a la izquierda y derecha del robot respectivamente, aprendiendo el robot en cada caso como orientarse hacia la pelota, momento en el cual entrar´ıa en funcionamiento el primer entrenamiento realizado para acercarse a capturar la pelota. As´ı pues, la primera secuencia de entrenamiento es usada para aprender como acercarse a la pelota cuando ya est´a orientado hacia ´esta, mientras que en las dos ´ultimas el robot aprende a girar hasta estar orientado hacia la pelota. El n´umero de casos final de este entrenamiento es de 60 casos, que a una tasa aproximada de 4 casos por segundo supone un entrenamiento de unos 15 segundos para obtener este comportamiento. Respecto al entrenamiento realizado, debe tenerse en cuenta que la base de casos del CBR s´olo almacena casos si el AIBO detecta la pelota en la imagen y el robot est´a movi´endose, descart´andose los patrones en los que est´a parado o no se detecte la pelota. Adem´as, hay que destacar que en la base de casos de este entrenamiento se a˜nade un patr´on CBR especial, definido a priori, que hace girar al robot hacia la izquierda cuando no se detecta ninguna pelota en la imagen (patr´on de entrada nulo). De esta forma, si el robot no encuentra la pelota en el campo de visi´on, comenzar´a a dar vueltas hasta que la encuentre. 88 Aprendizaje de comportamientos b´asicos Figura 3.19: Prueba final de b´usqueda de porter´ıa reactiva usando CBR con adaptaci´on 3.5.3. Comportamiento global: b´usqueda de pelota y porter´ıa Finalmente, tras la comprobaci´on del correcto funcionamiento de los comportamientos de b´usqueda de pelota y b´usqueda de porter´ıa se han enlazado secuencialmente ambos comportamientos para conseguir un comportamiento global que permita capturar la pelota y, posteriormente, llevarla hasta la porter´ıa. De hecho, la conmutaci´on de un comportamiento a otro depende de si el robot ha capturado o no la pelota, de forma que si el robot ha capturado la pelota activa el comportamiento de b´usqueda de porter´ıa, mientras que si no la ha capturado activa el comportamiento de b´usqueda de pelota. As´ı pues, esta tarea permite mostrar como dos comportamientos simples pueden ser unidos para desarrollar una tarea m´as compleja de un modo sencillo. Para ello, en primer lugar el AIBO activa el comportamiento de seguir pelota en el campo hasta que la captura, detectando la pelota capturada gracias al sensor pectoral del robot. En ese instante, se activa el comportamiento de buscar porter´ıa, con lo que el robot lleva la pelota capturada hacia la porter´ıa, donde finalmente marca gol. Si tras capturar la pelota y activar el comportamiento de b´usqueda de porter´ıa el robot detecta que ha perdido la pelota (la cual puede escaparse del AIBO por los propios movimientos del robot o bien por las imperfecciones del campo montado), se volver´ıa a activar el comportamiento de b´usqueda de pelota, comenzando de nuevo la secuencia. La figura 3.20 muestra una secuencia de im´agenes del comportamiento global en funcionamiento. En primer lugar, el AIBO ejecuta el comportamiento de seguimiento de pelota. Como no detecta la pelota, gira hacia la Conclusiones 89 Figura 3.20: Im´agenes reales del comportamiento global (prueba 1). izquierda hasta que ´esta entra dentro del campo de visi´on y entonces lanza el comportamiento de seguimiento de pelota para capturarla. En ese instante entra en acci´on el comportamiento de b´usqueda de porter´ıa, que dirige al AIBO hacia la porter´ıa con la pelota capturada. Finalmente, cuando el AIBO detecta que est´a suficientemente cerca de la porter´ıa, chuta la pelota y marca un gol. En la figura 3.21 se muestra otra prueba con el mismo comportamiento global, en este caso mostrando una visi´on cenital. En esta prueba, al igual que en el caso anterior, el robot consigue capturar la pelota, alcanzar la porter´ıa y chutar a gol sin mayores problemas. 3.6. Conclusiones En este cap´ıtulo se ha presentado una t´ecnica que permite la construcci´on de comportamientos para navegaci´on reactiva bas´andose en aprendizaje LfD usando CBR. Concretamente, el sistema de aprendizaje consiste en que una persona, que hace de supervisor, realice el entrenamiento de un robot, controlado remotamente mediante un joystick, ense˜nando as´ı al robot el comportamiento que se quiere realizar. De esta forma se puede relacionar de un modo sencillo y directo lo que percibe el robot (en el caso del robot usado mediante visi´on a trav´es de la c´amara integrada) y los comandos de movimiento que el operador est´a enviado al robot. Una de las ventajas de este enfoque es que la cinem´atica y din´amica del robot as´ı como los errores de calibraci´on y los errores sistem´aticos son 90 Aprendizaje de comportamientos b´asicos Figura 3.21: Im´agenes reales del comportamiento global (prueba 2). impl´ıcitamente tomados en cuenta por el supervisor, el cual los compensa naturalmente durante el entrenamiento. Por otro lado, este enfoque permite el desarrollo de comportamientos ad hoc de una forma sencilla sin tener que realizar ning´un modelado del entorno. Adem´as, y debido a la naturaleza reactiva del comportamiento, los errores puntuales no son, en principio, un problema ya que generalmente son absorbidos por la propia inercia del sistema. Sin embargo, hay que tener en cuenta tambi´en que este enfoque tiene una considerable dependencia con la definici´on de los casos del CBR, por lo que es conveniente prestar especial atenci´on a esta fase y escoger una definici´on de caso eficiente, ya que la informaci´on que contengan los par´ametros que forman el caso no deber´ıa estar correlada entre ellos ni repetida. Tambi´en hay que tener en cuenta que es recomendable que los par´ametros usados en el caso sean fiables y f´aciles de extraer de los sensores de entrada. Es importante tambi´en tener presente que los entrenamientos realizados deben ser lo m´as gen´ericos posible y cubrir la m´axima cantidad de situaciones pues, como se ha podido comprobar en este cap´ıtulo, la falta de entrenamiento b´asico en situaciones importantes puede ser suplido parcialmente por la adaptaci´on y el aprendizaje por experiencia, pero no todas las situaciones pueden resolverse mediante adaptaci´on, por lo que hay que hacer un estudio de las posibles situaciones que deber´an enfrentarse y tratar de entrenarlas todas para conseguir una mejor respuesta del sistema. Para comprobar la viabilidad de este enfoque se ha propuesto una prueba de concepto consistente en el aprendizaje de dos comportamientos sim- Conclusiones 91 ples que se enlazan secuencialmente para realizar una tarea m´as compleja. Los comportamientos implementados son sencillos, sin embargo, cumplen su objetivo, que no es otro que demostrar que se pueden desarrollar distintos comportamientos reactivos que permitan la navegaci´on de un robot mediante aprendizaje, sin necesidad de modificar el sistema. De hecho, para generar distintos comportamientos tan s´olo ser´ıa necesario determinar los par´ametros del caso que definen tanto la situaci´on actual como su soluci´on y entrenar al robot para que realice el comportamiento deseado. Los experimentos se han realizado con un robot AIBO ERS-7 con una c´amara integrada en un entorno en el que ´unicamente hay una pelota rosa y un campo de f´utbol de reducidas dimensiones delimitado por l´ıneas. Destacar que en estas pruebas no se han tenido en cuenta m´as robots de momento, pues la coordinaci´on con otros robots ser´a introducida en pr´oximos cap´ıtulos. As´ı pues, en los experimentos se ha mostrado como se ha conseguido un comportamiento complejo a partir de la secuencia de dos comportamientos aprendidos m´as simples. Concretamente, el comportamiento consist´ıa en conseguir que un robot AIBO capturase una pelota y la llevase hasta la porter´ıa. Para ello se ha dividido este comportamiento en dos m´as sencillos: b´usqueda de pelota y b´usqueda de porter´ıa. La activaci´on y desactivaci´on de estos m´odulos depende de si el robot ha capturado o no la pelota. Ambos comportamientos han sido aprendidos mediante LfD usando CBR, siendo las componentes del caso CBR en el primer comportamiento las coordenadas de la pelota en la imagen, su tama˜no y la posici´on de la cabeza respecto al cuerpo, y en el segundo comportamiento las cuatro l´ıneas dominantes detectadas en el campo de visi´on, definidas mediante sus par´ametros en el dominio de Hough, y el ´angulo de la cabeza del robot respecto al cuerpo. La salida del caso CBR en ambos comportamientos es el comando de movimiento frontal y de rotaci´on normalizado que debe realizar el robot para alcanzar su objetivo, sea el que sea seg´un el comportamiento. Durante el entrenamiento, se generar´a la base de casos CBR que almacena los comandos de movimiento realizados por el operador asociados a la situaci´on concreta en la que los aplic´o. Como se ha comentado antes, el entrenamiento de los comportamientos se ha realizado controlando remotamente el robot mediante un joystick, lo que permite definir f´acilmente las trayectorias que se desee que el robot aprenda. Tras finalizar el entrenamiento, el robot dispone, a trav´es de la base de casos CBR, de la informaci´on necesaria para poder funcionar de forma aut´onoma, obteniendo para ello, de la base de casos, los comandos de movimiento a realizar en cada situaci´on. Hay que indicar que la adaptaci´on en el CBR es una t´ecnica que permite el aprendizaje autom´atico a partir de nuevas situaciones. Sin embargo, tam- 92 Aprendizaje de comportamientos b´asicos bi´en hay que ser conscientes de que la base de conocimientos inicial es muy importante y que si esta no cubre las situaciones m´as importantes que debe enfrentar el robot, la adaptaci´on puede no ser suficiente para que el sistema afronte nuevas situaciones satisfactoriamente, como se ha comprobado en los experimentos. As´ı pues, en las pruebas realizadas se ha comprobado que el planteamiento propuesto resulta adecuado para entrenar comportamientos simples con un ´unico robot. Sin embargo, y dado que el objetivo final de este trabajo es la realizaci´on de un sistema de coordinaci´on multi-agente basado en comportamientos aprendidos, este enfoque no se considera apropiado para el sistema que se pretende realizar. La raz´on es que en los comportamientos mostrados en este cap´ıtulo no se ha usado ning´un tipo de localizaci´on expl´ıcita, sino que la localizaci´on se realiza de forma impl´ıcita en el mismo aprendizaje del comportamiento. Es decir, en ning´un momento se conoce directamente la posici´on del robot respecto a ning´un elemento o punto referencia concreto, pues el objetivo de los comportamientos es obtener el movimiento a realizar para alcanzar el destino en funci´on de la situaci´on actual, descrita por lo que el robot visualiza en ese mismo instante. El problema es que, si se usa este enfoque basado en localizaci´on impl´ıcita para el sistema coordinado a desarrollar, y no se permite la comunicaci´on entre los robots, las posibilidades de coordinaci´on se limitar´ıan a cuando ´estos se viesen directamente, pudiendo evitarse como obst´aculos, o bien a realizar tareas conjuntas para empujar o alcanzar una meta com´un en la que tengan que colaborar, pero ser´ıa dif´ıcil la realizaci´on de otro tipo de comportamientos coordinados m´as sofisticados. Sin embargo, si se permitiese la comunicaci´on entre los robots, el problema ser´ıa que la definici´on del caso resultar´ıa demasiado compleja al tener que a˜nadir en la descripci´on de la situaci´on actual todos los par´ametros (l´ıneas de campo o referencias visuales) de los dem´as robots para tener en cuenta la posici´on propia y la de los otros robots impl´ıcitamente en el entrenamiento. Sin embargo, esto complicar´ıa enormemente la definici´on del caso, el entrenamiento y la b´usqueda dentro de la base de casos, por lo que no ser´ıa una soluci´on viable. As´ı pues, se considera que la mejor soluci´on a este problema ser´ıa disponer de un sistema de localizaci´on expl´ıcita que permita obtener la posici´on de los dem´as robots respecto a alg´un punto de referencia de forma expresa para permitir comportamientos coordinados m´as complejos, lo cual se tratar´a en los siguientes cap´ıtulos. Cap´ıtulo 4 Sistema de localizaci´on 4.1. Introducci´on Los MRS han sido aplicados en la ´ultima d´ecada en una gran variedad de ´areas as´ı como a multitud de tareas. De hecho, los MRS han sido aplicados en una gran variedad de escenarios [156], como los robots auto-organizados [11, 92], la coordinaci´on de robots mediante modelos biol´ogicos [143], tales como los enjambres de robots [80,85], vigilancia y exploraci´on [34], tareas militares [63, 95], operaciones de rescate [87], entornos industriales [127], ambientes hostiles o peligrosos [42], etc. La principal ventaja de los MRS es que permiten la realizaci´on de una determinada tarea m´as r´apido y m´as eficientemente [9, 52, 152, 156] que un s´olo robot, ya que los robots del MRS pueden estar en distintos sitios al mismo tiempo, pueden desarrollar tareas concurrentes y cooperativas y, en general, pueden descomponer una tarea compleja en otras m´as simples. Sin embargo, no todo son ventajas en los MRS, ya que en estos sistemas la trayectoria de cada uno de los agentes que los componen no est´a definida ´unicamente por su posici´on con respecto al objetivo, sino tambi´en por su posici´on relativa con respecto a los dem´as agentes del sistema, ya que los dem´as agentes act´uan como obst´aculos, a pesar de que puedan estar cooperando en la resoluci´on de la misma tarea. As´ı, por ejemplo, en entornos din´amicos con elementos en movimiento, tareas como la navegaci´on, localizaci´on y actualizaci´on de los mapas del entorno resulta m´as compleja e importante en los MRS que en sistemas rob´oticos individuales. Por lo tanto, para la correcta navegaci´on de los distintos agentes de un sistema MRS y para evitar colisiones y el mejor desempe˜no posible, es crucial una correcta y r´apida localizaci´on de los miembros del sistema. Sin embargo, el uso de una localizaci´on que permita conocer la posici´on de 93 94 Sistema de localizaci´on otros robots respecto a la de uno mismo implica la necesidad de un punto de referencia en el entorno que permita relacionar el sistema de referencia local del robot con uno externo com´un que sirva de nexo con el resto de robots, lo que requiere un modelado del entorno. Por lo tanto, el uso de un sistema de localizaci´on implica que el sistema no ser´ıa puramente reactivo, pues un sistema reactivo supone no usar un modelado del entorno [147]. Sin embargo, dando por hecho que al usar localizaci´on el sistema no va a ser reactivo puro, hay sistemas de localizaci´on que son m´as reactivos que otros, en el sentido de que requerir´an un modelado del entorno m´as o menos estricto, as´ı como la posibilidad de requerir o no el uso de componentes temporales como una memoria. As´ı pues, se tratar´a de encontrar un sistema de localizaci´on lo m´as reactivo posible para el sistema de coordinaci´on a desarrollar. Como se ha comentado, en las pruebas del sistema coordinado a desarrollar se utilizar´an robots AIBO ERS-7 de Sony en un entorno de trabajo similar al entorno de la liga de f´utbol rob´otica de la Robocup. La localizaci´on en este entorno suele realizarse mediante visi´on, el principal sensor de estos robots, usando marcas artificiales de colores situadas en posiciones concretas del campo de la Robocup [37,108,110,140]. Adem´as, en este entorno es normal que se haga uso de filtros de Kalman [41, 89] o filtros de part´ıculas [108, 110, 151] para mejorar la precisi´on y la estabilidad de la posici´on obtenida. Sin embargo, este tipo de localizaci´on, a pesar de ser ampliamente usada, no encaja con el enfoque reactivo propuesto en el cap´ıtulo anterior debido al estricto modelado del entorno y el uso de una memoria (historial de observaciones de los filtros). Una alternativa m´as reactiva ser´ıa evitar el uso de una componente temporal (usando una localizaci´on instant´anea o inmediata) y reducir las restricciones de modelado del entorno al m´ınimo. As´ı pues, una opci´on que encajar´ıa mejor con un sistema reactivo ser´ıa que los robots obtuviesen la posici´on de los compa˜neros cuando se detecten directamente. Sin embargo, esto limitar´ıa las posibilidades de coordinaci´on ´unicamente a momentos puntuales o a comportamientos similares a los de los enjambres de robots en los que todos tienen una meta en com´un, como empujar un objeto. Otra alternativa ser´ıa el uso de un sistema de localizaci´on basado en objetos comunes a partir del cual puedan localizarse. La opci´on m´as reactiva de este enfoque ser´ıa que los robots se localizasen respecto a cualquier objeto en com´un, minimizando el modelado del entorno. Sin embargo, esto ser´ıa demasiado complejo, por lo que generalmente suelen usarse objetos f´aciles de detectar, como objetos de colores espec´ıficos. Otra alternativa ser´ıa el uso de marcas fiduciarias, que si bien suponen un modelado m´as estricto del entorno (al usar marcas espec´ıficas) pero pueden permitir el posiciona- Tipos de localizaci´on 95 miento instant´aneo de los robots a partir de la imagen actual (sin el uso de una componente temporal), resultando un enfoque m´as reactivo que el usado com´unmente en la Robocup. As´ı pues, en este cap´ıtulo se estudiar´an distintas alternativas de localizaci´on, determinando cu´ales de ellas son factibles para su uso en el sistema coordinado a desarrollar manteniendo, en la medida de lo posible, el enfoque reactivo de ´este. El cap´ıtulo se estructura de la siguiente forma. En primer lugar, en la secci´on 4.2 se hace una breve introducci´on a los distintos tipos de localizaci´on, comentando sus ventajas y desventajas. Tras esta introducci´on, se indicar´an las t´ecnicas de localizaci´on que se tendr´an en cuenta para el sistema de coordinaci´on propuesto (secci´on 4.3). Posteriormente, se har´a una prueba preliminar de las t´ecnicas de localizaci´on consideradas para comprobar su adecuaci´on y viabilidad (secci´on 4.4). Concretamente para probar cada uno de los sistemas de localizaci´on se realizar´a una prueba de navegaci´on segura entre dos robots AIBO ERS7 usando navegaci´on basada en PFA. Por ´ultimo en la secci´on 4.5 se presentan las conclusiones del cap´ıtulo indicando el sistema de localizaci´on que se estima m´as adecuado. 4.2. Tipos de localizaci´on Conocer la posici´on y orientaci´on en un entorno es una informaci´on fundamental que todo robot debe ser capaz de calcular para moverse e interactuar con su entorno, permitiendo que ´este realice las tareas que tenga asignadas [20]. Dado que es una tarea fundamental para la rob´otica m´ovil, ha sido un ´area muy activa [20,32,140] desde el comienzo de la rob´otica, existiendo una gran variedad de t´ecnicas y m´etodos para la estima y c´alculo de la posici´on. As´ı por ejemplo, las t´ecnicas de localizaci´on variar´an en funci´on de la informaci´on disponible del entorno (utilizaci´on de marcas naturales [150] o artificiales [117]), de los sensores disponibles (l´aser [133], sonar [89], visi´on [151] o una combinaci´on de distintos sensores [45]) o de la plataforma rob´otica (con ruedas [138] o con extremidades [48,100]). En cualquier caso, la localizaci´on se puede dividir en dos categor´ıas: Localizaci´on seg´un el tipo de posicionamiento. En esta categor´ıa el posicionamiento puede ser relativo o absoluto, siendo en la localizaci´on relativa (tambi´en referenciada en ocasiones como seguimiento) el posicionamiento del robot en todo momento relativo a la posici´on inicial de ´este, mientras que en el segundo caso la posici´on es absoluta respecto a alg´un mapa o modelado del entorno. 96 Sistema de localizaci´on Localizaci´on seg´un el modelado del entorno. En este caso se dividen las t´ecnicas de localizaci´on seg´un si se dispone de un modelado o mapa a priori del entorno, si el mapa se construye antes de realizar la localizaci´on o si no existe ning´un tipo de mapa del entorno. A pesar de esta clasificaci´on en dos grandes grupos, estos no son excluyentes, pues de hecho es normal usar localizaci´on relativa junto con localizaci´on absoluta con mapa a priori (por ejemplo) para corregir el primer tipo de localizaci´on. A continuaci´on se cuentan con m´as detalle cada una de estas t´ecnicas. 4.2.1. Localizaci´on seg´un el tipo de posicionamiento Una de las clasificaciones m´as usuales cuando se trata de localizaci´on en rob´otica m´ovil es la relativa al tipo de posicionamiento [22], el cual puede ser relativo o absoluto. En el primer caso el posicionamiento del robot se hace de forma relativa a la posici´on de inicio, mientras que en el segundo se hace de forma absoluta respecto al entorno, teniendo cada uno sus ventajas y sus desventajas como se comentar´a a continuaci´on. 4.2.1.1. Localizaci´on relativa En la localizaci´on relativa o local la localizaci´on del robot se realiza de forma relativa a la posici´on de inicio de este, que si bien no tiene porque ser conocida, en general suele ser conocida o se tiene una estimaci´on aproximada de ´esta [20,32]. La localizaci´on relativa es una de las m´as sencillas y b´asicas, siendo usada desde los comienzos de la rob´otica. La forma m´as com´un de realizar la localizaci´on relativa es mediante odometr´ıa o mediante navegaci´on inercial [22]: Odometr´ıa. La odometr´ıa es un m´etodo b´asico y simple para estimaci´on de la posici´on a partir de un punto de origen. Se basa en calcular la posici´on actual en funci´on de cuanto ha avanzado el robot o a que velocidad ha avanzado y durante cuanto tiempo. Para obtener esta informaci´on, normalmente se utilizan unos dispositivos acoplados a las ruedas del robot. La principal ventaja de este m´etodo es su sencillez, facilidad de uso, y que es autocontenido y no necesita de ninguna informaci´on sobre el entorno, permitiendo siempre ofrecer una estimaci´on de la posici´on respecto al origen de movimiento. Adem´as, este m´etodo es muy barato pues los sensores son bastante simples. Tipos de localizaci´on 97 Sin embargo, esta t´ecnica tiene una gran cantidad de desventajas. Por un lado, la estimaci´on de la posici´on tiene errores provenientes de los sensores (errores de calibraci´on y resoluci´on limitada), del tipo de locomoci´on (desalineaci´on de las ruedas, deslizamientos y diferencias de fricci´on seg´un el suelo, incertidumbres en el radio exacto de la rueda o en el avance de las extremidades), etc. Estos errores son acumulativos, lo que hace que esta t´ecnica s´olo sea v´alida en cortos per´ıodos de tiempo, pues el error en la estimaci´on de la posici´on es acumulable (creciendo sin l´ımite), de forma que a partir de un determinado momento la posici´on no ser´ıa fiable. As´ı pues, la odometr´ıa necesita utilizar alguna t´ecnica que permita, de forma peri´odica, corregir parcialmente el error acumulado y reducir la incertidumbre, obteniendo as´ı una mejor estima de la posici´on real. Otro problema inherente a esta t´ecnica es que es m´as adecuada para robots con ruedas que para robots con extremidades, pues en robots con ruedas es m´as sencillo estimar el avance real de ´este (a pesar de los errores ya comentados). Sin embargo, en el caso de robots con extremidades los errores cometidos en la estimaci´on del avance son mucho mayores que en el caso de los robots con ruedas, por lo que la localizaci´on basada ´unicamente en odometr´ıa es poco viable. Navegaci´on inercial. Esta t´ecnica, similar a la anterior, se basa en el uso de gir´oscopos y/o aceler´ometros para estimar la rotaci´on y aceleraci´on del robot de forma que, mediante esta informaci´on, se pueda estimar su avance. La principal ventaja de esta t´ecnica es la ya comentada en el caso de la odometr´ıa, y es que es un m´etodo autocontenido, que se puede aplicar sin necesidad de informaci´on externa. Sin embargo, el problema de esta t´ecnica es el mismo que el de la odometr´ıa, y es que el error crece sin l´ımite con el tiempo por lo que esta t´ecnica s´olo es v´alida en breves per´ıodos de tiempo, siendo necesaria su correcci´on peri´odicamente. Adem´as, los sensores necesarios para este tipo de localizaci´on son mucho m´as caros que en el caso de la odometr´ıa. As´ı pues, y como resumen, si bien la localizaci´on relativa resulta sencilla y aplicable en la mayor´ıa de entornos, pero tiene el problema de que requiere la correcci´on peri´odica de la posici´on estimada mediante t´ecnicas como los filtros de Kalman [41, 89] o filtros de part´ıculas [151] junto con marcas del entorno. 104 Sistema de localizaci´on memoria (historial de observaciones previas). Una alternativa m´as acorde y que tambi´en permitir´ıa un posicionamiento con bastante precisi´on ser´ıa el uso de marcas fiduciarias (fiducial marker en ingl´es). La ventaja de este enfoque es que se podr´ıa obtener la posici´on de los robots respecto a la marca a partir de la imagen actual y, por lo tanto, de una forma m´as reactiva al no usar m´as que la informaci´on actual de los sensores (eliminando la componente temporal). Sin embargo, este enfoque todav´ıa supone un modelado del entorno bastante espec´ıfico. As´ı pues, otro enfoque m´as acorde con la filosof´ıa de los comportamientos reactivos ser´ıa la localizaci´on basada ´unicamente en los objetos en com´un que puedan encontrarse en el entorno (como objetos de un color espec´ıfico) y que est´en visualizando los robots en el momento actual. Este enfoque ser´ıa el m´as reactivo, al requerir un menor modelado del entorno, pero tambi´en ser´ıa el menos preciso y m´as limitado en las situaciones en las que podr´ıa usarse. As´ı pues, a continuaci´on se comentar´a el funcionamiento de la localizaci´on basada en objetos comunes, marcas fiduciarias y balizas de colores usando filtrado, presentando posteriormente algunos experimentos realizados para comprobar la viabilidad de su uso para el sistema de coordinaci´on que se pretende desarrollar. 4.3.1. Localizaci´on basada en objetos comunes Un requisito general para establecer la localizaci´on entre varios robots es un sistema de referencia com´un, es decir, establecer de alguna manera una referencia entre el sistema de referencia local del robot y el sistema de referencia global del entorno. Dado el enfoque reactivo del sistema propuesto, la localizaci´on deber´ıa ser lo m´as b´asica posible, suponiendo el m´ınimo modelado del entorno y no necesitar una componente temporal o memoria. As´ı pues, lo ideal ser´ıa usar una localizaci´on inmediata o instant´anea respecto a cualquier tipo de objeto o patr´on que se pudiese identificar en el entorno. Sin embargo, esto es demasiado complejo, por lo que hay que delimitar los objetos que pueden servir como referencia a objetos concretos y f´aciles de identificar, aunque lo m´as gen´ericos posible, como podr´ıan ser objetos de un color espec´ıfico (dado que la localizaci´on a usar se basa en visi´on). Una forma usual de obtener la posici´on usando referencias visuales o balizas es mediante triangulaci´on, la cual permite el posicionamiento mediante la aplicaci´on de la trigonometr´ıa a partir de la informaci´on obtenida de dos o m´as balizas. Sin embargo, dado que se trata de evitar el uso de memoria en el sistema, para el uso de la triangulaci´on es necesario que las marcas u objetos de referencia a usar est´en todos dentro del campo de visi´on al mismo tiempo, lo cual no es f´acil ni viable en muchas ocasiones. Una forma de solucionar este problema ser´ıa hacer uso de la idea de la Localizaci´on visual basada en marcas 105 visi´on est´ereo, de forma que dos robots estimen su posici´on a partir de la disparidad que presenta un objeto desde su punto de vista. En este caso, ser´ıa necesario s´olo un elemento com´un en el campo de visi´on para establecer el posicionamiento, as´ı como permitir la comunicaci´on entre los robots. Estos dos enfoques ser´an los comentados en primer lugar, pues son dos alternativas que, en principio, encajar´ıan con un enfoque reactivo sin memoria y con un modelado m´ınimo del entorno al usar como referencia objetos generales, cuya ´unica limitaci´on es su color. 4.3.1.1. Localizaci´on basada en triangulaci´on La triangulaci´on consiste en el uso de la trigonometr´ıa para determinar la posici´on de puntos o distancias y es una de las t´ecnicas m´as cl´asicas para determinar la posici´on de un robot en funci´on a una serie de balizas o marcas repartidas en el entorno [20,32] independientemente de si las balizas son visuales [27], sonoras [119] o de radiofrecuencia [111]. De hecho, la triangulaci´on por radiofrecuencia es un tema de estudio muy activo ´ultimamente, pues resulta muy pr´actico al suponer un modelado m´ınimo del entorno, pero suele tener errores muy grandes y s´olo permite estimar la posici´on, no la orientaci´on. Figura 4.1: (a) Estimaci´on de posici´on de objetos ocultos usando triangulaci´on. (b) Estimaci´on de la posici´on mediante triangulaci´on usando dos objetos en com´un. As´ı pues, dejando de lado la triangulaci´on por radiofrecuencia queda la alternativa de la triangulaci´on por visi´on, mostr´andose en la figura 4.1 un par de ejemplos en los que se podr´ıa aplicar. En el ejemplo de la figura 4.1.a, el robot R1 podr´ıa estimar mediante triangulaci´on la distancia a la que est´a el compa˜nero de la pelota y enviarle su posici´on aproximada. Para ello, ser´ıa necesario aplicar la ley del seno (ec. 4.1) y del coseno (ec. 4.2) usando como 106 Sistema de localizaci´on informaci´on de partida la distancia a la que est´a su compa˜nero, la pelota y el ´angulo entre ambas. A sen(α)=B sen(β)(4.1) C2=A2+B2−2ABcos(α) (4.2) Sin embargo, la aplicaci´on m´as usual de la triangulaci´on, aunque partiendo del mismo enfoque, es el mostrado en la figura 4.1.b, en el que los robots puede estimar su posici´on a partir de la visualizaci´on de dos marcas u objetos reconocibles e identificables, sirviendo estos objetos como eje de referencia para que los robots puedan compartir su posici´on. El problema de este enfoque, sin el uso de memoria, es que requiere que las marcas a usar est´en visibles simult´aneamente y sean identificables, lo cual es dif´ıcil de conseguir en la realidad. Adem´as, aunque en teor´ıa baste con dos marcas para establecer el posicionamiento mediante triangulaci´on, en la pr´actica, debido a los errores, es recomendable el uso de m´as elementos para corregir el posicionamiento obtenido. 4.3.1.2. Localizaci´on basada en visi´on est´ereo Para evitar la necesidad de que haya varios objetos simult´aneamente en el campo de visi´on para posicionarse, se puede utilizar otro enfoque basado en la idea de la visi´on estereosc´opica. La visi´on estereosc´opica o visi´on est´ereo es una t´ecnica que permite obtener informaci´on tridimensional a partir de im´agenes en 2 dimensiones. Esta t´ecnica est´a basada en la visi´on humana, y de forma m´as gen´erica en la visi´on de muchos animales, los cuales usan las im´agenes capturadas por los ojos para estimar la profundidad o distancia a la que se encuentran objetos u otros animales. Concretamente, la estereoscop´ıa artificial permite obtener la distancia de los objetos visualizados respecto a las c´amaras que forman un par est´ereo. El c´alculo de la profundidad en la visi´on est´ereo parte de la suposici´on de que las dos c´amaras que capturan las im´agenes tienen la misma distancia focal, sus ejes ´opticos son paralelos y las im´agenes generadas por ambas c´amaras est´an en el mismo plano (Fig. 4.2.a). Teniendo en cuenta estas consideraciones, la profundidad o distancia del objeto observado respecto a las c´amaras est´a determinada por la siguiente ecuaci´on: Dfocal ∗Dcamaras =Dobjeto ∗Disp (4.3) Localizaci´on visual basada en marcas 107 Siendo Dfocal la distancia focal de las c´amaras, Dcamaras la distancia entre las c´amaras, Dobjeto la distancia al objeto a localizar o profundidad y Disp la disparidad entre las dos im´agenes, calculada como Disp =X1−X2, representando la diferencia en p´ıxeles de la posici´on de un objeto entre las dos im´agenes de las c´amaras. Figura 4.2: (a) Visi´on est´ereo y par´ametros para el c´alculo de la disparidad. (b) y (c) Importancia de la orientaci´on de los robots para la localizaci´on mediante visi´on estereosc´opica. Sin embargo, esta ecuaci´on se puede ver de otra forma, pues si se supone conocida la distancia de un objeto respecto a dos c´amaras que cumplan las condiciones anteriores, lo que se puede estimar es la distancia entre estas dos c´amaras. Es decir, partiendo de dos robots (Fig. 4.2.b), cada uno con una c´amara direccional, que est´an observando un objeto en com´un de tama˜no conocido (lo que permite obtener la distancia de ´este), se podr´ıa calcular la distancia entre ambos robots, permitiendo establecer una estimaci´on de la posici´on relativa entre ellos. El uso de esta t´ecnica requiere, por tanto, que ambos robots compartan su informaci´on visual para determinar la disparidad de las im´agenes de cada uno de los robots, por lo que se tratar´ıa de una t´ecnica de localizaci´on cooperativa. Sin embargo, para poder usar esta t´ecnica de localizaci´on es importante tener en cuenta las suposiciones de partida de la ecuaci´on 4.3 para el c´alculo de la profundidad. Por lo tanto, para que la estimaci´on de la distancia entre los robots sea fiable estos deben estar alineados y en el mismo plano (como las c´amaras del par est´ereo), pues cuanto m´as desalineados est´en los robots m´as errores se obtendr´a en la estimaci´on de su posici´on. As´ı, por ejemplo, la figura 4.2.b muestra un ejemplo de situaci´on ideal en el que esta localizaci´on podr´ıa ser aplicable obteni´endose una buena estimaci´on de la distancia entre los robots. Sin embargo, la figura 4.2.c muestra una situaci´on en la que esta 108 Sistema de localizaci´on t´ecnica no ser´ıa aplicable pues los valores obtenidos no ser´ıan correctos debido a la variaci´on de ´angulo de las c´amaras de ambos robots. As´ı pues, para usar esta t´ecnica habr´ıa que estimar si es aplicable o no, lo cual ser´ıa realmente complejo en un ambiente real. En el caso del entorno de un campo de f´utbol como el de la Robocup, sin embargo, una opci´on para calcular si ambos robots est´an en paralelo, o aproximadamente en paralelo, ser´ıa estimar su orientaci´on cuando visualicen alguna l´ınea del campo, lo que les dar´ıa una idea de su orientaci´on. En cualquier caso, para poder determinar si esta localizaci´on es aplicable o no pr´acticamente habr´ıa que tener una buena estimaci´on de la posici´on posici´on de los robots, dado el requisito de la alineaci´on y la posici´on en el mismo plano de ´estos para su aplicaci´on. Por ´ultimo, otro problema de este enfoque es que es necesario saber qu´e robot est´a a la derecha y cu´al a la izquierda para poder aplicar la t´ecnica adecuadamente. 4.3.2. Localizaci´on basada en marcas fiduciarias La localizaci´on basada en marcas fiduciarias requiere, como es l´ogico, el uso de marcas espec´ıficas f´acilmente reconocibles en el entorno. Las marcas fiduciarias son marcas de referencia concretas, como pueden ser los c´odigos QR, las marcas ARToolkit o las marcas reacTIVision, que permite obtener la posici´on de la c´amara respecto a la marca y viceversa. Este tipo de localizaci´on, por tanto, implica un modelado del entorno m´as concreto y exigente que en el caso anterior, que se basaba ´unicamente en la detecci´on de objetos de un color determinado, que si bien implica igualmente un modelado del entorno, pero era m´as gen´erico. Por lo tanto, este enfoque resulta menos reactivo que el planteamiento anterior, aunque tiene la ventaja de que permite obtener el posicionamiento ´unicamente a partir la imagen actual, por lo que no requiere ning´un uso de memoria. Una alternativa m´as reactiva al uso de marcas fiduciarias ser´ıa el reconocimiento de marcas naturales. El problema de este enfoque es que suele requerir una mayor capacidad de c´omputo, adem´as de que es necesario que en el entorno haya elementos caracter´ısticos que puedan funcionar como marcas naturales, y dado que el entorno de pruebas usado en los experimentos es un entorno artificial similar al de la Robocup no resultar´ıa un enfoque viable. As´ı pues, de entre las distintas alternativas de marcas fiduciarias disponibles, se ha decidido usar concretamente marcas ARToolkit [64,82], ya que permite el posicionamiento 3D de la c´amara respecto a la marca y se ha usado anteriormente para el desarrollo de aplicaciones de Realidad Aumentada (RA) con buenos resultados. As´ı pues, ARToolkit es una librer´ıa realizada en C distribuida bajo licencia GPL que est´a especialmente dise˜nada para la implementaci´on de aplicaciones de RA. Para ello, esta librer´ıa proporciona una Localizaci´on visual basada en marcas 109 serie de funciones para la captura de v´ıdeo y para la b´usqueda de patrones ARToolkit en tiempo real. Concretamente, los patrones ARToolkit (Fig. 4.3.a) son unas marcas visuales planas de tama˜no conocido a priori y formadas por un marco de color negro que contiene en su interior un dise˜no previamente configurado que permite la identificaci´on de cada marca concreta. De esta forma, cuando se detecta una marca la librer´ıa puede calcular la distancia y la orientaci´on de ´esta a partir de su tama˜no y de la distorsi´on provocada por el ´angulo desde el que se percibe. Por lo tanto, la librer´ıa permite obtener la posici´on de la marca respecto a la c´amara que la visualiza y viceversa. Figura 4.3: (a) Marca de ARToolkit y uso en RA. (b) Marca ARToolkit para localizaci´on. La ventaja de esta librer´ıa es que soluciona una de las principales dificultades en el desarrollo de la RA, que es el posicionamiento preciso de objetos reales (las marcas) respecto a la c´amara, lo que proporciona el punto de vista del observador para poder insertar los objetos virtuales en el mundo real de forma realista (Fig. 4.3.a). En el presente trabajo, el posicionamiento que ofrece ARToolkit permite obtener la posici´on de la c´amara (el robot) respecto a la marca. As´ı pues, usando una marca ARToolkit como referencia (Fig. 4.3.b), ser´ıa posible establecer la posici´on de varios robots respecto a ella f´acilmente a partir de la imagen actual. De esta forma, esta librer´ıa permitir´ıa obtener un posicionamiento preciso, manteniendo, dentro de lo posible, la filosof´ıa de los comportamientos reactivos al obtener el posicionamiento a partir de la imagen actual. 110 Sistema de localizaci´on 4.3.3. Localizaci´on basada en marcas y filtrado Esta localizaci´on consiste en el uso de balizas espec´ıficas repartidas en el entorno para ofrecer un posicionamiento global de una forma sencilla. As´ı pues, para este tipo de localizaci´on se suelen usar balizas de colores y tama˜nos conocidos a priori situadas en el entorno en posiciones fijas, facilitando de esta forma la localizaci´on del observador (en este caso robots). Sin embargo, debido a que este posicionamiento es sensible a oclusiones, incertidumbre en las marcas, etc., es normal que el posicionamiento obtenido se corrija mediante el uso de alg´un tipo de filtrado que permitan mejorar la estimaci´on y estabilidad de la posici´on, siendo los m´as normal el uso de filtros de part´ıculas [151] o de filtros de Kalman [41,89]. Ambos tipos de filtros son ampliamente conocidos y usados y ofrecen buenos resultados, aunque los filtros de part´ıculas ofrecen una mayor flexibilidad y f´acil implementaci´on que los filtros de Kalman, raz´on por la que se ha seleccionado la utilizaci´on de los filtros de part´ıculas. De hecho, la localizaci´on basada en balizas de colores y filtros de part´ıculas es una t´ecnica de localizaci´on muy conocida y usada en el entorno de la Robocup [67,108,110,151]. Lamentablemente, y como se coment´o anteriormente, esta opci´on es la que menos encaja con un enfoque reactivo, pues implica un modelado muy espec´ıfico y estricto del entorno, al forzar unas marcas concretas en posiciones fijas, a la vez que implica el uso de memoria (hist´orico de observaciones), lo cual va contra el enfoque general de los comportamientos reactivos. Sin embargo, se considerar´a el uso de esta localizaci´on, aunque sea como ´ultima opci´on debido a su enfoque menos reactivo, dado que se trata de una t´ecnica madura y ampliamente probada y usada que ofrece un posicionamiento estable y, en general, m´as fiable que las t´ecnicas anteriores. As´ı pues, y como es l´ogico, para aplicar esta t´ecnica es necesario un m´odulo que permita la detecci´on de las balizas y otro que implemente un filtro de part´ıculas. A continuaci´on se explican en m´as detalle cada uno de estos m´odulos. 4.3.3.1. Detecci´on de balizas de colores El entorno de la Robocup, el entorno de pruebas usado en los experimentos, suele incluir marcas artificiales de colores en posiciones concretas que el robot puede usar para una localizaci´on visual global [37,108,110,140]. Estas marcas cambian de a˜no en a˜no, modificando bien la distribuci´on de colores, la posici´on en el campo, etc. Sin embargo, una caracter´ıstica en com´un es que son marcas de colores f´aciles de identificar en el entorno, de tama˜no y posici´on conocida, lo que Localizaci´on visual basada en marcas 111 permite que al detectarlas se pueda estimar la posici´on de forma absoluta en el campo. En cualquier caso, y aunque existen distintas t´ecnicas y enfoques [26,108, 110], la mayor´ıa de detectores de balizas suponen realizar, de una forma u otra, los siguientes pasos: Conversi´on de la imagen a un espacio de color en el que sea f´acil detectar los colores, como HSI o HSV, y segmentar la imagen para detectar los colores que forman parte de las balizas. Para la segmentaci´on es especialmente importante definir correctamente los colores a detectar as´ı como sus umbrales. Detecci´on de regiones. Una vez segmentada la imagen, se detectan las zonas, formadas por p´ıxeles sin ninguna relaci´on entre s´ı, que se corresponden con un mismo color y zona delimitada. A esta detecci´on de regiones se le puede aplicar un filtrado para eliminar regiones que se dan por hecho que no son viables en la realidad, como regiones demasiado peque˜nas, grandes o que est´en en posiciones que no sean posibles o poco probables. Detecci´on de balizas. Tras detectar cada una de las regiones por separado, es el momento de determinar que regiones de las detectadas cumplen las condiciones para formar parte de una baliza. Estas condiciones, para el caso de una baliza como las de la Robocup, ser´ıan por ejemplo que los colores se correspondan con los de una baliza v´alida, que las regiones est´en una encima de otra o que ambas regiones tengan un tama˜no similar. C´alculo de la posici´on respecto al robot. Tras detectar una baliza con una cierta seguridad, se obtendr´a su tama˜no y posici´on en la imagen. As´ı pues, y dado que se conocen tanto el tama˜no predefinido de la baliza as´ı como los ´angulos de visi´on de la c´amara del AIBO (56.9o en horizontal y 45.2oen vertical), es posible estimar la distancia de la marca as´ı como su ´angulo respecto a la c´amara del robot. Por ´ultimo, la figura 4.4 muestra un ejemplo de detecci´on de balizas siguiendo los pasos indicados anteriormente (conversi´on de espacio de color y segmentaci´on, detecci´on de ´areas, detecci´on de balizas y c´alculo de posici´on). 4.3.3.2. Filtros de part´ıculas Los filtros de part´ıculas (tambi´en conocido como filtro de bootstrap, filtro de Monte Carlo o filtro de condensaci´on) se engloban dentro de los conocidos 112 Sistema de localizaci´on Figura 4.4: Proceso para detecci´on de balizas. como m´etodos de Monte Carlo, que son un conjunto de t´ecnicas de muestreo estad´ıstico que permiten representar cualquier distribuci´on con un n´umero reducido de muestras sin perder representatividad. Concretamente, los filtros de part´ıculas se basan en el Filtro Bayesiano, un algoritmo recursivo que permite estimar la distribuci´on de probabilidad del estado de un sistema en un cierto instante ten funci´on de los datos disponibles de momentos anteriores. A esa densidad de probabilidad se le suele llamar creencia (Belief en ingl´es). Aplicando esto al caso pr´actico de la localizaci´on, el estado del sistema ser´ıa la localizaci´on del robot, mientras que los datos en instantes anteriores ser´ıan los movimientos y las observaciones realizadas por el robot. Por lo tanto, los filtros de part´ıculas permiten estimar el estado de un sistema (la localizaci´on de un robot) en un cierto instante ta partir de valores actuales y pasados (movimientos del robot y sus observaciones) aproximando la funci´on de distribuci´on a estimar mediante una serie de muestras aleatorias conocidas normalmente como part´ıculas. Para ello, cada part´ıcula est´a formada por un posible estado del sistema (una localizaci´on concreta) y un peso que indica la probabilidad de que el estado que representa esa part´ıcula sea el correcto. As´ı pues, el c´alculo del peso de la part´ıcula depender´a del parecido que haya entre el sistema real y el que describe la part´ıcula. De esta forma, el estado actual del sistema es modelado como un conjunto de part´ıculas cuyos pesos dependen de los valores (movimientos y observaciones) anteriores del sistema. Una vez descrito en que consiste un filtro de part´ıculas, se comentar´a su funcionamiento que, como todo filtro predictor-corrector, est´a formado por dos fases que se repiten constantemente. Estas fases son: Fase de predicci´on. En esta primera fase se predice el estado del sistema en el instante ta partir de la funci´on de distribuci´on (el conjunto de part´ıculas) en el estado t−1. Para ello hace falta lo que se conoce como modelo del sistema, que en el caso de la localizaci´on tambi´en se conoce como modelo de movimiento, y que se es un modelo que permite estimar cuanto ha avanzado el robot entre el instante anterior y el actual. En Experimentos y resultados 113 general, el avance del robot suele calcularse a partir de la odometr´ıa o de la velocidad te´orica de ´este. Sin embargo, dado que este par´ametro no es exacto, hay que a˜nadirle un ruido que depender´a de la estimaci´on del error del movimiento del robot. As´ı pues, a trav´es de este modelo del sistema se puede determinar cuanto avanza el robot en funci´on de los comandos de movimiento ejecutados. Fase de actualizaci´on. Esta fase puede ser dividida a su vez en dos fases: •Correcci´on. En esta fase se corrige la predicci´on realizada en la fase anterior en base a las observaciones obtenidas por el robot. Para ello, se ajustan los pesos de cada part´ıcula en funci´on de si el estado que describe se parece o no al determinado por las observaciones. Para realizar esta correcci´on es necesario lo que se conoce como un modelo de observaci´on, que en el caso de la localizaci´on ser´ıa un modelo que determina la probabilidad de estar en una posici´on concreta en funci´on de las observaciones obtenidas, probabilidad que depender´a de los posibles errores en la estimaci´on de la observaci´on o de los sensores de entrada. As´ı pues, a partir del modelo de observaci´on se puede calcular la probabilidad de que el estado representado por las part´ıculas se corresponda a la observaci´on actual. Existen distintas formas de ajustar los pesos de las part´ıculas, aunque una alternativa usual es el uso de una funci´on de distribuci´on, como puede ser una distribuci´on normal, con una desviaci´on que depender´a del error del sensor de entrada o de las observaciones. •Normalizaci´on y remuestreo. En este ´ultimo paso se normalizan los pesos de las part´ıculas (la suma de todos los pesos debe valer 1) y se obtiene una nueva poblaci´on de part´ıculas en funci´on de sus pesos, de forma que las part´ıculas con un mayor peso (mayor probabilidad) generen m´as part´ıculas, aumentando la probabilidad global asociada a la siguiente poblaci´on. As´ı pues, realizando estos pasos de forma repetitiva los filtros de part´ıculas consiguen aproximar la posici´on del robot en funci´on de sus movimientos y de observaciones (las marcas que visualiza). 4.4. Experimentos y resultados En este apartado se mostrar´an los experimentos con los distintos sistemas de localizaci´on comentados. Para probar cada uno de los sistemas de 120 Sistema de localizaci´on DLA. Este m´odulo permite el intercambio de la posici´on de los robots respecto a la marca de forma f´acil y sencilla. Tras describir la implementaci´on del sistema de navegaci´on, a continuaci´on se comentan las pruebas realizadas al sistema de localizaci´on basado en marcas ARToolkit. 4.4.2.3. Experimentos realizados En esta secci´on se presentan los experimentos realizados con el sistema de localizaci´on basado en marcas ARToolkit. Para las pruebas se han usado dos robots AIBO ERS-7 y el entorno de las pruebas es una zona despejada de obst´aculos de aproximadamente 2x2m2. Dado que el objetivo es probar el sistema de localizaci´on, el comportamiento de los robots en s´ı es muy simple, siendo el objetivo que los dos robots se muevan hacia la marca sin colisionar ni interferirse, realizando una navegaci´on segura entre ellos, para lo cual es necesario que estimen sus posiciones relativas de forma adecuada. Figura 4.8: Navegaci´on segura entre AIBOSs usando localizaci´on basada en marcas ARToolkit. La figura 4.8.a muestra el resultado de una de las pruebas, en la que los robots comienzan muy cerca, lo que hace que el PFA los fuerce a alejarse, alcanzando finalmente la marca sin problemas. La figura 4.8.b muestra otro ejemplo en el que los robots est´an separados finalizando igualmente en las proximidades de la marca. Estas pruebas muestran que el uso de la localizaci´on basada en marcas de ARToolkit ser´ıa viable para la realizaci´on de comportamientos coordinados. Adem´as, en este caso, a diferencia del anterior, el posicionamiento s´olo requiere que los robots visualicen la marca, dependiendo la precisi´on de la localizaci´on de la distancia a la que est´e el robot de la marca. Sin embargo, hay que destacar que hab´ıa ocasiones en Experimentos y resultados 121 las que se perd´ıa la marca (debido al movimiento del robot o a una incorrecta identificaci´on) lo que provocaba posiciones err´oneas y que el robot se detuviese, momento en el cual volv´ıa a detectar la marca (pues en general se perd´ıa debido al movimiento del robot). En cualquier caso, en general el sistema de localizaci´on basado en marcas ARToolkit ha funcionado de forma adecuada en estas pruebas. 4.4.3. Localizaci´on basada en marcas y filtrado En este apartado se prueba el sistema de localizaci´on basado en balizas de colores como las del campo de la Robocup con correcci´on de la posici´on mediante filtrado, concretamente mediante filtros de part´ıculas. Dado que este sistema de localizaci´on posee memoria, a diferencia de los anteriores, tan s´olo requiere que los robots visualicen peri´odicamente alguna de las balizas de colores del campo para corregir y estimar su posici´on correctamente. De esta forma, se evita la necesidad de visualizar constantemente alguna de las balizas del entorno como en los otros dos ejemplos comentados. En esta prueba, al igual que en la anterior, los robots estiman su posici´on usando el sistema de localizaci´on implementado, y la enviar´an a su compa˜nero mediante DLA, facilitando as´ı la navegaci´on segura entre ambos. 4.4.3.1. Implementaci´on del sistema En este caso, la implementaci´on del sistema es id´entica a la mostrada en la figura 4.7, con la salvedad de que el sistema de localizaci´on en vez de usar la librer´ıa ARToolkit usa una librer´ıa desarrollada durante la realizaci´on de la tesis que permite la detecci´on de las balizas de colores as´ı como la correcci´on de esta posici´on usando un filtro de part´ıculas. Respecto a los par´ametros del filtro de part´ıculas, indicar que estaba compuesto por 500 part´ıculas, la varianza del error de la velocidad usada en el modelo del sistema se ha estimado heur´ısticamente en 25 mm/s y la del error de posicionamiento del modelo de observaci´on se ha estimado en 25 cm y 5o(usando coordenadas polares). El resto de la implementaci´on es id´entico, us´andose el entorno Tekkotsu para el desarrollo general del sistema, JNI para enlazar el m´odulo de localizaci´on (en C++) con el programa principal el Java, y DLA para el intercambio de la posici´on de los robots, por lo que no se repetir´a el esquema de bloques del sistema ni su descripci´on. 122 Sistema de localizaci´on 4.4.3.2. Experimentos realizados Respecto a los experimentos realizados, dado que la localizaci´on basada en balizas de colores y filtro de part´ıculas devuelve un posicionamiento concreto respecto a las balizas, al igual que ARToolkit respecto a sus marcas, y dado que el sistema usado era el mismo, el resultado de estas pruebas ha sido muy similar al de las pruebas anteriores realizadas con ARToolkit. Figura 4.9: Pruebas de localizaci´on est´atica. La principal diferencia observada entre estos dos sistemas de localizaci´on es que el posicionamiento obtenido con la localizaci´on basada en filtros de part´ıculas es m´as estable que en el caso de ARToolkit. Por ´ultimo, la figura 4.9 muestra algunas pruebas de posicionamiento est´atico realizadas al sistema de localizaci´on basado en balizas de colores con correcci´on mediante filtro de part´ıculas. 4.5. Conclusiones El objetivo del presente documento es la realizaci´on de un sistema de coordinaci´on multi-agente, siendo un elemento b´asico para poder realizar dicha coordinaci´on la localizaci´on de cada agente. Por lo tanto, en este cap´ıtulo se han presentado tres t´ecnicas distintas para poder estimar la posici´on de los robots de un MRS. Cada una de estas t´ecnicas tiene sus ventajas y desventajas, pues unas permiten un posicionamiento preciso y estable, pero no encajan en el esquema reactivo presentado en el cap´ıtulo anterior, mientras que otras encajan mejor en un enfoque m´as reactivo pero poseen otras desventajas. Concretamente, los sistemas de localizaci´on probados han sido un sistema de localizaci´on basado en objetos comunes en el campo de visi´on usando visi´on est´ereo y comunicaci´on entre los robots, un sistema de localizaci´on basado en marcas fiduciarias (concretamente marcas ARToolkit) con comunicaci´on para determinar las posiciones relativas de los robots, y un sistema de localizaci´on basado en balizas de colores como las de la Robocup y correcci´on Conclusiones 123 del posicionamiento mediante filtros de part´ıculas, habilitando igualmente la comunicaci´on entre los robots. Para probar cada uno de estos sistemas se han realizado pruebas con dos robots AIBO ERS-7 en un entorno despejado de obst´aculos. Las pruebas han consistido en conseguir que los robots naveguen de forma segura entre ellos mientras tratan de alcanzar su propio destino (el cual depende de las pruebas realizadas). En todas las pruebas realizadas se ha conseguido que los robots navegasen evitando colisionar e interferirse. Sin embargo, eso no quiere decir que todos los sistemas de localizaci´on ofreciesen las mismas prestaciones. As´ı pues, en el sistema de localizaci´on basado en visi´on est´ereo usando como referencia los objetos comunes en el campo de visi´on, a pesar de ser la localizaci´on con un modelado del entorno menos restrictivo y no usar memoria, el posicionamiento era muy impreciso y de hecho la aplicaci´on de esta localizaci´on pr´acticamente requer´ıa tener una estimaci´on de la posici´on de los robots, pues ´estos deben estar alineados y en el mismo plano. As´ı pues, este sistema no se considera adecuado para ser usado en el sistema de coordinaci´on que se pretende realizar, a pesar de ser la localizaci´on que mejor encaja con un enfoque reactivo. El segundo sistema de localizaci´on propuesto se trata de una localizaci´on basada en marcas ARToolkit. Esta localizaci´on ha ofrecido un posicionamiento adecuado aunque la localizaci´on obtenida no era del todo estable y en ocasiones era dif´ıcil obtener un valor debido al movimiento de la c´amara. Sin embargo, en general se considera que el resultado ha sido adecuado permitiendo, como se ha mostrado, que los robots navegasen de una forma reactiva evitando colisionar, por lo que este sistema es una alternativa a tener en cuenta para la localizaci´on del sistema de coordinaci´on. Por ´ultimo, el sistema de localizaci´on basado en balizas de colores y filtros de part´ıculas ha sido el que ha devuelto un posicionamiento m´as estable. Sin embargo, este sistema de localizaci´on no encaja con el enfoque reactivo propuesto en el cap´ıtulo 3 debido a que requiere un modelado del entorno m´as estricto as´ı como al uso de memoria (hist´orico de observaciones). Por lo tanto, y como conclusi´on, para el sistema de coordinaci´on multiagente se optar´a por el uso del sistema de localizaci´on basado en marcas ARToolkit porque se considera que ofrece un posicionamiento adecuado como para ser usado en el sistema de coordinaci´on a realizar. Como alternativa, si este sistema de localizaci´on mostrase alguna deficiencia o problema al probarse m´as exhaustivamente, se optar´ıa por el enfoque de localizaci´on basada en balizas de colores y correcci´on con filtros de part´ıculas, aunque el sistema perdiese su enfoque reactivo inicial. 124 Sistema de localizaci´on Cap´ıtulo 5 Coordinaci´on reactiva basada en aprendizaje 5.1. Introducci´on Los MRS tienen una serie de ventajas frente a los sistemas rob´oticos individuales [52,152,156], ya que los MRS mejoran la resistencia a fallos, el ´area de cobertura y el tiempo necesario para realizar una determinada tarea. Por contra, estos sistemas son m´as complejos de dise˜nar que un sistema rob´otico individual, pues requieren una correcta coordinaci´on entre los distintos robots para funcionar de forma eficiente. Por lo tanto, la coordinaci´on es un elemento clave en los MRS, pues sin una correcta coordinaci´on los distintos robots se entorpecer´ıan en vez de ayudarse, perdiendo todas sus ventajas frente a un robot individual. La coordinaci´on, de forma general, puede dividirse en coordinaci´on expl´ıcita [12,35] y coordinaci´on impl´ıcita [81,107]. La coordinaci´on expl´ıcita consiste en que los robots del sistema se coordinen de forma expl´ıcita entre ellos, es decir, que las acciones o tareas de cada robot se deciden de forma conjunta. Generalmente, este tipo de coordinaci´on requiere que los robots lleguen a un acuerdo en com´un o que un robot o agente centralizado decida que deben hacer los dem´as robots. Por su parte, la coordinaci´on impl´ıcita consiste en la coordinaci´on surgida de la interacci´on entre los distintos robots a partir de las decisiones individuales de cada uno de ellos. Es decir, en este tipo de coordinaci´on cada robot toma sus propias decisiones, pudiendo tener en cuenta o no la informaci´on de los dem´as robots, pero las decisiones son tomadas individualmente. As´ı pues, la coordinaci´on surge, generalmente, en la forma de un comportamiento emergente, similar al que se observa en las colonias de hormigas, termitas o abejas. 125 126 Coordinaci´on reactiva basada en aprendizaje De entre estos dos tipos de coordinaci´on, la coordinaci´on impl´ıcita es m´as adaptable a cambios din´amicos en el entorno, debido a que los robots act´uan por s´ı mismos sin necesidad de llegar a ning´un acuerdo entre ellos, por lo que el tiempo de respuesta ante cambios en el entorno suele ser menor que en sistemas coordinados expl´ıcitamente. Adem´as, la coordinaci´on impl´ıcita resulta m´as sencilla de encajar en una arquitectura basada en comportamientos, como la mostrada en el cap´ıtulo 3, que la coordinaci´on expl´ıcita. La raz´on es que para conseguir un comportamiento coordinado impl´ıcito, partiendo de comportamientos reactivos, tan s´olo es necesario que ´estos comportamientos tengan en cuenta a los otros robots para actuar de acuerdo a la distribuci´on e informaci´on del sistema, evitando colisionar e interferirse. As´ı pues, este tipo de coordinaci´on es casi inmediata de conseguir a partir de comportamientos reactivos de una manera sencilla. Por lo tanto, y partiendo del trabajo presentado en el cap´ıtulo 3, en este cap´ıtulo se presenta un sistema coordinado basado en el uso de comportamientos reactivos aprendidos mediante LfD usando CBR. As´ı pues, y al igual que en dicho cap´ıtulo, el entrenamiento se realiza controlando al robot de forma remota, obteniendo de esta forma las ventajas ya comentadas en la secci´on 3.4.3, como que no es necesario ning´un modelo cinem´atico expl´ıcito del robot o que los errores sistem´aticos y mec´anicos son absorbidos impl´ıcitamente por el operador durante el entrenamiento [47, 102]. Adem´as, para implementar comportamientos con distintas respuestas, tan s´olo es necesario definir los par´ametros que definen el caso del nuevo comportamiento y entrenar de nuevo el sistema para que realice el comportamiento deseado. Por otro lado, si durante el entrenamiento el operador tiene en cuenta la posici´on de los otros robots en el entorno, el comportamiento aprendido ser´a un comportamiento coordinado impl´ıcitamente, ya que las respuestas del comportamiento depender´an, al menos en parte, del otro robot. De esta forma se consigue una coordinaci´on impl´ıcita de un modo inmediato y sencillo, pues cada robot act´ua y se mueve de acuerdo a su propio entrenamiento y no por un acuerdo con los otros robots, aunque est´e teniendo en cuenta a los dem´as robots para realizar sus movimientos. As´ı pues, para que los comportamientos puedan tener en cuenta a los dem´as robots es necesario que los robots conozcan tanto su posici´on como la de los compa˜neros, por lo que se hace necesario un sistema de localizaci´on. Como se coment´o en el cap´ıtulo 4, de los distintos sistemas de localizaci´on considerados, el que se usar´a para las pruebas ser´a la localizaci´on basada en marcas ARToolkit, pues ofrec´ıa un posicionamiento de una forma sencilla y permit´ıa mantener el enfoque reactivo propuesto anteriormente. Por otro lado, para que los robots puedan conocer la posici´on de sus compa˜neros y fa- Coordinaci´on 127 cilitar la coordinaci´on del sistema se permitir´a la comunicaci´on e intercambio de informaci´on (como la posici´on) entre ellos. Para comprobar la viabilidad del enfoque propuesto, se ha realizado una prueba de concepto que consiste en que dos robots AIBO ERS-7 realicen un movimiento coordinado evitando colisionar entre ellos mediante aprendizaje. Esta prueba de concepto es similar a la del cap´ıtulo 3, aunque en este caso s´ı se tiene en cuenta otro robot en movimiento en el entrenamiento. Para determinar la posici´on de los robots y que puedan coordinarse adecuadamente sin colisionar se usar´a, como se ha comentado, localizaci´on basada en marcas ARToolkit. Por ´ultimo, para el intercambio de las posiciones de los robots se usar´a DLA [97,98], ya que permite una comunicaci´on sencilla y transparente entre programas. Por lo tanto, el cap´ıtulo se estructura de la siguiente manera. En primer lugar, se realiza una introducci´on a la coordinaci´on y a las estrategias de coordinaci´on m´as usuales (secci´on 5.2). Dado que la implementaci´on se realiza mediante comportamientos basados en aprendizaje usando CBR, se presentar´a tambi´en un breve estado del arte de CBR aplicado a coordinaci´on (secci´on 5.3). Tras esto, se describir´a el sistema de coordinaci´on propuesto (secci´on 5.4). Para comprobar la viabilidad del sistema se presentar´a una prueba de concepto consistente en el entrenamiento de dos robots AIBO ERS-7 para que se muevan de forma coordinada en paralelo sin colisionar entre ellos. Finalmente, se presentan los resultados de esta prueba de concepto (secci´on 5.5) y las conclusiones del cap´ıtulo (secci´on 5.6). 5.2. Coordinaci´on Aunque existen distintas definiciones de coordinaci´on, pero se podr´ıa entender como la administraci´on de las interdependencias entre distintas actividades o acciones. Teniendo en cuenta esta definici´on, la coordinaci´on en los MRS resulta fundamental, pues es la que permite administrar las dependencias entre las acciones que realizan los robots evitando as´ı el caos y la anarqu´ıa entre los miembros del sistema y permitiendo la eficiencia del MRS frente a los sistemas individuales. Como es l´ogico, la coordinaci´on entre distintos robots puede conseguirse de muchas formas distintas, sin embargo, en general la coordinaci´on se puede dividir en dos grandes grupos [55,153]: Coordinaci´on expl´ıcita. En la coordinaci´on expl´ıcita, los robots se comunican expl´ıcitamente entre ellos y las acciones de cada agente en el grupo son calculadas de forma expresa. En este tipo de coordinaci´on, 128 Coordinaci´on reactiva basada en aprendizaje las acciones del equipo pueden ser calculadas para determinar la mejor acci´on individual, evitando la duplicaci´on de acciones y minimizando el esfuerzo. Sin embargo, este enfoque tiende a ser poco flexible y poco tolerante a fallos, debido a que en general suele haber un elemento que centraliza la coordinaci´on. Por otro lado, si el n´umero de componentes del sistema crece suficientemente el coste computacional y la cantidad de mensajes para establecer la comunicaci´on entre los robots pueden resultar excesivos en este tipo de coordinaci´on. As´ı pues, la coordinaci´on expl´ıcita es habitualmente usada en entornos pocos din´amicos, pues no responde adecuadamente a cambios r´apidos en el entorno, con equipos de peque˜no tama˜no. Coordinaci´on impl´ıcita. La coordinaci´on impl´ıcita se basa en la din´amica de la interacci´on entre los robots y el entorno para lograr el objetivo colectivo, a menudo en la forma de un comportamiento emergente. Este comportamiento emergente surge, pues, de la combinaci´on de otros comportamientos m´as sencillos [33, 84, 101] que realizan cada uno de los robots por separado. As´ı pues, en este enfoque, los robots no trabajan unidos expl´ıcitamente, sino que cada uno act´ua por su cuenta, tomando en cuenta la existencia de los otros robots, para modificar sus acciones o simplemente para evitar estar en su camino. Las acciones de los agentes en este enfoque generan una acci´on combinada emergente [153] que se acepta como cooperativa, tales como las acciones de las colonias de insectos [36,40], por ejemplo. Este mecanismo es t´ıpico en animales y es bastante eficiente cuando todos los robots son similares y cuando hay gran cantidad de miembros en el equipo. Por otro lado, la independencia de los robots del sistema en la coordinaci´on impl´ıcita hace que este enfoque sea m´as adecuado para entornos din´amicos pues las respuestas del sistema resultan m´as r´apidas y flexibles. Por contra, y respecto a la coordinaci´on expl´ıcita, este tipo de coordinaci´on puede ser menos eficiente (duplicaci´on de tareas por falta de comunicaci´on o interferencias entre los robots). Es importante destacar que, a pesar de que cada robot act´ue por s´ı mismo, los distintos miembros del sistema pueden compartir expresamente informaci´on como su posici´on o los objetos que est´an captando, siempre y cuando la toma de decisiones se realice de forma aut´onoma, aunque influenciada por la informaci´on de los otros miembros. Sin embargo, y a diferencia de la coordinaci´on expl´ıcita, la coordinaci´on impl´ıcita suele requerir poca comunicaci´on o ninguna entre los distintos miembros. Como se puede observar, ambos enfoques son muy diferentes y cada uno CBR aplicado a Coordinaci´on 129 de ellos tiene un ´ambito de aplicaci´on distinto, que depender´a de las circunstancias y el problema concreto a resolver. En el caso presente, se ha optado por usar coordinaci´on impl´ıcita por varias razones. Por un lado, porque se adapta m´as f´acilmente a entornos din´amicos y a cambios en el entorno que la coordinaci´on explicita. Por otro lado, la coordinaci´on impl´ıcita es m´as sencilla de implementar a partir de una estructura basada en comportamientos como la propuesta, pues tan s´olo es necesario que los comportamientos tengan en cuenta a los otros robots para actuar de forma coordinada. 5.3. CBR aplicado a Coordinaci´on Entre las distintas t´ecnicas de IA aplicadas a la coordinaci´on, se encuentran por ejemplo las Redes Bayesianas, los GA o el CBR [5]. Concretamente este ´ultimo es el que se va a utilizar en el presente trabajo, como ya se ha comentado. El CBR ha sido aplicado anteriormente para coordinaci´on, por lo general a alto nivel. As´ı por ejemplo, [15] presenta un sistema que permite la cooperaci´on de dos robots para un comportamiento de pase de pared basado en CBR. Concretamente, el CBR es usado para determinar si la situaci´on es adecuada para realizar un pase de pared y, en ese caso, activar la secuencia de acciones que permite el comportamiento coordinado de pase de pared. Un enfoque similar muestra [113], donde el CBR es usado para la toma de decisiones. Concretamente, un robot es el encargado de obtener, en base a la situaci´on actual, el caso CBR m´as adecuado y se lo env´ıa al resto de robots para que todos ejecuten la secuencia de acciones (determinada por la salida del CBR) de forma coordinada. Otro ejemplo de aplicaci´on del CBR para coordinaci´on es [115], donde el CBR se utiliza para la selecci´on de los roles de los robots y planificaci´on a largo plazo de la coordinaci´on de un equipo de robots. Otro uso distinto del CBR para coordinaci´on ser´ıa el propuesto en [10], donde el CBR permite configurar los par´ametros que determinan la coordinaci´on de un sistema. En el presente trabajo, y a diferencia de los trabajos mencionados, el CBR ser´a aplicado, directamente, para implementar los propios comportamientos coordinados, ya que el mismo comportamiento, al aprenderse, tiene en cuenta a los dem´as robots.