基于終距指數(shù)的機器人路徑規(guī)劃方法研究

李東東，王 雷，馬康康

(安徽工程大學(xué) 機械工程學(xué)院，安徽 蕪湖 241000)

隨著互聯(lián)網(wǎng)的普遍應(yīng)用，各個領(lǐng)域使用越來越多的機器人來完成一些重復(fù)性的勞動.諸如物流領(lǐng)域的貨物搬運機器人，醫(yī)用的手術(shù)輔助機器人，制造業(yè)的加工機器人，家庭用的清潔機器人等.由于機器人的廣泛應(yīng)用，對機器人的路徑規(guī)劃研究變得尤其重要.

近些年來，智能算法的迅速發(fā)展使機器人路徑的規(guī)劃變得高效化和簡單化，常見的算法有遺傳算法[1]，粒子群算法[2]，人工勢場法[3]，A*算法[4]，蟻群算法[5-7]等.其中，蟻群算法作為一種基于種群的概率選擇算法，與其它啟發(fā)式算法相比，在求解性能上，具有很強的魯棒性和較好解的搜索能力，且容易與多種啟發(fā)式算法結(jié)合進而改善算法性能[8]，因此，蟻群算法在路徑規(guī)劃領(lǐng)域中得以廣泛應(yīng)用.文獻[9]將蟻群算法用于智能作業(yè)車間AGV 調(diào)度問題，文獻[10]用蟻群算法設(shè)計了一種小型無人機高性能動力學(xué)模型辨識方法，取得了較好的效果.但蟻群算法也存在一些缺點，如收斂速度慢、容易陷入局部最優(yōu)解等.針對這些不足，國內(nèi)外諸多學(xué)者嘗試著對傳統(tǒng)的蟻群算法進行改進，如陳勁峰等[11]通過提出一種自適應(yīng)信息素給予機制，避免算法受到非最優(yōu)路徑上信息素影響而最終陷入局部最優(yōu)解；曹新亮等[12]選擇將初始信息素進行差異化設(shè)置，以達到防止非最優(yōu)路徑上的信息素對螞蟻產(chǎn)生誤導(dǎo)的作用，從而加快算法的收斂速度.以上算法依舊存在一些缺陷需要彌補，比如螞蟻的選擇策略受制于信息素濃度，而濃度是由路徑?jīng)Q定的，故存在冗余部分的路徑，其產(chǎn)生的信息素濃度將受到冗余路徑的干擾，進而影響螞蟻的選擇正確率.基于以上存在的問題，本文提出一種新的改進蟻群算法，即通過引入終距指數(shù)這一概念，取代信息素濃度的標(biāo)記功能，從而螞蟻可以依賴該指數(shù)進行決策選擇.仿真實驗結(jié)果表明，采取本文新改進蟻群算法，算法的性能有明顯的改善.

1 傳統(tǒng)蟻群算法

蟻群算法(Ant Colony Optimization,ACO)是一種尋找優(yōu)化路徑的概率型算法.它由Marco Dorigo 于1992 年在其博士論文中提出[13]，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為.其最初主要被應(yīng)用于研究TSP 問題，并表現(xiàn)出良好的求解效果，因此該算法得到進一步的發(fā)展.隨后，在路徑規(guī)劃領(lǐng)域，蟻群算法也展現(xiàn)出較好的搜索能力，正反饋特性、分布式計算等等.但由于該算法的本質(zhì)是一種基礎(chǔ)算法，故在路徑規(guī)劃應(yīng)用中還存在一些缺陷，比如收斂速度較慢、易陷入局部最優(yōu)解等，因此，對該算法的改進也成為了路徑規(guī)劃領(lǐng)域的一個熱門課題.

1.1 環(huán)境模型在路徑規(guī)劃的研究中，對環(huán)境的建模方法有很多，其中以柵格圖最為簡單有效.柵格法是Howden 在1968 年提出的[14]，并用于路徑規(guī)劃問題環(huán)境.其原理可以簡單地描述為：假定機器人的運動空間是一個水平的二維平面，對平面進行矩形切割，通常采用20×20 的切割策略.將沒有障礙物的柵格標(biāo)記為0，被障礙物充滿或者部分填充的柵格標(biāo)記為1，這樣，就可以將一個真實的物理環(huán)境，映射成一個只包含0 或1 的數(shù)字矩陣.環(huán)境的柵格圖模型如圖1 所示.

圖1 柵格模型Fig.1 Grid model

另外，機器人在柵格范圍內(nèi)移動時，對其軌跡方向可以簡化等效為8 個方向，如圖2 所示.

圖2 機器人移動方向圖Fig.2 Robot’s moving directions

1.2 基本蟻群算法解決思路初始化一定數(shù)量m的螞蟻，進入迭代循環(huán)，在每一次的循環(huán)中，螞蟻按概率選擇節(jié)點移動，直到移動至終點或者無法移動為止.節(jié)點選擇方法有很多，這里采用最經(jīng)典的輪盤賭法，選擇概率受信息素以及距離啟發(fā)因子的影響，每個節(jié)點的概率依據(jù)全概率公式生成，如：

其中，di j為節(jié)點（i，j）到終點（ie，je）的歐式距離，公式為：

當(dāng)一代螞蟻移動終止后，環(huán)境中的信息素將會按照式(4)進行削減，以模擬現(xiàn)實中的揮發(fā)效果.

其中，ρ是揮發(fā)系數(shù).另外，根據(jù)當(dāng)代螞蟻的行駛軌跡，對路線上的節(jié)點依據(jù)式(5)進行信息素更新.

其中，Q為單只螞蟻在一條路徑上留下的總信息素量，Lk為第k只螞蟻走過的路徑總長度.

2 改進蟻群算法

在傳統(tǒng)蟻群算法中，螞蟻在選擇節(jié)點時，依賴于信息素濃度來進行節(jié)點選擇，但由于信息素濃度的生成受制于路徑長度，而路徑又可能含有冗余成分，因此，信息素濃度無法直接表明節(jié)點的優(yōu)劣，這會使得螞蟻不容易找到最短路徑，收斂速度過慢.于是，本文重寫信息素，旨在強調(diào)信息素與節(jié)點優(yōu)劣的關(guān)系，引入終距指數(shù)代替信息素的作用，螞蟻能通過終距指數(shù)更好地感知某節(jié)點的優(yōu)劣.

2.1 終距指數(shù)的引入在傳統(tǒng)的蟻群算法中，螞蟻是通過環(huán)境的信息素濃度以及距離啟發(fā)因子來選擇下一步的走向，其中，信息素濃度總是繼承于上一代螞蟻的可行路徑.然而，信息素濃度并不能有效地反映某一節(jié)點的優(yōu)劣程度，因為從算法的邏輯上來說，信息素是若干條路徑的某種表示的疊加，因此可能存在冗余路徑，那么，冗余部分可能就會使得路徑上的某一節(jié)點變差.以圖3 為例進行加以說明.

圖3 經(jīng)過某定點A 的不同路徑圖Fig.3 Different moving paths through a fixed point A

圖3 為3 條條螞蟻走出的路徑，假定左下角的節(jié)點為0，右上角的節(jié)點為399，節(jié)點序列由左向右，由下向上遞增，則圖3 中的兩條路徑的節(jié)點信息分別是：

3 條路徑的總長度分別是Lsum_1=35.80，Lsum_2=38.04以及Lsum_3=30.97，其中，第三條路線為全局最優(yōu)路徑.圖中標(biāo)記節(jié)點A 的序列為266，對于A 點來說，前兩個路線產(chǎn)生的信息素濃度根本無法反映出A 點的好壞，因為路徑中的冗余部分會干擾節(jié)點上的信息素濃度，盡管可以通過迭代的方式去慢慢消除這種影響，但是嚴(yán)重影響收斂速度.

分析3 條路徑信息可知，如果能提取出3 條路徑中好的部分，而忽略甚至棄用冗余部分，用提取的若干個好的片段進行組合，則可以加快最優(yōu)路徑的產(chǎn)生.首先，本文引入終距指數(shù)kij的概念，kij為i行j列的節(jié)點的終距指數(shù)，該值代表了該節(jié)點到終點的已知距離.每當(dāng)各代螞蟻都行動后，依據(jù)當(dāng)代所有可行解來對各節(jié)點進行kij更新，從每條路徑的最后一個節(jié)點開始反向更新kij.更新的原則是：初始化節(jié)點的kij為99，更新時，若某節(jié)點新產(chǎn)生的kij小于現(xiàn)有的kij，則更新，這意味著該節(jié)點到終點發(fā)現(xiàn)了新的最短距離，否則，代表了沒有發(fā)現(xiàn)新的最短路徑.不更新kij.kij的計算公式如下：

以上述案列中的第一個路徑為例，取A 節(jié)點為研究對象，按照前述的算法邏輯，從最后一個節(jié)點進行反向更新kij，故有k19?19=0，由于前一個節(jié)點和最后一個節(jié)點之間的路徑是直線而不是斜線，另外本文定義單位柵格長度為1，因此，k18?19=1，若路徑線段為斜線，則為1.414，即k17?18=1+1.414=2.414，以此類推，得到A 節(jié)點的終距指數(shù)k6?13=17.726，當(dāng)?shù)诙l路徑的終距指數(shù)更新時，會發(fā)現(xiàn)A 節(jié)點新的終距指數(shù)=17.14，由于即表明對于A 節(jié)點來說，出現(xiàn)了新的更短的到達終點的路徑，故更新A 的終距指數(shù)，按照既定的邏輯執(zhí)行完其余的節(jié)點的更新.注意，當(dāng)這些步驟完成時，如果從起點位置按照最大梯度連接一條指向終點的路徑，就會發(fā)現(xiàn)新的路徑是由兩條路徑的中若干段節(jié)點到節(jié)點的最短路徑組合而成，由于對于各節(jié)點來說，僅保留最優(yōu)的結(jié)果，因此，面對已有數(shù)據(jù)中的更優(yōu)解，新產(chǎn)生的路徑中的冗余部分將無法產(chǎn)生不良的影響.

2.2 終距指數(shù)抗干擾能力分析為了進一步證明終距指數(shù)對生成路徑中的局部冗余路段具備抗干擾能力，將上述案例推廣到一般模型，簡化環(huán)境模型為4×4 無障礙物柵格圖，將最優(yōu)路徑分成兩段并分別置于兩個非最優(yōu)路徑中，如圖4 和圖5 所示.

圖4 4×4 無障礙物柵格環(huán)境模型Fig.4 4×4 grid model for no obstacle

圖5 包含最優(yōu)路徑信息的兩段路徑(圓圈標(biāo)記節(jié)點為最優(yōu)路徑節(jié)點)Fig.5 Two segment paths with optimal path information (The circle marked node is the optimal path node)

由路徑1 與路徑2 單獨決定的終距指數(shù)矩陣如圖6 中所示(默認值設(shè)為99).觀察圖6，在以路徑1 對應(yīng)的終距指數(shù)矩陣為基準(zhǔn)的基礎(chǔ)上，更新路徑2 對應(yīng)的終距指數(shù)信息的過程中，依次更新終距指數(shù)0,1,2，但在更新終距指數(shù) 3時，由于現(xiàn)存對應(yīng)節(jié)點終距指數(shù)為2.41 ＜3，即路徑2 中該節(jié)點至終點的局部路徑相對路徑1 來說含有冗余成分，因此舍棄終距指數(shù)3，保留原值2.41，并且在路徑2 后續(xù)的節(jié)點更新都基于原值2.41進行，即將路徑2 中劣質(zhì)的局部路徑信息替換成路徑1 中更優(yōu)良的局部路徑信息，同時，在之后的更新中，即更新終距指數(shù)3.41與4.82，這意味著路徑1 中的劣質(zhì)局部路徑信息被路徑2 中更優(yōu)良的局部路徑信息替換.

圖6 終距指數(shù)更新機制演示Fig.6 Demonstration of renewal mechanism of terminal index

由上述內(nèi)容可知，兩條路徑中的優(yōu)良局部路徑信息可以相互優(yōu)化對方的劣質(zhì)局部路徑信息，從而使得各自所包含的優(yōu)良局部路徑信息得以遺留下來，進而組合成算法得到的最優(yōu)路徑信息.對比信息素濃度機制，無法快速從上述兩條路徑中找到最優(yōu)路徑信息，因此通過此法可以有效加快算法的尋優(yōu)速度.

2.3 概率選擇策略由于去除了信息素濃度，因此概率選擇策略也需要相應(yīng)修改.首先，由于kij分布的范圍較大，其直接作為概率選擇策略的影響因素欠合適，又考慮到相鄰節(jié)點的終距指數(shù)之差較小，在計算概率時，可以先對所有的相鄰節(jié)點的kij進行整體縮減，放大偏差處理，如：

其中，kmin為所有相鄰節(jié)點中的最小終距指數(shù)，q為削減系數(shù)，取值0.8，為更新后的終距指數(shù).經(jīng)實驗，完全可以直接帶入概率選擇策略中進行計算，故而概率選擇公式應(yīng)如下：

其中，α為距離啟發(fā)因子，β為終距指數(shù)啟發(fā)因子，allowedk指螞蟻k可選擇的下一節(jié)點的集合.

另外，由于原信息素濃度與選擇的關(guān)系是正比例關(guān)系，即濃度越高，選擇的概率越大，但終距指數(shù)恰恰相反，指數(shù)越小，被選擇的概率應(yīng)當(dāng)越高，因此，需要將原來的輪盤賭法的選擇機制改為排除機制，也就是說，通過輪盤賭選擇節(jié)點，選中者直接丟棄，循環(huán)執(zhí)行，直到只剩下一個可選節(jié)點.輪盤賭反向選擇的流程框圖如圖7 所示.

圖7 輪盤賭反向選擇框圖Fig.7 Flow chart based on roulette reverse selection

2.4 算法步驟基于上述內(nèi)容，改進后的蟻群算法步驟如下：

步驟 1將機器人的運動環(huán)境進行數(shù)字編碼，對編碼得到的0-1 矩陣映射為柵格圖模型.

步驟 2初始化所有節(jié)點的終距指數(shù)k′ij，以及距離啟發(fā)因子 α，終距指數(shù)啟發(fā)因子 β，螞蟻數(shù)量m，迭代次數(shù)T以及削減系數(shù)q等其它算法參數(shù).

步驟 3開始進入循環(huán)迭代.

步驟 4將各代螞蟻放至初始點，按照圖2 的運動規(guī)則，借助式(9)進行概率選擇下一個節(jié)點.

步驟 5判定當(dāng)前點是否為終點，如果是，就終止尋路，并記錄下路徑信息；否則，繼續(xù)選擇下一個節(jié)點.

步驟 6當(dāng)代螞蟻尋路結(jié)束后，取出當(dāng)代所有可行路徑解，依照式(7)對各節(jié)點進行終距指數(shù)的更新.從起點開始，通過基于終距指數(shù)的最大梯度下降法，得到一條最優(yōu)路徑作為當(dāng)前代的最優(yōu)解.

步驟 7循環(huán)T代后結(jié)束，輸出全局最優(yōu)解.

2.5 算法時間復(fù)雜度分析考慮到本文提出的改進策略主要是用終距指數(shù)代替信息素，從而改變螞蟻概率選擇可行節(jié)點的概率計算方法，進而影響螞蟻的尋路結(jié)果，進一步分析可以發(fā)現(xiàn)，信息素對蟻群算法時間復(fù)雜度的影響主要來源于信息素的更新機制，因此，在探討改良策略對原算法的時間復(fù)雜度影響時，僅需研究原算法中信息素的更新機制與改良算法中的終距指數(shù)的更新機制即可.

信息素濃度的更新機制的步驟如下：

步驟 1設(shè)獲取某條可通行路徑L，構(gòu)成其的n個節(jié)點為l0,l1,l2,···,ln，每只螞蟻一次行動釋放的信息素總量為E，信息素存放于矩陣M中.

步驟 2計算出每個節(jié)點分配的信息素量e=E/n.

步驟 3通過一層循環(huán)，依次對每個節(jié)點l0,l1,l2,...ln所對應(yīng)的M中元素進行更新.

終距指數(shù)的更新機制步驟如下：

步驟 1設(shè)獲取某條可通行路徑L，構(gòu)成其的n個節(jié)點為l0,l1,l2,···,ln，終距指數(shù)存放于矩陣M中.

步驟 2令終點的終距指數(shù)

步驟 3通過一層循環(huán)，倒序依次取出每個節(jié)點ln?1,ln?2,···l2,l1,l0進行后續(xù)步驟4～5 判斷.

分析上述內(nèi)可以得到，對于一個節(jié)點數(shù)為n的路徑，兩個更新機制僅含有一層與n一階線性相關(guān)的for 循環(huán)，因此，它們的時間復(fù)雜度都為O(n)，故終距指數(shù)的更新機制并不會增加原算法的時間復(fù)雜度.

3 仿真實驗與分析

3.1 算法參數(shù)選擇為了證實本文改進算法的可行性和有效性，本文采取python3.8 編制程序進行仿真.硬件環(huán)境信息：CPU2.5 GHz，i5 處理器.算法各參數(shù)設(shè)定如下：距離啟發(fā)因子β=1.5，終距指數(shù)啟發(fā)因子α=0.9，削減系數(shù)q=0.8，螞蟻數(shù)量m=30，最大迭代次數(shù)為T=100.

3.2 算法驗證仿真實驗首先取文獻[12]中的20×20 小規(guī)模柵格數(shù)據(jù)進行測試，仿真結(jié)果如圖8～圖10 所示.

圖8 本文改進算法在20×20 環(huán)境模型下的仿真結(jié)果Fig.8 Simulation result by using the improved algorithm under 20×20 environment model

圖9 20×20 環(huán)境模型下的迭代結(jié)束時各節(jié)點終距指數(shù)Fig.9 The terminal index of each node at the end of iteration under 20 ×20 environment model

圖10 不同算法對20×20 柵格模型的收斂結(jié)果對比圖Fig.10 Comparison of convergence results of different algorithms for 20× 20 grid model

圖8 為本文改進蟻群算法所得無碰撞最優(yōu)路徑，圖9 為算法迭代收斂后的各節(jié)點終距指數(shù)表，圖10 為算法迭代過程中的每代最優(yōu)路徑的對比結(jié)果，從仿真的結(jié)果來看，本文改進蟻群算法、傳統(tǒng)蟻群算法以及文獻[12]中的改進蟻群算法都能找到最優(yōu)解，但從收斂速度的角度來看，本文改進蟻群算法在第3 代就可以收斂到問題的最優(yōu)解，而傳統(tǒng)蟻群算法及文獻[12]中的改進蟻群算法分別要在第43 代與第34 代才能找到問題的最優(yōu)解.因此，本文的改進蟻群算法是有效和可行的.

為了進一步驗證本文算法的優(yōu)越性，將環(huán)境模型由20×20 擴大為更為復(fù)雜的30×30 柵格模型，柵格圖數(shù)據(jù)取文獻[11]中的數(shù)據(jù)作為測試數(shù)據(jù)，仿真環(huán)境不變，仿真結(jié)果如圖11～圖13 以及表1 所示.

圖11 為本文改進蟻群算法的仿真路徑結(jié)果，圖12 為算法達到收斂后的各節(jié)點的終距指數(shù)表，圖13 為傳統(tǒng)蟻群算法、文獻[11]改進蟻群算法以及本文改進蟻群算法的迭代圖,表1 為3 種算法仿真結(jié)果在收斂值以及收斂代數(shù)方面的對比.由以上仿真結(jié)果可得，在采用相同的螞蟻群體和迭代次數(shù)的前提下，本文改進蟻群算法與傳統(tǒng)蟻群算法以及文獻[11]算法在2 種不同規(guī)模環(huán)境的路徑規(guī)劃比較中，本文改進蟻群算法獲得路徑距離更短，收斂速度更快.

表1 不同算法的實驗結(jié)果Tab.1 Experimental results of different algorithms

圖11 本文算法仿真路徑圖Fig.11 Simulation result by using the improved algorithm under 30×30 environment mode

圖12 30×30 環(huán)境模型下的迭代結(jié)束時各節(jié)點終距指數(shù)Fig.12 The terminal index of each node at the end of iteration under 30×30 environment model

同時，觀察圖13 中3 種算法的波動曲線，明顯發(fā)現(xiàn)，傳統(tǒng)蟻群算法對應(yīng)的曲線波動較大，這也證實了傳統(tǒng)蟻群算法在收斂前期受到路徑冗余成分影響較為嚴(yán)重，這也驗證了前文所說的在信息素濃度的生成機制中，由于是以一條完整的路徑作為對象來生成信息素的，故而無法反映優(yōu)良的局部節(jié)點信息，因此，螞蟻很難通過信息素濃度快速找到最優(yōu)路徑.而文獻[11]也是通過使用自適應(yīng)信息素總量給予機制削弱螞蟻對信息素濃度的敏感程度，降低了由劣質(zhì)路徑產(chǎn)生的信息素對螞蟻決策的影響，從而提高算法的尋解效果，這從圖13 中對應(yīng)的迭代曲線的波動明顯較小可以證明其改進策略的有效性.而本文得益于終距指數(shù)更新的篩選策略，使得每代螞蟻生成的路徑信息，僅有更優(yōu)良的節(jié)點信息得以更新并遺留保存，其他劣質(zhì)路徑節(jié)點信息會被舍棄剔除，這從圖13 中對應(yīng)的算法收斂曲線的無波動可以證明.

圖13 不同算法對30×30 柵格模型的收斂結(jié)果對比圖Fig.13 Comparison of convergence results of different algorithms for 30×30 grid mode

3.3 算法穩(wěn)定性驗證為了進一步驗證本文改進蟻群算法的穩(wěn)定性，選擇上文30×30 柵格環(huán)境地圖案例進行仿真，對本文改進蟻群算法連續(xù)運行30 次，得到的具體數(shù)據(jù)如表2 所示.

表2 連續(xù)隨機運行30 次的仿真結(jié)果Tab.2 The simulation results running continuously and randomly for 30 times

如表2 所示，30 次運行的收斂代數(shù)較為平穩(wěn)且優(yōu)良，這再次證明本文的改進蟻群算法不但有效可行而且穩(wěn)定性好.

4 結(jié)論

傳統(tǒng)蟻群算法的信息素由于其自身的生成機制，故易受到冗余路徑的干擾，導(dǎo)致信息素濃度與節(jié)點優(yōu)劣性之間的關(guān)聯(lián)較為薄弱，本文對于節(jié)點的優(yōu)劣性，引入了終距指數(shù)的概念.終距指數(shù)主要受已知的若干個最優(yōu)局部路線的影響，若已記錄了更優(yōu)的路徑信息，則對于后續(xù)產(chǎn)生的冗余路徑，終距指數(shù)將會對冗余部分完全免疫.終距指數(shù)這種奇特的生成機制，使得螞蟻依賴終距指數(shù)來進行選擇節(jié)點變得更為可靠.算法的仿真結(jié)果表明，螞蟻在通過終距指數(shù)尋路后，無論是尋路結(jié)果，還是尋路速度，都有了明顯地提升.實驗仿真結(jié)果也表明本文基于終距指數(shù)的改進蟻群算法在不同復(fù)雜環(huán)境中移動機器人路徑規(guī)劃算法的可行性與優(yōu)越性.