An improved algorithm for interactive dynamic influence diagrams
Bo Li, Jian Luo, Huayi Yin, Le Tian · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · 2011
Interactive Dynamic Influence Diagrams(I-DIDs), as graphic models based on probabilistic graphical theory, are proposed to represent, the sequential decision-making problem over multiple time steps in the presence of other interacting agents. The algorithms for solving I-DIDs are haunted by the challenge of an exponentially growing space of candidate models ascribed to other agents over time. In this paper, in order to reduce the candidate model space according the behaviorally equivalent theory, a more efficient way to construct Epsilon behavior equivalence classes is discussed that using belief-behavior graph (BBG). A method of solving I-DIDs approximately is presented, which avoids solving all candidate models by clustering models with beliefs that are spatially close and selecting a representative one from each cluster. The simulation results show the validity of the improved algorithm.