Decentralized Markov Decision Processes with Event-Driven Interactions
Raphen Becker
Shlomo Zilberstein
Victor Lesser
Abstract
Decentralized MDPs provide a powerful formal framework
for planning in multi-agent systems, but the complexity
of the model limits its usefulness. We study in this paper
a class of DEC-MDPs that restricts the interactions between
the agents to a structured, event-driven dependency.
These dependencies can model locking a shared resource
or temporal enabling constraints, both of which arise frequently
in practice. The complexity of this class of problems
is shown to be no harder than exponential in the number
of states and doubly exponential in the number of dependencies.
Since the number of dependencies is much smaller
than the number of states for many problems, this is
significantly better than the doubly exponential (in the state space)
complexity of DEC-MDPs. We also demonstrate how an algorithm
we previously developed can be used to solve problems
in this class both optimally and approximately. Experimental
work indicates that this solution technique is significantly
faster than a naive policy search approach.
Download
[pdf]