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

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

0 引言

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

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

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

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

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

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

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

ρ=Dmax/D

(1)

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

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

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

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

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

1.2 人工勢場法

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

1.2.1 引力勢場函數(shù)

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

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

(2)

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

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

(3)

1.2.2 斥力勢場函數(shù)

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

(4)

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

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

(5)

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

(6)

(7)

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

(8)

1.3 布谷鳥搜索算法

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

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

(9)

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

2 基于APF與CS的編隊(duì)避障方法

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

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

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

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

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

(10)

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

(11)

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

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

(12)

(13)

改進(jìn)后對應(yīng)的引力與斥力如式(14)、(15)所示：

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

(14)

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

(15)

2.2 效率函數(shù)

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

fenvfit=Ifdd+Iect+Ifcct

(16)

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

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

fenvfit=Iδ

(17)

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

2.3 多智能體編隊(duì)避障方法

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

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

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

3 仿真實(shí)驗(yàn)及分析

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

表1 不同方法10次實(shí)驗(yàn)編隊(duì)避障時(shí)間Tab. 1 Formation obstacle avoidance time of different methods in ten experiments

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

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

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

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

實(shí)驗(yàn)2 選取的目標(biāo)點(diǎn)是(23，23)，選用本文方法、文獻(xiàn)[12]方法與文獻(xiàn)[5]方法進(jìn)行對比，三種方法相應(yīng)最優(yōu)的多智能體編隊(duì)避圖如圖3所示。

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

實(shí)驗(yàn)3 選取的目標(biāo)點(diǎn)是(23，15)，選用本文方法、文獻(xiàn)[12]方法與文獻(xiàn)[5]方法進(jìn)行對比，三種方法相應(yīng)最優(yōu)的多智能體編隊(duì)避如圖4所示。

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

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

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

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

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

圖5 不同目標(biāo)點(diǎn)不同方法的50次實(shí)驗(yàn)結(jié)果對比Fig. 5 50 experimental result comparison of different methods with different target points

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

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

4 結(jié)語

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