Differences
This shows you the differences between two versions of the page.
Next revision | Previous revision | ||
models-and-methods:overview [2014/05/06 05:01] stefan created |
models-and-methods:overview [2014/05/06 10:00] stefan |
||
---|---|---|---|
Line 44: | Line 44: | ||
Through the evolution of a tutorial at AAMAS, a couple of nice graphics have emerged that illustrates the differences in complexity of a few of the problem classes. The first places the Dec-POMDP, Dec-MMDP, and MMDP in the context of the overarching Partially-Observable Stochastic Game (POSG), as well as the single-agent MDP and POMDP models. | Through the evolution of a tutorial at AAMAS, a couple of nice graphics have emerged that illustrates the differences in complexity of a few of the problem classes. The first places the Dec-POMDP, Dec-MMDP, and MMDP in the context of the overarching Partially-Observable Stochastic Game (POSG), as well as the single-agent MDP and POMDP models. | ||
- | {{ :models-and-methods:msdm-classes.png?nolink&600 |}} | + | {{http://gaips.inesc-id.pt/switwicki/msdm-2014/msdm-classes.png&.png}} |
The second explores subclasses of the Dec-MDP model, some of which have significantly lower complexity. | The second explores subclasses of the Dec-MDP model, some of which have significantly lower complexity. | ||
- | {{ :models-and-methods:complexity-of-subclasses.jpg?nolink&600 |}} | + | {{http://gaips.inesc-id.pt/switwicki/msdm-2014/complexity-of-subclasses.jpg&.png}} |
These illustration were inspired by publications such as the following, which provide detailed complexity analyses: | These illustration were inspired by publications such as the following, which provide detailed complexity analyses: | ||
- | [[http://rbr.cs.umass.edu/papers/BGIZmor02.html|The Complexity of Decentralized Control of Markov Decision Processes]]. Daniel S. Bernstein, Robert Givan, Neil Immerman, and Shlomo Zilberstein. Mathematics of Operations Research, 27(4):819-840, 2002. | + | [[http://rbr.cs.umass.edu/papers/BGIZmor02.html|The Complexity of Decentralized Control of Markov Decision Processes]]. |
- | + | Daniel S. Bernstein, Robert Givan, Neil Immerman, and Shlomo Zilberstein. Mathematics of Operations Research, 27(4):819-840, 2002. | |
- | [[http://rbr.cs.umass.edu/papers/GZjair04.html|Decentralized Control of Cooperative Systems: Categorization and Complexity Analysis]]. Claudia V. Goldman and Shlomo Zilberstein. Journal of Artificial Intelligence Research, 22:143-174, 2004. | + | |
- | [[http://mas.cs.umass.edu/pub/paper_detail.php/405|Agent Interaction in Distributed MDPs and its Implications on Complexity]]. Jiaying Shen, Raphen Becker, and Victor Lesser. Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multi-Agent Systems, ACM, pp. 529-536. 2006. | + | [[http://rbr.cs.umass.edu/papers/GZjair04.html|Decentralized Control of Cooperative Systems: Categorization and Complexity Analysis]]. |
+ | Claudia V. Goldman and Shlomo Zilberstein. Journal of Artificial Intelligence Research, 22:143-174, 2004. | ||
+ | [[http://mas.cs.umass.edu/pub/paper_detail.php/405|Agent Interaction in Distributed MDPs and its Implications on Complexity]]. | ||
+ | Jiaying Shen, Raphen Becker, and Victor Lesser. Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multi-Agent Systems, ACM, pp. 529-536. 2006. | ||
[[http://anytime.cs.umass.edu/papers/AZnips09.html|Complexity of Decentralized Control: Special Cases]]. | [[http://anytime.cs.umass.edu/papers/AZnips09.html|Complexity of Decentralized Control: Special Cases]]. | ||
- | Martin Allen and Shlomo Zilberstein. Proceedings of the Twenty-Third Neural Information Processing Systems Conference (NIPS), 19-27, Vancouver, British Columbia, Canada, 2009. | + | Martin Allen and Shlomo Zilberstein. Proceedings of the Twenty-Third Neural Information Processing Systems Conference (NIPS), 19-27, Vancouver, British Columbia, Canada, 2009. |
A more recent study attempts to characterize various classes of problems based on the problem structure they exploit: | A more recent study attempts to characterize various classes of problems based on the problem structure they exploit: | ||
- | [[http://gaips.inesc-id.pt/~switwicki/bib/AAMAS2011.htm|Towards a Unifying Characterization for Quantifying Weak Coupling in Dec-POMDPs]]. Stefan J. Witwicki and Edmund H. Durfee. In Proceedings of the Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2011), pages 29-36. Taipei, Taiwan. May 2011. | + | [[http://gaips.inesc-id.pt/~switwicki/bib/AAMAS2011.htm|Towards a Unifying Characterization for Quantifying Weak Coupling in Dec-POMDPs]]. |
+ | Stefan J. Witwicki and Edmund H. Durfee. In Proceedings of the Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2011), pages 29-36. Taipei, Taiwan. May 2011. | ||
===== Additional Links ===== | ===== Additional Links ===== | ||
- | [[http://rbr.cs.umass.edu/shlomo/papers/SZjaamas08.html|Formal Models and Algorithms for Decentralized Decision Making under Uncertainty]]. Sven Seuken and Shlomo Zilberstein. Autonomous Agents and Multi-Agent Systems, 17(2):190-250, 2008. | + | [[http://rbr.cs.umass.edu/shlomo/papers/SZjaamas08.html|Formal Models and Algorithms for Decentralized Decision Making under Uncertainty]]. |
+ | Sven Seuken and Shlomo Zilberstein. Autonomous Agents and Multi-Agent Systems, 17(2):190-250, 2008. | ||
[[http://teamcore.usc.edu/projects/dpomdp/|Teamcore's Distributed POMDP page]] | [[http://teamcore.usc.edu/projects/dpomdp/|Teamcore's Distributed POMDP page]] | ||
[[http://rbr.cs.umass.edu/camato/decpomdp/|Chris Amato's Dec-POMDP page]] | [[http://rbr.cs.umass.edu/camato/decpomdp/|Chris Amato's Dec-POMDP page]] |