劉廣瑞，劉 軍，孔令云

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

0 引言

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

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

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

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

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

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

(1)機器人的工作空間為一個二維結構化空間，簡記為RS;障礙物位置、大小已知且在機器人運動過程中均不發(fā)生變化.

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

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

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

如果區(qū)域為不規(guī)則形狀，可在邊界處加上障礙柵格，補其為正方形或者長方形.補充的障礙物柵格若不滿一個，以一個計算.柵格的位置可以用坐標或序列號描述，序列號與坐標是一一對應的，圖1表示了柵格坐標與序列號之間的關系.

1.2 柵格標識方法

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

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

圖1 柵格坐標與序號的關系Fig.1 Relationship between grid coordinate and serial number

兩種表示方法都能唯一地表示一個柵格，一個柵格的直角坐標和序號之間是一一對應的.

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

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

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

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

2.2 蟻群算法的收斂性分析

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

以qi，k表示螞蟻爬行第k趟后留在路徑ACiB上的平均信息素，pi，k表示螞蟻爬行第k趟后選擇路徑ACiB的平均概率.假設各條路徑上的初始信息量相等，均為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.

證明：當 α≥0，β≥0 時，則

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

由上述推導過程可得

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

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

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

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

證明：由于

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

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

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

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

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

4 仿真計算

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

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

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

5 結論

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

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

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

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

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

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

［6］高尚，楊靖宇.最短路的蟻群算法收斂性分析［J］.科學技術與工程，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］.計算機工程與應用，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.