Coverage Control Of Multi-Agents Based On Game Theory

The intelligence of group, shown by the cooperation of multi-agents, can perform complicated tasks which an individual cannot. The cooperative control of multi-agents investigates how a large number of individuals with simple function can perform complicated tasks or achieve cooperative group behaviors by distributed control. As an important research aspect of the multi-agent system, coverage control of multi-agents has received more and more attention since last decade.In this dissertation, we study how a group of agents with limited sensing, communicating and computing capability can maximize their coverage area in given environment as well as keep connected after self-organized moving from a random distributed initial state. These agents can accomplish tasks such as data collection and transmission, target detecting and tracking, as well as the environment monitoring and control. So it has strong application background in the areas of national defense, military affairs, wireless sensor networks and so on. Non-cooperative Game emphasizes the individual rationality and is always used to solve the multi-person, multi-objective optimization problem, yet being applied to the multi-agent cooperation control problem more and more. Based on the general idea of non-cooperative game, a totally distributed coverage control algorithm is proposed in this dissertation. Results of simulations show that the algorithm can keep the connectivity of the multi-agent system effectively, and maximize the coverage area at the same time. The main research work of this dissertation can be summarized as the following three aspects:1. The model the coverage control problem of multi-agents is established based on the normalized form of non-cooperative game, where each agent in the system is regarded as a player in the game, and its moving orientation as the strategy set. Since all the agents are moving synchronously, and each agent only has local information, the whole moving process of the system can be regarded as a series of static games with incomplete information.2. An innovative multi-agent coverage control algorithm based on game theory (G-MAC algorithm) is proposed. At every moment, each agent only uses its local information to independently determine its current movement (including moving orientation and moving step-length) according to some rules. When choosing its moving orientation, each agent uses a simple'Cournot Adaptive Strategy', that is to choose its current optimal moving orientation according to the neighbors'actual moving orientation and step length at last moment, known by one-step communication.When deciding its step length, each agent identifies its current maximum feasible step length according to some heuristic rules. In fact, the global connectivity of the system is kept by such local constraint.3. The G-MAC algorithm is extended to some more practical situations such as the environment with fixed obstacles, existence of agents with different communication ranges, and the bounded environment covered. The improved algorithm can be applied to the above situations by changing the form of payoff function, or extending the rules to identify the maximum feasible step length.