劉建娟，劉忠璞，張會(huì)娟，袁 航，姬淼鑫

(河南工業(yè)大學(xué)a.電氣工程學(xué)院；b.機(jī)電設(shè)備及測(cè)控技術(shù)研究所，鄭州 450000)

0 引言

在科技進(jìn)步和工業(yè)發(fā)展的推動(dòng)下，以AGV為代表的移動(dòng)機(jī)器人已經(jīng)廣泛運(yùn)用到各類行業(yè)的技術(shù)革新和發(fā)展之中。如醫(yī)療行業(yè)的特殊服務(wù)機(jī)器人、智慧城市建設(shè)中AGV的設(shè)計(jì)和使用[1]。

路徑規(guī)劃是AGV技術(shù)中的重點(diǎn)和難點(diǎn)，保證AGV獲得一條安全、節(jié)能、無(wú)碰撞的最優(yōu)路徑，完成相應(yīng)的作業(yè)任務(wù)。在國(guó)內(nèi)外的研究中，AGV路徑規(guī)劃算法種類眾多[2]，包括Dijkstra算法、A*算法、人工勢(shì)場(chǎng)法、遺傳(GA)算法、粒子群(PSO)算法[3]、快速探索隨機(jī)樹(shù)(RRT)算法[4]以及蟻群(ACO)算法等。不同種類的算法優(yōu)劣各不相同，如A*算法搜索速度快但尋優(yōu)路徑并不是全局最優(yōu)[5]；遺傳算法(GA)具有較強(qiáng)的魯棒性，但是算法復(fù)雜，規(guī)劃效率不高，并且存在尋優(yōu)早熟現(xiàn)象[6]。其中，蟻群算法簡(jiǎn)單并且具備良好的全局搜索能力，在目前的路徑規(guī)劃研究和工程應(yīng)用中是常用算法。

蟻群算法(ant colony algorithm)是一種具有正反饋和啟發(fā)式搜索特性的生物啟發(fā)式算法[7]。傳統(tǒng)的蟻群搜索算法存在收斂速度慢、效率低等問(wèn)題。國(guó)內(nèi)外學(xué)者對(duì)此進(jìn)行相應(yīng)改進(jìn)，LIANG等[8]提出一種結(jié)合遺傳算法和蟻群算法的融合算法，解決蟻群算法容易出現(xiàn)早熟的現(xiàn)象，提高了蟻群算法的有效性和魯棒性，但算法存在迭代速度緩慢，存在冗余節(jié)點(diǎn)的問(wèn)題；AJEIL等[9]提出了一種螞蟻種群迭代優(yōu)化機(jī)制。該機(jī)制提出老齡化螞蟻群的概念，并根據(jù)老齡化螞蟻的數(shù)量和迭代結(jié)果計(jì)算和更新路徑權(quán)重，以提高ACO算法的全局收斂性和穩(wěn)定性。但該機(jī)制容易造成蟻群搜索多樣性大幅降低，增加算法陷入局部最優(yōu)的可能性。姚曉通等[10]引入帶權(quán)重的節(jié)點(diǎn)概率搜索公式，并通過(guò)自定義信息素?fù)]發(fā)因子更新機(jī)制進(jìn)一步增加蟻群算法有向性引導(dǎo)和搜索能力，但在該機(jī)制的作用下，蟻群定向搜索能力加強(qiáng)，破壞全局多樣性搜索和比較的平衡能力，在復(fù)雜環(huán)境中缺陷性較大。ZHENG等[11]提出一種“獎(jiǎng)懲”策略，用于改進(jìn)信息素更新效果，在一定程度上促進(jìn)蟻群搜索收斂速度，但對(duì)于復(fù)雜障礙環(huán)境，蟻群搜索存在高度冗余性，“獎(jiǎng)懲”策略的使用存在一定的局限，不利于全類型場(chǎng)景使用。杜力等[12]提出一種融合螢火蟲(chóng)算法的復(fù)合蟻群算法，通過(guò)螢火蟲(chóng)算法進(jìn)行蟻群算法參數(shù)優(yōu)化，通過(guò)精英策略促進(jìn)全局極值搜索和收斂，但該方法減弱了蟻群算法的全局隨機(jī)程度，存在收斂陷入局部極值的問(wèn)題。

常規(guī)的蟻群算法在路徑規(guī)劃中存在路徑最優(yōu)性低、算法收斂速度緩慢等問(wèn)題。為解決上述問(wèn)題，本文在保證蟻群算法多樣性搜索的基礎(chǔ)上提出一種改進(jìn)的智能自適應(yīng)蟻群算法。本文改進(jìn)蟻群算法，融合模糊控制技術(shù)，引入新的信息素更新策略，優(yōu)化信息素更新效果。同時(shí)，改進(jìn)節(jié)點(diǎn)搜索概率公式，動(dòng)態(tài)調(diào)整蟻群算法節(jié)點(diǎn)概率搜索公式的計(jì)算因子，加快算法的收斂速度。此外，本文提出基于幾何優(yōu)化的路徑節(jié)點(diǎn)優(yōu)化算法，優(yōu)化最短路徑，減少冗余節(jié)點(diǎn)，動(dòng)態(tài)更新最優(yōu)路徑。本文提出的改進(jìn)蟻群算法，能夠進(jìn)一步減短最優(yōu)路徑長(zhǎng)度，加快算法迭代收斂次數(shù)，避免算法陷入在局部最優(yōu)，保證多樣性。

1 環(huán)境建模與蟻群算法

1.1 環(huán)境建模

實(shí)際環(huán)境地圖是AGV路徑規(guī)劃的主要應(yīng)用場(chǎng)景。為了與路徑規(guī)劃算法相結(jié)合，環(huán)境地圖常常使用柵格地圖[13]建模的方式展現(xiàn)，如圖1所示。其中黑色陰影區(qū)域?yàn)闁鸥竦貓D中的障礙物標(biāo)識(shí)區(qū)域，空白區(qū)域?yàn)锳GV允許運(yùn)行區(qū)域。

圖1 二維柵格地圖建模

假設(shè)實(shí)際環(huán)境地圖為正方形地圖，柵格化建模后，以柵格地圖的左下角為坐標(biāo)系原點(diǎn)建立OXY坐標(biāo)系，每個(gè)柵格的長(zhǎng)度為一個(gè)單位a，柵格地圖每一行共有M個(gè)柵格，那么柵格地圖的柵格數(shù)總量為M*M個(gè)。設(shè)當(dāng)前AGV所在柵格為第G個(gè)柵格，那么此時(shí)AGV所在位置的二維坐標(biāo)(x,y)可由式(1)和式(2)計(jì)算。

(1)

(2)

式中，mod為取余符號(hào)；ceil為向上舍入的取整符號(hào)。

此外，實(shí)際環(huán)境地圖存在不全為正方形的特殊情況。對(duì)于此，柵格化建模通常采用“地圖規(guī)則化”處理，即擴(kuò)大柵格化地圖范圍，其中擴(kuò)大的柵格范圍設(shè)定為AGV不可行區(qū)域的處理方式，如圖2所示。其中，圖2a為實(shí)際地圖俯視圖，陰影區(qū)域?yàn)檎系K物，圖2b為柵格化建模地圖，條狀陰影區(qū)域?yàn)閿U(kuò)大范圍的地圖障礙物區(qū)域。

(a) 實(shí)際地圖俯視圖 (b) 柵格化建模地圖圖2 特殊環(huán)境建模

實(shí)際環(huán)境地圖根據(jù)上述建模規(guī)則進(jìn)行二維柵格化處理，使用柵格坐標(biāo)標(biāo)記AGV位置等參數(shù)，并支撐路徑規(guī)劃算法的運(yùn)行和實(shí)現(xiàn)。

1.2 路徑規(guī)劃基本蟻群算法

蟻群算法是以自然界螞蟻尋找食物的自然現(xiàn)象為主要思想進(jìn)行設(shè)計(jì)算法[15]，能夠良好地解決優(yōu)化控制領(lǐng)域、路由分配及路徑規(guī)劃等問(wèn)題。

路徑規(guī)劃技術(shù)中的蟻群算法實(shí)現(xiàn)主要包括算法初始化、轉(zhuǎn)輪賭法尋找下一合適節(jié)點(diǎn)和信息素更新3部分。其中，蟻群算法初始化主要進(jìn)行蟻群參數(shù)設(shè)定，包括：蟻群算法起始點(diǎn)和目的點(diǎn)、螞蟻種群數(shù)量、信息素初始分布、迭代次數(shù)的設(shè)置以及信息素蒸發(fā)率的設(shè)定等，其中，蟻群尋路起始點(diǎn)和目的點(diǎn)即為機(jī)器人路徑規(guī)劃的起始點(diǎn)和目的點(diǎn)。在尋路迭代次數(shù)為t時(shí)，螞蟻z從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的概率如式(3)所示。

(3)

(4)

圖3 蟻群搜索八向示意圖

每只螞蟻重復(fù)上述尋路過(guò)程，直至通過(guò)概率公式計(jì)算確定下一節(jié)點(diǎn)為路徑規(guī)劃目的點(diǎn)或迭代次數(shù)達(dá)到預(yù)設(shè)值時(shí)，完成一次尋路過(guò)程。當(dāng)所有的螞蟻完成一次尋路之后，每條路徑節(jié)點(diǎn)上的信息素濃度開(kāi)始進(jìn)行更新，更新計(jì)算如式(5)所示。

(5)

(6)

式中，Q為正常數(shù)，一般設(shè)定為1；Lz為本次尋路得到的最優(yōu)路徑的長(zhǎng)度數(shù)值。

蟻群通過(guò)概率選擇、信息素更新等步驟不斷迭代循環(huán)，利用正反饋特性不斷促進(jìn)算法收斂，實(shí)現(xiàn)路徑規(guī)劃。

2 融合模糊控制的改進(jìn)蟻群算法

本文提出一種路徑規(guī)劃中融合模糊控制的改進(jìn)蟻群算法FOACO，解決蟻群算法在路徑規(guī)劃過(guò)程中存在的收斂速度緩慢、精確度有待提高等問(wèn)題。改進(jìn)蟻群算法提出3個(gè)策略優(yōu)化方法：信息素更新策略改進(jìn)、權(quán)重因子自適應(yīng)調(diào)整和規(guī)劃路徑幾何優(yōu)化。

2.1 初始化信息素濃度分布規(guī)則

普通蟻群算法路徑規(guī)劃信息素初始分布為均一分布，全局信息素?zé)o差排列，蟻群尋路過(guò)程出現(xiàn)盲目性和不確定性，影響全局性能。為了增大初始化信息素的啟發(fā)作用，本文引入一個(gè)初始化信息素濃度分布規(guī)則，如圖4所示。

圖4 初始化信息素分布

根據(jù)規(guī)劃起點(diǎn)和終點(diǎn)建立信息素濃度特殊初始化區(qū)域，其余區(qū)域?yàn)樾畔⑺仄胀ǔ跏蓟瘏^(qū)域。信息素初始化分布如式(7)所示。

(7)

式中，χ為普通信息素初始化濃度分布數(shù)值；f為特殊分布系統(tǒng)，取值范圍為[0,0.5]。通過(guò)增加信息素初始分布，構(gòu)建蟻群有向性移動(dòng)最優(yōu)路徑區(qū)域，降低螞蟻尋路的盲目性和不確定性，加快蟻群算法路徑規(guī)劃速度。

2.2 融合模糊控制的信息素更新策略改進(jìn)

普通蟻群算法信息素更新啟發(fā)性較弱，全局規(guī)劃精度和速度不足。本文引入二維模糊控制器進(jìn)行蟻群經(jīng)過(guò)路徑節(jié)點(diǎn)信息素更新增量的計(jì)算與控制。模糊控制器輸入變量為螞蟻所在節(jié)點(diǎn)信息素濃度值Tau和當(dāng)前時(shí)刻傳統(tǒng)信息素更新策略的信息素更新值ΔTau_tra，模糊控制器輸出量ΔTau_Fuzzy作為信息素更新的變化量之一。模糊控制器結(jié)構(gòu)如圖5所示。

圖5 模糊控制器設(shè)計(jì)

模糊控制器的變量隸屬度函數(shù)根據(jù)專家經(jīng)驗(yàn)知識(shí)選定。其中，三角型隸屬度函數(shù)和廣義鐘型隸屬度函數(shù)對(duì)于離散系統(tǒng)具備良好的計(jì)算能力和平滑處理能力，因此，本文模糊控制器的隸屬度函數(shù)設(shè)計(jì)如表1所示。

表1 模糊控制器的變量模糊化

同時(shí)，模糊控制器輸出量的論域選定為[0.001,0.1]，為避免模糊控制器輸入溢出影響算法速度，本文選用的輸入和輸出變量隸屬度函數(shù)如圖6所示。

(a) Tau (b) ΔTau_tra (c) ΔTau_Fuzzy圖6 隸屬度函數(shù)

蟻群算法規(guī)劃路徑長(zhǎng)度隨著迭代次數(shù)的增加逐漸趨近于收斂狀態(tài)。在路徑規(guī)劃趨近收斂狀態(tài)中，普通信息素增加值的啟發(fā)作用不明顯，因此，蟻群算法路徑規(guī)劃速度受到極大的限制。為解決這個(gè)問(wèn)題，本文引進(jìn)收斂狀態(tài)信息素增量ΔTau_ste計(jì)算方式為：

(8)

式中，lengthk為第k次迭代的路徑長(zhǎng)度；itermax為最大迭代次數(shù)；R為常數(shù)。綜上所述，改進(jìn)蟻群算法信息素更新策略為：

(9)

式中，ΔTau_Fuzzy(j)為模糊控制器輸出量的值，即模糊控制器輸出的節(jié)點(diǎn)j的數(shù)值增量。

2.3 蟻群參數(shù)自適應(yīng)調(diào)整規(guī)則

普通蟻群算法參數(shù)數(shù)值固定，容易引起算法收斂速度降低，甚至不利于算法收斂。為了提高蟻群算法穩(wěn)定性和快速性，本文采用信息素權(quán)重因子和蒸發(fā)率自適應(yīng)調(diào)整規(guī)則，進(jìn)行算法優(yōu)化。信息素權(quán)重因子自適應(yīng)調(diào)整為：

(10)

式中，lengthop為第k次迭代最優(yōu)路徑長(zhǎng)度；R為常數(shù)。根據(jù)規(guī)劃路徑長(zhǎng)度進(jìn)行信息素啟發(fā)因子數(shù)值調(diào)整，增大信息素在后續(xù)迭代規(guī)劃中的啟發(fā)性，促進(jìn)算法快速收斂。同時(shí)，信息素蒸發(fā)率固定，隨著迭代次數(shù)增加，路徑節(jié)點(diǎn)信息素累積速度超過(guò)蒸發(fā)速度，容易出現(xiàn)冗余節(jié)點(diǎn)和冗余路徑。現(xiàn)引入信息素蒸發(fā)速率自適應(yīng)調(diào)整規(guī)則，提高路徑節(jié)點(diǎn)蒸發(fā)速度。若第k次迭代路徑長(zhǎng)度大于第k-1次，為減小較差路徑信息素濃度的啟發(fā)作用，促使蟻群向更優(yōu)路徑移動(dòng)，現(xiàn)對(duì)信息素蒸發(fā)率進(jìn)一步增加，如式(11)所示：

(11)

通過(guò)信息素權(quán)重因子和蒸發(fā)率自適應(yīng)調(diào)整，對(duì)全局迭代路徑信息素濃度有向性處理，加快全局最優(yōu)路徑的規(guī)劃速度。

2.4 規(guī)劃路徑幾何優(yōu)化算法(FOACO)

為了進(jìn)一步優(yōu)化改進(jìn)算法FACO的性能和效果，采用幾何原理進(jìn)行路徑優(yōu)化，即利用三角形兩邊的長(zhǎng)度之和大于第三邊的特性去除路徑中的冗余點(diǎn)。如圖7所示，路徑節(jié)點(diǎn)為1→2→3→4→5，以三個(gè)節(jié)點(diǎn)為一組判斷冗余節(jié)點(diǎn)，D為極限距離，如式(12)所示，其中a為柵格邊長(zhǎng)。假定節(jié)點(diǎn)組為3，4，5，以首尾節(jié)點(diǎn)為固定兩點(diǎn)建立直線y=K*x+B，計(jì)算中間節(jié)點(diǎn)距離該直線的距離d，并以此為節(jié)點(diǎn)冗余判斷參數(shù)。假設(shè)數(shù)值d大于極限距離D，則直線y經(jīng)過(guò)障礙物，節(jié)點(diǎn)4不可刪除。反之，節(jié)點(diǎn)4為冗余節(jié)點(diǎn)，刪除優(yōu)化后，路徑為1→2→3→5。

圖7 幾何優(yōu)化示意圖

(12)

結(jié)合路徑規(guī)劃結(jié)果中存在銳角路徑轉(zhuǎn)折的特殊情況，如圖7中路徑節(jié)點(diǎn)組1→2→3，采用上述冗余路徑判斷方法可能出現(xiàn)“幾何優(yōu)化”無(wú)效的問(wèn)題。本文采用“檢測(cè)銳角—增加節(jié)點(diǎn)優(yōu)化”的處理方法，即增加節(jié)點(diǎn)6，更新路徑節(jié)點(diǎn)組為1→2→6，重復(fù)進(jìn)行冗余路徑判斷過(guò)程，如圖7所示。幾何優(yōu)化后路徑為1→6→3→5，與原路徑相比，路徑長(zhǎng)度進(jìn)一步縮短，優(yōu)化路徑規(guī)劃整體效果。

2.5 FOACO算法總體流程

結(jié)合上述改進(jìn)策略：信息素更新策略改進(jìn)、權(quán)重因子自適應(yīng)調(diào)整和規(guī)劃路徑幾何優(yōu)化，改進(jìn)算法工作流程如圖8所示，通過(guò)改進(jìn)措施，動(dòng)態(tài)更新蟻群算法參數(shù)數(shù)值，優(yōu)化算法整體結(jié)構(gòu)，額外增加幾何優(yōu)化步驟提高改進(jìn)算法的完整度。

圖8 改進(jìn)蟻群算法(FOACO)流程圖

3 仿真實(shí)驗(yàn)與驗(yàn)證

為了驗(yàn)證本文算法的可靠性，在MATLAB 2017a開(kāi)發(fā)平臺(tái)下編寫(xiě)算法，實(shí)驗(yàn)硬件設(shè)備為：Intel(R)Core(TM)i5-6200U CPU@2.40 GHz和8 GB運(yùn)行內(nèi)存。本文根據(jù)不同實(shí)驗(yàn)環(huán)境分別設(shè)置三組對(duì)照實(shí)驗(yàn)，采用普通蟻群算法ACO、遺傳算法改進(jìn)蟻群算法GACO和本文算法FACO進(jìn)行算法效果對(duì)比，實(shí)驗(yàn)地圖大小為20×20。此外，三組蟻群算法基礎(chǔ)參數(shù)設(shè)置如表2所示。

表2 基礎(chǔ)蟻群算法參數(shù)設(shè)置

本文設(shè)置兩種仿真地圖，分別為一般地圖MAP1和文獻(xiàn)[15]地圖MAP2，對(duì)照實(shí)驗(yàn)結(jié)果如圖9所示。

(a) MAP1 (b) 迭代曲線

(c) MAP2 (d) 迭代曲線圖9 對(duì)照實(shí)驗(yàn)

如圖9所示，通過(guò)本文改進(jìn)方法實(shí)現(xiàn)，F(xiàn)ACO算法規(guī)劃路徑收斂速度優(yōu)于普通蟻群算法ACO和融合遺傳算法的蟻群算法GACO，規(guī)劃路徑長(zhǎng)度也有不同程度的降低改善。與文獻(xiàn)[15]的改進(jìn)蟻群算法相比，本文算法收斂性能和路徑最優(yōu)程度均進(jìn)一步得到提升，規(guī)劃路徑轉(zhuǎn)折次數(shù)降低，路徑更加平滑。加入幾何優(yōu)化策略后改進(jìn)蟻群算法FOACO路徑規(guī)劃結(jié)果如圖10所示。

圖10 FOACO幾何優(yōu)化實(shí)驗(yàn)

結(jié)合圖10和表3，本文改進(jìn)FOACO算法與對(duì)照組算法相比具有更強(qiáng)的最優(yōu)路徑規(guī)劃能力。對(duì)于MAP1，本文算法與ACO和GACO相比，路徑長(zhǎng)度減小8.51%和6.17%，迭代次數(shù)減小27.9%和36.73%；對(duì)于MAP2，本文算法與文獻(xiàn)[15]相比，路徑長(zhǎng)度減小0.371%，迭代次數(shù)減小6.25%。因此，本文改進(jìn)蟻群算法具備一定的優(yōu)越性。

表3 仿真對(duì)比實(shí)驗(yàn)數(shù)據(jù)表

4 結(jié)論

本文提出一種融合模糊控制和自適應(yīng)權(quán)重信息調(diào)整的改進(jìn)蟻群算法來(lái)優(yōu)化移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)的性能。首先使用信息素初始化規(guī)則提高初始信息素啟發(fā)能力。同時(shí)，引入模糊控制和收斂狀態(tài)信息素增量改進(jìn)普通蟻群算法的信息素更新策略，進(jìn)一步提高信息素更新效果，促進(jìn)算法全局最優(yōu)收斂；采用自適應(yīng)權(quán)重因子調(diào)整的方式，促進(jìn)蟻群算法快速迭代和收斂；最后，采用幾何優(yōu)化算法進(jìn)一步優(yōu)化規(guī)劃路徑，進(jìn)一步縮減路徑長(zhǎng)度，深化全局收斂路徑結(jié)果的最優(yōu)性。實(shí)驗(yàn)表明，本文算法能夠有效地提高移動(dòng)機(jī)器人路徑規(guī)劃性能，縮減路徑長(zhǎng)度效果明顯，有效減低最短路徑迭代次數(shù)，整體效果優(yōu)于其余同類型算法。結(jié)合移動(dòng)機(jī)器人實(shí)際使用場(chǎng)景，下一步可著重于動(dòng)態(tài)障礙物蟻群算法路徑規(guī)劃性能改進(jìn)與提升的研究工作，盡可能拓寬本文算法應(yīng)用場(chǎng)景和技術(shù)深度。