多智能体系统研究的历史、现状及挑战

8专题第 10 卷  第 9 期  2014 年 9 月来的AAAI人工智能会议(AAAIConferenceonArtificialIntelli-gence)和国际人工智能联合会议(InternationalJointConferenceOnArtificialIntelligence,IJCAI)上，录用的关于多智能体系统的文章数量一直名列前两位。多智能体系统领域的创始人维克托·莱瑟(VictorLesser)教授于2009年获得了IJCAI杰出研究奖(IJCAIAwardforResearchExcellence)。自1995年以来，IJCAI计算机与思维奖(IJCAIComputersandThoughtAward)的获奖者有一半以上来自多智能体系统领域。多智能体系统研究的历史自1956年约翰·麦卡锡(JohnMcCarthy)在著名的达特茅斯研讨会上提出“人工智能”这一概念后，“智能体”的概念便开始兴起。例如，阿兰·图灵(AlanTuring)提出了用来判断一台机器是否具备人类智能的“图灵测试”。在此测试中，测试者通过监视设备向被测试的实体（也就是我们现在所说的智能体）提问。根据图灵的观点，如果测试者无法区分被测试对象是计算机还是人，那么被测试对象就是智能的。人工智能泰斗马文·明斯基在他的《心智社会》这本书中将智能体描述为实现人类智能的多智能体系统(multi-agentsystems)由分布式人工智能演变而来，其研究目的是解决大规模、复杂、实时和有不确定信息的现实问题，而这类问题是单个智能体所不能解决的。多智能体系统通常具有自主性、分布性、协调性等特征，并具有自组织能力、学习能力和推理能力。对多智能体系统的研究既包括构建单个智能体的技术，如建模、推理、学习及规划等，也包括使多个智能体协调运行的技术，例如交互通信、协调、合作、协商、调度、冲突消解等。随着互联网技术的发展，多智能体系统中往往会出现一些“自私”的智能体（如电子商务市场的交易方），因此需要引入博弈论来分析智能体的交互策略，其研究内容包括电子商务、拍卖、机制设计、社会选择理论等。经过近30年的发展，多智能体系统已经成为国际人工智能领域的前沿和研究热点。在近年安　波1,2　史忠植2　1新加坡南洋理工大学2中国科学院计算技术研究所多智能体系统研究的历史、现状及挑战关键词：智能体　多智能体系统　人工智能图1　多智能体系统创始人维克托·莱瑟9第 10 卷  第9 期  2014 年 9 月基本模块。尽管智能体的概念很早就已经出现，但在20世纪70年代之前将多个智能体作为一个功能上的整体（即能够独立行动的自主集成系统）进行研究的做法却很少。一些研究着眼于构建一个完整的智能体或多智能体系统，比如Hearsay-II语音理解系统[1]、STRIPS规划系统[2]、Actor模型[3]等。1978年，美国国防部高级研究计划署(DARPA)在卡耐基梅隆大学举办分布式传感器网络研讨会，这是最早的此类会议。1980年，分布式人工智能领域的首次研讨会在麻省理工学院举办。在会议上，研究人员讨论了分布式问题求解、多智能体规划、组织控制、合同网、协商、分布式传感器网络、功能精确的协作分布式系统、大规模行为者模型以及智能体规范逻辑框架等重要的多智能体系统研究问题。自此，集成智能体构建和多智能体系统研究的各个分支领域都有了较大发展。20世纪80年代后期，随着《分布式人工智能》(DistributedArtificialIntelligence)和《分布式人工智能教程》(ReadingsinDis-tributedArtificialIntelligence)的出版[4,5]，分布式人工智能领域开始显著扩张，建立在博弈论和经济学概念之上的自私智能体交互的研究也逐步兴盛起来[6]。随着协作型和自私型智能体研究的交融，分布式人工智能逐渐演变并最终有了一个包罗万象的新名字——多智能体系统。90年代初期，多智能体系统研究快速发展，智能体的出现催生了许多软件技术。面向智能体的编程范式(Agent-OrientedPro-gramming，AOP)将软件的构建集中在软件智能体的概念之上。相比面向对象的编程以对象（通过变量参数提供方法）为核心的理念，AOP以外部指定的智能体（带有接口和消息传递功能）为核心。很快，一批移动智能体框架以Java包的形式开发和发布，2000年国内开展网构软件的研究[7]，2002年开展了构建智能体网格的工作[8]。由于90年代初期开发的KQML和KIF这两种颇具影响力的智能体通信语言一直没有被正式标准化，因此一些研究人员认为智能体技术可能会因为国际标准的缺乏而难以得到广泛认可。90年代中期，工业界对智能体系统的关注集中在标准化这一焦点上。FIPA1在1995年开始多智能体方面的标准化工作，它的核心目标是制定一套用于智能体协作的语言。90年代后期，研究人员开始在不断拓宽的现实领域寻求多智能体系统的新发展。机器人世界杯(RoboCup)应运而生。举行RoboCup比赛的目标是，在50年内，产生出一支能够战胜具有世界杯水准的人类球队的机器人足球队。其出发点是，从理论上说一支出色的球队需要一系列技能，比如利用有限的带宽进行实时动态的协作，机器人球队如果能战胜人类球队，标志多智能体系统在技术和理论上有根本的突破。参加RoboCup的热度在世纪之交暴涨，定期举办的RoboCup锦标赛吸引了来自世界各地的数百支参赛队伍。2000年，Ro-boCup推出了一项新的活动——RoboCup营救。这项活动以1995年发生的日本神户大地震为背景，目标是建立一支能够通过相互协作完成搜救任务的机器人队伍。在世纪之交，以智能体为媒介的电子商务成为智能体技术的最大单一应用场合，为智能体系统在谈判和拍卖领域的发展提供了巨大推动力。2000年以后，以促进和鼓励高质量的交易智能体研究为目的的交易智能体竞赛(TradingAgentCompetition)推出并吸引了很多研究人员参与。自2001年以来，多智能体系统的思想对主流计算机科学产生了深远影响，拍卖和机制设计等研究领域已经跻身理论计算机科学的主要课题。这些突破性进展首先缘于易趣(eBay)等在线拍卖行的巨大成功，但更普遍的是许多有趣的、重要的组合问题都可以表示为拍卖。对博弈论和计1FIPA(TheFoundationforIntelligentPhysicalAgents)是一个由活跃在智能体领域的公司和学术机构组成的国际组织，其目标是为异质的智能体和智能体系统之间的互操作而制订相关的软件标准。10专题第 10 卷  第 9 期  2014 年 9 月算机科学之间关联性的研究同样高涨。2008年，国际博弈论学会特意为最佳博弈论与计算机科学交叉研究设立了一个新的奖项。在多智能体系统领域涌现并得到应用的思想还包括：社会科学领域复杂分布式系统建模的多智能体模拟技术、形式化描述分布式系统的DEC-POMDP以及个人协助技术。同时下一代分布式传感器、网络化自动驾驶车辆和机器人系统、自主计算以及网络服务等未来多智能体技术更广阔的应用场景正展现在我们面前。2014年AAMAS年会1995年，第一届国际多智能体系统会议(InternationalCon-ferenceonMulti-AgentSystems,ICMAS)在美国旧金山举办[9]。紧接着，智能体理论、架构和语言国际研讨会(InternationalWorkshoponAgentTheories,Ar-chitectures,andLanguages,ATAL)和国际自主智能体会议(Interna-tionalConferenceonAutonomousAgents,AA)也相继举办。2002年，国际智能体及多智能体系统协会(InternationalFoundationforAutonomousAgentsandMul-tiagentSystems,IFAAMAS2)将上述三个会议合并为智能体及多智能体系统国际会议(InternationalJointConferenceonAutonomousAgentsandMulti-AgentSystems,AAMAS)。第13届AAMAS于2014年5月5~9日在法国巴黎举行，吸引了全世界800多名研究人员参会。AAMAS2014设置了一个主要议题——多智能体系统研究，4个特别议题——创新应用、机器人、虚拟智能体和创新思维。会议共收到投稿709篇，其中60%的论文第一作者是学生，会议最终录用了169篇全文，录取率为23%。从录用论文的关键词来看，博弈论以及相关领域的研究最受关注，紧随其后的是智能体合作和智能体推理。AAMAS2014共设28个专题研讨会，既包括相对传统的多智能体优化、增强学习、合作博弈论、电子商务、多智能体模拟、序贯决策、自动协商等，也包括最近兴起的面向可持续发展的多智能体系统、人与智能体交互等热点问题。ACM/SIGART智能体研究奖(ACM/SIGARTAutonomousAgentsResearchAward)是多智能体系统领域最重要的学术成就奖。本届会议的获奖者是美国密歇根大学的迈克尔·韦尔曼(Mi-chaelWellman)教授，以表彰他将经济学应用到多智能体系统研究的开创性贡献。IFAAMAS维克托·莱瑟杰出博士论文奖(DistinguishedDis-sertationAward)旨在奖励全世界多智能体系统领域最优秀的博士论文。2013年杰出博士论文奖得主是美国南加州大学的曼尼什·简(ManishJain)博士，表彰其在安全博弈论方向的研究及应用。IFAAMAS有影响力论文奖(InfluentialPaperAward)于2006年创立，旨在奖励10年以前发表的对多智能体系统理论及应用产生巨大影响的论文。今年该奖颁发给了IBM以色列研究院的安·史哈瑞(OnnShehory)博士和巴伊兰大学的克劳斯·萨里塔(SaritKraus)教授，以表彰他们于1998年在《人工智能》上发表的关于组织形成(coalitionfor-mation)的论文。研究热点算法博弈论算法博弈论是博弈论和算法设计的交叉领域。算法博弈论中算法的输入通常来自许多分布的参与者，这些参与者对输出有不同的个人偏好。智能体参与者可能会因为个人利益而隐瞒真实的输入信息。除了经典算法设计理论要求的多项式运算时间及较高近似度之外，算法设计者还需要考虑约束智能体的动机。显然，算法博弈论的研究有两个关键。1.分析：参照现有算法，利2一个以提供统一的、高质量的，并广受国际关注的智能体和多智能体系统理论和实践研究论坛，以促进人工智能、智能体与多智能体系统领域科技发展的非盈利机构。11第 10 卷  第9 期  2014 年 9 月用博弈论工具对其进行计算均衡、证明均衡性质、无序代价(priceofanarchy)、最优动态反应等方面的分析。2.设计：设计具备良好均衡和算法属性的博弈，即算法机制设计。自1999年尼桑(Nisan)和罗恩(Ronen)在美国计算机学会计算理论会议(ACMSymposiumonTheoryofComputing,STOC)[10]上将理论计算机学术界的目光引向针对自私用户的算法设计上，算法博弈论便开始兴起。雅虎、谷歌以及百度等从搜索广告拍卖获得的巨额收入掀起了对算法博弈论研究的高潮。算法博弈论当前的研究热点包括算法机制设计、计算社会选择理论、（社交）网络分析、均衡分析等。安全博弈论及其应用保护关键公共基础设施和目标是各国安全机构肩负的一项极具挑战性的任务。有限的安全资源使得安全机构不可能在任何时候都提供全面的安全保护。此外，安全机构的对手可以通过观察来发现安全机构保护策略的固定模式和弱点，并据此来选择最优的攻击策略。一种降低对手观察侦查能力的方式是随机调度安全机构的保护行为，这种方法广泛使用于警察巡逻、行李检测、车辆检查以及其他安全程序。然而，安全机构在进行有效的随机安全策略调度时面临许多困难[11]，特别是有限的安全资源无法无处不在或每时每刻提供安