Double compression of models for interactive dynamic influence diagrams

Conference Name:2011 International Symposium on INnovations in Intelligent SysTems and Applications, INISTA 2011. Conference Address: Istanbul-Kadikoy, Turkey. Time:June 15, 2011 - June 18, 2011.TUBITAK; IEEEInteractive Dynamic Influence Diagrams(I-DIDs) constitute a graphic model for multi-agent decision making under uncertainty, but solving them is provably intractable. Algorithms for solving I-DIDs face the challenge of an exponentially growing space of candidate models ascribed to other agents, over time. Pruning behaviorally equivalent models is one way toward minimizing the model set, but composing behavioral equivalence classes is a complex process as we need to compare all solutions of possible models of other agents in the merge operation. To further simplify the calculation, this paper describes an approximate solution of I-DIDs based on double compression method. First of time, using the insight that beliefs that are spatially close are likely to be behaviorally equivalent, cluster the models of other agents and select representative models from each cluster, and then, update those modes using the principle of discriminative behavior updates. We discuss the complexity of the approximation technique and demonstrate its empirical performance. ? 2011 IEEE