University of Southern California
Research Group

Planning and Coordination for Multiagent Teams: Distributed (PO)MDPs and DCOPs

 

Current Team:

Milind Tambe

Manish Jain

Jun-young Kwak

Onur Sert

Jagrut Sharma

 

Alumni:

Matthew E. Taylor

Prateek Tandon

 

Motivation

In planning and coordination for multiagent teams that includes humans, robots and software agents, we focus on realizing the promise of Distributed (Partially Observable) Markov Decision Problems (Distributed (PO)MDPs) and Distributed Constraint Optimization Problems (DCOPs). Our initial work on coordinating iRobot CREATEs used DCOPs, and we keep pushing towards several real-world domain problems based on distributed (PO)MDPs using robots and handheld devices.

 

Distributed (PO)MDPs

In realistic domains, uncertainty in terms of an agent's actions and observations is fundamental. A Markov Decision Problem (MDP) and a Partially Observable Markov Decision Problem (POMDP) offer an expressive and powerful computational mechanism for generating the optimal policy that maximizes an agent's total expected reward in such stochastic domains. More recently, the problem of deriving joint policies for a group of agents that maximize joint reward function has been modeled as distributed (PO)MDPs (DEC-(PO)MDPs) which provide a highly expressive framework for modeling multiagent collaboration problems. However, given the NEXP-Complete complexity of DEC-(PO)MDPs, the emerging consensus is to pursue approximate solutions or sacrifice expressiveness by identifying useful subclasses of DEC-(PO)MDPs. Such approaches aim to find approximate joint policies and/or exploit the structure of a subclass, and are able to significantly improve the performance.

We are currently working on building multiagent systems in energy domains and collaborating with researchers from different departments including Computer Science, Civil and Environmental Engineering and Architecture departments at USC. We are also collaborating with researchers at the Monterey Bay Aquarium Research Institute (MBARI) to work towards distributed POMDPs aimed at coordinating AUVs (Autonomous Underwater Vehicles) in the future. Specifically, we are currently collaborating with the Autonomy projects.

Links:

Publications:

  • Two Decades of Multiagent Teamwork Research: Past, Present, and Future
    (Matthew E. Taylor, Manish Jain, Christopher Kiekintveld, Jun-young Kwak, Rong Yang, Zhengyu Yin, and Milind Tambe).
    Book Chapter published at CARE workshop, 2010 (to appear)

  • Teamwork and Coordination under Model Uncertainty in DEC-POMDPs
    (Jun-young Kwak, Rong Yang, Zhengyu Yin, Matthew E. Taylor, and Milind Tambe). Published at AAAI 2010 Workshop on Interactive Decision Theory and Game Theory (IDTGT)

  • Exploiting Coordination Locales in Distributed POMDPs via Social Model Shaping
    (Pradeep Varakantham, Jun-young Kwak, Matthew E. Taylor, Janusz Marecki, Paul Scerri, and Milind Tambe). Published at International conference on automated planning and scheduling, 2009

 

DCOPs

Buoyed by recent successes in the area of Distributed Constraint Optimization Problems (DCOPs), this paper addresses challenges faced when applying DCOPs to real-world domains. Three fundamental challenges must be addressed for a class of real-world domains, requiring novel DCOP algorithms. First, agents may not know the payoff matrix and must explore the environment to determine rewards associated with variable settings. Second, agents may need to maximize total accumulated reward rather than instantaneous final reward. Third, limited time horizons disallow exhaustive exploration of the environment. We propose and implement a set of novel algorithms that combine decision-theoretic exploration approaches with DCOP-mandated coordination. In addition to simulation results, we implement these algorithms on robots, deploying DCOPs on a distributed mobile sensor network.

   

Links:

Publications: