朱磊 ，樊繼壯，趙杰，吳曉光，劉罡

(1. 哈爾濱工業(yè)大學 機器人技術(shù)與系統(tǒng)國家重點實驗室，黑龍江 哈爾濱，150080；2. 中國科學院 長春光學精密機械與物理研究所，吉林 長春，130033)

隨著時代的發(fā)展，煤炭作為一種重要能源，在國民經(jīng)濟發(fā)展中起著至關(guān)重要的作用。然而，許多煤礦為了獲得暴利，不顧安全生產(chǎn)，使得近些年來礦難事故頻發(fā)。與此同時，我國礦難搜救水平的落后也使得發(fā)生災難后傷亡人數(shù)無法得到最大限度的減少[1]。由于礦難發(fā)生的突然性以及破壞性，救援人員很難及時得到足夠多的井下環(huán)境信息，而確認井下環(huán)境的安全是救援人員下井搜救的必要條件。研究表明：當幸存者被困在礦井內(nèi)超過48 h后其生還的概率將會變得很低[2]。因此，在井下情況未知甚至危險的情況下，礦難搜救機器人成了減少傷亡、降低損失的有效手段，對于提高我國礦難搜救水平將起到關(guān)鍵作用。

礦難搜索機器人作為一種移動機器人，其路徑規(guī)劃能力決定了其智能水平的高低。移動機器人的路徑規(guī)劃的主要任務是在具有靜態(tài)或者動態(tài)障礙物的環(huán)境中，依據(jù)一定約束條件，尋找到一條沒有碰撞的路徑。同時，這些路徑有時候要求滿足一些優(yōu)化參數(shù)，例如最短距離、最小時間和最低能耗等。針對環(huán)境信息的已知程度，可以將移動機器人的路徑規(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]和快速搜索隨機樹算法[8]等。局部避障方法往往需要處理的是未知或者部分未知的環(huán)境。較為常用的有人工勢場法[9]、基于滾動窗口的方法[10]和基于再勵學習的方法[11]等。

近年來，隨著人工智能的發(fā)展，現(xiàn)代啟發(fā)優(yōu)化方法也被逐漸引入到路徑規(guī)劃中。Glasius等[12]提出了一種基于Hopfield網(wǎng)絡的實時、動態(tài)避障神經(jīng)網(wǎng)絡模型，能夠避免局部最小點，但是很難適應高速的動態(tài)環(huán)境。Xue等[13]采用等距分布粒子群并結(jié)合危險度地圖的方法，獲得全局最優(yōu)路徑。Huang等[14]提出了使用模糊邏輯行為對移動機器人在未知環(huán)境中進行實時路徑規(guī)劃。Zhang等[15]采用目標吸引函數(shù)對基于蟻群算法的機器人路徑優(yōu)化進行了改進，從而使其能夠順利到達目標點。Ghorbani等[16]設計了一種在非結(jié)構(gòu)環(huán)境下基于知識遺傳算法的路徑規(guī)劃方法。

利用柵格法表示地圖十分簡單且操作方便，已經(jīng)成為地圖表示方法中的一種常見方法。遺傳算法作為一種優(yōu)化方法，由于其魯棒穩(wěn)定性，也已經(jīng)成為機器人路徑規(guī)劃問題的主要研究方向之一。因此，國內(nèi)外的學者提出了一些基于柵格法的改進遺傳算法用于機器人路徑規(guī)劃[17-18]，并且在煤礦與礦難搜索機器人中也有應用[19-20]。但是遺傳算法較大的計算量、較慢的收斂速度以及由于早熟而陷入局部最優(yōu)都是其主要問題。為了克服以上的缺點，借鑒蟻群算法信息素的思想，一些學者提出了基于信息正反饋的改進遺傳算法[21-22]。本文作者提出了一種基于柵格模型的負反饋遺傳算法對機器人進行全局路徑規(guī)劃。采用一種新的種群初始化方法生成初始路徑，從而保證了初始生成路徑的多樣性與可行性。對變異算子進行了改進，并且自適應地調(diào)整交叉和變異的概率，從而避免了早熟現(xiàn)象。然后結(jié)合全局路徑規(guī)劃方法提出了一種基于柵格變化的局部避障方法。

1 環(huán)境模型的建立

機器人的路徑規(guī)劃中，基于真實環(huán)境的地圖建模是十分重要的。眾所周知，礦難發(fā)生后，井下的確切環(huán)境信息是很難直接獲得的，但是并不是所有的信息都是未知的。為此做出如下定義，稱在礦難中未被破壞的環(huán)境區(qū)域為“半可知道區(qū)域”。對于這樣的區(qū)域其附近的環(huán)境信息是可以不用通過傳感器就能確定的。由此可以做出這樣的假設，將井下的所有環(huán)境區(qū)域均認定為“半可知道區(qū)域”。這些“半可知道區(qū)域”的信息可以從煤礦井下的GIS地圖所獲知，從而可以以此為基礎對機器人進行全局路徑規(guī)劃，得到一個從井口到事故發(fā)生地點的一條最優(yōu)的運動路徑，這樣當機器人進入井下后就可以照此路徑前進。當機器人進入到破壞過的區(qū)域，則采取局部路徑規(guī)劃方法。通過局部避障方法與全局路徑規(guī)劃方法的結(jié)合，機器人能夠順利地到達事故發(fā)生地。考慮到用柵格方法表示二維的環(huán)境信息十分簡便有效，應用也很廣，因此，本文采用柵格法對環(huán)境進行建模。圖1所示為一個基于柵格法建立的一個10×10柵格環(huán)境地圖?？瞻讝鸥癖硎咀杂煽臻g也就是機器人能夠自由通過的地方，而陰影柵格表示的是障礙物空間，一般是在障礙物的實際邊界的基礎上加上一個通常和移動機器人的大小有關(guān)的安全距離，并且將其補為長方形。這樣機器人就可以被看作環(huán)境中的一個點，可以不用考慮其尺寸大小[23]。由于算法將會對柵格被選中的次數(shù)進行計數(shù)，因此，在初始時將柵格矩陣中的陰影柵格設置值為-1，空白柵格設置值為0。

柵格的表達和編碼方式對于遺傳算法也是一個關(guān)鍵因素，簡單方便的編碼方式，能夠使得算法效率更高。為此，采用了序號法和二維直角坐標2種方法相結(jié)合的方式來表示柵格模型。利用序號法存儲算法所產(chǎn)生的路徑，既很容易操作，又能夠節(jié)省存儲空間。這樣如圖1所示的一個從1到100的無碰撞路徑可以表示為 (1,2,3,14,25,36,47,58,69,80,90,100)。當需要評價一個路徑的優(yōu)劣的時候，又通過式(1)把序號轉(zhuǎn)換為二維直角坐標[24]。這樣可以很容易地得到2個節(jié)點之間的相對位置以及判斷路徑的可行性。

式中：mod為取余數(shù)；int為取整數(shù)；mx為一行中的柵格個數(shù)。

圖1 基于柵格法的環(huán)境模型Fig.1 Environment model based on grid method

2 全局路徑規(guī)劃方法

依據(jù)本文建立的環(huán)境柵格模型，可以離線地獲得機器人的最優(yōu)路徑規(guī)劃。為此，本文提出了一種改進的遺傳算法應用于機器人的全局路徑規(guī)劃。

2.1 種群初始化

大多數(shù)的遺傳算法都是隨機地產(chǎn)生初始種群。但是在路徑規(guī)劃中這樣的操作會導致產(chǎn)生許多不可行的路徑。盡管一些不可行的路徑可以通過相應的遺傳算子變成可行的路徑，但是也會使得適應度函數(shù)需要增加一些判斷條件，從而使得函數(shù)變得復雜。另外還耗費了很多的計算時間在一些不可行的路徑上，既浪費了存儲空間，又降低了收斂速度。甚至有的不可行的路徑會使得遺傳算子失去意義。例如，2個不可行路徑的交叉幾乎很難得到可行的路徑，同樣變異操作也不容易使不可行路徑變?yōu)榭尚?。由以上的分析可以看出：如果選擇更為有效地種群初始化方法將會使得遺傳算法更加有效。因此，本文提出了一種基于蟻群算法信息素思想的位置信息負反饋并結(jié)合優(yōu)先權(quán)分組思想的種群初始化方法，從而保證了所有生成路徑的可行性以及多樣性。具體步驟如下所示：

Step 1：依據(jù)柵格模型，首先獲得當前節(jié)點A的坐標。如果是路徑的第1個節(jié)點則將初始節(jié)點S的坐標代入節(jié)點A；

Step 2：基于當前節(jié)點A與終止節(jié)點F的坐標值，可以得到從節(jié)點A到節(jié)點F的最短路徑所對應的方向，然后可以依據(jù)這個方向?qū)⒐?jié)點A的8個鄰居節(jié)點分為3個具有優(yōu)先級的組；

Step 3：從第1組到第3組優(yōu)先級逐級遞減。優(yōu)先在第1組中選取下一個路徑上的節(jié)點,如果第1組中沒有合適的節(jié)點，則在第2組中選取，以此類推。如果所有鄰近節(jié)點都不可用，則將起始節(jié)點S的坐標再次代入節(jié)點A并轉(zhuǎn)到Step 1。由于在Step 4中將會在一個計數(shù)器中記錄一個節(jié)點被選中的次數(shù)。因此，在每一組中選擇臨近節(jié)點時，會參考節(jié)點的計數(shù)信息。其中，節(jié)點計數(shù)值最低的節(jié)點被選中的概率最大，與計數(shù)信息正好相反；

Step 4：如果節(jié)點B滿足條件，把節(jié)點B加入到路徑中，然后將節(jié)點B的坐標值代入節(jié)點A。同時對節(jié)點B對應的計數(shù)器加1；

Step 5：如果節(jié)點B和節(jié)點F重合，一次循環(huán)結(jié)束，產(chǎn)生了一個無碰撞的路徑。如果沒有重合則轉(zhuǎn)到Step 1繼續(xù)產(chǎn)生下一個節(jié)點；

Step 6：將路徑保存到初始種群中，并對種群個體個數(shù)計數(shù)器加 1，如果產(chǎn)生的初始個體數(shù)目達到了種群數(shù)，結(jié)束初始化，得到了初始種群。如果沒有轉(zhuǎn)到Step 1繼續(xù)生成。

圖2 相鄰節(jié)點的信息Fig.2 Information of neighbor nodes

現(xiàn)在舉例說明如何選擇下一個節(jié)點。圖2所示為相鄰節(jié)點的信息。假定當前節(jié)點為圖2(a)中的點 0。如果最短的路徑方向是垂直或者水平的，比如說是從節(jié)點0到節(jié)點5的方向，第 1級分組包括節(jié)點3，5和8，第2級分組包括節(jié)點2和7，第3級分組包括節(jié)點1，4和6；如果方向是斜的也就是與節(jié)點0的4個45°角的鄰近點相同或者相似，例如方向為節(jié)點0到節(jié)點8，第1級分組就包括節(jié)點5，7和8，第2級分組就包括節(jié)點3和6，第3級分組就包括節(jié)點1，2和4。如果節(jié)點0的鄰近點的計數(shù)信息如圖2(b)所示，并且假定最優(yōu)方向是節(jié)點0到節(jié)點8，那么，節(jié)點7由于具有最低的計數(shù)信息，所以最有可能被選中。

2.2 適應度函數(shù)設計

適應度函數(shù)用于評價路徑的質(zhì)量，決定了算法收斂的速度以及計算效率。因為不用對路徑可行性進行判斷，只要考慮能量與時間的消耗即可。因此，將路徑的長度和拐點的個數(shù)作為優(yōu)化指標，適應度函數(shù)表達式如下

式中：d(ki,ki-1)為2個相鄰節(jié)點之間的路徑長度；n為路徑中所有節(jié)點的個數(shù)；nn為路徑中拐點的總個數(shù)。

2.3 選擇算子

采用比例選擇算子從而保證優(yōu)良的個體可以存活在種群中。具體方法就是依據(jù)父輩的適應度大小決定子代中該個體的個數(shù)：

式中：fi為個體i的適應度；ppopsize為種群大小。

2.4 交叉算子

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

2.5 變異算子

變異操作使得種群變得多樣，能夠解決早熟問題，對于遺傳算法十分重要。許多學者的研究中都是采用隨機的變異操作，但是有時對于進化沒有好處。因此，對傳統(tǒng)的變異算子進行了改進。首先，仍然隨機的選擇一個個體的拐點進行變異，然后，選擇這個拐點的鄰近節(jié)點來代替拐點，鄰近節(jié)點的選取不是等概率的，具有最低計數(shù)值的鄰近節(jié)點被選中的概率最高，隨后利用種群初始化中的方法生成一個連接變異拐點前一拐點、后一拐點和變異后的節(jié)點的路徑。

2.6 刪除算子

圖3所示為刪除算子和修正算子示意圖。通常，如果一個路徑的2個相交的線段的夾角是銳角或者直角，這條路徑往往不是最短的路徑。因此，需要刪除算子來去掉一些不必要的節(jié)點改善路徑。刪除算子依據(jù)的原理是三角形的兩邊之和大于第3邊。如圖3(a)所示，節(jié)點3和7使得∠135和∠678分別為直角和45°銳角，這樣通過刪除算子就可以將這2個節(jié)點去掉，從而生成如圖3(b)所示的新的路徑(1,2,4,5,6,8)。改變后的路徑長度很明顯短于改變前的。

2.7 修正算子

對于一些路徑來說通過改變一些拐點的位置，可以減少轉(zhuǎn)彎的次數(shù)，而并不影響路徑總長度，這樣使得路徑得到了修正，能夠獲得更優(yōu)的路徑。如圖3(b)中的節(jié)點5如果被圖3(c)中節(jié)點9所替代，那么，生成的新路徑將會更加合理，有利于機器人的控制。

圖3 刪除算子和修正算子示意圖Fig.3 Crossover and correcting operator

2.8 交叉和變異概率的選擇

交叉和變異概率的大小很大程度上影響著遺傳算法。交叉算子可以交換2個路徑的信息，提供新的搜索節(jié)點，但是對于多樣性沒有任何幫助。而變異算子可以使得種群多樣化。因此，首先應該選用一個較高的交叉概率從而使得算法能夠產(chǎn)生優(yōu)良的個體，一個較低的變異概率使得進化更加有效。為了避免早熟，當最優(yōu)個體三代沒有改變的時候，則通過一定步數(shù)減少交叉概率增加變異概率到各自設定的極限值。例如，初始的交叉概率和變異概率分別為0.5和0.05，極限值分別為0.4和0.25。這樣如果步長值分別為0.25和0.5的話，經(jīng)過4步之后概率都到了極限值而最優(yōu)個體依然沒有變化的話，則輸出最優(yōu)個體，算法結(jié)束。

2.9 精英保留策略

為了能夠使得最優(yōu)個體不會在下一代中消失，本文采用了精英保留策略。在算法中用第n+1代的最優(yōu)個體與記錄下來的前n代的最優(yōu)個體比較。如果后者較優(yōu)，則用前n代的最優(yōu)個體代替第n+1代的最差個體；否則，不需要對種群進行操作，只是將第n+1代的最優(yōu)個體記錄下來即可。這樣可以使得算法全局收斂[25]。

2.10 方法分析

通過上述可以看出：由于本文所生成的初始路徑都是可行的，而且經(jīng)過各種遺傳算子操作后依然是可行的路徑，從而省去了許多對于路徑是否可行的不必要判斷，節(jié)省了計算量。采用了負反饋的機制可以使得生成的路徑多樣化，而且覆蓋的柵格節(jié)點更多，更加有利于加速方法的收斂。通過自適應地調(diào)整交叉和變異概率，避免了早熟問題?？梢姳疚乃岱椒ㄊ且环N有效可行的方法。

3 局部避障方法

如果在機器人行進的過程中檢測到周圍的環(huán)境信息能夠和GIS地圖中的保持一致，機器人只要跟蹤事先規(guī)劃的全局路徑即可；如果環(huán)境信息與GIS地圖上的不相符時，機器人就需要啟動局部避障方法。本文將針對2種環(huán)境的變化情況對機器人做出相應的局部避障策略。

3.1 障礙柵格轉(zhuǎn)化為自由柵格的規(guī)劃

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

3.2 自由柵格轉(zhuǎn)化為障礙柵格的規(guī)劃

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

圖4 柵格節(jié)點的選擇過程示意圖Fig.4 Progress of choosing neighbor nodes

4 仿真結(jié)果分析

4.1 全局路徑規(guī)劃仿真結(jié)果

針對一些路徑規(guī)劃算法往往會在凹障礙物中陷入局部最優(yōu)，從而無法進行規(guī)劃的問題，本文在U型障礙物的環(huán)境中進行了仿真。仿真環(huán)境是一個 10×10的柵格模型，其中陰影部分是一個U型障礙物，起始節(jié)點是S，終止節(jié)點是F，仿真結(jié)果如圖5所示。結(jié)果顯示機器人能夠在如此復雜的環(huán)境中規(guī)劃出一條從初始節(jié)點到目標節(jié)點的最優(yōu)無碰路徑，算法的魯棒性和尋優(yōu)能力都很強。

為了證實所提算法的有效性，和文獻[18]中提出的方法進行了仿真比較，采用了和文獻[18]一樣障礙物分布的10×10柵格模型進行了仿真，如圖6所示。

仿真參數(shù)設置如下，種群規(guī)模為 10，交叉概率PC的變化范圍是從0.65到0.3，變異概率PM的變化范圍是從0.01到0.08，最大迭代次數(shù)為50。規(guī)劃好的全局最優(yōu)路徑如圖 6中的實線所示。路徑的長度為13.899 5，雖然與文獻[18]中的路徑長度一致，但是中間拐點的個數(shù)只有2個，規(guī)劃后的路徑效果更佳。而且在0.25 s內(nèi)經(jīng)過13代就可以收斂到最優(yōu)解?？梢姳疚奶岢龅乃惴軌蛟谳^少的代數(shù)內(nèi)收斂到最優(yōu)解。

圖5 U型障礙物環(huán)境中的仿真結(jié)果Fig.5 Simulation result in U-shape obstacle

圖6 全局路徑規(guī)劃仿真結(jié)果對比Fig.6 Comparisons in global path planning

為了證明方法的一般性，在隨機生成的一個較大較復雜的環(huán)境中利用方法對路徑進行了規(guī)劃。仿真環(huán)境和結(jié)果如圖7所示，可以看出機器人能夠在這種錯綜復雜的環(huán)境下依然能夠找到最優(yōu)路徑，具有較強的魯棒性。

圖7 隨機生成環(huán)境仿真結(jié)果Fig.7 Result in random environment

由于本文所研究的方法是用于礦難搜索機器人的路徑規(guī)劃中。為此，按照礦井巷道的GIS地圖得到了如圖8所示的柵格地圖，并應用本文所提方法得到了一條從開始節(jié)點到終止節(jié)點的最優(yōu)機器人路徑。

圖8 煤礦GIS地圖環(huán)境仿真結(jié)果Fig.8 Result in environment based on mine GIS

4.2 局部避障仿真結(jié)果

圖9所示為基于GIS地圖所得的柵格環(huán)境，依據(jù)本文方法所得到的機器人的全局最優(yōu)路徑如圖中實線所示。而圖10所示為發(fā)生變化后的柵格環(huán)境，其中有三部分是由自由柵格變成了障礙柵格，有一部分是由障礙柵格變成了自由柵格。根據(jù)本文所提的局部避障策略得到的機器人最終行進路徑如圖10中實線所示，回程路徑如圖10中虛線所示。由此可見：本文提出的局部避障算法能夠依據(jù)環(huán)境變化情況生成相應的最優(yōu)路徑，使得機器人依然能夠到達目標節(jié)點。最后又通過環(huán)境信息的更新對回程路徑進行了優(yōu)化。

圖9 初始全局路徑規(guī)劃結(jié)果Fig.9 Global path planning result at beginning

圖10 環(huán)境變化后的局部避障仿真結(jié)果Fig.10 Local obstacle avoidance result after changes in environment

5 結(jié)論

(1) 提出了一種改進的遺傳算法用于礦難搜索機器人的全局路徑規(guī)劃，并且以全局路徑規(guī)劃的結(jié)果為基礎針對柵格的變化情況，設計了一種基于柵格變化的局部避障方法。

(2) 基于位置信息負反饋和優(yōu)先級分組的思想改進了種群初始化方法，使得生成的路徑都是可行的，節(jié)省了算法總體運行時間。采用了5種遺傳算子，并在變異節(jié)點的替代節(jié)點的選擇中采用了種群初始化的方法；以路徑長度與拐點個數(shù)作為適應度函數(shù)的參數(shù)，使得算法的指標更佳優(yōu)良；通過自適應地調(diào)節(jié)交叉算子與變異算子的概率從而使得算法保持多樣性的同時又能提高進化速度。

(3) 針對不同的障礙形式與柵格變化情況對機器人進行了全局路徑規(guī)劃仿真與局部避障仿真，結(jié)果證明了方法的有效性與魯棒性。

[1]王忠民,劉軍,竇智,等. 礦難救援機器人的研究應用現(xiàn)狀與開發(fā)[J]. 煤礦機械,2007,28(11): 6-8.WANG Zhong-min,LIU Jun,DOU Zhi,et al. Research and application status and development of search and rescue robot for mine disaster[J]. Coal Mine Machinery,2007,28(11): 6-8.

[2]Casper J,Micire M,Murphy R R. Issues in intelligent robots for search and rescue[C]//Proceedings of SPIE 2000. Orlando: SPIE,2000: 292-302.

[3]Alexopoulos C,Griffin P M. Path planning for a mobile robot[J].IEEE Transaction on Systems,Man,and Cybernetics,1992,22(2): 318-322.

[4]Lozano-peres T. Spatial planning: A configuration space approach[J]. IEEE Transaction on Computers,1983,32(2):108-120.

[5]Kambhampati S,Davis L S. Multiresolution path planning for mobile robots[J]. IEEE Journal of Robotics and Automation,1986,2(3): 135-145.

[6]Fan K C,Lui P C. Solving find path problem in mapped environments using modified A* algorithm[J]. IEEE Transaction on System,Man,and Cybernetics,1994,24(9): 1390-1396.

[7]Noto M,Sato H. A method for the shortest path search by extended dijkstra algorithm[C]//Proceedings of 2000 IEEE International Conference on Systems,Man,and Cybernetics.Nashville: IEEE,2000: 2316-2320.

[8]Bruce J,Veloso M. Real-time randomized path planning for robot navigation[C]//Proceedings for the IEEE /RSJ International Conference on Intelligent Robots and System. Lausanne: IEEE,2002: 2383-2388.

[9]Hwnag Y K,Ahuja N. A potential field approach to path planning[J]. IEEE Transactions on Robotics and Automation,1992,8(1): 23-32.

[10]張純剛,席裕庚. 機器人滾動路徑規(guī)劃的算法與仿真研究[J].高技術(shù)通訊,2003,13(4): 53-57.ZHANG Chun-gang,XI Yu-geng. Algorithm and simulation of robot rolling path planning[J]. High Technology Letters,2003,13(4): 53-57.

[11]Yung N H C,Ye C. An intelligent mobile vehicle navigator based on fuzzy logic and reinforcement learning[J]. IEEE Transactions on Systems,Man,and Cybernetics,1999,29(2):314-321.

[12]Glasius R,Komoda A,Gielen S. A biologically inspired neural net for trajectory formation and obstacle avoidance[J]. Biological Cybernetics,1996,74(6): 511-520.

[13]XUE Ying-hua,TIAN Guo-hui,HUANG Bin. Optimal robot path planning based on danger degree map[C]//Proceedings of 2009 IEEE International Conference on Automation and Logistics. Shenyang: IEEE,2009: 1040-1045.

[14]Huang G,Tung C,Ciou J. To achieve the path planning of mobile robot for a correct destination and direction using fuzzy theory[C]//Proceedings of 2009 IEEE International Symposium on Industrial Electronics. Seoul: IEEE,2009: 1737-1742.

[15]ZHANG Xiao-yong,WU Min,PENG Jun,et al. A rescue robot path planning based on ant colony optimization algorithm[C]//Proceedings of the 2009 IEEE International Conference on Information Technology and Computer Science.Kiev: IEEE,2009: 180-183.

[16]Ghorbani A,Shiry S,Nodehi A. Using genetic algorithm for a mobile robot path planning[C]//Proceedings of the 2009 International Conference on Future Computer and Communication. Kuala Lumpur: IEEE,2009: 164-166.

[17]Mansouri M,Shoorehdeli M A,Teshnehlab M. Integer GA for mobile robot path planning with using another GA as repairing function[C]//Proceedings of the IEEE International Conference on Automation and Logistics. Qingdao: IEEE,2008: 135-140.

[18]LIAO Wei-qiang. Genetic algorithm based robot path planning[C]//Proceedings of 2008 International Conference on Intelligent Computation Technology and Automation. Changsha:IEEE,2008: 56-59.

[19]周巍,李元宗. 基于改進遺傳算法的煤礦探測機器人路徑規(guī)劃[J]. 太原理工大學學報,2010,41(4): 364-367.ZHOU Wei,LI Yuan-zong. Path planning of coal mine detecting robot based on improved genetic algorithm[J]. Journal of Taiyuan University of Technology,2010,41(4): 364-367.

[20]張小艷,周筱媛,魏娟. 煤礦救援機器人全局路徑規(guī)劃[J]. 西安科技大學學報,2008,28(2): 323-326,335.ZHANG Xiao-yan,ZHOU Xiao-yuan,WEI Juan. Global path planning for coalmine rescue robots[J]. Journal of Xi’an University of Science and Technology,2008,28(2): 323-326,335.

[21]LEI Lin,WANG Hou-jun,WU Qin-song. Improved genetic algorithms based path planning of mobile robot under dynamic unknown environment[C]//Proceedings of the 2006 IEEE International Conference on Mechatronics and Automation.Luoyang: IEEE,2006: 1728-1732.

[22]司應濤,朱慶保,國海濤. 基于正反饋遺傳算法的機器人全局路徑規(guī)劃[J]. 計算機工程與應用,2008,44(1): 54-56,62.SI Ying-tao,ZHU Qing-bao,GUO Hai-tao. Global robot path planning based on positive feedback GA[J]. Computer Engineering and Applications,2008,44(1): 54-56,62.

[23]LI Qing,Zhang W,Yin Y,et al. An improved genetic algorithm of optimum path planning for mobile robots[C]//Proceedings of the Sixth International Conference on Intelligent Systems Design and Applications. Jinan: IEEE,2006: 637-642.

[24]陳曦,譚冠政,江斌. 基于免疫遺傳算法的移動機器人實時最優(yōu)路徑規(guī)劃[J]. 中南大學學報: 自然科學版,2008,39(3):577-583.CHEN Xi,TAN Guan-zheng,JIANG Bin. Real-time optimal path planning for mobile robots based on immune genetic algorithm[J]. Journal of Central South University: Science and Technology,2008,39(3): 577-583.

[25]Rudolph G.. Convergence analysis of canonical genetic algorithms[J]. IEEE Transaction on Neural Networks,1994,5(1):96-101.