<p> Software Architecture is a concept that arose during the last two decades as a consequence of the need for a structured design at an early stage. Software Architecture is defined as a pattern of interconnected components satisfying some structural rule. Software architectures are widely used in many types of systems; Multi-Agent Systems should not be an exception. Multi-Agent Systems have emerged as a design paradigm for large and distributed systems. They are composed of autonomous elements that work together in order to pursue a common goal. They are mostly used in Electronic Commerce, Human-Computer Interfaces, and so on.</p> <p> In this research, we investigate the state of the art of Software Architectures in the Multi-Agent Systems field, showing that, generally Multi-Agent Systems do no use the software architecture concept properly and, when they do, they do not show specific architectures for Multi-Agent Systems. The approach followed is based on the analysis of six case studies, which are implemented applications that have been published in some of the most important conferences in the area. Additionally we show that, based on the initial design of each case and existing architectural patterns, it is possible to impose a software architecture on each case.</p> <p> Furthermore, we analyze the way that the term "software architecture" is used in the Multi-Agent Systems literature, showing that, usually, it refers to abstract architectures proposed in standards and frameworks or to an initial design in a system. In addition we clarify related concepts, such as reference architecture, reference models, architectural patterns and design patterns. Finally, we do an exhaustive comparison of the case studies, which aims to highlight commonalities and differences. The objective of this comparison is to analyze if they share a similar architecture that can be reused in more cases and to show how specific properties of Multi-Agent Systems affect in the design of an architecture.</p> / Thesis / Master of Science (MSc)

Doctor of Philosophy / Self-driving cars promise a future with safer roads and reduced traffic incidents and fatalities. This future hinges on the car's accurate understanding of its surrounding environment; however, the reliability of the algorithms that form this perception is not always guaranteed and adverse traffic and environmental conditions can significantly diminish the performance of these algorithms. To solve this problem, this research builds on the idea that enabling cars to share and exchange information via communication allows them to extend the range and quality of their perception beyond their capability. To that end, this research formulates a robust and flexible framework for cooperative perception, explores how connected vehicles can learn to collaborate to improve their perception, and introduces an affordable, experimental vehicle platform for connected autonomy research.

Modern robotics demonstrates the reality of near sci-fi solutions regularly. Swarms of interconnected robotic agents have been proven to have benefits in scalability, robustness, and efficiency. In communication restricted environments, such teams of robots are often required to support their own navigation, planning, and decision making processes, through use of onboard processors and collaboration. Example scenarios that exhibit restriction include unmanned underwater surveys and robots operating in indoor or remote environments without cloud connectivity. We begin this thesis by discussing multi-agent state estimation and it's observability properties, specifically for the case of an agent-to-agent range measurement system. For this case, inspired by navigation requirements underwater, we derive several conditions under which the system's state is guaranteed to be locally weakly observable. Ensuring a state is observable is necessary to maintain an estimate of it via filters, thus observability is required to support higher level navigation and planning. We conclude this section by creating an observability-based planner to control a subset of the agents' inputs. For the next contribution, we discuss scalability for coverage maximizing path planners. Typically planning for many individual robots incurs significant computational complexity which increases exponentially with the number of agents, this is often exacerbated when the objective function is collaborative as in coverage optimization. To maintain feasibility while planning for a large team of robots, we call upon a powerful relation from combinatorics which utilizes the greedy selection algorithm and a matroid condition to create an efficient planner that maintains a fixed performance ratio when compared to the optimal path. We then introduce a motivating example of autonomously assisted search and rescues using multiple aerial agents, and derive planners and models to suit the application. The framework begins by estimating the likely locations of a lost person through a Monte Carlo simulation, yielding a heatmap covering the area of interest. The heatmap is then used in combination with parametrized agent trajectories and a machine learning optimization algorithm to maximize the search efficiency. The search and rescues use case provides an excellent computational testbed for the final portion of the work. We close by discussing a computation architecture to support multi-agent system autonomy. Modern robotic autonomy results, especially computer vision and machine learning algorithms, often require large amounts of processing to yield quality results. With general purpose computing devices reaching a progression barrier, one that is not expected to be solved in the near term, increasingly devices must be designed with their end purposes in mind. To better support autonomy in multi-agent systems, we propose to use a distributed cluster of embedded processors which allows the sharing of computation and storage resources among the component members with minimal communication overhead. Our proposed architecture is composed of mature softwares already well-known in the robotics community, Kubernetes and the robot operating system, allowing ease of use and interoperability with existing algorithms. / Doctor of Philosophy / The traditional approach of robotics typically uses a single large platform capable of accomplishing all tasks assigned to it. However, it has been discovered that deploying multiple smaller platforms, each with their own processor and specific expertise, can have massive performance benefits compared to previous approaches. This development has been driven largely by readily available computing and mobility hardware. Termed as multi-agent systems, they can excel in areas that benefit from multiple perspectives, simultaneous task execution, and redundancy. In addition, planning algorithms developed for previous approaches often can map well onto multi-agent systems, provided there is adequate computational support. In cases where network or cloud connectivity is limited, teams of agents must use their own processors and sensors to make decisions and communicate. However, often an individual agent's computing hardware is limited in mass or size, thus limiting it's processing capabilities. In this work we will first discuss several multi-agent system algorithms, starting with estimation and navigation and ending with area search. We then conclude the work by proposing a novel architecture designed to distribute the computation load across the team in a highly scalable way.

The use of autonomous aerial vehicles (UAVs) to explore unknown environments is a growing field of research; of particular interest is locating a target that emits a signal within an unknown environment. Several physical processes produce scalar signals that attenuate with distance from their source, such as chemical, biological, electromagnetic, thermal, and radar signals. The natural decay of the signal with increasing distance enables a gradient ascent method to be used to navigate toward the target. The UAVs navigate around obstacles whose positions are initially unknown; a hybrid controller comprised of overlapping control modes enables robust obstacle avoidance in the presence of exogenous inputs by precluding topological obstructions. Limitations of a distributed gradient augmentation approach to obstacle avoidance are discussed, and an alternative algorithm is presented which retains the robustness of the hybrid control while leveraging local obstacle position information to improve non-collision reliability. A heterogeneous swarm of multirotors demonstrates the target locating problem, sharing information over a multicast wireless private network in a fully distributed manner to form an estimate of the signal's gradient, informing the direction of travel toward the target. The UAVs navigate around obstacles, showcasing both algorithms developed for obstacle avoidance. Each UAV performs its own target seeking and obstacle avoidance calculations in a distributed architecture, receiving position data from an OptiTrack motion capture system, illustrating the applicability of the control law to real world challenges (e.g., unsynchronized clocks among different UAVs, limited computational power, and communication latency). Experimental and theoretical results are compared. / Master of Science / In this project, a new method for locating a target using a swarm of unmanned drones in an unknown environment is developed and demonstrated. The drones measure a signal such as a beacon that is being emitted by the target of interest, sharing their measurement information with the other drones in the swarm. The magnitude of the signal increases as the drones move toward the target, allowing the drones to estimate the direction to the target by comparing their measurements with the measurements collected by other drones. While seeking the target in this manner, the drones detect obstacles that they need to avoid. An issue that arises in obstacle avoidance is that drones can get stuck in front of an obstacle if they are unable to decide which direction to travel; in this work, the decision process is managed by combining two control modes that correspond to the two direction options available, using a robust switching algorithm to select which mode to use for each obstacle. This work extends the approach used in literature to include multiple obstacles and allow obstacles to be detected dynamically, enabling the drones to navigate through an unknown environment as they locate the target. The algorithms are demonstrated on unmanned drones in the VT SpaceDrones test facility, illustrating the capabilities and effectiveness of the methods presented in a series of scenarios.

Internet of things (IoT) is envisioned as a promising paradigm to interconnect enormous wireless devices. However, the success of IoT is challenged by the difficulty of access management of the massive amount of sporadic and unpredictable user traffics. This thesis focuses on the contention-based random access in massive cellular IoT systems and introduces two novel frameworks to provide enhanced scalability, real-time quality of service management, and resource efficiency. First, a local communication based congestion control framework is introduced to distribute the random access attempts evenly over time under bursty traffic. Second, a multi-agent reinforcement learning based preamble selection framework is designed to increase the access capacity under a fixed number of preambles. Combining the two mechanisms provides superior performance under various 3GPP-specified machine type communication evaluation scenarios in terms of achieving much lower access latency and fewer access failures. / Master of Science / In the age of internet of things (IoT), massive amount of devices are expected to be connected to the wireless networks in a sporadic and unpredictable manner. The wireless connection is usually established by contention-based random access, a four-step handshaking process initiated by a device through sending a randomly selected preamble sequence to the base station. While different preambles are orthogonal, preamble collision happens when two or more devices send the same preamble to a base station simultaneously, and a device experiences access failure if the transmitted preamble cannot be successfully received and decoded. A failed device needs to wait for another random access opportunity to restart the aforementioned process and hence the access delay and resource consumption are increased. The random access control in massive IoT systems is challenged by the increased access intensity, which results in higher collision probability. In this work, we aim to provide better scalability, real-time quality of service management, and resource efficiency in random access control for such systems. Towards this end, we introduce 1) a local communication based congestion control framework by enabling a device to cooperate with neighboring devices and 2) a multi-agent reinforcement learning (MARL) based preamble selection framework by leveraging the ability of MARL in forming the decision-making policy through the collected experience. The introduced frameworks are evaluated under the 3GPP-specified scenarios and shown to outperform the existing standard solutions in terms of achieving lower access delays with fewer access failures.

Multi-Agent Systems (MASs) and Partial and Ordinary Differential Equations (PDEs and ODEs respectively) have often been employed by researchers to effectively model and simulate Complex Adaptive Systems (CASs). PDEs and ODEs are reduction based approaches which view the system globally and ignore any local interactions and processes. MASs are considered by many to be a better tool to model CASs, but have issues as well. Case in point, there is concern that present day MASs fail to capture the true essence of inter-cellular communication in a CAS. In this work we present a realistic and utilizable communication framework for inter-agent communication for a CAS simulation. We model the dynamic properties of the communication signals and show that our model is a realistic model for inter-cellular communication. We validate our system by modeling and simulating pattern formation in Dictyostelium discoideum, a unicellular organism. / Master of Science

A software agents based manufacturing scheduling module for Advanced Planning and Scheduling (APS) is presented. The problem considered is scheduling of jobs with multiple operations, distinct operation processing times, arrival times, and due dates in a job shop environment. Sequence dependent setups are also considered. The additional constraints of material and resource availability are also taken into consideration. The scheduling is to be considered in integration with production planning. The production plans can be changed dynamically and the schedule is to be generated to reflect the appropriate changes. The design of a generic multi-agent framework which is domain independent along with algorithms that are used by the agents is also discussed. / Master of Science

Internet es, tal vez, el avance científico más relevante de nuestros días. Entre otras cosas, Internet ha permitido la evolución de los paradigmas de computación tradicionales hacia el paradigma de computaciónn distribuida, que se caracteriza por utilizar una red abierta de ordenadores. Los sistemas multiagente (SMA) son una tecnolog a adecuada para abordar los retos motivados por estos sistemas abiertos distribuidos. Los SMA son aplicaciones formadas por agentes heterog eneos y aut onomos que pueden haber sido dise~nados de forma independiente de acuerdo con objetivos y motivaciones diferentes. Por lo tanto, no es posible realizar ninguna hip otesis a priori sobre el comportamiento de los agentes. Por este motivo, los SMA necesitan de mecanismos de coordinaci on y cooperaci on, como las normas, para garantizar el orden social y evitar la aparici on de conictos. El t ermino norma cubre dos dimensiones diferentes: i) las normas como un instrumento que gu a a los ciudadanos a la hora de realizar acciones y actividades, por lo que las normas de nen los procedimientos y/o los protocolos que se deben seguir en una situaci on concreta, y ii) las normas como ordenes o prohibiciones respaldadas por un sistema de sanciones, por lo que las normas son medios para prevenir o castigar ciertas acciones. En el area de los SMA, las normas se vienen utilizando como una especi caci on formal de lo que est a permitido, obligado y prohibido dentro de una sociedad. De este modo, las normas permiten regular la vida de los agentes software y las interacciones entre ellos. La motivaci on principal de esta tesis es permitir a los dise~nadores de los SMA utilizar normas como un mecanismo para controlar y coordinar SMA abiertos. Nuestro objetivo es elaborar mecanismos normativos a dos niveles: a nivel de agente y a nivel de infraestructura. Por lo tanto, en esta tesis se aborda primero el problema de la de nici on de agentes normativos aut onomos que sean capaces de deliberar acerca / Criado Pacheco, N. (2012). Using Norms To Control Open Multi-Agent Systems [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/17800

The pursuit of multi-agent exploration is driven by its capacity to enhance operational robustness and efficiency in complex, dynamic environments, paving the way for advancements in autonomous systems and robotics. This thesis explores the development and assessment of decentralised planning algorithms within multi-agent systems, using the CARLA simulation environment. A methodology combining simulation-based testing and theoretical analysis was employed to evaluate the efficiency, and scalability of various decentralised planning strategies.  The study systematically analysed three different exploration strategies for multi-agent systems: Greedy, MinPos, and Hungarian Assignments, across various configurations concerning the number of agents and communication demands. The Hungarian Assignment strategy demonstrates the highest efficiency in area coverage and coordination, especially as the number of agents increases. Meanwhile, the Greedy Assignment strategy requires the least communication bandwidth, indicating its potential for scenarios with limited communication capabilities. The MinPos Assignment, while facilitating better spatial distribution of agents than the Greedy Assignment, showed a moderate increase in communication demands and did not significantly outperform the Greedy Assignment in terms of efficiency. This work contributes to the field by providing insights into the trade-offs between exploration efficiency and communication overhead in multi-agent systems. Future work could explore synchronisation mechanisms, collision-avoidance strategies, and further decentralisation of the system's components.

Dans la pratique, beaucoup de problèmes d'optimisation sont dynamiques : leur fonction objectif (ou fonction de coût) évolue au cours du temps. L'approche principalement adoptée dans la littérature consiste à adapter des algorithmes d'optimisation statique à l'optimisation dynamique, en compensant leurs défauts intrinsèques. Plutôt que d'emprunter cette voie, déjà largement explorée, l'objectif principal de cette thèse est d'élaborer un algorithme entièrement pensé pour l'optimisation dynamique. La première partie de cette thèse est ainsi consacrée à la mise au point d'un algorithme, qui doit non seulement se démarquer des algorithmes concurrents par son originalité, mais également être plus performant. Dans ce contexte, il s'agit de développer une métaheuristique d'optimisation dynamique. Deux algorithmes à base d'agents, MADO (MultiAgent algorithm for Dynamic Optimization) et MLSDO (Multiple Local Search algorithm for Dynamic Optimization), sont proposés et validés sur les deux principaux jeux de tests existant dans la littérature en optimisation dynamique : MPB (Moving Peaks Benchmark) et GDBG (Generalized Dynamic Benchmark Generator). Les résultats obtenus sur ces jeux de tests montrent l'efficacité des stratégies mises en oeuvre par ces algorithmes, en particulier : MLSDO est classé premier sur sept algorithmes évalués sur GDBG, et deuxième sur seize algorithmes évalués sur MPB. Ensuite, ces algorithmes sont appliqués à des problèmes pratiques en traitement de séquences d'images médicales (segmentation et recalage de séquences ciné-IRM cérébrales). A notre connaissance, ce travail est innovant, en ce sens que l'approche de l'optimisation dynamique n'avait jamais été explorée pour ces problèmes. Les gains de performance obtenus montrent l'intérêt d'utiliser les algorithmes d'optimisation dynamique proposés pour ce type d'applications / Many real-world problems are dynamic, i.e. their objective function (or cost function) changes over time. The main approach used in the literature is to adapt static optimization algorithms to dynamic optimization, compensating for their intrinsic defects. Rather than adopting this approach, already widely investigated, the main goal of this thesis is to develop an algorithm completely designed for dynamic optimization. The first part of this thesis is then devoted to the design of an algorithm, that should not only stand out from competing algorithms for its originality, but also perform better. In this context, our goal is to develop a dynamic optimization metaheuristic. Two agent-based algorithms, MADO (MultiAgent algorithm for Dynamic Optimization) and MLSDO (Multiple Local Search algorithm for Dynamic Optimization), are proposed and validated using the two main benchmarks available in dynamic environments : MPB (Moving Peaks Benchmark) and GDBG (Generalized Dynamic Benchmark Generator). The benchmark results obtained show the efficiency of the proposed algorithms, particularly : MLSDO is ranked at the first place among seven algorithms tested using GDBG, and at the second place among sixteen algorithms tested using MPB. Then, these algorithms are applied to real-world problems in medical image sequence processing (segmentation and registration of brain cine-MRI sequences). To our knowledge, this work is innovative in that the dynamic optimization approach had never been investigated for these problems. The performance gains obtained show the relevance of using the proposed dynamic optimization algorithms for this kind of applications