基于LiDAR場(chǎng)景建模的智能車路徑規(guī)劃*

王志強(qiáng) 胡釗政 ▲ 袁 凱 陶倩文

（1.武漢理工大學(xué)智能交通系統(tǒng)研究中心 武漢 430063；2.武漢理工大學(xué)能源與動(dòng)力工程學(xué)院 武漢 430063）

0 引 言

近年來(lái)，由于攝像頭、激光雷達(dá)等傳感器的更新?lián)Q代和大數(shù)據(jù)、人工智能等高科技在汽車領(lǐng)域的廣泛應(yīng)用，汽車智能化的程度越來(lái)越高[1]。無(wú)人駕駛智能車是基于機(jī)器人技術(shù)結(jié)合車輛工程研發(fā)設(shè)計(jì)的，涉及計(jì)算機(jī)視覺(jué)與人工智能等交叉學(xué)科，其作為新興科學(xué)技術(shù)的載體平臺(tái)，引領(lǐng)了目前科學(xué)技術(shù)的重要發(fā)展方向。

自主導(dǎo)航是智能車的一項(xiàng)最基本、最重要的功能，具體涉及到感知、決策以及控制等關(guān)鍵技術(shù)。具備感知能力，并且能夠構(gòu)建出駕駛場(chǎng)景模型，即環(huán)境地圖，是智能車實(shí)現(xiàn)自動(dòng)駕駛、自主導(dǎo)航的一個(gè)大前提。目前，用于智能車環(huán)境感知和障礙物檢測(cè)的傳感器主要包括激光雷達(dá)（LiDAR）[2]、毫米波雷達(dá)[3]、單雙目視覺(jué)[4]，以及超聲波傳感器[5]等。LiDAR基于飛行時(shí)間法原理，即激光遇到障礙物后的折返時(shí)間，計(jì)算目標(biāo)與自身的相對(duì)距離，并繪制出3D環(huán)境地圖，精度可達(dá)到厘米級(jí)別。此外，基于LiDAR的同時(shí)定位與建圖（simultaneous localization and mapping，SLAM）[6]在感知決策方面也具有非常重要的實(shí)際用途。駕駛場(chǎng)景建模是指建立智能車所處環(huán)境中的各種物體（如，障礙物、道路等）準(zhǔn)確的空間位置描述，即建立地圖[7]。地圖同樣是實(shí)現(xiàn)智能車自主導(dǎo)航的一個(gè)重要因素，發(fā)展至今，主要的地圖可以分為3類：①尺度地圖（metric map）；②語(yǔ)義地圖（semantic map）[8]；③拓?fù)涞貓D（topological map）。由于尺度地圖具有直觀明了的特點(diǎn)，因此被廣泛運(yùn)用。尺度地圖又主要包含了2種形式的地圖，即：柵格地圖（grid map）和特征地圖（feature-based map）[9]。占據(jù)柵格地圖由Elfes[10]提出并應(yīng)用于機(jī)器人感知中，目前被廣泛應(yīng)用于基于柵格法的路徑規(guī)劃研究鄰域。占據(jù)柵格地圖將環(huán)境離散化，形成了一系列相互獨(dú)立的正方形柵格，每個(gè)柵格的狀態(tài)只有自由（free）和被占據(jù)（occupied）2種狀態(tài)。對(duì)于建模環(huán)境相對(duì)穩(wěn)定不變的場(chǎng)景，占據(jù)柵格地圖的有關(guān)算法比較成熟，但是對(duì)于真實(shí)的環(huán)境（存在車輛、行人等臨時(shí)出現(xiàn)在場(chǎng)景中的障礙物），場(chǎng)景建模會(huì)存在一定的問(wèn)題[11]。

從規(guī)劃決策算法角度來(lái)看，現(xiàn)有的智能車路徑規(guī)劃算法起源于移動(dòng)機(jī)器人領(lǐng)域，然后逐漸應(yīng)用于不同環(huán)境下的智能車。移動(dòng)機(jī)器人的路徑規(guī)劃問(wèn)題是移動(dòng)機(jī)器人導(dǎo)航研究領(lǐng)域的熱點(diǎn)問(wèn)題，可以描述為：移動(dòng)機(jī)器人依據(jù)某個(gè)或某些性能指標(biāo)（如工作代價(jià)最小、行走路線最短、行走時(shí)間最短等），在運(yùn)動(dòng)空間中找到1條從起始狀態(tài)到目標(biāo)狀態(tài)、可以避開(kāi)障礙物的最優(yōu)或者接近最優(yōu)的路徑[12]。根據(jù)機(jī)器人對(duì)環(huán)境信息的掌握程度來(lái)分類，路徑規(guī)劃算法一般可以分為完全掌握地圖信息的全局路徑規(guī)劃和不完全掌握地圖信息的局部路徑規(guī)劃[13-14]。全局路徑規(guī)劃要求機(jī)器人路徑規(guī)劃前完全掌握作業(yè)環(huán)境的地圖信息，進(jìn)而規(guī)劃出1條從起始位置到目標(biāo)位置的最優(yōu)路徑。常用的全局路徑規(guī)劃算法有啟發(fā)式搜索算法，如，Dijkstra算法、A*算法等，以及各種智能算法，如：遺傳算法（genetic algorithm，GA）、蟻群算法（ant colony optimization，ACO）、粒子群優(yōu)化算法（particle swarm optimization，PSO）等；局部路徑規(guī)劃是移動(dòng)機(jī)器人在環(huán)境未知的情況下，根據(jù)傳感器的信息實(shí)時(shí)規(guī)劃出1條可通行的路徑。常用的算法包括：人工勢(shì)場(chǎng)法[15]（artificial potential field，APF）、滾動(dòng)窗口法（dynamic window approach，DWA）[16]、D*算法等。近年來(lái)，眾多研究者針對(duì)柵格環(huán)境下的路徑規(guī)劃算法進(jìn)行改進(jìn)，形成了很多啟發(fā)式搜索算法。國(guó)外方面，Likhachev[17]提出一種focussed dynamic A*lite算法（D*lite），Dakulovi?等[18]提出一種two-way D*算法（TWD*），上述2種算法主要用于環(huán)境未知的動(dòng)態(tài)場(chǎng)景，而環(huán)境已知的靜態(tài)環(huán)境下使用A*算法往往速度更快。在國(guó)內(nèi)方面，趙曉等[19]采用跳點(diǎn)搜索的方法，對(duì)A*算法加以改進(jìn)，在搜索過(guò)程中優(yōu)化搜索策略，通過(guò)篩選具有代表性的節(jié)點(diǎn)進(jìn)行擴(kuò)展，取代了原算法中對(duì)每個(gè)相鄰節(jié)點(diǎn)的操作，降低了算法的整體計(jì)算時(shí)間。辛煜等[20]將傳統(tǒng)A*算法的可搜索鄰域拓展為無(wú)限個(gè)，使得改進(jìn)后的算法可以沿任意方向進(jìn)行搜索，不僅縮短了路徑長(zhǎng)度，并且降低了轉(zhuǎn)折點(diǎn)的個(gè)數(shù)，但規(guī)劃的路徑中節(jié)點(diǎn)信息不便于儲(chǔ)存，算法在柵格環(huán)境下的適用性不好。

綜上所述全局路徑規(guī)劃在整個(gè)路徑規(guī)劃階段起著至關(guān)重要的作用，它為車輛運(yùn)動(dòng)提供了指引，為后續(xù)局部路徑規(guī)劃奠定了基礎(chǔ)。針對(duì)傳統(tǒng)算法規(guī)劃路徑消耗內(nèi)存、算法計(jì)算效率低等不足，本文通過(guò)搜索鄰域、搜索方向2個(gè)方面對(duì)傳統(tǒng)算法進(jìn)行優(yōu)化、改進(jìn)，有效提高了路徑規(guī)劃的計(jì)算效率。

1 場(chǎng)景建模及算法分析

路徑規(guī)劃問(wèn)題的核心研究?jī)?nèi)容一般包括場(chǎng)景建模方法和路徑搜索算法。本文圍繞智能車路徑規(guī)劃問(wèn)題展開(kāi)研究。

1）研究了一種基于LiDAR的智能車場(chǎng)景建模方法，實(shí)現(xiàn)了由三維激光點(diǎn)云到俯視投影的二維柵格地圖建模。

2）在柵格地圖環(huán)境下，對(duì)傳統(tǒng)A*算法進(jìn)行改進(jìn)，研究了一種自適應(yīng)搜索方向A*算法（adaptive search direction A*algorithm，ASD-A*），用于智能車全局路徑規(guī)劃，最后在虛擬柵格地圖環(huán)境和由真實(shí)場(chǎng)景生成的柵格地圖環(huán)境下進(jìn)行了實(shí)驗(yàn)驗(yàn)證。

1.1 基于LiDAR的智能車場(chǎng)景建模

場(chǎng)景建模是實(shí)現(xiàn)智能車自主導(dǎo)航的前提，場(chǎng)景地圖模型的優(yōu)劣直接影響著導(dǎo)航系統(tǒng)的整體性能。由于激光SLAM技術(shù)具有高精度、高效率的特點(diǎn)，近年來(lái)廣泛應(yīng)用于智能車定位、環(huán)境感知等領(lǐng)域，通過(guò)多傳感器信息融合來(lái)建立環(huán)境點(diǎn)云地圖的方法，已經(jīng)成為自動(dòng)駕駛等領(lǐng)域的熱門研究方向[21]。

本文研究一種基于LiDAR的智能車場(chǎng)景建模方法：主要以建模場(chǎng)景中的三維激光雷達(dá)點(diǎn)云數(shù)據(jù)為基礎(chǔ)，通過(guò)對(duì)原始點(diǎn)云數(shù)據(jù)進(jìn)行濾波、點(diǎn)云分割處理，將噪聲點(diǎn)、離群點(diǎn)濾除，并將路面點(diǎn)云去除，保留場(chǎng)景中建筑物、樹(shù)木等信息，然后把點(diǎn)云投影到XOY平面，根據(jù)XOY平面上的點(diǎn)云信息，實(shí)現(xiàn)了二維柵格地圖制作。該環(huán)節(jié)的流程圖見(jiàn)圖1。

圖1 場(chǎng)景建模流程圖Fig.1 Flowchart of scene modeling

利用車載多線激光雷達(dá)數(shù)據(jù)采集平臺(tái)進(jìn)行激光原始數(shù)據(jù)的采集見(jiàn)圖2。數(shù)據(jù)采集工作在校區(qū)某教學(xué)樓周圍的路段完成，見(jiàn)圖3。

圖2 數(shù)據(jù)采集平臺(tái)Fig.2 Data acquisition platform

圖3 數(shù)據(jù)采集區(qū)域Fig.3 Data collection area

借鑒LOAM算法[22]，首先將采集到的激光雷達(dá)數(shù)據(jù)進(jìn)行激光點(diǎn)云三維建模，建模工作在機(jī)器人操作系統(tǒng)（robot operating system，ROS）下完成，有效建圖面積約30 000 m2，其中長(zhǎng)約300 m，寬約100 m，三維激光點(diǎn)云地圖見(jiàn)圖4。

圖4 三維激光點(diǎn)云地圖Fig.4 3D LiDAR point cloud map

根據(jù)激光雷達(dá)的工作原理，距離激光雷達(dá)較遠(yuǎn)處的點(diǎn)云數(shù)據(jù)，其準(zhǔn)確性往往較差。原始數(shù)據(jù)中點(diǎn)云散布范圍過(guò)大，以及噪聲數(shù)據(jù)的存在，導(dǎo)致原始點(diǎn)云數(shù)據(jù)不能直接用于智能車路徑規(guī)劃，為了把采集到的三維激光雷達(dá)點(diǎn)云數(shù)據(jù)應(yīng)用到智能車路徑規(guī)劃中，需要對(duì)原始點(diǎn)云數(shù)據(jù)進(jìn)行預(yù)處理。在預(yù)處理中，需要將噪聲點(diǎn)、離群點(diǎn)剔除，同時(shí)還需要過(guò)濾掉場(chǎng)景中路面點(diǎn)云信息，只保留場(chǎng)景中除路面信息之外的固有靜態(tài)障礙信息，如建筑物、樹(shù)木等。

為了解決激光雷達(dá)點(diǎn)云數(shù)據(jù)散布范圍過(guò)大的問(wèn)題，采用直通濾波器過(guò)濾掉距離智能車較遠(yuǎn)處的點(diǎn)云數(shù)據(jù)，減少點(diǎn)云的數(shù)量，提高后續(xù)程序運(yùn)行的效率。針對(duì)激光雷達(dá)點(diǎn)云的三維坐標(biāo)信息，利用直通濾波器對(duì)點(diǎn)云進(jìn)行直接過(guò)濾。假設(shè)原始激光點(diǎn)云中某一點(diǎn)的坐標(biāo)pi( )xi，yi，zixi，yi，zi分 別 為 第i個(gè)點(diǎn)云的坐標(biāo)，若該坐標(biāo)滿足式（1）則該坐標(biāo)點(diǎn)被保留。

式中：X1，X2，Y1，Y2，Z1，Z2分別為激光點(diǎn)云坐標(biāo)沿X，Y和Z軸方向設(shè)定的下限和上限閾值。

本文采用Statistical Outlier Removal濾波器移除激光點(diǎn)云數(shù)據(jù)中的噪聲點(diǎn)?；邳c(diǎn)云臨近點(diǎn)距離分布，Statistical Outlier Removal濾波器計(jì)算每一個(gè)點(diǎn)到所有臨近點(diǎn)的平均距離D，設(shè)標(biāo)準(zhǔn)差倍數(shù)為Nt，若指定點(diǎn)到其m個(gè)臨近點(diǎn)的平均距離DM大于平均距離D超過(guò)Nt個(gè)標(biāo)準(zhǔn)差，那么該點(diǎn)將會(huì)被認(rèn)為是1個(gè)噪聲點(diǎn)而被去除。

在去除路面點(diǎn)云的過(guò)程中，基于高度閾值Zmin，對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行路面點(diǎn)云分割。在實(shí)驗(yàn)數(shù)據(jù)采集階段，由于激光雷達(dá)傳感器的安裝高度為1.5 m，那么場(chǎng)景中的路面高度在激光雷達(dá)坐標(biāo)系下應(yīng)該為-1.5 m，將高度閾值設(shè)為Zmin=-1.5 m。若點(diǎn)云Pi（xi，yi，zi）的Z軸高度zi滿足公式zi≥Zmin則將點(diǎn)云Pi保留，否則將其剔除經(jīng)過(guò)點(diǎn)云預(yù)處理，得到點(diǎn)云地圖見(jiàn)圖5。

圖5 處理后的點(diǎn)云地圖Fig.5 Processed point cloud map

使用基于柵格地圖的表示方法實(shí)現(xiàn)了從三維激光點(diǎn)云數(shù)據(jù)到二維俯視視角的柵格地圖構(gòu)建環(huán)節(jié)。首先，將預(yù)處理后的三維激光點(diǎn)云數(shù)據(jù)進(jìn)行XOY平面的投影處理。然后將整個(gè)XOY平面均勻地劃分為一定尺寸的柵格，本文使用的柵格尺寸為1 m×1 m，見(jiàn)圖6。接著統(tǒng)計(jì)每1個(gè)柵格的狀態(tài)，規(guī)定存在點(diǎn)云的柵格為占據(jù)狀態(tài)，不存在點(diǎn)云的柵格為自由狀態(tài)，將占據(jù)柵格用數(shù)字“1”表示，自由柵格用數(shù)字“0”表示，即

圖6 劃分柵格Fig.6 Dividing the grid

這樣便可以根據(jù)所有柵格狀態(tài)建立1個(gè)相對(duì)應(yīng)的矩陣，該矩陣的元素由“0”和“1”組成，即邏輯值矩陣Mmatirx，最終形成了以邏輯值矩陣表征地圖信息的柵格地圖，圖7為構(gòu)建柵格地圖的流程圖?；谏鲜鰣?chǎng)景建模方法，得到柵格地圖見(jiàn)圖8。

圖7 柵格地圖構(gòu)建流程Fig.7 Mapping process of grid map

圖8 柵格地圖Fig.8 Grid map

1.2 自適應(yīng)搜索方向A*算法

基于柵格環(huán)境的全局路徑規(guī)劃算法中，A*算法具有函數(shù)表達(dá)式簡(jiǎn)單、容易編程實(shí)現(xiàn)、計(jì)算量小、規(guī)劃路徑較短等特點(diǎn)，目前被廣泛應(yīng)用于機(jī)器人或智能車研究領(lǐng)域。

A*算法由Dijkstra算法發(fā)展而來(lái)，并加入啟發(fā)因子，形成了一種啟發(fā)式搜索算法[23]。它由啟發(fā)函數(shù)來(lái)評(píng)價(jià)地圖中任意節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)間的距離，根據(jù)啟發(fā)函數(shù)來(lái)選擇最優(yōu)的方向展開(kāi)搜索。A*算法的啟發(fā)函數(shù)表達(dá)式為

式中：f(n)為在當(dāng)前節(jié)點(diǎn)n時(shí)，從初始節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)的總代價(jià)函數(shù)；g(n)為從初始節(jié)點(diǎn)到達(dá)當(dāng)前節(jié)點(diǎn)n實(shí)際代價(jià)值的大??；h(n)為從當(dāng)前節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)的最小估計(jì)代價(jià)值的大小。

用來(lái)計(jì)算h(n)大小的公式主要有曼哈頓距離（Manhattan distance）和歐幾里得距離（Euclidean distance），具體的表達(dá)式為

式中：MD為曼哈頓距離；ED為歐幾里得距離；n)為當(dāng)前節(jié)點(diǎn)的坐標(biāo)；(xd，yd)為目標(biāo)節(jié)點(diǎn)的坐標(biāo)。

在路徑搜索時(shí)，算法沿著當(dāng)前節(jié)點(diǎn)的最小f(n)值所對(duì)應(yīng)的臨近節(jié)點(diǎn)進(jìn)行搜索，傳統(tǒng)A*算法的搜索方向一般為4個(gè)或8個(gè)，即沿著當(dāng)前節(jié)點(diǎn)相鄰的4個(gè)鄰域或8個(gè)鄰域展開(kāi)搜索，見(jiàn)圖9，以4鄰域搜索為例，4個(gè)方向分別為當(dāng)前節(jié)點(diǎn)的正上、正下、正左和正右方向。8鄰域搜索則是在前者的基礎(chǔ)之上增加了4個(gè)斜向方向。

圖9 搜索鄰域Fig.9 Search neighborhood

由圖9可知，在相同柵格環(huán)境下，若設(shè)定的起點(diǎn)和終點(diǎn)相同，4鄰域搜索策略在路徑搜索過(guò)程中訪問(wèn)柵格的數(shù)量要少于8鄰域搜索策略，這意味著前者在計(jì)算時(shí)間上要優(yōu)于后者。但從所規(guī)劃路線長(zhǎng)度的角度分析，8鄰域搜索策略要優(yōu)于前者。仿真實(shí)驗(yàn)在Matlab 2018a軟件平臺(tái)上進(jìn)行，圖10為2種不同搜索策略下的仿真實(shí)驗(yàn)結(jié)果。

通過(guò)上述分析可以看出，4鄰域搜索A*算法和8鄰域搜索A*算法在計(jì)算效率和規(guī)劃路線長(zhǎng)度2個(gè)方面上各有所長(zhǎng)，二者也各自都存在不足之處：①前者雖然在計(jì)算時(shí)間上優(yōu)于后者，但在規(guī)劃路線長(zhǎng)度上過(guò)長(zhǎng)；②后者雖然在規(guī)劃路線長(zhǎng)度上優(yōu)于前者，但計(jì)算時(shí)間上卻要比前者多，此外由于沿著8個(gè)方向進(jìn)行路徑搜索，其規(guī)劃出的路線難免會(huì)出現(xiàn)斜著穿過(guò)障礙物柵格某一頂點(diǎn)的現(xiàn)象，見(jiàn)圖11，對(duì)于智能車來(lái)講，這種規(guī)劃出的路徑顯然不合理，難以使智能車按照預(yù)定路線行駛。

本文從路徑規(guī)劃合理性和算法計(jì)算時(shí)間2個(gè)方面對(duì)傳統(tǒng)A*算法進(jìn)行改進(jìn)。針對(duì)傳統(tǒng)A*算法8鄰域搜索策略存在規(guī)劃路線不合理的問(wèn)題，研究了1種自適應(yīng)搜索鄰域A*算法，有效解決了該問(wèn)題，使規(guī)劃出的路徑更便于智能車的安全行駛；為縮短算法計(jì)算時(shí)間，在所提算法的基礎(chǔ)上進(jìn)行改進(jìn)，研究了一種自適應(yīng)搜索方向A*算法見(jiàn)圖11。

圖10 實(shí)驗(yàn)對(duì)比Fig.10 Experimental comparison

圖11 斜穿障礙柵格頂點(diǎn)Fig.11 Diagonally cross vertice of obstacle grid

由圖11可知，當(dāng)從節(jié)點(diǎn)n到節(jié)點(diǎn)n+1的運(yùn)動(dòng)為斜向時(shí)，如果在由上述2個(gè)節(jié)點(diǎn)所在柵格及其相鄰的2個(gè)柵格所組成的局部2×2柵格塊中存在障礙柵格，便會(huì)出現(xiàn)斜穿障礙柵格頂點(diǎn)的現(xiàn)象。如果使用4鄰域搜索策略，則可以避免該現(xiàn)象。本文結(jié)合A*算法的4鄰域搜索策略和8鄰域搜索策略，研究了一種自適應(yīng)搜索鄰域A*算法。圖12為算法流程，算法以8鄰域搜索策略為主，在從節(jié)點(diǎn)n到節(jié)點(diǎn)n+1的斜向運(yùn)動(dòng)中，算法將判斷是否存在斜穿障礙物柵格頂點(diǎn)的現(xiàn)象，如果存在該現(xiàn)象，則切換為4鄰域搜索策略，重新從節(jié)點(diǎn)n搜索路徑；否則算法將繼續(xù)以8鄰域搜索策略進(jìn)行路徑規(guī)劃。圖12為算法流程圖。

圖12 算法流程圖Fig.12 Algorithm flowchart

利用改進(jìn)后的算法進(jìn)行與圖11中相同的仿真實(shí)驗(yàn)，仿真結(jié)果見(jiàn)圖13。利用改進(jìn)算法規(guī)劃出的路徑不存在斜穿障礙柵格頂點(diǎn)的現(xiàn)象，路徑更加合理，便于智能車安全行駛。

圖13 改進(jìn)算法的實(shí)驗(yàn)結(jié)果Fig.13 Experimental results of improved algorithm

為了降低算法的計(jì)算時(shí)間，在基于自適應(yīng)搜索鄰域A*算法基礎(chǔ)上，研究了一種自適應(yīng)搜索方向A*算法，見(jiàn)圖14。

如圖14所示，ASD-A*算法將圖9中的8鄰域搜索方向劃分為8個(gè)主方向，與其相鄰的2個(gè)搜索方向共同構(gòu)成1個(gè)搜索區(qū)域。

圖14 搜索方向示意圖Fig.14 Search direction diagram

在ASD-A*中一共有8個(gè)搜索區(qū)域，每個(gè)搜索區(qū)域有1個(gè)主方向，搜索區(qū)域的范圍由與主搜索方向相鄰的2個(gè)副搜索方向所確定，即每個(gè)搜索區(qū)域包含了3個(gè)搜索方向，搜索區(qū)域可表示為

式中：SAi為搜索區(qū)域；M-Directioni為主方向。

算法根據(jù)路徑規(guī)劃的起點(diǎn)和終點(diǎn)，計(jì)算出終點(diǎn)相對(duì)于起點(diǎn)的方向Ds。然后在8個(gè)主方向中尋找到與Ds方向最接近的1個(gè)主方向，即

找到主方向后，便可確定搜索區(qū)域。

考慮到算法的搜索方向被縮減至3個(gè)后，可能會(huì)出現(xiàn)當(dāng)前節(jié)點(diǎn)被障礙柵格“包圍”而不能搜索到下1個(gè)節(jié)點(diǎn)的問(wèn)題，為克服算法的不足，將ASD-A*算法與本文提出的自適應(yīng)搜索鄰域A*算法相結(jié)合，當(dāng)不能搜索到下1節(jié)點(diǎn)時(shí)，算法將采用自適應(yīng)鄰域搜索策略跳出“包圍”，最終返回到ASD-A*算法。仿真實(shí)驗(yàn)采用圖13中的柵格地圖、起點(diǎn)和終點(diǎn)，實(shí)驗(yàn)結(jié)果見(jiàn)圖15。

從實(shí)驗(yàn)結(jié)果可知，ASD-A*算法規(guī)劃出的路徑與自適應(yīng)搜索鄰域A*算法規(guī)劃的路徑一致，但算法所訪問(wèn)的柵格數(shù)量明顯減少，對(duì)應(yīng)計(jì)算時(shí)間將降低。

2 實(shí)驗(yàn)與分析

2.1 虛擬柵格地圖環(huán)境下的實(shí)驗(yàn)

場(chǎng)景建模階段的地圖是以柵格法得到的，柵格地圖的規(guī)模與實(shí)際場(chǎng)景的大小以及所采用的柵格尺寸三者之間密切相關(guān)。當(dāng)建模場(chǎng)景固定時(shí)，合適的柵格尺寸對(duì)于真實(shí)場(chǎng)景的準(zhǔn)確表示是至關(guān)重要的，而柵格尺寸的大小又直接影響著整個(gè)柵格地圖的規(guī)模，若使用較小的柵格尺寸，那么柵格地圖的整體精度將會(huì)提高，但柵格地圖的規(guī)模必然會(huì)呈現(xiàn)出“指數(shù)性”的增長(zhǎng)；當(dāng)建模場(chǎng)景較大時(shí)，在保證地圖精度的前提下，柵格地圖的規(guī)模也同樣會(huì)比較大。此時(shí)算法的計(jì)算量將會(huì)大幅度地增加，算法的計(jì)算效率將相應(yīng)地下降，難以保證較高的實(shí)時(shí)性。此外，在較為簡(jiǎn)單的場(chǎng)景中，障礙物往往比較少，與之相對(duì)應(yīng)的障礙柵格在柵格地圖中的占有率（本文稱作：障礙柵格占有率）也比較小；在復(fù)雜的場(chǎng)景中，障礙物的數(shù)量一般比較多且密集，在對(duì)應(yīng)的柵格地圖中，障礙柵格占有率也比較高。而障礙柵格占有率的大小顯然會(huì)影響到算法的整體性能。通過(guò)上述分析可知，柵格地圖的規(guī)模和障礙柵格占有率這2個(gè)因素影響著路徑規(guī)劃算法的整體性能。

圖15 實(shí)驗(yàn)結(jié)果Fig.15 Experimental results

為了充分驗(yàn)證ASD-A*算法的整體性能，本節(jié)從柵格地圖規(guī)模和障礙柵格占有率2個(gè)方面，在虛擬柵格地圖環(huán)境下進(jìn)行仿真實(shí)驗(yàn)，利用控制變量的方法分別對(duì)上述2個(gè)方面進(jìn)行研究，選取了傳統(tǒng)4鄰域搜索A*算法、傳統(tǒng)8鄰域搜索A*算法、自適應(yīng)搜索鄰域A*算法以及自適應(yīng)搜索方向A*算法4種算法進(jìn)行了仿真對(duì)比試驗(yàn)，仿真實(shí)驗(yàn)在Matlab 2018a軟件平臺(tái)上進(jìn)行。

2.1.1 不同規(guī)模柵格地圖下的實(shí)驗(yàn)

選取傳統(tǒng)4鄰域搜索A*算法、8鄰域搜索A*算法、自適應(yīng)搜索鄰域A*算法以及ASD-A*算法4種算法進(jìn)行了20組仿真實(shí)驗(yàn)，并采用了5種不同規(guī)模的虛擬柵格地圖環(huán)境（20×20，40×40，60×60，80×80和100×100，柵格尺寸為1 m×1 m），在每種柵格地圖環(huán)境下均進(jìn)行4組實(shí)驗(yàn)，最后統(tǒng)計(jì)了實(shí)驗(yàn)結(jié)果。表1列出了實(shí)驗(yàn)結(jié)果的統(tǒng)計(jì)信息。其中，1～4組實(shí)驗(yàn)的柵格規(guī)模為20×20；5～8組實(shí)驗(yàn)的柵格規(guī)模為40×40；9～12組實(shí)驗(yàn)的柵格規(guī)模為60×60；13～16組實(shí)驗(yàn)的柵格規(guī)模為80×80；17～20組實(shí)驗(yàn)的柵格規(guī)模為100×100。圖16～18為從訪問(wèn)柵格、規(guī)劃路線長(zhǎng)度和算法計(jì)算時(shí)間3個(gè)方面對(duì)4種算法的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比分析的結(jié)果。

表1 對(duì)比實(shí)驗(yàn)結(jié)果Tab.1 Results of comparative experiment

圖16 訪問(wèn)柵格數(shù)對(duì)比Fig.16 Comparison of the number of access grids

圖17 規(guī)劃路線長(zhǎng)度對(duì)比Fig.17 Comparison of planned route lengths

圖18 計(jì)算時(shí)間對(duì)比Fig.18 Comparison of calculation time

從對(duì)比結(jié)果可以看出，隨著柵格地圖規(guī)模的增大，4種算法在訪問(wèn)柵格數(shù)量和規(guī)劃路線長(zhǎng)度方面整體上均呈現(xiàn)上升趨勢(shì)，但ASD-A*算法在每一次路徑規(guī)劃過(guò)程中所訪問(wèn)的柵格數(shù)量遠(yuǎn)小于其他3種算法，且在規(guī)劃路線長(zhǎng)度方面基本與傳統(tǒng)A*算法（8鄰域搜索）和自適應(yīng)鄰域搜索A*算法相持平；在算法計(jì)算時(shí)間方面，ASD-A*算法整體上明顯比其他3種算法要少。這說(shuō)明ASD-A*算法將搜索方向縮小至3個(gè)時(shí)，避免了一些不必要的計(jì)算量，使算法的計(jì)算時(shí)間縮短，提升了算法的計(jì)算效率。

2.1.2 不同障礙柵格占有率下的實(shí)驗(yàn)

在同一規(guī)模的柵格地圖環(huán)境下進(jìn)行了20組仿真實(shí)驗(yàn)，柵格地圖規(guī)模設(shè)置為：40×40，并采用了5種不同的障礙柵格占有率，分別為：20%，25%，30%，35%和40%。柵格尺寸均設(shè)置為：1 m×1 m，在每種柵格地圖環(huán)境中均進(jìn)行4組實(shí)驗(yàn)，圖19～21為對(duì)比分析結(jié)果。

圖19 訪問(wèn)柵格數(shù)對(duì)比Fig.19 Comparison of the number of access grids

圖20 規(guī)劃路線長(zhǎng)度對(duì)比Fig.20 Comparison of planned route lengths

圖21 計(jì)算時(shí)間對(duì)比Fig.21 Comparison of calculation time

從對(duì)比結(jié)果可以看出，在柵格地圖規(guī)模固定的前提下，隨著地圖中障礙柵格數(shù)量的增加，4種算法在進(jìn)行路徑規(guī)劃時(shí)所訪問(wèn)的柵格數(shù)量和規(guī)劃路線長(zhǎng)度整體上均呈現(xiàn)上升趨勢(shì)，其中傳統(tǒng)A*算法（8鄰域搜索）和自適應(yīng)搜索鄰域A*算法在每一次路徑規(guī)劃過(guò)程中訪問(wèn)的柵格數(shù)量較多，傳統(tǒng)A*算法（4鄰域搜素）次之，而ASD-A*算法則遠(yuǎn)小于其他3種算法；且ASD-A*算法在規(guī)劃路線長(zhǎng)度方面基本與傳統(tǒng)A*算法（8鄰域搜索）和自適應(yīng)鄰域搜索A*算法相持平；在算法計(jì)算時(shí)間方面，ASD-A*算法整體上明顯比其他3種算法要少。

2.1.3 綜合分析

前文利用控制變量的思想，分別從柵格地圖規(guī)模和障礙柵格占有率2個(gè)方面對(duì)4種算法進(jìn)行了仿真實(shí)驗(yàn)。從定性分析來(lái)看，本文所提出的ASD-A*算法較之其他3種算法具有較高的計(jì)算效率，且路徑規(guī)劃長(zhǎng)度相對(duì)較短。為了更加清晰地研究所提算法的整體性能，對(duì)表1中的實(shí)驗(yàn)數(shù)據(jù)采用定量分析的方法做進(jìn)一步的分析。將40組實(shí)驗(yàn)數(shù)據(jù)取平均值，表2統(tǒng)計(jì)了算法在訪問(wèn)柵格數(shù)量、規(guī)劃路徑長(zhǎng)度和計(jì)算時(shí)間3個(gè)方面的信息。

表2 實(shí)驗(yàn)數(shù)據(jù)平均值Tab.2 Average of experimental data

由表2可見(jiàn)，相較于傳統(tǒng)A*算法（4鄰域搜索），ASD-A*算法在訪問(wèn)柵格數(shù)量方面降低了約39.2%，在路徑長(zhǎng)度方面降低了約15.5%，在計(jì)算時(shí)間上降低了約38.2%；對(duì)比傳統(tǒng)A*算法（8鄰域搜索），ASD-A*算法在訪問(wèn)柵格數(shù)量和計(jì)算時(shí)間上分別降低了約54.5%和47.2%，雖然在路徑長(zhǎng)度方面略高于前者，但融合了自適應(yīng)搜索鄰域A*算法后，ASD-A*算法規(guī)劃出的路線更加合理，便于智能車安全行駛。綜上所述，通過(guò)仿真實(shí)驗(yàn)可以證明本文提出的ASD-A*算法具有良好的適用性，能夠在多種規(guī)模和不同障礙柵格占有率的柵格環(huán)境下保持良好的整體性能。

2.2 真實(shí)柵格地圖環(huán)境下的實(shí)驗(yàn)

根據(jù)上述虛擬柵格環(huán)境下的實(shí)驗(yàn)結(jié)果分析，可以看出，本文所提出的ASD-A*算法較之傳統(tǒng)A*算法具有計(jì)算效率高、規(guī)劃路線更加合理的優(yōu)點(diǎn)。為了進(jìn)一步驗(yàn)證該算法在真實(shí)柵格地圖環(huán)境下的整體性能，在圖22所示的真實(shí)柵格地圖環(huán)境下，分別選取不同的路徑規(guī)劃起點(diǎn)和終點(diǎn)，進(jìn)行了5組實(shí)驗(yàn)測(cè)試。圖22所示場(chǎng)景為1.1節(jié)中所對(duì)應(yīng)的建模場(chǎng)景。其中，柵格尺寸為：1 m×1 m。表3統(tǒng)計(jì)了相關(guān)實(shí)驗(yàn)數(shù)據(jù)。

圖22 真實(shí)柵格地圖下的實(shí)驗(yàn)Fig.22 Experiments on real grid map

表3 實(shí)驗(yàn)數(shù)據(jù)Tab.3 Experimental data

可以看出，ASD-A*算法在5組實(shí)驗(yàn)中所規(guī)劃的路徑長(zhǎng)度最短為63.885 m，最長(zhǎng)為157.059 m，算法計(jì)算時(shí)間最短為2.379 ms，最長(zhǎng)為3.71 ms。算法在真實(shí)柵格地圖環(huán)境下所表現(xiàn)出的整體性能與虛擬柵格地圖環(huán)境下基本一致。

3 結(jié)束語(yǔ)

針對(duì)智能車自主導(dǎo)航問(wèn)題，圍繞智能車路徑規(guī)劃問(wèn)題展開(kāi)研究工作。①研究了一種基于LiDAR的智能車場(chǎng)景建模方法，將數(shù)據(jù)量較大的三維激光點(diǎn)云進(jìn)行“降維”處理，以二維柵格地圖來(lái)表示智能車駕駛場(chǎng)景；②對(duì)傳統(tǒng)A*算法進(jìn)行改進(jìn)，運(yùn)用4鄰域、8鄰域自適應(yīng)搜索策略優(yōu)化了傳統(tǒng)算法斜穿障礙柵格頂點(diǎn)的不合理路線，所提出的自適應(yīng)搜索方向A*算法（ASD-A*）在計(jì)算時(shí)間上較之傳統(tǒng)A*算法（8鄰域搜索）降低了47.2%，很大程度上提升了計(jì)算效率。通過(guò)仿真實(shí)驗(yàn)可以證明，本文提出的自適應(yīng)搜索方向A*算法具有良好的適用性，能夠在多種規(guī)模和不同障礙柵格占有率的柵格環(huán)境下保持良好的整體性能。

此外，本文的研究工作也存在一些不足之處，如：①由于實(shí)驗(yàn)條件有限，本文的場(chǎng)景建模工作是在校區(qū)內(nèi)進(jìn)行的，后期將嘗試在物流園區(qū)、港口碼頭等適合智能車應(yīng)用的場(chǎng)景進(jìn)行場(chǎng)景建模工作；②僅研究一種路徑規(guī)劃算法，未來(lái)將考慮結(jié)合2種或2種以上的算法，嘗試研究路徑規(guī)劃融合算法。