Estudio y desarrollo de métodos y herramientas para el testeo, validación y verificación de sistemas multi-agente

Resumen

Desde el transporte aéreo civil a las plantas nucleares, cada año el software informático está encontrando su camino en más y más aplicaciones críticas para la vida. De acuerdo con el NIST (National Institute of Standards and Technology), los errores software tienen un costo estimado para la economía estadounidense de 59.500 millones de dólares. Estos errores deben ser encontrados en la fase de testado del desarrollo del software. El concepto de testado o ``testing'' significa ``el proceso de ejecutar un programa con la intención de encontrar errores''. El proceso de depuración o ``debugging'' puede ser descrito como la actividad que uno realiza tras detectar un error: (1) determinar la naturaleza exacta y localización de el error sospechado, y (2) arreglar el error. De acuerdo con el glosario estándar de terminología de ingeniería del software del IEEE: ``Validación es el proceso de evaluar un sistema o componente durante, o al final del proceso de desarrollo para determinar si este satisface los requisitos especificados''. Por consiguiente, la validación del software es el proceso de comprobar si su funcionalidad es correcta. Es decir, un fallo en la validación ocurre cuando el software hace algo diferente a lo que se supone que debería hacer por su diseño. Por otro lado, la verificación es el proceso de evaluar un sistema o componente para determinar si los productos de cierta fase de desarrollo satisfacen las condiciones impuestas al principio de esta fase. Por lo tanto, mientras que la validación asegura que ``estas construyendo el producto correcto'', la verificación asegura que ``lo estas construyendo correctamente''. Obviamente, verificación y validación no pueden ser realizadas sin un testado previo. Además, ambos procesos son inútiles sin un subsecuente proceso de depuración. Entre las numerosas estrategias para realizar la depuración, Glenford J. Meyers dice que la más común es la fuerza bruta (es decir, esparcir sentencias a lo largo del código que se encarguen de mostrar por pantalla valores de variables del programa bajo test). Este método es frecuentemente el más ineficiente e improductivo. Como Henry Lieberman dijo en la introducción al ``The Debugging Scandal and what to do about it'' : ¿...la gente que escribe estos programas todavía no tiene buenas maneras de averiguar qué es lo que ha ido mal exactamente. La depuración es aun, como lo era hace treinta años, esencialmente un proceso de ensayo y error.¿ Hay problemas que pueden ser difícil de resolver con clásicos sistemas software monolíticos en lugar de con sistemas multi-agente. El termino ``sistema multi-agente'' (o SMA) es aplicado a un sistema que tiene, entre otros, los siguientes elementos: (1) Un entorno En, (2) un conjunto de objetos O, (3) una reunión de agentes A con A siendo un subconjunto de O, y finalmente, una reunión de relaciones R que enlazan objetos (y, por lo tanto, agentes) entre ellos. Un caso especial de SMA en el cual A=O y En es el conjunto vacío es un SMA comunicante puro. En este caso, las relaciones R definen una red: cada agente esta directamente enlazado a una reunión de otros agentes, que son llamados sus conocidos. Estos sistemas son muy comunes en la inteligencia artificial distribuida y están caracterizados por el hecho de que sus interacciones son esencialmente comunicaciones intencionales. La interacción entre agentes es realizada por diálogos complejos porque los agentes son autónomos y, por lo tanto, estos deberían tener la habilidad de rechazar peticiones de otros agentes. Por esta razón, estas interacciones son complejas y, frecuentemente, inesperadas. Esto es también una consecuencia de la naturaleza compleja de un SMA, que hace que comportamientos sofisticados surjan de una multitud de interacciones relativamente simples entre los agentes independientes que componen el sistema (lo que comúnmente es llamado emergencia). Además, el objeto de estudio de esta tesis es un caso de SMA particular llamado SMA a gran escala, es decir, sistemas con más de cien agentes. Si la depuración de software tradicional es considerablemente compleja, mucho más complejo es depurar un SMA en el que comportamientos inteligentes o emergentes pueden aparecer. Estudios recientes indican las dificultades intrínsecas relacionadas con el testado y depuración de aplicaciones orientadas a servicios, que suelen ser realizadas por agentes. Además, el análisis de un SMA requiere el uso de las últimas tecnologías con el objetivo de automatizar y facilitar este complicado proceso tanto como sea posible. Tres principales propuestas de análisis de SMA han sido consideradas en la literatura especializada en función del nivel de abstracción considerado. Todas estas propuestas están basadas en el registro y análisis de eventos de ejecuciones del sistema. Por lo tanto, las tres propuestas se pueden incluir dentro de la categoría de análisis forense (es decir, un proceso de análisis realizado sobre datos previamente registrados de la ejecución de un SMA). La primera propuesta funciona mostrando los eventos registrados al programador por medio de una serie de representaciones gráficas simples. Estas representaciones deben ser estudiadas por el desarrollador para descubrir fallos en el software. Este modo de análisis es fuertemente criticado por David Poutakidis et al. Estos investigadores principalmente argumentan que las representaciones presentan demasiada información a los desarrolladores, haciendo difícil entender qué ocurrió realmente en el sistema. La segunda propuesta esta basada en la definición de protocolos que regulan las interacciones entre agentes, el testado de estos protocolos automáticamente, y la depuración a través de algún tipo de representación gráfica. El principal problema con este enfoque es que sólo se testea lo que ha sido definido previamente sin inferir ningún conocimiento adicional, y un SMA frecuentemente presenta comportamientos emergentes que no serían analizados. La tercera propuesta está centrada en el descubrimiento de conocimiento en el registro de eventos, para después mostrar el conocimiento extraído de alguna manera que permita dar pistas sobre qué ocurrió o qué puede haber ido mal en la ejecución del SMA. Hay una serie de carencias en las propuestas anteriormente mencionadas que motivan esta tesis. El registro de eventos no considera como se puede establecer el orden de estos eventos, la representaciones gráficas simples no tienen mecanismos para resumir la información presentada, el testado automático de protocolos no es capaz de detectar comportamientos emergentes no deseados, y las propuestas para descubrir conocimiento en el registro de eventos suelen requerir un profundo conocimiento sobre la implementación del SMA específico y las técnicas de aprendizaje utilizadas. Esta tesis se presenta como una contribución significativa al análisis forense de SMAs y a cada una de las mencionadas tres propuestas para el análisis de estos sistemas. Además, la contribución presentada permite realizar un análisis cuantitativo, pero también un análisis cualitativo. Los métodos para el análisis de interacciones suelen ser muy superficiales y sólo tratan los elementos fijos en la sintaxis que pueden ser observados en los intercambios de mensajes (por ejemplo la performativa, el emisor, receptor, correcta o incorrecta completitud del protocolo, etc.). Sin embargo, la semántica de las interacciones puede ser empleada para realizar un análisis cualitativo que infiera teorías sobre los estados mentales ocultos de los agentes, y esto es una oportunidad perdida en las propuestas existentes para el análisis de interacciones. Tomemos por ejemplo un sistema en el que los agentes interactúan usando el protocolo FIPA Contract- Net. Este protocolo describe un agente (el agente Iniciador) que quiere que uno o más agentes (los Participantes) realicen una tarea. En este protocolo, la información proporcionada por una herramienta para analizar las interacciones de los agentes podría ser: (1) número de conversaciones en las que cada agente ha participado, (2) conversaciones en las que ocurrió un error en el flujo de mensajes definido por el protocolo, (3) número de agentes que rechazaron una propuesta, (4) número de tareas que un participante fue incapaz de realizar tras comprometerse a ellas, etc. Aunque este análisis cuantitativo es muy útil, una información mucho más interesante se encuentra en la semántica específica de los mensajes, es decir, en las propiedades cualitativas. El desarrollador del agente iniciador, por ejemplo, puede estar interesado en cuales tareas son frecuentemente rechazadas por agentes, o más específicamente, cómo está implementado el proceso usado por un agente participante para aceptar o rechazar una tarea (en el sentido de una regla de decisión en el mecanismo de razonamiento del agente). Por supuesto, esta información esta oculta si las implementaciones de los agentes participantes son desconocidas por los agentes iniciadores. No obstante, considerando una ejecución del protocolo concreta y pasada, el agente iniciador puede reconocer fácilmente si una tarea particular ha sido aceptada o rechazada por un participante específico. Es más, después de varias ejecuciones del protocolo, el agente iniciador puede obtener más información y generalizar a partir de la información extraída de casos individuales para así construir una teoría más general. Esta teoría explicaría el resultado de las interacciones previas con los agentes participantes. De este modo se revelarían relaciones causales implícitas entre estados del sistema y el mecanismo de razonamiento y decisión de los agentes involucrados. Además del análisis cuantitativo y cualitativo de SMAs, esta tesis también trata con el análisis de simulaciones basadas en sistemas multi-agente (Multi-agent based simulations o MABSs). Las MABSs son modelos computacionales que se caracterizan por la existencia de muchos individuos autónomos llamados agentes que interactúan y actúan con los demás autonómicamente. Las MABSs son usadas en más y más dominios científicos: sociología, biología, física, química, ecología, economía, etcétera. Específicamente, esta tesis considera las MABSs que son usadas para la validación de aplicaciones AmI basadas en UbiCom. La Inteligencia Ambiental (AmI) permite a los humanos interactuar con entornos de una manera inteligente y discreta mediante el uso de dispositivos computacionales que están esparcidos por todo el entorno. El objetivo de estos sistemas es ser consciente de las necesidades de la gente personalizando los requisitos y prediciendo comportamientos. Las utilidades de la AmI son infinitas: casas inteligentes, monitorización del estado de la salud, hospitales, transporte, servicios de emergencia, educación, lugares de trabajo, etc. En un campo más general que la AmI, la Computación Ubicua (UbiCom) proporciona la ejecución de tareas en cualquier lugar y un uso intuitivo por parte de los humanos, a la vez que se presenta invisible al usuario. La tecnología UbiCom está basada en el uso de numerosos dispositivos de tamaño reducido que están presentes en el entorno físico de los usuarios, incluyendo el hogar, la oficina, y otros. El paradigma SMA has sido utilizado ampliamente para el desarrollo de aplicaciones AmI basadas en UbiCom. Sin embargo, la propuesta presentada en esta tesis es diferente, no implica el desarrollo de estas aplicaciones usando SMAs, sino que se usan MABSs como modelo de estos sistemas UbiCom con el objetivo de validarlos. Una característica bien conocida de las tecnologías basadas en agentes es su habilidad para generar comportamientos complejos y emergentes a partir de modelos de agentes muy simples. Por consiguiente, una MABS que modela un sistema UbiCom es bastante compleja y su análisis presenta desafíos. Precisamente por esta complejidad añadida, esta tesis propone aislar algunos elementos conflictivos de una MABS principal en simulaciones más simples. Además, el proceso de análisis forense introducido en esta tesis para SMAs es también aplicado a las MABSs. Finalmente, la tesis también propone inyectar realidad (integrar elementos reales con la simulación) para realizar un análisis lo más fiable posible. La tesis está estructurada como sigue. El capítulo 2 ofrece el estado del arte. El capítulo 3 introduce las bases del desarrollo de una infraestructura para el análisis forense de SMAs. La naturaleza distribuida de estos sistemas hace que presenten dificultades en el registro de eventos. Este capítulo 3 también ofrece visualizaciones simples de los eventos y critica el uso de métodos tradicionales. Mostrar el comportamiento de un sistema complejo implica usar algún mecanismo de abstracción que prevenga al desarrollador software de perderse dentro de tanta información. Por este motivo, el capítulo 4 contribuye aplicando técnicas de minería de datos para descubrir conocimiento no explicito en los registros derivados del análisis forense. Estas técnicas son superpuestas a representaciones gráficas con el objetivo de entender el comportamiento social del sistema, comportamientos emergentes, y depurar posibles comportamientos indeseados. Este capítulo 4 presenta varias ventajas pero también una serie de complicaciones y carencias. Como una alternativa más formal y automática, el capítulo 5 explica técnicas basadas en el análisis de redes sociales, específicamente redes Pathfinder (PFNETs). Este capítulo 5 muestra como las PFNETS pueden revelar la organización subyacente de un MAS partiendo de los datos generados por el sistema. El capítulo mencionado no ofrece un análisis cualitativo sino un análisis cuantitativo. El capítulo 6 proporciona un análisis cualitativo sobre la base de información semánticamente rica proporcionada por lenguajes de comunicación y protocolos de interacción para agentes. Esta propuesta interpreta las restricciones lógicas asociadas con la ejecución de caminos de un protocolo o mensajes individuales como modelos del contexto de una interacción observada, y los usa como características de muestras de aprendizaje. El capítulo 7 proporciona una metodología que ofrece un conjunto de procedimientos que guía al desarrollador en la definición, creación, testado y análisis de MABSs usadas como modelos de sistemas UbiCom. Este trabajo metodológico esta basado en una metodología descrita previamente por Gilbert y Troitzsch. Además, el capítulo 7 defiende la tesis de que las MABSs son útiles para asistir el proceso de ingeniería de los sistemas UbiCom. El capítulo comprende la creación de MABSs y cómo deben ser empleadas para encontrar errores en sistemas UbiCom. Finalmente, las conclusiones de la tesis son dadas en el capítulo 8.