基于改進(jìn)的五行環(huán)算法的移動(dòng)機(jī)器人路徑規(guī)劃

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

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

0 引 言

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

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

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

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

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

圖1 環(huán)境模型

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

2.1 五行環(huán)模型

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

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

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

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

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

2.2 路徑規(guī)劃

2.2.1 PSO算法

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

2.2.2 突變元子［13］

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

2.2.3 散開元子

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

圖3 散開元子示意

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

1）更新機(jī)制

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

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

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

式中 κ為縮小因素。

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

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

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

2.2.5 連接點(diǎn)刪除［16］

圖4為連接點(diǎn)刪除的簡單示意，黑色虛線為連接點(diǎn)刪除之前的路徑，淺色實(shí)線為刪除連接點(diǎn)之后的路徑。

圖4 連接點(diǎn)刪除示意

3 仿真與分析

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

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

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

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

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

從表1中數(shù)據(jù)可得，A*算法在路徑規(guī)劃中的路徑長度是最長的；GA和PSO算法總體上穩(wěn)定性較高，但有少數(shù)波動(dòng)情況，導(dǎo)致平均路徑大于最短路徑，拐點(diǎn)數(shù)目也較多；五行環(huán)優(yōu)化算法的數(shù)據(jù)波動(dòng)最大，穩(wěn)定性低，導(dǎo)致最短路徑和平均路徑差距較大；改進(jìn)五行環(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，在對其進(jìn)行連接點(diǎn)刪除處理之后，甚至能達(dá)到26.129 cm和27.602 5 cm的最短路徑。

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

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

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

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

圖7 收斂效果

4 結(jié) 論

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