多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模型,进行实验和算法比较,实验结果显示该概率分布近似方法的有效性.     

非对称博弈的表示和求解

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

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.     

Putting value of information theory into practice: a methodology for building sequential decision support systems

Abstract: The paper presents a methodology for building sequential decision support systems based on decision theory using value of information (for short, DT‐VOI based SDSSs). DT‐VOI based SDSSs support decision‐makers in difficult problems of sequential decision‐making. In particular we consider the problem of building DT‐VOI based SDSSs which are capable of supporting decisions in critical situations where (1) making a decision entails knowing the states of some critical hypotheses, and such knowledge is acquired by performing suitable tests; (2) test outcomes are uncertain; (3) performing a test entails, in general, some drawbacks, so that a trade‐off exists between such drawbacks and the value of the information provided by the test; (4) performing a test has the side‐effect that it changes the expected benefit from performing other tests; (5) exceptional situations alter probability and utility default values.     

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.     

Polynomial-Size Binary Decision Diagrams for the Exactly Half-<Emphasis Type="Italic">d</Emphasis>-Hyperclique Problem Reading Each Input Bit Twice

A binary decision diagram (BDD) is a graph-based data structure representing Boolean functions; ℓ-BDDs are BDDs with an additional restriction that each input bit can be tested at most ℓ times. A d-uniform hypergraph H on N vertices is an exactly half-d-hyperclique if N/2 of its vertices form a hyperclique and the remaining vertices are isolated. Wegener [J. ACM 35(2), 461–471 (1988)] conjectured that there is no polynomial-size (d−1)-BDD for the Exactly half-d-hyperclique problem. We refute this conjecture by constructing polynomial-size (syntactic) 2-BDDs for the Exactly half-d-hyperclique problem for every d≥2. Institute for Theoretical Computer Science (ITI) is supported by Ministry of Education of Czech Republic as projects LN00A056 and 1M0545.     

带权定性影响图

定性影响图是具有精确概率和效用的影响图的定性抽象。在定性影响图中,节点之间的影响关系使用定性符号描述,这种符号描述简化了不确定知识的表示,降低了影响图建模的难度,加速了不确定知识的推理。但是,定性影响图在抽象过程中损失了部分信息,导致定性影响图在评价过程中会产生不确定结果,阻碍了定性影响图的广泛应用。以加权的思想扩展定性影响图,使扩展的定性影响图中每个定性影响都带有一个表示节点间影响强弱的数值权值,在评价过程中根据定性影响权值的比较来减少不确定结果的产生,从而扩大定性影响图的应用范围。     

多智能体分层协作规划及在RoboCup中的应用

为了更好地解决一类通讯受限环境中多智能体任务协作规划问题,提出了基于MAXQ-OP的多智能体在线规划方法,并在RoboCup仿真2D足球比赛的人墙站位和多球员传球问题中对算法进行了实验.实验结果表明,这个方法使智能体在需要协作配合的环境中的表现比传统方法有了明显提升.     

A Comparison of Free BDDs and Transformed BDDs

Ordered binary decision diagrams (OBDDs) introduced by Bryant (IEEE Trans. on Computers, Vol. 35, pp. 677–691, 1986) have found a lot of applications in verification and CAD. Their use is limited if the OBDD size of the considered functions is too large. Therefore, a variety of generalized BDD models has been presented, among them FBDDs (free BDDs) and TBDDs (transformed BDDs). Here the quite tight relations between these models are revealed and their advantages and disadvantages are discussed.     

Free binary decision diagrams for the computation of EAR n

Free binary decision diagrams (FBDDs) are graph-based data structures representing Boolean functions with the constraint (additional to binary decision diagram) that each variable is tested at most once during the computation. The function EAR_n is the following Boolean function defined for n × n Boolean matrices: EAR_n(M) = 1 iff the matrix M contains two equal adjacent rows. We prove that each FBDD computing EAR_n has size at least and we present a construction of such diagrams of size approximately .