王楓紅， 鄧志燕， 陳熾坤

（華南理工大學(xué)設(shè)計(jì)學(xué)院，廣東 廣州 510640）

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

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

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

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

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

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

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

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

2.1 判斷路徑

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

2.2 構(gòu)造路徑

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

圖1 障礙物的擴(kuò)展

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

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

圖3 改進(jìn)的地圖

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

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

2.3 最短路徑

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

1）路徑的個(gè)體編碼

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

圖5 基因編碼

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

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

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

圖6 初始路徑的生成

3）適應(yīng)度函數(shù)

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

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

4）改進(jìn)后遺傳算法的操作算子

（1）選擇算子

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

（2）交叉算子

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

（3）變異算子

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

（4）算法停止條件

利用多代之間的平均適應(yīng)度之差小于某值Δ來終止[12]，本實(shí)驗(yàn)中Δ=0.5。

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

3 算法的仿真分析

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

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

圖8 環(huán)境地圖

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

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

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

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

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

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

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

4 結(jié) 論

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

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

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

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

[4]周 巍, 李元宗. 基于改進(jìn)遺傳算法的煤礦探測(cè)機(jī)器人路徑規(guī)劃[J]. 太原理工大學(xué)學(xué)報(bào), 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]楊?yuàn)檴? 戴學(xué)豐, 唱江華. 實(shí)現(xiàn)機(jī)器人動(dòng)態(tài)路徑規(guī)劃的仿真系統(tǒng)[J]. 計(jì)算機(jī)工程與應(yīng)用, 2009, 45(32):237-243.

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