Agent influence as a predictor of difficulty for decentralized problem-solving
M. Allen
S. Zilberstein
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.
@InProceedings{Allen07,
author = {Martin Allen and Shlomo Zilberstein},
title = {Agent Influence as a Predictor of Difficulty for Decentralized Problem-Solving},
booktitle = {Proceedings of the Twenty-Second National Conference on Artificial Intelligence ({AAAI}-07)},
pages = {688--693},
year = 2007,
address = {Vancouver, Canada}
}