Trial-Based Dynamic Programming for Multi-Agent Planning

, ,

Trial-based approaches offer an efficient way to solve singleagent 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.

» Read on
 address = {Atlanta, United States},
 author = {Feng Wu and Shlomo Zilberstein and Xiaoping Chen},
 booktitle = {Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI)},
 pages = {908-914},
 title = {Trial-Based Dynamic Programming for Multi-Agent Planning},
 year = {2010}