黃敬堯，劉洪宇，武慧慧，王欽甜

（三峽大學(xué) 電氣與新能源學(xué)院，湖北 宜昌 443002）

0 引 言

路徑規(guī)劃是移動機器人的熱門研究之一，隨著科技的進步和社會的發(fā)展，移動機器人智能化和自動化的水平逐步提高，已經(jīng)逐漸滲透到日常的生活中［1］。移動機器人需要規(guī)劃出從工作環(huán)境的起點位置到目標(biāo)位置的路徑，并且滿足效能高、安全性高等要求，還必須能夠避開沿途的障礙物。移動機器人的路徑規(guī)劃具有重要的研究意義和價值，國內(nèi)外學(xué)者已將其作為研究熱點。

作為智能搜索法的遺傳算法（genetic algorithm，GA）、蟻群算法、粒子群優(yōu)化（particle swarm optimization，PSO）算法等算法，可以通過隨機的可行初始解出發(fā)以及迭代改進的策略，不斷地逼近最優(yōu)路徑，從而求出最優(yōu)解。楊洋等人針對多自動導(dǎo)引運輸車（automated guided vehicle，AGV）避障路徑優(yōu)化問題，提出一種改進蟻群算法和彈性時間窗相結(jié)合的多AGV避障路徑優(yōu)化策略［2］。不僅能在無人倉庫中實現(xiàn)多AGV快速規(guī)劃，同時還能找到最優(yōu)的躲避障礙物的路徑。羅陽陽等人針對PSO算法能快速收斂，但容易陷入局部最優(yōu)的問題，設(shè)計了一種突變算子來提高全局尋優(yōu)能力［3］。雖然迭代次數(shù)會大幅增多，但其需要調(diào)節(jié)的參數(shù)較少，在更新機制中僅需要追蹤2 個“極值”來進行不斷的更新，也是很有可取之處的。

本文提出一種改進的五行環(huán)算法來解決機器人路徑規(guī)劃問題。在五行環(huán)模型的基礎(chǔ)上，采用PSO算法的更新機制來對元素進行更新。為了避免過早出現(xiàn)的較優(yōu)解使得種群陷入局部最優(yōu)解陷阱，采用變異的思想，設(shè)計了突變元子。為了避免種群快速趨同而降低元素的搜索效率，設(shè)計了散開元子。最后對路徑進行連接點刪除，刪除了不必要的連接點，使得路徑更優(yōu)。通過仿真結(jié)果表明，采用改進的五行環(huán)算法能夠使移動機器人找到最優(yōu)路徑的同時具有高度的穩(wěn)定性，也證明了算法改進的可行性和有效性。

1 問題描述與環(huán)境建模

本文將環(huán)境映射為柵格地圖，即將環(huán)境轉(zhuǎn)化為由相同大小格子構(gòu)成的一個柵格矩陣［4，5］。對每個柵格以實數(shù)進行編碼，將實際障礙物對應(yīng)的柵格以0填充，在地圖中以黑色表示，對可行區(qū)域以1 填充，以白色表示。本文采用20 ×20和30 ×30的兩種柵格地圖，如圖1 所示。每個柵格的邊長為1，其中機器人的起始點與目標(biāo)點都已標(biāo)明。

圖1 環(huán)境模型

2 改進五行環(huán)算法的移動機器人路徑規(guī)劃

2.1 五行環(huán)模型

五行環(huán)模型［6］是建立在五行（金、水、木、土、火）相生相克原理的基礎(chǔ)上，通過計算各個體之間的相互作用關(guān)系如圖2，比較出個體適應(yīng)值的優(yōu)劣，然后來對解進行更新，從而找出系統(tǒng)的最優(yōu)解。

圖2 五行元素相互關(guān)系

從圖2中可以看出，5種元素之間，由相生關(guān)系和相克關(guān)系建立了各個元素之間的關(guān)系，既相互促進又相互克制，形成了一個復(fù)雜的動態(tài)平衡［7］。為了將其應(yīng)用到各種復(fù)雜的優(yōu)化問題，文獻［8］提出了五行環(huán)算法，并且將它推廣到了一般形式，其一般表達(dá)式為

式中 mij（t）為第t 代中第j 個環(huán)中第i 個元素的質(zhì)量，F(xiàn)ij（t）為元素的力。假設(shè)復(fù)雜系統(tǒng)中總共有h 個環(huán)（j ＝1，2，…，h），y個元素（i ＝1，2，…，y），則種群的規(guī)模為h×y。

在五行環(huán)模型中，每個環(huán)中的元素Fij（t）都由4 個部分的力組成：1）上輩元素的“生”力：若上輩元素的質(zhì)量大于元素本身的質(zhì)量，則此部分力為正值，反之力為負(fù)值。2）祖輩元素的“克”力：其力本身為負(fù)值，若元素本身的質(zhì)量大于其祖輩元素的質(zhì)量，則力變?yōu)檎怠?）本元素對子元素的“生”力：這部分力會使自身能量產(chǎn)生損耗，因此為負(fù)值。4）本元素對祖輩元素的“克”力：同樣在施加力的過程中消耗了自身的能量，因此其力也為負(fù)值。式（1）中質(zhì)量的表達(dá)采用的是logsig 函數(shù)，其用來表示在力的作用下質(zhì)量的變化。其中，i ＝1 時，用y 替代i -1，用y -1 替代i-2；i ＝2時，用y替代i-2；i ＝y(tǒng)-1時，用1替代i ＋2；i ＝y(tǒng)時，用1替代i ＋1，用2替代i ＋2。

2.2 路徑規(guī)劃

2.2.1 PSO算法

在PSO算法中，群體中所有個體都被抽象為在d維空間中無重量和體積的粒子，并在搜索空間中以不同的速度飛行［9］。粒子在飛行時，通過追蹤2 個“極值”來不斷地更新自己的速度和位置，一個是全局極值，一個是個體極值［10］，其更新的速度和位置公式如下

2.2.2 突變元子［13］

具體突變方式是：先將實數(shù)編碼轉(zhuǎn)換為二進制編碼，再隨機生成一個整數(shù)（不能大于有效編碼的總長度的整數(shù)值）作為突變連接點的個數(shù)，然后在編碼區(qū)內(nèi)隨機確定突變的連接點位置，在突變位置上對該連接點進行突變（將1→0，0→1），最后將其轉(zhuǎn)化為實數(shù)編碼。

2.2.3 散開元子

為了減輕元素快速趨同帶來的不利影響，本文設(shè)計了散開元子［14］。對搜索空間中處于某一位置上的多個相同的元素僅保留一個，而對其余的元素進行突變使其離開原來的位置，突變方法和2.2.2節(jié)一致。如圖3 所示，在某一搜索空間中，如果同時聚集了3 個以上的元素，則元素A保持不變，其余元素被移至其他的位置；如果聚集了不到3個元素，則允許它們都保留在原位。

圖3 散開元子示意

2.2.4 改進的五行環(huán)算法

1）更新機制

通過對Fij（t）的計算，可以將結(jié)果分為Fij（t）＞0 和Fij（t）≤0兩類。若Fij（t）＞0，則采用式（2）的更新機制對元素群進行更新，并使用散開元子避免出現(xiàn)快速趨同的現(xiàn)象；若Fij（t）≤0，則xij（t）使用突變元子更新。

2）mij（t）變化規(guī)則

在使用五行環(huán)模型時，采用xij（t）表示第t代中第j個環(huán)的第i個元素的解，即xij（t）表示一條可行路徑，而S 表示搜索連接點的總個數(shù)。用（xd，yd）表示第d 個連接點的坐標(biāo)，d ＝1，2，…，S，重新定義mij（t），mij（t）表示一條可行路徑的歐氏距離，其表達(dá)式為

式中 κ為縮小因素。

3）適應(yīng)度函數(shù)

每個元素的適應(yīng)度函數(shù)［15］表達(dá)式為

改進的五行環(huán)算法具體步驟為：1）初始化參數(shù)，隨機生成種群。2）通過式（1）計算mij（0）。3）通過式（1）計算Fij（t），根據(jù)結(jié)果采用不同的更新機制。4）計算各個元素群的適應(yīng)度值，并通過式（3）計算mij（t ＋1）。5）如果沒達(dá)到最大迭代次數(shù)T，則令t ＝t ＋1，繼續(xù)返回進行步驟（3）；如果達(dá)到最大迭代次數(shù)T則結(jié)束整個流程。

2.2.5 連接點刪除［16］

圖4為連接點刪除的簡單示意，黑色虛線為連接點刪除之前的路徑，淺色實線為刪除連接點之后的路徑。

圖4 連接點刪除示意

3 仿真與分析

對比了五行環(huán)優(yōu)化算法、PSO算法、GA和A*算法，并分別置于2種不同柵格環(huán)境的2種不同復(fù)雜度的地圖中進行路徑規(guī)劃，并進行仿真與比較分析。圖5 是柵格環(huán)境為20 ×20的簡單和復(fù)雜地圖（障礙物覆蓋率為30%）不同算法的路徑規(guī)劃。僅展示不同地圖的改進五行環(huán)算法、五行環(huán)優(yōu)化算法和PSO算法3種算法的路徑規(guī)劃。

圖5 不同復(fù)雜度地圖的20 ×20 機器人路徑規(guī)劃路線

從圖5中可以明顯觀察到，當(dāng)3 種算法不論是在簡單地圖還是在復(fù)雜地圖中規(guī)劃的最優(yōu)路線中，五行環(huán)優(yōu)化算法能用較短時間規(guī)劃出一條路徑，但其穩(wěn)定性極差，局部搜索能力不強，規(guī)劃出來的路徑較長。PSO 算法在進行路徑規(guī)劃時極其容易陷入局部最優(yōu)解的陷阱中，搜索時間較長，收斂效果較差。而本文改進的五行環(huán)算法規(guī)劃出的路徑軌跡最為平滑，拐點數(shù)目明顯少于其他算法，能在短時間內(nèi)規(guī)劃處最短的無碰撞的路徑。

表1為各算法在20 ×20 柵格環(huán)境不同復(fù)雜度地圖的路徑規(guī)劃數(shù)據(jù)，設(shè)每個柵格邊長1 cm。

表1 5 種算法的數(shù)據(jù)比較（20 ×20 地圖）

從表1中數(shù)據(jù)可得，A*算法在路徑規(guī)劃中的路徑長度是最長的；GA和PSO算法總體上穩(wěn)定性較高，但有少數(shù)波動情況，導(dǎo)致平均路徑大于最短路徑，拐點數(shù)目也較多；五行環(huán)優(yōu)化算法的數(shù)據(jù)波動最大，穩(wěn)定性低，導(dǎo)致最短路徑和平均路徑差距較大；改進五行環(huán)算法在穩(wěn)定性上遠(yuǎn)優(yōu)于五行環(huán)優(yōu)化算法，規(guī)劃出的路徑長度也比其他算法短，在簡單環(huán)境地圖中的最短路徑和平均路徑都能保持在26.307 1 cm，在復(fù)雜環(huán)境地圖中的最短路徑和平均路徑都能保持在28.4493 cm，在對其進行連接點刪除處理之后，甚至能達(dá)到26.129 cm和27.602 5 cm的最短路徑。

本文設(shè)計了柵格環(huán)境為30 ×30的簡單和復(fù)雜地圖（障礙物覆蓋率為30%），不同算法的路徑規(guī)劃如圖6。

圖6 不同復(fù)雜度地圖的30 ×30 機器人路徑規(guī)劃路線

從表2中可知，改進五行環(huán)算法在更大的柵格地圖中仍然能穩(wěn)定地規(guī)劃出一條最優(yōu)路徑，路徑長度和拐點數(shù)目都明顯優(yōu)于其他算法。在對連接點進行刪除處理后，簡單地圖中的路徑長度可以縮短至25.284 6 cm，復(fù)雜地圖中的路徑長度可縮短至43.791 9 cm。

圖7為改進的五行環(huán)算法的收斂曲線?？梢悦黠@看出，在迭代次數(shù)為100次時，本文算法在第8代時就已經(jīng)收斂并保持穩(wěn)定狀態(tài)，而其他算法都達(dá)不到這么快的收斂速度。

圖7 收斂效果

4 結(jié) 論

本文結(jié)合五行環(huán)優(yōu)化算法和粒子群算法的優(yōu)點，提出了一種改進的五行環(huán)算法，用柵格法對環(huán)境進行建模，通過2種不同柵格環(huán)境、4 個不同復(fù)雜度的地圖、5 種不同算法來對機器人的行駛路徑進行規(guī)劃。而且路徑上的障礙物數(shù)量的不同、路徑規(guī)劃空間的不同，更體現(xiàn)了改進的五行環(huán)算法的優(yōu)勢。通過更新機制、突變元子、散開元子和連接點刪除等一系列流程后，所得的路徑更優(yōu)、長度更短。仿真結(jié)果表明：改進的五行環(huán)算法改進使得種群粒子能夠跳出局部最優(yōu)解，提高了算法的性能，也就是說算法的收斂速度和算法的穩(wěn)定性都得到了大幅提升。