劉智飛，劉冬冬

(中國石油大學(xué)(華東) 石油工業(yè)訓(xùn)練中心， 山東 青島 266580)

近年來機(jī)器人在生產(chǎn)制造業(yè)、物流、醫(yī)療、服務(wù)業(yè)等多個行業(yè)得到了廣泛應(yīng)用，不僅提高了生產(chǎn)效率，降低了生產(chǎn)成本，而且機(jī)器人可以代替人類從事勞力密集度高、危險、甚至人類無法完成的工作。路徑規(guī)劃技術(shù)是機(jī)器人的關(guān)鍵技術(shù)之一，是自主完成任務(wù)、實(shí)現(xiàn)智能化的前提，也極大地決定了機(jī)器人的工作效率[1]。因此，研究機(jī)器人路徑規(guī)劃問題對提高機(jī)器人工作效率、推動機(jī)器人廣泛應(yīng)用具有重要意義。

路徑規(guī)劃的主要任務(wù)是在滿足設(shè)定約束的前提下，為機(jī)器人規(guī)劃一條安全的最優(yōu)路徑，所謂最優(yōu)路徑是設(shè)定優(yōu)化目標(biāo)意義下的最優(yōu)路徑。根據(jù)環(huán)境信息的不同，路徑規(guī)劃可以劃分為全局路徑規(guī)劃和局部路徑規(guī)劃[2]。全局路徑規(guī)劃適用于靜態(tài)、已知的環(huán)境，這種情況下機(jī)器人可以獲得先驗地圖。局部路徑規(guī)劃適用于動態(tài)的、未知的環(huán)境，機(jī)器人只能依靠自身傳感器對周圍環(huán)境進(jìn)行探測，并實(shí)時進(jìn)行路徑規(guī)劃。路徑規(guī)劃的核心問題是規(guī)劃算法，路徑規(guī)劃方法可以分為傳統(tǒng)路徑規(guī)劃算法和仿生路徑規(guī)劃算法，傳統(tǒng)路徑規(guī)劃算法有人工勢場法[3]、A*算法[4]、柵格法[5]等，仿生的的路徑規(guī)劃算法包括遺傳算法、蟻群算法[6]、神經(jīng)網(wǎng)絡(luò)算法等。裴躍翔等[7]提出了嵌入篩選操作的遺傳算法，一方面使用改進(jìn)遺傳算法在優(yōu)化空間中細(xì)致搜索，另一方面使用標(biāo)準(zhǔn)遺傳算法進(jìn)行大范圍開拓，將此算法應(yīng)用于車身焊接路徑規(guī)劃中，得到了較好路徑。胡平志等[8]為了解決復(fù)雜山地中機(jī)器人遇到的坡度問題，將坡度約束作為啟發(fā)因素引入到蟻群算法中，得到了滿足機(jī)器人坡度約束的山地路徑。DAS等[9]提出了改進(jìn)粒子群算法，同時將差分?jǐn)z動速度算法融入到改進(jìn)粒子群算法中，得到了適用于復(fù)雜環(huán)境的路徑規(guī)劃方法。由以上分析可知，在不同環(huán)境和應(yīng)用背景下，具有不同的路徑規(guī)劃方法。在眾多規(guī)劃方法中，存在的共性問題是算法的規(guī)劃能力，通過對算法不斷改進(jìn)而得到更加優(yōu)化的路徑是當(dāng)前的研究熱點(diǎn)。

本文針對柵格環(huán)境下的路徑規(guī)劃問題，提出了具有開闊視野的蟻群算法規(guī)劃方法，對螞蟻視野、鄰域柵格、鄰域中的可選柵格進(jìn)行了重新定義，將開闊視野蟻群算法應(yīng)用于柵格環(huán)境下的機(jī)器人路徑規(guī)劃，有效減小了路徑長度并提高了路徑平滑性。

1 環(huán)境模型與算法分析

1.1 柵格環(huán)境模型

柵格環(huán)境是指使用固定尺寸的柵格將機(jī)器人工作環(huán)境進(jìn)行劃分，機(jī)器人在行駛過程中以柵格為軌跡的基本單元。使用柵格分割完畢后，對柵格內(nèi)的障礙物進(jìn)行膨化處理，即當(dāng)某柵格存在障礙物時，則障礙物膨脹而占滿整個柵格[10]。如圖1(a)為實(shí)際障礙物分布，膨化處理后如圖1(b)所示。

圖1 障礙物膨化示意圖

為了使機(jī)器人能夠識別障礙物柵格和可自由行駛柵格，本文對不同類型的柵格賦予不同的屬性值，將障礙物柵格的屬性賦值為1，將自由柵格的屬性賦值為0，從而得到機(jī)器人可以識別的0-1矩陣。以圖1所示柵格環(huán)境為例，其對應(yīng)的0-1矩陣為：

使用蟻群算法在柵格環(huán)境下進(jìn)行路徑規(guī)劃時，將螞蟻放置于起始柵格，螞蟻通過在鄰域自由柵格中不斷選擇，最終到達(dá)目標(biāo)點(diǎn)。

1.2 標(biāo)準(zhǔn)蟻群算法

在標(biāo)準(zhǔn)蟻群算法中，螞蟻依據(jù)啟發(fā)信息和信息素濃度對鄰域內(nèi)自由柵格進(jìn)行選擇，螞蟻對自由柵格的選擇概率為[11]：

(1)

當(dāng)蟻群算法完成一次迭代，則所有路徑進(jìn)行一次信息素濃度的更新，信息素濃度更新包括信息素?fù)]發(fā)和信息素殘留2個方面，即：

(2)

1.3 基于蟻群算法的路徑規(guī)劃分析

基于柵格地圖的路徑規(guī)劃方法中，由于柵格地圖的特點(diǎn)限制，主要存在4方向搜索和8方向搜索2種方法。其中4方向搜索主要指正上、正下、正左、正右4個方向的柵格，如圖2(a)所示。8方向搜索主要指正上、正下、正左、正右、左上、左下、右上、右下8個方向的柵格，如圖2(b)所示，圖中圓圈所在柵格為當(dāng)前柵格。

圖2 不同的鄰域搜索方法

在圖2(a)所示的4方向搜索方法中，螞蟻的可選柵格為鄰域內(nèi)的4個柵格，此時螞蟻的角度分辨率為90°；在圖2(b)所示的8方向搜索方法中，螞蟻的可選柵格為鄰域內(nèi)的8個柵格，此時螞蟻的角度分辨率為45°。由以上分析可知，當(dāng)前基于柵格環(huán)境的蟻群算法中，螞蟻的活動能力(即轉(zhuǎn)角分辨率)被限制在90°或者45°，這意味著螞蟻的活動能力受到了極大限制。

2 開闊視野蟻群算法

2.1 開闊視野設(shè)置方法及優(yōu)勢分析

為了提高螞蟻活動的機(jī)動能力，提出了柵格環(huán)境下具有開闊視野的蟻群算法。其核心思想為：將螞蟻的視野范圍擴(kuò)大1倍，在這種設(shè)置方式下，螞蟻的鄰域柵格由之前的8柵格變?yōu)?4柵格，如圖3所示。圖中圓形所在柵格為當(dāng)前柵格，實(shí)心圓點(diǎn)所在柵格為鄰域柵格。

圖3 不同視野螞蟻的鄰域柵格

螞蟻的視野范圍經(jīng)過擴(kuò)展以后，鄰域柵格數(shù)量上的增加可以帶來螞蟻機(jī)動能力的提高。如前文所述，在8方向搜索方式中，螞蟻運(yùn)動的角度分辨率為45°；結(jié)合圖3(b)可知，具有開闊視野的螞蟻運(yùn)動的角度分辨為22.5°，這意味著螞蟻運(yùn)動的靈活性得到了明顯提高。

將開闊視野蟻群算法與傳統(tǒng)的4方向搜索、8方向搜索進(jìn)行對比，更加能夠體現(xiàn)開闊視野蟻群算法的優(yōu)勢，以圖4所示的情況為例進(jìn)行說明。圖4中S柵格為起點(diǎn)柵格，G柵格為目標(biāo)柵格。

圖4 不同蟻群的運(yùn)動路徑

對比圖4中各種蟻群算法的規(guī)劃路徑，從轉(zhuǎn)彎次數(shù)、路徑長度、規(guī)劃次數(shù)3個角度進(jìn)行對比，結(jié)果如表1所示。設(shè)定柵格的邊框長度為1。

表1 不同算法規(guī)劃結(jié)果

結(jié)合表1和圖4可以明確看出開闊視野蟻群算法的幾點(diǎn)優(yōu)勢：① 路徑轉(zhuǎn)彎次數(shù)少，這意味著路徑更加平滑；② 規(guī)劃次數(shù)最少，這意味算法的規(guī)劃效率最高；③ 所規(guī)劃路徑長度最短，可以有效減少機(jī)器人的行駛能耗。

2.2 鄰域可選柵格的重新定義

按照開闊視野蟻群算法的鄰域設(shè)置，傳統(tǒng)關(guān)于可選柵格的定義不再適用，在此對鄰域內(nèi)的可選柵格進(jìn)行重新定義。分析圖5(a)中開闊視野蟻群的鄰域柵格可知，可以將24個鄰域柵格分為2類，一類是一步可到達(dá)的鄰域柵格，如圖5(a)中紅色三角標(biāo)出的柵格，此類柵格的可選柵格定義與傳統(tǒng)一致，也即柵格中不存在障礙物時為可選柵格。另一類是兩步可到達(dá)柵格，如圖5(a)中黑色實(shí)心圓標(biāo)出的柵格，當(dāng)此類柵格自身為自由柵格且與螞蟻間不存在障礙物遮擋時為可選柵格。

以圖5(b)為例對第2類柵格的可選柵格進(jìn)行解釋，圖5(b)中紅色實(shí)心圓所在柵格為當(dāng)前柵格，柵格1～5為其兩步可達(dá)的鄰域柵格，雖然柵格1～5均為自由柵格，但是由于柵格2、3、4與當(dāng)前柵格的連線經(jīng)過了障礙物，因此柵格2、3、4為不可選柵格，而柵格1、5與當(dāng)前柵格的連線不經(jīng)過障礙物，因此柵格1、5為可選柵格。

圖5 開闊視野蟻群的可選柵格定義

2.3 柵格選擇概率

按照2.2節(jié)可以確定當(dāng)前柵格的可選柵格，而每個可選柵格的選擇概率可以依據(jù)式(1)計算得到。在此需要明確的是，式(1)中的啟發(fā)信息ηij(t)為：

(3)

式中：sjG為柵格j與目標(biāo)柵格G之間的直線距離。

結(jié)合式(1)和式(3)計算各可選柵格的選擇概率，選擇概率最大的柵格為運(yùn)動的下一柵格。

2.4 基于開闊視野蟻群算法的路徑規(guī)劃步驟

按照開闊視野蟻群算法原理，結(jié)合工作環(huán)境的柵格模型特點(diǎn)，制定基于開闊視野蟻群算法的路徑規(guī)劃步驟為：

步驟1設(shè)置開闊視野蟻群算法參數(shù)，包括螞蟻規(guī)模、信息素因子、啟發(fā)因子、信息素?fù)]發(fā)系數(shù)、算法最大搜索次數(shù)等。

步驟2將所有螞蟻放置在起點(diǎn)柵格。

步驟3螞蟻按照2.1節(jié)方法確定鄰域中的可選柵格，根據(jù)式(1)(2)(3)計算各可選柵格的選擇概率，并選擇概率最大的柵格作為下一柵格，每只螞蟻重復(fù)執(zhí)行步驟3直至到達(dá)目標(biāo)柵格。

步驟4當(dāng)所有螞蟻到達(dá)目標(biāo)柵格時，意味著算法完成一次迭代，此時迭代次數(shù)+1。

步驟5判斷是否達(dá)到最大迭代次數(shù)，若否，則轉(zhuǎn)至步驟2；若是，則輸出最優(yōu)路徑，算法結(jié)束。

3 仿真驗證

為了驗證本文提出的開闊視野蟻群算法的規(guī)劃效果，設(shè)置15×15和30×30 2種規(guī)模的柵格環(huán)境，同時使用開闊視野蟻群算法、傳統(tǒng)的4向蟻群算法、8向蟻群算法進(jìn)行路徑規(guī)劃。算法的參數(shù)設(shè)置為：螞蟻數(shù)量為50，最大迭代次數(shù)為100，信息素因子為1.5，啟發(fā)因子為6.0，揮發(fā)系數(shù)為0.4。計算環(huán)境為Windows 10、i5CPU、內(nèi)存8 GB，仿真軟件為Matlab2017。

為了減小隨機(jī)因素的影響，同時使用3種算法在2個規(guī)模的柵格環(huán)境下進(jìn)行10次路徑規(guī)劃，2種柵格環(huán)境下10次規(guī)劃結(jié)果如圖6所示。

圖6 不同算法的10次路徑規(guī)劃結(jié)果曲線

由10次規(guī)劃路徑的長度可以看出，4方向蟻群算法的路徑長度最大，其次為8方向蟻群算法，開闊視野蟻群算法的路徑長度最小，這是因為開闊視野蟻群算法中螞蟻具有較大視野，螞蟻運(yùn)動的機(jī)動能力較強(qiáng)，路徑轉(zhuǎn)彎的角度最小分辨率僅為22.5°，轉(zhuǎn)角分辨率遠(yuǎn)遠(yuǎn)高于4方向蟻群算法和8方向蟻群算法。另外，由于本文蟻群算法具有較大的視野，當(dāng)螞蟻選擇兩步可達(dá)柵格時，則算法規(guī)劃1次相當(dāng)于另外2種算法規(guī)劃2次。因此在10次規(guī)劃結(jié)果中，開闊視野蟻群算法規(guī)劃的路徑長度遠(yuǎn)小于另外2種方法。以30×30規(guī)模柵格環(huán)境為例，給出3種蟻群算法的最短路徑，結(jié)果如圖7所示。

圖7 不同算法規(guī)劃的最短路徑

從圖7中可以明顯看出，開闊視野蟻群算法規(guī)劃的路徑最為光滑，不存在路徑折返現(xiàn)象。8方向蟻群算法規(guī)劃的最短路徑光滑性次之，4方向蟻群算法規(guī)劃的最短路徑光滑性最差，且存在一定的折返現(xiàn)象。為了進(jìn)一步進(jìn)行比較，統(tǒng)計3種蟻群算法規(guī)劃路徑的長度、迭代次數(shù)，結(jié)果如表2所示。

表2 不同算法的規(guī)劃參數(shù)

由表2中數(shù)據(jù)可知，在30×30規(guī)模的柵格環(huán)境中，開闊視野蟻群算法規(guī)劃的最短路徑長度為45.236，比8方向蟻群算法減少了14.37%；比4方向蟻群算法減少了33.88%。這是因為開闊視野蟻群算法中螞蟻活動的機(jī)動能力強(qiáng)、路徑平滑性好。從迭代次數(shù)的角度看，開闊視野蟻群算法迭代19次搜索到最短路徑，8方向蟻群算法迭代了32次，4方向蟻群算法迭代了63次，這是因為開闊視野蟻群算法的螞蟻視野范圍廣、機(jī)動能力強(qiáng)，當(dāng)螞蟻選擇2步可達(dá)柵格時相當(dāng)于另外2種算法迭代2次，因此開闊視野蟻群算法的迭代次數(shù)較少。綜合以上分析可知，本文提出的柵格環(huán)境下開闊視野蟻群算法的路徑規(guī)劃方法可以有效減少路徑長度、提高路徑平滑性。

4 結(jié)論

1) 開闊視野蟻群算法規(guī)劃的路徑長度小于4方向蟻群算法、8方向蟻群算法；

2) 開闊視野蟻群算法的螞蟻轉(zhuǎn)角分辨率較高，因此路徑平滑性優(yōu)于另外2種算法；

3) 開闊視野蟻群算法的收斂速度更快，收斂次數(shù)少于另外2種算法。