第6卷第2期 智能系统学报 Vol.6 No.2 2011年4月 CAAI Transactions on Intelligent Systems Apr.2011 doi:10.3969/i.issn.1673-4785.2011.02.009 不完全信息博弈的机器人对抗决策 史晓茹，侯媛彬，张涛 (西安科技大学电气与控制工程学院，陕西西安710054) 摘要：针对机器人比赛时局势的动态变化给机器人对抗决策博弈局面带来的不完全性问题，提出了豪尔绍尼转换 和贝叶斯均衡相融合的不完全信息博弈算法，该算法克服了博弈局势中对未知信息的盲目“猜测”.以机器人足球比 赛时的数据为背景建立不完全信息博弈模型，研究机器人的决策对抗系统.仿真结果表明，不完全信息博弈算法可 以使得机器人进行较优策略的选择，从而进一步提高机器人在比赛中的自主性和智能性. 关键词：不完全信息博弈：贝叶斯均衡；豪尔绍尼转换；对抗决策；机器人比赛 中图分类号：TP391文献标识码：A文章编号：16734785(2011)02014705 The decision-making system of robots based on an incomplete information game SHI Xiaoru,HOU Yuanbin,ZHANG Tao Xi'an University of Science and Technology Xi'an 710054,China Abstract:While considering the incomplete game situation of decision-making in robot competition caused by the dynamic changes of the situation,games of incomplete information fusing Harsanyi conversion and Bayesian equilib- ria were proposed.This enabled the elimination of blind guessing of unknown information in game circumstances. Based on the robot soccer competition,a game model of incomplete information was established and a decision-mak- ing robot system was researched.The simulation results showed that the incomplete information game algorithm can help robots to choose better strategies,further improving the independence and intelligence of robots in competi- tion. Keywords:incomplete information game;Bayesian equilibria;Harsanyi conversion;decision-making;robot compc- tition 博弈论(game theory)作为一门现代科学体系， 近年来，博弈论在机器人方面的应用都有了一定 起源于20世纪初，在二战后发展成为一门完整而丰 的研究3)]，意大利的学者N.Basilico和N.Gatt4在 富的理论科学.博弈算法经过不断的研究、改进与提 其论文中将博弈论理论应用于模拟机器人学，并提出 高，目前已经成为解决诸多动态复杂环境中决策问 了Leader-Follower平衡；美国耶鲁大学的专家M.Be 题的一种重要方法.以往的机器人决策方法主要采 etz、S.Buck等人[S)在其论文中将合作概率博弈应用 用了有限状态机法山和智能体强化学习法21.常规 于足球机器人策略选择中，提高了机器人应对复杂环 的方法都是建立在信息完全已知的前提条件下的. 境的能力；国内的学者柳长安等6]在对已有仿真足球 足球机器人在进行比赛时，虽然场地的信息及周围 机器人协作防守战术分析研究的基础上，运用合作 的环境信息是可以通过视觉系统完全已知，但是由 人博弈理论对防守战术进行分析研究，提出了一种基 于局势的动态变化导致敌方的信息无法直接获取. 于合作4人博弈的足球机器人协作防守对策，并建立 随着博弈理论的演化和发展，不完全信息博弈理论 了数学模型，最后通过仿真实验验证了其正确性和有 的应用对常规的方法是很好的补充和优化. 效性；王云等刀在协调博弈信念形成过程的基础上， 利用智能体策略相似性，提出换位推理的协调博弈学 收稿日期：2010-04-15. 基金项目：陕西省自然科学基金资助项目(2009M8002) 习方法，通过信念修正模型将客观观察行为和主观预 通信作者：史晓茹.E-mail:xiaoru.girl@163.com 测行为结合在一起，从而能取得更好的协调性能：宋
·148 智能系统学报 第6卷 明鑫等人[8]将典型的“囚徒困境”博奔模型应用在机 完全信息博弈的相关理论与方法来进行分析。 器人比赛的策略对抗中，但是这些模型的应用都是以 2.1不完全信息博弈模型建立 信息是完全已知为前提的.本文针对机器人比赛时信 机器人的视觉系统可以感知到周围的场地环 息的不完全性，探讨了将豪尔绍尼转换和贝叶斯均衡 境，且假设感知得到的这些信息都是准确的，即能够 相融合的不完全信息博弈理论，该理论通过引入虚拟 保证局部信息完全可知.在实际的比赛中，机器人不 的参与者，使得机器人所选择的保守决策点范围缩 仅仅要根据周围的场地信息，还要依据敌方机器人 小，从而可以有效地提高机器人比赛时对未知信息的 的决策动作信息，进行综合的分析推理后，从而得到 推理能力。 自己的决策动作信息， 在某场足球机器人比赛中，假设视觉系统传递 1不完全信息博弈理论 的场地环境信息是可靠的，且参与者为我方和敌方 定义1不完全信息.不完全信息博弈理论中 2队，即局中人N={1,2},并将某个局中人i之外 的不完全信息专指一种博弈局势中，人对其他局中 的其他局中人称为“i的对手”，记为-i.机器人比 人（或者他自己）与该种博弈局势有关的事前信息 赛决策博奔局势：局中人1要根据自己对场上形势 了解不充分.这里的事前信息是指关于在博弈实际 和局中人2的判断，决定自己是否踢球；局中人2要 开始之前局中人所处地位或者状态的信息，这种地 根据自己对场上形势和局中人1的判断，决定自己 位与状态对于博弈局势会产生影响[9o] 是否控球；局中人2的局势为在“进攻”状态下控球 定义2贝叶斯均衡.局中人具有类型0：∈⊙：， 与不控球和在“防守”状态下控球与不控球；局中人 策略：∈S:及支付函数4，类型上先验分布为p的 1决定是否踢球，而同时局中人2决定是否控球这 不完全信息博弈中的纯策略贝叶斯均衡是一种“扩 里只分析局中人1该做出何种决策，对其分析得出 充”博弈的纳什均衡，这种扩充博弈中每个局中人。 如表1所示的不完全信息博弈局势模型。 的纯策略空间是有⊙：到S:的映射的集合S 表1机器人比赛博弈模型 豪尔绍尼转换的思想：在理论上，各类不完全信 Table 1 The robot competition game model 息在博弈分析中都可以转换为一种不完全信息情 进攻支付矩阵 防守支不付炬阵 局中人1 势，即局中人对其他局中人的支付函数的不完全了 踢球不踢球 踢球不踢球 解.豪尔绍尼理论中，博弈的不完全信息表现为对博 扇 控球/% (3020) (4010) (4020)(9010) 弈的基本的数学结构的了解不充分，在策略型博弈 不控球/%(7020)(5050)(7020)(705) 中，也就是对于3种组成部分，即局中人、策略和支 付有着不完全了解.豪尔绍尼转换的主要思路是以 上述不完全信息引起了局中人1决策的困难， 类型概念构造对不完全信息的描述，在此基础上构 即是否进行踢球或者不踢球.利用划线法求得上述 造统一的概率模型来描述局中人在博弈中对不完全 比赛博弈模型的纳什均衡点：如果局中人2在进攻 信息的处理，从而将不完全信息转换为不完全信息 状态下，那么惟一的纯策略纳什均衡是，局中人1不 的完全信息博弈 踢球，局中人2不控球，即(50%50%)：如果局中人 贝叶斯理论求解转换后的博弈局势，即首先按 2在防守状态下，那么惟一的纯策略纳什均衡是，局 照概率分布P(01,02,…,0n)随机抽取选择类型向 中人1踢球，局中人2不控球，即(70%20%).所 量(81,02，…，0n),每个局中人知道自己的实际类 以，当机器人进行比赛时，2个局中人当时所处的状 型，但不知道其他局中人的实际类型，每个局中人选 态对比赛的结果起着一定的调控作用，它们分别对 择自己的策略，并且得到自己的支付. 应着不同的均衡结局.因此，局中人需要对自己所不 能确知的任何信息做出主观判断，并在此基础上决 2 基于贝叶斯均衡不完全信息博弈机 定自己的应该采取的行为以避免盲目“猜测”而导 器人对抗决策方法 致比赛的失败.在上述的不完全信息博弈中，并非所 有人都知道同样的信息，除了均知道的公共信息外， 局中人各自具有自己的私有信息.于是在进行策略 在完全信息博弈中，全体参与人都知道博弈的规 选择的时候，局中人需要对其他局中人的私有信息 则，否则这一博弈就是一个不完全信息博弈.一个不 进行判断，并依此进行相应的策略选择。 完全信息博弈，经过豪尔绍尼转换就变成一个完全但 在不完全信息博弈模型中，局中人知道其他局 不完美信息博弈，对这个转换形成的博弈就可以利用
第2期 史晓茹，等：不完全信息博弈的机器人对抗决策 ·149 中人的实际类型为若干可能类型中的一种，但不知 时，对局中人2的主观判断为局中人2为“进攻”的 道究竟是哪一种，只能在猜测的基础上选择自己的 概率为20%，为“防守”的概率为80%.类似的也可 策略 以有局中人2对局中人1类型的判断.在这种概率 为了描述这种主观判断，贝叶斯博弈理论利用 模型中，由于联合概率分布为各个局中人均知道的 贝叶斯理性原则来描述这种不确定情形下人们的理 公有信息，这种形成主观判断的机制也为所以局中 性行为.贝叶斯博弈理论假设局中人的类型{0：}1 人了解，所以局中人知道其他局中人的主观判断的 来自于一种类型上的联合概率分布p(01,02,…, 方式以及相应的结果， 日)，这种联合概率分布是局中人的共有信息，且比 2.2不完全信息博弈模型的转换 赛双方对这种共有信息都是已知的.这种联合概率 在概率模型的基础上，就可以通过豪尔绍尼转 分布是已知的，然后各个局中人在此基础上形成对 换将不完全信息博弈局势转化为不完美信息博弈局 其他局中人实际类型的概率判断，即局中人在知 势.其中引入“自然”这一虚拟局中人，所以局中人 道自己的实际类型为0，的情况下对对手类型形成 的实际类型均来自于“自然”根据类型上的联合概 的条件概率分布p(0:10),按贝叶斯推断即为 率分布进行的一种初始抽彩，局中人根据这种抽彩 p(0-l0)/p(0:).假设局中人1（我方）和局中人2 决定自己对其他局中人类型的主观判断，然后局中 (对方)均具有2种可能的类型：“防守”和“进攻”. 人进行实际博弈.豪尔绍尼转换将不完全信息博弈 现在引入上述不完全信息博弈的贝叶斯均衡概率模 转化为不完美信息的完全信息博弈后，就可以利用 型，其中概率分布如表2所示. 完全信息博弈的处理方法.上述的足球机器人比赛 表2联合概率分布 不完全信息博弈的豪尔绍尼转换如图1所示.在此 Table 2 Joint probability distribution % 博弈树中，有一个初始节点先于其他节点，记为 类型 进攻 防守 “O”,表示博奔的起点.为了博弈树的清晰起见，通 进攻 30 20 过引入虚拟自然局中人的“行动”建立惟一的初始 防守 10 40 节点；并且，除了初始节点之外，博弈树中的每一个 节点有且仅有一个直接前列节点；没有后序节点的 根据这一联合概率分布，就可以知道每个局中 节点被称为终止节点，表示博弈的可能结局，从而达 人在不同情况下对其他局中人实际类型的概率推 成博弈的一种结局.非终止节点的节点被称为决策 断.如果局中人1为“进攻”类型，那么它对局中人2 节点，非初始节点的决策节点用黑圆点表示。 的类型判断依据贝叶斯推断原则有局中人2为“进 豪尔绍尼转换将不完全信息博弈转换为了不完 攻”类型的概率为 美的信息扩展博弈，针对图1所示的不完美信息博 p(0,0-) 30% p(0) =309%+20% =60%】 弈，利用贝叶斯均衡可以将其转化为策略型博弈，即 求得不完全信息博弈树的解。 同理，局中人2为“防守”类型的概率为20%/ (30%+20%)=40%;而当局中人1为“防守”类型 0.4 0.6 控球 不控球 控球 不控球 踢球 不踢球 踢球 不、易 踢球 不踢球 踢球 不踢球 (40%20%)(90%10%)(70%20%)(70%5%)(30%20%)(40%10%)(70%20%)(50%50%) 图1经豪尔绍尼转换后的机器人博弈树 Fig.1 Robot game tree after Harsanyi conversion 2.3机器人博弈树求解 (s(01),s2(02),…,sm（0n)),其中每个局中人i 贝叶斯均衡是一种与类型有关的策略组合 在给定自己类型0：和其他局中人策略s:(0-:)的
·150 智能系统学报 第6卷 情况下最大化自己的期望效用函数.即 息不确定性问题提供了一种解决方案， s(0:)∈arg,max∑p(0.l0) 本文利用Matlab软件对机器人的决策优化问 题进行仿真.基本的仿真环境设计：在二维平面中， 4(s,s(0),(0,0-)) 系统运行的工作环境中的不同位置点表示不同的决 式中：山，（σ）=∑s[Π=1o,（(sy)]4(s)为与类型组 策命令，这些决策命令点是已知的，用“*”表示； 合有关的局中人支付函数；P(0:l0:)为局中人对其 “一”表示博弈选择的结果，直线穿越的决策点就是 他局中人类型的概率判断.利用上面的贝叶斯均衡 机器人要选择的决策点，即这些决策点都是对比赛 可以得到豪尔绍尼转换后的不完美信息博弈树的 的结果有利的决策点.任务要求机器人根据采集到 解，进而得到与不完全信息博弈局势等价的扩充博 的周围环境及敌方的信息推理分析后，从所有的决 弈局势如表3所示. 策命令集中选择出最有利的决策，并传送给机器人 表3对应的扩充博弈局势 执行命令，图2是机器人某次比赛的博弈局势，直接 Table 3 The corresponding expansion game situation 求其博弈局势的纳什均衡点，选择出了4个决策点； 局中人1 局中人2 图3是对同样的博弈局势进行豪尔绍尼转换和贝叶 踢球 不踢球 斯相融合的不完全信息博奔转换推理后，所得到的 (控球控球) (0.340.2） (0.60.1) 2个决策点. (控球不控球) (0.580.2) (0.660.34) (不控球控球】 (0.4602) (0.20.2) 比较图2和图3可知，豪尔绍尼转换和贝叶斯 (不控球不控球) (0.40.4》 (0.580.32)】 相融合的不完全信息博弈算法在机器人比赛中的应 如表3利用划线法可以求得经过豪尔绍尼转 用比传统直接求解方法减小了2个决策点，提高了 换并进行贝叶斯推理后的博弈局势的纯策略纳什均 决策的精度.如果在决策点更多时，这种方法可以大 衡点为(（不控球控球）不踢球)，即(0.70.2).可 大的缩小有利决策点的的决策范围，从而进一步提 以看出，这一贝叶斯博奔的纯策略贝叶斯均衡有一 高在比赛中获胜的概率， 45 个，即无论局中人2是处于“进攻”状态还是“防守” ◆ 决策点 40 决策结果 状态，局中人1都选择不踢球，这样的决策保证了局 35 中人1不失利，也就是说选择了最保守的决策方式. 30 这种建模和求解方式给出了局中人1在2种类 到 25 型下的策略选择，括号内前者是局中人1在实际类 型为“进攻”时选择的策略，后者为局中人1为“防 15 守”时选择的策略.通过这种概率机制的引人，构造 10 了局中人对其他局中人主观判断的不确定性，形成 了对不完全信息的完整描述. 10 15 决策点X坐标 2.42种决策方式比较 图2未经过转换推理的博弈仿真 对于不完全信息给博弈局势带来的决策困难， Fig.2 Game simulation diagram before convert reasoning 选择了豪尔绍尼转换和贝叶斯相融合的博弈处理方 法，这样的处理简化了博弈决策的结果，直接对博弈 45 状况进行分析的结果有2种博弈均衡，就是对于局 40 +决策点 块策结果 中人2不同的状况，局中人1需进行不同的决策，即 35 踢球和不踢球而经过豪尔绍尼转换和贝叶斯推理 30 后，局中人1可以不用考虑局中人2的状况，选择最 25 20 保守的决策命令，即选择不踢球 3 仿真验证 10 博弈局势的建模和求解是一个复杂的过程，即 10 15 使是确定的双方，在不同的比赛局势中的攻守策略 次策点X坐标 也是不同的，豪尔绍尼转换和贝叶斯推理相融合的 图3转换推理前后仿真图比较 方法为解决机器人比赛中局势的动态变化引起的信 Fig.3 Game simulation diagram before convert reasoning
第2期 史晓茹，等：不完全信息博奔的机器人对抗决策 ·151· LIU Changan,WANG Jing,LIU Chunyang.The research 4结束语 on the defensive support of soccer robot based on four coop- 豪尔绍尼转换和贝叶斯博弈相融合的不完全信 erative game[J].Journal of System Simulation,2009,21 息博弈算法可以有效地拓宽有利决策点的选择范 (1):132-134. 围，其实际仿真效果与理论相符合.存在的问题是在 [7]王云，韩伟.对称协调博奔问题的多智能体强化学习 [J].计算机工程与应用，2008,44(36)：230234 决策过程中的豪尔绍尼转换是否会使机器人的决策 WANG Yun,HAN Wei.A multi-agent reinforcement learn- 变得复杂，如何在程序中将这种转换程序化、简单化 ing on symmetrical and reconciling game[J].Computer En- 是需要进一步进行研究的.不完全信息动态博弈理 gineering and Applications,2008,44(36):230-234. 论引人到机器人足球决策系统当中，具有很好的理 [8]宋明鑫.计算机技术在“囚徒困境”博奔中的应用[D]. 论意义和实际应用价值。 天津：天津大学，2006：23-25. SONG Mingxin.The application of computer technology in 参考文献： prisoner's dilemma game[D].Tianjin:Tianjin University, [1]王志红.Robocup中型组足球机器人决策系统的研究 2006:23-25. [D].济南：山东大学，2007：4. [9]黄涛.博奔论教程[M].北京：首都经济贸易大学出版 WANG Zhihong.The research on the decision-making sys- 社，2004：4549. tem of Robocup medium group soccer robot D].Ji'nan [10]李光久.博奔论基础[M].镇江：首都经济贸易大学出 Shandong University,2007:4. 版社，2008：98-100. [2]施卫强。基于强化学习的足球机器人决策系统设计 作者简介： [D].长沙：中南大学，2007：5. 史晓茹，女，1987生，硕士研究生， SHI Weigiang.The design on the decision-making system of 主要研究方向为控制理论与控制工程。 robot soccer based on Q leamning[D].Changsha:Central South University,2007:5. [3]徐心和，邓志立，王骄，等.机器博弈研究面临的各种挑 战[J].智能系统学报，2008,3(4)：288-296. XU Xinhe,DENG Zhili,WANG Jiao,et al.The challenges of machine game[J].CAAI Transactions on Intelligent Sys- 侯媛彬，女，1953生，教授，博士生 tems,2008,3(4):288-296. 导师，博士，主要研究方向为控制理论、 [4]BASILICO N.CATTI N.AMIGONI F.AMIGONI F.Lead- 系统辨识、人工智能与模式识别等。 er-follower strategies for robotic patrolling in environments with arbitrary topologies C ]//Proc AAMAS.S.1.] 2008:5764. [5]BEETZ M,BUCK S,HANEK R.The AGILO autonomous robot soccer team:computational principles,experiences, 张涛，男，1985生，硕士研究生，主 and perspectives[C]//Proc AAMAS,[S.L.]2009:805- 要研究方向为控制理论与控制工程 813. [6]柳长安，王静，刘春阳.基于合作4人博弈的足球机器人 协作防守模型研究[J].系统仿真学报，2009,21(1)： 132-134