基于粒子群優化算法的機器人路徑規劃

覃正祥 丁家付 張彥旻 蔣偉 王志翔

摘? ?要：文章提出一種機器人路徑規劃的有效算法，為機器人找到一條從起點到終點最短的無碰撞路徑，主要是優化了粒子群的慣性權重，然而其在不同的階段采用不同的權重值。通過實驗發現，改進后粒子群能夠收斂得更快，數據收斂得更精確。

關鍵詞：優化粒子群;路徑規劃;移動機器人;環境模型

1? ? 路徑規劃

移動型機器人[1]的路徑規劃[2]是機器人能夠自主進行移動的必備先決條件之一，是指從起點到終點按照一定的約束條件，與環境中的障礙物無碰撞，達到研究者預設目標的最優規劃路徑。按照環境變量[3]劃分，可以將路徑規劃模型分為環境變量全局未知、環境變量局部未知、環境變量全局已知。

粒子群算法[4]是指如果需要搜索的環境變量是一個n維向量，則粒子群中的每一個粒子也是一個n維的向量。假設粒子群中共有M個粒子，則粒子群中的第i個粒子即可表示為該目標環境下的一個解，粒子通過不斷地改變自己的位置來尋求最優解。粒子的位置變化通過種群的粒子最優值、粒子自身的歷史最優值、粒子的自身狀態三者的共同疊加達到下一個位置點，并在最新點計算目標函數的值，刷新種群和個體的最優解，通過種群的迭代不斷刷新種群和個體的最優解，當達到預設的迭代次數時或者達到最優解或最優解附近時，迭代即可停止。

2? ? 數學模型

2.1? 環境模型建立

路徑規劃是移動機器人完成在復雜環境下移動導航的重要必備條件之一，在確定的環境下，按照目標的約束條件尋求一條從起始點到目標點的、和障礙之間無碰撞最優路徑。本文對二維平面上機器人的工作環境進行簡單的建模，再對障礙物及其邊界進行“圓形化”處理，避免了復雜的計算。環境模型的建立有多種方法，如：柵格法、人工勢場法、樹狀圖法等。為了避免過多復雜的討論，本文決定以障礙物圖形的幾何中心為原點，最大距離為半徑做圓，將障礙物全部囊括進所做的圓形中。

2.2? 粒子群算法介紹

假設粒子群的搜索空間是一個n維的連續空間，則第i個粒子的向量表現為：xi=（xi1，xi2，…，xi*n-1，xin），代表粒子i的速度向量為Vi=（vi1，vi2，…，Vi*n-1，vin）。

粒子群算法的迭代公式如下。

速度向量迭代公式：

（1）

位置向量的更新公式：

（2）

在速度向量迭代公式中，Pbest（i）表示第i個粒子的歷史最佳位置，Gbest體現種群歷史的最佳地位。可以看出，粒子群可以通過不斷地迭代學習自己和總粒子群的歷史最佳值，不斷規劃出新的位置點直至找到最佳的適應值。然而，實驗結果表明，由于粒子存在著隨機的不確定量，雖然粒子的全局檢索能力大大提高，但是會使其局部搜索能力較差。所以，在算法初期需要較強的全局搜尋能力，并在算法末期整個粒子種群應該有較強的部分搜索能力。在前期慣性權重應較大而在后期應較小，經過改動慣性權重修改了公式（1），從而提出了粒子群算法的慣性權重模型。

新的速度向量迭代公式為：

（3）

式（3）中，參數w是粒子群算法的慣性權重，是由函數隨機生成介于[0，1]之間的某個數，一開始讓w為0.98，使得粒子群優化算法（Particle Swarm Optimization，PSO）的全局搜尋能力較強，隨著迭代的逐漸深入，該參數逐步減小，從而使PSO具備較強的部分收斂能力;當迭代快要結束時，可以使這個參數趨近于0。參數c1，c2被稱為學習因子，通常被設置為1.5，參數rand（VarSize）的作用是產生一個隨機數，范圍為[0，1]。PSO算法的簡單流程如圖1所示。

2.3? 關于粒子群算法的優化

目前主要有3大類粒子群算法的優化方法：參數優化類、算法更新方程改進類和其他算法相結合類的算法優化。

本文主要探討第一類：參數優化改進類，以此改進粒子群算法。經過對前文的粒子群算法原理的介紹，了解到粒子群算法總共包含了3個參數：w，c1和c2。w是PSO的慣性權重，代表著粒子“按照自身意愿規劃下一步路徑”所占的比重，如果w較大，則利于全局尋找最優但是收斂較慢，不利于尋找局部的最優解，可能得不到最優解;如果w較小，則利于尋找局部最優解但不利于尋找全局最優解，易于陷入小范圍的最優解當中。因而使用一種慣性權重的自適應辦法，即在前期采用較大的w值，使之能夠有較大的搜索范圍，利于尋找全局最優，在后期采用較小的w值，讓其能夠在局部有較強的檢索能力。綜合兩方面優點，得出的慣性權重自適應公式為：

w=w*sin（pi/2+（pi/2）*（it/MaxIt））+wmin（4）

式中，利用正弦函數的變化規律，產生w參數的自適應功能。式子右邊的w表示上一次計算w的結果值，it表現為目前的迭代次數，MaxIt表示總的迭代次數，是預設的慣性權重的最小值，第一次的w值和wm均可根據條件的范圍以及搜索空間的大小，給出設定值。公式（4）根據粒子群的迭代次數的改變發生相應的變化，通過實驗觀察具有良好的全局搜索能力和局部的優化性能，且能夠快速收斂，比標準的粒子群收斂得更快、更精確。

3? ? 仿真研究

預設在二維平面內搜索從起點（0，0）到終點（8，8）的有效路徑，設定種群數量為150，總的迭代次數為200次，c1=1.5，c2=1.5，初始的w為2.5，慣性權重的最小值=0.05。實驗結果如圖2—3所示。

還可以公式進行改進：

w=w*sin（pi/2+（pi/2）*（it/MaxIt））+wm*it/MaxIt（5）

如圖4所示，進行改進型慣性權重的適應度調節，發現收斂得更快、數據更精確。

4? ? 結語

通過實驗仿真可以看出，在未加慣性權重適應度的情況下，粒子群在100代才穩定收斂于13.17;當加上慣性權重的適應公式后，粒子群在40代就穩定收斂于11.93。可見，經過算法的優化改進后，粒子群收斂得更快，同時，避免了粒子群算法的“早熟”和墮入部分最優解的弊端。但是改進的粒子群算法的不足是預設的w和wm需要根據環境和條件的不同而變化，可能需要多次嘗試。

[參考文獻]

[1]黃辰.基于智能優化算法的移動機器人路徑規劃與定位方法研究[D].大連：大連交通大學，2018.

[2]康玉祥，姜春英，秦運海，等.基于改進PSO算法的機器人路徑規劃及實驗[J].機器人，2018（12）：1-8

[3]黃超，梁圣濤，張毅，等.基于多目標蝗蟲優化算法的移動機器人路徑規劃[J].計算機應用，2019（10）：2859-2864.

[4]賈會群.無人駕駛車輛自主導航關鍵技術研究[D].北京：中國科學院大學，2019.

Robot path planning based on particle swarm optimization

Qin Zhengxiang， Ding Jiafu， Zhang Yanmin， Jiang Wei， Wang Zhixiang

（School of Information Engineering， Yangzhou University， Yangzhou 225000， China）

Abstract：This paper proposes an effective algorithm for robot path planning， which can find the shortest path for robot from start to end. It mainly optimizes the inertia weight of particle swarm， but it uses different weight values in different stages. The experimental results show that the improved particle swarm optimization can converge faster and the data converges more accurately.

Key words：particle swarm optimization; path planning; mobile robot; environment model