基于布谷鳥搜索算法的多智能體自動(dòng)避障方法

安文廣

（河北金融學(xué)院，保定 071051）

0 引言

隨著科技、智能化水平的不斷提升,智能體在眾多領(lǐng)域的應(yīng)用性普遍提高,特別是在災(zāi)害救援、空中偵察、有毒有害物質(zhì)管控方面均有較好的表現(xiàn)[1]。多智能體自動(dòng)避障即是在動(dòng)態(tài)變化的障礙環(huán)境中,規(guī)劃出合適且安全的運(yùn)動(dòng)路線,使其能夠躲避全部障礙物實(shí)現(xiàn)目標(biāo)的跟蹤,并且在環(huán)境條件允許的條件下,能以某種編隊(duì)隊(duì)形執(zhí)行任務(wù)[2,3]。通過對(duì)多智能體進(jìn)行避障控制,不僅能夠縮減任務(wù)成本花銷、也能加快任務(wù)執(zhí)行效率。因此,在利用多智能體進(jìn)行目標(biāo)搜尋、跟蹤時(shí),采用何種避障算法是確保多智能體安全、順利、無碰撞地完成任務(wù)的關(guān)鍵,具有很重要的現(xiàn)實(shí)意義。

眾多學(xué)者對(duì)多智能體避障問題進(jìn)行了相關(guān)研究,張瑋等人針對(duì)利用煙花算法對(duì)避障路徑進(jìn)行確定時(shí)的缺陷問題,通過引入“鏡面映射”規(guī)則及先鋒火花等對(duì)其進(jìn)行優(yōu)化,以此確定最短避障路線,再利用蟻群算法對(duì)其進(jìn)行優(yōu)化處理實(shí)現(xiàn)智能移動(dòng)體的避障路徑規(guī)劃,但該方法容易陷入局部最優(yōu)困局,無法獲得最合適避障路線[4]；黨霞針對(duì)包裝機(jī)器人的避障問題,提出通過基于引力勢(shì)場(chǎng)的避障方法,首先對(duì)機(jī)器人的運(yùn)動(dòng)軌跡模型進(jìn)行構(gòu)建,對(duì)其運(yùn)動(dòng)性能進(jìn)行分析,根據(jù)機(jī)器人間的引力勢(shì)場(chǎng)對(duì)其避障狀態(tài)方程進(jìn)行設(shè)計(jì),以此實(shí)現(xiàn)包裝機(jī)器人的自動(dòng)避障,但該方法中引力增益系數(shù)設(shè)定存在不足,導(dǎo)致隨機(jī)性強(qiáng)、動(dòng)態(tài)變化的障礙環(huán)境下的避障效果大打折扣[5]。因此,本文提出基于布谷鳥搜索算法的多智能體自動(dòng)避障方法,在多智能體目標(biāo)追蹤過程中,利用人工勢(shì)場(chǎng)法對(duì)其運(yùn)動(dòng)路線進(jìn)行規(guī)劃,并通過改進(jìn)布谷鳥搜索算法對(duì)其增益系數(shù)進(jìn)行優(yōu)化,提高多智能體的避障效果。

1 多智能體自動(dòng)避障

1.1 人工勢(shì)場(chǎng)法原理

人工勢(shì)場(chǎng)法的基本原理是所有智能體處于混合勢(shì)場(chǎng)的動(dòng)態(tài)環(huán)境下,其與障礙物間存在斥力場(chǎng),又與目標(biāo)之間存在引力場(chǎng),在兩種勢(shì)力場(chǎng)的共同作用下,通過勢(shì)函數(shù)實(shí)現(xiàn)其避障方向的確定,從而獲得安全、無碰撞的避障路線[6,7]。人工勢(shì)場(chǎng)法原理的實(shí)際應(yīng)用方法是在多智能體運(yùn)動(dòng)的動(dòng)態(tài)環(huán)境中,U為構(gòu)建的勢(shì)場(chǎng),由兩部分過程,其一為目標(biāo)對(duì)多智能體的引力場(chǎng),其方向是從多智能體到目標(biāo)位置,其二為障礙物對(duì)多智能體的斥力場(chǎng),其方向是障礙物到多智能體。U為引力、斥力勢(shì)能之和,多智能體在U狀態(tài)下,通過不斷躲避運(yùn)動(dòng)區(qū)域障礙物抵達(dá)目標(biāo)位置。

1.1.1 引力函數(shù)

在人工勢(shì)場(chǎng)法中,引力勢(shì)場(chǎng)函數(shù)與距離相關(guān),對(duì)于多智能體、目標(biāo)而言,二者間的距離是勢(shì)力函數(shù)的影響因素,多智能體受到的勢(shì)能大小與距離的遠(yuǎn)近成正比[8],當(dāng)勢(shì)能不斷降低,說明多智能體與目標(biāo)間距離越小,直到多智能體抵達(dá)目標(biāo)處時(shí),其勢(shì)能降低為0。引力勢(shì)場(chǎng)函數(shù)可通過式(1)進(jìn)行描述：

式(1)中：對(duì)于當(dāng)下智能體z,與目標(biāo)位置的相對(duì)距離表示為zg,引力增益系數(shù)表示為katt,其引力Fatt(z)可通過Uatt(z)的負(fù)梯度進(jìn)行描述,如式(2)所示：

1.1.2 斥力函數(shù)

對(duì)于動(dòng)態(tài)環(huán)境下的障礙物,其周圍產(chǎn)生的勢(shì)場(chǎng)與多智能體具有相斥性,且與二者間距離成反比關(guān)系[9],即二者相距距離越短,排斥性越大。斥力勢(shì)場(chǎng)函數(shù)可通過式(3)進(jìn)行描述：

式(3)中：對(duì)于多智能體,與障礙物間的距離表示為z-z0,斥力增益參數(shù)表示為krep,對(duì)于障礙物,其斥力可作用的距離表示為ρ0,其斥力可通過Urep(z)的負(fù)梯度進(jìn)行描述,如式(4)所示：

總勢(shì)能的公式可定義如式(5)所示：

對(duì)于多智能體,其合力公式的描述如式(6)所示：

1.2 改進(jìn)布谷鳥搜索算法原理

1.2.1 布谷鳥搜索算法（CS）

CS搜索算法是基于布谷鳥巢寄生、育雛行為以及萊維飛行機(jī)制的智能化搜索策略[10],與其余算法的差別即是其獨(dú)特的搜索方式,即萊維飛行機(jī)制,方向及步長(zhǎng)是該機(jī)制的主要內(nèi)容,前者通過均勻分布進(jìn)行確定,后者滿足Levy分布,且具有隨機(jī)性,可通過Mantegn法則實(shí)現(xiàn)。CS算法實(shí)現(xiàn)一般需滿足以下條件：

1）各布谷鳥對(duì)鳥巢的選取依據(jù)隨機(jī)性,且各鳥巢僅有1個(gè)鳥蛋。

2）布谷鳥子代選擇優(yōu)質(zhì)鳥巢,以確保CS算法具有最佳解。

3）n為備選鳥巢個(gè)數(shù),其值為定值,可搜索到的鳥蛋概率表示為pa,且pa∈[0,1]。

上述條件具有理想化特點(diǎn),通過CS算法可獲得局部最佳位置、全局最佳位置,前者可通過式(7)進(jìn)行調(diào)節(jié)：

其中：對(duì)于鳥巢i,其第t代的結(jié)果為該結(jié)果經(jīng)全局調(diào)整獲得的最新結(jié)果表示為。點(diǎn)對(duì)點(diǎn)乘法表示為⊕,步長(zhǎng)控制因子、步長(zhǎng)分別表示為γ、λ,Levy(λ)需滿足Levy分布函數(shù),其如式(8)所示：

通過式(9)可生成Levy的隨機(jī)數(shù),如式(9)所示：

其中：Levy的分布μ、壓縮因子v滿足標(biāo)準(zhǔn)正態(tài)分布。系數(shù)φ的表達(dá)式如式(10)所示：

僅利用萊維飛行機(jī)制的全局搜索無法滿足高準(zhǔn)確度要求,需結(jié)合局部搜尋方法完成位置的調(diào)整,局部最佳位置可通過式(11)進(jìn)行調(diào)整：

其中：滿足均勻分布的任意數(shù)為r,且r∈(0,1),迭代t次后,任意兩個(gè)位置表示為

1.2.2 改進(jìn)布谷鳥搜索算法

其中：在迭代t次時(shí),群體的最佳位置表示為慣性系數(shù)表示為的更新公式描述如式(13)、式(14)所示：

式(13)、式(14)中：wmax、wmin表示權(quán)重的最大、最小值；搜索范圍的界線分別為a、b,且b＞a。

改進(jìn)布谷鳥搜索算法實(shí)施過程為：

1）對(duì)布谷鳥個(gè)體所在位置的優(yōu)劣進(jìn)行判斷,并按從優(yōu)到差順序排列。

2）將布谷鳥種群分成兩組,其中位置較好的一組通過式(11)確定局部最佳解,可有效擴(kuò)大其搜索區(qū)域。另一組則通過式(12)獲取局部最佳解,雖然此組個(gè)體不具備較好的初始位置,但通過逐步獲取最佳位置,可有效提升個(gè)體搜索的準(zhǔn)確度。改進(jìn)后的布谷鳥搜索算法具備突出局部搜索性能的同時(shí),可提升其全局搜索能力。

1.3 基于人工勢(shì)場(chǎng)法與改進(jìn)布谷鳥搜索算法的多智能體自動(dòng)避障

在動(dòng)態(tài)環(huán)境下,多智能體存在對(duì)環(huán)境具有較低適應(yīng)性,編隊(duì)需要花費(fèi)較長(zhǎng)時(shí)間的缺點(diǎn),本文采用人工勢(shì)場(chǎng)法實(shí)現(xiàn)多智能體的自動(dòng)避障,通過改進(jìn)布谷鳥搜索算法對(duì)增益系數(shù)進(jìn)行優(yōu)化。

1.3.1 基于改進(jìn)布谷鳥搜索算法的增益系數(shù)優(yōu)化

在動(dòng)態(tài)環(huán)境中,障礙物的分布呈現(xiàn)任意性特點(diǎn),而人工勢(shì)場(chǎng)法生成的增益系數(shù)存在不變性,故采用改進(jìn)布谷鳥搜索算法對(duì)其進(jìn)行優(yōu)化,獲取合適增益系數(shù),為多智能體規(guī)劃出準(zhǔn)確避障路徑,提高避障精度[12,13]。利用式(8)對(duì)引力增益系數(shù)、斥力增益系數(shù)進(jìn)行優(yōu)化,由于多智能體是沿著目標(biāo)點(diǎn)引力方向進(jìn)行編隊(duì)飛行,即式(9)的Levy分布集合,此時(shí),引力增益系數(shù)可通過(15)式進(jìn)行描述：

斥力增益系數(shù)的描述公式如式(16)所示。

其中：基于萊維飛行機(jī)制,獲得的增益系數(shù)為β,滿足任意性原則。

將式(15)代入到引力勢(shì)場(chǎng)函數(shù)中對(duì)其進(jìn)行改進(jìn),改進(jìn)后公式如式(17)所示：

將式(16)代入到斥力勢(shì)場(chǎng)函數(shù)中對(duì)其進(jìn)行改進(jìn),改進(jìn)后公式描述如式(18)所示：

由此可確定引力、斥力表達(dá)式,分別用式(19)、式(20)描述：

1.3.2 效率函數(shù)

多智能體飛行隊(duì)形是否適合于當(dāng)下動(dòng)態(tài)環(huán)境可通過環(huán)境適應(yīng)度函數(shù)進(jìn)行描述[14],若其編隊(duì)隊(duì)形與動(dòng)態(tài)環(huán)境具有較好的適應(yīng)性,則具有較低適應(yīng)度函數(shù)值,該函數(shù)可通過式(21)進(jìn)行表達(dá)：

式(21)中：對(duì)于多智能體編隊(duì)隊(duì)形,其失真度表示為Kfdd,能量損失率表示為Kect,形式轉(zhuǎn)換中的收斂時(shí)間比表示為Kcct。

多智能體所處的動(dòng)態(tài)環(huán)境下,障礙物呈任意性分布,為分析多智能體對(duì)環(huán)境的適應(yīng)度,本文通過方差指標(biāo)進(jìn)行評(píng)估,視其為效率函數(shù)對(duì)多智能體的自動(dòng)避障路徑進(jìn)行判斷[15],如式(22)所示：

其中：對(duì)于多智能體,在其自動(dòng)避障時(shí),其時(shí)間方差表示為Kδ,其值決定了多智能體自動(dòng)避障過程對(duì)環(huán)境的適應(yīng)度,該值越低,說明多智能體避障路徑與環(huán)境的適合度高。

1.3.3 多智能體自動(dòng)避障

在實(shí)施多智能體自動(dòng)避障前,需先對(duì)其編隊(duì)隊(duì)形知識(shí)庫進(jìn)行構(gòu)建,再對(duì)避障線路進(jìn)行判斷,當(dāng)只有1條避障路線時(shí),根據(jù)隊(duì)形伸縮因子選擇最佳隊(duì)形,實(shí)現(xiàn)多智能體的自動(dòng)避障；當(dāng)避障路徑較多時(shí),采用改進(jìn)布谷鳥搜索算法優(yōu)化后的人工勢(shì)場(chǎng)法實(shí)現(xiàn)多智能體避障,并依據(jù)領(lǐng)航跟隨法對(duì)避障隊(duì)形進(jìn)行有效維護(hù)。多智能體自動(dòng)避障過程如圖1所示。

圖1 多智能體自動(dòng)避障過程

多智能體自動(dòng)避障過程為：

第一步：確定多智能體編隊(duì)的原始隊(duì)形,并對(duì)動(dòng)態(tài)障礙物環(huán)境進(jìn)行檢測(cè),識(shí)別目標(biāo)點(diǎn)坐標(biāo)。

第二步：根據(jù)障礙物檢測(cè)結(jié)果確定多智能體的避障路徑,當(dāng)只存在一條避障線路時(shí),在對(duì)障礙物進(jìn)行膨化處理的基礎(chǔ)上,對(duì)隊(duì)形的伸縮因子ρ進(jìn)行確定,當(dāng)滿足ρ≥1條件時(shí),則以原始隊(duì)形通過障礙區(qū)域,否則,繼續(xù)判斷是否滿足ρm≤ρ＜1條件,若條件滿足,則仍采用原始隊(duì)形進(jìn)行避障,但需對(duì)隊(duì)形進(jìn)行壓縮,縮減各智能體間的距離。反之,則需對(duì)fenvfit進(jìn)行運(yùn)算,根據(jù)其結(jié)果選擇合適的編隊(duì)隊(duì)形進(jìn)行避障。

第三步：當(dāng)存在多條避障路線時(shí),在對(duì)障礙物進(jìn)行膨化處理的前提下,仍需對(duì)隊(duì)形的伸縮因子ρ進(jìn)行計(jì)算,當(dāng)其值滿足條件ρ＜ρm時(shí),通過改進(jìn)布谷鳥搜索算法優(yōu)化后的人工勢(shì)場(chǎng)法確定多智能體的避障方向,根據(jù)fenvfit計(jì)算結(jié)果確定多智能體的編隊(duì)隊(duì)形,以此多智能體完成一次自動(dòng)避障。反之,返回到第二步。

第四步：判斷多智能體是否抵達(dá)目標(biāo)坐標(biāo),若任務(wù)未完成,則需繼續(xù)進(jìn)行飛行任務(wù),并返回到步驟二,反之,飛行任務(wù)結(jié)束。

2 實(shí)驗(yàn)分析

以多智能體為研究對(duì)象,設(shè)定動(dòng)態(tài)環(huán)境下障礙物數(shù)量為30,目標(biāo)點(diǎn)數(shù)量為2,其坐標(biāo)表示為（30,12）、（36,0）,智能體數(shù)量為5,各智能體標(biāo)記為A-E,其坐標(biāo)為（-20,-2.5）、（-25,4.5）、（-26,-2.5）、（-23,10）、（-23,-11）,且分別以0.3m/s、2m/s、1.5m/s、1m/s、0.8m/s速度向目標(biāo)點(diǎn)移動(dòng),多智能體編隊(duì)隊(duì)形夾角40度,應(yīng)用本文方法為多智能體提供避障規(guī)劃,驗(yàn)證本文方法的避障能力。

采用本文方法對(duì)多智能體進(jìn)行避障規(guī)劃,使其順利抵達(dá)目標(biāo)點(diǎn)（30,12）,通過不同時(shí)刻各智能體的避障狀態(tài),分析本文方法的自動(dòng)避障性能,避障過程中各智能體在不同時(shí)刻的運(yùn)動(dòng)狀態(tài)如圖2所示。

圖2 多智能體避障過程

分析圖2可知,采用本文方法對(duì)多智能體的運(yùn)動(dòng)路線進(jìn)行避障規(guī)劃,確定避障路線只有1條,在t=0時(shí)刻,各智能體處于雜亂運(yùn)動(dòng)狀態(tài),尚未形成編隊(duì)隊(duì)形,但運(yùn)動(dòng)方向均朝向目標(biāo)點(diǎn),經(jīng)1.1s后完成初始編隊(duì),并以V型編隊(duì)運(yùn)動(dòng)；當(dāng)發(fā)現(xiàn)前方障礙物后,采取V形編隊(duì)并對(duì)該隊(duì)形進(jìn)行壓縮方式實(shí)現(xiàn)障礙物的自動(dòng)避障,最終順利抵達(dá)目標(biāo)坐標(biāo)。實(shí)驗(yàn)結(jié)果表明,本文方法可根據(jù)動(dòng)態(tài)環(huán)境下障礙物的分布,判斷實(shí)現(xiàn)多智能體的自動(dòng)避障。

以（36,0）坐標(biāo)作為目標(biāo)點(diǎn),采用本文方法對(duì)多智能體的運(yùn)動(dòng)路線進(jìn)行自動(dòng)避障,通過分析多智能體的避障過程驗(yàn)證本文方法的避障能力,實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 多智能體避障能力分析

分析圖3可知,各智能體能夠在1.6s后迅速集結(jié)成編隊(duì)隊(duì)形對(duì)（36,0）位置的目標(biāo)進(jìn)行追蹤,當(dāng)遇到障礙物后,可快速規(guī)劃出避障軌跡,采用沿障礙物兩邊繞行方式完成自動(dòng)避障,并且能在躲避障礙物后恢復(fù)到原始V型隊(duì)形,最終抵達(dá)目標(biāo)坐標(biāo)。由實(shí)驗(yàn)結(jié)果表明,本文方法可實(shí)現(xiàn)避障路線規(guī)劃,并能夠確定適合的避障隊(duì)形,實(shí)現(xiàn)多智能體的自動(dòng)避障。

在多智能體對(duì)目標(biāo)（30,18）、（36,0）的追蹤過程中,采用時(shí)間方差指標(biāo)評(píng)估其避障性能的優(yōu)劣,為驗(yàn)證本文方法的避障效果,障礙物選擇遵循隨機(jī)性原則,并通過10次避障實(shí)驗(yàn)獲取方差均值實(shí)現(xiàn)避障性能的分析,實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 多智能體避障性能分析

分析圖4可知,在對(duì)各目標(biāo)進(jìn)行追蹤過程中,時(shí)間方差指標(biāo)均較低,其中（30,12）目標(biāo)的方差均值低于0.1、（36,0）目標(biāo)的方差均值低于0.15,說明采用本文避障方法后,多智能體對(duì)動(dòng)態(tài)環(huán)境具有較高適應(yīng)度,能夠?qū)崿F(xiàn)最優(yōu)避障路線規(guī)劃,取得突出避障效果。

3 結(jié)語

以多智能體為研究對(duì)象,采用本文方法對(duì)分布于動(dòng)態(tài)環(huán)境下的不同目標(biāo)點(diǎn)進(jìn)行避障跟蹤,通過分析多智能體對(duì)各目標(biāo)的避障跟蹤過程分析本文方法的自動(dòng)避障性能,并通過時(shí)間方差指標(biāo)驗(yàn)證本文方法的避障效果。實(shí)驗(yàn)結(jié)果表明：本文方法能夠?qū)?dòng)態(tài)環(huán)境下隨機(jī)分布的障礙物進(jìn)行自動(dòng)避障,規(guī)劃不同避障路線,且具有較低的方差均值、顯著的避障效果。