Adaptación computacional en sistemas percepto-efectores. Propuesta de arquitectura y políticas de control

^/2002-03 UNIVERSIDAD DE LAS PALMAS DE GRAN CANARIA UNIDAD DE TERCER CICLO Y POSTGRADO Reunido el día de la fecha, el Tribunal nombrado por el Excmo. Sr. Rector Magfco. de esta Universidad, el/a aspirante expuso esta TESIS DOCTORAL. Terminada la lectura y contestadas por el/a Doctorando/a las objeciones formuladas por los señores miembros del Tribunal, éste calificó dicho trabajo con la nota de Las Palmas de Gran Canaria, a 23 de mayo de de 2003. El/a Presidente/a: Dr.D. Juan Méndez Rodríguez, El/a Secretai El/a Vocal: Dr. '.Francisco Mario Hernández Tejera, El/a Vocal: Dr.D. Vicente Matellán Olivera, El/a Vocal: Dr.D. Humberto Martínez Barbera, El Doctorando: Di José Daniel Hernández Sosa, UNIVERSIDAD DE LAS PALMAS DE GRAN CANARIA Departamento de Informática y Sistemas TESIS DOCTORAL ADAPTACIÓN COMPUTACIONAL EN SISTEMAS PERCEPTO-EFECTORES. PROPUESTA DE ARQUITECTURA Y POLÍTICAS DE CONTROL José Daniel Hernández Sosa Las Palmas de Gran Canaria Marzo de 2003 AGRADECIMIENTOS Quiero agradecer a los directores de esta tesis, Jorge Cabrera Gámez y Antonio Falcón Martel, el apoyo y los consejos recibidos en la realización de la misma. A Jorge en particular, quiero agradecerle sinceramente su dedicación y entusiasmo, fundamentales a lo largo de todo este tiempo. También quiero agradecer a todos los miembros del antiguo grupo de investigación "Grupo de Inteligencia Artificial y Sistemas", por su ayuda. Esta memoria quiero dedicarla a mi familia, en especial a Carmen por su paciencia y comprensión. Gracias a todos. A Carmen. y a mis padres índice general Resumen xm 1. Introducción 1 2. Elementos de la Adaptación Computacional: Arquitecturas y Lenguajes 5 2.1. Introducción 5 2.2. Arquitecturas Reboticas: Deliberación o Reacción 8 2.2.1. Arquitecturas deliberativas 8 2.2.2. Arquitecturas reactivas 9 2.3. Arquitecturas Reboticas Híbridas 10 2.3.1. Nivel reactivo 11 2.3.2. Nivel ejecutivo 13 2.3.3. Nivel deliberativo 13 2.4. La Adaptación Computacional en Sistemas Percepto-Efectores 14 2.4.1. Niveles en la adaptación 15 2.5. Las Arquitecturas Robóticas Híbridas: Estudio de Casos 18 2.5.1. AuRA 18 2.5.2. CIRCA 20 2.5.3. Arquitectura 3T 22 2.5.4. Arquitectura del LAAS 27 2.5.5. Arquitectura DAMN 31 2.5.6. Sistema PRS 34 2.5.7. Arquitectura Saphira 35 2.5.8. Arquitectura S* 37 2.5.9. Arquitectura multinivel y control experto 39 I II índice general 2.5.10. Arquitectura GLAIR 40 2.5.11. Otras arquitecturas 42 2.6. Los Lenguajes: Estudio de Casos 42 2.6.1. ESL 42 2.6.2. TDL 43 2.6.3. Robot Schemas 45 2.6.4. Otros lenguajes 46 2.7. OROCOS 47 3. Propuesta de Sistema Percepto-Efector Distribuido 49 3.1. Introducción: Objetivos de Diseño 49 3.2. Estructura del Sistema 50 3.2.1. Los módulos BU-TD-COM 51 3.2.2. Flujos de información 53 3.2.3. Infraestructura 53 3.3. Infraestructura de Desarrollo: Comunicaciones y Control 54 3.3.1. Tipología de agentes 55 3.3.2. Tipología de señales 55 3.3.3. Guías de diseño 56 3.3.4. Implementación del sistema percepto-efector 56 3.4. Descripción Funcional del Sistema 57 3.4.1. Estados y tareas 58 3.4.2. Módulos funcionales 64 3.4.3. La base de conocimiento 71 3.4.4. Ejemplos de objetos contenidos en la base de datos 73 3.4.5. Señales 74 3.4.6. Lenguaje de programación 75 3.5. Estudio de Caso: Segmentación de Imágenes 77 3.6. El Sistema en Ejecución 80 3.6.1. Comandos de tareas 80 3.6.2. Asignación de prioridades y frecuencias 83 3.6.3. Control de errores 83 4. Adaptación Computacional y Control 87 índice general iii 4.1. Introducción 87 4.2. Adaptación de la Carga 88 4.2.1. Bucles de control 89 4.2.2. Modelado de la carga 90 4.2.3. Medida de la carga real 92 4.2.4. Acciones de control 95 4.2.5. Caracterización de la adaptación computacional 99 4.2.6. Calibración del sistema 102 4.3. Adaptación Computacional en Sistemas no Calibrados 103 4.3.1. Niveles de degradación 104 4.3.2. Políticas de control 104 4.3.3. Control de las violaciones temporales 106 4.3.4. Control del nivel de carga 108 4.3.5. Algoritmo de control para la distribución temporal de la carga . . 110 4.3.6. Coordinación de las políticas de control 112 4.4. Adaptación Computacional en Sistemas Calibrados 113 4.4.1. Tiempo de procesamiento y calidad 113 4.4.2. La compilación de tareas 118 4.4.3. Algoritmos de distribución de tiempo a las taxeas 127 4.4.4. Políticas de control 133 4.5. Transición de Sistemas no Calibrados a Sistemas Calibrados 137 4.5.1. Integración de las políticas de control 139 4.6. Multiprocesamiento 141 4.6.1. Distribución de módulos 143 4.6.2. Distribución basada en los datos 144 4.7. Aprendizaje de Situaciones 154 4.7.1. Casos y episodios 155 4.7.2. Selección de casos 156 4.7.3. Integración del aprendizaje, la calibración y el control 158 5. Experimentos 161 5.1. Introducción 161 5.2. Medida de la Carga 162 5.3. Bucles de Control 166 IV índice general 5.3.1. Control de la distribución temporal 166 5.3.2. Control de las violaciones temporales 166 5.3.3. Control del nivel de carga 169 5.4. Análisis de Factores 171 5.4.1. Influencia del número de niveles de degradación 171 5.4.2. Influencia de la prioridad 171 5.4.3. Influencia de la topología 172 5.4.4. Ensayos sobre distintas máquinas 177 5.5. Sistemas Calibrados y no Calibrados 178 5.5.1. Control proporcional 181 5.6. Una Aplicación Real 182 5.6.1. Planteamiento del problema 184 5.6.2. Estados, tareas y módulos 184 5.6.3. Adaptación computacional 187 5.6.4. Ejemplos de ejecución 188 6. Conclusiones y Perspectivas de Desarrollo 193 6.1. Conclusiones 193 6.1.1. Motivación 193 6.1.2. Sistema propuesto 194 6.1.3. Adaptación computacional 195 6.1.4. Experimentos 195 6.1.5. Principales aportaciones 196 6.2. Líneas Futuras de Desarrollo 198 índice de figuras 2.1. Diagrama de bloques de la arquitectura AuRA 19 2.2. Subsistemas de la arquitectura CIRCA 21 2.3. Niveles de la arquitectura 3T 23 2.4. Niveles en la arquitectura AAA 26 2.5. Arquitectura Atlantis 27 2.6. Ejemplo de aplicación basada en la arquitectura del LAAS 28 2.7. Estructura interna de un módulo genérico en la propuesta del LAAS. . . 30 2.8. Componentes de la arquitectura DAMN 32 2.9. Ejemplo del ciclo básico del intérprete PRS 35 2.10. Elementos de la arquitectura Saphira 36 2.11. Ciclo SMPA-W de la arquitectura S* 38 2.12. Niveles de la arquitectura GLAIR 41 3.1. Módulo genérico BU-TD-COM 51 3.2. Ejemplo mostrando las relaciones entre estado, tareas y módulos funcionales 58 3.3. Ejemplo de estados y transiciones entre estados 59 3.4. Topologías de tareas: a) Desacoplada, b) Concentración, c) Dispersión. . 61 3.5. Ejemplo de aplicación para un robot móvil 62 3.6. Solución simple al problema de navegación 63 3.7. Solución para la navegación añadiendo evitación de obstáculos 63 3.8. Diagrama de un control en bucle cerrado clásico 64 3.9. Diagrama que muestra las relaciones existentes entre los estados posibles de los módulos del sistema 66 3.10. Ejemplo de módulos combinados en una tarea simple 71 3.11. Ejemplo de código de diagnóstico simple. Se genera un resultado a partir de dos datos de entrada (input_l e input_2) y tres algoritmos de procesamiento (proc_A, proc_B y proc_C) 76 V XIV Resumen de acciones y diagnósticos, siendo posible la introducción de valores de frecuencia de funcionamiento y prioridad a nivel de tarea. En esta tesis se propone, de forma integrada con la arquitectura, un esquema de adaptación de bajo nivel que permite ajustar los recursos demandados a las capacidades computacionales disponibles en cada momento. Se analizan los diferentes problemas de control planteables, las acciones de control disponibles y su integración en políticas de control que las coordinen. De esta forma, se consigue que el sistema degrade y promocione en función de los recursos existentes de manera controlada. Se contempla tanto el caso de los sistemas calibrados como los no calibrados, y se realiza un análisis particular para contextos con multiprocesamiento. Se incluyen modelos para la estimación de la carga del sistema, a nivel local y global. En el caso de distribución del cómputo se definen modelos para estimar el tiempo de procesamiento en los diferentes esquemas de balanceo de carga. Se proponen además medidas para la caracterización de aspectos del sistema como su nivel de calibración o las capacidades de adaptación del mismo. Dentro de la estrategia de control, se arbitran políticas tanto locales como globales, las cuales se ofrecen como una utilidad al diseñador a través de los diferentes parámetros de configuración. En las definiciones de las tareas, pueden añadirse valores de tolerancia a las violaciones temporales, con el propósito de que sean utilizados en las políticas de control. A nivel de módulos es posible incluir información sobre los recursos de degradación disponibles, en caso de existir. Finalmente, se propone la inclusión de mecanismos de aprendizaje basado en casos y se presenta una configuración de control integrado que combina el aprendizaje con los procesos de auto calibración en el esquema de control global del sistema. Las diferentes propuestas realizadas a lo largo de la tesis se ilustran en un conjunto de experimentos para su discusión y validación. Capítulo 1 Introducción Una de las principales características de un ser vivo es la de reaccionar, bien de forma refleja bien de forma deliberada, ante cambios detectados internamente y en su entorno. Los seres artificiales, en su afán por emular las capacidades biológicas, tratan de incorporar esta funcionalidad con un nivel de competencia comparable. La tarea no es en modo alguno sencilla. Un sistema biológico es capaz de reaccionar de forma adecuada aún en casos de falta de información o en presencia de datos imprecisos, procesando y registrando de forma automática las experiencias pasadas para tratar de mejorar constantemente su rendimiento. La robustez y el aprendizaje son, por lo tanto, propiedades igualmente deseables y perseguidas por los sistemas artificiales. Los sistemas percepto-efectores son claros exponentes de estos intentos de emulación. Se han propuesto múltiples definiciones de sistemas percepto-efectores, también denominados agentes inteligentes autónomos o simplemente agentes autónomos. A continuación se incluyen algunas de ellas: " Un agente es cualquier cosa que perciba su entorno a través de sensores y actúe sobre el mismo a través de efectores''' [Russell y Norvig, 1995] ^''Los agentes autónomos son sistemas computacionales que habitan complejos entornos dinámicos, perciben y actúan autónomamente en los mismos y, de esta forma, alcanzan un conjunto de metas o tareas para las que han sido diseñados" [Maes, 1995] "Los agentes inteligentes realizan continuamente tres funciones: percepción de condiciones dinámicas en el entorno; acción para modificar las condiciones en ese entorno; y razonamiento para interpretar percepciones, resolver problemas, plantear inferencias y determinar acciones" [Hayes-Roth, 1995] "Los agentes autónomos son sistemas capaces de realizar acciones autónomamente y con propósito en el mundo real" [Pranklin, 1995] Los sistemas percepto-efectores constituyen un área de investigación en la que confluyen técnicas de diferentes disciplinas como son la Inteligencia Artificial, los Sistemas Operativos y el Control Automático. Las limitaciones de recursos a las que se ven sometidos normalmente este tipo de sistemas hacen que el cumplimiento de misiones de forma robusta requiera de una cuidada armonización de las técnicas disponibles en cada una de las áreas y niveles de actuación posibles. A raíz de la proliferación de sistemas y aplicaciones cada vez más complejas se ve clara la necesidad de imponer organizaciones modulares en los desarrollos. Una vez alcanzados los objetivos de eficacia y competencia a nivel técnico y táctico, se plantean objetivos estratégicos a más largo plazo. El propósito es ahora establecer bases metodológicas desde las que, por un lado, se simplifique la generación de las aplicaciones actuales, y por otro, puedan abordarse metas más ambiciosas. Como vía para trabajar eficientemente con la complejidad se proponen estructuras modulares que se combinan en arquitecturas sobre las que implementar aplicaciones de una manera sistemática. De esta forma se facilita su depuración y modificación, además de favorecer una mayor reutilización del código. Paralelamente se han dedicado esfuerzos de investigación a mejorar la capacidad de adaptación de los sistemas percepto-efectores con vistas a conseguir un comportamiento más robusto. De los sistemas caracterizados por un funcionamiento que se prolonga durante periodos extensos, si no indefinidos, más que el alcanzar un pico de rendimiento elevado en un instante determinado interesa la evolución media. En esta línea, se persigue el diseño de mecanismos de control y regulación que proporcionen un comportamiento promedio aceptable. Como consecuencia, el control adaptativo puede sacrificar el aprovechar al 100% las situaciones de recursos sobrantes, en favor de un mejor rendimiento cuando éstos escasean. Lo que sí es exigible en cualquier caso es un rendimiento mínimo, a fin de preservar aspectos como la seguridad y la integridad del sistema. No se aspira, lógicamente a que el sistema sea capaz de reponerse ante cualquier circunstancia adversa, pero al menos debe poder identificar correctamente su estado. En caso extremo se llegaría a una situación de "fallo consciente", de la que el sistema no puede salir sin ayuda exterior, pero sí aportar información suficiente para determinar cómo se llegó a ese estado. Considerando el comportamiento dinámico del sistema en situaciones de alteración de los recursos disponibles, los mecanismos de adaptación deben imponer una evolución suave y homogénea. Es deseable, por ejemplo, que ante un recorte en la potencia 1. Introducción computacional utilizable, el sistema degrade de forma paulatina, reduciendo progresivamente su rendimiento. El sistema debe mantenerse operativo, siendo la calidad de los resultados producidos la que se ve afectada negativamente por las circunstancias. La evolución suave del sistema lo hace más predecible, lo que reduce la incertidumbre e incrementa la seguridad. Normalmente, los aspectos ligados a la adaptación, especialmente a bajo nivel, se abordan de forma independiente a la estructuración y organización de los sistemas. De forma que son pocas las aproximaciones que tratan de incluir ambas vertientes de forma integrada. En este ámbito de problemas se sitúa la presente tesis. Se trata de la propuesta, implementación y prueba de una arquitectura para sistemas percepto-efectores que cumpla con los objetivos que se explicitan a continuación: • Estructurales: • Arquitectura modular flexible. . • Distribución funcional claramente identificable. • Integración de diferentes fuentes de información. • Reactividad. • Adaptación / Robustez: • Ajuste de la precisión de los resultados a la capacidad de cómputo disponible. • Estabilidad del sistema. • Mecanismos alternativos de procesamiento. • Observabilidad: • Monitorización del funcionamiento del sistema. • Informe de la calidad del resultado alcanzado. • Predecibilidad de los tiempos de respuesta. • Notificación de errores. • Validez / Aplicabilidad: • Combinación de ciclos de procesamiento con tiempos de respuesta variable. • Manejo de prioridades. • Reutilización del código. De todos ellos, son los objetivos relacionados con la modularidad y la adaptabilidad los que serán tratados con mayor profundidad en este trabajo. El presente documento se estructura en seis capítulos. En el capítulo 2 se describe el contexto de la tesis con una revisión de diferentes tendencias en arquitecturas robóticas y estrategias de comportamiento adaptativo. Se incluyen ejemplos representativos de diversos trabajos relacionados. El capítulo 3 presenta el sistema propuesto en esta tesis. En primer lugar se realiza una descripción desde el punto de vista de la organización estructural, definiendo los elementos modulares empleados. A continuación se presenta la propuesta desde la perspectiva funcional. En el capítulo 4 se profundiza en los aspectos ligados a la adaptación. Se describen las distintas técnicas que van a emplearse y su coordinación dentro de las diferentes políticas de control implementadas. También se presentan aspectos ligados al control distribuido y el aprendizaje. El capítulo 5 está dedicado a los experimentos, donde se analiza la influencia de diferentes factores sobre el comportamiento de los mecanismos de adaptación. Se incluye una aplicación del sistema propuesto en un entorno real. Finalmente, en el capítulo 6 se presentan los resultados y las conclusiones del trabajo, así como las futuras líneas de desarrollo. Capítulo 2 Elementos de la Adaptación Computacional: Arquitecturas y Lenguajes En este capítulo se sitúa el contexto de la tesis. Se presenta una revisión de las principales propuestas de arquitecturas para sistemas percepto-efectores. Paralelamente se introducen los conceptos relativos a la adaptación computacional y el comportamiento robusto en este tipo de sistemas. 2.1. Introducción Un sistema percepto-efector es aquél que captura información, tanto de su entorno como interna al propio sistema, la procesa y analiza, y modifica su comportamiento en base a los resultados obtenidos. Dentro de esta definición general se incluyen multitud de sistemas como son: • Sistemas biológicos. • Sistemas robóticos. • Sistemas robóticos móviles, sistemas de visión activa, manipuladores, etc. • Sistemas de control de procesos. Se trata de sistemas que evolucionan en un entorno cambiante, afectados por una serie de condicionantes adversos como son un elevado grado de incertidumbre tanto en la 6 2.1. Introducción percepción del entorno como del estado interno, la disponibilidad de recursos limitados, o las fuertes restricciones exigidas a los tiempos de respuesta. La eficacia del cumplimiento de su misión depende, pues, de mantener un constante y delicado equilibrio: tomar una decisión de control adecuada a partir de unos resultados de calidad aceptable en un tiempo suficientemente corto. A pesar de lo indicado anteriormente, los sistemas robóticos han sido objeto de notables avances en los últimos años, lo que ha conducido a una mejora significativa en sus capacidades y ámbitos de aplicación. Los resultados obtenidos alcanzan niveles elevados de eficacia y eficiencia en aplicaciones cada vez más exigentes [Kortenkamp et al., 1998]. Algunos ejemplos de aplicaciones exitosas incluyen los robots para limpieza [Prassler et al., 2000] [Simoncelli et al, 2000], exploración de áreas siniestradas o de difícil acceso [Kato y Hirose, 2001] [lagnemma et al., 2001], robots autónomos para museos [Thrun et al., 1999] [Domínguez-Brito et al., 2001], seguimiento visual en tiempo real [Paulus et al., 2000], etc. Como consecuencia de esta proliferación de sistemas surgen nuevas demandas desde las que un primer análisis pone en evidencia la necesidad de disponer de herramientas que faciliten tanto el diseño y la implementación como la monitorización del rendimiento en este tipo de aplicaciones [Kortenkamp et al., 2001] [Kortenkamp et al, 2002]. A largo plazo, los conceptos de facilidad de mantenimiento y modificación de los sistemas, así como la reutilización de desarrollos previos cobran una relevancia cada vez mayor. En términos de objetivos a alcanzar podemos hablar de objetivos tácticos y estratégicos. Dentro de las metas en el plano táctico se encontrarían las siguientes: • Robustez. • Alto grado de autonomía. • Capacidad para alcanzar metas propuestas. • Respuesta en tiempo real a los cambios del entorno. • Capacidad para seguir simultáneamente múltiples objetivos. En el horizonte estratégico cabe resaltar los siguientes puntos: • Facilidad de mantenimiento. • Reutilización del código. 2. Elementos de la Adaptación Computacional: Arquitecturas y Lenguajes 7 • Facilitar futuras extensiones. • Alcanzar un uso óptimo de los recursos computacionales disponibles. Un requisito fundamental para alcanzar los objetivos planteados es la utilización de una arquitectura de referencia en el diseño e implementación del sistema [CosteManiere y Simmons, 2000]. Una arquitectura claramente definida impone restricciones en el diseño que reportan beneficios en las etapas previas a la puesta en marcha del sistema, durante su ejecución, así como posteriormente en la validación del mismo. Lógicamente, las mencionadas restricciones deben ser entendidas como guías o recomendaciones de programación disciplinada, sin llegar al extremo de condicionar tanto el diseño del sistema que impida su utilización práctica. Dentro de un contexto como en el que nos encontramos de aplicaciones enormemente variables y complejas, pensamos que no tiene sentido buscar una solución que se adapte a todas ellas. Siempre existirán casos particulares en los que una aplicación se adapte mejor a una determinada arquitectura que a otra. Sin embargo, resultará beneficioso disponer al menos de un conjunto de alternativas entre las que poder seleccionar la más adecuada. También existen esquemas de organización modulares flexibles que no imponen ninguna configuración previa, permitiendo adaptarse a diferentes aplicaciones. La investigación en este área ha conducido a la presentación de múltiples propuestas. Con una visión general, podemos clasificar las arquitecturas robóticas en tres grandes categorías: • Arquitecturas deliberativas o jerárquicas. • Arquitecturas reactivas o basadas en comportamientos. • Arquitecturas híbridas. Las arquitecturas deliberativas se fundamentan en la utilización de un esquema ordenado de percepción, planificación y acción. Constituyen una configuración de tipo vertical (bottom-up) en la que la toma de decisiones se basa en la confrontación de los datos de los sensores con un modelo del entorno en constante actualización. Las arquitecturas reactivas definen una serie de comportamientos que ligan estrechamente la percepción con la acción. Pueden verse como estructuras de tipo horizontal en las que las decisiones pueden tomarse a distintos niveles, sin necesidad de mantener una representación común del entorno. 8 2.2. Arquitecturas Reboticas: Deliberación o Reacción Las arquitecturas híbridas son un intento de combinar la deliberación con la reacción de forma que se aproveche lo mejor de ambos planteamientos. Se trata de la línea que aglutina un mayor número de propuestas, impulsadas por diversos factores entre los que destacan la plausibilidad biológica, el rango de aphcación o el éxito alcanzado por muchas de sus implementaciones. 2.2. Arquitecturas Robóticas: Deliberación o Reac- • f cion En esta sección analizaremos brevemente los antecedentes de las arquitecturas híbridas, representados por las tendencias orientadas a la reacción frente a las puramente deliberativas. 2.2.1. Arquitecturas deliberativas Los primeros intentos de integrar las técnicas de inteligencia artificial en sistemas robóticos condujeron a la utilización generalizada de arquitecturas jerárquicas basadas en el paradigma de los ciclos de percepción, planificación y acción (SPA, Senst Plan Act). En éstos se defiende la necesidad de mantener una representación o modelo del mundo sobre el que mapear los resultados de los sensores. Este modelo permite la reducción del volumen de información a analizar en la etapa de razonamiento. Algunos ejemplos representativos de esta tendencia son los trabajos de Nilsson [Nilsson, 1980] y Moravec [Moravec, 1990]. La dificultad principal a la que tienen que hacer frente las arquitecturas deliberativas es la necesidad de garantizar una correspondencia directa entre el mundo externo y la representación del mismo manejada por el sistema robótico. La consecuencia es que gran parte de los esfuerzos se concentran en conseguir una elevada reactividad del modelo a los cambios del entorno, para que éstos se reflejen adecuadamente; y de forma simultánea se intenta reducir el tiempo de respuesta del sistema ante los cambios en el modelo. En situaciones donde la rapidez con que se producen cambios en el entorno es elevada, estos métodos tienden a producir resultados desfasados en el tiempo. 2. Elementos de la Adaptación Computacional: Arquitecturas y Lenguajes 9 2.2.2. Arquitecturas reactivas Ante los problemas mostrados por las propuestas SPA, se lanzan alternativas centradas en tratar de acortar el tiempo de reacción del sistema ante estímulos externos. Las arquitecturas reactivas proponen la construcción de sistemas robóticos a partir de la combinación de comportamientos de percepción/reacción simples. Las características principales que presentan son las siguientes: • Uso de los comportamientos como bloques básicos de construcción. • Evitar en lo posible el uso de modelos del mundo, los cuales - de existir - serán siempre locales. • Inspiración biológica. Algunos ejemplos representativos de esta propuesta incluyen los vehículos de Braitenberg [Braitenberg, 1984], la arquitectura de supresión ("subsumption architecture") de Brooks [Brooks, 1986] o los esquemas motores ("motor schema") de Arkin [Arkin, 1989]. Un aspecto importante de los sistemas basados en comportamientos es la coordinación de los mismos, puesto que las reacciones a los estímulos se traducen al final en acciones que compiten por un conjunto reducido de actuadores. Las clases principales de coordinación son los mecanismos selectivos por un lado y los de combinación por otro. Dentro de las estrategias de selección están las conexiones de supresión/inhibición en las que se basa la arquitectura de supresión o las de selección por votos empleadas en la arquitectura distribuida de Rosemblatt DAMN [Rosenblatt, 1995]. La combinación de comportamientos pretende que todas las salidas sean tenidas en cuenta para generar una señal de control por cooperación. Algunas posibilidades incluyen los mecanismos de combinación basados en lógica difusa [Safñotti et al., 1997], los campos potenciales [Khatib, 1986], o los de composición vectorial, como en el caso de los esquemas motores de Arkin. Otra propuesta interesante es la debida a Schoner, Dose y Engels [Schoner et al, 1996], en la que se incluyen ecuaciones diferenciales para modelar la dinámica de los comportamientos. El trabajo de Pirjanian [Pirjanian, 1998] incluye un análisis en profundidad de las diferentes alternativas en fusión de comportamientos y selección de acciones. Los sistemas puramente reactivos han demostrado su eficacia en multitud de aplicaciones. Sin embargo, estas arquitecturas presentan también características negativas 2.4. La Adaptación Computacional en Sistemas 16 Percepto-Efectores por otras equivalentes en función de los recursos disponibles, manteniéndose la planificación invariante. En el nivel más alto, sólo la misión del sistema permanece invariante, actuando los mecanismos de planificación como reguladores. En [Hayes-Roth, 1995], estos niveles de adaptación se identifican como adaptación de la estrategia perceptual, del modo de control, de las tareas de razonamiento, de los métodos de razonamiento y de las estrategias de meta-control. Nuestro interés se centra especialmente en la adaptación computacional de bajo nivel. Los esfuerzos de investigación se concentran aquí en dos aspectos: variación de la carga y planificación de las tareas. Por un lado se buscan esquemas de cómputo para las taxeas que permitan variar dinámicamente la carga que suponen para el sistema. Por otro, se intenta aprovechar ese nuevo grado de libertad en los mecanismos de planificación, a fin de permitir un reparto óptimo de los recursos disponibles. Vairiación de la carga computacional La carga de un sistema puede variarse mediante dos vías principales: modificar el número de tareas en ejecución o modificar sus demandas computacionales. La primera de las alternativas requiere normalmente una replanificación del sistema, por lo que se trata de una estrategia de alto nivel, mientras que la segunda puede aplicarse en niveles más bajos. La modificación de las demandas computacionales de una tarea puede a su vez alcanzarse mediante diferentes estrategias. Algunas alternativas que cabe destacar son las siguientes: • Algoritmos anytime. • Computaciones imprecisas. • Diseño en función del tiempo. • Planificación deliberativa. • Modificación de la frecuencia de funcionamiento (tareas periódicas). Los algoritmos anytime [Dean y Boddy, 1988] constituyen estrategias de procesamiento iterativas que proporcionan resultados de calidad creciente a medida que aumenta el tiempo disponible. En general, se precisa un tiempo mínimo para que se genere un primer resultado con calidad mínima. A partir de ese instante se van obteniendo refinamientos hasta llegar a la máxima calidad posible. 2. Elementos de la Adaptación Computacional: Arquitecturas y Lenguajes 17 En la computación imprecisa {Imprecise Computation) [Liu et al., 1994] se fraccionan las tareas en una paxte obligatoria y una parte opcional. La parte obligatoria siempre se ejecuta, mientras que la parte opcional únicamente se ejecuta si existen recursos computacionales disponibles. El diseño en función del tiempo {Design-to-time) [Garvey y Lesser, 1993] [Wagner et al, 1998], o método de múltiples versiones, se basa en disponer de varias implementaciones alternativas para cada tarea, cada una con diferentes consumos de recursos. En función de los recursos existentes en un momento determinado se van seleccionando para la ejecución implementaciones más o menos exigentes. En la planificación deliberativa {Deliberative scheduling) [Boddy y Dean, 1994] se consideran todas las tareas como algoritmos anytime. La ejecución se planifica de manera que se maximice alguna medida de la utilidad (calidad) global del sistema. Todos estos métodos se basan de una u otra manera en el manejo de perfiles de rendimiento en los que se representa la evolución de la calidad que se alcanza en función de la cantidad de recurso disponible. Otros autores como Musliner et al. [Musliner et al., 1995] trasladan estos resultados al contexto de una arquitectura robótica híbrida intentando eliminar la necesidad de disponer de perfiles de rendimiento. Para ello se combinan soluciones tácticas a nivel reactivo con soluciones estratégicas a nivel deliberativo. Los perfiles de rendimiento son reemplazados por una medida de la calidad global alcanzada. En tareas periódicas, es posible reducir la carga computacional modificando el periodo de funcionamiento. Si la tarea posee un rango de frecuencias de operación válidas, el desplazamiento hacia frecuencias menores permite relajar las demandas impuestas al sistema, mientras que las frecuencias mayores absorben más recursos. Planificación de las tareas Una vez identificados los elementos de ajuste disponibles, el siguiente paso es utilizar esos grados de libertad para alcanzar un comportamiento adecuado en situaciones de carga y recursos computacionales variables. En los sistemas con restricciones de tiempo real críticas {hard real-time), se aplican técnicas de planificación de CPU o scheduling que eviten la violación de los límites temporales. Una de las soluciones factibles es la planificación previa a la ejecución basada en el peor caso. Sin embargo, se trata de una alternativa que en la mayoría de las ocasiones resulta excesivamente conservadora, puesto que el peor caso suele estar muy 18 2.5. Las Arquitecturas Reboticas Híbridas: Estudio de Casos alejado del comportamiento promedio. Esto deriva en una clara infrautilización de los recursos disponibles en el sistema durante un porcentaje elevado de su tiempo de operación. En algunos casos, pueden incluso fallar las estimaciones para el peor caso, lo que no garantiza una ejecución libre de fallos [Stewart y Khosla, 1997]. Para evitar esto, se precisan mecanismos adaptativos que ajusten el consumo de recursos a los disponibles en cada momento. En esta línea existen múltiples trabajos de planificación dinámica para sistemas de tiempo real [Bondavalli et al., 1993][Ramamritham y Stankovic, 1991]. El objetivo de estas técnicas es normalmente extender los mecanismos de planificación básicos para sistemas de tiempo real duro EDF {Earliest Deadline First) de prioridades dinámicas o RM {Rate Monotonic) de prioridades fijas, de manera que puedan aprovecharse las características de la carga computacional variable. Algunos ejemplos son los trabajos que se concentran en la fijación de las frecuencias de funcionamiento, como es el caso de [Seto et al., 1996] o [Buttazzo et al., 1998]. Otro enfoque para el problema de la adaptación consiste en hacer énfasis en la integración en sistemas tolerantes a fallos ([González et al., 1997], [BondavalH et al., 1993]). En estos casos se buscan combinaciones de las técnicas de redundancia para alcanzar un comportamiento adaptativo. Dichas técnicas incluyen TMR (Triple Modular Redundancy), PB (Primary Backup) y PE {Primary Exception). Normalmente se aplican en entornos multiprocesador. Stewart [Stewart, 1994] propone un mecanismo de planificación híbrido denominado MUF (Máximum Urgency First). En este trabajo se combinan las prioridades estáticas del RM con las prioridades dinámicas del EDF. 2.5. Las Arquitecturas Reboticas Híbridas: Estudio de Casos A continuación, y por su significancia en el modelo propuesto en esta tesis, se van a describir brevemente un conjunto de arquitecturas reboticas híbridas, haciendo especial hincapié en su organización estructural y los mecanismos de adaptación computacional que incorporan. 2.5.1. AuRA AuRA (Autonomous Robot Architecture) es una propuesta de arquitectura robótica debida a Ronald Arkin. Se trata de una arquitectura híbrida [Arkin y Balch, 1997] de 2. Elementos de la Adaptación Computacional: Arquitecturas y Lenguajes 19 Aprendizaje 1 Reconocimiento i ' deiperfiide | 1 usuario i 1 Aprendizaje i • espaciai ' ¡ Oportunismo | , Adaptación oni 1 line 1 Entrada de usuario 1 Intenciones del ' ! usuario ', \ Objetivos 1 1 espaciales i 1 Modificaciones ' ' enlamisión | 1 Teleautonomía i Pianificadordela misión Razonador espacial Secuencladarde! - plan i • Control de Esquema! Motor 1 Perceptual R E P R E S E N T * C Ó N . k r 1 Acción Percepción Componente Jerárquico Componente Reactivo Figura 2.1: Diagrama de bloques de la arquitectura AuRA. dos niveles especialmente orientada hacia tareas de navegación. AuRA aprovecha ideas derivadas del estudio de sistemas biológicos y de la neurofisiología para trasladarlas a los sistemas robóticos. Se ha empleado esta arquitectura en la construcción de diferentes robots para diversas aplicaciones de navegación, exploración y manipulación. Estructura AuRA combina un componente jerárquico de deliberación en el nivel superior con un componente reactivo en el nivel inferior. El componente jerárquico está integrado por un planificador de misión {mission planner), un módulo de razonamiento espacial {spatial reasoner) y un secuenciador {plan sequencer). Enlazado con este nivel se sitúa como componente reactivo un controlador de esquemas motores {schema controller). La figura 2.1 muestra un diagrama de bloques con los elementos principales de la arquitectura. Dentro de la parte deliberativa, el planificador de misión establece las metas de alto nivel para el sistema y las restricciones bajo las que debe operar. El módulo de razonamiento espacial utiliza información cartográfica paxa construir la secuencia de segmentos de trayectoria que el robot debe seguir para completar su misión. Por último el secuenciador traslada cada trozo de trayectoria en un conjunto de comportamientos motores para comandar su ejecución en el nivel inferior. En el nivel reactivo, el controlador de esquemas monitoriza y controla en tiempo de ejecución la evolución de los comportamientos de bajo nivel. Cada comportamiento o esquema motor [Arkin, 1989] produce como salida de control un vector de respuesta que 20 2.5. Las Arquitecturas Reboticas Híbridas: Estudio de Casos se combina con las respuestas de todos los demás esquemas para producir el comando que llegará finalmente al robot físico. Todos los comportamientos operan de manera asincrona. Una vez se comandan las acciones correspondientes al nivel reactivo, el nivel deliberativo queda a la espera de recibir la notificación de tarea finalizada correctamente o bien de algún error. Los errores se intentan resolver ordenadamente, comenzando por el secuenciador y terminando en el planificador de misión si todos los demás han fracasado en la resolución del problema. La arquitectura es altamente modular, lo que ha permitido ensayar diferentes implementaciones para cada nivel, reemplazando las existentes. Adaptación Se han probado en AuRA diferentes mecanismos de adaptación y aprendizaje. Dentro de ellos cabe destacar los siguientes: • Control homeostático [Arkin, 1992]. • Adaptación dinámica para los comportamientos empleando métodos basados en reglas [Clark et al, 1992]. • Razonamiento basado en casos para gobernar la conmutación de comportamientos en función de las características del entorno [Ram et al., 1992]. • Algoritmos genéticos para el ajuste de los parámetros asociados a los lazos de control [Ram et al., 1994]. El control homeostático merece especial interés en el contexto de este trabajo. El objetivo es mantener bajo control determinadas variables relevantes para garantizar la integridad física del sistema, a modo de "constantes vitales". Se trata de un control autónomo de bajo nivel que opera de forma continua e independientemente de la presencia de bucles de control de más alto nivel. Algunos ejemplos serían la vigilancia del nivel de baterías o el control de la temperatura. Se ha probado fundamentalmente a nivel de simulación. 2.5.2. CIRCA La arquitectura CIRCA {Cooperative Intelligent Real-Time Control Architecture), ideada por David Musliner, Edmun Durfee y Kang Shin, constituye un intento de m "dr-A á^ 2. Elementos de la Adaptación Computacional: Arquitecturas y Lenguajes 21 li'.luilfljil KnüidiJu del t 'A J Figura 2.2: Subsistemas de la arquitectura CIRCA. combinar técnicas de Inteligencia Artificial con restricciones de tiempo real en el mismo sistema. Estructura CIRCA [Musliner et al., 1993] se compone de dos subsistemas, el RTS {Real Time Subsystem) y el AIS {Artificial Intelligence Subsystem), para abordar separadamente los objetivos de control y de tarea respectivamente. La figura 2.2 muestra estos subsistemas y sus interconexiones. El AIS utiliza métodos de Inteligencia Artificial para descomponer los objetivos a nivel de tarea en objetivos de control. Posteriormente se hace uso de un planificador para intentar garantizar los tiempos de respuesta de esos nuevos objetivos. Se utiliza un grafo dirigido para modelar el comportamiento del entorno y las acciones que debe tomar el RTS a fin de evitar fallos. El modelado se realiza siempre para el peor caso. El RTS ejecuta una secuencia de TAPs {Test-Action pairs) cíclicamente. Dichas secuencias son propuestas por el AIS de modo que cumplan los objetivos de control en dirección a los objetivos a nivel de tarea. El planificador comprueba su viabilidad en función de los recursos disponibles, dando lugar a una planificación de TAPs con tiempos de respuesta garantizados. Un TAP está formado por un conjunto de precondiciones, las acciones a tomar si se cumplen las precondiciones, datos sobre los sensores y actuadores requeridos, y estimaciones para el peor caso de los tiempos requeridos para comprobar las precondiciones 22 2.5. Las Arquitecturas Robóticas Híbridas: Estudio de Casos y ejecutar las acciones. Adicionalmente, las instancias específicas de cada TAP pueden incorporar parámetros extra como son la frecuencia de operación o el tiempo máximo de respuesta admisible. En un trabajo posterior, CIRCA ha evolucionado para dar lugax a SA-CIRCA {Self-Adaptive CIRCA) [Musliner et al, 1999]. En esta propuesta, el AIS pasa a estar constituido por dos módulos, el AMS o planificador de misión adaptativo {AMP-Adaptive Mission Planner) y el CSM o módulo de síntesis de controladores (Controller Synthesis Module). El AMS razona acerca de las metas a largo plazo en función de las restricciones impuestas para decidir cuáles deben ser los problemas a resolver a corto plazo. Las submetas son enviadas al CSM para que éste sintetice planes de control que cumplan con las especificaciones. Mientras el AMS y el CSM siguen procesando futuras situaciones por adelantado, el RTS recibe los planes de control generados y los ejecuta. El RTS mantiene un mecanismo de almacenamiento de múltiples planes que pueden ser activados como planes alternativos mediante una rápida conmutación de contexto. Adaptación Los esquemas de adaptación de CIRCA son limitados al ser un sistema orientado a garantizar restricciones de tiempo real. Aún así, incorpora un mecanismo para ajustar la demanda computacional a los recursos existentes basada en una lista de TAPs no garantizados. Esta lista se compone de TAPs que implementan tareas de baja prioridad. Cuando por alguna causa se detectan recursos disponibles, por ejemplo cuando una TAP perteneciente a la planificación garantizada no se ejecuta, se intenta seleccionar una TAP de la lista no garantizada para cubrir ese hueco. En [Musliner, 2001] se describen las capacidades de adaptación de SA-CIRCA. Existen mecanismos para alterar la planificación en tiempo de ejecución o bien para seleccionar dinámicamente planes previamente diseñados. Cuando una situación no prevista se presenta se intenta en primer lugar conmutar a un plan ya definido que la trate. Si esto no es posible, se solicita la generación de un nuevo plan. 2.5.3. Arquitectura 3T La arquitectura 3T ("3 Tiers") es el resultado de la colaboración entre diferentes investigadores: Peter Bonasso, James Firby, Erann Gat o David Kortenkamp, entre otros. Algunos ejemplos de otras propuestas de arquitecturas que han contribuido o están estrechamente relacionados con este proyecto son AAA [Firby et al., 1995o] o 2. Elementos de la Adaptación Computacional: Arquitecturas y Lenguajes 23 Deliberación Ordenación de Tareas Secuenciación Instanciación de Tareas Cap. Reactivas Lecturas de Sensores Comandos aActuadores Mundo/ Entorno Figura 2.3: Niveles de la arquitectura 3T. ATLANTIS [Gat, 1992]. El objetivo principal que se persigue en 3T es alcanzar un comportamiento robusto en la resolución de tareas mediante la combinación de reactividad y deliberación. En el contexto de este proyecto se han desarrollado, además, un conjunto de herramientas software para ayudar al programador en el diseño de aplicaciones robóticas. La arquitectura 3T ha sido utilizada en una gran variedad de entornos y aplicaciones [Bonasso et al., 1997], como son búsqueda y reconocimiento de personas, recolección de basuras, navegación en entornos de oficina y simulación de manipuladores. Estructura La arquitectura 3T comprende tres niveles: • Nivel de capacidades o habilidades reactivas. • Secuenciador. • Planificador. La figura 2.3 muestra la organización por niveles de esta arquitectura. El planificador sintetiza todos los objetivos que se impongan al sistema en un listado de tareas a realizar. Estas tareas, a su vez, se descomponen en uno o más conjuntos de acciones o RAPs {Reactive Action Packages) [Firby, 1989], que van siendo 24 2.5. Las Arquitecturas Robóticas Híbridas: Estudio de Casos seleccionadas por el planificador para su ejecución. En el nivel de secuenciación, se reciben los RAPs activados y se controla su ejecución. Esto supone obtener los conjuntos de habilidades requeridas y ordenar su activación al nivel reactivo, junto con un conjunto de monitores de eventos. Los monitores permiten detectar el disparo de diferentes eventos, que son notificados al secuenciador. El secuenciador va reemplazando las tareas por otras nuevas, si las hay, a medida que se detectan eventos, se registra una violación temporal o se recibe una nueva planificación desde el nivel superior. El nivel de las capacidades está formado por un conjunto de acciones de control dependientes del entorno {situated skills) que han sido obtenidas de manera sistemática para evitar resultados dependientes de un robot o contexto de aplicación concretos. Se llega así a una representación uniforme para las capacidades que facilita su manipulación. Esta representación incluye los siguientes elementos: • Especificación de las entradas y sahdas. • Algoritmo de procesamiento. • Rutina de inicialización. • Función de activación. • Función de desactivación. Las capacidades se controlan por medio de un gestor {skill manager) que establece una interfaz uniforme con el secuenciador. A través de esa interfaz circulan comandos dirigidos a las capacidades y eventos que deben ser notificados al secuenciador. El objetivo es liberar al programador de los detalles de coordinación entre las capacidades de bajo nivel para concentrarse en la tarea. La secuenciación corre a cargo del intérprete de tareas {RAPs interpreter). Este intérprete dispone de una librería de RAPs, cada una de las cuales es adecuada para una situación determinada y, por lo tanto, se traducen en un conjunto diferente de habilidades. Una clase especial de capacidades son los eventos, que se encargan de notificar al secuenciador circunstancias especiales relevantes para la evaluación el progreso de la actividad (fin de tarea, cambio de entorno, etc). Por encima de la combinación secuenciación/reacción, se necesita un elemento que añada perspectiva global al sistema. Esa labor está desempeñada por el planificador, aunque se sirve del grado de abstracción que aportan los niveles inferiores para simplificar su tarea, reduciendo la dimensión del espacio del problema a analizar. Una premisa 2. Elementos de la Adaptación Computacional: Arquitecturas y Lenguajes 25 importante para lograr los objetivos propuestos en 3T es que los tres niveles definidos operen de manera concurrente y asincrona. Una cuestión determinante es cómo decidir a qué nivel debe ubicarse una actividad concreta dentro del sistema. Para ello se propone un análisis basado en cuatro características: Periodo de repetición: Los periodos típicos utilizados en el nivel reactivo son del orden de milisegundos, los del nivel de secuenciación del orden de décimas de segundo y los del planificador varían de segundos a decenas de segundos. Ancho de banda: Las habilidades de bajo nivel pueden llegar a intercambiar elevados volúmenes de información, mientras que la interfaz entre niveles debe demandar un ancho de banda reducido. Funcionalidad: Si una actividad de un cierto nivel incorpora mecanismos ya recogidos en la arquitectura es mejor dividirla y que sea la propia arquitectura la que actúe (habilidades que realizan selección o RAPs que gestionan recursos). Grado de modificabilidad: Las capacidades suelen ser compiladas y no pueden modificarse en tiempo de ejecución, cosa que sí ocurre en los niveles de secuenciación y planificación que están basados en intérpretes. Adaptación La ejecución adaptativa se basa en disponer de múltiples métodos de resolución para satisfacer una determinada tarea. Cada uno de esos métodos está asociado a unas condiciones de aplicación determinadas. La tarea posee un test de éxito para comprobar cuándo la tarea ha finalizado correctamente. Arquitecturas relacionadas En [Firby et al., 1995a] se aplicaban soluciones similares a las requeridas en la implementación de la capa de bajo nivel de un sistema de visión, para constituir la arquitectura AAA {Animate Agent Archüecture). Se encapsula el procesamiento visual en módulos denominados rutinas visuales, formadas a su vez por combinaciones de primitivas u operadores visuales. En tiempo de ejecución, las rutinas visuales se emparejan con rutinas de acción dando lugar a bucles cerrados de operación en tiempo real. La figura 2.4 ilustra la organización por niveles de esta arquitectura. 32 2.5. Las Arquitecturas Reboticas Híbridas: Estudio de Casos Figura 2.8: Componentes de la arquitectura DAMN. Estructura La arquitectura DAMN [Rosenblatt, 1995] está integrada por los siguientes elementos: Sistema de control de la votación {DAMN Arbiter). Comportamientos. Controlador de modo de funcionamiento. Controlador del vehículo. La figura 2.8 muestra las interconexiones entre los diferentes componentes de la arquitectura. Los diferentes comportamientos, con independencia de su nivel de competencia, realizan votaciones positivas y negativas en el espacio de comandos. Aquí se incluyen comandos de giro, velocidad, área de visión, etc. El gestor de las votaciones se encarga de fundir los resultados para elegir la opción más votada. Esta selección es el producto de diferentes procesos que incluyen la combinación de los resultados con los pesos asignados por el controlador de modo, suavizado e interpolación. El funcionamiento es similax a la arquitectura de supresión, si bien aquí pueden emplearse representaciones internas del mundo. 2. Elementos de la Adaptación Computacional: Arquitecturas y Lenguajes 33 En esta arquitectura los comportamientos se agrupan en tres niveles de competencia: • Seguridad. • Dinámica del vehículo: Límites de giro y velocidad. • Evitación de obstáculos: Evaluación de colisión en posibles trayectorias. • Comportamientos auxiliares: Movimientos por defecto e inercias. • Acción. • Seguimiento de carretera. • Campo a través. • Teleoperación. • Objetivos. • Subobjetivos. • Campos de gradiente. • Planificador de trayectorias. El diseño de DAMN permite combinar comportamientos con frecuencias de funcionamiento variadas, como corresponde al caso de los comportamientos reactivos frente a los deliberativos. El resultado de la fusión de los comandos generados determina el comportamiento del sistema, de forma que las acciones producidas por módulos con un peso mayor son las que ejercen más influencia. Aún así, pueden emplearse mecanismos de operación de más alto nivel que controlan la asignación de pesos a los comportamientos, dando lugar a un nivel de metacontrol. Adaptación La ejecución adaptativa en DAMN se basa en la modificación dinámica de los pesos asignados a cada comportamiento. Es también en este punto donde es posible introducir aprendizaje en el sistema, de manera que la configuración de pesos adecuada se registre para su posterior utilización en situaciones similares. 34 2.5. Las Arquitecturas Robóticas Híbridas: Estudio de Casos 2.5.6. Sistema PRS PRS {Procedural Reasoning System) es una arquitectura genérica para representación y deliberación [Ingrand et al., 1992] sobre acciones y procedimientos en un entorno dinámico [Ingrand y Coutance, 1993]. Está basada en el concepto de agente reactivo o arquitectura de agentes BDI {Belief-Desire-Intention). PRS se constituye como un sistema de planificación híbrido que intenta combinar deliberación con reactividad mediante el uso de planes de meta-control. Se ha utilizado en diferentes aplicaciones con demandas de tiempo real como son la monitorización de fallos mecánicos en cohetes y aviones [Georgeff y Ingrand, 1989], control de robots móviles [Ingrand et al., 1995], y supervisión y control en redes de telecomunicación. Estructura Un módulo PRS está integrado por los siguientes componentes: • Base de hipótesis. • Un conjunto de metas. • Biblioteca de planes. • Estructura de intenciones. A partir de las metas y las hipótesis, un intérprete se encarga de seleccionar los planes adecuados para formar parte de la estructura de intenciones a ejecutar por el sistema. Los planes son denominados en PRS áreas de conocimiento o KA {Knowledge Áreas), y contienen secuencias de acciones y tests necesarios para alcanzar una meta determinada. Cada KA consta de un cuerpo principal y una condición de activación, la cual a su vez está constituida por un contexto de aphcación y un evento. El ciclo básico del intérprete comienza con la detección de cambios en las metas o hipótesis del sistema. Estos cambios dan lugar a la activación de diferentes KA's, de las cuales se seleccionan algunas para su ejecución. El ciclo termina con la ejecución de un paso de alguna de las KA's en la estructura de intenciones. La ñgura 2.9 ilustra este ciclo de operación. 2. Elementos de la Adaptación Computacional: Arquitecturas y Lenguajes 35 Acción primea Ejecutar acción M Ejecución di procedimientos Nuevas metas y liechos Biblioteca de procedimientos Figura 2.9: Ejemplo del ciclo básico del intérprete PRS. 2.5.7. Arquitectura Saphira Se plantean como objetivos fundamentales de un agente móvil autónomo la capacidad para atender y seguir (a una persona), la asimilación de información (aprender un mapa del entorno) y la ejecución de tareas (navegar con robustez) [Konolige et al., 1997]. Para cumplir con estos objetivos, una arquitectura debe incorporar tres características básicas: la coordinación, la coherencia y la comunicación. Desde estos presupuestos se ha concebido la arquitectura Saphira, utilizada en la implementación de aplicaciones de seguimiento, navegación e interacción en robots móviles [Guzzoni et al, 1997]. Estructura Se propone una arquitectura por niveles construida en torno a un mecanismo de representación interna, el espacio perceptual local o LPS {Local Perceptual Space). Existe una parte perceptora encargada de trasladar los datos de los sensores al LPS y extraer información de los mismos, y una parte efectora sobre la que se ejecutan los diferentes comportamientos. Se dispone de comportamientos reactivos de bajo nivel, comportamientos dirigidos por metas de nivel intermedio y comportamientos de tareas de alto nivel. La figura 2.9 presenta los diferentes elementos que integraxi esta propuesta. La arquitectura está concebida para establecer una relación cliente/servidor con un servidor robótico {robot server). Con esto se mejora la transportabilidad, aislando al sistema de las dependencias del hardware. 36 2.5. Las Arquitecturas Reboticas Híbridas: Estudio de Casos Biblioteca de esquemas Seguimiento de persorés Recorxjc.y regfetro de objetos . Corstrucción de Superficies Información de profuntídad < > < • < > < > Espacio i local psíiccptual (LPS) . / ff // A—> *.—> <—> Esquemas de tarea Comport.con propósito Comport. reactivos Sensores Actuadores Figura 2.10: Elementos de la arquitectura Saphira. El control de Saphira se basa en comportamientos. Los comportamientos de bajo nivel (reactivos) se definen y se coordinan empleando lógica difusa [Saffiotti et al., 1997]. En su definición se emplean una serie de reglas difusas y una función de actualización de las variables que intervienen en las mismas. La acción se selecciona por cada canal de control (variable actuadora) promediando los diferentes valores de acción obtenidos desde las reglas que concluyen sobre dicho canal. La función de ponderación tiene en cuenta para cada comportamiento un valor de prioridad fijo y un contexto de apHcación variable. Este mecanismo de coordinación dependiente del contexto se emplea tanto para los comportamientos reactivos como para los orientados a metas. La coherencia del sistema se basa en mantener actualizados unos descriptores de objetos del entorno, denominados artificios [artifacts), sobre el LPS. Para ello se generan características e hipótesis de objetos, realizándose tanto procesamiento bottom-up para simbohzación (características->hipótesis->artificios) como procesamiento top-down de verificación (artificios->hipótesis). Un ejemplo es la construcción de un mapa del entorno extrayendo características lineales a partir de lecturas de sensores ultrasónicos, las cuales son combinadas con información de profundidad para producir hipótesis de objetos tipo pasillo, pared o puerta. Los objetos son comparados con la lista de artificios para su actualización, en caso de coincidencia, o extensión, cuando se detecta un nuevo objeto. Este proceso se denomina anclaje (anchoring). La selección y coordinación de comportamientos la realiza el controlador PRS- 2. Elementos de la Adaptación Computacional: Arquitecturas y Lenguajes 37 Lite {Procedural Reasoning System). Algunas características de este controlador son la capacidad de integración de actividades dirigidas por objetivos y dirigidas por eventos, reactividad o descomposición jerárquica de tareas. Adicionalmente este módulo incorpora capacidades como la gestión de procesos continuos en interacción, un amplio conjunto de mecanismos de control declarativos o el uso de niveles de satisfacción como respuesta tras la realización de una tarea en vez del binomio éxito/fracaso. PRS-Lite se basa en la utilización de esquemas de actividad {activity schema), que se definen como conjuntos ordenados de metas {goal set), integrados a su vez por metas simples. Una meta puede pertenecer a dos categorías básicas; acción o secuenciación. Las acciones son del tipo test, asignación, ejecución, espera por condición o expansión/contracción. Este último tipo permite la descomposición jerárquica, dando lugar a estructuras en árbol. Las metas de secuenciación incluyen saltos, condicionales y paralelización. Se denominan intenciones del sistema al conjunto de esquemas de actividad lanzados. Dentro de ellos, los nodos hojas constituyen los conjuntos de metas actuales, y son los elementos considerados paxa su ejecución en cada ciclo del sistema. 2.5.8. Arquitectura S * Como continuación de sus críticas a los sistemas basados en comportamientos [Tsotsos, 1995], Tsotsos propone la arquitectura S*. Esta arquitectura [Tsotsos, 1997] se basa en la definición del concepto generalizado de mundo externo, para hacer referencia tanto al mundo físico como a las diferentes representaciones internas obtenidas a paxtir del mismo. Cada comportamiento, tanto interno como externo, del sistema se define en base a un modelo SMPA {Sense Model Plan Act) ampliado, constituyendo un ciclo SMPA-W. Estructura Los elementos que integran un ciclo SMPA-W (ver figura 2.11) son los siguientes: World: Este nodo contiene dos representaciones: una ventana de eventos y una ventana de acción. Un conjunto de demonios permanecen activos a la espera de detectar cambios en la ventana de eventos y actúan como disparadores de los comportamientos. 38 2.5. Las Arquitecturas Reboticas Híbridas: Estudio de Casos Figura 2.11: Ciclo SMPA-W de la arquitectura S*. Sense: Elemento que extrae información de la ventana de eventos paxa su transformación. Model: Asociación de modelos a subconjuntos de la información extraída. Plan: Asociación de modelos con comportamientos. Act: Manipulación generada por los comportamientos sobre la ventana de acción. A su vez, cada nodo SMPA posee una estructura interna formada por una ventana de eventos y otra de acción conectadas por medio de un elemento de cómputo que asocia los eventos con las acciones. Esta estructura puede expandirse por medio de ciclos auxiliares, lo que permite una descomposición recursiva. Para ello se conecta una salida desde la ventana de eventos hacia la entrada del nuevo ciclo y se recogen sus resultados en una ventana de acción auxiliar. Un módulo de resolución de conflictos debe entonces decidir qué acción (ventana de acción o ventana de acción auxiliar) se traslada a la salida del nodo. Estos ciclos de expansión toman la forma de implementaciones alternativas para obtener un mismo resultado con mayor precisión y, generalmente, más coste. Una aplicación rebotica precisa de una serie de representaciones: RO de estado, Rl de comandos de actuador, R2 de especificación de la taxea o misión, R3 del entorno, R4 de características extraídas del entorno, R5 de datos de sensores, ER de registro de excepciones, EW de ventanas de eventos y PP de parámetros internos del sistema. Abriendo múltiples ventanas de eventos y acción sobre estas representaciones es posible 2. Elementos de la Adaptación Computacional: Arquitecturas y Lenguajes 39 implementar políticas tales como mecanismos de atención, ajuste dinámico de parámetros o procesamiento dirigido por objetivos. La misión del sistema se define mediante un lenguaje que permite especificar comportamientos para su ejecución secuencial o en paralelo, agruparlos en fases, o definir restricciones temporales. Adaptación Un aspecto importante es la posibilidad de evaluar si una red de comportamientos puede satisfacer las restricciones de tiempo de ejecución impuestas a la misión. Para ello se define un procedimiento de verificación que parte de la asignación a cada comportamiento de una serie de costes: tiempo de ejecución en función del tamaño de la entrada, tiempo de escritura en la ventana de acción, coste incremental de los comportamientos extendidos y ventana de eventos mínima requerida. Este esquema constituye en realidad un test de aceptación para el peor caso, pero no se exponen mecanismos de adaptación en caso de que el test falle. 2.5.9. Arquitectura multinivel y control experto Se trata de una arquitectura híbrida en tres niveles que pretende dar soporte a problemas de distinta naturaleza, desde misiones de alto nivel a comportamiento reactivos. Esta propuesta es debida a Christensen y Pirjanian [Christensen y Pirjanian, 1997], y se ha ensayado sobre plataformas móviles en aplicaciones de navegación con evitación de obstáculos. Estructura En el primer nivel se ubican los comportamientos reactivos. Se trata de conductas básicas de bajo nivel que operan directamente sobre datos de sensores y proporcionan respuestas en tiempo real. Estos comportamientos son autónomos y tienen prioridad sobre los niveles superiores, que simplemente pueden activarlos o desactivarlos. En el nivel intermedio se sitúan los comportamientos de tarea, encargados de llevar a cabo acciones de navegación y detección y seguimiento de objetos. El nivel alto se encarga de la planificación de las misiones, descomponiendo el objetivo indicado por el usuario en una serie de tareas a ejecutar. Cuando alguna de las tareas fracasa, se busca una planificación alternativa. 40 2.5. Las Arquitecturas Robóticas Híbridas: Estudio de Casos Cada comportamiento se modela como una máquina de estados finita, y la combinación de los mismos como un sistema de eventos discretos (DES [Cassandras, 1993]) aplicados a robótica [Kosecka y Bajcsy, 1993] [Kosecka et al, 1995]. Esto permite la construcción de comportamientos de forma modular y jerárquica, así como predecir la controlabilidad de los mismos. Para la descripción de la combinación de comportamientos se emplea el modelo de autómata de procesos, siguiendo la propuesta de los esquemas robóticos de Lyons (ver sección 2.6.3). Pueden definirse relaciones de secuencialidad, concurrencia, condición, inhibición o recursión. El planificador se constituye como un sistema basado en reglas que realiza búsquedas ponderadas en estructuras de grafo con atributos. Estos atributos representan, para cada ubicación, el conjunto de conductas de navegación que deben ser activadas. El planificador hace uso de dos tipos de información: Modelos formales de los comportamientos: Modelo DES, precondiciones, condiciones de operación y postcondiciones. Mapa a priori del entorno: Información topológica. La descripción de la topología y la funcionalidad de los comportamientos es codificada como conocimiento declarativo para mejorar la adaptabilidad y escalabilidad del sistema. 2.5.10. Arquitectura GLAIR GLAIR {Grounded Layered Architecture wüh Integrated Reasoning) es una arquitectura de tres niveles basada en comportamientos. La propuesta [Hexmoor et al., 1992] se basa en una organización de comportamientos desde niveles básicos de acciones reflejas inconscientes hasta niveles altos de comportamientos deliberativos, dando lugar a un pirámide de comportamientos similar a las utilizadas en disciplinas como Visión por Computador para reducir el volumen de la información a manipular. Esta arquitectura se ha probado tanto a nivel de simulación como en implementaciones sobre robots reales [Hexmoor et al., 1993]. Estructura GLAIR está formada por tres niveles (ver figura 2.12): 2. Elementos de la Adaptación Computacional: Arquitecturas y Lenguajes 41 Nivel ae Conocimiento (consciente) Nivel PereeptoMotor (ineotisdeute) Nivel SensorAetuaáor (inconsciente) > Fltqo de control — —• Fhijo de datos —^^ Enlace Figura 2.12: Niveles de la arquitectura GLAIR. • Nivel de conocimiento o KL (Knowledge Level). • Nivel percepto-motor o PML {Perceptuo-Motor Level). • Nivel sensori-actuador o SAL [Senso-Actuator Level). El nivel KL constituye un nivel de planificación que opera sobre objetos de alto nivel, metas, eventos y estados. Este nivel se enlaza parcialmente con el nivel inferior, el PML, donde se manejan representaciones con un mayor nivel de detalle. En el PML se sitúan comportamientos intermedios sobre los que se aplican técnicas de aprendizaje para acabar convirtiéndolos en comportamientos automáticos. En el nivel más bajo, el SAL, se sitúan las acciones reflejas que operan de forma autónoma. En GLAIR se propone una clasificación de los comportamientos en cuatro tipos: Reflejos: Operan como ciclos cerrados de percepción-acción, simulando acciones reflejas. Reactivos: Precisan un nivel mínimo de procesamiento, aunque operan a nivel subconsciente. Equivalen a comportamientos aprendidos. Situados: Requieren un mayor nivel de procesamiento, con análisis del estado interno y externo. Deliberativos: Comportamientos de alto nivel con etapas de procesamiento y razonamiento. 48 2.7. PROCOS Importantes grupos de investigación dan soporte a este proyecto, incluyendo entre ellos el KTH (http://cogvis.nada.kth.se/orocos/), el LAAS (http://www.laas.fr/ maUet/orocos/) o el FAW (http://wwwl.faw.uni-ulm.de/orocos/). Actualmente, los esfuerzos se concentran en el desarrollo de la infraestructura de base: comunicaciones y primeros componentes para control de bajo nivel. Capítulo 3 Propuesta de Sistema Percepto-Efector Distribuido En este capítulo se describe el modelo arquitectónico de sistema percepto-efector distribuido propuesto en esta tesis. Se realiza una descripción del mismo tanto desde el punto de vista estructural como funcional. 3.1. Introducción: Objetivos de Diseño Los sistemas percepto-efectores abordan aplicaciones que van siendo cada vez más exigentes. Ello implica una creciente complejidad que precisa de técnicas y herramientas de programación específicas para garantizar el éxito de los desarrollos a largo plazo. Las aplicaciones "ad hoc", aunque efectivas en muchos casos, dejan de ser interesantes cuando se intenta su extensión o su traslado a otros contextos. Los principales objetivos que se persiguen en este enfoque a largo plazo son múltiples. Así, en la fase de especificación o diseño de las aplicaciones podemos hablar de: Facilitar el diseño: Deben ofrecerse al desarroUador elementos de construcción claramente definidos que ayuden a diseñar las aplicaciones de una manera rápida y sistemática. La separación de los aspectos relacionados con el control, las comunicaciones y la propia funcionalidad de los elementos o módulos de un sistema aporta ventajas como las siguientes: • Evita errores de programación en las comunicaciones (normalmente muy difíciles de depurar), lo que incide en una mayor robustez. 49 50 3.2. Estructura del Sistema • Permite establecer estrategias de control y adaptación - que como se verá - son independientes de los objetivos funcionales de cada módulo y, por tanto, genéricos. Reutilización del código: La transferencia de resultados entre diferentes equipos de investigación contribuye a la consolidación de etapas y acelera la consecución de nuevas metas. Para la fase de ejecución de las aplicaciones resultan interesantes los siguientes aspectos: Reactividad: Se persiguen sistemas que respondan con rapidez a los estímulos que se reciban del entorno. Robustez: Las condiciones de funcionamiento de este tipo de sistemas son a menudo adversas y cambiantes, lo que demanda mecanismos de tratamiento de excepciones y adaptación. Los objetivos expuestos han guiado el diseño y la implementación de un sistema percepto-efector distribuido. Se trata de un sistema de propósito general, que permite dar soporte a diferentes tipos de aplicaciones, desde las más simples monotareas hasta aplicaciones jerárquicas distribuidas. En este capítulo se realiza una descripción detallada del sistema propuesto a nivel básico, tanto desde un punto de vista estructural como funcional. Se dejan para capítulos posteriores los apartados del control/adaptación y el aprendizaje. 3.2. Estructura del Sistema Ante la diversidad de campos de aplicación y la variedad de hardware y software implicados en los sistemas percepto-efectores, se persigue una estructura fácilmente extensible a múltiples máquinas que no imponga restricciones a priori sobre la arquitectura finalmente implementada. El sistema percepto-efector que se propone está integrado por un conjunto de elementos modulares que se componen para dar lugar a diferentes entidades funcionales a distintos niveles. Estos elementos básicos incorporan unidades de procesamiento, comunicaciones y control, pudiendo interconectarse entre sí para configurar diferentes arquitecturas. 3. Propuesta de Sistema Percepto-Efector Distribuido 51 Datos/Hes. Figura 3.1: Módulo genérico BU-TD-COM. 3.2.1. Los módulos BU-TD-COM El sistema se estructura en elementos modulares genéricos denominados módulos BU-TD-COM (figura 3.1). Estos elementos pueden considerarse como bloques básicos en la construcción de una aplicación. Cada módulo BU-TD-COM está a su vez constituido por las siguientes unidades: • Una unidad de procesamiento (Bottom-Up o BU). • Una unidad de control (Top-Down o TD). Una unidad de comunicaciones (COM). Los módulos BU-TD-COM derivan de una serie de trabajos previos [CabreraGámez, 1994] en el área de la visión por computador y de los sistemas basados en conocimiento [Hernández-Sosa et al, 1999]. Las ideas allí expresadas se extienden ahora al caso de sistemas percepto-efectores genéricos. La estructura modular permite una clara separación entre los aspectos de procesamiento, control y comunicaciones que es altamente deseable en cualquier sistema percepto-efector. Esta estructura permite asimismo construir sistemas jerárquicos multinivel con diferentes configuraciones, manteniendo, sin embargo, la misma organización interna. 52 3.2. Estructura del Sistema La unidad BU La unidad de procesamiento o BU se encarga de transformar la información que recibe como datos de entrada en resultados. Estos resultados pueden estar dirigidos bien a otras unidades de procesamiento o hacia efectores finales. La transformación de datos realizada en estas unidades puede ser de naturaleza diversa, tales como la obtención de lecturas directas de los sensores físicos, las transformaciones numéricas sobre las mismas, o las operaciones de simbolización o procesamiento de datos simbólicos. La función concreta que se desempeñe en una unidad BU dependerá del código que se cargue en la misma para su ejecución. Desde esta perspectiva, una unidad BU puede considerarse una unidad de procesamiento genérica, cuya función concreta depende de las instrucciones que ejecute. El código de las unidades BU, como se explicará en detalle en la descripción funcional, consta de una sección de inicialización que se ejecuta al activarse el módulo, una sección principal, una sección de error para situaciones de fallo, y una sección de finalización que se ejecuta al desactivarse el módulo. La unidad TD La unidad de control o TD es la responsable de verificar el buen funcionamiento del módulo, supervisando la operación de las unidades BU y COM. Estas funciones incluyen el control de la correcta inicialización y finalización del módulo, la monitorización de la frecuencia de ejecución, la detección de bloqueos y otros errores. También se encarga de distribuir la información de estado hacia niveles de jerarquía superiores o de trasladar señales de control hacia módulos subordinados. Para responder a estos objetivos, el TD se estructura por un lado como un proceso de control que se activa periódicamente (en forma de watchdog), y por otro como un bucle de atención de mensajes para atender a las señales que se reciban. La unidad COM La unidad de comunicaciones o COM es la encargada de distribuir los datos desde los productores a los consumidores dentro del sistema. Esta transferencia puede tener carácter local o remoto en función de que el destinatario se encuentre o no en la misma máquina, y se realiza de forma concurrente con el procesamiento (BU) y el control (TD). 3. Propuesta de Sistema PerceptoEfector Distribuido 53 3.2.2, Flujos de información El intercambio de información dentro del sistema emplea diferentes mecanismos, siendo lo habitual la utilización de memoria compartida para las comunicaciones internas al módulo y las señales para las comunicaciones entre módulos. Las señales difundidas a través del sistema se establecen según los tres tipos siguientes: • Señales de datos. • Señales de control. • Señales de estado. Las señales de datos son usadas para transferir el resultado del procesamiento de las unidades BU a otros módulos. La unidad de comunicaciones conduce estas señales desde los módulos productores a cada uno de los módulos consumidores para su procesamiento. Las señales de control contienen comandos dirigidos desde los módulos con mayor jerarquía hacia módulos de nivel inferior con el objeto de configurarlos o alterar su funcionamiento. Por último, las señales de estado son las encargadas de notificar diferentes eventos desde niveles inferiores hacia los controladores de niveles superiores para su análisis, o simplemente son usadas para difundir información de estado a través de todo el sistema. En la figura 3.1 se muestran estos flujos de señal en el entorno de un módulo BU-TD-COM genérico. 3.2.3. Infraestructura Todo el sistema ha sido desarrollado utilizando como soporte un sistema de comunicación y control para sistemas distribuidos basado en agentes. Esta infraestructura permite la definición de los módulos, las unidades y las señales intercambiadas entre ellos de forma cómoda y sistemática. Cada unidad es implementada como una hebra independiente, lo que permite respetar los principios de independencia funcional y modularidad sin por ello perder la capacidad de disponer de diferentes mecanismos de intercambio de información. En la siguiente sección se describe la capa de bajo nivel y su utilización en el soporte del sistema propuesto. 54 3.3. Infraestructura de Desarrollo: Comunicaciones y Control 3.3. Infraestructura de Desarrollo: Comunicaciones y Control El desarrollo del sistema está soportado por un sistema de comunicaciones y control (en adelante SCC) que modela esquemas de control como un conjunto de entidades o agentes débilmente acoplados que interactúan entre ellos [Domínguez-Brito et al., 2000]. El mecanismo de interacción empleado paja comunicar entre sí a los agentes son las señales. Cada señal transporta información desde el agente que la envía hasta el que la recibe, permitiéndose una comunicación sin restricciones (todos con todos). Aunque inicialmente empleado para la implementación de esquemas de control paxa sistemas de visión activa, este entorno puede extenderse de forma natural a otro tipo de sistemas, como es este caso. El objetivo del SCC es permitir la definición del comportamiento del sistema global y el de los agentes individuales empleando señales. Para cada agente es posible modelar tanto su actividad individual como las interacciones con otros agentes, lo que a su vez define el comportamiento de todo el sistema en su conjunto. El SCC sistematiza la definición de los agentes, qué señales se reciben y qué acciones tomar en respuesta a las mismas. Asimismo se modela la definición de las propias señales y la información que transportan. Se proporcionan esqueletos tanto para los agentes como para las señales, de forma que únicamente es necesario rellenar determinadas secciones de código para alcanzar un sistema en estado operativo. La herramienta realiza de forma transparente el acceso en paralelo o de forma concurrente a los datos compartidos, de forma que los desarroUadores no tienen que preocuparse por este aspecto. Toda esta funcionalidad hace uso de los recursos típicos que proporciona un sistema operativo multitarea. En sistemas monoprocesador, el paralelismo entre agentes se alcanza por medio de la concurrencia. En sistemas multiprocesador o en sistemas distribuidos, el paralelismo se aprovecha de forma natural distribuyendo los agentes existentes entre los procesadores disponibles. El SCC permite la asignación de prioridades a cada agente, de forma que pueden definirse jerarquías. Así, es posible asignax prioridades más elevadas a agentes que desempeñan tareas de bajo nivel frente a los que realizan tareas de alto nivel. Otro ejemplo es la priorización de los agentes con baja latencia frente a los que presentan una latencia elevada. En resumen, esta herramienta permite modelar esquemas de control para sistemas percepto-efectores apoyándose en el concepto de agentes que se comunican por medio de 3. Propuesta de Sistema Percepto-Efector Distribuido 55 señales. Una vez el sistema ha sido diseñado, simplemente deben rellenarse los esqueletos de los agentes con las respuestas a las diferentes señales y los esqueletos de las señales con los datos transportados. Como demostración práctica se han desarrollado diferentes sistemas de seguimiento visual [Hernández-Tejera et al., 1999] y aplicaciones en robótica móvil [Cabrera-Gámez et al., 2000]. Esta herramienta se enmarca en un proyecto en pleno desarrollo al que se van añadiendo regularmente nuevas mejoras. El resultado más reciente es la versión denominada CoolBot [Cabrera-Gámez et al, 2001] [Domínguez-Brito et al, 2002]. 3.3.1. Tipología de agentes En el SCC se distinguen los siguientes tipos de agentes: Agentes fuente: No reciben señales, excepto las de inicio y final. Actúan sólo como emisores de datos, que normalmente corresponden a los suministrados por los sensores del sistema. Agentes destino: No envían señales, limitándose a recibirlas. En general están asociados con componentes efectores, a los que envían comandos generados a partir de las señales que reciben. Agentes genéricos: Pueden tanto enviar como recibir señales, sin restricción alguna por parte de la arquitectura. Agentes distribuidores: Permiten definir "buses virtuales" en el sistema. Su objetivo es únicamente distribuir las señales a través de los agentes, y sólo tienen sentido cuando una misma señal debe ser recibida por múltiples agentes. Agentes de red: Desempeñan un papel equivalente a los distribuidores pero para el caso de sistemas distribuidos, en los que las señales pueden ser enviadas entre agentes que residen en máquinas diferentes. 3.3.2. Tipología de señales El SCC proporciona diversos tipos de señales: Señales de inicio y fin: Son señales que no transportan información. La señal de inicio se emite cuando empieza la ejecución del sistema, y la de fin cuando la 56 3.3. Infraestructura de Desarrollo: Comunicaciones y Control ejecución termina. Ambas señales están dirigidas a todos los agentes del sistema, al tratarse de señales por defecto que son aportadas por la arquitectura de forma transparente. Señales tipo timer: Esta señales son periódicas y pueden programarse para que el agente desarrolle algún tipo de actividad a intervalos regulares. Son definidas transparentemente por la arquitectura y no transportan información. Señales genéricas: Constituyen el resto de señales del sistema y pueden ser definidas libremente por el usuario con propósito general. 3.3.3. Guías de diseño Para usax el SCC en un sistema real debe llevarse a cabo primero un análisis del sistema a implementar. Deben identificarse los agentes, su número, su tipo, etc. Posteriormente han de definirse todas las señales que van a utilizarse, la información que transportan, su origen y su destino. En general, pueden considerarse las siguientes recomendaciones a lo largo de este proceso: 1. Los agentes se corresponden con entidades que poseen objetivos propios. 2. Los agentes interactúan entre ellos y con su entorno, dando lugar al comportamiento global del sistema. Las señales deberían modelar este comportamiento. 3. Típicamente los distribuidores se asocian a señales de elevada frecuencia. 4. Las prioridades elevadas se asignan a agentes de bajo nivel o elevada frecuencia de ejecución y las prioridades bajas a los agentes de alto nivel o baja frecuencia. El problema fundamental se centra pues en las fases previas a la implementación, en las que deben identificarse acertadamente los agentes que van a formar parte del sistema y las señales que necesitan intercambiarse para obtener el comportamiento deseado. 3.3.4. Implementación del sistema percepto-efector La concepción modular del diseño de nuestro sistema facilita enormemente su desarrollo sobre el SCC. En esta implementación se han utilizado agentes genéricos 3. Propuesta de Sistema Percepto-Efector Distribuido 57 para la definición de las unidades BU, TD y COM. Además, se hace uso de los agentes distribuidores y de los agentes de red en implementaciones distribuidas. Se han utilizado todos los tipos de señales disponibles: de inicio y fin, genéricas y tipo timer. Las señales de inicio y fin se utilizan en el arranque y la parada del sistema, mientras que las señales genéricas transportan señales de datos, control y estado a través del sistema en ejecución. Las señales se envían directamente entre módulos cuando el origen y el destino son simples, y por medio de distribuidores cuando la misma señal debe llegar a diferentes módulos. Esta última característica es muy interesante a la hora de comandar múltiples módulos de forma simultánea con una gran eficiencia y sin introducir sobrecarga en el sistema. Las señales tipo timer se utilizan para implementar bucles de control internos a cada módulo, tanto para fijax frecuencias de control como de operación. Se ha comprobado que el overhead introducido por el control de bajo nivel del SCC sobre el sistema final es mínimo, lo que hace que éste no sea un factor determinante en la escalabilidad de las aplicaciones. 3.4. Descripción Funcional del Sistema La organización funcional del sistema debe alcanzar un equilibrio entre nivel de abstracción y flexibilidad. Por un lado, resulta beneficioso ofrecer al diseñador elementos funcionales que le liberen de tratar con detalles de bajo nivel, lo que permite concentrar los esfuerzos en el diseño de la aplicación. Por otra parte, un nivel excesivo de normalización resta libertad en el desarrollo, limitando los recursos de programación disponibles. La organización funcional del sistema percepto-efector que proponemos se basa en la siguiente jerarquía de objetos (ver ejemplo en la figura 3.2): • Estados. • Tareas. • Módulos funcionales: Supervisores, sensores, diagnósticos, acciones y actuadores. Los módulos funcionales son las unidades funcionales básicas reconocidas por el sistema. La combinación de los módulos da lugar a las tareas, donde se coordina la ejecución simultánea de varios de ellos. Por último, los estados agrupan a conjuntos de tareas que deben estar activas al mismo tiempo. 64 3.4. Descripción Funcional del Sistema Control Actuador Planta Sensor Figura 3.8: Diagrama de un control en bucle cerrado clásico. 3.4.2. Módulos funcionales Los diferentes tipos de módulos funcionales surgen a partir de la descomposición funcional de las tareas. El objetivo es alcanzar una mayor modularidad en la definición de las tareas, lo que permite sistematizar el desarrollo de las aplicaciones a costa de restar algo de libertad en el diseño. Desde la perspectiva de la claridad de los diseños y la reutilización del software, la conveniencia de esta descomposición está plenamente justificada. A efectos descriptivos, se puede establecer una analogía comparativa entre una tarea y un sistema de control en lazo cerrado clásico (figura 3.8). Los elementos sensor y actuador del bucle de control tienen una correspondencia directa con los sensores y actuadores que incorpora un sistema percepto-efector y que forman parte de las tareas que éste realiza, como es el caso de los sensores y los actuadores de un robot. En el bucle de control, sin embargo, se asume que el sensor suministra los datos necesarios para incorporarlos directamente a la estrategia de control. En el contexto de un sistema percepto-efector ésta es una visión simplificada, puesto que los datos suministrados por un mismo sensor pueden servir como punto de partida para diferentes tareas, que realizan distintos tipos de procesamiento sobre esos datos. El controlador, por su paxte, es quien dicta la estrategia de control, estableciendo las características particulares de cada bucle. Para una tarea, el controlador debe estar representado por un elemento que determine las características de la acción y su evolución. En sistemas de control multilazo jerárquicos, la coordinación entre los diferentes 3. Propuesta de Sistema Percepto-Efector Distribuido 65 bucles viene representada por supervisores de alto nivel. Análogamente, en el sistema propuesto deberán existir elementos similares para mantener la cohesión y la integridad del conjunto. Por otra parte, consideramos interesante disponer de un mecanismo de comunicación con el sistema cercano al lenguaje natural. Una descripción de tareas en forma de combinaciones de verbo más objeto contribuye a una mayor claridad en la secuencia de comandos, haciéndola más legible. Los verbos son asimilables a la secuencia de control en los sistemas percepto-efectores, mientras que el objeto está relacionado con las percepciones del sistema. Los sensores representan los dispositivos que suministran los datos necesarios para identificar a los objetos en el entorno, mientras que los actuadores son los elementos motores que hacen operativos a los verbos. Esta organización deja la puerta abierta para la incorporación de modificadores de tipo intensificación o atenuación sobre los verbos y los objetos. En base a la discusión anterior, se definen los siguientes módulos funcionales como objetos básicos en el sistema que se describirán posteriormente en detalle: • Sensores. • Diagnósticos. • Acciones. • Actuadores. • Supervisores. La asociación sensor-diagnóstico está relacionada con los sensores en control clásico y con los objetos en términos lingüísticos, mientras que el conjunto acción-actuador se corresponde con las funciones de comparación y el controlador en control clásico y con el verbo desde la perspectiva del lenguaje natural. Esta separación de la acción y el objeto de la acción facilita de forma directa la modularidad y la reutilización del código. Por ejemplo, puede pensarse en múltiples acciones que se lanzan sobre el mismo objeto, o bien, múltiples objetos que son los destinatarios de la misma acción. Los módulos estructurales BU-TD-COM son los encargados de hacer operativos estos módulos funcionales, de modo que puedan interconectarse entre sí para construir las tareas que el sistema deba desempeñar. Desde esta relación con los objetos del sistema, un módulo puede encontrarse en uno de los estados que se muestran en la siguiente tabla: 66 3.4. Descripción Funcional del Sistema Estado "IDLE" "READY" "RUNNING" "ERROR" "SUSPENDED" Descripción No se le ha asignado ningún objeto Preparado para la ejecución de un cierto objeto Ejecutando el código asignado Situación de error Ejecución temporalmente detenida Tabla 3.1: Descripción de los estados posibles para los módulos del sistema. /susPE.Nrim • i/:ii('r Figura 3.9: Diagrama que muestra las relaciones existentes entre los estados posibles de los módulos del sistema. La figura 3.9, ilustra los diferentes estados junto con las transiciones que se pueden dar entre ellos. Así, un módulo parte del estado "IDLE" y pasa al estado "READY" cuando se le asigna un objeto determinado para su ejecución. Del estado "READY" se puede pasar bien al estado "RUNNING" para iniciar la ejecución, al estado "IDLE" para desasignar el módulo, o al estado "ERROR" si se ha producido algún error durante la iniciahzación. Por último, del estado "RUNNING" se vuelve al estado "READY" cuando finaliza la ejecución, se pasa al estado "SUSPENDED" si la ejecución debe interrumpirse temporalmente, o se pasa al estado "ERROR" si se detecta una situación anómala. La transición a cada estado viene determinada por señales externas de control de los supervisores, salvo en el caso del estado "ERROR", al que se puede llegar y del que se puede salir mediante eventos detectados localmente. Una vez configurados, tendremos módulos sensores, módulos de diagnóstico, módulos de cómputo de acciones, módulos actuadores y módulos supervisores. El código que se ejecuta en cada uno de estos módulos funcionales se organiza en cuatro secciones: 3. Propuesta de Sistema PerceptoEfector Distribuido 67 • Sección de entrada. • Sección principal. • Sección de error. • Sección de salida. La sección de entrada está formada por el código de inicialización del módulo funcional, y consta de rutinas de apertura de dispositivos, reserva de memoria, etc. Es el código que se ejecuta al pasar al estado "READY". La sección de salida contiene código de liberación de recursos y cierre de dispositivos, y se activa al pasar al estado "IDLE". La sección principal es la que contiene el código que se ejecuta, normalmente de forma repetitiva cuando el módulo funcional se encuentra en ejecución, esto es, en el estado "RUNNING". Por último, la sección de error está integrada por los mecanismos de recuperación en caso de fallo. Normalmente, el usuario sólo necesita programar la sección principal, dejando que sea el sistema el que aplique las acciones por defecto para el resto de las secciones. De todas formas, siempre es posible incluir código del usuario en aquellos módulos que precisan condiciones adicionales para su puesta en funcionamiento o recuperación. Los sensores Los sensores son elementos que proporcionan datos de entrada de naturaleza fundamentalmente numérica al sistema. Normalmente están asociados a dispositivos reales del tipo cámaras, anillos de ultrasonidos, detectores infrarrojos, sensores de contacto, sensores de temperatura. Estos dispositivos son encapsulados de forma que los detalles particulares quedan recogidos en los controladores de bajo nivel, de forma que su manipulación a alto nivel se presenta homogénea. Dentro del módulo BU-TD-COM asignado al sensor, la unidad BU ejecuta un código, generalmente muy simple. En la sección de entrada se inicializa el dispositivo físico y se configura para la adquisición. También se reservan los recursos necesarios para la ejecución del código del sensor. En la sección principal se realizan peticiones de datos al sensor y se formatean para su distribución por el sistema, repitiéndose la secuencia a una frecuencia de funcionamiento determinada. La sección de finalización cierra el dispositivo sensor, liberando los recursos captados. La unidad de comunicaciones es notificada cada vez que se genera un nuevo dato y se encarga de su distribución a todos los módulos de cómputo de diagnósticos conectados al sensor. 68 3.4. Descripción Funcional del Sistema La unidad de control comprueba periódicamente el estado del sensor físico y la frecuencia de operación. Si se detecta algún error se intenta solventar a nivel local o, si esto no es posible, se notifica a los niveles superiores. Los diagnósticos Los diagnósticos son objetos de transformación aplicados a datos de entrada suministrados por sensores o por otros diagnósticos. Los resultados obtenidos son enviados a las acciones para su análisis o a otros diagnósticos para someterlos a un nuevo proceso de transformación. El núcleo de estos objetos está constituido por un algoritmo de procesamiento que opera sobre los datos de entrada. La unidad BU asociada al cómputo de un diagnóstico ejecuta un código de inicialización con el que se reserva la memoria temporal necesaria para el procesamiento. La sección principal cíclica está formada por instrucciones de procesamiento sobre los datos de entrada o sobre resultados temporales. Por último, la sección de finalización libera las zonas de memoria reservadas. La unidad de comunicaciones atiende a dos flujos de información. Por un lado, recibe los datos desde los módulos que suministran la información para el cómputo, y que pueden ser tanto sensores como otros diagnósticos. Por otro, transmite los resultados generados a los módulos consumidores, que pueden ser bien acciones, bien módulos de cómputo de otros diagnósticos. La unidad TD controla la evolución de los tiempos de procesamiento y comprueba si se respeta la frecuencia de operación; además de monitorizar la ausencia de errores y excepciones, tarea común a los TD de todos los objetos del sistema. Las acciones Las acciones son objetos de decisión que generan las diferentes salidas que presentará el sistema en función de los estímulos de entrada. Contienen el código de control que analiza el resultado del procesamiento de los diagnósticos y conduce la evolución de la ejecución del sistema, su actividad. Las acciones constituyen, en realidad, el núcleo de las tareas. En el interior de un módulo BU-TD-COM asociado a una acción, la unidad BU ejecuta las diferentes instrucciones de control presentes en el código, junto con las correspondientes secciones de inicialización y finalización. La unidad COM recibe datos de entrada desde diferentes módulos de cómputo de diagnósticos y envía los comandos 3. Propuesta de Sistema PerceptoEfector Distribuido 69 resultantes del procesamiento de la acción a los módulos actuadores conectados a la misma. La unidad de control, además de guardar la integridad del módulo, tiene en este caso funciones adicionales derivadas de su papel de supervisión de la tarea. Los actuadores Los actuadores son dispositivos de tipo terminal que se asocian con los efectores reales del sistema. Son los encargados de traducir las decisiones de control de las acciones sobre el entorno del sistema percepto-efector. La unidad BU de un módulo actuador ejecuta un código con secciones de entrada y salida, para la inicialización del dispositivo físico y su configuración y la desactivación, respectivamente. En la sección principal se espera por los comandos recibidos desde las acciones y se ejecutan. Las diferentes implementaciones dispondrán de mecanismos para resolver conñictos en caso de existir múltiples fuentes de comandos, pudiendo emplear técnicas como la selección por prioridad, ponderación por voto, fusión difusa, etc. La unidad de comunicaciones es utilizada únicamente en sentido de entrada para canalizar la información que se recibe desde las acciones. Por último, la unidad de control comprueba el correcto funcionamiento del actuador durante la ejecución de la tarea. Los supervisores Los supervisores son objetos encargados de controlar el funcionamiento del sistema en su conjunto. Los supervisores son quienes actúan, además, de interfaz con el usuario, del que reciben las peticiones para la ejecución de tareas. Desde el punto de vista del programador, los supervisores son elementos transparentes que son añadidos de forma automática por el sistema en función de la configuración de estados y tareas que se cargue. A pesar de esto, su comportamiento puede ser modificado a través de un conjunto de parámetros, como es el caso de los mecanismos de adaptación que se verán en el siguiente capítulo. La supervisión se realiza a múltiples niveles: • Nivel de tarea. • Nivel de estado. • Nivel de sistema. 70 3.4. Descripción Funcional del Sistema En el nivel más bajo están los supervisores de la tarea, papel desempeñado por los módulos TD de las acciones. Se encargan de todos los aspectos de monitorización y control ligados al funcionamiento de la tarea como agrupación de módulos. Por encima, están los supervisores de estado, que coordinan la evolución de las tareas pertenecientes al estado de que se trate. Son los responsables de comprobar las transiciones y, en caso de que alguna de ellas se active, enviar las señales correspondientes para que se produzca la transición al estado de destino. En el nivel más alto se encuentran los supervisores de sistema, que interactúan con el usuario y controlan la evolución de los estados que se hayan definido. El esquema habitual consiste en disponer un supervisor por cada máquina sobre la que vaya a distribuirse la ejecución de las tareas, siendo uno de ellos el supervisor principal. Desde el prisma de la implementación, los supervisores pueden verse como módulos BU-TD-COM que ejecutan dos tipos de código: Código genérico: Funciones de monitorización y control que son comunes a todas las aplicaciones, con independencia de su naturaleza. Código específico: Código asociado a las transiciones que se extrae de la definición de los estados suministrada por el usuario. Construcción de tareas Las tareas del sistema son el resultado de la combinación de diferentes módulos funcionales. Las tareas constituyen una asociación de uno o más diagnósticos con una acción en la que los diagnósticos representan la parte de procesamiento y la acción la paxte de decisión. Algunos ejemplos sencillos serían: "sigue color_rojo", "detecta temperatura_alta", etc. La información relativa a todas las implementaciones de objetos conocidas por el sistema se recoge en una base de conocimiento. Esta base de datos almacena las características de cada elemento, sus posibilidades de interconexión, requerimientos, etc. El bucle de control de las tareas se completa, a partir de la información contenida en la base de conocimiento, con los sensores que suministran datos de entrada a los diagnósticos y los actuadores que se comandan desde la acción como salidas. Desde la perspectiva del sistema, la acción es quien gobierna la tarea, desempeñando el papel de supervisor de la misma. La figura 3.10 muestra un ejemplo de una tarea simple y las interconexiones entre los diferentes módulos que la configuran. Para los casos más complejos, la red de sensores y diagnósticos puede crecer y -•'SiP 3. Propuesta de Sistema Percepto-Efector Distribuido 71 Acción Actuador Figura 3.10: Ejemplo de módulos combinados en una tarea simple. expandirse en múltiples niveles, configurando grafos de procesamiento con elementos compartidos entre múltiples tareas. Nada impide, sin embargo, definir tareas altamente reactivas en las que la conexión entre el sensor y la acción es prácticamente directa, lo que garantiza una latencia mínima entre el estímulo y la respuesta del sistema. Otros tipos especiales de tareas son las acciones puras, en las que no se requieren sensores o el cómputo de diagnósticos, como por ejemplo "parada_emergencia". El ciclo normal de operación de una tarea comienza con la generación de datos desde el sensor, que son procesados por los módulos de diagnóstico. Los resultados son analizados en las acciones para decidir qué comandos trasladar a los actuadores. Por encima de este nivel, los supervisores se encargan de controlar la evolución del sistema en su conjunto. 3.4.3. La base de conocimiento La base de conocimiento es el elemento que permite al sistema responder a las peticiones del usuario ejecutando las tareas que se soliciten. En ella se almacena la información relativa a las siguientes entidades: Tipos de objetos: Donde se describen los diferentes tipos de sensores, tipos de diagnósticos, tipos de acciones y tipos de actuadores que conoce el sistema. Son las referencias utilizadas en la descripción de las tareas. Implementaciones de objetos: En este caso se recogen cada una de las im- 72 3.4. Descripción Funcional del Sistema plementaciones alternativas que existen paxa cada uno de los tipos genéricos. Se trata de descripciones operativas que incluyen el código que debe ejecutarse en cada caso por parte de las unidades BU. Tipos de datos: Se realiza una descripción de los diferentes tipos de datos que maneja el sistema. Esta información permite centralizar las referencias que se hagan en cada objeto al tamaño y tipo de datos de entrada y salida. Dispositivos físicos: Consiste en una relación de los controladores que permiten manejar los diferentes dispositivos físicos (sensores y actuadores) conectados al sistema. Tipos de errores: Donde se define la tipología de errores reconocidos por el sistema. La organización en tipos e implementaciones resulta fundamental a la hora de pensar en aspectos del sistema como la adaptación o la robustez. Así, el cómputo de un determinado diagnóstico puede tener versiones adaptadas a diferentes entornos de interior o exterior, y una acción de seguimiento puede consumir más o menos energía en función de las velocidades máximas aplicables a los motores. En caso de fallos de dispositivos, esta cualidad resulta aún más importante, pues permite al sistema hacer uso de implementaciones alternativas que no requieran la presencia de los sensores o efectores dañados. Las condiciones existentes en el momento de la activación guían la selección de las diferentes implementaciones disponibles. Este contexto está formado por la información que el sistema va adquiriendo durante su funcionamiento, y que puede incluir entre otros datos el estado de los sensores y actuadores físicos, o las condiciones y tipo de entorno, como es el caso de los niveles de iluminación y de reserva de baterías. La información de los tipos de objetos permite establecer relaciones de compatibilidad, de manera que tanto las entradas como las salidas de los diferentes tipos de objetos incluyen información de los tipos compatibles. Esta característica simplifica la definición de las tareas del sistema y permite verificar la consistencia de las conexiones establecidas. Por ejemplo, el diagnóstico "obstáculo" puede computarse tanto a partir de sensores de ultrasonidos como de pares estéreo. La organización de los errores dentro del sistema en tipos permite aplicarles diferentes tratamientos en los distintos niveles del sistema. Una vez clasificado, el error puede intentar resolverse a nivel local y, si esto no es suficiente, se puede propagar hacia los niveles superiores. 3. Propuesta de Sistema Percepto-Efector Distribuido 73 3.4.4. Ejemplos de objetos contenidos en la base de datos Se presentan algunos ejemplos, sin ánimo de exhaustividad, para ilustrar la estuctura y forma de los objetos. Tipo de sensor: TS_Visión. • Sensores: S_CámaraA, S_CámaraB. • Tipo de dato: ImageruColor. Tipo de sensor: TSJDistancia. • Sensores: S_UltraS, S_Láser. • Tipo de dato: Mapa_Profundidad. Tipo de diagnóstico: TD_Obstáculo. • Diagnósticos: D_ObsCam, D_ObsUltraS. • Tipo de dato: Mapa_Obstáculos. Tipo de diagnóstico: TD_ColorVerde. • Diagnósticos: D_VerdeInterior, D_VerdeExterior. • Tipo de dato: Imagen_Simbólica. Tipo de acción: TA_SeguirVisual. • Acciones: A_SeguirVFast, A_SeguirVSlow. • Tipo de dato: Comando_Cabeza. Tipo de actuador: TAct_Cabeza. • Actuadores: Act_CabezaA, Act_CabezaB. • Tipo de dato: - Tipos de error: TE_ComDispositivo, TE_TimeOut. 80 3.6. El Sistema en Ejecución ^•i-^ • Figura 3.16: Resultado de la segmentación de la imagen A. Figura 3.17: Resultado de la segmentación de la imagen B. 3.6. El Sistema en Ejecución En el marco de este trabajo se ha desarrollado un prototipo de sistema ajustado a los conceptos estructurales y funcionales que se han propuesto. El prototipo admite la definición ordenada de diferentes tipos de objetos e implementaciones y su composición para dar lugar a tareas. Las tareas pueden agruparse en estados para recibir un tratamiento uniforme. 3.6.1. Comandos de tareas El prototipo admite la definición de tareas agrupadas en estados o de forma individual. Durante la evolución del sistema, las tareas pueden verse afectadas por los siguientes comandos: Registro: Una tarea se da de alta en el sistema. Esto supone por un lado un proceso de verificación de validez de la tarea y, por otro, una reserva de recursos para permitir la posterior ejecución de la misma. Activación: Solicitud de ejecución de la tarea. Suspensión: Petición para detener temporalmente la ejecución de la tarea. Reactivación: Una tarea suspendida puede reactivarse cuando se den las circunstancias adecuadas. 3. Propuesta de Sistema Percepto-Efector Distribuido 81 ~- i»i^ ^ ''Vi'" %- •',• jfc' • • •• • ; • -1:^-. '^ " ' » i sí f i .:. ,, - ••• • 1 Figura 3.18: Segmentos etiquetados como fachada en la imagen A. ^t^^^,4, J Figura 3.19: Segmentos etiquetados como ventanas en la imagen B. Eliminación: Cuando la tarea ya no va a ejecutarse más, se liberan los recursos capturados por la misma y se da de baja. Una tarea se registra en el sistema con un comando tipo "acción -|- diagnóstico" dirigido al supervisor. Este comando va acompañado de dos parámetros, que son el nivel de prioridad que se desea asignar a la tarea y la frecuencia de funcionamiento requerida. A partir de ese momento se inicia el proceso de asignación de módulos BUTD-COM libres de un número máximo de módulos previamente activados y marcados como disponibles. Este esquema viene impuesto por el SCC de bajo nivel utilizado, pero no constituye limitación alguna puesto que los módulos libres no suponen más que una mínima sobrecarga sobre el sistema. El siguiente paso es la selección de implementaciones para que la tarea pueda ser ejecutada. En respuesta a un comando de registro, el supervisor selecciona un módulo libre para el cómputo de la acción, le encarga el resto de la preparación de la tarea, y queda a la espera de recibir el mensaje de que la tarea está lista. El módulo de la acción debe entonces seleccionar una implementación concreta en base al contexto actual de operación, ordenar el cómputo del diagnóstico y de los actuadores, y esperar a recibir la confirmación correspondiente. Pueden darse dos situaciones, que dichos cómputos ya se estén realizando en el sistema para otra tarea o que se trate de elementos nuevos. En el primer caso simplemente hay que comunicar al módulo correspondiente que existe un nuevo destino para el resultado del procesamiento, en el caso del diagnóstico, o un nuevo origen de comandos, en el caso de los actuadores. En el segundo caso es necesario escoger un nuevo módulo para encargarle el cómputo, lo que a su vez supone esperar a 82 3.6. El Sistema en Ejecución Tarea A (nueva) -O-Tarea B Figura 3.20: Ejemplo de secuencia de activación de una tarea. que los módulos elegidos finalicen el proceso. En los módulos de cómputo de diagnósticos, debe seleccionarse una implementación adecuada y comprobar los sensores y/o diagnósticos que se necesitan como datos de entrada. De nuevo puede ocurrir que dichos elementos de entrada estén o no en ejecución en el sistema. En el primer caso se solicita añadir nuevo destino y en el segundo se deben activar nuevos módulos. Una vez completada la asignación de módulos a la tarea comienzan a enviarse los mensajes de confirmación, de los sensores a los diagnósticos, y de los actuadores y los diagnósticos a las acciones. Finalmente, y si no se ha producido ningún error, el módulo encargado de la acción envía la señal de tarea lista al supervisor, que la registra y la marca como preparada para ejecución. En caso contrario, se notifica el error al supervisor para que éste lo traslade al usuario. Las causas habituales de error son la solicitud de acciones o diagnósticos que no están recogidos en la base de conocimiento del sistema, y la especificación de valores no válidos para los parámetros de prioridad o frecuencia. En la figura 3.20, se muestran las señales implicadas en la activación de una tarea en la que todos los módulos a excepción del sensor han debido añadirse al sistema. El sistema puede comandar la ejecución de tareas de forma individualizada o globalmente para un estado y todas las tareas y transiciones asociadas al mismo. La ejecución se inicia por los sensores, que empiezan a generar datos a la frecuencia comandada. A partir de ahí, las diferentes unidades de comunicaciones se encargan de suministrar los datos que va generando cada módulo productor a sus módulos consumí- 3. Propuesta de Sistema Percepto-Efector Distribuido 83 Algoritmo 1 Algoritmo de recálculo de periodos y prioridades por adición de tarea. Leer nuevo periodo (NewPer) y nueva prioridad (NewPrio). Calcular mínimo periodo actual {MinPer) y máxima prioridad (MaxPrio). CamhioConf = falso if MinPer > NewPer then Cambiar periodo módulo. CamhioConf = verdadero end if if MaxPrio < NewPrio then Cambiar prioridad módulo. CamhioConf = verdadero end if if {CamhioConf -= verdadero)k{TipoMod\ = SENSOR) then Enviar señal de cambio de configuración a las fuentes del módulo. end if dores con la frecuencia solicitada por cada uno de ellos. Simultáneamente, las transiciones son analizadas en los supervisores para determinar la evolución del sistema a nivel de estados. 3.6.2. Asignación de prioridades y frecuencias Tanto los valores de prioridad como la frecuencia de funcionamiento asociados a la tarea se van propagando a través de todos los módulos afectados a lo largo de la fase de inicialización. Cuando los módulos son compartidos, debe tenerse en cuenta que los valores de prioridad y las frecuencias de las tareas involucradas pueden no coincidir, con lo que se hace necesario mantener un mecanismo de recálculo de los mismos cada vez que se produce una variación en la configuración del sistema. Así, un módulo productor con múltiples módulos consumidores posee una prioridad que es igual a la mayor de las que corresponden a sus destinos, mientras que su frecuencia de funcionamiento se ajusta a la más rápida de las demandadas. Además de esto, los módulos compartidos deben detectar cuándo dejan de demandarse sus servicios paxa finalizar su ejecución. Los algoritmos 1 y 2 muestran de forma resumida los pasos a seguir en caso de activación y eliminación de tareas, respectivamente. 3.6.3. Control de errores Los errores físicos que pueden detectarse siguen un esquema de propagación jerárquico, de forma que siempre intentan ser resueltos por el supervisor situado al nivel 84 3.6. El Sistema en Ejecución Algoritmo 2 Algoritmo de recálculo de periodos y prioridades por eliminación de tarea. if Ultima conexión eliminada then Enviar señal de finalización a las fuentes del módulo. else Leer periodo (OldPer) y prioridad {OldPrió) de tarea a eliminar Ti. Calcular mínimo periodo (MinPer) y máxima prioridad (MaxPrio) sin considerar Ti. CambioConf = falso if MinPer > OldPer then Cambiar periodo módulo. CambioConf = verdadero end if if MaxPrio < OldPrio then Cambiar prioridad módulo. CambioConf = verdadero end if if {CambioConf == verdadero)k{TipoMod\ = SENSOR) then Enviar señal de cambio de configuración a las fuentes del módulo. end if end if de generación del error y, si no es posible la resolución en ese punto, se traslada al supervisor de nivel superior. Este proceso es posible gracias a la declaxación de los tipos de error dentro del sistema. Algunos ejemplos de tipo de error, organizados por niveles, son los siguientes: • Nivel módulo: • Error de comunicación con dispositivo físico. • Error en la operación del dispositivo físico. • Error de comunicación con unidad BU. • Error de comunicación con unidad COM. • Fallo de memoria. Nivel tarea: • Error irrecuperable en sensor. • Error irrecuperable en diagnóstico. • Actuador no responde. 3. Propuesta de Sistema PerceptoEfector Distribuido 85 Nivel estado: • Error irrecuperable en tarea. • Supervisor de tarea no responde. • ... Nivel sistema: • Error irrecuperable en supervisor. • Supervisor de estado no responde. Los errores detectados a nivel de módulo suponen una transición al estado "ERROR" del mismo. Se aplican entonces las acciones de recuperación suministradas por el usuario, si existen, o las acciones por defecto. Puesto que los errores a este nivel están relacionados normalmente con fallos hardware de dispositivos, las acciones por defecto consisten en tratar de reinicializar el dispositivo un cierto número de veces. Si los intentos de recuperación fracasan, se traslada el error al nivel superior indicando que no ha podido resolverse a nivel local. En el nivel de tarea se puede intentar entonces reemplazar el sensor por uno equivalente, o bien el diagnóstico por otro que suministre la misma salida. Si no puede recuperarse la operatividad de la tarea, se notifica al nivel superior. En el nivel de estado se decide entonces si la tarea es prescindible o si es necesario trasladar el error al nivel superior para una replanificación de la misión del sistema. 86 3.6. El Sistema en Ejecución /-' '<='• Capítulo 4 Adaptación Computacional y Control En este capítulo se profundiza en uno de los aspectos fundamentales en el rendimiento de un sistema percepto-efector, como es su capacidad para ofrecer un comportamiento robusto en un entorno cambiante. A partir de las estimaciones de la carga y los recursos de adaptación disponibles se plantean diferentes técnicas y políticas de control. Los dos últimos apartados están dedicados al multiprocesamiento y el aprendizaje. 4.1. Introducción Uno de los aspectos que se considera fundamental en un sistema percepto-efector es la capacidad para garantizar un comportamiento robusto. Esto implica que en condiciones del entorno cambiantes o incluso desfavorables, la integridad del sistema en primer lugar, y su eficacia en segundo, deben disponer de elementos de salvaguarda. Los mecanismos de adaptación operan sobre el sistema en tiempo de ejecución a fin de conseguir un comportamiento más adecuado en función de una cierta señal de referencia externa. La definición de ese "comportamiento adecuado" deriva de los diferentes problemas a los que debe hacer frente el sistema como son gestionar recursos escasos, conseguir un comportamiento estable, reaccionax ante fallos, reducir el tiempo de respuesta, adaptarse a los cambios del entorno, etc. La concepción y el diseño del sistema propuesto permite hablar de adaptación a dos niveles: alto nivel y bajo nivel. En el nivel más alto, la organización de objetos por tipos permite seleccionar para la misma tarea diferentes implementaciones en función de las condiciones de operación. Algunos ejemplos de adaptación a alto nivel en sistemas 87 88 4.2. Adaptación de la Carga percepto-efectores serían los siguientes: • En el caso de un sistema percepto-efector visual, al cambiar las condiciones de iluminación, el cómputo de algunos diagnósticos como el color pueden requerir el uso de algoritmos diferentes. • Para un sistema percepto-efector visual que admita el trabajo tanto en entornos de interior como de exterior, pueden existir asimismo versiones de código especializadas en cada situación. • El caso de un sistema robótico móvil con cambios en las condiciones de navegación, pasando de corredores a espacios abiertos. En el nivel más bajo, la adaptación se produce manteniendo el código, es decir, conservando las implementaciones ya seleccionadas para cada objeto (sensor, diagnóstico, acción o efector), pero modificando sus demandas computacionales. En este capítulo, nos centraremos en el estudio de los recursos de adaptación de bajo nivel, analizando como caso particular la acomodación a los recursos computacionales disponibles. 4.2. Adaptación de la Carga Nuestro sistema se caracteriza por la ejecución simultánea de múltiples tareas con diferentes frecuencias de funcionamiento y niveles de prioridad distribuidas sobre diferentes máquinas. Cada una de esas tareas, como se detalló en el capítulo anterior, está formada por la interconexión de objetos de tipo sensor, diagnóstico, acción y actuador. A su vez, cada objeto es implementado por un módulo BU-TD-COM, desempeñando la unidad TD de la acción el papel de controlador de la tarea. En un entorno multitarea como el descrito se produce siempre una competencia por recursos comunes que, de no ser gestionada convenientemente, puede conducir a una pérdida de rendimiento en el sistema y, en caso extremo, a un bloqueo del mismo. Ante una situación de escasez de recursos computacionales, el sistema debe reaccionar de modo que las tareas actualmente en ejecución reduzcan su rendimiento en función de su prioridad. Es deseable que esta reducción sea homogénea para evitar desequilibrios dentro del sistema, esto es, situaciones de acaparamiento de recursos por parte de unas tareas frente a otras. Asimismo, se precisan acciones de recuperación para el caso en que las condiciones de funcionamiento mejoren ante un eventual incremento en los recursos 4. Adaptación Computacional y Control 89 disponibles. Como en el caso anterior, también aquí es deseable que el progreso de la acción sea homogéneo. El objetivo es plantear un esquema de adaptación para un contexto de tiempo real blando. Para garantizar una mayor aplicabilidad, se busca que los requerimientos impuestos al hardware y sistema operativo de soporte sean lo menos restrictivos posible. Se evitará, por lo tanto, la utilización de recursos privativos de sistemas operativos de tiempo real o planificadores {schedulers) especializados. Por otra parte, dentro de la estrategia de control, es interesante arbitrar políticas tanto locales como globales. Las primeras permiten mejorar los tiempos de respuesta y reducir los overheads, en tanto que las políticas globales, ofrecen una mejor selección de los objetivos del control. En función de qué factores se consideren más relevantes se podrá optar por unas u otras. 4.2.1. Bucles de control En el marco de trabajo definido son planteables diferentes bucles de control con el objeto de alcanzar un comportamiento adaptativo del sistema en tiempo de ejecución. Cada uno de estos bucles se corresponde con las siguientes señales de referencia básicas: Timeouts: Verificación de la frecuencia de funcionamiento deseada para cada tarea. Supone, en principio, un bucle de control específico para cada tarea. Nivel de carga deseado: Valor de referencia para la carga global del sistema. Constituye un bucle de control global para todo el sistema. Homogeneidad de la carga: Se persigue una distribución temporal uniforme de la carga del sistema. Tiempo de respuesta: Definido como el intervalo que transcurre entre la aparición de un estímulo en los sensores de entrada y la generación de la salida correspondiente en los actuadores finales de la tarea. Los controladores de cada uno de esos bucles son siempre las unidades TD, bien como supervisores de tarea, de estado, o de sistema. La unidad TD es la encargada de la monitorización y el control de la ejecución en cada módulo a nivel local. A partir de la evolución del procesamiento en la unidad BU, la unidad TD de control verifica los tiempos invertidos y toma acciones de control directas o bien notifica los eventos detectados a los niveles superiores. A nivel de tarea el TD de la acción puede asimismo 96 4.2. Adaptación de la Carga Sensor m^ Í:R2' ;:B3: f ':'..•.'\ ir.:-,, • \ (':•••••;•.:.•:' Figura 4.1: Ejemplo de control en calidad - Resolución. Los algoritmos de procesamiento, a su vez, pueden proporcionar resultados con distinto nivel de precisión, lo que también afecta a los recursos computacionales demandados. En este caso, son los módulos de cómputo de diagnósticos los que concentran este tipo de acciones de control, al ser los puntos de mayor consumo de tiempo de CPU dentro del sistema. La promoción consistirá en emplear mayores niveles de precisión en los algoritmos, mientras que con la degradación se forzará la utilización de niveles menores. En el modelo de carga esta acción se traduce nuevamente en una variación del tiempo de procesamiento, aunque en este caso localizado en un módulo concreto cuyo efecto se trasladará al sistema completo. Se trata, pues, de una acción de control orientada a módulos. En base a lo anterior, la aplicación de las acciones de control en calidad está condicionada a que las diferentes implementaciones de sensores, diagnósticos, etc., ofrezcan la posibilidad de trabajar con distintas resoluciones y niveles de precisión. Formalmente, estaríamos considerando un esquema de funcionamiento del tipo procesamiento anytime. Este sistema se basa en la utilización de algoritmos capaces de suministrar resultados en diferentes instantes de tiempo, de forma que la calidad de los mismos crece, hasta un valor máximo, con el tiempo disponible para el procesamiento. Dentro de este tipo de algoritmos se puede hablar de dos aproximaciones [Zilberstein, 1996]: Algoritmos anytime interrumpibles: Suministran un resultado en cualquier instante de tiempo, siempre por encima de un valor mínimo, con caUdad creciente. 4. Adaptación Computacional y Control 97 t í 1 -- 1 --I-- ... -- 1 1 1 rrínnnniiinn Actividad tarea j 1 1 1 1 k. Ffec.l Frec.2 Frec.3 75% 50% 25% k i 1 / ! li ! ! i I / i i i i i . Cai^a deii sistema ! '• • Figura 4.2: Ejemplo de cronograma y nivel de carga en el control en frecuencia. Algoritmos anytime de contrato: Admiten como parámetro de entrada el tiempo disponible para el procesamiento. Transcurrido ese tiempo de ejecución, se garantiza la entrega de un resultado con una calidad determinada. Es posible construir esquemas interrumpibles a partir de algoritmos de contrato [Zilberstein et al., 1999]. Nuestra propuesta de sistema computacional adaptativo se basa en algoritmos anytime tipo contrato, donde el tiempo disponible es aquél que permita a la tarea verificar su frecuencia de funcionamiento. Control en frecuencia Las acciones de control que afectan a la frecuencia de funcionamiento consisten en la alteración del periodo de las tareas, lo que implica una variación en la carga computacional demandada por las mismas (ver figura 4.2). En general, esta acción debe ser usada con precaución, pues puede comprometer la integridad del sistema; por ejemplo, en aplicaciones de detección de obstáculos o en lazos de control que impliquen movimiento. El control en frecuencia es una acción de control orientada a tarea, lo que significa que se aplica simultáneamente a todos los módulos pertenecientes a la tarea afectada. Desde el punto de vista de la implementación, sin embargo, la promoción/degradación en frecuencia es más simple que las acciones en calidad, no imponiendo especiales requerimientos a las tareas que vayan a correr sobre el sistema. Simplemente se incrementa 98 4.2. Adaptación de la Carga Téfé^"í"r Tare^2 Tareas f^. iFT= 1 ! r ttí Figura 4.3: Ejemplo de la influencia del oflPset - Sistema desequilibrado. el periodo de funcionamiento para degradar y se decrementa hasta un valor mínimo (normalmente el especificado por el usuario al lanzar la tarea) para promocional. Considerando el modelo para la carga del sistema, el control de la frecuencia implica una variación en el periodo de la tarea {TU). Con las simplificaciones establecidas, el efecto sobre la carga es proporcional a la variación introducida. Desplaizamiento temporeJ Otra posibilidad estudiada ha sido el análisis de la distribución temporal de la carga en el sistema. Se ha comprobado como esta situación puede provocar la aparición de zonas de congestión, cuando coinciden en el tiempo múltiples tareas, acompañadas de intervalos de baja ocupación de la CPU. La solución al problema consiste en la detección de dichas zonas de congestión y en intentar reducirlas. El desplazamiento en el tiempo de algunas tareas puede suavizar el perfil de carga, manteniendo unos niveles más homogéneos a lo largo del tiempo de ejecución. Este aspecto es interesante, puesto que las violaciones del periodo de funcionamiento de las tareas pueden no deberse a una insuficiencia de recursos computacionales, sino a una distribución de la demanda poco equilibrada. Una ventaja adicional de esta acción de control es la reducción de los retardos debidos a la conmutación de tareas en la CPU. Este hecho, aunque en pequeña escala, contribuye también a decrementar la carga global del sistema. 4. Adaptación Computacional y Control 99 Táfé&r i— rnzun xira n>^^^n j ri—lil—J-n -,.,iniBrea3.0l.....|0i--J-ai-- 1 jCarg^ del ^Istem^ < , 1 1 H— 1 —-r™— —i 1 1 1 -—f1 . j —"--1 1 1 1 —•i —•i i r~ 1 1... -•• Figura 4.4: Ejemplo de la influencia del offset - Sistema controlado. Suspensión/Reactivación Finalmente, y como recurso extremo, el sistema puede decidir que la configuración actual de tareas no es sostenible, con lo que la única solución posible es la suspensión o sustitución de algunas de las tareas demandadas al sistema. En caso de ser suspendidas, dichas tareas podrán ser retomadas cuando las condiciones lo permitan. Lógicamente, la suspensión de tareas sólo es efectiva cuando se aplica a tareas que están en ejecución. En un sistema sobrecargado las tareas con menor nivel de prioridad no tienen ocasión de ejecutarse, por lo que no tiene sentido aplicarles esta acción de control. 4.2.5. Caracterización de la adaptación computacional La evaluación de la calidad de la adaptación de los sistemas puede realizarse a través de diferentes medidas como son su flexibilidad y su progresividad. La primera de las medidas hace referencia a la variación de caxga que sobre el sistema supone ir desde el nivel de máxima degradación hasta el de funcionamiento a pleno rendimiento con calidad máxima. La medida de la flexibilidad tendría la forma siguiente: C — C max ^-^rmn 100 donde Cmax es la carga para la calidad máxima y Cmin la carga correspondiente a la 100 4.2. Adaptación de la Carga 70 -. 60504030I 20 10 O — Carga Real 20 40 60 80 Carga Deseada (%) 100 120 Figura 4.5: Relación entre la carga deseada y la carga correspondiente a los diferentes niveles de calidad del sistema. calidad mínima. Los efectos de la cuantización en los niveles de calidad se traducen en la imposibilidad de alcanzar todos los niveles posibles de carga en el sistema. En consecuencia, se produce un agrupamiento de niveles de tiempos de procesamiento disponibles o carga deseada que se mapean sobre un único valor de tiempo asignado o carga resultante. Asumiendo que el sistema de control es tal que se genera siempre una carga menor o igual a la deseada, se obtiene una gráfica escalonada como la del ejemplo mostrado en la ñgura 4.5. Si se define el grado de utilización de recursos como el cociente entre la carga/tiempo asignado y la carga/tiempo disponible puede trazarse una curva sobre todo el recorrido del sistema. La figura 4.6 muestra esta curva para un sistema sencillo con 5 niveles de calidad distribuidos desde el 10 hasta el 90 % de carga. La progresividad mide la relación que existe entre el tiempo disponible y el tiempo asignado, evaluada sobre un intervalo de carga determinado. Una posible medida consiste en evaluar el área bajo la curva de utilización y compararla con el valor máximo alcanzable. Un sistema con perfiles continuos poseerá una progresividad con valor próximo a la unidad, mientras que un sistema con pocos niveles de calidad disponibles tomará valores cercanos a cero. La fórmula de cálculo es la siguiente: P = Área bajo la curva Área máxima Podemos buscar una expresión simplificada para el caso en que se tengan n ni- 4. Adaptación Computacional y Control 101 1,20 1,00 I ^•^° I 0,60 S 0,40 0,20 0,00 - Uso de recursos \i i^: \ •-^ i^" 20 40 60 Carga Deseada (%) 80 100 Figura 4.6: Efecto de la cuantización en el uso de los recursos disponibles. veles de calidad distribuidos uniformemente (en el caso general no tiene porqué ser así). Tenemos entonces n intervalos de carga de ancho constante AC y extremos representados por los valores de carga Cj. El área puede aproximarse por una sucesión de trapecios de la forma A^ACJ2 1 + Ci-i/Ci ¿=i En el ejemplo de la gráfica de la figura 4.6 el área bajo la curva es de 0.77 unidades, mientras que la fórmula precedente da un valor de 0.8. En general esta aproximación da un buen resultado siempre que los niveles no se encuentren excesivamente dispersos. Como Ci = i X AC, queda A ^ nAC — > - i=i La progresividad es el cociente entre este área y el área máxima (nAC). P = = 1 -tEl producto de las dos medidas nos da un índice de adaptabilidad del sistema lA = F X P. En el ejemplo de la gráfica 4.6, la flexibilidad toma un valor de 0.8, la progresividad vale 0.77, y el índice de adaptabilidad estaría en torno a 0.62 unidades. 102 4.2. Adaptación de la Carga 40 60 Carga Deseada (%) 100 Figura 4.7: Sistema con buena flexibilidad y mala progresividad. El índice de adaptabilidad resultante es 0.25. Algunos ejemplos de situaciones extremas son las que se ilustran en las figuras 4.7 y 4.8. En el primer caso se muestra la gráfica de un sistema con una buena fiexibilidad pero una baja progresividad. La figura 4.8, por el contrario, muestra un sistema con una alta progresividad pero muy poco flexible. En ambos casos, las fórmulas dan como resultado un valor para el índice de adaptabilidad bajo: 0.25 y 0.2, respectivamente. 4.2.6. Calibración del sistema Dentro de los planteamientos generales del problema de la adaptación de la carga podemos hablar de dos situaciones claramente diferenciadas: • Sistema calibrado. • Sistema no calibrado. En el primer caso, los perfiles de rendimiento de las diferentes implementaciones están calibrados, por lo que es posible estimar con antelación la relación que existe entre el tiempo de procesamiento asignado y la calidad de los resultados obtenidos. En el segundo caso, simplemente se dispone de la información relativa a las posibilidades de reducción del coste computacional de cada implementación, pero no su repercusión sobre la carga del sistema. En cada una de las situaciones se plantearán esquemas de control que intentan hacer uso de la información existente. Otro problema interesante es el que 4. Adaptación Computacional y Control 103 1,20 1,00 I 0,80 S 0,60 § 0,40 - 0,20 0.00 i — Uso de recursos 20 40 60 Carga Deseada (%) 80 100 Figura 4.8: Sistema con buena progresividad y mala flexibilidad. El índice de adaptabilidad está en torno a 0.2. se presenta cuando, partiendo de un sistema no calibrado, se va obteniendo información en tiempo de ejecución que permite realizar una calibración online o autocalibración. Describiremos en este capítulo en primer lugar el caso de los sistemas no calibrados, para posteriormente pasar a los sistemas calibrados. Finalmente se plantea la forma de abordar la transición de un sistema no calibrado a otro calibrado. 4.3. Adaptación Computacional en Sistemas no Calibrados En un sistema no calibrado, no se dispone de información detallada acerca de la relación que existe entre la carga y el nivel de calidad de cada módulo. Simplemente se conocen para cada módulo sus posibilidades de degradación. La ordenación de la degradación dentro del sistema se basa en asumir un comportamiento homogéneo entre diferentes módulos situados en niveles de degradación iguales. Esto es, se supone que a saltos iguales en los niveles de degradación de los diferentes módulos se originan variaciones similares en la contribución a la carga total del sistema. 104 4.3. Adaptación Computacional en Sistemas no Calibrados 4.3.1. Niveles de degradación Como ya se ha expuesto con anterioridad, resulta indispensable arbitrar mecanismos que eviten situaciones de monopolio o acumulación de recursos por parte de ciertas tareas frente al resto. Por ello se ha diseñado un esquema de organización de los niveles de degradación/promoción de cada módulo en el sistema en base a umbrales de homogeneidad utilizados tanto a nivel local como global. Dichos umbrales consisten en dos límites, inferior y superior, que indican cuáles deben ser los niveles de degradación mínimos y máximos que pueden presentar en un momento determinado los módulos que se encuentran en ejecución en el sistema. El uso de estos umbrales se detallará más adelante. Cada alternativa de implementación para los diferentes objetos dentro del sistema es declarada con los niveles de degradación disponibles, los cuales hacen referencia a las posibilidades de reducción de la carga computacional existentes en cada caso. Así, para el caso de la degradación en calidad, un sensor se registrará con los diferentes tamaños de datos de sahda que puede suministrar, un diagnóstico con sus niveles de precisión, etc. Dentro del sistema se definen un conjunto de niveles de operación estándar, de forma que todos los módulos son comparables entre sí en base a una escala común. Hay que tener en cuenta que en un sistema real no cabe esperar un número de niveles de calidad elevado para las diferentes implementaciones. Esto hace que las acciones de control provoquen un comportamiento a saltos discretos, por lo que no todos los niveles de carga van a ser alcanzables. 4.3.2. Políticas de control Partiendo de la base de las medidas de carga explicadas anteriormente, el sistema debe hacer operativas políticas de control que coordinen las respuestas del sistema ante las diferentes señales de entrada posibles. Describiremos a continuación la implementación de una política de control que combina las acciones de regulación disponibles en el sistema. Los eventos considerados como causas de la activación de las distintas acciones de control son los siguientes: • Aparición de timeouts dentro del sistema. • Diferencias entre la carga deseada y la carga actual. 4. Adaptación Computacional y Control 105 • Distribución no homogénea de la carga. Los bucles de control definidos hacen referencia al control de las violaciones temporales, el mantenimiento de un nivel de carga predeterminado y la estabilización del sistema. Criterios de selección de candidatos La eficacia de la adaptación depende en gran medida de los criterios que se apliquen a la hora de seleccionar alguna tarea o módulo candidato para la promoción/degradación. Dentro de las acciones de control en calidad, la reducción del tamaño de los datos tiene un efecto más rápido, aunque también más violento, sobre la carga del sistema, mientras que con el uso de niveles de precisión inferiores se produce una acción de control más paulatina. En el caso de la promoción/degradación de diagnósticos, el efecto depende además de que la contribución de ese módulo a la caxga del sistema sea significativa, esto es, que presente un tiempo de procesamiento elevado en relación con su periodo. La topología afecta igualmente a la magnitud de las correcciones, de modo que un sensor cuyos datos de salida se suministran a módulos de cómputo de diagnósticos tiene tanta más relevancia como elemento de descarga del sistema cuanto mayor es el número de dichas conexiones. La frecuencia de operación de cada tarea también condiciona el resultado de la acción de control aplicada, siendo lógicamente las respuestas más rápidas e intensas las que se obtienen al degradar las tareas con frecuencias más elevadas. Otra característica a considerar nuevamente es el hecho de que no todas las tareas cargan igualmente al sistema, por lo que conviene buscar tareas con un elevado tiempo de procesamiento en relación con su tiempo de ciclo si se desea conseguir un mayor impacto. En los experimentos realizados, que se muestran en el capítulo 5, se han seleccionado generalmente las acciones de control más intensas, comenzando por los módulos de sensores para pasar luego a los módulos de cómputo de diagnósticos. Introducción de nuevas tareas Otro problema a considerar es la introducción de una nueva tarea dentro de un sistema ya estabilizado. Esta situación puede ser tratada de forma homogénea como una perturbación en la carga del sistema, dejando que las propias políticas de control 112 4.3. Adaptación Computacional en Sistemas no Calibrados Algoritmo 7 Algoritmo de desplazamiento temporal. if Terrii/Tmi > 1/3 then Retornar. end if if SimPi > 1/2 then Retrasar ejecución en Tmi/2. else if SimPi < -1/2 then Adelantar ejecución en Tmi/2. else Retornax. end if end if 4.3.6. Coordinación de las políticas de control La coordinación de los diferentes bucles de control debe analizarse para garantizar la efectividad de las acciones aplicadas. El control de la homogeneización de la carga, sin embargo, y en los casos en que sea aplicable, puede plantearse como un bucle de control de bajo nivel que siempre está operativo y no entra en conflicto con otras acciones. De hecho, un entorno de carga uniforme es la situación ideal para la ejecución de los restantes bucles de control. En la práctica esa situación ideal exige una distribución de las tareas que no siempre se puede alcanzar. La presencia de violaciones de periodo de funcionamiento implica un nivel de carga elevado (puntualmente del 100%) y un sistema inestable, por lo que no tiene sentido fijar un nivel de carga de referencia hasta que los timeouts hayan desaparecido y, en todo caso, hacia niveles de carga inferiores. Esto significa que el bucle de control paxa el nivel de referencia deja de estar operativo siempre que sistema presente timeouts. La figura 4.9 muestra un esquema con la organización de las políticas de control. Para evitar efectos avalancha en la detección de sobrecargas en el sistema que provoquen una sobrecorrección, la activación de una acción de control deshabilita los mecanismos de corrección durante un intervalo de tiempo determinado (del orden del periodo de la tarea afectada). Esta solución reduce el nivel de autonomía de las políticas locales, pero es necesaria para evitar oscilaciones en el comportamiento del sistema. 4. Adaptación Computacional y Control 113 Ref. • Offset . Inliibir Timeouts Inhibir Nivel de Carga Figura 4.9: Diagrama de coordinación de las políticas de control. 4.4. Adaptación Computacional en Sistemas Calibrados A diferencia de los sistemas no calibrados, en los sistemas calibrados se cuenta con datos relativos a la correspondencia entre calidad y coste computacional, de forma que el comportamiento de los diferentes algoritmos de procesamiento está caracterizado mediante perfiles de rendimiento. Disponer de esta información a priori permite plantear esquemas de configuración o compilación del procesamiento solicitado con antelación a su ejecución en el sistema, evitando los inconvenientes del ajuste basado en el ensayoerror. El objetivo final es obtener una distribución del tiempo de procesamiento entre los diferentes módulos en ejecución que cumpla con las restricciones de la carga máxima admisible proporcionando un nivel de calidad aceptable. 4.4.1. Tiempo de procesamiento y calidad En un contexto de procesamiento anytime la calidad de un resultado es una cantidad, normalmente expresada en el intervalo [0,1], que mide la bondad del producto de un determinado algoritmo en términos de cualidades tales como su certeza o su precisión/especificidad. La relación que existe entre tiempo de procesamiento y calidad queda determinada por los denominados perfiles de rendimiento. Esta representación muestra cómo evoluciona la calidad del resultado de un algoritmo anytime a medida que el tiempo de procesamiento disponible aumenta. La forma típica de estas curvas 114 4.4. Adaptación Computacional en Sistemas Calibrados Ideal T3 T3 ü Jr\ "Ti^^H't^lf\ 1T r 1 7i I 1 I 1 i ' i i i i—i i—*- Real Tiempo Tiempo Figura 4.10: Ejemplos de perfiles de rendimiento. (figiu-a 4.10) presenta un crecimiento en calidad rápido en los instantes iniciales de procesamiento, que se va suavizando hasta saturarse en el nivel de calidad máximo. Se trata siempre de funciones monótonas crecientes, puesto que la calidad siempre debe aumentar a medida que el algoritmo dispone de más tiempo de procesamiento. Los perfiles ideales son continuos. En la práctica, sin embargo, nos encontraremos con funciones escalonadas, puesto que no será posible aprovechar cada unidad de tiempo adicional para incrementar la cahdad. Serán las características de cada implementación las que determinen el número de niveles o saltos de calidad disponibles. Estas representaciones de calidad/tiempo constituyen una descripción más cercana a los algoritmos anytime interrumpibles. Como ya se ha indicado, nuestro sistema se basa en algoritmos de contrato, pero puede igualmente obtenerse esta información realizando test de las diferentes implementaciones para distintos tiempos de ejecución. Los perfiles de rendimiento pueden además estar condicionados por la calidad de los datos de entrada. De esta forma, se convierten en funciones que no sólo dependen del tiempo disponible para el procesamiento, sino de la calidad de sus entradas. Un ejemplo de estos perfiles condicionados se ilustra en la gráfica 4.11, donde se muestran los perfiles para tres calidades de entrada diferentes. Composición y compilación La obtención del nivel de calidad de una tarea pasa por la combinación o composición de los perfiles de calidad de los módulos que la integran. Los sensores cabe 4. Adaptación Computacional y Control 115 Figura 4.11: Ejemplo de perfil de rendimiento condicionado (Qil>Qi2>Qi3). considerarlos como una "calidad de entrada puntual" al sistema, puesto que no consumen prácticamente tiempo de procesamiento; desde el punto de vista del ancho de banda consumido por las comunicaciones, sin embargo, sí pueden existir diferencias importantes. Esta calidad de entrada se combina entonces con los perfiles de los diagnósticos incluidos en la tarea. La calidad resultante es muy cercana a la de la taxea completa, pues las acciones y los actuadores no contribuyen significativamente a su alteración al tratarse de elementos finales con escaso coste computacional. A fin de ensayar diferentes esquemas de distribución de carga en sistemas calibrados, se ha desarrollado un simulador que permite definir diferentes perfiles de rendimiento y funciones de combinación para topologías arbitrarias de módulos y tareas. Los perfiles implementados son de diverso tipo: Lineal: Se define un tiempo mínimo, un tiempo máximo y la calidad correspondiente a cada uno de esos extremos (normalmente para el tiempo máximo se alcanza el valor 1 de calidad). Seno-potencia: Seno con frecuencia paxametrizable elevado a una potencia determinada. Sigmoide: Perfil tipo sigmoide parametrizado. Constante: Perfil uniforme para módulos sencillos con calidad independiente del tiempo de procesamiento asignado. 116 4.4. Adaptación Computacional en Sistemas Calibrados Figura 4.12: Tarea simple utilizada en los ejemplos. Asimismo se han implementado versiones cuantizadas de cada uno de los tipos para permitir un modelado más próximo a la situación real. Las posibles funciones de combinación de perfiles de calidad son múltiples. El objetivo es derivar el perfil a la salida de un módulo a paxtir de los perfiles de las entradas y el propio del módulo. Algunos ejemplos de composición que se han implementado en el simulador son: • Promedio total. • Producto del promedio de las entradas por el perfil propio. • Mínimo total. • Producto del mínimo de las entradas por el perfil propio. En la figura 4.12 se muestra una tarea simplificada, constituida por dos módulos productores (mi y m2) que suministran datos de entrada a un módulo consumidor (m3). La tabla 4.1 muestra el resultado de combinar las calidades de los tres módulos de dicha tarea empleando las funciones comentadas anteriormente. Vemos como la opción del promedio total es la que proporciona valores más elevados, mientras que el producto de los mínimos es la opción más conservadora. El problema de la compilación [Zilberstein y Russell, 1996] consiste en el reparto de un tiempo máximo de ejecución para una tarea entre los diferentes módulos que la 4. Adaptación Computacional y Control 117 Calidad inl,m2,m3 0.5, 0.5, 0.5 0.5, 0.5, 0.25 0.5, 0.25, 0.5 0.125, 0.25, 0.5 Prom. Total 0.5 0.42 0.42 0.29 Prod. Promedio 0.25 0.125 0.19 0.09 Mín. Total 0.5 0.25 0.25 0.125 Prod. Mínimo 0.25 0.125 0.125 0.06 Tabla 4.1: Comparación entre diferentes funciones de composición. forman. En general, el reparto está condicionado por la maximización o minimización de alguna función objetivo. Tanto la composición como la compilación son los elementos sobre los que se basan los esquemas de control planteados paxa los sistemas calibrados. Relación con la carga computacional Una vez caracterizados en términos de un perfil de rendimiento, la adaptación puede plantearse en términos de tiempo o de calidad: fijax un tiempo máximo y comprobar la calidad resultante, o bien exigir una calidad mínima y verificar el tiempo necesario para alcanzarla. Sin embargo, el control se establece también en términos de la carga computacional a la que está sometido el sistema. Para ello es necesario establecer la relación existente entre calidad y carga. A partir del modelo 4.1 para tareas periódicas, vemos que la relación entre la carga y la calidad es directa y lineal. Por lo tanto, el perfil calidad/tiempo es equivalente al perfil calidad/carga. Esto no tiene porqué ser así en todos los casos. Cuando los algoritmos incorporan tiempos de espera, por ejemplo, se rompe la linealidad entre la carga y el tiempo, lo que hace que la forma de la curva calidad/carga cambie. Otro ejemplo de no linealidad ocurre en ios sensores, puesto que diferentes calidades (en este caso resoluciones) no implican variaciones significativas en la carga inducida en el sistema, que en cualquier caso es muy baja. Desde la perspectiva del control, lo ideal sería disponer de implementaciones en las que la carga varía linealmente con la calidad, con una relación cercana a la unidad. La peor situación se presenta, por contra, cuando se tienen perfiles en los que la calidad cae bruscamente en cuanto se reduce el nivel de carga. Algunos ejemplos de estos perfiles se muestran en la figura 4.13. Ejemplos Veamos algunos ejemplos de la relación entre la asignación de tiempo/carga a los módulos de las tareas y la calidad final resultante. 118 4.4. Adaptación Computacional en Sistemas Calibrados 11 •o •D ra ü -i-f1"í7 TIXÍ ...........1 Slll: 1 U 1—i—• Carga Carga . •o ra o ü 1 1 1 I i > t 1 • III 1 !_^ \"'\ 1 1 1 "—• Carga Carga Figura 4.13: Ejemplos de curvas de calidad frente a carga. Considérese de nuevo la tarea simplificada mostrada en la figura 4.12. Empleando un perfil constante para el módulo cabecera y perfiles lineales para las fuentes se puede comprobar la calidad obtenida para diferentes distribuciones temporales. La gráfica 4.14 muestra la calidad resultante de todas las posibles asignaciones de 10 unidades de tiempo entre los módulos de entrada. Como función de combinación se emplea el producto de la calidad del módulo por el mínimo de la calidad de las entradas. La gráfica 4.15 muestra la curva que se obtiene para la misma distribución de módulos, pero ahora con perfiles lineales cuantizados Si se considera que el nodo cabecera también consume recursos, pasamos de una curva en dos dimensiones a una superficie. La gráfica 4.16 muestra el resultado de las simulaciones para perfiles lineales en el módulo cabecera y una de las fuentes y senopotencia en la otra. La gráfica 4.17 muestra el resultado para la misma configuración anterior, pero con perfiles cuantizados. Puede apreciarse la existencia de algunos máximos locales en la superficie de calidad. 4.4.2. La compilación de tareas El problema de la compilación consiste en distribuir el tiempo de procesamiento disponible entre el conjunto de módulos que integran una tarea determinada de modo que la calidad resultante sea máxima. Para un conjunto de NumM módulos, se trata 4. Adaptación Computacional y Control 119 EvoKidón de la caDdad Tiempo módulo 1 Figura 4.14: Ejemplo de gráfica de calidad para perfiles lineales (2 nodos). Evducián de la calidad 5 6 Tienpo mtSduto 1 Figura 4.15: Ejemplo de gráfica de calidad para perfiles lineales cuantizados (2 nodos). 120 4.4. Adaptación Computacional en Sistemas Calibrados Evolución de la calidad Tiempo módirio 2 Tiempo módulo 1 Figura 4.16: Ejemplo de gráfica de calidad para perfiles lineales y seno-potencia (3 nodos). Evolución de la calidad Tiempo módulo 1 Tiempo módulo 2 Figura 4.17: Ejemplo de gráfica de calidad para perfiles lineales y seno-potencia cuantizados (3 nodos). 4. Adaptación Computacional y Control 121 Tdisp = tp1+tp2+tp3 Q==min(q1,q2)*q3 Figura 4.18: Ejemplo de distribución de tiempo y calidad paxa una tarea con tres módulos. de encontrar la configuración de tiempos de procesamiento para cada uno de ellos (T Tprrii, ...,TpmjvumAf-i) de forma que deben cumplirse las siguientes condiciones: Q{T) es máxima donde T^isp es el tiempo total disponible para procesamiento, y Q la calidad final resultante para la tarea. La gráfica 4.18 ilustra el problema para un caso simplificado de una tarea con tres módulos (mi, m^ y ma). Para la combinación de calidades se emplea la regla del producto del mínimo de las entradas por la calidad del módulo. Este planteamiento supone un problema de optimización del tipo NP-Completo, por lo que una solución mediante prueba exhaustiva de todas las posibles combinaciones no es viable cuando la dimensión del problema crece. En vez de ello, pueden plantearse algoritmos de compilación local, en los que el ámbito de la optimización se reduce, haciendo que el problema global sea computacionalmente tratable. En los trabajos de Zilberstein ([Zilberstein, 1996], [Zilberstein y Russell, 1996]), se presentan algunos algoritmos de compilación local cuya complejidad es polinomial. El autor demuestra además que el resultado de la compilación local (al menos para el caso en que no existan expresiones repetidas) proporciona una solución óptima. Se realizará una traslación de los 128 4.4. Adaptación Computacional en Sistemas Calibrados Perfil 1 1L 0.7 1 ^_^-^^^ '0 A3 Perfil 2 Figura 4.21: Grafo de 3 taxeas con perfiles lineales y 6 módulos. Tiempo total 60 30 15 T. Sensor 10 10 4 T.Diagnósticos 10, 10 6,1 3.5, 1 T.Acciones 10, 10, 10 6.5, 1, 5.5 3.5, 1, 2 Calidad final 1.0 0.39 0.05 Tabla 4.5: Resultados de la compilación para 6 módulos. Tiempo total 30 15 T. Sensor 9.5 1.5 T.Diagnósticos 2, 8 1, 5.5 T. Acciones 2.5, 7, 1 1,5,1 Calidad final 0.54 0.2 Tabla 4.6: Resultados de la compilación con intercambio de perfiles. Caben dos aproximaciones a la solución. La primera alternativa consiste en imponer un reparto de carga por niveles preestablecido, mientras que la segunda se basa en extender el proceso de compilación a múltiples tareas, con lo que la distribución de carga es la que ofrece un nivel de calidad final máximo. Distribución por niveles de prioridad El primer algoritmo propuesto para la distribución de ios tiempos de procesamiento (algoritmo 9) intenta realizar un reparto uniforme por niveles. Los datos de entrada necesarios son los siguientes: Nivel de carga global deseado para el sistema Cd. 4. Adaptación Computacional y Control 129 Algoritmo 9 Algoritmo I de distribución del tiempo de procesamiento. Leer parámetros de entrada. for Cada nivel j de prioridad (de mayor a menor prioridad) do for Cada tarea i en nivel de prioridad (de mayor a menor frecuencia) do MAXJTpti = Ti*Cd* PCj/Numtj end for end for • Reserva de porcentajes de carga relativos Pd para cada uno de los NumNP niveles de prioridad. Se cumple O <= PCi <= 1 y NumNP i=0 • Periodos {TU) y nivel de prioridad (NPti) de cada tarea. A partir de aquí se determina, comenzando por las tareas más prioritarias y de mayor frecuencia, el tiempo de procesamiento máximo asignable a cada taxea U en un nivel de prioridad j. Este valor {MAX-Tpti) se calcula como MAXJTpti = Ti*Cd* PCj Numtj donde Numtj es el número de tareas que se encuentran en el mismo nivel de prioridad 3Este algoritmo proporciona una solución en la que todas las tareas dentro del mismo nivel de prioridad reciben un reparto homogéneo de carga. Un posible refinamiento consiste en iterar dentro de cada nivel de prioridad redistribuyendo tiempo de procesamiento desde aquellas tareas que no alcanzan su cuota de carga máxima, aún a pleno rendimiento, hacia aquellas que se ven obligadas a reducir su calidad para no exceder dicho límite. Si finalizadas las iteraciones en un nivel sigue sin alcanzarse la cuota máxima, se puede optar por redistribuir esos recursos sobrantes entre los niveles inferiores o simplemente descartarlos. La segunda propuesta está representada por el algoritmo 10, donde se realiza una asignación ordenada por niveles de prioridad, continuando el proceso mientras queden recursos disponibles. En este caso los datos de entrada son: • Nivel de carga global deseado para el sistema Cd. • Periodos (Tí,) y nivel de prioridad {NPti) de cada tarea. 130 4.4. Adaptación Computacional en Sistemas Calibrados Algoritmo 10 Algoritmo II de distribución del tiempo de procesamiento. Leer parámetros de entrada. Carga-Admisible = Cd Nivel-Actual = Mximo-Nivel while (Carga-Admisible > 0)k{Nivel-Actual >= 0) do Calcular Carga-Nivel y TpU para máximo rendimiento. if Carga-Nivel < Carga-Admisible then Compilar cada tarea ti usando Tpti. else Compilar cada taxea U usando TpU* = Carga-Admisible/Carga-Nivel. Carga-Nivel = Carga-Admisible end if Restar Carga-Nivel a Carga-Admisible. Decrementar Nivel—Actual end while Una mejora para los algoritmos presentados consiste en tener en cuenta que la distribución de módulos entre tareas no tiene porqué estar balanceada, ni en número de módulos ni en carga demandada. Un criterio de reparto más razonable se basa en calcular para cada tarea su carga evaluada para un valor de calidad media CQMti como CQMti = Y, TpmjiQMmj) Tm, Módulos vinculados a íi •' donde QMrUj es el valor de carga media generada por el módulo rrij. En este caso la carga total del sistema para una calidad media vendrá dada por la expresión Numt CQM = ^ CQMti Suponiendo un valor de carga máxima admisible Cd, el tiempo MAX-Tpti a distribuir entre los módulos vinculados a la tarea í, es Distribución por optimización de la calidad Una distribución alternativa consiste en tratar de alcanzar una calidad óptima para todo el conjunto de tareas, dada una carga máxima admisible. Para implementar este método, sin embargo, deben salvarse una serie de inconvenientes. En primer lugar, 4. Adaptación Computacional y Control 131 no todas las tareas poseen la misma frecuencia de operación, por lo que no es correcto distribuir tiempos de forma directa. La distribución de tiempo máximo disponible se hace siempre con respecto a la referencia de la frecuencia de operación para poder estimar la carga, con lo que ante referencias distintas no podría emplearse la misma escala temporal. Algunas soluciones aplicables son: • Añadir al problema de optimización una restricción adicional de la forma Numt Tpti Esto garantiza que la carga final que resulta es la esperada. • Añadir al sistema Ui — l réplicas de cada tarea, siendo ni = TMCM/TÍ y TMCM — Mínimo común múltiplo {Ti} • Modificar los perfiles de rendimiento. La tercera de las soluciones parece la más adecuada por su facilidad de integración en el esquema de compilación local propuesto sin apenas introducir sobrecargas adicionales. La modificación de los perfiles se basa en considerar que las tareas más rápidas van a ejecutarse rij veces en el interior del nuevo periodo. Para alcanzar el mismo nivel de calidad, por tanto, precisará una reserva de tiempo Ui veces mayor que la que se requiere para una única ejecución. Esto supone escalar los perfiles en el eje temporal multiplicándolo por ese mismo factor. La gráfica 4.22 muestra el resultado de escalar un perfil de rendimiento en un factor 2. Con estas modificaciones, el tiempo disponible (Tdisp) paxa la distribución en el sistema es simplemente el producto de la carga deseada (Cd) por el nuevo periodo. Tdisp — Cd X TMCM El siguiente inconveniente es la necesidad de disponer de una medida de la calidad global de todo el conjunto. Este problema tiene fácil solución, pues basta con hacer que todas las tareas confluyan en un módulo de salida común ficticio con perfil de carga constante y unitario, de forma que su calidad sea la combinación de las calidades de todas las tareas. La figura 4.23 muestra el esquema resultante para un caso simple. El algoritmo de compilación puede tratar el nuevo problema sin precisax modificación 132 4.4. Adaptación Computacional en Sistemas Calibrados qmax fcf:i-íjHs;--i; qmln tmln tmax qmax qmln L ithb. u:'d\lJ't^'.^ :J^T^^i!-k..rg^'i;:U 2xtmin :;:.;::I:-:;;O:::.,::J ;;.:;: i -SÍ-"?:,;:;;: j.i..;.. .Li:;-:;,- ffi;j:::.;:¡: 2x "^^^ . Figura 4.22: Ejemplo de un perfil de rendimiento escalado en un factor de 2. alguna, puesto que en la optimización local no se asume ninguna estructura previa en la red de módulos. La combinación de calidades, como ya se ha visto con anterioridad, puede estar basada en una función de promediado, un cálculo de mínimo, etc. Finalmente queda un aspecto por resolver, que es la influencia de la prioridad en la asignación de carga. De alguna forma, un sistema con pocos recursos debería reflejar una relación directa entre calidad y prioridad. Una posibilidad que se ha probado es afectar la medida de la calidad final de cada tarea por un factor que dependa de su prioridad. Si ese factor es menor a medida que la prioridad es mayor se consigue el efecto deseado, puesto que el sistema asigna más recursos a las tareas más prioritarias y una menor cantidad a las menos prioritarias. La separación relativa que exista entre los factores de ponderación de la prioridad determina la naturaleza de la distribución. Así, es posible desde obtener una distribución independiente de la prioridad, a otra en la que sólo se asignan recursos a un nivel de prioridad cuando todos los superiores han sido cubiertos al 100% de su calidad. En el primer caso estaríamos hablando de factores iguales para todos los niveles, mientras que el último corresponde al empleo de factores que están claramente dispersos. Tomando como referencia el ejemplo de la figura 4.23, la tabla muestra el resultado de distribuir 30 unidades de tiempo entre las dos tareas para diferentes valores de prioridad. Se define el mismo perfil de rendimiento para los módulos mi y m2, lineal entre las coordenadas de tiempo-calidad (0,0) y (30,1). 4. Adaptación Computacional y Control 133 Tareal Módulo ficticio Figura 4.23: Estructura para la optimización de múltiples tareas. Prioridades inl,m2 1,1 1,2 3,1 Tiempo mi 15.0 10.2 22.2 Tiempo m2 15.0 19.8 7.8 Tabla 4.7: Influencia de la prioridad en la distribución temporal. La distribución de tiempos basada en la optimización de la calidad, aunque constituya el esquema más adecuado desde el punto de vista de la calidad final alcanzada, presenta el inconveniente de que una modificación en cualquiera de los parámetros del problema puede llevar a una reconfiguración del reparto de tiempos para todo el sistema, lo que puede representar un coste y unos retardos considerables. En estos casos, un esquema como el visto en el apartado anterior permite una reconfiguración localizada, aunque no proporcione la máxima calidad posible. 4.4.4. Políticas de control Una vez establecida la distribución temporal para las tareas de la aplicación, el sistema debería comportarse en base al modelo teórico. Sin embargo, puede ocurrir que durante la ejecución aparezcan variaciones en la carga no esperadas. Las causas de estas diferencias pueden tener distintos orígenes, tales como: Imperfecciones en el modelado. Errores en la calibración. 134 4.4. Adaptación Computacional en Sistemas Calibrados • Cargas extras no anticipadas. Los diferentes bucles de control a emplear coinciden con los ya vistos para el caso de los sistemas no calibrados. De hecho, en el control del desplazamiento temporal puede mantenerse el mismo esquema de funcionamiento, puesto que los recursos de bajo nivel empleados son los mismos en ambos casos. Aunque caben múltiples enfoques, el objetivo principal de los bucles de control planteados por el sistema será el mantenimiento de un nivel de calidad homogéneo dentro de cada nivel de prioridad en todo el sistema. La diferencia fundamental con el caso de los sistemas no calibrados es que los umbrales de homogeneidad se plantean en este caso de forma directa sobre las medidas de calidad de las tareas, y no sobre el número de niveles de degradación disponibles. De nuevo el coste de la compilación de tareas juega un papel importante, en especial cuando el número de módulos activados en el sistema es elevado. Hay que tener en cuenta la demanda computacional que representa este proceso para prever sus consecuencias. Suponiendo que no existen máquinas externas sobre las que lanzar la compilación en paralelo, puede adoptarse alguna de las dos posturas siguientes: • Ejecución en mínima prioridad. • Reserva de recursos. La ejecución en mínima prioridad consiste en asignar a la compilación de tareas la prioridad mínima dentro del sistema. Esto significa que ninguna tarea se verá desplazada de la CPU por la compilación y podrán aprovecharse los recursos disponibles en su totalidad. Como aspecto negativo está el hecho de que en un sistema sobrecargado el tiempo transcurrido hasta obtener el resultado de la compilación puede ser considerable, llegando al extremo de no poder completarse si se llega a la saturación de recursos con las tareas en ejecución. La segunda alternativa es la reserva de un cierto porcentaje de carga a fin de anticiparse a la demanda del algoritmo de compilación sin comprometer la estabiUdad del conjunto. Para lograr esto, debe acotarse la carga introducida por la compilación a un valor máximo. Una solución es la programación del algoritmo para conseguir una ejecución fraccionada, de modo que el intervalo de reanudación del cómputo permita controlar la carga. La reserva de recursos permite garantizar un tiempo de respuesta para la compilación a costa de limitar la capacidad máxima del sistema. 4. Adaptación Computacional y Control ^ En cualquier caso, la ejecución de la compilación de tareas debe notificarse de manera que los mecanismos de adaptación no traten de reaccionar como si se tratase de una carga externa no modelada. Control de violaciones temporales La detección de un timeout en un nivel de prioridad determinado admite un control en dos niveles, local y global. Los umbrales de calidad mínima y máxima determinan el margen de maniobra de las acciones locales, de forma que se notifican los errores al supervisor cuando dentro de la tarea se han agotado los recursos de control. A nivel local, la magnitud de la acción de control puede establecerse en función de la diferencia que existe entre el nivel de calidad actual y el nivel de calidad mínimo admisible. La selección del módulo a degradar afecta también a la magnitud de la corrección. A igualdad de calidad final, la acción más efectiva es la que provoca una mayor reducción en el tiempo de ejecución final de la tarea. A nivel global, las posibilidades de selección de candidatos a la degradación aumentan. Respetando los límites de homogeneidad, el efecto más intenso se obtiene con las tareas cuya contribución de carga al sistema completo sufre una reducción más importante. Control del nivel de carga En el control del nivel de carga intervienen tanto mecanismos de promoción como de degradación. La ordenación de las acciones es guiada por la prioridad de las tareas, de forma que las más prioritarias son las primeras en promocionar y las últimas en degradarse, mientras que con las menos prioritarias ocurre todo lo contrario. El comportamiento del bucle de control depende de la selección de candidatos. Pueden adoptarse dos posturas: Primar la homogeneidad: Se seleccionan siempre los candidatos con mayor calidad para degradar y con menor calidad para promocionar. Primar la rapidez de respuesta: Se seleccionan siempre los candidatos con mayor efecto sobre la caxga del sistema. 136 4.4. Adaptación Computacional en Sistemas Calibrados Algoritmo 11 Algoritmo para la incorporación de una nueva tarea sin alterar la configuración actual. CDisp = CargaDisponibleQ Test admisibilidad: CMin = CargaMin{Tnew) if CMin>CDisp then Salir. end if Calidad entrada: QMPrio = CaHdadMediaPrio{PriOnew) QCDisp = CalidadTarea{Tnew, CDisp) QTarea = Min{QMPrio, QCDisp) Activar tarea con calidad QTarea. Admisión de nuevas tareas En un sistema estable sobre el que se están ejecutando múltiples tareas, surge otro problema interesante cuando se desea introducir una nueva. Caben múltiples aproximaciones, que varían en función del tipo de algoritmo de distribución empleado y el grado de perturbación generado sobre la configuración actual. En un primer escenario se impondrá que la configuración de las tareas que actualmente se ejecutan en el sistema no sufra alteración. Tomando además la carga máxima deseada, bien por nivel de prioridad o para el sistema completo, puede realizarse un test de admisibilidad previo. Este test consiste en comprobar si la tarea, con su nivel de calidad mínimo, tiene hueco suficiente para entrar en el sistema. Si es así, hay que decidir el nivel de calidad con el que la nueva tarea ingresa en el sistema, que estará entre el mínimo anterior y un máximo que viene dado por la menor de las siguientes calidades: la calidad media de las tareas en su mismo nivel de prioridad y la calidad con la que se cubre el nivel de carga disponible. El algoritmo 11 resume los pasos a seguir en este caso. El siguiente supuesto en la línea de nivel de perturbación creciente sería la modificación de las tareas ya existentes únicamente en el nivel de prioridad de la nueva {Pnew)- Esto puede hacerse si existe una reserva de carga por niveles. En este caso, el test de admisibilidad consiste en comprobar si con todas las tareas en Pnew a su nivel de calidad mínimo no se supera el porcentaje de caxga máximo admitido. Superado el test, se aplica la compilación en busca de la calidad óptima para las tareas implicadas, siendo el tiempo de procesamiento a distribuir el correspondiente a la carga límite. En caso de que no se disponga de la especificación de límites de carga por niveles 4. Adaptación Computacional y Control 137 de prioridad se puede considerar tanto el nivel de prioridad de la tarea nueva como todos los inferiores. El test de admisibilidad situará a todas las tareas incluidas en dichos niveles en su calidad mínima y comprobará si hay recursos en el sistema para la ejecución simultánea de todas ellas. Si no es así, existen dos posibilidades: rechazar la nueva tarea o suspender la ejecución de tareas menos prioritarias para darle cabida. Asumiendo que el test es superado, se aplica la compilación con factores de prioridad y límite de tiempo definido por la carga disponible. Finalmente, el máximo grado de alteración se produce cuando todo el sistema es reconfigurado teniendo en cuenta la nueva tarea. Como en el caso anterior, también aquí puede aplicarse un test previo de entrada para garantizar que al menos con la calidad mínima es posible la ejecución de todas las tareas. Posteriormente, podrá aplicarse la compilación en función de las prioridades y el tiempo de procesamiento disponible. En todos los casos planteados, la existencia de módulos compartidos complica los algoritmos. La introducción de una tarea no impUca sólo una nueva demanda de carga a satisfacer, sino que puede provocar la modificación de las prioridades y/o las frecuencias de operación de algunos módulos ya presentes en el sistema. Esta alteración afecta tanto a la carga total como al reparto de carga por niveles de prioridad, lo que debe ser tenido en cuenta en la medida de la carga actual y la carga disponible. En este sentido, hay que recordar que los módulos compartidos toman como valor de prioridad el más alto de todas sus tareas asociadas, que generalmente serán las que presenten además una frecuencia de operación más elevada. 4.5. Transición de Sistemas no Calibrados a Sistemas Calibrados A medida que el sistema evoluciona, es posible recoger información relativa al funcionamiento de los diferentes módulos en ejecución. Esta información puede incorporarse a los mecanismos de adaptación para mejorar su funcionamiento. Un ejemplo habitual lo constituye la operación con implementaciones que no han sido previamente calibradas. Inicialmente el sistema asume un perfil de rendimiento por defecto que puede irse modificando hacia su forma real a medida que el sistema evoluciona. El resultado es un proceso de autocalibración del sistema que no precisa de la intervención del usuario. Lógicamente no cabe esperar unos resultados equiparables a los que resultarían de un procedimiento sistemático de calibración, pero sí ofrece una referencia válida para caracterizar los perfiles de rendimiento de manera aproximada.