多約束條件下基于改進遺傳算法的移動機器人路徑規(guī)劃

胡章芳，程 亮，張 杰，王春瑞

(重慶郵電大學 光電工程學院，重慶 400065)

0 引 言

機器人路徑規(guī)劃一直以來都是研究的熱點。移動機器人路徑規(guī)劃的一個難點是在有障礙物的環(huán)境中確定從起始點到目標點的全局最優(yōu)路徑，同時要避免碰撞。依據(jù)不同的角度，可以對路徑規(guī)劃方法進行不同的分類，本文將其分為傳統(tǒng)算法和智能算法，前者主要包括圖搜索法[1]、人工勢場法[2]和柵格法[3]等，這些方法搜索效率低，得到的優(yōu)化結果也不太理想，后者主要包括遺傳算法[4]、蟻群算法[5]、免疫算法[6]和神經網絡算法[7]等，這些算法雖然使機器人路徑規(guī)劃在性能方面得到提升，但是存在著運算時間較長、搜索空間較大、效率較低等問題。傳統(tǒng)算法大部分解決的是單個約束條件下的問題(如路徑最短)，在實際環(huán)境中往往需要考慮多個約束條件以尋找到一條最優(yōu)或次優(yōu)路徑，而這些約束條件往往是相互協(xié)調、相互競爭的，不存在使多個約束條件同時達到最優(yōu)解的情況。機器人路徑規(guī)劃本質上是一個具有多個性能指標的NP(non-deterministic polynomial)完全問題，很難找到精確的解決方案。因此，在多約束條件下優(yōu)化機器人行走路徑具有非常重要的實際意義[8]。

近年來，已有不少專家學者對此進行大量研究并提出多種路徑優(yōu)化方法和策略，文獻[9]提出一種在離散環(huán)境下進行移動機器人路徑規(guī)劃的新方法，主要是基于電場勢理論和電場對電荷的影響并在此基礎上，借鑒前人關于非凸數(shù)據(jù)聚類的研究成果，構造了一種基于路徑規(guī)劃的優(yōu)化算法，該算法雖然計算簡單，但容易陷入局部最優(yōu)。

文獻[10]提出了一種改進的交叉算子，用于求解靜態(tài)環(huán)境下的遺傳算法路徑規(guī)劃問題，該交叉算子使用具有良好適應度的雙親來提高后代的質量，同時使用適應度值較低的雙親來探索研究空間，確保種群之間的多樣性，但在交叉過程中增加了算法的搜索時間，從而延長了算法的運行時間。

文獻[11]針對移動機器人提出一種快速最優(yōu)路徑規(guī)劃算法。該算法采用粒子群技術將收斂度控制到全局最小，并采用自定義算法生成搜索空間的坐標，以確定給定的2個端點位置之間的最短路徑。該算法雖然能都較快尋找到一條最短路徑且改善了粒子群算法在種群規(guī)模較小時表現(xiàn)不佳的問題，但不適用于處理離散的優(yōu)化問題且容易陷入局部最優(yōu)。

文獻[12]利用蟻群算法對復雜環(huán)境中的移動機器人進行路徑規(guī)劃，針對不同工位、不同大小、不同形狀的障礙物，對算法參數(shù)進行了分析和調整。該算法雖然在一定程度上改善了復雜環(huán)境下蟻群算法的性能，但是需要不斷重復性的實驗確定參數(shù)以獲得一條最優(yōu)或次優(yōu)路徑，耗費時間長，且在簡單環(huán)境下該算法的性能會有所降低。

針對在多約束條件下移動機器人在路徑規(guī)劃中搜索效率低、收斂速度慢的缺點，本文研究一種多約束條件下基于改進的遺傳算法應用于機器人路徑規(guī)劃領域，在生成初始種群的過程中，引入SPS (surrounding point set)算法，并用Dijkstra算法測試該路徑是否可行；然后增加刪除算子、平滑算子優(yōu)化生成的路徑，加快算法的收斂速度，以降低在多約束條件下機器人路徑規(guī)劃所耗費的時間；最后引入小生境法來保持種群多樣性，避免算法陷入局部最優(yōu)。

1 問題描述

為了方便起見，本文做如下描述和定義。

首先，機器人工作在均勻分布柵格點的二維空間，空間中分布著Ob1,Ob2,…,Obn等數(shù)目有限的靜態(tài)障礙物，起始點記為S，目標點記為T，如圖1。

圖1 機器人工作環(huán)境Fig.1 Robot working environment

接著，機器人的可用路徑表示為

P={p1,p2,p3,…,pn},

p1=S,pn=T,pi∩Obj=?,

1≤i≤n,1≤j≤n

(1)

(1)式中：pi表示路徑P的第i個節(jié)點；n表示一條可用路徑節(jié)點的數(shù)量。

通過多約束條件下基于改進遺傳算法得到的移動機器人行走路徑表示為

(2)

(2)式中，m表示通過本文算法得到的行走路徑的數(shù)量，該路徑需要滿足

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

(3)

(3)式中，f1(P),f2(P),f3(P)分別由定義1—定義3給出。

定義1長度指標是指路徑的總長度，用f1(P)表示為

(4)

(4)式中，|pipi+1|是路徑節(jié)點pi到路徑節(jié)點pi+1的歐式距離。

定義2平滑度指標是指路徑中所有相鄰矢量線段的角度之和，用f2(P)表示為

(5)

定義3困難度指標是指機器人經過路徑中每一個節(jié)點的困難指數(shù)之和，用f3(P)表示為

(6)

(5)式中：xi表示路徑中第i個節(jié)點；d(xi)表示機器人通過該節(jié)點的困難指數(shù)。

最后，本文提出的機器人路徑規(guī)劃是在前面定義的3個目標對象上得到的一組帕累托最優(yōu)路徑。

2 基于多約束條件下改進的遺傳算法

針對在多約束條件下移動機器人在路徑規(guī)劃中的搜索效率低、收斂速度慢的問題，本文設計的改進遺傳算法流程圖如圖2。

圖2 改進遺傳算法流程圖Fig.2 Flow chart of improved genetic algorithm

2.1 個體編碼

遺傳算法在給定問題上需要對初始種群的潛在個體進行遺傳編碼，不同的問題需要選擇不同的編碼方式，其中二進制編碼方式在遺傳算法中應用最廣泛。

本文機器人工作于均勻分布的二維柵格點的空間中，空間中的每個點都有自己的坐標，恰好適用于二維編碼：(x1,y1)→(x2,y2)→…→(xn,yn)，其中xi和yi是二維坐標中潛在路徑節(jié)點的橫坐標與縱坐標，且路徑節(jié)點的數(shù)量和長度是可變的，這取決于空間中障礙物分布的復雜程度，在障礙物密集區(qū)域，路徑節(jié)點的長度和數(shù)量都會增加，使路徑更加順暢和安全，在障礙物稀疏區(qū)域，路徑節(jié)點的長度和數(shù)量會相應減少，這種編碼方式可以增加搜索的精度和靈活性。圖3是一個路徑編碼示例。

圖3 可行路徑的染色體表示Fig.3 Chromosome representations of feasible path

2.2 產生初始種群

傳統(tǒng)遺傳算法[13]采用的群體初始化方法是隨機的。許多研究都是通過在自由空間中隨機散布點或在網格地圖中考慮所有點來生成點。這些方法存在這樣的問題，即在路徑生成階段必須考慮對于最優(yōu)路徑而言不必要的點，這導致很高的計算成本，并且還可能無法生成最優(yōu)路徑，因為這些生成的點在狹窄或很小的空間內是不可用的。隨機點生成方法在每個獨立的運行中特別容易返回不一致的解決方案。此外，由于元啟發(fā)式算法通過隨機操作來工作，存在隨機性，因此減少最終解發(fā)生變化的可能性非常重要。

針對路徑規(guī)劃中的種群初始化問題，也有些學者提出了一些改進方法。例如，文獻[14]認為，起點和目標點都是已知的，因此當環(huán)境中沒有障礙物時，連接2點的線將是最短、最平滑的路徑。在這種啟發(fā)式信息的幫助下，利用隨機方法在直線附近生成了一些初始路徑。這種方法在相對理想的環(huán)境中效果較好，但在復雜的環(huán)境中尤其是在有障礙物定位起點與目標點連線的情況下，效率較低。

考慮到機器人路徑規(guī)劃的特點，生成初始種群的具體步驟如下[15]。

步驟1在二維柵格點圖中，設置機器人的初始點坐標和目標點坐標，并將機器人放置起始點。

步驟2機器人朝著目標點沿直線行走，若碰到障礙物，則采用SPS算法在障礙物的周圍產生點集。

步驟3用Dijkstra算法測試產生的路徑點是否可行，若可行，則繼續(xù)前進；若不可行，則減小柵格點寬度，重復步驟2。

步驟4判斷是否到達目標點，若已到達，則把當前產生的路徑保存下來，若未到達，則重復步驟2和步驟3。

步驟5判斷個體數(shù)目達到種群數(shù)目2M，若達到，則結束；若沒達到，則重復以上步驟。

圖4是根據(jù)SPS算法在MATLAB R2016a中仿真出的初始路徑圖(一個障礙物)。

圖4 仿真圖(一個障礙物)Fig.4 Simulated diagram (an obstacle)

通過周圍點集法產生初始路徑不僅搜索效率高，收斂速度快，沒有很高的計算成本，且所產生的初始路徑都是可行的，減小了產生初始路徑的隨機性，使得最終解發(fā)生變化的可能性很小。

2.3 適應值評價與分配

2.3.1 適應度函數(shù)

適應度函數(shù)是度量種群中每個個體適應度的函數(shù)，是由目標函數(shù)確定的。一旦形成初始種群，遺傳算法必須要根據(jù)適應度函數(shù)來確定每個個體的性能，該函數(shù)能夠為每個可行解分配一個反映其質量的適應值。它是遺傳算法在進化過程中的一個重要組成部分，適當選擇適應度函數(shù)將使搜索朝著最優(yōu)解的方向發(fā)展。適應度函數(shù)必須要考慮一些標準，比如路徑的長度、安全度以及平滑度等，因為遺傳算法需要使用該函數(shù)的值來選擇個體并通過交叉變異繁衍后代，直到算法結束時選擇最終群體的最優(yōu)解。

本文適應度函數(shù)需要考慮3個標準：路徑長度、路徑平滑度以及路徑困難度。其中將路徑長度和路徑困難度作為主要標準，路徑平滑度作為次要標準，并將(4)—(6)式分別作為它們的目標函數(shù)。

2.3.2 適應值分配

本文采取SPEA2[16]的適應值分配方法，該方法在為每個個體分配適應值的時候，既考慮了支配該個體的數(shù)目，也考慮了受該個體支配的數(shù)目。主要流程如下。

步驟1生成初始種群集合P，大小為N，建立一個空集合P′，大小為N′，并將集合P復制到集合P′中。

步驟2從P′中刪除受其他個體支配的個體，即Pareto Front為1的個體，若P′中個體數(shù)目大于N′，則采用聚類算法減少P′中個體的數(shù)目。

步驟3為P′中的個體分配適應度值得

(7)

(7)式中：i表示的是P′中的個體；t表示的是P′中的個體i支配P中個體的數(shù)量。

步驟4為P中的個體分配適應度值得

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

(8)

(8)式中：j表示在P′中支配i的個體；S(j)為個體j在P′中的適應度值。

本文對該方法進行改進，從集合P復制到P′的過程中，判斷是否有重復的解，若有則刪除，可以有效地防止適應度好的個體迅速繁衍而導致的早熟收斂。

2.4 遺傳算子

1)選擇。本文采用錦標賽法進行選擇，即對種群中的個體進行隨機分組，每組根據(jù)個體的適應度值選擇適應度值最低的個體進入子代種群。并采用精英保留策略，按一定比例將適應度最優(yōu)的個體不需要經過遺傳直接復制到子代種群。

2)交叉。本文采用單點交叉方式，即隨機選擇2個個體，找出路徑相同點進行交叉，這樣可以保證路徑的連續(xù)性，如圖5所示過程，如果不止一個路徑相同點，則隨機選取任意一個進行路徑交叉，如果沒有路徑相同點，則從2個個體中隨機選取2個點進行交叉，如果交叉后不是連續(xù)的路徑，則將上半段的最后一個點和下半段的第1個點作為起始點和目標點，運用障礙物的周圍點集進行修補使其成為一條連續(xù)的路徑。

3)變異。本文的研究方法產生的初始路徑一定是可行的，且經過選擇和交叉之后亦是如此，所以本文對路徑上點的坐標依據(jù)概率進行小范圍調整即可，從而保證變異后路徑的可行性。

圖5 交叉過程Fig.5 Cross process

4)刪除。在沒有增加刪除算子之前，可能會出現(xiàn)圖5的情況，則需要更多的迭代次數(shù)使路徑趨近于平滑。所以本文增加了刪除算子，如果一條路徑中存在如圖6a的情況，刪除pi后，pi的前一個路徑點pi-1與后一個路徑點pi+1相連后是可行路徑段，則刪除pi，連接pi-1與pi+1產生一條新的路徑，如圖6b，從而在一定程度上加快了算法的收斂速度，減少了算法的運行時間。

圖6 刪除前后路徑Fig.6 Path of before and after deletion

5)平滑。該路徑的平滑度算法是受到粒子群算法的啟發(fā)，在粒子群算法中每個粒子都有位置和速度2個屬性，在迭代過程中每個粒子需要跟蹤自己的歷史最優(yōu)值和全局最優(yōu)值，直到滿足終止條件。本文路徑中的每個坐標點相當于粒子群算法中粒子的位置，根據(jù)該坐標點的前后坐標計算出粒子的速度，根據(jù)位置更新公式和速度更新公式，計算出新的坐標點，經過多次迭代后使路徑更平滑。過程如圖7。

圖7中：ω是慣性權重，表示的是前一時刻速度對當前速度的影響程度；r1和r2是0和1之間的隨機數(shù)。各參數(shù)含義為

xt+1,i(p)=xt,i(p)+vt+1,i(p)

圖7 平滑過程Fig.7 Smoothing process

6)小生境法[17]。傳統(tǒng)的遺傳算法雖然能隨機尋找問題的最優(yōu)解，但是在應用過程中單一的種群個體很難保證種群的多樣性，容易出現(xiàn)早熟現(xiàn)象，且遺傳算法在本質上是串行運行的，進化過程相對比較緩慢。為了避免上述問題的產生,本文把2M個種群個體分解為M個小生境，每個小生境由2個相似的種群個體組成，種群的相似度由海明距離決定，海明距離越小，相似度越高。接著將M個小生境同時進化和繁衍，然后在每個小生境中選擇2個優(yōu)良個體進入下一代，最終由每個小生境中選擇適應度高的個體形成新的種群進行進化和繁衍，從而保持了種群的多樣性，在一定程度上加快了算法的運行速度。

3 實驗與分析

3.1 仿真環(huán)境

本文采用MATLAB R2016a構建仿真平臺，設置仿真環(huán)境如圖8，為了驗證本文算法的有效性，把它分別與文獻[10]、文獻[12]中的算法以及傳統(tǒng)的遺傳算法進行了比較，設置障礙物分布在柵格點寬度為10的500×500的柵格點矩陣中，機器人的起點為(10,10)，如圖8左上角的點，終點為(490,490)，如圖8右下角的點，圖8中黑色表示障礙物。

3.2 參數(shù)設置

種群規(guī)模N為50，最大迭代次數(shù)T=300，前T/2中，交叉概率Pc=0.5，變異概率Pm=0.5，刪除概率Pd=0.4，平滑概率Ps=0.1；后T/2中，交叉概率Pc=0.2，變異概率Pm=0.1，刪除概率Pd=0.4，平滑概率Ps=0.6。

3.3 結果分析

圖8表示的是多約束條件下由4種算法找到的從起點(10,10)到終點(490,490)的路徑，表1表示的是4種算法在路徑長度、路徑平滑度、路徑困難度與時間成本方面運行結果的數(shù)據(jù)對比，圖9表示的是4種算法迭代100次的收斂曲線。

圖8 4種算法路徑圖Fig.8 Path graph of four algorithms

圖9 4種算法收斂曲Fig.9 Convergence curves of four algorithm

表1為4種算法50次運行結果對比，由表1可以看出，相比于傳統(tǒng)的遺傳算法，本文改進的算法在路徑長度、路徑平滑度、路徑困難度以及時間成本方面都明顯優(yōu)于對方，即使與較新的文獻[10]算法相比，仍然略優(yōu)于對方。傳統(tǒng)遺傳算法的平均運行時間是14.69 s,文獻[10]算法的平均運行時間10.58 s，本文改進算法僅用了8.57 s，比傳統(tǒng)遺傳算法的運行時間縮短了1.7倍，相比于文獻[10]算法，運行時間縮短了1.23倍，且本文改進的遺傳算法相比于與文獻[10]、文獻[12]中的算法以及傳統(tǒng)的遺傳算法，在路徑長度、路徑平滑度以及路徑困難度方面均具有一定的優(yōu)勢。

由圖9可以看出，本文改進的遺傳算法相比于傳統(tǒng)的遺傳算法，收斂的速度得到一定的提升，而且最終收斂的值也小于傳統(tǒng)算法(在路徑規(guī)劃中，尋找最優(yōu)路徑所付出的代價越小越好)；本文改進的遺傳算法相比于其他2種算法，雖然最終收斂的值非常接近，但收斂速度卻得到略微的提升。所以本文改進的遺傳算法具有較高的搜索效率，加快了算法的收斂速度，在一定程度上有利于防止算法陷入局部最優(yōu)。

表1 4種算法50次運行結果對比

4 結束語

針對在多約束條件下移動機器人在路徑規(guī)劃中的搜索效率低、收斂速度慢的缺點，本文提出了一種多約束條件下基于改進遺傳算法的智能移動機器人路徑規(guī)劃方法，綜合考慮了路徑長度、路徑平滑度和路徑困難度這3種因素的影響，改進初始種群的生成方式，并在此基礎上增加了刪除算子和平滑算子，同時結合了小生境法，在相同的環(huán)境中和文獻[10]、文獻[12]以及傳統(tǒng)遺傳算法相比較，本文提出的算法能夠在較短時間內找到最優(yōu)路徑且收斂速度較快，表明本文提出的算法具有一定的優(yōu)越性。本文改進的算法主要是在靜態(tài)環(huán)境中進行路徑規(guī)劃，并沒有考慮到有動態(tài)障礙物的情況，這是本文的不足和以后研究的重點。