Coordination in multiagent systems applied to complex scenarios based on the theoretical models of division of labor in social insects

Agentes atuando em sociedade devem agir de maneira coerente para atingir um objetivo comum. A coordenação nos sistemas multiagente previne o comportamento caótico dos agentes, permite que o sistema lide com restrições globais e a interdependência entre os agentes, e faz com que o sistema possa ser composto por agentes com diferentes competências. A coordenação pode ser baseada na estrutura organizacional, onde a comunidade de agentes atua a favor de um objetivo comum através da forma como estão organizados. Em ambientes dinâmicos a organização dos agentes deve se adaptar a mudanças nos objetivos do sistema, na disponibilidade de recursos, nos relacionamentos entre os agentes, e assim por diante. Esta flexibilidade é um problema chave nos sistemas multiagente e está relacionada a modelos de adaptação como os observados nos insetos sociais. O presente trabalho propõe uma abordagem para a geração e adaptação da organização de um sistema multiagente, em tempo de execução, utilizando como base os modelos teóricos de organização das colônias de insetos sociais. Esta abordagem enfoca a alocação e o escalonamento dinâmicos de tarefas distribuídos entre agentes com diferentes competências e em ambientes de larga escala. Dois cenários principais são utilizados para experimentar e validar a abordagem proposta. Estes cenários estão baseados em problemas de pesquisa operacional denominados Resource-Constrained Project Scheduling Problem (RCPSP) e o Generalized Assignment Problem (GAP). Este trabalho contribui para o avanço do estado-da-arte no estudo e desenvolvimento de sistemas multiagente e na modelagem e aplicação de técnicas de inteligência de enxames em problemas computacionais. A abordagem proposta para coordenação de agentes em cenários complexos é nova, eficaz e robusta. De maneira geral, esta abordagem contribui para busca da solução de problemas de coordenação de sistemas multiagente aplicados a problemas reais.A community of individual agents must work in a coherent manner to reach some common goal. The coordination process in multiagent systems prevents chaotic behavior of agents, makes the system able to deal with global constraints and inter-agents dependencies, and allows the system to be composed of agents with different capabilities. This process is normally based on the organizational structure, where the community of agents works towards the system goal through the manner they are organized. However, in dynamic environments, agents must be able to adapt to the changing goals of the system, to the resources available, to their relationships with another agents, to changes on the environment and so on. This problem is a key one in multiagent systems and relates to models of adaptation, such as those observed among social insects. This work proposes a new approach to generate and adapt the multiagent organization on the fly based on the theoretical models of social insects colonies organization. This approach focuses on distributed dynamic scheduling and task allocation using agents with different capabilities in large scale environments. Two main scenarios have been used to experiment and validate the proposed approach: the Resource-Constrained Project Scheduling Problem (RCPSP) and the Generalized Assignment Problem (GAP). This work contributes to advancing the state-of-the-art in the study and development of multiagent systems and in the modeling and application of swarm intelligence techniques. The proposed approach to coordinate agents in complex scenarios is novel, effective and robust. This approach contributes to the search of coordination solutions to multiagent systems real applications