基于蟻群算法及博弈論的多Agent路徑規(guī)劃算法

鄭延斌 王林林 席鵬雪 樊文鑫 韓夢(mèng)云

摘 要：針對(duì)多Agent路徑規(guī)劃問(wèn)題，提出了一個(gè)兩階段的路徑規(guī)劃算法。首先，利用改進(jìn)的蟻群算法來(lái)為每個(gè)Agent規(guī)劃出一條從起始點(diǎn)到目標(biāo)點(diǎn)，不與環(huán)境中靜態(tài)障礙物碰撞的最優(yōu)路徑。在蟻群算法的改進(jìn)中引入反向?qū)W習(xí)方法來(lái)對(duì)螞蟻位置進(jìn)行初始化分布，提高了算法的全局搜索能力;利用粒子群算法中的自適應(yīng)慣性權(quán)重因子來(lái)調(diào)節(jié)信息素強(qiáng)度Q值，使其自適應(yīng)地變化，避免陷入局部最優(yōu);對(duì)信息素?fù)]發(fā)因子ρ進(jìn)行調(diào)節(jié)，提高算法的迭代速度。其次，若多Agent之間存在動(dòng)態(tài)碰撞，利用博弈論構(gòu)建多Agent之間的動(dòng)態(tài)避障模型，并利用虛擬行動(dòng)法來(lái)解決博弈的求解問(wèn)題及多Nash均衡的選擇問(wèn)題，確保每個(gè)Agent能夠快速學(xué)習(xí)到最優(yōu)Nash均衡。仿真實(shí)驗(yàn)結(jié)果表明改進(jìn)蟻群算法與傳統(tǒng)蟻群算法相比在搜索精度與搜索速度上有明顯的提高，與Mylvaganam的多Agent動(dòng)態(tài)避障算法相比，所提算法減小了路徑總長(zhǎng)度并提高了收斂速度。

關(guān)鍵詞：多Agent;路徑規(guī)劃;反向?qū)W習(xí);蟻群算法;博弈論

中圖分類(lèi)號(hào)： TP24

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-9081（2019）03-0681-07

Abstract： A two-stage path planning algorithm was proposed for multi-Agent path planning. Firstly， an improved ant colony algorithm was used to plan an optimal path for each Agent from the starting point to the target point without colliding with the static obstacles in the environment. The reverse learning method was introduced to an improved ant colony algorithm to initialize the ant positions and increase the global search ability of the algorithm. The adaptive inertia weighted factor in the particle swarm optimization algorithm was used to adjust the pheromone intensity Q value to make it adaptively change to avoid falling into local optimum. The pheromone volatilization factor ρ was adjusted to speed up the iteration of the algorithm. Then， if there were dynamic collisions between multiple Agents， the game theory was used to construct a dynamic obstacle avoidance model between them， and the virtual action method was used to solve the game and select multiple Nash equilibria， making each Agent quickly learn the optimal Nash equilibrium. The simulation results show that the improved ant colony algorithm has a significant improvement in search accuracy and search speed compared with the traditional ant colony algorithm. And compared with Mylvaganam's multi-Agent dynamic obstacle avoidance algorithm， the proposed algorithm reduces the total path length and improves the convergence speed.

Key words： multi-Agent; path planning; reverse learning; ant colony algorithm; game theory

0 引言

多Agent路徑規(guī)劃問(wèn)題是指在多Agent環(huán)境中為每個(gè)Agent找出一條從起點(diǎn)到終點(diǎn)的最優(yōu)無(wú)碰路徑[1]。路徑規(guī)劃問(wèn)題是MAS （Multi-Agent System， MAS）研究的核心問(wèn)題之一，受到國(guó)內(nèi)外許多研究者的關(guān)注。蟻群算法[2]是一種基于仿生學(xué)的全局優(yōu)化啟發(fā)式正反饋算法，已成功應(yīng)用于眾多優(yōu)化問(wèn)題中，在路徑規(guī)劃問(wèn)題中效果尤為顯著[3-5]。然而蟻群算法應(yīng)用規(guī)劃問(wèn)題中仍然存在收斂速度慢、易陷入局部最優(yōu)的缺陷，為此國(guó)內(nèi)外研究者提出了一些改進(jìn)，如：裴振兵等[6]通過(guò)自適應(yīng)地調(diào)整信息素啟發(fā)因子及期望啟發(fā)因子來(lái)提高蟻群算法的迭代速度，提出廣義信息素更新規(guī)則使算法避免陷入局部最優(yōu);柳長(zhǎng)安等[7]提出利用狼群分配原則的方法來(lái)對(duì)蟻群算法中最差路徑上釋放的信息素進(jìn)行刪除，從而提高了找到最短路徑的速度;Yuan等[8]通過(guò)對(duì)啟發(fā)式函數(shù)和路徑選擇策略進(jìn)行改進(jìn)來(lái)提高算法的迭代速度;Zouari等[9]將2-opt算法引入到蟻群算法中來(lái)減少找到最短路徑的時(shí)間;屈鴻等[10]根據(jù)限定信息素強(qiáng)度的上下界，并使陷入死鎖的螞蟻采取回退策略來(lái)解決死鎖問(wèn)題，從而完成機(jī)器人路徑規(guī)劃。

多Agent環(huán)境中，受資源約束的影響，Agent在運(yùn)動(dòng)過(guò)程中相互之間可能發(fā)生碰撞。上述方法只考慮靜態(tài)障礙的避碰問(wèn)題，不能解決Agent之間的動(dòng)態(tài)碰撞問(wèn)題。由于在動(dòng)態(tài)避障過(guò)程中，每個(gè)Agent的行為決策要受到環(huán)境中其他Agent行為決策的影響，研究者提出了基于博弈論的多Agent控制方法[11-12]，這些方法以避障為目的，規(guī)劃出的路徑可以確保不與靜態(tài)障礙物或其他Agent發(fā)生碰撞，然而難以確保每個(gè)Agent的路徑最優(yōu)，另外當(dāng)多個(gè)Nash平衡存在的情況下，會(huì)出現(xiàn)震蕩現(xiàn)象。

本文提出一種多Agent路徑規(guī)劃方法，該方法分為兩個(gè)階段：第一階段為靜態(tài)避障，利用改進(jìn)蟻群算法為每個(gè)Agent規(guī)劃出一條無(wú)碰最優(yōu)路徑;第二個(gè)階段為動(dòng)態(tài)避障，是在前面得到最優(yōu)路徑的基礎(chǔ)上所作的微調(diào)，用于解決Agent之間的碰撞問(wèn)題。利用博弈論來(lái)構(gòu)建多Agent動(dòng)態(tài)避障模型，在求解該模型的過(guò)程中，利用虛擬行動(dòng)法確保每個(gè)Agent都能快速學(xué)習(xí)到最優(yōu)Nash均衡解，從而解決多Agent之間的動(dòng)態(tài)避碰問(wèn)題。

1 相關(guān)知識(shí)

1.1 蟻群算法

1.1.1 柵格間轉(zhuǎn)移概率

在蟻群算法中，螞蟻s會(huì)根據(jù)路徑上的殘留信息素濃度的大小來(lái)選擇下一步要走的柵格，在時(shí)刻t螞蟻s從點(diǎn)m轉(zhuǎn)移到n的轉(zhuǎn)移概率公式如下所示：

1.1.2 信息素更新規(guī)則

當(dāng)?shù)瓿芍舐窂缴系男畔⑺匦枰?，更新值由歷史留下的信息素值與將要留下的信息素值所決定，更新公式為：

1.2 反向?qū)W習(xí)策略

Tizhoosh[13]在2005年基于相反數(shù)或?qū)αⅫc(diǎn)的概念提出了反向?qū)W習(xí)策略。在隨后的發(fā)展中，該方法被應(yīng)用于解決一些優(yōu)化問(wèn)題中。反向坐標(biāo)定義如下。

定義1 假設(shè)x在一維空間中的坐標(biāo)是-5，目標(biāo)點(diǎn)的坐標(biāo)為10，那么x反向點(diǎn)的坐標(biāo)點(diǎn)為5，且點(diǎn)x到目標(biāo)點(diǎn)的距離為15，點(diǎn)到目標(biāo)點(diǎn)的距離為5。比較可得，反向點(diǎn)靠近目標(biāo)點(diǎn)。x的反向坐標(biāo)的計(jì)算公式為：

應(yīng)用到優(yōu)化的過(guò)程中，則反向機(jī)制的優(yōu)化過(guò)程如定義3。

1.3 自適應(yīng)慣性權(quán)重值

粒子在尋優(yōu)過(guò)程中，慣性權(quán)重w應(yīng)該是保持動(dòng)態(tài)變化的。ω取值較大時(shí)，粒子的全局搜索能力較強(qiáng);反之局部搜索的能力較強(qiáng)。由于粒子在尋優(yōu)過(guò)程中，會(huì)逐漸靠近最優(yōu)點(diǎn)，粒子的慣性權(quán)重應(yīng)該隨著迭代次數(shù)自適應(yīng)的變化，因此粒子的自適應(yīng)慣性權(quán)重更新公式[14]為：

1.4 博弈論基礎(chǔ)

博弈論是研究相互影響、相互依存局中人理性行為的數(shù)學(xué)工具，是研究理性局中人如何交互的方法[15]。由于局中人的相互依存性，博弈中的決策必須建立在對(duì)其他局中人決策的預(yù)測(cè)之上。

Nash均衡是對(duì)博弈結(jié)局的一致性預(yù)測(cè)，如果所有局中人都預(yù)測(cè)某特定的Nash均衡會(huì)出現(xiàn)，則該Nash平衡就會(huì)出現(xiàn)，不會(huì)因?yàn)槟硞€(gè)局中人認(rèn)為不符合自己的利益而失敗。達(dá)到Nash均衡后，任何局中人都不存在單方面提高自身的效用而降低其他局中人效用的動(dòng)機(jī)，故Nash均衡是博弈的穩(wěn)定解。

2 基于蟻群算法的多Agent規(guī)劃方法

當(dāng)每個(gè)Agent的起點(diǎn)和目標(biāo)點(diǎn)確定后，就可以為每個(gè)Agent規(guī)劃出一條不與環(huán)境中靜態(tài)障礙物碰撞的路徑。研究發(fā)現(xiàn)在路徑尋優(yōu)和自組織性方面蟻群算法存在很大的優(yōu)勢(shì)，然而傳統(tǒng)蟻群算法存在易陷入局部最優(yōu)及迭代速度慢的缺陷[10]，為此本文對(duì)傳統(tǒng)蟻群算法作如下改進(jìn)。

2.1 種群初始化

螞蟻在解問(wèn)題空間中找到最短路徑的時(shí)間與螞蟻初始化時(shí)在解空間中的分布存在正比關(guān)系，距離最佳位置近的螞蟻找到最短路徑的時(shí)間比距離最佳位置遠(yuǎn)的螞蟻要短。

因此為了快速找到最短路徑，在蟻群算法中引入反向?qū)W習(xí)策略對(duì)螞蟻進(jìn)行位置初始化，通過(guò)與當(dāng)前種群與反向種群的位置進(jìn)行對(duì)比找出較優(yōu)的種群。

基于反向?qū)W習(xí)算法的種群位置初始化過(guò)程表述如下：

2.2 自適應(yīng)信息素強(qiáng)度值

信息素強(qiáng)度Q為螞蟻循環(huán)一周時(shí)在路徑上所釋放的信息總量，Q值越大，表示蟻群算法的收斂速度越快;但是一旦Q值過(guò)大時(shí)，螞蟻會(huì)過(guò)多地集中于一條路徑上從而導(dǎo)致算法的全局搜索能力變差，極易陷入局部最優(yōu)。因此為了調(diào)整好二者之間的關(guān)系，本文引入粒子群算法中自適應(yīng)慣性權(quán)重值來(lái)調(diào)節(jié)Q值的大小使其能夠在搜索的過(guò)程中自適應(yīng)的變化，從而兼顧好全局與局部搜索的關(guān)系。具體公式如下：

引入粒子群算法中的自適應(yīng)慣性權(quán)重值的方法來(lái)調(diào)節(jié)信息素強(qiáng)度值可以使信息素強(qiáng)度值自適應(yīng)地變化，避免螞蟻陷入局部最優(yōu)。

2.3 信息素?fù)]發(fā)因子

信息素?fù)]發(fā)因子ρ的大小也是影響路徑信息素量大小的因素，從而影響蟻群算法的全局搜索能力和收斂速度。在傳統(tǒng)的蟻群算法中揮發(fā)因子ρ是（0，1）上的一個(gè)常數(shù)，如果給定的ρ值過(guò)大，表明路徑上的信息素量減少，從而導(dǎo)致算法收斂速度降低;若給定的ρ過(guò)小，路徑上的信息素量會(huì)增大，導(dǎo)致算法快速收斂，雖然節(jié)約了算法的搜索時(shí)間，但可能導(dǎo)致算法陷入局部最優(yōu)解。因此本文利用式（11）對(duì)揮發(fā)因子ρ作如下改進(jìn)，使揮發(fā)因子ρ隨著迭代次數(shù)的改變而自適應(yīng)地變化，具體公式如下：

2.4 信息素更新規(guī)則

當(dāng)?shù)瓿芍舐窂缴系男畔⑺匦枰?，更新值由歷史留下的信息素值與將要留下的信息素值所決定，更新公式為：

2.5 基于改進(jìn)蟻群算法的多Agent路徑規(guī)劃算法

通過(guò)以上分析，引入反向?qū)W習(xí)策略可以增強(qiáng)算法的全局搜索能力，利用粒子群算法慣性權(quán)重值調(diào)節(jié)信息素強(qiáng)度Q值可避免螞蟻陷入局部最優(yōu)，對(duì)揮發(fā)因子進(jìn)行調(diào)節(jié)提高了算法的迭代速度。改進(jìn)后的蟻群算法流程如下：

步驟1 初始化蟻群算法中的參數(shù)，螞蟻數(shù)量M、最大循環(huán)次數(shù)Kmax、啟發(fā)因子、期望值β。

步驟2 利用反向?qū)W習(xí)方法即式（8）、（9）對(duì)螞蟻的位置初始化。

步驟3 啟動(dòng)蟻群，螞蟻根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則選擇下一個(gè)要途經(jīng)的柵格，若該柵格移動(dòng)至相鄰柵格路徑上的信息素值為0，則返回到上一個(gè)搜索的柵格，并將其設(shè)置為障礙柵格。

步驟4 重復(fù)步驟2，直到所有的螞蟻都完成路徑的搜索。

步驟5 計(jì)算并記錄下各螞蟻的路徑長(zhǎng)度Ls。

步驟6 依據(jù)式（12）、（13）、（14）進(jìn)行信息素的全局更新。

步驟7 若蟻群全部收斂到一條路徑或達(dá)到最大循環(huán)次數(shù)Kmax，則循環(huán)結(jié)束;否則轉(zhuǎn)步驟2。

步驟8 輸出全局最優(yōu)路徑，算法結(jié)束。

3 基于博弈論的多Agent動(dòng)態(tài)避碰方法

利用改進(jìn)的蟻群算法可以為每個(gè)Agent規(guī)劃出一條與環(huán)境中靜態(tài)障礙物之間無(wú)碰撞的最優(yōu)路徑。然而多Agent環(huán)境中，受資源的約束，Agent在運(yùn)動(dòng)過(guò)程中會(huì)相互發(fā)生碰撞，即動(dòng)態(tài)碰撞的問(wèn)題。由于每個(gè)Agent都是按照規(guī)劃的路徑前進(jìn)，為了避免碰撞，每個(gè)Agent需要從行為集合{不變，改變運(yùn)動(dòng)方向，改變運(yùn)動(dòng)速度，等待}中選擇一種行為來(lái)執(zhí)行。碰撞發(fā)生在多個(gè)Agent之間，因此Agent的行為決策要受到環(huán)境中其他Agent的行為決策的影響，博弈論為這種相互影響的決策問(wèn)題提供了很好的數(shù)學(xué)模型。本文利用博弈論來(lái)構(gòu)建多Agent動(dòng)態(tài)避障模型，把多Agent之間的避碰問(wèn)題轉(zhuǎn)換為求解該博弈模型的Nash均衡解問(wèn)題，并利用虛擬行動(dòng)法來(lái)確保每個(gè)Agent能夠快速學(xué)習(xí)到最優(yōu)Nash均衡解。

3.1 多Agent之間的碰撞檢測(cè)

由于只有鄰居中的Agent才有可能發(fā)生碰撞，因此為了便于計(jì)算，假設(shè)每個(gè)Agent都能獲取其鄰居集合中的Agent的速度信息v（包含大小和方向）等，Agent的半徑為r。

3.2 多Agent動(dòng)態(tài)避障博弈模型

定義9 由于只有鄰居中的Agent才可能發(fā)生碰撞，因此局中人集合N定義為：

NC（No Change）表示Agent不作變化繼續(xù)按照原始路徑行走;ST（Stop）表示Agent停止等待;CV（Change Velocity）表示Agent速度產(chǎn)生加速減速變化;CD（Change Direction）表示Agent轉(zhuǎn)變方向行走。

定義12 多Agent避碰博弈為G=（N，A，U），其中N表示局中人的集合，A是博弈過(guò)程Agent的行為集合，U是效用函數(shù)。

在避障過(guò)程中，如果Agent的行為選擇為改變方向或改變速度，則當(dāng)避障結(jié)束后，需要把方向和速度還原，不僅有一定的消耗，而且還需要一定的距離才能完成，因此設(shè)FL為Agent完成變化和還原需要的最短距離，當(dāng)Agent和其目標(biāo)點(diǎn)的距離小于FL時(shí)，就不能選擇CV和CD行為。為此為Agent定義了優(yōu)先級(jí)，表示Agent行為選擇的優(yōu)先級(jí)。

3.3 基于博弈論的多Agent動(dòng)態(tài)避碰算法

由于多Agent之間的動(dòng)態(tài)避障問(wèn)題可以描述為一個(gè)博弈模型G，由Nash定理知，博弈G至少存一個(gè)Nash均衡解（定義5）。然而Nash定理只指出均衡的存在性，如何求得均衡解是一個(gè)比較復(fù)雜的問(wèn)題。另外當(dāng)博弈G中存在多個(gè)均衡時(shí)，如何確保博弈中每個(gè)Agent選擇相同的均衡就尤為重要（即均衡的選擇問(wèn)題）。博弈學(xué)習(xí)中的虛擬行動(dòng)方法[16]為博弈求解及均衡選擇問(wèn)題提供很好的解決方案，算法1給出了詳細(xì)的描述。其中qaji（t））表示t時(shí)刻局中人i選擇行為集合中某個(gè)行為aj的概率。

在重復(fù)博弈的過(guò)程中，每個(gè)局中人都知道其他參與人是在根據(jù)一個(gè)固定的混合策略分布q-i（t）來(lái)選取他們的行為組合，雖然該混合策略分布是不知道的，他可以從行為歷史中學(xué)習(xí)到其他參與人的混合策略分布q-i（t）如式（20）、（21）。參與人i在學(xué)習(xí)時(shí)刻t實(shí)際行為選擇是他在時(shí)刻t關(guān)于其他參與人行為策略的后驗(yàn)信念的最優(yōu)反應(yīng)如式（23）。故如果博弈G存在多個(gè)Nash均衡的話，算法1確保收斂到最優(yōu)Nash均衡（詳見(jiàn)文獻(xiàn)[16-17]）。由于Nash均衡是多Agent的穩(wěn)定解，一旦達(dá)到均衡，每個(gè)Agent都沒(méi)有偏離該均衡解而去追求更高效用的意圖，另外由式（19）知道，達(dá)到均衡后，Agent相互之間的距離都不會(huì)小于安全距離LL，故解決了多Agent之間的動(dòng)態(tài)避障問(wèn)題。

4 實(shí)驗(yàn)仿真與分析

分兩階段來(lái)驗(yàn)證本文所提出的算法的有效性。首先是對(duì)第一階段，每個(gè)Agent的無(wú)靜態(tài)碰撞的最優(yōu)路徑的驗(yàn)證（4.1節(jié)）;對(duì)多Agent之間的動(dòng)態(tài)避障問(wèn)題，第3章給出了理論說(shuō)明，利用算法1和算法2能夠得到最優(yōu)的Nash均衡，解決Agent之間的動(dòng)態(tài)碰撞問(wèn)題。本章利用5個(gè)Agent之間的動(dòng)態(tài)避障問(wèn)題來(lái)驗(yàn)證算法的有效性（4.2節(jié)）。

4.1 Agent路徑規(guī)劃實(shí)驗(yàn)分析

為了驗(yàn)證本文算法的適用性分別在不同的環(huán)境下對(duì)本文算法進(jìn)行實(shí)驗(yàn)驗(yàn)證，首先利用本文算法與文獻(xiàn)[2]及文獻(xiàn)[10]算法在20×20的柵格環(huán)境中對(duì)單個(gè)Agent的路徑進(jìn)行實(shí)驗(yàn)對(duì)比，使用文獻(xiàn)[10]中同樣的參數(shù)：迭代次數(shù)Kmax=200，期望值β=5.0，螞蟻數(shù)量M=50，啟發(fā)因子α=1.5，慣性權(quán)重的最大最小取值為：ωmax=0.9，ωmin=0.4，但是本文算法中信息素強(qiáng)度值Q及信息素蒸發(fā)因子ρ是自適應(yīng)變化的，經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證可以得到如圖1所示多Agent的路徑規(guī)劃圖以及圖2所示的三種算法的迭代次數(shù)圖，經(jīng)過(guò)100次實(shí)驗(yàn)取得平均值得到表1所示對(duì)比結(jié)果。

通過(guò)表1中的數(shù)據(jù)可以看出，本文算法加入自適應(yīng)慣性權(quán)重值調(diào)節(jié)信息素強(qiáng)度Q值及自適應(yīng)的調(diào)節(jié)信息素蒸發(fā)因子ρ可以避免螞蟻陷入局部最優(yōu)值，從而提高算法的迭代速度。從三種算法的對(duì)比結(jié)果中可以看出，本文算法在時(shí)耗、最短路徑長(zhǎng)度及迭代次數(shù)方面都優(yōu)于文獻(xiàn)[2]與文獻(xiàn)[10]中算法。

為了驗(yàn)證本文算法的適用性，隨機(jī)生成20×20柵格環(huán)境利用本文算法及文獻(xiàn)[2]與文獻(xiàn)[6]中算法對(duì)單個(gè)Agent在路徑規(guī)劃上進(jìn)行對(duì)比驗(yàn)證，得到的結(jié)果如圖3所示路徑規(guī)劃圖及圖4所示的迭代次數(shù)對(duì)比圖，實(shí)驗(yàn)中所用參數(shù)為：迭代次數(shù)Kmax=200，期望值β=7.0，螞蟻數(shù)量M=30，啟發(fā)因子α=1，慣性權(quán)重的最大最小取值為：ωmax=0.9，ωmin=0.4。經(jīng)過(guò)100次實(shí)驗(yàn)取得平均值得到的結(jié)果如表2所示。

通過(guò)以上的對(duì)比結(jié)果可以看出，在最短路徑的尋找過(guò)程中，本文算法在信息素?fù)]發(fā)值上的改進(jìn)能夠明顯提高算法的迭代速度，在最短路徑長(zhǎng)度上優(yōu)于文獻(xiàn)[2]以及文獻(xiàn)[6]中算法。

4.2 多Agent動(dòng)態(tài)避障分析

對(duì)5個(gè)Agent進(jìn)行仿真，利用本文避障方法來(lái)解決多個(gè)Agent之間的碰撞問(wèn)題，本文中所說(shuō)的Agent的半徑r根據(jù)經(jīng)驗(yàn)值r=2，其中Agent1（A1）的起點(diǎn)與終點(diǎn)柵格為（1，179），Agent2（A2）的起點(diǎn)與終點(diǎn)柵格為（181，48），Agent3（A3）的起點(diǎn)與終點(diǎn)柵格為（101，180），Agent4（A4）的起點(diǎn)與終點(diǎn)柵格為（47，289），Agent5（A5）的起點(diǎn)與終點(diǎn)柵格為（364，55）。經(jīng)過(guò)實(shí)驗(yàn)可以得到如圖5所示為5個(gè)Agent的路徑規(guī)劃圖，圖6所示的加入博弈論的迭代次數(shù)圖。

從圖5中Agent之間的運(yùn)行路線雖然存在交點(diǎn)，但是經(jīng)過(guò)調(diào)用博弈論的多Agent動(dòng)態(tài)避碰算法可以解決Agent之間的碰撞問(wèn)題。如在圖5中的B點(diǎn)Agent2與Agent3會(huì)利用碰撞檢測(cè)方法檢測(cè)到兩者即將在B點(diǎn)處發(fā)生碰撞，則根據(jù)算法1及避障算法2兩者產(chǎn)生一個(gè)博弈的過(guò)程，因此可以得到Agent2選擇等待直到Agent3過(guò)去，這樣避免了兩者之間的碰撞;而在C點(diǎn)處Agent3、Agent4、Agent5同時(shí)檢測(cè)到三者之間會(huì)在C點(diǎn)處發(fā)生碰撞，因此三者之間會(huì)產(chǎn)生一個(gè)博弈的過(guò)程，這時(shí)經(jīng)過(guò)算法2可以得到由于Agent3距離目標(biāo)點(diǎn)較近因此為了減少損失不必要作過(guò)多的行為變化，從而其有較高的優(yōu)先級(jí)，這時(shí)只需微調(diào)方向后再回到原始蟻群算法規(guī)劃好的路徑就可以避免與Agent4與Agent5的碰撞;如圖5中紅色加粗虛線部分，而 Agent4與Agent5之間也會(huì)產(chǎn)生一個(gè)博弈的過(guò)程，利用算法2可以得到Agent4相比與Agent5會(huì)有較高的優(yōu)先選擇行為的權(quán)利，因此Agent5選擇等待直到Agent3與Agent4過(guò)去，這樣避免了三者之間的碰撞;在接下來(lái)的運(yùn)動(dòng)過(guò)程中雖然Agent之間的運(yùn)行路線存在交點(diǎn)，但是Agent不是同時(shí)到達(dá)的，因此不會(huì)發(fā)生碰撞。因?yàn)楸疚目紤]到對(duì)全局路徑的規(guī)劃，對(duì)比文獻(xiàn)[12]中算法可以得到圖6所示的5個(gè)Agent尋得最短路徑的迭代次數(shù)對(duì)比，經(jīng)過(guò)50次實(shí)驗(yàn)利用原始蟻群算法也即文獻(xiàn)[2]中算法不考慮Agent之間碰撞的情況下及本文與文獻(xiàn)[12]中的算法得到的平均路徑長(zhǎng)度的對(duì)比。

從圖6中可以看出，本文引入博弈論的避障方法能夠避免Agent之間的碰撞，使每個(gè)Agent快速收斂到最短路徑。從圖7中可以看出，本文算法與傳統(tǒng)算法相比經(jīng)過(guò)50次實(shí)驗(yàn)得到的平均路徑長(zhǎng)度較大，但是相比與文獻(xiàn)[12]中的算法，本文算法的平均路徑長(zhǎng)度較優(yōu)。此外為了驗(yàn)證本文算法的有效性，通過(guò)100次實(shí)驗(yàn)獲得了如圖8所示的本文算法與文獻(xiàn)[12]中算法多Agent的Nash均衡值收斂曲線對(duì)比。

通過(guò)圖8可以看出，本文算法在實(shí)驗(yàn)85次左右收斂到Nash均衡值而文獻(xiàn)[12]中算法會(huì)出現(xiàn)震蕩現(xiàn)象。

綜合以上的對(duì)比實(shí)驗(yàn)，可以看出本文算法在尋找全局最優(yōu)路徑的過(guò)程中能夠很好地解決Agent之間的碰撞，從而快速找到無(wú)碰路徑。

5 結(jié)語(yǔ)

多Agent路徑規(guī)劃問(wèn)題是MAS研究的核心問(wèn)題之一，然而現(xiàn)有的方法著眼于靜態(tài)障礙物的避碰問(wèn)題，故不能解決Agent之間的動(dòng)態(tài)避障問(wèn)題。本文提出一個(gè)兩階段的多Agent路徑規(guī)劃方法：第一階段，利用改進(jìn)的蟻群算法為每個(gè)Agent規(guī)劃出一條不與環(huán)境中靜態(tài)障礙物碰撞的最優(yōu)路徑;第二階段，如果在運(yùn)動(dòng)的過(guò)程中，Agent之間發(fā)生動(dòng)態(tài)碰撞，利用博弈論方法建立多Agent動(dòng)態(tài)避障博弈模型，并利用虛擬行動(dòng)法使每個(gè)Agent能夠快速學(xué)習(xí)到最優(yōu)Nash均衡解。在多Agent的路徑規(guī)劃中具有較好的應(yīng)用價(jià)值，仿真實(shí)驗(yàn)驗(yàn)證了該算法的有效性和合理性。

參考文獻(xiàn) （References）

[1] BENNET D J， MCINNES C R. Distributed control of multi-robot systems using bifurcating potential fields [J]. Robotics and Autonomous Systems， 2010， 58（3）： 256-264.

[2] DORIGO M， MANIEZZO V， COLORNI A. Ant system： optimization by a colony of cooperating Agents [J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B： Cybernetics： A Publication of the IEEE Systems， Man， and Cybernetics Society， 1996， 26（1）： 29-41.

[3] KOVACS B， SZAYER G， TAJTI F， BURDELIS Met al. A novel potential field method for path planning of mobile robots by adapting animal motion attributes [J]. Robotics and Autonomous Systems， 2016， 82（C）： 24-34.

[4] QIAN W J， ZHOU L F，YANG L， et al. An improved ant colony algorithm of three dimensional path planning [C]// Proceedings of the 2017 10th International Symposium on Computational Intelligence and Design. Piscataway， NJ： IEEE， 2017，1： 119-122.