中科大教授吴锋:多智能体的分布式在线决策

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技术。我们也把我们的主要技术用在了实体机器人身上,当前也取得了不错的效果。


谢谢大家!

腾讯AI实验室
腾讯AI实验室

入门多智能体
相关数据
机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

感知技术

知觉或感知是外界刺激作用于感官时,脑对外界的整体的看法和理解,为我们对外界的感官信息进行组织和解释。在认知科学中,也可看作一组程序,包括获取信息、理解信息、筛选信息、组织信息。与感觉不同,知觉反映的是由对象的各样属性及关系构成的整体。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

阿尔法围棋技术

阿尔法围棋是于2014年开始由英国伦敦Google DeepMind公司开发的人工智能围棋程序。AlphaGo是第一个打败人类职业棋手的计算机程序,也是第一个打败围棋世界冠军的计算机程序,可以说是历史上最强的棋手。 技术上来说,AlphaGo的算法结合了机器学习(machine learning)和树搜索(tree search)技术,并使用了大量的人类、电脑的对弈来进行训练。AlphaGo使用蒙特卡洛树搜索(MCTS:Monte-Carlo Tree Search),以价值网络(value network)和策略网络(policy network)为指导,其中价值网络用于预测游戏的胜利者,策略网络用于选择下一步行动。价值网络和策略网络都是使用深度神经网络技术实现的,神经网络的输入是经过预处理的围棋面板的描述(description of Go board)。

规划技术

人工智能领域的「规划」通常是指智能体执行的任务/动作的自动规划和调度,其目的是进行资源的优化。常见的规划方法包括经典规划(Classical Planning)、分层任务网络(HTN)和 logistics 规划。

蒙特卡罗树搜索技术

蒙特卡洛树搜索(英语:Monte Carlo tree search;简称:MCTS)是一种用于某些决策过程的启发式搜索算法,最引人注目的是在游戏中的使用。一个主要例子是电脑围棋程序,它也用于其他棋盘游戏、即时电子游戏以及不确定性游戏。

机器人技术技术

机器人学(Robotics)研究的是「机器人的设计、制造、运作和应用,以及控制它们的计算机系统、传感反馈和信息处理」 [25] 。 机器人可以分成两大类:固定机器人和移动机器人。固定机器人通常被用于工业生产(比如用于装配线)。常见的移动机器人应用有货运机器人、空中机器人和自动载具。机器人需要不同部件和系统的协作才能实现最优的作业。其中在硬件上包含传感器、反应器和控制器;另外还有能够实现感知能力的软件,比如定位、地图测绘和目标识别。之前章节中提及的技术都可以在机器人上得到应用和集成,这也是人工智能领域最早的终极目标之一。

多智能体系统技术

一个多智能体系统,是由一个在一个环境中交互的多个智能体组成的计算系统。多智能体系统也能被用在解决分离的智能体以及单层系统难以解决的问题。智能可以由一些方法,函数,过程,搜索算法或加强学习来实现。尽管存在相当大的重叠,然而一个多智能体系统并不总是一个基于智能体的模型表现一致。

强化学习技术

强化学习是一种试错方法,其目标是让软件智能体在特定环境中能够采取回报最大化的行为。强化学习在马尔可夫决策过程环境中主要使用的技术是动态规划(Dynamic Programming)。流行的强化学习方法包括自适应动态规划(ADP)、时间差分(TD)学习、状态-动作-回报-状态-动作(SARSA)算法、Q 学习、深度强化学习(DQN);其应用包括下棋类游戏、机器人控制和工作调度等。

人机交互技术

人机交互,是一门研究系统与用户之间的交互关系的学问。系统可以是各种各样的机器,也可以是计算机化的系统和软件。人机交互界面通常是指用户可见的部分。用户通过人机交互界面与系统交流,并进行操作。小如收音机的播放按键,大至飞机上的仪表板、或是发电厂的控制室。

推荐文章
暂无评论
暂无评论~