Online Planning for Multi-Agent Systems with Bounded Communication

Feng Wu, Shlomo Zilberstein, and Xiaoping Chen. Online Planning for Multi-Agent Systems with Bounded Communication. Artificial Intelligence, 175(2):487-511, 2011.

Abstract

We propose an online algorithm for planning under uncertainty in multi-agent settings modeled as DEC-POMDPs. The algorithm helps overcome the high computational complexity of solving such problems offline. The key challenges in decentralized operation are to maintain coordinated behavior with little or no communication and, when communication is allowed, to optimize value with minimal communication. The algorithm addresses these challenges by generating identical conditional plans based on common knowledge and communicating only when history inconsistency is detected, allowing communication to be postponed when necessary. To be suitable for online operation, the algorithm computes good local policies using a new and fast local search method implemented using linear programming. Moreover, it bounds the amount of memory used at each step and can be applied to problems with arbitrary horizons. The experimental results confirm that the algorithm can solve problems that are too large for the best existing offline planning algorithms and it outperforms the best online method, producing much higher value with much less communication in most cases. The algorithm also proves to be effective when the communication channel is imperfect (periodically unavailable). These results contribute to the scalability of decision-theoretic planning in multi-agent settings.

Bibtex entry:

@article{WZCaij11,
  author	= {Feng Wu and Shlomo Zilberstein and Xiaoping Chen},
  title		= {Online Planning for Multi-Agent Systems with Bounded Communication},
  journal	= {Artificial Intelligence},
  volume	= {175},
  number	= {2},
  year		= {2011},
  pages		= {487-511},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/WZCaij11.html}
}

shlomo@cs.umass.edu