This project is aimed at developing effective decision-theoretic planning algorithms for multi-agent systems that involve dozens or hundreds of agents. Current approaches to agent coordination that provide rigorous performance guarantees can only handle a few agents. The project addresses this barrier with the following objectives: (1) develop new problem representations that allow planning algorithms to leverage the interaction structure and independence relationships within a domain; (2) develop approximation methods that operate with limited memory and time, and exhibit anytime characteristics; (3) perform rigorous convergence analysis and establish tight error bounds on solution quality; (4) develop techniques that make it easy to exploit parallelization offered by multi-core processors; and (5) create a new set of challenging test problems and perform a rigorous evaluation. The project produces two fundamentally new approaches to planning in multi-agent settings. The first approach offers efficient message-passing planning algorithms based on computational paradigms such as expectation-maximization (EM) and the concave-convex procedure (CCCP). The second approach offers rollout sampling methods for domains that are too large to be explicitly represented. These new methods improve the scalability of existing techniques by several orders of magnitude. The results transform the ability of researchers and practitioners to apply rigorous decision-theoretic planning to multi-agent domains such as sensor networks and mobile robot coordination. The broader impact stems from the wide applicability of the resulting technology, undergraduate and graduate educational activities at UMass, dissemination efforts that make the experimental domain and algorithms publically available, and the development of international collaborations.
