多陷阱復(fù)雜環(huán)境下機(jī)器人導(dǎo)航路徑蟻群規(guī)劃方法

王明超

（無錫工藝職業(yè)技術(shù)學(xué)院，江蘇 宜興 214200）

1 引言

移動(dòng)機(jī)器人的導(dǎo)航路徑關(guān)乎機(jī)器人自身安全、使用壽命和生產(chǎn)效率，導(dǎo)航路徑要求短而光滑，光滑路徑可以減少機(jī)器人磨損、提高行走效率[1]，因此研究機(jī)器人導(dǎo)航路徑規(guī)劃問題具有明顯的經(jīng)濟(jì)意義。

機(jī)器人導(dǎo)航路徑規(guī)劃問題分為兩大部分內(nèi)容，即環(huán)境建模與路徑規(guī)劃策略。環(huán)境建模法有柵格法、可視圖空間法、自由空間法、虛擬力場(chǎng)法等，可視圖優(yōu)點(diǎn)是線路清晰明確，容易規(guī)劃出最優(yōu)路徑，缺點(diǎn)是普適性差，且只能應(yīng)用于全局路徑規(guī)劃[2]；自由空間法是可視圖空間法的改進(jìn)方法，適用性較好，但是在復(fù)雜環(huán)境下算法復(fù)雜度極高[3]；虛擬力場(chǎng)法優(yōu)點(diǎn)是復(fù)雜度低，缺點(diǎn)是空間中障礙物分布復(fù)雜時(shí)很可能求不到最優(yōu)解；柵格法優(yōu)點(diǎn)是簡(jiǎn)單、容易理解、普適性極好，缺點(diǎn)是障礙物“膨化”方法會(huì)損失部分工作空間[4]。路徑規(guī)劃策略分為傳統(tǒng)方法和智能算法兩類，傳統(tǒng)方法有人工勢(shì)場(chǎng)法、模糊邏輯法等，人工勢(shì)場(chǎng)法原理簡(jiǎn)單、路徑光滑性，缺點(diǎn)是容易陷入局部最優(yōu)，甚至在目標(biāo)點(diǎn)附近徘徊[5]；模糊邏輯法優(yōu)點(diǎn)是不需要精確的系統(tǒng)模型，但是模糊邏輯表較難制定[6]；智能算法包括遺傳算法、神經(jīng)網(wǎng)絡(luò)、蟻群算法等[7，8]，智能算法優(yōu)勢(shì)是發(fā)揮算法智能性，規(guī)劃路徑較優(yōu)，但是問題也明顯，算法本身都存在一定缺陷，如遺傳算法運(yùn)算效率低，神經(jīng)網(wǎng)絡(luò)算法需要一定量的訓(xùn)練樣本，蟻群算法收斂速度慢、易陷局部最優(yōu)等。

研究了多障礙物復(fù)雜環(huán)境下的導(dǎo)航路徑規(guī)劃問題，將陷阱深度標(biāo)記策略和分種群搜索策略融入到蟻群算法中，提出了多種群蟻群算法。在多障礙物復(fù)雜環(huán)境中，多種群蟻群算法規(guī)劃的路徑長(zhǎng)度和迭代次數(shù)明顯優(yōu)于基本蟻群算法。

2 機(jī)器人導(dǎo)航路徑規(guī)劃問題描述

2.1 環(huán)境建模

柵格法是環(huán)境建模最為簡(jiǎn)單有效的方法，雖然在障礙物“膨化”處理時(shí)會(huì)損失部分工作空間，但是卻極大地降低了計(jì)算復(fù)雜度。

在機(jī)器人的二維工作空間中，使用固定大小的柵格劃分工作區(qū)域，當(dāng)障礙物未充滿柵格時(shí)，使用“膨化”方法使其占滿柵格。某區(qū)域的柵格模型，如圖1所示。圖中黑色柵格表示障礙物柵格，白色柵格表示不含有障礙物的自由柵格。為了區(qū)分障礙物柵格與自由柵格，為其賦不同的屬性值，其中障礙物柵格賦值為1，自由柵格賦值為0，這樣就可以將柵格模型轉(zhuǎn)化為機(jī)器人可以識(shí)別的（0～1）矩陣模型。

圖1 柵格建模法Fig.1 Grid Modeling Method

柵格的編碼方法有順序編碼法和坐標(biāo)法兩種，路徑表示時(shí)使用編碼法，距離計(jì)算時(shí)使用坐標(biāo)法，因此必須明確兩者的轉(zhuǎn)換關(guān)系，為：

式中：i—柵格順序編碼號(hào)；N—柵格規(guī)模；（xi，yi）—柵格坐標(biāo)；mod—求余運(yùn)算；fix—取整運(yùn)算。

在此需要強(qiáng)調(diào)的是，在柵格環(huán)境下，機(jī)器人路徑表示為一系列數(shù)據(jù)序列的集合｛a1，a2，…ai，…｝，使用蟻群算法在柵格環(huán)境下求解導(dǎo)航路徑時(shí)，規(guī)劃路徑的柵格數(shù)是不固定的，無需限定數(shù)據(jù)序列的維數(shù)。

2.2 建立路徑評(píng)價(jià)函數(shù)

在大多數(shù)路徑規(guī)劃問題中，一般以路徑長(zhǎng)度作為評(píng)價(jià)路徑優(yōu)劣的唯一標(biāo)準(zhǔn)，但是當(dāng)路徑中轉(zhuǎn)彎較多、轉(zhuǎn)彎較急時(shí)，會(huì)對(duì)機(jī)器人造成轉(zhuǎn)彎磨損而影響使用效率，且轉(zhuǎn)彎的存在也會(huì)影響行走效率，所以路徑平滑度極大地影響機(jī)器人使用壽命和工作效率，因此將平滑度作為路徑的一個(gè)評(píng)價(jià)指標(biāo)。

（1）路徑長(zhǎng)度Lk的計(jì)算。路徑長(zhǎng)度為相鄰柵格距離的累加和，即：

式中：a—路徑中的柵格數(shù)；D（i，i+1）—第i個(gè)柵格與第i+1個(gè)柵格的距離。在柵格環(huán)境下，D（i，i+1）只能取值為1或。

（2）路徑平滑度Sk的計(jì)算。使用路徑轉(zhuǎn)彎時(shí)的拐角大小表征路徑平滑度，轉(zhuǎn)彎時(shí)拐角大小定義方法，如圖2中α所示。

圖2 拐角大小定義方法Fig.2 Definition Method of the Corner

3 蟻群算法及分析

3.1 蟻群算法原理

以旅行商問題為背景對(duì)蟻群算法進(jìn)行分析，記需訪問的城市數(shù)量為n，蟻群中螞蟻數(shù)量為m，城市i與城市j間距離為dij，兩城市間在t時(shí)刻的信息素為τ（ijt），則螞蟻k在t時(shí)刻由當(dāng)前城市i轉(zhuǎn)移到城市j的概率

式中：ηij—啟發(fā)信息，表示螞蟻由城市i轉(zhuǎn)移到城市j的期望程度；α、β—信息素和啟發(fā)信息影響因子，代表信息素和啟發(fā)因子在路徑引導(dǎo)中的影響力，其值越大代表信息素或啟發(fā)因子影響力越大，路徑搜索收斂性越強(qiáng)，同時(shí)越容易陷入局部極值，其值越小代表路徑規(guī)劃隨機(jī)性越大，越不容易收斂，但是容易跳出局部極值；allowedk—螞蟻k可以選擇的城市集合，即allowedk=n-tabuk，tabuk表示螞蟻k的禁忌表，即螞蟻k已經(jīng)歷的城市。

螞蟻在行走過程中，邊行走邊釋放信息素，這種信息素更新方式更符合蟻群實(shí)際。信息素更新方法為：

3.2 蟻群算法應(yīng)用于柵格環(huán)境需明確的幾點(diǎn)問題

蟻群算法最早基于旅行商問題提出，鑒于柵格環(huán)境下路徑規(guī)劃問題與旅行商問題的區(qū)別，明確以下幾點(diǎn)：

（1）蟻群算法應(yīng)用于柵格環(huán)境下路徑規(guī)劃時(shí)，allowedw表示螞蟻k可以選擇的柵格集合，即與當(dāng)前柵格相鄰的自由柵格除去禁忌表tabuk中的柵格；

4 多陷阱復(fù)雜環(huán)境下改進(jìn)蟻群算法

蟻群算法存在收斂速度慢、易陷入局部最優(yōu)的問題，且在多陷阱環(huán)境下這兩個(gè)問題更加突出，提出了兩種改進(jìn)策略。

4.1 陷阱深度標(biāo)記策略

在柵格環(huán)境下，最典型的陷阱為U型陷阱。在多陷阱復(fù)雜環(huán)境中，存在一定數(shù)量的螞蟻陷入陷阱，目前解決陷阱問題存在螞蟻回退策略和螞蟻夭折策略兩種方法。螞蟻回退策略[9]為當(dāng)螞蟻陷入陷阱底部時(shí)，螞蟻邊倒退邊標(biāo)記陷阱柵格，直至回到離開陷阱，標(biāo)記的目的是避免后續(xù)螞蟻再次陷入陷阱。這種方法能夠保證螞蟻離開陷阱而完成路徑規(guī)劃，但是當(dāng)環(huán)境中存在較多陷阱或陷阱較深時(shí)，大量螞蟻經(jīng)過反復(fù)的后退、標(biāo)記、判斷，會(huì)消耗大量的運(yùn)算時(shí)間，而已經(jīng)到達(dá)目標(biāo)的螞蟻需等待這部分未到達(dá)目標(biāo)的螞蟻，如此嚴(yán)重消耗了運(yùn)算時(shí)間，降低了算法效率。

螞蟻夭折策略[10]為當(dāng)螞蟻由起始點(diǎn)搜索至目標(biāo)點(diǎn)時(shí)，路徑搜索完成，螞蟻正常死亡。當(dāng)螞蟻陷入U(xiǎn)型陷阱時(shí)螞蟻夭折，不再進(jìn)行路徑搜索，走過的路徑不再進(jìn)行信息素更新。但是當(dāng)環(huán)境中存在較多陷阱時(shí)，會(huì)出現(xiàn)一定量的螞蟻夭折，降低算法在解空間中的探索深度和解的質(zhì)量。

在多陷阱復(fù)雜環(huán)境中，針對(duì)現(xiàn)有方法存在的問題，提出了陷阱深度標(biāo)記策略。分以下兩個(gè)步驟執(zhí)行：

（1）陷阱的確認(rèn)與深度計(jì)算。當(dāng)螞蟻k第一次出現(xiàn)可選柵格只有一個(gè)時(shí)，標(biāo)記螞蟻k當(dāng)前柵格的前一柵格為Trap，且開始計(jì)數(shù)用于計(jì)算陷阱深度。當(dāng)可選柵格只有一個(gè)連續(xù)出現(xiàn)且最終無柵格可選時(shí)，說明螞蟻k陷入了U型陷阱，陷阱深度記為H；

（2）螞蟻跳躍逃出陷阱。設(shè)置一個(gè)陷阱深度閾值HT，若H＆gt;HT說明陷阱較深，在陷阱中浪費(fèi)時(shí)間較多，此時(shí)螞蟻夭折，以免拖慢算法效率；若H≤HT說明陷阱較淺，在陷阱中浪費(fèi)時(shí)間較少，此螞蟻還可以繼續(xù)使用，此時(shí)螞蟻以跳躍方式直接跳躍至柵格Trap，同時(shí)將陷阱柵格標(biāo)記為1，視為障礙物柵格，以免后續(xù)螞蟻重蹈覆轍。

分析陷阱深度標(biāo)記策略可知，以螞蟻跳躍方式逃出陷阱，避免了回退策略中反復(fù)的回退、判斷，節(jié)省了大量的運(yùn)算時(shí)間，提高了算法效率。另外，當(dāng)螞蟻陷入U(xiǎn)型陷阱時(shí)，沒有像夭折策略一樣直接扼殺，而是將陷入不深的螞蟻進(jìn)行了保留，與螞蟻夭折策略相比保留了種群規(guī)模，提高了解的質(zhì)量。

4.2 分種群搜索策略

式中：d（i，j）—柵格 i與柵格 j的距離；d（j，Goal）—下一柵格與目標(biāo)柵格距離；k1、k2—近鄰啟發(fā)因子和目標(biāo)啟發(fā)因子的影響因子，分別表征算法的隨機(jī)性和目的性。

對(duì)于第一個(gè)種群group1，設(shè)置k1＆gt;＆gt;k2＆gt;0，k1＆gt;＆gt;k2保證了算法初期具有足夠的隨機(jī)性，使螞蟻擁有足夠的自由充分探索解空間，避免算法在初期由于啟發(fā)作用過于明顯而陷入局部最優(yōu)；k2＆gt;0而不允許取為0，保證了算法具有一定的啟發(fā)引導(dǎo)作用，避免算法因完全的隨機(jī)而嚴(yán)重偏離目標(biāo)方向。對(duì)于第二個(gè)種群group2，設(shè)置k2＆gt;＆gt;k1且k1=0，這種設(shè)置方式使第二種群對(duì)路徑規(guī)劃具有較好的引導(dǎo)作用，提高算法收斂速度，且避免算法陷入極差解。

4.3 分種群蟻群算法流程

將陷阱深度標(biāo)記策略與分種群搜索策略融入到蟻群算法中，得到分種群蟻群算法步驟為：

（1）參數(shù)初始化，包括種群數(shù)量m1和m2，信息素影響因子α、啟發(fā)信息影響因子β、揮發(fā)系數(shù)ρ、陷阱深度閾值HT、近鄰啟發(fā)因子影響因子k1、目標(biāo)啟發(fā)因子影響因子k2、算法最大迭代次數(shù)N等；

（2）將兩個(gè)種群的蟻群全部放置在起始點(diǎn)，螞蟻按照式（5）和式（7）計(jì)算選擇臨近柵格的概率，而后使用輪盤賭的方法確定下一柵格；當(dāng)可選柵格只有一個(gè)時(shí)，啟動(dòng)陷阱深度標(biāo)記策略；所有螞蟻邊行走邊進(jìn)行信息素更新；

（3）當(dāng)除夭折外的所有螞蟻均到達(dá)目標(biāo)點(diǎn)時(shí)，計(jì)算所有螞蟻搜尋路徑的長(zhǎng)度并比較，輸出算法本次循環(huán)的最優(yōu)路徑；

（4）判斷算法循環(huán)次數(shù)是否達(dá)大于N，若否則算法轉(zhuǎn)至（2）；若是則算法結(jié)束，同時(shí)輸出最優(yōu)路徑。

5 實(shí)例驗(yàn)證

為了驗(yàn)證分種群蟻群算法在多陷阱復(fù)雜環(huán)境中路徑規(guī)劃的有效性，使用MATLAB軟件分別仿真出多U型障礙物環(huán)境和多障礙物兩種復(fù)雜環(huán)境，使用蟻群算法與多種群蟻群算法分別進(jìn)行路徑規(guī)劃，對(duì)比路徑優(yōu)劣。

參數(shù)設(shè)置為：種群數(shù)量m1=25、m2=5，信息素影響因子α=1、啟發(fā)信息影響因子β=6、揮發(fā)系數(shù)ρ=0.3、陷阱深度閾值HT=4、算法最大迭代次數(shù)N=50。

5.1 多U型障礙物復(fù)雜環(huán)境

仿真出20×20的U型障礙物密集分布環(huán)境，如圖3所示。環(huán)境中U型障礙物多且深，柵格環(huán)境中1號(hào)柵格為起始點(diǎn)，標(biāo)記為S，400號(hào)柵格為目標(biāo)點(diǎn)，標(biāo)記為G?；鞠伻核惴ㄊ褂梦浵伝赝瞬呗詰?yīng)對(duì)U型障礙物環(huán)境，多種群蟻群算法使用陷阱深度標(biāo)記策略應(yīng)對(duì)U型障礙物，兩種算法各運(yùn)行100次，兩算法規(guī)劃的最優(yōu)路徑結(jié)果，如圖3所示。圖中虛線為基本蟻群算法規(guī)劃的最優(yōu)路徑，實(shí)線為多種群蟻群算法規(guī)劃的路徑。

圖3 多U型障礙物環(huán)境Fig.3 Multiple U-Shaped Obstacle Environment

統(tǒng)計(jì)兩種算法的最優(yōu)路徑長(zhǎng)度、算法平均運(yùn)行時(shí)間與平均迭代次數(shù)結(jié)果，如表1所示。

表1 兩蟻群算法的運(yùn)行結(jié)果Tab.1 Computational Result of the Two Ant Colony Algorithm

由表3可以看出，基本蟻群算法在多U型障礙物環(huán)境中規(guī)劃出的路徑折線特別多，這是因?yàn)槲浵伜笸说较葳宓谝粋€(gè)柵格時(shí)不再后退而繼續(xù)規(guī)劃路徑，導(dǎo)致規(guī)劃出的路徑非常不合理；而基本蟻群算法在陷入陷阱時(shí)會(huì)將前一柵格標(biāo)記為，待確認(rèn)陷入陷阱時(shí)以跳躍的方式直接回到柵格，使路徑不存在折線。

由表1中數(shù)據(jù)可知，多種群蟻群算法規(guī)劃的最優(yōu)路徑長(zhǎng)度短于基本蟻群算法，且平均運(yùn)行時(shí)間與平均迭代次數(shù)不足基本蟻群算法的一半，這是因?yàn)榛鞠伻核惴ㄏ萑險(xiǎn)型陷阱時(shí)，螞蟻反復(fù)的回退、判斷嚴(yán)重拖慢了算法運(yùn)行時(shí)間、增加算法迭代次數(shù)；而多種群蟻群算法在確認(rèn)陷入U(xiǎn)型陷阱時(shí)，直接跳躍至柵格，沒有反復(fù)的回退與判斷過程，極大地節(jié)省了運(yùn)算時(shí)間、減少了迭代次數(shù)。

5.2 多障礙物復(fù)雜環(huán)境

仿真出20×20的多障礙物復(fù)雜環(huán)境，如圖4所示。柵格環(huán)境中1號(hào)柵格為起始點(diǎn)，標(biāo)記為S，400號(hào)柵格為目標(biāo)點(diǎn)，標(biāo)記為G。分別使用基本蟻群算法與多種群蟻群算法各進(jìn)行100次路徑規(guī)劃，兩算法規(guī)劃的最優(yōu)路徑結(jié)果，如圖5所示。虛線為基本蟻群算法規(guī)劃的最優(yōu)路徑，實(shí)線為多種群蟻群算法規(guī)劃的路徑。算法迭代過程中，最優(yōu)路徑長(zhǎng)度隨迭代次數(shù)的變化情況，如圖5所示。

圖4 多障礙物環(huán)境Fig.4 Multiple Obstacles Environment

圖5 最優(yōu)路徑長(zhǎng)度隨迭代次數(shù)變化曲線Fig.5 Changing Curve of Optimal Path Length with Iteration Time

由圖4可以看出，多種群蟻群算法規(guī)劃出的路徑明顯短于基本蟻群算法規(guī)劃出的路徑，多種群算法規(guī)劃路徑拐點(diǎn)數(shù)為5個(gè)，而基本算法規(guī)劃路徑拐點(diǎn)數(shù)為17個(gè)，說明多種群算法規(guī)劃路徑的平滑性明顯優(yōu)于基本蟻群算法。由圖5可以看出，基本蟻群算法搜索到最優(yōu)路徑時(shí)迭代了26次，而多種群算法搜索到最優(yōu)路徑時(shí)迭代了13次。為了進(jìn)一步比較多種群蟻群算法與基本蟻群算法在多障礙物環(huán)境中的路徑規(guī)劃性能，統(tǒng)計(jì)兩算法的路徑規(guī)劃結(jié)果，如表2所示。

表2 兩蟻群算法的路徑規(guī)劃結(jié)果Tab.2 Path Planning Result of the Two Ant Colony Algorithm

分析表2中數(shù)據(jù)可知，與基本蟻群算法相比，多種群蟻群算法規(guī)劃路徑的平均長(zhǎng)度減少了24.8%，最優(yōu)路徑長(zhǎng)度減少了18.2%，平均迭代次數(shù)減少了約39.1%，最少迭代次數(shù)減少了50%，以上數(shù)據(jù)充分說明多種群蟻群算法不僅規(guī)劃路徑短于基本蟻群算法，而且迭代次數(shù)也明顯減少。這是因?yàn)槎喾N群蟻群算法將蟻群分為兩個(gè)種群，分別設(shè)置不同的啟發(fā)信息，使螞蟻搜索路徑時(shí)具有不同的傾向性，兼顧了算法的隨機(jī)性、目的性和收斂性，達(dá)到了提高算法收斂速度和尋優(yōu)精度的目的。

6 結(jié)論

建立了多陷阱復(fù)雜環(huán)境下的柵格模型，提出了多種群蟻群算法用于路徑規(guī)劃，經(jīng)仿真驗(yàn)證可以得出以下結(jié)論：（1）在多U型陷阱環(huán)境下，陷阱深度標(biāo)記策略規(guī)劃的最優(yōu)路徑比螞蟻回退策略減少了4.7%，平均運(yùn)行時(shí)間和平均迭代次數(shù)減少了一倍以上，說明了陷阱深度標(biāo)記策略的規(guī)劃效率和結(jié)果遠(yuǎn)遠(yuǎn)優(yōu)于螞蟻回退策略；（2）在多障礙物復(fù)雜環(huán)境下，與基本蟻群算法相比，多種群蟻群算法規(guī)劃的路徑平均長(zhǎng)度減少了24.8%，平均迭代次數(shù)減少了近一倍，說明多種群算法中每個(gè)種群使用不同的啟發(fā)信息，可以兼顧算法的隨機(jī)性、目的性和收斂性，提高算法收斂速度和尋優(yōu)精度。