基于多目標(biāo)蝗蟲優(yōu)化算法的移動機(jī)器人路徑規(guī)劃

黃超 梁圣濤 張毅 張杰

摘 要：在靜態(tài)多障礙物環(huán)境下的移動機(jī)器人路徑規(guī)劃問題中，粒子群算法存在容易產(chǎn)生早熟收斂和局部尋優(yōu)能力較差等缺點，導(dǎo)致機(jī)器人路徑規(guī)劃精度低。為此，提出一種多目標(biāo)蝗蟲優(yōu)化算法（MOGOA）來解決這一問題。根據(jù)移動機(jī)器人路徑規(guī)劃要求將路徑長度、平滑度和安全性作為路徑優(yōu)化的目標(biāo)，建立相應(yīng)的多目標(biāo)優(yōu)化問題的數(shù)學(xué)模型。在種群的搜索過程中，引入曲線自適應(yīng)策略以提高算法收斂速度，并使用Pareto最優(yōu)準(zhǔn)則來解決三個目標(biāo)之間的共存問題。實驗結(jié)果表明：所提出的算法在解決上述問題中尋找到的路徑更短，表現(xiàn)出更好的收斂性。該算法與多目標(biāo)粒子群（MOPSO）算法相比路徑長度減少了約2.01%，搜索到最小路徑的迭代次數(shù)減少了約19.34%。

關(guān)鍵詞：路徑規(guī)劃;移動機(jī)器人;蝗蟲優(yōu)化算法;多目標(biāo)

中圖分類號：TP242.6;TP23

文獻(xiàn)標(biāo)志碼：A

Abstract： In the mobile robot path planning problem in static multi-obstacle environment， Particle Swarm Optimization （PSO） algorithm has the disadvantages of easy premature convergence and poor local optimization ability， resulting in low accuracy of robot path planning. To solve the problem， a Multi-Objective Grasshopper Optimization Algorithm （MOGOA） was proposed. The path length， smoothness and security were taken as path optimization targets according to the mobile robot path planning requirements， and the corresponding mathematical model of multi-objective optimization problem was established. In the process of population search， the curve adaptive strategy was introduced to speed up the convergence of the algorithm， and the Pareto optimal criterion was used to solve the coexistence problem of the above three targets. Experimental results show that the proposed algorithm finds shorter paths and shows better convergence while solving the above problems. Compared with the Multi-Objective Particle Swarm Optimization （MOPSO） algorithm， the proposed algorithm has the path length reduced by about 2.01 percentage， and the number of iterations reduced by about 19.34 percentage.

Key words： path planning; mobile robot; grasshopper optimization algorithm; multi-objective

0 引言

在移動機(jī)器人導(dǎo)航系統(tǒng)中，規(guī)劃一條最優(yōu)路徑成為近年來一個重要的課題，引起了眾多研究者的關(guān)注[1]。移動機(jī)器人的最優(yōu)路徑規(guī)劃問題，就是依據(jù)某些優(yōu)化準(zhǔn)則（工作代價最小如行走路線最短等），在其工作空間中找到一條從起始狀態(tài)到目標(biāo)狀態(tài)并且能避開障礙物的最優(yōu)路徑。

當(dāng)前在移動機(jī)器人路徑規(guī)劃中常用的粒子群（Particle Swarm Optimization， PSO）算法[2]屬于進(jìn)化算法的一種，與模擬退火算法相似，它也是從隨機(jī)解出發(fā)，通過迭代尋找最優(yōu)解，利用適應(yīng)度來評價解的品質(zhì)，并通過追隨當(dāng)前搜索到的最優(yōu)值來尋找全局最優(yōu)。該算法的優(yōu)點是實現(xiàn)容易、精度高、收斂快;但容易產(chǎn)生早熟收斂，局部尋優(yōu)能力較差。賈會群等[3]為了提高路徑規(guī)劃的精度，對基本粒子群算法進(jìn)行改進(jìn)，將各階段慣性因子和加速因子使用三角函數(shù)方式進(jìn)行自適應(yīng)調(diào)節(jié)，并且引入了雞群算法中的母雞更新方程和小雞更新方程，提高了算法的搜索能力。多目標(biāo)進(jìn)化算法結(jié)合粒子群算法的研究在國內(nèi)外已經(jīng)取得了研究成果，2018年楊景明等[4]將帕累托（Pareto）解集與“多點變異”引入粒子群算法中，避免了算法陷入早熟收斂。但是多目標(biāo)粒子群（Multi-Objective PSO， MOPSO）算法在解集分布性、收斂性方面仍然存在不足。

近年來，一些學(xué)者提出了元啟發(fā)式方法[5]來克服經(jīng)典方法的不足。特別是在大范圍和高自由度問題中，蝗蟲優(yōu)化算法（Grasshopper Optimisation Algorithm， GOA）[6]由Saremi等于2017年1月提出?；认x算法相較于粒子群算法[7]具有良好的全局搜索能力和收斂速度。因為該算法的提出時間較短，目前對該算法的研究文獻(xiàn)較少，現(xiàn)在主要是對算法的應(yīng)用場景和算法自身的改進(jìn)兩個方面。2017年，Tumuluru等[8]利用蝗蟲優(yōu)化算法更新癌癥分級問題中神經(jīng)網(wǎng)絡(luò)的權(quán)值;2017年，Barman等[9]將蝗蟲優(yōu)化算法應(yīng)用于電力負(fù)荷預(yù)測問題中的向量機(jī)參數(shù)估計問題中。在算法改進(jìn)的方面，2017年Mirjalili等[10]提出了一種多目標(biāo)蝗蟲優(yōu)化算法（Multi-Objective Grasshopper Optimization Algorithm， MOGOA）;2018年閆旭等[11]將量子旋轉(zhuǎn)門引入基本蝗蟲優(yōu)化算法，并應(yīng)用到車間調(diào)度問題;2017年，程澤新等[12]首次將蝗蟲算法應(yīng)用到解決無人機(jī)（Unmanned Aerial Vehicle， UAV）三維航跡規(guī)劃問題中，并能夠規(guī)劃出一條較優(yōu)路徑。但由于UAV所處的環(huán)境障礙物較少、環(huán)境簡單，將蝗蟲優(yōu)化算法引入移動機(jī)器人路徑規(guī)劃當(dāng)中，其所處的環(huán)境相較于空中環(huán)境要復(fù)雜，所以容易陷入局部最優(yōu)和收斂精度不足。本文提出應(yīng)用曲線調(diào)整策略自適應(yīng)更新c參數(shù)來平衡局部搜索能力和全局搜索能力，提高算法的搜索能力;然后引入多目標(biāo)最優(yōu)方法來獲得合適的導(dǎo)航路線;最終提高了算法的收斂性及穩(wěn)定性。

為了平衡種群搜索和開發(fā)，需要用c參數(shù)動態(tài)調(diào)整蝗蟲群的勘探和開發(fā)，同時應(yīng)減小與迭代次數(shù)成比例的舒適區(qū)，采用曲線自適應(yīng)更新策略剛好彌補(bǔ)這一不足。式（15）中采用的是余弦自適應(yīng)方式，余弦函數(shù)在開始和結(jié)束時下降速率小，余弦自適應(yīng)調(diào)整參數(shù)c在前期的值比式（16）線性調(diào)整的值大，增加蝗蟲的搜索能力，隨著迭代次數(shù)的增加，搜索的效率提高，蝗蟲群會朝目標(biāo)位置附近收斂;后期c參數(shù)的比式（16）中的小，可以縮小蝗蟲的搜索范圍，增加蝗蟲的局部搜索能力。這些特點使得在不陷入局部最優(yōu)的情況下，極大地提高了算法的收斂速度。

2）添加外部儲存archive集來保存搜索過程中的非支配解。每次迭代過程對支配解集B進(jìn)行位置更新，并對更新后的支配解集B與archive中的粒子進(jìn)行比較，若xi∈B，且xj∈archive，使得xi支配xj，則刪除xj，使xi加入A更新外部archive，全局最優(yōu)解從外部儲存archive中選出。具有最短和最光滑路徑約束的多目標(biāo)路徑規(guī)劃優(yōu)化模型的主要目標(biāo)是獲得多目標(biāo)Pareto最優(yōu)解，因此，根據(jù)決策空間可行解集λ和Pareto最優(yōu)解F（p*），

MOGOA的主要目的是確定通過確定保存在archive中的Pareto最優(yōu)解集X的支配關(guān)系，

若新的候選解優(yōu)于當(dāng)前解，則優(yōu)勝劣汰，不斷更新當(dāng)前解和全局最優(yōu)解解。

2.2.2 算法流程

算法流程見圖1，具體算法步驟如下：

1）初始化蝗蟲種群的初始位置、種群規(guī)模及算法中的各參數(shù)，如：cmax、cmin、最大迭代次數(shù);

2）計算蝗蟲群每個搜索個體的適應(yīng)度值，并找出當(dāng)前全局最優(yōu)解;

3）M=最優(yōu)粒子;

4）使用式（17）更新參數(shù)c;

5）標(biāo)準(zhǔn)化區(qū)間在[1，4]的蝗蟲之間的距離;

6）通過式（6）更新當(dāng)前粒子的位置;

7）修剪外部種群，為每個粒子選擇全局最優(yōu)位置;

8）計算并選擇每個粒子的個體歷史最優(yōu)位置和種群最優(yōu)位置進(jìn)行比較;

9）將每個粒子的最優(yōu)位置粒子存檔，與M進(jìn)行比較，更新最優(yōu)粒子;

10）根據(jù)新的非支配解與已存檔的非支配解的比較，更新外部存儲archive;

11）移動機(jī)器人繞開障礙物，選擇距離目標(biāo)最安全的點，輸出最優(yōu)軌跡。

2.2.3 評價指標(biāo)該算法在多個障礙物且數(shù)目不同的環(huán)境中進(jìn)行了性能和效率的測試。

第一個測試標(biāo)準(zhǔn)是最優(yōu)解錯誤率（Error Ratio， ER）[16]，本文使用一個標(biāo)準(zhǔn)來評估多目標(biāo)優(yōu)化算法的性能，測量解是否為實際Pareto最優(yōu)解的概率，ER是評價帕累托最優(yōu)解算法精度的一個很好指標(biāo)。計算方法如下：

其中：m為Pareto最優(yōu)解的個數(shù)。當(dāng)xi=0時，得到的解是Pareto最優(yōu)解;否則，xi=1。

第二個測試標(biāo)注是最優(yōu)解覆蓋率SCM（Set Coverage Metric）[17]，計算公式如下：

其中：A和B是目標(biāo)空間中的兩個非支配解，即覆蓋率是B中的非支配解被A中非支配解覆蓋的個數(shù)在B中所占比例[18];|B|表示集合B中元素的個數(shù);表示Pareto占優(yōu)。

由式（19）可知，SCM（A，B）∈[0，1]。SCM（A，B）值越大，表示解集A覆蓋解集B的程度越高，也就是說A優(yōu)于B的程度也越高，當(dāng)SCM（A，B）>SCM（B，A）時，表示解集A覆蓋解集B的比例要小于解集B覆蓋解集A的比例，說明解集A中的非支配解要優(yōu)于解集B中的非支配解集。

3 實驗與結(jié)果分析

仿真實驗所用軟件是Matlab R2014，在具有Intel i7處理器（2.8 GHz）CPU和16 GB RAM的聯(lián)想筆記本上實現(xiàn)。最大迭代次數(shù)為100，cmax=1，cmin=0.00001。MOPSO的參數(shù)組合為：c1=c2=1.5，權(quán)重系數(shù)為0.8，最大最小權(quán)重系數(shù)分別為0.2和0.9。在環(huán)境1和環(huán)境2中，蝗群規(guī)模和粒子群規(guī)模均設(shè)置為500。

為了驗證該算法相較于粒子群算法的優(yōu)越性，與文獻(xiàn)[19]中的多目標(biāo)粒子群（MOPSO）算法進(jìn)行比較。實驗環(huán)境均采用20×20方格，初始位置的坐標(biāo)為（0，20），目標(biāo)位置的位置為（20，0），黑色陰影部分表示環(huán)境中的障礙物。

在環(huán)境1中，將障礙物的數(shù)量設(shè)置為80，圖2是MOGOA與MOPSO在80個障礙物數(shù)目下的路徑規(guī)劃結(jié)果和收斂性分析。

在環(huán)境2中，將障礙物的數(shù)量增加為100。圖3是MOGOA與MOPSO在100個障礙物數(shù)目下的路徑規(guī)劃結(jié)果和收斂性分析。

在環(huán)境1和環(huán)境2不同的障礙物數(shù)目下得到的路徑長度和迭代次數(shù)進(jìn)行比較分析。從表1可看出，不論在環(huán)境1還是環(huán)境2中，MOGOA在路徑長度均小于MOPSO，且收斂速度較快。多目標(biāo)蝗蟲群算法（MOGOA）與多目標(biāo)粒子群（MOPSO）算法相比路徑長度縮短了約2.01%，搜索到最小路徑的迭代次數(shù)相比減少了約19.34%。本文算法提高了蝗蟲優(yōu)化算法的搜索能力，同時也提高了算法的收斂速度。

表2為MOGOA和MOPSO在ER和SCM兩個指標(biāo)的運(yùn)算結(jié)果，為通過算法10次獨立運(yùn)行后獲得。從表2可以明顯看出，MOGOA的解集錯誤率都明顯低于MOPSO，同時在解集覆蓋度SCM（MOGOA，MOPSO）也都大于SCM（MOPSO，MOGOA），表明MOGOA在Pareto最優(yōu)解精度方面優(yōu)于MOPSO。因此，實驗結(jié)果表明，MOGOA能很好地收斂于帕累托最優(yōu)解。與MOPSO相比，本文算法在較短的時間內(nèi)獲得了最優(yōu)解和最優(yōu)路徑，說明該算法在尋找最短路徑、收斂性方面的性能優(yōu)于PSO算法。

為了驗證MOGOA的性能，將MOPSO和MOGOA在Schaffer2和ZDF4兩個多目標(biāo)測試函數(shù)上進(jìn)行對比，它們的最優(yōu)邊界收斂對比結(jié)果如圖4所示。Schaffer2和ZDF4具有不同的復(fù)雜度情況：Schaffer是一個一維兩個極小值點的函數(shù);ZDT4是一個多維多個極小值點的函數(shù)。

[11] 閆旭， 葉春明.混合蝗蟲優(yōu)化算法求解作業(yè)車間調(diào)度問題[J]. 計算機(jī)工程與應(yīng)用， 2019， 55（6）： 257-264. （YAN X， YE C M. Hybrid grasshopper optimization algorithm solves job-shop scheduling problem [J]. Computer Engineering and Applications 2019， 55（6）： 257-264.）

[12] 程澤新， 李東生， 高楊.基于蝗蟲算法的無人機(jī)三維航跡規(guī)劃[J]. 飛行力學(xué)， 2019， 37（2）： 46-50， 55. （CHENG Z X， LI D S， GAO Y. UAV three-dimensional path planning based on grasshopper algorithm[J]. Flight Dynamics， 2019， 37（2）： 46-50， 55.）

[13] HUA Y， JIN Y， HAO K. A clustering-based adaptive evolutionary algorithm for multiobjective optimization with irregular Pareto fronts[J]. IEEE Transactions on Cybernetics， 2019， 49（7）： 2758-2770.

[14] THABIT S， MOHADES A. Multi-robot path planning based on multi-objective particle swarm optimization[J]. IEEE Access， 2018， 7： 2138-2147.

[15] MAC T T， COPOT C， TRAN D T， et al. A hierarchical global path planning approach for mobile robots based on multi-objective particle swarm optimization[J]. Applied Soft Computing， 2017， 59： 68-76.

[16] COELLO C A C， LAMONT G B， van VELDHUIZEN D A. Evolutionary algorithms for solving multi-objective problems[M]. Boston： Springer， 2002.

[17] SHIM M， SUH M， FURUKAWA T， et al. Pareto-based continuous evolutionary algorithms for multiobjective optimization[J]. Engineering Computations， 2002， 19（1）： 22-48.

[18] FENG W， ZHANG L， YANG S， et al. A multiobjective evolutionary algorithm based on coordinate transformation[J]. IEEE Transactions on Cybernetics， 2019， 49（7）： 2732-2743.

[19] DI L， ZHENG Z， XIA M. Robot path planning based on an improved multi-objective PSO method[C]// Proceedings of the 2016 International Conferenceon Computer Engineering， Information Science & Application Technology. Paris： Atlantis Press， 2016： 496-501.