摘要

本文提出了一种名为Attritable MCTS (A-MCTS)的新型分散式多智能体规划算法，旨在解决在智能体频繁失败的真实大规模部署场景中，现有的分散式规划方法表现不佳的问题。A-MCTS通过使用全局奖励函数来估计每个智能体的局部贡献，并利用后悔匹配（Regret Matching, RM）进行协调，能够及时且高效地适应活动智能体集合的变化。本文通过在不同的信息收集问题场景中评估其有效性，展示了A-MCTS在智能体高失败率下仍能实现高效适应的理论和实验结果。结果表明，在频繁失败的情况下，我们的解决方案在全局效用和可扩展性方面显著优于现有最佳方法。

原理

A-MCTS算法的核心在于其能够通过全局奖励函数直接优化每个智能体的局部行动，同时利用后悔匹配（RM）技术来协调智能体之间的行动。具体来说，每个智能体在规划时不仅考虑自身的行动序列，还考虑其他智能体的潜在行动，从而形成一个全局视角下的优化问题。通过RM技术，智能体能够在不完全信息和有限通信的情况下，独立计算出对整体最优的策略，确保所有智能体的行为最终收敛到一个纳什均衡（Nash Equilibrium, NE），从而实现分散式环境下的高效协调和规划。

流程

A-MCTS的工作流程包括以下几个关键步骤：

1. 初始化搜索树：每个智能体初始化自己的蒙特卡洛树搜索（MCTS）树。
2. 选择与通信：智能体从搜索树中选择一个子集的行动序列，并与团队其他成员通信更新这些信息。
3. 后悔匹配协调：使用后悔匹配算法计算出一个最佳响应的联合行动序列。
4. 搜索树扩展与回传：智能体根据最佳响应策略扩展搜索树，并通过回传机制更新树中的价值估计。
5. 执行与重新规划：智能体执行规划的行动，并根据新的信息进行重新规划。

具体示例和详细步骤可以参考论文中的算法1和图1。

应用

A-MCTS算法在多智能体系统中的信息收集任务具有广泛的应用前景，特别是在无人机群自主空中监视、灾难救援操作、机器人团队协作探索未知环境等领域。由于其能够在智能体频繁失败的情况下仍保持高效和可扩展性，A-MCTS为实现复杂任务的分散式多智能体规划提供了一种新的有效解决方案。