基于柵格法的礦難搜索機(jī)器人全局路徑規(guī)劃與局部避障_圖文

1、第42卷第11期中南大學(xué)學(xué)報(bào)(自然科學(xué)版 V ol.42No.11 2011年11月Journal of Central South University (Science and TechnologyNov. 2011基于柵格法的礦難搜索機(jī)器人全局路徑規(guī)劃與局部避障朱磊1, 2,樊繼壯1,趙杰1,吳曉光1,劉罡1(1. 哈爾濱工業(yè)大學(xué)機(jī)器人技術(shù)與系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室,黑龍江哈爾濱,150080;2. 中國科學(xué)院長春光學(xué)精密機(jī)械與物理研究所,吉林長春,130033摘要:針對礦難發(fā)生后井下環(huán)境的不確定性,提出一種以礦難前的GIS(Geographic information system地圖為基礎(chǔ)

2、建立環(huán)境柵格模型并結(jié)合改進(jìn)遺傳算法的礦難搜索機(jī)器人全局路徑規(guī)劃方法。效仿蟻群算法中的信息素提出基于位置信息負(fù)反饋的方法,并結(jié)合優(yōu)先權(quán)分組的思想,提出一種新的有效的種群初始化方法,同時(shí)將該種群初始化方法應(yīng)用到變異算子中,且依據(jù)最優(yōu)解的變化情況自適應(yīng)地調(diào)整交叉和變異的概率。與此同時(shí),針對環(huán)境信息的不同變化情況,結(jié)合全局路徑規(guī)劃結(jié)果對機(jī)器人進(jìn)行局部避障方法的研究。最后,通過仿真實(shí)驗(yàn)證明本方法能夠快速有效地在已知環(huán)境中得到機(jī)器人的最優(yōu)路徑,并且能夠在局部變化的環(huán)境中實(shí)現(xiàn)實(shí)時(shí)避障。關(guān)鍵詞:搜索機(jī)器人;柵格法;全局路徑規(guī)劃;遺傳算法;局部避障中圖分類號:TP242 文獻(xiàn)標(biāo)志碼:A 文章編號:1672720

3、7(201111342108Global path planning and local obstacle avoidance ofsearching robot in mine disasters based on grid methodZHU Lei1, 2, FAN Ji-zhuang1, ZHAO Jie1, WU Xiao-guang1, LIU Gang1(1. State Key Laboratory of Robotics and System, Harbin Institute of Technology, Harbin 150080, China;2. Changchun

4、Institute of Optics, Fine Mechanics and Physics, Chinese Academy of Sciences,Changchun 130033, ChinaAbstract: Aiming at the uncertainty of the environment in mine disasters, the gird model was built based on the GIS (geographic information system map acquired from the mine in advance, and a modified

5、 genetic algorithm was provided for global path planning. An efficient method for population initialization which adopted the position information negative feedback like the ant colony optimization and priority grouping was provided. Also the population initialization method was applied to the mutat

6、ion operator. The method self-adaptively adjusted the probabilities of crossover and mutation due to the change of the best resolution. According to the condition of the environment and combining with the global path planning result a local obstacle avoidance method was presented. Finally, the simul

7、ation results verify that the provided method can provide an optimal path in known environment effectively, and reallize the real time obstacle avoidance in locally changed environment.Key words: searching robot; grid method; global path planning; genetic algorithm; local obstacle avoidance隨著時(shí)代的發(fā)展,煤

8、炭作為一種重要能源,在國民經(jīng)濟(jì)發(fā)展中起著至關(guān)重要的作用。然而,許多煤礦為了獲得暴利,不顧安全生產(chǎn),使得近些年來礦難事故頻發(fā)。與此同時(shí),我國礦難搜救水平的落后也使得發(fā)生災(zāi)難后傷亡人數(shù)無法得到最大限度的減少1。由于礦難發(fā)生的突然性以及破壞性,救援人員很難及時(shí)收稿日期:20101122;修回日期:20110220基金項(xiàng)目:國家高技術(shù)研究發(fā)展計(jì)劃(“863”計(jì)劃項(xiàng)目(2007AA041501;哈爾濱市科技創(chuàng)新人才研究專項(xiàng)項(xiàng)目(2008RFQXG051通信作者:朱磊(1982,男,黑龍江哈爾濱人,博士研究生,從事礦難搜索機(jī)器人定位與導(dǎo)航研究;電話:139*;E-mail: rayjew中南大學(xué)學(xué)報(bào)(自然

9、科學(xué)版 第42卷3422得到足夠多的井下環(huán)境信息,而確認(rèn)井下環(huán)境的安全是救援人員下井搜救的必要條件。研究表明:當(dāng)幸存者被困在礦井內(nèi)超過48 h后其生還的概率將會(huì)變得很低2。因此,在井下情況未知甚至危險(xiǎn)的情況下,礦難搜救機(jī)器人成了減少傷亡、降低損失的有效手段,對于提高我國礦難搜救水平將起到關(guān)鍵作用。礦難搜索機(jī)器人作為一種移動(dòng)機(jī)器人,其路徑規(guī)劃能力決定了其智能水平的高低。移動(dòng)機(jī)器人的路徑規(guī)劃的主要任務(wù)是在具有靜態(tài)或者動(dòng)態(tài)障礙物的環(huán)境中,依據(jù)一定約束條件,尋找到一條沒有碰撞的路徑。同時(shí),這些路徑有時(shí)候要求滿足一些優(yōu)化參數(shù),例如最短距離、最小時(shí)間和最低能耗等。針對環(huán)境信息的已知程度,可以將移動(dòng)機(jī)器人的

10、路徑規(guī)劃分為全局路徑規(guī)劃與局部避障。全局路徑規(guī)劃方法依據(jù)已知環(huán)境信息的情況,首先需要對環(huán)境建模,然后在環(huán)境模型中搜索出一條最優(yōu)的路徑。因此,目前根據(jù)環(huán)境建模形式可以將路徑規(guī)劃方法分為可視圖法3,C空間法4和柵格法5等。依據(jù)搜索的方法的不同又可以分為A*法6、Dijkstra方法7和快速搜索隨機(jī)樹算法8等。局部避障方法往往需要處理的是未知或者部分未知的環(huán)境。較為常用的有人工勢場法9、基于滾動(dòng)窗口的方法10和基于再勵(lì)學(xué)習(xí)的方法11等。近年來,隨著人工智能的發(fā)展,現(xiàn)代啟發(fā)優(yōu)化方法也被逐漸引入到路徑規(guī)劃中。Glasius等12提出了一種基于Hopfield網(wǎng)絡(luò)的實(shí)時(shí)、動(dòng)態(tài)避障神經(jīng)網(wǎng)絡(luò)模型,能夠避免局部

11、最小點(diǎn),但是很難適應(yīng)高速的動(dòng)態(tài)環(huán)境。Xue等13采用等距分布粒子群并結(jié)合危險(xiǎn)度地圖的方法,獲得全局最優(yōu)路徑。Huang等14提出了使用模糊邏輯行為對移動(dòng)機(jī)器人在未知環(huán)境中進(jìn)行實(shí)時(shí)路徑規(guī)劃。Zhang等15采用目標(biāo)吸引函數(shù)對基于蟻群算法的機(jī)器人路徑優(yōu)化進(jìn)行了改進(jìn),從而使其能夠順利到達(dá)目標(biāo)點(diǎn)。Ghorbani等16設(shè)計(jì)了一種在非結(jié)構(gòu)環(huán)境下基于知識遺傳算法的路徑規(guī)劃方法。利用柵格法表示地圖十分簡單且操作方便,已經(jīng)成為地圖表示方法中的一種常見方法。遺傳算法作為一種優(yōu)化方法,由于其魯棒穩(wěn)定性,也已經(jīng)成為機(jī)器人路徑規(guī)劃問題的主要研究方向之一。因此,國內(nèi)外的學(xué)者提出了一些基于柵格法的改進(jìn)遺傳算法用于機(jī)器人路

12、徑規(guī)劃1718,并且在煤礦與礦難搜索機(jī)器人中也有應(yīng)用1920。但是遺傳算法較大的計(jì)算量、較慢的收斂速度以及由于早熟而陷入局部最優(yōu)都是其主要問題。為了克服以上的缺點(diǎn),借鑒蟻群算法信息素的思想,一些學(xué)者提出了基于信息正反饋的改進(jìn)遺傳算法2122。本文作者提出了一種基于柵格模型的負(fù)反饋遺傳算法對機(jī)器人進(jìn)行全局路徑規(guī)劃。采用一種新的種群初始化方法生成初始路徑,從而保證了初始生成路徑的多樣性與可行性。對變異算子進(jìn)行了改進(jìn),并且自適應(yīng)地調(diào)整交叉和變異的概率,從而避免了早熟現(xiàn)象。然后結(jié)合全局路徑規(guī)劃方法提出了一種基于柵格變化的局部避障方法。1環(huán)境模型的建立機(jī)器人的路徑規(guī)劃中,基于真實(shí)環(huán)境的地圖建模是十分重要

13、的。眾所周知,礦難發(fā)生后,井下的確切環(huán)境信息是很難直接獲得的,但是并不是所有的信息都是未知的。為此做出如下定義,稱在礦難中未被破壞的環(huán)境區(qū)域?yàn)椤鞍肟芍绤^(qū)域”。對于這樣的區(qū)域其附近的環(huán)境信息是可以不用通過傳感器就能確定的。由此可以做出這樣的假設(shè),將井下的所有環(huán)境區(qū)域均認(rèn)定為“半可知道區(qū)域”。這些“半可知道區(qū)域”的信息可以從煤礦井下的GIS地圖所獲知,從而可以以此為基礎(chǔ)對機(jī)器人進(jìn)行全局路徑規(guī)劃,得到一個(gè)從井口到事故發(fā)生地點(diǎn)的一條最優(yōu)的運(yùn)動(dòng)路徑,這樣當(dāng)機(jī)器人進(jìn)入井下后就可以照此路徑前進(jìn)。當(dāng)機(jī)器人進(jìn)入到破壞過的區(qū)域,則采取局部路徑規(guī)劃方法。通過局部避障方法與全局路徑規(guī)劃方法的結(jié)合,機(jī)器人能夠順利地到

14、達(dá)事故發(fā)生地?？紤]到用柵格方法表示二維的環(huán)境信息十分簡便有效,應(yīng)用也很廣,因此,本文采用柵格法對環(huán)境進(jìn)行建模。圖1所示為一個(gè)基于柵格法建立的一個(gè)1010柵格環(huán)境地圖?？瞻讝鸥癖硎咀杂煽臻g也就是機(jī)器人能夠自由通過的地方,而陰影柵格表示的是障礙物空間,一般是在障礙物的實(shí)際邊界的基礎(chǔ)上加上一個(gè)通常和移動(dòng)機(jī)器人的大小有關(guān)的安全距離,并且將其補(bǔ)為長方形。這樣機(jī)器人就可以被看作環(huán)境中的一個(gè)點(diǎn),可以不用考慮其尺寸大小23。由于算法將會(huì)對柵格被選中的次數(shù)進(jìn)行計(jì)數(shù),因此,在初始時(shí)將柵格矩陣中的陰影柵格設(shè)置值為1,空白柵格設(shè)置值為0。柵格的表達(dá)和編碼方式對于遺傳算法也是一個(gè)關(guān)鍵因素,簡單方便的編碼方式,能夠使得算

15、法效率更高。為此,采用了序號法和二維直角坐標(biāo)2種方法相結(jié)合的方式來表示柵格模型。利用序號法存儲算法所產(chǎn)生的路徑,既很容易操作,又能夠節(jié)省存儲空間。這樣如圖1所示的一個(gè)從1到100的無碰撞路徑可以表示為(1, 2, 3, 14, 25, 36, 47, 58, 69, 80, 90, 100。當(dāng)需要評價(jià)一個(gè)路徑的優(yōu)劣的時(shí)候,又通過式(1把序號轉(zhuǎn)換為二維直角坐標(biāo)24。這樣可以很容易地得到2個(gè)節(jié)點(diǎn)之間的相對位置以及判斷路徑的可行性。第11期 朱磊,等:基于柵格法的礦難搜索機(jī)器人全局路徑規(guī)劃與局部避障 3423code code mod(/int(/1x x X c m Y c m =+(1式中:mo

16、d 為取余數(shù);int 為取整數(shù);m x 為一行中的柵格個(gè)數(shù)。 圖1 基于柵格法的環(huán)境模型Fig.1 Environment model based on grid method2 全局路徑規(guī)劃方法依據(jù)本文建立的環(huán)境柵格模型,可以離線地獲得機(jī)器人的最優(yōu)路徑規(guī)劃。為此,本文提出了一種改進(jìn)的遺傳算法應(yīng)用于機(jī)器人的全局路徑規(guī)劃。 2.1 種群初始化 大多數(shù)的遺傳算法都是隨機(jī)地產(chǎn)生初始種群。但是在路徑規(guī)劃中這樣的操作會(huì)導(dǎo)致產(chǎn)生許多不可行的路徑。盡管一些不可行的路徑可以通過相應(yīng)的遺傳算子變成可行的路徑,但是也會(huì)使得適應(yīng)度函數(shù)需要增加一些判斷條件,從而使得函數(shù)變得復(fù)雜。另外還耗費(fèi)了很多的計(jì)算時(shí)間在一些不可行

17、的路徑上,既浪費(fèi)了存儲空間,又降低了收斂速度。甚至有的不可行的路徑會(huì)使得遺傳算子失去意義。例如,2個(gè)不可行路徑的交叉幾乎很難得到可行的路徑,同樣變異操作也不容易使不可行路徑變?yōu)榭尚?。由以上的分析可以看?如果選擇更為有效地種群初始化方法將會(huì)使得遺傳算法更加有效。因此,本文提出了一種基于蟻群算法信息素思想的位置信息負(fù)反饋并結(jié)合優(yōu)先權(quán)分組思想的種群初始化方法,從而保證了所有生成路徑的可行性以及多樣性。具體步驟如下所示:Step 1:依據(jù)柵格模型,首先獲得當(dāng)前節(jié)點(diǎn)A 的坐標(biāo)。如果是路徑的第1個(gè)節(jié)點(diǎn)則將初始節(jié)點(diǎn)S 的坐標(biāo)代入節(jié)點(diǎn)A ;Step 2:基于當(dāng)前節(jié)點(diǎn)A 與終止節(jié)點(diǎn)F 的坐標(biāo)值,可以得到從節(jié)點(diǎn)

18、A 到節(jié)點(diǎn)F 的最短路徑所對應(yīng)的方向,然后可以依據(jù)這個(gè)方向?qū)⒐?jié)點(diǎn)A 的8個(gè)鄰居節(jié)點(diǎn)分為3個(gè)具有優(yōu)先級的組;Step 3:從第1組到第3組優(yōu)先級逐級遞減。優(yōu)先在第1組中選取下一個(gè)路徑上的節(jié)點(diǎn),如果第1組中沒有合適的節(jié)點(diǎn),則在第2組中選取,以此類推。如果所有鄰近節(jié)點(diǎn)都不可用,則將起始節(jié)點(diǎn)S 的坐標(biāo)再次代入節(jié)點(diǎn)A 并轉(zhuǎn)到Step 1。由于在Step 4中將會(huì)在一個(gè)計(jì)數(shù)器中記錄一個(gè)節(jié)點(diǎn)被選中的次數(shù)。因此,在每一組中選擇臨近節(jié)點(diǎn)時(shí),會(huì)參考節(jié)點(diǎn)的計(jì)數(shù)信息。其中,節(jié)點(diǎn)計(jì)數(shù)值最低的節(jié)點(diǎn)被選中的概率最大,與計(jì)數(shù)信息正好相反;Step 4:如果節(jié)點(diǎn)B 滿足條件,把節(jié)點(diǎn)B 加入到路徑中,然后將節(jié)點(diǎn)B 的坐標(biāo)值代入節(jié)

19、點(diǎn)A 。同時(shí)對節(jié)點(diǎn)B 對應(yīng)的計(jì)數(shù)器加1;Step 5:如果節(jié)點(diǎn)B 和節(jié)點(diǎn)F 重合,一次循環(huán)結(jié)束,產(chǎn)生了一個(gè)無碰撞的路徑。如果沒有重合則轉(zhuǎn)到Step 1繼續(xù)產(chǎn)生下一個(gè)節(jié)點(diǎn);Step 6:將路徑保存到初始種群中,并對種群個(gè)體個(gè)數(shù)計(jì)數(shù)器加1,如果產(chǎn)生的初始個(gè)體數(shù)目達(dá)到了種群數(shù),結(jié)束初始化,得到了初始種群。如果沒有轉(zhuǎn)到Step 1繼續(xù)生成。現(xiàn)在舉例說明如何選擇下一個(gè)節(jié)點(diǎn)。圖2所示為相鄰節(jié)點(diǎn)的信息。假定當(dāng)前節(jié)點(diǎn)為圖2(a中的點(diǎn)0。如果最短的路徑方向是垂直或者水平的,比如說是從節(jié)點(diǎn)0到節(jié)點(diǎn)5的方向,第1級分組包括節(jié)點(diǎn)3,5和8,第2級分組包括節(jié)點(diǎn)2和7,第3級分組包括節(jié)點(diǎn)1,4和6;如果方向是斜的也就是與

20、節(jié)點(diǎn)0的4個(gè)(a 節(jié)點(diǎn)序號;(b 節(jié)點(diǎn)計(jì)數(shù)值圖2 相鄰節(jié)點(diǎn)的信息 Fig.2 Information of neighbor nodes中南大學(xué)學(xué)報(bào)(自然科學(xué)版 第42卷 342445角的鄰近點(diǎn)相同或者相似,例如方向?yàn)楣?jié)點(diǎn)0到節(jié)點(diǎn)8,第1級分組就包括節(jié)點(diǎn)5,7和8,第2級分組就包括節(jié)點(diǎn)3和6,第3級分組就包括節(jié)點(diǎn)1,2和4。如果節(jié)點(diǎn)0的鄰近點(diǎn)的計(jì)數(shù)信息如圖2(b所示,并且假定最優(yōu)方向是節(jié)點(diǎn)0到節(jié)點(diǎn)8,那么,節(jié)點(diǎn)7由于具有最低的計(jì)數(shù)信息,所以最有可能被選中。 2.2 適應(yīng)度函數(shù)設(shè)計(jì)適應(yīng)度函數(shù)用于評價(jià)路徑的質(zhì)量,決定了算法收斂的速度以及計(jì)算效率。因?yàn)椴挥脤β窂娇尚行赃M(jìn)行判斷,只要考慮能量與時(shí)間的消

21、耗即可。因此,將路徑的長度和拐點(diǎn)的個(gè)數(shù)作為優(yōu)化指標(biāo),適應(yīng)度函數(shù)表達(dá)式如下fitness 1n211(,2ni i i f d k k n =+ (2式中:,(1i i k k d 為2個(gè)相鄰節(jié)點(diǎn)之間的路徑長度;n 為路徑中所有節(jié)點(diǎn)的個(gè)數(shù);n n 為路徑中拐點(diǎn)的總個(gè)數(shù)。 2.3 選擇算子采用比例選擇算子從而保證優(yōu)良的個(gè)體可以存活在種群中。具體方法就是依據(jù)父輩的適應(yīng)度大小決定子代中該個(gè)體的個(gè)數(shù):popsizequantity popsize 1ii p jj f q p f =(3 式中:f i 為個(gè)體i 的適應(yīng)度;p popsize 為種群大小。 2.4 交叉算子算法采用單點(diǎn)交叉算子。首先隨機(jī)的

22、選擇2個(gè)個(gè)體,然后選擇2個(gè)個(gè)體中除了開始節(jié)點(diǎn)和終止節(jié)點(diǎn)的一個(gè)公共節(jié)點(diǎn)作為交叉節(jié)點(diǎn),如果沒有公共節(jié)點(diǎn)則不作任何操作。例如,一個(gè)個(gè)體為(1, 2, 3, 14, 25, 36, 47, 58, 69, 80, 90, 100,另一個(gè)個(gè)體為(1, 12, 23, 34, 45, 56, 67, 68, 69, 79, 89, 90, 100。可以看到兩者有兩個(gè)共同節(jié)點(diǎn)69和90。因此,隨機(jī)選擇節(jié)點(diǎn)69作為交叉節(jié)點(diǎn),交換2個(gè)個(gè)體在該節(jié)點(diǎn)之后的所有節(jié)點(diǎn)。這樣交叉操作后的2個(gè)個(gè)體變?yōu)?1, 2, 3, 14, 25, 36, 47, 58, 69, 79,89, 90, 100和(1, 12, 23, 3

23、4, 45, 56, 67, 68, 69, 80, 90, 100。 2.5 變異算子變異操作使得種群變得多樣,能夠解決早熟問題,對于遺傳算法十分重要。許多學(xué)者的研究中都是采用隨機(jī)的變異操作,但是有時(shí)對于進(jìn)化沒有好處。因此,對傳統(tǒng)的變異算子進(jìn)行了改進(jìn)。首先,仍然隨機(jī)的選擇一個(gè)個(gè)體的拐點(diǎn)進(jìn)行變異,然后,選擇這個(gè)拐點(diǎn)的鄰近節(jié)點(diǎn)來代替拐點(diǎn),鄰近節(jié)點(diǎn)的選取不是等概率的,具有最低計(jì)數(shù)值的鄰近節(jié)點(diǎn)被選中的概率最高,隨后利用種群初始化中的方法生成一個(gè)連接變異拐點(diǎn)前一拐點(diǎn)、后一拐點(diǎn)和變異后的節(jié)點(diǎn)的路徑。 2.6 刪除算子圖3所示為刪除算子和修正算子示意圖。通常,如果一個(gè)路徑的2個(gè)相交的線段的夾角是銳角或者直

24、角,這條路徑往往不是最短的路徑。因此,需要?jiǎng)h除算子來去掉一些不必要的節(jié)點(diǎn)改善路徑。刪除算子依據(jù)的原理是三角形的兩邊之和大于第3邊。如圖3(a所示,節(jié)點(diǎn)3和7使得135和678分別為直角和45銳角,這樣通過刪除算子就可以將這2個(gè)節(jié)點(diǎn)去掉,從而生成如圖3(b所示的新的路徑(1, 2, 4, 5, 6, 8。改變后的路徑長度很明顯短于改變前的。 2.7 修正算子對于一些路徑來說通過改變一些拐點(diǎn)的位置,可以減少轉(zhuǎn)彎的次數(shù),而并不影響路徑總長度,這樣使得路徑得到了修正,能夠獲得更優(yōu)的路徑。如圖3(b中的節(jié)點(diǎn)5如果被圖3(c中節(jié)點(diǎn)9所替代,那么,生成的新路徑將會(huì)更加合理,有利于機(jī)器人的控制。 (a 原始路

25、徑;(b 刪除算子操作;(c 修正算子操作圖3 刪除算子和修正算子示意圖 Fig.3 Crossover and correcting operator第11期朱磊,等:基于柵格法的礦難搜索機(jī)器人全局路徑規(guī)劃與局部避障34252.8交叉和變異概率的選擇交叉和變異概率的大小很大程度上影響著遺傳算法。交叉算子可以交換2個(gè)路徑的信息,提供新的搜索節(jié)點(diǎn),但是對于多樣性沒有任何幫助。而變異算子可以使得種群多樣化。因此,首先應(yīng)該選用一個(gè)較高的交叉概率從而使得算法能夠產(chǎn)生優(yōu)良的個(gè)體,一個(gè)較低的變異概率使得進(jìn)化更加有效。為了避免早熟,當(dāng)最優(yōu)個(gè)體三代沒有改變的時(shí)候,則通過一定步數(shù)減少交叉概率增加變異概率到各自設(shè)

26、定的極限值。例如,初始的交叉概率和變異概率分別為0.5和0.05,極限值分別為0.4和0.25。這樣如果步長值分別為0.25和0.5的話,經(jīng)過4步之后概率都到了極限值而最優(yōu)個(gè)體依然沒有變化的話,則輸出最優(yōu)個(gè)體,算法結(jié)束。2.9精英保留策略為了能夠使得最優(yōu)個(gè)體不會(huì)在下一代中消失,本文采用了精英保留策略。在算法中用第n+1代的最優(yōu)個(gè)體與記錄下來的前n代的最優(yōu)個(gè)體比較。如果后者較優(yōu),則用前n代的最優(yōu)個(gè)體代替第n+1代的最差個(gè)體;否則,不需要對種群進(jìn)行操作,只是將第n+1代的最優(yōu)個(gè)體記錄下來即可。這樣可以使得算法全局收斂25。2.10方法分析通過上述可以看出:由于本文所生成的初始路徑都是可行的,而且經(jīng)

27、過各種遺傳算子操作后依然是可行的路徑,從而省去了許多對于路徑是否可行的不必要判斷,節(jié)省了計(jì)算量。采用了負(fù)反饋的機(jī)制可以使得生成的路徑多樣化,而且覆蓋的柵格節(jié)點(diǎn)更多,更加有利于加速方法的收斂。通過自適應(yīng)地調(diào)整交叉和變異概率,避免了早熟問題?？梢姳疚乃岱椒ㄊ且环N有效可行的方法。3局部避障方法如果在機(jī)器人行進(jìn)的過程中檢測到周圍的環(huán)境信息能夠和GIS地圖中的保持一致,機(jī)器人只要跟蹤事先規(guī)劃的全局路徑即可;如果環(huán)境信息與GIS地圖上的不相符時(shí),機(jī)器人就需要啟動(dòng)局部避障方法。本文將針對2種環(huán)境的變化情況對機(jī)器人做出相應(yīng)的局部避障策略。3.1障礙柵格轉(zhuǎn)化為自由柵格的規(guī)劃當(dāng)障礙物柵格轉(zhuǎn)化為自由柵格時(shí),會(huì)使得

28、機(jī)器人的移動(dòng)空間變得更大,不會(huì)對機(jī)器人的行進(jìn)路線造成任何干擾,因此,不需對機(jī)器人的行走路徑進(jìn)行調(diào)整機(jī)器人依然能夠到達(dá)目標(biāo)節(jié)點(diǎn),只要在地圖中將原來的障礙柵格轉(zhuǎn)換為自由柵格即可。這時(shí)候的局部避障策略就是繼續(xù)跟蹤全局路徑規(guī)劃。但是有時(shí)由于障礙物柵格的消失會(huì)使得機(jī)器人的全局最優(yōu)路徑可能變得不是最優(yōu)的,因此,當(dāng)機(jī)器人到達(dá)目標(biāo)點(diǎn)后,將對最優(yōu)路徑進(jìn)行一次刪除算子和修正算子操作,從而可以使得返回的路徑是最優(yōu)的。例如,如果圖3(c中所示的障礙柵格變?yōu)樽杂蓶鸥?可以看出節(jié)點(diǎn)1和節(jié)點(diǎn)6直接相連后的路徑會(huì)比現(xiàn)在圖3(c中所示的路徑性能更佳。3.2自由柵格轉(zhuǎn)化為障礙柵格的規(guī)劃如果增加的障礙物柵格對規(guī)劃的路徑?jīng)]有產(chǎn)生任何

29、影響,只需對地圖做出相應(yīng)修改即可。如果障礙物柵格在機(jī)器人的行走路徑上或者阻擋了機(jī)器人的行走路徑,機(jī)器人就需要啟動(dòng)局部避障策略。這時(shí)就需要選擇該障礙物柵格節(jié)點(diǎn)的臨近柵格節(jié)點(diǎn)并且不在路徑上的柵格節(jié)點(diǎn)作為新的路徑上的柵格節(jié)點(diǎn),然后利用和變異算子類似地操作生成一個(gè)連續(xù)路徑供機(jī)器人繼續(xù)跟蹤。選擇時(shí)根據(jù)優(yōu)先級分組的思想來進(jìn)行,但是優(yōu)先選擇使得障礙物柵格節(jié)點(diǎn)的上一路徑節(jié)點(diǎn)與選擇的障礙物柵格的臨近柵格節(jié)點(diǎn)的連線方向與該障礙物柵格所在的線段的下一個(gè)線段的方向相同的柵格節(jié)點(diǎn)。圖4所示為柵格節(jié)點(diǎn)的選擇過程示意圖。由于線段14的方向與線段23的方向一致,因此,選擇節(jié)點(diǎn)4來代替障礙物柵格節(jié)點(diǎn)(圖4。 (a 原始路徑;(

30、b 修改后路徑圖4柵格節(jié)點(diǎn)的選擇過程示意圖Fig.4 Progress of choosing neighbor nodes4仿真結(jié)果分析4.1全局路徑規(guī)劃仿真結(jié)果針對一些路徑規(guī)劃算法往往會(huì)在凹障礙物中陷入局部最優(yōu),從而無法進(jìn)行規(guī)劃的問題,本文在U型障礙物的環(huán)境中進(jìn)行了仿真。仿真環(huán)境是一個(gè)1010的柵格模型,其中陰影部分是一個(gè)U型障礙物,起始節(jié)點(diǎn)是S,終止節(jié)點(diǎn)是F,仿真結(jié)果如圖5所示。結(jié)果顯示機(jī)器人能夠在如此復(fù)雜的環(huán)境中規(guī)劃出一條從3426 中南大學(xué)學(xué)報(bào)(自然科學(xué)版 第 42 卷 初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最優(yōu)無碰路徑，算法的魯棒性 和尋優(yōu)能力都很強(qiáng)。 為了證實(shí)所提算法的有效性，和文獻(xiàn)18中提出 的

31、方法進(jìn)行了仿真比較，采用了和文獻(xiàn)18一樣障礙 物分布的 1010 柵格模型進(jìn)行了仿真，如圖 6 所示。 仿真參數(shù)設(shè)置如下，種群規(guī)模為 10，交叉概率 變異概率 PM 的變化范 PC 的變化范圍是從 0.65 到 0.3， 最大迭代次數(shù)為 50。 規(guī)劃好的全 圍是從 0.01 到 0.08， 局最優(yōu)路徑如圖 6 中的實(shí)線所示。路徑的長度為 13.899 5，雖然與文獻(xiàn)18中的路徑長度一致，但是中 間拐點(diǎn)的個(gè)數(shù)只有 2 個(gè)，規(guī)劃后的路徑效果更佳。而 可見本 且在 0.25 s 內(nèi)經(jīng)過 13 代就可以收斂到最優(yōu)解。 文提出的算法能夠在較少的代數(shù)內(nèi)收斂到最優(yōu)解。 圖7 隨機(jī)生成環(huán)境仿真結(jié)果 Fig.7

32、 Result in random environment 由于本文所研究的方法是用于礦難搜索機(jī)器人的 路徑規(guī)劃中。為此，按照礦井巷道的 GIS 地圖得到了 如圖 8 所示的柵格地圖，并應(yīng)用本文所提方法得到了 一條從開始節(jié)點(diǎn)到終止節(jié)點(diǎn)的最優(yōu)機(jī)器人路徑。 圖5 U 型障礙物環(huán)境中的仿真結(jié)果 Fig.5 Simulation result in U-shape obstacle 圖8 煤礦 GIS 地圖環(huán)境仿真結(jié)果 Fig.8 Result in environment based on mine GIS 4.2 圖6 全局路徑規(guī)劃仿真結(jié)果對比 Fig.6 Comparisons in globa

33、l path planning 局部避障仿真結(jié)果 圖 9 所示為基于 GIS 地圖所得的柵格環(huán)境，依據(jù) 本文方法所得到的機(jī)器人的全局最優(yōu)路徑如圖中實(shí)線 其中有 所示。 而圖 10 所示為發(fā)生變化后的柵格環(huán)境， 三部分是由自由柵格變成了障礙柵格，有一部分是由 障礙柵格變成了自由柵格。根據(jù)本文所提的局部避障 策略得到的機(jī)器人最終行進(jìn)路徑如圖 10 中實(shí)線所示， 由此可見： 本文提出的 回程路徑如圖 10 中虛線所示。 局部避障算法能夠依據(jù)環(huán)境變化情況生成相應(yīng)的最優(yōu) 為了證明方法的一般性，在隨機(jī)生成的一個(gè)較大 較復(fù)雜的環(huán)境中利用方法對路徑進(jìn)行了規(guī)劃。仿真環(huán) 境和結(jié)果如圖 7 所示，可以看出機(jī)器人能夠

34、在這種錯(cuò) 綜復(fù)雜的環(huán)境下依然能夠找到最優(yōu)路徑，具有較強(qiáng)的 魯棒性。 第 11 期 朱磊，等：基于柵格法的礦難搜索機(jī)器人全局路徑規(guī)劃與局部避障 3427 路徑，使得機(jī)器人依然能夠到達(dá)目標(biāo)節(jié)點(diǎn)。最后又通 過環(huán)境信息的更新對回程路徑進(jìn)行了優(yōu)化。 方法； 以路徑長度與拐點(diǎn)個(gè)數(shù)作為適應(yīng)度函數(shù)的參數(shù)， 使得算法的指標(biāo)更佳優(yōu)良；通過自適應(yīng)地調(diào)節(jié)交叉算 子與變異算子的概率從而使得算法保持多樣性的同時(shí) 又能提高進(jìn)化速度。 (3 針對不同的障礙形式與柵格變化情況對機(jī)器 人進(jìn)行了全局路徑規(guī)劃仿真與局部避障仿真，結(jié)果證 明了方法的有效性與魯棒性。 參考文獻(xiàn)： 1 王忠民, 劉軍, 竇智, 等. 礦難救援機(jī)器人的研究應(yīng)

35、用現(xiàn)狀與 開發(fā)J. 煤礦機(jī)械, 2007, 28(11: 68. WANG Zhong-min, LIU Jun, DOU Zhi, et al. Research and application status and development of search and rescue robot for mine disasterJ. Coal Mine Machinery, 2007, 28(11: 68. 2 Casper J, Micire M, Murphy R R. Issues in intelligent robots for search and rescueC/Proceed

36、ings of SPIE 2000. Orlando: SPIE, 2000: 292302. 3 Alexopoulos C, Griffin P M. Path planning for a mobile robotJ. IEEE Transaction on Systems, Man, and Cybernetics, 1992, 22(2: 318322. 4 Lozano-peres T. Spatial planning: A configuration space approachJ. IEEE Transaction on Computers, 1983, 32(2: 1081

37、20. 5 Kambhampati S, Davis L S. Multiresolution path planning for mobile robotsJ. IEEE Journal of Robotics and Automation, 1986, 2(3: 135145. 6 Fan K C, Lui P C. Solving find path problem in mapped environments using modified A* algorithmJ. IEEE Transaction on System, Man, and Cybernetics, 1994, 24(

38、9: 13901396. 7 Noto M, Sato H. A method for the shortest path search by extended dijkstra algorithmC/Proceedings of 2000 IEEE International Conference on Systems, Man, and Cybernetics. Nashville: IEEE, 2000: 23162320. 8 Bruce J, Veloso M. Real-time randomized path planning for robot navigationC/Proc

39、eedings for the IEEE /RSJ International Conference on Intelligent Robots and System. Lausanne: IEEE, 2002: 23832388. 9 Hwnag Y K, Ahuja N. A potential field approach to path planningJ. IEEE Transactions on Robotics and Automation, 1992, 8(1: 2332. 10 張純剛, 席裕庚. 機(jī)器人滾動(dòng)路徑規(guī)劃的算法與仿真研究J. 高技術(shù)通訊, 2003, 13(4:

40、5357. ZHANG Chun-gang, XI Yu-geng. Algorithm and simulation of robot rolling path planningJ. High Technology Letters, 2003, 13(4: 5357. 11 Yung N H C, Ye C. An intelligent mobile vehicle navigator based on fuzzy logic and reinforcement learningJ. IEEE Transactions on Systems, Man, and Cybernetics, 1

41、999, 29(2: 圖9 初始全局路徑規(guī)劃結(jié)果 Fig.9 Global path planning result at beginning 圖 10 Fig.10 環(huán)境變化后的局部避障仿真結(jié)果 environment Local obstacle avoidance result after changes in 5 結(jié)論 (1 提出了一種改進(jìn)的遺傳算法用于礦難搜索 機(jī)器人的全局路徑規(guī)劃，并且以全局路徑規(guī)劃的結(jié)果 為基礎(chǔ)針對柵格的變化情況，設(shè)計(jì)了一種基于柵格變 化的局部避障方法。 (2 基于位置信息負(fù)反饋和優(yōu)先級分組的思想改 進(jìn)了種群初始化方法，使得生成的路徑都是可行的， 節(jié)省了算法總體運(yùn)

42、行時(shí)間。采用了 5 種遺傳算子，并 在變異節(jié)點(diǎn)的替代節(jié)點(diǎn)的選擇中采用了種群初始化的 3428 314321. 中南大學(xué)學(xué)報(bào)(自然科學(xué)版 第 42 卷 Taiyuan University of Technology, 2010, 41(4: 364367. 20 張小艷, 周筱媛, 魏娟. 煤礦救援機(jī)器人全局路徑規(guī)劃J. 西 安科技大學(xué)學(xué)報(bào), 2008, 28(2: 323326, 335. ZHANG Xiao-yan, ZHOU Xiao-yuan, WEI Juan. Global path planning for coalmine rescue robotsJ. Journal of

43、 Xian University of Science and Technology, 2008, 28(2: 323326, 335. 21 LEI Lin, WANG Hou-jun, WU Qin-song. Improved genetic algorithms based path planning of mobile robot under dynamic unknown environmentC/Proceedings of the 2006 IEEE International Conference on Mechatronics and Automation. Luoyang

44、: IEEE, 2006: 17281732. 22 司應(yīng)濤, 朱慶保, 國海濤. 基于正反饋遺傳算法的機(jī)器人全 局路徑規(guī)劃J. 計(jì)算機(jī)工程與應(yīng)用, 2008, 44(1: 5456, 62. SI Ying-tao, ZHU Qing-bao, GUO Hai-tao. Global robot path planning based on positive feedback GAJ. Computer Engineering and Applications, 2008, 44(1: 5456, 62. 23 LI Qing, Zhang W, Yin Y, et al. An impro

45、ved genetic algorithm of optimum path planning for mobile robotsC/Proceedings of the Sixth International Conference on Intelligent Systems Design and Applications. Jinan: IEEE, 2006: 637642. 24 陳曦, 譚冠政, 江斌. 基于免疫遺傳算法的移動(dòng)機(jī)器人實(shí)時(shí) 最優(yōu)路徑規(guī)劃J. 中南大學(xué)學(xué)報(bào): 自然科學(xué)版, 2008, 39(3: 577583. CHEN Xi, TAN Guan-zheng, JIANG B

46、in. Real-time optimal path planning for mobile robots based on immune genetic algorithmJ. Journal of Central South University: Science and Technology, 2008, 39(3: 577583. 25 Rudolph G. Convergence analysis of canonical genetic algorithmsJ. IEEE Transaction on Neural Networks, 1994, 5(1: 96101. 12 Glasius R, Komoda A, Gielen S. A biologically inspired neural net for trajectory formation and obstacle avoidanceJ. Biological Cybernetics,