Decentralized Monitoring of Distributed Anytime Algorithms

Alan Carlin and Shlomo Zilberstein. Decentralized Monitoring of Distributed Anytime Algorithms. Proceedings of the Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 157-164, Taipei, Taiwan, 2011.

Abstract

Anytime algorithms allow a system to trade solution quality for computation time. In previous work, monitoring techniques have been developed to allow agents to stop the computation at the "right" time so as to optimize a given time-dependent utility function. However, these results apply only to the single-agent case. In this paper we analyze the problems that arise when several agents solve components of a larger problem, each using an anytime algorithm. Monitoring in this case is more challenging as each agent is uncertain about the progress made so far by the others. We develop a formal framework for decentralized monitoring, establish the complexity of several interesting variants of the problem, and propose solution techniques for each one. Finally, we show that the framework can be applied to decentralized flow and planning problems.

Bibtex entry:

@inproceedings{CZaamas11,
  author	= {Alan Carlin and Shlomo Zilberstein},
  title		= {Decentralized Monitoring of Distributed Anytime Algorithms},
  booktitle     = {Proceedings of the Tenth International Conference on Autonomous
                   Agents and Multiagent Systems},
  year		= {2011},
  pages		= {157-164},
  address       = {Taipei, Taiwan},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/CZaamas11.html}
}

shlomo@cs.umass.edu