Research On Complicated Coalition Mechanism Based On Swarm Intelligence

The distributed intelligent control based on multi-agent systems (MAS) is springing up vigorously for an application to cooperative tasks supported by computers. Therefore, research on coalition in the field of MAS is becoming more important. Forming stable and balanced coalitions is a major research challenge in the field of control theory. Existing researches suffer from an important drawback that an agent can not but join in only a coalition and a coalition can not but be engaged in only a task, producing a big waste of resources and capabilities, and limiting the scope of their applications in real-world scenarios.Against this background, we develop a novel "Complicated Coalition" and adopt swarm intelligence to address the problem of coalition formation in multitask environments where an agent may join in several different coalitions and a coalition may perform several different tasks simultaneously. Our aim is to improve the efficiency of solving tasks and utilizing resources and provide a theoretical and methodological guidance for many complicated control problems.The main research contents and innovative contributions of this dissertation are as follows:(1) We develop a particle swarms cooperative optimization based algorithm for complicated coalition serial generation. A novel "Virtual Agent" enlightened by graph theory is used to transfer the remainder capabilities of a father coalition. To the latter tasks, the father coalition will delegate its power to the virtual agent to compete for tasks. Specially, our algorithm realizes the condition that an agent can take part in several different coalitions and a coalition can turn its hand to several different tasks, partly reducing the waste of resources and capabilities. Moreover, the experimental result shows that our algorithm is more efficient for more tasks with small capabilities.(2) We develop discrete particle swarm optimization with two-dimensional binary encoding for solving complicated coalition parallel generation. Specially, checking on encoding validity and strategies for conflict resolution are brought into effect to surmount resource conflict and coalition lock when several different coalitions compete against each other for the same agent with small capabilities simultaneously in course of problem solving. Moreover, our algorithm realizes the condition that an agent can join in several different coalitions, partly improving the efficiency of utilizing resources in MAS.(3) We develop a novel strategy for coalition utility distribution based on distribution according to work and non-reducing utility. Existing strategies have an inextricable free-rider problem and can not clearly distinguish each agent's contribution for their coalition, which may result in the potential instability of their coalition In order to tackle the shortage above, auction is used to allocate tasks quickly and efficiently, bargain is adopted to distribute coalition utility especially additional utility reasonably, and also the necessary conditions of local non-reducing utility and global non-reducing utility are deduced respectively. Our strategy strictly follows the principles of distribution according to work and non-reducing utility. In super-additive task oriented domains, our strategy can reach a global optimal coalition which is stable with Nash equilibrium.(4) We develop an almost everywhere strong convergence proof for ant colony optimization by using Markov process and martingale theory, and then we present a dynamic coalition formation strategy based on positive feedback mechanism of ant colony optimization. Specially, familiarity is adopted to describe the interrelation between agents and pheromone trail in ant colony is reused to describe the familiarity between acquaintances. Moreover, pheromone updating rules in ant colony optimization are adopted to adjust the familiarity. The experimental result shows that our strategy can reduce the communication cost and resource consumption in the whole system and markedly enhance the whole system's reliability.