一種基于URWPGSim2D啟發(fā)式博弈策略設(shè)計

李生武+肖兆強+楊為民

摘要：針對北京大學(xué)機器魚仿真平臺URWPGSim2D 中“搶球博弈”項目控制目標(biāo)數(shù)量多，仿真機器魚之間的對抗性與團隊協(xié)作性強，復(fù)雜多變的競賽規(guī)則與模擬環(huán)境，設(shè)計一套穩(wěn)定，有效且對抗性強的控制策略，實現(xiàn)仿真魚的協(xié)同分工，最終獲得比賽勝利。由于仿真環(huán)境的復(fù)雜性與不確定性，為提高控制策略的高效性，提出先對仿真魚進行任務(wù)分工；其次依據(jù)仿真周期數(shù)將比賽進行階段劃分，再次根據(jù)場地中目標(biāo)水球的位置信息將場地進行區(qū)域劃分，最后利用啟發(fā)函數(shù)計算目標(biāo)球優(yōu)先級。然后綜合考慮這四個因素，給出多仿真魚協(xié)同搶球的高效策略。該策略在“2015國際水中機器人大賽”中獲得一等獎的成績，充分證明了該優(yōu)化策略的有效性及魯棒性。

關(guān)鍵詞：仿真魚；搶球博弈；協(xié)作；啟發(fā)函數(shù)；多目標(biāo)；優(yōu)先級

中圖分類號： TP242.6 文獻標(biāo)志碼： A 文章編號：1009-3044（2016）12-0075-05

以北京大學(xué)作為發(fā)起人聯(lián)合眾多科研機構(gòu)同開發(fā)了水中機器人URWPGSim2D （under robot water polo game simulation 2D）仿真平臺，該仿真系共統(tǒng)具有實時性強，逼真性高和人機交互性強的特點，有效地解決了實體機器魚在研究過程中遇到的問題，降低了實體魚的研究難度。

在2015年5月發(fā)布的新的仿真平臺URWPGSim2D 3.0中，搶球博弈項目的球門位置與模型均未發(fā)生變化，而目標(biāo)球的位置，目標(biāo)球分值及項目規(guī)則均有較大變化。平臺版本的更新使得在制定策略的時候需要更多的考慮單個目標(biāo)球?qū)Ρ荣惖梅值挠绊?，而且對機器魚的運輸有效性提出了更高的要求。因此本文分別對制約策略有效性的四個因素進行了優(yōu)化，得到了一種在新平臺下更為有效的智能策略。

1 水中機器人2D仿真簡介

1.1 URWPGSim2D平臺簡介

URWPGSim2D包括服務(wù)（URWPGSim2DServer）和客戶端（URWPGSim2DClient）兩大部分。服務(wù)端模擬水中環(huán)境，控制和呈現(xiàn)仿真過程及結(jié)果，向客戶端發(fā)送實時仿真環(huán)境和過程信息；半分布式客戶端模擬水中機器人隊伍，全分布式客戶端模擬單個水中機器人，加載比賽或?qū)嶒灢呗裕瓿蓻Q策計算過程，向服務(wù)端發(fā)送決策結(jié)果[1]。其整體結(jié)構(gòu)如圖1所示：

1.2 搶球博弈項目簡介

水中機器人2D仿真搶球博弈采用3000mm*2000mm的標(biāo)準(zhǔn)比賽場地。2D仿真搶球博弈項目的仿真環(huán)境包括4條被分為兩支隊伍的仿真魚，9個擁有不同分值的仿真水球和2個由矩形障礙物組成的球門。隨著多次大賽的成功舉行，為了提高比賽對抗的激烈性和機器魚團隊之間的協(xié)同性，開發(fā)人員將平臺做了如下更新（如圖2，圖3）所示。

1.3 計分規(guī)則

1） 水球分值：在圖3中場地四個角落的目標(biāo)球分值均為一分，場地中心附近的三個目標(biāo)球分值均為三分，其余兩個球的分值均為兩分。

2） 勝負標(biāo)準(zhǔn)：單場比賽，在6000個仿真周期內(nèi)得分多的隊伍獲勝，若分?jǐn)?shù)相同則率先進球的隊伍獲勝。

3） 進球得分：仿真水球被頂入球門時，該球門對應(yīng)的隊伍得到相應(yīng)分?jǐn)?shù)，每個球在一場比賽中如果被多次頂入同一隊伍的球門，不重復(fù)計分被頂出不扣分。

2策略設(shè)計思想

2.1 策略運行原理

仿真平臺開始運行后，平臺就會以40ms為周期循環(huán)執(zhí)行策略，以6000仿真周期總數(shù)逐步減少。這樣的循環(huán)執(zhí)行方式可以有效地提高仿真系統(tǒng)的實時性，使用者先在客戶端工程中編寫策略，在編譯通過后生成后綴名為dll的動態(tài)鏈接庫，開發(fā)者定義的函數(shù)模塊和平臺的部分信息都被封裝在了該dll文件中。在比賽時雙方在同一個服務(wù)器端加載各自策略的動態(tài)鏈接庫，準(zhǔn)備完成之后即可經(jīng)行比賽。

2.2任務(wù)調(diào)度

在筆者所提出的策略中每條己方仿真魚都有兩種任務(wù)的動態(tài)調(diào)度，一種任務(wù)是己方運球得分，另一種任務(wù)是破壞對方得分。

處于運球任務(wù)的仿真魚根據(jù)選球函數(shù)計算出來的優(yōu)先級確定運輸目標(biāo)，將目標(biāo)球迅速的運輸?shù)郊悍角蜷T。

處于破壞任務(wù)的仿真魚的是為干擾對方，破壞對方的運球狀態(tài)，抑制對方的得分。

2.3 區(qū)域劃分

受制于仿真魚智能水平的限制，仿真魚并不能主動對仿真場地障礙物和邊界做出響應(yīng)動作，因此會嚴(yán)重影響仿真魚的動作準(zhǔn)確度和運輸效率。因此筆者對比賽場地做了一定的劃分，一方面可以在不同的區(qū)域賦予仿真魚不同的動作策略以提高仿真魚的場地適應(yīng)能力，另一方面仿真魚可以根據(jù)不同區(qū)域中目標(biāo)球權(quán)值的不同可以智能選擇最有利的得分區(qū)域作為自己行動的目標(biāo)位置。

Zone 0為主要搶奪區(qū)域。此區(qū)域中目標(biāo)球較多且單個目標(biāo)球分值較大，需要綜合運用多種策略使己方迅速占領(lǐng)優(yōu)勢地位。

Zone 1，Zone 3為己方球門轉(zhuǎn)角區(qū)域。當(dāng)己方仿真魚進入此區(qū)域后在參考目標(biāo)點A，M1，B或G，M3，H（右半場則為C，M2，D或E，M4，F(xiàn)）的指引下迅速的完成運輸球從Zone 0到Zone 2或Zone 0到Zone3的任務(wù)。為防止仿真魚將目標(biāo)球帶入場地死角產(chǎn)生僵持現(xiàn)象所以需檢測函數(shù)，判斷是否滿足條件后進而調(diào)用相應(yīng)的處理模塊解決問題。

Zone 2為己方球門區(qū)域。在此區(qū)域己方魚易得分，加載射門函數(shù)，完成射門任務(wù)。

Zone 5為敵方球門區(qū)域。在此區(qū)域?qū)Ψ揭子诘梅?。對于己方來說，基于對得分規(guī)則和運輸代價的考慮，己方應(yīng)在在保證除Zone 5外的區(qū)域中無剩余目標(biāo)球的前提下才去考慮運輸Zone 5中的目標(biāo)球。

Zone 4，Zone 6為敵方球門轉(zhuǎn)角區(qū)域。在此區(qū)域不利于己方仿真魚的搶球動作，且容易在此區(qū)域與敵方因為爭奪目標(biāo)球?qū)⒛繕?biāo)球頂入死角陷入僵持階段，所以在此區(qū)域采取防守策略，通過干擾對方或者堵塞對方進入Zone 5的路徑來達到防守目的。

2.4 仿真周期控制

搶球博弈項目共10分鐘，比賽平臺設(shè)置的仿真周期即每個仿真循環(huán)周期毫秒數(shù)（如100ms），轉(zhuǎn)換得到該比賽項目的總仿真周期數(shù)（10*60*1000/100=6000）；比賽是通過倒計時的方式經(jīng)行的，筆者在此將依據(jù)仿真周期將比賽主要分為兩個階段。

進攻階段，此階段為仿真周期數(shù)從6000遞減至1800之間時間段。

破壞階段，此階段為仿真周期數(shù)從1800遞減至結(jié)束比賽之間的時間段。

3 策略設(shè)計與實現(xiàn)

3.1 仿真魚協(xié)作與任務(wù)調(diào)度

本文中提到的任務(wù)調(diào)度是由于比賽場上動態(tài)信息觸發(fā)而引起的，筆者認為將場地中仿真魚的實時狀態(tài)作為觸發(fā)信息極具代表性。在該策略中將仿真魚所處的狀態(tài)分為如下程序段所舉出的5個狀態(tài)。

3.1.2 仿真?zhèn)€體控制策略

在比賽開始后的50個仿真周期內(nèi)己方仿真魚M（M的取值為0，1）完成初始動作，之后判斷仿真比賽階段。

若當(dāng)前階段為破壞階段，以仿真魚M與對方球門距離為參考，若距離對方球門最近則去對方球門附近干擾對方得分，若不是則轉(zhuǎn)為進攻狀態(tài)。

若當(dāng)前階段為攻擊階段，仿真魚M選擇目標(biāo)球后，首先判斷己方球門是否有多于2個三分球，若滿足條件再根據(jù)仿真魚M到對方球門的距離指派具體任務(wù)；若不滿足條件則繼續(xù)執(zhí)行運輸目標(biāo)球的任務(wù)?？刂屏鞒倘鐖D6所示。

新的平臺設(shè)置了3個三分球，因此對三分球的控制直接影響著比賽結(jié)果。根據(jù)以往策略，敵我雙方都為了避免與對方因爭奪三分球過多浪費時間，采取一次性運輸分值為1或2分的目標(biāo)球，以求迅速得分占領(lǐng)優(yōu)勢而對于三分球的處理則在比賽較后階段才會去考慮。這樣不能夠及時得到三分球的控制權(quán)，因此存在被對方利用三分球得分逆轉(zhuǎn)的巨大風(fēng)險。因此本策略摒棄此種設(shè)計思想，對三分球的處理如下：比賽開始階段，己方兩條仿真魚直接選擇3個三分球中的兩個，在保證至少一個三分球能夠順利運輸?shù)郊悍角蜷T的前提下，在選球策略的指引下獲得下一個三分球的控制權(quán)。當(dāng)己方球門中三分球大于1個時，指派一條仿真魚做防守動作防止對方爭奪；另一條仿真魚繼續(xù)選球運輸。控制流程圖如圖6所示。

3.2 選球策略

有效的選球策略在比賽中不僅能夠提高隊伍的協(xié)作能力，而且能夠提高己方的得分速率與得分質(zhì)量，這在實時計時性對抗比賽中對比賽結(jié)果有著至關(guān)重要的影響作用。本文提出一種以權(quán)值評估為核心的啟發(fā)函數(shù)，該函數(shù)綜合考慮了仿真魚、球門和目標(biāo)球之間的距離關(guān)系，旋轉(zhuǎn)代價和目標(biāo)球 分值這四大要素。啟發(fā)函數(shù)形式如下。

3.2.1 [Ts，v]的計算

在URWPGSim2D平臺中由于仿真水環(huán)境的特殊性，魚即使沒有速度也難以做到相對靜止，會在水波的影響下發(fā)生位移。在設(shè)置了一個目標(biāo)點后，仿真魚到達該點后并不會立即停下，而是會沿著之前的方向運動一段距離。以此這里設(shè)定一個偏移量[μ] ，并近似認為偏移量是在之前的運動方向上。偏移量[μ][μ]與速度檔位VCode之間的對應(yīng)關(guān)系如表1所示：

3.2.2 [Aq，ω] 計算

由于仿真魚的動作存在延遲性，導(dǎo)致實際旋轉(zhuǎn)角度會受到上一時刻角速度的影響，因此難以精確控制?，F(xiàn)利用補償原理添加補償量，用來抵消前一時刻角速度對仿真魚旋轉(zhuǎn)的影響。

4 結(jié)束語

本文綜合任務(wù)調(diào)度，區(qū)域劃分，仿真周期控制和選球策略幾個方面制定了一種提出的突破常規(guī)的動作策略，該策略摒棄了局部最優(yōu)的缺點，使仿真魚對場上各種變量因素綜合評價，智能決策做到隨機應(yīng)變。經(jīng)過多次實驗驗證表明：運用上述策略可使己方在比賽過程中處于有利的主動狀態(tài)，較大的增加了己方的勝率。在本策略中主要以目標(biāo)球作為驅(qū)動因素，缺少對另一方仿真魚動作序列的檢測，因此在對方變換策略后不能及時地做出響應(yīng)動作。

參考文獻：

[1] 中國水中機器人大賽官方網(wǎng)站.URWPGSim2D開發(fā)人員手冊[EB/OL].北京：北京大學(xué)智能控制實驗室.（2010）.http：//robot.pku.edu.cn.

[2] Liu J， Dukes I， Hu H. Novel mechatronics design for a robotic fish[C]. Proc. 2005 IEEE/RSJ International Conference on Intelligent Robots andSystems，2005：2077-2082.

[3] Auzinger D.Djumlija G. Application of advanced technology packages for improved strip profile and flatness in hot-strip-mills[J].Iron and steel， 2004，39（11）：132-133.

[4] 劉舒.多機器魚編隊控制[D].北京：華北電力大學(xué)，2012.

[5] 龍海楠，李淑琴，安永躍.仿真機器魚搶球大作戰(zhàn)比賽策略的研究[J].計算機仿真，2013，30（7）：312-316.

[6] 黎章. 多水下機器人協(xié)作控制[D].北京：北京大學(xué)，2008：1-10.

[7] Anna Osborne，Stuart Baur，Katie Grantham.Simulation prototyping of an experimental solar house[J].Energies，2010，8（5） ： 27-35.

[8] Leonardand，N.E，Virtual，E.F.Virtual leaders artificial potentials and coordinated control of groups[C].The 40th IEEE Conference on Decision and Control，2001：2968-2973.

[9] Denis L，Baggi.Theintelligence left in AI[J].AI & Society，2005（2）：27-35.