基于混合蛙跳算法的移動(dòng)機(jī)器人路徑規(guī)劃

潘 翔，唐春暉，張仁杰

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

移動(dòng)機(jī)器人的路徑規(guī)劃技術(shù)，就是機(jī)器人根據(jù)自身傳感器對(duì)環(huán)境的感知，自行規(guī)劃出一條安全的運(yùn)行路線，同時(shí)高效地完成作業(yè)任務(wù)。移動(dòng)機(jī)器人的路徑規(guī)劃主要解決3 個(gè)問題［1］:(1)使機(jī)器人能從初始點(diǎn)運(yùn)動(dòng)到目標(biāo)點(diǎn)。(2)用一定的算法使機(jī)器人能夠繞開障礙物，并經(jīng)過某些必須經(jīng)過的點(diǎn)完成相應(yīng)的作業(yè)任務(wù)。(3)在完成以上任務(wù)的前提下，盡量?jī)?yōu)化機(jī)器人的運(yùn)行軌跡。目前，國(guó)內(nèi)外學(xué)者對(duì)移動(dòng)機(jī)器人的路徑規(guī)劃問題進(jìn)行了廣泛而深入的研究，就傳統(tǒng)方法而言主要有人工勢(shì)場(chǎng)法［2］、可視圖法［3］、柵格法［4］等。這些方法各有優(yōu)缺點(diǎn)，例如人工勢(shì)場(chǎng)法是利用目標(biāo)點(diǎn)對(duì)機(jī)器人的引力和障礙物對(duì)機(jī)器人斥力的綜合作用來(lái)進(jìn)行路徑規(guī)劃的，這種方法描述簡(jiǎn)單，便于實(shí)現(xiàn)實(shí)時(shí)控制，且可生成較為光滑的路徑，但其也存在當(dāng)目標(biāo)點(diǎn)附近存在障礙物從而使機(jī)器人無(wú)法到達(dá)目標(biāo)點(diǎn)，或者在兩個(gè)相近的障礙物前易產(chǎn)生振蕩等缺點(diǎn);可視圖法是以起始點(diǎn)、目標(biāo)點(diǎn)和所有多邊形障礙物頂點(diǎn)間的可行直線連線為路徑范圍來(lái)搜索最短路徑的，可視圖法的優(yōu)點(diǎn)是直觀，且可求得三維空間以下的最短路徑，但其缺點(diǎn)是當(dāng)起始點(diǎn)和目標(biāo)點(diǎn)發(fā)生改變時(shí)就需要重新構(gòu)造可視圖，因此缺乏靈活性。近年來(lái)，隨著智能仿生學(xué)算法應(yīng)用的發(fā)展，許多學(xué)者開始致力于利用智能算法解決移動(dòng)機(jī)器人的路徑規(guī)劃問題，其主要方法有人工神經(jīng)網(wǎng)絡(luò)算法［5］、遺傳算法［6］、粒子群算法［7］等。趙娟平等［8］提出了參數(shù)模糊自適應(yīng)窗口蟻群優(yōu)化算法，即利用模糊控制來(lái)優(yōu)化算法參數(shù)，同時(shí)為螞蟻建立動(dòng)態(tài)搜索窗口，并引入城市節(jié)點(diǎn)活躍度的概念以指導(dǎo)螞蟻進(jìn)行解的構(gòu)造和信息素的更新;Hsu 等［9］提出的改進(jìn)蟻群算法，一方面更新最優(yōu)路徑附近柵格的信息素，另一方面增加與目標(biāo)點(diǎn)反方向柵格的信息素，通過這種信息素更新機(jī)制可以有效避免算法在搜索過程中陷入局部最優(yōu);Wang 等［10］提出了端點(diǎn)逼近式的蟻群算法，即在迭代過程中，根據(jù)路徑上殘留信息素的強(qiáng)度以及螞蟻?zhàn)哌^的柵格的分布情況，逐漸移動(dòng)起始柵格和目標(biāo)柵格，從而縮小二者之間的距離，這樣既可簡(jiǎn)化問題的復(fù)雜度，也可加快算法的收斂速度。

混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)由Eusuf 和Lansey 為解決組合優(yōu)化問題于2003年提出［11］。作為一種新型的智能仿生優(yōu)化算法，其結(jié)合了具有較強(qiáng)局部搜索能力的模因演算法(Memetic Algorithm，MA)和具有良好全局搜索性能的粒子群算法(Particle Swarm Algorithm，PSO)的特點(diǎn)，因此其搜索尋優(yōu)能力強(qiáng)，且具有概念簡(jiǎn)單、參數(shù)調(diào)整少、易于實(shí)現(xiàn)等優(yōu)點(diǎn)。

本文利用混合蛙跳算法對(duì)移動(dòng)機(jī)器人的路徑規(guī)劃問題進(jìn)行了研究。首先利用蟻群算法生成一定數(shù)量的的路徑，然后引入混合蛙跳算法進(jìn)行全局路徑尋優(yōu)，并對(duì)最終生成的路徑進(jìn)行了簡(jiǎn)化處理，最后通過全局路徑仿真實(shí)驗(yàn)驗(yàn)證該算法的可行性和有效性。

1 基于混合蛙跳算法的機(jī)器人路徑規(guī)劃

1.1 基本思想

在相同的迭代次數(shù)內(nèi)，蟻群算法求值的精度比混合蛙跳算法要高，且可以在迭代初期迅速找到一個(gè)較優(yōu)解，但同時(shí)也易陷入局部最優(yōu);而混合蛙跳算法的搜索能力要比蟻群算法強(qiáng)，但其搜索結(jié)果在迭代過程中分布較為均勻，這使得其求得的解相對(duì)較差。因此，基于混合蛙跳算法的移動(dòng)機(jī)器人路徑規(guī)劃的實(shí)現(xiàn)思想為:首先利用蟻群算法生成N 條路徑，然后調(diào)用混合蛙跳算法，并且將這N 條路徑作為混合蛙跳算法N 只青蛙的初始值進(jìn)行全局路徑搜索。其中，以路徑形式表示的青蛙跳躍稱為子群內(nèi)的Memetic 進(jìn)化。

1.2 主要的算法策略

1.2.1 適應(yīng)度的定義及最優(yōu)青蛙評(píng)定方法

為搜索到全局最優(yōu)路徑，定義每只青蛙的適應(yīng)度為該青蛙所表示的路徑長(zhǎng)度的值，則劃分子群時(shí)按照青蛙的適應(yīng)度值升序排列個(gè)體，適應(yīng)度值最小的稱為全局最優(yōu)青蛙，每個(gè)子群中適應(yīng)度值最小的青蛙稱為該群中的最優(yōu)青蛙，反之稱為最差青蛙。

1.2.2 Memetic 進(jìn)化

每只青蛙均具有自身的文化(Meme)且被定義為問題的一個(gè)解，青蛙個(gè)體之間通過文化交流實(shí)現(xiàn)信息的交換。設(shè)計(jì)Memetic 進(jìn)化的關(guān)鍵就是如何實(shí)現(xiàn)文化信息的傳遞。

設(shè)有兩只青蛙frogA 和frogB，其具有的路徑分別為

其中，frogA 的路徑長(zhǎng)度優(yōu)于frogB 的路徑長(zhǎng)度，且下劃線表示兩只青蛙路徑重疊的部分。

要實(shí)現(xiàn)frogB 向frogA 的一次跳躍，即用frogA 中的較優(yōu)路徑［11 15］替換frogB 中的路徑［16 18 19］，若有多段不重疊的路徑，則只替換最后一段不重疊的路徑。

1.3 簡(jiǎn)化算子

對(duì)于機(jī)器人的行走路徑，除了要考慮路線最短外，還要充分考慮到機(jī)器人行走的安全性，即避免路徑中出現(xiàn)過大的拐角，因過大的拐角既會(huì)影響機(jī)器人的平衡性，又會(huì)增大其在尖峰處能量的消耗，因此路徑最優(yōu)應(yīng)該包含路徑長(zhǎng)度和安全性這兩個(gè)方面。實(shí)驗(yàn)中發(fā)現(xiàn)，最后生成的路徑中會(huì)出現(xiàn)兩條相交線段的夾角是直角或銳角的情況，這條路徑往往不是最優(yōu)的，故通過引入簡(jiǎn)化算子可去除一些不必要的節(jié)點(diǎn)來(lái)改善路徑。簡(jiǎn)化算子的原理就是利用三角形的兩邊之和大于第三邊。如圖1 所示，節(jié)點(diǎn)3 使得的拐角為直角，這樣機(jī)器人在行進(jìn)到節(jié)點(diǎn)3 時(shí)就需要轉(zhuǎn)彎90°以便繼續(xù)前進(jìn)，而通過引入簡(jiǎn)化算子，如圖2 所示，刪除節(jié)點(diǎn)3 后，一方面行走路徑變短，另一方面機(jī)器人在節(jié)點(diǎn)2 和節(jié)點(diǎn)4處只需要轉(zhuǎn)彎45°，拐角減小，更有利于機(jī)器人行走的安全性。同樣，當(dāng)遇到U 型陷阱時(shí)，為順利逃脫陷阱會(huì)出現(xiàn)如圖3 所示的路徑，通過刪除節(jié)點(diǎn)2 也可以達(dá)到優(yōu)化路徑的目的，如圖4 所示。

圖1 原始路線

圖2 修改后的路線

圖3 原始路線

圖4 修改后的路線

1.4 混合蛙跳算法的實(shí)現(xiàn)步驟

步驟1 初始化青蛙個(gè)體。將動(dòng)態(tài)保留的蟻群算法的前N 個(gè)最優(yōu)路徑賦給N 只青蛙，同時(shí)計(jì)算這N 只青蛙的適應(yīng)度。

設(shè)置初始Memetic 進(jìn)化次數(shù)in=1;初始全局信息交換次數(shù)G=1，最大全局信息交換次數(shù)為G_max。

步驟2 劃分青蛙子群。將N 只青蛙按照適應(yīng)度升序排列，并將其分成n 個(gè)子群，即第1 只青蛙進(jìn)入第1 個(gè)子群，第2 只青蛙進(jìn)入第2 個(gè)子群，第n 只青蛙進(jìn)入第n 個(gè)子群，第n+1 只青蛙進(jìn)入第1 個(gè)子群，以此類推。更新適應(yīng)度值全局最優(yōu)青蛙以及每個(gè)子群里的最優(yōu)青蛙，最差青蛙。

步驟3 Memetic 進(jìn)化。每個(gè)子群里的最差青蛙向最優(yōu)青蛙跳躍一次，若跳躍后最差青蛙的適應(yīng)度變小，則轉(zhuǎn)至步驟4;否則最差青蛙向全局最優(yōu)青蛙跳躍一次，然后轉(zhuǎn)至步驟4。

步驟4 in←in+1，若in ＜n，則轉(zhuǎn)至步驟3，否則表明n 個(gè)青蛙子群內(nèi)部均進(jìn)行了Memetic 進(jìn)化，則轉(zhuǎn)至步驟5。

步驟5 全局信息交換。G←G+1，若G ＜G_max，則轉(zhuǎn)至步驟2，否則輸出全局最優(yōu)青蛙，轉(zhuǎn)至步驟6。

步驟6 利用簡(jiǎn)化算子對(duì)全局最優(yōu)青蛙的路徑進(jìn)行優(yōu)化。輸出最優(yōu)路徑，算法結(jié)束。

2 仿真實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證混合蛙跳算法的全局尋優(yōu)能力，現(xiàn)使用Matlab 軟件對(duì)混合蛙跳算法進(jìn)行仿真，并將其與蟻群算法進(jìn)行比較與分析。

機(jī)器人的環(huán)境模型來(lái)自文獻(xiàn)［12］，各參數(shù)分別設(shè)置為:青蛙總數(shù)N=100，子群個(gè)數(shù)n=10，全局信息交換次數(shù)G_max=100。圖5 和圖6 分別為蟻群算法和混合蛙跳算法的最優(yōu)路徑圖和收斂曲線圖。

圖5 蟻群算法的最優(yōu)路徑圖和收斂曲線圖

圖6 混合蛙跳算法的最優(yōu)路徑圖和收斂曲線圖

從所尋最優(yōu)路徑可看出，兩種算法從起始點(diǎn)出發(fā)，均能成功避開障礙物并且找到一條通往目標(biāo)點(diǎn)的路徑，但混合蛙跳算法所尋路徑一方面長(zhǎng)度大幅減小，另一方面路徑的平滑度也比蟻群算法的路徑好，轉(zhuǎn)彎次數(shù)以及拐角均比蟻群算法有明顯改善，這樣更有利于機(jī)器人的安全前行;從兩種算法的收斂曲線可看出，混合蛙跳算法的收斂速度明顯加快，并且其產(chǎn)生解的波動(dòng)范圍比蟻群算法的波動(dòng)范圍要小得多，說(shuō)明混合蛙跳算法產(chǎn)生的解集中度高，穩(wěn)定性強(qiáng)。

為進(jìn)一步驗(yàn)證混合蛙跳算法的優(yōu)越性，現(xiàn)將實(shí)驗(yàn)結(jié)果與文獻(xiàn)［12］的實(shí)驗(yàn)結(jié)果進(jìn)行比較。

表1 文獻(xiàn)算法與本文算法仿真比較

需要說(shuō)明的是文獻(xiàn)［12］中的算法計(jì)算路徑長(zhǎng)度時(shí)相鄰斜對(duì)角柵格的路徑長(zhǎng)度取的是1.414，而本文算法取的是，因此文獻(xiàn)［12］尋得的最優(yōu)路徑長(zhǎng)度28.038 與文本算法最優(yōu)路徑長(zhǎng)度28.0416 其實(shí)是一致的。從表1 中可看出，本文算法和文獻(xiàn)算法都能找到最優(yōu)路徑，但在效率方面，本文算法運(yùn)行10 次有7次找到了最優(yōu)路徑，而文獻(xiàn)算法只有1 次，因此混合蛙跳算法具有更強(qiáng)的路徑搜索能力，效率更高。

同時(shí)，還選取一個(gè)更為復(fù)雜的40×40 柵格地圖，該地圖模型來(lái)自文獻(xiàn)［13］，圖7 為利用本文混合蛙跳算法得到的最優(yōu)路徑圖。

圖7 混合蛙跳算法的最優(yōu)路徑圖

利用本文算法運(yùn)行10 次，得到的最優(yōu)路徑分別為:60.669 0，61.840 6，61.254 8，60.669 0，61.254 8，61.840 6，60.426 4，61.254 8，61.840 6，60.834 0，而文獻(xiàn)［13］中得到的最優(yōu)路徑為69.213。這說(shuō)明本文提出的混合蛙跳算法在大規(guī)模柵格地圖中也能夠表現(xiàn)出良好的路徑搜索能力，且搜索過程不易陷入局部最優(yōu)，因此，可解決復(fù)雜地圖模型中的路徑規(guī)劃問題。

3 結(jié)束語(yǔ)

本文以柵格地圖作為環(huán)境模型，將混合蛙跳算法應(yīng)用于解決移動(dòng)機(jī)器人的路徑規(guī)劃問題。首先利用蟻群算法在柵格地圖中生成一定數(shù)量的路徑，然后引入混合蛙跳算法，子群內(nèi)進(jìn)行Memetic 進(jìn)化，最壞青蛙根據(jù)與子群最優(yōu)青蛙或全局最優(yōu)青蛙的路徑交點(diǎn)柵格進(jìn)行路徑更新，最后，考慮到機(jī)器人路徑行走的平滑要求，利用簡(jiǎn)化算子對(duì)算法尋得的路徑進(jìn)行優(yōu)化，以消除不必要的路徑尖峰，減小機(jī)器人在路徑拐角處的能量消耗，確保其行走的安全性。

仿真實(shí)驗(yàn)表明，本文提出的混合蛙跳算法在柵格地圖中能有效避開障礙物的同時(shí)快速地規(guī)劃出一條通往目標(biāo)點(diǎn)的優(yōu)化路徑，且較之蟻群算法，在解的優(yōu)化性、收斂性、波動(dòng)性方面均有很大提高，并由于混合蛙跳算法具有較強(qiáng)的全局搜索能力，使其也適用于大規(guī)模、障礙物覆蓋率高的環(huán)境，從而驗(yàn)證了算法的有效性和可行性。

［1］ 朱大奇，顏明重.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述［J］.控制與決策，2010，25(7):961－967.

［2］ Khatib O.Real－time obstacle avoidance for manipulators and mobile robots［J］.The International Journal of Robotics Research，1986，5(1):90－98.

［3］ Lozano－Pérez T，Wesley M A.An algorithm for planning collision－free paths among polyhedral obstacles［J］.Communications of the ACM，1979，22(10):560－570.

［4］ Mansor M A，Morris A S.Path planning in unknown environment with obstacles using virtual window［J］.Journal of Intelligent and Robotic Systems，1999，24(3):235－251.

［5］ Simon D.The application of neural networks to optimal robot trajectory planning［J］.Robotics and Autonomous Systems，1993，11(1):23－34.

［6］ Holland J H.Genetic algorithms and the optimal allocation of trials［J］.SIAM Journal on Computing，1973，2(2):88－105.

［7］ Kennedy J.Particle swarm optimization encyclopedia of machine learning［M］.US:Springer，2010.

［8］ 趙娟平，高憲文，劉金剛，等.移動(dòng)機(jī)器人路徑規(guī)劃的參數(shù)模糊自適應(yīng)窗口蟻群優(yōu)化算法［J］.控制與決策，2011，26(7):1096－1100.

［9］ Hsu C C，Hou R Y，Wang W Y.Path planning for mobile robots based on improved ant colony optimization［C］.IEEE International Conference on Systems，Man and Cybernetics(SMC)，IEEE，2013.

［10］Wang P，Tang G，Li Y，et al.Ant colony algorithm using endpoint approximation for robot path planning［C］.China:IEEE Control Conference(CCC)，2012.

［11］Eusuff M M，Lansey K E.Optimization of water distribution network design using the shuffled frog leaping algorithm［J］.Journal of Water Resources Planning and Management，2003，129(3):210－225.

［12］萬(wàn)曉鳳，胡偉，方武義，等.基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃研究［J］.計(jì)算機(jī)工程與應(yīng)用，2014，50(18):63－66.

［13］Zhou Z，Nie Y，Min G.Enhanced ant colony optimization algorithm for global path planning of mobile robots［C］.International Conference on Computational and Information Sciences(ICCIS)，IEEE，2013.