基于遺傳算法的目標(biāo)追蹤過(guò)程中路徑規(guī)劃研究*

鞠成恩， 趙曉俠， 王明興， 黎振紅

0 引 言

在目標(biāo)追蹤過(guò)程中，路徑規(guī)劃[1，2]是關(guān)鍵問(wèn)題之一，其目的是在具有障礙物的環(huán)境里，根據(jù)一定的規(guī)則，尋找一條從起始點(diǎn)到目標(biāo)的無(wú)碰撞路徑，以較短的行程在較少的時(shí)間內(nèi)追蹤目標(biāo)。路徑規(guī)劃常用的方法有人工勢(shì)場(chǎng)法、可視圖法和蟻群算法[3～5]等，但均存在著一定的缺點(diǎn), 如算法計(jì)算量大 、自適應(yīng)能力差以及易陷入局部最優(yōu)解等。本文提出了路徑規(guī)劃方法，在遺傳算法[6，7]的基礎(chǔ)之上，應(yīng)用簡(jiǎn)單幾何避障方式產(chǎn)生遺傳編碼，通過(guò)仿真證明了方法能在障礙物環(huán)境下，實(shí)現(xiàn)追蹤目標(biāo)過(guò)程中的路徑規(guī)劃。

1 基于遺傳算法的追蹤路徑規(guī)劃

1.1 追蹤區(qū)域及路徑編碼的表示方法

整個(gè)環(huán)境區(qū)域用二維柵格表示，以二維坐標(biāo)(x，y)表示位置如圖1所示。圖中的空白區(qū)域表示無(wú)障礙物阻擋，目標(biāo)及追蹤器在該區(qū)域內(nèi)可以自由移動(dòng)；陰影部分表示有障礙。追蹤器的行進(jìn)路徑由一串二維坐標(biāo)點(diǎn)連接而成，本文采用浮點(diǎn)數(shù)編碼。圖中，S和D為路徑的起點(diǎn)和目標(biāo)點(diǎn)，v1(x1，y1)，v2(x2，y2)，…，vn(xn，yn)為路徑上的點(diǎn)，路徑長(zhǎng)度可變，目標(biāo)D沿序號(hào)1，2，3，4，5，6運(yùn)動(dòng)。

圖1 追蹤區(qū)域及路徑

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

1.2.1 當(dāng)前隨機(jī)方式產(chǎn)生初始種群存在的問(wèn)題

當(dāng)前遺傳算法產(chǎn)生種群一般采用隨機(jī)方式，產(chǎn)生的種群中有很多非連通路徑，雖然在迭代運(yùn)算中可能轉(zhuǎn)化為連通路徑，但轉(zhuǎn)化效果一般并不理想，使得過(guò)程解的覆蓋空間具有很大的不確定性，可能在有限的進(jìn)化代數(shù)內(nèi)過(guò)早收斂，影響最終解的質(zhì)量。所以，在確保初始種群的多樣性的前提下盡可能保證所產(chǎn)生的路徑連通，有助于改善算法的求解速度和全局收斂性。

1.2.2 基于切線方向方式的幾何避障方法

本文提出了一種沿切線方向拉開(kāi)的避障方法，基本思想為遇到障礙時(shí)沿切線方向作規(guī)避動(dòng)作遠(yuǎn)離障礙，如圖2所示 ，具體實(shí)現(xiàn)步驟為：

1)連接起始節(jié)點(diǎn)S和目標(biāo)點(diǎn)D，得線段SD。

2)判斷線段SD間是否被障礙物隔開(kāi)。如果未隔開(kāi)，則線段SD為最短路徑；否則，繼續(xù)。

3)若障礙區(qū)和線段SD相交于點(diǎn)A，以A為起點(diǎn)作障礙物在A點(diǎn)處邊緣的切線，該直線交無(wú)障礙區(qū)域F于任一點(diǎn)B，若相交處為障礙物頂點(diǎn)，則在該點(diǎn)處作垂直于路徑的垂線，同樣該垂線交無(wú)障礙區(qū)域F于任一點(diǎn)B。

4)連接線段SB，BD。

5)在線段SB，BD中重復(fù)步驟(1)～步驟(4)直至線段不與障礙區(qū)域相交為止。

6)將各條分線段組合，形成一條由S到D的連通路徑。

注意在通過(guò)各障礙區(qū)時(shí)每次直線避開(kāi)障礙物的拉開(kāi)方向應(yīng)保持在最短連線的一側(cè)，避免路徑迂回。

圖2 障礙物

1.2.3 初始種群生成

采用沿切線方向拉開(kāi)的避障方法生成初始種群，當(dāng)出現(xiàn)一個(gè)或多個(gè)障礙區(qū)域時(shí)，其產(chǎn)生初始路徑的方法相似。以多個(gè)障礙區(qū)為例：1)作一條連接起點(diǎn)和目標(biāo)點(diǎn)的連線；2)根據(jù)自由區(qū)域?qū)^(qū)域進(jìn)行分割，對(duì)不同的障礙區(qū)域生成各自的避障路徑, 最后將各段路徑連成一條完整的初始路徑，如圖3所示，(S-v1-v2-c3-v4-D)為生成的一條路徑。

圖3 初始路徑

1.3 適應(yīng)度函數(shù)確定

采用的適應(yīng)度函數(shù)為總路徑S最短，pi為路徑中間點(diǎn)

(1)

1.4 交叉算子

本文利用切線方向拉開(kāi)的特點(diǎn)，采用分區(qū)同側(cè)交叉方式改進(jìn)傳統(tǒng)交叉算子不利于收斂的特點(diǎn)。根據(jù)產(chǎn)生種群時(shí)的劃分區(qū)域，隨機(jī)選擇一個(gè)區(qū)域，在此區(qū)域內(nèi)若交叉線段位于障礙物一側(cè)，則在此線段上進(jìn)行單點(diǎn)交叉；若交叉線段位于障礙物兩側(cè)，則放棄。如圖4所示,路徑S-B1-C1-D與S-B2-C1-D在障礙物一側(cè)可以進(jìn)行單點(diǎn)交差，而S-B3-D在障礙物另一側(cè)不與前兩條路徑進(jìn)行單點(diǎn)交差。

圖4 交叉算子

1.5 變異方式

采用多點(diǎn)變異方式，根據(jù)產(chǎn)生種群時(shí)對(duì)區(qū)域的劃分隨機(jī)選擇多個(gè)區(qū)域，每個(gè)區(qū)域內(nèi)選擇一個(gè)點(diǎn)，對(duì)該點(diǎn)橫坐標(biāo)及縱坐標(biāo)進(jìn)行高斯小范圍變異

(2)

2 仿 真

設(shè)整個(gè)區(qū)域由50×50柵格組成，每個(gè)柵格表示一個(gè)二維位置坐標(biāo)(x,y)，如圖5(a)所示。S點(diǎn)方塊表示追蹤器位置，D點(diǎn)實(shí)心圓表示目標(biāo)位置，追蹤器的速度為目標(biāo)的1.5倍。假設(shè)整個(gè)區(qū)域內(nèi)布置有固定探測(cè)器[8,9]，每隔一段時(shí)間對(duì)目標(biāo)進(jìn)行探測(cè)以獲得目標(biāo)的當(dāng)前位置。目標(biāo)計(jì)劃的侵入路線如圖所示，由1號(hào)點(diǎn)位置侵入順序經(jīng)過(guò)2,3,4,5號(hào)點(diǎn)由6號(hào)點(diǎn)逃逸出區(qū)域。假設(shè)追蹤器與目標(biāo)若相距5個(gè)柵格即視為追蹤到目標(biāo)。

圖5 目標(biāo)追蹤過(guò)程

當(dāng)探測(cè)器偵測(cè)到目標(biāo)出現(xiàn)在1號(hào)位置時(shí)追蹤器啟動(dòng)，追蹤的路線如圖5(b)所示。

當(dāng)經(jīng)過(guò)一段時(shí)間后對(duì)目標(biāo)進(jìn)行第二次探測(cè)，此時(shí)追蹤器已經(jīng)到達(dá)S1點(diǎn)位置，而此時(shí)目標(biāo)已經(jīng)到達(dá)2號(hào)點(diǎn)位置，重新對(duì)目標(biāo)追蹤路線進(jìn)行規(guī)劃。如圖5(c)所示。

再經(jīng)過(guò)一段時(shí)間后對(duì)目標(biāo)進(jìn)行第三次、第四次探測(cè)，追蹤器經(jīng)過(guò)S2點(diǎn)已到達(dá)S3點(diǎn)位置，目標(biāo)則到達(dá)了4號(hào)點(diǎn)位置。目標(biāo)與追蹤器間距已經(jīng)小于5柵格距離，完成了追捕如圖5(d)所示。

3 結(jié)束語(yǔ)

基于切線方向的幾何避障方法，不僅保證了遺傳算法產(chǎn)生種群時(shí)路徑的連通性，而且避免了傳統(tǒng)遺傳算法的隨機(jī)性對(duì)結(jié)果產(chǎn)生的不利影響，仿真結(jié)果表明本文方法正確可行。

參考文獻(xiàn):

[1] 山 丹，胡玉蘭．移動(dòng)機(jī)器人動(dòng)態(tài)目標(biāo)規(guī)劃研究[J]．沈陽(yáng)理工大學(xué)學(xué)報(bào),2011,30(3)：13-16．

[2] Deepak B L，Parhi D R，Kundu S．Innate immune based path planner of an autonomous mobile robot[J]．Procedia Engineering，2012，38：2663-2671．

[3] 顧幸方，陳晉音．移動(dòng)機(jī)器人未知環(huán)境避障研究[J]．傳感器與微系統(tǒng),2011,30(5)：16-20．

[4] 白金柯，陳立家，金 何,等．動(dòng)態(tài)未知環(huán)境下一種新的機(jī)器人路徑規(guī)劃方法[J]．傳感器與微系統(tǒng),2011,30(10)：33-36．

[5] 張 琦，馬家辰，謝 瑋,等．基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]．東北大學(xué)學(xué)報(bào):自然科學(xué)版,2013,34(11)：1521-1524．

[6] 鄒細(xì)勇．自主移動(dòng)機(jī)器人的智能導(dǎo)航研究 [D]．杭州： 浙江大學(xué),2004：48-58.

[7] 姜明洋．基于遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃方法的研究[D]．沈陽(yáng)：沈陽(yáng)理工大學(xué), 2008：6-45.

[8] 王 雪．無(wú)線傳感網(wǎng)絡(luò)測(cè)量系統(tǒng)[M]．北京：機(jī)械工業(yè)出版社，2007：307-360.

[9] 呂淑芳．無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位研究綜述[J]．傳感器與微系統(tǒng)，2016，35(5)：1-3,8．