基于遺傳算法的目標追蹤過程中路徑規劃研究*

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

0 引 言

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

1 基于遺傳算法的追蹤路徑規劃

1.1 追蹤區域及路徑編碼的表示方法

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

圖1 追蹤區域及路徑

1.2 初始種群的產生

1.2.1 當前隨機方式產生初始種群存在的問題

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

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

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

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

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

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

4)連接線段SB，BD。

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

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

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

圖2 障礙物

1.2.3 初始種群生成

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

圖3 初始路徑

1.3 適應度函數確定

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

(1)

1.4 交叉算子

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

圖4 交叉算子

1.5 變異方式

采用多點變異方式，根據產生種群時對區域的劃分隨機選擇多個區域，每個區域內選擇一個點，對該點橫坐標及縱坐標進行高斯小范圍變異

(2)

2 仿 真

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

圖5 目標追蹤過程

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

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

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

3 結束語

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

參考文獻:

[1] 山 丹，胡玉蘭．移動機器人動態目標規劃研究[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] 顧幸方，陳晉音．移動機器人未知環境避障研究[J]．傳感器與微系統,2011,30(5)：16-20．

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

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

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

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

[8] 王 雪．無線傳感網絡測量系統[M]．北京：機械工業出版社，2007：307-360.

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