La coordinació i assignació de tasques en entorns distribuïts ha estat un punt important de la recerca en els últims anys i aquests temes són el cor dels sistemes multi-agent. Els agents en aquests sistemes necessiten cooperar i considerar els altres agents en les seves accions i decisions. A més a més, els agents han de coordinar-se ells mateixos per complir tasques complexes que necessiten més d'un agent per ser complerta. Aquestes tasques poden ser tan complexes que els agents poden no saber la ubicació de les tasques o el temps que resta abans de que les tasques quedin obsoletes. Els agents poden necessitar utilitzar la comunicació amb l'objectiu de conèixer la tasca en l'entorn, en cas contrari, poden perdre molt de temps per trobar la tasca dins de l'escenari. De forma similar, el procés de presa de decisions distribuït pot ser encara més complexa si l'entorn és dinàmic, amb incertesa i en temps real. En aquesta dissertació, considerem entorns amb sistemes multi-agent amb restriccions i cooperatius (dinàmics, amb incertesa i en temps real). En aquest sentit es proposen dues aproximacions que permeten la coordinació dels agents. La primera és un mecanisme semi-centralitzat basat en tècniques de subhastes combinatòries i la idea principal es minimitzar el cost de les tasques assignades des de l'agent central cap als equips d'agents. Aquest algoritme té en compte les preferències dels agents sobre les tasques. Aquestes preferències estan incloses en el bid enviat per l'agent. La segona és un aproximació d'scheduling totalment descentralitzat. Això permet als agents assignar les seves tasques tenint en compte les preferències temporals sobre les tasques dels agents. En aquest cas, el rendiment del sistema no només depèn de la maximització o del criteri d'optimització, sinó que també depèn de la capacitat dels agents per adaptar les seves assignacions eficientment. Addicionalment, en un entorn dinàmic, els errors d'execució poden succeir a qualsevol pla degut a la incertesa i error de accions individuals. A més, una part indispensable d'un sistema de planificació és la capacitat de re-planificar. Aquesta dissertació també proveeix una aproximació amb re-planificació amb l'objectiu de permetre als agent re-coordinar els seus plans quan els problemes en l'entorn no permeti la execució del pla. Totes aquestes aproximacions s'han portat a terme per permetre als agents assignar i coordinar de forma eficient totes les tasques complexes en un entorn multi-agent cooperatiu, dinàmic i amb incertesa. Totes aquestes aproximacions han demostrat la seva eficiència en experiments duts a terme en l'entorn de simulació RoboCup Rescue. / Distributed task allocation and coordination have been the focus of recent research in last years and these topics are the heart of multi-agent systems. Agents in these systems need to cooperate and consider the other agents in their actions and decisions. Moreover, agents may have to coordinate themselves to accomplish complex tasks that need more than one agent to be accomplished. These tasks may be so complicated that the agents may not know the location of them or the time they have before the tasks become obsolete. Agents may need to use communication in order to know the tasks in the environment, otherwise, it may take a long time to find the tasks into the scenario. Similarly, the distributed decisionmaking process may be even more complex if the environment is dynamic, uncertain and real-time. In this dissertation, we consider constrained cooperative multi-agent environments (dynamic, uncertain and real-time). In this regard, we propose two approaches that enable the agents to coordinate themselves. The first one is a semi-centralized mechanism based on combinatorial auction techniques and the main idea is minimizing the cost of assigned tasks from the central agent to the agent teams. This algorithm takes into account the tasks' preferences of the agents. These preferences are included into the bid sent by the agent. The second one is a completely decentralized scheduling approach. It permits agents schedule their tasks taking into account temporal tasks' preferences of the agents. In this case, the system's performance depends not only on the maximization or the optimization criterion, but also on the agents' capacity to adapt their schedule efficiently. Furthermore, in a dynamic environment, execution errors may happen to any plan due to uncertainty and failure of individual actions. Therefore, an indispensable part of a planning system is the capability of replanning. This dissertation is also providing a replanning approach in order to allow agents recoordinate his plans when the environmental problems avoid fulfil them. All these approaches have been carried out to enable the agents to efficiently allocate and coordinate all their complex tasks in a cooperative, dynamic and uncertain multi-agent scenario. All these approaches have demonstrated their effectiveness in experiments performed in the RoboCup Rescue simulation environment.

Doctor of Philosophy / Department of Computing and Information Sciences / Scott A. DeLoach / Organization-based Multiagent Systems (OMAS) have been viewed as an effective paradigm for addressing the design challenges posed by today’s complex systems. In those systems, the organizational perspective is the main abstraction, which provides a clear separation between agents and systems, allowing a reduction in the complexity of the overall system. To ease the development of OMAS, several methodologies have been proposed. Unfortunately, those methodologies typically require the designer to handle system complexity alone, which tends to lead to ad-hoc designs that are not scalable and are difficult to maintain. Moreover, designing organizations for large multiagent systems is a complex and time-consuming task; design models quickly become unwieldy and thus hard to develop. To cope with theses issues, a framework for organization-based multiagent system designs based on separation of concerns and composition principles is proposed. The framework uses category theory tools to construct a formal composition framework using core models from the Organization-based Multiagent Software Engineering (O-MASE) framework. I propose a formalization of these models that are then used to establish a reusable design approach for OMAS. This approach allows designers to design large multiagent organizations by reusing smaller composable organizations that are developed separately, thus providing them with a scalable approach for designing large and complex OMAS. In this dissertation, the process of formalizing and composing multiagent organizations is discussed. In addition, I propose a service-oriented approach for building autonomous, adaptive multiagent systems. Finally, as a proof of concept, I develop two real world examples from the domain of cooperative robotics and wireless sensor networks.

Service-oriented architectures are a popular architectural paradigm for building software applications from a number of loosely coupled, distributed services. Through a set of procedural rules, workflow technologies define how groups of services coordinate with one another to achieve a shared task. A problem with workflow specifications is that often the patterns of interaction between the distributed services are too complicated to predict and analyse at design-time. In certain cases, the exact patterns of message exchange and the concrete services to call cannot be predicted in advance, due to factors such as fluctuating network load or the availability of services. It is a more realistic assumption to endow software components with the ability to make decisions about the nature and scope of their interactions at runtime. Multiagent systems offer a complementary paradigm: building software applications from a number of self interested, autonomous agents. This thesis presents an investigation into fusing the agency and service-oriented architecture paradigms, in order to facilitate flexible, workflow composition. Our approach offers an agent-based solution to service choreography and is founded on the concept of shared interaction protocols. By adopting an agent-based approach to service choreography, active autonomous agents can utilise the typically passive service-oriented architectures, found in Internet and Grid systems. In contrast with statically defined, centralised service orchestrations, decentralised agents can perform service choreography at runtime, allowing them to operate in scenarios where it is not possible to define the pattern of interaction in advance. Application to real scenarios is a driving factor behind this research. By working closely with a number of active Grid projects, namely AstroGrid and the Large-Synoptic Survey Telescope (LSST), a concrete set of requirements for scientific workflow have been derived, based on realistic science problems. This research has resulted in the MultiAgent Service Choreography (MASC) language to express scientific workflow, methodology for system building and a software framework which performs agent based Web service choreography, in order to enact distributed e-Science experiments. Evaluation of this thesis is conducted through case study, applying the language, methodology and software framework to solve a motivating set of workflow scenarios.

Fundamental aspects of biologically-inspired regulatory mechanisms are considered in a robotics context, using artificial neural-network control systems . Regulatory mechanisms are used to control expression of genes, adaptation of form and behavior in organisms. Traditional neural network control architectures assume networks of neurons are fixed and are interconnected by wires. However, these architectures tend to be specified by a designer and are faced with several limitations that reduce scalability and tractability for tasks with larger search spaces. Traditional methods used to overcome these limitations with fixed network topologies are to provide more supervision by a designer. More supervision as shown does not guarantee improvement during training particularly when making incorrect assumptions for little known task domains. Biological organisms often do not require such external intervention (more supervision) and have self-organized through adaptation. Artificial neural tissues (ANT) addresses limitations with current neural-network architectures by modeling both wired interactions between neurons and wireless interactions through use of chemical diffusion fields. An evolutionary (Darwinian) selection process is used to ‘breed’ ANT controllers for a task at hand and the framework facilitates emergence of creative solutions since only a system goal function and a generic set of basis behaviours need be defined. Regulatory mechanisms are formed dynamically within ANT through superpositioning of chemical diffusion fields from multiple sources and are used to select neuronal groups. Regulation drives competition and cooperation among neuronal groups and results in areas of specialization forming within the tissue. These regulatory mechanisms are also shown to increase tractability without requiring more supervision using a new statistical theory developed to predict performance characteristics of fixed network topologies. Simulations also confirm the significance of regulatory mechanisms in solving certain tasks found intractable for fixed network topologies. The framework also shows general improvement in training performance against existing fixed-topology neural network controllers for several robotic and control tasks. ANT controllers evolved in a low-fidelity simulation environment have been demonstrated for a number of tasks on hardware using groups of mobile robots and have given insight into self-organizing system. Evidence of sparse activity and use of decentralized, distributed functionality within ANT controller solutions are found consistent with observations from neurobiology.

Multiagent systems offer a design paradigm used to conceptualise and implement systems composed of autonomous agents. Autonomy facilitates proactive independent behaviour yet in practice agents are constrained in order to ensure the system satisfies a desired social objective. Explicit constraints on agent behaviour, in the form of social norms, encourage this desirable system behaviour, yet research has largely focused on norm representation languages and protocols for norm proposal and adoption. The fundamental problem of how to automate the process of norm synthesis has largely been overlooked with norms assumed provided by the designer. Previous work has shown that automating the design of social norms is intractable in the worst case. Existing approaches, relying on state space enumerations, are effective for small systems but impractical for larger ones. Furthermore, they do not produce a set of succinct, general norms but rather a large number of state-specific restrictions. This work presents conflict-rooted synthesis, an automated norm synthesis approach that utilises a planning-based action schemata to overcome these limitations. These action schemata facilitate localised searches around specifications of undesirable states, using representations of sets of system states to avoid a full state enumeration. The proposed technique produces concise, generalised social norms that are applicable in multiple system states while also providing guarantees that agents are still able to achieve their original goals in the constrained system. To improve efficiency a set of theoretically sound, domain-independent optimisations are presented that reduce the state space searched without compromising the quality of the norms synthesised. A comparison with an alternative model checking based technique illustrates the advantages and disadvantages of our approach, while an empirical evaluation highlights the improved efficiency and quality of norms it produces at the cost of a less expressive specification of undesirable states. We empirically investigate the effectiveness of each of the proposed optimisations using a set of benchmark domains, quantifying how successful each of them is at reducing search complexity in practice. The results show that, with all optimisations enabled, conflict-rooted synthesis produces more generally applicable and succinct norms and consumes fewer system resources. Additionally, we show that this approach synthesises norms in systems where the competing approach is intractable. We provide a discussion of our approach, highlighting the impact our abstract search approach has on the fields of multiagent systems and automated planning, and discuss the limitations and assumptions we have made. We conclude with a presentation of future work.

This thesis provides an implementation of consensus of multi-agent networked systems. Consensus problem is an important issue of distributed computing and has various algorithms and applications in the field of electronical and computer science. The consensus requests all nodes of a network reach an agreement over a certain measurement. An algorithm of convergent consensus problem is implemented through a small network of Bluetooth communication in the thesis. The connections of the Bluetooth devices are wireless, and the device nodes of the network are driven by C++ software and Winsock API. The simulation results show that the implementation completes all the requirements of the distributed consensus algorithm.

Doctor of Philosophy / Department of Computing and Information Sciences / Scott A. DeLoach / There is a growing demand for more effective integration of humans and computing systems, specifically in multiagent and multirobot systems. There are two aspects to consider in human integration: (1) the ability to control an arbitrary number of robots (particularly heterogeneous robots) and (2) integrating humans as peers in computing systems instead of being just users or supervisors. With traditional supervisory control of multirobot systems, the number of robots that a human can manage effectively is between four and six [17]. A limitation of traditional supervisory control is that the human must interact individually with each robot, which limits the upper-bound on the number of robots that a human can control effectively. In this work, I define the concept of "organizational control" together with an autonomous mechanism that can perform task allocation and other low-level housekeeping duties, which significantly reduces the need for the human to interact with individual robots. Humans are very versatile and robust in the types of tasks they can accomplish. However, failures in computing systems are common and thus redundancies are included to mitigate the chance of failure. When all redundancies have failed, system failure will occur and the computing system will be unable to accomplish its tasks. One way to further reduce the chance of a system failure is to integrate humans as peer "agents" in the computing system. As part of the system, humans can be assigned tasks that would have been impossible to complete due to failures.

Muitos problemas de otimização em ambientes multiagentes utilizam os algoritmos evolutivos para encontrar as melhores soluções. Uma das abordagens mais utilizadas consiste na aplicação de um algoritmo genético, como alternativa aos métodos tradicionais, para definir as ações dos jogadores em um time de futebol de robôs. Entretanto, conforme relatado na literatura, há inúmeras possibilidades e formas de se aplicar um algoritmo genético no domínio do futebol de robôs. Assim sendo, neste trabalho buscou-se realizar uma análise comparativa dos algoritmos genéticos mono-objetivo e multi-objetivo aplicados no domínio do futebol de robôs. O problema padrão escolhido para realizar essa análise foi de desenvolver uma estratégia de controle autônomo, a fim de capacitar que os robôs tomem decisões sem interferência externa, pois, além de sua solução se encontrar ainda em aberto, o mesmo é também de suma relevância para a área de robótica. / Many optimization problems in multiagent environments adapt evolutionary algorithms to find the best solutions. A widely used approach consists of applying a genetic algorithm as an alternative to traditional methods, in order to define the actions of the players on a soccer team of simulated robots. However, as reported in the literature, there are many possibilities and ways to apply a genetic algorithm in the field of robot soccer. Therefore, this work attempts to make a comparative analysis of mono-objective and multi-objective genetic algorithms applied to control a robot soccer. The standard problem chosen for this analysis was to develop a strategy for autonomous control, in order to enable the robots to make decisions without external interference, because in addition to its solution is still open, it is also of utmost relevance to the area robotics.

Os múltiplos trabalhos de sistemas multiagentes musicais realizados nos últimos anos demonstram o interesse crescente na pesquisa de sistemas de composição e de performance musical que utilizem a tecnologia de agentes computacionais, sendo que apresentam um interesse maior por aqueles sistemas que integram técnicas de composição algorítmica, componentes de vida artificial e interatividade. Observamos também que a maioria dos trabalhos existentes apresentam muitas limitações em termos de escopo e flexibilidade, normalmente apresentando codificação musical simbólica e a resolução de um único problema, sendo que a motivação é mais técnica do que musical. Nesse contexto, surgem arcabouços voltados à criação de sistemas multiagentes musicais, como o Ensemble e o Interactive Swarm Orchestra, oferecendo flexibilidade para a modelagem e implementação de sistemas desse tipo, diversificando tanto os tipos de aplicação, tendo um propósito composicional ou performático, como os tipos de codificação musical que podem ser utilizados. Partimos da aparição dessas ferramentas para estudar o agente musical a partir de uma perspectiva interna, focando nos seus raciocínios, que são processos que definem o comportamento do agente no ambiente virtual do sistema e que são fundamentais para determinar e melhorar o seu valor composicional. Os arcabouços estudados se diferenciam por permitir a utilização de áudio como possível formato de codificação musical, o aproveitamento da espacialização sonora e a exploração da interatividade nos aplicativos, seja esta apenas entre agentes computacionais ou entre agentes e usuários humanos. Pretendemos portanto, nessa pesquisa, abordar sistemas com essas características. Através de extensões nos arcabouços e estudos de caso com motivação estética pretendemos dar continuidade a esses projetos e ao mesmo tempo validar e divulgar a sua utilização entre os potenciais usuários das ferramentas, como compositores, músicos interessados em performance e outros entusiastas dos sistemas musicais interativos. / Multiple musical multiagent systems have been developed in the last years proving the increasing interest in composition and musical performance systems that exploit intelligent agents technology. Theres an special focus on systems that integrate algorithmic composition techniques, artificial life and interactivity. We can also observe that most of these existing projects show many flexibility and scope limitations, as they normally use symbolic musical notation and they solve a single issue or scenario, as well as they have a technical motivation rather than a musical one. In that context, some musical multiagent systems frameworks as Ensemble and Interactive Swarm Orchestra emerge, trying to help the modeling and development of this kind of musical systems, diversifying the applications\' types, as they can be composition problems or musical performances, and allowing the inclusion of other kind of musical content communication. Through these new tools we study the musical agent from an internal perspective, focusing on its reasoning components, processes that define the behavior of an agent on its system\'s virtual environment and that are essential to determine and improve its compositional value. The studied frameworks show unique features as they support audio as a possible musical notation format; they exploit sound spatialization and they work with interactivity in their applications, including agent-to-agent or human-to-agent interaction. We will explore this type of systems on this research. Through framework extensions and aesthetics-oriented study cases we pretend to continue these projects and validate them at same time. We also will contact potential users for these tools, as composers and musicians interested in performances or other musical interactive systems enthusiasts.

Nesta tese, propõe-se integrar, de modo sistemático, modelos organizacionais para prover interoperabilidade organizacional em sistemas multiagentes abertos. A interoperabilidade organizacional consiste em permitir que, em uma mesma organização de agentes, coexistam agentes desenvolvidos a partir de modelos organizacionais distintos. Para realizar tal intuito, aplica-se uma abordagem baseada em técnicas da Engenharia Dirigida por Modelos. A abordagem proposta divide-se em três etapas principais: (1) representar a estrutura conceitual de modelos organizacionais através de metamodelos; (2) identificar correspondências entre as estruturas conceituais dos modelos organizacionais utilizando como heurística a idéia de dimensões e padrões de modelagem organizacional ; e (3) combinar os metamodelos dos modelos organizacionais seguindo um algoritmo de junção de modelos baseado em grafos e articulações de grafos. Utilizando a abordagem proposta, quatro modelos organizacionais existentes são integrados: os modelos AGR, STEAM, MOISE+ e ISLANDER. Para ilustrar o uso da integração de metamodelos no problema de interoperabilidade organizacional, especifica-se e implementa-se uma infraestrutura de interoperabilidade organizacional chamada MAORI (Model-driven Architecture for Organizational Interoperability). A infraestrutura MAORI é estruturada em duas camadas: (1) a camada M2M, na qual a integraçãoo de modelos realizada é utilizada para traduzir especificações e estados organizacionais, e (2) a camada ORI, na qual infraestruturas organizacionais são interconectadas. Para testar e validar toda a proposta, a infraestrutura MAORI foi implementada para as infraestruturas organizacionais S-MOISE+ e MADKIT, e uma aplicaçào denominada WritePaper foi desenvolvida. A partir das implementações, alguns experimentos foram realizados. Os resultados obtidos demonstram que a integração de modelos organizacionais proposta, realizada na infraestrutura de interoperabilidade MAORI, efetivamente interconecta infraestruturas organizacionais distintas e permite que, em uma mesma organização de agentes, coexistam agentes desenvolvidos a partir de modelos organizacionais distintos. / This thesis proposes to integrate systematically organizational models for providing organizational interoperability in open multiagent systems. Organizational interoperability consists in enabling the participation, in the same agent organization, of agents developed with different organizational models. For this purpose, it is applied an approach based on techniques from Model-driven Engineering. The approach is divided in three main steps: (1) to represent the conceptual structure of organizational models by means of metamodels; (2) to identify correspondences among the conceptual structures of the organizational models using as heuristics the idea of organizational modeling dimensions and patterns; (3) to combine the metamodels of the organizational models by following a merge algorithm based on graphs and graph articulations. Using the proposed approach, four existing organizational models are integrated: AGR, STEAM, MOISE+ and ISLANDER. To illustrate the use of the integration, an organizational interoperability infrastructure called MAORI (Model-driven Architecture for Organizational Interoperability) is specified and implemented. The MAORI infrastructure is structured in two layers: (1) the M2M layer, in which the integration of models is used to translate the organizational specifications and states, and (2) the ORI layer, in which the organizational infrastructures are interconnected. To test and validate the approach, MAORI infrastructure was implemented for the organizational infrastructures S-MOISE+ and MADKIT, and an application called Write Paper was developed. Using the implementations, some experiments were done. The results show that the organizational model integration, implemented in the MAORI infrastructure, effectively interconnects distinct organizational infrastructures and enables the participation, in the same agent organization, of agents developed with different organizational models.