球隊決策策略

1、1第第7章章 球隊決策策略球隊決策策略本章的主要內(nèi)容Robocup球隊策略里面應該包含的那些內(nèi)容。一個經(jīng)典的跑位規(guī)劃方法FC Portugal的SBSP(Situation Based Strategic Positioning)介紹了一個局部戰(zhàn)術(shù)配合3Vs.2戰(zhàn)術(shù)。一般進攻體系的設(shè)計，主要包含進攻隊員的動作選擇，一般隊員的協(xié)同以及跑位。一般防守體系的設(shè)計，涉及到防守點的選擇，防守動作的評價、守門員的防守的動作等方面的內(nèi)容。7.1 Robocup球隊策略綜述從足球比賽的角度來看，體現(xiàn)球隊整體策略的就是球隊的整體進攻和防守體系，當所有球員都按照相同的決策框架來進行決策時，球員的決策依據(jù)都相同，對

2、其他隊員的預測就比較準確，整個球隊就能夠體現(xiàn)出一定的協(xié)調(diào)性了。當Agent間的意愿一致的時候他們就會進行協(xié)作，當他們的意愿不一致的時候，就要進行協(xié)商，處理矛盾。Remco在他的論文中對球隊的整體策略進行了一下歸納。7.1 RoboCup球隊策略綜述(1)整體策略指定了隊伍的陣型以及其中隊員的位置。更進一步，它可以決定什么情況下應該采用什么樣的陣型。(2)整體策略定義了陣型中不同的角色，并把角色分配給不同位置的球員，同時確定哪種異構(gòu)球員適合哪種角色。(3)對于每種類型的球員（后衛(wèi)，中場，前鋒等）球隊策略應該根據(jù)它的角色確定分配給他哪些相應的行為。如對一個防守隊員來說，一般它應該比進攻隊員保守，它

3、選擇的動作也應該是偏向防守的。7.1 RoboCup球隊策略綜述(4)整體策略一般還包括球員應該如何根據(jù)場上形勢來調(diào)整行為的信息。比如在特定的策略下，一個球員在對自己的動作進行選擇的時候應該考慮到位置和位置所在的區(qū)域，同時還要考慮隊友和對手的位置。 (5)整體策略應該指定如何協(xié)調(diào)各個球員的行為因為不同的球員由于感知的不同，在策略的執(zhí)行上可能出現(xiàn)不協(xié)調(diào)。如何減小這種潛在不協(xié)調(diào)的危險是策略的一部分。 (6)整體策略還應該能夠在比賽中合理的管理球員的體力。如球員在比賽中如果自己的體力特別低，除非萬不得已一般盡量減少跑動以恢復體力。7.1 RoboCup球隊策略綜述 此外，球隊的整體策略還應該考慮其他

4、一些因素。比如說(1)對手的強弱。對強弱不同的對手的動作是不一樣的，如對手的截球能力強在傳球的時候?qū)髑虻募毠?jié)考慮就應該更細一點，對手弱，考慮的就少一點，可以為追求更好的結(jié)果而采用更加冒險的傳球。(2)對方球隊的整體傾向。如對手是傾向于進攻還是傾向于防守。 (3)比賽的場上情況。比如說場上的比分，是落后還是領(lǐng)先。 7.1 Robocup球隊策略綜述(4)場上是否處于關(guān)鍵狀態(tài)。如我們已經(jīng)攻入對方禁區(qū)或?qū)κ止ト胛曳降慕麉^(qū)采取緊急動作。(5)其他一些因素。是否考慮換人、是否考慮球員類型的轉(zhuǎn)換等等。 在設(shè)計的時候應盡量考慮到上面的情況。7.2基于場上形勢的戰(zhàn)術(shù)跑位(SBSP) SBSP首先是由FC P

5、ortugal提出的，它是結(jié)合了Peter Stone在CMU球隊里面的陣型和位置的概念，并在此基礎(chǔ)上面引入了戰(zhàn)術(shù)、場上情況、隊員類型等概念。SBSP的一些定義SBSP的一些定義（續(xù)）SBSP的一些定義（續(xù)）SBSP的一些定義（續(xù)）SBSP的使用SBSP的使用（續(xù)）SBSP的使用（續(xù)）最后得出了球員(Agent)在場上的戰(zhàn)略跑位：SBSP小結(jié)SBSP是一個比較成功的球隊整體策略的應用。它的基本思想是把場上狀態(tài)分為積極的和戰(zhàn)略的。球員的策略也分積極的和戰(zhàn)略的。當場上狀態(tài)是積極的時候，一般這是也就是關(guān)鍵的時候，如已經(jīng)攻入了對方禁區(qū)，或進行戰(zhàn)術(shù)配合的時候，這時Agent就不在考慮在進行高層的決策直接

6、采用反應式的方式，如進入禁區(qū)面對守門員形成單刀，這是只有一個動作選擇，那就是射門。當場上狀態(tài)進入戰(zhàn)略狀態(tài)的時候，如進攻時，控球隊員是處于積極狀態(tài)，它進行動作的選擇，其他隊員都進入戰(zhàn)略狀態(tài)，這時它們的選擇就是跑位，這就是使用SBSP，跑到一個戰(zhàn)略位置。防守時在考慮盯人、阻截球的情況下，其他隊員就要選擇合適的位置進行跑位。這時使用的也是SBSP。SBSP的一般算法IF 場上是戰(zhàn)略狀態(tài) IF 本方進攻 進攻球員進行動作選擇、其他隊員按SBSP跑位 ELSE 防守隊員截球、盯人、按SBSP跑位 ELSE 采用積極狀態(tài)下的即時動作設(shè)計RoboCup仿真比賽程序的主要難點： 在連續(xù)空間作連續(xù)的決策； 多個

7、Agent的存在給狀態(tài)空間帶來維數(shù)災難； 環(huán)境的反饋延遲太長。 環(huán)境具有強實時性和動態(tài)性； 環(huán)境通訊帶寬很窄； 環(huán)境有噪聲； 環(huán)境具有部分可觀性； 環(huán)境不具有馬爾可夫性；7.3強化學習實現(xiàn)局部戰(zhàn)術(shù)實際上，機器人足球比賽中的動作選擇可以看成是在一定的環(huán)境下Agent在自己獲取的世界狀態(tài)(s)情況下的選擇什么樣的a,由于系統(tǒng)實現(xiàn)的時候引入了噪音，因此環(huán)境不具有Markov性，也就是不可再現(xiàn)性，原則上說他就不具有使用強化學習的可能。當如果簡化這些影響，也可以把這個過程看成馬爾可夫過程，進而采用強化學習的方法。強化學習的關(guān)鍵是Agent與環(huán)境的交互可以看成是一個馬爾可夫模型，也就是說，環(huán)境應該具有再現(xiàn)

8、性。7.3強化學習實現(xiàn)局部戰(zhàn)術(shù)在Robocup中，我們考慮“戰(zhàn)術(shù)”任務(wù)是這樣一種情況：進攻一方在一活動范圍內(nèi)試圖保持控球權(quán)，同時另一方試圖奪回控球權(quán)。無論何時防守方獲得控球權(quán)或球離開此區(qū)域，這個時間段就結(jié)束，球員便放置到另一個時間段（進攻方再次被給予控球權(quán)）。7.3強化學習實現(xiàn)局部戰(zhàn)術(shù)區(qū)域設(shè)定為20M*20M的正方形，并總有3個進攻隊員和2個防守隊員。球員涉及的動作主要有： HoldBall( )：持球，持球保持靜止并盡可能遠離對手。PassBall(f)：傳球，將球直接踢給f。 GotoBall( )：跑向球。 GetOpen( )：跑位，跑到一個空曠的位置，在這個位置能得到傳出的球。 所有

9、防守方都采用固定的策略GOTOBALL( )，也就是說他們試圖阻截球，拿到球后用HOLDBALL( )保持控球權(quán)。在學習的時候，使用一個全能的教練Trainer(也是agent)在控制比賽，當防守隊員在設(shè)定時間里獲得控球權(quán)或球離開區(qū)域時Trainer就結(jié)束此時間段，就完成了一次對抗。在每個時間段開始，他在區(qū)域內(nèi)隨機的置球和球員的位置，兩個防守方隊員從區(qū)域的一個角落開始，而每個進攻球員隨機放在其他三個角落，每個角落一個球員。 學習過程學習過程（續(xù)）學習過程（續(xù)）13個函數(shù)表示狀態(tài)（WS）dist(F1,C)dist(F1,F2)dist(F1,F3)dist(F1,D1)dist(F1,D2)d

10、ist(F2,C)dist(F3,C)dist(D1,C)dist(D2,C)Minimum(dist(F2,D1),dist(F2,D2)Minimum(dist(F3,D1),dist(F3,D2)Minimum(ang(F2,F1,D1),ang(F2,F1,D2)Minimum(ang(F3,F1,D1),ang(F3,F1,D2)Tile Coding 采用Tile coding方法來進行，狀態(tài)用一個13維的空間來表示，用網(wǎng)格表示每個具體狀態(tài)，在分析的時候，每個格對應一個二進制狀態(tài)，或是1（當狀態(tài)在這個格內(nèi)）或是0（狀態(tài)不在這個格內(nèi)）。 狀態(tài)評價函數(shù)這里是學習率，一個固定的參數(shù)，T是

11、從s開始的時間段內(nèi)經(jīng)過了T個時間步。規(guī)定，進攻隊員能確切控球的狀態(tài)有最高值0；所有其他狀態(tài)是負值，立即失球的狀態(tài)值接近-1。1000( )|, tTttVsEr ssEss策略學習 強化學習去完善進攻隊員的策略以達到盡可能長的時間控球 。 使用Q-learning，即每個進攻隊員獨立學習。這樣，所有的進攻隊員都能學會相似的策略或不同的策略。每個進攻隊員有三個動作選擇，對應于控球時的每個可能動作（GetOpen( )，GotoBall( )，HoldBall(),PassBall(f)）這是我們的策略評價試驗中最有效的情況。策略學習 給出一個被用于每個進攻隊員的學習算法。函數(shù)UpdateRL(r

12、)在后面定義。counter=-1; If (球出界或防守方得到球)If (counter 0) UpdateRL(-1) else if (球不可踢) If (counter 0) counter+; If (可以跑向球達到控球) GoToBall(); else GetOpen(); else if (球可控) If (counter 0),UpdateRL(0) LastAction=Max(ActionValue(a,current state variables); Execute LastAction ; counter=0; Else (這時球被另外一個前鋒控制) If (cou

13、nter 0) UpdateRL(0); counter=-1;函數(shù)UpdateRL(r) UpdateRL(r):用TDError來更新狀態(tài)評價函數(shù)。11= + Max(ActionValue()-ActionValue()countercounterTdError ra,current,state,variablesLastAction,LastVariables注意事項： 為了鼓勵策略空間的擴展，可以使用簡單的初始條件：未經(jīng)過訓練的逼近函數(shù)開始輸出為0，這在所有真實值為負的情況下是可行的。由于任何沒有試過的動作往往看上去比已經(jīng)試過多次并被確切賦值的動作更好，這就使所有動作都有機會被嘗試。

14、小結(jié)： 使用強化學習進行局部3VS.2戰(zhàn)術(shù)的學習要求對手的防守能力強，也就是對球的截球能力強，這方面存在兩個困難：（1）跟自己比賽，提高有限，（2）和強隊比賽，高層策略無法控制。另外，3VS.2只是一個針對局部區(qū)域的策略，理論上是可以擴充到全局(11VS.11)，這時一個實際需要解決的問題是就是怎么解決龐大的狀態(tài)空間。這也是我們以后的研究方向。 7.4進攻體系 進攻是從本方隊員控球開始，直到本方失去控球權(quán)為止。 進攻體系考慮的問題持球隊員進行備選動作的選擇，其他隊員或進行策應，或進行合理的跑位。 可以分為戰(zhàn)術(shù)配合（局部的幾個球員）和戰(zhàn)略配合。7.4.1戰(zhàn)術(shù)配合 戰(zhàn)術(shù)觸發(fā)條件 戰(zhàn)術(shù)的實施過程 戰(zhàn)

15、術(shù)的終止條件 戰(zhàn)術(shù)的設(shè)計主要涉及到2個方面： 戰(zhàn)術(shù)本身的設(shè)計 通訊協(xié)議7.4.2戰(zhàn)略配合 持球隊員（進攻的核心球員）的動作選擇設(shè)計。 接球隊員的響應設(shè)計 一般隊員的跑位設(shè)計7.4.2.1持球隊員的動作選擇決策樹（if else規(guī)則）：這實際上是MAS中的策略學選取中的比較匹配函數(shù)、興趣或愛好函數(shù)的方法。 基于效用對策論進行動作選擇?；谛в脤Σ哒撉懊娼榻B了HfutAgent的個體技術(shù)，一個球員在控球以后，它可以選擇帶球、開球、傳球（包括選擇哪個隊友進行傳球）等動作。如何恰當?shù)剡x擇合適的動作是比較重要的問題。歸根結(jié)底，在選擇這些動作的時候必須考慮其他球員的利益，這就是多Agent的協(xié)作問題了。上

16、節(jié)介紹了使用強化學習的方法來進行動作的選擇。本節(jié)討論一下使用對策論的方法來進行動作的選擇?；谛в玫膶Σ哒撌荕AS協(xié)作是的一種常用的方法。對策論對策論，又稱博弈論，是使用嚴謹?shù)臄?shù)學模型研究沖突對抗條件下最優(yōu)決策問題的理論。它的研究方法和其他很多利用數(shù)學工具研究社會經(jīng)濟現(xiàn)象的學科一樣，是從復雜的現(xiàn)象中抽象出基本的元素，對這些基本元素構(gòu)成的數(shù)學模型進行詳盡分析，而后逐步引入對其形勢產(chǎn)生影響的其他因素，從而分析其結(jié)果。為建立沖突對抗條件下決策的數(shù)學模型，必須數(shù)學化地描述沖突的參與者所有可能的行為方式及其行為結(jié)果，因此它也被視為數(shù)學的一個分支。 對策論Robocup中對策論的方法實際上解決的就是在對抗

17、條件下(在考慮多方面 影響因素)怎么使自己(本方球隊)的利益最大化。MAS中的對策論就是求參與MAS協(xié)作和規(guī)劃的所有Agent的整體效用，針對Robocup，選擇動作的影響因素，以及選擇該動作的效用作為對策論的基礎(chǔ)，持球者計算得出所有參與進攻的球員的效用最大值，并把最大值對應下的動作作為該持球隊員的輸出動作。 基于效用的對策論設(shè)影響的因素cond1, cond2 , ,condn， 確定它們對動作的影響P（act| condi），計算P（actcond1, cond2, ,condn），求出的 動作。 其中U（a）為采取某種動作后的效用，P（actcond1, cond2, ,condn）表示

18、條件概率，只有高于特定的閾值的動作才被我們考慮作為備選動作。 max( |1,2,.,) ( )a actionsetP a cond condcondnU a影響因素：(1)戰(zhàn)術(shù)。戰(zhàn)術(shù)需要分析的問題：當前的戰(zhàn)術(shù)（特定陣型下的）、戰(zhàn)術(shù)是否要改變等方面的內(nèi)容。它主要包含陣型和進攻的傾向性。(2)球員類型。在真實的足球比賽中，隊員之間的屬性是不同的。同人類的足球比賽一樣，我們給每個仿真隊員定義了一個類型。用attackness、leftness和aggressiveness三個取值在0和1之間的量來表示一個隊員的類型屬性。前兩個量標明球員所打的位置。Attackness區(qū)分隊員的任務(wù)偏重于進攻的程

19、度。Leftness區(qū)分隊員所在區(qū)域的偏左的程度，Aggressiveness標明的是一個隊員的動作侵略性。影響因素(續(xù))：(3)陣型。在足球比賽中，每個隊員的活動區(qū)域是相對固定的，隨著球的位置變化，活動區(qū)域也在變化，但是每個隊員的相對位置變化比較小，這在足球比賽中稱為陣型。 (4)對手模型。目前對對手模型考慮的較少，還沒有一個比較成熟的基于對手的建模機制。7.4.2.2接球隊員的響應設(shè)計 傳球隊員一旦準備傳球，就向需要響應的接球隊員喊話(say)，可以出球的目標狀態(tài)通過一定的通訊協(xié)議傳遞給接球隊員，指導接球隊員的跑位。7.4.2.3一般隊員的跑位設(shè)計 一般隊員按照SBSP跑位思想進行跑位。

20、注：清華采用把隊員的跑位點通過神經(jīng)網(wǎng)絡(luò)做成關(guān)于球的位置和本身球員號碼的一個函數(shù)P(B,i).7.4防守體系 防守是從本方失球以后就開始的，一直到本方球員重新獲得控球權(quán)。防守體系主要考慮的問題就是一般球員組成的防守體系和守門員的防守。更進一步就是考慮加入了守門員的防守體系。 防守動作Mark（盯人，主要是指盯無球隊員）Block（卡位,堵截帶球隊員，防止其推進）Press(貼身回追帶球隊員)Formation（跑本位點）。Intercept(截球)其它注：盯人的目的是防止被盯的對手接到傳球；Block的目的是阻礙對方控球隊員帶球前進；跑本位點是指球員站在本位點處防守，即進行區(qū)域防守。 7.4.1

21、一種防守方法的介紹該體系用防守動作的目標點（對于Mark來說，防守動作的目標點在被盯隊員附近；對于Intercept來說，防守動作的目標點在阻截點上）離本位點的遠近、目標點離球員當前位置的遠近和防守目標的對防守的威脅程度來作為一個防守動作的特征。目標點離本位點遠，說明隊員要離開自己的防守的區(qū)域去防守，這對整體的防守利益帶來不好的影響。目標點離當前位置遠，說明該防守動作短期內(nèi)不容易收到效果，因為可能在往防守目標點移動的過程中，原來的決策已經(jīng)失去意義了；如果目標點離當前位置近，說明該防守動作可以很快見效，比如已經(jīng)貼著對手，這時如果能堅持對目標的防守可能收到很好的防守效果。威脅程度大致可以用被防守的

22、對手離球門的遠近來衡量，離球門越近，威脅程度越大。 一種防守方法的介紹 如果考慮的細致些的話，可以把場上的區(qū)域離散化，根據(jù)足球?qū)＜业慕?jīng)驗標明每個區(qū)域大致的威脅程度，通過插值可以得到每個點的威脅程度。顯然防守威脅程度越高的隊員，防守動作的利益越大。 一種防守方法的介紹 為了提高效率，在該防守體系中每個進攻球員只有一個防守隊員負責防守。即針對同一名對方隊員防守隊員的動作是互斥的。每個防守隊員在一個時刻只能執(zhí)行上述防守動作中的一個。防守規(guī)劃：在體系中還對防守進行了規(guī)劃，使用的方法是基于局部視覺的全局規(guī)劃。在該防守規(guī)劃中，每個防守隊員均考慮場上所有隊員的防守策略。首先對所有的進攻-防守隊員配對以及防守

23、隊員-本位點配對生成防守動作。接著根據(jù)前面提到的防守動作的特征得出防守動作的優(yōu)先級；然后用分支定界的方法，求出這個最優(yōu)的防守動作集；最后防守隊員從方案中查詢應該有自己執(zhí)行的動作。 具體算法：(1)判斷球被控制的類型。分為四種，雙方同時控球（爭球）、對方控球、我方控球、無人控球（搶球）。如果是對方控球或者無人控球但對方會先得球，我方隊員就采取防守策略，并預測球下一次被控制的位置。(2)判斷對方控球球員。如果是爭球情況，根據(jù)各種信息判斷最有可能控球的人。(3)判斷防守任務(wù)和可用人手。根據(jù)世界模型和內(nèi)部狀態(tài)，判斷有進攻威脅的對方球員并確定防守任務(wù)和確定可用來防守的我方球員。(4)考慮所有用一個可用人

24、手執(zhí)行一個防守任務(wù)的情況，判斷所應該采取的防守類型和相應的防守細節(jié)，并確定該次防守行為的效益。(5)從防守任務(wù)和可用人手配對生成最優(yōu)的防守方案（最大化防守效益和），然后提交自己有關(guān)的防守請求。7.4.2守門員的防守 在實際的足球比賽中我們經(jīng)常聽到一個好的守門員相當于半支球隊。守門員的防守在Robocup中的影響也很大。經(jīng)過實踐證明，在守門員的防守當中，最重要的是守門員的站位和守門員得球后的開球動作。當然，守門員的防單刀球、邊路防守等動作也比較重要。下面首先給出守門員在比賽過程中的決策過程，然后著重介紹守門員的站位和開球動作。 守門員的一般決策過程：(1)判斷比賽是否開始；如果沒有則調(diào)整站位，否則轉(zhuǎn)(2)(2)判斷球的位置是否不可信，如果不可信則搜索球的位