二分圖最佳匹配算法在中型組Robpcup角色分配中的應(yīng)用

徐雯

摘要：在中型組足球機(jī)器人的決策模型中，用狀態(tài)自動(dòng)機(jī)模型實(shí)現(xiàn)了Robocup中機(jī)器人各個(gè)角色的決策過程，形成了決策知識(shí)庫。根據(jù)比賽場(chǎng)上的信息，調(diào)用知識(shí)庫，利用二分圖最佳匹配算法的思想來實(shí)現(xiàn)角色分配，提高隊(duì)伍的成績(jī)。

關(guān)鍵詞：機(jī)器人足球；動(dòng)態(tài)角色分配；二分圖最佳匹配法；估值函數(shù)

中圖分類號(hào)：TP342文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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

機(jī)器人足球比賽是[1]人工智能和多智能體系統(tǒng)的一個(gè)典型的應(yīng)用平臺(tái)，正逐漸成為一個(gè)熱門研究課題。它和人類足球比賽一樣，是一個(gè)集體項(xiàng)目，無論一個(gè)機(jī)器人的能力再?gòu)?qiáng)，單靠一個(gè)人的力量是無法取得勝利的，這需要依靠團(tuán)隊(duì)的協(xié)作，才能更有效地完成比賽。但由于中型組比賽的動(dòng)態(tài)性，不確定性，以及通信的限制，團(tuán)隊(duì)協(xié)作和配合的具體實(shí)現(xiàn)是有困難的。目前，實(shí)現(xiàn)協(xié)作的隊(duì)伍大都是采用在比賽中轉(zhuǎn)換角色的方法。文獻(xiàn)[2]中的The RMIT United 2000隊(duì)利用基于世界模型得到的信息構(gòu)造啟發(fā)函數(shù)的方法實(shí)現(xiàn)隊(duì)員角色的分配；文獻(xiàn)[3]中The CMU Hammerheads隊(duì)采用劃分各個(gè)角色占有區(qū)域，從而劃分場(chǎng)地的方法實(shí)現(xiàn)角色轉(zhuǎn)換；文獻(xiàn)[4]中The ART 2000隊(duì)定義了兩個(gè)utility functions來評(píng)估角色實(shí)現(xiàn)角色轉(zhuǎn)換。通過分析它們的算法，結(jié)合自己隊(duì)伍的特點(diǎn)，通過二分圖最佳匹配算法的思想完成了場(chǎng)上角色的分配，從一定意義上實(shí)現(xiàn)了全局利益的提高。避免了機(jī)器人各自為戰(zhàn)，在同一時(shí)刻每個(gè)機(jī)器人做出同樣的決策和動(dòng)作，而一些角色沒人去承擔(dān)，比較典型的就是除守門員外其他的機(jī)器人都擔(dān)任前鋒的角色去搶球，場(chǎng)面混亂，從而導(dǎo)致無人防守的情況。

1二分圖最佳匹配算法的描述

數(shù)學(xué)模型[5]：設(shè)G=(V,E）是一個(gè)無向圖。如頂點(diǎn)集V可分割為兩個(gè)互不相交的子集V1,V2之并，并且圖中每條邊依附的兩個(gè)頂點(diǎn)都分屬于這兩個(gè)不同的子集。則稱圖G為二分圖。二分圖也可記為G=(V1,V2,E）。給定一個(gè)二分圖G，在G的一個(gè)子圖M中，M的邊集{E}中的任意兩條邊都不依附于同一個(gè)頂點(diǎn)，則稱M是一個(gè)匹配。如果一個(gè)匹配中，圖中的每個(gè)頂點(diǎn)都和圖中某條邊相關(guān)聯(lián)，則稱此匹配為完全匹配，也稱作完備匹配。

在一個(gè)二分圖內(nèi)，兩個(gè)不相交集合X和Y，現(xiàn)對(duì)于集合連接XiYj有權(quán)wij，求一種匹配使得所有wij的和最大，即二分圖最佳匹配。

Kuhn－Munkras算法基本原理：

該算法是通過給每個(gè)頂點(diǎn)一個(gè)標(biāo)號(hào)（叫做頂標(biāo)）來把求最大權(quán)匹配的問題轉(zhuǎn)化為求完備匹配的問題的。設(shè)頂點(diǎn)Xi的頂標(biāo)為A[ i ]，頂點(diǎn)Yj的頂標(biāo)為B[ j ]，頂點(diǎn)Xi與Yj之間的邊權(quán)為w[i,j]。在算法執(zhí)行過程中的任一時(shí)刻，對(duì)于任一條邊(i,j)，A[ i ]+B[j]>=w[i,j]始終成立。

算法流程：

1)初始化可行頂標(biāo)的值；

2)用匈牙利算法尋找完備匹配；

3)若未找到完備匹配則修改可行頂標(biāo)的值；

4)重復(fù)2)、3)直到找到相等子圖的完備匹配為止。

2算法應(yīng)用的基礎(chǔ)

在中型組中，場(chǎng)外的電腦作為服務(wù)器，放置全局信息，機(jī)器人之間只是簡(jiǎn)單的點(diǎn)對(duì)點(diǎn)通訊來傳送簡(jiǎn)單的命令，每個(gè)隊(duì)員都有自

己的視覺信息，所以角色分配方法實(shí)現(xiàn)的條件：機(jī)器人之間必須能和存儲(chǔ)所以機(jī)器人信息的服務(wù)器正常通訊，從而保證最新的信息被存儲(chǔ)。帶有全景，近景攝像頭且完全自主的機(jī)器人個(gè)體，在硬件構(gòu)造上四個(gè)機(jī)器人完全一樣，程序的設(shè)計(jì)也是一樣，即任意的機(jī)器人都具備擔(dān)任任意的角色的能力。

由于足球場(chǎng)上的環(huán)境時(shí)刻在變化，如果采用固定角色的隊(duì)形，即每個(gè)機(jī)器人從比賽開始一直擔(dān)任一種角色，即使在某一時(shí)刻該機(jī)器人更適于擔(dān)任別的角色的情況下也不能去擔(dān)任，這樣會(huì)喪失很多好機(jī)會(huì)，比賽的成績(jī)也要受影響?；诖吮锥说那闆r，綜合考慮中型組機(jī)器人的特點(diǎn)，完全自主，帶有全景攝像頭來獲得場(chǎng)上球門，隊(duì)友，球的信息，所以在比賽中充分利用隊(duì)員已知道的信息，把任務(wù)分給最適于擔(dān)當(dāng)?shù)年?duì)員，獲得目標(biāo)的最優(yōu)結(jié)果，采用實(shí)時(shí)動(dòng)態(tài)分配角色的方法。

機(jī)器人足球比賽角色和人類足球一樣分為前鋒，助攻，后衛(wèi)，守門員等，前鋒負(fù)責(zé)進(jìn)球，助攻把球傳給前鋒，后衛(wèi)幫助守門員防守，同時(shí)可以傳球給前鋒或者助攻的隊(duì)員,銜接中場(chǎng)和后場(chǎng)…。在目前球員從視覺上（我們的隊(duì)沒實(shí)現(xiàn)）不能識(shí)別隊(duì)友的情況下，為了避免隊(duì)友之間的互相搶球而造成沖突，首要的就是保證同一時(shí)刻一個(gè)角色不能由兩個(gè)隊(duì)員同時(shí)擔(dān)當(dāng)，而且同一時(shí)刻一個(gè)隊(duì)員不能擔(dān)任兩個(gè)不同的角色。

在算法中，為了表示完成某個(gè)角色的能力值，引入角色能力估值函數(shù)對(duì)每個(gè)角色進(jìn)行估值作為權(quán)值，函數(shù)f1(),f2(),f3(),……，分別用來計(jì)算擔(dān)任不同角色的能力值，用這些值來表示機(jī)器人勝任此角色的能力。估值函數(shù)的構(gòu)造與以下因素有關(guān)，這些因素都可以從機(jī)器人視覺信息中得到數(shù)值[6],各因素見下圖1：

第二步：構(gòu)造機(jī)器人集合R={R1,R2 ,R3…},角色集合Y={r1,r2,r3…},利用第一步所計(jì)算的權(quán)值以及R,Y構(gòu)造加權(quán)完全二分圖G，其中節(jié)點(diǎn)集V(G)被分為R和Y兩部分，這些數(shù)據(jù)構(gòu)成了利用KM算法的條件，對(duì)這些數(shù)據(jù)使用KM算法，就能求出最佳的匹配。

利用二分圖匹配算法進(jìn)行的分配，保證了機(jī)器人和角色之間的最佳對(duì)應(yīng)關(guān)系，使每個(gè)角色的能力都能得到充分發(fā)揮，在比賽場(chǎng)上每個(gè)機(jī)器人通過場(chǎng)上的實(shí)時(shí)環(huán)境轉(zhuǎn)換，從而擔(dān)任自己最擅長(zhǎng)的角色，更好地完成比賽。圖3前鋒和助攻隊(duì)員進(jìn)攻圖

如上圖3，通過計(jì)算估值函數(shù)，知道在圖中，助攻隊(duì)員的位置相比于此時(shí)的前鋒角色，具有比助攻隊(duì)員更多的優(yōu)勢(shì)：離球近，離球門近，且球，球門和此機(jī)器人在一條直線上。鑒于此，可改變它們?cè)诒荣愔械慕巧脛?dòng)態(tài)的分配角色算法，助攻隊(duì)員和前鋒交換角色繼續(xù)比賽，這樣能根據(jù)場(chǎng)上的實(shí)時(shí)情況更好地發(fā)揮隊(duì)員的各自優(yōu)勢(shì)，實(shí)現(xiàn)場(chǎng)上的配合來完成比賽。如果不交換角色，此時(shí)的前鋒并不適合前鋒的角色,就會(huì)浪費(fèi)了得分的機(jī)會(huì)。這正是比賽中角色固定不變的缺陷,也更能體現(xiàn)動(dòng)態(tài)分配角色的靈活性。

該文在經(jīng)過實(shí)際測(cè)試后，改變了傳統(tǒng)機(jī)器人足球比賽固定角色的方法，在通訊能保證的情況下，運(yùn)用二分圖最佳匹配算法來實(shí)現(xiàn)中型組機(jī)器人足球比賽中的角色分配，此算法提高了隊(duì)伍的靈活性，但是由于算法的時(shí)間占用，以及視覺信息的誤差造成的計(jì)算錯(cuò)誤，發(fā)揮算法結(jié)果的延遲性，都能影響機(jī)器人的發(fā)揮，在以后的工作中還需要進(jìn)一步的改進(jìn)。