|
改進蟻群算法在移動機器人路徑規(guī)劃中的應用研究
董武連 2021/8/7 20:34:08
（江蘇省鹽城技師學院，江蘇鹽城 224001）
摘要：移動機器人作為智能化發(fā)展的重要產物之一，為人們提供掃地、擦地、擦窗戶等服務，是人類生活中的得力幫手。雖然此類型機器人可以為人們提供多種服務，但是在移動路徑規(guī)劃上尚存在一定提升空間。為了改善機器人移動路徑規(guī)劃精度，加快路徑搜索收斂速度，本文在傳統(tǒng)蟻群算法基礎上，采用螞蟻相遇方法，在保留螞蟻遍歷路徑記憶能力的同時，對算法路徑搜索、路徑選擇、揮發(fā)系數進行改進。經過仿真分析驗證改進后，算法收斂性能及路徑規(guī)劃性能得到提升。
關鍵詞：移動機器人；改進蟻群算法；路徑規(guī)劃
中圖分類號：TP18;TP242 文獻標志碼：A
目前，應用比較多的是格柵標識方法，該方法是將機器人的工作環(huán)境轉化為數學模型，在此模型中識別移動路徑，為機器人移動路徑的規(guī)劃奠定了基礎。關于路徑的規(guī)劃則是需要使用算法，經過計算分析，確定最優(yōu)路徑。蟻群算法路徑搜索和選取的重要手段，被人們用來開發(fā)機器人移動路徑控制程序。由于以往開發(fā)的蟻群算法在機器人路徑規(guī)劃中的應用方案，缺少自適應調整，所以收斂速度偏小，不利于最優(yōu)移動路徑的挖掘。為了彌補這些不足，本文對蟻群算法進行改進，并探究改進后的應用方案。
1 移動機器人路徑規(guī)劃的格柵標識
移動機器人路徑規(guī)劃問題的研究，其核心是全局路徑規(guī)劃，按照類別的不同，可以將這個問題拆分為兩部分，其中一部分是機器人移動工作的環(huán)境建模，另外一部分為路徑規(guī)劃方法的探究。關于移動工作環(huán)境模型的構建，主要是將環(huán)境范圍轉化為能夠識別的數學模型，以便更加精準的控制移動路徑。格柵法是當前應用比較多的一種環(huán)境建模方法，通過創(chuàng)建二維直角坐標系，綜合分析機器人外形尺寸、障礙物尺寸，繪制柵格，形成3種不同區(qū)域。第一類障礙物格柵，此區(qū)域不可以通行；第二類半障礙物格柵，需要詳細計算，得到精準移動路徑；第三類無障礙格柵，可供行駛。
智能識別中，將第一類和第二類柵格均視為不可通行區(qū)域，賦值1，第三類格柵賦值0，從而實現機器人路徑規(guī)劃。在標識過程中，采用直角坐標系方法，為柵格定位，或者采用序號法進行標識。相比之下，后者標識方法簡單一些，本研究選擇序號標識法，對柵格進行定位。
2 蟻群算法的原理及改進
2.1 蟻群算法的原理
關于路徑規(guī)劃方法的研究，建立在模型創(chuàng)建基礎上，需要經過精準計算，確定最優(yōu)路徑。蟻群算法，通過模擬螞蟻行走路線，計算最佳路徑。通常情況下，可以將螞蟻行走路線看作旅行問題，在有效避開障礙物的前提下，通過計算起點和終點的最短路線，確定最終行進路線。假設螞蟻行走于i，j兩個城市之間，n只隨機選擇行走路線，經過m個時刻后，計算每一只螞蟻行走路線長度，同時保存最短路徑，將此路徑作為最優(yōu)路徑，并更新信息素。其中，信息素主要由兩部分組成，其中一部分為螞蟻行走期間留下的信息素，另外一部分為每一條路徑揮發(fā)的信息素。假設所有螞蟻行走軌跡信息素為 ，那么完成一次遍歷后，更新信息素的計算公式如下：
上述公式中，k代表城市遍歷路徑長度；Q代表螞蟻自身的信息素強度大��； 代表螞蟻在兩個城市之間爬行路徑上的信息素濃度； 代表遍歷城市后的總路徑長度； 代表信息素發(fā)揮系數。
從公式（3）的表達形式可以看出，信息素濃度大小在很大程度上取決于優(yōu)化程度，并且信息素濃度與路徑存在負相關關系。當遍歷路徑比較短的情況下，信息素濃度數值偏大。
2.2 蟻群算法的改進
2.2.1 基于路徑搜索的算法改進
算法開啟時刻，信息素量大小為0，需要經過一段時間的遍歷后才會表現出差異。所以，算法初期信息素并未起到爬行路徑引導作用，在搜索路徑方面耗費了大量時間。為了彌補蟻群算法在路徑搜索方面的不足，本文提出螞蟻相遇方法。這種方法是將螞蟻拆分為兩組，其中一組放置在起點，另外一組放置在終點，分別從兩地出發(fā)，向對方地點爬行，當兩組螞蟻在路途中相遇后，螞蟻各自回到初始位置。與傳統(tǒng)的單向自由搜索路徑相比，這種路徑搜索效率更高一些。假設起點螞蟻為 ，終點螞蟻為 ，那么兩只螞蟻相遇就可以用以下公式來表示：
當滿足上述條件時，兩只螞蟻在途徑相遇，此時兩只螞蟻的路徑總長度就是遍歷兩個城市路徑的總長度，記為：  （未完，下一頁）
|