王志強 胡釗政 ▲ 袁 凱 陶倩文

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

0 引 言

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

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

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

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

1 場景建模及算法分析

路徑規(guī)劃問題的核心研究內容一般包括場景建模方法和路徑搜索算法。本文圍繞智能車路徑規(guī)劃問題展開研究。

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

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

1.1 基于LiDAR的智能車場景建模

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

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

圖1 場景建模流程圖Fig.1 Flowchart of scene modeling

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

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

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

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

圖4 三維激光點云地圖Fig.4 3D LiDAR point cloud map

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

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

式中：X1，X2，Y1，Y2，Z1，Z2分別為激光點云坐標沿X，Y和Z軸方向設定的下限和上限閾值。

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

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

圖5 處理后的點云地圖Fig.5 Processed point cloud map

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

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

這樣便可以根據(jù)所有柵格狀態(tài)建立1個相對應的矩陣，該矩陣的元素由“0”和“1”組成，即邏輯值矩陣Mmatirx，最終形成了以邏輯值矩陣表征地圖信息的柵格地圖，圖7為構建柵格地圖的流程圖。基于上述場景建模方法，得到柵格地圖見圖8。

圖7 柵格地圖構建流程Fig.7 Mapping process of grid map

圖8 柵格地圖Fig.8 Grid map

1.2 自適應搜索方向A*算法

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

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

式中：f(n)為在當前節(jié)點n時，從初始節(jié)點到達目標節(jié)點的總代價函數(shù)；g(n)為從初始節(jié)點到達當前節(jié)點n實際代價值的大?。籬(n)為從當前節(jié)點n到達目標節(jié)點的最小估計代價值的大小。

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

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

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

圖9 搜索鄰域Fig.9 Search neighborhood

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

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

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

圖10 實驗對比Fig.10 Experimental comparison

圖11 斜穿障礙柵格頂點Fig.11 Diagonally cross vertice of obstacle grid

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

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

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

圖13 改進算法的實驗結果Fig.13 Experimental results of improved algorithm

為了降低算法的計算時間，在基于自適應搜索鄰域A*算法基礎上，研究了一種自適應搜索方向A*算法，見圖14。

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

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

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

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

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

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

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

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

2 實驗與分析

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

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

圖15 實驗結果Fig.15 Experimental results

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

2.1.1 不同規(guī)模柵格地圖下的實驗

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

表1 對比實驗結果Tab.1 Results of comparative experiment

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

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

圖18 計算時間對比Fig.18 Comparison of calculation time

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

2.1.2 不同障礙柵格占有率下的實驗

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

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

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

圖21 計算時間對比Fig.21 Comparison of calculation time

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

2.1.3 綜合分析

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

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

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

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

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

圖22 真實柵格地圖下的實驗Fig.22 Experiments on real grid map

表3 實驗數(shù)據(jù)Tab.3 Experimental data

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

3 結束語

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

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