Performance Optimization Of Multi-agent Systems

Multi-agent systems have attracted great interest from the control community due to their wide practical applications in engineering,biological and social systems.We study performance optimization problems of multi-agent systems in this dissertation by using the tools of matrix theory,control theory,game theory and algebraic graph theory together.The main results and contributions include the following points.1.For multi-agent systems with a leader,the optimal topology for leader-following consensus is considered based on linear quadratic regulator theory.For multi-agent systems with single-integrators,we propose a quadratic cost function,which is independent of the interaction graph,and find that the optimal topology is a star topology.For multi-agent systems with double-integrators,a quadratic cost function is also constructed,whereas the optimal topology is an unevenly weighted star topology.The universality of these findings indicates that if every follower is connected with the leader,the information exchange among followers is unnecessary.2.For multi-agent systems with a navigational leader and its opponent,the problem of minimizing the opponent's influence on followers is approached by designing interaction topology.Firstly,we tackle this problem by selecting guided informed-agents(the followers who can obtain information from the navigational leader).Two combinatorial optimization problems are subsequently formulated.One is to minimize the tracking error by selecting guided informed-agents.The other is to minimize the number of guided informed-agents under an upper bound constraint of the tracking error.Since the two problems are NP-hard,two algorithms are developed to obtain their suboptimal solutions,respectively.Secondly,for the scenario where the guided informed-agents are preset,we consider the problem of assigning the weights of edges to minimize the tracking error.We evaluate the upper and lower bounds of the tracking error by using convex optimization.3.Competitive behaviors between leaders are investigated in a game theoretical framework.For multi-agent systems with two leaders,there exist conflicts between leaders;namely,the leaders compete to attract followers.Firstly,by using graph theory and matrix theory,we formulate a standard two-player zero-sum game where two leaders are players.Strategies of each leader are defined by choosing at most k followers to propagate their information.Thus,the interaction graphs are generated from strategy pairs and the Nash equilibrium point of the game corresponds to the equilibrium topology.Secondly,we further prove that each player will choose exactly k followers when the game achieves a Nash equilibrium.Thirdly,for the case of choosing one follower,a necessary and sufficient condition is established for equilibrium topology.The equilibrium topology is obtained for the case where followers' interaction graph is a circulant graph or a graph with a center vertex.4.Competitive phenomena among competitive groups are also addressed.We study competition phenomena of multi-agent systems consisting of three groups of agents.In order to achieve maximal influence,agents of the first and the second groups send information to agents of the third group,which leads to competition.Since agents of the first(the second)cooperate and reach consensus,they have the same interests.Consequently,the competition among agents of the first and the second is actually a competition between two groups.Firstly,we formulate this competition as a noncooperative game in which the first and the second groups are two players.Players decide agents who send and receive information.Consequently,the interaction topology of the system is generated from players' strategies.Therefore,we define the interaction topology decided by Nash equilibrium of the game as the equilibrium topology of the system.Secondly,a necessary condition is developed for equilibrium topology.For the case where the third group's interaction graph is a tree or has a center root vertex,interchangeable Nash equilibrium solutions are obtained.Moreover,due to competition,the agents of the third group might reach consensus under the equilibrium topology.Thirdly,when the third group's interaction graph is bi-directed,a necessary and sufficient condition is given for the equilibrium topology.The equilibrium topology is also presented in the scenario where the third group's interaction graph is a bi-directed circulant graph.