中科大吴锋：多智能体的分布式在线决策 | 腾讯AI Lab学术论坛演讲

本文转载自：腾讯AI实验室

本文第一部分是中国科学技术大学计算机科学与技术学院副教授吴锋带来的主题演讲，第二部分介绍了腾讯AI Lab在AI研究到应用的布局中，在「AI+游戏」方向的挑战与应对的分析。

3月15日，腾讯AI Lab第二届学术论坛在深圳举行，聚焦人工智能在医疗、游戏、多媒体内容、人机交互等四大领域的跨界研究与应用。全球30位顶级AI专家出席，对多项前沿研究成果进行了深入探讨与交流。腾讯AI Lab还宣布了2018三大核心战略，以及同顶级研究与出版机构自然科研的战略合作（点击 这里 查看详情）。

腾讯AI Lab希望将论坛打造为一个具有国际影响力的顶级学术平台，推动前沿、原创、开放的研究与应用探讨与交流，让企业、行业和学界「共享AI+未来」。

吴锋

中国科学技术大学计算机科学与技术学院副教授

在下午的“AI+游戏”论坛上，中国科学技术大学计算机科学与技术学院副教授吴锋做了主题为《多智能体分布式在线决策》的演讲。

吴锋博士的主要研究方向为多智能体系统、自动规划理论和智能机器人决策，在 AIJ、IJCAI、 AAAI、NIPS、UAI、AAMAS、ICAPS和ECAI等人工智能学术会议和期刊上发表论文30余篇。他曾获中国科学院院长奖特别奖、中国科学院优秀博士论文奖，以及第14届智能体与多智能体国际会议（AAMAS 2015）最佳应用论文奖。此外，他还是中科大“蓝鹰”足球机器人团队的核心成员，多次参加RoboCup机器人学术竞赛，并获得3项世界冠军和1项世界亚军。他曾担任 AIJ、JAIR、JAAMAS、ACM Trans 等国际人工智能学术期刊的审稿人，以及AAAI、IJCAI、AAMAS等国际人工智能学术会议的程序委员会委员。

演讲内容

本演讲介绍了在以足球为代表的多人竞技游戏中，要求多个智能体能够在动态不确定性环境中自主的做出决策，配合队友与对手对抗并最终赢得比赛。针对这类挑战性问题，吴锋教授的团队发展出了基于马尔科夫决策过程的技术路线，设计了高效的多智能体分布式在线决策系统。该系统成功应用于足球机器人中，在国际机器人竞赛中连续十年保持世界前二，显示出了良好的稳定性和适应性。

以下为演讲全文（为便于阅读进行过适当编辑整理）：

大家好，我将分享一下我们在“多智能体分布式在线决策”方面的研究工作。和前面的几位专家的强化学习研究方向不同，我们采用的是基于模型（model-based）的方法，这是一种比较经典的用于推理决策的方法。这种方法在数据很少或很难获得数据的场景中有时也能取得很好的表现。

这是我报告的提纲。首先我会介绍一下我们研究的背景，即游戏中的智能决策。然后我会介绍一下我们所采用的模型，即局部可观察的随机博弈。针对这样的模型和问题，最后我会介绍一下我们设计的高效求解算法。

首先是我们的背景。作为检测机器是否具有智能的一个重要手段，智力游戏受到了AI研究者的广泛青睐。从早期的“深蓝”到近期的“AlphaGo”，机器每一次战胜人类的世界冠军都会引起轰动，成为AI发展史上的一个里程碑。在这类游戏中，都要求机器能够做出复杂的决策，并且达到可与人类媲美的水平。当前这类问题的研究逐渐从完全信息和确定性的棋类游戏转向了信息不完全且具有不确定性的游戏（比如扑克、《星际争霸》），并且已经取得了不俗的成果。

对于《王者荣耀》这样的多人在线游戏，它的决策问题也有一些自身的特点；比如玩家需要利用手机屏幕上看到的有限信息（包括左上角的小地图）对形势做出判断，然后实时做出决策并采取相应操作。同时玩家控制的英雄还具备不同的能力和属性，有些是肉盾型的（比如坦克和战士），有些是输出型的（比如射手和刺客），还有一些是控制型的（比如法师和辅助）。他们之间需要相互配合共同完成杀敌和推塔这样的任务，同时这样的任务还具有随机不确定性；比如在玩游戏时会有“顺风局”和“逆风局”的说法。针对多人在线游戏问题的研究现在有很多，而且涉及到很多不同的游戏。

其中的焦点问题之一是足球游戏，足球在电子游戏流行之前就已经风靡全球了。在足球比赛中，球员需要根据视野中获得的有限信息做出判断，决定这个球怎么踢。不同的球员之间也有不同的能力和一定的属性，比如有的球员跑得比较快、有的个子比较高、有的耐力比较好、有的射门比较准。不同球员之间不同的身体素质决定了他们不同的能力。但他们之间还需要相互配合，共同完成防御对手、射门得分等任务。另外足球比赛还具有很强的随机不确定性，在比赛中经常会出现一些黑马球队改写整个比赛的进程，给大家带来一些惊喜。

所以，简单比较我们可以发现，足球问题其实和《王者荣耀》等多人在线游戏是非常接近的，特别是在决策问题方面，它们具有很多相似性。

早在 1997 年深蓝战胜人类国际象棋世界冠军的时候，就有一些顶尖研究者开始寻找下一个挑战目标了，他们相中了足球。他们在那一年发起了一个学术竞赛活动——RoboCup（机器人世界杯）。当时他们制定了极具野心的目标：在 2050 年左右设计出一支能够战胜当时的人类世界杯冠军球队的机器人球队。经过了二十多年的发展，RoboCup 已经成为了国际上规模最大且最有影响力的机器人赛事之一。

RoboCup 中有很多专门针对足球的项目，比如双足、轮式、仿真。今天我主要介绍的是和多人游戏最接近的仿真游戏。在足球仿真竞赛中，由于是在电脑上进行仿真，所以能摆脱机器人硬件发展相对滞后的束缚。仿真比赛中采用了与真实足球非常相同的规则，就是每支球队有 11 个异构球员和 1 个教练，其中 11 个异构球员有不同的能力和属性（比如跑步速度、耐力等等）。在决策方面，这个问题有一些核心难点，比如信息有限、需要各个智能体自主决策、动作带有很强的不确定性。仿真设计只是对控制和感知方面进行了一些必要的抽象，所以这个问题就更注重球员之间的相互配合和团队协作。因此，这个问题的研究重点是动态和不确定性环境中的多智能体系统的决策。

针对这样的问题，我们采用了一种称为“局部可观察随机博弈”的模型（简称POSG），可以建模多个智能体在动态不确定环境中的对抗和合作。在这个模型中它有N个智能体集合，每个智能体会在环境中执行相应的动作，执行的动作会导致这个环境发生一定的状态转移，然后每个智能体又会获得各自的观察。这是把不确定的多智能体对抗问题抽象成了动态可观察的随机博弈问题。比如在足球中，一个智能体就是一个球员，能够执行各种踢球、奔跑的动作，它获得的观察是它视野内可以看到的球、队友以及对手的信息。比如在《王者荣耀》游戏中，每个智能体代表的是一个英雄，每个英雄有自己的动作集和观察集——不同的英雄有不同的技能，观察能力也不一样。

在这个模型中，转移函数是刻画每个智能体的动作效果，观察函数是建模每个智能体的感知能力，回报函数是描述每个智能体的主要任务。我们求解的这个模型的目标是获得一组策略，以最大化每个智能体的收益。

每个智能体的策略通常可以表示成策略树的形式。每个智能体都有自己的策略树，策略树的节点代表你需要执行的动作，每条边表示智能体在环境中可能获得的观察。在执行的时候从根节点开始，根据获得的一系列观察执行一个动作序列。

在机器人足球发展的早期，很多球队都是基于规则的，因为这种方法比较简单。但是基于规则的方法有个问题：需要人工地为每个机器人写一棵策略树，这个过程既复杂又繁琐，而且也不能保证策略的质量。最重要的是策略树的分支太多了！在一步决策时，策略树非常简单，每个智能体可能只有两个策略。在两步决策时，就变得很多了，但还可以接受。三步的时候就非常多了。六、七步的时候可能就变成了天文数字。事实上，这类问题的策略空间会随问题的规模呈双指数爆炸式增长。

在这么大的策略空间中，智能体很难为自己找到最优解。而且每个智能体在挑选最优策略时不仅要考虑环境状态的变化，同时还要考虑其它智能体可能会采取的策略。比如，在足球比赛过程中，你不仅要考虑球的位置和自己的状态，还要考虑你的队友或对手可能会采取什么策略来帮助或制衡你。队友和对手可能采取的策略会最终决定你自己的策略选择。也就是说，每个智能体在进行决策时所需要考虑的因素处在非常高维的空间，而且这个高维空间的维度还会随问题规模的增大而爆炸式增长。所以我们已经从理论上证明了这类可观察随机博弈问题的计算复杂度是 NEXP 难的，比普通的 NP 难问题要复杂得多。

问题虽然很难，但还是有办法进行求解。下面介绍一下我们在求解该模型上的一些尝试。简单来说，多智能体的分布式在线规划就是在在线执行时每个智能体都独立执行多步前瞻搜索，然后选择一个最优动作来执行。这和很多博弈过程中所采用的蒙特卡罗树搜索非常接近，但主要区别在于多智能体分布式在线规划的所有智能体会同时进行决策，而不是一人一步回合制地决策。因此这就需要对其它智能体的决策进行预判。同时每个智能体所得到的信息都是不完全的，没有全局信息，所以需要根据获得的局部信息维护一个信念状态，即全局信息的一个概率分布。

更具体地说，我们在前瞻搜索的时候采取了一个策略，即把多步随机博弈分解成多个单步子博弈，然后在搜索树的每个节点计算子博弈的均衡解。搜索结束之后，我们会回溯更新，沿着搜索路径更新每个节点的收益函数。此外我们还会根据对手的特点和实际反应来调整整个搜索过程中的模型参数，因为有些队伍在某些策略失败之后可能会转向其它策略，所以就会存在在线学习的过程。

这里有两个值得一提的关键技术。一个是基于关系图的博弈快速求解，它的主要想法是为每个智能体指定不同的角色，用智能体之间的角色和行为的相关性来简化单步博弈均衡解的计算。比如在足球中有一定的阵型，不同的球员会有不同的角色分配（比如后卫、中场、前锋）。根据这些信息就能够对博弈问题进行快速求解。

另一个尝试是针对具体问题的分层规划。智能体的行为从上到下会有不同层次，这样划分之后就能够在不同层次上进行处理，从而提高搜索效率。比如在足球问题中，有“进攻”这样的高层策略，也有“踢球”这样的底层具体动作；如果全部一起规划，问题求解可能就会非常低效。

最后对我们的研究工作进行一个总结。在这个报告中，我们说到多人在线游戏中的决策问题可以利用POSG（部分可观察的随机博弈）来进行建模，但该问题的求解非常困难，极具挑战性。我们提出的分布式在线规划可以有效地求解该类问题，在足球仿真游戏中表现突出。另外，如何深度结合机器学习来提高性能仍是一个开放性的问题。

此外，我们研究的不仅适用于足球、《王者荣耀》，它其实是比较通用的AI技术。我们也把我们的主要技术用在了实体机器人身上，当前也取得了不错的效果。

谢谢大家！

延伸阅读

在去年11月8日举办的腾讯2017全球合作伙伴大会上，腾讯AI Lab披露了AI发展布局的最新动态。本文转载游戏AI布局演讲的干货内容，介绍游戏AI研究的挑战与应对。更多内容可以点击文章【重磅 | 腾讯提出共享AI，抢先布局游戏与多媒体AI，首秀同声传译】查看。

《游戏AI：虚拟世界对物理世界的赋能》

演讲人：腾讯AI Lab机器学习中心负责人 刘晗博士

我们最想强调的，是游戏AI研究的奥义——远不止于游戏本身。这是一个富有挑战而令人振奋的研究课题，研究当中累积的经验、方法与结论，能在更广大深远的范围被利用。首先是打通虚拟与现实世界的藩篱，从而赋能物理世界，比如无人车和机器人的发展；其次，游戏中对话智能的研究，或能成为通向强人工智能的重要路径；第三，研究游戏中人、智能体和环境的交互，能让智慧城市这样复杂而意义深远的项目受益。

游戏AI是人工智能与博弈论的一个交叉领域。从小的方面来说，游戏AI研究如何用人工智能技术来提升人类玩游戏的体验。从大的方面来说，游戏AI研究人，智能体，以及环境之间的复杂交互关系。 游戏AI驱动了人工智能的发展，从国际象棋到围棋击败人类顶尖高手，而目前所挑战的游戏已从棋盘类转向《星际争霸》Real Time Strategy(RTS)和《DOTA 2》Multi-Player Online Battle Arena (MOBA)等游戏。

游戏AI涉及到三个核心能力：对外界环境的感知，根据状态做出的决策，人与智能体之间的对话。比如在围棋的游戏场景，可以通过感知棋盘的全局表达状态决定在哪里落子。而现实中的无人车，同样可以通过视觉，激光雷达的感知对方向盘，刹车等动作做出决策。

理解了游戏AI的三个核心能力。接下来我解释研究中三个核心挑战，及腾讯的解决方案。

第一个挑战是游戏的状态空间过大。比如很多战略型游戏的状态空间是无穷维，远大于围棋空间。腾讯提出了一套整合了模型，算法，与计算体系结构的解决方案，叫做腾讯机器大脑，整个系统的核心是使用深度神经网络来建模超大规模的状态空间。

第二个挑战是许多复杂的多玩家游戏需要多个智能体协调操作，目前这方面理论比较缺乏。为设计出一个完善的多智能体AI，一个核心问题是将强化学习的价值网络与描述宏观战略的行为树进行互操作，并使其融合。

第三个挑战是绝大部分游戏AI是用模拟器在一个理想化的虚拟世界中开发。如何打通虚拟与现实，又是一个核心挑战。我们的解决方案结合反向强化学习及动态探索机制，对游戏AI中的参数进行贝叶斯升级。这样得到的系统能保证在现实世界花最小的成本，就能成功部署。

这一套感知、对话与决策模块，形成了一套通用系统，未来有望在现实中被应用到更多场景中，这就是我们说的虚拟对现实的赋能。