《mdp在仿真2d中的应用初探》由会员分享，可在线阅读，更多相关《mdp在仿真2d中的应用初探（31页珍藏版）》请在金锄头文库上搜索。
1、章宗长 2008-11-24,MDP在仿真2D中的应用初探,动机 马氏决策过程(MDP) 运用MDP对仿真2D中的动态打法进行建模 实验结果 未来工作,主要内容,动 机,田忌赛马,出自史记卷六十五：孙子吴起列传第五，是中国历史上有名的揭示如何善用自己的长处去对付对手的短处，从而在竞技中获胜的事例。,田忌,诸公子,上等马,中等马,下等马,上等马,中等马,下等马,田忌,诸公子,下等马,上等马,中等马,上等马,中等马,下等马,RoboCup仿真2D(1),每场比赛开始前有18种不同的异构球员供教练选择。每种异构球员的Speed Max、StamInc、Kickable、Inertia、KickRan
2、d等参数不同。,18种异构球员在比赛前随机生成，每个异构球员各有特点，教练根据自己球队的风格从中选取11种异构球员参加比赛。,WrightEagle2D球队喜欢选取跑得快、体力好、可踢半径大的球员参加比赛。,选取好11种异构球员之后，教练会对每个异构球员的一系列重要参数加权，对加权的结果排序。数字越大，表示该异构球员的优先级越高。,RoboCup仿真2D(2),WrightEagle2D球队把给定优先级的异构球员放在球场指定的位置上。在RoboCup2008之前很长一段时间，这部分代码没有人修改过。也就是说，球队用同一打法和不同的对手（BrainStormers、Helios等）对抗。,3,8
3、,6,4,1,5,2,10,7,9,1,7,8,4,2,9,5,3,10,6,变换,数字代表:优先级,数字代表:球员号码,RoboCup仿真2D(3),今年RoboCup仿真2D与BrainStormers的两场比赛给了我们一个启示：一个球队的打法对比赛的结果有着非常关键的影响。以与BrainStormers的比赛结果为例，当我们以进攻型打法与他们交锋的时候，胜率不到10%；但当我们以防守型打法与他们交锋的时候，胜率却可以达到50%。但是，这样的状况在对Helios的比赛中却不会发生，也就是说，同样的打手在与不同的对手比赛的时候，结果是可以完全不同的。,现在WrightEagle2D球队采用手
4、工设置的方式，在和一个主要对手比赛之前，用几种不同的典型打法和对手打循环赛，选取测试结果最好的版本与对手进行比赛。整个比赛过程中打法保持不变。,存在的问题：如果对手比赛时的打法和先前测试程序中对手的打法不同的话，那么之前通过打循环赛得到的最好版本就没有意义了。,RoboCup仿真2D(4),能否在比赛一开始时采用一种比较通用的打法（或者就用测试时得到的最好版本对应的打法）与对手比赛，然后根据场上的形势来调整自己的打法，使得WrightEagle2D球队在每场比赛中的打法是动态的呢？,如何判断场上的形势？ 所谓场上的形势，指的就是我方11个球员和对方11个球员的类型、体力、位置、得分等信息。如果
5、把这些因素都考虑，那么问题会变得太复杂。最简单的方式就是用我方球队与对手球队当前的比分差来反映场上的形势。,按照怎样的原则来调整自己的打法？,通过 Markov决策模型 来调整自己的打法。,马 氏 决 策 过程,马氏决策过程,马氏决策模型是一个四元组，其中 S是状态空间； A是行动空间，表明每个状态下主体可以执行的行动，状态s下可执行的行动记为A(s); T: S X A X S -0,1是状态转换模型，T(s,a,s)表示在状态s下执行行动a到达状态s的概率，满足,R: S X A X S -R是即时回报函数，R(s,a,s)表示环境对主体 在状态s下执行行动a到达状态s的实值即时评价。,半
6、马氏决策过程(Semi-MDP,SMDP)中，每个行为动作的时间 间隔作为变量。,运用MDP对仿真2D中 的动态打法进行建模,状态空间,状态：用我方比分与对手比分之差来表示。不妨假设为： =5，初始状态为0。比分差反映了对手的强弱、风格和当前足球场上的局势（虽然这样做会显得有些笼统，但却是最简便的方式，正如POMDP中也是用b来反映历史信息的）。,状态可以进一步扩展。如，考虑我方和对手有威胁的射门次数、传球成功率、拦截球成功率等信息。,行动空间(1),行为：设置打法为防守型、折衷型、进攻型。,7,10,9,8,1,3,2,5,6,4,10,3,6,7,2,1,5,9,8,4,变换,数字代表:优
7、先级,数字代表:球员号码,防守型,行动空间(2),3,8,6,4,1,5,2,10,7,9,1,7,8,4,2,9,5,3,10,6,变换,数字代表:优先级,数字代表:球员号码,折衷型,行动空间(3),1,4,3,2,5,7,6,9,10,8,2,4,1,5,9,10,8,6,3,7,变换,数字代表:优先级,数字代表:球员号码,进攻型,行动可以进一步扩展。如，考虑左边路进攻型、右边路进 攻型等。阵型总共有10!种不同的组合方式。,状态转移概率函数(1),1、求在比赛中从状态i转移到状态j出现的总次数。,下图为：频率表 s0 s1 s2 s3 s4 s5 s6 s7 s8 s9 s10 s0 0
8、 0 0 0 0 0 0 0 0 0 0 s1 0 0 0 0 0 0 0 0 0 0 0 s2 0 0 0 1 0 0 0 0 0 0 0 s3 0 0 2 0 2 0 0 0 0 0 0 s4 0 0 0 13 0 11 0 0 0 0 0 s5 0 0 0 0 39 0 32 0 0 0 0 s6 0 0 0 0 0 6 0 8 0 0 0 s7 0 0 0 0 0 0 2 0 1 0 0 s8 0 0 0 0 0 0 0 0 0 0 0 s9 0 0 0 0 0 0 0 0 0 0 0 s10 0 0 0 0 0 0 0 0 0 0 0,以其中黄色加粗字体“13”为例， 表示的是从“我
9、方与对手球队的 比分差为-1”这个状态转移到“我 方与对手球队的比分差为-2” 这个状态共出现13次。这样， 在知道当前状态为s4，行动为 defensive策略的时候，转移到 状态s3的概率就是：13/(13+11)。 这些状态转移频率是在我方或对 方进球后，将矩阵中相应的元素 加1得到的。,状态转移概率函数(2),2、求得给定策略从状态i转移到状态j的概率。,下图为：给定策略的状态转移概率矩阵,即时回报函数,If 到达当前状态时比赛还未结束 then 给定行动a的即时回报 = E(下一状态我方比分与对手比分之差) 当前状态我方球队与对手球队的比分之差； else /到达当前状态时比赛结束
10、if 当前状态 0 then 即时回报 = 5; else if当前状态 = 0 then 即时回报 = 0; else /当前状态 0 即时回报 = -5; end if End if,马氏决策过程的值迭代算法,值迭代公式,这里给出的是三个阶段的Markov决策过程的求解结果。,我们马上会实现一个更实用的多个阶段的Markov决策过程。 这个决策过程与前面讲的那个过程的区别就在于：求解最优 策略时向前计算的步数视比赛的情况而定。例如：当前周期 数是2000，我方和对方各进1球，这种情况下求解最优策略 时向前计算的4步（6000-2000）/（1+1）。,实 验 结 果,不同策略下的统计结果,
11、Defensive策略的状态转移概率矩阵,变换,Balanced策略的状态转移概率矩阵,变换,Offensive策略的状态转移概率矩阵,变换,各阶段的不同策略的最优值函数(1),各阶段的不同策略的最优值函数(2),各阶段的不同策略的最优值函数(3),红色背景的状态对应的回报是-5,绿色背景的状态对应的回报是5,各阶段的不同策略的最优值函数(4),各阶段的不同策略的最优值函数(5),未来工作,1、修正当前算法设计中存在的问题，使得利用动态打法得到的测试结果好于任意一种利用单一打法进行比赛得到的测试结果。,2、扩展行动数和状态数，修正回报函数，使得设计的算法更趋于实用。,3、思考如何动态地确定在进行MDP求解时，需要求解的阶段数？,4、测试给定策略的状态转移概率矩阵是否是稳定的？能否在数学上给出证明。,5、思考并实验测试能够设计一组对所有对手都近似成立的状态转移概率矩阵？然后得到一个对所有对手都有效的MDP动态打法求解过程。,参考文献,1、Colin McMillen and Manuela Veloso, Thresholded Rewards: Acting Optimally in Timed, Zero-Sum Games,
