多Agent动态影响图及其一种近似推理算法研究

针对多Agent影响图不能建模动态环境和多Agent马尔可夫决策过程难以表示Agents之间结构关系的问题,提出一种新决策模型——多Agent动态影响图(MADIDs).为了能有效地对MADIDs进行推理,提出一种扩展的BK(EBK)近似推理算法,其扩展体现在三个方面:在BK算法中加入效用结点的边际化操作,加入分割团来减小BK算法的推理误差,使用MADIDs分层分解所生成的联合树来降低推理的复杂性.在模型实例上的实验结果显示了MADIDs模型和EBK算法的有效性.     

多Agent动态影响图的近似计算方法

由于复杂系统具有高维性和不确定性常难以表示处理,因而知识表示和计算方法是复杂系统研究中的公开难题.当前,多Agent影响图不能建模动态环境和多Agent,马尔可夫决策过程难以表示Agents之间结构关系的问题,因而提出一种用局部概率因式表示动态环境中多Agent之间关系的新决策模型--多Agent动态影响图(MADIDs).针对MADIDs模型的联合概率分布和联合效用函数在计算上的高维问题,研究该模型的近似计算方法.给出MADIDs概率结构部分的一种分层分解的分布近似方法,并通过对该近似方法的误差和复杂性的分析,给出一个可对近似分布的精度和复杂性进行均衡的函数δ(k);给出一种BP神经网络通过局部效用的学习来近似计算MADIDs的联合效用.在模型实例上的实验结果显示了MADIDs模型近似计算方法的有效性.     

一种新的结构化博弈模型的表示和求解

针对多-Agent影响图表示方法存在效率低、结构模糊、表示复杂等方面的问题,提出了一种新的结构化博弈模型-非对称多-Agent影响图.该模型借鉴了非对称影响图中的表示机制和方法,继承了多-α-gent影响图在表示博弈时所具有的优点同时又具备了有效的表示非对称博弈的特点.给出了求解的算法,并使用一个实例来说明该模型的表示和求解.     

基于扩展影响图的超视距空战辅助决策方法

利用扩展影响图的表示特性和计算特性来解决辅助决策系统中知识表示与问题求解的一致性问题.采用条件弧和决策簇扩展影响图解决其在描述非对称性、不确定性问题中的局限,并根据该扩展影响图提出了基于条件分解的求解算法.基于扩展影响图方法对系统进行分析并描述系统结构,给出了基于扩展影响图进行辅助任务分析设计的框架和系统结构.仿真结果表明了所提出方法的有效性.     

基于扩展影响图的体系结构可靠性分析

扩展影响图是决策者基于不确定信息表示来求解复杂决策问题的图模型,由影响图延伸而来。体系结构可靠性分析是度量体系结构质量的重要内容之一。介绍了扩展影响图的基本思想,引入了防御图原理来构建体系结构可靠性的扩展影响图,通过与数据模型结合,给出了评价目标节点的效用值的方法。实验结果验证了基于扩展影响图的体系结构可靠性分析的可行性。     

基于Agent图的三级多Agent系统组织模型

多Agent系统的组织结构是Agent个体之间交互的框架。对分布式多Agent系统的组织方式、协作机制进行了简要讨论,提出了Agent域及Agent图的概念。根据不同Agent之间的地理位置和通信代价,由Agent个体、Agent组及Agent域三级组织结构形成一个Agent图,并借鉴计算机网络的分布式自适应路由选择策略进行多Agent系统的协作组织。分析表明,该模型具有高效、健壮、通信开销较小等优点。     

一种交互式动态影响图的改进算法

交互式动态影响图(I-DIDs)是基于概率图形理论的多智能体动态交互决策的图模型。为缓解该模型状态空间随时间片增加呈指数级增长的趋势,文中基于行为等价的基本思想压缩状态空间,提出构建Epsilon行为等价类的方法:利用有向无环图表示其它Agent可能的信度和行为,把信度在空间上接近的模型聚为一类,实现自顶向下合并行为等价模型。该过程避免求解状态空间中的所有候选模型,节省了存储空间和计算时间。模型实例上的仿真结果显示了该算法的有效性。     

动态影响图模型研究

部分可观察马尔可夫决策过程在策略空间和状态空间上的计算复杂性,使求解其一个最优策略成为NP-hard难题.为此,提出一种动态影响图模型来建模不确定环境下的Agent动态决策问题.动态影响图模型以有向无环图表示系统变量之间的复杂关系.首先,动态影响图利用动态贝叶斯网络表示转移模型和观察模型以简化系统的状态空间;其次,效用函数以效用结点的形式清晰地表示出来,从而简化系统效用函数的表示;最后,通过决策结点表示系统的行为来简化系统的策略空间.通过实例从3个方面和POMDP模型进行了比较,研究的结果表明,动态影响图模型为大型的POMDP问题提供了一种简明的表示方式,最后在Robocup环境初步验证了该模型.     

动态故障树的边值多值决策图分析

动态故障树分析对于复杂系统来说是一种重要的可靠性分析技术,但是二叉决策图等传统模块化方法存在严重的状态空间爆炸问题.本文系统介绍了边值决策图的动态故障树分析方法,其中边值多值决策图相对于其它现有的决策图具有更紧凑的表示函数,通过状态数的缩减,缩短了计算时间,有效缓解状态空间爆炸问题.实例证明了边值多值决策图在多状态系统和多功能系统中使用的方法和优势.     

多Agent动态影响图及其概率分布的近似方法

将多Agent影响图(MAIDs)在时间上进行扩展,提出一种决策模型:多Agent动态影响图(MADIDs),用于表示动态环境中多Agent协作的结构关系.为了有效计算MADIDs的概率分布,以Agents之间的策略偏序关系为指导,给出概率分布的一种分解近似方法,进而讨论概率分布在推理中的近似.对MADIDs概率分布计算的复杂性、误差以及误差在时间上的传播进行分析,进而基于KL差分,给出一个可对近似分布的精度和复杂性进行均衡的函数.最后,针对一个表示协作关系的MADID模型,进行实验和算法比较,实验结果显示该概率分布近似方法的有效性.     

Probabilistic Inference in Influence Diagrams

This paper is about reducing influence diagram (ID) evaluation into Bayesian network (BN) inference problems that are as easy to solve as possible. Such reduction is interesting because it enables one to readily use one's favorite BN inference algorithm to efficiently evaluate IDs. Two such reduction methods have been proposed previously (Cooper 1988; Shachter and Peot 1992). This paper proposes a new method. The BN inference problems induced by the new method are much easier to solve than those induced by the two previous methods.     

多Agent动态影响图的一种混合近似推理算法

多Agent动态影响图模型适合于对动态环境中多Agent问题进行建模,Agent之间结构关系被表示成局部的概率因式形式.概率图模型推理所面临的一个主要问题是难以实现近似推理的精度和复杂性之间的均衡.近似推理方法可提高推理精度,但同时也会带来推理精度的损失.BK和粒子滤波(PF)是动态概率模型两种重要的近似推理算法,BK算法有较高的计算效率但会引入较大的误差,PF可以近似任意分布但存在计算的高维问题.结合BK和PF的优点,提出多Agent动态影响图(MADIDs)的一种混合近似推理算法.根据概率图模型的可分解性,将MADIDs分解生成用于推理的原型联合树,混合近似推理算法在规模复杂度较小的团上执行PF推理以达到局部最佳估计,而在其他的团上执行BK推理,为了减小推理误差引入了分割团.仿真实验表明混合近似推理算法是MADIDs模型的一种有效推理方法,与BK和PF算法相比,该算法显著提高了推理精度,且可以实现推理精度和时间复杂性之间的均衡.     

非对称博弈的表示和求解

非对称博弈是一种普遍存在的博奔现象,现实中大量的博弈都呈现出非对称的特性.但是非对称博弈的表示问题在多-Agent影响图中是一个难以解决的问题,存在表示复杂和求解效率低的情况.针对该问题,借鉴了单-Agent决策系统中非对称性表示的方法,提出了一种新的博弈模型,有效的解决了非对称博弈的表示问题.给出了该模型详细的求解算...     

基于影响图的传球训练策略的实现

影响图是决策问题的图形表示,利用影响图可以有效地解决智能Agent的行为选择,而传球问题就是球员Agent选择传球速度和角度的问题。建立了一个基于影响图的传球模型,并根据该模型创建一个评价传球效果的效用函数;然后利用由教练程序改写的记录员程序来记录数据,并进行统计得到效用函数中的概率值;最后通过训练得到效用函数中系数的值,并利用此效用函数作传球训练。训练结果表明该效用函数是可信的。     

动态随机影响图建模方法

通过引入时间片的概念和反馈特性,时间片影响图增强了经典影响图描述因果影响关系网络的能力,但仍不足以支撑对复杂系统/体系问题中并发、交互、协同等过程的有效描述.参考离散事件系统建模的相关特性及方法,通过增加一个时间变量节点并扩展现有的模型规范,提出了一种动态随机影响图建模方法;详细说明了该方法的图形化语法、语义,并给出了其模型节点逻辑关系的迭代演算算法.该方法较完整地保持了典型时间片影响图的现有特性,可以作为改进现有方法的折中方案,以描述决策问题中的复杂行为过程.     

基于动态影响图的股市趋势预测

历史数据对未来状态的影响具有隐蔽性,导致基于数据的股市趋势预测是一个公开难题。为了有效地发现历史数据对股市未来状态的影响力,利用动态影响图建模成交量和K线形态之间的结构关系,提出一种基于量价结构关系的联合树推理预测算法（VP-JT）。提取股票的阶段成交量特征和阶段K线形态特征,给出阶段成交量对于股市价格影响的作用原理;利用配合度量化当前阶段成交量与K线形态之间关系一致性程度;利用动态影响图建模阶段量价在时间上的作用过程;通过联合树的自动推理对股市未来状态进行预测。在实际数据上进行实现和算法比较,实验结果表明量价结构关系的联合树推理算法具有更高的准确率。     

Symbolic Reasoning with Weighted and Normalized Decision Diagrams

Several variants of Bryant's ordered binary decision diagrams have been suggested in the literature to reason about discrete functions. In this paper, we introduce a generic notion of weighted decision diagrams that captures many of them and present criteria for canonicity. As a special instance of such weighted diagrams, we introduce a new BDD-variant for real-valued functions, called normalized algebraic decision diagrams. Regarding the number of nodes and arithmetic operations like addition and multiplication, these normalized diagrams are as efficient as factored edge-valued binary decision diagrams, while several other operators, like the calculation of extrema, minimum or maximum of two functions or the switch from real-valued functions to boolean functions through a given threshold, are more efficient for normalized diagrams than for their factored counterpart.     

A NEW METHOD FOR INFLUENCE DIAGRAM EVALUATION

As influence diagrams become a popular representational tool for decision analysis, influence diagram evaluation attracts more and more research interests. In this article, we present a new, two-phase method for influence diagram evaluation. In our method, an influence diagram is first mapped onto a decision graph and then the analysis is carried out by evaluating the decision graph. Our method is more efficient than Howard and Matheson's because, among other reasons, our method generates a much smaller decision graph for the same influence diagram. Like those most recent algorithms reported in the literature, our method also provides a clean interface between influence diagram evaluation and Bayesian net evaluation. Consequently, various well-established algorithms for Bayesian net evaluation can be used in influence diagram evaluation. Furthermore, our method has a few unique merits. First, it takes advantage of asymmetry in influence diagrams to avoid unnecessary computation. Second, by using heuristic search techniques, it provides an explicit mechanism for using heuristic information that may be available in a domain-specific form. These additional merits make our method more efficient than the current algorithms in general. Finally, by using decision graphs as an intermediate representation, the value of perfect information can be computed in a more efficient way.     

Algebric Decision Diagrams and Their Applications

In this paper we present theory and experimental results on Algebraic Decision Diagrams. These diagrams extend BDDs by allowing values from an arbitrary finite domain to be associated with the terminal nodes of the diagram. We present a treatment founded in Boolean algebras and discuss algorithms and results in several areas of application: Matrix multiplication, shortest path algorithms, and direct methods for numerical linear algebra. Although we report an essentially negative result for Gaussian elimination per se, we propose a modified form of ADDs which appears to circumvent the difficulties in some cases. We discuss the relevance of our findings and point to directions for future work.