淺析基于蟻群算法的機器人路徑規(guī)劃

王軼毅 呂行軍

摘要：現(xiàn)有大量的針對機器人路徑規(guī)劃的算法，但蟻群算法具有其獨特優(yōu)勢。為了探究蟻群算法在機器人路徑規(guī)劃上的應(yīng)用，對蟻群算法進行了簡單研究，總結(jié)出其基本原理與螞蟻選擇路徑的過程，之后通過設(shè)置變量、簡列公式，計算出信息素濃度與路徑長短的關(guān)系，并設(shè)計出其算法流程。又對路徑規(guī)劃問題進行了簡單分析，發(fā)現(xiàn)蟻群算法的應(yīng)用可以使機器人找到一條到達目的地最短路徑，最后通過Matlab仿真確定信息素濃度與路徑長短的關(guān)系，提高了分析的準(zhǔn)確性，使其更有說服力。

關(guān)鍵詞：蟻群算法;路徑規(guī)劃;最短路徑;信息素濃度

0引言

機器人作為高科技時代的產(chǎn)物，對其路徑規(guī)劃能力的研究是極其重要的一方面。根據(jù)已知的環(huán)境信息和未知的環(huán)境信息，路徑規(guī)劃分為已知環(huán)境信息的全局規(guī)劃和未知環(huán)境信息的局部規(guī)劃兩部分。另外，對于機器人路徑規(guī)劃有很多的算法。全局規(guī)劃方面，如遺傳算法[1]、快速隨機搜索樹算法、人工蜂群算法等等;對于局部規(guī)劃，有人工勢場法[2]、模糊算法、A*算法[3]等等。

本文要講的蟻群算法具有較強的通用性和魯棒性，并且適合在圖上探索路徑問題。蟻群算法通過對螞蟻尋找食物的抽象化來研究信息素的揮發(fā)等因素對路徑規(guī)劃的影響。以此來使用蟻群算法對機器人的路徑規(guī)劃進行進一步探究。

1簡述蟻群算法

1.1基本原理

螞蟻在覓食時，會在經(jīng)過的路徑上釋放一種名為信息素的物質(zhì)，螞蟻之間通過信息素傳遞消息，當(dāng)一條路徑上信息素濃度較大時，說明此路徑上的螞蟻個數(shù)較多，其它的螞蟻也就會有更大概率選擇這條路徑[4]。另外，信息素會隨著時間的推移而揮發(fā)。剛開始有一部分螞蟻經(jīng)過某路徑，之后少數(shù)螞蟻經(jīng)過此路徑，最后沒有螞蟻經(jīng)過此路徑，另一條被多數(shù)螞蟻選擇的路徑的信息素濃度比此路徑的信息素濃度高，經(jīng)過一段時間，所有的螞蟻都會選擇信息素濃度較高的路徑，最終形成一條最優(yōu)路徑。

此過程進行以下抽象：螞蟻的巢穴視為起點，食物視為終點，信息素的濃度越大說明這條路徑越短，可以將信息素濃度的大小作為螞蟻選擇路徑的依據(jù)。螞蟻在尋找食物時總是會大概率選擇信息素濃度較大的一條路徑，類似于最短路徑的問題。

1.2工作過程

如圖1，A為螞蟻巢穴，E為食物點，可供選擇的路徑為ABCE或ABDE，假設(shè)DE=DC，BC>BD，每只螞蟻釋放的信息素濃度為1，信息素每過1s揮發(fā)1，第一次外出覓食的螞蟻為20只，即AB的初始信息素濃度為20，令20只螞蟻分為兩組，每組10只，分別經(jīng)過BD和BC，假設(shè)BD長度為0.05m，BC長度為0.15m，設(shè)螞蟻行走速率為0.05m/s。由于DE=BC，所以只需在意BD段與BC段之間的差異。

使用（1）求出螞蟻經(jīng)過BD、BC的時間，如圖1a。由于信息素每過一段時間會揮發(fā)，使用（2）求出螞蟻到達D點和C點后BD和BC的信息素濃度，如圖1b。BD濃度大于BC濃度，螞蟻通過現(xiàn)存信息素濃度得出BD<BC，所以當(dāng)仍有螞蟻到達B點后，大概率會選擇BD，隨著時間的推移，選擇BC的螞蟻將會越來越少，最后螞蟻不選擇BC，而全部選擇BD段，ABDE就成為了螞蟻覓食的最短路徑。

t表示時間，s表示兩點間距離，v表示螞蟻的速度，c表示信息素濃度，n表示螞蟻個數(shù)。

1.3算法步驟

步驟1：設(shè)置參數(shù)。包括螞蟻數(shù)量、螞蟻行進速率、信息素揮發(fā)量、信息素初始值、兩點間距離等參數(shù)的設(shè)置。

步驟2：計算時間。兩點距離已知，行進速率已知，可以求出經(jīng)過某一點到達另一點的時間，為計算剩余信息素濃度做準(zhǔn)備。

步驟3：更新剩余信息素濃度。由于信息素的揮發(fā)，所以每過一段時間要計算剩余信息素濃度，方便研究螞蟻所做出的決策。

步驟4：根據(jù)濃度選擇最優(yōu)路線。螞蟻可以通過比較不同路段信息素濃度的大小判斷出哪一條路徑是到達下一點的最短路徑，形成局部最優(yōu)解。

步驟5：是否滿足終止條件。是否到達食物點，當(dāng)沒有到達時，經(jīng)過下一個不止一條路徑的路口時，重復(fù)步驟2、步驟3、步驟4。當(dāng)滿足終止條件時，結(jié)束此算法。

2簡述機器人路徑規(guī)劃問題

機器人路徑規(guī)劃問題是根據(jù)某一方面的指標(biāo)（消耗最少、路徑最短、所需時間最短），在規(guī)定區(qū)域內(nèi)選擇出一條由起點到終點最優(yōu)的路徑，簡單來說就是在某些約束條件下得到某個問題所需最優(yōu)解的問題[5]。根據(jù)周圍環(huán)境的掌握程度，機器人路徑規(guī)劃分為全局路徑規(guī)劃和局部路徑規(guī)劃，前者是一種宏觀的規(guī)劃，主要為機器人在運動中提供核心運動點，保證機器人如期、按要求到達目的地，但是全局路徑規(guī)劃生成的不是一條連續(xù)的軌跡，而是一些離散的點，因此又稱為離散域路徑規(guī)劃。而為了使機器人的路線更加合理，就產(chǎn)生了局部路徑規(guī)劃，它是在機器人執(zhí)行任務(wù)時，隨時根據(jù)自身所攜帶的感應(yīng)器收集周圍環(huán)境信息，進行實時的路徑規(guī)劃，在局部路徑規(guī)劃中，機器人由收集的周圍環(huán)境的信息得出的路徑很大概率上只是局部最優(yōu)而不是全局最優(yōu)，這便是它的局限性，局部路徑規(guī)劃得到的是一條連續(xù)的軌跡，所以也稱其為連續(xù)域路徑規(guī)劃[6]。

3基于蟻群算法的機器人路徑規(guī)劃分析

為了進一步分析蟻群算法對于路徑規(guī)劃的影響，使用Matlab將圖1復(fù)雜化，如圖2，其中A點為起點，J點為終點，其中圖2a的各路徑的權(quán)重采用經(jīng)過一段時間后信息素濃度的倒數(shù)，路徑權(quán)重越小，說明信息素濃度越大。圖2b的各路徑的權(quán)重為兩點間的距離，不難發(fā)現(xiàn)，兩者的解吻合。依據(jù)圖2，表示機器人可以尋找到一條到達目的地最優(yōu)的路徑，此路徑為該算法下的最短路徑。

4結(jié)論

對基于蟻群算法的路徑規(guī)劃進行了研究，最后得出了剩余信息素的濃度越大，選擇此條路徑的概率就越大的結(jié)論，隨著時間的推移，越來越多的螞蟻會選擇信息素濃度大的路徑，最終就會形成尋找食物的最優(yōu)路徑。另外，當(dāng)信息素濃度的揮發(fā)程度增大時，原本信息素濃度就小的路徑隨著時間的推移，信息素濃度會變得更小，這也使得選擇這條路徑的可能性減小，進而去選擇信息素濃度較大的路徑。

通過對蟻群算法的研究，發(fā)現(xiàn)此算法在機器人的規(guī)劃路徑中具有重大意義，可以使機器人找到一條到達目的地最短的路徑。

參考文獻

[1]石鐵峰，改進遺傳算法在移動機器人路徑規(guī)劃中的應(yīng)用.計算機仿真，2011.28（04）：p.193-195+303.

[2]劉建華，et?al.，基于勢場蟻群算法的移動機器人全局路徑規(guī)劃方法.農(nóng)業(yè)機械學(xué)報，2015.46（09）：p.18-27.

[3]沈顯慶，et?al.，改進A～*算法的移動機器人的路徑規(guī)劃.黑龍江科技大學(xué)學(xué)報，2021.31（04）：p.494-499.

[4]史恩秀，et?al.，基于蟻群算法的移動機器人全局路徑規(guī)劃方法研究.農(nóng)業(yè)機械學(xué)報，2014.45（06）：p.53-57.

[5]霍鳳財，et?al.，移動機器人路徑規(guī)劃算法綜述.吉林大學(xué)學(xué)報（信息科學(xué)版），2018.36（06）：p.639-647.

[6]宋曉茹，et?al.，移動機器人路徑規(guī)劃綜述.計算機測量與控制，2019.?27（04）：p.1-5+17.