1.2 主要研究领域

在这一部分，我们将介绍分布式人工智能四个有代表性的研究领域。

1.2.1 算法博弈论

算法博弈论是博弈论和算法设计的交叉领域。算法博弈论问题中算法的输入通常来自许多参与者，这些参与者对输出有不同的个人偏好。在这种情况下，这些智能体参与者可能因为个人利益而隐瞒真实的信息。除了经典算法设计理论要求的多项式运算时间及较高近似度，算法设计者还需要考虑智能体动机的约束。

当前算法博弈论的研究者主要关注完全信息博弈和非完全信息博弈中的纳什均衡的求解。纳什均衡指当所有人都执行其纳什均衡策略时，没有人能够通过单方面改变自己的策略增加自己的收益。在每个参与者的动作都是有限的情况下，混合策略的纳什均衡存在于任意博弈中。虽然纳什均衡在算法博弈论中应用广泛，但是其求解是非常困难的，对于二人及以上的非零和博弈，其计算难度是PPAD-complete的[19]。幸运的是，对于二人零和博弈，其纳什均衡可以在多项式时间内求解。目前研究者关注的二人有限下注和无限下注的德州扑克都属于二人零和博弈。小型的博弈可以通过求解线性规划得到，但对于大规模博弈，很难求解其线性规划表示。因而求解大规模二人零和博弈最广泛应用的算法是反事实遗憾最小化算法（CFR）[100]和Fictitious（Self）-Play[32,44]。其中，CFR被成功地用于求解二人德州扑克，并决定性地打败了人类职业选手[10]。在多人零和博弈或者非零和博弈中，研究者利用类似的方法取得了一些实验成果，但依然缺乏相应的理论支撑。多人博弈目前还是一个开放的问题。

进入深度学习时代以来，上述提到的反事实遗憾最小化算法（CFR）和Fictitious（Self）-Play也有了相应的深度学习版本，即Deep CFR[12]和Neural Fictitious Self-Play（NFSP）[31]，这类算法成功地应用于大规模的博弈问题求解，取得了很好的结果[47,93,98]。另外，基于经典的Double Oracle算法[35,54]，DeepMind的研究者提出了Policy Space Response Oracle（PSRO）算法及其拓展变体，并将一些现有算法统一起来[42,59]。基于深度学习的算法具有强大的表示能力，但是其训练相对更为耗时，所以更适用于博弈的表示学习方法是一个值得探索的方向。

1.2.2 分布式问题求解

作为分布式人工智能的一个子领域，分布式问题求解着眼于让多个智能体共同解决一个问题。这些智能体通常都是合作性的。在众多分布式问题求解模型中，分布式约束推理（Distributed Constraint-Reasoning，DCR）模型，如分布式约束满足问题（Distributed Constraint-Satisfaction Problem，DCSP）和分布式约束优化问题（Distributed Constraint-Optimization Problem，DCOP）的使用和研究较为广泛。DCR模型历史较长，在各种分布式问题上都有应用，包括无线电信道分配和分布式传感器网络（图1.2）。自20世纪90年代中期以来，DCSP和DCOP算法设计（包括完全的和非完全的）获得了学术界的广泛关注。根据搜索策略（最佳优先搜索或深度优先分支定界搜索）、智能体间同步类型（同步或异步）、智能体间通信方式（约束图邻居间点对点传播方式或广播方式）以及主要通信拓扑结构（链式或树形）的不同，可以对学术界提出的众多DCR算法进行归类。例如，ADOPT[57]采用的是最佳优先搜索、异步同步、点对点的通信和树形通信拓扑结构。近年来，研究人员在多个方面延伸了DCR模型和算法，从而更精确地建模和求解现实问题[97]。隐私保护是使用DCR建模诸如分布式会议安排这类问题的一个动机。例如当两名用户没有安排同一个会议的需求时，他们应当无权知悉对方对于会议时间的偏好。遗憾的是，隐私泄露常常难以避免。为此，研究人员引入一些指标去衡量DCR的隐私泄露程度，并设计新的DCR算法来更好地保护隐私。DCR模型也被扩展为动态DCR模型，如动态DCSP和动态DCOP。一个典型的动态DCR问题由一连串（静态的）DCR问题组成，问题与问题之间有一定的变化。其他相关的扩展还包括：智能体以截止时间决定价值的连续时间模型、智能体对所处环境认知不完全的模型。研究人员还将DCOP扩展为多目标DCOP及资源受限的DCOP。

由于其出色的表征能力，近年来深度学习被广泛应用于求解大规模约束规划、推理问题，涌现出一大批优秀算法。2018年来自南加州大学的研究者成功地将卷积神经网络（Convolutional Neural Network，CNN）应用于表征约束满足问题，并据此提出用于预测可满足性的CSP-CNN模型[92]。在布尔满足问题上，加州大学伯克利分校结合图神经网络通过强化学习得到分支启发信息（Branching Heuristics），极大地提升了现有算法的求解效率[43]。深度桶消除（Deep Bucket Elimination，DBE）算法[68]则利用深度神经网络来表示高维效用表，解决了约束推理中指数级的内存消耗问题。类似的想法也应用于求解其他DCOP问题[20]。然而，大多数基于深度学习的算法很难提供理论上的质量保障，使得其在大量关键场景下（例如船舶导航、灾难救援等）无法得到广泛应用。因此，如何更好地将深度学习和符号推理相结合，以开发具有理论保障的约束推理算法是未来亟待解决的问题。

1.2.3 多智能体规划

不确定性是多智能体系统研究面临的最大挑战之一。即便在单智能体系统中，行动的输出也会存在不确定性（如行动失败的概率）。此外，在许多问题中，环境的状态也会因噪声或传感器能力所限而带有不确定性。在多智能体系统中，这些问题更加突出。一个智能体只能通过自己的传感器来观测环境状态，因此智能体预知其他智能体动向的能力十分有限，合作也会因此变得复杂。如果这些不确定性不能得到很好的处理，各种糟糕的情况都有可能出现。理论上，智能体通过相互交流和同步它们的信号协调行动。然而，由于带宽的限制，智能体往往不可能将必要的信息广播至其他所有智能体。此外，在许多实际场景中，通信是不可靠的，这就不可避免地对其他智能体行动的感知带来了不确定性。近年来，大量的研究集中于寻求以规范的方式处理多智能体系统不确定性的方法，建立了各种模型和求解方法。分散型马尔可夫决策过程（Decentralized Markov Decision Process，Dec-MDP）和分散型部分可观测马尔可夫决策过程（Decentralized Partially Observable Markov Decision Process，Dec-POMDP）是不确定性情形下多智能体规划建模最为常用的两种模型。不幸的是，求解Dec-POMDP（即计算最佳规划）通常是很难的（NEXP-complete）[8]，即便是计算绝对误差界内的解也是NEXP-complete的问题[65]。特别地，联合策略的数量随智能体数量和观察次数呈指数级增长，随问题规模呈双重指数级增长。尽管这些复杂性预示很难找到对所有问题都行之有效的方法，开发更好的Dec-POMDP优化求解方法仍然是一项至关重要且近来广受关注的问题。

一些相关研究也试图将深度学习尤其是深度强化学习应用到多智能体规划问题中。在多智能体路径寻找（Multi-Agent Path-Finding，MAPF）[81]的研究中，研究者将传统启发式算法和深度强化学习结合起来获得了比传统方法更好的结果[69]，并提出了基于深度网络的、针对多种算法的选择算法，来综合不同算法的优势以达到最好的求解效果[38]。在更贴近真实场景的多智能体运动规划（Multi-Agent Motion Planning）中，研究者利用深度强化学习和基于力的（Force-based）规划算法来提高到达目标的准确率和减少到达目标的时间[76]。相对而言，基于深度学习的多智能体规划算法的研究还相对较少，仍未能完全发掘深度学习的潜力。

1.2.4 多智能体学习

多智能体学习（Multi-Agent Learning，MAL）将机器学习技术（特别是强化学习）引入多智能体系统领域，研究如何创建动态环境下的自适应智能体。一些单智能体的强化学习算法在智能体所处环境满足马尔可夫性质且智能体能够尝试足够多行动的前提下会收敛至最优的策略。在多个智能体相互作用的情况下，一个智能体的收益通常依赖于其他个体的行动，每个智能体都面临一个目标不断变化的环境，因此需要对原有算法框架做相应的扩展，而这些扩展通常产生大规模的状态及行动空间。如何处理复杂的现实问题，如何高效地处理大量的状态及策略空间已经成为目前多智能体学习研究的核心问题。

随着深度强化学习的兴起，上述问题的解决迎来了新的转机，多智能体强化学习（Multi-Agent Reinforcement Learning，MARL）乘势兴起。在多智能体强化学习中，每个智能体都采用强化学习对自己的策略进行训练，其中智能体的策略利用深度网络来表示。为解决在同时训练的过程中每个智能体的外部环境都不是静态的问题，以及多智能体之间的收益分配问题，“集中训练，分布式执行”的训练范式[25,50]被提出，并成为后续工作中的一个基本训练范式。该训练范式的核心思路是在执行过程中每个智能体都只能根据自己的观察做出决策，但在训练过程中对于每个决策的评价都可以通过一个使用全局信息的模块来进行，这种全局模块可以是一个Critic网络[50]、一个反事实遗憾值[25]，或者一个专门用来做收益分配的Mix网络[66,80,90]。这样的设计在基于粒子的环境[50]和基于StarCraft II的一组合作任务[72]上都取得了很好的效果。在当下的研究趋势中，研究者正在把MARL应用到更复杂和更大规模的多智能体学习任务上，诸如地面和空中交通管控、分布式监测、电子市场、机器人营救和机器人足球赛、智能电网等一系列实际应用场合。

1.2.5 分布式机器学习

随着“大数据”时代的来临，各大平台每天产生的数据高达PB（1PB=1024TB）的量级。这样量级的数据在单机上的存储和应用都极度困难，因而将数据部署到多台、多类型的机器上进行并行计算是非常必要的，分布式机器学习因此兴起。分布式机器学习的目标是将具有庞大数据和计算量的任务分布式地部署到多台机器上，以提高数据计算的速度和可扩展性，减少任务耗时。随着数据量和计算量的不断攀升，以及对于数据处理的速度和计算准确性的严格要求，分布式机器学习需要从软件和硬件两方面分别进行提升。

分布式机器学习平台能够从软件层面极大地为研究者带来便利。Apache Spark是一个开源集群运算框架，最初由UCBerkeley AMPLab所开发。Spark框架是基于数据流的模型，其在处理大规模、高维度的大数据时，巨大的参数规模使得模型训练异常耗时。为解决该困难，研究人员提出了参数服务器模型，如Petuum框架。在后续的长期开发和应用中，研究和工程人员深感两类模型各有利弊，应该扬长弃短，搭配使用。Google Brain团队于2015年推出了TensorFlow[1]，其综合使用了两类模型，将计算任务抽象成有向图，可以更方便地进行分布式训练，一跃成为当时机器学习研究者使用的首选框架。2017年，Facebook的科学家推出了PyTorch[63]，它是Python开源科学计算库NumPy的替代者，支持GPU且具有更高的性能，为深度学习研究平台提供了最高的灵活性和最快的速度。PyTorch和TensorFlow类似，都是将网络模型的符号表达式抽象成计算图，不同的是，PyTorch的计算图是在运行时动态构建的，而TensorFlow是事先经过编译的，也即静态图。PyTorch因其简洁易用深得研究者的喜欢，而TensorFlow在工业界则更受欢迎。一些小众的框架如MXNet在特殊领域获得应用。

软件和硬件相互搭配，才能够发挥分布式机器学习的最大潜力。大部分研究者使用的是英伟达（Nvidia）公司的图形处理器（Graphics Processing Unit，GPU），利用其在进行图像计算中的优越性来加快机器学习算法的训练速率。除了通用的处理器，Google在2016年5月公布了张量处理单元（Tensor Processing Unit，TPU）[37]，这是Google专门为TensorFlow开发的专用集成电路芯片（Application-Specific Integrated Circuit，ASIC）。随着自然语言处理和计算机视觉的研究对于计算量的要求越来越高，TPU已经成为处理该类任务的首选项。Google在其云平台上开放了TPU租用服务，让更多的研究者可以利用TPU训练模型。

随着分布式机器学习的发展，数据孤岛和数据隐私问题获得了更多的关注。数据孤岛指由于商业公司的数据大多具有极大的潜在价值，并且涉及用户的隐私，因此数据很难在商业公司乃至其部门之间进行共享，导致数据大多以孤岛的形式出现。在这种情况下，联邦学习应运而生[39,94]。联邦学习作为分布式机器学习的范式，可以有效解决数据孤岛问题，让参与方在不共享数据的基础上联合建模，从技术上打破数据孤岛，实现AI协作（参见图1.3）。联邦学习最早于2016年提出，原本用于解决安卓手机终端用户在本地更新模型的问题[53]。在2016年的这篇文章中，Google的研究者提出了Federated Averaging（FedAvg）算法，其基本想法是对所有本地模型的梯度进行平均来更新模型，这样既避免了本地用户之间的数据共享，还可以利用其梯度信息进行联合建模。在此基础上，联邦学习拓展到了更多的场景中，如适用于数据集共享相同特征空间但样本不同的情况下的横向联邦学习，适用于两数据集共享相同的样本ID空间但特征空间不同的情况下的纵向联邦学习，和适用于两数据集不仅在样本上而且在特征空间上都不同的情况下的联邦迁移学习[94]。2018年12月，IEEE标准协会批准了关于联邦学习架构和应用规范的标准立项。