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

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

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

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

礦難搜索機(jī)器人作為一種移動(dòng)機(jī)器人，其路徑規(guī)劃能力決定了其智能水平的高低。移動(dòng)機(jī)器人的路徑規(guī)劃的主要任務(wù)是在具有靜態(tài)或者動(dòng)態(tài)障礙物的環(huán)境中，依據(jù)一定約束條件，尋找到一條沒(méi)有碰撞的路徑。同時(shí)，這些路徑有時(shí)候要求滿(mǎn)足一些優(yōu)化參數(shù)，例如最短距離、最小時(shí)間和最低能耗等。針對(duì)環(huán)境信息的已知程度，可以將移動(dòng)機(jī)器人的路徑規(guī)劃分為全局路徑規(guī)劃與局部避障。全局路徑規(guī)劃方法依據(jù)已知環(huán)境信息的情況，首先需要對(duì)環(huán)境建模，然后在環(huán)境模型中搜索出一條最優(yōu)的路徑。因此，目前根據(jù)環(huán)境建模形式可以將路徑規(guī)劃方法分為可視圖法[3]，C空間法[4]和柵格法[5]等。依據(jù)搜索的方法的不同又可以分為A*法[6]、Dijkstra方法[7]和快速搜索隨機(jī)樹(shù)算法[8]等。局部避障方法往往需要處理的是未知或者部分未知的環(huán)境。較為常用的有人工勢(shì)場(chǎng)法[9]、基于滾動(dòng)窗口的方法[10]和基于再勵(lì)學(xué)習(xí)的方法[11]等。

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

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

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

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

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

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

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

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

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

2.1 種群初始化

大多數(shù)的遺傳算法都是隨機(jī)地產(chǎn)生初始種群。但是在路徑規(guī)劃中這樣的操作會(huì)導(dǎo)致產(chǎn)生許多不可行的路徑。盡管一些不可行的路徑可以通過(guò)相應(yīng)的遺傳算子變成可行的路徑，但是也會(huì)使得適應(yīng)度函數(shù)需要增加一些判斷條件，從而使得函數(shù)變得復(fù)雜。另外還耗費(fèi)了很多的計(jì)算時(shí)間在一些不可行的路徑上，既浪費(fèi)了存儲(chǔ)空間，又降低了收斂速度。甚至有的不可行的路徑會(huì)使得遺傳算子失去意義。例如，2個(gè)不可行路徑的交叉幾乎很難得到可行的路徑，同樣變異操作也不容易使不可行路徑變?yōu)榭尚小Ｓ梢陨系姆治隹梢钥闯觯喝绻x擇更為有效地種群初始化方法將會(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)A到節(jié)點(diǎn)F的最短路徑所對(duì)應(yīng)的方向，然后可以依據(jù)這個(gè)方向?qū)⒐?jié)點(diǎn)A的8個(gè)鄰居節(jié)點(diǎn)分為3個(gè)具有優(yōu)先級(jí)的組；

Step 3：從第1組到第3組優(yōu)先級(jí)逐級(jí)遞減。優(yōu)先在第1組中選取下一個(gè)路徑上的節(jié)點(diǎn),如果第1組中沒(méi)有合適的節(jié)點(diǎn)，則在第2組中選取，以此類(lèi)推。如果所有鄰近節(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滿(mǎn)足條件，把節(jié)點(diǎn)B加入到路徑中，然后將節(jié)點(diǎn)B的坐標(biāo)值代入節(jié)點(diǎn)A。同時(shí)對(duì)節(jié)點(diǎn)B對(duì)應(yīng)的計(jì)數(shù)器加1；

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

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

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

現(xiàn)在舉例說(shuō)明如何選擇下一個(gè)節(jié)點(diǎn)。圖2所示為相鄰節(jié)點(diǎn)的信息。假定當(dāng)前節(jié)點(diǎn)為圖2(a)中的點(diǎn) 0。如果最短的路徑方向是垂直或者水平的，比如說(shuō)是從節(jié)點(diǎn)0到節(jié)點(diǎn)5的方向，第 1級(jí)分組包括節(jié)點(diǎn)3，5和8，第2級(jí)分組包括節(jié)點(diǎn)2和7，第3級(jí)分組包括節(jié)點(diǎn)1，4和6；如果方向是斜的也就是與節(jié)點(diǎn)0的4個(gè)45°角的鄰近點(diǎn)相同或者相似，例如方向?yàn)楣?jié)點(diǎn)0到節(jié)點(diǎn)8，第1級(jí)分組就包括節(jié)點(diǎn)5，7和8，第2級(jí)分組就包括節(jié)點(diǎn)3和6，第3級(jí)分組就包括節(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ù)用于評(píng)價(jià)路徑的質(zhì)量，決定了算法收斂的速度以及計(jì)算效率。因?yàn)椴挥脤?duì)路徑可行性進(jìn)行判斷，只要考慮能量與時(shí)間的消耗即可。因此，將路徑的長(zhǎng)度和拐點(diǎn)的個(gè)數(shù)作為優(yōu)化指標(biāo)，適應(yīng)度函數(shù)表達(dá)式如下

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

2.3 選擇算子

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

式中：fi為個(gè)體i的適應(yīng)度；ppopsize為種群大小。

2.4 交叉算子

算法采用單點(diǎn)交叉算子。首先隨機(jī)的選擇2個(gè)個(gè)體，然后選擇2個(gè)個(gè)體中除了開(kāi)始節(jié)點(diǎn)和終止節(jié)點(diǎn)的一個(gè)公共節(jié)點(diǎn)作為交叉節(jié)點(diǎn)，如果沒(méi)有公共節(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,34,45,56,67,68,69,80,90,100)。

2.5 變異算子

變異操作使得種群變得多樣，能夠解決早熟問(wèn)題，對(duì)于遺傳算法十分重要。許多學(xué)者的研究中都是采用隨機(jī)的變異操作，但是有時(shí)對(duì)于進(jìn)化沒(méi)有好處。因此，對(duì)傳統(tǒng)的變異算子進(jìn)行了改進(jìn)。首先，仍然隨機(jī)的選擇一個(gè)個(gè)體的拐點(diǎn)進(jìn)行變異，然后，選擇這個(gè)拐點(diǎn)的鄰近節(jié)點(diǎn)來(lái)代替拐點(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è)相交的線(xiàn)段的夾角是銳角或者直角，這條路徑往往不是最短的路徑。因此，需要?jiǎng)h除算子來(lái)去掉一些不必要的節(jié)點(diǎn)改善路徑。刪除算子依據(jù)的原理是三角形的兩邊之和大于第3邊。如圖3(a)所示，節(jié)點(diǎn)3和7使得∠135和∠678分別為直角和45°銳角，這樣通過(guò)刪除算子就可以將這2個(gè)節(jié)點(diǎn)去掉，從而生成如圖3(b)所示的新的路徑(1,2,4,5,6,8)。改變后的路徑長(zhǎng)度很明顯短于改變前的。

2.7 修正算子

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

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

2.8 交叉和變異概率的選擇

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

2.9 精英保留策略

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

2.10 方法分析

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

3 局部避障方法

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

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

當(dāng)障礙物柵格轉(zhuǎn)化為自由柵格時(shí)，會(huì)使得機(jī)器人的移動(dòng)空間變得更大，不會(huì)對(duì)機(jī)器人的行進(jìn)路線(xiàn)造成任何干擾，因此，不需對(duì)機(jī)器人的行走路徑進(jìn)行調(diào)整機(jī)器人依然能夠到達(dá)目標(biāo)節(jié)點(diǎn)，只要在地圖中將原來(lái)的障礙柵格轉(zhuǎn)換為自由柵格即可。這時(shí)候的局部避障策略就是繼續(xù)跟蹤全局路徑規(guī)劃。但是有時(shí)由于障礙物柵格的消失會(huì)使得機(jī)器人的全局最優(yōu)路徑可能變得不是最優(yōu)的，因此，當(dāng)機(jī)器人到達(dá)目標(biāo)點(diǎn)后，將對(duì)最優(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ī)劃

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

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

4 仿真結(jié)果分析

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

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

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

仿真參數(shù)設(shè)置如下，種群規(guī)模為 10，交叉概率PC的變化范圍是從0.65到0.3，變異概率PM的變化范圍是從0.01到0.08，最大迭代次數(shù)為50。規(guī)劃好的全局最優(yōu)路徑如圖 6中的實(shí)線(xiàn)所示。路徑的長(zhǎng)度為13.899 5，雖然與文獻(xiàn)[18]中的路徑長(zhǎng)度一致，但是中間拐點(diǎn)的個(gè)數(shù)只有2個(gè)，規(guī)劃后的路徑效果更佳。而且在0.25 s內(nèi)經(jīng)過(guò)13代就可以收斂到最優(yōu)解?？梢?jiàn)本文提出的算法能夠在較少的代數(shù)內(nèi)收斂到最優(yōu)解。

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

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

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

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

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

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

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

圖9所示為基于GIS地圖所得的柵格環(huán)境，依據(jù)本文方法所得到的機(jī)器人的全局最優(yōu)路徑如圖中實(shí)線(xiàn)所示。而圖10所示為發(fā)生變化后的柵格環(huán)境，其中有三部分是由自由柵格變成了障礙柵格，有一部分是由障礙柵格變成了自由柵格。根據(jù)本文所提的局部避障策略得到的機(jī)器人最終行進(jìn)路徑如圖10中實(shí)線(xiàn)所示，回程路徑如圖10中虛線(xiàn)所示。由此可見(jiàn)：本文提出的局部避障算法能夠依據(jù)環(huán)境變化情況生成相應(yīng)的最優(yōu)路徑，使得機(jī)器人依然能夠到達(dá)目標(biāo)節(jié)點(diǎn)。最后又通過(guò)環(huán)境信息的更新對(duì)回程路徑進(jì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) 提出了一種改進(jìn)的遺傳算法用于礦難搜索機(jī)器人的全局路徑規(guī)劃，并且以全局路徑規(guī)劃的結(jié)果為基礎(chǔ)針對(duì)柵格的變化情況，設(shè)計(jì)了一種基于柵格變化的局部避障方法。

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

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

[1]王忠民,劉軍,竇智,等. 礦難救援機(jī)器人的研究應(yīng)用現(xiàn)狀與開(kāi)發(fā)[J]. 煤礦機(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]張純剛,席裕庚. 機(jī)器人滾動(dòng)路徑規(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]周巍,李元宗. 基于改進(jìn)遺傳算法的煤礦探測(cè)機(jī)器人路徑規(guī)劃[J]. 太原理工大學(xué)學(xué)報(bào),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]張小艷,周筱媛,魏娟. 煤礦救援機(jī)器人全局路徑規(guī)劃[J]. 西安科技大學(xué)學(xué)報(bào),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]司應(yīng)濤,朱慶保,國(guó)海濤. 基于正反饋遺傳算法的機(jī)器人全局路徑規(guī)劃[J]. 計(jì)算機(jī)工程與應(yīng)用,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]陳曦,譚冠政,江斌. 基于免疫遺傳算法的移動(dòng)機(jī)器人實(shí)時(shí)最優(yōu)路徑規(guī)劃[J]. 中南大學(xué)學(xué)報(bào): 自然科學(xué)版,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.