【作者】 李勇；

【导师】 蒋建国；

【作者基本信息】 合肥工业大学 ， 计算机应用技术， 2008， 博士

【摘要】 在多Agent系统中,多个Agent可以通过联盟的形式完成单个Agent不能完成的任务,集中体现了多Agent系统设计的初衷。有关联盟的研究是多Agent系统的一个关键问题。学术界现已进行了大量研究,并取得了丰富的成果。单任务联盟生成问题是一个复杂的组合优化问题,进化算法和群智能算法是常见的解决方法。但现有的研究仅仅从进化算法或群智能算法的角度出发,研究单任务联盟生成的求解,而忽略了问题本身的特点,因此在问题的求解质量上还存在着改进的必要和可能。另外目前尚没有研究提出本问题的多项式时间近似算法来适应实时性要求高的场合。联盟特征函数是联盟问题的基础。现有的联盟特征函数定义基于能力向量或资源向量的描述,但这两种方式都存在着不足:无论能力或资源,用简单的数字来描述都是不切实际的:能力的增强或资源的累加也不一定可以用简单的加减法来计算。基于合同网的任务分配是多Agent系统常见的任务分配机制。但传统的合同网存在着待选Agent范围大、通信代价大、对自私Agent的恶意投标缺乏防范等不足,现有的相关的改进也缺乏较全面的考虑。针对以上问题,本文做了相关研究。主要贡献在于:(1)提取单任务Agent联盟生成的先验知识,用于指导相关进化算法和群智能算法求解单任务联盟生成问题(2.1节内容),提高了算法求解质量;提出一种求解单任务Agent联盟生成的贪婪算法(3.1节内容):提出一种求解单任务Agent联盟生成的多项式时间近似算法(3.2节内容),更适合于实时性要求高的场合。(2)对现有的Agent信任与名誉的FIRE模型进行改进,提出基于Agent组织的半分布式FIRE模型(4.2节内容);提出了一种基于服务观点和改进的FIRE模型的新联盟特征函数定义,并考察了在此定义下的单任务联盟和多任务联盟问题的求解(4.3节内容);设计了一种求解在新联盟特征函数定义下的多任务联盟生成问题的贪婪算法(4.4节内容)。(3)提出基于改进FIRE模型的合同网运行机制,将其运用于任务分配。相比现有的工作,对缩小投标范围、评估Agent投标标书质量、减小招标风险等有着明显的效果,基于此合同网的多Agent任务分配机制在通信成本、安全性等方面也得到了很好的改善(5.2节内容)。更多还原

【Abstract】 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).更多还原