第一部分 分布式人工智能简介

1 概述

1.1 研究背景

我们首先对分布式人工智能的历史进行扼要的回顾。分布式人工智能初创于20世纪70年代，在过去五十多年的发展过程中，可大致分为前深度学习时代和深度学习时代。前深度学习时代的分布式人工智能研究主要采用传统的优化算法，而在深度学习时代，人们则利用深度神经网络的强大表示能力来解决更大规模和更复杂的问题。

1.1.1 前深度学习时代

继1956年约翰·麦卡锡（John McCarthy）在著名的达特茅斯研讨会上提出“人工智能”（Artificial Intelligence）这一概念后，智能体（Intelligent Agent）领域开始兴起。“智能体”这一概念在早期的人工智能文献中就已经出现，例如阿兰·图灵（Alan Turing）提出用来判断一台机器是否具备人类智能的图灵测试。在这个测试中，测试者通过一些监视设备向被测试的实体（也就是我们现在所说的智能体）提问。如果测试者不能区分被测试对象是计算机程序还是人，那么根据图灵的观点，被测试的对象就被认为是智能的。尽管智能体的概念很早就出现，将多个智能体作为一个功能上的整体（即能够独立行动的自主集成系统）加以研究的思路在20世纪70年代之前都发展甚微。这期间，一些研究着眼于构建一个完整的智能体或多智能体系统，其中比较有影响的有Hearsay-II语音理解系统[22]、STRIPS规划系统[23]、Actor模型[33]等。1978年12月，DARPA分布式传感器网络研讨会作为最早致力于多智能体系统问题的研讨会在卡耐基梅隆大学（CMU）举办。1980年6月9日至11日，分布式人工智能的首次研讨会在麻省理工学院（MIT）举办。该研讨会持续了大约15年，在此期间，欧洲和远东地区的分布式人工智能研讨会也随着研究队伍的壮大而逐步开展。在1980年的这次会议上，研究人员开始谈论分布式问题求解、多智能体规划、组织控制、合同网、协商、分布式传感器网络、功能精确的协作分布式系统、大规模行为者模型，以及智能体规范逻辑框架等重要的多智能体系统研究问题。在此之后，集成智能体构建和多智能体系统研究的各个分支领域都有较大的发展。分布式人工智能领域自诞生之际起就海纳百川，包罗各个学科，直到今天依然是跨学科交叉的沃土。恰如其名，分布式人工智能和人工智能领域之间始终维系着最强的纽带。

随着20世纪80年代后期Distributed Artificial Intel ligence和Readings in Distributed Artificial Intelligence的出版[9,34]，重要的文献有了集中的去处，分布式人工智能领域开始联合并显著地扩张。在这段成长的时期，建立在博弈论和经济学概念上的自私智能体交互的研究逐步兴盛起来[71]。随着协作型和自私型智能体研究的交融，分布式人工智能逐渐演变并最终采用了一个更广阔、更包罗万象的新名字——“多智能体系统”。

20世纪90年代初期，得益于同期互联网的迅猛扩张，多智能体系统研究快速发展。此时互联网已从一个学术圈外鲜为人知的事物演变成全球商业和生活等领域不可或缺的日常工具。如果说计算的未来在于分布式的、联网的系统，人们亟须新的计算模型去挖掘这些分布式系统的潜能，那么互联网的爆炸式增长或许就是最好的说明。毫无疑问，互联网将成为多智能体技术的主要试验场之一。基于和用于互联网的智能体的出现催生了新的相关软件技术。人们提出了面向智能体的编程范式（Agent-oriented Programming，AOP），将软件的构建集中在软件智能体的概念上。相比面向对象的编程以对象（通过变量参数提供方法）为核心的理念，AOP以外部指定的智能体（带有接口和消息传递功能）为核心。很快，一批移动智能体框架以Java包的形式被开发和发布。

20世纪90年代中期，工业界对智能体系统的兴趣集中在标准化这一焦点上。一些研究人员开始认为智能体技术可能会因为公认的国际标准的缺失而难以得到广泛的认可。当时开发的两种颇具影响力的智能体通信语言——KQML和KIF——就一直没有被正式地标准化。因此，FIPA（Foundation for Intelligent Physical Agents）运动在1995年开始了标准化多智能体的工作，它的核心是一套用于智能体协作的语言。20世纪90年代后期，随着互联网的继续发展，电子商务应运而生，“.com”公司席卷全球。很快，人们意识到电子商务代表着一个自然且利益丰厚的多智能体系统应用领域，其中的基本想法是智能体驱动着电子商务中从产品搜寻到实际商谈的各个环节。到世纪之交，以智能体为媒介的电子商务或许已经成为智能体技术的最大单一应用场合，为智能体系统在谈判和拍卖领域的发展提供了商业和科学上的巨大推动力。2000年以后，以促进和鼓励高质量的交易智能体研究为目的的交易智能体竞赛（Trading Agent Competition）推出并吸引了很多研究人员的参与。到20世纪90年代后期，研究人员开始在不断拓宽的现实领域寻求多智能体系统的新发展，机器人世界杯（RoboCup）应运而生。RoboCup的目的很清晰，即证明在五十年之内，一支机器人足球队能够战胜世界杯水准的人类球队，其基本理论在于一支出色的球队需要一系列的技能，比如利用有限的带宽进行实时动态的协作。RoboCup的热度在世纪之交暴涨，定期举办的RoboCup锦标赛吸引了来自世界各地的数百支参赛队伍。2000年，RoboCup推出了一项新的活动——RoboCup营救。这项活动以20世纪90年代中期日本神户大地震为背景，以建立一支能够通过相互协作完成搜救任务的机器人队伍为目标。

高水平的学术会议对于一个领域的发展至关重要。1995年，第一届ICMAS大会（International Conference on Multi-Agent Systems）在美国旧金山举办。紧接着，ATAL研讨会（International Workshop on Agent Theories，Architectures，and Languages）和AA会议（International Conference on Autonomous Agents）相继举办。国际智能体及多智能体系统协会（International Foundation for Autonomous Agents and Multiagent Systems，IFAAMAS）以促进人工智能、智能体与多智能体系统领域的科技发展为宗旨成立。为了提供一个统一、高质量并广受国际关注的智能体和多智能体系统理论和实践研究论坛，IFAAMAS在2002年将上述三个会议合并为智能体及多智能体系统国际会议（International Joint Conference on Autonomous Agents and Multi-Agent Systems，AAMAS），一般在每年的5月举行，在美洲、欧洲、亚洲和大洋洲轮流召开。自那以后，AAMAS会议成为多智能体系统和分布式人工智能领域的顶级会议，与会者发表了许多具有开创性意义的文章，极大地促进了这一领域的发展。

1.1.2 深度学习时代

深度学习自2006年提出之后，为学术界和工业界带来了巨大的变革。它从计算机视觉领域出发，进而影响了强化学习和自然语言处理领域，并在近几年越来越多地用于分布式人工智能领域。深度学习用于分布式人工智能，并引起广泛关注的是2016年来自DeepMind的科学家开发的用于求解围棋策略的AlphaGo[77]，它是第一个击败人类职业围棋选手、第一个击败围棋世界冠军的人工智能算法（见图1.1）。基于AlphaGo，DeepMind后续开发了AlphaGo Zero[78]、AlphaZero[79]和Muzero[74]，极大地推进了该方面的研究。在AlphaGo中采用的算法可以很好地求解完全信息博弈下的策略，但不适用于非完全信息博弈。2017年阿尔伯塔大学开发了DeepStack系统，它被用来解决在二人无限下注场景下的德州扑克问题，并最终史无前例地击败了职业的扑克玩家[58]。在此之后，人们将目光转移到了斗地主和麻将上面，借助于深度学习和强化学习的强大能力，人工智能算法依然取得了击败人类职业玩家的良好效果。

图1.1 AlphaGo对战李世石

深度学习在分布式约束问题（DCOP）和组合优化问题的求解上也得到了应用。深度学习的优势在于其借助深度神经网络强大的表示能力，可以对大规模的复杂问题进行表示，这也是分布式约束问题和组合优化问题常常需要的。因而在2014年，研究者将深度学习用到了分支定界的算法当中，取得了不错的效果[30]。2015年，Google的研究者提出了Pointer Network（Ptr-Net）[88]，这是一类专为解决组合优化问题提出的神经网络，作者成功地将其应用在了旅行商问题（TSP）上。基于Pointer Netwok的相关后续工作包括将强化学习和Pointer Network相结合来解决对于标签的依赖[6]，利用注意力模型和强化学习解决车辆路径规划问题[61]，以及使用自然语言处理中的Transformer模型提升算法效果[40]。另外，由于图神经网络（Graph Neural Network，GNN）研究的兴起，研究者也开始将其用于解决组合优化问题[15]。早期的尝试包括利用Structure2Vec GNN结构结合强化学习算法解决旅行商问题，以及最大割和最小顶点覆盖问题[18]。后续工作包括利用监督学习和GNN解决决策版本的旅行商问题[64]，含有更多约束的问题如带有时间窗口的旅行商问题[14]。这类方法也被应用于解决布尔可满足性（SAT）问题，同样取得了不错的效果[13,75]。

研究者不仅把深度学习的技术应用在博弈和分布式优化问题上，也把它应用到了分布式人工智能的其他领域。近几年发展尤为迅速的是多智能体强化学习（MARL）领域。2017年提出的MADDPG算法[50]提出了“集中式训练，分布式执行”的训练模式，在简单问题上很好地解决了不同智能体之间在没有通信情况下的合作问题。2018年牛津大学提出了QMIX算法[66]，并且开源了StarCraft II Multi-Agent Challenge（SMAC）环境[72]作为测试MARL算法效果的通用环境。SMAC是一组基于暴雪公司开发的星际争霸（StarCraft）游戏精心设计的智能体之间合作的任务，它可用来测试算法在不同合作模式下的训练效果。自那之后出现了很多基于SMAC的工作，受到研究者关注的有QTRAN[80]、QPLEX[90]和Weighted QMIX[67]。虽然SMAC是一组理想的测试环境，但是任务本身难度较小，具有一定的局限性，因而DeepMind的研究者基于完全版本的星际争霸来训练智能体，最终他们训练的智能体达到了Grandmaster水准[89]。几乎与此同时，OpenAI的研究者利用深度学习训练了打Dota 2游戏的多智能体系统，并击败了人类职业玩家[7]。这些研究被认为是多智能体强化学习在复杂决策问题上可以超过人类的典型例子。

中国学者为分布式人工智能的发展也贡献了自己的力量。2019年，第一届分布式人工智能国际会议（International Conference on Distributed Artificial Intelligence，DAI）在北京召开。DAI的主要目标是将相关领域（例如通用人工智能、多智能体系统、分布式学习、计算博弈论）的研究人员和从业者聚集在一起，为促进分布式人工智能的理论和实践发展提供一个高水平的国际研究论坛。自创办以来，该会议得到了中外许多研究者的关注和参与，会上所发表的文章也获得了研究者的引用，激发了许多后续的研究，形成了一定的影响力。