改進自適應蟻群的城市道路智能車路徑優化

裴文鑫 孫寧 馬健霄

摘 要：為優化城市道路中智能車輛規劃路徑的長度與轉折次數，本文提出一種改進的自適應蟻群算法。以柵格法對城市道路環境網格化處理，以路徑最短、轉折次數最少為優化目標函數，改進鄰域搜索范圍，將8鄰域擴大為24鄰域，利用啟發函數更新初始信息素，動態調整信息素揮發系數，并提出返回上一步的死鎖策略，最后考慮曲率限制，以三次B樣條曲線法（B-spline curve）平滑優化處理。此研究表明，在隨機生成的城市環境地圖模型下，該算法較標準蟻群算法與自適應算法，路徑長度分別縮短3.89%、8.38%，路徑節點分別減少28%、24.2%，收斂次數分別減少37.5%、20%。此研究結果為城市道路智能車輛路徑優化提供較好的理論依據。

關鍵詞：智能車輛;城市道路;自適應蟻群算法;鄰域搜索;B條曲線法;路徑優化

中圖分類號：U463;TP18;S77??? 文獻標識碼：A?? 文章編號：1006-8023（2022）01-0152-07

Improved Adaptive Ant Colony-based Urban Road Smart

Car Path Optimization

PEI Wenxin， SUN Ning*， MA Jianxiao

（College of Automobile and Traffic Engineering， Nanjing Forestry University， Nanjing 210037， China）

Abstract：In order to optimize the length and number of turns of intelligent vehicle planning paths in urban roads， this paper proposes an improved adaptive ant colony algorithm. The raster method is used to grid the urban road environment， the shortest path and the least number of turns are used as the optimization objective function， the neighborhood search range is improved， the 8 neighborhood is expanded to 24 neighborhoods， the initial pheromone is updated using a heuristic function， the pheromone volatility coefficient is dynamically adjusted， and a deadlock strategy of returning to the previous step is proposed， and finally the curvature limitation is considered and the three-time B-spline curve method is used to process smoothing optimization. This study shows that the algorithm reduces the path length by 3.89% and 8.38%， the path nodes by 28% and 24.2%， and the number of convergence by 37.5% and 20%， respectively， compared with the standard ACO and the adaptive algorithm under the randomly generated urban environment map model. The results of this study provide a good theoretical basis for the optimization of intelligent vehicle paths on urban roads.

Keywords：Smart vehicle; city road; adaptive ant colony algorithm; neighborhood search; B-spline curve;? path optimization

0 引言

城市道路下智能車輛的路徑規劃算法是當前無人駕駛領域的研究熱點，而算法的優劣將直接影響著車輛的通行能力[1-3]。以迪杰斯特拉（Dijkstra）算法[4-5]、A*（A-Star）算法[6]為代表的傳統路徑算法，搜索效率低、易陷入局部最優，很難應用于空間復雜度較高的城市道路[7]，且受鄰域搜索限制、求解路徑的節點及轉折數較多。

目前國內外學者對模擬退火算法[8]、遺傳算法[9]、粒子群算法[10-11]等為代表的智能仿生算法方面做了大量研究，該類算法通過模仿生物行為規律的算法，具有自我學習與更新的優點，但在復雜環境中依然存在算法性能的缺陷。而蟻群算法[12-13]是一種模擬螞蟻覓食行為的啟發算法，因其魯棒性強、易于與其他算法結合等優點而被廣泛應用。文獻[14-16]通過改進蟻群算法來實現路徑上的規劃，雖提高了算法的性能，但不能從根本上優化路徑，因此，本文提出一種新的自適應蟻群算法，以最短路徑長度與最少轉折次數為優化目標，改進鄰域搜索范圍、初始信息素與信息揮發系數，提升算法的性能。

對于路徑平滑處理，文獻[17-18]分別采用二次優化與刪除中間節點的方法，雖有較好的平滑效果，但不能直接作為智能車輛的行駛路徑。故本文采用B（B-spline curve）樣條曲線平滑處理[19]，考慮車輛非完整約束，使其滿足智能車輛轉向穩定性及速度和加速度連續性的要求。

1 數學模型

1.1 城市道路環境建模

本文采用廣泛應用于路徑規劃的柵格法，對城市道路環境建模，將城市道路環境簡化為網格地圖。如圖1所示。以4×4柵格環境矩陣G為例，柵格地圖由柵格環境矩陣G生成，白色柵格為可行駛區域，即G（m，n）=0，黑色柵格表示被城市建筑、綠化帶、車輛等占用的區域，即G（m，n）=1，m、n分別表示矩陣行、列數。

在二維平面上，每個柵格坐標在正交參考系中計算，假設整個柵格用整數標記，長度等于坐標的單位長度，就可以得到以下坐標，表示為：

xi=mod（i，Nx）-0.5yj=mod（j，Ny）-0.5。（1）

式中：i、j分別表示為每行每列柵格序號;Nx、Ny為柵格地圖每行每列的柵格數;mod為余數運算。

1.2 問題描述

城市道路中智能車輛的路徑長度、轉折次數是反映車輛的通行能力的重要指標。因此，可以通過優化路徑長度與轉折次數，提高車輛的通行能力。

1.2.1 最短路徑長度

路徑長度決定車輛的通行能力，路徑越短，車輛通過能力越好，因此定義行駛路徑總長度W目標函數為：

minW=∑Nn=1dnij。（2）

式中：dnij為在第n步時位置i與j之間的步長;N為總步數。

1.2.2 最少轉折次數

路徑轉折次數決定車輛通行的穩定性，規劃的轉折次數越少車輛越穩定，因此定義路徑總累計轉折次數P目標函數為：

minP=∑n-1n=0（dn+1-dn）。? （3）

dn+1-dn=0，1，n=0或kn=kn+1kn≠kn+1。 （4）

式中：dn+1-dn為在第n與n+1步時的轉折次數，kn、kn+1分別為第n、n+1步時路徑的斜率。

1.2.3 總目標優化函數

將最短路徑和最少轉折次數作為總目標優化，在保證路徑最短的同時，有較少的轉折次數，從而提高車輛的通行能力。

minZ（n）=ξ1∑Nn=1dnij+ξ2∑n-1n=0（dn+1-dn）。（5）

式中：Z（n）為總目標函數;ξ1、ξ2為路徑長度和轉折次數的權重。

2 改進的蟻群算法

針對標準蟻群算法（Ant Colony Optimization，ACO）求解路徑的節點及轉折數較多，且搜索能力與收斂能力不足，做出如下改進：擴大搜索鄰域范圍，采用A*算法的最短路徑全局總代價更新初始蟻群信息素，動態調整信息素揮發系數。

2.1 擴大領域搜索范圍

標準蟻群算法中可以沿8個方向轉移到相鄰的柵格，如圖2（a）所示。相鄰2個搜索方向的夾角為45°，步長為1、2。在該鄰域搜索范圍下，規劃出的路徑節點較多且轉折次數多，因此，標準蟻群算法所得路徑實際上不是最短的。

針對上述問題，對節點搜索鄰域范圍改進，如圖2（b）所示，在保留當前節點鄰域的8個節點為算法的擴展節點的同時，還將當前節點次鄰域的16個節點也納入擴展節點，此時算法搜索鄰域節點的個數將擴大到24，節點移動的方向也增加到16個方向，步長為1、2、2、5、22可供選擇，擴大鄰域搜索的范圍。

2.2 自適應蟻群初始信息素

A*算法有避免盲目搜索，提高搜索效率的優點，本文改進算法利用A*算法最短路徑得到總代價更新蟻群初始信息素。

A*算法的啟發式函數用估計函數表示，公式為：

f（n）=h（n）+g（n）。（6）

式中：h（n）是當前位置到目標位置的代價;g（n）是初始位置到當前位置的代價。

根據A*啟發函數得到的最短路徑的總代價Cf，將全局引導的蟻群初始信息素設置為：

τ=Q1Cf。（7）

式中：Q1是比例系數，反復實驗選取為0.002;τ為蟻群初始信息素。

2.3 自適應信息素揮發系數

標準蟻群算法的信息素揮發系數（ρ）是小于1的常量。當ρ偏大時，路徑被再次選擇的可能性較大，易出現局部收斂;當ρ偏小時，算法的搜索能力提高，但收斂的速度降低[20]。因此，在算法搜索前期，需要較大的ρ，快速找到優勢路徑;而在算法搜索后期，需要較小的ρ，擴大全局搜索能力。故本文提出改進的信息ρ與迭代次數u的高斯函數變化關系見公式（8）。

ρ（u）=Ce-（u75）2。 （8）

式中：C為比例系數，經過多次實驗，比例系數選取0.5。

2.4 死鎖策略

當螞蟻搜索最優路徑時，可能會出現死鎖現象，使得螞蟻在柵格中無法執行下一步動作。針對死鎖現象，提出當螞蟻無法找到起始柵格以外的其他柵格時，可以回到上一柵格位置，并將當前位置從可行柵格剔除，視為障礙柵格，避免出現死鎖現象。

2.5 蟻群算法參數校驗

啟發式因子α、β，是螞蟻進行路徑搜索的重要程度指標，取值直接影響轉移概率，信息素啟發因子越大，信息素所占比重就越大，從而使得后面螞蟻放棄新路徑的搜索;而信息素過少時，則無法找到全局最優解，因此需要對其進行參數檢驗。本文實驗：選取迭代次數K=100;螞蟻數量M=50，將α、β分別設置1、2、3、…、10，分別在2種不同環境復雜度下進行仿真。

信息素啟發因子對最優路徑長度與迭代次數的影響曲線如圖3和圖4所示。

由圖3和圖4可見，在2種仿真環境下，當啟發式因子α增大時，最短路徑長度曲線整體均呈現增大、發散趨勢，收斂次數曲線整體均呈現下降趨勢，綜合分析：當啟發式因子α增大時，螞蟻難以得到全局最優路徑，因此α最佳取值范圍為[1，2]。而當啟發式因子β增大時，最短路徑的長度逐漸減少，迭代次數也逐漸減少，綜合分析：考慮到啟發式因子β過大時，會使螞蟻在某個局部節點上選擇最短路徑，因此β最佳取值范圍為[7，8]。

3 路徑優化處理

改進的自適應蟻群算法在搜索最短路徑的過程中，因避開障礙物產生較多的轉折角，故不能直接當作車輛的行駛路徑[21-22]。而三次B樣條曲線在節點處二階連續，可滿足自動駕駛車輛的速度和加速度連續性要求，因此，本文采用三次B樣條曲線對路徑節點平滑處理。

三次B樣條曲線表達式為：

p（t）=∑3i=0piG1，3（t）。?? （9）

式中：Gi，3（t）稱為基函數。

基函數表示為：

G0，3（t）=16（-t3+3t2-3t+1）

G1，3（t）=16（3t3+6t2+4）

G2，3（t）=16（-3t3+3t2+3t+1）

G3，3（t）=16t3??????? 。 （10）

將公式（10）帶入公式（9）得到曲線段P0，3（t）為：

P0，3（t）=161tt2t3T1410-30303-630-13-31P0P1P2P3，t∈[0，1]。（11）

由于智能車輛是非完整約束，三次B樣條處理的路徑曲率必須滿足車輛的約束：κ≤tanδL，δ為前輪擺角，L為軸距。

4 仿真實驗

利用MATLAB進行仿真實驗，在不同復雜程度、規模大小的城市道路環境模型下，將本文改進自適應蟻群算法與其他算法比較實驗。由于城市道路是動態的，不能直觀體現改進算法的性能，因此本文將選取某一時刻下的城市道路環境進行仿真實驗。經初步實驗，在柵格地圖中，Nx=20，Ny=20，初始點坐標為xi=0.5，yj=19.5，目標點坐標為xi=19.5，yj=0.5，改進蟻群的參數設置：迭代次數K=100;螞蟻數量M=50;選取信息素重要性因子α為1.5;選取啟發式重要性因子β為7;初始信息素的比例系數C=0.5;信息素揮發系數的比例系數Q1=0.002。

4.1 城市道路環境模型下算法比較

在由環境矩陣G生成柵格環境地圖，選取標準蟻群算法，該算法環境為復雜的城市道路環境模型，其運行結果與本文改進算法路徑對比，如圖5所示。其次，選取自適應蟻群算法，該算法環境為簡單城市道路環境模型，其運行結果與本文改進算法路徑對比，如圖6所示。

最優路徑與收斂代數是衡量蟻群算法的2個重要指標，將算法均獨立運行20次，比較仿真結果，見表1。改進的算法中將A*算法啟發式函數與蟻群算法初始信息素相結合，動態的更新信息素揮發系數，使得算法具有更高的搜索能力和更快的收斂速度。較標準蟻群算法最小收斂代數平均值減少37.5%，較自適應蟻群算法最小收斂代數平均值減少20%;擴大蟻群算法中搜索鄰域搜索范圍，有效地縮短路徑的長度。較標準蟻群算法最優路徑縮短3.89%，比較自適應蟻群算法最優路徑縮短8.37%。改進的蟻群算法中路徑節點較標準蟻群算法減少28%，較自適應蟻群算法減少24.2%，由圖5和圖6可直觀看出路徑轉折次數減少，路面更加平緩。

4.2 平滑實驗

采用三次B樣條曲線平滑處理改進蟻群算法的最優路徑，仿真結果如圖7所示。可見，采用三次B樣條處理后的路徑轉折角度進一步減少，路徑整體更加平滑，滿足智能車輛速度與加速度連續性的要求，保證車輛平穩運行。

5 結論

為了優化城市道路中智能車輛的路徑，提出改進的自適應蟻群算法，得出以下結論。

（1）通過優化目標函數，改進領域搜索范圍，能有效縮短路徑長度及轉折數，提高智能車輛的通行能力。

（2）改進蟻群初始信息素和信息揮發系數，加快全局搜索能力和收斂速度，提高智能車輛的實時性。

（3）采用B樣條曲線平滑處理所得路徑，保證智能車輛轉向的穩定性及安全性。

改進算法雖較好地降低收斂代數，但受鄰域搜索方式影響，前期最短路徑長度較長，因此，可對該方面不足繼續深入研究。

【參 考 文 獻】

[1]丁柏群，姜瑾.基于蟻群算法和動態路阻的物流配送路徑優化[J].森林工程，2014，30（2）：149-152.

DING B Q， JIANG J. Path optimization of logistics distribution vehicle based on ant colony algorithm and dynamic road impedance[J]. Forest Engineering， 2014， 30（2）： 149-152.

[2]肖廣兵，王藍儀，孫寧，等.基于車路協同的地下停車場車輛定位算法發散性研究[J].計算機應用研究，2021，38（2）：530-533.

XIAO G B， WANG L Y， SUN N， et al. Divergence of cooperative vehicle localization in underground parking lots[J]. Application Research of Computers， 2021， 38（2）： 530-533.

[3]XIAO G B， ZHANG H B， SUN N， et al. Cooperative link scheduling for RSU-assisted dissemination of basic safety messages[J]. Wireless Networks， 2021， 27（2）： 1335-1351.

[4]湯紅杰，王鼎，皇攀凌，等.優化dijkstra算法在工廠內物流AGV路徑規劃的研究[J].機械設計與制造，2018（S1）：117-120.

TANG H J， WANG D， HUANG P L， et al. AGV path planning based on optimized dijkstra algorithm in logistics factory[J]. Machinery Design & Manufacture， 2018（S1）： 117-120.

[5]鄭琰，黃興，潘穎.城市應急物流中心多目標選址模型及方法研究[J].重慶理工大學學報（自然科學），2020，34（6）：239-246.

ZHENG Y， HUANG X， PAN Y. Research on the multi-objective facility location model for urban emergency logistics centers[J]. Journal of Chongqing University of Technology （Natural Science）， 2020， 34（6）： 239-246.

[6]宋宇，王志明.改進A星算法移動機器人路徑規劃[J].長春工業大學學報，2019，40（2）：138-141.

SONG Y， WANG Z M. Path planning simulation based on improved A star algorithm[J]. Journal of Changchun University of Technology， 2019， 40（2）： 138-141.

[7]楊艷艷，馬成林，王怡菲，等.基于禁忌搜索帶時間窗與車載約束的配送路線研究[J].森林工程，2018，34（3）：100-106.

YANG Y Y， MA C L， WANG Y F， et al. Research on distribution route with time window and on-board constraint based on tabu algorithm[J]. Forest Engineering， 2018， 34（3）： 100-106.

[8]袁佳泉，李勝，吳益飛，等.基于模擬退火蟻群算法的機器人路徑規劃方法[J].計算機仿真，2019，36（10）：329-333.

YUAN J Q， LI S， WU Y F， et al. Robot path planning method based on simulated annealing ant colony algorithm[J]. Computer Simulation， 2019， 36（10）： 329-333.

[9]《中國公路學報》編輯部.中國汽車工程學術研究綜述·2017[J].中國公路學報，2017，30（6）：1-197.

Editorial Department of China Journal of Highway and Transport. Review on Chinas automotive engineering research progress： 2017[J]. China Journal of Highway and Transport， 2017， 30（6）： 1-197.

[10]鄧高峰，張雪萍，劉彥萍.一種障礙環境下機器人路徑規劃的蟻群粒子群算法[J].控制理論與應用，2009，26（8）：879-883.

DENG G F， ZHANG X P， LIU Y P. Ant colony optimization and particle swarm optimization for robot-path planning in obstacle environment[J]. Control Theory & Applications， 2009， 26（8）： 879-883.

[11]周文璐，林萍，徐曉美，等.黃麻纖維氈吸聲特性及其在汽車上的應用[J].林業工程學報，2021，6（3）：113-119.

ZHOU W L， LIN P， XU X M， et al. Sound absorption characteristics of the jute fiber felt and its application in automobiles[J]. Journal of Forestry Engineering， 2021， 6（3）： 113-119.

[12]RESHAMWALA A， DEEPIKA P. Robot path planning using an ant colony optimization approach： a survey[J]. International Journal of Advanced Research in Artificial Intelligence， 2013， 2（3）：65-71.

[13]李燕，季建楠，沈葭櫟，等.基于改進蟻群算法的移動機器人路徑規劃方法[J].南京信息工程大學學報（自然科學版），2021，13（3）：298-303.

LI Y， JI J N， SHEN J L， et al. Mobile robot path planning based on improved ant colony algorithm[J]. Journal of Nanjing University of Information Science & Technology （Natural Science Edition）， 2021， 13（3）： 298-303.

[14]趙靜，湯云峰，蔣國平，等.基于改進蟻群算法的移動機器人路徑規劃[J].南京郵電大學學報（自然科學版），2019，39（6）：73-78.

ZHAO J， TANG Y F， JIANG G P， et al. Mobile robot path planning based on improved ant colony algorithm[J]. Journal of Nanjing University of Posts and Telecommunications （Natural Science Edition）， 2019， 39（6）： 73-78.

[15]徐玉瓊，婁柯，李婷婷，等.改進自適應蟻群算法的移動機器人路徑規劃[J].電子測量與儀器學報，2019，33（10）：89-95.

XU Y Q， LOU K， LI T T， et al. Path planning of mobile robot based on improved adaptive ant colony algorithm[J]. Journal of Electronic Measurement and Instrumentation， 2019， 33（10）： 89-95.

[16]辜勇，段晶晶，蘇宇霞，等.基于改進蟻群算法的倉儲物流機器人路徑規劃[J].武漢理工大學學報（交通科學與工程版），2020，44（4）：688-693，697.

GU Y， DUAN J J， SU Y X， et al. Path planning of warehouse logistics robot based on improved ant colony algorithm[J]. Journal of Wuhan University of Technology （Transportation Science & Engineering）， 2020， 44（4）： 688-693， 697.

[17]趙曉，王錚，黃程侃，等.基于改進A*算法的移動機器人路徑規劃[J].機器人，2018，40（6）：903-910.

ZHAO X， WANG Z， HUANG C K， et al. Mobile robot path planning based on an improved A* algorithm[J]. Robot， 2018， 40（6）： 903-910.

[18]周兵，萬希，吳曉建，等.緊急避撞工況下的路徑規劃與跟蹤[J].湖南大學學報（自然科學版），2020，47（10）：10-18.

ZHOU B， WAN X， WU X J， et al. Path planning and tracking in scenario of emergency collision avoidance[J]. Journal of Hunan University （Natural Sciences）， 2020， 47（10）： 10-18.

[19]史恩秀，陳敏敏，李俊，等.基于蟻群算法的移動機器人全局路徑規劃方法研究[J].農業機械學報，2014，45（6）：53-57.

SHI E X， CHEN M M， LI J， et al. Research on method of global path-planning for mobile robot based on ant-colony algorithm[J]. Transactions of the Chinese Society for Agricultural Machinery， 2014， 45（6）： 53-57.

[20]李冰林，徐曉美，呂立亞，等.基于分數階微積分的爆胎汽車橫向穩定性控制[J].安全與環境學報，2018，18（6）：2219-2224.

LI B L， XU X M， LYU L Y， et al. On the lateral stability control of a blownout vehicle based on the fractional calculus[J]. Journal of Safety and Environment， 2018， 18（6）： 2219-2224.

[21]張磊，徐曉美，潘健，等.半掛汽車列車高速側傾穩定性控制研究[J].制造業自動化，2019，41（12）：99-102.

ZHANG L， XU X M， PAN J， et al. Roll stability control of the truck semi-trailer at high speed[J]. Manufacturing Automation， 2019， 41（12）： 99-102.