蟻群算法在無人駕駛園區參觀路線的應用

郭蓬 張金煒 戎輝 王文揚 高嵩 何佳

摘 ?要： 針對無人車在中國汽車技術研究中心院區內參觀線路的規劃問題，提出一種基于蟻群算法參觀路線規劃的方法。首先利用柵格搭建環境地圖，然后通過蟻群算法設置始末位置、構造解空間、更新信息素、增加迭代次數、判斷路徑長度，最后輸出最短路線。文中根據參觀要求做出三種不同路徑規劃方案以驗證算法的可行性。

關鍵詞： 無人車; 蟻群算法; 路線規劃; 信息表; 柵格地圖; 最短路線

中圖分類號： TN911.1?34 ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2019）11?0149?04

Abstract： A visit route planning method based on ant colony optimization algorithm is presented to solve the planning problem of the visit route of unmanned vehicle in district of China Automotive Technology and Research Center. The grid is used to construct the environment map， and the ant colony optimization algorithm is used to set the beginning and end positions， construct the solution space， update the pheromones， increase the number of iterations， judge the path length， so as to output the shortest route. Three different schemes are made according to visit requirements， which are used to verify the feasibility of the algorithm

Keywords： unmanned vehicle; ant colony optimization algorithm; route planning; pheromone; grid map; shortest route

0 ?引 ?言

無人車路徑規劃是當前無人駕駛領域的關鍵技術之一。路徑規劃可以分為全局路徑規劃和局部路徑規劃[1]，全局路徑規劃又稱為靜態路徑規劃，它是在環境已知的情況下由初始位置到目標位置尋找一條最優或者近似最優的無碰撞路徑。局部路徑規劃又稱為動態路徑規劃，它是在環境未知的情況下通過感知系統實時感知周圍環境做出局部行駛路線。路徑規劃的算法有很多，大致可以分為五大類：傳統路徑規劃算法（模擬退火法、人工勢場法等）[2]、啟發式搜索算法（Dijkstra算法、A*算法及其變種等）[3]、離散優化算法（模型預測算法、幾何軌線算法等）[4]、隨機采樣算法（隨機路圖法、快速隨機拓展樹法等）[5?6]和智能仿生算法（遺傳算法、蟻群算法、神經網絡等）[7]。

蟻群算法（ACO）是一種模擬進化算法，又稱為螞蟻算法，是由Dorigo等人提出[8]的，主要是仿照螞蟻群體在覓食過程中尋找路徑，即巢與食物之間的最短路徑行為進行路徑規劃。

本文利用基于蟻群算法的無人車在中國汽車技術研究中心院區內規劃參觀路線。首先根據實際需要建立環境地圖，進而選擇初始點和目標點，構造解空間，更新信息素，增加迭代次數，判斷路徑長度，最后輸出最短路線。Matlab仿真實驗證明了本文方法的有效性，可用于院區內參觀路線的路徑規劃。

1 ?問題描述

如圖1所示為中國汽車技術研究中心院區，其橫向長度為534 m，縱向長度為462 m，道路寬14 m，共有19個試驗室，按照參觀規定只開放NVH試驗室、電磁電氣試驗室、零部件試驗室2、性能開放綜合試驗室2、汽車安全試驗室等五個試驗室，圖1中[l]為無人車出發位置，②～⑥為試驗室停車位置，⑦為出口位置。

圖1 ?中國汽車技術研究中心院區

本文根據具體要求，利用蟻群算法給出三種方案，以驗證蟻群算法在院區內規劃參觀路線的可行性。

方案一：驗證蟻群算法是否能夠搜索最短路徑，采用在任意兩個試驗室之間尋找最短行駛路線的方法，以驗證蟻群算法搜索最短路徑的可行性。

方案二：根據參觀要求，在特殊情況下僅開放三個試驗室，磁電氣試驗室、汽車安全試驗室以及零部件試驗室2。利用蟻群算法計算出三個實驗室的參觀順序以及最短路線。

方案三：五個試驗室全部開放，并且規定NVH試驗室為第一個參觀的實驗室，汽車安全試驗室為最后一個參觀的實驗室，利用蟻群算法計算出五個實驗室的參觀順序以及最短路線。

2 ?蟻群算法

螞蟻尋找路徑不是單只螞蟻的行為，而是一個群體性的行為。它們互相協作，每只螞蟻都會在所走的路徑上留下信息素（路徑長度的倒數）[9?10]，當下一只螞蟻路過該路徑時就會利用信息素做出下一步的判斷，并且會釋放出自己的信息素，這樣就形成了信息素的積累[11]，使得后續螞蟻可以選擇信息素強的路徑，隨著大量螞蟻在信息素的作用下不斷搜索路徑，最終會得到一條最優或者次優路徑[12?13]。蟻群算法流程圖如圖2所示。

1） 構造解空間

采用在二維空間內構建解空間的方法，構造柵格地圖，用白色柵格表示可行駛區域，黑色柵格表示障礙物區域，對柵格進行數字標號處理，只有白色柵格才能成為搜索路徑的節點，設置出發點和目標點，然后通過選擇概率公式選擇下一個節點，直至選擇到目標點，這樣所有經過的柵格就組成了解空間。

圖2 ?蟻群算法流程圖

2） 節點選擇

每次迭代有[M]只螞蟻搜索路徑，一共經過[N]次迭代，設置出發點為[S]，目標點為[E]，每只螞蟻選擇下一個節點[j]的方法是：計算當前節點[j]與四周節點[i]之間的選擇概率[Pi，j]，利用選擇概率[Pi，j]選擇下一節點。[Pi，j]的計算方法如下：

式中：[i]代表當前節點的周圍八個節點數字標號集合;[τi，j]為信息素;[ηi，j]為啟發值;[B]為影響因子;[w]表示沒有被選擇點的集合。

3） 信息素更新

通常有兩種信息素更新方法，第一種如式（2）所示，叫做實時信息素更新，即當前螞蟻在路徑搜索中每過一個節點就會對該節點進行信息素更新。本文即采用該方法。

3 ?仿真實驗與驗證

本文將蟻群算法應用于無人車院區參觀路線的規劃中，為驗證本文方法的可行性和有效性，采用Matlab進行大量仿真實驗。算法運行環境如下：Windows7，64 bit;Matlab，R2017a;處理器Intel[?] Xeon[?] CPU E5?1620;主頻3.50 GHz;內存32 GB。

3.1 ?建立仿真環境

針對無人車參觀路線的規劃問題，本文需要根據真實環境搭建環境模型。有兩大類構建環境模型的方法：一是基于網絡或圖的模型方法;二是基于網格的模型方法。如前文所述，蟻群算法利用建立柵格圖的方法，此方法屬于網格模型中的一種。柵格圖法結構簡單、易于實現，是常用的建模方法。

本文建立25×25的柵格地圖，共有625個正方形柵格，按照從左往右、從上到下的順序對柵格進行1～625編號。白色柵格代表道路，黑色柵格代表建筑物。按照院區實際尺寸規劃柵格地圖，因為真實道路寬約20 m，所以設計每單位長度柵格表示實際長度20 m，如圖3所示。

圖3 ?仿真環境圖

3.2 ?仿真實驗一

任意兩個試驗室之間搜索最短路徑。如圖4所示，選擇兩個試驗室，NVH試驗室和性能開發綜合試驗室2。選擇初始點84號柵格，目標點294號柵格，設置80只螞蟻，迭代100次，將搜索出的路徑進行長度比較選擇出最短路徑，如圖中曲線所示為最短路徑。

圖4 ?仿真實驗一

3.3 ?仿真實驗二

三個試驗室之間選擇最短路徑，選擇電磁電氣試驗室、零部件試驗室2以及汽車安全試驗室，在三個試驗室之間經過6種不同組合的仿真實驗，選擇如圖5曲線所示路線，參觀順序為起始點、電磁電氣試驗室、汽車安全試驗室、零部件試驗室2、出口，此順序為參觀這三個試驗室最短行駛路徑，其中1號柵格是無人車起始點，609號柵格是無人車出口位置。

圖5 ?仿真實驗二

3.4 ?仿真實驗3

五個試驗室之間搜索最短路徑，按照規定NVH試驗室第一個參觀，汽車安全試驗室最后一個參觀，所以共有24種不同組合方式，經過仿真驗證，圖6曲線所示為最短行駛路徑。

圖6 ?仿真實驗三

參觀順序為起始點、NVH試驗室、電磁電氣試驗室、零部件試驗室2、汽車安全試驗室、出口。

4 ?結 ?論

本文在院區靜態環境下，利用柵格對無人車在院區的行駛環境創建模型圖，通過蟻群算法規劃出參觀線路，得到以下三種實驗結論：

1） 利用蟻群算法可以得到參觀院區內任意兩個試驗室的最短路線。

2） 在開放三個試驗室的情況下，通過6組實驗可得到正確的參觀順序和最短路徑。

3） 在五個試驗室全部開放的情況下，通過24組實驗可得到正確的參觀順序和最短路徑。

實驗仿真結果證明，蟻群算法可用于中汽中心院區三種參觀需求的全局路徑規劃。后續擬將基于蟻群算法的全局路徑規劃和局部路徑規劃進行結合算法開發并上車進行實際運行。

參考文獻

[1] 孫梅.移動機器人路徑規劃技術綜述[J].山東工業技術，2016（21）：164.

SUN Mei. Overview of path planning technology for mobile robots [J]. Shandong industrial technology， 2016（21）： 164.

[2] 霍鳳財，任偉建，劉東輝.基于改進的人工勢場法的路徑規劃方法研究[J].自動化技術與應用，2016，35（3）：63?67.

HUO Fengcai， ?REN Weijian， LIU Donghui. Research on path planning method based on improved artificial potential field method [J]. Automation technology and application， 2016， 35（3）： 63?67.

[3] ZHANG L， SUN L， ZHANG S， et al. Trajectory planning for an indoor mobile robot using quintic Bezier curves [C]// 2015 IEEE International Conference on Robotics and Biomimetics. Zhuhai： IEEE， 2015： 757?762.

[4] CHU K， LEE M， SUNWOO M. Local path planning for off?road autonomous driving with avoidance of static obstacles [J]. IEEE transactions on intelligent transportation systems， 2012， 13（4）： 1599?1616.

[5] 余卓平，李奕姍，熊璐.無人車運動規劃算法綜述[J].同濟大學學報（自然科學版），2017，45（8）：1150?1159.

YU Zhuoping， LI Yishan， XIONG Lu. Unmanned vehicle motion planning algorithm review [J]. Journal of Tongji University （Natural Science Edition）， 2017， 45（8）： 1150?1159.

[6] 孫豐財，張亞楠，史旭華.改進的快速擴展隨機樹路徑規劃算法[J].傳感器與微系統，2017，36（9）：129?131.

SUN Fengcai， ZHANG Yanan， SHI Xuhua. Improved rapid expansion of random tree path planning algorithm [J]. Transducer and microsystem technologies， 2017， 36（9）： 129?131.

[7] 于樹科，瞿國慶，祁宏宇，等.蟻群遺傳融合算法在移動機器人路徑規劃中的應用[J].火力與指揮控制，2017，42（12）：88?91.

YU Shuke， QU Guoqing， QI Hongyu， et al. Application of ant colony genetic fusion algorithm in mobile robot path planning [J]. Fire control and command control， 2017， 42（12）： 88?91.

[8] 王志中.基于改進蟻群算法的移動機器人路徑規劃研究[J].機械設計與制造，2018（1）：242?244.

WANG Zhizhong. Based on improved ant colony algorithm for mobile robot path planning study [J]. Journal of mechanical design and manufacturing， 2018（1）： 242?244.

[9] HASSAN S， YOON J. Virtual maintenance system with a two?staged ant colony optimization algorithm [C]// 2011 IEEE International Conference on Robotic and Automation. Shanghai： IEEE， 2011： 931?936.

[10] DENG Yan， HU Hongyu， TIAN Xiaolu， et al. A path planning method for substation laser inspection robot based on improved ant colony algorithm [C]// The 2nd International Conference on Computer Engineering， Information Science & Application Technology. [S.l.]： Atlantis Press， 2017： 62?69.

[11] ESCARIO J B， JIMENEZ J F， GIRON?SIERRA J M. Ant co?lony extended： experiments on the traveling salesman problem [J]. Expert systems with applications，2015， 42： 390?410.

[12] ERIN B， ABIYEV R， IBRAHIM D. Teaching robot navigation in the presence of obstacles using a computer simulation program [J]. Procedia： social and behacioral sciences， 2010， 2（2）： 565?571.

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

SHI Enxiu， CHEN Minmin， LI Jun， et al. Study on global path planning for mobile robot based on ant colony algorithm [J]. Transactions of the Chinese society of agricultural machi?nery， 2014， 45（6）： 53?57.

[14] 胡玉文.城市環境中基于混合地圖的智能車輛定位方法研究[D].北京：北京理工大學，2014.

HU Yuwen. Hybrid map based localization method for unmanned ground vehicle in urban scenario [D]. Beijing： Beijing Institute of Technology， 2014.