Exploiting Coordination Locales in Distributed POMDPs via Social Model Shaping

By Pradeep Varakantham, J. Kwak, Matthew E. Taylor, Janusz Marecki, Paul Scerri, Milind Tambe. 2009

76 citations recorded by the source corpus.

Distributed POMDPs provide an expressive framework for modeling multiagent collaboration problems, but NEXP-Complete complexity hinders their scalability and application in real-world domains. This paper introduces a subclass of distributed POMDPs, and TREMOR, an algorithm to solve such distributed POMDPs. The primary novelty of TREMOR is that agents plan individually with a single agent POMDP solver and use social model shaping to implicitly coordinate with other agents. Experiments demonstrate that TREMOR can provide solutions orders of magnitude faster than existing algorithms while achieving comparable, or even superior, solution quality.

Subfields: Artificial Intelligence, Automotive Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Automotive Engineering

Citations in the corpus

Multi-agent Reinforcement Learning in Sequential Social Dilemmas (2017, background): “Researchers have also studied the emergence of multi-agent coordination in the decentralized, partially observable MDP framework [36, 37, 38].”
QueryPOMDP: POMDP-Based Communication in Multiagent Systems (2011, methodology): “Further examples of models with sparse interactions include interaction-driven Markov games (IDMGs) [5, 17], distributed POMDPs with coordination locales [7], transition-decoupled POMDPs [6], factored Dec-POMDPs [4], and models relying on event-driven interactions [3,27].”
Decentralized POMDPs (2012, background): “Finally, there has been a body of work on networked distributed POMDPs (ND-POMDPs) (Nair et al, 2005; Kim et al, 2006; Varakantham et al, 2007; Marecki et al, 2008; Kumar and Zilberstein, 2009; Varakantham et al, 2009).”
Exploiting Agent and Type Independence in Collaborative Graphical Bayesian Games (2011, methodology): “008a).18 Even when making much stricter assumptions such as transition and observation independence,previous approacheshave not scaled beyond15 agents (Varakantham et al., 2007; Marecki et al., 2008; Varakantham et al., 2009; Kumar and Zilberstein, 2009). Though these experiments evaluate only the c”
Decentralized MDPs with sparse interactions (2011, background): “1 A related model has recently been proposed under the designation of distributed POMDPs with coordination locales [13].”
A multi-agent reinforcement learning model of common-pool resource appropriation (2017, background): “Others study the emergence of cooperation in partially observable Markov decision processes [9, 37, 38] but rely on knowledge of the model which is unrealistic when studying independent interaction.”
A Concise Introduction to Decentralized POMDPs (2016, methodology): “…et al., 2008c], and many oth- 2.4 Special Cases, Generalizations and Related Models 23 ers [Becker et al., 2004a, 2005, Shen et al., 2006, Spaan and Melo, 2008, Varakantham et al., 2009, Mostafa and Lesser, 2009, Witwicki and Durfee, 2009, 2010b, Mostafa and Lesser, 2011a,b, Witwicki et al., 2012].”