陳繼清,莫榮現(xiàn),譚成志,劉 旭,王志奎
(1.廣西大學(xué) 機(jī)械工程學(xué)院,廣西 南寧 530004;2.廣西制造系統(tǒng)與先進(jìn)制造技術(shù)重點(diǎn)實(shí)驗(yàn)室,廣西 南寧 530004)
移動(dòng)機(jī)器人是集監(jiān)測(cè)傳感、動(dòng)態(tài)決策、路徑規(guī)劃、行為控制和執(zhí)行為一體的復(fù)雜智能控制系統(tǒng)。它的“智能”主要體現(xiàn)在機(jī)器人在運(yùn)動(dòng)過(guò)程中是否具有良好的環(huán)境交互能力,這一能力主要指路徑規(guī)劃能力。對(duì)路徑規(guī)劃的研究可以追溯到20 世紀(jì)60年代,經(jīng)過(guò)幾十年的研究和發(fā)展,大量?jī)?yōu)良的算法被提出,如A?star 算法、人工勢(shì)場(chǎng)法、模糊控制算法等傳統(tǒng)算法和蟻群算法、魚(yú)群算法等仿生智能算法。其中,蟻群算法因?yàn)轸敯粜詮?qiáng)、易與其他算法結(jié)合、能并行運(yùn)算等優(yōu)點(diǎn)被廣泛用于解決移動(dòng)機(jī)器人的路徑規(guī)劃問(wèn)題。從20 世紀(jì)90年代提出至今,無(wú)數(shù)專家和學(xué)者對(duì)其進(jìn)行改進(jìn),使蟻群算法成功應(yīng)用在不同的行業(yè)。如文獻(xiàn)[8]利用蟻群算法來(lái)優(yōu)化生產(chǎn)車間的運(yùn)輸效率,有效地節(jié)約能源和降低生產(chǎn)成本;文獻(xiàn)[9]提出一種作業(yè)路徑生成算法和蟻群算法相結(jié)合的改進(jìn)蟻群算法,并應(yīng)用在無(wú)人機(jī)植保方面,有效縮短了無(wú)人機(jī)的搜索路徑等。
然而,蟻群算法也有易受參數(shù)影響、收斂速度慢、易陷入局部最優(yōu)解和前期路徑有效性差等缺點(diǎn)。根據(jù)文獻(xiàn)[10?11]和蟻群算法程序可知,蟻群算法在找到可行路徑前,每個(gè)柵格的信息素濃度都相等,蟻群算法根據(jù)轉(zhuǎn)移概率公式隨機(jī)地選擇可行柵格,這可能會(huì)出現(xiàn)蟻群算法搜尋遠(yuǎn)離目標(biāo)點(diǎn)的方向,從而增加搜索時(shí)間和加大陷入局部最優(yōu)解的概率。此外,文獻(xiàn)[10]提出的蟻群算法前期的路徑有效性差;文獻(xiàn)[12?13]提及的蟻群算法的收斂速度慢和搜索時(shí)間長(zhǎng)。為了解決這些問(wèn)題,本文提出一種改進(jìn)的蟻群算法。
蟻群算法的改進(jìn)包括兩個(gè)部分:第一個(gè)部分是提出一種方向性信息素,該信息素與目標(biāo)點(diǎn)方向的夾角有關(guān),越靠近目標(biāo)點(diǎn)方向信息素濃度越大,反之則越小。引入方向性信息素可以減少蟻群算法前期的盲目搜索,縮短搜索時(shí)間、減少轉(zhuǎn)折點(diǎn)數(shù)量和蟻群算法陷入局部最優(yōu)解的概率。第二個(gè)部分是提出一種針對(duì)方向性信息素的蒸發(fā)函數(shù),該蒸發(fā)函數(shù)能減少前期方向性信息素濃度的蒸發(fā),使蟻群算法更快速地搜索到可行路徑,進(jìn)而縮短搜索時(shí)間,減少迭代次數(shù);而后期能加快方向性信息素濃度的蒸發(fā),減少方向性信息素濃度對(duì)原有信息素濃度的影響。
根據(jù)蟻群轉(zhuǎn)移概率公式(1)可知,蟻群算法在沒(méi)有信息素殘留的初期,每個(gè)方向的概率是一樣的,因而每只螞蟻會(huì)隨機(jī)選擇搜索方向,這可能導(dǎo)致螞蟻選擇與目標(biāo)點(diǎn)方向相反的路徑進(jìn)行搜索,增加了前期的搜索時(shí)間,可能使搜尋的路徑長(zhǎng)度陷入局部最優(yōu)解。為了解決這個(gè)問(wèn)題,本文提出一種方向性信息素。方向性信息素與偏離目標(biāo)點(diǎn)方向的夾角有關(guān),當(dāng)偏離目標(biāo)點(diǎn)方向的夾角在0°~180°時(shí),夾角越小,方向性信息素的數(shù)值越大;當(dāng)偏離目標(biāo)點(diǎn)方向的夾角在180°~360°時(shí),夾角越大,方向性信息素的數(shù)值越大。
本文將方向性信息素和蟻群算法原有的轉(zhuǎn)移概率公式結(jié)合起來(lái),通過(guò)方向性信息素濃度限制蟻群算法前期對(duì)偏離目標(biāo)點(diǎn)方向的搜索,從而避免蟻群算法陷入局部最優(yōu)解和減少搜索時(shí)間。帶有方向性信息素的轉(zhuǎn)移概率公式前期大概率會(huì)選擇靠近目標(biāo)點(diǎn)方向的路徑,減少前期盲目搜索的時(shí)間。
為了設(shè)計(jì)出滿足要求的方向性信息素函數(shù),本文分兩步:第一步是確定選取基本函數(shù)種類和確定遞增遞減關(guān)系,得出函數(shù)的大概輪廓;第二步是利用實(shí)驗(yàn)的方法將函數(shù)中特殊位置的坐標(biāo)求出,然后利用插值的方法求出最終函數(shù)。
首先確定選取基本函數(shù)種類和遞增、遞減關(guān)系。方向性信息素函數(shù)與偏離目標(biāo)點(diǎn)方向的夾角有關(guān),因此選取三角函數(shù)cos和sin作為基本函數(shù)。其次,偏離目標(biāo)點(diǎn)方向的夾角為0°~360°,且當(dāng)偏離目標(biāo)點(diǎn)方向的夾角在0°~180°時(shí),夾角越小,方向性信息素的數(shù)值越大;當(dāng)偏離目標(biāo)點(diǎn)方向的夾角在180°~360°時(shí),夾角越大,方向性信息素的數(shù)值越大。為了方便函數(shù)擬合,本文規(guī)定當(dāng)偏離目標(biāo)點(diǎn)方向的夾角為180°時(shí),方向性信息素大小為0。由此可知,方向性信息素函數(shù)在0°~180°遞減,在180°~360°遞增,在夾角為180°時(shí)方向性信息素大小為0。第二步,做如下實(shí)驗(yàn):分別在偏離目標(biāo)點(diǎn)方向夾角為0°,45°和90°時(shí)加入等梯度的方向性信息素,求出0°,45°和90°的最優(yōu)路徑長(zhǎng)度對(duì)應(yīng)的方向性信息素;然后,利用函數(shù)擬合的方法求出方向性信息素的函數(shù)表達(dá)式。方向性信息素的取值范圍為[0,1.6],步長(zhǎng)為0.1。蟻群算法的基本參數(shù)為:=1;=8;=1;=0.6;=200;=50。
方向性信息素的大小和算法最優(yōu)路徑的關(guān)系如圖1 所示。
圖1 三種夾角的方向性信息素與最優(yōu)路徑的關(guān)系
從圖1 可以看出:偏離目標(biāo)點(diǎn)方向夾角為0,加入方向性信息素的值為1.4 時(shí),算法路徑最短;同理,夾角為45°和90°,加入方向性信息素分別是1.2 和0.7 時(shí),路徑最短。
0°,45°和90°與360°,325°和270°是對(duì)稱的,且當(dāng)夾角為180°時(shí)的方向性信息素濃度為0。因此,可以通過(guò)上述求出的7 個(gè)點(diǎn)擬合出方向性信息素的函數(shù)。擬合結(jié)果如下:
式中為偏離目標(biāo)點(diǎn)方向的夾角。擬合的函數(shù)圖像如圖2 所示。從圖2 可以看出,方向性信息素函數(shù)是連續(xù)的,蟻群算法的搜索方向越靠近目標(biāo)點(diǎn)方向,方向性信息素的數(shù)值越大。而由蟻群轉(zhuǎn)移概率公式可知,蟻群算法在初期階段向每個(gè)方向搜索的概率是一樣的,如果加上方向性信息素,那么靠近目標(biāo)點(diǎn)方向搜索的概率會(huì)變大,避免了前期蟻群算法其他非必要方向的搜索,可大大縮短搜索的時(shí)間;同時(shí)還可以避免路徑長(zhǎng)度陷入局部最優(yōu)解,因?yàn)榉较蛐孕畔⑺氐南拗剖瓜伻核惴ǔ繕?biāo)點(diǎn)方向搜索的概率增大,而朝著目標(biāo)點(diǎn)方向搜索的路徑長(zhǎng)度最優(yōu)。最后,增加方向性信息素的蟻群算法還可以增加前期路徑的有效性,因?yàn)榍捌谙伻核惴ㄊ菦](méi)有目標(biāo)點(diǎn)方向的盲目搜索,所以搜索的方向是隨機(jī)的,只有小部分路徑能“幸運(yùn)”地到達(dá)目標(biāo)點(diǎn),且路徑長(zhǎng)度不是最優(yōu)。而增加方向性概率的蟻群算法開(kāi)始就有目標(biāo)點(diǎn)方向的指引,能到達(dá)目標(biāo)點(diǎn)的概率增大且路徑長(zhǎng)度比蟻群算法要短,因而前期的路徑有效性增加。
圖2 方向性信息素函數(shù)圖像
方向性信息素在前期可以減少蟻群算法的搜索時(shí)間,提高算法的效率。但方向性信息素不會(huì)隨著迭代次數(shù)改變,而殘留的信息素不斷蒸發(fā),導(dǎo)致殘留信息素濃度比方向性信息素濃度小,最后使蟻群算法尋路失敗或陷入局部最優(yōu)解。為此,需要引入一種適合的蒸發(fā)函數(shù)。該蒸發(fā)函數(shù)前期需要減少方向性信息素的蒸發(fā),使改進(jìn)的蟻群算法能快速找到可行路徑,避免局部最優(yōu)解和縮短時(shí)間;而后期則加快方向性信息素的蒸發(fā),避免方向性信息素的濃度影響新增的信息素濃度,從而影響蟻群算法最優(yōu)路徑的搜索。
為了發(fā)揮方向性信息素前期的作用,避免后期方向性信息素對(duì)新增信息素的影響,需要合適的蒸發(fā)函數(shù)來(lái)調(diào)節(jié)每次迭代后的方向性信息素濃度。本文列出蟻群算法的蒸發(fā)函數(shù),通過(guò)分析該蒸發(fā)函數(shù)來(lái)確定方向性信息素的蒸發(fā)函數(shù)。蟻群算法的蒸發(fā)函數(shù)如下:
式中:是蒸發(fā)系數(shù);是迭代次數(shù);τ(0) 表示信息素的初始濃度,一般為8。
原始的蒸發(fā)函數(shù)不能滿足方向性信息素前期減少蒸發(fā)而后期加快蒸發(fā)的要求,因此本文對(duì)原有的蒸發(fā)函數(shù)進(jìn)行改進(jìn),假設(shè)方向性信息素蒸發(fā)函數(shù)的表達(dá)式如下:
式中:τ(0) 是方向性信息素的初始濃度;是待確定的系數(shù)。因?yàn)榉较蛐孕畔⑺匾谇捌诼窂降倪x擇中占主導(dǎo)作用,所以方向性信息素的初始濃度要比信息素的初始濃度高。其次,為了加快后期方向性信息素的蒸發(fā),方向性信息素的蒸發(fā)函數(shù)要比蟻群蒸發(fā)函數(shù)更快遞減。根據(jù)上述兩個(gè)條件不難得出,τ( 0 )>τ( 0 )=8 且>1。
為了求出系數(shù)和方向性信息素的初始濃度τ( 0 ),本文設(shè)計(jì)如下實(shí)驗(yàn):設(shè)置等梯度實(shí)驗(yàn)求出改進(jìn)蟻群算法路徑長(zhǎng)度和迭代次數(shù)最優(yōu)時(shí)的初始方向性信息素濃度τ( 0 )和系數(shù)。初始方向性信息素濃度τ( 0 )的取值范圍為[8,10],梯度步長(zhǎng)為1;系數(shù)的取值范圍為[1,2.5],梯度步長(zhǎng)為0.1。初始方向性信息素濃度為8,9,10 時(shí),系數(shù)與路徑長(zhǎng)度、迭代次數(shù)的關(guān)系如圖3圖5 所示。
圖3 初始濃度為8 時(shí)a 與路徑長(zhǎng)度和迭代次數(shù)的關(guān)系
由圖3 可知,當(dāng)初始濃度為8、系數(shù)為1.8 時(shí),算法路徑長(zhǎng)度最短,為42.183 8,迭代次數(shù)為76 次;由圖4 可知,初始濃度為9、系數(shù)為1.9 時(shí),算法路徑長(zhǎng)度最短且迭代次數(shù)最優(yōu),分別為42.183 8 和51;由圖5 可知,初始濃度為10、系數(shù)為1.2 時(shí),算法路徑長(zhǎng)度最短且迭代次數(shù)最優(yōu),分別為42.183 8 和49。通過(guò)上述實(shí)驗(yàn)可知,當(dāng)初始濃度取10,系數(shù)取1.2 時(shí)改進(jìn)蟻群算法路徑長(zhǎng)度和迭代次數(shù)最優(yōu),所以方向性信息素的蒸發(fā)函數(shù)表達(dá)式如下:
圖4 初始濃度為9 時(shí)a 與路徑長(zhǎng)度和迭代次數(shù)的關(guān)系
圖5 初始濃度為10 時(shí)a 與路徑長(zhǎng)度和迭代次數(shù)的關(guān)系
式中,方向性信息素的初始濃度τ( 0 )為10,系數(shù)為1.2。
引入方向性信息素蒸發(fā)函數(shù)可以減少算法初期方向性信息素濃度的蒸發(fā),使蟻群算法大概率向目標(biāo)點(diǎn)方向搜索,減少非必要方向的搜索,從而減少搜索時(shí)間;而后期則加快方向性信息素濃度的蒸發(fā),減少對(duì)殘留信息素濃度的影響。
式中,為當(dāng)前節(jié)點(diǎn)前進(jìn)方向與目標(biāo)節(jié)點(diǎn)的夾角。
由公式(6)可以看出,改進(jìn)蟻群算法的轉(zhuǎn)移概率公式由兩部分組成,前面的部分是原有的轉(zhuǎn)移概率公式,后面的部分是方向性信息素和對(duì)應(yīng)的蒸發(fā)函數(shù)。原有的轉(zhuǎn)移概率公式在開(kāi)始階段由于沒(méi)有殘留信息素,所以向每個(gè)方向搜索的概率相同,而方向性信息素越靠近目標(biāo)點(diǎn)方向數(shù)值越大,所以前期蟻群算法的搜索方向由方向性信息素決定,且大概率向目標(biāo)點(diǎn)方向搜索。而后期方向性信息素比殘留信息素蒸發(fā)快,所以后期方向性信息素對(duì)蟻群算法搜索方向的影響變小,防止蟻群算法受方向性信息素的影響而無(wú)法收斂或陷入局部最優(yōu)解。
圖6 是改進(jìn)蟻群算法的程序流程。首先初始化所有參數(shù);然后開(kāi)始循環(huán)迭代次數(shù)和螞蟻個(gè)數(shù),根據(jù)轉(zhuǎn)移概率選擇搜索節(jié)點(diǎn)并修改禁忌表;所有螞蟻搜索完成便更新原始信息素和方向性信息素,再開(kāi)始下一次迭代,直到迭代次數(shù)完成;最后輸出最優(yōu)解并結(jié)束程序。
圖6 改進(jìn)蟻群算法的程序流程
為了驗(yàn)證改進(jìn)蟻群算法的性能,將改進(jìn)蟻群算法、原始蟻群算法和文獻(xiàn)[10]算法進(jìn)行仿真分析,仿真地圖采用30×30 的隨機(jī)柵格地圖,障礙比為0.2,機(jī)器人的起點(diǎn)坐標(biāo)為(0.5,29.5),終點(diǎn)坐標(biāo)為(29.5,0.5)。三種蟻群算法的隨機(jī)地圖對(duì)比結(jié)果如圖7 所示。
圖7 30×30 障礙比為0.2 的隨機(jī)地圖對(duì)比
為了對(duì)比改進(jìn)算法和原始算法、文獻(xiàn)[10]算法的性能,本文列出路徑長(zhǎng)度、搜索時(shí)間、迭代次數(shù)的對(duì)比,如表1 所示。
表1 三種蟻群算法對(duì)比
從表1 可知,相比原始蟻群算法,改進(jìn)算法所需的迭代次數(shù)更少,路徑長(zhǎng)度也更短。迭代次數(shù)變少是因?yàn)榉较蛐孕畔⑺乜梢詼p少前期的盲目搜索,使蟻群算法能更快速地搜索到可行路徑;路徑長(zhǎng)度變短是因?yàn)榉较蛐孕畔⑺乜梢员苊庀伻核惴ㄏ萑刖植孔顑?yōu)解。文獻(xiàn)[10]的算法在路徑長(zhǎng)度、搜索時(shí)間優(yōu)于原始蟻群算法,但路徑長(zhǎng)度和搜索時(shí)間都比本文算法更長(zhǎng),因?yàn)樵撍惴ㄖ灰?guī)定了核心區(qū)域的信息素減少蒸發(fā),蟻群算法會(huì)大概率在核心區(qū)域搜索,但沒(méi)有指向目標(biāo)點(diǎn)方向的信息素,無(wú)法保證蟻群算法以最短的路徑向目標(biāo)點(diǎn)方向搜索,所以路徑長(zhǎng)度更長(zhǎng)、搜索時(shí)間也更久。
此外,圖7b)中改進(jìn)算法的收斂曲線比原始蟻群算法更快速地達(dá)到平滑,震蕩幅度更小。由表1 可知,改進(jìn)的蟻群算法性能要比原始的蟻群算法更好,路徑長(zhǎng)度縮短了3.15%,迭代次數(shù)減少了50.74%,搜索時(shí)間縮短了14.19%;相比文獻(xiàn)[10]的算法,本文算法在路徑長(zhǎng)度上縮短了1.87%,在搜索時(shí)間上減少了6.79%,在迭代數(shù)上減少了45%,本文算法在搜索時(shí)間和路徑長(zhǎng)度上優(yōu)于文獻(xiàn)[10]的算法。
本文用TurtleBot2 機(jī)器人來(lái)驗(yàn)證改進(jìn)蟻群算法的性能。TurtleBot2 是一種開(kāi)放式的機(jī)器人平臺(tái),最大的移動(dòng)速度為0.7 m/s,最大的轉(zhuǎn)向速度為180(°)/s。為了提高測(cè)試的精度,設(shè)定TurtleBot2 的線速度為0.2 m/s,角速度為30(°)/s。構(gòu)建環(huán)境地圖的傳感器是RPLIDAR A1 激光雷達(dá)。實(shí)驗(yàn)場(chǎng)地選在實(shí)驗(yàn)樓樓梯口處,場(chǎng)地尺寸為6 m×5.5 m,用Rplidar A1 構(gòu)建樓道2D 地圖。改進(jìn)的蟻群算法尋路結(jié)果和原始的蟻群算法尋路結(jié)果如圖8 和圖9 所示,選用的柵格尺寸為0.3 m×0.3 m。圖8 中的黑色區(qū)域表示障礙物區(qū)域,粉紫色為可行區(qū)域,青藍(lán)色為膨脹區(qū)域。機(jī)器人的起點(diǎn)和終點(diǎn)都相同,從圖8 和圖9 中可以看出,改進(jìn)的蟻群算法路徑更平滑,距離障礙物邊界更遠(yuǎn),減少發(fā)生碰撞的風(fēng)險(xiǎn)。為了更方便地比較改進(jìn)蟻群算法的性能,本文將兩種算法的尋路時(shí)間和路徑長(zhǎng)度進(jìn)行對(duì)比,對(duì)比結(jié)果如表2 所示。
表2 兩種算法尋路時(shí)間和路徑長(zhǎng)度的對(duì)比
從圖8和圖9可以看出,改進(jìn)的蟻群算法可以用于機(jī)器人的路徑規(guī)劃,且相比傳統(tǒng)的蟻群算法,改進(jìn)的蟻群算法搜尋的路徑更平滑,距離障礙物邊界更遠(yuǎn)。從表2 可以看出,改進(jìn)的蟻群算法在運(yùn)行時(shí)間和路徑長(zhǎng)度上都優(yōu)于原始的蟻群算法,在路徑長(zhǎng)度上縮短了4.27%,在運(yùn)行時(shí)間上減少了4.53%。因此,本文認(rèn)為改進(jìn)的蟻群算法能用于機(jī)器人的路徑規(guī)劃,且比原始的蟻群算法更優(yōu)。
圖8 改進(jìn)的蟻群算法尋路結(jié)果圖
圖9 原始的蟻群算法尋路結(jié)果圖
針對(duì)蟻群算法中存在搜索時(shí)間長(zhǎng)、收斂速度慢和容易陷入局部最優(yōu)解等問(wèn)題,本文提出一種改進(jìn)的蟻群算法。第一個(gè)改進(jìn)的部分是引入方向性信息素,該信息素可以減少蟻群算法前期的盲目搜索,降低蟻群算法的搜索時(shí)間,避免蟻群算法陷入局部最優(yōu)解。第二個(gè)部分是提出針對(duì)方向性信息素的蒸發(fā)函數(shù),使改進(jìn)的蟻群算法減少前期方向性信息素的蒸發(fā),加快可行路徑的搜索;而后期能加快方向性信息素的蒸發(fā),使改進(jìn)的蟻群算法更快收斂,避免方向性信息素對(duì)新增信息素的影響。仿真結(jié)果和機(jī)器人實(shí)驗(yàn)結(jié)果表明,改進(jìn)的蟻群算法在路徑長(zhǎng)度、迭代次數(shù)和搜索時(shí)間上相比蟻群算法和文獻(xiàn)[10]的算法有明顯的提升。后續(xù)工作是將改進(jìn)的蟻群算法和局部規(guī)劃算法結(jié)合起來(lái),使機(jī)器人能適應(yīng)動(dòng)態(tài)的實(shí)驗(yàn)環(huán)境。