常 見，任 雁

(河南林業(yè)職業(yè)學院a.信息與藝術設計系；b.河南省果園管理特種機器人工程技術研究中心，洛陽 471002)

0 引言

當前，路徑規(guī)劃是智能機器人研究領域的熱點技術之一，其廣泛應用于工業(yè)、醫(yī)學和農業(yè)等各個領域[1-2]。路徑規(guī)劃的主要目的是根據特定標準在充滿障礙物的環(huán)境中，在規(guī)定的起點和終點之間找到一條最佳或接近最佳的無碰撞路徑[3]。在路徑規(guī)劃問題中，機器人路徑規(guī)劃的質量、效率及成功率，受機器人類型、環(huán)境條件、靜態(tài)或動態(tài)障礙物等眾多因素影響[4-5]。因此，要找到一條避免與障礙物干擾的平滑路徑或最短路徑是一個非常具有挑戰(zhàn)的問題。

由于路徑規(guī)劃問題的復雜性，通常將其視為非確定性多項式難題[6]。在早期研究中，主要通過進化算法尋找路徑規(guī)劃的最佳解決方案[7]。但進化算法在環(huán)境建模時，要求網格的位置預先固定，會使得路徑規(guī)劃的靈活性受網格大小的限制[8]。其次，進化算法主要采用隨機初始解決方案，將可能導致在多次迭代后找不到任何可行路徑，特別是對于大型復雜環(huán)境。同時，進化算法為單目標路徑規(guī)劃，只能實現路徑長度最小化規(guī)劃，即找到起點和目標位置之間長度最短的路徑[9]。在實際應用中隨著機器人工作環(huán)境的限制，傳統的單目標路徑規(guī)劃方法已無法滿足機器人路徑規(guī)劃需求[10]。

為解決上述問題，眾多專家學者對此開展了大量研究。王樂樂等[11]提出一種改進快速擴展隨機樹的機器人路徑規(guī)劃算法，通過建立搜索樹模型提高機器人路徑感知能力，能夠有效解決機器人在復雜環(huán)境下的路徑規(guī)劃問題。QU等[12]提出了一種混合灰狼路徑規(guī)劃優(yōu)化算法，通過簡化計算階段加快收斂速度并保留種群探索能力，從而獲得有效的最佳運動路徑，但上述方法路徑規(guī)劃效率相對較低，且易陷入局部極小點。阮曉鋼等[13]提出了一種自適應啟發(fā)式快速探索隨機樹路徑規(guī)劃方法，通過在起點、目標點、子目標點等處分別生成隨機樹同時進行擴展搜索，提高路徑規(guī)劃效率。CHAYMAA等[14]提出了一種基于改進交叉遺傳算法的自主移動機器人路徑規(guī)劃方法，通過對距離、安全性等條件進行優(yōu)化，同時避開障礙物，可在兩個位置之間找到一條有效且可行的路徑。姚曉通等[15]提出一種基于改進蟻群算法的機器人路徑規(guī)劃方法，通過對螞蟻狀態(tài)轉移策略的調整，改進個體在尋優(yōu)的過程中的導向性，使路徑規(guī)劃的路徑長度和迭代次數獲得最優(yōu)解，但上述方法存在初始解成功率低、運行時間長且路徑不平滑等問題。

針對上述問題，本文提出了一種基于改進遺傳算法的機器人路徑規(guī)劃方法。在路徑長度、路徑平滑度、路徑困難度等約束條件下以柵格法構建環(huán)境模型，并采用周圍點集法(surrounding point set，SPS)解決障礙物附近路徑生成問題。同時引入刪除算子、平滑算子和小生境法對傳統遺傳算法進行改進，提高路徑的平滑度，避免算法陷入早熟，提高算法收斂速度。

1 環(huán)境模型構建

如圖1所示為采用柵格點所構建的機器人工作環(huán)境，該二維空間內包含有多個障礙物，分別為Ob1,Ob2,…,Obn，機器人工作起點為S，目標位置為T。

圖1 機器人的工作環(huán)境

如式(1)所示為機器人的某一可行走路徑：

P={p1,p2,p3,…,pn}，
p1=S，pn=T，pi∩Obj=?
1≤i≤n，1≤j≤n

(1)

式中，n為機器人行走路徑集合P所包含的節(jié)點數；pi為路徑上的某一i節(jié)點。

本文改進遺傳算法下，機器人的行走路徑為：

(2)

式中，m為路徑集合P*中所包含的節(jié)點數量，該路徑需要滿足以下條件：

f(P*)=min{f1(P),f2(P),f3(P)}

(3)

式中，f1(P)、f2(P)、f3(P)分別見定義1、定義2、定義3。

定義1：f1(P)為衡量路徑P*的總長度的長度指標，如式(4)所示。

(4)

式中，|pipi+1|為節(jié)點pi、pi+1的歐式距離。

定義2：f2(P)為平滑度指標，表征路徑P*的平滑度，如式(5)所示。

(5)

式中，θ(pipi+1,pi+1pi+2)為pipi+1、pi+1pi+2之間的夾角。其中，0≤θ≤π，S為路徑P*中線段數量；C1為大于0的整數；Ni為i次迭代所得路徑中的節(jié)點數量。

定義3：f3(P)為路徑P*的困難指數，如式(6)所示。

(6)

式中，d(xi)為機器人經過i節(jié)點的困難程度。

經過上述3個目標對象，本文可以得到一組帕累托最優(yōu)路徑即為本文算法為機器人規(guī)劃的最優(yōu)路徑。

2 改進的多目標遺傳算法

針對多約束條件下的機器人路徑尋優(yōu)能力差、搜索效率低的問題，本文對傳統遺傳算法進行了改進。

2.1 個體編碼

傳統遺傳算法在處理問題時需要對初始種群當中的個體進行編碼，通常根據需要處理問題的不同需要選擇對應的編碼方式。在遺傳算法中二進制編碼方式是一種較為常用且應用廣泛的編碼方式。

本文機器人的工作環(huán)境為由柵格點構建的均勻分布的二維空間，每個柵格點用坐標(xi,yi)表示，其中xi為路徑節(jié)點橫坐標，yi為路徑節(jié)點縱坐標，不同節(jié)點構成的連線即為機器人的行駛路徑，節(jié)點之間的路徑長度總和即為機器人行駛的路徑長度。當二維空間分布的障礙物不同，則機器人行駛的路徑長度、節(jié)點數量、路徑復雜度均不同。如圖2所示為機器人可行路徑編碼示例。

圖2 移動機器人可行路徑編碼

2.2 種群初始化

傳統遺傳算法的種群初始化是隨機進行的，通常使用網格地圖或者是自由空間中隨機生成散布點來實現算法種群初始化。隨機初始化的問題在于，在初始化后需要考慮這些隨機生成的節(jié)點對于路徑規(guī)劃是否有用，當無用的節(jié)點過多時必然會導致算法的計算成本增加，甚至影響最優(yōu)路徑的獲取。

為了解決上述種群隨機初始化中存在的問題，對傳統遺傳算法種群初始化進行了改進，具體步驟如下：

步驟1：在機器人工作的二維空間中，首先確定機器人的起點和目標點。其中，機器人所處的位置位于起點；

步驟2：假設起點和目標點無障礙物，則移動機器人從起點根據最短直線距離方向向目標位置進行移動，如果移動途中有障礙物，則在障礙物周圍通過SPS算法生成點集，如圖3所示為該過程示意圖；

圖3 SPS算法生出初始路徑

步驟3：通過Dijkstra算法對SPS算法生成的路徑點的可行性進行測試，如果可行則繼續(xù)行走，如果路徑點不可行，則將柵格點的寬度進行縮減，而后返回步驟2；

步驟4：判斷機器人坐標是否已經到達目標位置，如果已經到達了，就保存當前從起點到目標點的路徑，如果沒有達到目標位置，那么就返回步驟2；

步驟5：計算種群中的個體的數量，如果種群數量大于等于2M，則結束迭代；如果小于2M，則從步驟1開始重復上述步驟。

2.3 適應值評價與分配

2.3.1 適應度函數

適應度函數是表示種群當中個體適應度的一種函數，通常采用適應度函數對種群中個體適應值進行計算，且該函數可以決定遺傳算法的搜索方向。考慮到機器人路徑規(guī)劃的復雜性，本文根據路徑困難度、平滑度以及路徑長度3個目標來確定適應度函數。其中主要考慮因素為路徑的困難度和長度，其次考慮路徑平滑度，式(4)～式(6)分別為對應的3個因素的目標函數。

2.3.2 適應值分配

適應值可以對算法迭代過程中的可行解的質量進行評估。本文使用SPEA2[16]方法對種群中的個體進行適應值分配，具體分配方法如下：

步驟1：種群初始化得到大小為N的種群P，另建一個大小為N′的空集合P′，而后將種群P復制至P′中；

步驟2：刪除P′中受其他個體支配的個體，若P′個體數>N′，那么需要通過聚類算法處理集合P′使其個體數量減少；

步驟3：集合P′中的個體可以根據式(4)求解適應值。

(7)

式中，t為在集合P′中i可支配的P中的個體數。

步驟4：對種群P中的個體分配如式(8)所示的適應值。

f(i)=1+∑S(j)

(8)

式中，j為集合P′中可以支配個體i的個體；S(j)為集合P′中個體j的適應值。

本文通過將P復制至P′的步驟來對重復解進行判斷，如果有重復解，那么就進行刪除，可以避免由于重復解導致的適應值高的個體因過度繁衍而造成的早熟收斂問題。

2.4 遺傳算子

在遺傳算子方面，本文主要是在傳統算法的基礎上增加了刪除算子和平滑算子，同時引入了小生境法來避免算法陷入局部最優(yōu)。具體如下：

(1)選擇。首先，隨機對種群中的個體進行分組；其次，根據精英保留的方法計算所有個體適應值并根據該值篩選出每個分組中適應度值較優(yōu)的個體，并讓這個個體可以直接進入子代群體中而非通過遺傳方式。

(2)交叉。隨機選擇兩個個體，并對兩個隨機個體的相同路徑點進行交叉，如果相同路徑點大于等于2個，那么選擇其中任意一個相同的路徑點進行單點交叉；若無相同路徑點，則分別從兩個個體各選擇一個路徑點，即交叉這兩個個體上選擇的路徑點，若交叉后形成的路徑為不連續(xù)路徑，則通過SPS算法將斷開的路徑重新連接形成連續(xù)路徑。

(3)變異。本文改進后遺傳算法中種群初始化路徑為可行路徑，即使經過選擇和交叉其仍為可行路徑，所以本文變異處理即為對可行路徑上點進行小概率小范圍調整，以確保個體變異后路徑仍可行。

圖4 個體交叉的過程

(4)刪除。經過變異處理后的路徑，往往可能還需要大量的迭代才能使路徑趨于平滑，因此本文增加了刪除算子。如圖5所示，如果在障礙物附近路徑需要多次轉折(見圖5a)，則對其中轉折點進行刪除，即刪除圖5a中的pi，連接pi-1和pi+1，生成一條可行的直線路徑段，通過這種方式一方面可以大大縮短機器人的行駛路徑，另一方面可以有效提高算法的迭代效率。

(a) 刪除前 (b) 刪除后圖5 刪除算子對路徑的處理

(5)平滑。為了提高機器人移動路徑的平滑度，本文借鑒了粒子群算法，即每個粒子記錄并跟蹤自身位置、速度兩個屬性，記錄歷史最優(yōu)值，同時在每次迭代中記錄全局最優(yōu)值，如此多次迭代直到滿足迭代退出條件。將本文二維空間中路徑節(jié)點代入到粒子群算法中，則路徑節(jié)點的坐標對應于粒子位置，而后根據該節(jié)點前后節(jié)點的坐標對粒子速度進行計算，并由粒子群算法不斷迭代計算最優(yōu)值，最終得到更新后的新坐標點。如圖6所示為機器人移動路徑的平滑過程。

圖6 路徑平滑過程

在圖6中，r1、r2∈random(0,1)，ω表示慣性權重，具體平滑過程如式(9)所示。

(9)

(6)小生境法。通過隨機種群初始化、選擇、交叉、刪除等步驟可以使傳統的遺傳算法隨機得到最優(yōu)路徑，但是其中存在種群單一、遺傳早熟、進化較為緩慢等問題。針對上述問題，本文引入了小生境法，即首先將2M個種群分解為M個小生境，其中M個小生境中又包含兩個個體相似度較高的種群。然后，同時讓M個小生境進化，而后對每個小生境中的個體適應度值進行計算，選擇兩個最優(yōu)的個體直接進入子代群體，并形成一個新的種群。通過這種方式可以有效保證種群遺傳的多樣性，進而提高算法的收斂性，避免了算法陷入局部最優(yōu)。如圖7所示為本文提出的改進遺傳算法的流程圖。

圖7 改進遺傳算法流程圖

3 實驗結果與分析

為評估所提改進型遺傳算法的性能，進行了算法有效性驗證實驗和對比分析實驗，兩個實驗均在MATLAB 2019仿真平臺上實現的。其中有效性驗證實驗主要比較改進后的遺傳算法較傳統遺傳算法的性能，而對比實驗主要將本次提出的算法與當前的一些主流算法進行比較。在對比實驗中，構建了6個地圖環(huán)境，不同環(huán)境的大小、形狀和障礙物數量各不相同。通過搭建不同的環(huán)境，為所提改進型遺傳算法在路徑長度、路徑平滑度、運行時間和路徑困難度等方面的性能進行對比分析。

實驗中改進遺傳算法的參數設置如表1所示。

表1 參數設置

3.1 有效性驗證實驗

如圖8所示為所提算法與傳統遺傳算法的路徑規(guī)劃結果，其中灰色正方形為起點，灰色五角星為目的地。如圖9所示為兩種算法的收斂曲線。

圖8 兩種算法路徑規(guī)劃 圖9 兩種算法收斂曲線

從圖8和圖9可知，傳統遺傳算法算法更容易陷入局部最優(yōu)解，收斂速度慢，規(guī)劃的路徑不夠平滑且路徑更長。在經過40次迭代后，傳統遺傳算法基本上收斂到最優(yōu)解，而所提的改進遺傳算法在20次迭代后即可收斂到最優(yōu)解。另外，從路徑的困難度上來看，傳統遺傳算法的路徑困難度為76，而改進后的遺傳算法路徑困難度為59。由此表明，改進后的遺傳算法在路徑長度、路徑平滑度以及路徑困難度等性能上均優(yōu)于傳統遺傳算法。

3.2 對比實驗

選取A*、PRM、B-RRT和PSO算法與所提改進型遺傳算法算法進行對比分析。如圖10所示，為A*、PRM、B-RRT、PSO和所提改進型遺傳算法的50次迭代執(zhí)行的路徑長度、平滑度、運行時間和路徑困難度的平均值，其中Map2和Mpa3兩個地圖環(huán)境下B-RRT無法進行路徑規(guī)劃，因此在柱狀圖中采用空白代替。圖11為所選取的幾種對比算法在6個不同地圖環(huán)境下的路徑規(guī)劃結果。

(a) 路徑長度 (b) 運行時間

(a) Map1 (b) Map2 (c) Map3

由圖10和圖11可知，在6個地圖環(huán)境中本文所提方法所獲得的路徑最短。同時，除路徑長度為目標函數外，引入的刪除和平滑算子使改進型遺傳算法能夠在除地圖4外其他環(huán)境中實現最平滑的路徑。其中地圖4環(huán)境中，PRM雖能夠獲得最平滑的路徑，但在所有環(huán)境中其路徑長度都比改進型遺傳算法長得多。因此，同時考慮路徑長度、路徑平滑度、運行時間和路徑困難度，所提改進型遺傳算法在所有環(huán)境中都表現出最佳性能。

4 結論

為解決機器人在多約束條件下路徑尋優(yōu)能力差、搜索算法收斂速度慢等問題，提出了一種改進遺傳算法的多機器人路徑規(guī)劃方法，并通過實驗分析得出以下結論：

(1)所提方法通過在目標函數中添加刪除算子和平滑算子可有效提高算法的迭代效率，獲取平滑的尋優(yōu)路徑。

(2)與其他幾種對比方法相比，在同時考慮路徑長度、路徑平滑度、運行時間和路徑困難度的多目標函數下，所提方法在所有環(huán)境中均能夠表現出最佳性能。

(3)所提方法僅考慮了靜態(tài)障礙物，下一步研究將致力于將所提方法擴展到具有移動障礙物的環(huán)境中進行路徑規(guī)劃。