Anytime Coordination Using Separable Bilinear Programs
Marek Petrik
Shlomo Zilberstein
Abstract
Developing scalable coordination algorithms for multi-agent
systems is a hard computational challenge. One useful approach,
demonstrated by the Coverage Set Algorithm (CSA),
exploits structured interaction to produce significant computational
gains. Empirically, CSA exhibits very good anytime
performance, but an error bound on the results has not been
established. We reformulate the algorithm and derive both
online and offline error bounds for approximate solutions.
Moreover, we propose an effective way to automatically reduce
the complexity of the interaction. Our experiments show
that this is a promising approach to solve a broad class of
decentralized decision problems. The general formulation used
by the algorithm makes it both easy to implement and widely
applicable to a variety of other AI problems.
Download
[pdf]