ABSTRACT
Interactive dynamic influence diagrams (I-DIDs) are graphical models for sequential decision making in uncertain settings shared by other agents. Algorithms for solving I-DIDs face the challenge of an exponentially growing space of candidate models ascribed to other agents, over time. We formalize the concept of a minimal model set, which facilitates qualitative comparisons between different approximation techniques. We then present a new approximation technique that minimizes the space of candidate models by discriminating between model updates. We empirically demonstrate that our approach improves significantly in performance on the previous clustering based approximation technique.
- P. Doshi, Y. Zeng, and Q. Chen. Graphical models for interactive pomdps: representations and solutions. JAAMAS, DOI:10.1007/s10458-008-9064-7, 2008. Google ScholarCross Ref
- Y. Gal and A. Pfeffer. A language for modeling agent's decision-making processes in games. In AAMAS, pages 265--272, 2003. Google ScholarDigital Library
- P. Gmytrasiewicz and P. Doshi. A framework for sequential planning in multiagent settings. JAIR, 24:49--79, 2005. Google ScholarCross Ref
- D. Koller and B. Milch. Multi-agent IDs for representing and solving games. In IJCAI, pages 1027--1034, 2001. Google ScholarDigital Library
- J. Pineau, G. Gordon, and S. Thrun. Anytime point-based value iteration for large pomdps. JAIR, 27:335--380, 2006. Google ScholarDigital Library
- D. Pynadath and S. Marsella. Minimal mental models. In AAAI, pages 1038--1044, 2007. Google ScholarDigital Library
- B. Rathnas., P. Doshi, and P. J. Gmytrasiewicz. Exact solutions to interactive pomdps using behavioral equivalence. In AAMAS, pages 1025--1032, 2006. Google ScholarDigital Library
- S. Seuken and S. Zilberstein. Improved memory bounded dynamic programming for decentralized pomdps. In UAI, pages 2009--2015, 2007. Google ScholarDigital Library
- R. Smallwood and E. Sondik. The optimal control of partially observable markov decision processes over a finite horizon. OR, 21:1071--1088, 1973.Google ScholarDigital Library
- D. Suryadi and P. Gmytrasiewicz. Learning models of other agents using IDs. In UM, pages 223--232, 1999. Google ScholarDigital Library
- J. A. Tatman and R. D. Shachter. Dynamic programming and influence diagrams. IEEE Trans. SMC, 20(2):365--379, 1990.Google ScholarCross Ref
Index Terms
- Improved approximation of interactive dynamic influence diagrams using discriminative model updates
Recommendations
Learning Communication in Interactive Dynamic Influence Diagrams
WI-IAT '12: Proceedings of the The 2012 IEEE/WIC/ACM International Joint Conferences on Web Intelligence and Intelligent Agent Technology - Volume 02Communication is one of central activities in multiagent systems. It enables the knowledge sharing among multiple agents and improves the planning quality in a long run. In this paper, we study communication decision problems in the framework of ...
Efficient solutions of interactive dynamic influence diagrams using model identification
Interactive dynamic influence diagram (I-DID) is one of the graphical frameworks for sequential decision making in partially observable environment. Subject agent in I-DID maintains beliefs over not only physical states of the environment, but also over ...
Exploiting model equivalences for solving interactive dynamic influence diagrams
We focus on the problem of sequential decision making in partially observable environments shared with other agents of uncertain types having similar or conflicting objectives. This problem has been previously formalized by multiple frameworks one of ...
Comments