智能自動駕駛汽車的軌跡優化

李曉芳++何俊

摘要： 智能自動化駕駛技術是一門新興的技術，在汽車自動駕駛的過程中，如何讓汽車避開障礙物并以最短的路徑到達指定的位置，是智能自動化駕駛汽車的關鍵性問題。本文通過模擬智能自動駕駛汽車的運行環境，利用遺傳算法對汽車的運行軌跡進行研究，實驗證明可以獲得較好的結果。

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.

關鍵詞： 智能自動駕駛汽車；遺傳算法；軌跡優化

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

中圖分類號：U471.1 文獻標識碼：A 文章編號：1006-4311（2017）21-0129-02

0 引言

自動駕駛汽車又稱無人駕駛汽車、電腦駕駛汽車或輪式移動機器人，是一種通過電腦系統實現無人駕駛的智能汽車。自動駕駛汽車技術的研發，在20世紀也已經有數十年的歷史，于21世紀初呈現出接近實用化的趨勢。自動駕駛汽車依靠人工智能、視覺計算、雷達、監控裝置和全球定位系統協同合作，讓電腦可以在沒有任何人類主動的操作下，自動安全地操作機動車輛。

全局路徑規劃是指在環境信息全部已知的情況下，為智能自動駕駛汽車規劃一條無碰最優路徑。由于常用路徑規劃方法均存在一定的局限性，因此，目前智能自動駕駛汽車路徑規劃問題的研究重點在于尋求一些更加有效的求解方法或者在已有方法的基礎上進行改進，以使其能夠更好地解決路徑規劃問題。

1 遺傳算法的基本理論

遺傳算法的核心思想是借用遺傳學中的思想以及達爾文進化論的“物競天擇，適者生存”，最早由美國密歇根大學的John Holland教授于1975年提出的，1989年，Goldberg在其著作中對遺傳算法進行了更為全面和系統的總結，并由此奠定了遺傳算法的基礎。遺傳算法是從某一初始解集出發，采用一個評價函數（也稱為適應度函數）來評價每個個體的優劣，即個體對環境的適應程度，用作以后遺傳操作的依據，經過選擇、交叉和變異等遺傳操作產生新一代的種群，然后對新的一代重復遺傳操作，經過一定次數的迭代之后，最終收斂到問題的最優解或次優解。

2 自動駕駛汽車路徑規劃方法

2.1 環境模型的建立

環境建模是實現路徑規劃的基礎，其目的是將實際的物理空間映射成算法能夠處理的抽象空間。合理的環境模型有利于計算機存儲、處理和更新以及減少搜索量。目前常用的環境建模方法主要包括：可視圖法、柵格法、自由空間法和拓撲法，其中柵格法是使用較為成功的一種環境建模方法，本文將采用柵格法建立環境模型。

在A中建立直角坐標系XOY，其中坐標原點設在A區域的左下角，且和分別是在Xmax、Ymax軸上的最大值，對X，Y以智能自動駕駛汽車能自由運動的最大活動范圍Ra為步長分別進行劃分，由此形成工作柵格，其中每行的柵格數m=ceil（Xmax/Ra），每列的柵格數n=ceil（Ymax/Ra），最終構成一個m×n的柵格矩陣。假設環境中存在k個障礙物，則每個障礙物obi（i=1，2…，k）占一個或多個柵格，當不滿一個柵格時，按一個柵格計算。

目前關于柵格的標識方法主要有以下兩種：

①直角坐標法。

把（0，0）設為坐標原點，規定水平向右為X軸正方向，豎直向上為Y軸正方向，坐標軸上的單位長度為柵格大小，因此，任意一個柵格都可以用直角坐標（x，y）表示。

②序號法。

在建立的柵格模型中，定義從左上角開始的第一個柵格A（1，1）的序號為1，A（1，2）的序號為2，…，依次類推。

對于任意一個柵格A（a，b），其中a為在A中的行號，b為在A中的列號，都有確定的坐標（x，y）及相應的序號S與之一一對應， 在n×n的柵格環境中，柵格序號S和坐標（x，y）的關系為：

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

式（1）中，mod為求余運算，ceil為向上取整運算。

另外，對智能自動駕駛汽車運行環境和智能自動駕駛汽車本身做出如下假設：

①智能自動駕駛汽車是長方形的，其最大尺寸為D，規劃時不考慮智能自動駕駛汽車的高度；

②環境中障礙物的位置信息及智能自動駕駛汽車的起始點和目標點位置全部已知，不存在動態障礙物。

③將已知的靜態障礙物邊界向外擴展D/2，則智能自動駕駛汽車可用其中心點來表示，在規劃過程中作為質點考慮。

2.2 適應度函數

適應度函數不僅反映了各條路徑的優劣程度，而且對算法的收斂和穩定性都有較大的影響，此處適應度函數F以路徑總長度的倒數作為評價標準，如下所示：

F=■（2）

式中n為該個體通過的柵格數目總數，di，i+1為節點i和節點i+1之間的歐氏距離。

2.3 遺傳操作

2.3.1 選擇操作

選擇操作的設計目的在于保留好的基因個體，從而提高種群的質量。目前，常用的方法包括錦標賽選擇法、輪盤賭法、最佳個體保留法和基于排序的選擇法，然而不同的選擇方法將會導致不同的選擇壓力，若選擇壓力較大，種群的多樣性迅速減少，算法易出現早熟收斂現象；若選擇壓力過小，雖然可以維持種群的多樣性，增大搜索到全局最優解的概率，但是又使得算法趨于隨機搜索狀態；因此，選擇壓力對算法的性能具有重要作用。

2.3.2 交叉、變異操作

交叉操作選用單點交叉方法，由于路徑的不同而導致個體長度的不同，因此，對于所選擇的兩個個體，其交叉點的位置不一定相同，這里選取相同序號點處進行交叉（除S和G外），以保證路徑的連續性。如果兩個體具有相同序號的點不止一個，則任選其一進行交叉，如果無相同序號點，不進行交叉操作。交叉操作結束后，首先判斷其子代中的每個個體是否包含相同序號點，若包含，則應刪除相同點其中之一及其中間部分。

在變異過程中，由于所產生的初始種群均為連續路徑，若采用隨機變異操作將會產生間斷路徑，導致種群質量退化，為克服這一缺陷，本文采取對待變異個體隨機刪除一點（除S和G外），并把該點所在柵格標記為靜態障礙物，再判斷該個體是否為間斷路徑，如果是間斷路徑，則采用種群初始化的方法修補間斷路徑，以保證變異后路徑的連續性。

3 實驗結果及分析

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

通過多次實驗，該算法在一般環境下的路徑規劃問題，具有較快的收斂速度，能夠以很大的概率收斂到全局最優解；對于復雜環境下的路徑規劃，雖然收斂速度有所減慢，但最終也能夠收斂于全局最優或近似最優解。

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

4 總結

本文為了解決智能自動駕駛汽車的軌跡優化問題，首先采用柵格法建立自動駕駛汽車的工作環境空間，然后利用遺傳算法對其進行優化，獲得了較好的運行軌跡。

參考文獻：

[1]王藝帆.自動駕駛汽車測試體系與現狀探究[J].汽車與安全，2016（10）.

[2]董長印.自動駕駛汽車下匝道路徑優化控制策略研究[D].東南大學，2016.

[3]張星.基于麥克納姆輪的全向AGV運動控制技術研究[D].重慶大學，2016.