基于粒子群優(yōu)化算法的機(jī)器人路徑規(guī)劃

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

摘? ?要：文章提出一種機(jī)器人路徑規(guī)劃的有效算法，為機(jī)器人找到一條從起點(diǎn)到終點(diǎn)最短的無碰撞路徑，主要是優(yōu)化了粒子群的慣性權(quán)重，然而其在不同的階段采用不同的權(quán)重值。通過實(shí)驗(yàn)發(fā)現(xiàn)，改進(jìn)后粒子群能夠收斂得更快，數(shù)據(jù)收斂得更精確。

關(guān)鍵詞：優(yōu)化粒子群;路徑規(guī)劃;移動(dòng)機(jī)器人;環(huán)境模型

1? ? 路徑規(guī)劃

移動(dòng)型機(jī)器人[1]的路徑規(guī)劃[2]是機(jī)器人能夠自主進(jìn)行移動(dòng)的必備先決條件之一，是指從起點(diǎn)到終點(diǎn)按照一定的約束條件，與環(huán)境中的障礙物無碰撞，達(dá)到研究者預(yù)設(shè)目標(biāo)的最優(yōu)規(guī)劃路徑。按照環(huán)境變量[3]劃分，可以將路徑規(guī)劃模型分為環(huán)境變量全局未知、環(huán)境變量局部未知、環(huán)境變量全局已知。

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

2? ? 數(shù)學(xué)模型

2.1? 環(huán)境模型建立

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

2.2? 粒子群算法介紹

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

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

速度向量迭代公式：

（1）

位置向量的更新公式：

（2）

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

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

（3）

式（3）中，參數(shù)w是粒子群算法的慣性權(quán)重，是由函數(shù)隨機(jī)生成介于[0，1]之間的某個(gè)數(shù)，一開始讓w為0.98，使得粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）的全局搜尋能力較強(qiáng)，隨著迭代的逐漸深入，該參數(shù)逐步減小，從而使PSO具備較強(qiáng)的部分收斂能力;當(dāng)?shù)煲Y(jié)束時(shí)，可以使這個(gè)參數(shù)趨近于0。參數(shù)c1，c2被稱為學(xué)習(xí)因子，通常被設(shè)置為1.5，參數(shù)rand（VarSize）的作用是產(chǎn)生一個(gè)隨機(jī)數(shù)，范圍為[0，1]。PSO算法的簡單流程如圖1所示。

2.3? 關(guān)于粒子群算法的優(yōu)化

目前主要有3大類粒子群算法的優(yōu)化方法：參數(shù)優(yōu)化類、算法更新方程改進(jìn)類和其他算法相結(jié)合類的算法優(yōu)化。

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

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

式中，利用正弦函數(shù)的變化規(guī)律，產(chǎn)生w參數(shù)的自適應(yīng)功能。式子右邊的w表示上一次計(jì)算w的結(jié)果值，it表現(xiàn)為目前的迭代次數(shù)，MaxIt表示總的迭代次數(shù)，是預(yù)設(shè)的慣性權(quán)重的最小值，第一次的w值和wm均可根據(jù)條件的范圍以及搜索空間的大小，給出設(shè)定值。公式（4）根據(jù)粒子群的迭代次數(shù)的改變發(fā)生相應(yīng)的變化，通過實(shí)驗(yàn)觀察具有良好的全局搜索能力和局部的優(yōu)化性能，且能夠快速收斂，比標(biāo)準(zhǔn)的粒子群收斂得更快、更精確。

3? ? 仿真研究

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

還可以公式進(jìn)行改進(jìn)：

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

如圖4所示，進(jìn)行改進(jìn)型慣性權(quán)重的適應(yīng)度調(diào)節(jié)，發(fā)現(xiàn)收斂得更快、數(shù)據(jù)更精確。

4? ? 結(jié)語

通過實(shí)驗(yàn)仿真可以看出，在未加慣性權(quán)重適應(yīng)度的情況下，粒子群在100代才穩(wěn)定收斂于13.17;當(dāng)加上慣性權(quán)重的適應(yīng)公式后，粒子群在40代就穩(wěn)定收斂于11.93?？梢?，經(jīng)過算法的優(yōu)化改進(jìn)后，粒子群收斂得更快，同時(shí)，避免了粒子群算法的“早熟”和墮入部分最優(yōu)解的弊端。但是改進(jìn)的粒子群算法的不足是預(yù)設(shè)的w和wm需要根據(jù)環(huán)境和條件的不同而變化，可能需要多次嘗試。

[參考文獻(xiàn)]

[1]黃辰.基于智能優(yōu)化算法的移動(dòng)機(jī)器人路徑規(guī)劃與定位方法研究[D].大連：大連交通大學(xué)，2018.

[2]康玉祥，姜春英，秦運(yùn)海，等.基于改進(jìn)PSO算法的機(jī)器人路徑規(guī)劃及實(shí)驗(yàn)[J].機(jī)器人，2018（12）：1-8

[3]黃超，梁圣濤，張毅，等.基于多目標(biāo)蝗蟲優(yōu)化算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)應(yīng)用，2019（10）：2859-2864.

[4]賈會(huì)群.無人駕駛車輛自主導(dǎo)航關(guān)鍵技術(shù)研究[D].北京：中國科學(xué)院大學(xué)，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