人机博弈（共3篇）
人机博弈 篇1
卷首语EN企TERPR业ISER改EFOR革MANDM与ANAG管EME理NT
人机博弈
富士康注定就是一口高产的新闻油井, 即使在今年“十一”长假期间, 仍然“井喷”不已。
10月6日, 据美国非营利性机构“中国劳工观察”网站报道, 富士康郑州工厂周五发生罢工事件, 约有3000至4000名工人参与了罢工。他们担心这将影响i Phone5的产量。随后, 富士康对该报道予以否认, 但同时也承认, 当天郑州园区确实发生员工纠纷事件, 约有三四百名员工缺勤。
富士康在中国大陆的声名鹊起, 似乎总是与负面新闻有关。最早是人命攸关的“十三连跳”, 之后是中原逐鹿的“招工补贴门”, 后来是严重侵犯劳工权利的“血汗工厂风波”。再加上这次因厂方单方面提高质检标准而引发的“罢工事件”, 富士康的HRM短板由此暴露无遗。
富士康是一家拥有120万名员工的庞大制造帝国, 员工人数甚至超过许多大城市的人口总量, 出现一些劳资纠纷本来是一件十分正常的事情。让富士康管理层非常纠结的是, 随着劳资纠纷频次和规模的不断扩大以及劳动力市场价格的不断攀升, 为了改善企业的负面形象, 增强薪酬的外部竞争性, 企业虽然多次提升员工的工资水平, 但是仍然无法遏止劳资矛盾的不断升级。也许正是这种纠结促使富士康开始另辟蹊径。
去年7月, 富士康董事长郭台铭在深圳公司的一场晚会上透露, 公司将实施百万机器人战略, 即在3年后, 公司的机器人规模将达100万台。这一宏伟规划自然引起了人们的高度关注。特别是由于百万机器人的数量与富士康的员工总数大体相当, 因此许多人猜测, 富士康的新战略实质上就是一个机器人取代人的战略。
用机器人代替人类进行生产劳动, 这是人类的一大梦想。富士康或许会成为实现这一梦想的先驱, 但前提是它必须在这场人机博弈中找到新的平衡。
本刊编辑部
二零一二年十月
人机博弈中评估函数的研究 篇2
关键词：人机博弈,评估函数,LMS算法
0、引言
在人机博弈中, 机器会根据当前局面, 基于博弈搜索的算法在当前所有走法中作出一个最佳选择。机器的智能体现在两个方面:一是其搜索未来局面深度的能力;二是其对局面的评估能力。从理论上讲, 如果机器针对每一步走法都能对未来局面进行无限的搜索, 直到最后分出胜负的局面, 那么对局面的评估就仅仅转变成了对胜负的判断, 从而评估局面就不是什么需要解决的难点问题。但在实践中, 由于计算机的运算速度和资源的有限, 无限的搜索后继局面是不可能实现的。当搜索深度加深到一定程度时, 机器每走一步棋所用的时间就将慢到使人无法接受的地步。因此, 在实践中往往是让机器搜索到可以接受的深度, 然后对形成的局面作出优劣的评估, 从而使机器知道如何走子才能在未来得到好的优势。然而, 要对一特定的局面作出合理的具体的评估 (给定一个具体的得分数) 并不容易, 面对千差万别的棋盘局面, 即使是专业棋手也很难用一个具体的分值去衡量它。因此, 各种评估函数算法应运而生。本文将讨论其中三种评估函数:静态评估函数;基于LMS的线性评估函数以及基于BP人工神经网络的评估函数, 以及如何将后两种评估函数应用于博弈程序中。
1、静态评估函数
所谓静态评估函数是指对任何一局面, 根据人在某种棋类中长期研究的经验抽取局面中与棋局优劣相关的各个特征, 然后根据经验为每一个特征给于一个不变的分值。对机器有利的特征给予正值, 对机器不利的给予负值。对局面影响较大的特征给予相应较大的分值, 对局面影响较小的特征给予相应较小的分值。可以将静态评估函数形式化为:用xi表示各个特征, 用wi表示每个特征的分值 (也称为权值) , 用y表示最后的得分。那么通过静态评估函数针对某一局面得到的最后分数即为:
我们可以看出, 此函数其实是一个线性的函数, 而且这个线性的评估函数一旦确定 (即各权值wi确定) 就不可以再改变, 因此被称作静态评估函数。
2、基于LMS算法的线性评估函数
与静态评估函数一样, 基于LMS算法的线性评估函数同样可以形式化为公式 (1) 。其中xi, wi, y的含义与静态评估函数一致。此评估函数与静态评估函数的不同之处再于它不是一个不可改变的函数, 而是在每盘棋局结束之后, 通过LMS算法重新改变权值wi, 以通过不断的学习来获得一个不断改良的线性函数。
2.1 LMS算法[1]
LMS算法又叫增量算法或最小均方算法。它是一个有教式的学习算法, 所谓有教式即为每个训练样例提供学习的目标。因此, 训练样例和学习目标是一一对应的。我们可以将其形式化为〈b, ytrain (b) 〉, b表示向量〈x1x2, …, xn〉即特征的集合, n为特征的总数。ytrain (b) 表示学习的目标值, 将在2.2节中介绍。并使用y (b) 表示当前对此训练样例根据公式 (1) 所得到的实际值, γ表示学习率, 那么通过LMS算法更新权值的算法为:
γ是一个小的常数 (比如0.1) , 用来调整权值的更新幅度。为了直观理解这个算法, 当[ytrain (b) -y (b) ]等于0时, 也就是说当前实际值与训练目标值一致, 那么权值不需要更新, 当[ytrain (b) -y (b) ]大于0时, 也就是说当前实际值比训练目标值小, 每一个权值会根据其对应的特征值增加一定的比例, 这样会提高y (b) 的值, 从而接近目标值。当[ytrain (b) -y (b) ]小于0时, 也就是说当前实际值比训练目标大, 每一个权值会根据其对应的特征值减小一定的比例, 这样会使Y (b) 的值减小, 从而接近目标值。还有一点需要说明的是, 当xi为0时, wi永远不会被更新, 这也就是说只有那些在训练样例中的特征的权值才会被更新。
2.2 算法在博弈中的应用
首先随机生成各个权值wi。对于一盘已结束的棋局, 我们可以用b1, b2...bn来表示各个局面, 其中b1表示双方都还未走子的局面, b2表示双方各走一子后的局面, 依次类推, bn表示棋局结束后的局面。对于最终的局面是很好给出目标值ytrain (b) , 因为胜负已分。比如当机器胜利给予100分, 当机器失败给予-100分, 但对于中间局面的目标值ytrain (b) 给分就不是太容易了。因为一盘棋的的最终胜负未必能说明这盘棋的中间局面的好坏。有一种方法在实践中可以取得良好的效果。这种方法是把任何中间棋局b的目标值:
Successor (b) 表示b的后继局面, 例如b2的后继局面是b3, 依次类推。y (Successor (b) ) 的值表示后继局面的当前评估值。凭直觉我们可以知道, 越是接近棋局结束, y (Successor (b) ) 就越趋向精确, 因此, 在大量次数的博弈对局后, y (Successor (b) ) 就能够非常完美的收敛到ytrain (b) 。有了各个局面的目标值ytrain (b) 后, 我们就可以对每一盘结束的棋局从bn开始生成前面各个局面的〈b, ytrain (b) 〉, 然后按照公式 (2) 针对每个局面更新权值wi。
虽然此算法和静态评估函数一样基于了线性的评估函数, 但由于基于LMS算法来对各个权值进行更新, 使得此线性函数不再是一成不变的, 它可以不断的针对每盘棋局进行自我学习, 不断优化自己。
3、基于BP人工神经网络的评估函数
与前两种评估函数不同, 基于BP人工神经网络的评估函数是一种基于非线形函数关系的评估函数。其函数的形式是通过网络来表示的。如图1所示, 一个BP人工神经网络可以有多个输入和多个输出。整个网络由多层神经元组成, 最后一层为输出层, 中间为隐藏层。每层中的每个神经元都连接着前一层所有神经元的所有输出, 并将自己的输出连接到下一层中的每个神经元。与前两种评估函数不同, 基于BP人工神经网络的评估函数是一种基于非线形函数关系的评估函数。其函数的形式是通过网络来表示的。如图1所示, 一个BP人工神经网络可以有多个输入和多个输出。整个网络由多层神经元组成, 最后一层为输出层, 中间为隐藏层。每层中的每个神经元都连接着前一层所有神经元的所有输出, 并将自己的输出连接到下一层中的每个神经元。
如图2所示, 每个神经元有n个输入, 一个输出, 每个输入都有一个权值与之对应。输入和输出的关系可形式化为:
如图3所示, sigmoid函数的输出范围为0到1, 随输入单调递增。因为这个函数把非常大的输入值域映射到一个小范围输出, 它也经常被称为sigmoid挤压函数。
因此, 当确定了网络的层数和每层中神经元的个数, 那么整个网络结构就确定了。因此可以通过大量的训练样例来不断训练网络 (更新所有权值) 直到与目标的误差达到可接受的范围。
3.1 BP学习算法[1]
BP学习算法又称反向传播学习算法。它也是一个有教式学习算法。由于BP人工神经网络可以有多个输出, 与LMS算法有所不同, 它的训练样例形式化为〈b obj〉, 其中b表示一个局面的特征向量〈x1, x2, …, xn〉, ob表示对应目标值向量〈Ytrain1, Ytrain2, …, Ytrainn〉。我们再做如下形式化:γ表示学习率, nin表示网络输入数量nhidden表示隐藏层单元数, nout表示输出单元, xji表示从单元i到单元j的输入, wji表示从单元i到单元j的权值。整个算法的流程步骤描述如下:
1.创建具有nin个输入, nhidden个隐藏单元, nout个输出单元的网络
2.初始化所有的网络权值为0到1之间的随机数
3.当遇到终止条件前:
对于训练样例中的每一个<b, obj>
1) 把输入b沿网络传播计算出每个单元u的输出ou
2) 对于网络中每个输出单元k, 计算它的误差项:δk=ok (1-ok) (objk-ok)
3) 对于网络的每个隐藏单元h, 计算它的误差项:δh=oh (1-oh) ∑wkhδk
4) 更新每个网络权值:wji=wji+γδjjix
终止条件为对所有的训练样例的每一个输出值和目标值的误差达到可接受的条件, 因此会对多次使用同样的训练样例。
3.2 算法在博弈中的应用
把基于BP人工神经网络评估函数应用到博弈系统中的方法与前面介绍的基于LMS算法的评估函数在博弈系统的应用基本上是一样的。所不同的是评估函数的形式不再是直接给出, 而是通过人工神经网络来表示的。因此首先应该建立适当规模的人工神经网络。作为参考, 可以将局面的所有特征作为网络的输入, 使用一层隐藏层和两个输出单元, 用两个输出单元的差值作为评估值 (范围从-1到1) 。还有一点需要说明, 在每结束一盘棋局后对BP人工神经网络的训练会反复多次直到终止条件。而基于LMS算法的评估函数的学习只需要进行一次。原因在于BP人工神经网络的权值收敛速度比较慢, 需要反复多次训练。
4、结束语
本文给出了3种在人机博弈中常用的评估函数。静态评估函数使用简单方便, 但要给出一个非常好的静态评估函数却非常难, 需要对某种棋类非常的熟悉, 即使如此也不一定能做到非常的精确;后两种评估函数最大的特点在于它们是可以自学习的, 并不需要对某种棋类有很深的了解, 而是在博弈的过程中不断自己改进自己。
参考文献
[1]Tom Mitchell.机器学习.北京:机械工业出版社, 2003.
基于合作博弈的多无人机任务研究 篇3
随着当今军事技术的发展与需求,将博弈论应用到军事领域中己受到国内外学者的广泛关注与研究[1,2]。文献[3]通过分析实际环境中信息的不确定性,提出了不确定信息情况下解决多无人机任务分配的问题。文献[4]提出一种分布式通信决策模型,利用卡尔曼滤波算法对无人机局部观测信息进行滤波处理,当局部任务分配结果与当前执行的跟踪任务产生冲突时,无人机发出通信信息,实现局部信息共享,从而达到信息的一致;在不确定条件的环境中,实时有效的动态任务分配是多无人机顺利完成对地攻击任务的关键点。文献[5]基于拍卖机制原理提出了多无人机的动态任务分配算法,同时也有文献[6]基于动态博弈理论提出了攻防双方目标武器分配方法。而以无人机攻防为背景,建立基于不完全信息的无人机攻防对抗动态博弈模型,利用免疫进化算法[7]求解出贝叶斯纳什均衡,得到了无人机的最优策略序列。文献[8]建立了基于Agent协商的多无人机任务分配模型,构建了无人机编队中资源管理和任务管理等两种Agent角色,并建立了两种角色之间任务分配协商协议,既有效地保证了个体Agent的自主性,又最大限度地发挥了多Agent之间的合作性。文献[9]针对异构多无人机协同任务分配问题,提出了一种基于改进的遗传算法的多UAV任务分配方法。
需要指出的是,虽然国内外在多无人机作战博弈中已经取得了一些很有价值和意义的研究成果,但目前已有的博弈方法大部分的研究集中于非合作博弈问题,没有考虑到多无人机合作博弈问题。而在实际网络环境中,为了提高作战效能,尤其是进攻重要目标的时候,需要考虑多无人机如何进行联盟合作问题,以提高整体的作战效益[10]。因此,如何在实际作战中考虑我方多无人机合作博弈问题,求解合作博弈的纳什均衡值问题,这是一个新的重要研究课题。
基于此,本文将多无人机合作联盟考虑为合作博弈问题,实现整体联盟收益最大化,提高多无人机整体执行任务的收益。在实际情况中,无人机之间的通信常会受到传输速度、网络拥塞等因素的影响而存在通信延迟。因此,本文将考虑存在通信延迟时,根据多无人机信息传输的过程,建立多无人机合作联盟博弈模型,给出合作博弈的求解方法,并动态分析联盟结构的变化情况。
1 无人机合作博弈模型的建立
1.1 合作联盟的基本概念
无线通信网络中,联盟中的无人机集合表示为N={1,2,...,n},对任意S⊆N,称S为N的一个联盟。Γ={S|S⊆N}为联盟集合,其中联盟集合Γ元素的个数为2n,特殊情况,允许取S=Φ和S=N,后一种情况称为一个大联盟。对于无人机系统,自主无人机之间能以通信的方式传递状态信息,侦察无人机检测到关于任务的信息后,选择传递信息至周围的无人机,形成联盟,共同完成特定的任务。具体的多无人机合作联盟模型如图1所示。
1.2 合作联盟作战收益函数
收益是指无人机在合作联盟中最终所得或损失。考虑合作联盟收益指标为目标价值和代价指标,建立多无人机合作联盟的作战收益函数。
1)目标价值指标函数
在多无人机作战过程中,目标价值是首先考虑的一个重要指标。重点考虑侦察无人机的目标价值Ri(S),定义如下:
其中,di(S)为侦查无人机i∈S的数据包传送延时,di=di({i}),为侦查无人机i单独行动时的数据包传送延时,diTTL为数据包的生存时间值,|S|为联盟s中无人机的数目。
2)代价指标函数
代价指标是指侦查无人机给执行无人机的平均支付。侦查无人机i传送数据包到同-联盟中的执行无人机j的平均成本Ci(S),定义如下:
其中,ξij为侦察无人机i传送数据包到同-联盟中执行无人机j的平均成本,Pij为侦察无人机i与执行无人机j的相遇概率。
3)联盟合作收益函数
综合上述模型,可以得到侦察无人机i的收益函数Ui(S):
其中,α、β分别为目标价值和代价的非负权重系数。
2 无人机合作联盟求解
在这里,我们首先介绍联盟形成算法:
联盟形成算法通过比较联盟内无人机的收益,根据MergeSplit-Rule形成联盟。若无人机形成联盟后收益提高,则自组织形成联盟;反之无人机不参与联盟形成。Merge-Split-Rule定义如下[11]:
Merge Rule-联盟集合{S1,...,Sm},当无人机收益满足时,小联盟合并为大联盟,即:
Split Rule-大联盟,当无人机收益满足时,大联盟分裂为若干不相交小联盟,即:
无人机的通信距离为do,执行无人机在侦察无人机的通信范围内,称侦察无人机遇见执行无人机,任务在侦察无人机的通信范围内,称侦察无人机发现任务。侦察无人机与执行无人机形成联盟来完成任务。
假设仿真区域为2km×2km,任务均匀分布在区域内,水平间距和垂直间距均为400m,有4架无人机,其中第1架侦察任务,另3架执行任务,侦察无人机具有传感器,执行无人机具有相同的火力能力,以相同的10km高度和最大50km/h速度飞行。设定无人机的通信距离分别为50m、100m和200m,得出三种情况下侦察无人机发现任务和侦察无人机与执行无人机的相遇概率,如表1所示。
4架无人机,其中,无人机1为侦察无人机,无人机2、3和4为执行无人机,那么在网络中可能存在7种联盟结构:{1,2},{1,3},{1,4},{1,2,3},{1,2,4},{1,3,4},{1,2,3,4}。依据MergeSplit-Rule算法,无人机之间形成合作的联盟。根据以上概率,分别计算在各种联盟结构下的收益,如表2所示。从中可以看到,大联盟结构收益最大,即在这种情况下,所有的无人机选择形成{1,2,3,4}这种结构来共同完成任务并且在这种结构下获得的收益最大。
3 系统性能分析
当变化侦察无人机传送数据包到同-联盟中执行无人机的平均成本系数为ξij时,联盟结构进行动态调整,如图2所示。当代价在0~9范围内时,大联盟结构一直是最佳联盟结构,当超过9时,形成{1,3,4}这种结构较好,也就是说,无人机综合考虑合作的成本及获得收益,会形成这种联盟结构。
4 总结
本文通过联盟形成算法,分析多无人机执行任务,考虑侦察无人机传递信息到执行无人机的代价,以及无人机执行任务的通信延时,建立多无人机合作博弈模型,得出最佳联盟结构,获得最小通信延时,并在代价变化的情况下分析了系统性能。
参考文献
[1]Poropudas J,Virtanen K.Game-theoretic validation and analysis of air combat simulation models[J].Systems,Man and Cybernetics,Part A:Systems and Humans,IEEE Transactions on,2010,40(5):1057-1070.
[2]Mc Grew J S,How J P,Williams B,et al.Air-combat strategy using approximate dynamic programming[J].Journal of guidance,control,and dynamics,2010,33(5):1641-1654.
[3]陈侠,唐婷.不确定环境下多无人机动态任务分配方法[J].火力与指挥控制,2013,38(1):45-49.
[4]崔亚妮,任佳,杜文才.多目标跟踪下的无人机分布式通信决策模型[J].计算机仿真,2014,31(7):68-72.
[5]周小程,严建钢,谢宇鹏,等.多无人机对地攻击任务分配算法[J].海军航空工程学院学报,2012,27(3):308-312.
[6]马飞,曹泽阳,刘晖.基于纳什均衡的动态目标分配策略研究[J].现代防御技术,2010,38(6):81-84.
[7]惠一楠,朱华勇,沈林成.无人机攻防对抗不完全信息动态博弈方法研究[J].兵工自动化,2009,28(1):4-7.
[8]罗贺,王国强,胡笑旋,等.基于Agent的多无人机任务分配模型[J].火力与指挥控制,2014,39(7):22-26.
[9]王婷,符小卫,高晓光.基于改进遗传算法的异构多无人机任务分配[J].火力与指挥控制,2013,38(5):37-41.
[10]Virtanen K,Karelahti J,Raivio T.Modeling air combat by a moving horizon influence diagram game[J].Journal of guidance,control,and dynamics,2006,29(5):1080-1091.