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

摘 要：蟻群算法具有較強的魯棒性和發(fā)現(xiàn)較優(yōu)解的能力，但同時存在著限于局部最優(yōu)解、收斂速度慢、容易出現(xiàn)停滯現(xiàn)象等缺點。本文針對球形機器人的特點，考慮球形機器人本身的尺寸影響，對其進(jìn)行路徑規(guī)劃優(yōu)化處理。并且在傳統(tǒng)的蟻群算法基礎(chǔ)上，采用了退回原則和信息素加強原則對該算法進(jìn)行改進(jìn)。通過仿真結(jié)果表明，該方法能以任意接近于1的概率收斂到全局最優(yōu)解，并且提高了求解最優(yōu)解的效率。

關(guān)鍵詞：球形機器人；蟻群算法；路徑規(guī)劃

中圖分類號：TP242

路徑規(guī)劃是機器人智能化程度的一個指標(biāo)，其路徑規(guī)劃算法得出的路徑越短，也就體現(xiàn)出了該機器人的智能化程度越高。由于球形機器人可以應(yīng)用于危險環(huán)境的探測，管道內(nèi)部焊縫的檢測等方面，近年來國內(nèi)外對于球形機器人路徑規(guī)劃的研究成為了一個越來越熱門的話題?，F(xiàn)在已提出的路徑規(guī)劃智能算法有BP神經(jīng)網(wǎng)絡(luò)算法、遺傳算法、粒子群算法、模擬退火算法等，這些都是近幾年比較熱門的仿生啟發(fā)式算法。

根據(jù)機器人對環(huán)境情況的了解程度不同，路徑規(guī)劃可分為三種類型：環(huán)境信息全部已知情況下的全局路徑規(guī)劃，環(huán)境信息部分已知情況下的局部路徑規(guī)劃，全局路徑規(guī)劃和局部路徑規(guī)劃相結(jié)合。局部路徑規(guī)劃主要依靠于機器人實時地對周圍環(huán)境進(jìn)行檢測，從而獲得機器人的位置以及周圍障礙物的分布情況、尺寸大小、形狀等信息，并通過這些信息規(guī)劃出一條局部最優(yōu)路徑。因此，局部規(guī)劃可以跟隨環(huán)境的變化而發(fā)生改變，相對于全局規(guī)劃具有較強的適應(yīng)性和魯棒性。

1 環(huán)境模型

環(huán)境模型的主要目的是將外部環(huán)境情況轉(zhuǎn)變?yōu)閿?shù)字、符號等可操作的一些數(shù)學(xué)量，便于為求解模型或計算機仿真提供數(shù)據(jù)。環(huán)境模型是環(huán)境狀態(tài)到數(shù)學(xué)量的一個抽象映射過程，該過程在路徑規(guī)劃中占有重要的地位。

對于環(huán)境情況的表述有四種常用方法：（1）按照原始工作空間表示環(huán)境，（2）用柵格法表示環(huán)境，（3）空間劃分（包含有三種空間：自由空間、障礙空間、混合空間）法表示環(huán)境，（4）多邊形逼近法表示環(huán)境。

本文采用柵格法來表示機器人的工作環(huán)境，建立環(huán)境模型。在這里規(guī)定：（1）機器人每走一步的起始點和終止點都是柵格的中點；（2）機器人工作環(huán)境為已知且障礙物是靜止的；（3）環(huán)境障礙物的數(shù)目是有限的。將工作空間的左下角定義為坐標(biāo)原點O，以橫向為X軸，縱向為Y軸建立直角坐標(biāo)系。將工作空間劃分為m*n個柵格大小相同的正方形，該邊長為1。則機器人每斜走一步的步長為 ，水平和豎直方向的步長為1。其中柵格中的障礙物可能占了多個柵格，把其中不滿一個柵格處理成一個柵格被占滿來計算。

2 基于蟻群算法的路徑規(guī)劃模型

2.1 算法描述

蟻群算法可以看成是一種求解空間參數(shù)化概率分布模型的搜索算法框架，而求解空間參數(shù)化概率分布模型的參數(shù)就是信息素。本文中的路徑規(guī)劃的蟻群算法可以描述為：信息素模型用解構(gòu)造圖（柵格圖）的形式表現(xiàn)出來，然后定義一種隨機搜索的人工螞蟻，這些螞蟻根據(jù)構(gòu)造圖上的信息素的多少決定走的方向，某方向的信息素越多，人工螞蟻將會選擇走這個方向，當(dāng)人工螞蟻走過這條路，則在這條路上留下信息素。因此，根據(jù)概率分布，長度最短的路徑上會留下最多的信息數(shù)，以后所有的螞蟻將從這條路通過，最終得出在該構(gòu)造圖上的最優(yōu)路徑。

2.2 模型建立

4 結(jié)束語

本文針對球形運動器在已知環(huán)境信息情況下提出一種路徑優(yōu)化模型，并在此基礎(chǔ)上考慮到球形移動器本身的尺寸，然后通過計算得出補償后的障礙物尺寸，使得計算結(jié)果更加精確且符合實際情況。并針對蟻群算法的缺點，提出退回原則和信息素加強原則，并且對退回所經(jīng)過的柵格點上的信息素去掉，從這幾個方面對模型進(jìn)行改進(jìn)，提高了求解的收斂速度和最優(yōu)解的精度，同時又不會在計算過程中出現(xiàn)停滯現(xiàn)象。根據(jù)仿真結(jié)果表明，本分提出的改進(jìn)算法是有效的，并且具有較高的魯棒性。

參考文獻(xiàn)：

[1]史峰，王輝.MATLAB智能算法30個案例分析[M].北京：北京航空航天大學(xué)出版社，2011（07）：217-228.

[2]黃席樾.現(xiàn)代智能算法理論及應(yīng)用[M].北京：科學(xué)出版社，2005（04）：310-342

[3]覃剛力，楊家本.自適應(yīng)調(diào)整信息素的遺傳算法[J].信息與控制，2002（03）：198-201.

[4]王穎，謝劍英.一種自適應(yīng)蟻群算法及仿真研究.系統(tǒng)仿真學(xué)報，2002（01）：32-33.

[5]DORIGO M，GAMBARDELLA L M. Guest Editoria： Special Section on Ant Colony Optimization[J].IEEE Transactions on Evolutionary Computation，2002（04）：317-319

[6]崔世鋼，徐雪蓮，趙麗，田立國，楊耿惶.蟻群優(yōu)化在移動機器人路徑規(guī)劃上的研究[J].制造業(yè)自動化，2009（01）：5-8.

[7]王俊峰.基于改進(jìn)蟻群算法的機器人路徑規(guī)劃[D].南京師范大學(xué)，2005.

[8]C Wongngamnit.D Angluin The robot，the grid，and the algorithm，Technical Report，YALE/DCS/TR-1188，1999.

[9]陳雄，袁楊.一種機器人路徑規(guī)劃的蟻群算法[J].系統(tǒng)工程與電子技術(shù)，2008（05）：952-955.

[10]牛曉丹，朱曉光.蟻群算法在復(fù)雜地形下的路徑規(guī)劃應(yīng)用[J].軟件導(dǎo)刊，2009（02）：50-51.

[11]Zhu Qingbao.Ant Colony Optimization Parallel Algorithm And Based On Coarse—grained Model[J].Computer Engineering，2005（01）：157-159.

作者簡介：覃小峰，男，四川巴中人，研究方向；機械設(shè)計制造及自動化。

作者單位：西南交通大學(xué)，成都 610031