Agent Influence as a Predictor of Difficulty for Decentralized Problem-Solving

Martin Allen and Shlomo Zilberstein. Agent Influence as a Predictor of Difficulty for Decentralized Problem-Solving. Proceedings of the Twenty-Second Conference on Artificial Intelligence (AAAI), 688-693, Vancouver, British Columbia, 2007.

Abstract

We study the effect of problem structure on the practical performance of optimal dynamic programming for decentralized decision problems. It is shown that restricting agent influence over problem dynamics can make the problem easier to solve. Experimental results establish that agent influence correlates with problem difficulty: as the gap between the influence of different agents grows, problems tend to become much easier to solve. The measure thus provides a general-purpose, automatic characterization of decentralized problems, identifying those for which optimal methods are more or less likely to work. Such a measure is also of possible use as a heuristic in the design of algorithms that create task decompositions and control hierarchies in order to simplify multiagent problems.

Bibtex entry:

@inproceedings{AZaaai07,
  author	= {Martin Allen and Shlomo Zilberstein},
  title		= {Agent Influence as a Predictor of Difficulty for Decentralized
                   Problem-Solving},
  booktitle     = {Proceedings of the Twenty-Second Conference on
                   Artificial Intelligence},
  year		= {2007},
  pages		= {688-693},
  address       = {Vancouver, British Columbia},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/AZaaai07.html}
}

shlomo@cs.umass.edu