This dissertation is concerned with three problems within the field of optimization for agent--based systems. Firstly, the inverse optimal control problem is investigated for the single-agent system. Given a dynamic process, the goal is to recover the quadratic cost function from the observation of optimal control sequences. Such estimation could then help us develop a better understanding of the physical system and reproduce a similar optimal controller in other applications. Next, problems of optimization over networked systems are considered. A novel differential game approach is proposed for the optimal intrinsic formation control of multi-agent systems. As for the credit scoring problem, an optimal filtering framework is utilized to recursively improve the scoring accuracy based on dynamic network information. In paper A, the problem of finite horizon inverse optimal control problem is investigated, where the linear quadratic (LQ) cost function is required to be estimated from the optimal feedback controller. Although the infinite-horizon inverse LQ problem is well-studied with numerous results, the finite-horizon case is still an open problem. To the best of our knowledge, we propose the first complete result of the necessary and sufficient condition for the existence of corresponding LQ cost functions. Under feasible cases, the analytic expression of the whole solution space is derived and the equivalence of weighting matrices is discussed. For infeasible problems, an infinite dimensional convex problem is formulated to obtain a best-fit approximate solution with minimal control residual, where the optimality condition is solved under a static quadratic programming framework to facilitate the computation. In paper B, the optimal formation control problem of a multi-agent system is studied. The foraging behavior of N agents is modeled as a finite-horizon non-cooperative differential game under local information, and its Nash equilibrium is studied. The collaborative swarming behaviour derived from non-cooperative individual actions also sheds new light on understanding such phenomenon in the nature. The proposed framework has a tutorial meaning since a systematic approach for formation control is proposed, where the desired formation can be obtained by only intrinsically adjusting individual costs and network topology. In contrast to most of the existing methodologies based on regulating formation errors to the pre-defined pattern, the proposed method does not need to involve any information of the desired pattern beforehand. We refer to this type of formation control as intrinsic formation control. Patterns of regular polygons, antipodal formations and Platonic solids can be achieved as Nash equilibria of the game while inter-agent collisions are naturally avoided. Paper C considers the credit scoring problem by incorporating dynamic network information, where the advantages of such incorporation are investigated in two scenarios. Firstly, when the scoring publishment is merely individual--dependent, an optimal Bayesian filter is designed for risk prediction, where network observations are utilized to provide a reference for the bank on future financial decisions. Furthermore, a recursive Bayes estimator is proposed to improve the accuracy of score publishment by incorporating the dynamic network topology as well. It is shown that under the proposed evolution framework, the designed estimator has a higher precision than all the efficient estimators, and the mean square errors are strictly smaller than the Cramér-Rao lower bound for clients within a certain range of scores. / I denna avhandling behandlas tre problem inom optimering för agentbaserade system. Inledningsvis undersöks problemet rörande invers optimal styrning för ett system med en agent. Målet är att, givet en dynamisk process, återskapa den kvadratiska kostnadsfunktionen från observationer av sekvenser av optimal styrning. En sådan uppskattning kan ge ökad förståelse av det underliggande fysikaliska systemet, samt vara behjälplig vid konstruktion av en liknande optimal regulator för andra tillämpningar. Vidare betraktas problem rörande optimering över nätverkssystem. Ett nytt angreppssätt, baserat på differentialspel, föreslås för optimal intrinsisk formationsstyrning av system med fler agenter. För kreditutvärderingsproblemet utnyttjas ett filtreringsramverk för att rekursivt förbättra kreditvärderingens noggrannhet baserat på dynamisk nätverksinformation. I artikel A undersöks problemet med invers optimal styrning med ändlig tidshorisont, där den linjärkvadratiska (LQ) kostnadsfunktionen måste uppskattas från den optimala återkopplingsregulatorn. Trots att det inversa LQ-problemet med oändlig tidshorisont är välstuderat och med flertalet resultat, är fallet med ändlig tidshorisont fortfarande ett öppet problem. Så vitt vi vet presenterar vi det första kompletta resultatet med både tillräckliga och nödvändiga villkor för existens av en motsvarande LQ-kostnadsfunktion. I fallet med lösbara problem härleds ett analytiskt uttryck för hela lösningsrummet och frågan om ekvivalens med viktmatriser behandlas. För de olösbara problemen formuleras ett oändligtdimensionellt konvext optimeringsproblem för att hitta den bästa approximativa lösningen med den minsta styrresidualen. För att underlätta beräkningarna löses optimalitetsvillkoren i ett ramverk för statisk kvadratisk programmering. I artikel B studeras problemet rörande optimal formationsstyrning av ett multiagentsystem. Agenternas svärmbeteende modelleras som ett icke-kooperativt differentialspel med ändlig tidshorisont och enbart lokal information. Vi studerar detta spels Nashjämvikt. Att, ur icke-kooperativa individuella handlingar, härleda ett kollaborativt svärmbeteende kastar nytt ljus på vår förståelse av sådana, i naturen förekommande, fenomen. Det föreslagna ramverket är vägledande i den meningen att det är ett systematiskt tillvägagångssätt för formationsstyrning, där den önskade formeringen kan erhållas genom att endast inbördes justera individuella kostnader samt nätverkstopologin. I motstat till de flesta befintliga metoder, vilka baseras på att reglera felet i formeringen relativt det fördefinierade mönstret, så behöver den föreslagna metoden inte på förhand ta hänsyn till det önskade mönstret. Vi kallar denna typ av formationsstyrning för intrinsisk formationsstyrning. Mönster så som regelbundna polygoner, antipodala formeringar och Platonska kroppar kan uppnås som Nashjämvikter i spelet, samtidigt som kollisioner mellan agenter undviks på ett naturligt sätt. Artikel C behandlar kreditutvärderingsproblemet genom att lägga till dynamisk nätverksinformation. Fördelarna med en sådan integrering undersöks i två scenarier. Då kreditvärdigheten enbart är individberoende utformas ett optimalt Bayesiskt filter för riskvärdering, där observationer från nätverket används för att tillhandahålla en referens för banken på framtida finansiella beslut. Vidare föreslås en rekursiv Bayesisk estimator (stickprovsvariabel) för att förbättra noggrannheten på den skattade kreditvärdigheten genom att integrera även den dynamiska nätverkstopologin. Inom den föreslagna ramverket för tidsutveckling kan vi visa att, för kunder inom ett visst intervall av värderingar, har den utformade estimatorn högre precision än alla effektiva estimatorer och medelkvadrafelet är strikt mindre än den nedre gränsen från Cramér-Raos olikhet. / <p>QC 20190603</p>

Le but de cette thèse est d'étendre l'état de l'art par des contributions sur le comportement collectif d'un groupe de robots volants, à savoir des quadrirotors UAV. Afin de pouvoir sûrement naviguer dans un environnement, ces derniers peuvent se reposer uniquement sur leurs capacités à bord et non sur des systèmes centralisés (e.g., Vicon ou GPS). Nous réalisons cet objectif en offrant une possible solution aux problèmes de contrôle en formation et de localisation à partir de mesures à bord et via une communication locale. Nous abordons ces problèmes exploitant différents concepts provenant de la théorie des graphes algébriques et de la théorie de la rigidité. Cela nous permet de résoudre ces problèmes de façon décentralisée et de proposer des algorithmes décentralisés capables de prendre en compte également des limites sensorielles classiques. Les capacités embarquées que nous avons mentionnées plus tôt sont représentées par une caméra monoculaire et une centrale inertielle (IMU) auxquelles s'ajoute la capacité de chaque robot à communiquer (par RF) avec certains de ses voisins. Cela est dû au fait que l'IMU et la caméra représentent une possible configuration économique et légère pour la navigation et la localisation autonome d'un quadrirotor UAV. / The aim of this Thesis is to give contributions to the state of the art on the collective behavior of a group of flying robots, specifically quadrotor UAVs, which can only rely on their onboard capabilities and not on a centralized system (e.g., Vicon or GPS) in order to safely navigate in the environment. We achieve this goal by giving a possible solution to the problems of formation control and localization from onboard sensing and local communication. We tackle these problems exploiting mainly concepts from algebraic graph theory and the so-called theory of rigidity. This allows us to solve these problems in a decentralized fashion, and propose decentralized algorithms able to also take into account some typical sensory limitations. The onboard capabilities we referred to above are represented by an onboard monocular camera and an inertial measurement unit (IMU) in addition to the capability of each robot to communicate (through RF) with some of its neighbors. This is due to the fact that an IMU and a camera represent a possible minimal, lightweight and inexpensive configuration for the autonomous localization and navigation of a quadrotor UAV.

In this thesis, various control problems originating from the field of mobile robotics are considered. In particular, the thesis deals with problems that are related to the interaction and coordination of multiple mobile units. The scientific contributions are presented in five papers that together constitute the main part of the thesis. The papers are preceded by a longer introductory part, in which some important results from control theory, data processing and robotics are reviewed. In the first of the appended papers, two stabilizing tracking controls are proposed for a non-holonomic robot platform of unicycle type. Tolerance to errors and other properties of the controllers are discussed and a reactive obstacle avoidance control, that can easily be incorporated with the proposed tracking controls, is suggested. In Paper B, the results from Paper~A are extended to multi-agent systems. It is demonstrated how the tracking controls from Paper A can be used as building blocks when putting together formations of robots, in which each robot maintains a fixed position relative its neighbors during translation. In addition, switching between the different control functions is shown to be robust, implying that it is possible to change the shape of a formation on-line. In the first two papers, the tracking problem is facilitated by the assumption that the approximate velocity of the target/leader is known to the tracking robot. Paper C treats the the case where the target velocity is neither directly measurable with the available sensor setup, nor possible to obtain through communication with neighboring agents. Straight-forward computation of the target velocity from available sensor data unfortunately tend to enhance measurement errors and give unreliable estimates. To overcome the difficulties, an alternative approach to velocity estimation is proposed, motivated by the local observability of the given control system. Paper D deals with another problematic aspect of data acquisition. When using range sensors, one often obtains a mixed data set with measurements originating from many different sources. This problem would, for instance, be encountered by a robot moving in a formation, where it was surrounded by other agents. There exist established techniques for sorting mixed data sets off-line, but for time-depending systems where data need to be sorted on-line and only small time delays can be tolerated, established methods fail. The solution presented in the paper is a prediction-correction type algorithm, referred to as CCIA (Classification Correction and Identification algorithm). Finally, in Paper E, we consider the problem of maintaining connectivity in a multi-agent system. Often inter-agent communication abilities are associated with some proximity constraints, so when the robots move in relation to each other, communication links both break and form. In the paper we present a framework for analysis that makes it possible to compute a set of general constraints which, if satisfied, are sufficient to guarantee maintained communication for a given multi-agent system. Constraints are computed for two sorts of consensus-based systems and the results are verified in simulations. / QC 20100715

In this thesis, we investigate a special class of multi-agent systems, which we call reciprocal multi-agent (RMA) systems. The evolution of agents in a RMA system is governed by interactions between pairs of agents. Each interaction is reciprocal, and the magnitude of attraction/repulsion depends only on distances between agents. We investigate the class of RMA systems from four perspectives, these are two basic properties of the dynamical system, one formula for computing the Morse indices/co-indices of critical formations, and one formation control model as a variation of the class of RMA systems. An important aspect about RMA systems is that there is an equivariant potential function associated with each RMA system so that the equations of motion of agents are actually a gradient flow. The two basic properties about this class of gradient systems we will investigate are about the convergence of the gradient flow, and about the question whether the associated potential function is generically an equivariant Morse function. We develop systematic approaches for studying these two problems, and establish important results. A RMA system often has multiple critical formations and in general, these are hard to locate. So in this thesis, we consider a special class of RMA systems whereby there is a geometric characterization for each critical formation. A formula associated with the characterization is developed for computing the Morse index/co-index of each critical formation. This formula has a potential impact on the design and control of RMA systems. In this thesis, we also consider a formation control model whereby the control of formation is achieved by varying interactions between selected pairs of agents. This model can be interpreted in different ways in terms of patterns of information flow, and we establish results about the controllability of this control system for both centralized and decentralized problems. / Engineering and Applied Sciences

Orientador: Prof. Dr. Wagner Tanaka Botelho / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2017. / Os avanços tecnológicos realizados na robótica móvel ao longo do tempo requereram o estudo e desenvolvimento de robôs cada vez mais autônomos e complexos, capazes de se adaptarem aos ambientes e condições que lhe são impostas. Contudo, dependendo do objetivo a alcancar, torna-se mais efetivo a utilização de uma maior quantidade de robos menores e mais simples, com capacidade cooperativa, resultando em um sistema escalavel e menos suscetývel a falhas gerais, denominado Sistema Multirrobotico (SMR). Tendo um SMR como objeto de estudo principal, este trabalho consiste no desenvolvimento de uma arquitetura multirrobotica descentralizada para o controle de posição e formação utilizando quadricopteros. A arquitetura é composta por n quadricopteros virtuais, implementados no software de simulação Gazebo e um quadricoptero real. O Robot Operating System (ROS) controla todos os quadricopteros, alem de gerenciar a comunicação entre os agentes roboticos. Um ponto importante é que, visando a diminuição dos custos do projeto, foi utilizado apenas um quadricoptero real, uma vez que somente um é necessário para validar a integração entre os mundos virtual e real. Para o controle de posição e formação foram propostos modelos matematicos que determinam as trajetorias dos n quadricopteros em formação linear, formação de figuras poligonais com troca de posição e formação de figuras poligonais com troca de posição e ponto de referencia movel. Nas simulações, foi possivel observar o deslocamento dos quadic'opteros em formação, validando os modelos matematicos. Por'em, no experimento real, a trajetoria no controle de formação foi parcialmente observada devido a alguns problemas apresentados na estrutura do quadricoptero e tambem por não possuir um sistema de sensoriamento no ambiente real. Apesar desses problemas, a integração entre os mundos virtual e real também foi validada. / The technological advances made in mobile robotics over time have required the study and development of robots that are increasingly autonomous and complex, capable of adapting to the environments and conditions that are imposed on them. However, depending on the goal to be achieved, it becomes more e.ective to use a larger number of smaller and simpler robots with cooperative capability, resulting in a scalable system that is less susceptible to general failures, called Multi-Robot Systems (MRS). Considering a MRS as the main study, the main target in this work is to develop a descentralized multi-robot architecture for position control using quadcopters. The architecture consists of n virtual quadcopters, implemented on the Gazebo simulation software and a real quadcopter. The Robot Operating System (ROS) controls all quadcopters as well as managing communication between them. In order to reduce the project costs, only one real quadcopter was used, since it is enough to validate the integration between the virtual and real worlds. The mathematical models were proposed to calculate the paths of the quadcopters in linear formation, formation of polygonal figures with rotation and formation of polygonal figures with rotation and mobile reference point. In the simulations, it was possible to observe the displacement of the quadcopters in formation, validating the mathematical models. However, in the real experiment, the trajectory in the formation control was partially observed due to some limitations presented on the quadcopter structure. Also, the sensing system was not available in the real environment. Despite these problems, the integration between the virtual and real worlds has also been validated.

Autonomous ground vehicles (AGVs) is a growing field within research. AGVs are used in areas like reconnaissance,surveillance, transportation and self-driving cars. The goal of this project is to drive a system of five AGVs modelled as differential drive vehicles along an arbitrary path through a field of obstacles while holding a formation. The goal is achieved by dividing the project into three subprojects. The first subproject is trajectory tracking of one AGV. This is achieved by using the differentialdrivemodel and driving the tracking error of the system to zero.The second subproject is formation control, where a displacement-based, double integrator model is used to get five AGVs to hold a formation of an equilateral triangle while following a path.The third subproject is collision avoidance between AGVs and static obstacles placed along the predetermined path. Collision avoidance is achieved by adding a repulsive potential field around the AGVs and obstacles. All three subprojects are then combined to achieve the goal of the project. Finally, simulations are done in Matlab which confirms that the proposed models are correct. / Autonoma vägfordon är ett växande område inom forskning. Autonoma vägfordon används inom områden som spaning, övervakning, transportering och självkörande bilar.Målet med det här projektet är att köra ett system med fem autonoma vägfordon modellerade som differentialdrivna fordon längsmed en slumpmässig väg genom ett fält med hinder samtidigt som de håller en formation. Målet uppnås genom att dela upp projektet i tre delprojekt. Det första delprojektet är banspårning med ett autonomt vägfordon. Det görs genom att använda den differentialdrivna modellen och driva systemets spårningsfel till noll. Det andra delprojektet är formationshållning där en förskjutningsbaserad dubbelintegratormodell används för att få fem fordon att följa en väg samtidigt som de håller formen av en liksidig triangel. Det tredje delprojektet handlar om att undvika kollision mellan fordonen och statiska hinder som placerats på vägen. Kollisionsundvikning uppnås genom att lägga på ett repellerande potentialfält runt alla agenter och hinder. Alla tre delprojekt kombineras sedan för att lösa projektmålet. Slutligen görs simuleringar i Matlab vilket bekräftar att de framtagna modellerna är korrekta. / Kandidatexjobb i elektroteknik 2022, KTH, Stockholm

In this thesis, new algorithms for formation control of multi agent systems (MAS) based on continuum mechanics principles will be investigated. For this purpose agents of the MAS are treated as particles in a continuum, evolving in an n-D space, whose desired configuration is required to satisfy an admissible deformation function. Considered is a specific class of mappings that is called homogenous where the Jacobian of the mapping is only a function of time and is not spatially varying. The primary objectives of this thesis are to develop the necessary theory and its validation via simulation on a mobile-agent based swarm test bed that includes two primary tasks: 1) homogenous transformation of MAS and 2) deployment of a random distribution of agents on to a desired configuration. Developed will be a framework based on homogenous transformations for the evolution of a MAS in an n-D space (n=1, 2, and 3), under two scenarios: 1) no inter-agent communication (predefined motion plan); and 2) local inter-agent communication. Additionally, homogenous transformations based on communication protocols will be used to deploy an arbitrary distribution of a MAS on to a desired curve. Homogenous transformation with no communication: A homogenous transformation of a MAS, evolving in an space, under zero inter agent communication is first considered. Here the homogenous mapping, is characterized by an n x n Jacobian matrix ( ) and an n x 1 rigid body displacement vector ( ), that are based on positions of n+1 agents of the MAS, called leader agents. The designed Jacobian ( ) and rigid body displacement vector ( ) are passed onto rest of the agents of the MAS, called followers, who will then use that information to update their positions under a pre- iv defined motion plan. Consequently, the motion of MAS will evolve as a homogenous transformation of the initial configuration without explicit communication among agents. Homogenous Transformation under Local Communication: We develop a framework for homogenous transformation of MAS, evolving in , under a local inter agent communication topology. Here we assume that some agents are the leaders, that are transformed homogenously in an n-D space. In addition, every follower agent of the MAS communicates with some local agents to update its position, in order to grasp the homogenous mapping that is prescribed by the leader agents. We show that some distance ratios that are assigned based on initial formation, if preserved, lead to asymptotic convergence of the initial formation to a final formation under a homogenous mapping. Deployment of a Random Distribution on a Desired Manifold: Deployment of agents of a MAS, moving in a plane, on to a desired curve, is a task that is considered as an application of the proposed approach. In particular, a 2-D MAS evolution problem is considered as two 1-D MAS evolution problems, where x or y coordinates of the position of all agents are modeled as points confined to move on a straight line. Then, for every coordinate of MAS evolution, bulk motion is controlled by two agents considered leaders that move independently, with rest of the follower agents motions evolving through each follower agent communicating with two adjacent agents.

978-91-7729-579-2A multi-agent system consists of multiple agents cooperating to achieve a common objective through local interactions. An important problem is how to reduce the amount of information exchanged, since agents in practice only have limited energy and communication resources. In this thesis, we propose dynamic event-triggered control strategies to solve consensus and formation problems for multi-agent systems under such resource constraints. In the first part, we propose dynamic event-triggered control strategies to solve the average consensus problem for first-order continuous-time multi-agent systems. It is proven that the state of each agent converges exponentially to the average of all agents' initial states under the proposed triggering laws if and only if the underlying undirected graph is connected.In the second part, we study the consensus problem with input saturation over directed graphs. It is shown that the underlying directed graph having a directed spanning tree is a necessary and sufficient condition for achieving consensus. Moreover, in order to reduce the overall need of communication and system updates, we propose an event-triggered control strategy to solve this problem. It is shown that consensus is achieved, again, if and only if the underlying directed graph has a directed spanning tree.In the third part, dynamic event-triggered formation control with connectivity preservation is investigated. Single and double integrator dynamics are considered. All agents are shown to converge to the formation exponentially with connectivity preservation.The effectiveness of the theoretical results in the thesis is verified by several numerical examples. / <p>QC 20171025</p>

Unmanned aerial vehicles have developed rapidly in recent years due to technological advances. UAV technology can be applied to a wide range of applications in surveillance, rescue, agriculture and transport. The problems that can exist in these areas can be mitigated by combining clusters of drones with several technologies. For example, when a swarm of drones is under attack, it may not be able to obtain the position feedback provided by the Global Positioning System (GPS). This poses a new challenge for the UAV swarm to fulfill a specific mission. This thesis intends to use as few sensors as possible on the UAVs and to design the smallest possible information transfer between the UAVs to maintain the shape of the UAV formation in flight and to follow a predetermined trajectory. This thesis presents Extended Kalman Filter methods to navigate autonomously in a GPS-denied environment. The UAV formation control and distributed communication methods are also discussed and given in detail.

As autonomous ground vehicles grow in popularity,it is of interest to study how they could coordinate together andhow the technical systems can be implemented in a safe andeffective manner. The objective of this report is to examine howto autonomously move a formation of vehicles without collisionswith obstacles or other vehicles. This is done by considering threefundamental aspects: trajectory tracking, formation control andcollision avoidance. Firstly a trajectory tracking controller for anindividual vehicle is implemented, with the function of followinga desired trajectory. Secondly a displacement-based formationcontrol is explored for two models, the double-integrator modeland the nonholonomic model, with the objective of coordinatingmultiple vehicles to keep a certain formation. Lastly collisionavoidance is integrated in the formation control by adding arepulsive term to the formation controller. It is shown thatthe agents maintained formation while avoiding collision withobstacles and other agents. The implemented controllers wereverified through simulations in MATLAB. / Eftersom autonoma markfordon blir allt mer vanligt är det vikt att studera hur de kan samordna tillsammans och hur de tekniska systemen kan implementeras på ett säkert samt effektivt sätt. Syftet med denna rapport är att undersöka hur man autonomt kan flytta en formation av fordon utan kollisioner med hinder eller med andra fordon. Detta görs genom att tre grundläggande aspekter övervägs: projektilspårning, formationshållning och kollisionsundvikande. Först implementeras en regulator för projektilsspårning, där funktionen är att följa en önskad bana. Därefter undersöks två modeller inom förskjutningsbaserad formationshållning, med ambitionen att samordna alla fordon för att behålla formationen. Slutligen så integreras metoder för kollisionsundvikning med formationshållning genom att lägga till bortstötande teknik i regulatorn för formationshållning. Det visades att fordonen lyckades med att upprätthålla formationen samtidigt som kollisioner mellan hinder och andra fordon undveks. De implementerade regulatorerna verifierades genom simuleringar i MATLAB. / Kandidatexjobb i elektroteknik 2021, KTH, Stockholm