Trial-Based Dynamic Programming for Multi-Agent Planning

Feng Wu, Shlomo Zilberstein, and Xiaoping Chen. Trial-Based Dynamic Programming for Multi-Agent Planning. Proceedings of the Twenty-Fourth Conference on Artificial Intelligence (AAAI), 908-914, Atlanta, Georgia, 2010.

Abstract

Trial-based approaches offer an efficient way to solve single-agent MDPs and POMDPs. These approaches allow agents to focus their computations on regions of the environment they encounter during the trials, leading to significant computational savings. We present a novel trial-based dynamic programming (TBDP) algorithm for DEC-POMDPs that extends these benefits to multi-agent settings. The algorithm uses trial-based methods for both belief generation and policy evaluation. Policy improvement is implemented efficiently using linear programming and a sub-policy reuse technique that helps bound the amount of memory. The results show that TBDP can produce significant value improvements and is much faster than the best existing planning algorithms.

Bibtex entry:

@inproceedings{WZCaaai10,
  author	= {Feng Wu and Shlomo Zilberstein and Xiaoping Chen},
  title		= {Trial-Based Dynamic Programming for Multi-Agent Planning},
  booktitle     = {Proceedings of the Twenty-Fourth Conference on Artificial
                   Intelligence},
  year		= {2010},
  pages		= {908-914},
  address       = {Atlanta, Georgia},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/WZCaaai10.html}
}

shlomo@cs.umass.edu