Satisficing was introduced by the economist Herbert Simon to allow for decisions that are "good enough" when there are insufficient computational resources and knowledge to obtain the optimal outcome. Autonomous multi-agent systems often require such decision making because of the complexity and unknown factors present in such an environment. Satisficing has been extended significantly by Wynn Stirling. Through extended satisficing, he has departed from conventional approaches to autonomous multi-agent systems, based as they usually are on the assumption that each participant is motivated exclusively by its own self interest, and will therefore attempt to maximize its benefit, regardless of the benefit or cost to others. He considers an alternative view based on the assumption that, when forming its preferences, the agent is willing to take into consideration the preferences of others. This thesis explores the application of satisficing to simulated soccer, an autonomous multi-agent system with significant inherent complexity. The work described in this thesis shows that satisficing provides an easy way to switch between an agent's various roles, to take into consideration the likely goals and actions of other agents, and to work in conjunction with a genetic algorithm to help optimize parameters. Some principles of developing simple and concise satisficing code are suggested. Satisficing is thus shown to be an effective solution to decision making in complex multi-agent systems.

Policy Hill Climbing (PHC) is a reinforcement learning algorithm that extends Q-learning to learn probabilistic policies for multi-agent games. WoLF-PHC extends PHC with the "win or learn fast" principle. A proof that PHC will diverge in self-play when playing Shapley's game is given, and WoLF-PHC is shown empirically to diverge as well. Various WoLF-PHC based modifications were created, evaluated, and compared in an attempt to obtain convergence to the single shot Nash equilibrium when playing Shapley's game in self-play without using more information than WoLF-PHC uses. Partial Commitment WoLF-PHC (PCWoLF-PHC), which performs best on Shapley's game, is tested on other matrix games and shown to produce satisfactory results.

Satisficing game theory is an alternative to traditional non-cooperative game theory which offers increased flexibility in modeling players' social interactions. However, satisficing players with conflicting attitudes may implement dysfunctional behaviors, leading to poor performance. In this thesis, we present two attempts to "bridge the gap" between satisficing and non-cooperative game theory. First, we present an evolutionary method by which players adapt their attitudes to increase raw payoff, allowing players to overcome dysfunction. We extend the Nash equilibrium concept to satisficing games, showing that the evolutionary method presented leads the players toward an equilibrium in their attitudes. Second, we introduce the conditional utility functions of satisficing theory into an otherwise traditional non-cooperative framework. While the conditional structure allows increased social flexibility in the players' behaviors, players maximize individual utility in the traditional sense, allowing us to apply the Nash equilibrium. We find that, by adjusting players' attitudes, we may alter the Nash equilibria that result.

Deep Reinforcement Learning (DRL) is a new research area, which integrates deep neural networks into reinforcement learning algorithms. It is revolutionizing the field of AI with high performance in the traditional challenges, such as natural language processing, computer vision etc. The current deep reinforcement learning algorithms enable an end to end learning that utilizes deep neural networks to produce effective actions in complex environments from high dimensional sensory observations, such as raw images. The applications of deep reinforcement learning algorithms are remarkable. For example, the performance of trained agent playing Atari video games is comparable, or even superior to a human player. Current studies mostly focus on training single agent and its interaction with dynamic environments. However, in order to cope with complex real-world scenarios, it is necessary to look into multiple interacting agents and their collaborations on certain tasks. This thesis studies the state-of-the-art deep reinforcement learning algorithms and techniques. Through the experiments conducted in several 2D and 3D game scenarios, we investigate how DRL models can be adapted to train multiple agents cooperating with one another, by communications and physical navigations, and achieving their individual goals on complex tasks. / Djup förstärkningsinlärning (DRL) är en ny forskningsdomän som integrerar djupa neurala nätverk i inlärningsalgoritmer. Det har revolutionerat AI-fältet och skapat höga förväntningar på att lösa de traditionella problemen inom AI-forskningen. I detta examensarbete genomförs en grundlig studie av state-of-the-art inom DRL-algoritmer och DRL-tekniker. Genom experiment med flera 2D- och 3D-spelscenarion så undersöks hur agenter kan samarbeta med varandra och nå sina mål genom kommunikation och fysisk navigering.

Mapping is an enabler for further actions. With the map of an area available, it is possible to plan ahead. Maps of landmasses and heavily used deep waters have been produced and are in use but many shallow waters have been largely unmapped. This thesis proposes and examines two methods of control to produce depth maps of shallow waters using multiple autonomous surface vehicles. Assumptions about the environment are kept to a minimum and agents are expected to explore and map inside a given polygonal boundary. Gaussian process regression is used to guide the agents to areas with large uncertainty. A group of autonomous surface vehicles are used for experimental evaluation. Existing works in this area are compared with the method proposed in this thesis to evaluate map quality and time needed to create the map. Results show that one of the proposed methods is best suited for fast and raw map generation while the other strikes a good balance between accuracy and speed. / Att ha tillgång till en karta över ett område är en förutsättning för många olika aktiviteter, och därför har det skapats allt mer exakta kartor över de flesta landområden. För hav och sjöar har man skapat mer ungefärliga djupkartor för att undvika grundstötningar för sjöfart. Grundare områden har däremot ofta undvikits av stora djupmätningsfartyg, och är därför i hög grad okarterade.I denna rapport föreslås och analyseras en metod för att kartera djupet i grunda områden med hjälp av en grupp autonoma ytfarkoster. Givet en polygon inom vilken man vill ha botten karterad skall gruppen autonomt söka av området med få ytterligare antaganden. Gaussiska processer används för att styra farkosterna mot områden med stora mätosäkerheter, och algoritmen utvärderas i riktiga experiment.Resultaten jämförs med befintliga metoders prestanda, med avseende på kartkvalitet och tid för kartering. Resultaten visar att en av de föreslagna metoderna är snabb men mindre noggrann, medan den andra ger en bättre avvägning mellan kvalitet och uppdragstid.

In this dissertation, we consider differential games for multi-agent systems under distributed information where every agent is only able to acquire information about the others according to a directed information graph of local communication/sensor networks. Such games arise naturally from many applications including mobile robot coordination, power system optimization, multiplayer pursuit-evasion games, etc. Since the admissible strategy of each agent has to conform to the information graph constraint, the conventional game strategy design approaches based upon Riccati equation(s) are not applicable because all the agents are required to have the information of the entire system. Accordingly, the game strategy design under distributed information is commonly known to be challenging. Toward this end, we propose novel open-loop and feedback game strategy design approaches for Nash equilibrium and noninferior solutions with a focus on linear quadratic differential games. For the open-loop design, approximate Nash/noninferior game strategies are proposed by integrating distributed state estimation into the open-loop global-information Nash/noninferior strategies such that, without global information, the distributed game strategies can be made arbitrarily close to and asymptotically converge over time to the global-information strategies. For the feedback design, we propose the best achievable performance indices based approach under which the distributed strategies form a Nash equilibrium or noninferior solution with respect to a set of performance indices that are the closest to the original indices. This approach overcomes two issues in the classical optimal output feedback approach: the simultaneous optimization and initial state dependence. The proposed open-loop and feedback design approaches are applied to an unmanned aerial vehicle formation control problem and a multi-pursuer single-evader differential game problem, respectively. Simulation results of several scenarios are presented for illustration.

This dissertation addresses the problem of influence maximization in social networks. In- fluence maximization is applicable to many types of real-world problems, including modeling contagion, technology adoption, and viral marketing. Here we examine an advertisement domain in which the overarching goal is to find the influential nodes in a social network, based on the network structure and the interactions, as targets of advertisement. The assumption is that advertisement budget limits prevent us from sending the advertisement to everybody in the network. Therefore, a wise selection of the people can be beneficial in increasing the product adoption. To model these social systems, agent-based modeling, a powerful tool for the study of phenomena that are difficult to observe within the confines of the laboratory, is used. To analyze marketing scenarios, this dissertation proposes a new method for propagating information through a social system and demonstrates how it can be used to develop a product advertisement strategy in a simulated market. We consider the desire of agents toward purchasing an item as a random variable and solve the influence maximization problem in steady state using an optimization method to assign the advertisement of available products to appropriate messenger agents. Our market simulation 1) accounts for the effects of group membership on agent attitudes 2) has a network structure that is similar to realistic human systems 3) models inter-product preference correlations that can be learned from market data. The results on synthetic data show that this method is significantly better than network analysis methods based on centrality measures. The optimized influence maximization (OIM) described above, has some limitations. For instance, it relies on a global estimation of the interaction among agents in the network, rendering it incapable of handling large networks. Although OIM is capable of finding the influential nodes in the social network in an optimized way and targeting them for advertising, in large networks, performing the matrix operations required to find the optimized solution is intractable. To overcome this limitation, we then propose a hierarchical influence maximization (HIM) iii algorithm for scaling influence maximization to larger networks. In the hierarchical method the network is partitioned into multiple smaller networks that can be solved exactly with optimization techniques, assuming a generalized IC model, to identify a candidate set of seed nodes. The candidate nodes are used to create a distance-preserving abstract version of the network that maintains an aggregate influence model between partitions. The budget limitation for the advertising dictates the algorithm’s stopping point. On synthetic datasets, we show that our method comes close to the optimal node selection, at substantially lower runtime costs. We present results from applying the HIM algorithm to real-world datasets collected from social media sites with large numbers of users (Epinions, SlashDot, and WikiVote) and compare it with two benchmarks, PMIA and DegreeDiscount, to examine the scalability and performance. Our experimental results reveal that HIM scales to larger networks but is outperformed by degreebased algorithms in highly-connected networks. However, HIM performs well in modular networks where the communities are clearly separable with small number of cross-community edges. This finding suggests that for practical applications it is useful to account for network properties when selecting an influence maximization method.

The security objectives enforce the security policy, which defines what is to be protected in a network environment. The violation of these security objectives induces security threats. We introduce an explicit notion of security objectives for a security protocol. This notion should precede the formal verification process. In the absence of such a notion, the security protocol may be proven correct despite the fact that it is not equipped to defend against all potential threats. In order to establish the correctness of security objectives, we present a formal model that provides basis for the formal verification of security protocols. We also develop the modal logic, proof based, and multi-agent approaches using the Strand Space framework. In our modal logic approach, we present the logical constructs to model a protocol's behavior in such a way that the participants can verify different security parameters by looking at their own run of the protocol. In our proof based model, we present a generic set of proofs to establish the correctness of a security protocol. We model the 802.11i protocol into our proof based system and then perform the formal verification of the authentication property. The intruder in our model is imbued with powerful capabilities and repercussions to possible attacks are evaluated. Our analysis proves that the authentication of 802.11i is not compromised in the presented model. We further demonstrate how changes in our model will yield a successful man-in-the-middle attack. Our multi-agent approach includes an explicit notion of multi-agent, which was missing in the Strand Space framework. The limitation of Strand Space framework is the assumption that all the information available to a principal is either supplied initially or is contained in messages received by that principal. However, other important information may also be available to a principal in a security setting, such as a principal may combine information from different roles played by him in a protocol to launch a powerful attack. Our presented approach models the behavior of a distributed system as a multi-agent system. The presented model captures the combined information, the formal model of knowledge, and the belief of agents over time. After building this formal model, we present a formal proof of authentication of the 4-way handshake of the 802.11i protocol.

Robots are increasingly utilized in industry for their capability to perform repetitive,complex tasks in environments unsuitable for humans. This surge in robotic applicationshas spurred research into Multi-Robot Systems (MRS), which aim to tackle complex tasksrequiring collaboration among multiple robots, thereby boosting overall efficiency. However,MRS introduces multifaceted challenges that span various domains, including robot perception,localization, task assignment, communication, and control. This dissertation delves into theintricate aspects of task assignment and path planning within MRS.The first area of focus is on multi-robot navigation, specifically addressing the limitationsinherent in current Multi-Agent Path Finding (MAPF) models. Traditional MAPF solutionstend to oversimplify, treating robots as holonomic units on grid maps. While this approachis impractical in real-world settings where robots have distinct geometries and kinematicrestrictions, it is important to note that even in its simplified form, MAPF is categorized as anNP-hard problem. The complexity inherent in MAPF becomes even more pronounced whenextending these models to non-holonomic robots, underscoring the significant computationalchallenges involved. To address these challenges, this thesis introduces a novel MAPF solverdesigned for non-holonomic, heterogeneous robots. This solver integrates the hybrid A*algorithm, accommodating kinematic constraints, with a conflict-based search (CBS) for efficientconflict resolution. A depth-first search approach in the conflict tree is utilized to accelerate theidentification of viable solutions.The second research direction explores synergizing task assignment with path-finding inMRS. While there is substantial research in both decentralized and centralized task assignmentstrategies, integrating these with path-finding remains underexplored. This dissertation evaluatesdecoupled methods for sequentially resolving task assignment and MAPF challenges. Oneproposed method combines the Hungarian algorithm and a Traveling Salesman Problem (TSP)solver for swift, albeit suboptimal, task allocation. Subsequently, robot paths are generatedindependently, under the assumption of collision-free navigation. During actual navigation, aNonlinear Model Predictive Controller (NMPC) is deployed for dynamic collision avoidance. Analternative approach seeks optimal solutions by conceptualizing task assignment as a MultipleTraveling Salesman Problem (MTSP), solved using a simulated annealing algorithm. In tandem,CBS is iteratively applied to minimize the cumulative path costs of the robots.

Yes / Industry 4.0 promotes highly automated mechanisms for setting up and operating flexible manufacturing systems, using distributed control and data-driven machine intelligence. This paper presents an approach to reconfiguring distributed production systems based on complex product requirements, combining the capabilities of the available production resources. A method for both checking the “realisability” of a product by matching required operations and capabilities, and adapting resources is introduced. The reconfiguration is handled by a multi-agent system, which reflects the distributed nature of the production system and provides an intelligent interface to the user. This is all integrated with a self-adaptation technique for learning how to improve the performance of the production system as part of a reconfiguration. This technique is based on a machine learning algorithm that generalises from past experience on adjustments. The mechanisms of the proposed approach have been evaluated on a distributed robotic manufacturing system, demonstrating their efficacy. Nevertheless, the approach is general and it can be applied to other scenarios. / This work was supported by the SURE Research Projects Fund of the University of Bradford and the European Commission (grant agreement no. 314762). / Research Development Fund Publication Prize Award winner, Nov 2022