多Agent系统中合作与协调机制的研究

摘要

普适化、网络化、智能化、代理化、人性化是自动化计算发展的总体趋势,多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个性化行为选择模型。

目录

前言

摘要

ABSTRACT

第一章 绪论

1.1.研究背景

1.2.基于MAS计算的关键问题

1.3.本文工作及创新

1.4.本文组织与结构

参考文献

第二章 多AGENT合作与协调研究概况及现状

2.1.引言

2.2.AGENT与多AGENT系统基本理论

2.2.1.Agent概念和结构

2.2.2.多Agent系统概念和外延

2.3.多AGENT合作与协调的分析方法

2.4.多AGENT合作问题的研究现状

2.4.1.组织建立

2.4.2.联盟形成

2.4.3.任务分配

2.5.多AGENT协调问题的研究现状

2.5.1.群体思维状态模型

2.5.2.多Agent规划

2.5.3.Agent社会规范

2.6.小结

参考文献

第三章 适应分布异构环境的任务分配机制

3.1.引言

3.2.相关工作

3.3.静态任务分配模型

3.3.1.问题定义

3.3.2.最优分配算法

3.3.3.启发式分配算法

3.3.4.时间复杂度分析

3.3.5.案例学习及性能分析

3.4.多任务流动态分配模型

3.4.1.问题定义

3.4.2.单任务流Q学习模型

3.4.3.值函数共享机制

3.4.4.基于Q学习的分布式多任务流分配算法

3.4.5.实验及性能分析

3.5.小结

参考文献

第四章 基于强化学习的行为协调机制

4.1.引言

4.2.MARKOV对策及强化学习

4.3.多AGENT学习相关工作

4.4.冲突博弈强化学习模型

4.4.1.冲突博弈

4.4.2.最优策略

4.4.3.基于后悔值的Q学习模型

4.4.4.算法实现

4.4.5.实验与结果分析

4.5.一般和博弈动态策略强化学习模型

4.5.1.时变性策略

4.5.2.适应性策略

4.5.3.纯策略Q学习

4.5.4.混合策略Q学习

4.5.5.性能验证与分析

4.6.小结

参考支献

第五章 个性化行为选择机制

5.1.引言

5.2.离散个性空间的行为选择

5.2.1.定性决策理论

5.2.2.基于定性决策论的个性化决策模型

5.2.3.有效性验证

5.3.连续个性空间的行为选择

5.3.1.基于神经网络的个性化决策模型

5.3.2.个性神经网络学习算法

5.3.3.有效性验证

5.4.基于SWARM的多AGENT系统仿真

5.4.1.Swarm简介

5.4.2.仿真平台及实例解析

5.5.小结

参考文献

第六章 总结及展望

6.1.本文研究总结

6.2.下一步工作

致谢

附录A 攻读博士学位期间发表(录用)论文情况

附录B 攻读博士学位期间参加科研学术活动情况