论文摘要
在多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节内容)。