基于博弈論及Q學習的多Agent協作追捕算法

鄭延斌，樊文鑫，韓夢云，陶雪麗

（1.河南師范大學計算機與信息工程學院，河南新鄉 453007；2.智慧商務與物聯網技術河南省工程實驗室，河南新鄉 453007）

（?通信作者電子郵箱525845701@qq.com）

0 引言

多Agent 協作追捕問題是多Agent 協調與協作研究中的一個典型問題，在軍事、工業、農業等方面都有典型的應用。受到國內外研究者的廣泛關注［1-7］。根據逃跑者的數量，多Agent 協作圍捕問題可以分為單逃跑者圍捕和多逃跑者圍捕問題，本文關注在有障礙物條件下的單逃跑者協作圍捕問題。在單個逃跑者圍捕中，當逃避者不具備學習能力時，圍捕者可以根據逃避者的逃跑策略制定相應的圍捕策略，其追捕效率高；當逃避者具有學習能力時，環境中的障礙物可以同時被追捕者和逃跑者利用，追捕者可以利用障礙物阻擋逃跑者，逃跑者同時可以利用障礙物躲避追捕者，同時逃跑者又可以根據圍捕者的策略來改變自己的逃跑策略，因此追捕的效率低。

針對逃跑者具有學習能力使得追捕效率降低的問題，國內外研究者提出了許多解決可感知環境下的多Agent 協作圍捕的方法，可以分為兩類：

1）利用強化學習方法探索多Agent 協調行為，解決單逃跑者的追捕問題［8-11］。如：Asl 等［9］提出了一種基于強化學習的多Agent協作圍捕方法，該方法利用Q學習方法建立一個共享的Q值表，用于記錄逃避者過去的行為路線，每個圍捕者在選擇自己的圍捕策略時，不是從固定的動作集中選擇，而是從已經建立好的Q值表中來選擇，與同類型的追捕算法相比較，追捕效率更高。Bilgin 等［10］使用強化學習方法對多Agent 追捕問題進行了研究，用Q-Learning 與資格跟蹤相結合方法，首先在多Agent 團隊中使用并行學習的方式，每個Agent 獨立選擇自己的行為，并收到相應的反饋信息（環境的獎勵或懲罰），并利用這些反饋來更新每一個成員的action-value 矩陣；其次，為每個Agent 存儲臨時的行為軌跡（存儲其行為的臨時記錄），當資格跟蹤發生錯誤時返回獎勵或懲罰，由于過去的追捕行為會隨著時間的推移而消失，因此在Q-Learning 算法中加入衰減率。實驗結果證明了該算法的有效性，表明了在同等環境下不同學習率和衰減值的差異性。Qair等［11］提出了一種基于自組織特征映射（Self-Organizing Feature Mapping，SOFM）和基于Agent 群角色隸屬函數（Agent Group Role Membership Function，AGRMF）模型的增強學習的移動多智能體追蹤方法。該方法基于SOFM 和AGRMF 技術，促進了追求者群體的動態組織，并使追求者群體根據自己的意愿進行規避。這有助于克服在AGRMF 模型運行過程中，當目標過于獨立時，追求者不能完全重組的缺點。此外，還加入了獎勵功能。在群體形成后，應用強化學習得到每個Agent 的最優解。捕獲過程中每一步的結果最終都會影響AGRMF，從而加快競爭神經網絡的收斂速度。

2）基于博弈論的多Agent 協作追捕策略［12-15］。如：Fang等［13］針對多機器人協作圍捕的時間會受到每個自利的機器人動作選擇的影響，提出了一種基于量子博弈的方法，將經典戰略空間擴展到量子伙伴的范圍，確保機器人的行為策略收斂到最優平衡點，消除隨機性和盲目性；晏亞林［14］通過將逃跑者加入“拒捕”行為，且改進了有效包圍和距離影響的權重，在可感知的環境下將追捕問題轉化為博弈問題，提高了圍捕的效率；Hakli［15］提出了一種基于規劃和博弈團隊推理相結合的協同規劃方法，該方法從構建一個群體計劃開始，從中派生出它們的子計劃，個體在群體的計劃中執行它們各自的部分，適合在可以觀察到彼此行動的情況下的合作，在實際情況中能夠更像人類一樣進行有效的聯合動作。

多Agent 追捕環境中，追捕者和逃跑者都具有學習能力，故追捕者的協作追捕行為受逃跑者的逃跑的影響，逃跑者的行為也會受到障礙物追捕者以及障礙物的影響。上述的方法在強化學習方面雖然考慮到了對逃跑者的行為策略進行學習，但是未能考慮到在動態環境中追捕雙方受到的相互影響，及資源沖突的問題；在博弈論方法方面，考慮到了團隊之間的協作，但純博弈的思想會有收斂速度慢的問題。然而，博弈論為這種具有相互影響的決策性提供了很好的數學模型，而強化學習可以讓Agent 在特定環境中，根據當前的狀態，做出行動，從而獲得最大回報；另外，博弈論的核心是均衡局勢的問題，故為了達到均衡，追捕者和逃跑者應相互學習，從而使得自身利益最大化。因此，研究者提出將博弈理論與強化學習進行有效結合，考慮到在動態環境中受到的相互影響，并通過學習的方法將追捕者的策略進行迭代更新，設定出具有針對性的追捕策略，將策略作為博弈論中Agent 可選擇的動作策略，能夠有效地完成多Agent的協作追捕任務。

本文提出了一種基于博弈論及Q 學習的多Agent 協作追捕算法，來解決可感知環境中，逃跑者和追捕者都具有學習能力的情況下，多Agent 的協作追捕問題。該算法利用Agent 的屬性以及任務的需求，利用博弈的相關知識建立追捕團隊；對追捕成功的多條運動軌跡進行學習，并把學習到路徑軌跡調整到追捕者可選擇的可執行策略集中，更新追捕者的策略；通過求解博弈得到Nash 均衡解。同時針對在求解中可能存在多個均衡解的問題，加入了虛擬行動行為選擇算法，選擇最優的均衡策略。在實驗平臺上對本文提出的算法進行分析實驗，驗證了本文算法的合理性及有效性。

1 相關基礎

1.1 博弈論基礎

博弈論（Game Theory）又稱“對策論”，它研究的是在決策者的行為之間發生相互作用時，各個決策者所做對策的問題［16-17］。

定義1博弈可以用一個三元組來描述，即。

其中：P表示所有局中人的集合P={p1，p2，…，pn}；S表示局中人可行的策略集S={S1，S2，…，Sn}；每個Agent 的策略可以形式化為()；U表示局中人的支付函數U={U1，U2，…，Un}。

定義2Nash均衡。

設G=，如果存在一個聯合行為a*∈S，滿足條件：?I∈P，?ai∈S，)≥U(ai，ai-1)，則稱a*為博弈G的Nash均衡（Nash equilibrium）。

Nash 均衡是博弈的穩定解。只有當所有的局中人都預測到某一個特定的Nash均衡出現的情況下，Nash均衡才會出現，當這樣的一個Nash 均衡出現，任何一個局中人偏離這個策略組，其收益函數不會變大，因此一旦所有的局中人組成了Nash均衡，任何一個局中人都不會擅自偏離。

1.2 Q學習

機器學習（Machine Learning，ML）是當前人工智能領域的一個熱點問題。根據數據類型的不同，以及對一個問題建模方式的不同，將機器學習分為三種類型：監督學習（Supervised Learning，SL）、非監督學習和強化學習（Reinforcement Learning，RL）。

強化學習（RL）主要強調智能體能基于環境而行動，以取得最大化的效益，即：智能體在學習過程中通過環境給予的獎勵或懲罰，不斷嘗試，逐步形成對刺激的預期，從而產生能獲取最大回報的策略［18-19］。

強化學習中Q-learning是一種具有代表性的算法，它主要由四種部分組成：1）Q表：Q(s，a)為狀態s下執行a動作的累積價值；2）選擇動作；3）做出動作，環境反饋；4）環境更新。在其過程中Agenti觀察周圍環境，執行動作策略集中的動作。在t時刻，Agenti執行動作at，同時反饋收益R（St，at），更新Q值表，重復上述過程，直到任務結束。其中Q（St，at）的值可用公式表示為：

式中：a為動作策略集中的某一動作；常量參數γ（0≤γ≤1）稱作影響因子。在Agenti訓練學習過程中，選擇最大Q值的動作進行迭代訓練。

2 基于博弈論及Q學習的協作追捕算法

2.1 追捕問題描述

假定在一個多Agent 協作環境X中，由M個Agent 構成的追捕者用集合R={R1，R2，…，Rn}表示，由N個Agent 構成的逃跑者用集合T={T1，T2，…，Tn}表示。環境內有形狀和大小任意的固定障礙物，其位置映射關系為m：X→{0，1}，指定所有x∈X，m(x)=1表示位置x是障礙物。時間可離散化，并用t∈T={1，2，…}表示，規定任意Agent 在每個時刻只能執行一個動作，原地不動或者移動到其相鄰并未被占據位置。多個追捕者形成一個協作團隊完成任務W，完成任務后可以獲得一定的效用U。

將逃跑者被捕獲定義為定義3。

定義3Ge(t)={Xe(t-1)}，t∈T。

定義3表明，當逃跑Agent在t時刻被追捕成功時，它只能運動到t-1 時刻所在的位置中，其中Xe(t-1)表示其逃跑Agent 在t-1 時刻所占據的位置，同時若能滿足以下三個條件也可以認為是被捕獲的。

1）在沒有障礙物的情況下。

假設逃跑Agent 在t-1 時刻運動，其周圍的呈三角形位置已經被其他追捕的Agent 占據，且相鄰兩個追捕Agent 的距離小于兩個身長的長度，如圖1所示。

圖1 沒有障礙下追捕成功Fig.1 Successful pursuit without obstacles

2）在有障礙物的情況下。

假設逃跑Agent在t-1時刻，逃跑Agent的某一個或者不多于四個方向都存在障礙物，此時追捕Agent 占據其他可移動方向的位置，如圖2所示。

圖2 障礙下追捕成功Fig.2 Successful pursuit with obstacles

3）在無法掙脫的情況下。

假設逃跑Agent 在t-1時刻，已經被團隊形成圍捕之勢，其活動空間存在，但其運動的路徑已經無法掙脫圍捕圈，這種情況也可判定為已被抓捕。

2.2 障礙物問題描述

實驗平臺中會設定一些大小、位置不一的障礙物，用于模擬真實的環境。下面設定障礙物的一些屬性：

1）由于實驗環境設定得比較大，在環境中設定的障礙物不能占滿整個環境。

2）環境中設定的障礙物不能全部聚集在一起。

由于障礙物沒有布滿整個環境，在沒有障礙物阻擋的一些地方就會形成無障礙的狀態。在無障礙環境下，追捕者只能靠自己運動才能將逃跑者圍捕，其追捕難度就會比較大；相反，在有障礙的環境下，追捕者既可以利用障礙物對逃跑者進行圍捕，逃跑者也可以利用障礙物躲避追捕者，因此平臺中障礙物的大小、數量以及分布會對追捕者和逃跑者的運動產生影響，這種影響就會降低追捕的難度。在實驗平臺中障礙物的數量越多，逃跑者在某一特定的位置可選擇的方向就越少，此時追捕者利用障礙物將逃跑者圍捕的概率就變大；然而，障礙物比較分散的情況下，追捕者與逃跑者的可選擇方向都會減少，此時對兩者都是有影響的。

2.3 虛擬管理者

在整個追捕環境X中已經設立了M個追捕者和N個逃跑者，為了使追捕的環境趨于真實化，就需要有管理者同意安排并初始化障礙物的位置和大小，以及在追捕者團隊中擔任指揮的角色。

在多Agent 系統中建立一個虛擬管理者，此管理者不參與任何追捕活動，虛擬管理者的任務負責確定N個逃跑者、M個追捕成員，記錄所有Agent 從開始到結束的軌跡路線，當追捕團隊有多個均衡解時，虛擬管理者作為居中調度選擇最優解。

2.4 追捕團隊的形成

在多Agent 中選擇一個Agent 來管理完成任務的分配，管理Agent 掌握所有Agent 的位置、能量、偏好等屬性信息，但由于Agent 的自利性，了解所有Agent 的全部信息是不現實的，故采用基于拍賣的方式實現任務分配，管理Agent 了解所有的任務信息，負責發布任務，其他Agent 根據自己的能量、自身屬性和已經發布的任務需求進行投標。具體算法如算法1所示。

算法1 任務分配算法。

步驟1 虛擬管理者將環境中的所有Agent 初始化為逃跑者與追捕者。

步驟2 虛擬管理者發布，并利用廣播的方式告知未分配的任務Wi的信息，以及該項任務完成所能給予的報酬Uwi。

步驟3 追捕者接收到虛擬管理者的廣播，預估該任務可能消耗的能量和所獲得的報酬Uwi，根據自己剩余的能量以及偏好等屬性選擇愿意承擔的任務來投標，并把投標的信息廣播給虛擬管理者。

步驟4 虛擬管理者等待追捕者提交投標信息，若有投標信息，則進行步驟5；若無投標信息，轉向步驟8。

步驟5 虛擬管理者設定投標價格為BP（Bid Price），并將每個任務中M個追捕者的投標從高到低進行排序。

步驟6 虛擬管理者選擇n(n≤m)個追捕者分配給該任務，并將中標信息廣播給追捕者，該追捕者的標志busy=1，不允許再投標其他任務。

步驟7 如果同一個Agent 向多個任務提交了投標，虛擬管理者計算Uwi-UPowi（UPowi為執行任務需要消耗的收益），選擇能獲得最大效用的任務分配給該追捕者。

步驟8 若所有的任務分配完畢，則轉向步驟9；否則對未分配的任務進行分解，轉步驟1。

步驟9 結束。

2.5 協作追捕算法

2.5.1 博弈模型的構建

在追捕環境中通過團隊之間協作完成任務的追捕者，團隊中一個追捕者的行為會受到其他追捕者的影響，同時逃跑者的行為也會受到追捕者的行為決策的影響。而博弈論為這種相互影響的決策行為給出了很好的數學模型［20］。

定義4多Agent協作圍捕博弈模型，。

其中：P為追捕團隊中追捕者的集合，P={1，2，…，n}；S為追捕者可能執行的策略集合；Si是團隊中每個追捕者的動作策略，每個追捕者根據當前自己周圍的環境和其他追捕者周圍的環境做出相應的動作。每個Agent 的策略可以形式化為()，U是支付函數，表示執行策略之后的得失情況。

設多Agent 系統所處的環境為X，Xt表示多Agent 系統在時刻t所處的環境。

設Agent可觀測到的環境狀態的集合為St，為系統中在t時刻的聯合觀測，記為：。在動態復雜的環境下，多Agent 系統中的Agent 所獲取的信息可能是完全的，也可能是不完全的。

設Agent 動作集合為A，Ai用于表示Agenti的動作集合，Agent 的動作集合用A表示，，從每個Agent 在時刻t所觀測的環境采取的動作對環境產生的影響看，多個追捕者之間的聯合行動也會對當前所處的環境的狀態產生影響。

設狀態轉移函數為T，Tt：S×A→S，表示在某一特定的環境下，某個追捕者與其他追捕者之間通過協作對環境可能產生的影響。

設Agent 支付函數為U，Ui=S×A→U，表示Agenti在多Agent系統中為了完成任務所采取的行為后的收益情況。

Agent 的目標集合G={G1，G2，…，Gn}，Gi表示多Agent 系統中每個Agent 的目標，通?？梢岳弥Ц逗瘮礥來表示，每個Agenti之間的目標可能存在多種關系：當目標一致時，Agent 之間目標的完成是相互促進的；當目標沖突時，就會產生利益資源的沖突。

2.5.2 基于Q學習的可執行的策略集

在單獵物追捕問題中，需要在環境中隨機生成M個追捕者，由它們組成一支協作追捕團隊A。由于單獵物以是否具有學習能力分為智能化和非智能化。非智能化的逃跑者其逃跑運動軌跡一般比較固定，智能化的逃跑者運動軌跡不確定，會根據自身對環境的狀態進行選擇路徑。因此，在其逃跑的策略集中加入強化學習算法，對其動作選擇的策略集進行改進。

在t時刻可以進行移動的方向稱為Agent 的策略集，其策略集就是其能進行決策的集合。t時刻逃跑者的策略集表示為St：

St包含｛Xa，Xb，Xat，Xbt｝

其中：0°≤Dir≤360°，供其選擇的方向有360°；π=3.14；V表示速度。

由于追捕者無法獲知逃跑者的狀態-動作值Q，也就無法準確地找到適合的策略應對，其原有的策略集就顯得比較寬泛，因此加入Q學習的方法對逃跑者的動作狀態值進行學習，調整為具有針對性的追捕策略集。

由于逃跑者的逃跑策略都是未知的，因此，使用強化學習的方法對逃跑者的逃跑策略進行學習，制定適合追捕者的追捕策略。首先，在此算法中加入Step-T累積獎賞的學習任務，從逃跑者的初始狀態出發，使追捕者經過有限次的學習獲得一條具有Step-T的逃跑者的逃跑軌跡：

其次，記錄軌跡中每一對狀態-動作Q的累計獎賞之和，作為一次關于逃跑者累積獎賞采樣值。當對逃跑者進行多次采樣得到多條逃跑軌跡后，將對多次獲得的累積獎賞采樣值利用式（1）求取平均，得到Q值的估計。

由于要得到較好的動作-狀態值函數的估計，就需要產生多條不同的軌跡，然而逃跑者選擇的策略有可能是固定的，經過采樣會導致追捕者得到的路線都是一致的。為了得到最優的策略，引入ε-貪心算法，以ε的概率從所有的動作中均勻地隨機選擇一個動作，以1-ε的概率選取當前最優動作，將已經確定的策略標記為“原始策略”。在原始策略中使用了ε-貪心算法的策略記為式（2）：

2.5.3 追捕團隊成員避障策略

追捕團隊成員在環境中進行抓捕以及逃跑者在進行逃逸的過程中，在t時刻其要運動到的位置可能被其他物體占領，這就有可能會發生碰撞，因此就需要根據所處環境的約束，進行實時有效的避障。傳統的人工勢場法的基本思想就是將追捕團隊所處的環境充斥著混合勢力場，環境中的逃跑者充斥著引力勢場，方向由追捕者指向逃跑者；環境中的障礙物以及各個追捕者充斥著斥力勢場，方向是由障礙物指向追捕者及逃跑者。分析傳統人工勢場法易出現局部極小點和目標不可達的原因，文獻［21-22］給出了一種改進后的合力公式（3）如下：

式中：Fall為合力；Fg為虛擬目標點對Agent 的引力；α為方向向量的增益系數；derc為單位方向向量；β為斥力增益系數；Fol為障礙物點i對Agent的斥力。

這樣既能保證追捕者趨向于逃跑者，又能避免環境中的所有Agent與障礙物發生碰撞以及追捕者之間發生碰撞。

2.5.4 支付函數

追捕過程中，雙方需要一個標準來評估自己選擇策略的優劣，博弈論中用支付函數實現這一功能，追捕者的目標是：1）判斷逃跑者下一個時刻t的逃跑方向；2）預測下一點的位置中是否存在障礙；3）先將逃跑者在最短的時間內圍住。而逃跑者的目標是有多條路徑供其選擇逃跑。雙方具有不同的目標，且雙方在一方受到利益損害時另一方并不一定有收益，因此可以認為追捕者與逃跑者之間博弈為協作博弈。

由于追捕者對于逃跑者的威脅程度主要體現在距離的遠近、包圍圈的好壞上，因此在支付函數中包含以下三個影響系數：

1）距離影響系數Kd。

當追捕者距離逃跑者的距離越近，那么它對逃跑者的威脅系數就越大；反之則越小。以此來定義距離影響系數，如式（4）所示：

其中：n為追逃環境中追捕者的數量；DPjEt表示t時刻第j個追捕者與逃跑者之間的距離。

2）有效包圍系數KC。

由于成功追捕的條件是逃跑者在其周圍已經沒有其選擇的逃跑方向，并且其可能的走步數在逐漸減少，此時的狀態是追捕者逐步地接近逃跑者，并且已經在形成圍捕的局勢。以此來定義有效包圍系數式（5）：

式中，Dir為可供其選擇的方向。

3）速度變化系數KV。

在環境中逃跑者的運動由于受到人工勢場的影響，其會受到合力Fall的作用；其次，追捕者的初始位置是隨機的，有的追捕者就可能會出現在距離逃跑者較遠的位置。為了保證能快速形成圍捕的趨勢，因此需要根據受到的合力Fall以及距離逃跑者的距離S及時地調整速度，其計算式定義如式（3）和式（6）～（7）。

式中：S表示追捕者與逃跑者之間的距離；tx、ty為當前逃跑Agent 的坐標位置，dx、dy為當前追捕者的坐標位置；α、β為影響速度V的權重值，在不同的局勢下，追捕的側重點不同。例如在距離較遠的情況下，采取的策略以加速靠近為主；在距離縮小到一定的范圍之后，采取的策略應該以形成包圍圈為主。因此針對不同的情況設定不同的權重值。

定義支付函數U：

式中：λd與λc、λv分別代表不同的權重值，其中λd+λc+λv=1，權重的大小要根據在環境中遇到的情況進行調整。

2.5.5 逃跑Agent的追捕策略選擇算法

追捕者與逃跑者在某t時刻選擇各自的走步策略，追捕者根據定義的支付函數可以分別計算出追捕雙方在不同的策略選擇下追捕者的支付矩陣Ut。將t時刻的支付矩陣表示如式（9）：

根據博弈論中矩陣博弈的基本定理，一定存在混合策略意義下的解，通過排除法求解此矩陣，可得到t時刻局中人的最優策略。

2.5.6 基于虛擬行動的Agent行為選擇算法

在上述的多Agent 協作追捕方法中，多個Agent 通過學習收斂到納什均衡Q值。然而在協作追捕的博弈模型G的環境中，由Nash定理可知，博弈G至少存在一個Nash均衡解，因此每個Agent 通過學習都可能存在有多個納什均衡的情況，當多個Agent 存在多個納什均衡解時，就需要每個Agent 都會選擇同一個納什均衡解。

本節要考慮的問題是當博弈中存在多個納什均衡解時，Agent 如何通過合適的策略保證最終選擇同一個均衡解。在此，引入博弈學習中虛擬行動過程的概念，這種學習模型將有利于解決存在多個均衡解的問題。

虛擬行動模型中，多個Agent 處于有限重復博弈中，每個Agent 都會根據對手Agent 的歷史行為，對在當前階段對手Agent行動的概率分布進行預測和評估，并且會選擇一個最優化其預測支付的行動。其評估的特定形式如下：Agenti有一個初始的加權函數，+，每次當對手Agent 選擇策略S-i時，通過給每個對手相應的策略權重加1 對該函數進行調整，即式（10）。

在階段t，Agent賦予其他Agent采取策略S-i的概率為：

在虛擬行動中，Agent 僅僅跟蹤對手Agent 的行動頻率是不行的，還需要學習到這些概率分布，因此Agent 應該漸進地獲取概率分布時相應的效用U。用D-i t表示Agenti的對手行動的經驗分布。

在虛擬行動中某一時刻t，定義Agent 對其所評估的對手Agent的行為策略而言最優的行動集合為：

在重復博弈的過程中，每個Agent 相信對手Agent 的行為是一個未知的但固定概率分布的多重隨機變量序列，這種序列可以通過式（10）、式（11）從行為歷史中學到。Agenti在學習時刻t實際行為選擇是它在t時刻關于對手Agent 行為策略的最優行動，如式（13），基于虛擬行動方法構建了Agent 行為選擇算法如算法2所示。

算法2 基于虛擬行動的Agent行為選擇算法。

將上述的方法進行整合，用一個完整的算法3 表示整個多Agent協作追捕算法的過程。

算法3 基于博弈論及Q學習的協作追捕算法。

步驟1 初始化生成逃跑者和追捕者；令其動作-狀態Q(x，a)=0，count(x，a)=0，π(x，a)=1 |A|。

步驟2 根據算法1建立追捕團隊，并建博弈模型。

步驟3 根據成功捕獲的條件判斷逃跑者是否被捕獲，如果已經被捕獲，則結束任務；否則，則進行步驟4。

步驟4 利用式（4）～（5）、式（7）控制速度變化，并向逃跑者的位置進行移動。

步驟5 執行策略π，產生軌跡。

步驟6count(xt，at)=count(xt，at)+1，利用式（1）對Q(x，a)值策略進行更新。

步驟7 判斷能否形成完整Step-T運動軌跡，若形成則轉至步驟8；否則繼續進行步驟4～7。

步驟8 對所有可見的狀態x利用值函數式（2）得到完整策略。

步驟9 根據步驟8獲得的學習策略得到支付值，形成支付矩陣Ut。

步驟10 由步驟9 得到的t時刻的支付矩陣Ut求取其納什均衡解，得到t時刻的較優走步策略。

步驟11 執行算法2 虛擬行動方法找到協作追捕的最優解。

步驟12 執行走步策略，追捕成功，返回步驟3。

上述的算法流程如圖3 所示，可以更加清晰直觀地展示本文所提出的追捕算法。

圖3 多Agent追捕單目標獵物流程Fig.3 Flowchart of multi-agent pursuit single-target prey

3 實驗仿真與結果分析

為了充分驗證本文算法的有效性和合理性，將具有針對性的三種算法（文獻［14］算法、文獻［9］算法、文獻［11］算法）與本文算法進行仿真實驗對比，結果如表1 所示。實驗的仿真環境為一個具有多處不同大小障礙物（房屋、人、山、河流等）的實驗平臺，環境中有三個追捕者、一個逃跑者。

假設所有的Agent具有以下特質：

1）追捕過程中所有的Agent 均只能活動在具有邊界的地形中，其運動可選擇的方向為360°。

2）所有的Agent 對環境中的障礙物以及每個Agent 等位置信息已知，并且所有的Agent 在環境中初始位置隨機，初始化所有參與追捕者的速度值均為2 m/s，追捕者在速度上比逃跑者的速度要快，其追捕者的速度變化要根據速度影響系數KV變化。

3）假設當前時刻t是追捕者所占據的位置Xa，b(0 m ＜a＜720 m，0 m ＜b＜720 m)，追捕者與逃跑者每次移動一個身位（自身的寬度20 cm）*V（速度），其移動的方向選擇為360°。用Hi(t)表示此時Xa，b處的Agent 可以運動到的位置，如式（14）所示：

其中：Xa，b表示t時刻所在的位置；(Xa+cos(Dir*π/180°)*20*V，Xb+sin(Dir*π/180°)*20*V）表示在t+1 時刻所在的位置；Dir為轉向度數，并且規定轉向度數一次為5°；π=3.14；20 為追捕者以及逃跑者的身長；V為速度值。

在上述同樣的環境中進行基于博弈方法的多Agent 追捕［14］、基于強化學習的多Agent 追捕［9］、基于自組織結構的多Agent 追捕［11］，以及本文提出的基于博弈論及Q 學習的多Agent 協作追捕等算法的研究。每種算法實驗50 次，不同算法的追捕時間如表1 所示，表中數字代表追捕者從開始追捕逃跑者到完成追捕所用的時間。從表1 中可以看出，本文算法的協作追捕效率更高。

表1 不同算法的追捕時間對比單位：sTab.1 Pursuit time comparison of different algorithmsunit：s

在圖4具有障礙物的環境中，多Agent追捕團隊從初始位置開始，在人工勢場合力的影響下，通過學習逃跑者的逃跑路徑形成Step-T 策略，求解協作追捕博弈，得到Nash 均衡解，Agent 選擇均衡策略進行圍捕。從整個追捕的時間上可以得出，本文算法較優，且較為穩定。由圖4（a）中可知，環境中的障礙物可以作為圍捕逃跑者的有利條件；而圖4（b）中為追捕團隊不利用障礙物進行的圍捕。

圖4 多Agent追捕環境Fig.4 Multi-agent pursuit environment

在圖5 中，利用不同的曲線展示了追捕團隊從任務開始到任務結束的一個動態過程，仿真實驗環境中設定環境的邊界為X、Y，其中，0 m ≤X≤720 m，0 m ≤Y≤720 m。

圖5（a）是利用文獻［14］中博弈論的算法在本文實驗平臺中進行的追捕，圖5（b）是利用文獻［9］中學習的算法在本文實驗平臺中完成的追捕，圖5（c）是利用文獻［11］中自組織算法在本文實驗平臺中完成的追捕，圖5（d）是本文所提出的基于博弈論和Q 學習的協作追捕算法在實驗平臺中完成的追捕。從圖5 中可以看出：追捕者在前半段發現逃跑者之后都盡可能地去貼近逃跑者，速度變化根據式（7）動態改變；在后半段中，其包圍系數KC會變得比較重要，可以直觀地看出圖5（d）中后半段的追捕完成的效率較高。

圖6 通過實驗驗證本文所提出的算法3 即基于博弈論和Q 學習的協作追捕算法在同等環境下，支付函數權重值的不同對追捕效率的影響。使用隨機的策略進行了15 次實驗，分別每次改變兩種參數。同時依據圖5 中的追捕模擬運動軌跡可知，在前半段進行的貼近逃跑者運動中，速度影響的因素KV極為重要，在形成圍捕之勢時，包圍系數KC的重要性就顯示出來了。從圖6 結果中可以看出，在同等環境下距離、包圍程度，以及速度的權重不同，會使追捕的效率產生較大差異。

圖6 同等條件下不同權值追捕時間對比Fig.6 Comparison of pursuit time with different weights under same condition

4 結語

本文提出了一種基于博弈論及Q 學習的多Agent 協作追捕算法，考慮到Agent 具有的學習能力，在追捕過程追捕者與逃跑者會因為策略選擇相互影響。首先，利用博弈的相關模型建立協作追捕團隊；其次，在追捕過程中隨機選擇已經成功的追捕案例，將逃跑者的逃跑路徑進行切段劃分總結，對逃跑者的運動路徑進行有限次的學習，更新狀態值，調整追捕者的可執行策略集；最后，求解協作博弈模型，追捕者選擇較優的追捕行動策略并完成追捕，增強了博弈方法的環境適應性。同時，加入了虛擬行動行為選擇算法，在出現有多個Nash 均衡的情況下，使得Agent 能夠選擇最優的均衡策略。仿真實驗驗證了所提算法既能快速捕獲逃跑者和避開障礙物，又能適應當前的環境。在未來的研究中，將進一步研究存在多個逃跑者和多個追捕團隊的協作追捕問題。