Tesis:
Resilient Multi-Agent Model for Team Formation Problems in Dynamic Scenarios based on Distributed Constraint Optimisation
- Autor: BARAMBONES RAMÍREZ, Jose María
- Título: Resilient Multi-Agent Model for Team Formation Problems in Dynamic Scenarios based on Distributed Constraint Optimisation
- Fecha: 2022
- Materia:
- Escuela: E.T.S DE INGENIEROS INFORMÁTICOS
- Departamentos: LENGUAJES Y SISTEMAS INFORMATICOS E INGENIERIA DE SOFTWARE
- Acceso electrónico: https://oa.upm.es/72263/
- Director/a 1º: IMBERT PAREDES, Ricardo
- Resumen: In recent years, the scientific community has shown a special interest in the research, deployment, and use of computational, heterogeneous, and autonomous entities as intelligent agents to work together for different emerging or critical tasks in the field. The literature proposes and evidences the benefits of providing proactive organisational capability to these entities in dynamic scenarios. The motivation is the following: all decisions that can be planned by these entities as agents are no longer delegated to the users, so that the automation of tasks lightens the workload and frustration from users, with the goal of maximising the teams’ effectiveness.
AI deployment through Multi-Agent Systems requires modelling that proactivity in a changing scenario. Additionally, ensuring the achievement of all objectives is even more challenging when considering events and risks that compromise the integrity of the team. However, these scenarios require distributed solutions with capabilities beyond traditional and centralised fault-tolerant techniques. Resilient AI research proposes systems that can recover as gracefully and efficiently as possible from unavoidable and high-impact circumstances.
The deployment of resilient systems implies the incremental implementation of the different principles and the different synergies that compose it, involving a challenge in defining a generalised model of the resilient system. The question that arises is how Resilience can be characterised through a distributed system in a dynamic scenario in such a way that it would provide an advantage in the search, guarantee and quality of the solution.
This Ph.D. thesis aims to answer this question by proposing a first approach to solving the resilient Team Formation problem. This constrained-based problem consists of a well-known mathematical framework to represent a dynamic scenario as a set of agents, variables, and restrictions to be satisfied. Thus, the goal in its resilient version is to assemble a team of agents capable to perform a set of tasks with the minimum cost and guaranteeing its solution in the event of a possible failure or deprivation of a number of agents. For this purpose, it is proposed to introduce the principle of Stabilisation by characterising the agent communication when forming the team. Thus, a resilient solution now includes the search for a team that also meets and preserves certain conditions in its graph structure.
As contributions of this work, an extended generalisation of the resilient Team Formation problem that includes the representation of the communication between agents is presented, as well as the design and implementation of an optimal and efficient distributed algorithm that solves this problem. The results support that stabilisation is a valid component within a resilient system that allows the characterisation of both distributed and intelligent nature required in these scenarios.
RESUMEN
En los últimos años, la comunidad cientifica ha mostrado un especial interés en la investigación y desarrollo de entidades computacionales, heterogéneas y autónomas para trabajar en conjunto y de forma colaborativa, en forma de agentes inteligentes, en la realización de diferentes tareas emergentes o críticas sobre el terreno. La literatura propone y evidencia los beneficios de dotar de una capacidad de organización proactiva a estas entidades en escenarios dinámicos. La motivación del presente trabajo es la siguiente: las decisiones que pueden ser planificadas y automatizadas por un conjunto de agentes inteligentes no necesitan ser delegadas a los usuarios, con el objetivo de maximizar la efectividad y el rendimiento del equipo y sus tareas.
Desplegar una inteligencia artificial sobre estos sistemas multi-agente requiere caracterizar esa proactividad en un escenario cambiante. Además, garantizar la consecución de todos los objetivos supone un reto aún mayor si consideramos los eventos y riesgos que comprometen la integridad del equipo. Tradicionalmente, el enfoque en estos escenarios pasa por soluciones parcialmente centralizadas junto con el uso de heurísticas basadas en técnicas de tolerancia a fallos. Sin embargo, estos escenarios requieren soluciones distribuidas con la capacidad adicional de poder recuperarse de la forma más grácil y eficiente posible ante circunstancias inevitables y de gran impacto, lo que se conoce en la literatura como sistemas resilientes.
La aplicación de la Inteligencia Artificial Resiliente se basa en la implementación incremental de los diferentes principios y conceptos que la componen. Sin embargo, las sinergias entre los distintos componentes hacen complicado un diseño generalizado y que incluya una solución óptima al mismo tiempo. Surge entonces la pregunta de cómo la resiliencia puede ser caracterizada a través de un sistema distribuido, de tal forma que modelar un problema representativo de estos escenarios dinámicos suponga una ventaja en la búsqueda, garantía, y calidad de la solución.
La presente tesis doctoral pretende contestar a esta pregunta proponiendo una primera aproximación que resuelva el problema conocido de formación de equipos resiliente. Este problema distribuido está basado en restricciones, un marco matemático para representar un escenario dinámico como un conjunto de agentes asignando variables sujetas a satisfacer una serie de restricciones o limitaciones. El objetivo del problema en su versión resiliente consiste en reunir un equipo de agentes para realizar un conjunto de tareas con el mínimo coste y garantizando su solución ante una posible avería o eliminación de un número de agentes. Para ello, se propone incorporar al problema la caracterización de la comunicación de los agentes a la hora de conformar el equipo. Se extiende así la resiliencia introduciendo por primera vez el principio de la estabilización. Esta definición establece en el problema la búsqueda de un equipo que además cumpla y preserve ante cualquier circunstancia ciertas condiciones en su estructura basándose en ciertas propiedades bien conocidas de la teoría de grafos, como su conectividad o densidad.
Como contribuciones más importantes de este trabajo, por un lado, se presenta una generalización del problema de formación de equipos resiliente que incluye la representación de la comunicación entre agentes, así como el diseño e implementación de un algoritmo distribuido que resuelve de forma parametrizada, óptima y eficiente este problema. Por otro lado, se analizan y discuten las diferentes implicaciones de la estabilización del equipo frente a aspectos resilientes como su robustez y recuperabilidad, así como su eficiencia y escalabilidad. Como resultado, se demuestra que la estabilización es un componente válido dentro de un sistema resiliente que permite caracterizar la naturaleza distribuida e inteligente requerida en estos escenarios.