基于分層PSO的智能車輛超車路徑規劃

尹 華，吳君華

（1.江蘇農林職業技術學院，江蘇 句容 212400；2.南京林業大學，江蘇 南京 210037）

1 引言

弗吉尼亞理工大學的在自動駕駛方面的研究報告表明[1]，如今智能車輛的安全性和舒適性超過人類平均駕駛水平，未來智能車輛的應用將越來越廣泛，智能車輛的研究需求越來越高。而超車問題是自動駕駛的重要環節，這里針對超車過程的路徑規劃展開研究。

在已有的路徑規劃方法中，著名的經典方法包括單元格分解法[2]，人工勢場法[3]，道路圖法[4]和子目標法[5]。經典方法能夠生成路徑規劃，但是路徑的評價函數與路徑生成本身關聯不緊密，需要研究人員根據實際情況調整路徑規劃的方案。相比而言，啟發式方法能夠將路徑的評價指標同路徑的生成過程緊密連接起來，其包括神經網絡方法[6]，模糊邏輯[7]以及遺傳算法[8]和粒子群算法[9]。當路徑的適用環境改變時，可通過改變約束函數組或者目標函數生成新的規劃路徑。

超車換道的路徑規劃本質上可以轉化為是一個帶有約束的目標優化問題。由于車輛本身具有不同特性，道路約束，法規約束和安全等級等影響因素很多，因此沒有限定的“最佳路徑”是一個不精確的表達方式。但它可以集中體現在幾個方面，例如安全性、超車路程和能量消耗等方面。

到目前為止，純粹優化的方法并不能完美地解決智能車輛路徑規劃問題。有的耗時太長，有的不能計算出規劃路徑。因此，研究人員需要綜合不同的方法，提高算法的可靠性。幾位研究學者[10-12]已經探討了采用分層結構來解決這一類問題的思路。在不同的層級中應用多種算法，不僅可有效地降低算法的復雜度，而且所得出的軌跡更加可靠。

針對智能車超車問題，提出了多層粒子群優化的路徑規劃方法。首先，深入分析了智能車輛超車變道過程中的各個影響因素，進而建立數學模型。其次，基于模型構造出粒子群優化方法需要的約束函數和優化目標。再次，針對粒子群優化方法存在的問題，設計分層結構提高初始粒子的準確性，并采用Pareto優先原則加速收斂過程。最后，通過CarSim和Matlab混合仿真驗證了該方法優化路徑的可行性。第二節通過分析各個影響要素建立雙車道車輛超車模型，第三節構造了分層結構的路徑規劃粒子群優化方法，第四節介紹了CarSim和Matlab的仿真效果。最后一節總結全文并提出了幾點展望。

2 雙車道車輛超車模型

超車換道的基本動作流程共有五種[3]，超車準備，前超車過渡，超車實施，后超車過渡，超車結束階段。通過分析超車換道的基本動作流程，得知超車準備中超車換道空間是超車規劃中的關鍵，如圖1所示。超車空間的確定需要考慮的安全、車輛、道路等基本要素，以及各個要素的相互約束關系。規劃的路徑不僅要符合車輛動力學的基礎上，而且確保安全避開其他車輛，還能夠滿足實際道路的約束。在后面的討論中，統一道路的坐標方向，其中前進方向設為X方向，側向設為Y。

圖1 超車換道空間示意圖Fig.1 Schematic Diagram of Overtaking Lane Change

2.1 約束條件分析

車輛自身動力學約束在確保安全、平穩同時，車輛加速度波動越低，乘客的舒適性體驗越高。

式中：—M1的質點在橫向的加速度—M1和M2的質點處縱向速度；Vmax—道路限速；ɑy，max—車輛最大側向加速度。

2.2 超車安全距離分析

超車車輛M1在行駛過程中，當因前方車輛M2速度低而采取超車換道行為時，兩者可能發生的碰撞為斜向碰撞。保證兩車不發生碰撞的條件[13]為：

式中：xM1(t)、x M2(t)—車輛M1、M2經過時間t的縱向位移；c—車輛M1的寬度；θ—t時刻車輛M1車身與車道線之間的夾角；t≤tɑdj為時間；tɑdj—車輛M1側向轉彎的時刻。

由可知，確保M1和M2不發生任何情況下的碰撞的最小安全距離Dmin為：

式中：(0)、(0)—換道開始時車輛M1和M2的縱向速度；(t)、(t)—換道過程中車輛M1和M2在t時刻的縱向加速度；η—時間。

3 分層粒子群的超車路徑規劃

多目標粒子群優化的基礎思想來源于單目標粒子群優化方法，兩者都關心的核心問題是初值和更新算法。

3.1 單目標粒子群優化

PSO算法首先由文獻［14］提出來解決單目標優化問題。假設維數為N的搜索空間D?RN中，第i個粒子的位置和速度分別為xi=(xi1，xi2，…，xiN)∈D和vi=(vi1，vi2，…，viN)∈D。根據兩個因素，激勵粒子更新位置，并朝全局最優值收斂的因素有兩個：（1）該粒子本身最優位置（Pb）和（2）全體粒子群的最佳位置（Gb）。第一項為局部極值，表示為Pbi(t)=[Pbi1(t)，Pbi2(t)，…，PbiN(t)第二項為全局極值，并表示為Gb(t)=[Gb1(t)，Gb2(t)，…，GbN(t)在第t+1次搜索中，速度和位置的更新關系為：

式中：w—慣性重量；c1、c2—兩個非負常數，通稱為加速因子；r1、r2—［0，1］中的隨機數。

基本的PSO算法只能解決連續解空間的單目標優化問題，并且算法本身收斂比較慢。因此，基本粒子群算法不適用于解決這里的問題。針對上述兩個問題，設計多層結構，通過在不同的層級中單獨解決問題，從而實現多目標粒子群快速優化，最終完成超車路徑規劃的任務。

3.2 多層路徑規劃設計

為實現路徑規劃的目的，對實際問題分解為三個層面的小問題。第一層主要是確定障礙的邊界。對M2而言，根據車輛的危險等級系數ζ，對超車最小車距ζDmin適當調整。對道路而言，根據車輛自身的寬度c確定，確定邊界寬度。應用三角分解法快速得到智能汽車安全運行的空間。第二層是采用Dijkstra算法在第一層的得到的空間中獲取一條軌跡。第三層則是采用基于Pareto原則加速的多目標PSO算法，尋找最優路徑。具體處理步驟，如圖2所示。

圖2 多層PSO路徑規劃的結構Fig.2 Structure of Multi-Layer PSO Path Planning

3.2.1 三角分解

單元分解法是路徑規劃中常用的方法[10]，其具體是將可活動空間劃分為相同幾何類型的多邊形區域。典型的形狀主要有梯形、三角形、多邊形和矩形。該文獻研究了單元分解中不同幾何類型的實現路徑規劃的效果和計算復雜度，指出三角分解方法具有高魯棒性，低復雜度，并且可行路徑比例高等優點。因此在第一層應用三角分解法取得一個可行路徑。

通常三角分解法的輸入為可行空間C［28］，而輸出為三角形單元集合C={c1，c2，…cm}和各個單元相臨邊的集合。與一般的靜態路徑規劃不同，超車變道路徑規劃的三角分解與所規劃路徑具有耦合關系，虛線的M1是指最終達到的位置。具體，如圖3所示。

圖3 規劃路徑與三角分解方法耦合Fig.3 Coupling of Planning Path and Triangulation Method

3.2.2 Dijkstra算法

Dijkstra算法的核心思想[29]是根據三角分解的結果，規劃出M1經歷的所有的相連三角單元，在每三角單元中選取距離最近兩個點（也即是邊的中點）作為軌跡，各點連接起來作為總體的軌跡。

3.2.3 基于約束的多目標PSO

前文已經假設，每一個粒子的狀態就代表了一條路徑。第三層的主要目標就是通過設計PSO算法，在迭代更新中，求出在約束條件下目標函數的最優值。通過分析雙車道車輛超車模型，提出一種基于模型約束的多目標PSO。關于約束和算法的詳情說明在第四節中。

3.3 多目標粒子群算法

多目標粒子群的基本要素也是粒子空間和目標函數。與單目標粒子群算法的不同之處有兩點，第一是考慮約束條件。實際上，通過超車模型的分析得出的約束有多種類型，比如邊界約束，不可以作為目標函數進行優化，只能單獨在粒子狀態更新中作為零和條件，避免規劃的路徑出現在邊界以外。第二是需要優化的目標函數不僅有多個，而且在不同階段之間還要變化。

3.3.1 搜索空間

假定車輛前進的速度是保持不變的，那么在每一個時刻核心的控制因素就是轉角。于是可以考慮每一個粒子是一組不同時刻的轉角序列θ={θ1，θ2，…θN}。一個粒子中，每一個元素θi，就可以確定當前時刻的車輛速度：

進而通過速度的積分求解路徑各個位置的坐標可以表達為：

式中：Δt—時刻間隔；—M1的速度。由上可知，這樣的粒子定義可以完全表達路徑。

3.3.2 目標函數

對智能車輛而言，規劃路徑距離車輛和道路邊界的距離越遠，車輛就越安全，出現意外發生故障的概率也就越低。在此基礎上，還需要追求規劃路徑具有最短的路徑長度，從而提高行車效率，縮短車輛占用超車道路的時間。此外，在考慮外部環境意外，還需要提高乘客的體驗，規劃的路徑加速度需要滿足平滑性的要求，越平穩越好。綜合上述考慮，將安全性、路徑長度和舒適性作為優化的目標函數。

為了避免矩形模型的復雜計算過程，將障礙車模型構造為橢圓形狀，如圖4所示。這樣計算過程可以通過橢圓的性質得以簡化。根據超車模型，橢圓的長邊距為安全距離ζDmin。根據道路安全法規，M1應該在與M2不同的車道超車，則短邊距為M2與車道邊的寬度1/2(H-c)。在超車過渡時間段內，t∈(t0，t0+tɑdj)，其中，超車起始時刻滿足的條件為-ζDmin，M1與M2平行的時刻滿足條件為＜ε，ε為給定的一個小正數。軌跡的避障目標函數為：

圖4 M2的橢圓距離模型Fig.4 Elliptical Distance Model of M2

其中，橢圓焦點的位置分別M2平行質心的(-，0)和(-d2，0)處，且M2的位置為：

路徑的長度與時刻有關系，那么對于超車結束過渡階段t∈(t0+tɑdj，NΔt)：

3.3.3 約束函數

如圖5所示，在分析三角分解方法給出的可行軌跡空間，得到粒子空間的上邊界序列UB和下邊界序列LB。

圖5 路徑的上下邊界Fig.5 Upper and Lower Boundaries of the Path

另外從安全分析，在t∈(t0+tɑdj，t1)時，強制要求：

才進入超車結束過渡階段。

3.4 生成規劃軌跡

一般的多目標優化方案通常采用各個目標加權的線性組合方式，但是這樣的方式常常使目標優化的結果很大程度依賴于加權系數，造成計算的優化結果與真實的最優存在很大差別。而在這里的優化中，采用帕累托最優方法，通過計算違約函數確定方案的優先順序。違約函數為：

粒子群的進化公式為：

其中，局部優化參數c0∈[0.1，0.5]，收斂底數γ∈(0，1)，rand(LB，UB)為隨機參數，全局優化參數c2∈[0.1，0.7]，Gb(t)為當前粒子群中優先級最高的粒子狀態。

4 路徑跟蹤仿真模型

利用CarSim的模型檢驗這里方法獲得的優化路徑。在Car-Sim8.10軟件中構建模型，詳細參數，如表1所示。利用Matlab2014a的Simulink將模型導入，同時在Simulink控制器模塊編寫分層PSO算法生成路徑和目標函數的代碼，如圖6所示。使用Simulink的函數模塊和常數生成器為CarSim的Simulink模塊提供M1、M2速度和M1的轉角序列。CarSim模塊計算的位移等情況，通過示波器顯示出來。其中，M1、M2位置和轉動角度作為控制器的輸入送入Simulink控制器中，通過目標函數判斷當前路徑的優先級，并生成新的路徑進入下一輪循環。這樣的循環一直持續到全部粒子都收斂進入穩定狀態。

表1 CarSim詳細參數Tab.1 The Detailed Parameters of CarSim

圖6 Simulink聯合仿真平臺Fig.6 The Co-Simulation Platform for Simulink

在雙車道建模分析過程中，道路通暢，寬度設為3m，附著系數μ=0.75。基于對安全距離的約束，假設兩輛車均為勻速行駛，M1速度為72km/h，拐彎不削減路徑上的速度。M2速度為50km/h，并且在超車過程中車輛方向基本在縱向。反映了優化后的路徑下，M1超車的情況，如圖7、圖8所示。

圖7 換道超車路徑仿真圖Fig.7 Simulation Diagram of Lane Change Overtaking Path

圖8 幾處關鍵節點的超車路徑Fig.8 The Overtaking Path of Several Key Nodes

為了表達清楚，所有圖片都在Y方向2m處繪制虛線表示行車道和超車道的分界線。整體過程的軌跡變化圖，如圖7所示。圖中一種框和另一種框位置重合的部分是處于不同的時間，這一點在圖8的三張圖中表現更加清晰。圖8為在幾處關鍵時間點上的超車情況圖。圖8（a）為超車過渡階段，圖8（b）為超車并行階段，圖8（c）為超車后過渡階段。

角度變化，如圖9所示。Y方向的加速度，其變化幅度最大為±3m/s2＜0.67μg，車輛最大轉角0.3rad，符合車輛動力學，能夠為乘客提供一個舒適的乘車環境，如圖10所示。

圖9 優化路徑的轉角Fig.9 Corner of the Optimized Path

圖10 優化路徑的Y方向加速度Fig.10 Acceleration of the Y-Direction of the Optimized Path

仿真結果表明，通過設計多層粒子群，采用多目標優化的方法得到的規劃路徑是可行的，智能車輛可以在符合運動學，動力學條件下，安全的完成超車任務。

5 結束語

針對自動駕駛智能車輛超車問題，采用多層粒子群加速優化方法規劃出最優路徑。首先，通過對駕駛員超車操作的分析建立超車換道模型，從而得到優化問題的約束條件和目標函數。其次，如果直接采用傳統的粒子群算法，由于初始條件對算法具有一定的影響，存在計算量大，容易陷入局部極小的問題。對此，設計分層結構，采用三角分解和Dijkstras算法確定車輛的可運行空間，為粒子群算法提供了較好的初始條件。在研究的背景中，涉及優化的問題和約束條件比較多，一定程度上提高了算法的復雜程度。針對該問題，通過引入Parote優先規則，可以加快算法的計算速度，降低算法的計算復雜度。最后，Simulink仿真結果表明，粒子群算法計算出的路徑能夠使智能車輛安全、穩定、高效、舒適地完成超車過程，滿足實際需求。

此外，主要考慮了超車車輛和被超車車輛的超車變道方案，理論分析和仿真部分是在比較理想的情況下進行的。下一步，可以討論更加復雜的情況，例如障礙車輛有多個，超車過程需要應急控制，路況不夠理想等問題。