王楓紅， 鄧志燕， 陳熾坤

（華南理工大學設計學院，廣東 廣州 510640）

路徑規(guī)劃技術是排爆機器人技術領域中的一個重要研究內(nèi)容，要求機器人根據(jù)給予的指令及環(huán)境信息自主地決定路徑，避開障礙物實現(xiàn)排爆任務。為了讓排爆機器人在各種環(huán)境中能夠及時的排除爆炸物，真正實現(xiàn)無人干預的自主式，對其進行路徑規(guī)劃算法的研究是非常重要的。

本文主要針對排爆機器人的全局路徑規(guī)劃方法進行研究，根據(jù)給定的工作環(huán)境信息條件，離線規(guī)劃出符合某種給定規(guī)則的最優(yōu)路徑，即路徑最短、能量最省等。

1 傳統(tǒng)的路徑規(guī)劃算法和其存在的問題

路徑規(guī)劃技術經(jīng)過幾十年的發(fā)展，涌現(xiàn)出很多方法和思想。目前，比較成熟和被廣泛接受的方法有：人工勢場法、柵格法和遺傳算法[1]。其中遺傳算法因其編碼技術和遺傳操作比較簡單，優(yōu)化不受限制性條件的約束，故其應用最為廣泛[2]。

但傳統(tǒng)遺傳算法具有如下缺點：編碼不規(guī)范及編碼存在表示的不準確性；單一的遺傳算法編碼不能全面地優(yōu)化問題的約束表示出來[3]；傳統(tǒng)遺傳算法容易出現(xiàn)過早收斂；遺傳算法通常的效率比其他傳統(tǒng)的優(yōu)化方法低[4]。

本文選擇遺傳算法對排爆機器人進行路徑規(guī)劃，針對傳統(tǒng)遺傳算法的一些缺點，對傳統(tǒng)算法進行了一系列的改進，提出適宜的個體編碼等。

2 基于傳統(tǒng)遺傳算法的改進算法

本算法主要從：判斷路徑、構造路徑和最短路徑三方面進行了探討和研究，并對其進行模塊處理，從而大大簡化了排爆機器人的路徑規(guī)劃算法，便于算法維護，且能夠及時的找到任意形狀障礙物地圖的最優(yōu)路徑。

2.1 判斷路徑

在本文的機器人路徑規(guī)劃中，目標是在一幅障礙物分布已知的二維地圖上尋找一條最優(yōu)路徑使到達目標點距離盡可能短，同時盡可能少消耗機器人的能量。由于機器人本身有尺寸，先將障礙物的邊界向外擴張半個機器人最大直徑，將機器人當作一個質(zhì)點[5]。若擴展之后的障礙物相交了，則沒有有效路徑，將相交障礙物合并為一個障礙物，如圖1所示。采用凸多邊形創(chuàng)建多個靜止障礙物，就存在一個障礙物的有限集合S，S={S1, S2, S3,…Si}，其中：i為區(qū)域中的障礙物的個數(shù)。

2.2 構造路徑

判斷路徑之后，我們則需要尋找排爆機器人的真正可行路徑，也就是尋找機器人的可行區(qū)域?？梢晥D法是目前最常用的構造路徑方法。該方法雖然能保證在三維以下構形空間中求出最短安全路徑，但是不能推廣到更高維的空間中，且對于障礙物過多的時候，可視圖比較復雜（如圖2所示）時，采用該方法會導致可視圖中有些線條是多余的，這樣就減慢了路徑規(guī)劃的速度。為了提高路徑規(guī)劃速度，本文基于可視圖的基本原理[6]，對其進行一系列改進尋找機器人可行區(qū)域的，構造新穎的可視圖。

圖1 障礙物的擴展

圖2 利用可視圖法創(chuàng)建的地圖

首先生成常規(guī)的可視圖如圖2，對生成的連線按從短到長的順序進行排序，生成一個由線段組成的隊列。取第一條線段m，檢查是否和其后的線段相交。如果發(fā)現(xiàn)隊列中某一條線段n和線段m相交，那么從隊列中刪除n線段，以此類推，直到將所有隊列中與線段m相交的線段刪除。再取隊列中m的下一條線段，重復上述步驟，直到取完所有的線段。圖3所示為在圖2基礎上改進后所得到的新地圖。

圖3 改進的地圖

可見此時機器人的可行區(qū)域就是由圖3中的多邊形組成。本算法把這些多邊形當成單獨的一個個區(qū)域，在進行最短路徑搜索的時候針對的只是可行的多邊形（非障礙物）。在進行個體編碼時不采用常規(guī)二進制編碼，而是對可行區(qū)域多邊形邊上的點進行編碼，這樣大大簡化了遺傳算法的個體編碼，減少了路徑規(guī)劃的計算量。如圖4所示為使用該算法產(chǎn)生的一條路徑。

圖4 新地圖上產(chǎn)生的路徑

2.3 最短路徑

在找出機器人的可行區(qū)域之后，則需要在這個可行區(qū)域內(nèi)找出最優(yōu)路徑。本算法基于傳統(tǒng)遺傳算法的優(yōu)點，采用其進行最短路徑的求取。為了讓算法在很少的進化代數(shù)中就可以求出問題的最優(yōu)解，且避免傳統(tǒng)遺傳算法的“早熟收斂”和“收斂速度慢”的問題，本文對傳統(tǒng)遺傳算法進行了如下的改進：路徑個體編碼沒采用常規(guī)的二進制編碼，而是采用多線段編碼，大大簡化了編碼長度；結(jié)合排爆機器人的實際情況提出合適的適應度函數(shù)；對選擇算子和變異算子進行改進，擴大種群的范圍，避免快速進入局部最優(yōu)解[7]。具體計算步驟如下：

1）路徑的個體編碼

本算法使用多段線表示路徑，除了第1點和最后一點分別落在出發(fā)點和目標點上之外，其它路徑線段與線段之間的連接點都必須落在地圖連接線中點上，編碼如圖5所示。

圖5 基因編碼

基于上述編碼原理，圖4上的路徑則可表示為((Xs, Ys), (X17, Y17), (X12, Y12), (X5,Y5),(X3, Y3), (Xg, Xg))，其中每個點的角標根據(jù)生成連接線按長度排序之后的位置，(Xi, Yi)代表是中間點的坐標，(Xs, Ys)和(Xg, Yg)分別表示起點和終點。

2）初始種群的產(chǎn)生

本算法中初始種群就是在地圖的起點和終點確定，以及連接點生成之后，隨機的選取這些連接點組成路徑，如圖6所示，是隨機產(chǎn)生的路徑。

圖6 初始路徑的生成

3）適應度函數(shù)

每條路徑的優(yōu)劣評價通過適應度函數(shù)來給出[8]。對于排爆機器人適應度的評價是行走路徑的長短和能量消耗的大小，理想的狀況是最短路徑同時耗能最小。由于履帶式排爆機器人的能量消耗主要取決于拐彎角度的大小和拐彎次數(shù)等因素，所以最短路徑的情況下如果拐彎角度較大或拐彎次數(shù)較多都會增加能耗，其適應度不一定最好，所以最優(yōu)路徑是路徑長短和能耗的最佳配合值。綜上，排爆機器人的適應度函數(shù)確定如下：，其中：dist——對路

式中：xk——第k個連接點的x坐標。 (,, ,)gαn…μ是能耗函數(shù)，其能耗主要取決于拐彎半徑、連接點數(shù)量以及地面的摩擦系數(shù)等因素。

4）改進后遺傳算法的操作算子

（1）選擇算子

為了增加群體的多樣性，有效的避免早熟現(xiàn)象發(fā)生，本算法引入了相似度的概念。隨機生成種群后，在遺傳算法進行選擇運算前，對群體中每兩個個體逐位比較。如果兩個個體在相對應的位置上存在著相同的字符（基因），則將相同字符數(shù)量定義為相似度R。在實驗中設T=適應度平均值，在群體中取大于T的個體進行個體相似程度判斷。R小的則表示這兩個個體相似性差，當R≥L/2（L為個體的長度）時，即認為這兩個個體相似[12]。

（2）交叉算子

采用單點交叉[9]。首先確定一個交叉概率，對選擇后的子個體進行隨機配對，然后為每一對個體產(chǎn)生一個[0, 1]的隨機數(shù)，如果隨機數(shù)小于交叉概率，則對該對個體隨機指定的基因進行交叉操作。

（3）變異算子

變異是對群體中的元素（基因）加入隨機擾動，變異與有節(jié)制地交叉一起使用，是一種防止過度成熟而丟失重要遺傳信息的保險策略[10-11]。改進型變異算子優(yōu)先選取和障礙物相交的線段的端點進行變異，同時限制變異所得的路點坐標在障礙物之外。并且對適應度值大的采用較少的變異率，適應度值小的采用較大的變異率。

（4）算法停止條件

利用多代之間的平均適應度之差小于某值Δ來終止[12]，本實驗中Δ=0.5。

其算法的路徑規(guī)劃迭代步驟如圖7所示。

3 算法的仿真分析

為了分析算法的路徑規(guī)劃效果，本文構造兩種工作環(huán)境，它們所在的地圖尺寸一樣，不同的是障礙物的分布、密度以及形狀，如圖8所示，map1為障礙物稀疏地圖，map2為障礙物密集地圖。

圖7 基于傳統(tǒng)遺傳算法的改進算法流程圖

圖8 環(huán)境地圖

不同的種群大小，對收斂的代數(shù)和收斂的時間有很大的影響。群體的規(guī)模選取越大，獲取的的路徑越好，但收斂時間也越長；反之，群體規(guī)模越少，收斂時間越短，且有可能得不到最短路徑。本實驗對障礙稀疏分布的map1分別采用傳統(tǒng)遺傳算法和改進遺傳算法對不同的種群做6次規(guī)劃，得到的結(jié)果如表1所示。由此可見，相同種群大小的情況下，改進后的算法可較有效地縮短進化時間。

表1 不同種群下的進化結(jié)果比較

為了更明顯的比較傳統(tǒng)遺傳算法和改進遺傳算法在具體路徑規(guī)劃過程中的尋優(yōu)效果，本實驗取種群大小為30。比較map1中進化到20代的路徑，map2進化30代的路徑，仿真結(jié)果如圖9、圖10所示。

圖9 分別使用GA和NGA方法第20代產(chǎn)生的路徑

圖10 分別使用GA與CGA方法第30代產(chǎn)生的路徑

從圖9和圖10中可以很清晰看出，改進后的遺傳算法有更好的尋優(yōu)效果，優(yōu)選的路徑往往更加平緩，可使排爆機器人在距離相同的情況下能耗減少。

仿真實驗證明，本文提出的算法較傳統(tǒng)遺傳算法能更快的找到較優(yōu)路徑，且應用此算法能夠?qū)θ我庑螤畹亩噙呅芜M行路徑規(guī)劃，找出排爆機器人需求的路徑。

4 結(jié) 論

本文針對傳統(tǒng)遺傳算法進化速度慢、容易陷入局部最優(yōu)點等缺陷，提出了改進后新的路徑規(guī)劃算法。通過仿真實驗驗證了此算法的可行性，證實了該算法可以在一定程度上幫助排爆機器人更快的獲得質(zhì)量高的路徑，減少能量消耗。

[1]高 巍, 趙 海, 羅桂蘭, 等. 一種AAPF算法及其在多機器人路徑規(guī)劃中的應用[J]. 東北大學學報(自然科學版), 2009, (5): 644-647.

[2]唐 健, 史文中, 孟令奎. 基于遺傳算法的時相關動態(tài)車輛路徑規(guī)劃模型[J]. 武漢大學學報(信息科學版), 2008, (8): 875-878.

[3]李 擎, 馮金玲, 柳延領, 等. 自適應遺傳算法在移動機器人路徑規(guī)劃中的應用[J]. 北京科技大學學報,2008, (3): 316-323.

[4]周 巍, 李元宗. 基于改進遺傳算法的煤礦探測機器人路徑規(guī)劃[J]. 太原理工大學學報, 2010, (4):364-367.

[5]Elshamli A. Mobile robots path planning optimization in static and dynamicenvironments [D]. The Faculty of Graduate Studies of The University ofGuelph, 2004.

[6]Beilingham J, Richards A, How J P. Receding horizon control of autonomous aerialvehicles[C]//Proceedings of American Control Conference Anchorage, AK,2002: 3741-3746.

[7]Ayala R V, Pecrez G A, Montecillo P F J, et a1. Path planning using genetic algorithms for mini-robotic tasks[C]//Hague Netherlands: IEEE SMC'2004 Conference Proceedings, 2004: 3746-3750.

[8]Qi Yuanqing, Sun Debao, Li Ning, et a1. Path plan for mobile robot using the particle swarm optimization with mutation operator [C]//Shanghai: Proceedings of the Third-International Conference on Machine Laming and Cybernetics, 2004: 2473-2478.

[9]Hu Yanrong, Rang S X. A knowledge based genetic algorithm for path planning of a mobile robot [C]//Proceedings of the 2004 IEEE International Conference on Robotics Automation, New Orleans,April, 2004: 4350-4355.

[10]Li Wei, Cassandras C G. A cooperative receding horizon controller for multivehiele uncertain environments [J]. IEEE Transactions 012 Automatic Control, 2006, 51(2): 242-257.

[11]楊姍姍, 戴學豐, 唱江華. 實現(xiàn)機器人動態(tài)路徑規(guī)劃的仿真系統(tǒng)[J]. 計算機工程與應用, 2009, 45(32):237-243.

[12]鄧志燕, 陳熾坤. 基于改進遺傳算法的移動機器人路徑規(guī)劃研究[J]. 機械設計與制造, 2010, (7):147-149.