New Algorithms for Collaborative and Adversarial Decision Making in Partially Observable Stochastic Games

摘要

The project has produced new computational models and algorithms for coordination, prediction and planning in situations involving multiple decision makers that operate over an extended period of time in either collaborative or adversarial domains. This includes the development of the decentralized partially-observable Markov decision process (DEC-POMDP) model, memory-bounded algorithm for solving finite-horizon DEC-POMDPs, sparse representations of agent strategies using finite-state controllers, bounded policy iteration algorithms for infinite-horizon DEC-POMDPs, and algorithms for solving DEC- POMDPs using non-linear optimization methods. The project produced the best existing exact algorithms for these problems as well as scalable approximation techniques and benchmark problems that are now widely used within the multi- agent systems community. The report describes these research accomplishments and provides references to published papers and PhD dissertations that include detailed descriptions of the results.