In various industries, such as manufacturing, logistics, agriculture, defense, search and rescue, and transportation, Multi-robot systems (MRSs) are increasingly gaining popularity. These systems involve multiple robots working together towards a shared objective, either autonomously or under human supervision. However, as MRSs operate in uncertain or even adversarial environments, and the sensors and actuators of each robot may be error-prone, they are susceptible to faults and security threats unique to MRSs. Classical techniques from distributed systems cannot detect or mitigate these threats. In this dissertation, novel techniques are proposed to enhance the security and fault-tolerance of MRSs through inter-robot observations and accusations. A fundamental security property is proposed for MRSs, which ensures that forbidden deviations from a desired multi-robot motion plan by the system supervisor are detected. Relying solely on self-reported motion information from the robots for monitoring deviations can leave the system vulnerable to attacks from a single compromised robot. The concept of co-observations is introduced, which are additional data reported to the supervisor to supplement the self-reported motion information. Co-observation-based detection is formalized as a method of identifying deviations from the expected motion plan based on discrepancies in the sequence of co-observations reported. An optimal deviation-detecting motion planning problem is formulated that achieves all the original application objectives while ensuring that all forbidden plan-deviation attacks trigger co-observation-based detection by the supervisor. A secure motion planner based on constraint solving is proposed as a proof-of-concept to implement the deviation-detecting security property. The security and resilience of MRSs against plan deviation attacks are further improved by limiting the information available to attackers. An efficient algorithm is proposed that verifies the inability of an attacker to stealthily perform forbidden plan deviation attacks with a given motion plan and announcement scheme. Such announcement schemes are referred to as horizon-limiting. An optimal horizon-limiting planning problem is formulated that maximizes planning lookahead while maintaining the announcement scheme as horizon-limiting. Co-observations and horizon-limiting announcements are shown to be efficient and scalable in protecting MRSs, including systems with hundreds of robots, as evidenced by a case study in a warehouse setting. Lastly, the Decentralized Blocklist Protocol (DBP), a method for designing Byzantine-resilient decentralized MRSs, is introduced. DBP is based on inter-robot accusations and allows cooperative robots to identify misbehavior through co-observations and share this information through the network. The method is adaptive to the number of faulty robots and is widely applicable to various decentralized MRS applications. It also permits fast information propagation, requires fewer cooperative observers of application-specific variables, and reduces the worst-case connectivity requirement, making it more scalable than existing methods. Empirical results demonstrate the scalability and effectiveness of DBP in cooperative target tracking, time synchronization, and localization case studies with hundreds of robots. The techniques proposed in this dissertation enhance the security and fault-tolerance of MRSs operating in uncertain and adversarial environments, aiding in the development of secure MRSs for emerging applications.

Recent rapid advances in computing, communication, sensing, and actuation, together with miniaturization technologies, have offered unprecedented opportunities to employ large numbers of autonomous vehicles (air, ground, and water) working cooperatively to accomplish a mission. Cooperative control of such multi-agent dynamical systems has potential impact on numerous civilian, homeland security, and military applications. Compared with single-agent control problems, new theoretical and practical challenges emerge and need to be addressed in cooperative control of multiagent dynamical systems, including but not limited to problem size, task coupling, limited computational resources at individual agent level, communication constraints, and the need for real-time obstacle/collision avoidance. In order to address these challenges, a unified optimal multi-agent cooperative control strategy is proposed to formulate the multi-objective cooperative control problem into one unified optimal control framework. Many cooperative behaviors, such as consensus, cooperative tracking, formation, obstacle/collision avoidance, or flocking with cohesion and repulsion, can be treated in one optimization process. An innovative inverse optimal control approach is utilized to include these cooperative objectives in derived cost functions such that a closedorm cooperative control law can be obtained. In addition, the control law is distributed and only depends on the local neighboring agents’ information. Therefore, this new method does not demand intensive computational load and is easy for real-time onboard implementation. Furthermore, it is very scalable to large multi-agent cooperative dynamical systems. The closed-loop asymptotic stability and optimality are theoretically proved. Simulations based on MATLAB are conducted to validate the cooperative behaviors including consensus, Rendezvous, formation flying, and flocking, as well as the obstacle avoidance performance.

We investigate an approach to apply Genetic Programming for the evolution of optimal escaping strategies of a team of caribou agents in the wolf-caribou predator prey problem (WCPPP) where the WCPPP is comprised of a team of caribou agents attempting to escape from a single yet superior (in terms of sensory abilities, raw speed, and maximum energy) wolf agent in a simulated twodimensional infinite toroidal world. We empirically verify our hypothesis that the incorporation of empathy in caribou agents significantly improves both the evolution efficiency of the escaping behavior and the effectiveness of such a behavior. This finding may be viewed as a verification of the survival value of empathy and the resulting compassionate behavior of the escaping caribou agents. Moreover, considering the fact that a single caribou cannot escape from the superior wolf, the ability of a team of empathic caribou agents to escape may also be viewed as an illustration of the emergent nature of a successful escaping behavior – in that the team-level properties are more than the mere sum of the properties of the individual entities. Within this context, we also present empirical results that verify the complex (nonlinear) nature of the relationship between the size of team of caribou agents and the efficiency of their escaping behavior. / 博士(工学) / Doctor of Philosophy in Engineering / 同志社大学 / Doshisha University

Background. The A* algorithm is a well-established pathfinding technique frequently used in video game development. However, a disadvantage of the A* algorithm is that it becomes computationally inefficient and impractical to utilize whenthousands of agents demand an optimal path. A solution to mitigate this issue isthe use of the flow field algorithm. This algorithm employs a goal-based pathfindingstrategy, which allows for the movement of a large number of units through the useof a single direction map (flow field map) that indicates the direction units must take to progress toward their goal. Objectives. The main objective of this study is to examine the performance and scalability of precomputed flow field maps with regard to execution time and memory utilization, with the objective of determining the feasibility of precomputed maps as an alternative to maps generated at runtime. Furthermore, the study implements and investigates compression techniques to minimize the memory footprint of precomputed flow field maps. Methods. The study adopts an experimental research design to assess the performance of the two implementations under various conditions of grid size and movement system. Performance evaluation is accomplished through the measurement and comparison of execution time and memory consumption. Additionally, a directional accuracy test is performed to quantify the potential loss of accuracy in the vectors stored in the precomputed flow field maps. Results. The precomputed flow field maps provide constant access time, with a time complexity of O(1), regardless of the grid size and the type of movement system. The memory usage of these maps increases significantly with the growth of the grid size. A doubling of the grid size leads to a more than fifteen-fold increase in memory usage. The techniques proposed in the study significantly reduced the memory footprint by a factor of thirty-two and by a factor of eight, depending on the selected movement system. The average loss in accuracy was approximately 0.35 degrees for the proposed any-angle compression technique. Conclusions. The use of precomputed flow field maps has limitations, including being limited to static environments and having high memory requirements. On the other hand, they provide constant access time for pathfinding information, independent of the grid dimensions, movement system, and the number of target nodes. Whether precomputed flow field maps are better than the traditional runtime implementation depends on the intended use.

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.