一種基于URWPGSim2D啟發式博弈策略設計

李生武+肖兆強+楊為民

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

關鍵詞：仿真魚；搶球博弈；協作；啟發函數；多目標；優先級

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

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

在2015年5月發布的新的仿真平臺URWPGSim2D 3.0中，搶球博弈項目的球門位置與模型均未發生變化，而目標球的位置，目標球分值及項目規則均有較大變化。平臺版本的更新使得在制定策略的時候需要更多的考慮單個目標球對比賽得分的影響，而且對機器魚的運輸有效性提出了更高的要求。因此本文分別對制約策略有效性的四個因素進行了優化，得到了一種在新平臺下更為有效的智能策略。

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

1.1 URWPGSim2D平臺簡介

URWPGSim2D包括服務（URWPGSim2DServer）和客戶端（URWPGSim2DClient）兩大部分。服務端模擬水中環境，控制和呈現仿真過程及結果，向客戶端發送實時仿真環境和過程信息；半分布式客戶端模擬水中機器人隊伍，全分布式客戶端模擬單個水中機器人，加載比賽或實驗策略，完成決策計算過程，向服務端發送決策結果[1]。其整體結構如圖1所示：

1.2 搶球博弈項目簡介

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

1.3 計分規則

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

2） 勝負標準：單場比賽，在6000個仿真周期內得分多的隊伍獲勝，若分數相同則率先進球的隊伍獲勝。

3） 進球得分：仿真水球被頂入球門時，該球門對應的隊伍得到相應分數，每個球在一場比賽中如果被多次頂入同一隊伍的球門，不重復計分被頂出不扣分。

2策略設計思想

2.1 策略運行原理

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

2.2任務調度

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

處于運球任務的仿真魚根據選球函數計算出來的優先級確定運輸目標，將目標球迅速的運輸到己方球門。

處于破壞任務的仿真魚的是為干擾對方，破壞對方的運球狀態，抑制對方的得分。

2.3 區域劃分

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

Zone 0為主要搶奪區域。此區域中目標球較多且單個目標球分值較大，需要綜合運用多種策略使己方迅速占領優勢地位。

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

Zone 2為己方球門區域。在此區域己方魚易得分，加載射門函數，完成射門任務。

Zone 5為敵方球門區域。在此區域對方易于得分。對于己方來說，基于對得分規則和運輸代價的考慮，己方應在在保證除Zone 5外的區域中無剩余目標球的前提下才去考慮運輸Zone 5中的目標球。

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

2.4 仿真周期控制

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

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

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

3 策略設計與實現

3.1 仿真魚協作與任務調度

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

3.1.2 仿真個體控制策略

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

若當前階段為破壞階段，以仿真魚M與對方球門距離為參考，若距離對方球門最近則去對方球門附近干擾對方得分，若不是則轉為進攻狀態。

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

新的平臺設置了3個三分球，因此對三分球的控制直接影響著比賽結果。根據以往策略，敵我雙方都為了避免與對方因爭奪三分球過多浪費時間，采取一次性運輸分值為1或2分的目標球，以求迅速得分占領優勢而對于三分球的處理則在比賽較后階段才會去考慮。這樣不能夠及時得到三分球的控制權，因此存在被對方利用三分球得分逆轉的巨大風險。因此本策略摒棄此種設計思想，對三分球的處理如下：比賽開始階段，己方兩條仿真魚直接選擇3個三分球中的兩個，在保證至少一個三分球能夠順利運輸到己方球門的前提下，在選球策略的指引下獲得下一個三分球的控制權。當己方球門中三分球大于1個時，指派一條仿真魚做防守動作防止對方爭奪；另一條仿真魚繼續選球運輸?？刂屏鞒虉D如圖6所示。

3.2 選球策略

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

3.2.1 [Ts，v]的計算

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

3.2.2 [Aq，ω] 計算

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

4 結束語

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

參考文獻：

[1] 中國水中機器人大賽官方網站.URWPGSim2D開發人員手冊[EB/OL].北京：北京大學智能控制實驗室.（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].北京：華北電力大學，2012.

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

[6] 黎章. 多水下機器人協作控制[D].北京：北京大學，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.