機器人路徑規(guī)劃的遺傳算法求解策略分析

楊 平， 譚代倫

(1.西華師范大學數(shù)學與信息學院，四川南充 637009;2.西華師范大學計算方法及應用軟件研究所，四川南充 637009)

0 引言

隨著智能技術的發(fā)展，移動機器人已被廣泛應用到軍事、工業(yè)、商業(yè)及家庭生活等各個領域[1].路徑規(guī)劃是移動機器人工作的基礎，根據(jù)作業(yè)環(huán)境的不同，移動機器人的路徑規(guī)劃可分為兩類.一類是基于機器人自身安裝的環(huán)境信息傳感器對未知環(huán)境信息實時獲取的局部路徑規(guī)劃，也稱為動態(tài)路徑規(guī)劃.另一類是基于全局地理信息的路徑規(guī)劃，也被稱為靜態(tài)路徑規(guī)劃[2].靜態(tài)路徑規(guī)劃通常是指機器人的作業(yè)環(huán)境中分布著一些障礙物，在給定的起點和目標點之間為機器人規(guī)劃一條安全、高效的免碰撞路徑[3].通常滿足避障條件的路徑不止一條，在具體問題中需要根據(jù)不同的目標，例如路徑長度最短、用時最少、能量消耗最小等，尋找出一條最優(yōu)路徑[4].

針對機器人路徑規(guī)劃，國內外學者提出了很多方法，常見有可視圖法[5-7]、柵格法[8-9]、A*及其改進算法[10-11]、蟻群算法[12-14]、遺傳算法[15-17]等.其中，模擬生物進化過程的遺傳算法(Genetic Algorithm, GA)具有靈活性好、魯棒性強和不易陷入局部最優(yōu)等優(yōu)點.已有文獻研究表明，遺傳算法在機器人避障路徑規(guī)劃問題中求解中取得了較好的效果.不少學者做了一些改進性的研究工作，并取得了一定的研究成果.如文獻[18]提出的基于分組和精英策略的遺傳算法，加快了算法的收斂速度.文獻[19]對遺傳算法的交叉、變異算子進行了改進，提高了算法的進化能力.

已有文獻資料主要研究遺傳算法的改進以提高收斂速度和求解精度，但較少涉及遺傳算法的不同求解策略對求解效果的影響.為此，本文通過構造四種不同障礙物的測試場景，分別采取遺傳算法的輪盤賭策略、君主策略、錦標賽策略進行多次求解，進而分析求解效果的差異.

1 測試場景的構建

一般地，在移動機器人作業(yè)平面內的障礙物可以被近似為規(guī)則幾何圖形和不規(guī)則幾何圖形.規(guī)則幾何圖形主要包括三角形、矩形、圓和其他多邊形，不規(guī)則幾何圖形主要是指障礙物的邊沿輪廓復雜多變，難以用單一的規(guī)則幾何圖形表示.為方便設計避障算法，測試不同求解策略的性能，本文主要構造由單個幾何圖形或它們簡單混合的測試場景，如圖1.

在圖1中，移動機器人在一個水平方向和豎直方向都為20個單位長度的二維平面內行走，左下角坐標為(0,0)，右上角坐標為(20,20)，分別為機器人行走的起點和終點.場景(a)和(b)由單個障礙物構成，均位于平面的正中央處，(a)圖中圓的圓心為(10,10)，半徑為2；(b)圖中正方形邊長為4.場景(c)和(d)是由矩形、正方形和圓形三個規(guī)則圖形混合構成，其中圓的半徑仍為2，矩形的長為5、寬為2，正方形的邊長為4.在實驗中忽略機器人自身的大小，將其視作一個移動的質點.

圖1 不同類型障礙物的測試場景Fig.1 Test scenarios for different obstacle types

2 遺傳算法的設計

2.1 個體編碼與初始種群

圖2 個體染色體及其基因編碼Fig.2 Individual chromosome of path and its gene coding

遺傳算法的個體染色體編碼影響著遺傳算子的操作，進而影響到算法的收斂.在機器人作業(yè)平面內，移動路徑節(jié)點由平面內的若干個坐標點構成.為了提高計算精度，增強遺傳算法的避障和穿越能力，本文采用二維實數(shù)對編碼，即取每一個節(jié)點的二維實數(shù)坐標(xi,yi)為一個基因編碼，設路徑節(jié)點數(shù)為n，全部節(jié)點構成一條染色體(路徑)編碼，即一個個體的編碼，如下圖2所示.

路徑節(jié)點數(shù)n即為個體基因編碼長度，由于機器人作業(yè)平面不大、場景中障礙物較少，因此n的取值在5～10內可獲得較好的求解效果.另設個體的種群規(guī)模為M，節(jié)點的二維實數(shù)坐標構成本問題的雙種群，分別記為X=[X1;X2;…;XM],Y=[Y1;Y2;…;YM].

2.2 與障礙物相交的判斷算法

路徑規(guī)劃的首要目標就是要使機器人能夠避開障礙物，獲得一條不與障礙物發(fā)生碰撞的安全路徑.下面首先給出路徑與圓形和矩形障礙物是否相交的判斷算法.

算法1：與圓形障礙物相交的判斷算法.

輸入：圓形障礙物的圓心坐標和半徑：C(xC,xC),r；

路徑上第i條線段的兩個端點坐標：Ai(xi,yi),Ai+1(xi+1,yi+1).

輸出：線段是否能避開障礙物的判斷變量ri.

(1)計算線段CAi,CAi+1的長度|CAi|，|CAi+1|，令li=min{|CAi|，|CAi+1|}

(2)若lir,則Ai,Ai+1至少有一個點在圓形障礙物內部，即不能避開，則置ri=0，算法結束；否則繼續(xù).

(3)根據(jù)頂點Ai,Ai+1坐標，計算AiAi+1直線一般方程的系數(shù)：ai,bi,ci.

(4)計算圓心C到直線AiAi+1的距離，記為di，計算公式為：

(5)計算圓心C到直線AiAi+1的垂足坐標，記為D(xdi,ydi)，計算公式為：

(6)若dir且xi(xi+1)

算法2：與矩形障礙物相交的判斷算法

輸入：矩形四個頂點的坐標：B1(x1,y1),B2(x2,y2),B3(x3,y3),B4(x4,y4)

路徑上第i條線段的兩個端點坐標：Ai(xi,yi),Ai+1(xi+1,yi+1).

輸出：線段是否能避開障礙物的判斷變量ri.

(1)置ri=1,令k=1,取矩形的頂點Bk(xk,yk),Bk+1(xk+1,yk+1)

(2)構造向量AiAi+1,BkBk+1,AiBk,AiBk+1,BkAi+1,BkAi

(3)根據(jù)向量坐標作向量叉乘，計算公式如下：

p1=AiAi+1×AiBk,q1=AiAi+1×AiBk+1

p2=BkBk+1×BkAi,q2=BkBk+1×BkAi+1

(4)若p1q10且p2q20，則線段AiAi+1與矩形的邊BkBk+1相交，即不能避開障礙物，則置ri=0，算法結束；否則繼續(xù).

(5)令k=k+1，若k=4則算法結束，否則轉到步驟(1).

2.3 適應度函數(shù)

適應度函數(shù)是用來度量種群中的每個個體是否能夠達到或者接近最優(yōu)解的優(yōu)良程度，適應度高的個體遺傳到下一代的概率更大.在機器人路徑規(guī)劃問題中，其最優(yōu)目標是使行走路徑盡量短，需要滿足的約束是不與場景內任何障礙物發(fā)生碰撞.為降低算法計算量，減少對種群中非法個體的篩選和過濾，本文采用罰函數(shù)方法，即若一條路徑穿過障礙物，則該條路徑的長度被懲罰為0.

對任意一條路徑A1→A2→A3→…→AN，設第i個節(jié)點Ai的坐標為(xi,yi)，路徑總長度分量記為f1，則有

根據(jù)3.2節(jié)中與障礙物相交的判斷算法，定義如下0-1型變量：

為了便于算法的遺傳操作，需使短的可行路徑獲得更大的適應度值，可用一個較大數(shù)C減去原有路徑長度，將最小值問題轉換為最大值問題.因此，最終的適應度函數(shù)為：

2.4 選擇策略

選擇操作的任務是按照一定的規(guī)則挑選出與種群規(guī)模相同的適應度較優(yōu)的個體.個體的適應度越大，被選入新種群的可能性越高，這是對自然選擇中優(yōu)勝劣汰的模擬.不同的選擇策略對算法的求解效果有著重要的影響.[20]本文選取常用的三種策略：輪盤賭策略、錦標賽策略、君主策略，為每種策略設計了具體的步驟.在個體編碼方案中，本問題是雙種群的，因此下述策略對兩個種群均要同步操作.

2.4.1 輪盤賭策略 輪盤賭策略是最早被提出的一種個體選擇策略，它根據(jù)每個個體的適應度來計算該個體在子代中出現(xiàn)的概率，并根據(jù)此概率隨機選擇個體構成子代種群.輪盤賭策略的原理是適應度值越大的個體被選擇的概率越大.因此，在求解最大化問題中可直接采用適應度值來進行選擇.但對于最小化問題，必須先將問題的適應度函數(shù)進行轉換為最大化問題.輪盤賭策略的基本步驟為：

(2)計算每個個體的入選概率Pj=fj/F；

(3)計算所有個體的累積概率，構造一個輪盤；

(4)輪盤選擇：生成一個區(qū)間[0,1]內的隨機數(shù)，若隨機數(shù)小于等于個體j的累積概率但大于等于個體j-1的累積概率，則個體j進入下一代群體；

(5)重復操作(4)，直至產生與父輩同樣規(guī)模的種群.

2.4.2 錦標賽策略 錦標賽策略模擬了體育比賽中的分組聯(lián)賽機制，基本思想是每次從種群中取出一定數(shù)量的個體構成一個小組，然后選擇該組中適應度最高的個體進入子代種群.這類似于體育聯(lián)賽機制中，只有每個分組的勝出者才能參加下一階段的比賽.在遺傳算法中模擬體育比賽的錦標賽機制時，為增強隨機性、提高全局尋優(yōu)能力，一般采用有放回式的隨機采樣機制，具體操作步驟如下：

(1)確定錦標賽的分組大小r(稱為r元錦標賽).

這里，分組規(guī)模的大小也會影響到錦標賽策略的效果，一些文獻已經(jīng)對此有所研究.文獻[20]通過實驗分析，建議錦標賽策略的分組規(guī)模大小取種群規(guī)模的60%～80%.本文在后續(xù)實驗仿真中取值為r=種群規(guī)模×70%.

(2)從種群中隨機抽取r個個體(每個個體被選中的概率相同)組成一個聯(lián)賽小組；

(3)在聯(lián)賽小組內，根據(jù)每個個體的適應度值，根據(jù)準則

對最大化問題：pk=max{p1,p2,…,pr}

對最小化問題：pk=min{p1,p2,…,pr}

選擇組內最優(yōu)個體進入子代種群；

(4)重復操作步驟(2)和(3)，直到子代種群達到預定的種群規(guī)模.

由于步驟(2)和(3)每次都是從原來的種群中選擇r個個體，因此，在一輪中被選出來構成一個聯(lián)賽小組的個體，無論是否被選入子代種群中，在下一輪操作中仍然有可能被再次選出來，但是它在新的聯(lián)賽小組中，并不一定還是最優(yōu)個體.這樣，每個較優(yōu)的個體被選中的機會更高，子代種群的平均適應度也更高，對尋找問題的全局最優(yōu)解更為有利.

2.4.3 君主策略 君主選擇策略是對自然種群中動物首領、蟻后等個體繁衍特點的模擬.這些個體通常擁有最好的基因，在繁衍過程中可與多個個體進行結合.在君主選擇策略中，適應度最高的個體即為“君主”，它會多次參與到遺傳過程中.君主策略具體操作如下：

(1)選取種群中適應度值最大的個體，記為“君主”；

(2)把父代種群的剩余個體按照適應度從大到小排列；

(3)奇數(shù)號個體用君主替換，偶數(shù)號個體不變，生成下一代種群.

2.5 交叉與變異策略

選擇操作只能將初始種群中的路徑保留復制到新種群中，并沒有新個體產生.為保持種群的多樣性，能真正實現(xiàn)全局尋優(yōu)，還必須借助交叉和變異操作.本文的機器人路徑規(guī)劃問題中，起點和終點是固定的，因此這兩個點不參與交叉和變異.

2.5.1 交叉策略 交叉操作作用于種群中某對個體之間，是對生物遺傳過程中基因重組的模擬.通過交叉，種群會產生新的基因組合，從而可能獲得比父輩更優(yōu)秀的個體，達到進化的目的.本文采用單點交叉策略，基于一定的交叉概率(交叉概率通常取值為0.4～0.9)進行交叉.交叉操作作用于種群中某些相鄰個體間，首先采用隨機產生的方式確定交叉點位置，然后交換兩個個體在該基因點后的基因片段，得到新的基因組合方式.用交叉后的新個體替換原種群中的個體，從而得到新的種群.

圖3 遺傳算法的流程圖Fig.3 Flow chart of genetic algorithm

2.5.2 變異策略 變異操作的目的是使種群中產生新的基因型，從而擴大尋優(yōu)范圍避免陷入局部最優(yōu).本文采用單點變異策略，首先基于一定的變異概率(變異概率取值較小，通常取值為0.001～0.4)確定需要變異的個體，然后隨機選取染色體中的一個基因位置作為變異點，最后用隨機產生的新的基因替換變異點原來的基因.用發(fā)生變異后的個體替換原本種群中的個體，使種群獲得新的基因型.

2.6 遺傳算法的流程圖

綜合上述工作，在遺傳算法的標準流程圖基礎上，本文的遺傳算法流程圖見圖3.

3 實驗結果與分析

本文程序在MATLAB 2018a中編寫，遺傳算法的初始參數(shù)設置為：種群規(guī)模200、迭代次數(shù)300、路徑節(jié)點(基因數(shù)目)為5、交叉概率0.7、變異概率0.06.

3.1 算法求解結果

本文共構造四個基本測試場景，經(jīng)上述遺傳算法求解，均能成功避開障礙物，獲得最優(yōu)路徑.限于篇幅，下面給出場景(c)在三種不同選擇策略下的求解結果，如圖4.在圖4(a)中，所獲得的最優(yōu)路徑長度為29.095 8，圖4(b)獲得的最優(yōu)路徑長度為29.984 5，圖4(c)獲得的最優(yōu)路徑長度為29.369 5.

圖4 三種策略下圖1(c)場景的最優(yōu)路徑Fig.4 The three strategies are shown in Figure 1 (c)

3.2 求解效果分析

只是一次或幾次實驗，不能很好地體現(xiàn)遺傳算法的不同選擇策略對有障礙物的路徑規(guī)劃問題的求解性能.為此，在保持上述算法參數(shù)不變的情況下，對圖1的四種場景，分別使用三種選擇策略各自獨立運行100次，經(jīng)統(tǒng)計記錄，獲得實驗結果如下表1.

表1 三種選擇策略對避障路徑規(guī)劃問題的求解性能統(tǒng)計Tab.1 Performance statistics of three selection strategies for obstacle avoidance path planning

續(xù)表1：

由表1可知，錦標賽選擇策略求得的平均值和標準差全部小于另外兩種選擇策略，即錦標賽策略規(guī)劃出的路徑平均值更短，且具有更好的穩(wěn)定性.輪盤賭策略和君主策略相比較，君主策略的平均值均小于輪盤賭策略，而且君主策略的標準差也是全部小于輪盤賭.因此，在使用遺傳算法求解有障礙物的路徑規(guī)劃問題時，錦標賽選擇具有比其他常見策略更好的求解性能，其次是君主策略，然后是輪盤賭策略.

4 結束語

本文針對有障礙物的機器人路徑規(guī)劃問題，構造了四個基本測試場景，分別選擇遺傳算法的輪盤賭策略、錦標賽策略和君主策略進行求解，通過運行100次的統(tǒng)計分析來對三種策略的求解性能進行比較，結果表明錦標賽策略優(yōu)于另外兩種策略.因此在使用遺傳算法求解機器人路徑規(guī)劃問題時，采用錦標賽選擇策略不僅可以避免轉換適應度值的問題，而且比其他兩種常見策略具有更好的求解性能.