A Successive Approximation Algorithm for Coordination Problems

Marek Petrik and Shlomo Zilberstein. A Successive Approximation Algorithm for Coordination Problems. Proceedings of the Tenth International Symposium on Artificial Intelligence and Mathematics, (ISAIM), Ft. Lauderdale, Florida, 2008.

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 an online error bound 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.

Bibtex entry:

@inproceedings{PZisaim08,
  author	= {Marek Petrik and Shlomo Zilberstein},
  title		= {A Successive Approximation Algorithm for Coordination Problems},
  booktitle     = {Proceedings of the Tenth International Symposium on Artificial 
                   Intelligence and Mathematics},
  year		= {2008},
  pages		= {},
  address       = {Ft. Lauderdale, Florida},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/PZisaim08.html}
}

shlomo@cs.umass.edu