Este trabalho tem por objetivo propor uma abordagem para o problema de alocação dinâmica de recursos em ambiente de produção baseada no paradigma de multiagentes. Para tanto, é especificada uma arquitetura multiagente genérica chamada M-DRAP - Multi-agent Dynamic Resource Allocation Planning, a partir da qual podem ser derivados modelos particulares. As principais contribuições deste trabalho compreendem: (i) a definição de uma estratégia que permita o planejamento dinâmico de cada recurso no atendimento as demandas das atividades de produção de forma descentralizada e distribuída, através de uma abordagem orientada a projeto; (ii) a proposição de uma organização social baseada em uma abordagem multiagente orientada a mercado, capaz de propiciar relações de negociação entre agentes autônomos no sentido de atenderem aos seus interesses individuais, contribuindo de forma efetiva para a satisfação dos objetivos e restrições temporais e de custos globais ao sistema de produção como um todo; (iii) a especificação de uma arquitetura multiagente derivada do CIMOSA, representando de forma consistente a estrutura funcional e organizacional de um sistema de produção; (iv) a definição de estratégias baseadas em negociação entre os agentes capazes de propiciarem o tratamento das perturbações que afetam o sistema de produção em tempo real. Como contribuindo associada, e proposta uma metodologia para a modelagem conceitual de sistemas multiagentes para o domínio das aplicações envolvendo modelagem de empresas. / The objective of this work is to propose an approach to the problem of dynamic resource allocation in production systems. A multi-agent reference architecture called M-DRAP - Multi-agent Dynamic Resource Allocation Planning - is specified and described in this thesis. The main contributions of this work are (i) the definition of a decentralised and distributed strategy for dynamic resource allocation planning, using a project oriented approach, (ii) the proposition of a social organisation based on marketoriented behaviour, which considers the necessity of each agent's local plan to converge to an adequate global plan in terms of production costs to the whole system, (iii) the definition of a multi-agent architecture inspired in the CIMOSA reference architecture representing a functional and organisational structure, (iv) the definition of a strategy based on negotiation which propitiates real-time disturbance treatment. As an associated contribution, we propose a methodology to multi-agent systems conceptual modelling adequate to the enterprise modelling domain.

Este trabalho encontra-se situado na área de Inteligência Artificial, mais especificamente na modelagem de Sistemas Multiagentes destinados à simulação social. A área de pesquisa de simulação social baseada em agentes é uma área recente e bastante promissora. Por tratar de problemas extremamente complexos, existe a necessidade de criar modelos e abstrações para possibilitar sua realização. Dando continuidade a trabalhos anteriores, esta tese pretende consolidar uma nova versão do modelo MAS-SOC, destinado à definição de simulações sociais baseada em Sistemas Multiagentes Situados, com organizações que funcionam em ambientes determinados (organizações situadas). É proposta uma abordagem integrada, que conecta de maneira forte as entidades agentes, organizações e ambiente, sendo os agentes, o ambiente e as estruturas da organização tratadas como entidades de primeira ordem. A definição do ambiente é feita através da linguagem ELMS, estendida com uma infraestrutura normativa. Esta infraestrutura normativa é composta basicamente por objetos normativos e espaços normativos que permitem a distribuição espacial da informação normativa no ambiente, possibilitando a contextualização das normas que os agentes devem seguir em um escopo espacial determinado. A contextualização das normas facilita a sua operacionalização e a verificação de conformidade, reduzindo também a possibilidade de interpretações errôneas das normas. Com isso, a infraestrutura normativa conecta ambiente físico à estrutura da organização do sistema multiagente. Além disso, o modelo proposto usa um esquema mínimo de definição das organizações para armazenar informações e restrições que o projetista da simulação prefira representar desta forma. Esta maneira integrada de modelar os sistemas multiagentes, associando a organização ao espaço em que a organização deve funcionar, pode facilitar a modelagem de grandes sistemas, pois o conceito de espaço normativo permite que a modelagem seja feita através da partição do ambiente físico em módulos onde as atividades da organização situada são realizadas. Assim, o modelo trata de forma bastante prática o uso das normas organizacionais que podem ser representadas através de objetos normativos. Esta forma de representação possibilita aos agentes decidirem sobre a aderência as normas, já que estas não estão embutidas no mecanismo de raciocínio dos agentes. Além disso, a forma contextualizada das normas facilita raciocínio sobre elas e possibilita a aderência a normas previamente desconhecidas pelos agentes. / This work is situated in the research area of Artificial Intelligence, specifically the modelling of Multi-agent systems for social simulation. The research area of agent based social simulation is a recent and interesting area. In order to handle with its very complex problems, it requires the development of models and abstractions to make possible its realisation. Continuing previous works, this thesis aims to consolidate extensions to the MAS-SOC model, in order to turn it into a suitable model for the social simulation based on situated multi-agent systems with organizations that operate in determined environments (situated organisations). It is proposed an integrated approach in which multiagent entities such as agents, organisations and environments are strongly connected to each other, and the environment and the organisational structures being treated as first order entities. The definition of the environment is made with the use of the ELMS language, which have been extended with a normative infrastructure. The normative infrastructure is composed essentially by normative objects and normative places, which are means for the spatial distribution of the normative information over the environment, allowing the contextualisation of the norms in a bounded spatial scope. The norms being bounded in a specific spatial scope facilitates its operationalisation and conformity checks, also reducing the possibilities of norms misinterpretations. Thus, the normative infrastructure connects the physical environment to the organisational structures of the multiagent system. The thesis proposes that this integrated approach to model multi-agent systems may ease the modelling of large scale systems, since it allows the partition of the environment in a modular way, facilitating the operationalisation and verification of the adequacy of the structure of an organisation to the physical space where it is located, and also reducing the possibility of the misinterpretations of norms by the agents, through the contextualisation of norms. Also, the proposed scheme uses a minimal structure for the definition of the organisations in order to store information that the simulation designer prefers to represent in such way. Further, the proposed approach allows a very practical way to use of norms in a physical environment, by allowing the agents to reason about following a norm abiding behaviour or not, since the norms are not hard-wired in their reasoning mechanisms, and its contextualized form facilitates that agents reason about adhering to norms that were previously unknown to them.

Este trabalho tem por objetivo propor uma abordagem para o problema de alocação dinâmica de recursos em ambiente de produção baseada no paradigma de multiagentes. Para tanto, é especificada uma arquitetura multiagente genérica chamada M-DRAP - Multi-agent Dynamic Resource Allocation Planning, a partir da qual podem ser derivados modelos particulares. As principais contribuições deste trabalho compreendem: (i) a definição de uma estratégia que permita o planejamento dinâmico de cada recurso no atendimento as demandas das atividades de produção de forma descentralizada e distribuída, através de uma abordagem orientada a projeto; (ii) a proposição de uma organização social baseada em uma abordagem multiagente orientada a mercado, capaz de propiciar relações de negociação entre agentes autônomos no sentido de atenderem aos seus interesses individuais, contribuindo de forma efetiva para a satisfação dos objetivos e restrições temporais e de custos globais ao sistema de produção como um todo; (iii) a especificação de uma arquitetura multiagente derivada do CIMOSA, representando de forma consistente a estrutura funcional e organizacional de um sistema de produção; (iv) a definição de estratégias baseadas em negociação entre os agentes capazes de propiciarem o tratamento das perturbações que afetam o sistema de produção em tempo real. Como contribuindo associada, e proposta uma metodologia para a modelagem conceitual de sistemas multiagentes para o domínio das aplicações envolvendo modelagem de empresas. / The objective of this work is to propose an approach to the problem of dynamic resource allocation in production systems. A multi-agent reference architecture called M-DRAP - Multi-agent Dynamic Resource Allocation Planning - is specified and described in this thesis. The main contributions of this work are (i) the definition of a decentralised and distributed strategy for dynamic resource allocation planning, using a project oriented approach, (ii) the proposition of a social organisation based on marketoriented behaviour, which considers the necessity of each agent's local plan to converge to an adequate global plan in terms of production costs to the whole system, (iii) the definition of a multi-agent architecture inspired in the CIMOSA reference architecture representing a functional and organisational structure, (iv) the definition of a strategy based on negotiation which propitiates real-time disturbance treatment. As an associated contribution, we propose a methodology to multi-agent systems conceptual modelling adequate to the enterprise modelling domain.

Este trabalho encontra-se situado na área de Inteligência Artificial, mais especificamente na modelagem de Sistemas Multiagentes destinados à simulação social. A área de pesquisa de simulação social baseada em agentes é uma área recente e bastante promissora. Por tratar de problemas extremamente complexos, existe a necessidade de criar modelos e abstrações para possibilitar sua realização. Dando continuidade a trabalhos anteriores, esta tese pretende consolidar uma nova versão do modelo MAS-SOC, destinado à definição de simulações sociais baseada em Sistemas Multiagentes Situados, com organizações que funcionam em ambientes determinados (organizações situadas). É proposta uma abordagem integrada, que conecta de maneira forte as entidades agentes, organizações e ambiente, sendo os agentes, o ambiente e as estruturas da organização tratadas como entidades de primeira ordem. A definição do ambiente é feita através da linguagem ELMS, estendida com uma infraestrutura normativa. Esta infraestrutura normativa é composta basicamente por objetos normativos e espaços normativos que permitem a distribuição espacial da informação normativa no ambiente, possibilitando a contextualização das normas que os agentes devem seguir em um escopo espacial determinado. A contextualização das normas facilita a sua operacionalização e a verificação de conformidade, reduzindo também a possibilidade de interpretações errôneas das normas. Com isso, a infraestrutura normativa conecta ambiente físico à estrutura da organização do sistema multiagente. Além disso, o modelo proposto usa um esquema mínimo de definição das organizações para armazenar informações e restrições que o projetista da simulação prefira representar desta forma. Esta maneira integrada de modelar os sistemas multiagentes, associando a organização ao espaço em que a organização deve funcionar, pode facilitar a modelagem de grandes sistemas, pois o conceito de espaço normativo permite que a modelagem seja feita através da partição do ambiente físico em módulos onde as atividades da organização situada são realizadas. Assim, o modelo trata de forma bastante prática o uso das normas organizacionais que podem ser representadas através de objetos normativos. Esta forma de representação possibilita aos agentes decidirem sobre a aderência as normas, já que estas não estão embutidas no mecanismo de raciocínio dos agentes. Além disso, a forma contextualizada das normas facilita raciocínio sobre elas e possibilita a aderência a normas previamente desconhecidas pelos agentes. / This work is situated in the research area of Artificial Intelligence, specifically the modelling of Multi-agent systems for social simulation. The research area of agent based social simulation is a recent and interesting area. In order to handle with its very complex problems, it requires the development of models and abstractions to make possible its realisation. Continuing previous works, this thesis aims to consolidate extensions to the MAS-SOC model, in order to turn it into a suitable model for the social simulation based on situated multi-agent systems with organizations that operate in determined environments (situated organisations). It is proposed an integrated approach in which multiagent entities such as agents, organisations and environments are strongly connected to each other, and the environment and the organisational structures being treated as first order entities. The definition of the environment is made with the use of the ELMS language, which have been extended with a normative infrastructure. The normative infrastructure is composed essentially by normative objects and normative places, which are means for the spatial distribution of the normative information over the environment, allowing the contextualisation of the norms in a bounded spatial scope. The norms being bounded in a specific spatial scope facilitates its operationalisation and conformity checks, also reducing the possibilities of norms misinterpretations. Thus, the normative infrastructure connects the physical environment to the organisational structures of the multiagent system. The thesis proposes that this integrated approach to model multi-agent systems may ease the modelling of large scale systems, since it allows the partition of the environment in a modular way, facilitating the operationalisation and verification of the adequacy of the structure of an organisation to the physical space where it is located, and also reducing the possibility of the misinterpretations of norms by the agents, through the contextualisation of norms. Also, the proposed scheme uses a minimal structure for the definition of the organisations in order to store information that the simulation designer prefers to represent in such way. Further, the proposed approach allows a very practical way to use of norms in a physical environment, by allowing the agents to reason about following a norm abiding behaviour or not, since the norms are not hard-wired in their reasoning mechanisms, and its contextualized form facilitates that agents reason about adhering to norms that were previously unknown to them.

Doctor of Philosophy / Department of Computing and Information Sciences / Scott A. DeLoach / The Organization-Based Multi-Agent Systems (OMAS) paradigm is an approach to address the challenges posed by complex systems. The complexity of these systems, the changing environment where the systems are deployed, and satisfying higher user expectations are some of current requirements when designing OMAS. For the agents in an OMAS to pursue the achievement of a common goal or task, a certain level of coordination and collaboration occurs among them. An objective in this coordination is to make the decision of who does what. Several solutions have been proposed to answer this task allocation question. The majority of the solutions proposed fall in the categories of marked-based approaches, reactive systems, or game theory approaches. A common fact among these solutions is the system information sharing among agents, which is used only to keep the participant agent informed about other agents activities and mission status. To further exploit and take advantage of this system information shared among agents, a framework is proposed to use this information to answer the question who does what, and reduce the communication among agents. DTAACS-OK is a distributed knowledge-based framework that addresses the Single Agent Task Allocation Problem (SAT-AP) and the Multiple Agent Task Allocation Problem (MAT-AP) in cooperative OMAS. The allocation of tasks is based on an identical organization knowledge posses by all agents in the organization. DTAACS-OK di ers with current solutions in that (a) it is not a marked-based approach where task are auctioned among agents, or (b) it is not based on agents behaviour, where the action or lack of action of an agent cause the reaction of other agents in the organization.

Agent-based computing has attracted much attention as a promising technique for application domains that are distributed, complex and heterogeneous. Current research on multi-agent systems (MAS) has become mature enough to be applied as a technology for solving problems in an increasingly wide range of complex applications. The main formal architectures used to describe the relationships between agents in MAS are centralised and distributed architectures. In computational complexity theory, researchers have classified the problems into the followings categories: (i) P problems, (ii) NP problems, (iii) NP-complete problems, and (iv) NP-hard problems. A method for computing the solution to NP-hard problems, using the algorithms and computational power available nowadays in reasonable time frame remains undiscovered. And unfortunately, many practical problems belong to this very class. On the other hand, it is essential that these problems are solved, and the only possibility of doing this is to use approximation techniques. Heuristic solution techniques are an alternative. A heuristic is a strategy that is powerful in general, but not absolutely guaranteed to provide the best (i.e. optimal) solutions or even find a solution. This demands adopting some optimisation techniques such as Evolutionary Algorithms (EA). This research has been undertaken to investigate the feasibility of running computationally intensive algorithms on multi-agent architectures while preserving the ability of small agents to run on small devices, including mobile devices. To achieve this, the present work proposes a new Hybrid Multi-Agent Architecture (HMAA) that generates new heuristics for solving NP-hard problems. This architecture is hybrid because it is "semi-distributed/semi-centralised" architecture where variables and constraints are distributed among small agents exactly as in distributed architectures, but when the small agents become stuck, a centralised control becomes active where the variables are transferred to a super agent, that has a central view of the whole system, and possesses much more computational power and intensive algorithms to generate new heuristics for the small agents, which find optimal solution for the specified problem. This research comes up with the followings: (1) Hybrid Multi-Agent Architecture (HMAA) that generates new heuristic for solving many NP-hard problems. (2) Two frameworks of HMAA have been implemented; search and optimisation frameworks. (3) New SMA meeting scheduling heuristic. (4) New SMA repair strategy for the scheduling process. (5) Small Agent (SMA) that is responsible for meeting scheduling has been developed. (6) “Local Search Programming” (LSP), a new concept for evolutionary approaches, has been introduced. (7) Two types of super-agent (LGP_SUA and LSP_SUA) have been implemented in the HMAA, and two SUAs (local and global optima) have been implemented for each type. (8) A prototype for HMAA has been implemented: this prototype employs the proposed meeting scheduling heuristic with the repair strategy on SMAs, and the four extensive algorithms on SUAs. The results reveal that this architecture is applicable to many different application domains because of its simplicity and efficiency. Its performance was better than many existing meeting scheduling architectures. HMAA can be modified and altered to other types of evolutionary approaches.

Self-reconfigurable robotic systems are variable-morphology machines capable of changing their overall structure by rearranging the modules they are composed of. Individual modules are capable of connecting and disconnecting to and from one another, which allows the robot to adapt to changing environments. Optimally reconfiguring such systems is computationally prohibitive and thus in general self-reconfiguration approaches aim at approximating optimal solutions. Nonetheless, even for approximate solutions, centralized methods scale poorly in the number of modules. Therefore, the objective of this research is the development of decentralized self-reconfiguration methods for modular robotic systems. Building on completeness results of the centralized algorithms in this work, decentralized methods are developed that guarantee stochastic convergence to a given target shape. A game-theoretic approach lays the theoretical foundation of a novel potential game-based formulation of the self-reconfiguration problem. Furthermore, two extensions to the basic game-theoretic algorithm are proposed that enable agents to modify the algorithms' parameters during runtime and improve convergence times. The flexibility in the choice of utility functions together with runtime adaptability makes the presented approach and the underlying theory suitable for a range of problems that rely on decentralized local control to guarantee global, emerging properties. The experimental evaluation of the presented algorithms relies on a newly developed multi-robotic testbed called the "Robotarium" that is equipped with custom-designed miniature robots, the "GRITSBots". The Robotarium provides hardware validation of self-reconfiguration on robots but more importantly introduces a novel paradigm for remote accessibility of multi-agent testbeds with the goal of lowering the barrier to entrance into the field of multi-robot research and education.

This thesis proposes a holistic and hierarchical architecture to Multi-agent System design, in order to resolve the collaboration problem in diabetic healthcare system. A diabetic healthcare system is a complex and social system in the case that it involves many actors and interrelations. Collaborations among various healthcare actors are vital to the quality of diabetic healthcare. The collaboration problem is manifested by the problems of accessibility and interoperability. To support the collaboration in diabetic healthcare as such a complex and social system, the MAS must have corresponding social entities and relationships. Therefore, it is assumed that theories explaining social activity can be applied to design of MAS. Activity Theory, specifically its holistic triangle model from Engström and hierarchy thinking, provides theoretical supports to the design of individual agent architecture and MAS coordination mechanism. It is argued that the holistic and hierarchical aspects should be designed in a MAS when applied to the healthcare setting. The diabetic healthcare system is analyzed on three levels based on the hierarchy thinking. The collaboration problem is analyzed and resolved via MAS coordination. Based on the holistic activity model in Activity Theory, Müller’s Vertical Layered Architecture is re-conceptualized in the Control Unit and Knowledge Base design. It is also argued that autonomy, adaptivity and persona should be especially focused when designing the interaction between an agent system and human users. This study has firstly identified some important social aspects and the technical feasibility of embedding those identified social aspects in agent architecture design. Secondly, a MAS was developed to illustrate how to apply the proposed architecture to design a MAS to resolve the collaboration problem in diabetic healthcare system. We have designed and implemented an agent system – IMAS (Integrated Multi-agent System) to validate the research questions and contributions. IMAS system provides real time monitoring, diabetic healthcare management and decision supports to the diabetic healthcare actors. A user assessment has been conducted to validate that the quality of the current diabetic healthcare system can be improved with the introduction of IMAS.

Multi-agent systems represent a group of agents that cooperate to solve common tasks in a dynamic environment. Multi-agent control systems have been widely studied in the past few years. The control of multi-agent systems relates to synthesizing control schemes for systems which are inherently distributed and composed of multiple interacting entities. Because of the wide applications of multi-agent theories in large and complex control systems, it is necessary to develop a framework to simplify the process of developing control schemes for multi-agent systems. <br /><br /> In this study, a framework is proposed for the distributed control and coordination of multi-agent systems. In the proposed framework, the control of multi-agent systems is regarded as achieving decentralized control and coordination of agents. Each agent is modeled as a Coordinated Hybrid Agent (CHA) which is composed of an intelligent coordination layer and a hybrid control layer. The intelligent coordination layer takes the coordination input, plant input and workspace input. After processing the coordination primitives, the intelligent coordination layer outputs the desired action to the hybrid layer. In the proposed framework, we describe the coordination mechanism in a domain-independent way, as simple abstract primitives in a coordination rule base for certain dependency relationships between the activities of different agents. The intelligent coordination layer deals with the planning, coordination, decision-making and computation of the agent. The hybrid control layer of the proposed framework takes the output of the intelligent coordination layer and generates discrete and continuous control signals to control the overall process. In order to verify the feasibility of the proposed framework, experiments for both heterogeneous and homogeneous Multi-Agent Systems (MASs) are implemented. In addition, the stability of systems modeled using the proposed framework is also analyzed. The conditions for asymptotic stability and exponential stability of a CHA system are given. <br /><br /> In order to optimize a Multi-Agent System (MAS), a hybrid approach is proposed to address the optimization problem for a MAS modeled using the CHA framework. Both the event-driven dynamics and time-driven dynamics are included for the formulation of the optimization problem. A generic formula is given for the optimization of the framework. A direct identification algorithm is also discussed to solve the optimization problem.

The field of swarm robotics has been growing fast over the last few years. Using a swarm of simple and cheap robots has advantages in various tasks. Apart from performance gains on tasks that allow for parallel execution, simple robots can also be smaller, enabling them to reach areas that can not be accessed by a larger, more complex robot. Their ability to cooperate means they can execute complex tasks while offering self-organised adaptation to changing environments and robustness due to redundancy. In order to keep individual robots simple, a control algorithm has to keep expensive communication to a minimum and has to be able to act on little information to keep the amount of sensors down. The number of sensors and actuators can be reduced even more when necessary capabilities are spread out over different agents that then combine them by cooperating. Self-organised differentiation within these heterogeneous groups has to take the individual abilities of agents into account to improve group performance. In this thesis it is shown that a homogeneous group of versatile agents can not be easily replaced by a heterogeneous group, by separating the abilities of the versatile agents into several specialists. It is shown that no composition of those specialists produces the same outcome as a homogeneous group on a clustering task. In the second part of this work, an adaptation mechanism for a group of foragers introduced by Labella et al. (2004) is analysed in more detail. It does not require communication and needs only the information on individual success or failure. The algorithm leads to self-organised regulation of group activity depending on object availability in the environment by adjusting resting times in a base. A possible variation of this algorithm is introduced which replaces the probabilistic mechanism with which agents determine to leave the base. It is demonstrated that a direct calculation of the resting times does not lead to differences in terms of differentiation and speed of adaptation. After investigating effects of different parameters on the system, it is shown that there is no efficiency increase in static environments with constant object density when using a homogeneous group of agents. Efficiency gains can nevertheless be achieved in dynamic environments. The algorithm was also reported to lead to higher activity of agents which have higher performance. It is shown that this leads to efficiency gains in heterogeneous groups in static and dynamic environments.