某型輪式裝甲車輛局部路徑規(guī)劃研究
——一種考慮人類視覺特點的幾何算法

薛　青，孫松濤，2，陳　琳，丁　蘋，2

(1.裝甲兵工程學(xué)院，北京　100072; 2.總參陸航部，北京　101114)

?

某型輪式裝甲車輛局部路徑規(guī)劃研究
——一種考慮人類視覺特點的幾何算法

薛青1，孫松濤1，2，陳琳1，丁蘋1，2

(1.裝甲兵工程學(xué)院，北京100072; 2.總參陸航部，北京101114)

摘要：為了提高輪式裝甲車輛局部路徑規(guī)劃能力，滿足裝備作戰(zhàn)仿真的需求，在基本幾何算法的基礎(chǔ)上考慮人類視覺特點，提出了一種基于坐標(biāo)變換的幾何算法用于輪式裝甲車輛局部路徑規(guī)劃。經(jīng)過仿真實驗與對比分析，該算法在運算速度上有明顯優(yōu)勢，既能滿足實時性要求，也能真實反映作戰(zhàn)人員野戰(zhàn)機動特點，是一種實用的局部路徑規(guī)劃方法。

關(guān)鍵詞：路徑規(guī)劃；改進(jìn)幾何算法；裝甲車輛；視覺

輪式裝甲車輛局部路徑規(guī)劃是指在全局規(guī)劃的路徑機動過程中，遇到新的障礙物后迅速做出反應(yīng)，待完成局部避障處理后，再回到預(yù)先規(guī)劃的全局路徑上機動[1]。因此，局部路徑規(guī)劃算法要求實時性強，計算效率高。目前，常用的局部路徑規(guī)劃算法有A*算法、人工勢場法、遺傳算法等[2-5]，但存在一些不足之處，例如A*算法對啟發(fā)函數(shù)依賴程度高；人工勢場法容易在障礙物前振蕩；遺傳算法搜索時間長、局部尋優(yōu)能力不足等[6-8]。本研究根據(jù)幾何理論，同時考慮人類視覺特點，研究一種幾何算法用于輪式裝甲車輛局部路徑規(guī)劃，仿真結(jié)果表明，該算法簡便高效，能夠滿足路徑規(guī)劃實時要求。

1算法原理

研究表明，視覺是人類感知信息的主要來源，人類80%以上的信息都是由視覺提供的。但是，視覺也有局限性：單眼視野約150°，雙眼視野約180°，中間120°為雙眼共有的有效視覺范圍；在垂直方向上的視野為視平線上50°和視平線下70°范圍。因此，本研究設(shè)計一種符合人類視覺特點的幾何算法，著重考慮輪式裝甲車輛眼前的局部環(huán)境信息，而不考慮后面的障礙物情況，這樣得到的可能不是最優(yōu)路徑，但卻符合作戰(zhàn)人員的局部路徑規(guī)劃特點。

在野戰(zhàn)環(huán)境下，輪式裝甲車輛按照預(yù)先規(guī)劃的全局路徑機動時，一般會遇到一些新的局部障礙物，例如彈坑、斷橋等，當(dāng)這些障礙物進(jìn)入輪式裝甲車輛的探測范圍時，首先會判斷當(dāng)前障礙物是否在前進(jìn)方向上。如果在當(dāng)前行進(jìn)方向上，則要基于兩點之間直線距離最短的原則，分析怎樣繞過這個障礙物，即根據(jù)具體環(huán)境的經(jīng)驗判斷，選擇一個可行駛路徑點避開當(dāng)前這個障礙物。在這些情況下，大多數(shù)作戰(zhàn)人員會憑視覺感知規(guī)劃行駛路徑，得到的規(guī)劃路徑不一定是最優(yōu)的，但是大致方向沒有變，對全局路徑規(guī)劃影響不大。

算法的整體思路：在初始坐標(biāo)系中，以輪式裝甲車輛發(fā)現(xiàn)障礙物時的位置為相對原點o′，以目標(biāo)方向為o′x′建立相對直角坐標(biāo)系x′o′y′，于是o′x′可以將障礙物分為上、下兩個集合，然后選擇輪式裝甲車輛當(dāng)前位置o′所能觀察到的障礙物可通過邊緣頂點作為備選路徑點，計算出上、下兩個方向集中備選路徑點的行駛方向角，找出上、下兩個方向集中行駛方向角最大的兩個點，通過對比選擇這兩點中行駛方向角小的那一個作為“最佳路徑點”。

2坐標(biāo)空間描述

采用可視圖法建立虛擬三維空間模型，障礙物則采用歐氏平面里的凸多邊形表示，而對于存有凹點的多邊形，可以通過求取凸殼得到包含這些凹頂點的最小凸多邊形。為便于描述先確定幾個定義：

定義1：設(shè)障礙物o為有限平面區(qū)域，該區(qū)域由一系列點P1，P2，…，PN首尾相連所圍成，Pi(i=1，2，…，N)是多邊形o的頂點，相鄰頂點的連線PiPi+1是多邊形o的邊界。若多邊形o的所有頂點都位于連線PiPi+1的一側(cè)(除去直線上的兩點)，則稱該多邊形o為凸多邊形。

定義2：設(shè)機動中的輪式裝甲車輛當(dāng)前位置為r，接連的下一個可選路徑點為T，其中T是從凸多邊形的頂點產(chǎn)生的，連線rt的方向稱為輪式裝甲車輛的行進(jìn)方向。

定義3：設(shè)機動中的輪式裝甲車輛當(dāng)前位置為r，接連的下一個子目標(biāo)點為G，其中G是預(yù)先全局路徑規(guī)劃中r接連的下一個路徑點，連線rg的方向稱為輪式裝甲車輛目標(biāo)方向。

定義4：機動中的輪式裝甲車輛目標(biāo)方向與行進(jìn)方向之間的夾角稱為路徑方向角δ。

本研究采用虛擬三維環(huán)境中的大地平面坐標(biāo)和輪式裝甲車輛兩種坐標(biāo)空間。如圖1所示，其中大地平面坐標(biāo)系xoy為絕對坐標(biāo)系，也稱全局坐標(biāo)系，用于表示起始點位置、目標(biāo)點位置以及輪式裝甲車輛每一時刻的位置，以便于在輪式裝甲車輛每一次局部路徑規(guī)劃都能直接轉(zhuǎn)化為全局坐標(biāo)。x′o′y′為相對坐標(biāo)系，代表輪式裝甲車輛的局部坐標(biāo)空間，用于計算路徑方向角，以輪式裝甲車輛的當(dāng)前位置為相對原點o′，橫軸o′x′方向則表示目標(biāo)方向。兩種坐標(biāo)系的坐標(biāo)變換按如下方法計算：

設(shè)o′點在xoy坐標(biāo)系中的坐標(biāo)值為(A,B)，ox與o′x′的夾角為θ，若已知頂點A在xoy坐標(biāo)系中的坐標(biāo)為(x,y)，可按式(1)轉(zhuǎn)換為x′o′y′坐標(biāo)系中的坐標(biāo)(x′,y′)

(1)

同理，可實現(xiàn)相對坐標(biāo)系到絕對坐標(biāo)系的變換，若已知頂點A在x′o′y′坐標(biāo)系中的坐標(biāo)為(x′,y′)，可按式(2)將其轉(zhuǎn)換為xoy坐標(biāo)系中的坐標(biāo)(x,y)

(2)

其中：式(1)稱為正變換，式(2)稱為逆變換。通過以上的坐標(biāo)空間描述，可將障礙物o映射到坐標(biāo)系x′o′y′中。

圖1　坐標(biāo)空間示意圖

3算法設(shè)計

輪式裝甲車輛在預(yù)先規(guī)劃的全局路徑上行駛時，目標(biāo)方向左右共計120°范圍內(nèi)發(fā)現(xiàn)障礙物后可按照以下操作流程進(jìn)行局部路徑規(guī)劃，其算法流程如圖2所示。

步驟1：首先進(jìn)行坐標(biāo)正變換。為便于判斷，可采用相對坐標(biāo)系x′o′y′來計算，如圖3所示，多邊形o1表示局部出現(xiàn)的障礙物，在絕對坐標(biāo)系xoy中，以輪式裝甲車輛的當(dāng)前位置r為原點，以rg為橫軸建立相對坐標(biāo)系x′oy′，由初始條件可知多邊形o1各頂點在絕對坐標(biāo)系xoy下的坐標(biāo),由式(1)分別求得可看到的各頂點在相對坐標(biāo)系x′oy′下的坐標(biāo)。

圖2　算法流程

步驟2：判斷目標(biāo)方向rg是否穿越障礙物。逐個比較可看到的各頂點在相對坐標(biāo)系x′o′y′下的縱坐標(biāo)值：若都大于0或都小于0，則目標(biāo)方向rg不會與該障礙物相交，轉(zhuǎn)至Step6；若存在同時大于0和小于0的情況，則目標(biāo)方向rg會與該障礙物相交，將障礙物頂點分為上、下兩個集合，假設(shè)相交情況如圖3所示。

圖3　算法示意圖

步驟3：分別計算路徑方向角。考慮到人類視覺局限性，輪式裝甲車輛位于當(dāng)前位置r時，作戰(zhàn)人員只能把看到A、d、E、f4個障礙物頂點作為備選路徑點，根據(jù)各個頂點在相對坐標(biāo)系x′o′y′下的坐標(biāo)，分別計算路徑方向角δ，以A點為例，其路徑方向角計算公式如下

(3)

步驟4：選擇“最佳路徑點”。分別比較上頂點集合和下頂點集合中各個路徑方向角的大小，選取上、下各一個最大路徑方向角作為備選路徑，然后在上、下兩個備選路徑中選取路徑方向角較小的一個作為“最佳路徑點”。假設(shè)上頂點集中的備選路徑點表示為{(xi′,yi′)∪yi′>0}，下頂點集中的備選路徑點表示為{(xj′,yj′)∪yj′<0}，最佳路徑方向角記作δbest，則有式(4)：

(4)

步驟5：進(jìn)行坐標(biāo)反變換。按照式(2)計算“最佳路徑點”在xoy坐標(biāo)系下的坐標(biāo)，待輪式裝甲車輛行進(jìn)至該點后，接著將該點確定為新的當(dāng)前位置，返回步驟1進(jìn)行新一輪局部路徑規(guī)劃。

步驟6：若未發(fā)現(xiàn)目標(biāo)方向上有相交的障礙物，輪式裝甲車輛可直接行進(jìn)至子目標(biāo)點G。

4實驗對比分析

將仿真實驗與傳統(tǒng)的A*算法和遺傳算法的仿真結(jié)果進(jìn)行對比分析。實驗參數(shù)設(shè)置如下：A*算法的啟發(fā)函數(shù)H(N)定義為輪式裝甲車輛從當(dāng)前位置到目標(biāo)位置的估計路徑長度；遺傳算法的種群大小為150，交叉概率、變異概率分別取0.8、0.1，終止進(jìn)化代數(shù)為200。計算機基本配置為Pentium(R)D CPU 3.0 GHz，內(nèi)存2 GB，在Windows XP系統(tǒng)下用Visual C++ 6.0和Matlab R2007進(jìn)行仿真程序設(shè)計開發(fā)。實驗時選擇3種算法的路徑長度和運行時間這兩個指標(biāo)進(jìn)行對比分析，為消除實驗中的誤差，每種算法各進(jìn)行10次實驗，并對實驗結(jié)果進(jìn)行平均處理。實驗結(jié)果如表1、表2所示。

表1　路徑長度比較　m

表2　運算時間比較　s

通過對表1和表2的實驗結(jié)果進(jìn)行分析可以得出如下結(jié)論：

1)路徑長度方面：遺傳算法所規(guī)劃的路徑長度最短，A*算法和幾何算法所規(guī)劃的路徑長度差別不大。主要是因為由于遺傳算法是經(jīng)過迭代計算，可以找到最優(yōu)最短路徑；A*算法對啟發(fā)函數(shù)的依賴性較強，難以保證每次搜索到的都是最短路徑，有可能是次短路徑；幾何算法是根據(jù)當(dāng)前位置和目標(biāo)位置以及障礙物備選路徑點的連線計算路徑方向角，通過對比分析，選擇相對小的路徑方向角，僅考慮當(dāng)前所看到的障礙物，不了解障礙物后面的情況，所選路徑不一定最短。

2)運算時間方面：幾何算法的運算時間最少，A*算法和遺傳算法都明顯多于幾何算法。這是因為幾何算法考慮人類視覺局限性，僅判斷當(dāng)前位置到目標(biāo)點連線上的障礙物，也僅選擇當(dāng)前位置所能夠觀察到的障礙物頂點作為備選路徑點用以計算備選路徑角，同時計算方法也比較簡單，算法運行效率較高；A*算法在進(jìn)行路徑規(guī)劃時對啟發(fā)函數(shù)依賴較大，需要計算啟發(fā)函數(shù)用以評估待擴展的節(jié)點值，并且可能經(jīng)常要擴展到整個全局路徑規(guī)劃空間才能搜索到理想路徑，所需時間明顯多于幾何算法；而遺傳算法在進(jìn)行路徑規(guī)劃時需要進(jìn)行循環(huán)迭代計算，并且都需要通過選擇、交叉、變異、刪除、插入等遺傳算法操作，運算時間最長。圖4是表1和表2中實驗結(jié)果的直觀顯示。

圖4　3種算法實驗對比曲線

綜上所述，考慮人類視覺特點的幾何算法在運算時間方面的優(yōu)勢明顯，所得到的路徑卻不是最短路徑。但是作戰(zhàn)環(huán)境下的局部路徑規(guī)劃應(yīng)首先考慮實時快速性要求，繼而兼顧局部路徑規(guī)劃長度，這樣才能夠滿足戰(zhàn)場環(huán)境瞬息萬變的要求。由于幾何算法運算速度快，算法相對簡單，因此，采用幾何算法進(jìn)行局部路徑規(guī)劃的輪式裝甲車輛在發(fā)現(xiàn)新出現(xiàn)的障礙物后能夠迅速做出規(guī)避動作，按新規(guī)劃路徑繼續(xù)機動，這滿足實戰(zhàn)化訓(xùn)練要求，能夠真實反映作戰(zhàn)人員野戰(zhàn)機動特點，是一種實用的局部路徑規(guī)劃方法。

5結(jié)論

本文對輪式裝甲車輛局部路徑規(guī)劃方法進(jìn)行了深入研究，分析了傳統(tǒng)的局部路徑規(guī)劃方法的優(yōu)劣，結(jié)合人類視覺特點提出了一種基于坐標(biāo)變換的幾何算法方法用于裝備作戰(zhàn)仿真研究，結(jié)果表明該方法有效提高了輪式裝甲車輛局部路徑規(guī)劃能力，運算速度明顯提高，所選路徑雖然不一定是最短或次短路徑，但符合作戰(zhàn)人員的局部路徑規(guī)劃特點，滿足野戰(zhàn)環(huán)境下的實時性需求，是一種實用的輪式裝甲車輛局部路徑規(guī)劃方法。

參考文獻(xiàn)：

[1]薛青.裝備作戰(zhàn)仿真基礎(chǔ)[M].北京：國防工業(yè)出版社,2010.

[2]趙志輝,朱亞紅,劉素兵,等.定積分的幾何算法[J].高等數(shù)學(xué)研究,2014,17(6):38-40.

[3]陳小燕,張圣貴.一類凸規(guī)劃問題的幾何算法[J].福建師范大學(xué)學(xué)報,2012,28(2):7-10.

[4]閆守住,薛青,羅佳,等.基于免疫遺傳算法的輪式裝甲車輛CGF路徑規(guī)劃研究[J].四川兵工學(xué)報,2014(10):25-28.

[5]張海英,范進(jìn)楨.移動機器人路徑規(guī)劃研究現(xiàn)狀及展望[J].微型機與應(yīng)用,2011,30(2):5-8.

[6]栗紅生,劉瑩.復(fù)雜路徑下機器人路徑規(guī)劃優(yōu)化方法仿真[J].計算機仿真,2012,31(1):407-411.

[7]楊柳,張洪,高忠國.基于人工勢場法的移動機器人路徑規(guī)劃研究[J].機床與液壓,2011,39(9):68-70.

[8]趙開新,王東署.未知環(huán)境中自主機器人的路徑規(guī)劃研究[J].鄭州大學(xué)學(xué)報,2011,34(5):74-79.

(責(zé)任編輯周江川)

本文引用格式：薛青，孫松濤，陳琳，等.某型輪式裝甲車輛局部路徑規(guī)劃研究——一種考慮人類視覺特點的幾何算法[J].兵器裝備工程學(xué)報，2016(5):25-28.

Citation format:XUE Qing，SUN Song-tao，CHEN Lin，et al.Research of One Wheeled Armored Vehicle Local Path Planning: A Geometric Algorithm Considering the Characteristics of Human Vision[J].Journal of Ordnance Equipment Engineering,2016(5):25-28.

Research of One Wheeled Armored Vehicle Local Path Planning: A Geometric Algorithm Considering the Characteristics of Human Vision

XUE Qing1，SUN Song-tao1,2，CHEN Lin1，DING Ping1,2

(1.Academy of Armored Force Engineering，Beijing 100072，China；2.Army Aviation Department，Beijing 101114，China)

Abstract:In order to improve the ability of the wheeled armored vehicle local path planning and to satisfy the needs of equipment fight simulation,this paper proposed a geometric algorithm for local path planning of wheeled armored vehicle based on the basic geometric algorithm.Through simulation experiments and contrastive analysis，this algorithm is a practical method of local path planning，and it perform superiority obviously at running speed,and it meets the real-time requirements,and it reacts the characteristics of the warfighter field motor truly.

Key words:path planning；improved geometric algorithm；armored vehicle；vision

doi:【裝備理論與裝備技術(shù)】10.11809/scbgxb2016.05.007

收稿日期：2015-11-28；修回日期：2015-12-30

作者簡介：薛青(1961—)，男，教授，博士生導(dǎo)師，中國計算機用戶協(xié)會仿真應(yīng)用分會副理事長，主要從事裝備作戰(zhàn)與保障仿真研究。

中圖分類號：TJ811；TP391

文獻(xiàn)標(biāo)識碼：A

文章編號：2096-2304(2016)05-0025-04