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.