交互式动态影响图的一种近似求解算法  

Approximate solving-solution of interactive dynamic influence diagrams

作　　者：李波[1] 罗键[1] 庄进发[2,3] 尹华一[1] 

机构地区：[1]厦门大学自动化系,福建厦门361005 [2]厦门东南融通系统工程有限公司博士后科研工作站,福建厦门361008 [3]解放军信息工程大学通信与信息系,河南郑州450002

出　　处：《华中科技大学学报（自然科学版）》2011年第10期64-68,共5页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(60975052)

摘　　要：提出一种基于行为等价原理分段处理交互式动态影响图(I-DID)的近似算法:先将底层I-DID模型分解成包含若干时间片的子片段,求解首片段,获得各模型的策略树,并依行为等价原理合并策略树,形成策略图,其结果作为下一片段的初始模型,再进行求解.重复这个过程,直到最后片段结束,获得完全策略图,用来指导agent是否进行模型更新.最后,针对多agent老虎问题进行试验和算法比较,试验结果从模型解的质量和模型空间大小2个方面验证了所提算法的有效性.An approximate solution was presented based on the principle of behaviorally equivalent for interactive dynamic influence diagrams（I-DID）.The amount of calculation was reduced by decomposing the I-DID model into more than one fragment and compressing the space of other agents′ candidate models.First,the model of I-DID or DID at bottom level was split into sub-segments that include a number of time slices,then the solution of the first segment for the initial models was obtained,and the policy graph could be gotten by merging policy trees based on the principle of behaviorally equivalent.Continue to solve the next I-DID or DID,the output of the previous fragment was regarded as the input for the subsequent fragment,until the last fragment,and the whole policy graph was available,which identifying whether the model needed to be updated.Experiment results,which on the quality of solution and the magnitude of model space for multi-agent tiger problem,show the validity of the approximate method.

关 键 词：多AGENT系统 AGENT建模 动态决策 交互式动态影响图 行为等价 最小模型集 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]