Arquitectura de Comportamientos Reactivos para Agentes Robóticos basada en CBR

Arquitectura de Comportamientos Reactivos para Agentes Robóticos basada en CBR Tesis Doctoral Ignacio Herrero Reder Escuela Técnica Superior de Ingeniería de Telecomunicación Málaga, 2015 AUTOR: Ignacio Herrero Reder http://orcid.org/0000-0001-9567-200X 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: 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. http://creativecommons.org/licenses/by-nc-nd/4.0/legalcode Esta Tesis Doctoral está depositada en el Repositorio Institucional de la Universidad de Málaga (RIUMA): riuma.uma.es Departamento de Tecnología Electrónica E.T.S.I. Telecomunicación Universidad de Málaga Tesis Doctoral Arquitectura de Comportamientos Reactivos para Agentes Robóticos basada en CBR Autor: Ignacio Herrero Reder Ingeniero de Telecomunicación Directora: Cristina Urdiales García Dra. Ingeniera de Telecomunicación Dña. Cristina Urdiales García, Profesora Doctora del Departamento de Tecnología Electrónica de la Universidad de Málaga Certifica: Que D. Ignacio Herrero Reder, 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: Arquitectura de Comportamientos Reactivos para Agentes Robóticos basada en CBR 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 Noviembre de 2015 Fdo: Dra. Dª. Cristina Urdiales García A las niñas de mis ojos, Rosi y Sofía. Si he acabado esta Tesis ha sido por VOSOTRAS Agradecimientos Esta Tesis no hubiera sido posible sin la intervención y ayuda de gran cantidad de personas y entidades que me han dado su apoyo, tanto moral como material, en el proceso de realización del presente trabajo. Mi agradecimiento a los doctores Francisco Sandoval y Antonio Díaz Estrella que confiaron en mí para darme su aval en la petición de una beca FPU del MEC, beca que me permitió adentrarme en el maravilloso mundo de la docencia y la investigación en el ámbito de la Universidad de Málaga. Espero no haber decepcionado su confianza. Al grupo de investigación ISIS (Ingeniería de Sistemas Integrados) por su soporte económico y material a través de los diferentes proyectos en los que he participado, soporte indispensable para la realización de toda mi investigación. A mis compañeros del Departamento de Tecnología Electrónica, los “Habituales del Comedor”, con sus charlas de desayuno en las que hablar de lo divino y de lo humano, de la política universitaria y de las aficiones personales, de la mejora docente e investigadora, y de los últimos chismes del pasillo. A mis compañeros de asignaturas: Microcontroladores, Sistemas Empotrados, Microbótica, las asignaturas del Máster SEEI, etc. Por hacer de mi trabajo una tarea más agradable y demostrarme cada día su compañerismo y amistad. A los sufridores de las Tesis a extinguir: Peula, Carmen, Jose Manuel, Martín...mucho ánimo que ya queda menos!!! A mis padres, por haberme proporcionado los medios para desarrollar una carrera que me ha llenado plenamente, como ingeniero, como docente, y como investigador. También por su cariño y apoyo en todas las fases de mi vida. A mi directora, Cristina, mi “jefa”, compañera de asignaturas, y amiga. Gracias por tu apoyo y tiempo dedicado, muchas veces sacado de no se sabe donde. Espero seguir disfrutando de tu compañía en futuras aventuras docentes e investigadoras. Y finalmente a Rosi y Sofía, por los sacrificios realizados para permitirme acabar esta Tesis, y porque lo son TODO en mi vida. Espero poder dedicaros, a partir de ahora, todo el tiempo que os merecéis. 3. Inteligencia y Aprendizaje 39 1. Inteligencia Humana e Inteligencia Artificial . . . . . . . . . . . . . . . 39 1.1. PionerosdelaIA.......................... 39 1.2. Funcionalismo............................ 42 1.3. Conductismo (inteligencia) . . . . . . . . . . . . . . . . . . . . . 43 1.4. Conexionismo............................ 44 1.5. Inteligencia artificial débil: Sistemas Expertos . . . . . . . . . . 46 2. El proceso de Aprendizaje . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.1. Conductismo (aprendizaje) . . . . . . . . . . . . . . . . . . . . . 54 2.2. Cognitivismo ............................ 54 2.3. Constructivismo........................... 54 2.4. Otros modelos de inteligencia y teorías de aprendizaje . . . . . . 55 3. El modelo de Inteligencia como Memoria Jerárquica Temporal (HTM) . 55 3.1. Organización jerárquica de la memoria . . . . . . . . . . . . . . 55 3.2. Importancia del tiempo: predicciones . . . . . . . . . . . . . . . 57 3.3. Funciones básicas del modelo de inteligencia/aprendizaje HTM . 58 3.4. Críticas al modelo HTM . . . . . . . . . . . . . . . . . . . . . . 60 4. CBR: razonamiento basado en Casos 61 1. Introducción................................. 61 2. Historia y campos de aplicación . . . . . . . . . . . . . . . . . . . . . . 63 2.1. CBR en el campo de la Robótica . . . . . . . . . . . . . . . . . 64 3. Organización de la información: Bases del conocimiento . . . . . . . . . 66 3.1. Compilación en sistemas CBR . . . . . . . . . . . . . . . . . . . 67 3.2. Recipientes de conocimiento en CBR . . . . . . . . . . . . . . . 67 3.3. Adquisición y Trasvase de conocimiento entre recipientes . . . . 71 4. Aspectos básicos de un sistema CBR . . . . . . . . . . . . . . . . . . . 74 4.1. ElcasoCBR ............................ 74 4.2. Estructura de la base de casos . . . . . . . . . . . . . . . . . . . 77 5. Operación de un sistema CBR: El ciclo CBR . . . . . . . . . . . . . . . 80 5.1. Fase de Recuperación . . . . . . . . . . . . . . . . . . . . . . . . 81 5.2. Medidas de Similitud . . . . . . . . . . . . . . . . . . . . . . . . 83 5.3. Fase de Reutilización: Adaptación . . . . . . . . . . . . . . . . . 85 5.4. FasedeRevisión .......................... 86 5.5. Fase de Retención: Aprendizaje . . . . . . . . . . . . . . . . . . 86 5. Arquitectura híbrida de aprendizaje basada en CBR 91 1. Introducción................................. 91 2. Modelo general de inteligencia robótica basada en la arquitectura HTM 91 2.1. Componentes del modelo . . . . . . . . . . . . . . . . . . . . . . 93 2.2. Representación de la información . . . . . . . . . . . . . . . . . 94 2.3. Identificación de conceptos . . . . . . . . . . . . . . . . . . . . . 95 2.4. Respuestas asociadas a conceptos identificados . . . . . . . . . . 95 3. Arquitectura aprendizaje reactivo para AIBO jugador de fútbol . . . . 97 3.1. Estructura general del sistema propuesto . . . . . . . . . . . . . 98 3.2. Escenario de trabajo . . . . . . . . . . . . . . . . . . . . . . . . 100 4. Estructura de un módulo de la arquitectura en el dominio propuesto . . 103 4.1. Información de entrada . . . . . . . . . . . . . . . . . . . . . . . 103 II 4.2. Base de conocimientos: adquisición y almacenamiento de la información ............................. 107 4.3. Organización y recuperación de la información: estructura de la baseCBR.............................. 114 4.4. Fase operativa: aprendizaje por experiencia . . . . . . . . . . . . 118 5. Composición de comportamientos reactivos emergentes . . . . . . . . . 127 6. Pruebas experimentales 129 1. Introducción................................. 129 2. Primera etapa: Implementación de comportamientos simples . . . . . . 131 2.1. Escenario de pruebas . . . . . . . . . . . . . . . . . . . . . . . . 131 2.2. Módulo de comportamiento determinado por la pelota . . . . . 131 2.3. Módulo de posicionamiento en el campo . . . . . . . . . . . . . 134 2.4. Otros ejemplos de comportamientos básicos basados en visión . 141 2.5. Combinación de módulos simples: emergencia de comportamientos142 2.6. Conclusiones de las pruebas de la primera etapa . . . . . . . . . 152 3. Comportamientos reactivos complejos . . . . . . . . . . . . . . . . . . . 153 3.1. Modificaciones SW y de escenario de pruebas . . . . . . . . . . 153 3.2. Diseño de un comportamiento complejo de acercamiento a la pelota155 3.3. Incorporación de nuevos conocimientos a través de la experiencia 167 3.4. Diseño de un comportamientos complejos adicionales . . . . . . 181 3.5. Emergencia de comportamientos basada en reglas de decisión . . 186 3.6. Conclusiones de las pruebas de la segunda etapa . . . . . . . . . 193 7. Conclusiones y líneas futuras 197 1. Conclusiones................................. 197 2. LíneasFuturas ............................... 199 III IV Acrónimos 3T Three Tier AFSM Augmented Finite State Machine AIBO Artificial Intelligence roBOt ANN Artificial Neural Networks BBR Behavior-Based Robotics BERRA Behavior Based Robot Research Architecture CBR Case Based Reasoning CIP Cognitive Information Process DBN Dynamic Bayesian Networks FL Fuzzy Logic FSM Finite State Machine GA Genetic Algorithms HTM Hierarchical Temporal Memory IA Inteligencia Artificial IRM Innate Releasing Mechanism ISIS Ingeniería de Sistemas Integrados KEMLG Knowledge Engineering and Machine Learning MPL Multilayer Perceptron NHC Nested Hierarchical Controller V Índice de acrónimos PCA Principal Component Analysis PF Potential Fields PFA Potential Fields Approach RAE Real Academia Española de la Lengua RCS RealTime Control System RL Reinforced Learning ROS Robot Operating System SA Sense-Act SPA Sense-Plan-Act TCA Task Control Architecture TCP Transfer Control Protocol VHF Vector Histogram Field YUV Luminance-Bandwidth-Chrominance VI Simbología ρEn la representación de una recta en el espacio de Hough, distancia entre el origen de coordenadas y el punto (x, y)de la recta más cercano al origen de coordenadas. θEn la representación de una recta en el espacio de Hough, ángulo del vector director de la recta perpendicular a la recta original y que pasa por el origen de coordenadas. θIN (i)Valor θde la recta ipresente en la imagen de entrada al caso. θCBR(i)Valor θde la recta ipresente en el caso CBR recuperado. θP rom Promedio de las variaciones de θde todas las rectas consideradas en la entrada del caso CBR. UadapθUmbral en la variación promedio de θpara todas las líneas, para adaptar el caso recuperado. Fadapt Factor de adaptación para la rotación propuesta en el caso CBR recuperado. kadapt Constante de adaptación para la rotación propuesta en el caso CBR recuperado. BallP os Indicador binario de posesión de pelota. cnCaso ndentro de una base CBR. (Cx, Cy)Coordenadas [x, y]del centroide de un objeto. aiComponente identro de un caso CBR. d(c1, c2)Distancia entre dos casos, c1yc2, de una base CBR. di(c1ai, c2ai)Distancia local entre los componentes ide dos casos, c1yc2. Fobj Factor de objetivo como componente de la función de utilidad de un comportamiento. Cap Parámetro heurístico que permite ajustar la expresión del factor de utilidad dependiente de la aplicación. tampel Tamaño de la pelota en la imagen de cámara. θrob−pel Ángulo entre el robot y la pelota. VII Índice de símbolos Fseg Factor de seguridad como componente de la función de utilidad de un comportamiento. Cseg Parámetro heurístico que permite ajustar la expresión del factor de seguridad. tamobst Tamaño del obstáculo más cercano al robot. θrob−obst Ángulo entre el robot y el obstáculo más cercano. Fsuav Factor de suavidad como componente de la función de utilidad de un comportamiento. Csuav Parámetro heurístico que permite ajustar la expresión del factor de suavidad. ∆dir Variación de la dirección de avance del robot entre dos consultas CBR consecutivas. Kobj Constante que fija la importancia relativa del objetivo en la eficiencia del comportamiento. Kseg Constante que fija la importancia relativa de la seguridad en la eficiencia del comportamiento. Ksuav Constante que fija la importancia relativa de la suavidad en la eficiencia del comportamiento. Modinput Información de entrada a un comportamiento/módulo CBR. Objidesc Descritor del objeto identro de un caso. IConjunto de imágenes observadas durante la ejecución o entrenamiento de un comportamiento. VIVolumen de información asociado al conjunto de imágenes observadas durante la ejecución o entrenamiento de un comportamiento. NDimensión del espacio de información de todas las imágenes observadas durante la ejecución o entrenamiento de un comportamiento. PDimensión de un sub-espacio de Ncon información suficiente para la caraterización de un comportamiento determinado. λolvido Factor de olvido exponencial para el enventanado de imágenes consecutivas. wiPeso de la distancia local del componente i entre dos casos. giPeso del componente de similitud local dentro de la similitud global. pP F Peso del del vector PFA en la adaptación de un caso CBR. SiSaltos entre los intervalos de dicretización del componente ientre el problema y el caso CBR. sim(c1, c2)Similitud entre dos casos, c1 y c2, de una base CBR. simiMedida de similitud local entre los atributos de un caso y un problema. sim(q, p)Medida de similitud entre un caso y un problema. umbralCmpCaso Umbral en el número de saltos totales de diferencia entre un problema y un caso recuperado, para adaptar el caso. VIII Índice de símbolos umbralCmpIndiv Umbral en el número de saltos de diferencia entre componentes individuales de un problema y un caso recuperado, para adaptar el caso. umbralCmpObj Umbral en el número de saltos totales de diferencia entre objetos de un problema y un caso recuperado, para adaptar el caso. ηUtilidad del caso CBR adaptado tras su aplicación. ~ VAtriVector PFA de atracción del objeto i. ~ VCBRCase Vector de acción del caso CBR recuperado. pRD(t)Peso a aplicar al vector de respuesta del comportamiento de evitación de obstáculos en la composición del comportamiento emergente. dAtriDistancia estimada de un objeto atractor al robot. αAtriConstante de caida del campo atractor. βRepjConstante de caida del campo repulsor. φhead Ángulo de la cabeza del robot con respecto a su dirección de avance. φimg Ángulo del centro de los objetos visualizados respecto del punto inferior medio de la imagen de cámara. φobj (Estimación del) Ángulo los objetos visualizados respecto a la dirección de avance del robot. AaiÁrea visible del objeto atractor i. ArjÁrea visible del objeto repulsor j. krep Número de objetos repulsores/factor de ponderación del componente atractor en la generación del vector PF. ~ VP F Vector generado mediante PFA para la adaptación de un caso CBR. ~ VRepjVector PFA de repulsion del objeto j. IX Índice de símbolos X Índice de figuras 2.1. Primitivas Sense-Plan-Act en los diferentes paradigmas . . . . . . . . . 11 2.2. Comportamiento complejo por superposición de comp. reactivos . . . . 13 2.3. Ejemplos de arquitecturas Jerárquicas . . . . . . . . . . . . . . . . . . . 15 2.4. Arquitectura reactiva de subsunción . . . . . . . . . . . . . . . . . . . . 16 2.5. CamposdePotencial............................ 17 2.6. Ejemplos de arquitecturas Híbridas de Gestión . . . . . . . . . . . . . . 19 2.7. Arquitectura3T............................... 20 2.8. Ejemplos de arquitecturas Híbridas orientadas a Modelos . . . . . . . . 21 2.9. Definición gráfica de un comportamiento . . . . . . . . . . . . . . . . . 23 2.10. Mecanismo de liberación de comportamientos . . . . . . . . . . . . . . 24 2.11. Ciclo Percepción-Acción . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.12. Flujo de información en la IA clásica (izquierda) y en BBR (derecha) . 26 2.13. Arquitecturas de selección exclusiva de comportamientos . . . . . . . . 33 2.14. Tipos de combinación de comportamientos . . . . . . . . . . . . . . . . 37 3.1. Ars Magna: árbol del conocimiento . . . . . . . . . . . . . . . . . . . . 40 3.2. TestdeTuring ............................... 41 3.3. Redes Neuronales Artificiales . . . . . . . . . . . . . . . . . . . . . . . . 44 3.4. Estructura y componentes de un Sistema Experto . . . . . . . . . . . . 48 3.5. Ejemplo de una red Bayesiana simple . . . . . . . . . . . . . . . . . . . 49 3.6. Ejemplo de reglas de lógica difusa . . . . . . . . . . . . . . . . . . . . . 50 3.7. Ejemplos de clases en un sistema basado en marcos . . . . . . . . . . . 51 3.8. Organización jerárquica HTM . . . . . . . . . . . . . . . . . . . . . . . 56 4.1. FundamentosdeCBR ........................... 62 4.2. Recipientes de conocimiento CBR y su interacción . . . . . . . . . . . . 67 4.3. ElcicloCBR ................................ 80 4.4. Descomposición de las fases y sub-fases CBR . . . . . . . . . . . . . . . 88 5.1. Marco general de aprendizaje basado en experiencia . . . . . . . . . . . 92 5.2. Estructura de un módulo . . . . . . . . . . . . . . . . . . . . . . . . . . 93 5.3. Base de conocimiento en cada módulo . . . . . . . . . . . . . . . . . . . 94 XI Capítulo 1. Introducción funciones, como volar o incluso ejecutar piezas musicales. A finales del siglo XIX y hasta finales del XX se construyeron varios ingenios de apariencia humana, capaces de realizar únicamente funciones muy específicas; todos ellos se basaban en servomecanismos. El término Robot data de 1921, y apareció por primera vez en la obra de teatro Los Robots Universales Rossum del escritor checo Karel Capek, para describir a servidores de apariencia humana. Desde este momento se empieza a extender la idea de que podría ser posible crear robots con comportamiento y apariencia que imitase a los seres humanos de una forma amplia: primero en la ciencia ficción, con autores como Isaac Asimov; y, poco después, con visos a una implementación real, con la formulación de los principios de la cibernética por parte de Norbert Wiener. Es a partir de aquí que se toma conciencia de que, si se desea diseñar y construir robots con características similares a los seres humanos y que se comporte de forma autónoma, necesitamos dotarles de los medios para adquirir conocimientos acerca del entorno en el que se desenvuelve, procesar y comprender esta información, y tomar las decisiones adecuadas según la tarea que le haya sido encomendada, para influir sobre el mundo a partir de las órdenes a sus componentes motores y actuadores. En resumen, más allá de los componentes mecánicos y electrónicos; de la variedad de sensores; de la forma y estructura del robot, uno de los aspectos fundamentales para su diseño se debe centrar en dotarle de Inteligencia similar a la que tenemos los seres humanos. La Real Academia Española de la Lengua (RAE) define la Inteligencia, en su diccionario de la lengua española, como la “capacidad para entender y comprender” y “la capacidad para resolver problemas”. Detrás de esta aparentemente sencilla definición, nos encontramos algo mucho más complejo: la inteligencia nos permite comprender el mundo que nos rodea, asimilar su información a través de nuestras percepciones, y desenvolvernos en el mismo mediante las respuestas desencadenadas ante las percepciones que tenemos de nuestro entorno. La inteligencia es lo que nos hace seres humanos, lo que nos ha llevado a situarnos por encima del resto de seres vivos en la cadena trófica y lo que marca el acento en la evolución de nuestro futuro. Sin embargo los aspectos clave de la inteligencia permanecen aún envueltos en la bruma del misterio; sabemos que la tenemos, la usamos a diario para resolver problemas o realizar nuestras tareas cotidianas, pero no conocemos en toda su profundidad como se desarrolla, como funciona, que factores que una persona pueda llegar a alcanzar un potencial distinto de otra, etc.... Diversos investigadores de distintas áreas (Psicología, Biología, Computación,...) han reconstruido pequeñas partes aisladas del gran puzle, pero aún estamos lejos de completarlo. La IA es un área multidisciplinar que estudia la creación y diseño de entidades artificiales con capacidad de razonar y resolver problemas de manera similar a como lo hacemos los seres humanos. Aunque la mayoría de los trabajos se desarrollan en las áreas de Ciencias de la Computación (Informática, Robótica, Electrónica,..), la IA se apoya en gran medida en los conocimientos propios de otras áreas, como la Psicología, la Lógica, la Filosofía, o la Biología. En resumen, trata de trasladar los conocimientos que tenemos de la Inteligencia Humana 1al campo de la computación. Por ello, resulta fundamental el campo de origen a partir del cual se desarrollan las teorías e intentos de la IA: los nuevos avances y teorías acerca de la Inteligencia Humana constituyen un buen punto de partida para intentar desarrollar nuevos modelos de IA. En este sentido, esta tesis parte del análisis un nuevo modelo de Inteligencia 1Nos referimos a Inteligencia Humana en contraposición a la Inteligencia Artificial 2 3. Objetivos de la tesis Humana, el modelo memoria/predicción desarrollado por el profesor Jeff Hawkins en su libro On Intelligence [1], para tratar de establecer una posible arquitectura de IA aplicable a la robótica. Dentro de esta arquitectura nos interesa especialmente las capas de nivel más bajo, que permitirían que un robot pudiese aprender comportamientos a un nivel reactivo, a partir de las experiencias vividas en situaciones similares durante su funcionamiento. Para la implementación de estas capas nos basaremos, en principio, en uno de los tipos de sistemas expertos que en nuestra opinión mejor se ajustan al modelo original, como es el razonamiento basado en casos o CBR. 3. Objetivos de la tesis En la actualidad, las arquitecturas híbridas de modelado de inteligencia son, debido a su competencia y aplicación exitosa, las preferidas para el diseño de sistemas de control inteligente de los robots modernos. La mayoría de estas arquitecturas constan de una capa deliberativa de alto nivel, que gestiona los objetivos globales del robot a largo plazo, manejando para ello conocimiento más abstracto; de una capa reactiva que determina la respuesta del robot de forma local y a corto plazo, y está constituida por comportamientos rudimentarios; y de una o varias capas intermedias que actúan como interfaz o árbitro entre las capas deliberativa y reactiva. Las diversas implementaciones existentes pueden diferir en la organización de sus capas; en las herramientas o técnicas empleadas para implementar estas capas; o en las mecanismos para seleccionar o combinar los módulos que las integran. Sin embargo y, por lo general, los comportamientos se suelen diseñar en las etapas iniciales de desarrollo de la arquitectura y de un modo algorítmico inmutable con poca o ninguna capacidad de adaptación a posibles cambios en el entorno o en la evolución del problema. Hay ciertas evidencias que sugieren que estos componentes reactivos deberían tener capacidad de cambio o adaptación mediante un aprendizaje derivado de las situaciones experimentadas por el robot. Por ejemplo, el campo de la Etología nos enseña como existen ciertos comportamientos presentes en algunos animales, los llamados comportamientos reflejos o innatos, que son adquiridos desde el nacimiento, y que podrían “imitarse” en un robot mediante la programación de patrones sensación-acción, o usando Máquinas de Estado Finito —Finite State Machine (FSM)—. Por otra parte, las conductas y habilidades aprendidas deben ser entrenadas y desarrolladas mediante repeticiones y experimentación. Finalmente, tenemos los comportamientos innatos-con-memoria, una variante de los comportamientos innatos, que necesitan de un ajuste o puesta a punto a través de la experiencia: es así como, por ejemplo, una abeja-infante aprende, a partir del reflejo innato de vuelo. a reconocer el aspecto de su panal y como navegar desde y hacia él [2]. Adicionalmente, las teorías más actuales acerca de la inteligencia humana afirman que, incluso en una respuesta deliberativa compleja, solo hay un número pequeño de neuronas implicadas en la transmisión de impulsos nerviosos que constituye el reflejo del pensamiento, transmisión que tampoco se realiza a una velocidad muy elevada y que está, en todo caso, muy alejada de la velocidad de procesamiento de cualquier computador moderno. En vez de en la velocidad o capacidad de procesamiento, la inteligencia humana parece estar basada en el aprendizaje por experiencia, en almacenar los eventos diarios, los conocimientos adquiridos, las respuestas dadas, en 3 Capítulo 1. Introducción la potente base de datos constituida por nuestro cerebro, para recuperarlas cuando se presente una situación similar [1]. A día de hoy ya existen multitud de arquitecturas robóticas híbridas que siguen estas pautas de adaptación o aprendizaje [3] [4] [5],pero la mayoría se centra en el aprendizaje en los niveles deliberativos. Según estudios recientes, el cerebro humano parece seguir una estructura cíclica o “de nido”, de forma que sus diferentes áreas deberían operar según los mismos principios de funcionamiento sin importar a que aspectos se dediquen. Solo se diferenciarían en la naturaleza de la información tratada y, especialmente, en el nivel de abstracción de los conceptos manejados que determinaría su posición en la cadena de razonamiento [1]. Así, parece razonable proponer una arquitectura de inteligencia robótica en la cual sus diferentes capas tendrían mecanismos de operación equivalentes, al menos a un nivel funcional y de procesamiento de la información. De este modo, todas las capas y sub-capas a cualquier nivel deberían fundarse en algún tipo de aprendizaje por experiencia, y esto incluye a las capas inferiores de tipo reactivo. Además de mejorar la flexibilidad y adaptabilidad del nivel reactivo, la arquitectura ganaría en homogeneidad y escalabilidad, especialmente si se emplean los mismo métodos o herramientas de IA. En este sentido, proponemos CBR como el método que consideramos más adecuado para acometer esta tarea, como veremos a continuación. En un arquitectura robótica híbrida, la capa reactiva se basa en establecer una correspondencia entre la información sensorial y la respuesta de los actuadores, mediante un conjunto de módulos rudimentarios de bajo nivel denominados “comportamientos”. Estos módulos no necesitan un modelo complejo del entorno o del problema a resolver, ya que trabajan únicamente con información local y a corto plazo, relacionada con los objetivos o campo de acción del comportamiento. Esto los hace especialmente adecuados para una toma de decisiones rápida a bajo nivel, algo fundamental en entornos dinámicos y no estructurados. Además, y mediante su combinación, debería ser posible obtener comportamientos emergentes más complejos —de nivel “más alto”—, lo cual redundaría positivamente en la escalabilidad del sistema. Esta emergencia se puede conseguir de diferentes formas, desde conmutación entre comportamientos hasta arquitecturas de subsunción [6], pasando por el uso de campos de potencial —Potential Fields (PF)— [7], pero en todas estas técnicas es necesario ajustar u optimizar un alto número de parámetros conforme al problema a resolver, con lo que existe una gran dependencia de aspectos como la cinemática y dinámica del robot empleado, la calibración de los sensores, o la aparición de errores de origen mecánico. Por este motivo, gran número de arquitecturas o capas reactivas incluyen herramientas de IA tales como reglas de lógica difusa —Fuzzy Logic (FL)— [8] [9], o redes neuronales artificiales —Artificial Neural Networks (ANN)— [10] que permiten un “ajuste fino” de los comportamientos a través de su ejecución. No obstante, el desarrollo de las expresiones analíticas que definan un comportamiento suele ser una tarea ardua, ya que algunos comportamientos son difíciles de expresar y se adaptan mejor a una función u otra dependiendo de las circunstancias específicas de operación. Los métodos basados en lógica difusa definen un conjunto de reglas para establecer correspondencias entre las lecturas de los sensores del robot y las instrucciones motoras, reglas cuyos parámetros pueden ajustarse a través del funcionamiento del robot. Sin embargo, resulta complejo diseñar correctamente estas reglas, ya que para ello se requiere un gran dominio tanto del 4 4. Estructura de la tesis campo de la lógica difusa como del dominio del problema a resolver. Por su parte las ANN no presentan estos problemas ya que, una vez se ha escogido la estructura de capas y neuronas de la red neuronal, el proceso de aprendizaje resulta transparente para el usuario. Por contra, aunque el uso de ANN nos va a proporcionar un sistema de control mejor o peor, no nos proporciona ninguna pista acerca de que se podría hacer para mejorar su comportamiento, ya que las ANN son, para el usuario, similares a “cajas negras”. Frente a estas herramientas tenemos CBR que, combinado con una adquisición de conocimientos a través del aprendizaje nos permite, no solo obtener un sistema totalmente funcional, sino comprender también el proceso de aprendizaje y adquisición de conocimientos, lo cual resulta extremadamente útil para la depuración de errores o funcionamientos incorrectos del sistema. Por este motivo, en esta tesis elegiremos CBR como el elemento fundamental sobre el que se basa el diseño de la arquitectura de inteligencia robótica propuesta. A partir de bases CBR especialmente modificadas y adaptadas a las necesidades de la arquitectura, desarrollaremos módulos que implementen comportamientos básicos a nivel reactivo, cuya funcionamiento se aprenderá a través de un entrenamiento y de la experiencia del robot. Posteriormente, y siempre a un nivel reactivo, se estudiará la forma de combinar entre sí varios de estos comportamientos para conseguir obtener un comportamiento emergente de nivel superior. 4. Estructura de la tesis Este trabajo se enmarca dentro de una de las líneas de investigación que ha venido desarrollando, en los últimos años, el grupo de investigación Ingeniería de Sistemas Integrados (ISIS), dentro del Departamento de Tecnología Electrónica, en el campo de la Inteligencia Computacional aplicada a la Robótica. ISIS ha participado en varios proyectos de investigación (TIN2004-05961 TIN2004-07741-C02-01, TIN2008-06196/TIN, o TIN2011-27512-C05-01, entre otros) en los cuales se han implementado y probado diversos paradigmas de IA en el entorno de la Robótica. El trabajo se entronca también con otras tesis desarrolladas por miembros del grupo [11] [12]. Una gran parte de estos trabajos previos ya utilizan CBR como paradigma fundamental del modelo de inteligencia artificial desarrollado, si bien la gran mayoría se centra en los niveles deliberativos o de planificación a alto nivel en las arquitecturas de comportamiento desarrolladas. Además, estos trabajos no utilizan la visión artificial como fuente principal de información del robot. Por último, todos ellos trabajan con robots rodantes, por lo que se eluden una serie de aspectos que cobran especial relevancia con el uso de robots de tipo bípedo o cuadrúpedo. La organización seguida en la presente tesis es la que se describe a continuación: Capítulo 2. Arquitecturas y Comportamientos . Este capítulo se centra en el concepto de arquitectura, entendida como el modelo de organización y procesamiento de información que hace posible la inteligencia en un robot. En él se repasarán las principales familias o paradigmas de arquitectura robótica, indicando algunos ejemplos de implementación de las mismas. De todas ellas, nos fijaremos seguidamente en las arquitecturas y capas reactivas, para las cuales se define el concepto de comportamiento, como elemento fundamental constituyente. Se realizará un breve repaso a los comportamientos, desde su origen bioĺógico 5 Capítulo 1. Introducción hasta su aplicación en el ámbito de la robótica, revisando sus aspectos asociados más importantes que serán tratados posteriormente de forma práctica. Capítulo 3. Inteligencia y aprendizaje. En este capítulo se realizará una revisión del concepto de inteligencia, inicialmente referida a la inteligencia humana, para su posterior trasposición a la inteligencia artificial o robótica. De esta última se realizará un rápido repaso de sus herramientas y métodos más relevantes. A continuación, se incidirá en el papel que tiene el aprendizaje en el desarrollo de la inteligencia partiendo, de nuevo, desde la visión de la inteligencia humana. Por último, se estudiará y analizará el modelo “memoria/predicción” de Inteligencia Humana, propuesto por J. Hawkins que, trasladado al campo de la Robótica, constituirá la base teórica de la arquitectura de inteligencia propuesta en esta tesis. Capítulo 4. CBR: razonamiento basado en Casos. Se estudiará de forma detallada las características y aspectos más relevantes de esta herramienta IA, prestando especial importancia a los aspectos de adquisición y gestión del conocimiento en la misma. Se tratará de buscar analogías entre sus diferentes aspectos y componentes, y los asociados al modelo “memoria-predicción” analizado en el capítulo anterior, como medio de implementar dicho modelo en el ámbito de la Robótica. Capítulo 5. Arquitectura híbrida de aprendizaje basada en CBR. En este capítulo se propondrá una arquitectura de IA basada en el modelo de inteligencia “memoria-predicción”, y fundamentada en CBR 2. De esta arquitectura se estudiará en detalle la implementación de sus capas inferiores (capas reactivas) en un robot cuadrúpedo modelo Artificial Intelligence roBOt (AIBO) cuyo funcionamiento se probará en la resolución de un problema en un entorno simulado. En dicho problema, la fuente principal de información para el robot provendrá de una cámara integrada en el mismo, por lo que tendremos que resolver varios problemas relacionados con la Visión Artificial. Capítulo 6. Pruebas experimentales. Este capítulo está dedicado a presentar las pruebas realizadas para analizar la viabilidad de la capa de arquitectura propuesta en los capítulos anteriores. Para ello se presentará un escenario de pruebas —campo de fútbol de Robocup para AIBOs— para el cual se desarrollarán módulos básicos CBR que implementen comportamientos o aspectos de comportamientos a través de un entrenamiento previo complementado con un aprendizaje por experiencia. Se detallará el proceso de diseño e implementación de los módulos justificando las decisiones tomadas. Finalmente se propondrán algunas pruebas de combinación de módulos básicos para la obtención de comportamientos emergentes más complejos. Capítulo 7. Conclusiones y Lineas Futuras. Para finalizar en este capítulo, y a la luz de los resultados obtenidos en el capítulo de Pruebas, se establecerán las adecuadas conclusiones respecto a la capacidad de la arquitectura propuesta como base para implementar la capa reactiva de una arquitectura híbrida de 2Se propondrán también alternativas que incluyan otros paradigmas de IA como, por ejemplo, reglas de decisión 6 4. Estructura de la tesis inteligencia robótica. Así mismo, se detallarán posibles líneas de acción para subsanar debilidades o errores de la misma, y/o buscar nuevas propuestas basadas en el paradigma CBR o en variantes del mismo que añadan otros métodos o herramientas complementarias de IA . 7 Capítulo 1. Introducción 8 2 Arquitecturas y comportamientos “El comportamiento es un espejo en el que cada uno muestra su ser Johann Wolfgang von Goethe (1749-1832) Escritor y científico ” 1. Arquitecturas de control Los sistemas robóticos se diferencian de muchas otras aplicaciones tecnológicas en la complejidad de sus objetivos de funcionamiento y en la necesidad de desenvolverse en entornos dinámicos no estructurados. En esta situación, la combinación de la propia dinámica del robot con la de su entorno, la aparición de errores e incertidumbre, y la necesidad de reaccionar en tiempo real ante situaciones inesperadas o no perfectamente definidas, determinan que los aspectos de diseño, operación, y validación de estos sistemas requieran un tratamiento especial y un conjunto de técnicas adecuadas. En el ámbito de la Robótica, una arquitectura de control define un marco de implementación y un conjunto de herramientas que permiten afrontar la complejidad del diseño y realización de un robot completo o un sistema o subsistema del mismo. La arquitectura de un robot engloba diferentes aspectos o puntos de vista. La estructura arquitectónica se refiere a como un sistema complejo se puede dividir en subsistemas, y a la forma en que estos interactúan; un ejemplo sería establecer una serie de capas o niveles, cada uno de los cuales trata con un aspecto específico de funcionamiento del robot. En cambio, el estilo arquitectónico se centra a los conceptos computacionales o algorítmicos que subyacen en el sistema, por ejemplo, si el intercambio de información entre los módulos del sistema se realiza mediante sockets o memoria compartida, o si se utiliza el entorno Tekkotsu o el Robot Operating System (ROS) para el desarrollo software de la estructura. Si bien todo robot tiene una arquitectura con una estructura dada y un estilo, a menudo resulta complicado separarla de la implementación particular sobre la que se ha desarrollado inicialmente. Por lo general la elección de la arquitectura está muy influenciada por el tipo de aplicación para la que se diseña el sistema o subsistema o, en el caso de los robots, a la funcionalidad que se trata de conseguir en su operación. Por este motivo, la búsqueda de una arquitectura con una orientación más generalista como el diseño de un marco general de inteligencia robótica, resulta 9 Capítulo 2. Arquitecturas y comportamientos una tarea realmente difícil. En todo caso, la estructura de la arquitectura estará más orientada a la implementación particular, e implica la realización de una filosofía que se puede obtener a través de diversas herramientas. En esta tesis consideraremos ambos aspectos, si bien dentro de la filosofía —en nuestro caso, la importancia del aprendizaje como elemento clave de la inteligencia—, nos centraremos en la implementación de una determinada estructura. Para ello seguiremos una estrategia de descomposición en la cual dividiremos el sistema a implementar en módulos, unidades funcionales menores interconectadas entre sí que, al operar conjuntamente, desarrollarán la funcionalidad total del sistema. Esta descomposición nos permite afrontar el diseño de cada módulo de forma independiente lo cual redunda en un diseño mas fácil de abordar. Por el contrario, la división da lugar a una necesaria fase de integración de componentes en la cual se deposita gran parte de la complejidad eludida a través del diseño individual de los módulos. En los siguientes apartados se analizarán someramente los principales estilos de arquitectura de control existentes en el estado de la ciencia actual, en lo referente a su aplicación al diseño de una arquitectura de inteligencia robótica. Estos son los denominados Paradigmas de inteligencia robótica, y son el paradigma jerárquico o deliberativo; el paradigma reactivo; y, por último, el paradigma híbrido. 2. Paradigmas de inteligencia robótica Aunque hay una enorme variedad de robots, con diferentes capacidades y entornos o campos de utilización, todos ellos comparten unas mismas características en lo relacionado a su estructura y componentes. Todo robot tiene un armazón o estructura mecánica con una forma física, orientada generalmente a la realización de una tarea en particular. Esta estructura está muy relacionada con las necesidades sensoriales de adquisición de información, y las necesidades motoras asociadas al tipo de movimiento y manipulación que es capaz de desarrollar el robot, que determinan la inclusión de los sensores y actuadores adecuados a dichos requerimientos. Además, los robots contienen algún tipo de elemento de control que determina que debe hacer el robot en cada momento según las circunstancias en que se encuentre, tanto a nivel del estado del entorno, como de su propio estado actual interno, y el objetivo —o sub-objetivo final— que determina su razón de ser. Este elemento de control es lo que constituye lo que podríamos denominar la Inteligencia del robot. En este sentido, se suele considerar la existencia de tres grandes familias o paradigmas que estudian posibles formas de organización de la inteligencia en los robots: jerárquico,reactivo, e híbrido deliberativo/reactivo. Para diferencia entre estos paradigmas, partimos de la existencia de tres primitivas básicas que definen el funcionamiento de un robot: sensar(SENSE), planificar(PLAN), y actuar(ACT) [13]. La operación de sensar, nos permite recolectar información del entorno del robot a través de sus diversos sensores; planificar, se centra en construir un modelo del mundo en el que se desenvuelve el robot, y determinar las acciones a realizar según el estado de dicho entorno y la funcionalidad o motivación que rige al robot; actuar, se refiere a como realizar las acciones planificadas en el paso anterior, así como supervisar su cumplimiento. Es a través de estas primitivas como establecemos las diferencias entre los paradigmas y sus implementaciones: en particular, según la forma en que se relacionan las tres primitivas; pero también según como se procesa y distribuye la 10 2. Paradigmas de inteligencia robótica información sensorial a través de todo el sistema que integra al robot, y en que lugar —o lugares— del sistema se toman las decisiones correspondientes a la planificación. Figura 2.1: Primitivas Sense-Plan-Act en los diferentes paradigmas(C. Urdiales) 2.1. Paradigma Jerárquico El paradigma Jerárquico (también llamado Deliberativo) es el más antiguo de los tres y fue el más empleado hasta principios de los 90. Bajo este paradigma, las tres primitivas de la Robótica se engarzan de forma secuencial y ordenada, en una filosofía descendente (top-down). En primer lugar, el robot obtiene información de su entorno a través de sus sensores (SENSE) y construye un modelo de su entorno y del estado actual del mismo; en una segunda fase, el robot computa las órdenes y acciones necesarias para alcanzar o al menos acercarse a su objetivo (PLAN); y en una tercera fase, se trasladan esas órdenes a comandos debajo nivel sobre los actuadores que permiten llevarlas a cabo (ACT, figura 2.1.a) [14] [15]. Shakey, el considerado como primer robot móvil autónomo con IA utilizaba una variante de este paradigma. A medida que aumentó la complejidad de los robots y de las tareas a realizar por estos, empezaron a mostrarse las limitaciones de este modelo. La información necesita atravesar todos los módulos de la arquitectura, por lo que cualquier fallo en alguno de ellos provoca un fallo total del sistema. La construcción de un modelo del mundo, que incluya no solo las características mas o menos estables del entorno, sino las cambiantes, e incluso las del propio robot, se convirtió en una tarea realmente complicada. Además, se reconoció rápidamente el problema de no poder rectificar ante una información errónea, incompleta, o cambiante, durante las fases de planificación y actuación. Para paliar este problema, se introdujeron sub-objetivos dentro del objetivo general del robot, así como la capacidad de evaluar en que medida se iban cumpliendo 11 Capítulo 2. Arquitecturas y comportamientos se agrupan en capas, y no hay especificado un elemento de control coordinado (aunque puede existir). Las arquitecturas reactivas presentan, no obstante, algunos problemas evidentes. Tomando el ejemplo de implementación mediante PFA se suele observar la aparición de oscilaciones en la trayectoria de los robots, especialmente en el recorrido de corredores estrechos, cuando no se produce la caída en situaciones de mínimos o trampas locales que impiden una correcta ejecución del comportamiento [31]. Incluso en ausencia de los problemas anteriormente mencionados, se observa una cierta falta de eficiencia en el funcionamiento, como por ejemplo la dificultad para encontrar y ejecutar el camino más corto y directo en una determinada trayectoria. El principal inconveniente de este tipo de arquitecturas es su limitación a aplicaciones que puedan ser implementadas con comportamientos basados en reflejos. Por tanto, no proporcionan soluciones adecuadas para casos en los que el robot necesita, por ejemplo, razonar acerca de la localización de un recurso, planear un curso de acción, etc...Un robot con esta arquitectura hará siempre algo consistente con su percepción actual del entorno, pero esa acción no tiene porqué ser las más correcta o indicada. Un factor crucial será también la capacitación del sistema sensorial del robot para proporcionar la información mas adecuada a cada comportamiento, y el pre-procesado que le permita dar un formato tratable y manejable por parte de los comportamientos. 3.3. Arquitecturas Híbridas A partir de la década de los 90, comenzaron a aparecer numerosas arquitecturas híbridas de control que presentaban variantes con respecto a las ya existentes. En las arquitecturas híbridas, sus implementaciones se diferencian principalmente en la forma en que se separan las partes reactivas y deliberativas; la manera en que se asignan responsabilidades por parte de la porción deliberativa; y el mecanismo de emergencia del comportamiento global. Las arquitecturas Híbridas más típicas suelen incluir varios módulos funcionales comunes [2]: Un agente secuenciador, que determina el conjunto de comportamientos a usar en la realización de una sub-tarea, y su orden y condiciones de activación. Puede implementarse, por ejemplo con una FSM. Un gestor de recursos, que asigna recursos a los comportamientos e incluso selecciona entre diferentes planes o esquemas. Un cartógrafo, módulo que se ocupa de crear, almacenar, y mantener un modelo del entorno, y una representación de la información necesaria para llevar a cabo su tarea. Un planificador de misiones, que interactúa con los operadores humanos, transfiere sus órdenes a comandos de robot, y genera un plan adecuado a la misión encomendada. Un módulo de monitorización y resolución de problemas, que permite al robot comprobar el progreso de su operación. Las arquitecturas híbridas se suelen encuadrar en una de entre tres posibles categorías: 18 3. Arquitecturas de IA en Robótica (a) Arquitectura AuRA [32] (b) Arquitectura SFX [33] Figura 2.6: Ejemplos de arquitecturas Híbridas de Gestión Arquitecturas de Gestión (managerial), que subdividen la porción deliberativa en capas relacionadas con su alcance de control, de forma similar a como se hace en en un organigrama empresarial: a alto nivel estarían los agentes que establecen un plan global, que pasan a sus subordinados, los cuales se ocupan de concretar los aspectos del mismo, establecer los recursos necesarios, y dar las órdenes adecuadas a los trabajadores del nivel inferior, que en este caso serían los comportamientos reactivos. Cada capa de la arquitectura se comunica únicamente con sus vecinas, superior e inferior; además de indicar órdenes, es posible supervisar el desempeño de las capas inferiores y dar indicaciones adicionales. Ejemplos de esta arquitectura son AuRA (Autonomous Robot Architecture) [32] ySFX (Sensor Fusion Effects) [33] (figura 2.6). Arquitecturas de Jerarquía de Estados (state-hierarchical). Organizan sus actividades por el alcance temporal de la información o conocimiento del entorno mediante 3 capas —relacionadas con el pasado, presente, y futuro—. Hay una jerarquía de capas que operan sobre las capas inmediatamente inferiores, y tienen acceso a las salidas de dichas capas. Dentro de cada capa existen varios agentes que se interrelacionan para lograr el objetivo de cada capa. La arquitectura más característica de este tipo es la 3T o de “tres hileras” [34] (figura 2.7), que es la empleada de forma predominante en los robots de la NASA. En esta arquitectura se establecen 3 capas, una deliberativa (Planner), otra reactiva (Skill Manager) y una que sirve de interfaz entra ambas (Sequencer). Esta última capa recibe los objetivos y estrategias de la capa deliberativa, y utiliza una técnica de planificación reactiva (RAP) [35], para la selección de un subconjunto de comportamientos primitivos reactivos (skills), que se ejecutan según la secuencia indicada por una red de tareas. Estos comportamientos o skills son mas similares a los de las arquitecturas AuRA oSFX, que a a los de las arquitecturas reactivas puras. Asociados a los skills se incluyen eventos (events) que sirven como puntos de verificación de la corrección en las acciones realizadas. 19 Capítulo 2. Arquitecturas y comportamientos Figura 2.7: Arquitectura 3T [34] Arquitecturas orientadas a Modelos (model-oriented). Las dos anteriores categorías de arquitectura tenían una clara componente ascendente (bottom-up): partían de las arquitecturas reactivas y trataban de incorporar funcionalidades de más alto nivel. Sin embargo, existe otra categoría de arquitecturas que siguen una componente descendente (top-down): se centran en la creación de un modelo del entorno que, a la vez, funciona como un “sensor virtual”, en la medida en que proporciona información a los comportamientos (o sus módulos equivalentes). Estos últimos no disponen de sensores específicos asociados, sino que toman su información de dicho modelo. Una ventaja importante de este modelo es la posibilidad de realizar una fusión de la información de los sensores a lo largo del tiempo, de forma que la información que se proporciona a los comportamientos de bajo nivel está mas estructurada, simplificada, y filtrada ante la posibilidad de errores e inconsistencias. Entre las arquitecturas más representativas de esta categoría destacamos Saphira [36], presente en la línea de robots Pioneer; y TCA [18]. Saphira busca establecer una coordinación, no solo en los sensores y actuadores del robot, sino también en el cumplimiento de sus objetivos a lo largo del tiempo: se debe mantener una coherencia entre los mismos, si se desea que el robot sea capaz de desempeñar correctamente su función. Saphira también incide en la necesidad de que el robot sea capaz de comunicarse para interactuar con los seres humanos, y en las dificultadas relacionadas con la búsqueda de un marco común de referencia para esa comunicación. En su implementación original, Saphira realiza la fusión de las salidas de los comportamientos mediante lógica difusa, obteniendo un resultado parecido al de los campos potenciales. Podemos ver un esquema de la arquitectura de Saphira en la figura 2.8a. En cuanto a TCA (figura 2.8b), no tiene comportamientos como tales, aunque las 20 4. Comportamientos (a) Arquitectura Saphira [36] (b) Arquitectura TCA [18] Figura 2.8: Ejemplos de arquitecturas Híbridas orientadas a Modelos capas inferiores son muy similares a estos; la inteligencia se distribuye en capas y los errores en los módulos de nivel inferior se propagan hacia las capas superiores para encontrar una posible solución, de manera similar a lo que se propone en el modelo de inteligencia Memoria Jerárquica Temporal —Hierarchical Temporal Memory (HTM)— de Hawkins [37]. Hay que destacara que, a menudo, se encajan en esta categoría de Híbridas, aquellas arquitecturas que no encajan entre las Jerárquicas o Reactivas Puras, la gran mayoría emplean módulos o elementos que se pueden ajustar al concepto de comportamiento, aunque a menudo se usan otros nombres. También suele ser aceptada el establecimiento de capas de abstracción de la inteligencia tanto a nivel conceptual como temporal, existiendo capas de nivel superior de tipo deliberativo y capas de nivel inferior de tipo reactivo puros; lo que diferencia a unas arquitecturas híbridas de otras suele ser la existencia de capas intermedias de “acoplo” de las deliberativas y reactivas, y la forma de organizar, estructurar, y controlar cada una de las capas, así como las técnicas o métodos empleadas para su implementación (ANN,CBR, lógica difusa, reglas de decisión,etc...). 4. Comportamientos Tras la revisión general a los paradigmas y arquitecturas existentes en IA, en este apartado se tratará con más detalle los aspectos relacionados con los Comportamientos, concepto que apareció por primera vez en las arquitecturas reactivas, y que también suele formar parte de las capas inferiores de las más modernas arquitecturas híbridas. La motivación de este apartado es el enfoque de la tesis a la implementación, a través de comportamientos, en las capas reactivas de la arquitectura híbrida propuesta, basada en el modelo HTM. 21 Capítulo 2. Arquitecturas y comportamientos El concepto de Comportamiento básico aplicado a IA, aparece por primera vez en la tesis de Maja Mataric [23], si bien este trabajo se puede considerar heredero de los trabajos previos de Brooks a mediados de los 80 [26]. Los comportamientos permitirían establecer un modelo descentralizado de la inteligencia, en el que de podría obtener una funcionalidad compleja e inteligente a partir de interacciones locales, estructuradas en dichos comportamientos, y mediante el uso de reglas sencillas. Un comportamiento establecería unas leyes de conducta que aspirarían a lograr un determinado objetivo, cumpliendo una serie de restricciones. En este sentido, para muchos autores la Robótica basada en Comportamientos (Behavior-Based Robotics (BBR)) constituye una evolución de la implementación primitiva del paradigma reactivo. 4.1. Orígenes biológicos de los comportamientos: Agentes Inteligentes Muchos investigadores en IA y en Robótica toman como modelo para sus trabajos, aspectos relacionados con ciencias biológico-humanas como la Psicología, o la Biología. Aunque existen ejemplos de logros tecnológicos que han divergido completamente de su equivalente biológico —siendo el más evidente el vuelo a reacción de los aviones, frente al aleteo de los pájaros— se pueden obtener importantes consecuencias observando la conducta de los seres vivos. Parece razonable acudir al modelo más perfecto que conocemos de la inteligencia, la Inteligencia Humana, como punto de partida, a pesar de lo mucho que nos queda todavía por conocer acerca de ésta. Pero esta aproximación no tiene porqué hacerse necesariamente desde un punto de vista“ mecanicista“ como hacen, por ejemplo, los ”conexionistas“ con sus modelos de ANN; en su lugar, se puede buscar una equivalencia funcional. Para conseguir esta equivalencia se define el concepto de agente, como sistema capaz de interactuar con el mundo, para obtener información y actuar sobre este, siguiendo unas reglas de conducta. Este concepto se puede aplicar tanto a un animal como un insecto o un perro, a una persona, pero también a seres artificiales. En última instancia. la única diferencia entre estas realizaciones de un agente radica en como se implementan y relacionan los diferentes sub-componentes del sistema. Así, por ejemplo en [38] se establece una correspondencia entre los diversos comportamientos-agentes asociados a la navegación de animales y robots, a través de una jerarquía de navegación. Los comportamientos animales se basan en establecer una correspondencia entre un conjunto de entradas sensoriales y unas acciones motoras que permitan realizar la tarea u objetivo asociado al comportamiento. En el campo de la Etología, se distinguen 3 tipos de comportamientos animales: reflejos, que están ”grabados“ en los circuitos neuronales, y generalmente se corresponden con comportamientos con necesidades de respuesta rápida; reactivos, que se aprenden inicialmente y se consolidan para ser ejecutados de forma no consciente; y conscientes, que se ejecutan de manera deliberativa. Nótese que el término ”reactivo“ tiene unas connotaciones distintas que las utilizadas generalmente en Robótica, que se corresponderían mas con ”reflejo“. En esta tesis utilizaremos la acepción etológica de ”reactivo“, puesto que los comportamientos que forman la base de nuestro modelo serán aprendidos. Además de la identificación de los propios comportamientos en sí mismos, otros aspectos claves estudiados en la Etología son la forma en que se adquieren dichos 22 4. Comportamientos Figura 2.9: Definición gráfica de un comportamiento comportamientos —cuando no son innatos— y como se seleccionan y coordinan conjuntos de comportamientos que se ejecutan simultáneamente. 4.1.1. Tipos de comportamientos según su adquisición En cuanto a la adquisición de los comportamientos, se diferencian cuatro formas [39]: Comportamientos innatos de tipo reflejo, como el reflejo de succión de un recién nacido ante la sensación de hambre. En Robótica se corresponderían con comportamientos pre-programados. Secuencia de comportamientos innatos. Está compuesta por comportamientos similares al del punto anterior, pero que desencadenan la aparición de un nuevo comportamiento. Existe una especie de estado interno que va modificándose a medida que van ejecutándose los comportamientos de la secuencia como , por ejemplo, todos los pasos necesarios para que una avispa se aparee, construya un nido, y ponga huevos en el mismo, pasos que van sucediéndose según la combinación de las condiciones del entorno y ese estado interno. Este tipo de conductas se puede imitar fácilmente en Robótica usando FSM. Comportamientos innatos con memoria. Son comportamientos innatos que necesitan de una cierta ”personalización“. Un ejemplo es el comportamiento de las abejas jóvenes para aprender a reconocer la forma de su colmena: de forma innata vuelan alrededor de la colmena pero , al mismo tiempo. aprenden a reconocerla y pueden así encontrar su apertura de entrada. En Robótica se podrían implementar mediante algoritmos pre-programados con parámetros ajustables a través de la operación del robot. Comportamientos aprendidos, que son los más comunes en animales superiores como los mamíferos y primates, como podría ser el aprendizaje de caza en las crías de león. Este tipo de comportamiento suele ser más complejo, pero suele estar compuesto de comportamientos más simples (en el caso de la caza, por ejemplo, buscar a la presa, acecharla, rodearla,etc...), muchos de ellos innatos. En muchos casos el aprendizaje de estos comportamientos tiene por objeto determinar cuando desencadenar un comportamiento y que acciones llevar a cabo en el mismo. 4.1.2. Control y coordinación de comportamientos En cuanto al control y coordinación de comportamientos, Lorenz y Tinbergen definieron [40, 41] el concepto de mecanismo de liberación innata (Innate Releasing 23 Capítulo 2. Arquitecturas y comportamientos Mechanism (IRM)). En el IRM un comportamiento se activa en respuesta a un estímulo específico, que cumple una determinada condición (liberador o releaser) sin la cual el comportamiento no se ejecuta (figura 2.10). A diferencia de los comportamientos reflejos, no basta con que se da la entrada sensorial adecuada para que el comportamiento produzca una salida. A menudo el estímulo liberador procede de un preprocesado de la información sensorial, o de aspectos más abstractos de la misma. Así mismo, puede ser necesaria una combinación de varios estímulos liberadores, tanto internos (motivaciones como el hambre o el miedo), como externos (del entorno, como la presencia de comida o de un predador), para activar el comportamiento. La activación de varios comportamientos se puede producir en paralelo, siempre que se cumplan los estímulos liberadores correspondientes, dando la impresión de un comportamiento conjunto más complejo. Algunos comportamientos pueden entrar en conflicto y/o afectar a la ejecución de otros. Se pueden dar situaciones de equilibrio entre los comportamientos que lleven a que ambos se ejecuten simultáneamente —o no lleguen a ejecutarse del todo!—; de dominancia, por el que solo uno de los comportamientos llega a ejecutarse; o incluso de cancelación, en cuyo caso, los comportamientos se anulan, y puede llegar a ejecutarse un tercer comportamiento completamente distinto. Figura 2.10: Mecanismo de liberación de comportamientos 4.1.3. Recolección de información: tipos de percepción Otro aspecto clave de los comportamientos —refiriéndonos aún a los animales— es el relacionado con la forma en que se obtiene la información sensorial y como afecta esta información a los comportamientos: en este sentido, los agentes inteligentes participan de un ciclo de acción-percepción en el que la propia actuación del agente provoca cambios en el entorno y, por tanto, en la percepción que tiene el agente del mismo (figura 2.11). Este proceso puede llevar a una estimación de posibles errores o consecuencias de las acciones, que pueden modificar futuras actuaciones; o a predicciones de lo que se espera encontrar en futuras percepciones del mundo. Aunque la percepción del mundo es algo continuo y, a menudo, automático, a veces el agente necesita dirigir sus acciones a la obtención de una determinada información en concreto, necesaria u orientada a la realización de sus objetivos; es lo que se conoce como percepción activa. Las acciones o comportamientos se activarán cuando se detecten los estímulos liberadores asociados a los mismos. Pero las percepciones, además de activar 24 4. Comportamientos Figura 2.11: Ciclo Percepción-Acción los comportamientos, también proporcionan información necesaria para su realización (percepción orientada a acción). Las percepciones del mundo nos permiten obtener información de varias maneras: por una parte,existe una percepción directa que permite reconocer potencialidades (affordances [42]) del entorno para la realización de una acción, sin necesidad de memoria, inferencia, o interpretación. Un ejemplo es nuestra conducta de esquivar un objeto lanzado por sorpresa contra nuestra cara: en este caso, el flujo óptico del objeto nos permite establecer el tiempo de contacto y esquivarlo a tiempo, sin que existan una etapa consciente deliberativa que determine la acción a tomar. Por otro lado, existen otras formas mas complejas de percepción en los animales: para reconocer instancias particulares de un objeto —por ejemplo, el coche de uno mismo— si que es necesaria la memoria; en general, para la resolución de tareas más complejas que impliquen inferencia o interpretación, no basta con la percepción directa, sino que es necesario un modelo interno, y una percepción descendente [43]. Este es un aspecto importante a la hora de diseñar los comportamientos de un robot: si el comportamiento se puede diseñar mediante percepción directa únicamente, su arquitectura de IA y programación resultará más sencilla que si requiere reconocimiento. Todos los conceptos analizados en los apartados anteriores,nacidos en el ámbito de la Etología, se pueden trasladar al ámbito de la Robótica, dando lugar a la aparición de arquitecturas de control y modelos de inteligencia robóticos basados en comportamientos (BBR). En el siguiente apartado se tratarán los aspectos fundamentales para conseguir esta trasposición de conceptos, muchos de los cuales se tendrán en cuenta para el diseño de la arquitectura que es objeto de estudio en esta tesis. 4.2. Robótica basada en comportamientos BBR propone una implementación de la IA que difiere considerablemente de los paradigmas más clásicos de IA, en los cuales ya hemos visto que suele existir un flujo de información secuencial: primero se obtiene información del entorno a través del ”sensado“ (Sense); a continuación se construye un modelo del mundo, por lo general bastante complejo, a partir del cual se intenta evaluar el efecto que tendría la realización de las posibles acciones sobre el entorno (Plan); y finalmente se decide la acción o acciones a tomar, y se ejecutan (Act). Este tipo de modelos difiere 25 Capítulo 2. Arquitecturas y comportamientos bastante de la forma de trabajar del cerebro humano que, como veremos en un capítulo posterior, tiene una orientación más distribuida. Por ello, el paradigma SPA presenta una respuesta bastante lenta y difícil de aplicar en entornos dinámicos y poco estructurados. Por contra,BBR propone una alternativa a la IA clásica, mediante la construcción de comportamientos inteligentes de forma ascendente (bottom-up), y partiendo de comportamientos simples que se ejecutan simultáneamente en el cerebro robótico, proporcionando sugerencias acerca de las posibles acciones que podría llevar a cabo un robot ante una determinada situación (figura 2.12). Mientras que en el diseño top-down se parte del sistema completo, y se descompone ésta en sub-sistemas cada vez más pequeños y sencillos, en la filosofía bottom-up se trabaja con porciones aisladas del problema o sistema o resolver, que se implementan mediante componentes simples conectados en red. La visión top-down suele hacer énfasis en el análisis formal y la caracterización de requisitos, buscando que la abstracción esconda los detalles de bajo nivel en el alto nivel. Por contra, el diseño bottom-up se apoya en la experimentación y la adaptación para realizar un mapeo directo entre percepciones locales a un módulo y acción como respuesta del mismo. Un aspecto clave es la consecución de comportamientos mas complejos a través de la combinación de los simples. Aunque BBR puede parecer exactamente igual a las arquitecturas reactivas clásicas —o a las porciones reactivas de arquitecturas híbridas como la 3T—, las redes de comportamientos pueden tener un estado, y establecer una representación del problema, algo que no es posible en los esquemas reactivos puros. Esta característica permite expandir enormemente las capacidades de expresión y aprendizaje de estos sistemas. Además, en las arquitecturas híbridas se establece una clara diferenciación entre la operación a corto plazo de las capas reactivas, y a largo plazo de las capas deliberativas, mientras que en BBR se trata de usar una representación y una escala temporal uniforme, buscando que cada parte se acomode en tiempo real a las necesidades de otras partes del sistema [44]. Figura 2.12: Flujo de información en la IA clásica (izquierda) y en BBR (derecha) En este ámbito, un comportamiento se define a través de una secuencia de acciones que se ejecutan en un orden determinado y que permiten alcanzar un determinado objetivo. Este tipo de comportamiento inteligente no necesita de razonamiento o deliberación, y está mas relacionado con la capacidad de sobrevivir y luchar por alcanzar una serie de objetivos mientras se desenvuelve en un entorno abierto y no estructurado. Los robots basados en comportamientos presentan, por lo general, una serie de características comunes: 26 4. Comportamientos Inicialmente presentan o se les proporciona comportamientos muy básicos, como la evitación de obstáculos o la búsqueda de fuentes de energía, que son indispensables para poder desenvolverse en un entorno no estructurado. Algunos de estos comportamientos van a operar de forma simultánea, de forma que la acción final ejecutada por el robot va a implementarse a partir de las sugerencias obtenidas de los diferentes comportamientos, bien por elección de una de ellas, bien por composición, o utilizando técnicas más complejas; BBR, como arquitectura de control, suele estar más asociado a la implementación de robots autónomos, que se pueden mover libremente sin supervisión humana. En BBR no se construyen modelos complejos y abstractos del entorno; en su lugar, los robots operan en el mundo real y muchos de sus comportamientos son reactivos, si bien también pueden existir estados internos que proporcionen motivaciones al robot, o una memoria a corto plazo. Pese a esta asunción de contextualización (situatedness) del robot, suele ser aconsejable usar simulaciones en la implementación preliminar de los comportamientos, si bien también es necesario probar posteriormente el funcionamiento en robots reales. El cerebro de un robot con arquitectura BBR está constituido por un conjunto de comportamientos básicos, el repertorio de comportamientos, y su construcción suele realizarse a través de un proceso de dos etapas: en primer lugar, se deben definir o evolucionar de alguna manera los comportamientos individuales; y, una vez realizada la etapa anterior, se debe diseñar un sistema que seleccione que comportamiento o comportamientos usar en una determinada situación. A medida que aumenta la complejidad de la aplicación, crece también la importancia del diseño de un mecanismo de organización adecuado. En los siguientes apartados analizaremos aspectos relacionados con cada una de las dos etapas referidas. 4.3. Generación de comportamientos Cualquier robot con arquitectura BBR debe contar con comportamientos fundamentales para la supervivencia, como por ejemplo los que le lleven a evitar daños en su estructura, y a mantener un nivel de energía suficiente para su operación. Así mismo puede ser importante, especialmente en robots de mayor tamaño, incorporar comportamientos que eviten dañar a las personas, incluso por encima de dañarse el robot mismo. En cierto sentido, la arquitectura BBR trata con comportamientos relacionados con las leyes de la Robótica de Isaac Asimov [45]. Antes de diseñar un comportamiento es necesario elegir un marco general de implementación, o filosofía de diseño. Existe una gran variedad de posibilidades en cuanto a métodos y modelos para esta implementación, aunque en la práctica la elección se suele realizar entre ciertos tipos de métodos o herramientas, en función de la orientación de la arquitectura o filosofía elegida. 4.3.1. Comportamientos cableados Un modelo muy sencillo para la generación de comportamientos es el seguido por los Vehículos de Braitenberg [46], criaturas artificiales construidas mediante un mapeo 27 Capítulo 2. Arquitecturas y comportamientos También es posible combinar alguna de las arquitecturas anteriores: en [77] se combinan aspectos de arquitecturas de selección distribuidas y centralizadas, para explicar el funcionamiento del ganglio basal como un componente importante en la arbitración o selección de comportamientos en animales vertebrados. En la figura 2.13 podemos ver un modelo conceptual del sistema de selección propuesto para el ganglio basal, para un ejemplo de control de recursos motores compartidas por 3 comportamientos o sistemas de comandos, denominados “canales” en la imagen. Observamos como cada uno de estos canales genera señales excitadoras(gris claro) e inhibidoras (gris oscuro) hacia los recursos motores y el elemento central de arbitraje -el ganglio basal-, el cual genera a su vez nuevas señales de inhibición o excitación hacia los canales de forma que, finalmente, se selecciona un único canal o comportamiento para la ejecución de las acciones motoras. Este mismo esquema podría adaptarse a métodos de combinación emergente de comportamientos eliminando el paso final de inhibición de los “perdedores” y permitiendo una aportación de cada uno de ellos proporcional al nivel de la señal enviada desde el elemento central. Función de utilidad Un aspecto clave en las arquitecturas de selección exclusiva presentadas es establecer un criterio o medida que determine la fuerza excitadora o inhibidora de cada uno de los comportamientos intervinientes en la selección. Para ello se puede acudir al concepto de Utilidad [78]. La Utilidad nos proporciona un medio de sopesar el resultado de diferentes situaciones, comparando unas con otras, para decidir finalmente la acción a tomar. Von Neumann y Morgenstein demostraron que, bajo ciertas condiciones [79], existe siempre una función de utilidad que nos permite mapear los miembros cide un conjunto de posibles resultados a un valor numérico u(ci), la utilidad de Ci, que cumple las siguientes condiciones: 1. u(c1)> u(c2)si y solo sí la persona o el criterio prefiere c1ac2. 2. ues una transformación afín, es decir: u(p·c1+ (1 −p)·c2) = p·u(c1) + (1 −p)·u(c2),(2.1) para cualquier valor de p∈[0,1]. Para que la función de utilidad exista, se deben de cumplir los siguientes axiomas: Axioma 1 Ordenación. Dados dos posibles resultados, c1yc2, un individuo puede decidir de forma consistente acerca de sus preferencias entre ambos, es decir, si prefiere c1ac2(c1> c2) ; si por el contrario prefiere c2ac1; o si la elección le resulta indiferente (c1c2). Axioma 2 Transitividad. Si c1≥c2yc2≥c3, se debe cumplir que c1≥c3. Axioma 3 Axioma de Arquímedes. Si c1≥c2≥c3,∃p∈[0,1] tal que pc1+ (1 −p)c3> c2y ∃q∈[0,1] tal que c2> qc1+ (1 −q)c3 34 4. Comportamientos Axioma 4 Independencia. Para todo c1, c2, c3,c1≥c2si y solo si pc1+(1 −p)c3> pc2+(1 −p)c3 ∀p∈[0,1]. Hay que destacar que no hay un único conjunto de preferencias válido para todas las personas ante un problema; ante una determinada situación, una persona podría preferir una consecuencia c1frente a otra c2, mientras que otra persona podría pensar al contrario. La función de utilidad lo que proporciona es una manera de sopesar las situaciones, comparándolas entre sí. En el caso de que exista cierta incertidumbre sobre las consecuencias que puedan derivarse de una situación se puede acudir al concepto de Utilidad esperada,U(c)de una consecuencia promedio c=p1c1+p2c2+.... +pncn donde pk, la probabilidad de una consecuencia ckse obtiene a partir de: U(c) = X k pku(ck),(2.2) Esto, unido a los axiomas anteriores, nos permitiría estimar una utilidad esperada de una consecuencia mixta,cmque incluyese las probabilidades de las diferentes consecuencias ante una situación. En la organización de comportamientos basada en utilidad, a cada comportamiento del repertorio, Bi, se le asigna una función de utilidad Ui, dependiente de ciertas variables de estado del robot. Estas variables pueden estar relacionadas con las lecturas de los sensores —se les denomina variables externas, s—; variables físicas internas, p, como pudiera ser el nivel de energía del robot; y variables abstractas internas, x, que serían las equivalentes a las hormonas en los sistemas biológicos: Ui=Ui(s1, ...sne, p1, ...pnp, x1, ...xni)(2.3) Aunque ne,npynidenotarían el número total de variables de cada tipo, no es indispensable que la función de utilidad de cada comportamiento incluya todas las variables: solo aquellas que resultan relevantes en la medida de la utilidad del comportamiento. En este método se suele establecer una división de comportamientos en dos categorías: comportamientos de Tarea, que están orientados a acercarse al objetivo del robot; y comportamientos auxiliares, que no modifican la eficiencia del robot hacia su tarea, pero son indispensables para su funcionamiento. A cada comportamiento se le asocia una variable de tiempo de comportamiento, ti. Esta variable se pone a 0 cuando un comportamiento se activa, permite medir el tiempo que permanece activado éste, y afecta a la función de utilidad a través de las variables abstractas internas . En intervalos regulares de tiempo se estiman las funciones de utilidad de los diferentes comportamientos, y se selecciona el comportamiento con mayor valor de utilidad. El aspecto clave de este método se centra en la elección de la función de las variables asociadas al comportamiento y de la forma de la función de utilidad. Para ello se suelen usar a menudo aproximaciones polinómicas, donde los parámetros se obtienen mediante técnicas de computación evolutiva [80,81] como los algoritmos genéticos de los que se hablará en el capítulo 3. Cuando los comportamientos básicos se ordenan según una jerarquía o un comportamiento incluye varios posibles sub-comportamientos, se realiza una comparación de valores de utilidad a cada nivel, empezando por los niveles superiores o más abstractos. 35 Capítulo 2. Arquitecturas y comportamientos En la arquitectura que propondremos en el capítulo 5 consideraremos el uso de funciones de utilidad para medir la bondad de la operación del robot en la ejecución de los diferentes comportamientos, especialmente en lo relacionado con la incorporación de nuevos conocimientos a través de la experiencia. Sin embargo no se considera una selección única de un comportamiento dominante ya que tales tipos de comportamiento tendrían demasiada complejidad y serían muy difíciles de diseñar. 4.5.2. Combinación de Comportamientos A menudo no basta con seleccionar uno de entre varios comportamientos, sino que es necesario considerar a los comportamientos básicos como los cimientos de comportamientos compuestos más complejos en el mismo dominio. Para generar estos comportamientos compuestos es necesario aplicar algún tipo de operador de combinación con propiedades definidas, y que nos permita obtener la salida deseada. Dos de los operadores más empleados son la combinación directa de comportamientos básicos, y la combinación temporal de los mismos. Combinación directa de comportamientos (figura 2.14.a). Consiste en aplicar una función de combinación a las salidas de un subconjunto de comportamientos escogido del repertorio en un instante determinado. Por ejemplo, cuando las salidas de los comportamientos son vectores de dirección y velocidad relacionados con la navegación del robot, se puede realizar una suma ponderada de dichos vectores para obtener un vector que sería la salida del comportamiento de alto nivel equivalente [10]. La elección de los comportamientos a agregar suele ser de tipo intuitiva, aunque también sería posible —aunque más complejo— considerar inicialmente todos los posibles comportamientos del repertorio, y ajustar su peso o influencia de forma forma adaptativa, mediante diversas técnicas como Algoritmos Genéticos (GA) [82], lógica difusa [8] [83], ANNs, o CBR [84]. Combinación temporal de comportamientos [85]. A menudo la consecución de un determinado objetivo conlleva la realización secuencial de varios sub-objetivos asociados a comportamientos simples o combinaciones directas de estos, de forma que para conseguir el objetivo global se debe realizar una combinación temporal apropiada de dichos comportamientos (figura 2.14.b). La transición de un comportamiento a otro —o a una combinación directa de varios— se produce cuando se cumplen unas determinadas condiciones, que deben ser percibidas o identificadas por el agente. Una vez establecidas las condiciones que determinan la activación de un comportamiento simple o compuesto, se puede construir un módulo de selección mediante diversos métodos, como por ejemplo una máquina de estados finitos(FSM). Estas condiciones pueden venir dadas por diversos medios: RL [86] [87] [88]; por una base CBR con aprendizaje por demostración [89];mezclando los dos métodos anteriores, a través de una función de ”confianza“ en la actividad de los comportamientos, adaptada a través de un sistema CBR [90]; o aprendidas por una ANN [91] [92]. Aunque estas son las bases de organización de comportamientos a través de combinaciones, existen diversos problemas que es necesario resolver. No siempre están claros las condiciones que indican los comportamientos a activar en cada momentos; ni 36 4. Comportamientos (a) (b) (c) Figura 2.14: Combinación de comportamientos directa (a), temporal simple (b), y temporal-directa (c) los comportamientos específicos a combinar o la función de composición de las salidas de los comportamientos escogidos. Muchos de estos aspectos dependerán, en todo caso, de las herramientas y métodos empleados para implementar los comportamientos y los módulos de arbitración. 4.5.3. Otros métodos Además de los métodos indicados en los apartados anteriores, existen otros métodos de organización de comportamientos en la literatura que mezclan o combinan los indicadores en las secciones anteriores. La mayoría de ellos se identifican con arquitecturas específicas, como las redes de activación [93], o la arquitectura DAMN (Distributed Architecture for Mobile Navigation) [94]. En muchos de los métodos, se debe especificar la arquitectura de organización de comportamientos ”a mano“, lo cual hace la tarea especialmente compleja al tener que lidiar generalmente con entornos no-estructurados en los que resulta complicado hacer predicciones. Además, suele ser especialmente difícil estimar la relevancia de algunos comportamientos —sobre todo de forma cuantitativa—, en particular aquellos comportamientos que no están directamente relacionados con el objetivo del robot. Por último, la codificación manual de comportamientos se aleja bastante del modelo biológico-psicológico que se puede encontrar en la naturaleza, en el que el aprendizaje y la adaptación cumplen un papel fundamental. En este sentido es más apropiado acudir al aprendizaje, por medio de algoritmos evolutivos o de sistemas expertos adaptables mediante la experiencia. Este enfoque, defendido por algunas de las más novedosas teorías acerca de la inteligencia humana, tal como veremos en el capítulo 3, es el que predominará en el diseño de comportamientos dentro de la arquitectura de control/inteligencia que proponemos en la presente tesis. 37 Capítulo 2. Arquitecturas y comportamientos 38 3 Inteligencia y Aprendizaje “Se mide la inteligencia de un individuo por la cantidad de incertidumbre que es capaz de soportar Emmanuel Kant (1724-1804) Filósofo ” 1. Inteligencia Humana e Inteligencia Artificial: evolución histórica y estado de la Técnica Como ya hemos comentado en capítulos anteriores, si queremos desarrollar una arquitectura de IA aplicable a la Robótica, es indispensable partir de un buen modelo que describa el funcionamiento, estructura, y características de la Inteligencia Humana, en la que nos queremos apoyar para nuestro diseño. Nos interesa en particular una descripción de la Inteligencia Humana de tipo conceptual: no es tan importante —además de que complicaría la tarea en gran medida— imitar a la perfección los componentes biológicos que constituyen el cerebro humano, soporte de nuestra inteligencia, si bien es verdad que de la observación de muchos de estos comportamientos biológicos se pueden obtener interesantes conclusiones para la realización de nuestro modelo de IA (no obstante, más adelante se hablará de la vertiente conexionista de la IA, y de las redes neuronales artificiales o ANN). 1.1. Pioneros de la IA Mil años antes de Cristo, antiguos filósofos griegos, chinos, e indios ya estudiaban el desarrollo de métodos de razonamiento mecánico o deducción formal. Pero no fue hasta el siglo IV a.C. cuando Aristóteles, a través de su Lógica Deductiva y el concepto de Silogismos [95], realizó la primera investigación sistemática acerca de los principios del razonamiento válido o correcto. Aristóteles, además, destacó ya el papel de la memoria y de la experiencia o aprendizaje en el desarrollo de la inteligencia: de como las percepciones y acciones de las personas quedan impresas en la memoria [96], y son exploradas durante los procesos cognitivos, de manera que pueden ser recuperadas a través de relaciones de similitud, contraste, o contigüidad [97]. Esta visión de la inteligencia, y en particular el papel que juega la memoria en el proceso, está muy 39 Capítulo 3. Inteligencia y Aprendizaje relacionada con la propuesta en el modelo que seguiremos como referencia en esta Tesis, como veremos en apartados posteriores. En el año 1.315 Ramon Llull expresó, en su Ars Magna la idea de que el razonamiento podía implementarse de manera artificial en un artefacto mecánico con el que poder mostrar las verdades de la fe cristiana de una manera tan clara que no hubiese lugar a discusión. Inspirado en los trabajos de Roger Bacon, Llull pretendía construir una máquina que demostrase que los dogmas de la fe cristiana eran correctos y una tesis, en forma de libro, que pusiera sobre la mesa los errores que cometían los infieles, sin dejar lugar a ningún tipo de incertidumbre. El Ars Magna establece una teoría formal del conocimiento, y al mismo tiempo una mecanización formal del mismo, dando soporte físico u operativo a la lógica aristotélica. Por este motivo se le considera uno de los precursores del razonamiento automático, ya entendido como procedimiento mecánico que razona por sí mismo [98]. Figura 3.1: Ars Magna: árbol del conocimiento [99] En el siglo XVII Gottfried Leibniz, fuertemente influenciado por la obra de Llull, postula la posibilidad de que las maquinas puedan generar ideas automáticamente, es decir, por sí mismas [100]. Según su punto de vista, el pensamiento se reduce a la realización de cálculos, por lo que propone construir un lenguaje simbólico y formal, la característica universal (Characteristica Universalis), capaz de expresar sin ambigüedad todos los pensamientos humanos. Este lenguaje guiaría el razonamiento de filósofos y científicos, que podrían reducir sus investigaciones y discusiones a una traslación de sus enunciados o problemas a dicho lenguaje simbólico —codificación del pensamiento—, seguido de una aplicación de cálculos matemáticos sobre los mismos, que llevaría a la solución correcta. Leibniz escribió el compendio de su teoría en su tesis, De Arte Combinatoria [101]. Aunque la concepción de la mente humana como una calculadora o computadora parece superada hoy día, sus conceptos de codificación de experiencias y conocimientos son un aspecto clave —y aún no resuelto— en las más modernas teorías sobre la inteligencia. De esta misma época, destacamos también los trabajos del filósofo Thomas Hobbes, en su concepción del hombre como máquina; y de Blaise Pascal en el diseño y construcción de calculadoras mecánicas. En la segunda mitad del siglo XIX y primera del XX, científicos y matemáticos como Charles 40 1. Inteligencia Humana e Inteligencia Artificial Babbage, Ada Lovelace, o George Boole lograron romper, a través del estudio de la lógica matemática, las barreras que impedían una realización plausible y tangible de la Inteligencia Artificial. El matemático David Hilbert planteó a la comunidad científica de las décadas de 1920-1930, la necesidad de responder a una cuestión fundamental: “¿Puede el razonamiento matemático ser formalizado?” [102]. En respuesta a esta pregunta Gödel, con su Teorema de Incompletitud, estableció los límites de lo que la lógica matemática era capaz de lograr; y Turing y Church, con su Test de Turing y Calculo Lambda respectivamente, establecieron que, dentro de estos límites, cualquier tipo de razonamiento matemático podía ser mecanizado o plasmado de forma artificial [103] [104]. Para Turing, la conciencia y el pensamiento se identifican con estados de Figura 3.2: Test de Turing [105] un sistema, definidos principalmente por su papel en la generación de nuevos estados y salidas en el sistema. Por primera vez se admitía completamente la certeza de que un dispositivo mecánico, a través del manejo de un lenguaje simbólico binario, pudiese imitar cualquier proceso de deducción matemática. Estos descubrimientos marcaron un hito en la historia de la IA e hicieron soñar a los científicos con la posibilidad de desarrollar máquinas pensantes [106]. En las siguientes décadas se empezarían a construir máquinas cada vez mas avanzadas, con capacidades para realizar operaciones complejas de cálculo matemático, aplicables a multitud de áreas de la sociedad humana. Es en 1956 cuando, en la famosa Conferencia de Darmouth, John McCarthy acuña el término Inteligencia Artificial, entendido como “la ciencia e ingeniería de hacer máquinas inteligentes”. En la actualidad, la IA se suele definir como el “estudio y diseño de agentes inteligentes”, entendiendo por agentes inteligentes, a aquellos sistemas capaces de percibir y obtener información de su entorno, y realizar acciones basadas en esta información, con objeto de maximizar la probabilidad de éxito en la realización de una determinada tarea o función [107]. 41 Capítulo 3. Inteligencia y Aprendizaje 1.2. Funcionalismo De cualquier forma, la mayoría de las teorías que hemos ido mencionando establecen un paralelismo entre el cerebro humano y los computadores; es una teoría de la mente denominada Funcionalismo [108]. Esta visión de la inteligencia, aparecida en la segunda mitad del siglo XX, considera que los estados mentales se identifican por su rol funcional o relación causal con otros estados mentales, entradas sensoriales, y salidas conductuales. Por ello, se podrían implementar a través de estados físicos en diferentes tipos de criaturas o sistemas como por ejemplo, computadores o robots, siempre y cuando estos sistemas implementen las funciones apropiadas. Desde este punto de vista, el cerebro no sería mas que un computador que maneja otra simbología distinta de la binaria, y ejecuta algoritmos aún no conocidos totalmente por los investigadores. Si esto fuese así, y dada la potencia creciente de cálculo de los computadores, en muy poco tiempo sería posible que las máquinas superasen al ser humano en inteligencia [109]; dentro de la IA esta visión es la que se denomina también de Inteligencia Artificial Fuerte. El problema es si este concepto de cálculo algorítmico es realmente —y únicamente— lo que determina la inteligencia y el pensamiento humano, y parece ser que no es así. Se han planteado muchas objeciones a la visión Funcionalista de la inteligencia [107]. Algunas de ellas son de naturaleza filosófica o subjetiva: la identificación del pensamiento con al alma; el temor ante la posibilidad de que puedan existir seres superiores a los humanos; predicciones de lo que una máquina “nunca será capaz de hacer”, muchas de las cuales han sido refutadas en la actualidad; supuestos sentidos extrasensoriales de los seres humanos; necesidad de una creatividad;...Aunque la gran mayoría no suponen objeciones importantes a la teoría hay, sin embargo, algunas que si han puesto seriamente en duda las bases del Funcionalismo: Objeciones matemáticas. El teorema de incompletitud de Gödel apela a la existencia de límites a la capacidad de un sistema computador basado en lógica para responder ante cualquier tipo de problema o cuestión. Ante esto, Turing responde que los seres humanos también son propensos a cometer errores e incapaces de realizar cierto tipo de tareas, pero no tiene en cuenta que llega un momento en que los humanos somos capaces de resolver problemas que parecían imposibles en el pasado. Informalidad del comportamiento. Todo sistema gobernado por leyes es predecible y, por tanto, no es realmente inteligente. Turing replica que con el tiempo, el comportamiento de las máquinas podría llegar a ser tan complejo que sería muy complicado de predecir. Sin embargo, si se conoce en profundidad la programación algorítmica de la máquina si que sería posible establecer al menos probabilidades de observar un determinado comportamiento dado una situación o información manejada por el sistema artificial. Naturaleza biológica del cerebro, en especial, comportamiento analógico del funcionamiento de la neuronas, las unidades fundamentales que componen el cerebro humano. Turing admite esta importante diferencia con respecto a la lógica binaria de las máquinas pero defiende que, dada la creciente potencia de los computadores, el comportamiento analógico de los sistemas nerviosos humanos podría llegar a ser simulado por una máquina. Sin embargo, Turing no tiene en cuenta que en la actividad cerebral humana las neuronas son capaces de realizar 42 1. Inteligencia Humana e Inteligencia Artificial “solo” unas 200 operaciones por segundo [110], mientras que hay gran cantidad de actividades que deben ser resueltas en medio segundo o incluso menos tiempo. Es verdad que el cerebro humano se asemejaría mas a una red de computadores paralelos, que a su vez realizan ciertas actividades de forma secuencial, en vez de a un solo computador muy rápido; pero aún así, el argumento se caería por la “regla de los 100 pasos” [111]: no importa cuantos computadores paralelos se conecten entre sí, ya que estos, funcionando con lógica de Turing, no podrían ser capaces de realizar la mayoría de procesos considerados mas simples en el ser humano. Necesidad de Consciencia o Entendimiento. Para que un sistema o entidad sea considerada como inteligente, no solo basta con que sea capaz de resolver problemas o demostrar comportamientos considerados como inteligentes; es necesario que el sistema sea consciente de lo que está realizando, y comprenda la forma de resolver ese problema. Esta objeción fue presentada por Searle en su “Experimento de la Habitación China” [112]; y por Block, con su ”Argumento de la Nación China“ [113]. Ante esta objeción, Turing arguye la imposibilidad filosófica de saber, a través únicamente de la observación de un comportamiento considerado como inteligente, si al agente —incluido una persona— es consciente de dicho comportamiento inteligente. Esta objeción parece una de las más débilmente contestadas y constituye, en gran medida, la base de la teoría de inteligencia que pretendemos trasladar a la IA. De esta forma, se intuye que la computación algorítmica (la IA fuerte) no parece ser la clave de la inteligencia humana, y probablemente, tampoco lo será nunca para la IA. 1.3. Conductismo (inteligencia) Otra importante corriente en el campo de teoría de la Inteligencia, aparecida en la primera mitad del siglo XX, es la denominada Conductismo [114]. De acuerdo con esta escuela de pensamiento, el comportamiento de los seres humanos (y en general de cualquier animal) se explica a través de sus inclinaciones conductuales, es decir sus tendencias a comportarse de cierta manera, según su naturaleza, y en respuesta a la aparición de determinados estímulos. La inteligencia no se explicaría a través de estados mentales, o procesos internos, sino a través de la observación de comportamientos considerados como inteligentes, en la medida que resuelven problemas o implementan tareas. or tanto interesa más replicar los resultados de lo inteligencia que como funciona en realidad ésta. Esta corriente, englobada dentro de la conocida como Inteligencia Artificial Tradicional (GOFAI, Good Old Fashioned IA), representa la información de forma simbólica y la manipula mediante una serie de reglas orientadas a la resolución de un determinado problema en particular, sea mover a un robot a través de una fábrica, reconocer la escritura humana, o localizar rostros en una imagen. Tiene por tanto importantes puntos en común con el Funcionalismo, ya que defiende la implementación de IA mediante algoritmos ejecutados en potentes computadoras. Y cae, por tanto, en las mismas ”debilidades“ ya que, al ignorar el funcionamiento intrínseco de los procesos cognitivos en el cerebro humano, descarta la presencia de importantes características atribuidas a la inteligencia humana, como la creatividad, la capacidad de generalización, 43 Capítulo 3. Inteligencia y Aprendizaje Figura 3.6: Ejemplo de reglas de lógica difusa expertos. De la misma manera, en esta técnica es posible fusionar distintos expertos, cada uno especializado en un problema o área, de forma que se consiga expandir el dominio de aplicación de los problemas sin necesidad de recurrir a un experto con un dominio muy amplio de varios campos o a un nivel muy abstracto, lo cual resultaría mucho mas complicado que trabajar con sistemas enfocados a un dominio mas preciso y reducido. Un aspecto clave para el buen desempeño de este tipo de sistemas es la definición o extracción de reglas de los expertos humanos, algo que depende no solo de las capacidades del experto, sino también de la complejidad del problema. Por otra parte, puede ser muy costoso en tiempo y esfuerzo ajustar y probar las reglas hasta que el sistema diseñado logre un buen desempeño1. En este sentido, existen actualmente sistemas de lógica difusa adaptativos que, apoyándose en otros tipos de técnicas o métodos como las ANN, permiten encontrar nuevas reglas o adaptar y mejorar las existentes a partir del procesamiento de los datos de entrada y la observación de los resultados. 1.5.4. Marcos de representación del Conocimiento (Frame-based) Los sistemas expertos basados en Reglas de Decisión y Redes Bayesianas representan el conocimiento mediante reglas de uno u otro tipo, pero esta no es la única representación posible: Minsky [131] propuso una representación de conocimiento basada en marcos. Un marco permite representar un concepto mediante un conjunto de atributos (slots), con unos valores asociados, o los procedimientos necesarios para calcularlos. En contraste con los métodos basados en reglas, esta representación evita que la información se disperse por toda la base de conocimientos, acelerando la búsqueda de soluciones. El concepto es similar al de los objetos en la programación orientada a objetos: los marcos contienen todos los atributos que los describen, así como los métodos necesarios para gestionarlos. Además, y de la misma manera que en programación orientada a objetos, distinguimos entre marcos de clase, que representan un concepto o grupo de objetos similares, e instancias de clase, que se refieren a un objeto particular dentro de la clase. El nivel de descomposición de un problema en marcos depende del problema en cuestión a resolver y de las indicaciones del experto, pero como los marcos admiten herencia, es posible establecer diferentes niveles de abstracción. La interrelación entre 1Como ejemplo, el metro de la ciudad japonesa de Sendai se controla con un sistema que utiliza 54 reglas de lógica difusa, pero los ingenieros que lo diseñaron tardaron varios años en ajustar el sistema hasta lograr un funcionamiento correcto 50 1. Inteligencia Humana e Inteligencia Artificial los marcos puede establecerse a partir de la generalización, que relacionaría una superclase más general con sus subclases (como por ejemplo, la clase ”coche“ como parte de la clase ”vehículo“); agregación, por el que las subclases son componentes de una superclase que representa un todo (la subclase ”rueda“ como parte de la clase ”coche“); o la asociación, que describe una relación semántica entre dos clases independientes (por ejemplo, una persona puede ser dueña de tres instancias de las clases ”coche“, ”perro“, y ”casa“; aunque estas clases son independientes, se relacionan a través de ese concepto de posesión). Figura 3.7: Ejemplos de clases en un sistema basado en marcos [132] Pese a que conceptualmente este tipo de sistemas presenta aspectos muy interesantes para una teoría de inteligencia, al igual que los niveles de abstracción entre conceptos, también presentan algunos inconvenientes. A menudo es muy difícil diferenciar las propiedades esenciales de los objetos de las accidentales, por lo que suele ser complicado construir conceptos compuestos que presenten herencia múltiple. No obstante, los sistemas expertos mas actuales combinan tanto marcos como reglas, usando reglas para la evaluación de la información contenida en marcos; para ello se usan claúsulas de búsqueda de patrones. A diferencia de los sistemas basados en reglas, aquí las reglas juegan un papel auxiliar. 1.5.5. Computación Evolutiva La Computación Evolutiva es otra aproximación a la IA basada en la realización de modelos computacionales tomados de la selección natural y la genética. No en vano, la inteligencia define también la capacidad de un sistema para adaptar su comportamiento a un entorno abierto y cambiante. La evolución está relacionada con la habilidad de una población para sobrevivir y reproducirse en un entorno, pero también con la habilidad de un organismo para anticipar cambios en dicho entorno y adaptarse a los mismos. Esta cualidad, denominada aptitud evolutiva (evolutionary fitness), es lo que se trata de optimizar en la Naturaleza. En una población, el cruce de dos individuos con mayor aptitud evolutiva tiene mayor probabilidad de obtener un individuo con alta aptitud evolutiva; y como estos individuos son los que tienden a sobrevivir, la población evoluciona hacia la existencia de dicha aptitud. Pero si las condiciones del entorno cambian, favoreciendo otra aptitud distinta, la población evolucionará con el tiempo hacia esta nueva aptitud. Las principales técnicas de la computación evolutiva 51 Capítulo 3. Inteligencia y Aprendizaje son los algoritmos genéticos, las estrategias evolutivas, y la programación genética, que simulan la evolución mediante procesos de selección, mutación, y reproducción. Los algoritmos genéticos (GA) [133] manipulan cromosomas artificiales —en realidad, cadenas de dígitos binarios— mediante operaciones como selección, cruce, o mutación. Para ello, realizan una serie de etapas que permiten moverse de una población de cromosomas artificiales a otra distinta. Dos aspectos básicos para la resolución de un problema mediante GAs, son i) la forma en que se codifica el problema; y ii) cómo se evalúa. Para la codificación cada cromosoma está compuesto por genes, generalmente binarios. En cuanto a la evaluación, se define una función de aptitud de un cromosoma en la resolución de un problema; esta aptitud determina las bases de selección de los cromosomas durante la fase de reproducción. En la reproducción se utilizan los operadores de cruce para intercambiar partes de dos cromosomas; y de mutación, para modificar el valor de un gen en una posición aleatoria. Este proceso se realiza de forma iterativa, siendo cada iteración una generación de la población. Tras un cierto número de iteraciones se espera obtener una población de cromosomas con gran aptitud. En un problema real se suele usar una población de miles de cromosomas en un proceso de 50 a 500 generaciones, hasta obtener una solución casi óptima. Para estudiar la evolución de la población se suelen emplear gráficas de rendimiento, que representan la aptitud media de la población. Las estrategias evolutivas [134] suelen estar enfocadas a la resolución de problemas de optimización en ingeniería. Se basan en la introducción de cambios aleatorios imitando las mutaciones naturales. En su versión mas simple, se aplican mutaciones normalmente distribuidas con media cero y una desviación predefinida, en cada rango de variación de las variables. En cada generación se calcula la solución obtenida con respecto a la población original; si la solución con los parámetros mutados mejora la de los parámetros originales, estos son reemplazados. Este proceso continúa hasta encontrar una solución satisfactorio o ejecutar un determinado número de generaciones. Una ventaja de este método respecto del anterior, es que no es necesario codificar el problema, es decir establecer una representación del mismo adecuada a la manipulación de los algoritmos evolutivos. La programación genética [135] tiene como objetivo hacer que las computadoras solucionen problemas sin ser programadas explícitamente para ello. Esta tećnica se considera una extensión de los GA, pero el resultado final no es una representación codificada de un problema, sino un programa que resuelve ese problema. Para ello se manipulan los programas aplicando operadores genéticos, lo que hace necesario que los programas en si mismos se puedan representar como datos manipulables; esto se consigue utilizando programas en lenguaje LISP, que tiene una estructura muy orientada a símbolos, y capacidad para automodificarse y escribir nuevos programas. Los elementos básicos de un programa LISP —átomos y listas— se pueden representar en estructuras de árbol, lo cual permite separar los elementos en ramas, sobre los que aplicar los operadores genéticos de cruce o mutación. Sin embargo, estas técnicas no han obtenido grandes resultados en problemas complejos, que necesiten programas de gran tamaño. 52 2. El proceso de Aprendizaje Las técnicas de computación evolutiva parecen mas orientadas a la resolución de problemas concretos más que a un marco de inteligencia artificial general. Sin embargo, puede ser interesante incluirlas como parte de esquema más complejos como en el caso de las soluciones híbridas, especialmente para la resolución de aspectos concretos que no presenten excesiva complejidad. 1.5.6. Razonamiento basado en casos (CBR) El razonamiento basado en casos(CBR) [136] es otra aproximación de la IA a la resolución de problemas a través del aprendizaje. En vez de apoyarse en un conocimiento general en el dominio del problema, o buscar correspondencias en las relaciones generales entre los descriptores del problema y las soluciones, CBR utiliza conocimientos específicos obtenidos a partir de la experimentación de diversas situaciones concretas de dicho problema y las soluciones empleadas para ellas. La idea es poder resolver problemas nuevos a partir de situaciones semejantes experimentadas y resueltas, adaptando las soluciones a las nuevas circunstancias. Este tipo de sistemas son capaces, además, de mantener un aprendizaje incremental y continuado a lo largo del tiempo añadiendo soluciones ante nuevas experiencias, optimizando las ya existentes, y mejorando, en suma, su rendimiento a medida que continúa ejecutándose. La operación de un sistema CBR se realiza a través de un ciclo CBR, que implica operaciones de: i) recuperación de experiencias almacenadas parecidas a la que se presenta en el momento actual; ii) reutilización de la información y el conocimiento recuperado para resolver el problema actual; iii) evaluación de la corrección en la solución alcanzada; y iv) almacenamiento de la nueva experiencia en la base de información del sistema. Cualquier sistema CBR se define a través de un modelo de funcionamiento o procesado de este ciclo CBR: y de una estructura de tareas y métodos para la realización del razonamiento basado en la información almacenada a través de los casos. Aunque CBR nació como una herramienta enfocada a la resolución de problemas en un dominio concreto, su estructura , características, y funcionamiento parecen muy apropiadas para utilizarla como componente básico de un modelo y arquitectura de IA; aspectos como el aprendizaje continuo a través de la experiencia; la resolución de problemas por analogía; o la capacidad para representar información a diferentes niveles de abstracción se ajustan a las características supuestamente presentes en la inteligencia humana. Por este motivo, hemos considerado este paradigma como la base para el modelo de IA que propondremos en esta Tesis. En el capítulo 4 se analizará con mayor profundidad los aspectos fundamentales de CBR, aspectos que deberemos considerar a la hora de implementar los niveles reactivos de la arquitectura propuesta, que constituyen la base de nuestro trabajo. 2. El proceso de Aprendizaje Tan importante como el concepto o modelo de inteligencia es el proceso de como surge y se desarrolla tal inteligencia. El proceso de aprendizaje es fundamental en el desarrollo de la inteligencia humana y, consecuentemente, se supone que ha de tener también un papel fundamental en el desarrollo de las IA. Existen gran cantidad de Teorías de Aprendizaje que intentan describir como se realiza este proceso, tanto 53 Capítulo 3. Inteligencia y Aprendizaje en humanos como en otros animales, así como su impacto en el desarrollo de la inteligencia. La mayoría de ellas están muy interrelacionadas con algunas de las teorías sobre la inteligencia que hemos visto en el apartado 1 de este capítulo. Se distinguen principalmente tres perspectivas con respecto a las teorías sobre el aprendizaje: Conductismo,Cognitivismo, y Constructivismo. 2.1. Conductismo (aprendizaje) El Conductismo, como teoría sobre el aprendizaje [137], está íntimamente relacionada con su teoría homónima en el campo de la inteligencia. Según esta teoría, el aprendizaje es resultado de ejercer un condicionamiento sobre un sujeto que está adquiriendo un nuevo comportamiento, mediante la aplicación de una recompensa o un castigo, que incrementan o decrementan, respectivamente, la probabilidad de ocurrencia de ese comportamiento en presencia de estímulos o circunstancias similares. Según esta concepción, no se necesita un entendimiento del proceso de aprendizaje, más allá de una asociación entre un estimula de entrada y una respuesta de salida. Muchos métodos de IA, tales como las ANN, los algoritmos genéticosGA, o los sistemas expertos, se basan o aplican un aprendizaje reforzado. Una explicación más detallada acerca del aprendizaje reforzado en la IA se puede consultar en [138]. 2.2. Cognitivismo El Cognitivismo [139] o Procesamiento Cognitivo de la Información —Cognitive Information Process (CIP)— se inspira en el desarrollo de computadoras con una arquitectura de procesamiento estricto tipo ”entrada-procesado-salida“. Según las teorías cognitivas, el conocimiento está compuesto por construcciones simbólicas mentales en el cerebro de los individuos, y el aprendizaje se basa en trasladar estas representaciones simbólicas a la memoria, para que allí puedan ser procesadas. El aprendizaje, en el Cognitivismo, se centra más en asimilar una solución particular a un problema particular, que en adquirir ciertas habilidades que harían posible, no solo resolver dicho problema, sino un conjunto de problemas de características similares. En este modelo de aprendizaje, se programarían algoritmos específicos en potentes computadoras, que no tendrían ninguna capacidad de adaptación mas allá de las posibles variaciones programadas. 2.3. Constructivismo Para el Constructivismo [140], el aprendizaje es un proceso activo, en el que los aprendices construyen nuevas ideas o conceptos, a partir de su experiencia y conocimiento pasado y actual. El aprendiz toma un papel activo en la selección y transformación de la información, construye hipótesis y toma decisiones, apoyado en un modelo mental o estructura cognitiva. Esta teoría incluye muchos conceptos y características deseables en un modelo de inteligencia, como la flexibilidad en los conceptos a aprender; la asimilación de los mismos a través de la experiencia; la adaptación ante diferencias entre los conocimientos adquiridos y nuevas situaciones; y un cierto grado de autonomía respecto del instructor o programador, en el proceso de aprendizaje. Sin embargo, muchas de estas características (como se toma una decisión, 54 3. El modelo de Inteligencia como Memoria Jerárquica Temporal (HTM) como se selecciona y codifica la información, como se modela una experiencia,..) no están definidas con precisión, por lo que queda mucho trabajo de investigación por delante para plasmar este modelo en el campo de la IA. 2.4. Otros modelos de inteligencia y teorías de aprendizaje Finalmente, algunas de las últimas teorías acerca de la inteligencia humana y el proceso de aprendizaje, se alimentan de los mejores aspectos e ideas de los que hemos analizado en las secciones anteriores, de forma que unos puedan resolver las debilidades y carencias de otros, hasta llegar al mejor rendimiento posible. Esto no nos debe sorprender, ya que los sistemas de IA con mayor éxito son, en la actualidad, Sistemas Híbridos [115] [141], los cuales combinan muchas de las tecnologías anteriormente indicadas. Una de estas teorías, que ha causado un gran impacto especialmente en el campo de la IA, es la enunciada por Jeff Hawkins en [1], y su modelo derivado llamado Memoria Jerárquica Temporal(HTM), propuesto por Hawkins y George en [37]. En realidad, la mayoría de los aspectos que integran el modelo de Hawkins no son conceptos nuevos en los campos de IA o Neurociencia; ya existían como fragmentos diseminados aquí y allí, como parte de diferentes interpretaciones de la inteligencia y el aprendizaje. Quizás el principal mérito de Hawkins ha sido agruparlos en un marco común. El modelo HTM se tratará en mayor profundidad en la siguiente sección, ya que este trabajo se centra en la implementación de algunos aspectos de este modelo aplicados a un robot cuadrúpedo orientado a través de la visión. 3. El modelo de Inteligencia como Memoria Jerárquica Temporal (HTM) El modelo de Memoria Jerárquica Temporal HTM [37] es un modelo de aprendizaje computacional desarrollado por Jeff Hawkins y Dileep George, que intenta modelar algunas de las propiedades algorítmicas y estructurales del neocortex en forma de redes con una estructura similar a la de las redes Bayesianas [142]. La idea principal del modelo HTM es que el cerebro humano no actúa como un procesador o una red de procesadores distribuidos, ejecutando programas que permiten obtener una respuesta ante un conjunto de entradas; ni el aprendizaje consiste en escribir un conjunto de instrucciones suficientemente amplio como para tener respuesta ante cualquier situación posible. En lugar de esto, y de acuerdo al modelo HTM, el cerebro humano se parece mas a un sistema de memorias que almacena, de forma distribuida entre sus diferentes componentes, información relacionada con las experiencias vividas por el individuo en el pasado. Desde este punto de vista, la inteligencia estaría directamente relacionada con la abundancia y riqueza de las experiencias disfrutadas, y con la capacidad de asimilar nuevas experiencias de una forma útil, que permitiese responder a experiencias similares futuras o adaptar los conocimientos almacenados a experiencias distintas. 3.1. Organización jerárquica de la memoria Según el modelo HTM, una posible modelo de cerebro artificial, estaría organizada como un árbol jerárquico e interconectado de módulos idénticos en estructura y 55 Capítulo 3. Inteligencia y Aprendizaje funcionalidad, cada uno de los cuales implementaría una funcionalidad común de aprendizaje y memoria —o parte de ella—, de manera similar a como hacen las diferentes áreas y sub-áreas especializadas del cerebro humano [143]. Los módulos de las capas inferiores manejan conceptos muy sencillos, incrementando la abstracción y complejidad de estos conceptos a medida que ascendemos en la jerarquía. Los módulos inferiores recibirían su información, en principio, de entradas sensoriales, y proporcionarían los conceptos mas simples a los módulos de su capa inmediatamente superior, los cuales combinarían estos conceptos para formar otros cada vez mas elaborados a medida que la información fluye hacia las capas más altas. Existen además gran cantidad de conexiones de realimentación entre los módulos de las diferentes capas, como ocurre con las neuronas de un área en el cerebro humano (figura 3.8). Figura 3.8: Organización jerárquica HTM [1] Estas conexiones de realimentación permiten reforzar y consolidar los conceptos identificados inicialmente por los diferentes módulos al afrontar una determinada situación, a medida que dichos conceptos son confirmados por los componentes de las capas superiores. Así, por ejemplo al encontrarnos a una persona y verle la cara, las capas de los niveles inferiores de la jerarquía obtienen información de las áreas visuales que les permiten reconocer la existencia de unos ojos, una nariz, o una boca; esta información sería reconocida en módulos o áreas de la capa superior como una cara; y esa cara en particular se pasaría como información a otras áreas superiores relacionadas con el almacenamiento de ”rostros conocidos“, para acabar identificando a esa persona como tu jefe, tu esposa, un actor famoso...o alguien que se parece a alguno de estas personas! Esta organización jerárquica y distribuida presenta ventajas incuestionables, como por ejemplo que cualquier fragmento de información, a cualquier nivel de la jerarquía, en cuanto a complejidad o abstracción del concepto, se puede compartir con cualquier otro módulo de la jerarquía para participar en la creación de nuevos conceptos o consolidar los ya almacenados. Además, y tal como hemos visto en el ejemplo anterior, esta estrategia presenta una gran ventaja respecto a la generalización del conocimiento, evitando largas etapas de aprendizaje pero permitiendo, al mismo 56 3. El modelo de Inteligencia como Memoria Jerárquica Temporal (HTM) tiempo, la incorporación de nueva información incluso en la fase operativa del sistema. Adicionalmente, se consigue una gran eficiencia en cuanto al almacenamiento de información, en cuanto se evita la redundancia de datos. Con respecto a la implementación de los módulos o componentes de la arquitectura HTM, y aunque en la propuesta original se modelaban como redes similares a las Bayesianas [37], creemos que éste no es un aspecto esencial del modelo, sino más bien una cuestión de implementación. Otras aproximaciones de la IA, como las ANN, los sistemas de lógica difusa, un sistema CBR, o incluso una combinación de estos, u otros paradigmas de la IA en la forma de un sistema híbrido, podrían modelar los diferentes módulos de la jerarquía, si bien se deberían realizar los cambios apropiados en cuanto al proceso de aprendizaje y el procesamiento de la respuesta inteligente, con respecto a la propuesta original. 3.2. Importancia del tiempo: predicciones Otro aspecto clave de la teoría de inteligencia de Hawkins, y que está presente en su modelo HTM, es el reconocimiento de la importancia de los aspectos temporales en los procesos cognitivos y de aprendizaje. En cada objeto que vemos, se reconoce fácilmente una estructura jerárquica espacial, al considerarlo compuesto de objetos o elementos mas simples y pequeños, los cuales a su vez están formados por otros elementos más simples, y así sucesivamente. Este modelo del mundo y de sus objetos, como una estructura nido, ya ha sido ampliamente utilizado en muchos sistemas de IA, especialmente los relacionados con el reconocimiento de patrones, y puede ser trasladado al modelo propuesto, considerando que los módulos inferiores se ocuparían de las partes menores y mas simples —conceptualmente hablando— de la jerarquía espacial, subiendo hacia elementos cada vez mas complejos manejados en capas mas altas. Así un determinado patrón espacial, a cualquier nivel de complejidad, sería el resultado de una coincidencia en la activación de estados o respuestas implantados en diversos módulos de la jerarquía en un determinado instante de tiempo. Por ejemplo, la memoria de cómo es nuestra casa no se almacena en una única región, si no en una jerarquía de regiones que representa en sí la estructura jerárquica de nuestra casa, las relaciones entre sus componentes y el reconocimiento de los mismos (a alto y a bajo nivel). Pero es precisamente la inclusión de una estructura jerárquica temporal la que da su importancia real a este modelo HTM. Los módulos, en cualquier capa de la jerarquía, establecen también una correlación temporal entre los patrones que se encuentran cercanos, no solamente a nivel espacial, como los que representan una nariz y una boca en una cara, sino también a nivel temporal, como varias notas musicales consecutivas, que se reconocen como una o mas posibles secuencias de ocurrencia. A un nivel superior de la jerarquía, estas secuencias se identifican como conceptos más complejos, que a su vez se agrupan con otros conceptos de complejidad similar, en nuevas secuencias tanto temporales como espaciales que, de nuevo, se identifican con conceptos aún mas complejos o globales, y así sucesivamente. Por ejemplo, los órganos sensoriales auditivos reconocen una nota a partir de unas variaciones temporales de presión en el tímpano; módulos de niveles superiores podrían reconocer varias notas consecutivas como parte de un riff y, finalmente, módulos todavía más arriba en la jerarquía reconocerían este riff como parte de una melodía o canción. Se llega así a una conclusión que 57 Capítulo 3. Inteligencia y Aprendizaje puede sorprender en principio, y es que todo lo que nos rodea en el mundo posee una estructura jerárquica dual, tanto en el tiempo, como en el espacio, no importa cuales sean los sentido implicados en captar la información principal asociada a ese concepto; a veces, no obstante, es complicado identificar alguno de estos componentes, el espacial o el temporal, en el mismo. La principal consecuencia de esta inclusión de una componente de correlación temporal asociada al modelo de inteligencia, es la capacidad de predecir una respuesta en los niveles mas bajos, algo que resulta fundamental para evaluar las consecuencia de las posibles acciones que se van a llevar a cabo, y evaluar los posibles desconocimientos o éxitos en la reconstrucción mental de los conceptos a partir de unos patrones de entrada, mediante la comparación de la respuesta esperada con la realmente obtenida. Por tanto es la capacidad de predicción, y no la observación de un comportamiento, la verdadera expresión de la inteligencia, si bien el comportamiento va a ser, generalmente, el resultado o respuesta ante una predicción. La predicción va a ser posible gracias al aprendizaje que nos permitirá almacenar, a lo largo del tiempo, patrones de experiencia en el ámbito del tiempo y el espacio, organizados en una estructura jerárquica, y distribuidos a lo largo de los diferentes elementos de las sucesivas capas que forman la estructura del cerebro humano o de la arquitectura de IA que se proponga. Por último, la Creatividad, otra de las características típicas atribuidas a la inteligencia humana, estaría relacionada con la capacidad de inferir predicciones para una situación no experimentada ni almacenada en la memoria, por analogía o reconstrucción a partir de datos en principio diferentes y no relacionados. 3.3. Funciones básicas del modelo de inteligencia/aprendizaje HTM Con respecto al proceso de aprendizaje, el aprendizaje necesario para el desarrollo de la inteligencia supone, según el modelo HTM, al menos cuatro pasos o funcionalidades básicas [1] que pueden ser implementadas de muy diversas maneras: 1. Identificar conceptos en el mundo. Relacionado con la forma en que la información se reconoce, codifica y almacena en la base de conocimientos. Los principales aspectos a resolver en esta etapa, están relacionados con la forma en que la entrada primaria se particiona y sub-muestrea para ser distribuida entre los diferentes módulos y niveles de la jerarquía; como se representa la información en cada módulo, teniendo en cuenta el nivel de la jerarquía donde está integrado el mismo; y cuanta información se debe proporcionar para un buen aprendizaje. 2. Inferir conocimiento de las nuevas entradas. En un proceso similar al reconocimiento de patrones, las nuevas entradas se deben mapear respecto a las almacenadas, o al menos se debe medir su similitud para establecer cuales de las almacenadas son las mas afines, y así decidir una determinada respuesta en función del conocimiento almacenado. Los patrones muy distintos a los existentes y considerados como nuevos, se deberán añadir a la base de conocimiento, haciéndola cada vez más completa. En teoría, si la representación interna del conocimiento se ha establecido de forma acertada, no será necesario 58 3. El modelo de Inteligencia como Memoria Jerárquica Temporal (HTM) añadir muchos nuevos patrones, ya que la información o conceptos subyacentes serán equivalentes a la mayoría de las entradas. 3. Realizar predicciones. Para ello se combinarían las entradas actuales y las más recientes para ajustarse a una secuencia similar que estuviese ya almacenada en la base de conocimiento, de manera que pudiese predecirse cuales son las siguientes entradas más probables, y realizar las acciones o tomar las respuestas adecuadas en consecuencia. Este mecanismo se realizaría en paralelo en cada módulo de un nivel de la jerarquía, y sus salidas alimentarían a los módulos de las capas inmediatamente superiores para donde se realizarían acciones similares. Además, las salidas o respuestas de cada módulo también se realimentarían hacia los módulos de las capas inferiores, permitiendo comparar las predicciones en las respuestas con las entradas reales que se produzcan a continuación. Si las predicciones resultan ser acertadas, se tomarán las acciones asociadas y se reforzarán los conceptos relacionados; en caso contrario, se ascenderá en la jerarquía hacia un concepto más abstracto que permita ajustar la predicción con la nueva situación. Esto nos permitiría, por ejemplo, reconocer un rostro con algún tipo de alteración como un golpe u ojo morado, a pesar de que no hayamos visto nunca ese rostro en dicha situación. La combinación de ciertos elementos reconocibles a bajo nivel —el resto de elementos de la cara que si se reconocen— junto con la generalización en niveles más altos —el cambio de aspecto que sufre cualquier rostro cuando tiene un golpe u ojo morado— nos permitiría reconocer ese rostro como perteneciente a alguien familiar. Estas diferencias entre las predicciones y las entradas reales se incorporarían a la base de conocimientos en los niveles adecuados —ya almacenaríamos el aspecto que tiene ese familiar en particular cuando sufre un golpe en el ojo—. 4. Dirigir los comportamientos. Finalmente, las predicciones obtenidas como resultado del proceso de reconocimiento cognitivo, nos permiten realizar ciertas acciones relacionadas con la respuesta predicha. Algunas de estas acciones estarán directamente relacionadas con los estados alcanzados en algún módulo o módulos de forma que estos módulos, además de enviar su salida hacia arriba y hacia abajo en la jerarquía, activarán la ejecución de determinadas acciones o comportamientos, en sentido ”sensar“ →actuar. Una combinación de varias de estas acciones imbricadas en los módulos podría dar lugar a comportamientos conjuntos o emergentes realmente complejos. No obstante, parece razonable que estos comportamientos directos o reactivos deberían combinarse con comportamientos de alto nivel de tipo deliberativo, que modulasen los de bajo nivel, dando mas peso a unos u otros según las circunstancias. En los siguientes capítulos de esta Tesis se explorará en mas detalle este subnivel dentro del modelo de memoria/aprendizaje, mediante la propuesta de un marco similar de aprendizaje reactivo basado en la experiencia, que se implementará en un robot AIBO, y que se probará en un entorno controlado. El modelo HTM ha sido utilizado en varias aplicaciones del campo de la inteligencia artificial, como Vitamin-D, para la detección y reconocimiento de personas en imágenes de vídeo; el sistema de análisis energético, EDSA, para la detección de eventos en yacimientos petrolíferos [144]; diversas aplicaciones de la empresa aeronáutica Lockheed 59 Capítulo 4. CBR: razonamiento basado en Casos base CBR a lo largo del tiempo. Si bien esta segunda opción puede ser interesante de considerar, la estructura jerárquica lleva inherente en si misma las diferentes escalas de tiempo a considerar a la hora de resolver un problema. Los módulos de nivel inferior pueden realizar consultas CBR ante cada instancia de valores de los parámetros sensoriales y motores; sin embargo, es posible construir módulos de nivel superior que vayan coleccionando, no solo los patrones de salida de módulos asociados a diferentes áreas sensoriales/motoras, sino a secuencias de patrones procedentes de un mismo módulo, e incluso a varias secuencias de patrones, cada una de ellas correspondientes a módulos distintos. Finalmente, las capas inferiores a nivel reactivo absorberán la dinámica y cinemática del robot, así como los errores sistemáticos de los sensores, a través del aprendizaje. Así, sustituyendo estas capas, se podría reutilizar el resto de la jerarquía cuando se cambie de robot, de una forma ágil e intuitiva. 3. Organización de la información: Bases del conocimiento Un aspecto fundamental para el uso correcto de CBR como herramienta de aprendizaje, se centra en la adquisición de la información necesaria representativa de la experiencia que se desea aprender, así como en la codificación adecuada de dicha información. Richter [199] considera una organización de los sistemas basada en módulos, que manejan el conocimiento o la parte del conocimiento asociada a la tarea o subtarea que es gestionada por ese módulo en particular. A su vez, este conocimiento se clasifica y divide en elementos de conocimiento a los que llama Recipientes de Conocimiento(Knowledge Containers), que contribuyen a un proceso de aplicación del conocimiento completo, y que pueden gestionarse a través de diferentes mecanismos. Cada recipiente de conocimiento, al contener únicamente partes o aspectos particulares del conocimiento total del módulo y sistema, no es capaz de resolver individualmente la subtarea asociada al módulo que los contiene; necesita para ello de la contribución del resto de elementos de conocimiento. Otro aspecto clave en este modelo de conocimiento es la forma de expresar los conocimientos en sí mismos, a través de estructuras de datos elementales y operaciones de inferencia que manipulan dichas estructuras. Estas estructuras de datos no tienen porqué identificarse directamente con los recipientes de conocimiento (suelen ser más sencillas en ese caso), pero si que forman parte de estos. De hecho, una misma estructura u operación puede formar parte de del conocimiento encerrado en más de un recipiente de conocimiento y, habitualmente, un recipiente de conoclimiento englobará a varias estructuras de datos o/y operaciones, como base de conocimiento. La representación y caracterización adecuada de los recipientes de conocimiento que constituyen parte de un módulo asociado al conocimiento o aprendizaje de una subtarea, constituyen aspectos clave en el diseño del sistema de conocimiento. La compilación se ocupa de estos aspectos. con el objeto de disponer de un conocimiento completo de todo lo relacionado con la tarea o subtarea a resolver. 66 3. Organización de la información: Bases del conocimiento 3.1. Compilación en sistemas CBR Para CBR, la organización de la información es importante, pero no tan crucial como en otros sistemas expertos. En CBR es posible “funcionar“ con un conjunto de información incompleto, y con representaciones del conocimiento incompletas o no ”perfectas“. Aún en estas condiciones el sistema CBR funcionará, puede que no de una forma totalmente correcta, o de la manera más eficiente, pero lo hará, a diferencia de otros sistemas expertos ”tradicionales“ en las que estas carencias e inconcreciones suelen provocar un comportamiento absolutamente incorrecto del sistema. Una ventaja adicional de CBR es su capacidad para modificar sobre la marcha el contenido de la base de conocimientos, añadiendo nueva información o modificando la ya existente mediante nuevos procesos de compilación en los que se trasvasa información entre los diferentes recipientes de conocimiento. Esto ocurre, por ejemplo, cuando se evalúa la eficiencia de un caso y se determina que dicho caso no es tan interesante. 3.2. Recipientes de conocimiento en CBR En [199] se identifican 4 clases de recipiente de conocimiento que, a través de su contenido e interacción, comprimen la información necesaria para el buen funcionamiento de un módulo CBR. Estas 4 clases son: i)el Vocabulario; ii)la medida de similitud o distancia; iii)la base de casos; y iv)los métodos de transformación de soluciones, que dan lugar a una adaptación del conocimiento existente en la base CBR. Figura 4.2: Recipientes de conocimiento CBR y su interacción [199] A su vez, cada recipiente de conocimiento se puede subdividir en diferentes sub-recipientes, más relacionados con las estructuras de datos y algoritmos que implementan el soporte de conocimiento; por ejemplo, las distintas partes de un problema pueden estar asociadas a diferentes bases de casos; se pueden emplear diversas funciones de distancia para la medida de similitud de distintos elementos; pueden utilizarse varios métodos de adaptación de soluciones, etc... Como se ve en la figura 4.2, todos los recipientes dependen unos de otros para la representación de la información completa que nos permita llegar a una solución. Por este motivo, una decisión inadecuada en la integración o caracterización de un recipiente puede afectar al resto, dando lugar a soluciones que no sean totalmente correctas, a una menor eficiencia 67 Capítulo 4. CBR: razonamiento basado en Casos en la resolución de los problemas, a una menor competencia general del sistema, o a dificultar el mantenimiento del mismo. Un aspecto clave de la forma de organización de la información en un sistema CBR; será la capacidad de transferir información de unos recipientes a otros, para buscar la representación del conocimiento más eficiente y sencilla en cada uno de ellos. Esto nos permite construir sistemas CBR que inicialmente tienen un bajo desempeño, pero que mejoran su calidad a medida que se refina su estructura a lo largo del tiempo. 3.2.1. El Vocabulario Cuando hablamos de Vocabulario en el campo del conocimiento, nos referimos a las estructuras de datos y elementos de éstas que se emplean para representar aspectos básicos del conocimiento. Por ejemplo, en CBR se suele usar una representación atributo/valor, aunque se pueden utilizar otras representaciones, como una taxonomía o una jerarquía, a partir de los atributos; y también es posible añadir predicados. En la representación atributo/valor, tan importante es escoger los atributos adecuados, como su semántica o forma de expresión. Esta elección de los atributos es una de las tareas más complejas e importantes en las fases iniciales del diseño de un sistema CBR, ya que nada nos garantiza que la elección realizada contenga el número y tipo adecuado de atributos que definen el conocimiento necesario para resolver un problema en particular. A este proceso de elección los atributos se le conoce como indexación (indexación). Algunos autores [200] [171] han propuesto guías para esta labor que, aunque orientadas al campo del vocabulario, pueden ser aplicables a otros campos. A la hora de escoger cuales éstos índices o atributos para un caso CBR se debe tener en cuenta que: Los índices han de ser predictivos o deterministas. Deben refleje los aspectos fundamentales del problema a resolver Deben ser lo suficientemente abstractos, como para ampliarse en un futuro... ...pero lo suficientemente concreto como para ser reconocido como tal en una ocasión futura. El número de índices o atributos no debe ser muy grande, por motivos computacionales, ya que un número elevado de atributos implica un mayor tiempo de comparación entre el caso ofrecido y los almacenados, y por tanto mayor tardanza en la recuperación. Además, a mayor número de atributos por caso, mayor espacio de casos posibles para explicar el problema, con lo que se necesita más memoria y más tiempo para encontrar el caso más adecuado de entre la base. Hay que tener en cuenta que puede que la información elegida tenga cierta correlación convirtiendo alguno de los parámetros en redundantes. Por lo general se suelen establecer dos criterios para la elección de los atributos: Plenitud principal. Se consigue cuando todas las propiedades relevantes del módulo o tarea pueden ser formuladas. Si el conjunto de atributos escogido es incompleto, algunas propiedades o características relevantes para el problema no podrán representarse en el mismo, disminuyendo la corrección o eficiencia del sistema. Aún así, el sistema CBR será capaz de funcionar. 68 3. Organización de la información: Bases del conocimiento Eficiencia. Este aspecto está relacionado con la creación de atributos virtuales que expresan un conocimiento relevante para el problema que viene dado por una relación entre varios atributos, pero no por la inclusión individual de los mismos. Estos atributos virtuales permiten mejorar el comportamiento de la base de conocimiento. La forma más usual para escoger estos índices suele ser por medio de decisiones tomadas por un experto humano, que analiza el problema y determina cuales son los atributos más adecuados del mismo, de forma subjetiva. El problema es que la decisión puede no ser correcta u óptima y, en este sentido es adecuado apoyarse en análisis estadísticos y minería de datos para analizar la idoneidad de la elección. Existen también métodos alternativos automatizados para la elección de los atributos, como la indexación basada en listas de control(checklist-based indexing) [201] empleada en MEDIATOR yCHEF, y consistente en analizar el dominio y obtener las dimensiones o descriptores que demuestren gran influencia en la resolución del problema; cada caso sería indexado en función de los valores tomados con respecto a los atributos de esta lista. En CYRUS, la selección se realiza en función de las características que permiten diferenciar unos casos de otros. Otras técnicas se basan en el aprendizaje inductivo [202] para identificar aquellos atributos que sean predictivos, y que se emplearán como índices. Por último existen técnicas basadas en ”explicaciones” (explanation-based), que determinan atributos relevantes para cada caso, investigando cuales de ellos son predictivos [203]. Finalmente, es posible dividir los recipientes de conocimientos en partes o sub-recipientes, como por ejemplo atributos de recuperación útiles para la computación de similitudes entre casos de la base CBR; atributos de entrada, para crear reglas de conclusión, o de generación de nuevos conocimientos; o atributos de salida, que proporcionen información útil para el usuario para por ejemplo, depuración del comportamiento de la base de conocimientos. 3.2.2. La medida de Similitud o Semejanza. Utilidad La medida de similitud como recipiente de conocimiento, sim(q, p), tiene por objeto el “mapeo” de pares de descripciones de un problema para establecer un nivel de “parecido” entre los mismos. La similitud se obtiene como una función de medidas locales de similitud simien el dominio (o dominios) de los atributos A. sim(q, p) = f(simi(qi, pi)|i∈I)(4.1) En general, la función fsuele ser una suma lineal ponderada de las similitudes entre atributos locales de forma que la ecuación anterior queda: sim(q, p) = X(gi×simi(qi, pi)|1≤i≤n)(4.2) donde gies un conjunto de pesos con coeficientes reales no negativos (generalmente en [0,1] y normalizados de forma que Pgi= 1). Así, en el recipiente de conocimiento que es la medida de similitud, estamos considerando varios sub-recipientes, como son las medidas o funciones de similitud locales, gi; y la función de similitud global, f(en la ecuación (4.2), un sumatorio). E incluso dentro de estos sub-recipientes encontraríamos otros elementos, como los pesos 69 Capítulo 4. CBR: razonamiento basado en Casos asociados a las funciones de similitud locales. Nótese como el conocimiento asociado a las funciones de similitud locales pertenece más al dominio de conocimiento general del problema, mientras que la función de similitud global está mas orientada a la tarea y comprime aspectos de conocimiento relacionados con su utilidad para la tarea, y la relevancia de las similitudes locales en la resolución de la misma. Uno de los aspectos que consideraremos en capítulos posteriores, una vez hayamos planteado en detalle el problema a resolver, es como establecer las funciones y estructuras más adecuadas para la implementación tanto de las medidas de similitud locales, como una mediad de similitud global. En la elección de la medida de similitud global deberemos procurar siempre que se cumpla el siguiente axioma de monotonicidad: Axioma 5 Si sim(q, p)> sim(q, r)entonces debe existir al menos un i∈I(y, por tanto, algún atributo) que cumpla que sim(qi, pi)> sim(qi, ri)[204] Si este axioma falla en el problema planteado, esto significa, probablemente, que la descripción del problema no es correcta y, por tanto, no hay garantías de encontrar una solución adecuada. Por eso es clave organizar el sistema de forma que el vecino más cercano (atendiendo a la medida de semejanza) a un problema p, permita obtener de la base de casos la solución más útil para el problema. Stahl, en [205], introduce una nueva variable, la utilidad, como elemento de conocimiento que forma parte de la información almacenada en la base de casos. El concepto de utilidad tiene dos versiones, una relacional, y otra funcional. Si planteamos un problema (o caso de entrada a una base CBR), p, y tenemos dos posibles soluciones, s1ys2, en el espacio de soluciones del dominio de conocimiento, vamos a encontrar: Una relación de preferencia entre las soluciones,s1ys2,pref(s1, s2), que representa que, ante el problema p, es más útil la solución s1, que la s2(definición relacional de utilidad). Una función real u(p, s1), que determina un grado de utilidad de la solución s1asociada a p, dentro de una escala absoluta. Todas las posibles soluciones si tendrán un determinado valor de utilidad en esa escala para dicho caso (definición funcional de utilidad). Dependiendo del escenario de aplicación, la utilidad puede venir determinada por diferentes aspectos, como la corrección de las soluciones sugeridas; el grado de aplicabilidad o reutilización de las acciones o decisiones asociadas a esas soluciones; un grado de satisfacción del usuario del sistema; o una ganancia de información acerca del sistema para el usuario, a partir de las soluciones, o salidas. En CBR, en una primera aproximación, se puede identificar la función de utilidad con la medida de similitud, de forma que para un problema qy un caso (p, s), la ecuación sim(q, p) = u(q, s)se puede considerar válida. No obstante, en una aproximación más compleja y evolucionada, la medida de similitud incluirá, no solo el ”parecido” entre el problema presentado y cada uno de los casos almacenados, sino también la eficiencia de la solución asociada a dichos casos para la resolución del problema presentado. En este sentido, más adelante veremos como incluir el concepto de eficiencia de la solución en la fase de recuperación en la base CBR, y como dicho concepto está muy ligado a las características y condicionantes de la tarea a resolver por parte del módulo CBR. 70 3. Organización de la información: Bases del conocimiento 3.2.3. La base de casos El papel de esta base es contener las experiencias en el formato indicado por el vocabulario. Las experiencias se obtienen a partir de los casos almacenados en la base o de variaciones de los mismos. Entre los aspectos más importantes para el diseño de una ”buena” base de casos tenemos: Tratar de contener solo casos (p, s)para los que la utilidad de ses máxima o al menos la mejor posible. Esto significa que se deberían evaluar los casos almacenados tras la fase de adquisición o aprendizaje por experiencia realizada por el entrenador, a través de una función de utilidad/recompensa, y eliminar aquellos que no aporten ventajas reales. Almacenar el mayor número de casos posibles para aumentar la competencia del sistema. Obtener una base de casos de menor tamaño posible para disminuir el tiempo de búsqueda. Para ello, de nuevo, tendremos que estimar la eficiencia de los casos almacenados. 3.2.4. La transformación de la solución Este aspecto del conocimiento hace referencia a como el conocimiento obtenido a partir del vecino mas cercano, puede no ser suficiente para resolver el problema planteado, bien porque la medida de similitud no es la más adecuada, o porque la base de casos no contiene una solución mejor, y la obtenida no es suficientemente correcta. La adaptación de soluciones suele seguir una serie de reglas que son el componente principal de este recipiente de conocimiento Por tanto, el conjunto de problemas que puede resolver el sistema está determinado por los casos almacenados en la base sometidos a la aplicación de las reglas. Un problema es que la aplicación de las reglas no tiene porque dar lugar, necesariamente , a un aumento de la similitud original obtenida tras la consulta a la base CBR. De nuevo, en la transformación de las soluciones jugará un papel importante la medida de la eficiencia de las mismas en la resolución de la tarea asociada al módulo. 3.3. Adquisición y Trasvase de conocimiento entre recipientes En los apartados anteriores hemos visto como el conocimiento de un sistema experto, en nuestro caso, un sistema CBR, se va a organizar en la forma de diferentes recipientes de conocimiento que responden a distintas estructuras, representaciones, y relaciones. Teóricamente podrían existir recipientes de conocimiento “ideales” que, en sí mismos, y sin colaboración de otro tipo de recipientes comprimiesen todo el conocimiento necesario para el aprendizaje de una tarea. En el caso del vocabulario, el recipiente ideal e único estaría constituido, para cada descripción del problema, p, por un solo atributo virtual en el dominio de todas las soluciones, sol, y construido a partir de todos los atributos significativos del problema. Este atributo ideal cumpliría que s=sol(p)nos permitiría obtener la solución correcta, para cualquier problema p. 71 Capítulo 4. CBR: razonamiento basado en Casos Una medida de similitud ideal sería aquella que nos diese una similitud absoluta simideal(q, p) = 1 si el caso (p, s)nos permite obtener la mejor solución, s; y nos daría simideal(q, p) = 0 en caso contrario. Una base de casos ideal sería aquella que contuviese todos los casos posibles en el dominio del problema. Y la transformación de soluciones ideal sería aquella que pudiese ignorar completamente los casos, y construir una solución desde 0, simplemente aplicando las reglas de adaptación asociadas. Esto claro que estos recipientes de conocimiento ideales no existen, pero su simple proposición nos plantea la cuestión de como y cuando repartir el conocimiento del sistema a lo largo de los diferentes tipos de recipientes. Respecto al cuándo, se van a considerar generalmente dos momentos o etapas para establecer este reparto: antes de poner en marcha el sistema; y una vez el sistema está ejecutándose. En un sistema CBR se puede incrementar el conocimiento a lo largo de su ejecución, especialmente en lo que respecta al contenido de la base de casos, lo cual implica que no es necesario partir de un conocimiento inicial completo y comprendido del problema para poner en marcha el sistema. Esto es una gran ventaja respecto a los tradicionales sistemas de lógica programada, en los que el conocimiento será el codificado antes de la puesta en marcha del sistema, y permanecerá inmutable durante su funcionamiento. Será necesario, no obstante, antes de la puesta en marcha del sistema, resolver aspectos como la definición de los atributos a considerar, y la recogida de (algunas) muestras de los mismos; la elección de una medida de similitud adecuada; y el establecimiento de unas reglas de adaptación eficientes y operativas. Una buena elección en todos estos aspectos, permitirá aumentar la eficiencia del sistema, no solo la inicial, sino también la mejora que se logrará con la incorporación de nuevos conocimientos durante su funcionamiento. Para optimizar las características de los recipientes en cuanto a su aportación al conocimiento completo del problema, se puede optar por mejorar individualmente el conocimiento comprendido dentro de cada recipiente (y sub-recipiente) de conocimiento; o traspasar conocimiento entre los diferentes recipientes, dado el elevado grado de acoplamiento entre los mismos. Tanto en uno como en otro tipo de mejora, existen tanto técnicas basadas en intervención humana como por aprendizaje automático de máquina (machine learning). 3.3.1. Mejora de información en los recipientes individuales Vocabulario. Para mejorar o refinar los atributos que conforman los elementos básicos del conocimiento, se tratará de eliminar aquellos atributos redundantes o con dependencias funcionales, y añadir atributos virtuales útiles (lo cual conlleva a menudo la eliminación de los atributos desde los que se forman). La inclusión de atributos virtuales suele ser necesaria debido a fallos en el axioma de monotonicidad visto más arriba; este método es inductivo y bastante complejo en la actualidad, no existiendo demasiado progreso en cuanto a métodos automáticos para conseguirlo. Medida de Similitud. No hay métodos sistemáticos para determinar cuál es la mejor medida de similitud para un dominio concreto. Las principales 72 3. Organización de la información: Bases del conocimiento investigaciones se centran en determinar los pesos de la suma ponderada en la función global [206] [207]. En [208] podemos encontrar un estudio comparativo de medidas de similitud para dominios en el que los atributos del problema son categóricos. La elección de la medida de similitud está muy condicionada por el dominio del problema que se desea resolver, y necesita de la intervención de un experto. Es posible refinar algunos aspectos mediante estudios comparativos, aunque en todos ellos hay que tener en cuenta que el elevado acoplamiento de los recipientes de conocimiento puede dificultar la interpretación de los resultados. Base de Casos. Es conveniente tratar de eliminar aquellos casos que no contribuyan a la resolución del problema, aunque esto no es siempre obvio, ya que un caso que no sirve por ahora puede hacerlo en el futuro. Es importante establecer un baremo de calidad de cada caso en la base. Esta calidad se puede medir en relación a la competencia general del sistema [209] [210], o a una orientación utilitarista hacia el problema a resolver [211]. Este apartado está muy relacionado con la denominada fase de mantenimiento del proceso CBR En cuanto a la transformación de soluciones, no hay demasiados trabajos que estudien la mejora sistemática de las reglas de adaptación en el dominio CBR. En la práctica, se suelen emplear las técnicas estándar de los sistemas basados en reglas. Podemos ver algunas aplicaciones de estas técnicas a CBR en [212] [213] [214] y [215]. 3.3.2. Trasvase de información entre recipientes de conocimiento Es otro aspecto clave en la mejora de la información contenida en los recipientes. Nótese que un trasvase de información de un contenedor a otro no siempre supone que se elimine la información del contenedor original. Se recomienda el siguiente procedimiento de diseño del conocimiento de un sistema: 1. Comenzar con un vocabulario dado u obvio. 2. Establecer un conjunto de casos 3. Considerar una medida de similitud simple y/u obvia. 4. No utilizar, inicialmente, reglas de adaptación. A continuación se procedería a mejorar el sistema mediante técnicas de compilación horizontal y vertical: Compilación Vertical. Trasvase entre diferentes niveles de abstracción. En [216] se muestra un ejemplo de trasvase de conocimiento entre la base de casos y la transformación de las soluciones. Compilación Horizontal. Dentro del mismo nivel de lenguaje, buscar una formulación mas compacta. Se busca mejorar la eficiencia, el tamaño de la base, o su inteligibilidad. Por ejemplo, reemplazar características por variables, omitir detalles, o introducir nuevos niveles de abstracción. En CBR se podría, por ejemplo, añadir casos generalizados que engloben conjuntos de casos con soluciones similares [217], apoyándose en técnicas de clustering. 73 Capítulo 4. CBR: razonamiento basado en Casos Adicionalmente se puede mejorar el conocimiento de un recipiente apoyándose en el contenido en otro recipiente distinto, pero sin trasvase efectivo del mismo. Por ejemplo, se pueden optimizar las medidas de similitud a partir de las reglas de adaptación como en [218]. 4. Aspectos básicos de un sistema CBR A la hora de utilizar CBR para la resolución de cualquier tipo de problema, o para el modelado de algún sistema complejo, hay una serie de decisiones importantes que es necesario tomar, y pasos a seguir para el diseño e implementación de la estructura CBR. Los principales aspectos y elementos a tener en cuenta son: 1. Estructura y características del caso a considerar 2. Estructura u organización de la base de casos 3. Operaciones sobre la base CBR: el ciclo CBR A continuación realizaremos una breve introducción a estos aspectos. En capítulos posteriores profundizaremos sobre los mismos,indicando las decisiones tomadas para la implementación del modelo CBR empleado en nuestro sistema. 4.1. El caso CBR Un aspecto básico para el funcionamiento correcto del CBR es la descripción adecuada del problema que queremos resolver o, más bien, de las experiencias que hemos tenido con respecto a dicho problema, y que servirán de base para afrontar futuras experiencias expresadas en términos similares. Como hemos comentado anteriormente, las experiencias que constituyen la base de conocimiento del sistema se almacenan como una colección de casos. El concepto de caso entronca con el ”paquete de organización de memoria“ o MOP (Memory Organization Packet) de la teoría de Schank; un caso se puede definir como una unidad de conocimiento dentro de un contexto, que describe una determinada experiencia [219]. Un caso debe contener, al menos, un conjunto de atributos o parámetros que permitan describir adecuadamente el problema a resolver, y una solución que indique la respuesta a ejecutar ante esa instancia del problema, o permita clasificar/categorizar la misma (CASEY [177]). A menudo los casos suelen incluir también una métrica del grado de la eficiencia resultante, con respecto a un objetivo, al aplicar dicha solución (MEDIATOR [169]). De esta forma se espera solucionar nuevos problemas a partir de las soluciones existentes ante problemas parecidos, evaluar nuevas situaciones, y prevenir problemas que puedan surgir de aplicar la solución almacenada ante un problema parecido al actual. La forma exacta de representación de la información es muy variable, y abarca un amplio rango de formalismos típicos del campo de la Inteligencia Artificial, como por ejemplo reglas y redes semánticas, predicados, objetos o tramas (frames, [131]). Estas dos últimas representaciones son las mas usadas en la mayoría de los sistemas CBR actuales. Aparte de la propia información incluida en el caso, otro aspecto fundamental es la estructura final de dicha información dentro del caso, la cual estará muy ligada a 74 4. Aspectos básicos de un sistema CBR la estructura de la base de casos empleada para su almacenamiento y a los métodos utilizados para explorar dicha base a la búsqueda de la solución más adecuada a un nuevo problema. Esta elección a menudo depende de las características o dominio del conocimiento del problema a resolver. En [136] y [220], se propone una clasificación del caso, dependiendo de las características de la información que encierre, respecto al dominio del conocimiento al que pretende identificar: casos concretos, que representan experiencias concretas; o abstractos para episodios más generalizados. casos completos, que representan unidades de conocimiento separadas; o parciales, en el que la información de la experiencia está distribuida en varias sub-unidades. casos aislados entre si; o relacionados unos con otros. Podemos distinguir tres representaciones básicas del caso: i)plana; ii)jerárquica(estructurada); o iii)generalizada. Esta representación va a influir en la organización de los casos dentro de una base de casos. 4.1.1. Representación Plana En la representación plana, cada caso es entrada o fila de una tabla, donde cada columna se corresponde con un atributo del caso. Por tanto, cada caso se representa mediante un vector c= (a1, a2, ..an)∈D1×D2×... ×Dn, siendo Diel dominio del atributo en la posición i−sima. Cada atributo representaría una dimensión en el espacio multidimensional que representa al caso, y por ende a la experiencia. Desde este punto de vista, un caso se puede representar como un punto en el espacio n-dimensional, donde sus coordenadas vienen dadas por los valores particulares de sus atributos. En el caso de que el valor de algún atributo no se conozca, no es posible identificar esta posición, pero si un objeto n-dimensional que incluya el caso buscado, con todos los valores posibles para el atributo desconocido. La representación plana de una base de casos constituye la alternativa mas sencilla de implementación, con la ventaja de que siempre se va a obtener el caso más parecido dentro de la base, al realizarse una búsqueda exhaustiva en la fase de recuperación. Además, la incorporación de nuevos casos es muy simple: basta con incluir el caso como una nueva entrada al final de la tabla. Su principal inconveniente es el crecimiento exponencial en el tiempo de respuesta del sistema si el número de casos almacenados es muy elevado, al necesitar realizar un mayor número de comparaciones para encontrar el caso más cercano. Por otra parte, esta estructura no es capaz de capturar las dependencias y relaciones entre atributos, con lo que la similitud de casos no siempre se establece de la forma más adecuada. Por estos motivos, este tipo de representación no es la más aconsejable para problemas complejos con gran número de atributos. 4.1.2. Representación Estructurada o Jerárquica Para subsanar los problemas antes mencionados de la representación plana, Watson y Pereira [221] sugirieron en la división de un problema complejo en subproblemas más simples, algo realizable cuando no existe un alto grado de dependencia entre los 75 Capítulo 4. CBR: razonamiento basado en Casos grupo de casos, y el resto discrimina entre estos [236]. Se realiza una búsqueda de tipo árbol. Es una técnica interesante cuando hay algún atributo que es claramente más decisivo a la hora de caracterizar un caso. Inducción guiada por Conocimiento. Es una variante del anterior, en la que se identifican manualmente aquellos atributos que se piensa que pueden afectar a los atributos principales. Se suele emplear en conjunción con otras técnicas para acotar el conjunto inicial de casos y acelerar el proceso de búsqueda. Recuperación de plantillas. Consiste en recuperar todos aquellos casos que encajan dentro de unas ciertas restricciones; se suele combinar con otras técnicas como las de vecindad [227]. Recuperación guiada por adaptación. En este caso, no solo se tiene en cuenta la similitud entre el casos de entrada y el recuperado, si no la utilidad de éste último para resolver el problema [237]. En este sentido, en [210] se considera más útil un caso que se más fácil de adaptar combinando medidas locales y globales de adaptabilidad. Esta estrategia favorece la fase posterior de adaptación. otros métodos menos utilizados están basados en la medida de la competencia de los casos en una base organizada según la cobertura de los mismos respecto al domino del problema (recuperación basada en ’huella’ [238]); en el cumplimiento de unos compromisos en un subconjunto de índices del caso [239]; en una organización de los casos de la base en función de unas relaciones de orden [240]; o en la vecindad entre casos, considerando a estos como una red donde los casos están interconectados en función de su distancia respecto a un aspecto, para realizar la búsqueda del caso a recuperar solo entre casos vecinos (recuperación por ’pesca y disminución’ —fish-and-shrink— [241]). El método de vecindad es muy adecuado para dominios en los que predominan valores numéricos en los atributos, y los casos se pueden ver como puntos en un espacio [242]. Lo atributos simbólicos resultan más complicados de evaluar; para simplificar se suele buscar simplemente que tomen un valor exacto. En [242] se emplearon matrices de distancias para calcular las distancias entre valores simbólicos. A menudo, el proceso de recuperación se divide en varias sub-fases que implican algunos de los métodos indicada más arriba, en especial una primera fase de recuperación por vecindad, con objeto de limitar el número de posibles candidatos; y una segunda que tiene en cuenta una representación estructural o jerárquica de los casos recuperados en la primera fase. La recuperación propuesta en nuestro modelo toma aspectos de varias de las técnicas indicadas, combinándolas en pro de una operación más eficaz. Así, se partirá de una recuperación por búsqueda en árbol, que nos permitirá discriminar un escenario más concreto dentro de todos los posibles escenarios del problema para, posteriormente, aplicar una recuperación por plantillas que considere únicamente aquellas situaciones almacenadas con los mismos objetos presentes que el problema presentado. Finalmente, se acudirá a una búsqueda por vecindad en la que se compararán los atributos de los casos seleccionados para encontrar el caso almacenado más similar al problema propuesto. 82 5. Operación de un sistema CBR: El ciclo CBR 5.2. Medidas de Similitud Como se ha visto en el apartado anterior, una medida de similitud es necesaria para recuperar el caso más adecuado de la base de casos, y también como estimación, a priori, del rendimiento tras la fase de adaptación. Algunos autores prefieren utilizar el termino relevancia para definir a los casos escogidos, término que incluye, pero no se limita a la similitud. Las medidas de similitud se pueden dividir en dos tipos: ordinal ycardinal [243]. Las ordinales devuelven un orden de parecido del conjunto de casos respecto al caso de entrada; las cardinales devuelven un valor numérico para cada par de casos comparados, una puntuación, que puede utilizarse también para establecer un orden en el conjunto de casos. En las medidas cardinales no se considera la posibilidad de que dos casos sean incomparables, algo que es posible en el caso ordinal. 5.2.1. Similitud basada en distancia Es una medida de similitud típicamente usada en la representación plana, cuando los casos, cn, se representan mediante vectores de características, en los que todos ellos se representan mediante valores numéricos, y la recuperación de casos se realiza por vecindad. La distancia d(c1, c2)entre dos casos, c1yc2, vendría dada por la ecuación: d(c1, c2) = n X i=1 wi×di(c1ai, c2ai)(4.3) donde, di(c1ai, c2ai)es una distancia local entre los componentes aide ambos casos, ywiun peso a aplicar a dicha distancia local dentro del cómputo de la distancia global. Asimismo, la medida de similitud entre los mismos, sim(c1, c2), en un intervalo [0,1], vendría dada por: sim(c1, c2) = 1 1 + d(c1, c2)(4.4) Este concepto de similitud no siempre es el más apropiado: no tiene en cuenta las relaciones estructurales entre los casos; y aparecen problemas cuando alguno de los atributos del caso no tiene un valor definido. Esto se debe a que no siempre es adecuado considerar los casos como puntos en un espacio multidimensional; esto dependerá del dominio del problema y de la representación del mismo. Por ese motivo, los conceptos de ’recuperación del caso más ajustado’ y ’medida de similitud’ no siempre son sinónimos, aunque se puedan basar en las mismas técnicas. En [244], se diferencia el concepto de distancia de percepción, que se correspondería con el concepto clásico de distancia en la representación espacial, y el concepto de distancia juzgada, que sería una función de la anterior, y es la que debería permitir recuperar el caso más adecuado a otro en una base CBR. Una de las propiedades que distinguen a una distancia de otra es la inecuación triangular; en la distancia de percepción se cumple que d(A, C)≤ d(A, B) + d(A, C)) lo cual no tiene porqué cumplirse en la distancia juzgada. Si el cuarto axioma se cumple para una distancia d, y ésta es aditiva en cada línea recta del espacio de atributos, a dicha distancia se le llama distancia de Minkowski y cumple, para cada par de puntos A= (a1, ...an)yB= (b1...bn), la ecuación: 83 Capítulo 4. CBR: razonamiento basado en Casos d(A, B)=( n X i=1 |ai−bi|p)1 p(4.5) Otras técnica de medida de similitud, el modelo de contraste de características, proponen abandonar la representación en un espacio multidimensional de los casos, en favor de una representación basada en características binarias [245]. La similitud entre dos casos, AyBvendría medida por una función de sus características comunes y de sus características distintivas sim(A, B) = f(A∩B, A \B, B \A)). Esta función, siempre que satisfaga unas propiedades de monotonicidad e independencia [245], se podría representar mediante una función lineal de las características comunes y distintivas. Leake [246] añadió al concepto de similitud entre dos casos la adaptabilidad del nuevo caso respecto al antiguo. Ante una descripción incompleta del caso, se realiza un preproceso del mismo para establecer hipótesis sobre el posible valor a partir de los casos almacenados. Relacionado con el tema de la descripción incompleta de casos, en [247] se defiende una representación del caso a diferentes niveles de abstracción de manera que la similitud se comienza a medir a un alto nivel de abstracción, exigiendo un alto grado de coincidencia, que se irá relajando a medida que bajemos el nivel de abstracción del caso al añadir nuevos detalles y características. Esta representación reduce el número de casos en la base de casos, y aumenta la flexibilidad del sistema al ser capaces de reutilizar los niveles bajos de abstracción en varios de los niveles altos; sin embargo se debe incorporar un mayor conocimiento del problema para establecer las relaciones entre los diferentes niveles, lo que aconseja contar con la ayuda de un experto humano. 5.2.2. Similitud para representación estructurada de casos Muchos autores defiende una representación estructurada de los casos, criticando la incapacidad de la representación plana de capturar las características relevantes de un problema y, sobre todo, sus interrelaciones. Sin embargo la representación estructurada exige una reconsideración del concepto clásico de similitud. Frecuentemente se representa la información de los casos estructurados a través de grafos dirigidos, donde los nodos son conceptos, objetos o relaciones entre ellos, y las flechas permiten relacionar entre sí los nodos. Wang e Ishii [248] establecieron una medida de similitud para este tipo de grafos a partir de un mapeo uno-a-uno entre los nodos y flechas de dos casos distintos, estableciendo una medida de similitud local entre los mismos. La similitud entre dos grafos-casos se obtendría agregando las similitudes locales de sus elementos. El problema surge ante la necesidad de establecer correspondencias entre los nodos y flechas de uno y otro caso, lo cual es altamente ineficiente desde un punto de vista computacional, teniendo en cuenta que los casos pueden tener bastantes elementos, y pueden existir gran cantidad de casos almacenados en la base de casos. En [248] se intentó solucionar el problema mediante algoritmos genéticos con resultados eficientes, aunque no óptimos. En nuestro modelo se probaron algunas medidas de similitud ”clásicas” , como la distancia Euclidea, Manhattan, y Chebychev [249]. No se encontraron diferencias significativas en su comportamiento por lo que, atendiendo a experimentos pasados, y al proceso seguido de conceptualización de la información a través de una discretización, se decidió utilizar finalmente una distancia Manhattan para la búsqueda final por 84 5. Operación de un sistema CBR: El ciclo CBR vecindad, y una distancia Jaccard para el filtrado previo de casos según los objetos presentes en el escenario. Hay que tener en cuenta que no se realizó un estudio intensivo de la aplicación de cada una de las distancias, en el que se modificasen los atributos aplicados a cada caso, o los intervalos de discretización de los mismos. Sin embargo se programaron las estructuras adecuadas para permitir modificar la medida de similitud, y se introdujo la posibilidad de usar diferentes medidas de similitud a aplicar a atributos individuales o grupos de atributos del caso. En trabajos posteriores se espera explorar esta línea de investigación para analizar si se mejora el comportamiento de la recuperación de casos por similitud, aplicando dichas medidas. 5.3. Fase de Reutilización: Adaptación Tras haber obtenido el caso almacenado más parecido al caso de entrada, es necesario emplear el mismo para resolver el problema planteado. Si el caso devuelto coincide o es muy similar al de entrada, se puede aplicar directamente la solución propuesta para éste. En caso contrario será necesario adaptar la solución obtenida por el sistema para que sea aplicable al problema a resolver. La fase de adaptación se concentra principalmente en las discrepancias entre el caso de entrada y el recuperado; y en las porciones reutilizables del caso recuperado en el problema definido por el nuevo caso [136]. La adaptación se suele apoyar bastante más en el conocimiento general del dominio del problema que en el conocimiento específico contenido en el caso. Por ello los métodos específicos empleados para la adaptación en un determinado sistema CBR, pueden no ser válidos para sistemas distintos. Existe una gran variedad de técnicas de adaptación, pero básicamente se clasifican en tres grupos. La adaptación nula propone directamente la solución aportada en el caso devuelto, sin realizar ningún tipo de modificación en la misma [250]. Esta técnica es muy útil para sistemas que pudiendo ser más o menos complejos tienen soluciones simples. La familia de técnicas de adaptación estructural otransformacional [201] [183] reutiliza la solución asociada al caso devuelto, aplicando una serie de operadores transformacionales como borrado, adición, reemplazo,etc [250], o por medio de funciones de transformación dependientes de la calidad de las soluciones adaptadas [251]. Para ello es necesario tener un conocimiento experto acerca de como las diferencias entre las descripciones del problema afectan a la diferencia entre las soluciones. Por último los métodos de adaptación derivativa no almacenan solo casos, si no también los métodos que permitieron llegar a las soluciones de dichos casos. Ante un nuevo problema, simplemente se aplica el método asociado al caso más cercano para encontrar la nueva solución. Estas técnica solo se pueden emplear en aquellos casos en los que el dominio del problema está bien comprendido. Es posible combinar técnicas estructurales y derivativas para lograr mejores resultados [183]. El grado de adaptación necesario está muy relacionado también con la estructura y complejidad de la solución de los casos [250]. Por ejemplo, la existencia de interacción entre partes de la solución tiene un impacto importante en la complejidad de la adaptación ya que, de no existir dicha interacción, cada porción de la solución se puede tratar independientemente con lo que la adaptación será más sencilla. Otra posibilidad de adaptación se basa en la recuperación de más de un caso como posible solución, de manera que todos ellos puedan contribuir a una solución final 85 Capítulo 4. CBR: razonamiento basado en Casos adecuada [228], mediante diferentes técnicas, como la aproximación evolutiva [250] [252]. En nuestro modelo hemos considerado la recuperación del caso más similar únicamente. Una vez recuperado, se medirá si el caso es lo suficientemente similar al problema presentado a través del número de “saltos” en la representación discreta o conceptual del problema, lo que significaría un mayor o menor alejamiento en el concepto particular que representa un atributo o grupo de atributos del caso. El número de “saltos” considerado como límite que determina la necesidad de adaptación se obtendrá de forma heurística teniendo en cuenta el significado de los conceptos asociados a los diferentes atributos y objetos de los casos. En cuanto a la adaptación en sí, se realizará a través de la combinación de la respuesta asociada al caso obtenido, con la generación de un vector de movimiento a través de la técnicas de campos de potencial o PFA. 5.4. Fase de Revisión A menudo suele ocurrir que la solución generada en la fase de reutilización-adaptación no da los resultados esperados. En este caso, es necesario aprender de los fallos cometidos para mejorar el sistema, mediante una fase de Revisión. Esta fase suele sub-dividirse en otras dos, evaluación yreparación de fallos. En la fase de evaluación se determina la viabilidad de la solución adaptada para resolver el problema planteado por un nuevo caso. Esto se suele llevar a cabo fuera del ciclo CBR, ya que es necesario aplicar la nueva solución y las consecuencias de la misma pueden tardar algo de tiempo en aparecer. La evaluación de la nueva solución se pude realizar manualmente, mediante la intervención de un experto humano; automáticamente, mediante un algoritmo que simule el resultado de la aplicación de la nueva solución; o experimentalmente, observando el funcionamiento del sistema tras la incorporación de la nueva solución. Si se detectan errores en la solución adaptada, es importante ser capaces de determinar cuales fueron las causas de los mismos y, en función de éstas, realizar una nueva adaptación del caso para lograr una nueva solución que deberá ser evaluada. Para ello suele ser necesario tener conocimientos del dominio del problema, por lo que esta fase suele llevar el apoyo de un experto humano. En nuestro modelo se definirá, para cada comportamiento desarrollado, una función de utilidad o eficiencia, que determinará el grado de cumplimiento en la realización de los objetivos del comportamiento. Esta función incluirá aspectos relacionados con la suavidad en las acciones de movimiento del robot, y con la seguridad en su desplazamiento en el escenario de pruebas. 5.5. Fase de Retención: Aprendizaje La fase de retención la última fase del ciclo CBR y atañe a la incorporación de todos aquellos nuevos casos obtenidos tras la fase de adaptación, que han sido evaluados satisfactoriamente. Añadir un nuevo caso a la base de casos CBR implica enriquecer el conocimiento total del problema al añadir las experiencias almacenadas en el nuevo caso. La información que se añade a la base de casos representa el aprendizaje del 86 5. Operación de un sistema CBR: El ciclo CBR sistema acerca del problema que se intenta solucionar o ”comprender” mediante CBR. Esta información puede haber sido introducida ”a priori” por un operador humano o por observación directa de casos reales, en lo que se denomina un aprendizaje por observación, o puede incrementarse con la ejecución del sistema tras añadir un nuevo caso adaptado y evaluado positivamente; en este último caso se habla de aprendizaje por experiencia. El aprendizaje por observación [253] forma parte del desarrollo inicial de cualquier sistema que implementa el paradigma CBR, de forma similar a la fase de entrenamiento de las redes neuronales. Se basa en la introducción de un conjunto de casos iniciales dentro de la base de casos, que constituirán el conocimiento inicial con el que el sistema empezará a operar El aprendizaje por experiencia [160] permite aumentar gradualmente el conocimiento que posee el sistema al ir incorporando, mediante su funcionamiento normal, nuevas experiencias en la resolución de nuevos problemas. Para añadir un nuevo caso a la base CBR es necesario que el caso haya sido adaptado (de lo contrario ya existiría en la base) y su aplicación al dominio del problema haya sido valorada positivamente. En algunas ocasiones, un nuevo caso no será añadido a la base de casos, pero modificará la estructura de casos existentes o su valoración. Existen dos grande familias de métodos que implementan el esquema de aprendizaje por experiencia de un sistema CBR: Aprendizaje Positivo, que se realiza en caso de evaluación positiva del nuevo caso adaptado. En este caso, es necesario incorporar el nuevo caso a la base de casos, operación que tendrá mayor o menor complejidad según la estructura de casos y de base de casos considerada. Aprendizaje Negativo. Ocurre cuando la evaluación del caso adaptado (de su solución), es negativa. Es necesario averiguar si la causa de la valoración negativa es la recuperación de un caso inadecuado en el sistema, debido a que, a pesar de ser el más similar, no lo es lo suficiente (esto suele ocurrir cuando la base de casos no contiene los suficientes, a consecuencia de un entrenamiento escaso); o si el sistema no ha devuelto el caso más parecido al de entrada, algo más común en los sistemas y casos con representación jerárquica o estructurada. En este último caso puede ser necesario una re-organización de la estructura del caso y/o de la base de casos [254]. De cualquier forma, es necesario evitar que esta solución adaptada con evaluación negativa vuelva a aparecer en el sistema. Para ello, se puede almacenar el caso fallido en la base de casos, añadiendo una nueva etapa de filtrado de casos no deseados previa a la búsqueda (etapa de Anticipación); o almacenar el caso en otra base CBR exclusivamente dedicada a situaciones fallidas, de manera que, antes de buscar en la base asociada a la resolución del problema, se buscaría en esta para descartar el caso entrante como fallido [171]; o corregir el error mediante un procesamiento externo a la base CBR —por ejemplo, un experto humano— e incluir la solución en la base cuando se evalúe como correcta. En el modelo propuesto emplearemos la función de utilidad referida en el apartado anterior para evaluar la bondad del nuevo caso en cuanto a la consecución de los objetivos del comportamiento. Se considerará únicamente un aprendizaje positivo, por lo que el nuevo caso se incorporará a la base en caso de resultar eficiente; si el caso 87 Capítulo 4. CBR: razonamiento basado en Casos Figura 4.4: Descomposición de las fases y sub-fases CBR [136] 88 5. Operación de un sistema CBR: El ciclo CBR no es considerado adecuado, no se conservará ninguna información en este sentido del mismo. En el siguiente capítulo se tratarán con más detalle este y otros aspectos relacionados con la implementación concreta del sistema CBR utilizado en el desarrollo de comportamientos según el modelo que proponemos. 89 Capítulo 4. CBR: razonamiento basado en Casos 90 5 Arquitectura híbrida de aprendizaje de comportamientos robóticos basada en CBR: implementación de etapas reactivas “La clave de la Inteligencia Artificial ha sido siempre la representación Jeff Hawkins (1957-) Ingeniero ” 1. Introducción En este capítulo, y tras haber realizado en los capítulos anteriores una revisión de los aspectos pertinentes, presentamos la arquitectura propuesta para la implementación de comportamientos robóticos reactivos a bajo nivel, a través del aprendizaje por observación y experiencia. Para ello se describirán en detalle las diferentes características que tiene y los componentes que la integran, justificando las decisiones tomadas en cada caso. En ocasiones estas decisiones estarán relacionadas con las propias pruebas de funcionamiento, si bien la descripción de estas últimas se realizará en un capítulo posterior. Así mismo, se inscribirá la arquitectura propuesta dentro del marco global de arquitectura de inteligencia robótica inspirada en la teoría de inteligencia de Hawkins [1], en la cual ocupa los niveles mas bajos correspondientes a un horizonte reactivo de respuesta. 2. Modelo general de inteligencia robótica basada en la arquitectura HTM Tal como vimos en el capítulo 3, el modelo de inteligencia y aprendizaje humano propuesto por Hawkins constituye un buen punto de partida para tratar de establecer un modelo similar aplicable a la inteligencia robótica. Los puntos principales a considerar en nuestra arquitectura serían: capacidad para almacenar información que describa de forma adecuada las situaciones a las que se enfrenta un robot para resolver un problema. La 91 Capítulo 5. Arquitectura híbrida de aprendizaje basada en CBR la que su comportamiento es inmutable y predefinido, también es posible y deseable diseñar los comportamientos de bajo nivel a través de un proceso de aprendizaje. Para ello estableceremos un modelo de arquitectura ascendente —bottom-up— de diseño de comportamientos reactivos a través del aprendizaje. En esta arquitectura los comportamientos reactivos de bajo nivel se implementarán mediante un serie de módulos, cada uno de los cuales incluirá un sistema CBR que le dotará de la capacidad de aprender a través de la observación y la experiencia, y predecir las acciones más adecuadas a partir del conocimiento almacenado. Además se estudiará la construcción de comportamientos emergentes más complejos a partir de los módulos reactivos, considerando su combinación y/o alternancia dirigidas inicialmente por un sistema de reglas de decisión y proponiendo, para trabajos futuros, su sustitución por un sistema CBR que decida el peso de cada uno de los módulos componentes en la respuesta conjunta, a partir de la experiencia acumulada en la realización de los objetivos globales. Finalmente se incluirá una demostración de diseño e implementación de esta arquitectura en un escenario de aplicación y robot concreto, a través del cual se mostrarán las criterios a seguir para la toma de ciertas decisiones de diseño y las ventajas y debilidades de la arquitectura propuesta, así como su rendimiento y eficiencia. 3.1. Estructura general del sistema propuesto Dentro del modelo general de arquitectura de inteligencia propuesto en el apartado 2 del presente capítulo, nuestro trabajo se centrará en la capa inferior , correspondiente a los niveles reactivos más simples del robot. Para la implementación de un comportamiento reactivo con cierto grado de complejidad, se tendrán que definir una serie de comportamientos directos que implementen diferentes aspectos o facetas del comportamiento de alto nivel que se desea construir. Cada uno de estos comportamientos directos tendrá su propia base CBR para el almacenamiento de la información que caracterice el comportamiento, información que será incorporada a través de una fase previa de aprendizaje por observación, complementada con una fase posterior de aprendizaje por experiencia durante la operación del robot. Un menor nivel de complejidad de los comportamientos directos de partida permitirá que la adquisición de la base de conocimientos asociada al comportamiento sea más sencilla y la cantidad de información menor, al estar implicados un menor número de variables en la definición del caso, si bien el número de módulos componentes aumentará. Sin embargo la obtención del comportamiento emergente se complicará ya que la interrelación entre las salidas de los módulos componentes no será —en principio— aprendida durante las fases de entrenamiento y deberá ser establecida a posteriori. En una fase inicial de nuestro trabajo se tomó esta aproximación (figura 5.5.izq.), trabajando con módulos muy sencillos asociados a conceptos simples y poca información de entrada, de forma que la caracterización de cada comportamiento directo se conseguía a través de aprendizajes relativamente cortos con una base de conocimientos pequeña. La implementación de comportamientos emergentes a partir de pocos módulos de estas características, y mediante conmutación de comportamientos dio buenos resultados para la obtención de comportamientos emergentes no demasiado complejos, que sin embargo eran relativamente fáciles de entrenar y obtener como un único comportamiento con un número de entradas mayor pero todavía manejable. 98 3. Arquitectura aprendizaje reactivo para AIBO jugador de fútbol Sin embargo, al incorporar un mayor número de módulos simples a combinar, la combinación hacia la emergencia presentaba problemas relacionados con la orientación independiente del entrenamiento de cada módulos. Se realizaron pruebas adicionales para realizar la combinación de las respuestas de los diferentes módulos mediante la incorporación de un módulo superior de arbitración/combinación que determinaba la influencia de cada submódulo componente a través de un entrenamiento, pero no se lograron resultados concluyentes. Estos ejemplos se muestran en el apartado 2 del capítulo 6. NIVEL REACTIVO MÓDULO BÁSICO MÓDULO BÁSICO MÓDULO BÁSICO Info Pelota Info Enemigo Etc MÓDULO DE COMPOSICIÓN(n) Salida/creencia MÓDULO DE COMPOSICIÓN(n) CBR CBR u Otro MÓDULO INTERMEDIO Info Pelota Info Enemigo Info Amigo CBR Salida/Creencia conjunta MODULO DE COMPOSICIÓN(n+1) Salida/creencia compuesta Salida/creencia compuesta Salida/creencia compuesta MÓDULO INTERMEDIO Info Portería Info Enemigo Etc CBR Salida/Creencia conjunta COMPOSITION MODULE CBR u Otro Salida/creencia compuesta MÓDULO REACTIVO ÚNICO Info Pelota Info Enemigo Info Amigo Info Portería Etc Salida/creencia compuesta REACTIVO DELIBERATIVO Salida/creencia Figura 5.5: Diferentes estrategias de diseño de comportamientos reactivos emergentes mediante CBR Por otra parte la aproximación opuesta, que consideraría un único comportamiento muy complejo con un enorme número de entradas(figura 5.5.der.), se descartó de entrada por problemas de escalabilidad, si bien esta opción permitiría incluir en la base de conocimientos y mediante aprendizaje, no solo la respuesta del robot en presencia de determinados objetos/conceptos individuales, sino la variación de esta respuesta ante combinaciones y relaciones de estos objetos. Un único comportamiento de “jugar al fútbol” teniendo en cuenta todas las posibles variables y elementos de influencia, incluso en un escenario limitado como el propuesto, necesitaría de una cantidad absurda de casos de un tamaño demasiado grande como para ser manejable en tiempo real. Recordemos que la potencia del diseño de comportamientos a través del aprendizaje radica en la incorporación automática de la “reglas” que determinan dichos comportamientos sin tener un conocimiento detallado de los algoritmos y relaciones que definen dichas reglas. Finalmente, la arquitectura propuesta (figura 5.5.cent.) considera módulos básicos de un nivel de complejidad intermedio, más orientados a la incorporación de acciones o porciones del comportamiento global que a respuestas ante objetos o conceptos concretos. Estos módulos incorporan información de varios elementos del mundo donde se desenvuelva la aplicación del robot, pero solo aquellos que se considere que influyen realmente en la respuesta de dicho comportamiento, de forma que aunque el número de entradas y el tamaño de la base de conocimientos aumenta con respecto a la propuesta original, sigue dentro de unos márgenes razonables. La principal ventaja de esta decisión de diseño es que es posible capturar, a través del entrenamiento, la influencia de los componentes de entrada en el comportamiento, tanto de forma individual como conjunta, facilitando la etapa posterior de agrupación de módulos para obtener el 99 Capítulo 5. Arquitectura híbrida de aprendizaje basada en CBR comportamiento emergente de alto nivel. En el capítulo 6 se mostrará un ejemplo de diseño de un comportamiento reactivo con estas características así como la obtención de comportamientos más complejos mediante emergencia. 3.2. Escenario de trabajo Uno de los aspectos recurrentes de las arquitecturas y métodos empleados en IA, es que suelen estar orientados —sobre todo en sus primeras realizaciones— a un dominio en particular, que determina la toma de muchas de las decisiones de diseño. Aunque esta orientación a la aplicación choca con la propuesta de una teoría o arquitectura de aplicación general para la inteligencia/aprendizaje robótico, suele ser necesaria en las fases iniciales del desarrollo para, una vez comprobada su corrección y utilidad, tratar de extender la teoría a una generalización mas amplia en otros dominios y aplicaciones. El trabajo desarrollado en esta tesis no será una excepción a esta pauta: muchas de las decisiones de diseño tomadas vendrán determinadas por el dominio de la aplicación que se desarrollará como ejemplo de la arquitectura, si bien trataremos de indicar, en la medida de lo posible, las alternativas que se podrían seguir para lograr una mayor generalidad. De esta forma, antes de empezar a describir las diferentes características de diseño de los componentes y etapas de desarrollo de nuestra arquitectura, pasaremos a describir el escenario de trabajo en el que se desarrollarán los experimentos de prueba de la arquitectura. 3.2.1. Sistema hardware de testeo Como soporte de implementación de nuestra arquitectura, usaremos un robot AIBO cuadrúpedo modelo ERS-7 (figura 5.6), que cuenta con una cámara “a-bordo” situada en el morro del robot, así como diversos sensores infrarrojos de distancia. La elección de un robot cuadrúpedo no es casual, ya que esta clase de robots experimentan un control más impreciso que los robots con ruedas, debido a la propia mecánica de control de su movimiento. En este tipo de robots el control odométrico interno resulta muy complejo, por lo que es necesario realizar continuas correcciones fundadas en el propio estado del robot y el modelo del entorno percibido. Esta característica lo hace ideal para probar como la reactividad de los comportamientos absorbe fácilmente las pequeñas imprecisiones de control de los motores, de posibles deslizamientos de las extremidades y también de imperfecciones en el propio modelo del mundo. Recordemos que tampoco la inteligencia humana tiene siempre un conocimiento completo y perfecto de su entorno, y es su capacidad de adaptación ante estas lagunas de conocimiento lo que le dota de su enorme capacidad y versatilidad. Por otra parte, una descripción algorítmica de un comportamiento, por ejemplo de navegación del robot, resulta más compleja en este tipo de robots que en los robots con ruedas, por lo que quedarán mas de manifiesto las ventajas de absorber las características del comportamiento a aprender a través del entrenamiento,en vez de utilizar dichos algoritmos. Se podría decir que un funcionamiento adecuado de la arquitectura propuesta en este tipo de robot implicaría también un funcionamiento correcto, casi con toda seguridad, en la mayoría de robots con ruedas de un nivel de complejidad similar. Otro tipo de robots, como hexápodos o bípedos, se han descartado inicialmente por su mayor lentitud y la no disponibilidad física del robot, aunque se plantea intentar adaptar la arquitectura propuesta en un futuro a otros modelos. 100 3. Arquitectura aprendizaje reactivo para AIBO jugador de fútbol Figura 5.6: Robot AIBO ERS-7 En los seres humanos la visión constituye el sentido más desarrollado y que aporta mas información para modelar el mundo y determinar su conducta, por lo que parece razonable que fuese también la principal fuente de información de nuestro robot. AIBO dispone de una cámara a color en espacio Luminance-Bandwidth-Chrominance (YUV) de una resolución máxima de 208x160 píxeles con un ritmo de captura de 30fps. Para simplificar la operatividad de nuestro modelo, partiremos de un cierto grado de elaboración de la información prescindiendo, desde el punto de vista comparativo con un cerebro humano, de algunas de las capas inferiores, como las que reconocerían luz/oscuridad, orientación, agrupación de puntos (píxeles) de un mismo color, etc. Estas funciones “primitivas” serán realizadas conjuntamente por módulos no basados en aprendizaje sino en algoritmos clásicos de segmentación (figura 5.7). También usaremos como información de entrada a nuestros módulos la lectura del sensor de infrarrojos alojado en el pecho del robot y que le permitirá detectar la presencia de objetos tales como el suelo o una pelota, indicando la distancia a los mismos. Figura 5.7: Segmentación de imágenes de la cámara de AIBO Finalmente, y pese a contar con robots AIBO reales , gran parte de las pruebas se realizarán sobre el simulador 3D MIRAGE (figura 5.8), el cual está integrado en la herramienta de desarrollo Tekkotsu [262], que es la que usaremos para el control del robot, y sobre la que desarrollaremos nuestra arquitectura. Los principales motivos también están relacionados con la discontinuidad de AIBO por parte de Sony, que hace difícil la reparación o sustitución de robots que puedan averiarse. Algunos de los robots empleados ya han sufrido de ciertas averías asociadas principalmente a causas 101 Capítulo 5. Arquitectura híbrida de aprendizaje basada en CBR mecánicas (“cojera“ o desequilibrio motriz en las extremidades; ”tembleque“ en la unión del cuello; agotamiento y ruptura de baterías,...) lo cual nos hace especialmente cautos a la hora de realizar pruebas con estos robots reales. Sin embargo, el simulador escogido reproduce con una gran fidelidad los aspectos mas importantes de nuestro robot al contar con un motor físico —Bullet Physics [263]— muy completo. Como ventajas adicionales, el uso del simulador nos permite abstraernos de problemas adicionales como fallos del enlace WIFI de conexión entre el robot y el interfaz de control, distorsiones de la cámara del robot, cambios en las condiciones de iluminación, recarga de la batería del robot entre pruebas, etc... Estos problemas, si bien son intrínsecos a la aplicación de cualquier arquitectura o método en los robots reales, no resultan imprescindibles para probar el funcionamiento de la arquitectura propuesta, por lo que se ha preferido evitarlos por ahora. Por otra parte, los módulos desarrollados sobre Tekkotsu se pueden ejecutar directamente en el robot, cambiando simplemente la herramienta de compilación. Esta dualidad simulador/robot-real fue testada en las etapas iniciales de desarrollo de la arquitectura, demostrando su correcto funcionamiento, por lo cual en investigaciones futuras se tratará de aplicar la arquitectura propuesta en robots reales —AIBO, si continúan funcionando u otros robots distintos— para probar el impacto de estos problemas en el rendimiento de la misma. Figura 5.8: Simulador 3D MIRAGE con motor físico Bullets en el entorno Tekkotsu 3.2.2. Entorno de pruebas Por otra parte, la elección de la información de entrada específica para cada módulo será determinada por un experto en función del campo de dominio de la aplicación a desarrollar. Como ejemplo de aplicación se ha buscado una aplicación clásica de prueba de las capacidades de los robots, como es el campeonato de fútbol robótico RoboCup, que se lleva disputando de forma anual desde 1997. Este dominio de aplicación permite probar las técnicas y arquitecturas de IA aplicadas a la robótica en un marco común, y en un entorno controlado con un numero finito y bien conocido de variables. En la figura 5.9 podemos ver la estructura y elementos intervenientes en un partido de RoboCup. Al centrarse esta tesis en el desarrollo de la arquitectura para un robot autónomo 102 4. Estructura de un módulo de la arquitectura en el dominio propuesto individual, utilizaremos una versión modificada en la que el número de robots que intervienen es menor. Así mismo, no haremos uso de las balizas que permiten situarse al robot en el campo, ya que nos centraremos en el aprendizaje de comportamientos reactivos puros que son relativamente independientes de la posición absoluta del robot en el campo. No obstante, sería perfectamente posible añadir un módulo de localización al robot —por ejemplo mediante un filtro de partículas apoyado en las balizas— que proporcionase una información adicional con una aproximación de la posición del robot en el campo a los comportamientos que lo demandasen para implementar su actividad. Desgraciadamente, la suspensión en la producción de la linea de robots AIBO en el año 2006, llevó a su eliminación como parte de las categorías de la RoboCup a partir del año 2007. Esto dificulta en cierta medida, la comparativa del funcionamiento de nuestra arquitectura con las empleadas en los tiempos actuales en este dominio de RoboSoccer. Figura 5.9: Campo de juego RoboCup, modalidad AIBO 4. Estructura de un módulo de la arquitectura en el dominio propuesto En este apartado se describirán las características y aspectos de diseño de los módulos individuales que implementarán los comportamientos directos o de bajo nivel, que constituyen la base de nuestra arquitectura. La definición del módulo vendrá determinada por el tipo y formato de la información de entrada al mismo; por las características y operativa de la base CBR que integrará los conocimientos o conceptos asociados al módulo; por la representación de la información dentro de la base de conocimientos; y por la salida proporcionada por el módulo. En los siguientes apartados analizaremos cada uno de estos aspectos detallando las decisiones tomadas para el dominio de la aplicación propuesta, y justificando dichas decisiones en sus respectivos contextos. La implementación específica de ejemplos concretos se tratará en el capítulo siguiente, dedicado a la realización de experimentos y pruebas. 4.1. Información de entrada Como hemos indicado anteriormente, la mayor parte de la información de entrada que consideraremos es de tipo visual, procedente de una imagen artificial captado por la cámara ”a bordo“ del robot. Una aproximación directa nos llevaría a alimentar 103 Capítulo 5. Arquitectura híbrida de aprendizaje basada en CBR directamente la imagen, su descripción en píxeles YUV, como entrada de cada uno de los módulos de bajo nivel de la arquitectura. Esta aproximación, sin embargo, daría lugar a un tamaño de la información de entrada excesivamente grande —ancho_imagen x alto_imagen x 3_componentes_por_píxel—, y que además conllevaría una excesiva redundancia de información, lo cual se contradice con la visión de comportamientos simples que no contemplan el modelo completo del mundo, sino solo la información local útil para el módulo. El marco general de inteligencia propuesto, llevado al extremo, incluiría varios módulos de bajo nivel que aprenderían, a través de un sistema CBR y partiendo de la descripción de la imagen en píxeles, a reconocer características visuales como colores, bordes, tamaños, formas de objetos, etc, y que proporcionarían la información de estos conceptos a los módulos de nivel superior, aún reactivos, que tomarían las decisiones de comportamiento del robot en función de las instancias reconocidas. Para simplificar, y dado que la teoría algorítmica de reconocimiento de tales conceptos visuales de bajo nivel está perfectamente definida, hemos considerado utilizar módulos con esta orientación algorítmica para esta tarea, los cuales proporcionarán una descripción de los objetos de interés del experimento mediante una segmentación rápida de objeto basada en colores [264] a partir de la imagen de entrada. Por otra parte, y dado que estamos considerando un horizonte temporal reactivo en la respuesta de nuestros comportamientos, la toma de decisiones no tendrá en cuenta la evolución de las entradas, ni existirán estados internos que determinen dicha evolución: el robot tomará sus decisiones en función únicamente de la información percibida en cada instante. La información particular de entrada a cada módulo deberá ser escogida por un experto humano, en base a la funcionalidad que se pretende dotar al comportamiento directo. Para esta toma de decisiones el experto se puede ayudar de herramientas estadísticas que nos permitan analizar factores como la correlación entre los componentes del patrón de entrada, y la influencia que puedan tener sobre los aspectos que vayan a determinar la respuesta del comportamiento. La estructura general de un patrón de entrada a un módulo de la arquitectura, en el dominio de la aplicación propuesto, vendrá dada por una descripción de los objetos localizados en cada imagen a partir de las regiones o blobs obtenidas tras el proceso de segmentación. La descripción típica de dichas regiones de segmentación suele realizarse a través de su bounding box y su área, pero con vistas a una reducción de la dimensionalidad del patrón de entrada, se ha considerado una descripción alternativa que define a cada objeto a través de su centroide, (Cx, Cy), su área y, en caso de que exista, el clipping, o cantidad de área que bordea con los bordes de la imagen. El clipping resulta imprescindible para distinguir, por ejemplo, si un objeto con poca área visible se encuentra realmente alejado, o está cercano pero solo visible parcialmente (figura 5.10). Esta transformación de información permite obtener unos descriptores más coherentes y más fáciles de tratar en operaciones adicionales como la discretización. Todos estos parámetros se normalizarán con respecto a sus valores máximos y mínimos posibles a una escala [0,1], con objeto de poder utilizarlos de forma conjunta, sin que unos pesen más que otros en función de su magnitud. Otro aspecto clave para una buena operatividad del robot radica en disponer de información actualizada de forma constante. En la medida en que la mayoría de información procede de la visión del robot, es importante mantener enfocados los objetos de interés el mayor tiempo posible, lo cual ayudaría también a minimizar el clipping, consiguiendo una información más precisa de los objetos. En este mismo 104 4. Estructura de un módulo de la arquitectura en el dominio propuesto Figura 5.10: Información de entrada para descripción de un objeto sentido, los seres humanos tenemos un mecanismo de atención, el movimiento sacádico, que permite que nuestra visión busque objetos de interés en el campo visual, permitiendo construir un mapa mental de la escena, realizar predicciones que confirmen dicho mapa, y encontrar objetos de interés que puedan motivar una actuación. A este respecto, el robot cuenta con la posibilidad de mover la cabeza en tres grados de libertad (pan,nod, y roll) lo cual permite apuntar la cámara hacia las zonas de interés sin tener que alinear el cuerpo hacia las mismas. Si bien se han realizado pruebas para controlar la atención visual del robot hacia los objetos de interés con vistas a aprender pautas de atención que controlen el movimiento de la cabeza [265], la dificultad para realizar dichos movimientos dentro de un horizonte reactivo, sin tener en cuenta la evolución temporal de la escena, nos ha llevado a descartar este tipo de control, al menos a este nivel. En su lugar se ha desarrollado un algoritmo de seguimiento de objetos que simplemente mueve la cabeza del robot para tratar de mantener el mayor número posible de objetos de interés en el campo visual del robot. Para simplificar este mecanismo, se ha ”anulado“ el desplazamiento de la componente tilt ya que, si bien permite ampliar algo más la capacidad de atención visual, sus efectos se superponen en gran medida con los de la componente nod. Si bien este procedimiento reduce el clipping y, por tanto, permite obtener una información más fiable del área y la Bounding Box, dado que la información percibida depende de la orientación de la cabeza del robot, en el patrón de información de entrada se deberá proporcionar, además de la descripción de los objetos de interés, dicha posición de la cabeza del robot al tomar la imagen de referencia de los objetos (figura 5.11). Esta posición vendrá descrita por al ángulo de las componentes libres de movimiento de la cabeza del robot, normalizadas a sus valores máximos y mínimos posibles, por los motivos anteriormente comentados. Los datos de entrada a un módulo pueden incluir información adicional de contexto. En algunos casos esta información no puede ser obtenida a través del sistema de visión, como por ejemplo las situaciones en las que el robot se encuentra en posesión de la pelota, pero necesita observar la escena para determinar un comportamiento. Para ello, hemos añadido un componente de detección de posesión de la pelota a través del sensor infrarrojo alojado en el pecho del robot. También es posible realizar un procesamiento adicional con la información visual, para reducir la dimensionalidad de la entrada aprovechando ese conocimiento de contexto. Un ejemplo de esta situación sería la inclusión de solo una de las porterías del escenario RoboCup en la información de entrada considerando que, por las limitaciones 105 Capítulo 5. Arquitectura híbrida de aprendizaje basada en CBR Figura 5.11: Influencia de PAN y NOD sobre la imagen de entrada en el escenario del campo —se rodea el campo con vallas— no es posible detectar simultáneamente ambas porterías en una imagen. De este modo, un ejemplo de un patrón de información de entrada genérico para los módulos considerados en nuestra aplicación, Modinput , tendría la forma: Modinput = [Obj1desc, Obj2desc, ..., ObjNdesc, P AN, NOD, BallP os](5.1) donde Objidesc representa el conjunto de descriptores de un objeto con información útil para el módulo: Objidesc = [Cx, Cy, Area, Clipping](5.2) Los parámetros descritos constituyen toda la información obtenible de la posición, cámara y sensores de distancia de un AIBO en nuestro entorno de pruebas. Sin embargo, no todos los módulos necesitan el conjunto completo de estos datos. Cada módulo incluirá únicamente la información de los objetos que, a juicio del experto, influyan en su comportamiento. Los diferentes parámetros estarán normalizados a sus valores máximos y mínimo posibles, excepto el indicador de posesión de la pelota, BallPos, que será un indicador binario. Una alternativa sería normalizar los valores de cada uno de los parámetros con respecto a los valores máximos y mínimos observados en la información adquirida en el proceso de aprendizaje. Si bien esta alternativa permite una mayor precisión en la representación de la información útil, al no considerar los rangos extremos con una menor frecuencia de aparición, se corre el peligro de, durante la fase de operación, adquirir nueva información fuera de los rangos establecidos, lo cual obligaría a una nueva operación de normalización tras la adquisición de esta nueva información. Por este motivo, y por la orientación conceptual de la información de la que hablaremos en próximos apartados, consideraremos la normalización de los datos con respecto a sus valores máximos y mínimos posibles. Finalmente, se ha contemplado la posibilidad de incluir también una estimación de la posición del robot en el campo, como factor de influencia adicional en su comportamiento —sistema propioceptor—, que podría modificar el mismo, en función de si , por ejemplo, el robot se encuentra en una posición de ataque o de defensa, o en la parte central o lateral del campo. Sin embargo, esto demandaría la inclusión de un módulo adicional en la arquitectura del robot que proporcionase una estimación de su posición, en función de su evolución a lo largo del tiempo, lo cual entra en conflicto con la naturaleza reactiva pura de los comportamientos que se desea probar. En cualquier 106 4. Estructura de un módulo de la arquitectura en el dominio propuesto caso, la realización de dicho módulo a través de un filtro de partículas, se contempla para trabajos futuros. 4.2. Base de conocimientos: adquisición y almacenamiento de la información La respuesta o definición de cada unos de los comportamientos directos viene determinada por la información encerrada en su base de conocimientos. Esta base es construida por aprendizaje a partir de los diferentes patrones de información que se van presentando a su entrada durante una fase inicial de entrenamiento por observación, complementada por un aprendizaje por experiencia durante la fase de operación, que permite integrar nuevos conocimientos no tenidos en cuenta inicialmente, y ajustar los posibles fallos e imprecisiones de la información almacenada (figura 5.12). estado del robot info imagen Procesado de Datos caso nuevo Base CBR del comporta miento Figura 5.12: Aprendizaje por observación de un comportamiento En la arquitectura propuesta, la base de conocimientos se implementa a partir de un sistema CBR ya que consideramos que, por sus características y funcionamiento, es la herramienta de IA más adecuada a la teoría de inteligencia en la que se basa dicha arquitectura. Como ya vimos en el capítulo 4, a la hora de diseñar un sistema CBR es necesario establecer unas opciones de diseño que determinarán en gran medida la eficacia en el funcionamiento del sistema, y que están relacionadas con las diferentes fases del ciclo CBR. Entre las decisiones a tomar tenemos: el formato de los casos que engloban la información almacenada; la estructura de la propia base de almacenamiento; las operaciones y métricas empleadas en el proceso de búsqueda de la información más similar al problema presentado; la evaluación de si la similitud del caso recuperado es suficiente para una aplicación directa de su respuesta asociada; las técnicas de adaptación del caso recuperado en caso de que no sea así; la evaluación de la eficiencia o utilidad del caso adaptado; y el mantenimiento de la información de la base de casos, para la incorporación de nuevos problemas cuya solución adaptada sea satisfactoria, y eliminación de aquellos casos que no se consideren suficientemente útiles. En los siguientes apartados indicaremos las soluciones tomadas, justificando las decisiones, teniendo en cuenta que en el capítulo 4 ya se realizó una revisión de las opciones mas relevantes de todos estos aspectos de diseño. 107 Capítulo 5. Arquitectura híbrida de aprendizaje basada en CBR durante la fase de ejecución. Esta información se adquiere en una fase previa de aprendizaje supervisado a través de una serie de pruebas en las que el experto opera el funcionamiento del robot ante distintos escenarios, de manera que el robot almacena en la base de casos la representación de las situaciones experimentadas junto con la respuesta establecida por el operador ante dichas situaciones. Es necesario destacar que el comportamiento aprendido no tiene que ser forzosamente el más eficiente para lograr su supuesto objetivo: en teoría será una síntesis de lo que haya realizado el operador, incluyendo posibles errores o malas decisiones de éste. No obstante, si suponemos que el entrenador es suficientemente hábil en la operación del robot, el conocimiento adquirido por el robot será el adecuado. Ineficiencias puntuales, como pequeños errores en trayectorias, o dudas en la actuación serán absorbidos por el sistema y compensados por la reactividad de la arquitectura. Es importante que el entrenador base sus respuestas en la información que percibe el robot en cada momento, y no tenga en cuenta aspectos globales y temporales que no van a estar incluidos en la instancia de entrada. Por ello este proceso no resulta siempre sencillo, especialmente en lo relativo a la característica temporal del comportamiento que se está entrenando. La adquisición de conocimientos se puede realizar mediante una prueba “no controlada” de cierta duración, en la que el experto trata de realizar la tarea asociada al comportamiento durante un tiempo suficiente —por ejemplo, jugar un partido de fútbol completo— ; o a través de pequeñas pruebas correspondientes a situaciones controladas y decididas por el experto, cada una de las cuales integraría una parte de la base de conocimientos. Esta segunda opción tiene la ventaja de que es más fácil de controlar y depurar, pero a cambio exige un procedimiento más disciplinado con una planificación de los escenarios necesarios. También es posible añadir manualmente información que no se obtenga a través del aprendizaje por observación, por ejemplo para situaciones que rara vez se van a experimentar pero para las cuales se tiene claro cual debe ser la respuesta. Cuanta mayor sea la información obtenida en esta fase de entrenamiento previo, mejor será la respuesta general del comportamiento, toda vez que el formato de los casos —elección de información relevante, rangos de discretización, etc...— sea el adecuado. En cuanto a las situaciones que no se incorporen en esta fase, bien por omitir las pruebas correspondientes, o porque las instancias concretas no sean adquiridas, existirá la posibilidad de incorporarlas posteriormente a la base de conocimientos del módulo, a través de una fase de adaptación CBR realizada durante la fase operativa del comportamiento. 4.3. Organización y recuperación de la información: estructura de la base CBR Si bien el caso representa la unidad básica de información de los módulos que implementan cada uno de los comportamientos básicos, tan importante como el diseño adecuado del caso, en cuanto a la elección de los componentes de información que se proporcionarán al módulo así como la conceptualización o discretización que se aplicará a los mismos, es la estructura en que se organizarán todos los casos dentro de la base CBR. Esta estructura tiene una importancia capital en la capacidad de predicción del robot y especialmente en la velocidad a la que es capaz de realizar nuevas predicciones. Todo sistema CBR debe ser capaz de explorar la información almacenada en su anterior 114 4. Estructura de un módulo de la arquitectura en el dominio propuesto para, ante un problema que se presente, predecir cual es la respuesta más adecuada en función de las experiencias ya vividas ante esa misma situación u otra parecida. La fase de recuperación (retrieve) de un sistema CBR conlleva codificar el problema a resolver en el mismo “lenguaje“ de representación de la información en que están codificados los casos, y buscar el caso más parecido expresado en este ”lenguaje“. La codificación del problema se realiza de la misma manera que se indicó en el apartado 4.2.1, incluyendo la conceptualización según el mismo orden de conceptos que se utilizó para los casos. Con respecto a la recuperación de la experiencia más cercana al problema, depende de la estructura de organización del caso (apartado 4.2) en la base CBR , en particular en el tiempo necesario para completar el ciclo. Las estructuras jerárquicas/en-árbol son las que permiten unos tiempos de recuperación más rápidos, ya que el avance por las diferentes ramas se realiza mediante comparaciones de componentes individuales. Sin embargo, estas estructuras plantean problemas en la descomposición del caso entre los diferentes niveles, ya que la asignación de cada componente de información debería estar relacionada con su importancia o incluir al resto de componentes como sub-categorías, algo que no siempre es posible. Una mala distribución de la información conllevaría el riesgo de ”viajar“ por la rama equivocada del árbol y no recuperar el caso más adecuado, especialmente cuando ninguno de los casos almacenados coincide exactamente con el problema planteada. Además, la inclusión de nuevos casos y, en general, el mantenimiento de la base presenta mayores dificultades que otras estructuras. Una alternativa pasaría por una transformación de la información hacia una estructura en categorías u ontologías [269], pero esto exige, de nuevo, un conocimiento detallado del problema y de las relaciones entre los elementos de información del comportamiento, y parece más apropiado para niveles más abstractos del esquema de inteligencia que el nivel reactivo que estamos tratando. Como alternativa se planteó inicialmente un almacenamiento de la información en una base plana, de forma que la recuperación se basa en la comparación uno-a-uno del problema con todos los casos almacenados en la base. En este esquema la información del caso se considera como un todo, aunque es importante asignar un peso adecuado a cada componente según su influencia en el comportamiento. De esta manera se evitan los problemas de selección propios de la estructura jerárquica, y además la inclusión de nuevos casos a la base se convierte en algo trivial. Ante un nuevo problema se calcula la semejanza entre el mismo y todos los casos de la base mediante una función de similitud, (apartado 3.2.2), que nos permite establecer una ordenación de parecido de todos los casos almacenados en la base del comportamiento con respecto al problema. A partir de esta ordenación existen diferentes estrategias, como escoger los nprimeros casos mas similares y establecer una respuesta a partir de los mismos, o simplemente elegir el caso mas similar, que es la estrategia que hemos decidido seguir en nuestro trabajo (figura 5.20). En relación a la elección de la función de similitud, éste es un aspecto muy dependiente del problema y para el cual no existe una traslación sencilla entre dominios. Una hipótesis muy influyente defiende que la distancia Euclidea es más adecuada cuando las dimensiones de los estímulos están integradas perceptualmente, como por ejemplo la saturación y el brillo de un color; mientras que la distancia Manhattan o city-block es apropiada cuando las dimensiones de los estímulos son perceptualmente separables, como el color y la forma de un objeto [270]. Por este 115 Capítulo 5. Arquitectura híbrida de aprendizaje basada en CBR motivo hemos elegido como función de similitud para nuestros experimentos de prueba, la distancia Manhattan discreta [249], ya que consideramos que la mayoría de los componentes de información pertenecen al segundo tipo. En el futuro se planteará la posibilidad de utilizar distancias mixtas en las que cada tipo de componentes sea considerado, a nivel de similitud, con una u otra distancia, según sus características de percepción. En los experimentos realizado no haremos distinción en los pesos a aplicar a cada uno de los componentes del caso, si bien este sería un apartado a estudiar en trabajos futuros. Figura 5.20: Recuperación por similitud del caso mas cercano al problema 4.3.1. Diseño de comportamientos complejos: problemas de escalabilidad Los seres humanos realizan decenas de predicciones a cada segundo relacionados con ámbitos muy distintos del entorno en el que se desenvuelven, a veces de forma activa y otras de forma subconsciente. De la misma forma, un robot que intentase replicar el esquema de inteligencia humano basado en predicciones a partir de experiencias, necesita también ser capaz de realizar un gran número de predicciones por segundo, más aún si el comportamiento sobre el que se va a aplicar la predicción tiene una fuerte componente reactiva. Si el robot no es capaz de realizar todo el proceso de recuperación y adaptación de experiencias a tiempo, no podrá aplicar correctamente su respuesta y fracasará en su operación. Si los módulos a diseñar son sencillos, esto es, la cantidad de información asociada es pequeña, en cuanto a número de componentes del caso, y variedad de estos, no suele existir problema en la recuperación de experiencias de los mismos. En [63] se presentaron diversos experimentos en los que cada módulo o comportamiento a diseñar giraba en torno a la influencia aislada de un elemento del escenario en el comportamiento. Así, los casos que integran el conocimiento de cada módulo tienen un número pequeño de componentes y, tras una discretización, la variedad de posibles casos es menor: en estos experimentos bastaban unas pocas decenas de casos para adquirir la información necesaria para definir el comportamiento. Sin embargo, con esta filosofía de diseño, la integración de módulos de bajo nivel para obtener comportamientos emergentes se complicaba en demasía: tal como indica la 116 4. Estructura de un módulo de la arquitectura en el dominio propuesto teoría de la información en CBR (ver apartado 3.3), ésta se tiene que repartir de una u otra forma entre los elementos que integran el sistema de conocimiento, de manera que, la que no forme parte de cada base CBR, se debe incluir posteriormente, en este caso en la fase de composición emergente de los módulos básicos. Y es esta inclusión la que resulta muy difícil, ya que implica un conocimiento adicional de la interrelación entre las respuestas individuales a cada uno de los objetos. En este sentido, se desaprovechan las capacidades de CBR para absorber automáticamente las experiencias de las cuales se nutre el aprendizaje. Por tanto, si se desea diseñar comportamientos más complejos que impliquen varios elementos de influencia, parece más adecuado considerar todos esos elementos como información de entrada de un módulo CBR, de manera que a través del aprendizaje se adquiera el conocimientos de la respuesta ante cada elemento individual, pero también ante ante la interacción o presencia simultánea de los mismos. Esta inclusión se ve limitada por aspectos de escalabilidad relacionados con la dimensionalidad del espacio de información de los casos, tal como se vio en el apartado 4.2.1, por lo que es indispensable escoger adecuadamente los elementos de información de entrada al módulo para evitar redundancias pero también falta de información. Aún así, la información almacenada finalmente puede ser tan amplia como para que la fase de recuperación CBR comprometa la reactividad en la respuesta del comportamiento. Por este motivo, se proponen alguna modificaciones a la estructura ”tradicional“ plana de la base de casos CBR, así como a la fase de recuperación, modificaciones que permitirán acelerar el proceso de recuperación CBR y mejorar la reactividad del sistema. 4.3.2. Estructura mixta de la base CBR y recuperación multietapa de la información Tras descartar las estructuras jerárquica y plana para la base CBR, por los motivos ya expuestos, se planteó finalmente la utilización de una estructura ”mixta” que se podría encuadrar dentro de la categoría de representación generalizada del caso (figura 5.21). Para ello, se distinguen ciertos componentes del caso que representan información de “contexto”, con generalmente pocas alternativas que son excluyentes entre sí. Estos componentes de “contexto” implementan la parte jerárquica del esquema, estableciendo un árbol con parte de la información, y que tras atravesarse, desemboca en una u otra sub-base CBR con estructura plana, situada en las hojas del árbol. De esta forma se subdivide la información en tantos “subconjuntos” como hojas tengo el árbol —lo cual viene determinado por el número de componentes de contexto identificados—, y la búsqueda por similitud se produce en un subconjunto reducido de la información acelerando el tiempo de respuesta al operar sobre un número menor de casos. Por supuesto, el éxito de esta estrategia de diseño está relacionada con la identificación correcta de elementos de información de contexto, lo cual no siempre es sencillo para cualquier dominio del problema. En el dominio de aplicación que se está considerando en este trabajo, un ejemplo de información de contexto podría ser la posesión o no de la pelota; o la observación de la portería propia, la rival, o ninguna portería. Para acelerar aún mas la fase de recuperación CBR, se ha modificado la recuperación clásica por similitud con todos los casos, añadiendo una etapa previa de recuperación por índice de objetos en escena. Dicha etapa se basa en la asociación a cada caso de una información adicional que representa la existencia o no, en cada caso, de los objetos de interés en el comportamiento. Esta información toma la forma de una cadena binaria, donde cada objeto ocupa una determinada posición en la cadena, de forma que se 117 Capítulo 5. Arquitectura híbrida de aprendizaje basada en CBR Figura 5.21: Estructura jerárquica-plana de la base de casos puede representar su presencia (“1”) o ausencia (“0”) en la escena relacionada con el problema (figura 5.22). Tras la adquisición de conocimientos por aprendizaje cada caso incluiría, además de su información conceptualizada, una cadena de representación de objetos. Ante un nuevo problema, se calcularía su cadena binaria y se compararía con las cadenas de todos los casos almacenados, seleccionado solo un subconjunto de los mismos. La comparación puede ser “estricta” con una función OR que solo seleccionaría casos representando situaciones con exactamente los mismos objetos que el problema; o se puede utilizar una función Jaccard, que admitiría los casos pertenecientes a la clase más cercana al problema en cuanto coincidencia de objetos. En cualquier caso, el coste computacional de estas operaciones es mucho menor que el empleado en las funciones de similitud más comunes, de forma que se consiguen importantes mejoras en los tiempos de respuesta, mayores cuantas mas objetos hay presentes en la definición del comportamiento. Únicamente en situaciones en que los casos incluyan siempre los mismos objetos se produce un empeoramiento del tiempo de respuesta. En el capítulo de Experimentos se presentarán algunos resultados de este esquema de organización y recuperación de la base con respecto al esquema tradicional de base plana. En [271] se realizó un estudio para determinar la ganancia obtenida al aplicar las variaciones propuestas sobre la fase de recuperación CBR. En dicho estudio se constató el efecto beneficioso de los cambios propuestos en la reducción del tiempo de recuperación del caso CBR más cercano (figura 5.23). Asimismo se observó como este efecto era más acentuado conforme aumentaba la complejidad del comportamiento a adquirir, ya que dicha complejidad se asocia a la dimensionalidad de los casos y, por tanto, a la cantidad de casos necesarios para aprender dicho comportamiento. 4.4. Fase operativa: aprendizaje por experiencia Tras la fase de aprendizaje por observación, y si el diseño de los módulos, de la representación de los casos, y de la conceptualización de la información ha sido suficientemente correcto, el robot estará preparado para ejecutar el comportamiento aprendido. No obstante, puede que la respuesta autónoma no sea siempre la adecuada ante cualquier situación que se presente, debido principalmente a que no hay garantías de que el entrenamiento por observación haya sido exhaustivo, cubriendo todas las 118 4. Estructura de un módulo de la arquitectura en el dominio propuesto 11011 Pelota X X X X X Rival1 Rival2 Compañero Portería 10010 CASE1 11011 CASE34 10010 CASE53 11010 CASE99 10011 CASE157 Recuperación por índice (DistancIa Jaccard ) ETAPA1 ETAPA2 X X X 11011 (Componentes del caso) CASO34 11011 (Componentes del caso) CASO157 11011 (Componentes del caso) CASO_N Problema (Componentes del caso) Base CBR “hoja” Base de casos reducida Índice para el problema √ √ Recuperación por función de similitud Caso más similar Figura 5.22: Recuperación del caso con etapa de indexación de objetos 0 5 10 15 20 25 30 35 0 500 1000 1500 2000 2500 3000 3500 4000 tiempo (ms) Comparación de métodos de recuperación CBR con discretización Gruesa Sin ind. de Objetos Índice de Objetos Num. Casos Complejidad de Comportamiento Solo Pelota +Pelota y 1 Rival +Pelota y 1Compañero +Pelota y 2 Rivales +Pelota y 1 Rival y 1 Compañero 0 10 20 30 40 50 60 70 80 0 1000 2000 3000 4000 5000 6000 7000 8000 Sin ind. de Objetos Solo Pelota + Pelota y 1 Rival +Pelota y 1Compañero +Pelota y 2 Rivales +Pelota y 1 Rival y 1 Compañero Num. Casos Complejidad de Comportamiento Comparación de métodos de recuperación CBR con discretización Fina Índice de Objetos tiempo (ms) Figura 5.23: Mejoras en la fase de recuperación CBR usando una etapa previa de indexación de objetos 119 Capítulo 5. Arquitectura híbrida de aprendizaje basada en CBR posibles situaciones posibles —de hecho no es suele ser deseable tal medida—. También en el aprendizaje de los seres humanos el aprendizaje por observación/tutorización solo introduce los fundamentos básicos y generales de la conducta a aprender. Es necesario que el usuario refuerce este aprendizaje, lo adapte a sus características particulares, y resuelva los “huecos” de conocimiento existentes a través un aprendizaje por experiencia. Este tipo de aprendizaje se asocia a las fases de reutilización (reuse), revisión (revise), y mantenimiento (retain) del ciclo CBR, e implica la definición de estrategias y políticas adicionales, como veremos a continuación. 4.4.1. Reutilización del caso y adaptación de la respuesta Ya vimos en el apartado anterior como la recuperación del caso mas similar de entre los almacenados en la base CBR propia del comportamiento suponía, en teoría, la predicción de una respuesta adecuada —la asociada al caso recuperado— según las experiencias previas del robot. Si el problema propuesto coincide completamente con alguno de los casos almacenados, eso significa que se está volviendo a repetir una situación ya experimentada anteriormente y que, por tanto, es adecuado responder de la misma forma en que se hizo en esa ocasión previa1. Una posible optimización pasaría por evaluar los casos adquiridos y adaptarlos con vistas a mejorar el comportamiento aprendido. Aún así, suele ser frecuente que el problema no encuentre un caso exactamente igual en la base del comportamiento; en ese caso se realiza una predicción basada en la experiencia almacenada más similar, mediante la extracción del caso que presente mayor similitud. Este mismo proceso es el que realizamos los seres humanos cuando establecemos analogías, o encontramos situaciones completamente nuevas y exploramos nuestra memoria para encontrar alguna situación que se asemeje. Sin embargo, el caso más similar no tiene porque ser necesariamente un caso adecuado al nuevo problema; si la distancia entre el problema y el caso recuperado es muy grande significa que, si bien la situación expresada por el caso es “la más parecida entre las experiencias almacenadas”, no es lo suficientemente parecida para ser utilizada directamente. En este caso es necesario plantear una nueva respuesta que puede ser derivada, en parte, de la respuesta asociada al caso recuperado. La adaptación de un caso recuperado supone “probar algo nuevo” distinto de lo ya conocido y/o experimentado. Los seres humanos, cuando no somos capaces de encontrar una analogía para un nuevo problema, también “improvisamos” y aplicamos conocimientos que puedan ser, en principio, alejados del que estamos considerando en un momento dado. La adaptación del caso puede realizarse de muy diversas formas, desde utilizar una respuesta completamente aleatoria, hasta acudir a otros algoritmos o conocimientos de otros módulos. Lo que si parece razonable es que la nueva respuesta esté basado o incluya elementos de la respuesta asociada al caso recuperado, que tendrán un peso mayor en tanto la similitud entre el problema y dicho caso sea también mayor. En nuestra arquitectura de comportamientos se planteó en primer lugar cual debía ser el criterio que determinase si el casos recuperado era “suficientemente parecido” al problema, como para aplicar directamente la respuesta almacenada en dicho caso. Inicialmente se consideró la posibilidad de establecer un umbral mínimo de similitud que, una vez traspasado, determinaría la adaptación de la respuesta incluida en el 1Suponemos que el entrenamiento por observación ha sido adecuado y sin errores 120 4. Estructura de un módulo de la arquitectura en el dominio propuesto caso recuperado. Para ello se ejecutaron varias pruebas en las que se analizó qué valor mínimo de similitud, normalizada en [0,1], permitía aún un comportamiento correcto al aplicar la respuesta del caso recuperado, pero no se obtuvieron resultados concluyentes. Consideramos que esto se debe a la conceptualización de la información de entrada para definir el problema y los casos, que implica diferente número de categorías para cada componente, y en muchos casos, no equiespaciada. Además, cuando una situación o escenario está descrito por muchos componentes, pequeñas diferencias en varios de ellos se consideran tolerables desde el punto de vista de la similitud de las situaciones, pero una gran diferencia en aunque sea solo uno de ellos, no. Este último caso podría llegar a pasar desapercibido en el cálculo de la función de similitud, haciendo pasar por similar una situación descrita en un caso que sea completamente distinta a la del problema. Un ejemplo claro lo podemos ver en la posición de la cabeza del robot: un mismo escenario de objetos presentes en la imagen con una disposición del cuello muy distinta representará, por lo general, situaciones muy diferentes para el comportamiento y que de ser tomadas como similares provocará, generalmente, un comportamiento erróneo del robot (figura 5.24). Figura 5.24: Identificación errónea de escenarios por posición de cámara Por este motivo, se decidió utilizar un criterio distinto para decidir la adaptación o no del caso: la situación descrita por el problema sería suficientemente similar al caso recuperado como para aplicar su respuesta, si el número de “saltos” en los rangos o categorías conceptuales no superaba un máximo para cada componente individual, Si; para el conjunto de componente que describen cada objeto; y para el conjunto de todos los componentes que describen el caso (Ecuación 5.3): Adaptación Caso si            ∃i, Si> umbralCmpIndiv ,o ∃Obj, X i∈ObjComp Si> umbralCmpObj ,o P i∈CasoCmp Si> umbralCmpCaso (5.3) donde umbralCmpIndiv,umbralCmpObj, y umbralCmpCaso, son los umbrales que determinan respectivamente si la similitud es suficiente o no, a nivel de componente 121 Capítulo 5. Arquitectura híbrida de aprendizaje basada en CBR individual, de objeto, y de caso al completo. Actualmente, estos umbrales se calculan de forma heurística, a través de la observación del comportamiento del robot en situaciones en las que hay poco entrenamiento previo por observación. Hay que tener en cuenta que su valor está relacionado con el número rangos o categorías de los componentes en el proceso de conceptualización de los mismos, por lo que en el futuro se estudiarán alternativas para poder generalizar un método de cálculo. En cuanto al algoritmo explícito para generar una respuesta adaptada, en caso de que el criterio de la ecuación 5.3 así lo determine, se plantearon diversas alternativas, desde un vector de salida completamente aleatorios, hasta la utilización de algoritmos genéticos, para la modificación de la respuesta original del caso. Hay que tener en cuenta que esta adaptación supone la aplicación de una solución no-óptima como complemento de la solución aprendida que no se considera lo suficientemente buena y aproximada a la situación real. Se consideró la utilización de un Campo de Histogramas Vectoriales (Vector Histogram Field (VHF)) [272], pero esta técnica es más adecuada para una representación global espacial en 2D del entorno del robot y, en nuestro caso, estamos trabajando con una proyección 2D del campo de visión local del robot, por lo que no parecía sencillo trasladar el algoritmo a estas circunstancias. Finalmente, se decidió generar un posible vector de respuesta, obtenido mediante Campos de Potencial (PFA) [31] [273] de los objetos que influyen en el comportamiento, y que se combinaría con la salida del caso recuperado, con pesos determinados por la similitud entre dicho caso y el problema. A pesar de que los campos de potencial parten también de una representación global 2D del entorno en la que es necesario, en principio, conocer la distancia entre el robot y los objetos, en este caso si hemos podido representar los efectos de atracción y repulsión de los mismos basándonos en su área visible en el campo de visión, que sería proporcional a su distancia o, en caso de estar parcialmente oculto en un extremo de la pantalla, indicaría una menor influencia en el comportamiento del robot, coherente con un menor área visible. El vector de campo de potencial, ~ VP F se obtendrá como un sumatorio de los vectores generados por los distintos campos de potencial de cada uno de los objetos que afectan al comportamiento (ecuación 5.4). El cómputo de los campos de potencial para cada objeto, depende de las características del comportamiento que se está diseñando, y en particular de como afecta al mismo. Así, por ejemplo, en un comportamiento para intentar tomar posesión de la pelota, los robots rivales funcionarían como repulsores, ~ VRepj, y la pelota como atractor, ~ VAtri. En el capítulo de experimentos se presentarán ejemplos de definición de esta función de potencial para el diseño de algunos comportamientos. ~ VP F =X~ VAtri+X~ VRepj(5.4) Una vez obtenido un vector de campo de potencial, ~ VP F , dicho vector se combinará, de forma ponderada, con el vector de respuesta del caso recuperado, ~ VCBRCase,tal como se indica en la ecuación 5.5: ~ Vadapt =~ VP F ∗pP F +~ VCBRCase ∗(1 −pP F )(5.5) El parámetro pP F ∈[0,1] representa la preponderancia o peso que se le da a la nueva respuesta generada frente a la adquirida por experiencia correspondiente a una situación que consideramos similar pero alejada como para aplicar la misma respuesta. La elección de pP F se puede hacer por diversos criterios: 122 4. Estructura de un módulo de la arquitectura en el dominio propuesto Una posibilidad sería considerar pP F como d, la distancia entre el caso recuperado y el problema. Por desgracia, con esta aproximación encontramos el problema de que a menudo estamos adaptando casos que no tienen demasiada distancia con el problema, aunque sí la suficiente a nivel de“saltos” de categoría en un parámetro, objeto, o en el caso completo. En estas condiciones la aportación del vector PF sería casi nula en la mayoría de ocasiones. Para evitar este problema podríamos plantear algunas variantes: 1. Normalizar con respecto al número máximo de “saltos” considerado como umbral mínimo de adaptación. Si se alcanza el umbral mínimo para considerar necesaria la adaptación, la contribución sería del 50% por parte del vector generado mediante PFA, y del 50 % del obtenido a partir del caso recuperado. Para valores que superen ese umbral se consideraría cada vez más peso para el vector generado mediante PFA, hasta un cierto límite a partir del cual se despreciaría completamente la aportación del caso recuperado —se juzga que dicho caso es demasiado distinto al problema— y la respuesta del robot vendría dada únicamente a partir del vector PF. Este límite máximo también se puede determinar heurísticamente. También es posible establecer otros rangos de contribución para el vector PF, además de [50%, 100%], por ejemplo, empezando desde una contribución menor aunque entonces es muy posible que la aportación del vector PF sea inapreciable en gran cantidad de casos. 2. Añadir un “factor de innovación”, , que incentive la aplicación de nuevas respuestas generadas frente a las almacenadas en la base de casos. Este factor aumentaría el peso del factor ddando una mayor fuerza a ~ VP F en la generación del vector de respuesta adaptado. Se podría establecer con un valor constante elegido de forma heurística o aumentar su valor de forma adaptativa a medida que se compruebe que las respuestas generadas no se alejan los suficiente de las almacenadas en la base CBR. ~ Vadapt =~ VP F ∗(d+ϕinn) + ~ VCBRCase ∗(1 −(d+ϕinn)) (5.6) Como alternativa a la distancia, se podría escoger pP F en función de la utilidad o eficiencia del caso recuperado, de manera que aunque este esté alejado del problema planteado, se supone que, tras su aplicación, se seguirá manteniendo una parte suficiente de su utilidad En este caso (1−p)se sustituiría por el factor de utilidad ηdel caso recuperado (ecuación 5.10) y, al vector PF se le aplicaría un peso (1 −η)—suponemos que ηestá normalizado en [0,1]—. Por supuesto, sería necesario definir previamente un factor de utilidad a los casos, tal como se describe en el apartado 4.4.2. En el capítulo 6 se analizarán las diferentes propuestas para determinar cuales son las más adecuadas a la estructura y características de la presente tesis. Además, se discutirá la solución de problemas relacionados con la forma de la respuesta del caso en la aplicación específica de ejemplo, como por ejemplo que hacer ante la obtención de un vector adaptado nulo, o como actuar cuando alguno de los vectores componentes incluye acciones pregrabadas. Tras obtener el vector adaptado, éste se discretizará en una cadena de vectores, que se aplicarán al robot en los instantes apropiados. Si algún componente de la cadena 123