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.
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)
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.
