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

（1.河南師范大學(xué)計算機與信息工程學(xué)院，河南新鄉(xiāng) 453007；2.智慧商務(wù)與物聯(lián)網(wǎng)技術(shù)河南省工程實驗室，河南新鄉(xiāng) 453007）

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

0 引言

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

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

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

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

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

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

1 相關(guān)基礎(chǔ)

1.1 博弈論基礎(chǔ)

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

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

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

定義2Nash均衡。

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

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

1.2 Q學(xué)習(xí)

機器學(xué)習(xí)（Machine Learning，ML）是當(dāng)前人工智能領(lǐng)域的一個熱點問題。根據(jù)數(shù)據(jù)類型的不同，以及對一個問題建模方式的不同，將機器學(xué)習(xí)分為三種類型：監(jiān)督學(xué)習(xí)（Supervised Learning，SL）、非監(jiān)督學(xué)習(xí)和強化學(xué)習(xí)（Reinforcement Learning，RL）。

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

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

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

2 基于博弈論及Q學(xué)習(xí)的協(xié)作追捕算法

2.1 追捕問題描述

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

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

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

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

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

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

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

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

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

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

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

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

2.2 障礙物問題描述

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

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

2）環(huán)境中設(shè)定的障礙物不能全部聚集在一起。

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

2.3 虛擬管理者

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

在多Agent 系統(tǒng)中建立一個虛擬管理者，此管理者不參與任何追捕活動，虛擬管理者的任務(wù)負(fù)責(zé)確定N個逃跑者、M個追捕成員，記錄所有Agent 從開始到結(jié)束的軌跡路線，當(dāng)追捕團隊有多個均衡解時，虛擬管理者作為居中調(diào)度選擇最優(yōu)解。

2.4 追捕團隊的形成

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

算法1 任務(wù)分配算法。

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

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

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

步驟4 虛擬管理者等待追捕者提交投標(biāo)信息，若有投標(biāo)信息，則進行步驟5；若無投標(biāo)信息，轉(zhuǎn)向步驟8。

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

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

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

步驟8 若所有的任務(wù)分配完畢，則轉(zhuǎn)向步驟9；否則對未分配的任務(wù)進行分解，轉(zhuǎn)步驟1。

步驟9 結(jié)束。

2.5 協(xié)作追捕算法

2.5.1 博弈模型的構(gòu)建

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

定義4多Agent協(xié)作圍捕博弈模型，。

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

設(shè)多Agent 系統(tǒng)所處的環(huán)境為X，Xt表示多Agent 系統(tǒng)在時刻t所處的環(huán)境。

設(shè)Agent可觀測到的環(huán)境狀態(tài)的集合為St，為系統(tǒng)中在t時刻的聯(lián)合觀測，記為：。在動態(tài)復(fù)雜的環(huán)境下，多Agent 系統(tǒng)中的Agent 所獲取的信息可能是完全的，也可能是不完全的。

設(shè)Agent 動作集合為A，Ai用于表示Agenti的動作集合，Agent 的動作集合用A表示，，從每個Agent 在時刻t所觀測的環(huán)境采取的動作對環(huán)境產(chǎn)生的影響看，多個追捕者之間的聯(lián)合行動也會對當(dāng)前所處的環(huán)境的狀態(tài)產(chǎn)生影響。

設(shè)狀態(tài)轉(zhuǎn)移函數(shù)為T，Tt：S×A→S，表示在某一特定的環(huán)境下，某個追捕者與其他追捕者之間通過協(xié)作對環(huán)境可能產(chǎn)生的影響。

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

Agent 的目標(biāo)集合G={G1，G2，…，Gn}，Gi表示多Agent 系統(tǒng)中每個Agent 的目標(biāo)，通常可以利用支付函數(shù)U來表示，每個Agenti之間的目標(biāo)可能存在多種關(guān)系：當(dāng)目標(biāo)一致時，Agent 之間目標(biāo)的完成是相互促進的；當(dāng)目標(biāo)沖突時，就會產(chǎn)生利益資源的沖突。

2.5.2 基于Q學(xué)習(xí)的可執(zhí)行的策略集

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

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

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

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

由于追捕者無法獲知逃跑者的狀態(tài)-動作值Q，也就無法準(zhǔn)確地找到適合的策略應(yīng)對，其原有的策略集就顯得比較寬泛，因此加入Q學(xué)習(xí)的方法對逃跑者的動作狀態(tài)值進行學(xué)習(xí)，調(diào)整為具有針對性的追捕策略集。

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

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

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

2.5.3 追捕團隊成員避障策略

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

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

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

2.5.4 支付函數(shù)

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

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

1）距離影響系數(shù)Kd。

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

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

2）有效包圍系數(shù)KC。

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

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

3）速度變化系數(shù)KV。

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

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

定義支付函數(shù)U：

式中：λd與λc、λv分別代表不同的權(quán)重值，其中λd+λc+λv=1，權(quán)重的大小要根據(jù)在環(huán)境中遇到的情況進行調(diào)整。

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

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

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

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

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

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

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

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

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

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

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

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

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

算法3 基于博弈論及Q學(xué)習(xí)的協(xié)作追捕算法。

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

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

步驟3 根據(jù)成功捕獲的條件判斷逃跑者是否被捕獲，如果已經(jīng)被捕獲，則結(jié)束任務(wù)；否則，則進行步驟4。

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

步驟5 執(zhí)行策略π，產(chǎn)生軌跡。

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

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

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

步驟9 根據(jù)步驟8獲得的學(xué)習(xí)策略得到支付值，形成支付矩陣Ut。

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

步驟11 執(zhí)行算法2 虛擬行動方法找到協(xié)作追捕的最優(yōu)解。

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

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

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

3 實驗仿真與結(jié)果分析

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

假設(shè)所有的Agent具有以下特質(zhì)：

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

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

3）假設(shè)當(dāng)前時刻t是追捕者所占據(jù)的位置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為轉(zhuǎn)向度數(shù)，并且規(guī)定轉(zhuǎn)向度數(shù)一次為5°；π=3.14；20 為追捕者以及逃跑者的身長；V為速度值。

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

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

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

圖4 多Agent追捕環(huán)境Fig.4 Multi-agent pursuit environment

在圖5 中，利用不同的曲線展示了追捕團隊從任務(wù)開始到任務(wù)結(jié)束的一個動態(tài)過程，仿真實驗環(huán)境中設(shè)定環(huán)境的邊界為X、Y，其中，0 m ≤X≤720 m，0 m ≤Y≤720 m。

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

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

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

4 結(jié)語

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