论文部分内容阅读
普适化、网络化、智能化、代理化、人性化是自动化计算发展的总体趋势,多Agent计算正是在此历史进程中继分布式计算、P2P计算出现的一种新的先进计算模式。其对问题求解过程类似于人类思维的方式,不同于传统的算法设计,不需要对问题有全面的分析,而只需指定Agent的目标,它们能通过彼此交互自动地逐步实现用户的目标。对大型分布式问题建立多Agent系统使计算机系统能更智能化,进一步代替更多人的工作;面向Agent的软件工程使程序设计更为人性化,软件设计过程更符合人的思考习惯;基于Agent的社会仿真是计算机科学与社会学的结合,使计算机技术在人文领域发挥其积极作用。多Agent计算有利于促进计算机技术的进一步繁荣。多Agent计算要真正达到其概念提出所具有的优秀特性,还需要大量的科研努力。就基于Agent的系统而言,Agent的构造、通信语言的设计、合作与协调是多Agent计算最直接面临的、亟待解决的关键问题。而以合作与协调为目的的Agent交互能力是多Agent计算区别于其他计算模式的关键所在。正如人类社会一样,合作与协调是解决大型复杂问题的重要途径。本文正是对多Agent系统的合作与协调问题进行了积极的探索,在部分子方向上取得了一定的成果。组织建立、联盟形成、任务分配是多Agent合作研究的主要方向。组织和联盟是多Agent合作的基础,而任务分配实现合作关系的实例化。本文针对多Agent系统的任务分配问题,考虑多Agent的网络拓扑和能力水平存在差异的特点后,在以往并行计算任务调度的基础上,提出了两个适应网络拓扑的合作异构Agent间任务分配算法。一个是考虑这两个特性后通过穷举搜索得到最优Agent分配组合,一个是利用启发式搜索降低算法时间复杂度得到任务次优的Agent组合。对于大规模的多Agent系统、任务动态到达的情形下,以上算法无用武之地。因此,继续探讨了多任务流的动态分配问题,提出了基于Q学习的分布式自适应分配算法。该算法不仅能适应自身任务流的到达过程,还充分兼顾其他任务流到达过程及分配的影响。分布式特性使得算法适用于开放的、局部可见的多Agent系统,而强化学习的采用使得任务分配决策能适应系统的任务负载和分布。该算法表现出较高的任务吞吐量,较低的平均任务执行时间。对于多Agent系统中协调问题,主要的研究工作可以划分为三块:建立群体思维状态模型、多Agent规划、Agent社会规范。这三块对Agent之间的协调都有各自的优势和效果。本文对这一问题的工作是多Agent规划的延续。本文提出的两个模型所得到的规划不再是传统意义上一系列行为的排列组合,而是Agent在实现目标过程中行为的选择策略。这使得规划具有更大灵活性。多Agent学习是制定行为策略中研究较多且很具前景的方法。本文针对冲突博弈这一常见的Agent竞争关系进行了分析,基于矩阵博弈的Nash均衡概念定义了Agent的最佳响应策略,然后利用模型无关的强化学习方法找到该策略。该模型得到的策略很大程度上降低了冲突发生的次数,增强了Agent行为的协调性,而且从长期效用看,策略具有一定的公平性,有利于系统的稳定。对于一般和博弈的协调,目前提出的许多算法都较容易被利用而降低了自身的利益,本文在分析了Agent行为策略的时变性和适应性两个重要属性后,认为具有这两个属性的动态策略有利于Agent做出更为理性的决策,在混合多Agent环境下有利于避免被利用的风险,针对不同类型Agent做出最大化自身利益的响应。Agent大规模应用后,Agent社会将成为一个特殊的多Agent系统。这时Agent的社会属性将变得越来越重要。除了信念、意图、愿望等心智属性外,个性也将在Agent的行为选择中具有重要影响,依据个性对其他Agent建模有利于制定更为协调的行为策略。本文将个性加入到Agent的行为选择过程中,利用定性决策理论,建立了一个个性化的行为选择模型。不同的定性决策原则对应了不同的Agent性格特征,依据这些决策原则选择的行为造成了Agent行为的多样化。进一步,由于个性存在复杂和描述困难的特点,而人工神经网络具有刻画人类难以理解函数的优势,因此基于神经网络提出了一个新的个性化行为选择模型。相比于前者,该模型具有更强的个性表征能力,能刻画出更为细腻的个性类型。此外,基于复杂适应系统仿真工具包Swarm搭建了多Agent系统的仿真平台,并透过实例研究了个性在实践中的应用,更明确了个性研究的重要性和现实价值。以上这些工作尽管原理较为简单,但却是在传统符号逻辑基础上研究Agent心智状态之外的一个新的尝试和初步的探索,为多角度反映社会混沌复杂特征提供了可能。综上所述,本文以多Agent系统中的合作与协调机制为研究课题,通过广泛调研和深入探索,在任务分配、基于学习的行为协调、个性化行为选择三个问题上提出了如下若干有益的模型和算法:适应网络拓扑的合作异构Agent静态任务分配算法;基于Q学习的多任务流动态分配算法;基于后悔值的多Agent冲突博弈强化学习机制;混合多Agent环境下一般和博弈动态策略强化学习机制;基于定性决策理论的Agent个性化行为选择模型;基于人工神经网络的Agent个性化行为选择模型。