A scenario where multiple entities interact with a common environment to achieve individual and common goals either co-operatively or competitively can be classified as a Multi-Agent System. In this thesis, we concentrate on the situations where the agents exhibit selfish, competitive and strategic behaviour, giving rise to interesting game theoretic and optimization problems. From a computational point of view, the presence of multiple agents introduces strategic and temporal issues, apart from enhancing the difficulty of optimization. We study the following natural mathematical models of such multi-agent problems faced in practice: a) combinatorial optimization problems with multi-agent submodular cost functions, b) combinatorial auctions with partially public valuations and c) online vertex-weighted bipartite matching and single bid budgeted allocations. We provide approximation algorithms, online algorithms and hardness of approximation results for these problems.

The objectives of this research are to extend cooperative control methods based on potential games to dynamic environments and to develop an experimental test bed to illustrate theoretical results. Cooperative control concerns coordinating a collective performance of multiple autonomous agents. Possible applications include mobile sensor networks, distributed computation, and unmanned vehicle teams. Prior work has explored game theory, specifically the framework of potential games, as an approach to cooperative control, but has been restricted to static environments. This research shows that potential game based cooperative control also can be applied to dynamic environment problems. The approach is illustrated on three example problems. The first one is a moving target tracking problem using a modified form of the learning algorithm, restrictive log-linear learning. The second example is mobile sensor coverage for an unknown dynamic environment. The last example is multi-agent path optimization using payoff based learning. The performances of the developed systems are studied by simulation. The last part of this thesis develops an experimental moving target tracking system using multiple mobile robots. Finally, the thesis concludes with suggestions for future research directions.

Les Systèmes Multi-Agents Ouverts et Décentralisés (SMAOD) sont<br />particulièrement vulnérables à l'introduction d'agents mal conçus ou<br />malveillants. Il est donc nécessaire de contrôler ces systèmes.<br /><br />Dans cette thèse, nous proposons le modèle LIAR, permettant aux<br />agents eux-mêmes de mettre en place un contrôle des interactions des<br />autres agents, à l'aide d'un modèle de réputation.<br /><br />Ce modèle permet d'abord aux agents de représenter les interactions<br />qu'ils perçoivent grâce à des engagements sociaux, ainsi que de<br />modéliser les règles que chaque agent doit respecter à l'aide de<br />normes sociales. En comparant les comportements qu'ils ont observés<br />aux normes dont ils ont connaissance, les agents sont capables<br />d'évaluer leurs pairs et d'estimer les niveaux de réputation qu'ils<br />leur associent. Ensuite, les agents peuvent décider des sanctions à<br />appliquer en s'appuyant sur les niveaux de réputation ainsi estimés.<br /><br />Grâce à l'intégration des deux phases : évaluation des comportements<br />et décision des sanctions à appliquer, le modèle LIAR permet de<br />mettre en place un contrôle social des interactions entièrement<br />automatisé.<br /><br />Diverses expérimentations ont été menées avec ce modèle dans le cadre<br />d'un réseau pair-à-pair, afin de montrer comment les agents contrôlent<br />les interactions de leurs pairs.

Artificial immune systems (AIS), biologically inspired from natural immune functions, can be reactive as well as adaptive in handling generic and varying pathogens, respectively. Researchers have used the immunological metaphors to solve science and engineering problems where unknown/unexpected scenarios are plausible. AIS can be a suitable choice for various robotic applications requiring reactive and/or deliberative control. This research aims to translate modern trends in immunology, to develop an immunity-based framework, to control a team of heterogenous robots on varying levels of task allocation and mutual interactions. The presented framework is designed to work as a multi-agent system in which safe environment is treated reactively through innate immunity, whereas unsafe situations invoke adaptive part of immune system, simultaneously. Heterogeneity is defined in terms of different sensing and/or actuation capabilities as well as in terms of different behavior-sets robot(s) possess. Task allocation ranges from primitive to advanced behaviors. Mutual interactions, on the other hand, range from simpler one-to-one interaction to mutual coordination. In this context, a new immunity-based algorithm has been developed & tested, combining innate and adaptive immunities, to regulate cell populations and corresponding maturations, along with internal health indicators, in order to effectively arbitrate behaviors/robots in a heterogenous robotic system, in environments that are dynamic and unstructured. / text

While evolutionary computation is well suited for automatic discovery in engineering, it can also be used to gain insight into how humans and organizations could perform more effectively. Using a real-world problem of innovation search in organizations as the motivating example, this dissertation formalizes human creative problem solving as competitive multi-agent search. It differs from existing single-agent and team-search problems in that the agents interact through knowledge of other agents' searches and through the dynamic changes in the search landscape caused by these searches. The main hypothesis is that evolutionary computation can be used to discover effective strategies for competitive multi-agent search. This hypothesis is verified in experiments using an abstract domain based on the NK model, i.e. partially correlated and tunably rugged fitness landscapes, and a concrete domain in the form of a social innovation game. In both domains, different specialized strategies are evolved for each different competitive environment, and also strategies that generalize across environments. Strategies evolved in the abstract domain are more effective and more complex than hand-designed strategies and one based on traditional tree search. Using a novel spherical visualization of the fitness landscapes of the abstract domain, insight is gained about how successful strategies work, e.g. by tracking positive changes in the landscape. In the concrete game domain, human players were modeled using backpropagation, and used as opponents to create environments for evolution. Evolved strategies scored significantly higher than the human models by using a different proportion of actions, providing insights into how performance could be improved in social innovation domains. The work thus provides a possible framework for studying various human creative activities as competitive multi-agent search in the future. / text

Heterogeneous multi-agent systems are currently used in a wide variety of situations, including search and rescue, military applications, and off-world exploration, however it is difficult to understand the actions of these systems or naturalistically assign these mixed teams to tasks. These agents, which may be human, robot or software, have different capabilities but will need to coordinate effectively with humans in order to operate. The first and largest contributing factor to this challenge is the processing, understanding and representing of elements of the natural world in a manner that can be utilized by artificial agents. A second contributing factor is that current abstractions and robot architectures are ill-suited to address this problem. This dissertation addresses the lack of a high-level abstraction for the naturalistic coordination of teams of heterogeneous robots, humans and other agents through the development of roles. Roles are a fundamental concept of social science that may provide this necessary abstraction. Roles are not a new concept and have been used in a number of related areas. This work draws from these fields and constructs a coherent and usable model of roles for robotics. This research is focussed on answering the following question: Can the use of social roles enable the naturalistic coordinated operation of robots in a mixed setting? In addition to this primary question, related research includes defining the key concepts important to artificial systems, providing a mapping and implementation from these concepts to a usable robot framework and identifies a set of robot-specific roles used for human-robot interaction. This research will benefit both the artificial intelligence agent and robotics communities. It poses a fundamental contribution to the multi-agent community because it extends and refines the role concept. The application of roles in a principled and complete implementation is a novel contribution to both software and robotic agents. The creation of an open source operational architecture which supports taskable robots is also a major contribution.

Over the past few years, mining data located in heterogeneous and geographically distributed sites have been designated as one of the key important issues. Loading distributed data into centralized location for mining interesting rules is not a good approach. This is because it violates common issues such as data privacy and it imposes network overheads. The situation becomes worse when the network has limited bandwidth which is the case in most of the real time systems. This has prompted the need for intelligent data analysis to discover the hidden information in these huge amounts of distributed databases. In this research, we present an incremental approach for building an efficient Multi-Agent based algorithm for mining real world databases in geographically distributed sites. First, we propose the Distributed Multi-Agent Association Rules algorithm (DMAAR) to minimize the all-to-all broadcasting between distributed sites. Analytical calculations show that DMAAR reduces the algorithm complexity and minimizes the message communication cost. The proposed Multi-Agent based algorithm complies with the Foundation for Intelligent Physical Agents (FIPA), which is considered as the global standards in communication between agents, thus, enabling the proposed algorithm agents to cooperate with other standard agents. Second, the BitTable Multi-Agent Association Rules algorithm (BMAAR) is proposed. BMAAR includes an efficient BitTable data structure which helps in compressing the database thus can easily fit into the memory of the local sites. It also includes two BitWise AND/OR operations for quick candidate itemsets generation and support counting. Moreover, the algorithm includes three transaction trimming techniques to reduce the size of the mined data. Third, we propose the Pruning Multi-Agent Association Rules algorithm (PMAAR) which includes three candidate itemsets pruning techniques for reducing the large number of generated candidate itemsets, consequently, reducing the total time for the mining process. The proposed PMAAR algorithm has been compared with existing Association Rules algorithms against different benchmark datasets and has proved to have better performance and execution time. Moreover, PMAAR has been implemented on real world distributed medical databases obtained from more than one hospital in Egypt to discover the hidden Association Rules in patients' records to demonstrate the merits and capabilities of the proposed model further. Medical data was anonymously obtained without the patients' personal details. The analysis helped to identify the existence or the absence of the disease based on minimum number of effective examinations and tests. Thus, the proposed algorithm can help in providing accurate medical decisions based on cost effective treatments, improving the medical service for the patients, reducing the real time response for the health system and improving the quality of clinical decision making.

Construction usually involves careful preplanning and direct human operation of tools and material. Bringing automation to construction has the potential to improve its speed and efficiency, and to enable building in settings where it is difficult or dangerous for humans to work, e.g., in extraterrestrial environments or disaster areas. Nature provides us with impressive examples of animal construction: in particular, many species of termites build complex mounds several orders of magnitude larger than themselves. Inspired by termites and their building activities, our goal is to develop systems in which large numbers of robots collectively construct human-scale structures autonomously. In this thesis I present TERMES, a system comprised of (1) A high-level control algorithm for decentralized construction of 3D user-specified structures using stigmergy, exploiting implicit rather than explicit communication; and (2) A complete physical implementation where three robots reliably assemble such structures using only local sensing, limited locomotion, and simple control, exploiting embodied rather than explicit intelligence. A major contribution of this work is the translation from abstract models to a real robotic system. I achieved this through careful co-design of algorithms and physical systems and of robots and building material, allowing passive mechanical features to minimize control complexity. To attain reliable performance without relying on costly high-precision sensors and actuators, I put an emphasis on error-tolerant control, making robots able to autonomously detect and recover from small errors. This work advances the aim of engineering collectives of robots that achieve human-specified goals, using biologically-inspired principles for robustness and scalability. While our work is inspired by models of termite construction from the 1970s and 1980s, much is still unknown about how individual termites coordinate and respond to different environmental factors. To address this issue I developed methods and tools to enable high-resolution quantitative data collection on the behavior of individual termites engaged in collective construction in confined experimental arenas. This work advances our ability to study the termites which will hopefully lead to new insights on the design of robust autonomous systems for collective construction. / Engineering and Applied Sciences

In concept, online communities allow people to access the wide range of knowledge and abilities of a heterogeneous group of users. In reality, current implementations of various online communities suffer from a lack of participation by the most qualified users. The participation of qualified users, or experts, is crucial to the social welfare and widespread adoption of such systems. This research proposes techniques for identifying the most valuable contributors to several classes of online communities, including question and answer (QA) forums and other content-oriented social networks. Once these target users are identified, content recommendation and novel quantitative incentives can be used to encourage their participation. This research represents an in-depth investigation into QA systems, while the major findings are widely applicable to online communities in general. An algorithm for recommending content in a QA forum is introduced which can route questions to the most appropriate responders. This increases the efficiency of the system and reduces the time investment of an expert responder by eliminating the need to search for potential questions to answer. This recommender is analyzed using real data captured from Yahoo! Answers. Additionally, an incentive mechanism for QA systems based on a novel class of incentives is developed. This mechanism relies on systemic rewards, or rewards that have tangible value within the framework of the online community. This research shows that human users have a strong preference for reciprocal systemic rewards over traditional rewards, and a simulation of a QA system based on an incentive that utilizes these reciprocal rewards outperforms a leading incentive mechanism according to expert participation. An architecture is developed for a QA system built upon content recommendation and this novel incentive mechanism. This research shows that it is possible to identify the most valuable contributors to an online community and motivate their participation through a novel incentive mechanism based on meaningful rewards. / text

Η διατριβή ασχολείται με το πρόβλημα της διαλειτουργικότητας και συνεργασίας εκπαιδευτικών εφαρμογών στο διαδίκτυο. Η έρευνα οδήγησε στη σχεδίαση και υλοποίηση ενός πρωτότυπου περιβάλλοντος που στηρίζεται στην αρχιτεκτονική πολλαπλών πρακτόρων και επιτρέπει τη συνεργασία μεταξύ των εκαπιδευτικών κόμβων να υποστηρίξουν μαθησιακές δυσκολίες του από απόσταση εκπαιδευομένου. / This thesis focuses on the problem of the interoperability an d cooperation between educational applications in the open enviroment of the World Wide Web. The research led to the design and development of a prototype enviroment (Multi Agent Tutoring System MATS) that implements the collaboration among educational nodes in order to support the needs of a distantr learner.