论文部分内容阅读
多智能体在不确定环境下的决策问题是目前的研究热点。在众多决策模型中,交互式动态影响图(I-DID)脱颖而出。与其它模型不同,I-DID从个体智能体的角度来建模由环境的物理状态和其它智能体共同组成的交互式状态空间,并利用贝叶斯方法更新模型的信度状态。凭借着明显的建模和计算优势,I-DID已成为求解多智能体序贯决策问题的一种全新的有效方法。然而在现实生活中,合作与竞争并存,使得决策面临着一系列的挑战。在合作型问题中,建立合理的通信模型使得队友之间可以更好地共享信息。由于通信是有偿的,因此通信时机的选择同样重要;在竞争型问题中,智能体需要建立起未知对手的模型,然后在若干候选模型中进一步判断其真实模型从而制定相应的对策。另外,面对复杂问题时模型求解速度较慢,有必要寻找快速而准确的求解算法。本文为了解决这些实际问题,对I-DID进行了深入的研究。主要工作如下: 1.在合作型多智能体系统中,通信是智能体之间沟通的主要方式。本文基于I-DID建立了通信交互式动态影响图(Com-I-DID),使得智能体具有了交换和共享信息的能力。通过在I-DID的两个相邻时间片之间加入通信子阶段,来实现通信的过程。由于Com-I-DID运算复杂度高,再加上通信需要一定的费用,使得智能体必须理性决定何时发起通信,而不是在每个时间片都执行通信动作。本文探讨了一种基于事件驱动的通信时机选择方法,在得到相对准确的信息时才触发通信行为,优化了整个Com-I-DID的运行。 2.I-DID的枚举式表达——交互式部分可观测马尔科夫决策过程(I-POMDP)采用嵌套建模方法,因此求解它的复杂度较高,其复杂性从未量化地度量过。本文使用了多种信息熵,如块熵、熵率和熵增益来度量I-POMDP的复杂性和不确定性。而后分别分析了在随机策略和确定性策略下其复杂性的熵测度。可以看出,I-POMDP复杂性的熵测度是随着策略变化的,这说明其复杂性和智能体使用的策略有一定的相关性。其结果对研究I-DID与I-POMDP的快速求解算法有一定的参考价值。 3.在非合作的多智能体系统中,智能体必须对有限的资源展开争夺。在这样的环境中,智能体之间不会经通信共享私有信息,而了解对手就需要通过建模的方法来实现。本文利用I-DID作为对手建模的工具,其特有的模型节点可以用来保存对手的所有候选模型,并能随着时间不断地更新。接着提出了两种判断对手真实模型的方法: (1)在智能体之间的不断交互中,结合观察到的其它智能体做出的动作,在模型空间中利用“观察—动作”序列逐步排除候选模型,最终判断出其真实模型。 (2)利用贝叶斯网提出一种判断对手真实模型的方法。记录下观察到的对手动作序列,并与预先计算好的最优动作序列一起作为训练集,训练动态贝叶斯网络的参数,不断计算并修正候选模型的权重,从而判断出对手的真实模型; 4.影响I-DID应用到实际问题的最重要原因是,其它智能体的模型数量随时间呈指数级增长。之前的方法侧重于比较候选模型的整个策略树或部分策略树,再将等价模型归为一类,取出代表性模型从而加速计算。本文提出了一种全新的求解思路,利用互信息度量候选模型与真实模型的相关性,通过逐步剔除不相关或弱相关的候选模型,只保留真实模型来最大程度地压缩模型空间。这使得求解I-DID变得更加高效,也让I-DID可用于求解更加复杂、规划时间更长的问题。