基于布谷鳥搜索算法的多智能體自動避障方法

安文廣

（河北金融學院，保定 071051）

0 引言

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

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

1 多智能體自動避障

1.1 人工勢場法原理

人工勢場法的基本原理是所有智能體處于混合勢場的動態環境下,其與障礙物間存在斥力場,又與目標之間存在引力場,在兩種勢力場的共同作用下,通過勢函數實現其避障方向的確定,從而獲得安全、無碰撞的避障路線[6,7]。人工勢場法原理的實際應用方法是在多智能體運動的動態環境中,U為構建的勢場,由兩部分過程,其一為目標對多智能體的引力場,其方向是從多智能體到目標位置,其二為障礙物對多智能體的斥力場,其方向是障礙物到多智能體。U為引力、斥力勢能之和,多智能體在U狀態下,通過不斷躲避運動區域障礙物抵達目標位置。

1.1.1 引力函數

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

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

1.1.2 斥力函數

對于動態環境下的障礙物,其周圍產生的勢場與多智能體具有相斥性,且與二者間距離成反比關系[9],即二者相距距離越短,排斥性越大。斥力勢場函數可通過式(3)進行描述：

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

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

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

1.2 改進布谷鳥搜索算法原理

1.2.1 布谷鳥搜索算法（CS）

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

1）各布谷鳥對鳥巢的選取依據隨機性,且各鳥巢僅有1個鳥蛋。

2）布谷鳥子代選擇優質鳥巢,以確保CS算法具有最佳解。

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

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

其中：對于鳥巢i,其第t代的結果為該結果經全局調整獲得的最新結果表示為。點對點乘法表示為⊕,步長控制因子、步長分別表示為γ、λ,Levy(λ)需滿足Levy分布函數,其如式(8)所示：

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

其中：Levy的分布μ、壓縮因子v滿足標準正態分布。系數φ的表達式如式(10)所示：

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

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

1.2.2 改進布谷鳥搜索算法

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

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

改進布谷鳥搜索算法實施過程為：

1）對布谷鳥個體所在位置的優劣進行判斷,并按從優到差順序排列。

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

1.3 基于人工勢場法與改進布谷鳥搜索算法的多智能體自動避障

在動態環境下,多智能體存在對環境具有較低適應性,編隊需要花費較長時間的缺點,本文采用人工勢場法實現多智能體的自動避障,通過改進布谷鳥搜索算法對增益系數進行優化。

1.3.1 基于改進布谷鳥搜索算法的增益系數優化

在動態環境中,障礙物的分布呈現任意性特點,而人工勢場法生成的增益系數存在不變性,故采用改進布谷鳥搜索算法對其進行優化,獲取合適增益系數,為多智能體規劃出準確避障路徑,提高避障精度[12,13]。利用式(8)對引力增益系數、斥力增益系數進行優化,由于多智能體是沿著目標點引力方向進行編隊飛行,即式(9)的Levy分布集合,此時,引力增益系數可通過(15)式進行描述：

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

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

將式(15)代入到引力勢場函數中對其進行改進,改進后公式如式(17)所示：

將式(16)代入到斥力勢場函數中對其進行改進,改進后公式描述如式(18)所示：

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

1.3.2 效率函數

多智能體飛行隊形是否適合于當下動態環境可通過環境適應度函數進行描述[14],若其編隊隊形與動態環境具有較好的適應性,則具有較低適應度函數值,該函數可通過式(21)進行表達：

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

多智能體所處的動態環境下,障礙物呈任意性分布,為分析多智能體對環境的適應度,本文通過方差指標進行評估,視其為效率函數對多智能體的自動避障路徑進行判斷[15],如式(22)所示：

其中：對于多智能體,在其自動避障時,其時間方差表示為Kδ,其值決定了多智能體自動避障過程對環境的適應度,該值越低,說明多智能體避障路徑與環境的適合度高。

1.3.3 多智能體自動避障

在實施多智能體自動避障前,需先對其編隊隊形知識庫進行構建,再對避障線路進行判斷,當只有1條避障路線時,根據隊形伸縮因子選擇最佳隊形,實現多智能體的自動避障；當避障路徑較多時,采用改進布谷鳥搜索算法優化后的人工勢場法實現多智能體避障,并依據領航跟隨法對避障隊形進行有效維護。多智能體自動避障過程如圖1所示。

圖1 多智能體自動避障過程

多智能體自動避障過程為：

第一步：確定多智能體編隊的原始隊形,并對動態障礙物環境進行檢測,識別目標點坐標。

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

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

第四步：判斷多智能體是否抵達目標坐標,若任務未完成,則需繼續進行飛行任務,并返回到步驟二,反之,飛行任務結束。

2 實驗分析

以多智能體為研究對象,設定動態環境下障礙物數量為30,目標點數量為2,其坐標表示為（30,12）、（36,0）,智能體數量為5,各智能體標記為A-E,其坐標為（-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速度向目標點移動,多智能體編隊隊形夾角40度,應用本文方法為多智能體提供避障規劃,驗證本文方法的避障能力。

采用本文方法對多智能體進行避障規劃,使其順利抵達目標點（30,12）,通過不同時刻各智能體的避障狀態,分析本文方法的自動避障性能,避障過程中各智能體在不同時刻的運動狀態如圖2所示。

圖2 多智能體避障過程

分析圖2可知,采用本文方法對多智能體的運動路線進行避障規劃,確定避障路線只有1條,在t=0時刻,各智能體處于雜亂運動狀態,尚未形成編隊隊形,但運動方向均朝向目標點,經1.1s后完成初始編隊,并以V型編隊運動；當發現前方障礙物后,采取V形編隊并對該隊形進行壓縮方式實現障礙物的自動避障,最終順利抵達目標坐標。實驗結果表明,本文方法可根據動態環境下障礙物的分布,判斷實現多智能體的自動避障。

以（36,0）坐標作為目標點,采用本文方法對多智能體的運動路線進行自動避障,通過分析多智能體的避障過程驗證本文方法的避障能力,實驗結果如圖3所示。

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

分析圖3可知,各智能體能夠在1.6s后迅速集結成編隊隊形對（36,0）位置的目標進行追蹤,當遇到障礙物后,可快速規劃出避障軌跡,采用沿障礙物兩邊繞行方式完成自動避障,并且能在躲避障礙物后恢復到原始V型隊形,最終抵達目標坐標。由實驗結果表明,本文方法可實現避障路線規劃,并能夠確定適合的避障隊形,實現多智能體的自動避障。

在多智能體對目標（30,18）、（36,0）的追蹤過程中,采用時間方差指標評估其避障性能的優劣,為驗證本文方法的避障效果,障礙物選擇遵循隨機性原則,并通過10次避障實驗獲取方差均值實現避障性能的分析,實驗結果如圖4所示。

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

分析圖4可知,在對各目標進行追蹤過程中,時間方差指標均較低,其中（30,12）目標的方差均值低于0.1、（36,0）目標的方差均值低于0.15,說明采用本文避障方法后,多智能體對動態環境具有較高適應度,能夠實現最優避障路線規劃,取得突出避障效果。

3 結語

以多智能體為研究對象,采用本文方法對分布于動態環境下的不同目標點進行避障跟蹤,通過分析多智能體對各目標的避障跟蹤過程分析本文方法的自動避障性能,并通過時間方差指標驗證本文方法的避障效果。實驗結果表明：本文方法能夠對動態環境下隨機分布的障礙物進行自動避障,規劃不同避障路線,且具有較低的方差均值、顯著的避障效果。