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

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

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

0 引言

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

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

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

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

1 相關基礎

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

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

ρ=Dmax/D

(1)

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

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

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

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

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

1.2 人工勢場法

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

1.2.1 引力勢場函數

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

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

(2)

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

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

(3)

1.2.2 斥力勢場函數

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

(4)

式中：q-q0表示多智能體與障礙物的距離;ρ0為障礙物的影響距離;krep為斥力增量系數。斥力Frep(q)是由斥力勢場函數的負梯度所得，大小為式(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)隊形變化策略下的異構模式進行編隊避障，并利用布谷鳥搜索算法(CS)改進人工勢場法(APF)的增益系數設置的局限，用領航跟隨法[1]控制編隊隊形，本文提出了基于APF與CS的編隊避障方法。

2.1 改進引力與斥力的增益系數

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

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

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

(10)

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

(11)

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

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

(12)

(13)

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

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

(14)

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

(15)

2.2 效率函數

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

fenvfit=Ifdd+Iect+Ifcct

(16)

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

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

fenvfit=Iδ

(17)

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

2.3 多智能體編隊避障方法

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

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

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

3 仿真實驗及分析

為了充分驗證本文方法的有效性和合理性，進行了3組仿真實驗。選取的編隊隊形為V型(此隊形的密集編隊覆蓋觀察角最大，不易丟失隊形),使用領航跟隨法控制編隊隊形。每個智能體的速度為0.1 m/s，勻速運動，隊形的夾角設置為45°，環(huán)境中的障礙物個數設為150(障礙物的位置隨機生成)。為了適應環(huán)境中不同方向的編隊避障，選取3個方向：(0，π/4)，π/4，(π/4，π/2)，對應3個目標點為：(15，23)，(23，23)，(23，15)。每組實驗對比3種方法，每種方法實驗10次，得到相應編隊避障時間結果數據如表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)點是領航智能體的坐標，其他的是跟隨智能體坐標。選擇本文方法、文獻[12]方法和文獻[5]方法，針對隨機障礙物的不同分布情況做了10次實驗，對應最優(yōu)的多智能體編隊避障圖如圖2中所示。

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

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

從圖2(c)中可知，在避障過程中編隊的隊形無法保持良好，文獻[5]方法是編隊避障過程中，利用遺傳算法得到最優(yōu)染色體，進行反變化換形成解數據，得到智能體的姿態(tài)信息，動態(tài)調整編隊中的智能體。雖然此方法可以將智能體的運動參數調整到最佳狀態(tài)，但是在障礙物個數多的環(huán)境中，這樣的方法實時調整智能體的姿態(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]方法作對比，結果如圖5所示。由圖5可知，本文方法在不同目標點的避障時間都優(yōu)于文獻[12]方法和文獻[5]方法。

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

使用效率函數對這10次以及50次的各個目標點編隊避障進行評價，結果如圖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 結語

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