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

楊 平， 譚代倫

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

0 引言

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

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

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

1 測試場景的構建

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

在圖1中，移動機器人在一個水平方向和豎直方向都為20個單位長度的二維平面內行走，左下角坐標為(0,0)，右上角坐標為(20,20)，分別為機器人行走的起點和終點.場景(a)和(b)由單個障礙物構成，均位于平面的正中央處，(a)圖中圓的圓心為(10,10)，半徑為2；(b)圖中正方形邊長為4.場景(c)和(d)是由矩形、正方形和圓形三個規則圖形混合構成，其中圓的半徑仍為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

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

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

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

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

算法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，算法結束；否則繼續.

(3)根據頂點Ai,Ai+1坐標，計算AiAi+1直線一般方程的系數：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)根據向量坐標作向量叉乘，計算公式如下：

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，算法結束；否則繼續.

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

2.3 適應度函數

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

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

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

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

2.4 選擇策略

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

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

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

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

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

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

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

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

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

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

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

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

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

選擇組內最優個體進入子代種群；

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

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

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

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

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

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

2.5 交叉與變異策略

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

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

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

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

2.6 遺傳算法的流程圖

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

3 實驗結果與分析

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

3.1 算法求解結果

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

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

3.2 求解效果分析

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

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

續表1：

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

4 結束語

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