面向機器人路徑規劃的改進粒子群算法

封建湖，張婷宇，封 碩，鄭寶娟

（1.長安大學理學院，陜西 西安710064；2.長安大學工程機械學院，陜西 西安710064）

1 引言

路徑規劃問題是在有復雜障礙物環境中搜索從初始點到目標點的無碰撞路徑［1］。機器人的路徑規劃即對機器人行駛路徑進行合理的決策。對于已知地圖環境的情況，粒子群優化（PSO）算法是一種模擬鳥類飛行的優化算法，具有收斂速度快、算法易于實現等優點；遺傳算法（GA）是基于生物種群進化的算法，具有全局收斂性的優勢。然而這兩種算法都有各自的局限性：粒子群算法容易陷入早熟、遺傳算法收斂速度較慢等問題。針對這種情況，文獻［2］提出了一種PSO和GA的混合算法，混合算法的初始種群由PSO生成，文獻［3］人提出了一種只與GA突變算子結合的PSO算法，避免了粒子陷入局部最優。文獻［4］在為旅客提供最佳路徑選擇的旅行商問題中提出PSO-GA算法，得到了很好的效果，但是會造成收斂代數大幅度增加。

針對算法中的不足，引入基于劃分的聚類方法中的Kmeans算法，對粒子進行聚類，把粒子劃分為若干個子群，使相當數量的具有較優適應度值的粒子位置信息傳遞到下一代粒子中。對每個子群采用一定規則的交叉和變異算子，從而提高粒子群算法的種群多樣性。在每個子區內更新粒子速度和位置時，隨著代數的增加改變慣性權重和加速系數。最后通過計算機仿真實驗驗證了該算法的有效性。

2 傳統粒子群算法

粒子群算法是用位置、速度、適應度來描述粒子的運動特征，每次迭代通過跟蹤粒子的個體極值Pbest和群體極值Gbest動態更新［5］。個體極值Pbest是粒子在迭代過程中得到的適應度值最優的個體所在位置，群體極值Gbest是搜索到所有粒子的適應度值最優個體所在位置。

傳統粒子群算法通過以下公式在每次迭代過程中更新速度和位置：

式中：ω—慣性系數，j=1,2,…,n—維數，c1、c2—加速度因子，r1、r2—［0，1］區間的隨機數。為了使粒子更好地搜索，通常將粒子的位置和速度限制在一定范圍內[ -xmax,xmax]、[ -vmax,vmax]。

傳統粒子群算法的劣勢在路徑規劃問題中體現為：粒子群算法是全局隨機搜索算法，但是如果缺少逃逸策略容易陷入局部最優解［6］。對于智能機器人，不僅需要盡可能縮短路徑長度，更加需要在復雜環境中減少路徑的起伏，使其平滑地走到終止點，避免局部最優的出現。

3 聚類融合交叉粒子群算法

3.1 環境建模

針對已知地圖情況下的機器人路徑規劃問題，柵格法是由文獻［7］于1968年提出。該方法將智能機器人實際運動環境分解成具有二值信息的網格單元，并通過判斷障礙物是否占用此網格單元進行分類，處理后的路徑規劃問題就轉化成在帶有序號表示的柵格網中尋找兩個網絡節點的最優路徑問題。

將已知地圖柵格化，在柵格化的空間中分布著若干障礙物，0表示自由柵格，在圖中用白色表示；1表示障礙柵格，在圖中用黑色表示。

3.2 適應度函數的選擇

在尋找最優路徑時，要綜合考慮路徑的長短和是否成功避開障礙物。在實際的三維地圖轉換為二維柵格表示中，障礙物點可能是機器不能穿過的點，也可能是坡度較大、易損失能量的點。綜合各種因素，改進的算法選擇的適應度函數如下所示：

式中：N－路徑段數，n－不可行的路徑段數目，D－已走的路徑總長度，通過公式（4）進行計算。

式中：(xs,ys),(xf,yf)—路徑的起點坐標與終點坐標。

3.3 K均值聚類

為了保持目標粒子種群的多樣性，引入K均值聚類算法。K均值聚類算法［8］是一種基于原型的目標函數聚類方法，將一批現實或抽象的數據對象分組成為多個類或簇的過程，是根據目標粒子的編碼設計，定義目標粒子i與粒子j之間的距離的度量函數，改進后的算法采用基于初始聚類質心產生法。

在聚類融合交叉粒子群算法中，將初始種群N中的粒子根據K-means算法分為若干個子種群Ci，由每個子種群的最優粒子以及個體最優粒子的速度和位置信息指導下一代粒子更新進行速度和位置值：

式中，(i=1,2,…,N)—粒子i目前搜索到的最優個體位置，qi(i=1,2,…,K)—每個聚類區Ci(i=1,2,…,m)中的粒子搜索到的最優位置。

3.4 交叉操作

交叉算子是指以某種方式對兩個染色體交換某部分基因，得到兩個新的個體［9］。改進的具體思想是：

（1）交叉概率初始化。為了加快收斂速度，交叉概率初始化時采用在迭代過程中隨代數線性遞增的方式，記為Cross=(cross1,cross2,…,crossN)，其中N為粒子數。算法中迭代次數t越大，粒子進行交叉操作的概率crosst也隨之增大。

（2）判斷是否交叉。對具有交叉可能性的粒子（i），隨機產生一個數字randi與之對應，當隨機數比交叉概率小時，即randi＜crosst，則對粒子i進行交叉操作，進入步驟3；反之，則粒子i跳過交叉操作（步驟3），執行算法的下一步。

（3）交叉操作。若粒子i需要進行交叉操作時，在粒子路徑點范圍內，隨機產生一個位置區間[xa,xb]，把分區極值qi位置區間內的路徑點覆蓋在被粒子i相應位置區間內，執行算法的下一步。

假設粒子路徑交叉區間是［3，4］，則交叉過程，如表1所示。

表1 粒子交叉操作示例Tab.1 The Example of Crossover

3.5 變異操作

變異算子是指對染色體中的一部分進行突變，使其轉化為一個新的個體［9］。相應的改進思路為：

（1）變異概率初始化。采用迭代過程中線性遞減的方式定義變異概率，記為Var′=(var1′,var2′,…,varN′)，算法中迭代次數t越大，粒子進行變異操作的概率vart′也隨之減小。

（2）判斷是否變異。對具有變異可能性的粒子i，隨機產生一個數字randi與之對應，當隨機數比交叉概率小時，即randi＜vart′，則對粒子i進行變異操作，進入步驟3；反之，則粒子i跳過步驟3，執行算法的下一步。

（3）變異操作。當粒子i達到變異概率vart′時，隨機選擇粒子i的一個路徑點(xc,yc)，使新生成的路徑點代替舊的路徑點，繼續算法的下一步。假設隨機產生的變異路徑點位置為3，則變異后的粒子，如表2所示。

表2 粒子變異操作示例Tab.2 The Example of Mutation.

3.6 自適應調整加速系數和慣性權重

在機器人路徑規劃過程中，早期希望機器人能有更多探索的能力，這樣保持路徑的多樣性；在后期希望機器人根據走過的路徑信息，有較多的自我學習能力，這樣使路徑能較快地收斂于全局最優解。為此，對傳統的粒子群加速系數進行改進，具體為：

式中：c1max和c1min—加速系數c1的上下限。c2max和c2min—加速系數c2的上下限。tmax—迭代的最大次數，t—當前迭代次數。

3.7 聚類融合交叉粒子群算法流程圖

圖1 聚類融合交叉粒子群算法流程圖Fig.1 Process of Clustering Combined with Crossed PSO Algorithm

4 仿真及結果分析

在MATLAB上分別用傳統粒子群算法、具有交叉、變異算子的粒子群算法和聚類融合交叉粒子群算法對虛擬輪式機器人進行了對比仿真實驗。

首先對復雜地圖初始柵格化，仿真過程中地圖大小從10×10逐步擴充到40×40，起始點定為（1，1），終止點為相應矩陣的對角點，并隨機生成一定比例的障礙物。

隨著柵格地圖的規模擴大，收斂代數和粒子數量都需要以一定比例增長才可以得到較為理想的路線。為了更好展示不同粒子群算法的應用效果，以40×40的路徑規劃效果為例說明。實驗中參數設置，如表3所示。

表3 路徑規劃參數表Tab.3 Parameter Setting for Path Planning

為了更加直觀看出算法的優勢，將算法運行50次效果，比較，如表4所示。

表4 算法運行50次仿真結果Tab.4 The Simulation Result for Three Algorithms Run Fifty Times

根據適應度公式（3）可以得到，適應度值越大，路徑長度越小，路徑表現越優秀。在柵格地圖較大、環境較為復雜的情況下，當總的迭代次數和粒子數目一定時，交叉粒子群算法比傳統粒子群算法的最優路徑長度縮短約16.3%，其中傳統粒子群算法收斂過快，容易陷入早熟；交叉粒子群則有效避免了早熟現象，從而減少了產生局部最優路徑的可能性，但是交叉粒子群算法比基礎粒子群的每一代迭代時間多了約64.8%，收斂代數增加了約90.8%，計算成本較高。聚類融合交叉粒子群是在交叉粒子群的基礎上，加了K-means聚類分析算法，比交叉粒子群算法收斂代數減少約23.8%。在保證相對最短路徑的情況下，跳出局部最優有很好的效果，同時程序運行過程中，聚類融合交叉粒子群中的分區操作，雖然使存儲空間有少許增加，卻大大減小了收斂代數，加快了收斂速度，且每一代的運行時間與交叉粒子群相差細微，最終得到最優路徑的總時間減少約45.9%，可以看出改進后的算法對點到點的機器人路徑規劃具有較好的應用價值。

從上述比較效果來看，本文改進后的算法搜索結果在精度上有明顯的提高。算法在迭代的開始對初始群體按照K-means聚類法分成若干個子群體，從而在迭代過程中每個粒子根據其個體極值和所在子種群中的最好個體更新自己的位置和速度，增加粒子的信息交換，有助于引導算法向可行路徑方向搜索。為了克服傳統算法在后期易于陷入局部最優的缺陷，引入交叉、變異算子，幫助算法擺脫局部極值點的束縛，極大地提高了算法的搜索效率，有效地實現了全局搜索能力及收斂速度方面的平衡。

下面將更加直觀地給出采用傳統粒子群算法、帶有交叉、變異算子的粒子群算法和聚類融合交叉粒子群算法的最優路徑圖，從起始點到目標點單獨執行10000代得到的路徑中，長度最短即適應度值最大的一次規劃路徑圖，如圖2所示。

圖2 三種算法的路徑圖Fig.2 Path Map of Three Algorithms

從上圖中容易看出，圖2（a）傳統粒子群優化算法在相同迭代次數下走出的路徑效果最差，雖然找出一條不和障礙物重疊的路線，但是粒子路線跳躍起伏較大，使機器人耗能隨之增大，明顯是一條局部最優路徑。圖2（b）是在傳統粒子群中加入交叉、變異算子后的結果，可以看出減少了一些冗余路線，效果雖然有所改進，但是耗費時間長，一些區域還存在可以優化的可能性。而在交叉粒子群的基礎上加入K-means聚類分析的改進算法，圖2（c）得到的最優路徑精度相對較高，在相同運行代數下，路徑長度明顯最短，路線較為順滑，相對而言降低了拐點數和無效路徑段，實際過程中可以達到減少能量消耗、機器損耗的效果。

為了更直觀看出加入聚類算法的優勢，對交叉粒子群算法和聚類融合交叉粒子群算法收斂情況進行比較（參數設置：粒子數為3000，迭代次數為10000，聚類數為10），如圖3所示。

圖3 兩種算法收斂情況對比圖Fig.3 Comparison of the Convergence Curve

對比結果可以看出，加入K-means聚類分析算法，能夠使收斂代數穩定下降，加快收斂速度，使得獲得最優路徑的總計算時間也大大縮短，對于智能路徑尋優有很好的效果。

雖然加入聚類的思想可以明顯達到加速收斂速度的效果，但是聚類的數目不同，產生的效果也不完全相同。選取5000粒子，10000代，在相同環境下對以下聚類數目進行對比實驗，對比結果，如表5所示。

表5 聚類效果對比Tab.5 Clustering’s Comparison of Effects

如果初始化參數時選擇的聚類數目過多，會導致這些群體極值中保留很多適應度值適中甚至偏差的粒子信息，將直接影響下一代的優化結果，最終導致形成的最優路徑趨于局部最優的結果。在仿真實驗中，我們可以根據柵格地圖的復雜度，選擇適中的分區數目，在加快收斂速度的同時選擇相對運算成本較小、路徑長度較優的參數設置。

5 結論

在機器人路徑規劃虛擬仿真過程中，通過引入聚類分析的思想和遺傳算法中的交叉、變異算子到傳統粒子群算法中，避免了粒子群算法在復雜環境下容易出現停滯現象，最終出現局部最優的結果，有效的幫助機器人找到最優路徑。通過對比仿真實驗可以看出，改進后的算法有以下三個優點：

（1）加入交叉、變異算子，增加了粒子多樣性。

（2）引入復雜環境下適合的聚類數目，可以加快算法收斂速度。

（3）在路徑規劃的應用中，改進后的算法搜索出的路徑明顯優于傳統粒子群算法和交叉粒子群算法。