基于改進(jìn)蟻群算法機(jī)器人路徑規(guī)劃★

邢協(xié)泓， 黃坤榮， 唐德文

（1.南華大學(xué)機(jī)械工程學(xué)院， 湖南 衡陽(yáng) 412000；2.南華大學(xué)核設(shè)施應(yīng)急安全技術(shù)與裝備重點(diǎn)實(shí)驗(yàn)室， 湖南 衡陽(yáng) 412000）

0 引言

隨著社會(huì)的發(fā)展，機(jī)器人在生活、工業(yè)生產(chǎn)等方面的應(yīng)用越來(lái)越廣泛。機(jī)器人進(jìn)行自由運(yùn)動(dòng)的必要條件是其具備路徑設(shè)計(jì)功能，而路徑規(guī)劃的好壞關(guān)鍵在路徑搜索算法的選取上[1]。目前對(duì)于機(jī)器人路徑規(guī)劃提出了多種算法，如：A*算法、D*算法、人工勢(shì)場(chǎng)法、人工魚(yú)群算法[2]等，與其他算法相比，蟻群算法具有信息正反饋、自組織、并行等特點(diǎn)，所以在路徑規(guī)劃中應(yīng)用更為方便廣泛，但在一些復(fù)雜的環(huán)境中，傳統(tǒng)的蟻群算法也存在一定的不足，如彎折多，收斂速度慢等。隨著環(huán)境復(fù)雜性的提高，對(duì)算法的要求也會(huì)更高，單一算法往往不能尋找出最優(yōu)路徑。文獻(xiàn)[3]將傳統(tǒng)螞蟻群體計(jì)算和D*算法結(jié)合，通過(guò)優(yōu)化原始D*算法的啟發(fā)式函數(shù)和子節(jié)點(diǎn)的方法，用傳統(tǒng)蟻群計(jì)算的評(píng)價(jià)方法來(lái)改善計(jì)算，從而增強(qiáng)了高效性和適應(yīng)性;文獻(xiàn)[4]融合蟻群算法和遺傳算法，運(yùn)用遺傳算法的快速搜索對(duì)螞蟻群體計(jì)算初始信息素加以處理，避免進(jìn)入局部?jī)?yōu)化，并且縮短了尋找路徑時(shí)間;文獻(xiàn)[5]提出了結(jié)合Dijkstra 方法和蟻群方法來(lái)解決MRPP 問(wèn)題，實(shí)現(xiàn)在最短時(shí)間內(nèi)獲得全局最優(yōu)路徑的目標(biāo)。

蟻群算法是最先提出的模擬蟻群覓食活動(dòng)的智能模擬算法，該算法由于具有魯棒性、正反饋等特點(diǎn)，易與其他算法相結(jié)合并運(yùn)用到機(jī)器人路徑規(guī)劃中[6]。本文中提出將單一蟻群算法與Dijkstra 算法相互融合，利用Dijkstra 算法的快速全局查詢能力，對(duì)單蟻群算法的信息素進(jìn)行處理，并利用Dijkstra 算法實(shí)現(xiàn)節(jié)點(diǎn)選擇，再用蟻群算法進(jìn)行優(yōu)化。通過(guò)用數(shù)學(xué)軟件MATLAB 模擬，對(duì)融合方法和傳統(tǒng)算法進(jìn)行比較，實(shí)現(xiàn)優(yōu)化后的方法通過(guò)更短的迭代時(shí)間達(dá)到了最佳路徑設(shè)計(jì)。

1 傳統(tǒng)路徑規(guī)劃算法

1.1 蟻群算法

蟻群計(jì)算，是尋求優(yōu)化途徑的一個(gè)模擬進(jìn)化算法[7]，是依據(jù)螞蟻覓食的基本原理而得到。螞蟻在行走的步驟中產(chǎn)生信息素，用以記錄自己的步行路程。

在構(gòu)建路徑的每一步中，使用輪盤賭法來(lái)選定下一次到達(dá)的節(jié)點(diǎn)。其節(jié)點(diǎn)的選取方程是：

式中：i、j 分別為起點(diǎn)和終點(diǎn)；α 為信息素因子；β 為啟發(fā)函數(shù)因子；τij（t）為時(shí)間t 時(shí)由i 到j(luò) 的信息素濃度；ηij（t）=1/dij（t）是兩點(diǎn)i、j 路徑距離的倒數(shù)；Aallowed，k為尚未訪問(wèn)過(guò)的節(jié)點(diǎn)的集合。

其中dij表示i、j 之間的歐式幾何距離[8]，如式（2）所示：

搜索時(shí)，由于螞蟻種類的增多，路徑中的信息素含量會(huì)相應(yīng)提高，因?yàn)樾畔⒃貛в胁▌?dòng)性，信息元素含量會(huì)隨著持續(xù)時(shí)間的延長(zhǎng)而減少。

其表達(dá)式為：

式中：τij（t+1）為經(jīng)過(guò)一次更新后路徑上的信息素濃度；ρ 為信息素?fù)]發(fā)系數(shù)且0<ρ<1；為第k 只螞蟻在路徑（i，j）上的信息素增量；N 為蟻群總數(shù)量；Q為信息素增量系數(shù)；Lk為第k 只螞蟻搜索經(jīng)過(guò)的路徑長(zhǎng)度。

1.2 Dijkstra 算法

Dijkstra 算法是一種經(jīng)典的求解最短路徑的算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他各個(gè)不相關(guān)節(jié)點(diǎn)的最小移動(dòng)價(jià)值[9]。

在路徑規(guī)劃中，先假定起點(diǎn)為s，再引入S 和U。S記錄已求出最短路徑的頂點(diǎn)和相應(yīng)的最短路徑長(zhǎng)度的集合，U 記錄還未求出最短路徑的頂點(diǎn)以及該頂點(diǎn)到s 的距離的集合。如果所找出的點(diǎn)到一節(jié)點(diǎn)的路不通，則距離視為∞。

Dijkstra 算法在節(jié)點(diǎn)的選取過(guò)程中實(shí)質(zhì)上從某個(gè)節(jié)點(diǎn)出發(fā)，然后沿著地圖的邊通過(guò)路徑到達(dá)另一節(jié)點(diǎn)，再選取在每條邊上權(quán)重之和最小的路徑[10-12]，將相鄰的下一個(gè)節(jié)點(diǎn)進(jìn)行標(biāo)記，比較起點(diǎn)到下一節(jié)點(diǎn)的距離大小，篩選出離起點(diǎn)較短的節(jié)點(diǎn)，刪除較長(zhǎng)的節(jié)點(diǎn)。在改進(jìn)的算法中，只需要將障礙物的各頂點(diǎn)加入到U 中，這樣既縮短了搜索時(shí)間，又使得搜索更具有導(dǎo)向性，路徑更短。

2 改進(jìn)蟻群算法路徑規(guī)劃

本文改進(jìn)蟻群算法的基本思想是搜索初期使用Dijkstra 算法重新進(jìn)行節(jié)點(diǎn)的選取，使其將搜索目標(biāo)向最優(yōu)解靠攏，再用蟻群算法優(yōu)化節(jié)點(diǎn)尋找最優(yōu)路徑，防止機(jī)器人離障礙物太近。

2.1 路徑規(guī)劃環(huán)境建模

環(huán)境建模的方法有柵格法、拓?fù)浞ā⒖梢晥D法等[13]。由于柵格法直觀且建模容易，本文采用柵格法進(jìn)行環(huán)境建模。圖1 是柵格法的基本模型，20 cm×20 cm 格子表示機(jī)器人所處總環(huán)境，黑色格子表示環(huán)境中的障礙物，沒(méi)有障礙物的自由移動(dòng)環(huán)境用白色格子表示每一格為1 cm。在建模過(guò)程中，可能存在不足一格的現(xiàn)象，應(yīng)進(jìn)行膨化處理，不足一格用一格代替[14]。

圖1 柵格法環(huán)境建模

在柵格圖中坐標(biāo)表示為：

式中：b 為柵格邊長(zhǎng)；mod 為取余；ceil 為取最小整數(shù)；xi，yi為每個(gè)柵格的坐標(biāo)位置[15]。

2.2 節(jié)點(diǎn)選取

機(jī)器人在尋找最短路徑時(shí)，首先要越過(guò)障礙物，文獻(xiàn)[16]中介紹了越過(guò)圓形障礙物的可達(dá)路徑，即從起點(diǎn)經(jīng)過(guò)圓的切線，如圖2 所示。

圖2 經(jīng)過(guò)圓形障礙物可達(dá)路徑[16]

基于此，本文改進(jìn)算法引入切點(diǎn)，在柵格法建模的環(huán)境中，將障礙物的頂點(diǎn)看成切點(diǎn)，如圖3 所示，正方形ABCD 為障礙物，起點(diǎn)為O，終點(diǎn)N；從起點(diǎn)到終點(diǎn)，按照?qǐng)A形障礙物可達(dá)路徑方式，越過(guò)柵格環(huán)境有4 條路徑，分別為O→B→N；O→C→N；O→A→N；O→D→N。但考慮無(wú)法直接越過(guò)障礙物，機(jī)器人會(huì)選擇B、C 作為中間節(jié)點(diǎn)。

圖3 經(jīng)過(guò)柵格環(huán)境障礙物可達(dá)路徑

將改進(jìn)后的可達(dá)路徑與傳統(tǒng)算法進(jìn)行比較，如圖4 所示。

圖4 改進(jìn)與傳統(tǒng)路徑比較

圖4 所示，OMN 為傳統(tǒng)路徑，OCN 為改進(jìn)路徑，OE+EC>OC，CF+FN>CN，EC=MF，CF=EM?OM+MN>OC+CN，改進(jìn)后的路徑比傳統(tǒng)路徑更短且更優(yōu)。

由圖4 對(duì)比可知，機(jī)器人會(huì)選擇走經(jīng)過(guò)B、C 兩點(diǎn)的路徑。若選擇經(jīng)過(guò)A、D 兩點(diǎn)，則需要繞過(guò)障礙物，路徑的權(quán)重之和變大，則Dijkstra 算法的S、U 表中將刪除A、D 兩點(diǎn)。

2.3 節(jié)點(diǎn)優(yōu)化

經(jīng)過(guò)多個(gè)障礙物時(shí)，先將所有障礙物的端點(diǎn)進(jìn)行標(biāo)記加入到U 表中，用Dijkstra 算法選擇出權(quán)值和最小的路徑，而當(dāng)離障礙物很近時(shí)，直接用Dijkstra 算法進(jìn)行節(jié)點(diǎn)選擇時(shí)會(huì)讓路徑可行性降低，改用蟻群算法進(jìn)行路徑更優(yōu)化選擇。

優(yōu)化原則：在柵格法建模的環(huán)境中，當(dāng)螞蟻離障礙物的水平距離少于一個(gè)單位時(shí)，用蟻群算法選擇水平點(diǎn)，如圖5 所示。

圖5 蟻群算法優(yōu)化原理

設(shè)起點(diǎn)坐標(biāo)O（x0，y0），B 點(diǎn)坐標(biāo)（x1，y1），則A 點(diǎn)坐標(biāo)為（x0，y1），將式（3）進(jìn)行更新，得到：

更新后的啟發(fā)式函數(shù)計(jì)算如式（8）所示：

如圖5 所示，障礙物在起點(diǎn)右方，用優(yōu)化后的算法更新后得到A 點(diǎn)。B 點(diǎn)為Dijkstra 算法找出的權(quán)值最小的點(diǎn)，A 為蟻群算法優(yōu)化找出的節(jié)點(diǎn)。在三角形OAB 中，OB 為斜邊，OA 為直角邊，直角邊比斜邊短，權(quán)重更小，A 為最優(yōu)點(diǎn)，將B 點(diǎn)從U 表中刪除，A點(diǎn)放入U(xiǎn) 中。

用蟻群算法優(yōu)化更新后的距離更短，路徑更優(yōu)，同時(shí)也避免了機(jī)器人在移動(dòng)的過(guò)程中與障礙物發(fā)生碰撞，實(shí)現(xiàn)了路徑最優(yōu)的要求。

2.4 改進(jìn)蟻群算法

在未知環(huán)境中，將蟻群算法和Dijkstra 算法相融合，使機(jī)器人在路徑規(guī)劃中，初期使用Dijkstra 算法將搜索目標(biāo)向最優(yōu)解靠攏，再用蟻群算法尋找最優(yōu)路徑。機(jī)器人遇到障礙物時(shí)，利用融合算法將切點(diǎn)作為節(jié)點(diǎn)放入S 進(jìn)行搜索，選擇距離起始點(diǎn)最近的切點(diǎn)，若切點(diǎn)離障礙物過(guò)近，再將切點(diǎn)平移后的點(diǎn)移到U中，隨后更新信息素以及迭代次數(shù)，輸出最優(yōu)路徑，其算法流程如圖6 所示。

圖6 融合算法流程

3 仿真結(jié)果與討論

本文采用MATLAB_R2022a 進(jìn)行仿真，對(duì)機(jī)器人在建立的已知地圖上進(jìn)行實(shí)驗(yàn)，分別運(yùn)行傳統(tǒng)蟻群算法以及本文改進(jìn)融合蟻群算法，從最短路徑長(zhǎng)度、迭代次數(shù)、運(yùn)行總時(shí)間這三方面分析比較，實(shí)驗(yàn)環(huán)境建模如圖1 所示，設(shè)置的蟻群初始參數(shù)如表1 所示，起點(diǎn)為（0.5，19.5），終點(diǎn)為（19.5，0.5）。

表1 蟻群算法初始參數(shù)

仿真結(jié)果中，圖7-1 為傳統(tǒng)蟻群算法路徑規(guī)劃，圖7-2 為改進(jìn)融合蟻群算法路徑規(guī)劃，對(duì)比可知，傳統(tǒng)算法路徑軌跡有14 個(gè)彎折點(diǎn)，改進(jìn)后的算法有7個(gè)彎折點(diǎn)，融合后的蟻群算法比傳統(tǒng)蟻群算法路徑彎折點(diǎn)減少了50%，路徑更為平穩(wěn)。

圖7 傳統(tǒng)與改進(jìn)算法路徑規(guī)劃對(duì)比

圖8-1 為傳統(tǒng)蟻群算法收斂曲線，迭代次數(shù)在50 次趨于平穩(wěn)，最短路徑為30.38 cm；圖8-2 為改進(jìn)融合蟻群算法收斂曲線，可知最小路徑迭代到32 次時(shí)趨于平穩(wěn)，最短路徑為26.21 cm。迭代最短路徑由30.38 cm 降到26.21 cm，迭代次數(shù)由50 次降到32次，可見(jiàn)改進(jìn)后的算法路徑更優(yōu)，搜索效率更高。

圖8 傳統(tǒng)與改進(jìn)算法收斂曲線對(duì)比

綜上，數(shù)據(jù)對(duì)比如表2 所示，傳統(tǒng)蟻群算法的最短路徑為30.38 cm，迭代次數(shù)為50 次，而經(jīng)過(guò)優(yōu)化融合后的蟻群算法的最短路徑為26.21 cm，迭代次數(shù)為32 次，減少了40%的路徑長(zhǎng)度，同時(shí)改進(jìn)后的算法也增加了收斂效率，相比于傳統(tǒng)蟻群算法增加了37%，優(yōu)化后的算法執(zhí)行時(shí)間大大縮短，搜索效率更高，路線彎折更少。

表2 數(shù)據(jù)對(duì)比

4 結(jié)語(yǔ)

本文采用了柵格法環(huán)境模型，面對(duì)蟻群算法中收斂速度慢且極易陷入局部求解的難題，提出了融合Dijkstra 算法與蟻群算法的方法：搜索初期用Dijkstra算法引入切點(diǎn)向最優(yōu)解靠攏，后期用蟻群算法優(yōu)化節(jié)點(diǎn)選擇。實(shí)驗(yàn)表明，在同一環(huán)境下改進(jìn)后的算法路徑長(zhǎng)度縮短了14%，收斂速度提高了37%，彎折點(diǎn)減少了50%，在路徑長(zhǎng)度、迭代次數(shù)、搜索時(shí)間、彎折點(diǎn)等方面均優(yōu)于傳統(tǒng)蟻群算法。利用MATLAB 仿真證實(shí)了融合后的算法可以進(jìn)一步提高收斂速率，并使得搜索的路徑更有引導(dǎo)性，相比于常規(guī)的蟻群方法，經(jīng)過(guò)改進(jìn)后的方法路徑彎折更少，易獲得最優(yōu)的路徑。