二分图最佳匹配算法在中型组Robpcup角色分配中的应用|匹配算法

　　摘要：在中型组足球机器人的决策模型中，用状态自动机模型实现了Robocup中机器人各个角色的决策过程，形成了决策知识库。根据比赛场上的信息，调用知识库，利用二分图最佳匹配算法的思想来实现角色分配，提高队伍的成绩。
　　关键词：机器人足球；动态角色分配；二分图最佳匹配法；估值函数
　　中图分类号：TP342文献标识码：A文章编号：1009-3044(2012)21-5178-03
　　Application of the best Matching Algorithm of Binary Chart in Medium Group Robpcup Roles Assignment
　　XU Wen
　　(Information Engineering College of ShanDong Shenghan Finance and Trade Vocational College，Jinan 250316,China)
　　Abstract: In the medium group decision-making model of soccer robot, and using state automata model realized the Robocup in each role the decision making process of the robot, formed the decision knowledge base. According to the information on the pitch, invoked the knowledge base, using the best matching algorithm of binary chart of thought to realize the roles assignment, and improve the performance of the team.
　　Key words: robot soccer; dynamic roles assignment; the best matching algorithm of binary chart; evaluation function
　　机器人足球比赛是[1]人工智能和多智能体系统的一个典型的应用平台，正逐渐成为一个热门研究课题。它和人类足球比赛一样，是一个集体项目，无论一个机器人的能力再强，单靠一个人的力量是无法取得胜利的，这需要依靠团队的协作，才能更有效地完成比赛。但由于中型组比赛的动态性，不确定性，以及通信的限制，团队协作和配合的具体实现是有困难的。目前，实现协作的队伍大都是采用在比赛中转换角色的方法。文献[2]中的The RMIT United 2000队利用基于世界模型得到的信息构造启发函数的方法实现队员角色的分配；文献[3]中The CMU Hammerheads队采用划分各个角色占有区域，从而划分场地的方法实现角色转换；文献[4]中The ART 2000队定义了两个utility functions来评估角色实现角色转换。通过分析它们的算法，结合自己队伍的特点，通过二分图最佳匹配算法的思想完成了场上角色的分配，从一定意义上实现了全局利益的提高。避免了机器人各自为战，在同一时刻每个机器人做出同样的决策和动作，而一些角色没人去承担，比较典型的就是除守门员外其他的机器人都担任前锋的角色去抢球，场面混乱，从而导致无人防守的情况。
　　 1二分图最佳匹配算法的描述
　　数学模型[5]：设G=(V,E）是一个无向图。如顶点集V可分割为两个互不相交的子集V1,V2之并，并且图中每条边依附的两个顶点都分属于这两个不同的子集。则称图G为二分图。二分图也可记为G=(V1,V2,E）。给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。
　　在一个二分图内，两个不相交集合X和Y，现对于集合连接XiYj有权wij，求一种匹配使得所有wij的和最大，即二分图最佳匹配。
　　Kuhn－Munkras算法基本原理：
　　该算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A[ i ]，顶点Yj的顶标为B[ j ]，顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻，对于任一条边(i,j)，A[ i ]+B[j]>=w[i,j]始终成立。
　　算法流程：
　　1)初始化可行顶标的值；
　　2)用匈牙利算法寻找完备匹配；
　　3)若未找到完备匹配则修改可行顶标的值；
　　4)重复2)、3)直到找到相等子图的完备匹配为止。
　　 2算法应用的基础
　　在中型组中，场外的电脑作为服务器，放置全局信息，机器人之间只是简单的点对点通讯来传送简单的命令，每个队员都有自
　　己的视觉信息，所以角色分配方法实现的条件：机器人之间必须能和存储所以机器人信息的服务器正常通讯，从而保证最新的信息被存储。带有全景，近景摄像头且完全自主的机器人个体，在硬件构造上四个机器人完全一样，程序的设计也是一样，即任意的机器人都具备担任任意的角色的能力。
　　由于足球场上的环境时刻在变化，如果采用固定角色的队形，即每个机器人从比赛开始一直担任一种角色，即使在某一时刻该机器人更适于担任别的角色的情况下也不能去担任，这样会丧失很多好机会，比赛的成绩也要受影响。基于此弊端的情况，综合考虑中型组机器人的特点，完全自主，带有全景摄像头来获得场上球门，队友，球的信息，所以在比赛中充分利用队员已知道的信息，把任务分给最适于担当的队员，获得目标的最优结果，采用实时动态分配角色的方法。
　　机器人足球比赛角色和人类足球一样分为前锋，助攻，后卫，守门员等，前锋负责进球，助攻把球传给前锋，后卫帮助守门员防守，同时可以传球给前锋或者助攻的队员,衔接中场和后场…。在目前球员从视觉上（我们的队没实现）不能识别队友的情况下，为了避免队友之间的互相抢球而造成冲突，首要的就是保证同一时刻一个角色不能由两个队员同时担当，而且同一时刻一个队员不能担任两个不同的角色。
　　在算法中，为了表示完成某个角色的能力值，引入角色能力估值函数对每个角色进行估值作为权值，函数f1(),f2(),f3(),……，分别用来计算担任不同角色的能力值，用这些值来表示机器人胜任此角色的能力。估值函数的构造与以下因素有关，这些因素都可以从机器人视觉信息中得到数值[6],各因素见下图1：
　　第二步：构造机器人集合R={R1,R2 ,R3…},角色集合Y={r1,r2,r3…},利用第一步所计算的权值以及R,Y构造加权完全二分图G，其中节点集V(G)被分为R和Y两部分，这些数据构成了利用KM算法的条件，对这些数据使用KM算法，就能求出最佳的匹配。
　　利用二分图匹配算法进行的分配，保证了机器人和角色之间的最佳对应关系，使每个角色的能力都能得到充分发挥，在比赛场上每个机器人通过场上的实时环境转换，从而担任自己最擅长的角色，更好地完成比赛。图3前锋和助攻队员进攻图
　　如上图3，通过计算估值函数，知道在图中，助攻队员的位置相比于此时的前锋角色，具有比助攻队员更多的优势：离球近，离球门近，且球，球门和此机器人在一条直线上。鉴于此，可改变它们在比赛中的角色，利用动态的分配角色算法，助攻队员和前锋交换角色继续比赛，这样能根据场上的实时情况更好地发挥队员的各自优势，实现场上的配合来完成比赛。如果不交换角色，此时的前锋并不适合前锋的角色,就会浪费了得分的机会。这正是比赛中角色固定不变的缺陷,也更能体现动态分配角色的灵活性。
　　该文在经过实际测试后，改变了传统机器人足球比赛固定角色的方法，在通讯能保证的情况下，运用二分图最佳匹配算法来实现中型组机器人足球比赛中的角色分配，此算法提高了队伍的灵活性，但是由于算法的时间占用，以及视觉信息的误差造成的计算错误，发挥算法结果的延迟性，都能影响机器人的发挥，在以后的工作中还需要进一步的改进。