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

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

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

?

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

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

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

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

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

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

1算法原理

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

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)

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

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

3算法設(shè)計(jì)

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

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

圖2　算法流程

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

圖3　算法示意圖

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

(3)

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

(4)

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

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

4實(shí)驗(yàn)對(duì)比分析

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

表1　路徑長(zhǎng)度比較　m

表2　運(yùn)算時(shí)間比較　s

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

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

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

圖4　3種算法實(shí)驗(yàn)對(duì)比曲線

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

5結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

本文引用格式：薛青，孫松濤，陳琳，等.某型輪式裝甲車輛局部路徑規(guī)劃研究——一種考慮人類視覺(jué)特點(diǎn)的幾何算法[J].兵器裝備工程學(xué)報(bào)，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

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

中圖分類號(hào)：TJ811；TP391

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

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