RI: Small: Planning Algorithms for Large Decentralized Multiagent Settings

该项目旨在为涉及数十或数百个智能体的多智能体系统开发有效的决策理论规划算法。当前提供严格性能保证的代理协调方法只能处理少数代理。该项目通过以下目标解决了这一障碍：(1)开发新的问题表示，允许规划算法利用域内的交互结构和独立关系；(2)开发在有限内存和时间下运行的近似方法，并表现出随时随地的特征；(3)进行严格的收敛分析，建立严密的解质量误差界；(4)开发便于利用多核处理器提供的并行化的技术；(5)创建一组新的具有挑战性的测试问题，并进行严格的评估。该项目产生了两种全新的多智能体环境规划方法。第一种方法提供了基于期望最大化（EM）和凹凸过程（CCCP）等计算范式的高效消息传递规划算法。第二种方法为太大而无法显式表示的域提供了rollout采样方法。这些新方法将现有技术的可扩展性提高了几个数量级。研究结果改变了研究人员和实践者将严格的决策理论规划应用于多智能体领域（如传感器网络和移动机器人协调）的能力。更广泛的影响源于所产生的技术的广泛适用性，马萨诸塞大学的本科生和研究生教育活动，使实验领域和算法公开可用的传播努力，以及国际合作的发展。

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.