NeurIPS 2020 | 学习多智能体分层协作，优化有向传感器网络目标覆盖
关键词：多智能体协作，有向传感器网络
导 读
本文是第三十四届神经信息处理大会（NeurIPS 2020）入选论文《Learning Multi-Agent Coordination for Enhancing Target Coverage in Directional Sensor Networks》的解读。
论文链接：https://arxiv.org/abs/2010.13110
项目主页：https://sites.google.com/view/hit-mac
代码链接：https://github.com/XuJing1022/HiT-MAC
（点击文末“阅读原文”跳转论文链接）
01
背景和动机
有向传感器网络（Directional Sensor Networks, DSNs）是指由多个只能感知特定方向物理状态的有向传感器构成的传感器网络。常见的有向传感器有摄像机，雷达，红外传感器等。在很多现实应用中，网络中的传感器往往需要动态调整其自身的感知方向以实时动态捕捉移动目标状态，如自动录制体育比赛视频，主动目标追踪等。
图1. 常见的有向传感器及真实应用场景
目标覆盖问题（target coverage problem）是有向传感器网络中的关键问题之一，即如何控制有限数量的传感器覆盖尽可能多的移动目标。但由于传感器位置固定且感知范围有限，同时目标物体通常随机移动，所以这个问题的解决仍十分具有挑战性。为此，我们将该问题形式化成一个多智能体协作问题，认为各传感器可以通过协作的调整各自感知方向，以达到全局最优的目标覆盖效果。这样的多智能体系统应具备以下能力：1）通过多智能体合作/协作完成全局任务；2）具有良好的泛化能力（对不同传感器数量、分布、目标数量等）；3）低功耗。
图2：有向传感器网络目标覆盖问题示例
然而，目前已有的方法解决目标覆盖问题表现并不理想。最简单的方法是用一个中心控制器根据全局观测信息同步控制多个传感器，但这种方法在真实场景下并不可行。一方面，是因为该系统高度依赖于传感器与中心控制器间的实时通信。另一方面，很难将系统进一步扩展到大规模网络，因为中心服务器的计算开销会随着传感器数量的增加而爆炸式增加。
当前流行的多智能体强化学习方法则主要专注于构建完全分布式系统用于多智能体合作。在分布式系统中，每个智能体单独运行，它们自己观察环境并可通过点对点通信交换信息，实现多智能体合作。这样的分布式系统可以灵活构建大规模多智能体系统，并且具有极低的通信成本。但是在大多数情况下，分布式策略不稳定且难以学习，因为它们通常会互相影响，导致环境动态过程不稳定。虽然这个问题通过最近流行的“集中式训练和分布式执行”方法得到缓解，但如何有效地训练集中式的批评家至今仍是一个挑战。
为此，我们希望结合上述两种方法的优点，探索一种切实可行的解决方案，以构建适用于有向传感器网络目标覆盖问题的多智能体系统。
图3: 集中式控制方法(左)和分布式多智能体控制方法(右)示意图
02
具体方法
本文中，我们提出了一种面向目标的多智能体分层协作框架（Hierarchical Target-oriented Multi-agent Coordination，HiT-MAC）。该框架主要分两层，包括了一个集中式的协调者（coordinater）和多个分布式的执行者（executor）。
当运行时，首先执行步骤 A：协调者收集各个执行者的观测信息，进行全局规划，为每个执行者分配特定的任务目标（即指定需要跟踪的具体目标）；然后执行步骤 B：每个执行者通过采取一系列基本动作（即左转/右转/保持不变）来完成指定任务，即在 k 个时间步内转动传感器方向使之尽可能完美覆盖指定目标。然后重复步骤 A 和 B。这样，DSNs 的目标覆盖问题将分解为不同时间尺度的两个子任务，即目标分配和目标跟踪。此时，协调者和执行者均可以直接采用当前流行的单智能体强化学习方法（如A3C，PPO等）进行训练，以使得各自的累计奖赏函数最大化。
具体来说，协调者的团队奖赏取决于覆盖率；执行者的目标条件奖赏是关于传感器跟踪选定目标的性能，即传感器和被分配的目标之间的相对角度偏差。
图4：面向目标的多智能体分层协作框架示意图
为了实现可扩展的（scalable）HiT-MAC，我们仍需要克服两个挑战：1）对于协调者，需要能够灵活处理可变数量的传感器和目标之间分配；2）对于执行者，需要能够在给定任何目标组合时，都能表现良好。
为此，我们采取了一系列方法来应对这些挑战。
采用了自注意力模块来处理变长的输入并获得一个与输入顺序无关的状态表示。
为了更好的估计全局价值，我们对每一对传感器-目标分配的边际贡献（marginal contribution）进行了近似估计（approximate marginal contribution, AMC），从而更精确地估计和分解全局价值，引导协调者学习更有效的分配策略。
对于执行者，提出了基于目标条件的过滤器以去除与被分配目标无关的观测信息，从而提高执行者策略的鲁棒性。
考虑到训练的稳定性，整体训练策略采用了二阶段分步训练方式进行。对目标集进行采样，生成伪目标来训练执行者策略；然后利用现有的执行者策略来训练协调策略。从而避免共同训练时，协调者和执行者因探索时不可避免的随机性导致训练不稳定。
图5：协作者和执行者模型示意图及一系列实用方法
关于 AMC，我们通过神经网络近似估计每个传感器-目标分配相对于整体分配的边际贡献，以有效地学习协调策略。具体算法流程如下：
其它模块具体的实现和训练细节请参见原文。
03
实验验证
为验证以上方法的有效性，我们构建了一个二维仿真模拟器用于实验验证。我们与最新的多智能体强化学习方法（SQDDPG, MADDPG, COMA）和传统最优化方法（Integer Linear Programming, ILP）进行了对比。相比基准方法，我们的方法在4个传感器和5个目标的情况下，达到了最高覆盖率和最快的收敛速度。同时，我们还进行了消融研究，以分析每个关键部件的作用。
图6：对比训练过程中不同模型的平均累计奖赏曲线
左：将HiT-MAC与基准方法对比，右：将HiT-MAC与不同消融方法对比
具体实例如下：
此外， 我们还验证了 HiT-MAC 在不同数量的传感器（2~6）和目标（3~7）下的泛化能力。在具有不同数量的传感器（2~6）和目标（3~7）的环境下，测试特定环境下（含有4个传感器和5个目标）训练的模型性能。下图报告了不同数量设置下的平均覆盖率，可以看到我们方法面对传感器/相机数量变化时,性能的变化趋势与传统最优化方法（ILP）基本一致，而没有发生剧烈波动。
具体示例如下：
03
总结
在这项工作中，我们提出了面向目标的多智能体分层协作框架（HiT-MAC），以优化有向传感器网络的目标覆盖率。在 HiT-MAC 中，我们将目标覆盖问题分解成两个子任务：指定目标分配给每个传感器和控制传感器跟踪被分配的目标。具体实现中，我们采用了一系列实用的方法，如面向目标分配的边际贡献近似、基于注意力机制的状态编码器等。实验结果表明，我们的方法可以在具有挑战性的场景中稳定表现且明显优于当前最先进的多智能体强化学习方法。
NeurIPS
神经信息处理系统大会（Conference on Neural Information Processing Systems, NeurIPS）是人工智能和机器学习领域的国际顶级会议，自1987年开始，每年的12月份，来自世界各地的从事人工智能和机器学习相关的专家学者和从业人士汇聚一堂。NeurIPS 2020于12月6日-12日在线举行。
图文 | 钟方威、许婧
Computer Vision and Digital Arts (CVDA)
About CVDA
The Computer Vision and Digital Art (CVDA) research group was founded in 2007 within the Institute of Digital Media at Peking University led be Prof. Yizhou Wang. The group focuses on developing computational theories and models to solve challenging computer vision problems in light of biologically plausible evidences of visual perception and cognition. The primary goal of CVDA is to establish a mathematical foundation of understanding the computational aspect of the robust and efficient mechanisms of human visual perception, cognition, learning and even more. We also believe that the marriage of science and art will stimulate exciting inspirations on producing creative expressions of visual patterns.
CVDA近期科研动态
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点击“阅读原文”跳转论文