RI: Small: Planning Algorithms for Large Decentralized Multiagent Settings

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

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.