基于人工勢場法的多智能體編隊避障方法

鄭延斌，席鵬雪，王林林，樊文鑫，韓夢云

(1.河南師范大學 計算機與信息工程學院，河南 新鄉(xiāng) 453007； 2.智慧商務與物聯(lián)網(wǎng)技術(shù)河南省工程實驗室，河南 新鄉(xiāng) 453007)(*通信作者電子郵箱xipengxue@163.com)

0 引言

多智能體編隊問題是指多智能體在執(zhí)行任務的過程中相互之間保持某種幾何形狀不變。編隊問題是多智能體系統(tǒng)研究的熱點問題之一，在許多領(lǐng)域都有很好的應用，如軍用、民用、游戲等。受環(huán)境因素的制約，多智能體編隊在執(zhí)行任務的過程中，不可避免地會遇到環(huán)境中的靜態(tài)障礙(如環(huán)境中的山川、河流、房屋、樹木等)和動態(tài)障礙(如環(huán)境中其他移動的智能體)，如何合理地避開這些障礙物，又能最大限度地保持編隊隊形，是多智能體編隊研究的關(guān)鍵問題之一，目前研究者提出了許多解決的方法。

常用的多智能體編隊避障算法有：領(lǐng)航跟隨法[1]、人工勢場法(Artificial Potential Field method, APF)[2]、虛擬結(jié)構(gòu)法[3]、基于行為法[4]等。其中人工勢場法具有結(jié)構(gòu)簡單、實用性好、實時避障且路徑平滑的優(yōu)點，但容易陷入局部最優(yōu)。針對此問題研究者提出許多改進方法如：仇國慶等[5]提出了將多智能體系統(tǒng)與傳統(tǒng)遺傳算法相結(jié)合的編隊控制方法，利用最優(yōu)染色體調(diào)節(jié)智能體的運動參數(shù)至最佳狀態(tài)，同時將領(lǐng)航跟隨法與人工勢場法結(jié)合，有效地保持隊形的穩(wěn)定性，人工勢場法中歸一化其超過最小安全距離的斥力，達到有效避障目的；Kowdiki等[6]提出了領(lǐng)航跟隨法框架的混合編隊控制技術(shù)，用人工勢場法規(guī)劃領(lǐng)航智能體的導航路徑，使整個編隊控制具有穩(wěn)定性；Dang等[7]在動態(tài)環(huán)境下，利用旋轉(zhuǎn)勢場和排斥力使得機器人逃離障礙物并避免局部極小問題。編隊避障過程中存在的“局部困擾”[7-8]情況，加入了“回環(huán)力”，使多智能體編隊能夠通過障礙物區(qū)域。然而這些方法沒有考慮隨機性障礙物對編隊控制及避障的影響。

人工勢場法中增益系數(shù)設置的局限，使得該算法不適應隨機性障礙物的動態(tài)環(huán)境，近幾年為了增加避障算法的環(huán)境適應性，研究者對人工勢場法的增益系數(shù)進行改進，如：張立陽等[9]提出了將模糊控制法與人工勢場法結(jié)合，實時調(diào)整斥力與引力的增益系數(shù)，實現(xiàn)軌跡跟蹤與避障；翟紅生等[10]提出了將量子粒子群算法引入到人工勢場法，優(yōu)化斥力與引力勢場的增益系數(shù)，實時控制機器人的運動。這些方法解決的是單個智能體的避障問題，沒有涉及多個智能體的避障。有涉及多個智能體避障并修改其增益系數(shù)的方法，比如：Chatraei等[11]使用Mamdani模糊系統(tǒng)所給出的人工勢場斥力與引力的增益系數(shù)來驗證該系統(tǒng)的避障效果。

針對動態(tài)環(huán)境中，多智能體編隊耗時長、環(huán)境適應度差的問題[12]，本文在動態(tài)隊形變換策略[12-13]的異構(gòu)模式下，使用人工勢場法對編隊中各個智能體實時規(guī)劃避障；針對人工勢場的引力增量系數(shù)和斥力增量系數(shù)設置的局限，利用布谷鳥搜索算法(Cuckoo Search algorithm, CS)[14]，隨機搜索適合當前環(huán)境的引力和斥力增量系數(shù)。使用效率函數(shù)對實驗的數(shù)據(jù)進行評價及分析，驗證本文優(yōu)化方法的合理性及有效性。

1 相關(guān)基礎

1.1 多智能體動態(tài)隊形變換避障策略

多智能體編隊在進行編隊避障時，需要根據(jù)所處環(huán)境的約束，進行實時有效的避障。本文用文獻[13]提出的伸縮因子，選擇適合的編隊隊形避障方法。伸縮因子是指多個智能體組成的隊形維持現(xiàn)有形狀不變，只是在大小上實現(xiàn)伸縮的參數(shù)[13]。伸縮因子用符號ρ表示，ρ≥ρm，而ρm表示隊形伸縮因子的閾值。利用伸縮因子來確定避障的隊形變換模式指令σ(σ∈{σi|0,1,2|})，伸縮因子計算式如式(1)所示：

ρ=Dmax/D

(1)

其中：D表示智能體小組隊列的寬度；Dmax表示障礙環(huán)境下智能體小組運行路線的可通行路徑的最大寬度。

動態(tài)隊形變化策略的模式如下：

1)零變換模式(σ=0)：若ρ≥1，則Dmax≥D，表明編隊中的智能體不需要改變現(xiàn)有隊形即可通過障礙區(qū)。

2)同構(gòu)變換模式(σ=1)：若ρ<1且ρ≥ρm，表明智能體編隊不能直接通過障礙區(qū)，但是可以壓縮隊形大小、不改變隊形形狀的方式通過障礙區(qū)。

3)異構(gòu)變換模式(σ=2)：當兩種模式均不成立時，即ρ<ρm時，表明只能破壞多智能體編隊現(xiàn)有的隊形，才能通過障礙區(qū)。

1.2 人工勢場法

傳統(tǒng)人工勢場法的基本思想是編隊中各個智能體所處的環(huán)境充斥著混合勢力場，環(huán)境中的目標點充斥著引力勢場，方向是由智能體指向目標點；環(huán)境中的障礙物充斥著斥力勢場，方向是由障礙物斥力的合力指向智能體。多智能體編隊在人工勢場法的引力和斥力的合力狀態(tài)下朝向目標點運動，并且規(guī)劃出一條平滑無碰撞的路徑。

1.2.1 引力勢場函數(shù)

在混合勢場中，目標點對于智能體產(chǎn)生引力，算法中所用到的引力勢場函數(shù)如式(2)所示：

Uatt(q)=katt×(q-qg)2/2

(2)

式中:Uatt(q)為引力場;q為當前的智能體;katt為引力增量系數(shù)，其值大于零；qg為智能體與目標點的相對距離。引力Fatt(q)是由引力勢場函數(shù)的負梯度所得，計算式為式(3)所示：

Fatt(q)=-▽Uatt(q)=-katt|q-qg|

(3)

1.2.2 斥力勢場函數(shù)

在混合勢場中，障礙物對于智能體產(chǎn)生斥力，算法中所用到的斥力勢場函數(shù)，計算式如式(4)所示：

(4)

式中：q-q0表示多智能體與障礙物的距離;ρ0為障礙物的影響距離;krep為斥力增量系數(shù)。斥力Frep(q)是由斥力勢場函數(shù)的負梯度所得，大小為式(5)所示：

Frep(q)=-▽Urep(q)=

(5)

文獻[15]在斥力的分量進行了改進，解決了人工勢場法的局部極小值問題，如式(6)～(7)所示：

(6)

(7)

則在混合勢場中，智能體所受的合力如式(8)所示：

(8)

1.3 布谷鳥搜索算法

布谷鳥搜索算法(CS)是由Yang等[14]提出的一種群智能優(yōu)化算法，也是一種新型的啟發(fā)式搜索算法。該算法思想來自于布谷鳥的繁殖行為和育雛習性，主要的兩個策略是布谷鳥的巢寄繁殖方式和萊維飛行(Lěvy flight)機制。通過隨機游走的方式搜索得到一個最優(yōu)的鳥窩來孵化自己的鳥蛋，這種方式可以達到一種高效的尋優(yōu)模式[16]。萊維飛行是一類非高斯隨機過程，其平穩(wěn)增量服從Lěvy穩(wěn)定分布[17],其優(yōu)點是在飛行過程中，利用步長較小的短距離與較大步長的長距離行走相互交替，提高了全局搜索能力，不易陷入局部最優(yōu)。利用L(λ)的隨機搜索路徑思想，隨機步長的Lěvy分布如(9)所示：

L(s,λ)～s-λ； 1<λ≤3

(9)

式中s為萊維飛行得到的隨機步長。

2 基于APF與CS的編隊避障方法

針對動態(tài)環(huán)境下的隨機性障礙物，使用動態(tài)隊形變化策略下的異構(gòu)模式進行編隊避障，并利用布谷鳥搜索算法(CS)改進人工勢場法(APF)的增益系數(shù)設置的局限，用領(lǐng)航跟隨法[1]控制編隊隊形，本文提出了基于APF與CS的編隊避障方法。

2.1 改進引力與斥力的增益系數(shù)

考慮到環(huán)境障礙物的隨機分布特性，故利用布谷鳥搜索算法中萊維飛行機制的隨機搜索思想，產(chǎn)生增量系數(shù)，消除增量系數(shù)的固定值所帶來的局限性。

使用萊維飛行機制的Lěvy分布函數(shù)式(9)，改進引力場函數(shù)中的增量系數(shù)katt和斥力場函數(shù)的增量系數(shù)krep，由于編隊方向始終是朝向目標點的引力方向，式(9)所產(chǎn)生的集合，故選擇引力增量系數(shù)與斥力增量系數(shù)的值分別如式(10)、(11)所示：

katt=max(a-λ)；λ∈(1,3]

(10)

krep=min(a-λ)；λ∈(1,3]

(11)

式中a是由萊維飛行得到的隨機增量系數(shù)。

改進式(2)、(4)，如下所示：

(12)

(13)

改進后對應的引力與斥力如式(14)、(15)所示：

Fatt(q)=-▽Uatt(q)=-a-λ|q-qg|

(14)

Frep(q)=-▽Urep(q)=

(15)

2.2 效率函數(shù)

環(huán)境適應度函數(shù)[12-13]用來評價編隊隊形適應當前環(huán)境的程度，其值越小，說明該隊形變換對環(huán)境的適應度越好,計算式如式(16)所示：

fenvfit=Ifdd+Iect+Ifcct

(16)

其中：Ifdd表示為隊形失真度；Iecr表示為能量消耗率；Ifcct表示為隊形變換收斂時間比。

本文為了驗證多智能體編隊在隨機性障礙物環(huán)境的適應性，利用方差作為效率函數(shù)評價避障方法的有效性和合理性，如式(17)所示：

fenvfit=Iδ

(17)

式中：Iδ表示編隊避障過程的時間方差，其值越小說明編隊避障方法的環(huán)境適應性越強。

2.3 多智能體編隊避障方法

該方法的主要思想為：先建立常用的智能體隊形知識庫，當檢測到障礙物區(qū)域僅有有一條路徑，計算伸縮因子，選擇適合當前避障的最佳隊形；檢測到多條路徑時，使用人工勢場法

進行編隊避障，并使用領(lǐng)航跟隨法保持隊形通過障礙區(qū)。多智能體編隊避障流程如圖1所示。

圖1 多智能體編隊避障方法流程Fig. 1 Flow chart of obstacle avoidance method of multi-agent formation

3 仿真實驗及分析

為了充分驗證本文方法的有效性和合理性，進行了3組仿真實驗。選取的編隊隊形為V型(此隊形的密集編隊覆蓋觀察角最大，不易丟失隊形),使用領(lǐng)航跟隨法控制編隊隊形。每個智能體的速度為0.1 m/s，勻速運動，隊形的夾角設置為45°，環(huán)境中的障礙物個數(shù)設為150(障礙物的位置隨機生成)。為了適應環(huán)境中不同方向的編隊避障，選取3個方向：(0，π/4)，π/4，(π/4，π/2)，對應3個目標點為：(15，23)，(23，23)，(23，15)。每組實驗對比3種方法，每種方法實驗10次，得到相應編隊避障時間結(jié)果數(shù)據(jù)如表1所示，編隊避障時間是指編隊從初始點到目標點整個過程所需的時間。從表1中可以看出，本文方法的避障效率更高。

表1 不同方法10次實驗編隊避障時間Tab. 1 Formation obstacle avoidance time of different methods in ten experiments

實驗1 選取的目標點是(15，23)，V型編隊中的每個智能體的初始坐標分別是(0，0)，(-1，1)，(-1，-1)，(-2，2)，(-2，-2)。(0，0)點是領(lǐng)航智能體的坐標，其他的是跟隨智能體坐標。選擇本文方法、文獻[12]方法和文獻[5]方法，針對隨機障礙物的不同分布情況做了10次實驗，對應最優(yōu)的多智能體編隊避障圖如圖2中所示。

由圖2(a)可知，在隨機障礙物分布的環(huán)境中，多智能體編隊從開始點計算伸縮因子選擇異構(gòu)模式的人工勢場法進行動態(tài)避障，平滑的避障軌跡經(jīng)過障礙物區(qū)域，過程中用領(lǐng)航跟隨法保持編隊隊形。從整個編隊避障時間可以得出，本文方法優(yōu)于文獻[12]方法、文獻[5]方法，隊形保持相對穩(wěn)定。

由圖2(b)中可知，環(huán)境中的隨機障礙物個數(shù)多，文獻[12]方法用環(huán)境適應度函數(shù)獲得最佳隊形，使用的是柱型編隊進行避障。V型編隊從初始隊形變換成柱型隊形，然后開始進行編隊避障，到達目標點恢復到原來的隊形。此方法在初始點編隊隊形變換目標隊形需要一定的時間，在到達目標點后恢復到原來的隊形也需要時間，這兩次的時間增加了整個編隊避障的時間。

從圖2(c)中可知，在避障過程中編隊的隊形無法保持良好，文獻[5]方法是編隊避障過程中，利用遺傳算法得到最優(yōu)染色體，進行反變化換形成解數(shù)據(jù)，得到智能體的姿態(tài)信息，動態(tài)調(diào)整編隊中的智能體。雖然此方法可以將智能體的運動參數(shù)調(diào)整到最佳狀態(tài)，但是在障礙物個數(shù)多的環(huán)境中，這樣的方法實時調(diào)整智能體的姿態(tài)反而增加了等待時間，整個編隊避障效率將會降低。

實驗2 選取的目標點是(23，23)，選用本文方法、文獻[12]方法與文獻[5]方法進行對比，三種方法相應最優(yōu)的多智能體編隊避圖如圖3所示。

從圖3可知，本文方法的多智能體編隊避障時間是相比較優(yōu)的，而且在避障過程中的編隊隊形保持良好；文獻[5]方法在避障過程中沒有保持好隊形，但比文獻[12]方法的編隊避障時間優(yōu)；文獻[12]雖然避障時間較長，但在編隊過程中不用考慮隊形保持問題。

實驗3 選取的目標點是(23，15)，選用本文方法、文獻[12]方法與文獻[5]方法進行對比，三種方法相應最優(yōu)的多智能體編隊避如圖4所示。

圖2 實驗1不同方法最優(yōu)多智能體編隊避障(目標點(15,23))Fig. 2 Optimal multi-agent formation obstacle avoidance of different methods in experiment 1 (object point (15, 23))

圖3 實驗2不同方法最優(yōu)多智能體編隊避障(目標點(23,23))Fig. 3 Optimal multi-agent formation obstacle avoidance of different methods in experiment 2 (object point (23,23))

圖4 實驗3不同方法最優(yōu)多智能體編隊避障(目標點(23,15))Fig. 4 Optimal multi-agent formation obstacle avoidance of different methods in experiment 3 (object point (23,15))

從圖4可知，本文方法的多智能體編隊避障時間相比較優(yōu)，本文方法與文獻[5]方法的編隊隊形都能保持隊形。

為了進一步驗證本文方法的性能，使用隨機障礙物進行50次實驗，對本文方法、文獻[12]方法與文獻[5]方法作對比，結(jié)果如圖5所示。由圖5可知，本文方法在不同目標點的避障時間都優(yōu)于文獻[12]方法和文獻[5]方法。

圖5 不同目標點不同方法的50次實驗結(jié)果對比Fig. 5 50 experimental result comparison of different methods with different target points

使用效率函數(shù)對這10次以及50次的各個目標點編隊避障進行評價，結(jié)果如圖6所示。由圖6可知，本文方法的編隊避障時間方差相比文獻[12]方法、文獻[5]方法偏低，表明本文方法在隨機障礙物分布的動態(tài)環(huán)境下，具有較好的環(huán)境適應性以及避障高效性。

圖6 不同方法10次及50次實驗避障時間方差對比Fig. 6 Variance comparison of obstacle avoidance time for different methods between 10 and 50 experiments

4 結(jié)語

本文提出了一種人工勢場法與布谷鳥搜索算法相結(jié)合的多智能體編隊避障方法，考慮隨機性障礙物對動態(tài)隊形變換策略的影響，改進異構(gòu)模式下的避障方法。首先，根據(jù)檢測到的障礙物信息，計算伸縮因子選擇異構(gòu)模式，在此模式下使用人工勢場法進行編隊避障，為每個智能體規(guī)劃平滑無碰撞的路徑，并用領(lǐng)航跟隨法保持編隊的隊形；其次，針對人工勢場法的引力增益系數(shù)和斥力增益系數(shù)設置的局限性，使用布谷鳥搜索算法中萊維飛行機制的隨機搜索思想，搜索出適應環(huán)境的增益系數(shù)，增強了人工勢場法的環(huán)境適應性。仿真實驗結(jié)果驗證了所提方法既能動態(tài)控制編隊避障和隊形，又能適應當前環(huán)境。