Approximating behavioral equivalence for scaling solutions of I-DIDs
Approximating behavioral equivalence for scaling solutions of I-DIDs
复制标题
I-DID 扩展解决方案的近似行为等效性
DOI：
10.1007/s10115-015-0912-x
复制
发表时间：
2016
影响因子：
2.7
通讯作者：
rasekaran Muthukumaran
中科院分区：
文献类型：
--
作者：
Zeng Yifeng;Doshi Prashant;Chen Yingke;Pan Yinghui;Mao Hua;Ch;rasekaran Muthukumaran
交互动态影响图（I-DID）是一种公认的用于不确定情况下多智能体顺序决策的图形框架。i - did简洁地表达了一个问题，即个体代理在与其他未知类型的代理共享的不确定环境中应该如何行动。i - did面临着解决归因于其他代理的大量模型的挑战。解决i - did的一种已知方法是将行为等效的其他代理的模型分组。识别模型等价性需要求解模型并比较它们的解，通常表示为策略树。由于树随着决策时间步数呈指数增长，比较整个策略树变得难以处理，从而限制了以前I-DID技术的可扩展性。在本文中，我们的具体方法侧重于利用部分策略树进行比较，并确定树的叶子上更新的信念之间的距离。我们提出了一种原则性的方法来确定要考虑多少策略树，以解决方案的质量换取效率。通过允许部分策略树具有不同长度的路径，我们进一步改进了这项技术。我们在多个问题领域评估了这些方法，并证明了与以前的方法相比，这些方法的可扩展性有了显著提高。
Interactive dynamic influence diagram (I-DID) is a recognized graphical framework for sequential multiagent decision making under uncertainty. I-DIDs concisely represent the problem of how an individual agent should act in an uncertain environment shared with others of unknown types. I-DIDs face the challenge of solving a large number of models that are ascribed to other agents. A known method for solving I-DIDs is to group models of other agents that are behaviorally equivalent. Identifying model equivalence requires solving models and comparing their solutions generally represented as policy trees. Because the trees grow exponentially with the number of decision time steps, comparing entire policy trees becomes intractable, thereby limiting the scalability of previous I-DID techniques. In this article, our specific approaches focus on utilizing partial policy trees for comparison and determining the distance between updated beliefs at the leaves of the trees. We propose a principled way to determine how much of the policy trees to consider, which trades off solution quality for efficiency. We further improve on this technique by allowing the partial policy trees to have paths of differing lengths. We evaluate these approaches in multiple problem domains and demonstrate significantly improved scalability over previous approaches.