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

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

A Hybrid Approximate Inference Algorithm for Multi-Agent Dynamic Influence Diagrams

Multi-agent dynamic influence diagrams (MADIDs) are fit for modeling multi-agent systems in dynamic environment, where structural relations among agents are represented in the local factorial probability form. A major problem of probability graphical models inference is that it is difficult to realize tradeoff between accuracy and complexity computational of approximate inference. In general, the approximation inference methods can improve computational efficiency, but it will also induce the loss of accuracy. BK algorithm and particle filter are two important approximate algorithms for dynamic probability models. BK algorithm has considerable computational efficiency, but induces the error of the inference. PF algorithm can approximate arbitrary distribution, but with the high dimension problem of computation. Hybrid approximate inference(HAI) algorithm for multi-agent dynamic influence diagrams (MADIDs) is presented by combining the advantage of BK and particle filter, and HAI algorithm converts the distribution of MADIDs into the local factorial form. Based on decomposability of probability graph models, HAI algorithm decomposes MADIDs to prototype junction tree, and particle filter is executed on these clusters with lesser scale complexity to achieve local optimal estimation, while BK for other clusters; in addition, separator clusters are induced for decreasing inference errors in HAI algorithm. Simulation results show that the proposed algorithm improves computational precision notably comparied with BK algorithm and PF algorithm, and the algorithm is an efficient approximation inference method of MADIDs and can establish a tradeoff between accuracy and complexity of approximate distribution.