智能自動(dòng)駕駛汽車(chē)的軌跡優(yōu)化

李曉芳++何俊

摘要： 智能自動(dòng)化駕駛技術(shù)是一門(mén)新興的技術(shù)，在汽車(chē)自動(dòng)駕駛的過(guò)程中，如何讓汽車(chē)避開(kāi)障礙物并以最短的路徑到達(dá)指定的位置，是智能自動(dòng)化駕駛汽車(chē)的關(guān)鍵性問(wèn)題。本文通過(guò)模擬智能自動(dòng)駕駛汽車(chē)的運(yùn)行環(huán)境，利用遺傳算法對(duì)汽車(chē)的運(yùn)行軌跡進(jìn)行研究，實(shí)驗(yàn)證明可以獲得較好的結(jié)果。

Abstract： Intelligent automation driving technology is an emerging technology. In the process of vehicle automated driving， how to let the car to avoid obstacles and to reach the location specified in the shortest path is key problem of intelligent automation vehicle driving. In this paper， through the simulation of the running environment of intelligent automatic vehicle driving， the genetic algorithm is used for vehicle trajectory study， and the experiments show good results can be obtained.

關(guān)鍵詞： 智能自動(dòng)駕駛汽車(chē)；遺傳算法；軌跡優(yōu)化

Key words： intelligent automation vehicle driving；genetic algorithm；trajectory optimization

中圖分類(lèi)號(hào)：U471.1 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-4311（2017）21-0129-02

0 引言

自動(dòng)駕駛汽車(chē)又稱(chēng)無(wú)人駕駛汽車(chē)、電腦駕駛汽車(chē)或輪式移動(dòng)機(jī)器人，是一種通過(guò)電腦系統(tǒng)實(shí)現(xiàn)無(wú)人駕駛的智能汽車(chē)。自動(dòng)駕駛汽車(chē)技術(shù)的研發(fā)，在20世紀(jì)也已經(jīng)有數(shù)十年的歷史，于21世紀(jì)初呈現(xiàn)出接近實(shí)用化的趨勢(shì)。自動(dòng)駕駛汽車(chē)依靠人工智能、視覺(jué)計(jì)算、雷達(dá)、監(jiān)控裝置和全球定位系統(tǒng)協(xié)同合作，讓電腦可以在沒(méi)有任何人類(lèi)主動(dòng)的操作下，自動(dòng)安全地操作機(jī)動(dòng)車(chē)輛。

全局路徑規(guī)劃是指在環(huán)境信息全部已知的情況下，為智能自動(dòng)駕駛汽車(chē)規(guī)劃一條無(wú)碰最優(yōu)路徑。由于常用路徑規(guī)劃方法均存在一定的局限性，因此，目前智能自動(dòng)駕駛汽車(chē)路徑規(guī)劃問(wèn)題的研究重點(diǎn)在于尋求一些更加有效的求解方法或者在已有方法的基礎(chǔ)上進(jìn)行改進(jìn)，以使其能夠更好地解決路徑規(guī)劃問(wèn)題。

1 遺傳算法的基本理論

遺傳算法的核心思想是借用遺傳學(xué)中的思想以及達(dá)爾文進(jìn)化論的“物競(jìng)天擇，適者生存”，最早由美國(guó)密歇根大學(xué)的John Holland教授于1975年提出的，1989年，Goldberg在其著作中對(duì)遺傳算法進(jìn)行了更為全面和系統(tǒng)的總結(jié)，并由此奠定了遺傳算法的基礎(chǔ)。遺傳算法是從某一初始解集出發(fā)，采用一個(gè)評(píng)價(jià)函數(shù)（也稱(chēng)為適應(yīng)度函數(shù)）來(lái)評(píng)價(jià)每個(gè)個(gè)體的優(yōu)劣，即個(gè)體對(duì)環(huán)境的適應(yīng)程度，用作以后遺傳操作的依據(jù)，經(jīng)過(guò)選擇、交叉和變異等遺傳操作產(chǎn)生新一代的種群，然后對(duì)新的一代重復(fù)遺傳操作，經(jīng)過(guò)一定次數(shù)的迭代之后，最終收斂到問(wèn)題的最優(yōu)解或次優(yōu)解。

2 自動(dòng)駕駛汽車(chē)路徑規(guī)劃方法

2.1 環(huán)境模型的建立

環(huán)境建模是實(shí)現(xiàn)路徑規(guī)劃的基礎(chǔ)，其目的是將實(shí)際的物理空間映射成算法能夠處理的抽象空間。合理的環(huán)境模型有利于計(jì)算機(jī)存儲(chǔ)、處理和更新以及減少搜索量。目前常用的環(huán)境建模方法主要包括：可視圖法、柵格法、自由空間法和拓?fù)浞ǎ渲袞鸥穹ㄊ鞘褂幂^為成功的一種環(huán)境建模方法，本文將采用柵格法建立環(huán)境模型。

在A中建立直角坐標(biāo)系XOY，其中坐標(biāo)原點(diǎn)設(shè)在A區(qū)域的左下角，且和分別是在Xmax、Ymax軸上的最大值，對(duì)X，Y以智能自動(dòng)駕駛汽車(chē)能自由運(yùn)動(dòng)的最大活動(dòng)范圍Ra為步長(zhǎng)分別進(jìn)行劃分，由此形成工作柵格，其中每行的柵格數(shù)m=ceil（Xmax/Ra），每列的柵格數(shù)n=ceil（Ymax/Ra），最終構(gòu)成一個(gè)m×n的柵格矩陣。假設(shè)環(huán)境中存在k個(gè)障礙物，則每個(gè)障礙物obi（i=1，2…，k）占一個(gè)或多個(gè)柵格，當(dāng)不滿(mǎn)一個(gè)柵格時(shí)，按一個(gè)柵格計(jì)算。

目前關(guān)于柵格的標(biāo)識(shí)方法主要有以下兩種：

①直角坐標(biāo)法。

把（0，0）設(shè)為坐標(biāo)原點(diǎn)，規(guī)定水平向右為X軸正方向，豎直向上為Y軸正方向，坐標(biāo)軸上的單位長(zhǎng)度為柵格大小，因此，任意一個(gè)柵格都可以用直角坐標(biāo)（x，y）表示。

②序號(hào)法。

在建立的柵格模型中，定義從左上角開(kāi)始的第一個(gè)柵格A（1，1）的序號(hào)為1，A（1，2）的序號(hào)為2，…，依次類(lèi)推。

對(duì)于任意一個(gè)柵格A（a，b），其中a為在A中的行號(hào)，b為在A中的列號(hào)，都有確定的坐標(biāo)（x，y）及相應(yīng)的序號(hào)S與之一一對(duì)應(yīng)， 在n×n的柵格環(huán)境中，柵格序號(hào)S和坐標(biāo)（x，y）的關(guān)系為：

x=mod（S-1，n）+0.5y=n+0.5-ceil（S/n）（1）

式（1）中，mod為求余運(yùn)算，ceil為向上取整運(yùn)算。

另外，對(duì)智能自動(dòng)駕駛汽車(chē)運(yùn)行環(huán)境和智能自動(dòng)駕駛汽車(chē)本身做出如下假設(shè)：

①智能自動(dòng)駕駛汽車(chē)是長(zhǎng)方形的，其最大尺寸為D，規(guī)劃時(shí)不考慮智能自動(dòng)駕駛汽車(chē)的高度；

②環(huán)境中障礙物的位置信息及智能自動(dòng)駕駛汽車(chē)的起始點(diǎn)和目標(biāo)點(diǎn)位置全部已知，不存在動(dòng)態(tài)障礙物。

③將已知的靜態(tài)障礙物邊界向外擴(kuò)展D/2，則智能自動(dòng)駕駛汽車(chē)可用其中心點(diǎn)來(lái)表示，在規(guī)劃過(guò)程中作為質(zhì)點(diǎn)考慮。

2.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)不僅反映了各條路徑的優(yōu)劣程度，而且對(duì)算法的收斂和穩(wěn)定性都有較大的影響，此處適應(yīng)度函數(shù)F以路徑總長(zhǎng)度的倒數(shù)作為評(píng)價(jià)標(biāo)準(zhǔn)，如下所示：

F=■（2）

式中n為該個(gè)體通過(guò)的柵格數(shù)目總數(shù)，di，i+1為節(jié)點(diǎn)i和節(jié)點(diǎn)i+1之間的歐氏距離。

2.3 遺傳操作

2.3.1 選擇操作

選擇操作的設(shè)計(jì)目的在于保留好的基因個(gè)體，從而提高種群的質(zhì)量。目前，常用的方法包括錦標(biāo)賽選擇法、輪盤(pán)賭法、最佳個(gè)體保留法和基于排序的選擇法，然而不同的選擇方法將會(huì)導(dǎo)致不同的選擇壓力，若選擇壓力較大，種群的多樣性迅速減少，算法易出現(xiàn)早熟收斂現(xiàn)象；若選擇壓力過(guò)小，雖然可以維持種群的多樣性，增大搜索到全局最優(yōu)解的概率，但是又使得算法趨于隨機(jī)搜索狀態(tài)；因此，選擇壓力對(duì)算法的性能具有重要作用。

2.3.2 交叉、變異操作

交叉操作選用單點(diǎn)交叉方法，由于路徑的不同而導(dǎo)致個(gè)體長(zhǎng)度的不同，因此，對(duì)于所選擇的兩個(gè)個(gè)體，其交叉點(diǎn)的位置不一定相同，這里選取相同序號(hào)點(diǎn)處進(jìn)行交叉（除S和G外），以保證路徑的連續(xù)性。如果兩個(gè)體具有相同序號(hào)的點(diǎn)不止一個(gè)，則任選其一進(jìn)行交叉，如果無(wú)相同序號(hào)點(diǎn)，不進(jìn)行交叉操作。交叉操作結(jié)束后，首先判斷其子代中的每個(gè)個(gè)體是否包含相同序號(hào)點(diǎn)，若包含，則應(yīng)刪除相同點(diǎn)其中之一及其中間部分。

在變異過(guò)程中，由于所產(chǎn)生的初始種群均為連續(xù)路徑，若采用隨機(jī)變異操作將會(huì)產(chǎn)生間斷路徑，導(dǎo)致種群質(zhì)量退化，為克服這一缺陷，本文采取對(duì)待變異個(gè)體隨機(jī)刪除一點(diǎn)（除S和G外），并把該點(diǎn)所在柵格標(biāo)記為靜態(tài)障礙物，再判斷該個(gè)體是否為間斷路徑，如果是間斷路徑，則采用種群初始化的方法修補(bǔ)間斷路徑，以保證變異后路徑的連續(xù)性。

3 實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證算法的正確性和合理性，本文運(yùn)用Matlab軟件在10×10的柵格環(huán)境模型下對(duì)該算法進(jìn)行仿真，并與基本遺傳算法進(jìn)行比較。在基本遺傳算法中，初始種群隨機(jī)生成，選擇算子采用輪盤(pán)賭法，算法的主要控制參數(shù)；在本文算法中的主要控制參數(shù)設(shè)置。其中S和G分別表示起始點(diǎn)和目標(biāo)點(diǎn)。

通過(guò)多次實(shí)驗(yàn)，該算法在一般環(huán)境下的路徑規(guī)劃問(wèn)題，具有較快的收斂速度，能夠以很大的概率收斂到全局最優(yōu)解；對(duì)于復(fù)雜環(huán)境下的路徑規(guī)劃，雖然收斂速度有所減慢，但最終也能夠收斂于全局最優(yōu)或近似最優(yōu)解。

本文的計(jì)算方法獲得了較好的軌跡。（表2）

4 總結(jié)

本文為了解決智能自動(dòng)駕駛汽車(chē)的軌跡優(yōu)化問(wèn)題，首先采用柵格法建立自動(dòng)駕駛汽車(chē)的工作環(huán)境空間，然后利用遺傳算法對(duì)其進(jìn)行優(yōu)化，獲得了較好的運(yùn)行軌跡。

參考文獻(xiàn)：

[1]王藝帆.自動(dòng)駕駛汽車(chē)測(cè)試體系與現(xiàn)狀探究[J].汽車(chē)與安全，2016（10）.

[2]董長(zhǎng)印.自動(dòng)駕駛汽車(chē)下匝道路徑優(yōu)化控制策略研究[D].東南大學(xué)，2016.

[3]張星.基于麥克納姆輪的全向AGV運(yùn)動(dòng)控制技術(shù)研究[D].重慶大學(xué)，2016.