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

0 引 言

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

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

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

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

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

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

1.2.1 當前隨機方式產(chǎn)生初始種群存在的問題

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

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

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

1)連接起始節(jié)點S和目標點D，得線段SD。

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

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

4)連接線段SB，BD。

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

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

注意在通過各障礙區(qū)時每次直線避開障礙物的拉開方向應保持在最短連線的一側，避免路徑迂回。

圖2 障礙物

1.2.3 初始種群生成

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

圖3 初始路徑

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

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

(1)

1.4 交叉算子

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

圖4 交叉算子

1.5 變異方式

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

(2)

2 仿 真

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

圖5 目標追蹤過程

當探測器偵測到目標出現(xiàn)在1號位置時追蹤器啟動，追蹤的路線如圖5(b)所示。

當經(jīng)過一段時間后對目標進行第二次探測，此時追蹤器已經(jīng)到達S1點位置，而此時目標已經(jīng)到達2號點位置，重新對目標追蹤路線進行規(guī)劃。如圖5(c)所示。

再經(jīng)過一段時間后對目標進行第三次、第四次探測，追蹤器經(jīng)過S2點已到達S3點位置，目標則到達了4號點位置。目標與追蹤器間距已經(jīng)小于5柵格距離，完成了追捕如圖5(d)所示。

3 結束語

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

參考文獻:

[1] 山 丹，胡玉蘭．移動機器人動態(tài)目標規(guī)劃研究[J]．沈陽理工大學學報,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] 顧幸方，陳晉音．移動機器人未知環(huán)境避障研究[J]．傳感器與微系統(tǒng),2011,30(5)：16-20．

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

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

[6] 鄒細勇．自主移動機器人的智能導航研究 [D]．杭州： 浙江大學,2004：48-58.

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

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

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