Towards a Unifying Characterization for Quantifying Weak Coupling in Dec-POMDPs.


Publication Info

Stefan J. Witwicki and Edmund H. Durfee. In Proceedings of the Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2011). Taipei, Taiwan. May 2011. To appear.


Abstract

Researchers in the field of multiagent sequential decision making have commonly used the terms “weakly-coupled” and “loosely-coupled” to qualitatively classify problems involving agents whose interactions are limited, and to identify various structural restrictions that yield computational advantages to decomposing agents’ centralized planning and reasoning into largely-decentralized planning and reasoning. Together, these restrictions make up a heterogeneous collection of facets of “weakly-coupled” structure that are conceptually related, but whose purported computational benefits are hard to compare evenhandedly. The contribution of this paper is a unified characterization of weak coupling that brings together three complementary aspects of agent interaction structure. By considering these aspects in combination, we derive new bounds on the computational complexity of optimal Dec- POMDP planning, that together quantify the relative ben- efits of exploiting different forms of interaction structure. Further, we demonstrate how our characterizations can be used to explain why existing classes of decoupled solution algorithms perform well on some problems but poorly on others, as well as to predict the performance of a particular algorithm from identifiable problem attributes.


Bibtex

@inproceedings{Witwicki:AAMAS2011,
    author = {Stefan J. Witwicki and Edmund H. Durfee},
    title = {Towards a Unifying Characterization for Quantifying Weak Coupling 
            in {Dec-POMDPs}.},
    booktitle = {Proceedings of the Tenth International Conference on Autonomous 
		Agents and Multiagent Systems (AAMAS-2011)},
    month = {May},
    year = {2011},
    pages = {},
    address = {Taipei, Taiwan},
    note = {To appear.}
}