Research On Coalition And Task Allocation In Multi-Agent System

Multi-Agent systems are becoming increasingly important. Autonomous Agents working in multi-Agent environment may need to cooperate by means of coalition in order to fulfill tasks which can't be performed by any single Agent. Coalition formation problem is a key topic in multi-Agent systems and has received a considerable amount of attention in recent years.It is a complicated combinatorial optimization problem to search for the optimal, task-oriented Agent coalition for single task. Evolutionary algorithms and swarm intelligent algorithms are widely used to solve the problem. However, the characteristics of the problem have been ignored by the presented research. Therefore, it is both necessary and possible to improve the quality of the algorithms. Another reality is that there are no any deterministic approximation algorithms being proposed to apply to those occasions where real-time performance is important.Coalition value given by a coalition characteristic function is used to measure the quality of a coalition in a multi-Agent system. However, both the present capacity vector method and the resource vector method are unsuitable for defining coalition characteristic function.The existing task allocation mechanism based on the Contract Network Protocol (CNP) in a multi-Agent system exist some disadvantages such as the high network traffic and the low security. And the relative improvements lack comprehensive considerations.The following is the main work and contribution of the author:(1) Prior knowledge derived from the characteristics has been used to improve the quality of search of evolutionary algorithms and swarm intelligent algorithms and the results of contrastive experiment show that this improvement is effective (section 2.1). Furthermore, a greedy algorithm and a fast approximation algorithm are presented to apply to some special occasions where real-time performance is important (section 3.1 & 3.2).(2) FIRE is a new, decentralized, and integrated trust and reputation model for Agent in MAS. However, there are some drawbacks in FIRE such as the low efficiency in getting WR and the difficulty in eliminating possible lying from Agents. To solve the drawbacks, an improved organization-based and half-decentralized FIRE model is presented (section 4.2). In addition, with a focus on service, a simple and efficient coalition characteristic function based on the improved FIRE model is proposed and a greedy algorithm is also presented to solve the coalition formation problem based on the new coalition characteristic function (section 4.3 & 4.4).(3) A new task allocation mechanism based on the CNP and the improved FIRE model is put forward to counter the shortcomings of the existed ones(section 5.2).