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

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

0 引言

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

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

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

1.1 蟻群算法

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

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

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

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

搜索時，由于螞蟻種類的增多，路徑中的信息素含量會相應(yīng)提高，因為信息元素帶有波動性，信息元素含量會隨著持續(xù)時間的延長而減少。

其表達式為：

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

1.2 Dijkstra 算法

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

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

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

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

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

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

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

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

在柵格圖中坐標表示為：

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

2.2 節(jié)點選取

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

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

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

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

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

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

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

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

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

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

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

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

設(shè)起點坐標O（x0，y0），B 點坐標（x1，y1），則A 點坐標為（x0，y1），將式（3）進行更新，得到：

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

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

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

2.4 改進蟻群算法

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

圖6 融合算法流程

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

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

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

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

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

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

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

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

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

4 結(jié)語

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