移動(dòng)機(jī)器人路徑規(guī)劃蟻群算法及其收斂性分析

劉廣瑞，劉 軍，孔令云

(1.鄭州大學(xué)機(jī)械工程學(xué)院，河南鄭州450001;2.黃河科技學(xué)院工學(xué)院，河南鄭州450005)

0 引言

移動(dòng)機(jī)器人的路徑規(guī)劃是指搜索一條從起點(diǎn)到終點(diǎn)的最優(yōu)或次最優(yōu)的無(wú)碰撞路徑使某性能指標(biāo)最優(yōu)或次優(yōu).路徑規(guī)劃可分為：全局路徑規(guī)劃和局部路徑規(guī)劃.其中，全局路徑規(guī)劃的環(huán)境信息是完全已知的，局部路徑規(guī)劃的環(huán)境信息是不完整或未知的.

蟻群優(yōu)化算法的論述和研究較多［1-10］，蟻群算法收斂性分析也有不少［5-6，9］，但是把蟻群優(yōu)化算法看做馬爾科夫過程進(jìn)行收斂性分析的并不多見.筆者的創(chuàng)新之處在于：將蟻群算法用于移動(dòng)機(jī)器人的路徑規(guī)劃，將蟻群算法的迭代過程視為馬爾科夫過程并進(jìn)行了分析，在此基礎(chǔ)上分析該算法的收斂性并提出了改善算法收斂性的途徑.

1 路徑規(guī)劃蟻群算法的基本原理

蟻群優(yōu)化(ACO)是蟻群算法的核心，其思路為：螞蟻的個(gè)體行為非常簡(jiǎn)單，而它們的群體行為卻很復(fù)雜;一群螞蟻容易找到從蟻巢到食物源的最短路徑，而單個(gè)螞蟻則難以找到最短路徑;蟻群能夠適應(yīng)環(huán)境的變化，當(dāng)在它們的移動(dòng)路線上突然出現(xiàn)障礙物時(shí)，它們能夠很快重新找到最短路徑.

1.1 環(huán)境模型的建立

采用柵格法建立移動(dòng)機(jī)器人的環(huán)境模型，建模時(shí)首先作如下假設(shè)：

(1)機(jī)器人的工作空間為一個(gè)二維結(jié)構(gòu)化空間，簡(jiǎn)記為RS;障礙物位置、大小已知且在機(jī)器人運(yùn)動(dòng)過程中均不發(fā)生變化.

(2)機(jī)器人的運(yùn)動(dòng)空間中分布著有限個(gè)已知的、大小不同的障礙物，障礙物可以由柵格描述，忽略障礙物的高度信息.

(3)假定機(jī)器人運(yùn)動(dòng)在二維平面上的凸多邊形有限區(qū)域內(nèi).

該區(qū)域內(nèi)分布著有限個(gè)大小不同的障礙物，在該區(qū)域內(nèi)建立直角坐標(biāo)系.假設(shè)機(jī)器人運(yùn)動(dòng)的步長(zhǎng)為R，并且x軸和y軸均以R為單位來(lái)劃分柵格.則每行的柵格數(shù)為：Nx=xmax/R;每列的柵格數(shù)為：Ny=ymax/R.

如果區(qū)域?yàn)椴灰?guī)則形狀，可在邊界處加上障礙柵格，補(bǔ)其為正方形或者長(zhǎng)方形.補(bǔ)充的障礙物柵格若不滿一個(gè)，以一個(gè)計(jì)算.柵格的位置可以用坐標(biāo)或序列號(hào)描述，序列號(hào)與坐標(biāo)是一一對(duì)應(yīng)的，圖1表示了柵格坐標(biāo)與序列號(hào)之間的關(guān)系.

1.2 柵格標(biāo)識(shí)方法

(1)直角坐標(biāo)法.建立如圖1所示的直角坐標(biāo)系.x軸水平向右為其正方向，y軸豎直向下為其正方向，坐標(biāo)原點(diǎn)在柵格陣左上角.用直角坐標(biāo)(x，y)來(lái)表示任意柵格的位置.

(2)序號(hào)法.按照由左到右，由上到下的順序，從柵格陣左上角第一個(gè)柵格開始，賦予每一個(gè)柵格一個(gè)序號(hào)n(從0開始計(jì))，則序號(hào)n與柵格塊一一對(duì)應(yīng)，如圖1所示.

圖1 柵格坐標(biāo)與序號(hào)的關(guān)系Fig.1 Relationship between grid coordinate and serial number

兩種表示方法都能唯一地表示一個(gè)柵格，一個(gè)柵格的直角坐標(biāo)和序號(hào)之間是一一對(duì)應(yīng)的.

2 路徑規(guī)劃蟻群算法的收斂性分析

2.1 蟻群算法的迭代過程是馬爾科夫過程

馬爾科夫過程是俄國(guó)數(shù)學(xué)家Α.Α.馬爾科夫于1907年首次提出的，是一類將來(lái)發(fā)生的事情與過去發(fā)生的事情無(wú)關(guān)的隨機(jī)過程［1］.這種在已知“現(xiàn)在”的條件下，“將來(lái)”與“過去”獨(dú)立的特性叫做馬爾科夫性.從蟻群算法的概念可知蟻群算法的迭代過程是一個(gè)典型的隨機(jī)過程.設(shè)蟻群在t=0，1，2，…，n 時(shí)，對(duì)應(yīng)的狀態(tài)分別為：E0，E1，E2，…，En.

若t=n時(shí)系統(tǒng)的狀態(tài)已知，那么由蟻群算法的迭代過程可知：在t=n時(shí)以前的狀態(tài)對(duì)t=n以后的狀態(tài)沒有任何影響，即在“現(xiàn)在狀態(tài)”已知的情況下，“將來(lái)狀態(tài)”與“過去狀態(tài)”相互獨(dú)立，這種過程就是馬爾科夫性.

2.2 蟻群算法的收斂性分析

預(yù)設(shè)A，B兩點(diǎn)之間有m條路徑AC1B，AC2B，AC3B，…，ACmB，如圖2所示.各條路徑長(zhǎng)度依次設(shè)為 d1，d2，d3，…，dm，不失一般性，假設(shè) d1≤d2≤d3≤…≤dm.在算法預(yù)定的環(huán)境中有n只螞蟻在A、B之間往返爬行，根據(jù)蟻群算法的特性可知，隨著時(shí)間的推移，大多數(shù)螞蟻應(yīng)在路徑AC1B上，此時(shí)我們就認(rèn)為從出發(fā)點(diǎn)A到目標(biāo)點(diǎn)B之間的最短路徑是AC1B，蟻群算法以接近于概率1的趨勢(shì)尋找最短路徑.

以qi，k表示螞蟻爬行第k趟后留在路徑ACiB上的平均信息素，pi，k表示螞蟻爬行第k趟后選擇路徑ACiB的平均概率.假設(shè)各條路徑上的初始信息量相等，均為C.

圖2 最短路問題Fig.2 Shortest route problem

定理 1 若 α≥0，β≥0，則 q1，k≥q2，k≥…≥qm，k，p1，k≥p2，k≥…≥pm，k，k=0，1，2，…，n.

證明：當(dāng) α≥0，β≥0 時(shí)，則

由 d1≤d2≤…≤dm，可得：p1，0≥p2，0≥…≥pm，0;qi，0= ρC+npi，0從而 q1，0≥q2，0≥…≥qm，0;

由上述推導(dǎo)過程可得

式中：ρ為信息素?fù)]發(fā)系數(shù).

由上述證明的過程可知：一個(gè)循環(huán)迭代結(jié)束后，路徑AC1B上的傳遞介質(zhì)濃度最高，因此路徑AC1B將會(huì)被更多螞蟻以較大概率選擇.

把 pj，k-1與 p1，k-1的表達(dá)式代到以上公式：簡(jiǎn)化得到因 qj，k-1＜ q1，k-1，dj＞ d1，當(dāng) α≥1，β≥0 時(shí)，式子成立.那么＜0，k=1，2，…n，j=2，3，…，m.

定理 3 若 α≥1，β≥1，則 p1，k＞ p1，k-1，k=1，2，….

證明：由于

證明：根據(jù)上述證明過程可得，若α≥1，β≥1 時(shí)，那么 p1，k＞ p1，k-1，隨機(jī)數(shù)列 p1，k單調(diào)遞增，由高等數(shù)學(xué)極限理論知識(shí)易知“單調(diào)有界數(shù)列必有極限，且收斂到其上界”可得，若k→∝滿足的條件下1.

3 改善蟻群算法收斂性的途徑

蟻群算法的收斂性與信息素更新機(jī)制及參數(shù)匹配有很大的聯(lián)系，可以從下述幾方面改善算法的收斂性.

(1)兩個(gè)指數(shù)α、β的選取至關(guān)重要，應(yīng)選在合適的范圍內(nèi);α≥1，β≥0，選擇最優(yōu)路徑的概率才會(huì)趨近于1.

(2)由定理1，2的證明過程可知，信息素?fù)]發(fā)系數(shù)ρ對(duì)算法的收斂速度有較大的影響，應(yīng)重視該參數(shù)的選擇.ρ愈小，過去信息揮發(fā)的愈快，算法收斂愈慢;ρ愈大，揮發(fā)的愈慢，算法收斂愈快.ρ應(yīng)在0和1之間選擇.

4 仿真計(jì)算

如圖2所示，假設(shè) A、B之間有4條路徑AC1B，AC2B，AC3B，AC4B，路徑長(zhǎng)度分別為 1，1.05，1.1，1.15，螞蟻數(shù)目 n=100，信息量 C=30，Q=1，ρ=0.6 .當(dāng) α =2，β=2時(shí)，算法收斂很快，選擇概率的結(jié)果如圖3所示;當(dāng)α=0.8，β=1算法運(yùn)行了200次后還沒有收斂，信息素變化規(guī)律結(jié)果如圖4所示.

當(dāng)α=1.1，β=-0.9時(shí)，選擇概率的結(jié)果如圖5所示，雖然收斂，但不一定收斂到最短路徑，如圖3所示就收斂到路徑AC2B中，由上述選擇概率的收斂圖可以看出：α≥1，β≥0是算法收斂的較好組合.

圖5 當(dāng) α=1.1，β= －0.9時(shí)蟻群算法選擇概率變化規(guī)律Fig.5 Selection probability varying rules of ant colony algorithm when α =1.1，β = －0.9

5 結(jié)論

為了尋找機(jī)器人從起點(diǎn)到終點(diǎn)的最優(yōu)或次最優(yōu)路徑，筆者將蟻群算法應(yīng)用于移動(dòng)機(jī)器人的路徑規(guī)劃之中，闡述了蟻群算法的基本原理，分析了路徑規(guī)劃蟻群算法的收斂性，概括性地指出了改善蟻群算法收斂性的途徑，并以最短路問題為例在設(shè)定參數(shù)下做了仿真計(jì)算.理論分析和仿真計(jì)算的結(jié)果均表明：指數(shù)在α≥1，β≥0的范圍內(nèi)時(shí)，算法有較好的收斂性.因此我們認(rèn)為，指數(shù)α、β以及信息揮發(fā)系數(shù)ρ對(duì)算法的收斂性影響較大，應(yīng)仔細(xì)選擇.

［1］馬良，朱剛，寧愛兵.蟻群優(yōu)化算法［M］.北京：科學(xué)出版社，2008：15-150.

［2］高尚，楊靖宇.群智能算法及其應(yīng)用［M］.北京：中國(guó)水利水電出版社，2006.

［3］高尚.解旅行商問題的混沌蟻群算法［J］.系統(tǒng)工程理論與實(shí)踐，2005，25(9)：100-104.

［4］段海濱.蟻群算法原理及其應(yīng)用［M］.北京：科學(xué)出版社，2005.

［5］馮遠(yuǎn)靜，馮祖仁，彭勤科.一類自適應(yīng)蟻群算法及其收斂性分析［J］.控制理論與應(yīng)用，2005，22(5)：713-717.

［6］高尚，楊靖宇.最短路的蟻群算法收斂性分析［J］.科學(xué)技術(shù)與工程，2006，6(3)：273-277.

［7］COLORNI A.Heuristics from nature for hard combinatorial optimization problems［J］.Int Trans in Opnl Res，1996，3(1)：1-21.

［8］PIRLOT M.General local search methods［J］.European J of Opnl Res，1996，92(3)：493-511.

［9］趙霞，田恩剛.蟻群系統(tǒng)及其收斂性證明［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43(5)：67-70.

［10］KELLER Y，AVERBUCH A.Fast motion estimation using bidirectional gradient methods［J］.IEEE Trans on Image Processing，2004，13(8)：1042-1054.